无线组播网络中应用网络编码的动态组合重传算法

李彬,李泉,张若南,蒋毅,杨荣

(1.西北工业大学电子信息学院,710072,西安;2.西安交通大学工程坊,710049,西安)



无线组播网络中应用网络编码的动态组合重传算法

李彬1,李泉1,张若南1,蒋毅1,杨荣2

(1.西北工业大学电子信息学院,710072,西安;2.西安交通大学工程坊,710049,西安)

针对无线组播网络中降低数据包重传次数及对抗信道衰落、建立稳定无线连接的需求,提出了一种基于网络编码的动态组合重传算法。该算法采用动态线性组合编码算法(DLCCA),以提高无线组播网络带宽利用效率。首先,利用发送端向用户发送原始数据包;其次,通过组播网络的控制信道,发送端获取了网络用户的接收状态,对未正确解码的数据包进行编码,并在传输过程中根据网络状态采用动态组合策略来形成网络编码包,从而有效提高了网络的整体吞吐量。与此同时,还进一步提出了低复杂度编码算法,并分析了所提编码算法的性能,获得了相应的理论分析结果。仿真实验表明,与传统的无编码算法和XOR网络编码算法相比,动态组合重传算法可以显著减少30%的数据重传次数,提高了网络吞吐量。

组播网络;网络编码;动态线性组合

近年来,随着4G/5G网络中图像、视频等多媒体业务的相继开展,人们对多媒体视频传输质量的要求越来越高。由于无线组播技术能以高效、可扩展的方式发送单点到多点、多点到多点的数据流,因此越来越受到人们的重视,而且在无线组播网络中如何保证收发端之间建立可靠的连接也已成为人们所关心和长期研究的问题。通常,自动重传请求(automatic repeat request,ARQ)等机制采用重传策略对接收错误的数据包进行重传,但同时也带来了频谱资源利用率低、延时长等问题,导致用户服务质量的降低。对此,网络编码提出了在网络节点存储转发过程中通过对接收到的数据包进行重组编码来减少重传时间,并提高了无线组播网络的信道利用效率。网络编码的关键之处在于:中继节点在完成路由功能的同时还需要将在不同链路传输中的数据包进行组合编码。这种方式在无线信道带宽资源利用率、能量利用率及其他潜在方面带来显著的益处。值得关注的是,随机网络编码技术(random network coding,RNC)[1-2]——一种将原始数据包进行随机线性加权的编码方式,已经被证明可达到组播容量的上限。因此,越来越多的研究者把目光聚集到网络编码技术上。Katti等人在文献[3]中阐述了一种COPE方法,该方法在无线传感器网络中利用网络编码减少了数据包重传次数,并提高了单播网络数据传输效率;Chachulski等人在文献[4]中则针对无线传感器网络提出了一种传输协议,在该协议中,数据包在转发之前先进行随机合并,从而显著地减少数据包路由中的重传次数;文献[5]将机会式网络编码应用到无线网络的广播传输中,提高了网络带宽的利用率。此外,文献[6-9]的研究则侧重于改善无线衰落信道下的数据包重传效率;文献[10]中提出了一种基于网络编码的重传机制,并根据发包顺序依次发送丢失的编码包,以期降低重传次数。Ren则提出了一种改进重传机制[11],从而有效地提高联合数据包的解码概率从而降低重传次数;同时,Nguyen在文献[12]中也提出了一种无线组播网络中利用网络编码的优势减少传输次数的方法。

在上述研究工作中,特别是文献[12]提出的算法中,作者探讨了当接收端无法对原始数据包进行正确解码时如何利用异或(XOR)机制通过数据包编码进行重传。具体地,若编码包被丢失,发送端则会重复发送相同的XOR编码包,直到所有接收端都正确解码后才继续发送下一个编码包。因此,这种机制对编码包丢失的情况处理时依然回到了常规的ARQ解决思路,而已有研究表明ARQ这种方式在无线组播网络中效率极低。事实上,当网络中只有部分接收端成功接收了某编码包时,网络状态已经产生了相应的改变。此时发送端可以依据当前的网络状态,对编码包的组合方式进行重新规划,即只将成功解码的原始数据包进行动态组合,以此来提高网络的吞吐量。

