多源多中继无线网络中基于随机线性网络编码的调度方案

王 练 梁申虎 彭代渊



多源多中继无线网络中基于随机线性网络编码的调度方案

王 练*①②梁申虎①彭代渊②

①(重庆邮电大学计算机科学与技术学院 重庆 400065)②(西南交通大学信息科学与技术学院 成都 611756)

现有多中继无线网络中传输调度方案主要针对单信源且转发链路状态相同的情况，多采用顺序转发的调度方式，传输效率较低。针对此问题，该文提出一种基于随机线性网络编码的优先级调度方案。该方案在不同的传输阶段，利用信息包接收状态或编码向量之间的线性关系生成反馈信息，计算中继节点的有效信息包数。在转发链路状态不同的情况下，综合考虑各中继节点的有效信息与链路传输可靠性，确定优先级，从而完成调度。该方案实现了多中继对多信源信息的协同转发，在转发链路状态差异较大时，能自适应地选择最优转发节点和路径，提高信息包的传输成功率。仿真结果表明，相比传统基于单信源或顺序调度的方案，该方案能有效提高网络吞吐量，减少重传次数。

无线网络；随机线性网络编码；调度；多源多中继

1 引言

Ahlswede等人[1]在2000年提出了网络编码的思想，并证明其可以逼近最大理论传输容量。随着研究的深入，网络编码被广泛应用于无线网络传输。其中，文献[2-4]指出将网络编码应用于无线广播重传能有效提升无线传输吞吐量。中继协作传输的应用实现了远距离无线网络的有效通信[5,6]。在此基础上，Fan等人[7]率先研究了机会式网络编码在中继协作多播中的应用，考虑了两个接收端的情况。随后，Lu等人[8,9]提出该场景下基于随机线性网络编码(Random Linear Network Coding, RLNC)的高效调度方案，并将该方案拓展到双小区广播系统，Huang等人[10]改进此方案，以稀疏矩阵为基础，采用确定性的算法获取线性无关编码向量，降低了编解码复杂度。由于网络节点的分布式特性，总可能出现多个信源同时传输信息。针对该情况，Amerimehr等人[11]对使用网络编码的双向单中继无线网络调度进行了时延和吞吐量的分析，但只适合于两者或两者为一组的相互通信。Wei等人[12]提出一种多源多中继无线网络中计算与转发的网络编码信道设计方案，用基于候选集的搜索算法确定网络编码系数，提高了网络传输速率，对于调度只是概念性的涉及。Ding等人[13]提出了多中继无线网络中基于网络编码的自适应转发调度(Adaptive Forwarding with Network Coding, AF-NC)和结合自动重传请求(Automatic Repeat Quest, ARQ)的自适应转发重传调度(Adaptive Forwarding with Network Coding and Retransmission, AFR-NC)，减少了传输所需时隙，但该方案中的多中继转发和重传均是采用顺序调度，对给定的多源模型，也只是依次单独执行各源节点的传输。Aslam等人[14]将多跳转发抽象为马尔科夫随机过程，对使用随机网络编码的多源多跳协作网络的网络覆盖进行了研究，但要求每跳能够解码原始信息的节点不少于源节点数才能保证信息继续传输。

上述多中继调度方案多是基于顺序转发，但广播会使多个中继节点有相同的信息，若按该方法总会优先传输顺序靠前的中继节点所拥有的有效信息包，这并不是最理想的方式，传输成功率也会受到很大影响。此外，这些调度方案只适用于单信源且具有相同转发链路状态的网络环境，与实际网络传输有差异。在上述研究基础上，本文研究了不同链路状态下的多中继协作传输，针对多信源信息在多中继节点的转发，以提高吞吐量和可靠性为目标，提出一种多源多中继无线网络中基于随机线性网络编码的优先级调度方案(Priority Scheduling based on Network Coding, PSNC)。该方案根据不同的转发链路状态，通过预算有效信息包的最优到达数实现调度。为了验证PSNC方案的有效性，本文对吞吐量和重传次数进行了分析和仿真。结果表明，与基于网络编码的多中继顺序调度(Order Schedulingbased on Network Coding, OSNC)、基于网络编码的多中继随机转发调度(Random Schedulingbased on Network Coding, RSNC)以及AF-NC方案相比，所提方案在一定条件下吞吐量和可靠性都具有明显优势。

