高损耗无线网络中基于网络编码的广播重传策略

肖  潇，杨路明，王伟平

(中南大学 信息科学与工程学院，湖南 长沙，410083)

摘 要：

摘  要：利用网络编码减少无线传输信息量的原理，结合高损耗无线广播丢包特点，提出多接收节点情况下网络编码组合重传的方法，给出基于网络编码的高损耗无线网络广播重传策略。通过对广播节点保存的信息接收情况矩阵进行丢失概率排序得到新的接收情况矩阵，再按照基于网络编码的多节点编码组合定理寻找满足可解性条件的丢失包组合。对于广播节点，将丢失包组合存入发送序列，进行编码组合，广播发送；对于接收节点，得到编码组合包，进行解码操作，解出丢失包。理论分析结果表明：策略中的编码信息包在所有接收节点具有可解性，可以达到重传目的。模拟测试表明：不同的节点丢包率和广播接收节点数目下，与逐个重传的策略相比，发送次数显著减少。尽管节点需要更大的计算能力，但是可以接受，策略可行。

关键词：

高损耗无线网络；无线广播；网络编码；重传策略；

中图分类号：TP393         文献标识码：A         文章编号：1672-7207(2008)06-1291-05

High loss wireless broadcasting retransmission scheme based on network coding

XIAO Xiao, YANG Lu-ming, WANG Wei-ping

(School of Information Science and Engineering, Central South University, Changsha 410083, China)

Abstract: Based on the physical-layer broadcasting property offered by the wireless medium, the number of transmissions was saved in the packets transmits by network coding. Combined with the drop feature of high loss wireless broadcasting, a novel retransmission scheme in high loss wireless broadcasting based on network coding was presented. Retransmission packet lists were generated based on the probability of information packets, and then information packets were coding combined using network coding theory. In broadcasting nodes, packets were collected and sent; in received nodes, combined packets were decoded and got the lost packets. The theoretic analysis shows that the approach ensures the solvability in the received nodes and achieves retransmission. The simulation results indicate that comparing with traditional scheme, the scheme effectively reduces the average number of transmissions. The greater computing abilities are required than the original approach, but the overhead is reasonable and the approach is effective.

Key words: high loss wireless network; wireless broadcasting; network coding; retransmission scheme

传输损耗较严重的情况下(如恶劣环境下布置的无线传感器网络)，广播操作传输错误率较高，必须使用重传策略来进行错误处理^[1]。普通重传策略的思想基于：发送方通过反馈得到接收方的出错情况，重传出错的数据报文以恢复出错的报文^[2]。然而，在高损耗无线网络广播中应用普通重传策略，较高的比特出错率会产生2个方面的问题：一方面，广播传输中丢失信息包较多，需要数量较大的重传次数；另一方面，重传信息包再次丢失概率较高，需要数量较大的再次重传次数。因此，如何利用现有的网络资源来提高重传效率成为研究的热点之一^[3-5]。

2000年，Ahlswede等基于网络信息流的概念提出了网络编码的思想^[6]，其实质来自于图论中的Max-flow Min-cut(最大流最小割)理论。网络编码是指网络节点既实现路由功能又实现编码功能，通过允许对来自不同链路的信息进行编码组合，从而提高网络性能^[7-9]。利用无线传输信道的广播特性，网络编码被应用于提高无线网络性能，用于提高网络吞吐量、能量利用效率、安全性^[10-12]。同时，网络编码思想也为无线重传性能改善提供了一种新的途径。2006年，Nguyen等^[13]针对2个接收节点广播情况，将网络编码技术和重传相结合提出了2种策略：基于时间重传策略和改进型基于时间重传策略，用来减少传输次数。

但Nguyen等^[13]的策略只针对2个接收节点的情况且没有考虑传输损耗影响。在此，本文作者将网络编码技术和重传的结合推广到多个节点的情况，利用网络编码减少无线传输信息量的特点，针对高损耗无线网络广播重传问题，提出一种基于网络编码的重传策略。其基本思想是在传输损耗较严重的情况下，将网络编码技术和无线广播重传相结合，在1次重传中编码组合多个丢失包，然后广播发送，接收节点接收到编码包后通过解码恢复其丢失信息包数据，减少重传次数，提高传输效率。

1  网络编码减少无线传输信息量基本原理