针对上述问题,本文提出了无线组播网络中基于随机网络编码的动态线性组合编码算法(DLCCA)。DLCCA的核心思想在于如何在传输过程中,根据网络的实时状态,对原始数据包进行动态组合来形成即将发送的编码包,从而有效地提高网络的整体吞吐量。此外,为了简化算法的计算复杂度,本文进一步提出了低复杂度的确定线性组合编码算法(FLCCA),FLCCA同时也是DLCCA的性能下界。最后,针对所提出的算法进行了性能分析,并得到了相应的理论分析结果。仿真实验结果表明,相比传统的XOR编码算法和非编码算法,DLCCA与FLCCA算法可以显著地减少重传次数(减少30%以上),有效改善了组播网络的信道利用率。

1 系统模型

在本文无线组播网络模型中,发送端(例如基站或者AP)将N个原始数据包通过时分的方式发送给M个接收端,并规定系统每个时隙传输一个数据包(原始包或者编码包)。发送端利用控制信道获取网络中接收端反馈的数据包接收状态。与数据包相比,由于反馈信息包往往很短,只包含必要的节点状态信息,因此该模型假设反馈信息不会发生错误和丢失。此外,系统的无线信道为瑞利信道模型,并假定不同收发端的无线信道是相互独立的,其中第i个接收端的误包率设为pi。为了更清晰地阐述DLCCA算法,本文做出如下定义。

定义1 状态矩阵T。T为根据接收端反馈信息而形成的矩阵,用来表示数据传输期间每个接收端的数据包接收状态。矩阵中的元素称之为标志位。其中,第i行的标志位代表第i个接收端接收数据包的状态(1≤i≤M),而第j列的标志位代表每个接收端接收第j个数据包的接收状态(1≤j≤N)。若某个原始数据包被接收端成功解码,则T中的相应的标志位记为1,否则标记为0。

定义2 传输带宽η。发送端成功将一个原始数据包发送给所有接收端所使用的平均传输次数。

定义3 原始数据包传输阶段。该阶段发送端利用N个时隙向用户传输N个原始数据包。

定义4 编码包传输阶段。在该阶段中发送端根据网络状态动态生成编码包并进行传输,直到所有的接收端均能解码出所有原始数据包。

2 动态线性组合重传机制

在动态线性组合编码策略中,数据的发送分为两个阶段。首先,发送端进行原始数据包传输阶段。在该阶段中,发送端利用N个时隙将N个原始数据包进行时分传输。当该阶段结束后,由于无线信道的衰落特性,所以并不是所有接收端对所有原始数据包都能进行正确解码。因此,接收端利用控制信道将自身的解码情况反馈回发送端,而发送端则根据反馈信息形成网络状态矩阵T。因此,状态矩阵T记录了某个数据包是否被某一接收端正确解码的信息。当原始数据包传输阶段完成之后,发送端进入编码包传输阶段。在该阶段中发送端将会根据状态矩阵T对部分被接收端丢失的原始数据进行组合,从而生成新的编码包。因此,如何对丢失的数据包进行组合是该编码策略的关键所在。据此,本文提出如下编码和调度策略。

(1)发送端在T的每一行中查找第一个0值标志位,并将这些值为0的标志位所对应的原始数据包按照随机线性编码的方式[1]生成新的编码包。同时,参与编码的标志位则被改写为1。

(2)发送端将步骤1中形成的编码包在全网内广播。若部分接收端仍无法正确解码该编码包,该接收端则通过控制信道将其状态信息反馈给发送端。此时,T中所对应标志位再次变为0。

