鲁达 薛琰1， 孟利民2
（1. 浙江工业大学 信息工程学院，浙江 杭州 3100232. 浙江省通信网技术应用研究重点实验室，浙江 杭州 310023）
摘要：近年来，网络编码技术理论飞速发展，为提高无线网络传输的吞吐率和可靠性提供了新的启发点。首先介绍了网络编码理论的发展现状和线性网络编码理论，然后构建了无线网络重传模型，对原有的网络编码无线广播重传（NCWBR）算法和改进型网络编码无线广播重传（ENCWBR）算法进行了MATLAB仿真，证明了ENCWBR算法在高丢包率的条件下确实可以很好地控制重传次数。
0引言
广播是无线网络通信的一种常见模式，但是由于无线信道较有线信道更为恶劣，重传是必要的。传统的重传方式比较浪费网络资源，比如自动重发请求（Automatic Repeat Request ，ARQ）模式，对于每一个丢失的包都要一一重传。所以有必要探索新的重传方式。
在2000年，AHLSWEDE R等人［１］首次提出了网络编码的概念，由此改变了人们对于网络传输中中间节点的观念，即中间节点不仅可以扮演存储转发的角色，还可以对数据包进行计算和编码［2］。网络编码是通信领域的重大突破，核心观点是中间节点集成路由和编码的功能。使用网络编码可以有效地改善无线网络的吞吐率，并实现最大流传输［3］。
KOETTER R讨论了一种网络编码的代数方法［4］；吕玉萍等人［5］说明了运用网络编码在无线网络中优化传输效率的方法；陈娟等人［6］提出一种有效减少重传次数的改进ARQ技术；王练等人［7］总结了无线网络重传方案的多种方法；KATTI S等人［8］通过使用完全机会编码来构建无线Mesh网络减小重传次数； 肖潇等人［9］提出NCWBR算法使用XOR方法来组合丢失的数据包，并通过中心节点向接收节点广播组合包，但是当同一个节点在组合包中有多于一个的丢失包时，将会造成解码速率的降低。本文根据Yao Xukun等人提出的网络编码高效率多播解码（Efficient Multipacket Decoding Network Coding， EMDNC）方法改进了原有NCWBR方法［10］，经过MATLAB仿真表明，这种方法确实会减少重传次数，在对实时性要求不高的场景下，会有很好的应用。
1无线网络模型和问题描述
图1展示了缓冲矩阵的一个例子，通过接收节点的ACK和NAK反馈而创建。在这个矩阵当中，0代表接收节点成图1无线网络的NCWBR例子
功收到数据包，而1代表接收节点接收数据包失败。通过构建缓冲矩阵可以完全反映这一次传输的情况，传输模型中包括5个接收节点和10个传送包，构成一个批次。
NCWBR的步骤如下：中心节点从缓冲矩阵中依次搜索每一行中的第一个1，并把这些包放入编码包序列来编码，在编码完毕后广播第一个批次的编码包1⊕2⊕3⊕4⊕5，广播的编码包就可以在节点R1、R2、R3、R4、R5与原来存储的编码包异或分别解码。
但如果丢失数据包6和8，当R2接收编码包6⊕7⊕8⊕9⊕10时，节点R2不能恢复这些丢失包。每当这个情况发生时，网络需要更多的重传次数，这样就会降低网络的性能。考虑到这种情况，本文提出了一种新的算法，利用每个节点的存储能力，增加解码效率。
2ENCWBR方法
（1）依次寻找缓存矩阵每一行中首个为1的数据包。
（2）将数据包放入编码序列，把相应的位置重置为0。
（3）使用网络编码异或在编码序列中的数据包，然后广播编码包，依次发送第一个批次的编码包、第二个批次的编码包，直到缓冲矩阵更新为0。
（4）接收节点接收到所有的编码包以后，利用所有的编码包进行解码，如果不能解码，则反馈给中心节点，中心节点重新更新缓冲矩阵，跳到步骤（1）。
图2展示了使用NCWBR的例子。中间节点广播编码包的组合1⊕2⊕3⊕4⊕5、1⊕6⊕7、3⊕8⊕9⊕10、4⊕11，然后单独传输数据包9。总共需要传输5次。
图3展示了ENCWBR的例子，中心节点广播第一个编码组合包1⊕2⊕3⊕4⊕5，这个编码组合包不能在节点R1进行解码，R1将这个编码包放入缓存当中。然后R1收到第二个编码包3⊕6⊕7，依然把它放入缓存当中，再接收第三个编码4⊕8⊕9⊕10放入缓存中，最后重传编码包9⊕11，把4个编码包联立起来构成一个异或方程组，就可以解每个数据包，所以总共需要4次重传。实际上ENCWBR利用了缓冲节点的存储能力，通过后续到达的包进行解码。使用ENCWBR方法时，不管接收节点是否成功解码相应的数据包，都不需要给中心节点传送NAK，所以ENCWBR方法减少了整个网络的开销。
3ENCWBR方法的仿真分析
对于一般重传方法、NCWBR方法和ENCWBR方法，分别使用MATLAB进行建模分析。先构建概率矩阵，设数据包的丢失概率为p=0.2，由此代表缓冲矩阵，再通过编码包逐步把矩阵变为0矩阵，代表矩阵解码成功。通过计算发送编码包的次数来代表重传的次数。为简化仿真，不考虑编码包的丢失。
采用NCWBR方法，MATLAB仿真流程图如图4所示。首先寻找每一行的第一个1，寻找完以后放入编码包进行异或编码处理，并广播编码包，广播完编码包以后重传次数retram就加1，如果不能解码就重新把缓存矩阵相应位置重置为1，进行迭代，直到矩阵变为0矩阵。
ENCWBR的MATLAB仿真图如图5所示。在ENCWBR方法中一次性发送全部的编码包，等接收点接收全部编码包以后再判定是否可以解码。然后反馈解码情况，更新缓冲矩阵以后，再次编码并发送编码包，直到数据包全被解码完毕。如图5所示，先输入缓冲矩阵，寻找编码包，找到每一行的第一个1，放入编码包，并把相应地位置置0，相应地重传计数值retram加1，如此构建多个编码包，当全部发送且接收节点接收全部编码包以后判定是否可以解码。给出相应的反馈，更新缓冲矩阵，进行迭代，直到矩阵变为0。
4结论
分别将数据包丢失概率p设置为0.02和0.2。如图6所示，在数据包丢失概率p=0.02的情况下，由于丢失的数据包比较分散，ARQ对每一个数据包都要重传，因此重传次数较大，而NCWBR和ENCWBR能够对数据包进行编码，所以降低了重传次数，且当数据包丢失概率较小时，NCWBR和ENCWBR都能解码成功，两者差别不大。而当数据包丢失概率p=0.2的情况下，如图7所示，当节点较少时，NCWBR可以很好地控制重传次数，要优于传统的一般ARQ，但当节点数目增多时，由于NCWBR中不能解码的节点的数量增多，造成编码机会的浪费，其重传次数甚至大于一般ARQ，而ENCWBR方法可以很好地控制重传的次数，提高了解码效率，在多节点的情况下依旧可以很好地控制重传次数。
参考文献
［1］ AHISWEDE R, Cai Ning, LI S Y R, et al. Network Information Flow［C］. IEEE Transactions on Information Theory, 2000,46(4):12041216.
［2］ Zhang Zhenyu, Li Ming, Lou Wenjing.Rcode:network codingbased reliable broadcast in wireless mesh networks［J］. Ad Hoc Networks, 2011, 9(5):788–798.
［3］ 胡平. 一种网络编码构造算法研究［J］. 微型机与应用, 2010,29(5):3334.
［4］ KOETTER R, DARD M. An algebraic approach to network coding［C］. IEEE/ACM Transactions on Networking, 2003:782795.
［5］ 吕玉萍. 基于网络编码的无线网络重传方法研究［D］. 成都：西南交通大学, 2014.
［6］ 陈娟, 张玉明, 郑学强. 一种有效降低重传次数的SARQ技术［C］. 2006年全国无线电应用与管理学术会议， 2006.
［7］王练, 雷芳. 基于网络编码的无线网络重传方案综述［J］.重庆邮电大学学报（自然科学版）， 2012，24（5）：664668.
［8］ KATTI S, RAHUL H, HU W, et al. XORs in the air: practical wireless network coding［J］. IEEE/ACM Transactions on Networking , 2008, 16(3):497 510.
［9］ 肖潇, 王伟平, 杨路明,等. 基于网络编码的无线网络广播重传方法［J］. 通信学报, 2009, 30(9):6975.
［10］ Yao Yukun, Wen Yadi, Ren Zhi, et al. High efficient multipacket decoding approach for network coding in wireless networks［J］. 中国邮电高校学报（英文版）, 2013, 20(1):95100.