基于可靠重传机制的无线网络数据广播算法

张莉华，魏长宝

（黄淮学院信息工程学院，河南 驻马店 463000）

基于可靠重传机制的无线网络数据广播算法

张莉华，魏长宝

（黄淮学院信息工程学院，河南 驻马店 463000）

为降低无线网络中数据重传时最优异或编码集合的复杂性，并减少数据传输次数、提高算法稳定性，提出一种新的基于可靠重传机制的无线网络数据广播算法 （wireless network broadcast data algorithm based on reliable retransmission mechanism，WDRRM)。基于随机线性编码理论，将网络中丢失的数据包进行线性异或编码，以生成新的数据包，并设计可靠的数据重传机制，对其进行重传；引入高斯消元法，在接收节点收到足够数目的编码包后，对其进行解码，获取原始数据包。理论分析与仿真结果显示：WDRRM算法的数据包平均重传次数以及控制开销低于其他对比编码算法。该文算法在一定程度上能够有效降低网络编码复杂性，提高网络性能。

异或编码；无线广播；数据重传；高斯消元

0 引 言

在无线网络中，广播是一种向多个接收节点传输相同数据包的重要机制，广泛应用于IPTV、视频点播（video on demand，VoD)及设备配置等领域[1]。可靠的广播意味着每个接收节点都可以正确收到源节点发送的数据包。在无线广播中，虽然自动重传请求（automatic repeat quest，ARQ)可使通信变得可靠，但是效率不高。在源节点传输数据包时，如存在至少一个节点没有正确收到数据包，则源节点利用该算法进行重传，会产生大量的控制包，如确认包（acknowledgement，ACK)或非确认包（negative acknowledgment，NAK)等，造成网络吞吐量下降。文献[2]首次提出网络编码，被认为是改善无线网络吞吐量的有效算法，不同于传统的“存储-携带-转发”机制，网络编码的核心思想是允许转发节点在转发消息前对数据包编码。为此国内外学者进行了大量研究，如吕政等[3]针对无线网络中源节点与中继节点或目的节点间链路不可靠的问题进行研究，提出协作通信联合信道网络编码资源分配机制；Prashanthi V等[4]分析了网络编码在无线网络中的应用，论述了如何降低网络负载；Kamal A E等[5]强调了在数据包广播重传过程中网络编码的安全性问题并提出了相关机制。

1 网络编码重传机制

近些年，Nguyen D等[6]提出了异或网络编码重传机制，其源节点维护用于记录每个数据包被其他节点正确接收的反馈矩阵表，在数据重传阶段，源节点将其他节点没有正确接收的数据包集合进行异或编码，生成新的数据包用于重传，通过一次重传，其他节点收到经过异或后的数据包，并恢复丢失的数据包，有效降低了数据包重传次数，提高了带宽利用率。其算法可以描述如下：源节点维护一个反馈矩阵表T，记为T=（K，M)，每个元素T（i，j)表示接收节点Ri是否正确收到数据包Pj，即若T（i，j)=1表示节点Ri正确收到数据包Pj，若T（i，j)=0则表示节点Ri丢失数据包Pj，其中，1≤i≤K，1≤j≤M。如图1（a)所示，源节点发送4个数据包，其余接收节点接收数据包，可以得到反馈矩阵T。节点R1成功接收到数据包P1、P2、P3，而没有收到数据包P4。根据传统的传输机制，源节点需要单独地重传数据包P1、P2、P3、P4，直到所有的接收节点成功地收到数据包。但是，利用基于异或的网络编码算法，源节点仅需要将P1、P2、P3、P4进行异或，生成新的数据包P=P1⊕P2⊕P3⊕P4，并进行重传操作。其他节点收到广播包P后，可以恢复出丢失的数据包。

以节点R1为例，通过P1⊕P2⊕P3⊕P4，可以得到丢失的P4。类似地，节点R2、R3、R4也可以单独恢复出各自丢失的数据包。然而，Nguyen D等没有考虑对于任意给定的反馈矩阵表T，如何确定其最优异或编码集合。

图1 反馈矩阵