(3)针对步骤2中更新的T,发送端再次检查状态矩阵T中是否仍然有值为0的标志位。若有,发送端则需重复上述的步骤直到矩阵T中没有0值。为了便于对DLCCA的理解,图1进行了举例说明。在图1中,状态矩阵代表发送端将N=10个数据包向M=5个接收端进行组播。若接收端在原始数据包发送阶段成功解码某个数据包,则矩阵T中相应标志位的值记为1,否则记为0。

图1 采用DLCCA机制进行组合的矩阵T

图1为DLCCA机制进行组合的状态矩阵T,矩阵中标记的虚线框给出了在编码包传输阶段中组合形成新的编码包所包含的原始数据包。图中,每个虚线框包括了每一行中具有相同出现顺序的0标志位。例如,状态矩阵T最左边的虚线框包含了每一行中的第一个0标志位。状态矩阵中处于同一个虚线框的原始数据包将会被组合后形成新的编码包,而状态矩阵中其他的虚线框会按照相同的规则进行数据包编码。随后,发送端依次将新形成的编码包进行发送。

需要特别指出的是,若某个编码包在传输时发生错误,发送端会根据网络状态动态调整编码策略。例如图1中矩阵第3行第6列的圆圈代表第3个虚线框和第4个虚线框的重叠部分。这意味着由第3个虚线框所生成的编码包没有被接收端R3成功接收。此时圆圈位置处的标志位将被置为0,而发送端进行动态编码策略调整,将数据包a6与第4个虚线框内的原始数据包组合后形成编码包。据此,发送端共依次生成6个编码包c1～c6,并按照如下顺序发送

(1)

(2)

(3)

(4)

(5)

(6)

式中:βij是从伽罗华域Fq中随机获得的网络编码系数。需要注意的是,与传统的随机网络编码将所有原始数据包进行组合的方式不同,本文所提出的编码算法会根据实时网络状态对原始数据包进行动态组合。DLCCA与XOR编码机制不同之处在于:在XOR中若一个XOR数据包丢失,发送端会重传该XOR编码包直至所有接收端都能正确接收到该编码包;在DLCCA中,发送端利用线性无关的随机系数对原始数据包进行编码并发送。根据线性代数理论可知接收端只要接收到足够数量的编码包便可以解出原始数据包,从而获取比XOR更高的传输效率。DLCCA算法的代码如下。

输入N,M,P=[p1,p2,…,pM]

输出 传输带宽η

(1)初始化矩阵T=zeros(M,N),n

(2) fort=1:Ndo

(3)fori=1:Mdo

(4) if rand(1)>P(i) then

(5)T(t,i)=1;

(6)n=n+1;

(7) end if

(8)end for

(9) end for

(10)fort=1:Ndo

(11) fori=1:Mdo

(12)ifT(t,i)==0 then

(13) 获取相应的丢失数据包,T(t,i)=1;

(14)end if

(15) end for

(16)end for

(17)将这些数据包组合形成一个新的数据包并重新发送

(18)n=n+1;

(19)if某些接收节点接收新数据包失败then

(20) 知阵T中相应位置的值保持不变;

(21)end if

(22)执行步骤10～18直到矩阵T中没有0值;

(23)η=n/N。

3 确定线性组合重传算法

在DLCCA算法中,发送端在编码包传输发生错误后会动态地调整编码包的组合形式,以此来实现更高的吞吐量,但该算法也同时带来了更大的计算复杂度。对此,本文提出了一种称为确定线性组合重传算法(FLCCA)的新算法,可作为DLCCA的下界。与DLCCA一样,FLCCA仍分为2个传输阶段:原始数据包传输阶段和编码包传输阶段。第一个阶段即原始数据包传输阶段与动态线性组合重传算法DLCCA的第一阶段相同;第二阶段则根据状态矩阵T选择相对简单的规则对原始数据包进行组合。具体步骤与细节如下所述。

(1)与DLCCA算法机制相同,发送端首先查找状态矩阵T中每一行的第一个0标志位值所对应的数据包,并将该组数据包组合形成新的编码包。