2 网络模型

PSNC方案分为初始阶段和重传阶段。初始阶段，所有源节点分别广播信息包给中继节点，中继节点缓存收到的信息包；根据各中继节点的信息包覆盖数和各转发链路的丢包率两个条件进行初始调度，转发有效信息给节点。在重传阶段，源节点根据反馈信息，重传所有中继节点都丢失的信息包；再利用节点和各个中继节点的全局编码矩阵之间的向量线性关系与不同的链路丢包率确定调度优先级，获取重传节点，并对该节点已经收到信息进行再次随机编码后发送给。两个阶段采用完全不同于现有方案的分阶段反馈方式和预算优先级的调度策略。

图1 系统模型

图2的缓存结构

使用确定性网络编码时会采用接收状态表征信息包接收情况，优点是简单且易实现。本方案采用RLNC，在传输过程中可局部使用该表示方法，是由于没有进入重传阶段前，所有已传输的原始编码信息包都是唯一且确定的。因此，使本方案的编码传输过程得到局部简化。

3 优先级调度方案

PSNC方案是从各个中继节点对源节点信息的覆盖情况出发，利用节点与各中继节点之间的原始信息接收差异以及各转发链路的不同丢包率选取最优中继传输点。其优势主要体现在，整个传输方案都从多个源节点发送信息的角度出发，考虑多缓存队列，使基于RLNC的传输方案变得简单。此外，所有的转发调度是建立在传输最优到达的选择机制之上，充分利用网络资源的同时提高传输吞吐量。本节主要的符号含义，如表1所示。

表1 符号的含义

符号含义 第个源节点 第个中继节点 到的链路丢包率 中继节点到的链路丢包率 的编码矩阵 的编码矩阵 中继对原始信息的覆盖 节点的接收状态矩阵 两个节点之间的接收状态差异 节点能为提供的有效信息包数 中继对第个源节点所发信息的覆盖数 能为提供线性无关的编码向量数

3.1 初始传输调度

根据各中继节点的接收状态矩阵了解相应的信息包接收情况，通过调度中继节点将已经收到的信息包转发给。在节点没有接收到任何信息包之前，其接收状态矩阵为的零矩阵。

定义1 所有中继节点的接收状态矩阵相对应元素进行逻辑或运算的结果表示中继对原始信息的覆盖。

定义2 两个节点的状态矩阵之差表示它们的信息包接收差异，即。

由式(2)可知，被选节点是所有候选节点中理论上能成功传输最多新信息包给的。被选节点完成转发后，更新和候选节点集。根据变化结果重复调度步骤，获取下一个转发节点，直到与相等或候选节点集为空，就结束初始阶段。由上文可知，已获取的信息包不会再被后续节点转发，避免了信息包的重复发送。通过调度，减少了参与转发的中继节点数，让传输更集中，也更有效。初始传输调度的主要伪代码如表2所示。

表2 初始调度主要伪代码

输入：输出：//初始调度; //获得对信息的覆盖；; //初始为的零矩阵while(1)for ()//初始; //计算和的信息包差异由得出; //可提供的有效信息包数if ; //加入集合endifendfor; //获得最佳转发节点转发a缓存的有效信息包；; //记录转发节点数更新；if ||Break;else; //去除已转发的节点endifendwhile

3.2 重传调度

完全覆盖原始信息后的中继节点，通过重传调度，转发有效信息给。此时，和各中继节点已接收到各源节点的部分或全部信息。经过到的重传，已经打破了初始阶段的接收状态反馈。根据文献[15]可知RLNC是在有限域GF(28)内随机选取编码系数，生成两个线性相关编码包的概率可以小到忽略不计，而生成两个相同编码包的概率还要小很多，因此不能像确定性网络编码那样，固定性地重传丢失的那些信息包。那么，再发送确定性的反馈信息也就没有意义，这也是RLNC最根本的特点。所以，在接下来的传输中将编码向量之间的线性关系作为新的反馈信息。