对此，Xiao X等[7]提出一种基于网络编码的无线网络广播重传策略（NCWBR)，以解决该问题。该算法寻找T中每行第1个为0的元素结合相应的数据包进行异或。接收节点收到经过异或的数据包后，将试图恢复丢失的包，如果恢复成功，则源节点将反馈矩阵T中相应元素置1，否则仍为0。源节点根据接收节点反馈的信息更新矩阵T中元素，之后继续编码并重传，直到所有元素均为1。以图1（b)为例，NCWBR首先异或包P1、P2、P3，仅R2可以恢复丢失的数据包P3。源节点根据R2回复的信息，更新T（2，3)元素为1。但是，其他接收节点无法解码出其丢失的数据包，则T中相应元素T（1，1)、T（1，2)仍为0，源节点继续编码新的数据包并重传。

但是，NCWBR也存在一定的缺点。首先，寻找最优算法确定编码包被证明是复杂的NP问题[8-9]。此外，源节点在广播每个数据包后，需要更新反馈矩阵，会产生大量的控制开销。其次，该算法受限于丢失包的分布情况，导致性能不稳定。以图1（a)为例，源节点需要重传1个数据包，即P=P1⊕P2⊕P3⊕P4。在图1（b)中，源节点需要按顺序重传异或包P1⊕P2⊕P3、P1⊕P2⊕P4、P1⊕P2、P1⊕P3、P1⊕P2⊕P4、P1⊕P2、P1⊕P4、P2、P3，相比传统的ARQ机制重传次数更多。

为减少重传阶段数据包发送次数、降低重传带来的网络开销，本文提出了基于可靠重传机制的无线网络数据广播算法（WDRRM)。本文设计了可靠数据重传机制，避免了数据包分布丢失，其数据包重传次数由丢失数据包最多的接收节点决定，从而有效降低丢失数据包传输次数，达到改善无线网络数据传输效率目的，并测试了本文无线广播重传方案的可靠性能。

2 基于可靠重传机制的无线网络数据广播算法设计

2.1 系统模型

本文的无线网络广播传输模型如图2所示。

1)系统模型由1个源节点和K个（K＞2)接收节点组成，一组数据包需要广播给K个接收节点。本文假设源节点在固定的时间段Δt内广播数据包。

2)接收节点向源节点发送ACK或NAK信息，源节点接收并维护一个反馈矩阵表T，记为T=（K，N)，矩阵中元素T（i，j)表示接收节点Ri是否正确接收到数据包Pj，其中，1≤i≤K，1≤j≤N。

图2 系统模型

3)简便起见，本文假设所有的控制消息ACK或NAK均瞬间发送且不会丢失。

4)节点Ri数据包丢失率服从参数为pi（i=1，2，…，K)的伯努利分布。

2.2 随机线性网络编码

本文考虑网络中存在大小相同的n个数据包需要传输，数据包用X1，X2，…，Xn表示。源节点利用随机线性异或编码接收节点丢失的数据包，新的数据包Yi表示如下：

编码系数gij（1≤j≤n)为从限定域Fq中随机选取的值。每个接收节点收到n个编码包后，可以通过下面线性方程，解码出原始包：

系数矩阵由n个系数矢量G={gi1，gi2，gi3，…，gin}构成。根据Ho T和Li Y R等[10-11]提出的线性编码理论，对于接收节点，式（2)具有可解性的条件是：系数矢量矩阵G中的元素个数要与未知原始包数相同，即矩阵G中n个系数相互独立。根据文献[12]，当限定域Fq足够大，如Fq=29，编码成功率超过99.6%，编码失败主要是因为矩阵G中系数非独立，在满足网络性能条件下可以忽略不计。假设网络在广播数据时，存在1个源节点K个（K＞2)接收节点，节点Ri丢包率最大，N个原始数据包丢失D个，文献[10]已经证明在数据重传阶段，广播D个线性网络编码包，所有接收节点可以恢复出其丢失的数据包。这样，节点Ri需要D个编码包才能使其矢量矩阵达到满排列并解码出丢失的原始包，而其他接收节点Rj（1≤j≤K，j≠i)已经使其矢量矩阵达到满排列，因为丢失的数据包少于D个。这就是说，所有接收节点满足式（2)的可解性。

2.3 WDRRM算法设计

本文提出的WDRRM算法分为数据广播阶段和重传阶段，详细步骤如下：