(2)发送端将上一步骤形成的编码包进行发送。若在该阶段传输中仍有部分接收端没有成功接收到新的编码包,发送端会再次重新发送该编码包直至所有接收端都实现成功接收。此时,状态矩阵T中相应为0的标志位会更新为1。

(3)发送端根据接收端发送的反馈信息更新状态矩阵,直至状态矩阵中的所有元素都为1。

4 算法性能分析

4.1 DLCCA算法性能分析

假设网络中有M个接收端,其误包率遵循如下顺序p1≤p2≤…≤pM。发送端进行了N轮传输后,接收端R1,R2,…,RM的平均丢包数分别为Np1,Np2,…,NpM。根据DLCCA算法的编码规则,在编码包传输阶段,如果一个编码包没有被某一接收端成功接收,就会依据状态矩阵T形成一个新的编码包,以确保与先前成功接收到的编码包进行联合解码,从而获取所有的原始数据包。因此,从统计学角度来看,网络的重传次数主要取决于具有最高误包率的接收端,而传输次数等于NpM(pM=max{p1,p2,…,pM})。将X记为一个接收端成功解出一个数据包的传输次数,则X的期望为

(7)

因此,DLCCA的传输带宽为

(8)

4.2 FLCCA算法性能分析

假设FLCCA和DLCCA算法具有相同的参数设定。根据FLCCA的编码规则,第二阶段中发送端可能会对某个组合编码包进行多轮重复发送。第一轮里,由于R1拥有最少数量的丢失数据包,因此接收端R1所有的丢失数据包都可以与R2,R3,…,RM的丢失数据包进行组合,形成Np1个编码包。当这些编码包均被所对应的接收端正确接收后,R1,R2,…的丢失数据包数分别变为0,N(p2-p1),N(p3-p1),…,N(pM-p1)。在第二轮中,R2变成了拥有最少丢包的接收端,这些丢失的数据包将会与R3,R4,…,RM的丢失数据包进行组合。经过第二轮传输后,R1,R2,…,RM的丢失数据包数分别为0,0,N(p3-p2),…,N(pM-p2)。依据这一规律,在经过M轮传输后,所有的丢失数据包均已经被组合形成了新的编码包。因此,将N个数据包成功传给所有接收端的传输次数为

(9)

式中:φi表示在第i轮中将一个编码包成功传给所有相应的接收端所需的平均重传次数。因此,FLCCA算法的传输带宽为

(10)

(11)

式中:z为传播次数。

由式(7)可得

(12)

因此,将一个原始数据包成功传给L(1≤L≤M)个接收端所需的平均传输次数为

(13)

式中:i1,i2,…,iL∈{0,1},并且∃ij≠0。

在式(5)中,Np1个编码包被M个接收端成功接收,N(p2-p1)个编码包被M-1个接收端成功接收,以此类推。因此,根据φL的定义,可知φi=φM-i+1。

4.3 反馈信息性能分析

从反馈信息角度来看,在整个传输过程中(原始数据包的传输和编码包的传输),每传输一次数据包,总会有M个反馈信息在一定的时间段Δt内被反馈到发送节点。由于反馈信息只是反映数据包是否被接收节点成功地接收,因此所有的反馈信息数据量很小,且假设都被发送节点正确地接收到,那么DLCCA和FLCCA算法需要的平均反馈信息次数分别为nD和nF,平均传送时间为tnD和tnF。因此,对于不同的重传算法,不同的传输带宽对应的反馈信息的平均传送时间也不一样,传输带宽越大的算法,对应的反馈消息所占用的时间也越长,通信传输性能也越差,反之亦然。

5 仿真实验

在仿真实验中,将文献[12]所提出的NC机制与本文提出的算法进行比较。为了便于描述,文献[12]中所提出的两种编码算法分别记为算法1和算法2。在下述的仿真实验中,原始数据包数量N设为1 000,同时设定如下4类场景。