(4)

(6)

在重传之前，先再次编码被选节点已有的信息。根据RLNC的原理，当接收节点的编码矩阵达到满秩则该矩阵可逆，就能实现完全解码。对于中继节点，若收到个编码包后，对这些编码包再次编码并不能生成与原个编码包线性无关的新编码包。对应到向量，由原有的个线性无关向量随机任意表示而成的新向量与原个向量一定存在线性相关关系。由此看来，重新编码无实际意义。但当可以为节点提供线性无关信息包时，对中所有编码包重新编码后获得的任意一个编码包都能使增加1，促进解码。因此，为了使重传更有效，对被选节点原有的信息再次编码后再发送。被选节点重传后，若仍不能完全解码，重复该调度过程获取新的重传节点，直到能完全解码为止。重传调度过程的主要伪代码如表3所示。

当原始传输的文件很大时，同时处理多源节点的信息会对节点的资源提出更高的要求，为了保证有效的调度传输，采取分块传输模式，将各源节点的文件分批次进行传输。

表3 重传调度主要伪代码

输入：,输入：//重传调度while (不为全1矩阵)//未完全覆盖for (); //所传信息被覆盖的数量if //的信息存在绝对丢失至少重传个编码包；endif根据接收包更新; //更新；endforendwhile//达到完全覆盖；构建; //的编码矩阵构建; //的编码矩阵while ()//可完全解码就结束for (); //能提供给的线性无关包数if ；endifendfor；再次编码中的信息包；发送至少个编码包给；更新；endwhile

4 性能分析

4.1 吞吐量

(8)

同理，若转发数据包全部由丢包率最大的链路传输给接收端，再加上初始阶段的所需传输时隙期望，可以得出的最大期望值。

4.2 重传次数

重传次数由两部分构成，一是各中继节点在初始阶段未完全覆盖原始信息，源节点重传信息包达到该状态的重传次数；二是中继节点重传阶段传输信息包的次数。因为本方案考虑同一链路上的重传信息包和初始传输具有相同的丢包率，加上各转发链路的状态不同，使得转发过程具有不确定性，所以无法给出所需重传次数的准确表达式，只能通过仿真结果进行描述。

4.3 复杂度分析

表4 算法时间和空间复杂度

复杂度AF-NCOSNCRSNCPSNC 时间 空间

5 仿真结果

本文采用Matlab R2015a仿真软件，测试计算机为Intel Core i7-5500U, 8 G RAM, Windows7操作系统。在此环境下，将本文PSNC方案与OSNC, RSNC以及AF-NC方案进行了仿真对比和分析。由于编码系数的随机性和信息包丢失的偶然性，导致相同条件下的两次完整传输在吞吐量和重传次数上可能有明显差异。为了更准确地分析系统性能，采用平均吞吐量和平均重传次数作为指标。根据仿真条件，设,，链路丢包率(,),,是一个随机序列的丢包率数组。通过多次仿真实验和数据处理后得到以下结果。

图3(a)中，OSNC方案和AF-NC方案的吞吐量很接近，且明显低于其他方案。而PSNC方案的吞吐量最大，因为同时考虑了中继节点能否提供有效信息、提供多少有效信息和信息包传输到达率，使传输更集中，成功率更高。RSNC方案的吞吐量介于PSNC和AF-NC之间，原因在于随机调度产生的结果肯定低于每次按最佳选择的PSNC方案，基于顺序转发的OSNC和AF-NC方案极其依赖节点序列，而随机调度使每次的结果或好或坏，但RSNC方案获得较大吞吐量的概率要大，平均结果更好。