1)源节点向K个接收节点广播N个数据包，每个数据包在固定的时间间隔发送出去，源节点通过收到的ACK或NAK反馈信息建立反馈矩阵T，并维护更新。

2)源节点广播N个数据包后，经过MΔt时间进入重传阶段。所有丢失数据包构成集合D={X1，X2，X3，…，Xn)，系数矢量gi={gi1，gi2，gi3，…，gin}（1≤i≤Mmax)中最大系数Mmax（从限定域Fq中随机选取)用来编码所有丢失的数据包，生成Mmax个编码包。Mmax为所有接收节点中丢失数据包最大数，由下式决定：

3)重传Mmax个编码包后，每个接收节点估算自身的编码矢量矩阵G的排列，并用ri表示。若ri≠N，对节点Ri意味着G没有达到满排列，之后节点Ri将通知源节点需要重传多少个编码包，才可以使G达到满排列，本文通过Ni表示需要的编码包，具体情况如下式所示：

式中i=1，2，…，K。

如在数据重传阶段接收节点Ri收到Mmax个编码包，则Ni为0。如节点Ri丢失2个编码包，则Ni=2。

为使接收节点向源节点反馈所需编码包个数Ni，本文在反馈包中添加一个新的域，用来记录需要编码包的个数Ni值，Ni普遍使用值不会大于255，所以1个字节的空间即满足Ni使用。

4)源节点根据每个接收节点反馈的Ni值更新Mmax，并在新的重传阶段生成Mmax个编码包，Mmax算法见式（4)。

5)重复3)和4)，直到所有接收节点矢量矩阵排列等于N，即Mmax=0，无丢失数据包，接收节点利用高斯消元法可以解码出原始数据包。

可见，本文提出的WDRRM与NCWBR算法的区别主要表现在以下方面：

1)WDRRM算法在组合丢失数据包时具有低复杂度。NCWBR算法需要更新反馈矩阵以及决定异或哪一个数据包，而WDRRM算法仅组合所有丢失数据包进行重传，而且编码包的个数由Mmax决定。

2)WDRRM算法不受丢失数据包分布的影响，主要由丢失数据包最多的接收节点决定编码包数。以图1（b)为例，利用NCWBR算法源节点需要重传9个数据包，比传统的ARQ机制的重传个数还多；利用WDRRM算法仅需要3个编码包：Y1=g11P1+g12P2+g13P3+g14P4、Y2=g21P1+g22P2+g23P3+g24P4、Y3=g31P1+g32P2+g33P3+g34P4，即可以使接收节点解码出所有丢失数据包。

3)WDRRM算法降低了在重传阶段反馈信息带来的开销。如使用NCWBR算法接收节点在接收到每个异或包后，需要反馈ACK或NAK控制包，以便源节点更新矩阵T。当广播系统中存在大量使用者时，会造成大量反馈信息开销。使用WDRRM算法所有接收节点仅在Mmax个编码包重传后才反馈信息，无需频繁地向源节点发送反馈信息，在一定程度上降低了控制开销。WDRRM算法的具体流程如图3所示。

图3 WDRRM算法流程

2.4 数学分析

本文限定平均每个数据包传输次数作为分析参数，令L1表示传统传输算法的平均传输次数。参考文献[2]给出了传统传输算法的平均传输次数L1计算算法：

式中K表示接收节点个数。

为了计算本文提出的WDRRM算法平均传输次数L2，给出如下假设：

WDRRM算法平均传输次数计算如下：

其中PX=max{P1，P2，…，PK}；P1，P2，…，PK表示待重传数据包；K表示接收节点个数。

证明：假设节点j具有最大丢包率，则有Pj=max {P1，P2，…，PK}，根据WDRRM算法重新广播数据包数由具有最大丢包率的接收节点决定，并且只有节点j的编码矢量矩阵G的排列为满置时，源节点才结束重传操作。也就是说，节点j至少成功接收M个数据包（包括原始数据包和编码包)。这意味着WDRRM算法传输阶段等价于源节点向节点j传输M个数据包。这样，可以得出总的传输数据包数如下：

则可以得出WDRRM算法的平均传输次数L2如式（6)所示。

3 仿真和性能分析

为体现WDRRM算法的优越性，将NCWBR算法和传统ARQ机制视为对照组。采用OPNET[13]仿真工具对这3种算法进行测试。具体仿真参数设置如表1所示。