场景1 假定接收端数量M=8,每个接收端的误包率pi(i=1,2,…,8)均相同,且设定误包率的值均从0.02变化到0.24。图2给出了传输带宽η的理论推导值和仿真结果。从图2可以得出,在传输带宽占用方面,本文所提出的两种机制所需带宽要明显小于文献[12]中提出的机制。同时,本文提出的机制所对应的仿真曲线与理论推导值曲线可以很好地吻合。此外,在参与对比的所有机制中传输带宽占用情况都随着误包率的上升而增大,而随着误包率的上升,本文提出的机制与对比机制之间的差距变得更大,这也表明本文所提出的机制在网络具有较高误包率的情况下优势更加明显。

图2 不同误包率下4种算法的传输带宽

场景2 在该场景中论文研究接收端数目对平均传输带宽的影响。仿真实验假设所有接收端的误包率均相同且为0.12,而接收端数量则从2逐渐增加至12,如图3所示。根据传输带宽的理论与仿真结果可以看出,随着接收端数量的增加,传输带宽占用也随之增大,但本文所提出的两种传送算法的传输带宽占用始终低于其他传送算法。更为重要的是,当接收端数量明显增大时,本文提出的算法具有更明显的优势,其性能要远优于其他对比算法。同样,从图3中可以看到本文提出的算法的仿真结果与理论结果很吻合。

图3 不同接收端数量时4种算法的传输带宽

场景3 该场景研究较大误包率(pi=0.24)和较小误包率(pi=0.12)情形下的传输带宽特性,并假设网络中的每个接收端都具有相同的误包率。仿真实验得到的结果如图4所示,可以看到,无论在信道质量好或坏的情况下,本文提出的算法在较大误包率或较多接收端时均比传统的算法具有更高的传输效率。因此,本文提出的算法更适合信道质量较差时的数据传输。

图4 误包率较大及较小时4种算法的传输带宽

图5 原始数据包数对传输带宽影响

场景4 在该场景中论文研究原始数据包数量对平均传输带宽的影响。接收端数量设为12,且误包率均为0.04。如图5所示,根据传输带宽的仿真结果可以看出,传输带宽随着数据包数的增长没有变化,这说明该类机制不受原始数据包数量的影响,从而保证传输带宽不受堆栈内编码数据包多少的影响。从图5可以看出,本文所提出的两种传送算法的传输带宽占用仍始终低于其他传送算法。

6 结论和展望

本文提出了两种可以在无线组播网络中降低传输带宽占用的重传算法。在DLCCA算法中,发射端利用系统控制信道获取接收端数据包接收状态,并根据当前全网数据包接收状态动态地利用随机线性网络编码生成编码包。在传输过程中,发射机不断进行编码生成策略调整,从而有效提高网络的整体吞吐量。此外,本文还提出了一种低复杂度的FLCCA算法,该机制对DLCCA在编码包生成过程中进行了化简,从而降低了系统实现复杂度。最后,通过理论推导和仿真实验证明了本文所提出算法的传输效率与传统的重传算法相比具有明显优势。

[1] ZHANG D, MANDAYAM N B. Analyzing random network coding with differential equations and differential inclusions [J]. IEEE Transactions on Information Theory, 2011, 57(12): 7932-7949.

[2] MOHAMMAD M, ZHANG Q, DUTKIEWICZ E. Reading damaged scripts: partial packet recovery based on compressive sensing for efficient random linear coded transmission [J]. IEEE Transactions on Communications, 2016, 64(2): 3296-3310.

[3] CHI K, JIANG X, HORIGUCHI S. A more efficient cope architecture for network coding in multi-hop wireless networks [J]. IEICE Transactions on Communications, 2009, 92(3): 766-775.

[4] LIU H, YANG H, WANG Y. CAR: coding-aware opportunistic routing for unicast traffic in wireless mesh networks [J]. Journal of Network & Systems Management, 2015, 23(4): 1-21.

[5] CHEN T, ZHONG S. An enforceable scheme for packet forwarding cooperation in network coding wireless networks with opportunistic routing [J]. IEEE Transactions on Vehicular Technology, 2014, 63(9): 4476-4491.

