无线网络中基于机会网络编码的加权广播重传

苟 亮张更新 孙 伟 谢智东 边东明

(解放军理工大学通信工程学院 南京 210007)

1 引言

网络编码的概念于2000年首次提出[1]，能够极大地提高网络吞吐量，并减小传输时延[2,3]。然而，要达到网络编码的最大吞吐量是一个NP问题。因此，为了提高传输效率，研究者提出了一些将网络编码应用到无线组播/广播网数据重传中的启发式方法。其中，机会网络编码重传(Opportunistic Network Coding Retransmission, ONCR)方案只需要进行 XOR操作就可实现编解码，复杂度较低，因此对ONCR的研究逐步成为主流，取得了很多成果。肖潇等人[4]给出了一种 NCWBR (Network-Coding-based Wireless Broadcasting Retransmission)方案，该方案能有效减少平均传输次数。文献[5,6]中提出了两种更加高效的重传策略(Improved Network-Coding-based Broadcasting Retransmission,INCBR和Wireless Broadcasting Retransmission based on Opportunistic Network Coding,WBRONC)，在提高重传效率的同时减小了计算复杂度。然而，以上方法都是基于链路状态相同的网络环境，而对各路径丢包率不同条件下的ONCR重传方法研究很少。截止目前，仅文献[7]提出了一种基于图论的最大加权团(Maximum Weig-hted Clique, MWC) 算法。但是，该算法的计算复杂度随数据包数目、节点数目和丢包率呈指数增长，对节点能量和处理能力有限，规模较大的网络不适用。

在上述研究成果的基础上，本文对ONCR在链路丢包率不同时的无线广播重传方法进行了分析研究，以减少传输次数和计算复杂度为目标，提出了一种新的基于机会网络编码的加权广播重传(Weighted Opportunistic Network Coding Retransmission WONCR)方案。该方案以构建加权数据色分布矩阵(Weighted Packet Distribution Matrix, WPDM )为基础，采用一种新的数据包调度算法对编码数据包进行选取。为了验证所提方案的有效性，本文对平均传输次数和计算复杂度进行了分析和仿真，结果表明该方案传输效率高，且计算复杂度较低。

2 系统模型

本文采用通用无线广播模型，该模型包含一个源节点S和N个接收节点，假设源节点广播M个原始数据包给N个接收节点。广播过程分为两个阶段：初始阶段和重传阶段。在初始阶段，源节点逐个广播M个原始数据包，接收节点接收到原始数据包后，将每个数据包的状态信息（成功接收或丢失)反馈给源节点。在重传阶段，源节点根据接收节点反馈的状态信息选择来自不同接收节点的丢包进行 XOR编码，再将编码包重传给接收节点。

假设源节点 S在广播数据包后，接收节点 Ri能根据接收信号信噪比准确估算出链路状态信息，且状态信息在反馈信道中不存在丢失。另外，假设源节点和各接收节点之间的信道是相互独立的，且在广播一个数据包的时隙内丢包率不变。

定义1 加权数据包分布矩阵（WPDM)指传输过程中，源节点通过收集各接收节点反馈的数据包状态信息和链路状态信息形成列表。该列表是一个N×M的矩阵，行系数和列系数分别表示接收节点和原始数据包，矩阵中的元素用;表示。如果，则表示接收节点Ri没有接收到数据包Pj，且源节点和Ri之间的链路成功传输1个数据包的概率为1–pi，其中pi为源节点和接收节点Ri之间链路的丢包率；如果wi,j=0，则表示Ri已成功接收到数据包Pj。表1给出了1个具有6个接收节点和8个原始数据包的WPDM示例。

表1 加权数据包分布矩阵(WPDM)

证明 给定接收节点 Ri和编码包kCP ，如果WPDM中对应的所有元素为0，则说明Ri已成功接收参与编码的所有数据包，因而此次重传对Ri来说收益为0。如果Ri原本缺少这些数据包中的2个或2个以上，则不能通过XOR操作从编码包中解出任何原始数据包，其收益也为0。除去这两种情况，当且仅当其中1个数据包丢失的情况下，Ri才有可能解出1个原始数据包，即元素中有且仅有一个为1，其它全为0，从而证明式(1)。

定义3 总传输增益kG 指在第k次传输中发送编码数据包，成功接收并译出原始数据包的接收节点数目的期望值，即

不同的编码包可以使不同的接收节点受益，如果每次重传的编码包都能使更多的接收节点受益，即总传输增益更大，那么重传的次数就会更少，传输效率就会更高。因此，本文所描述问题的核心就是如何选择或调度原始数据包进行编码，使每次重传都能让最多的接收节点受益。