图1所示为传统方法和网络编码改善无线网络性能、减少无线传输信息量的例子，节点a和c通过节点b进行信息互换。对于传统方法，首先，节点a和c分别传输信息X_a和X_b到节点b。中间节点b分别广播信息X_a和X_b，完成信息互换需要传输4次。而使用网络编码的方法，中间节点b对X_a和X_b进行编码组合得到X_aX_b，然后，广播X_aX_b。由于节点a和节点c分别有信息X_a和X_b，通过异或操作，节点a和c可以解出X_b和X_a，完成信息互换只需要传输3次。相对于传统方法，使用网络编码的方法减少了传输次数，可以有效地提高无线网络性能。

(a) 传统方法信息互换；(b)基于网络编码方法信息互换

图1  传统方法和基于网络编码方法的信息互换比较

Fig.1  Information exchange between conventional approach and network coding

2  传输损耗较严重情况下基于网络编码的广播重传策略

分析重传方法需要一个接近现实环境的模型。假设一个具有1个广播源节点和N(N＞2)个接收节点的无线广播网络，传输损耗较严重 ，损耗率大于50%。

假设1  所有数据均通过信息包来传输。广播源节点以固定间隔时间(?t)广播信息包，N个接收节点传输丢包率互不相关，且服从伯努利分布，对应某个接收节点i的丢包率为P_i。

假设2  广播源节点能获得接收节点信息包丢失情况：a. 信息包是否丢失；b. 丢失信息包序列号和丢失节点序列号。节点丢失情况的获得通过ACK/NACKs来完成，假定ACK/NACKs不存在损耗。

假设3  广播源节点存在一个信息包接收情况矩阵，丢失情况记录在该矩阵中，矩阵中行表示接收节点接收情况，列表示信息包接收情况。如果某个信息包在某个接收节点成功接收，矩阵相应位置赋值为0；若丢失，相应位置赋值为1。

2.1  基于网络编码广播重传策略基本思想

基于网络编码的重传策略针对高损耗无线网络广播，针对多个接收节点，编码组合不同的丢失包来进行重传，减少重传发送次数。图2所示为5个接收节点10个传输信息包的示例。

由图2(a)可以看出，在5个接收节点10个信息包广播传输过程中，共发生25次丢失，丢包率为50%。在假定重传包不损耗的情况下，应用普通重传策略，需要重传所有的10个信息包。

(a) 5个接收节点接收情况；(b) 基于网络编码重传策略组合情况

图2  基于网络编码的重传策略示例

Fig.2  Example of retransmission scheme with network coding

在该例中，应用基于网络编码的重传策略，可以计算得到，，，7，，将结果重传。这样，节点R₁通过()2可以解出丢失包1；通过()3可以解出丢失包4；通过()5可以解出丢失包6；通过()()可以解出丢失包8，网络编码包在节点R₁具有可解性，R₁可以解出其丢失信息包。同理，在节点R₂，R₃，R₄和R₅网络编码包也具有可解性。在该例中，所有接收节点可以解出丢失信息包，达到重传目的。

图2(b)所示为基于网络编码重传策略的组合情况，在假定重传包不损耗的情况下，基于网络编码的重传策略只需要重传5个信息包，与普通重传策略相比，有效地减少了重传发送次数。

2.2  基于网络编码的多接收节点编码组合定理

由前面的基本思想可以看出，重传中编码组合包在所有接收节点可解才可达到重传目的。这里给出多个接收节点(N＞2)情况下编码组合定理。

定理1  设广播接收节点个数为N，若其中n   (n≤N)个接收节点丢失某个信息包，而另外N-n个节点丢失另外多个信息包，且这些信息包的信息包接收情况子矩阵中每行当且仅有1个信息包丢失。则在重传时，应用网络编码技术编码组合这几个信息包，在所有接收节点具有可解性。

证明  接收节点个数为N，假设在n(n≤N)个节点丢失信息包为A₁，而另外N-n个节点丢失信息包为A₂，A₃，…，A_s (s≤λ)。广播组合包到所有节点。对于某个丢失信息包为A_i的节点，由于缓存子矩阵中每一行当且仅有1个信息包丢失，即该节点除了A_i信息包，其他信息包成功接收。对应有：

。     (1)

即每个节点可以解出所需重传信息包。应用网络编码技术组合这几个信息包，在接收节点具有可解性。

图3所示为图2(b)中信息包组合1和2以及信息包组合8，9和10的接收情况子矩阵，由定理1可判定这二组信息包满足可解性条件，可以达到重传目的。

(a) 信息包1和2接收情况子矩阵；(b) 信息包8，9和10接收情况子矩阵

图3  接收情况子矩阵示例

Fig.3  Example of received status submatrix

2.3  应用网络编码的重传再丢失处理