表1 仿真参数表

3.1 仿真统计量

本文采用的评估指标为：1)在一次广播中不同丢包率和不同接收节点数对每个数据包平均重传次数的影响；2)归一化控制开销。

1)平均传输次数。平均传输次数是指在仿真时间内数据包（包括原始数据包和编码数据包)发送的总次数与网络中节点数的比值[15]，其计算式为

式中：TA——数据包平均传输次数；

Ttotal——数据包总传输次数；

N——网络中节点数。

2)归一化控制开销。归一化控制开销是指所有节点发送和转发的数据包所含的比特数与到达目的节点数据包所含的比特数的比值[16]。其计算模型为

式中：PC——整个网络输送的数据包含的比特数；

PD——到达目的节点数据包的总比特数。

3.2 仿真结果分析

图4显示了不同算法在不同丢包率情况下，对平均传输次数的影响，网络中有4个接收节点和20个数据包需要广播。由图可知，WDRRM算法的数据包平均传输次数最低。另外，当丢包率相当小时，NCWBR算法与WDRRM算法的数据包平均重传次数很接近。随着丢包率增加到0.3后，WDRRM算法性能要明显优于NCWBR算法和传统ARQ机制，主要因为WDRRM算法将需要重传的数据包进行组合，代替传统ARQ机制单个数据包重传的操作，与NCWBR算法相比，WDRRM算法编码包数由丢失率最高的接收节点决定，不受数据包丢失分布的影响，而NCWBR算法则性能不稳定。

图4 丢包率对平均传输次数的影响

图5显示了不同算法在不同接收节点个数情况下，对平均传输次数的影响，网络中接收节点丢包率为0.2，有20个数据包需要广播。当仅有两个广播接收节点时，WDRRM算法与其他对比算法在性能上没有大的差别。随着接收节点数K的增加，与其他两个算法相比，WDRRM算法的数据包平均传输次数低于其他两种机制，这是因为WDRRM算法数据包传输次数主要由丢包率最大的节点决定，在丢包率不变的情况下不会引起传输次数的明显增加。而相比于WDRRM算法，NCWBR算法丢包分布情况变得复杂，接收节点通过接收到的异或包解码出丢失包的概率降低，造成平均传输次数增加。

图5 接收节点个数对平均传输次数的影响

图6显示了在一次广播中，4个接收节点在不同丢包数量情况下，每个数据包平均传输次数的仿真结果。从图中可知，随着广播过程中丢失数据包数量的增加，两种算法的平均传输次数均减少，而WDRRM算法更加明显。在丢包数量较少情况下（见图6（a))，WDRRM算法较NCWBR算法性能改善不明显；在丢包数量较大的情况下（见图6（b))，WDRRM算法要明显优于NCWBR算法。这主要是因为丢包率较小时，仅有少数数据包需要重传，通过异或组合数据包的概率不高；当丢包数量增加时，数据包丢失分布变得不均，导致接收节点通过异或包解码出丢失包的概率降低，而平均传输次数相应变大。而对比算法NCWBR没有有效地对丢失数据包进行编码且编码复杂度较高，所以数据包平均传输次数高些。

图6 不同丢包率对平均传输次数的影响

图7显示了不同算法在不同丢包率情况下，对网络归一化控制开销的影响。依图可知，本文提出的WDRRM算法的归一化控制开销要低于对照组机制，这是因为WDRRM算法计算复杂度低，不受丢失数据包分布的影响，主要由丢失数据包最多的接收节点决定编码包数，在一定程度上降低了数据包重传次数；且目的节点无需将控制信息反馈给源节点，而对比机制具有较高的复杂度，且其选取编码包的效率较低，导致归一化控制开销比较高。

图7 丢包率对归一化控制开销的影响

4 结束语

本文提出了一种新颖的基于可靠重传机制的无线网络数据广播算法WDRRM，有效降低了数据包平均重传次数，通过在不同情况下进行大量仿真，验证WDRRM算法的性能。仿真结果显示，与现有基于异或的网络编码算法（如NCWBR算法)相比，本文提出的WDRRM算法的传输效率更高，在具有大量接收节点的情况下更为突出。

