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

  薛琰1, 孟利民2

  (1. 浙江工业大学 信息工程学院,浙江 杭州 3100232. 浙江省通信网技术应用研究重点实验室,浙江 杭州 310023)

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

  关键词:网络编码;无线网络;重传次数

0引言

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

  在2000年,AHLSWEDE R等人[1]首次提出了网络编码的概念,由此改变了人们对于网络传输中中间节点的观念,即中间节点不仅可以扮演存储转发的角色,还可以对数据包进行计算和编码[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无线网络模型和问题描述

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

  图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)。

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

  图2展示了使用NCWBR的例子。中间节点广播编码包的组合1⊕2⊕3⊕4⊕5、1⊕6⊕7、3⊕8⊕9⊕10、4⊕11,然后单独传输数据包9。总共需要传输5次。

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

  图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矩阵。

  

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

  ENCWBR的MATLAB仿真图如图5所示。在ENCWBR方法中一次性发送全部的编码包,等接收点接收全部编码包以后再判定是否可以解码。然后反馈解码情况,更新缓冲矩阵以后,再次编码并发送编码包,直到数据包全被解码完毕。如图5所示,先输入缓冲矩阵,寻找编码包,找到每一行的第一个1,放入编码包,并把相应地位置置0,相应地重传计数值retram加1,如此构建多个编码包,当全部发送且接收节点接收全部编码包以后判定是否可以解码。给出相应的反馈,更新缓冲矩阵,进行迭代,直到矩阵变为0。

  

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

4结论

  分别将数据包丢失概率p设置为0.02和0.2。如图6所示,在数据包丢失概率p=0.02的情况下,由于丢失的数据包比较分散,ARQ对每一个数据包都要重传,因此重传次数较大,而NCWBR和ENCWBR能够对数据包进行编码,所以降低了重传次数,且当数据包丢失概率较小时,NCWBR和ENCWBR都能解码成功,两者差别不大。而当数据包丢失概率p=0.2的情况下,如图7所示,当节点较少时,NCWBR可以很好地控制重传次数,要优于传统的一般ARQ,但当节点数目增多时,由于NCWBR中不能解码的节点的数量增多,造成编码机会的浪费,其重传次数甚至大于一般ARQ,而ENCWBR方法可以很好地控制重传的次数,提高了解码效率,在多节点的情况下依旧可以很好地控制重传次数。

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

  参考文献

  [1] AHISWEDE R, Cai Ning, LI S Y R, et al. Network Information Flow[C]. IEEE Transactions on Information Theory, 2000,46(4):12041216.

  [2] Zhang Zhenyu, Li Ming, Lou Wenjing.Rcode:network codingbased reliable broadcast in wireless mesh 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] 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):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.

 

  • 基于线性网络编码重传算法的MATLAB仿真分析已关闭评论
    A+
发布日期:2019年03月03日  所属分类:参考设计