无线单跳网络中的高效低时延网络编码算法

Efficient low-delay algorithm for network coding in wireless single-hop networks

为了提高当前无线网络广播重传的效率,针对效用值排序(sort by utility,SBU)算法存在的搜索数据分组参与编码时效率较低的问题,提出了适用于无线单跳网络的倒序搜索网络编码(reverse search based network coding,RSNC)算法和二分搜索网络编码(binary search based network coding,BSNC)算法。通过降低因效用值之和大于接收节点数而不能编码的概率来提高搜索数据分组参与编码的效率,并且采用分组冲突检测机制(packet collision de-tection,PCD)快速地确定是否可以进行编码包生成。理论分析论证了RSNC和BSNC算法能有效地降低分组冲突概率;仿真结果表明,RSNC和BSNC与SBU算法相比,在编码增益保持不变的前提下能够有效地减少分组判断次数,提高编码搜索效率,降低数据分组的平均端到端时延。

For improving the broadcasting transmission efficiency of current wireless networks and aiming at the problem of low searching efficiency of Sort-By-Utility,Reverse Search based Network Coding（RSNC）and Binary Search based Network Coding（BSNC）were proposed based on the model of wireless single-hop networks.They improve the searching efficiency through reducing the probability of the total of utility that is greater than the number of receiving nodes.The mechanism of Packet Collision Detection（PCD）propounded in this paper is used by the two algorithms for detecting whether two packets are conflicting to define the combining of these packets.Theoretical analysis reveals that RSNC and BSNC can reduce the probability of packets collision.Simulation results indicate that these two algorithms can effectively reduce the transmission delay and improve the efficiency of searching on the premise of keeping the encoding gain compared with Sort-By-Utility in the different model of wireless networks.