图3(b)是各方案的平均重传次数随传输数据包数变化的对比结果。4种方案的平均重传次数均随原数据包数的增加而增加，当原数据包数为20时，各方案的平均重传次数相差较小；而原数据包数增加到120时，PSNC的平均重传次数明显优于RSNC, AF-NC和OSNC方案。随着原数据包数的增加PSNC的增加趋势明显缓和很多，优势更加突出。在相同的条件下，PSNC会选择低丢包率的链路进行转发，从而减少丢失，所需重传次数减少。

其他条件不变，平均吞吐量和平均重传次数随中继节点数变化的对比如图4所示，随中继节点数的增加，4种方案的吞吐量有所增大，而平均重传次数不断减少，最终都逐渐趋于平稳。说明一定范围内，适当增加中继节点数量可以减少数据包的绝对丢失，从而提高吞吐量，减少重传次数。但系统性能由多个条件共同决定，中继节点数所带来的影响只是一定程度上的。

平均吞吐量和平均重传次数随转发链路状态差异变化(转发链路丢包率的平均值和方差都增加，以方差和平均值的比值为横坐标，表示转发链路之间状态差异在增大)的对比，如图5所示。

从图5(a)可看出，其他条件不变，各转发链路状态差异不断增大时，由于丢包率的增加，使吞吐量整体呈现下降的趋势，但PSNC方案的优势会越来越明显，下降的趋势较为平缓。如图5(b)所示，PSNC的平均重传次数优势也随着链路状态差异的增大而逐渐明显，整体呈增加趋势是由于丢包率是增大的。OSNC和AF-NC方案到后边急剧上升主要是由于随着丢包率和丢包率差异的增大使原本就存在劣势被继续放大，而RSNC方案的随机方式在链路集不大的情况下不会持续出现极端劣势。

6 结论

本文改进了多源多中继无线网络传输模型，基于随机线性网络编码提出了优先级调度方案PSNC。该方案综合考虑了节点的有效信息包数与链路传输可靠性，在转发链路状态不同的情况下，优先选择有效信息包数较多且链路可靠性较高的节点传输信息，使传输更集中，更有效，从而提高信息包的传输成功率，减少反馈次数和传输次数。分析与仿真结果表明，PSNC具有吞吐量高，可靠性强的特点，使多源多中继无线网络协作传输性能得以明显提升。特别在丢包率较高，转发链路间状态差异较大的无线网络环境下，优势会更加突出。该方案可推广到移动通信网络、Ad hoc网络等。

图3 不同原信息包个数下的性能对比

图4 不同中继节点个数下的性能对比

图5 不同转发链路状态差异下的性能对比

[1] AHLSWEDE R, CAI N, LI S Y R,. Network information flow[J]., 2000, 46(4): 1204-1216. doi: 10.1109/18.850663.

[2] NGUYEN D, TRAN T, NGUYEN T,. Wireless broadcast using network coding[J]., 2009, 58(2): 914-925. doi: 10.1109/ TVT.2008.927729.

[3] 周志恒, 周亮. 多播网络中基于网络编码的高效丢失恢复机制[J]. 电子与信息学报, 2012, 34(8): 1962-1967. doi: 10.3724/SP.J.1146.2011.01233.

ZHOU Zhiheng and ZHOU Liang. Efficient loss recovery based on network coding in multicast networks[J].&, 2012, 34(8): 1962-1967. doi: 10.3724/SP.J.1146.2011.01233.

[4] 苟亮, 张更新, 孙伟, 等. 无线网络中基于机会网络编码的加权广播重传[J]. 电子与信息学报, 2014, 36(3): 749-753. doi: 10.3724/SP.J.1146.2013.00598.

GOU Liang, ZHANG Gengxin, SUN Wei,. Weighted broadcasting retransmission based on opportunistic network coding in wireless networks[J].&, 2014, 36(3): 749-753. doi: 10.3724/ SP.J.1146.2013.00598.

[5] KRAMER G, GASTPAR M, and GUPTA P. Cooperative strategies and capacity theorems for relay networks[J]., 2005, 51(9): 3037-3063. doi: 10.1109/TIT.2005.853304.

