基于线性网络编码重传算法的MATLAB仿真分析*

薛　琰，孟利民（.浙江工业大学信息工程学院，浙江杭州3003 .浙江省通信网技术应用研究重点实验室，浙江杭州3003）



基于线性网络编码重传算法的MATLAB仿真分析*

薛琰1，孟利民2
（1.浙江工业大学信息工程学院，浙江杭州310023 2.浙江省通信网技术应用研究重点实验室，浙江杭州310023）

摘 要：近年来，网络编码技术理论飞速发展，为提高无线网络传输的吞吐率和可靠性提供了新的启发点。首先介绍了网络编码理论的发展现状和线性网络编码理论，然后构建了无线网络重传模型，对原有的网络编码无线广播重传（NCWBR）算法和改进型网络编码无线广播重传（ENCWBR）算法进行了MATLAB仿真，证明了ENCWBR算法在高丢包率的条件下确实可以很好地控制重传次数。

关键词：网络编码；无线网络；重传次数

0　引言

广播是无线网络通信的一种常见模式，但是由于无线信道较有线信道更为恶劣，重传是必要的。传统的重传方式比较浪费网络资源，比如自动重发请求（Automatic Repeat Request，ARQ）模式，对于每一个丢失的包都要一一重传。所以有必要探索新的重传方式。

在2000年，AHLSWEDE R等人［1］首次提出了网络编码的概念，由此改变了人们对于网络传输中中间节点的观念，即中间节点不仅可以扮演存储转发的角色，还可以对数据包进行计算和编码［2］。网络编码是通信领域的重大突破，核心观点是中间节点集成路由和编码的功能。使用网络编码可以有效地改善无线网络的吞吐率，并实现最大流传输［3］。

KOETTER R讨论了一种网络编码的代数方法［4］；吕玉萍等人［5］说明了运用网络编码在无线网络中优化传输效率的方法；陈娟等人［6］提出一种有效减少重传次数的改进ARQ技术；王练等人［7］总结了无线网络重传方案的多种方法；KATTIS等人［8］通过使用完全机会编码来构建无线Mesh网络减小重传次数；肖潇等人［9］提出NCWBR算法使用XOR方法来组合丢失的数据包，并通过中心节点向接收节点广播组合包，但是当同一个节点在组合包中有多于一个的丢失包时，将会造成解码速率的降低。本文根据Yao Xukun等人提出的网络编码高效率多播解码（Efficient Multipacket Decoding Network Coding，EMDNC）方法改进了原有NCWBR方法［10］，经过MATLAB仿真表明，这种方法确实会减少重传次数，在对实时性要求不高的场景下，会有很好的应用。

1　无线网络模型和问题描述

图1展示了缓冲矩阵的一个例子，通过接收节点的ACK和NAK反馈而创建。在这个矩阵当中，0代表接收节点成功收到数据包，而1代表接收节点接收数据包失败。通过构建缓冲矩阵可以完全反映这一次传输的情况，传输模型中包括5个接收节点和10个传送包，构成一个批次。

NCWBR的步骤如下：中心节点从缓冲矩阵中依次搜索每一行中的第一个1，并把这些包放入编码包序列来编码，在编码完毕后广播第一个批次的编码包1⊕2⊕3⊕4⊕5，广播的编码包就可以在节点R1、R2、R3、R4、R5与原来存储的编码包异或分别解码。

但如果丢失数据包6和8，当R2接收编码包6⊕7⊕8⊕9⊕10时，节点R2不能恢复这些丢失包。每当这个情况发生时，网络需要更多的重传次数，这样就会降低网络的性能。考虑到这种情况，本文提出了一种新的算法，利用每个节点的存储能力，增加解码效率。

图1　无线网络的NCWBR例子

2　ENCWBR方法

（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次。

图2　无线网络的NCWBR例子

图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方法减少了整个网络的开销。

图3　无线网络ENCWBR例子