3 WONCR方案

基于以上模型，本文提出了一种新的启发式广播重传方案 WONCR，其基本思想是直接通过WPDM选取原始丢包进行编码，这种方法直观且效率更高。WONCR方案的实施分5个步骤，其中第3个步骤包括1个数据包调度算法，具体步骤描述如下。

步骤..1 初始传输阶段，发送节点将所有的原始数据包广播给所有接收节点。

步骤2 在初始传输或是在某次重传结束之后，对 WPDM 矩阵进行初始化或更新。源节点首先通过无线信道从每个接收节点收集相应的数据包状态信息和链路状态信息，然后根据这些状态信息形成WPDM。WPDM矩阵形成后，源节点判断WPDM是否为全“0”矩阵。如果是，则代表每个接收节点都收到所有M个数据包，整个传输过程结束；如果不是，则转到步骤3继续执行。

步骤3 在初始化或WPDM更新结束后，源节点开始选取第k次传输的编码数据包，调度过程由一个加权数据包调度算法具体实施，具体如表2所示。

表2 加权数据包调度算法

步骤4 根据步骤3中存储在数组T中的数据包系数，源节点将选取的数据包使用 XOR操作进行编码，并广播重传给所有接收节点，接收节点再进行解码。然后，根据各接收节点反馈的状态信息生成新的WPDM矩阵，如果WPDM矩阵不是全“0”矩阵，则从步骤2开始新一轮的调度、编码和重传。

步骤 5 当所有接收节点都成功接收到它们需要的数据包，即WPDM为全“0”矩阵后，整个传输过程结束。如果源节点有更多信息需要广播，则系统将从步骤1开始新一轮的传输。

4 性能分析

4.1 平均传输次数

在数据包数目M足够大时，该结果可以进一步扩展，即对具有N个接收节点的系统，其数据包传输次数由链路丢包率最大的接收节点所需的传输次数决定，得出系统的理论传输次数为

每个数据包平均需要的传输次数为

4.2 计算复杂度

在每次编码包的选取过程中，WONCR,INCBR和NCWBR 3个调度方案首先为N个接收节点确认M个数据包的状态。如果有接收节点丢失了数据包，那么源节点将寻找所有可能的2M 个包的组合。因此，算法的时间复杂度为。然而，MWC方案将WPDM中各非0元素转换为邻接图的顶点，最多为NM×个顶点，源节点将寻找所有可能的( )2NM×个组合。因此，其算法时间复杂度为随着N和M的增加，该方案复杂度比WONCR, INCBR和NCWBR方案要高得多。

表3 4种调度方案的计算复杂度

5 仿真结果

为了验证WONCR方案的有效性，本节对平均传输次数和计算复杂度进行了仿真实验。假设链路的平均丢包率为ε，源节点和各接收节点之间的链路丢包率在[εσ-,εσ+]范围内，且均匀分布。通过500次的蒙特卡洛仿真，得出了不同网络条件下WONCR方案的平均传输次数和计算开销，并与传统的 ARQ方案，MWC方案及经过加权修改后的NCWBR方案和INCBR方案进行了比较。

5.1 平均传输次数

根据式(5)和仿真条件设定，可以得出平均传输次数的理论上界为

图 1(a)给出了各方案的平均传输次数随数据包数目变化的情况。从仿真结果可以看出，MWC,WONCR和 INCBR方案的平均传输次数远小于ARQ方案，而NCWBR方案的性能介于两者之间。随着数据包数目的增加，ARQ方案和NCWBR方案的平均传输次数几乎不变；而MWC, WONCR和 INCBR方案则随着数据包数目的增加而逐步减少，并越来越接近理论上界，这是因为数据包越多，编码机会就越多；WONCR方案的性能稍逊于MWC方案，但优于INCBR方案。各方案的平均传输次数同接收节点数目变化的情况如图 1(b)所示。同以上结果类似，MWC, WONCR和INCBR方案的性能要远好于ARQ和NCWBR方案，4个方案的平均传输次数均随接收节点数目的增加而增多。WONCR方案和MWC方案的平均传输次数随接收节点数目的增加有很小的增大，INCBR方案次之，ARQ方案增加较大但曲线斜率逐步减小，而NCWBR方案则是线性增大，在接收节点数目达到50~60时，NCWBR方案的平均传输次数甚至超过了ARQ方案，这是由于NCWBR在选取数据包时未对可解性进行判断，从而导致很多的无效传输。图 1(c)给出了各方案的平均传输次数随丢包率变化的比较关系。从图 1(c)中看出，4个方案的平均传输次数均随丢包率的增大而快速增加，但WONCR和MWC方案的性能远好于NCWBR和ARQ方案，INCBR次之，MWC方案性能最好。