提高重传效率的另一个重要方面是处理高传输损耗带来的重传再丢失问题。图4所示为应用网络编码重传再丢失处理的示例。在图4(a)中，应用普通重传策略发送信息包1，在丢包率为50%的情况下，重传包被2个丢失节点顺利接收需重传发送2.67次，其中再丢失重传次数为1.67次，消耗较大的资源。

基于网络编码的特点，可以采用完全不同于普通重传策略的再丢失处理思想：若重传中出现再丢失情况，重传发送不再重复发送原包，而是参照当前丢失情况编码新包发送。

在图4(a)中，对于信息包1和2，初始状态编码丢失包重传发送，若重传中在R₂和R₅节点丢失，丢失后最新的接收情况如图4(b)所示。此时，本例中，应用网络编码的特点，重传再丢失处理不再重复发送，而是参照最新丢失情况发送，新的重传包可以实现重传再丢失处理，同时又进行了新的重传发送。应用网络编码的重传再丢失处理参照接收情况动态的组合重传包，相比起普通重传策略的再丢失处理，可以有效地减少再次重传次数，提高传输效率。

(a) 初始状态信息包1和2编码发送；(b) 信息包1和2编码发生重传丢失时的处理

图4  应用网络编码的重传再丢失处理

Fig.4  Handling of retransmission loss with network coding

实际重传发送中，为更有效应用网络编码重传再丢失处理，可以调整接收情况矩阵。调整矩阵基于如下原则：在传输中损耗率较高的信息包，在重传中损耗率也会较高，重传中也应优先发送。

由原有的接收情况矩阵调整成新的矩阵，具体步骤如下：

步骤1  对于完全顺利接收的信息包，不需要考虑加入重传中，将相应信息包接收情况矩阵列清空处理；

步骤2  将其他信息包接收情况按照丢失节点数目大小从大到小排序；

通过调整后的矩阵，应用网络编码重传再丢失处理几率更大，可以有效地减少再次重传次数。

2.4  基于网络编码的广播源重传发送策略

根据编码策略分析和重传再丢失处理，结合无线网络广播发送特性，可以设计出高损耗无线网络中基于网络编码的广播重传发送策略，其步骤如下：

步骤1 广播源在固定数量的时间间隔(即?t时刻)，停止传输操作进入重传发送步骤。此时广播源节点会有N行、列的信息包接收情况矩阵，该矩阵记录了个信息包的节点接收情况。

步骤2  按照2.3节所述的调整步骤根据信息包丢失概率大小排序生成新的接收情况矩阵。

步骤3  按照基于网络编码的多节点编码组合定理寻找满足可解性条件的信息包组合，将对应的信息包数据导出存入广播源发送序列。

步骤 4  网络编码(可以参照具体情况选择编码方式)生成编码重传信息包。在编码重传信息包包头加入该包内所带的原始信息包序号，使得接收节点清楚编码包内容从而进行解码。

步骤5  广播发送编码重传信息包，通过ACK/NACKs获得接收情况，对重传再丢失的信息包，使用应用网络编码的重传再丢失处理；

步骤 6  所有信息包重传完成后，完成重传操作。广播源节点进入下一轮传输步骤。

由定理1，高损耗无线网络中基于网络编码的广播重传发送策略生成信息包在所有接收节点具有可解性，N个接收节点可以解出其所丢失的信息包，可以达到重传目的。

直观的看，本文的策略在重传中组合多个丢失包发送，且应用了完全不同于普通重传策略的再丢失处理思想，相比与普通重传策略减少了重传次数，提高了重传效率。

3  仿真结果与分析

采用网络仿真工具OMNet++^[14]测试传输损耗较严重情况下，本文策略和普通重传策略的重传性能。测试中参用异或(模2和)编码方式。性能评价参数为平均传输次数(ETX)^[15]。

图5所示为节点丢包率P_i和广播接收节点数目N变化下本文策略和普通重传策略的重传性能比较。测试中取接收节点对应丢包率P₁=P₂…=P_N=0.5，0.6，0.7，重传时间间隔为500?t，广播接收节点数N从2到8个依次增加。

从图5可以看出，在不同的参数下本文的策略相比普通重传策略可以显著地减少平均传输次数，且在节点数量增加的情况下，策略的改善更加明显。这可以解释为节点数目增多，能够参与编码组合的信息包也越多，从而能更有效地提高重传性能和传输效率。本文提出的策略一方面通过编码处理组合多个丢失包重传，另一个方面使用了网络编码的重传再丢失处理，这些处理均有效的在节点丢包率增加的情况下，减缓了重传次数的增加趋势，有效地减少了重传次数。

1—P_i=0.5, 本文策略；2—P_i=0.5, 普通重传策略；3—P_i=0.6, 本文策略；4—P_i=0.6, 普通重传策略；5—P_i=0.7, 本文策略；6—P_i=0.7, 普通重传策略