[1]后学知，张大方，何施茗.无线广播中基于网络编码的隐藏终端解决机制[J].小型微型计算机系统，2013，34（2)：238-242.

[2]Ahlswede R，Cai N，Li S Y R，et al.Network information flow[J].IEEE Trans on Information Theory，2000，46（4)：1204-1216.

[3]吕政，余志军，刘海涛.协作通信中联合信道-网络编码的性能分析与资源分配[J].西安交通大学学报，2012（4)：83-87.

[4]Prashanthi V，Guru R.Network coding-based communication in wireless ad-hoc networks[C]∥Proceedings of Communications and Signal Processing （ICCSP).Melmaruvathur：IEEE Press，2014：1040-1044.

[5]Kamal A E，Mohandespour M.Network coding-based protection[J].Optical Switching and Networking，2014，26（11)：189-201.

[6]Nguyen D，Tran T，Nguyen T.Wireless broadcast using network coding[J].IEEE Trans on Vehicular Technology，2009，58（2)：914-925.

[7]Xiao X，Yang L M，Wang W P.A wireless broadcasting retransmission approach based on network coding[C]∥Proc 4th IEEE Int'l Conf.Circuits and Systems for Communications.IEEE，2008：782-786.

[8]Chi K K，Jiang X H，Ye B L.Efficient network coding-based loss recovery for reliable multicast in wireless networks[J].IEICE Trans on Communication，2010，93（4)：971-981.

[9]Poonguzharselvib B，Vetrisselvi V.Survey on routing algorithms in opportunistic networks[C]∥Proceedings of 2013 International Conference on Computer Communication and Informatics（ICCCI).Coimbatore：IEEE Press，2013：1-5.

[10]Li Y R，Yetmg R W，Cai N.Linear network coding[J]. IEEE Trans on Information Theory，2003，49（2)：371-381.

[11]Ho T， Chen L，Chiang M，et al.Congestion control for multicast flows with network coding[J].Information Theory IEEE Tran，2012，58（9)：5908-5921.

[12]Wei S，Li J，Chen W.Power adaptive net work coding for a non-orthogonal multiple-access relay channel[J]. IEEE Transactions on Communications，2014，62（5)：872-887.

[13]Keller L，Atsan E，Argyraki K.SenseCode：Network coding for reliable sensor networks[J].ACM Transactions on Sensor Networks，2013，9（2)：1452-1461.

[14]Bettstetter C，Resta G，Santi P.The node distribution of the random waypoint mobility model for wireless Ad Hoc networks[J].IEEE Transactions on Mobile Computing，2003，2（3)：257-269.

[15]卢冀，肖嵩，吴成柯.无线网络中应用机会式网络编码的广播重传方法[J].西安交通大学学报，2011，45（2)：68-72.

[16]任智，徐中浩，曹建玲，等.基于跨层设计的无线传感器网络节能双向梯度路由算法[J].电子与信息学报，2013，35（1)：133-140.

A wireless network broadcast data algorithm based on reliable retransmission mechanism

ZHANG Lihua，WEI Changbao
（College of Information Engineering，Huanghuai University，Zhumadian 463000，China）

A new wirelessnetwork broadcastdata algorithm based on reliable retransmission mechanism （WDRRM）was proposed to decrease the complexity of the optimal XOR coding set and reduce the number of data retransmission as well as improve the stability of algorithm.The loss data packets in network were transformed into new data packets by XOR according to random linear coding theory.And a new reliable retransmission mechanism was designed for retransmitting these data packets.The original data packet was decoded by introducing Gaussian elimination after a sufficient number of code packages were received at the receiving node.Theoretical analysis and simulation resultsshow that，compared with othercodingalgorithms，the proposed WDRRM algorithm is superiorin average packetretransmission times and controlexpenses and can effectively reduce the network complexity ofnetwork coding and significantly improve the performances of the network.

XOR coding；wireless broadcasting；data retransmission；Gaussian elimination

A

：1674-5124（2015）10-0098-06

10.11857/j.issn.1674-5124.2015.10.022

2014-12-19；

：2015-01-11

河南省科技攻关计划项目（122102210430)河南省教育厅重点科技攻关项目（13A520786)

张莉华（1978-)，女，河南驻马店市人，副教授，硕士，研究方向为通信协议、网络信息安全。