[6] 卢冀, 肖嵩, 吴成柯. 无线网络中应用机会式网络编码的广播重传方法 [J]. 西安交通大学学报, 2011, 45(2): 68-72. LU Ji, XIAO Song, WU Chengke. A broadcast retransmission method using opportunistic network coding in wireless networks [J]. Journal of Xi’an Jiaotong University, 2011, 45(2): 68-72.

[7] LI H, LI B, TRAN T T, et al. Transmission schemes for multicasting hard deadline constrained prioritized data in wireless multimedia streaming [J]. IEEE Transactions on Wireless Communications, 2016, 15(3): 1631-1641.

[8] 王斌, 王文鼐. 一种基于并行网络编码的无线广播重传方案 [J]. 南京邮电大学学报(自然科学版), 2014, 34(6): 9-14. WANG Bin, WANG Wennai. Wireless broadcast retransmission scheme based on parallel network coding [J]. Journal of Nanjing University of Posts and Telecommunications (Natural Science Edition), 2014, 34(6): 9-14.

[9] DAI M, KWAN H Y, SUNG C W. Linear network coding strategies for the multiple access relay channel with packet erasures [J]. IEEE Transactions on Wireless Communications, 2013, 12(1): 218-227.

[10]SUN W, ZHANG G X, GOU L. Network coding based broadcasting retransmission approach in satellite communications [J]. Advanced Materials Research, 2012, 54(7): 1302-1307.

[11]REN Z, WEN Y, YAO Y. An improved wireless broadcasting retransmission approach based on network coding [C]∥Proceeding of IEEE International Conference on Wireless Communications, Networking & Mobile Computing. Piscataway, NJ, USA: IEEE, 2012: 1-4.

[12]NGUYEN D, TRAN T, NGUYEN T. Wireless broadcast using network coding [J]. IEEE Transactions on Vehicular Technology, 2009, 58(2): 914-925.

(编辑 刘杨)

A Retransmission Algorithm with Dynamic Linear Combination Based on Network Coding in Wireless Multicast Networks

LI Bin1,LI Quan1,ZHANG Ruonan1,JIANG Yi1,YANG Rong2

(1. School of Electronics and Information, Northwestern Polytechnical University, Xi’an 710072, China;2. Engineering Workshop, Xi’an Jiaotong University, Xi’an 710049, China)

A retransmission algorithm with dynamic linear combination based on the network coding is proposed to meet the demands for decreasing the packets retransmission, to overcome the wireless channel fading, to build reliable wireless connection and to improve the efficiency of the bandwidth utilization in multicast networks. A dynamic linear combining coding algorithm (DLCCA) is used in the algorithm. Firstly, the transmitter in DLCCA sends original packets to users in the network. Then, the transmitter obtains the receiving status feedback from the users through control channel, and encodes the original packets that have not been correctly decoded by the users. Meanwhile, the encoding strategy is dynamically adjusted based on the network status so that the network throughput is improved. Furthermore, a coding algorithm with lower complexity is proposed, and the performance of the coding algorithm is analyzed. Theoretical result is obtained through analysis. Simulation results and comparisons with the transmission algorithm without network coding and the traditional XOR network coding algorithm show that the proposed algorithm greatly reduces 30% of packet retransmission, and the network throughput is increased.

multicast networks; network coding; dynamic linear combination

2016-05-11。 作者简介:李彬(1983—),男,博士,讲师。 基金项目:国家自然科学基金资助项目(61202394,61571370,61203233,61601365);陕西省自然科学基金资助项目(2016JQ6017);中央高校基础科研基金资助项目(3102014 KYJD033,3102015ZY093)。

时间:2016-10-10

10.7652/xjtuxb201612007

TN92

A

0253-987X(2016)12-0038-07

网络出版地址:http: ∥www.cnki.net/kcms/detail/61.1069.T.20161010.1753.008.html