图5  不同参数影响下重传性能比较

Fig.5  Retransmission performances with different parameters

由模拟测试可以看出，本文提出的策略相对于普通重传策略可以显著地减少平均传输次数，提高传输效率，有着较好的重传性能。新的策略要求节点具有较大的计算能力，由摩尔定律，计算能力代价相比传输代价远远的低，这种代价是可以接受的。

4  结  论

a. 提出基于网络编码的高损耗无线网络广播重传策略，给出多接收节点情况下编码组合重传和重传再丢失处理思想。模拟测试表明不同的节点丢包率和广播接收节点数目下，相比于逐个重传的普通重传策略，重传发送次数有显著减少。

b. 分析新的策略中，尽管节点需要更大的计算能力，但是可以接受的，策略有优势。下一步的工作需要考虑不同无线网络传输协议的应用，进一步扩展编码重传策略的适用范围。

参考文献：

[1] Dianati M, Ling X H, Naik K, et al. A node-cooperative ARQ scheme for wireless Ad hoc networks[J]. IEEE Transactions on Vehicular Technology, 2006, 55(3): 1927-1938.

[2] 康松林, 费洪晓, 施荣华. 网络应用软件监控系统同步与容错的设计与实现[J]. 中南大学学报: 自然科学版, 2005, 36(6): 1048-1053.
KANG Song-lin, FEI Hong-xiao, SHI Rong-hua. Design and implementation of accommodating-err and synchronism mechanism in net monitor system for application softwares[J]. Journal of Central South University: Science and Technology, 2005, 36(6): 1048-1053.

[3] 王高才, 王国军, 陈建二, 等. Mesh网络容错单播路由算法[J]. 中南工业大学学报: 自然科学版, 2003, 34(6): 657-660.
WANG Gao-cai, WANG Guo-jun, CHEN Jian-er, et al. Fault-tolerant unicast routing algorithm on mesh networks[J]. Journal of Central South University of Technology: Natural Science, 2003, 34(6): 657-660.

[4] Yun J, Kavehrad M. Markov error structure for throughput analysis of adaptive modulation systems combined with ARQ over correlated fading channels[J]. IEEE Transactions on Vehicular Technology, 2005, 4(1): 235-245.

[5] Liu Q, Zhou S, Giannakis G B. Cross-layer combining of adaptive modulation and coding with truncated ARQ over wireless links[J]. IEEE Transactions on Wireless Comm, 2004, 3(5): 1746-1755.

[6] Ahlswede R, Cai N, LI S Y, et al. Network information flow[J]. IEEE Transactions on Information Theory, 2000, 46(4): 1204-1216.

[7] Li S Y R, Yeung R W. Linear network coding[J]. IEEE Transactions on Information Theory, 2003, 49(2): 371-381.

[8] Koetter R, Médard M. An algebraic approach to network coding[J]. IEEE/ACM Transactions on Networking, 2003, 11(5): 782-795.

[9] Ho T, Médard M, Koetter R, et al. On randomized network coding[C]//Proceedings of the 41st Annual Allerton Conference on Communication Control and Computing. New York: ACM Press, 2003: 1354-1357.

[10] Widmer J, Fragouli C, Le Boudec J Y. Low-complexity energy efficient broadcasting in wireless ad-hoc networks using network coding[C]//Proceedings of 1st Workshop on Network Coding Theory and Applications. Riva del Garda, Italy: Springer-Verlag, 2005: 2354-2361.

[11] Cai N, Yeung R W. Network coding and error correction[R]. Bangalore: ITW, 2002.

[12] Wu Y, Chou P A, Kung S Y. Information exchange in wireless networks with network coding and physical-layer broadcast[R]. Baltimore: Microsoft Research, 2004.

[13] Nguyen D, Nguyen T, Bose B. Wireless broadcasting using network coding[R]. Oregon: Oregon State University, 2006.

[14] OMNET simulation documents: Simulation standard specification[EB/OL]. http://www.omnetpp.org/index.php. 2007.

[15] Couto D, Aguayo D, Bicket J, et al. A high-throughput path metric for multi-hop wireless routing[C]//Proceedings of ACM Mobicom. New York: ACM Press, 2003: 1125-1131.

收稿日期：2008-01-25；修回日期：2008-04-09

基金项目：国家自然科学基金资助项目(60873265)

通信作者：肖  潇(1981-)，男，湖南娄底人，博士研究生，从事网络优化和网络编码研究；电话：13187059283；E-mail: xiaogentleman@163.com