此外，本文还对各接收节点链路丢包率相同和丢包率差异较大情况下的传输性能进行了实验比较。结果表明，在丢包率相同情况下, WONCR方案的重传性能最好，且稍优于MWC方案。这是因为MWC方案对选取的数据包集合中的每个元素都要求可解，从而丧失了少量的编码机会，而WONCR方案以传输增益最大化为目标，虽然选取的数据包对某些接收节点可能不具有可解性，也可能不是最优解，但在MWC方案丧失编码机会较多的情况下，MWC方案性能将优于MWC方案。在各接收节点丢包率差异较大时, WONCR和MWC方案的性能最佳，INCBR和NCWBR方案次之，ARQ方案最差。

图1 各情况下的重传性能比较

图2 各情况下的计算开销比较

5.2 计算复杂度

本节对WONCR, NCWBR, INCBR和MWC 4种方案的计算开销进行了仿真验证，使用的仿真计算机CPU为Intel (R) Core (TM)2 2.5 GHz，内存为2 GB，仿真实验软件为Matlab R2008a。

图2给出了4种方案计算开销随数据包数目，接收节点数目及丢包率变化的比较曲线。从仿真曲线可以看出，4种方案的计算开销均随数据包数目，接收节点数目及丢包率的增大而增大，但WONCR,INCBR和NCWBR方案的处理时间远小于MWC方案。WONCR和NCWBR方案的计算开销随接收节点数目增加而线性增大，且曲线斜率不大。从计算开销的角度来看，这两种方案更适合于节点较多的大规模广播网络。

由以上仿真可以看出：MWC方案传输效率最高，但其计算复杂度远高于其它方案，不适用于能量和计算资源受限的系统；WONCR在传输效率上接近MWC方案，且其计算开销相对较低，在传输效率和复杂度之间取得了很好的平衡，具有更高的应用价值。

6 结束语

本文对丢包率不同条件下基于机会网络编码的无线广播重传方法进行了分析，提出了使用WPDM矩阵进行编码数据包调度的WONCR方案。分析和仿真结果表明，该方案具有传输效率高，计算复杂度低的特点。WONCR方案可以在保证较高传输效率的同时减小节点的处理负荷，使基于机会网络编码的无线广播重传性能得到很大提升，能广泛应用到卫星广播网、无线传感器网和行星际互联网等系统的广播业务中，具有很高的应用价值。

[1] Ahlswede R, Ning Cai, Li S-Y R, et al.. Network information flow[J]. IEEE Transactions on Information Theory, 2000,46(4): 1204-1216.

[2] Li Zong-peng, Li Bao-chun, and Lau L C. A constant bound on throughput improvement of multicast network coding in undirected networks[J]. IEEE Transactions on Information Theory, 2009, 55(3): 1016-1026.

[3] Traskov D, Heindlmaier M, Médard M, et al.. Scheduling for network-coded multicast[J]. IEEE/ACM Transactions on Networking, 2012, 20(5): 1479-1488.

[4] 肖潇, 王伟平, 杨路明, 等. 基于网络编码的无线广播重传方法[J]. 通信学报, 2009, 30(9): 69-75.Xiao Xiao, Wang Wei-ping, Yang Lu-ming, et al.. Wireless broadcasting retransmission approach based on network coding[J]. Journal on Communications, 2009, 30(9): 69-75.

[5] 孙伟, 张更新, 边东明, 等. 卫星通信中基于网络编码改进的广播重传策略[J]. 宇航学报, 2013, 34(2): 231-236.Sun Wei, Zhang Geng-xin, Bian Dong-ming, et al.. An improved network-coding-based broadcasting retransmission scheme in satellite communications[J]. Journal of Astronautics, 2013, 34(2): 231-236.

[6] Gou Liang, Zhang Geng-xin, Sun Wei, et al.. WBRONC:efficient wireless broadcast retransmission based on opportunistic network coding[J]. Frequenz, 2013, 67(3/4):117-125.

[7] Wang Xiu-min, Wang Jiang-ping, and Xu Yin-long. Data dissemination in wireless sensor networks with network coding[J]. EURASIP Journal on Wireless Communications and Networking, 2010, (1): DOI:10.1155/20101465915..