[6] LIANG Y and VEERAVALLI V V. Cooperative relay broadcast channels[J]., 2007, 53(3): 900-928. doi: 10.1109/TIT.2006.890726.

[7] FAN P, ZHI C, WEI C,. Reliable relay assisted wireless multicast using network coding[J]., 2009, 27(5): 749-762. doi: 10.1109/JSAC.2009.090615.

[8] LU L, XIAO M, RASMUSSEN L K,. Efficient scheduling for relay-aided broadcasting with random network codes[C]. 2011 IEEE 22nd International Symposium on Personal Indoor and Mobile Radio Communications, Toronto, Canada, 2011: 1815-1819. doi: 10.1109/PIMRC.2011. 6139821.

[9] LU L, SUN F, XIAO M,. Relay-aided multi-cell broadcasting with random network coding[C]. IEEE International Symposium on Information Theory and its Applications, Taichung, China, 2010: 957-962. doi: 10.1109/ ISITA. 2010.5649536.

[10] HUANG L and SUNG C W. Scheduling and network coding for relay-aided wireless broadcast: Optimality and heuristic[J]., 2014, 63(2): 674-687. doi:10.1109/TVT.2013.2281392.

[11] AMERIMEHR M H and ASHTANI F. Delay and throughput analysis of a two-way opportunistic network coding-based relay network[J]., 2014, 13(5): 2863-2873. doi: 10.1109/TWC. 2014.040914.121461.

[12] WEI L and CHEN W. Compute-and-forward network coding design over multi-source multi-relay channels[J]., 2012, 11(9): 3348-3357. doi: 10.1109/TWC.2012.070912.111948.

[13] DING L, Bi Y, SUN D,. Efficient scheduling with random network coding in multi-relay wireless network[J].(), 2014, 19(1): 59-64. doi: 10.1007/s12204-014-1475-9.

[14] ASLAM M A and HASSAN S A. Analysis of multi-source multi-hop cooperative networks employing network coding [C]. IEEE 81st Vehicular Technology Conference, Glasgow, United Kingdom, 2015: 1-5. doi: 10.1109/VTCSpring. 2015.7145700.

[15] HO T, MEDARD M, KOETTER R,. A random linear network coding approach to multicast[J]., 2006, 52(10): 4413-4430. doi: 10.1109/TIT.2006.881746.

Scheduling Scheme for Multi-source Multi-relay Wireless Network Based on Random Linear Network Coding

WANG Lian①②LIANG Shenhu①PENG Daiyuan②

①(,,400065,)②(,,611756,)

Current scheduling schemes in multi-relay wireless network mainly focuse on single source wireless network with the same link status. Furthermore, the sequential-forward scheduling scheme is used usually, and the transmission efficiency is comparatively low. To solve this problem, a priority scheduling scheme based on random linear network coding is proposed. In different transmission stages, the feedback information is generated according to the packets accepting state or the linear relation among the encoding vectors. The number of the effective packets of the corresponding relay node is calculated. In the condition of different link status, the effective information of each relay node and the link transmission reliability is taken into consideration comprehensively to generate the priority index and complete scheduling. This scheme can realize cooperation transmission in multi-relays for multi-sources information. When the link status difference is obvious, the optimal forwarding node and the path can be adaptively chosen to improve the information transmission efficiency. According to the simulation results, this scheme can effectively improve network throughput and reduce the number of retransmission compared with the traditional scheduling schemes for single source wireless network.

Wireless network; Random linear network coding; Scheduling; Multiple-source multiple-relay

TP393

A

1009-5896(2017)03-0532-07

10.11999/JEIT160454

2016-05-03；改回日期：2016-11-11；

2017-01-11

王练 wanglian@cqupt.edu.cn

国家高技术研究发展计划(2015AA01A705)，国家自然科学基金(61571375)

The National High-Technology Research and Development Program of China (2015AA01A705), The National Natural Science Foundation of China (61571375)

王 练： 女，1976年生，博士生，副教授，研究方向为网络编码、无线网络安全.

梁申虎： 男，1988年生，硕士生，研究方向为网络编码.