3　ENCWBR方法的仿真分析

对于一般重传方法、NCWBR方法和ENCWBR方法，分别使用MATLAB进行建模分析。先构建概率矩阵，设数据包的丢失概率为p=0.2，由此代表缓冲矩阵，再通过编码包逐步把矩阵变为0矩阵，代表矩阵解码成功。通过计算发送编码包的次数来代表重传的次数。为简化仿真，不考虑编码包的丢失。

采用NCWBR方法，MATLAB仿真流程图如图4所示。首先寻找每一行的第一个1，寻找完以后放入编码包进行异或编码处理，并广播编码包，广播完编码包以后重传次数retram就加1，如果不能解码就重新把缓存矩阵相应位置重置为1，进行迭代，直到矩阵变为0矩阵。

图4　ENCWBR的仿真流程图

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方法可以很好地控制重传的次数，提高了解码效率，在多节点的情况下依旧可以很好地控制重传次数。

图5　ENCWBR的仿真流程图

图6　p=0.02的情况下三者的重传次数

图7　p=0.2的情况下三者的重传次数

参考文献

［1］AHISWEDE R，Cai Ning，LIS Y R，et al.Network Information Flow［C］. IEEE Transactions on Information Theory，2000，46（4）：1204-1216.

［2］Zhang Zhenyu，LiMing，Lou Wenjing.R-code：network codingbased reliable broadcast in wirelessmesh networks［J］.Ad Hoc Networks，2011，9（5）：788 - 798.

［3］胡平.一种网络编码构造算法研究［J］.微型机与应用，2010，29（5）：33-34.

［4］KOETTER R，DARD M.An algebraic approach to network coding［C］.IEEE/ACM Transactions on Networking，2003：782-795.

［5］吕玉萍.基于网络编码的无线网络重传方法研究［D］.成都：西南交通大学，2014.

［6］陈娟，张玉明，郑学强.一种有效降低重传次数的S-ARQ技术［C］.2006年全国无线电应用与管理学术会议，2006.

［7］王练，雷芳.基于网络编码的无线网络重传方案综述［J］.重庆邮电大学学报（自然科学版），2012，24（5）：664-668.

［8］KATTIS，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）：69-75.

［10］Yao Yukun，Wen Yadi，Ren Zhi，et al.High efficient multipacket decoding approach for network coding in wireless networks［J］.中国邮电高校学报（英文版），2013，20（1）：95-100.

薛琰（1989 -），男，硕士研究生，主要研究方向：线性网络编码。

孟利民（1963 -），女，博士，教授，主要研究方向：无线通信与网络，智能信息系统，网络管理，多媒体数字通信与网络。

引用格式：薛琰，孟利民.基于线性网络编码重传算法的MATLAB仿真分析［J］.微型机与应用，2016，35（10）：67-69.

The MATLAB simulation of network broadcast retransmission algorithm based on linear network coding

Xue Yan1，Meng Limin2
（1.College of Information Technology，Zhejiang University of Technology，Hangzhou 310023，China；2.Zhejiang Province Key Laboratory of Communication Networks，Hangzhou 310023，China）

Abstrac t：In recent years，network coding technology is developing very quickly.It provides a good inspiration to enhance reliability and throughput rate of wireless network transmission.Firstly，the paper describes the current status of the development of network coding and linear network theory，then constructs the model of wireless network transmission.The paper simulates the network coding wireless broadcast retransmission（NCWBR）algorithm and enhanced network coding wireless broadcast retransmission（ENCWBR），and it proves that ENCWBR does enhance the effectiveness of the wireless network retransmission.

Key w ords：network coding；wireless network；times of retransmission

作者简介：

收稿日期：（2015-12-22）

*基金项目：国家自然科学基金项目（61372087）

中图分类号：TN934

文献标识码：A

DOI：10.19358 /j.issn.1674-7720.2016.09.023