非完全无线报文重传分析研究及其分治策略

Analysis on Imperfect Wireless Packet Retransmission Problems and Its Divide-and-Conquer Based Scheme

网络编码为无线网络报文重传问题WPRTPs(Wireless Packet ReTransmission Problems)提供了有效解决途径.现有关于WPRTP问题的研究主要针对完全无线网络报文重传问题P-WPRTPs(Perfect WPRTPs),而尚未发现对非完全无线网络报文重传问题IP-WPRTPs(ImPerfect WPRTPs)的专门研究.本文研究了IP-WPRTP问题,证明了无线报文重传问题的归约定理,分析了IP-WPRTP问题最优线性网络编码报文重传策略中报文重传数量的上限和下限.然后利用分治思想提出了IP-WPRTP问题网络编码策略IP-WPRTP-DC(Divide and Conquer based scheme for IP-WPRTPs).仿真测试表明IP-WPRTP-DC相对于传统非网络编码策略明显节省了报文传输数量.

NC（Network Coding） provides an interesting approach to WPRTPs（Wireless Packet ReTransmission Problems） in wireless networks.Existing researches are mostly focused on P-WPRTPs（Perfect WPRTPs） where,for one receiver,a packet is either being requested by or already known to it.Contrastively,no previous efforts focus on IP-WPRTPs（ImPerfect WPRTPs） where,for one receiver,a packet can be neither being requested by nor already known to it.In this paper,we focus on IP-WPRTPs.WPRTP reduction theorem for simplifying WPRTPs is proposed and proved at First.Then,the upper and lower bounds of the number of packet transmissions in optimal linear NC-based solutions to IP-WPRTPs are analyzed.Next,a scheme named as IP-WPRTP-DC（Divide and Conquer based scheme for IP-WPRTPs） is proposed based on WPRTP reduction theorem using a divide and conquer approach.Extensive simulations showed that IP-WPRTP-DC is more effective in saving the number of packet transmissions for solving IP-WPRTPs than traditional schemes not using network coding.