无线mesh网中最小编码代价低时延多播路由

陈志刚，沈小建,，刘立



无线mesh网中最小编码代价低时延多播路由

陈志刚1，沈小建1,2，刘立2

（1. 中南大学信息科学与工程学院，湖南长沙410083；2. 湖南工业大学计算机与通信学院，湖南株洲412007）

提出了一种无线mesh网中最小网络编码代价低时延多播路由协议(MNCLDMR, minimal network coding and low delay multicast routing)。MNCLDMR的目标是选择合适的网络编码节点，最小化网络编码代价，降低网络时延。MNCLDMR主要思想是引入拓扑关键节点和网络编码关键节点的概念，以下一跳的节点是否是网络编码关键节点或拓扑关键节点作为路由判据，采用MNCLD算法构造多播树。仿真结果表明，MNCLDMR可以达到预定目标，合理形成网络编码机会，能实现最小网络编码代价低时延多播路由。

无线mesh网；最小代价；网络编码；低时延；多播路由

1 引言

在传统的网络中，中继节点只存储转发接收到的信息，这有时会造成网络资源的浪费。网络编码允许网络中的中继节点将接收到的信息重新组合，然后多播转发出去[1]。因此，网络编码突破了中继节点只存储转发的限制，能更好地利用网络资源。无线mesh网中引入网络编码的作用[2]是提高网络吞吐量和安全性，减小传输延迟，增强网络健壮性等。

网络编码感知的无线mesh网路由的研究是现在研究的热点[3~6]。有关基于网络编码最小代价路由的研究不少[7~11]。文献[7]提出了一个基于最小网络编码次数的多播路由算法来改善多播性能。提出了2个启发式准则，旨在建立具有较低的网络编码代价和较高的多播性能的多播路由。文献[8]从编码节点数的角度来解决复杂性问题，通过减少编码节点的数目来减少复杂性。文献[9]在静态多播中将网络编码最小代价问题简化为一个多项式时间内可解的优化问题，提出了用分散算法来解决。对于动态多播，Desmond等将网络编码最小代价问题简化为一个动态规划问题，并用动态规划理论来解决。文献[10]提出了一种基于关键链路的最小代价网络编码算法，能有效降低网络编码的代价。文献[11]提出了一种基于动态冗余控制的无线mesh网络编码机会路由协议，与经典的MORE协议相比，该协议能提高30%~100%的网络吞吐量，同时降低20%~45%的归一化开销。

利用网络编码减少传输时延的研究也是现在研究的热点[12~19]。卢冀等[12]提出了一种基于机会式网络编码的广播传输算法，有效地提高了广播传输效率并降低了传输时延。Sameh等[13]提出了一个简单的网络选择算法，有效地减少了一帧广播数据分组的平均完成延迟，其计算复杂度与随机性和贪婪选择算法的计算复杂度一样。文献[14]提出了适用于无线单跳网络的倒序搜索网络编码(RSNC)算法和二分搜索网络编码(BSNC)算法。在编码增益保持不变的前提下能够有效地减少分组判断次数，提高编码搜索效率，降低数据分组的平均端到端时延。杨奎武等[15]提出一种基于网络编码的广播传输机制(NBT)，与目前广播时延最小的泛洪机制相比，NBT能有效降低广播传输时延。张健等[16]研究了随机网络编码下的数据块时延特性，采用梯度法进行网络时延预测。文献[17]提出了一种编码增益的计算方法和编码图的简化方法，并基于此提出了编码增益感知的路由协议CGAR。仿真实验表明，CGAR的时延优于COPE和DCAR协议。文献[18]提出了基于网络编码的无线网络中端到端的延迟分析的一种分析方法，目的是分析网络中的每个数据流的延迟，以网络演算为理论基础。文献[19] 使用机会网络编码(ONC)研究了双向中继网络的基本流量延迟。通过最优ONC策略在平均分组延迟约束的网络中最大化网络吞吐量。

以上都是单独针对网络编码代价或时延的研究。经查阅相关文献，目前，同时针对无线mesh网中网络编码代价和时延的研究还没有，本文是首次提出了一个无线mesh网中最小网络编码代价低时延多播路由协议MNCLDMR。MNCLDMR的目标是选择合适的网络编码节点，最小化网络编码代价，降低网络时延。

本文创新点如下：1)MNCLDMR协议引入了拓扑关键节点和网络编码关键节点的概念，以下一跳的节点是否是网络编码关键节点或拓扑关键节点作为路由判据；2)采用算法MNCLD构造多播树。举例和仿真结果表明MNCLDMR可以达到预定目标，合理形成网络编码机会，能实现最小网络编码代价低时延多播路由。

2 相关知识

2.1 网络编码代价衡量标准

1) 网络编码节点数

由于节点执行网络编码需要额外的编码功能，那么最小化网络编码节点数是有潜在的利益。在采用相同网络编码方法和相同路由方式的前提下，编码节点越多，网络编码的复杂度就越大。不是所有的中间节点都需要进行网络编码，而只需选取其中有必要编码的节点进行网络编码。

2) 网络编码操作次数

与传统的路由不同，网络编码需要在节点进行编码或解码操作，增加了运算成本，提高了信息的传输延迟，这不仅影响了信息的传输速度，并且使宿点接收信息延迟。控制网络编码的操作次数对控制网络编码代价具有重要的意义。

3) 网络编码中的数据分组个数

单次网络编码中数据分组的个数也是影响网络编码代价的一个重要因素。要进行网络编码，相应的编码节点需要较大的缓存空间，单次网络编码中数据分组个数越多，目标节点解码的成功率相对就越低，相应的网络编码代价会增加。

4) 消耗的资源

编码节点需要进行编码运算，目的节点需要进行相应的解码操作，这些都需要消耗一定的CPU资源和内存资源。这与编码算法关系很大，编码算法越复杂，所消耗的资源就越多，相应的编码算法越简单，所消耗的资源就越少。

本文主要考虑网络编码节点数和网络编码次数，编码算法采用简单的异或算法（XOR），因此消耗的计算资源是比较小的。

2.2 时延

在传统的网络中，网络时延主要是传输时延，引入网络编码后，将增加编码、解码时延。网络中源节点的数据分组到达目的节点的传输时间就是传输时延。传输时延的大小取决于传输速率和传输距离。编码、解码时延与编码算法相关，选择一个简单的编码算法(如XOR)，编码、解码时延就会很低。相对于传输时延，编码、解码时延是很少的。因此，本文主要考虑传输时延。

假设网络中所有节点都具有相同的性能，那么时延跟跳数成正比。假设网络中有对源节点和目的节点进行通信，那么整个网络的平均时延[end−end]为这个端到端时延的平均值，即

其中，[end−end]与网络中的总跳数成正比。

3 最小网络编码代价低时延多播路由

3.1 网络模型

本文主要考虑在无线mesh网的mesh骨干层中如何实现最小网络编码代价低时延多播路由，mesh骨干层的拓扑结构是比较稳定的。无线mesh网可以建模为无向图(,)，其中，表示节点的集合，表示无线链路的集合。每个节点v∈均存在一个通信距离T和一个干扰距离I。通常是3TIT，本文假设I=2T。γ=(S, D, b)为无线业务集合，其中，S表示无线多播γ的源点，D表示γ的目的节点集合，b表示γ需要的带宽约束。()表示为无线业务γ构造的多播树。()中的节点有3类：源点、中间节点以及目的节点。(())表示中间节点集合。

3.2 拓扑关键节点与网络编码关键节点

用λ表示节点的入度，初始设定λ=0。I表示从链路输入的信息，I(1,2,…,λ)表示所获得的不同输入信息(相同的舍弃)。

定义1 拓扑关键节点。输入链路数λ≥2的中间节点。

定义2 网络编码关键节点。输入链路数λ≥2，且I(1,2,…,λ)中的≥2的中间节点。

相对于路由选择来说，拓扑关键节点是静态的而网络编码关键节点是动态的，一个节点是否为网络编码关键节点不仅要考虑节点的入度数量，还需要考虑经过节点的数据流条数以及节点缓存队列中信息数量。

在网络编码关键节点进行网络编码的条件：I(1,2,…,λ)中的≥2，且编码形成的数据分组的目的节点数不少于编码到一起的原数据分组个数。

3.3 最小编码代价低时延多播路由

MNCLDMR的基本思想如下：首先，初始化网络(,)，初始化多播树()只包含源点S；然后运用Dijkstra算法计算多播源节点S到目的节点集合D中所有目的节点的最短路径，(S,d)表示多播源节点S到目的节点d的最短路径；最后引入拓扑关键节点和网络编码关键节点，下一跳的路由节点优先选择网络编码关键节点，其次选拓扑关键节点，最后才选普通节点，采用MNCLD算法构造多播树。形成多播树的具体算法如下。

算法1 MNCLD算法

输入(,),γ=(S, D, b)

输出()

1)()←{S},←D;

2) while≠0 do {

3) whiled∈Ddo {

4)(S, d)←Dijkstra(S, d);//Dijkstra算法求最短路径并确定中间节点的入度

5) }

6) ifλ≥2&&I(1,2,…,λ)中的≥2{//节点为S任意一个邻居节点，下同

7)()←;//节点为网络编码关键节点，根据编码条件进行网络编码

8) }else //S的所有邻居节点中没有网络编码关键节点

9) ifλ≥2{

10)()←; //节点为拓扑关键节点

11) }else//S的所有邻居节点中没有拓扑关键节点

12)()←; //节点为普通节点

13)(())←(()));

14)D←D−d,←−1,S←;

15) }

16) return [()]

MNCLD算法说明：运用Dijkstra算法计算多播源节点S到目的节点集合D中所有目的节点的最短路径并确定中间节点的入度，引入拓扑关键节点和网络编码关键节点，并且在网络编码关键节点根据编码条件进行网络编码，在计算下一个新的多播树节点时，将已算出的()作为中间节点集合来实施Dijkstra算法。由于只在网络编码关键节点进行网络编码，这样在整个网络通信中网络编码节点数和网络编码次数都将非常有限，从而能实现最小网络编码代价。也由于在网络编码关键节点引入网络编码，在网络编码关键节点发送信息时可以将多个数据分组编码成一个数据分组发送，这样可以减少发送次数，提高网络吞吐量，降低网络时延。

3.4 复杂度分析

MNCLDMR算法是以Dijkstra算法为基础的，因而MNCLDMR算法的复杂度与Dijkstra算法的复杂度是一致的。设网络的边数为，顶点数为，那么该算法的复杂度为(2)。如果边数远小于2，可以考虑用堆这种数据结构进行优化，该算法的复杂度降为(() log)。

3.5 实例说明

下面通过一个实例来说明MNCLDMR的优越性。如图1所示12个节点的无线mesh网中，节点之间的实线表示可以直接无线通信，没有实线直接相连的节点则必须通过其他节点间接无线通信。源节点为1234，分别发送数据分组1234，目的节点为，最终要使所有目的节点都接收到数据分组1234。假设每条链路的传输时间为单位时间，节点处理数据分组的时间忽略不计。假设每个节点的发送和接收可以同时进行，每条链路可以同时双向通信(比如采用频分双工FDD模式)。

图2为单位时间之后，无线mesh网中各节点拥有的数据分组。根据定义2，和是网络编码关键节点，根据在网络编码关键节点进行编码的条件，只需在节点进行网络编码。

节点将数据分组134进行编码4，然后多播到节点。节点根据已有的数据分组可分别解码出134。在此同时，节点将4发送到节点，节点将2发送到节点和，节点3将2发送到节点。那么经过2时间之后，无线mesh网中各节点的数据分组如图3所示。

根据编码条件，这时不需进行任何编码，节点将2发送到节点，节点将3发送到节点，节点将3发送到节点，节点将2发送到节点和，节点将4发送到节点和。经过3时间之后，无线mesh网中各节点的数据分组如图4所示。

根据编码条件，这时也不需进行任何编码，节点将3发送到节点，节点将2发送到节点，节点将3发送到节点。经过4时间之后，无线mesh网中各节点的数据分组如图5所示。这时所有目的节点都接收到数据分组1234，完成传输。

在网络数据分组传输全过程中网络编码仅有一次，而且网络时延仅有4。如果在所有拓扑关键节点都进行网络编码或不进行网络编码，显然达不到这种效果。

用d()表示目的节点D(1≤≤)成功收到第个数据分组P(1≤≤)的时延。其中，为网络中目的节点总个数，此例中为8；为所有源节点发送的数据分组个数，此例中为4。假设MNCLDMR的目的节点D(1≤≤)在最后都能收到所有数据分组，则目的节点D(1≤≤)收到所有数据分组的平均传输时延[d()]可以表示为

在上面所举例子中，采用MNCLDMR路由算法计算如下

(3)

(5)

(6)

(8)

(9)

成功传输数据分组P(1≤≤)的平均时延为。在上面所举例子中，采用MNCLDMR路由算法计算如下

(11)

(13)

(14)

4 仿真分析

使用NS2(network simulator version 2)产生具有实际网络特性的无线mesh网拓扑[20]。个节点随机分布在1 000 m×1 000 m矩形区域内。在微机上使用NS2仿真工具分4组进行，分别仿真AODV、COPE[21]、CGAR[17]和MNCLDMR。AODV协议是典型的按需路由协议，AODV支持多播功能，支持QoS，只支持双向链路。AODV协议在NS2中有完整源代码，可以直接调用。COPE协议是基于网络编码的适合无线mesh网络的路由，但没有考虑时延。COPE协议在NS2中也已具体实现。

仿真参数如下：数据分组大小为512 byte，节点传输范围为200 m，节点干扰半径为400 m，节点带宽为10 Mbit/s，工作模式为混杂模式，节点队列长度为80个数据分组。分别对节点数为20、30、40、50、60的网络进行了路由时延、吞吐量、编码节点数、编码次数和解码出错次数的统计。

仿真场景：当网络中节点数为20、30、40、50、60时，分别设置2、3、4、5、6个多播通信，每个多播通信有1个源节点和6个目的节点，每个源节点的数据发送速率为50 kbit/s。每个场景仿真20次后取平均值。

图6所示为网络编码节点数与网络规模之间的关系。如图6所示，当网络规模增大时网络编码节点数随着增加，但是COPE和CGAR的曲线比较陡峭，而MNCLDMR的曲线增加比较平缓。原因是当网络规模增大时，可用的链路增加，网络编码的机会就更多，而MNCLDMR只在网络编码关键节点进行网络编码，因而比COPE和CGAR增加缓慢些。

图7所示为路由时延与网络规模之间的关系。如图7所示，时延随着网络规模增大而增加，但是AODV时延曲线比较陡峭，而COPE、CGAR和MNCLDMR的曲线比较平缓。原因是当网络规模增大时，网络中间链路数增加，因而路由时延会随之增加，但COPE、CGAR和MNCLDMR都考虑了网络编码，随网络规模增大而增多的数据分组经过网络编码后能够得到有效地控制，网络中路由的总链路数也会得到有效地控制，因而路由时延增长缓慢。

图8表示吞吐量与网络规模之间的关系。如图8所示，吞吐量随着网络规模增大而增加，但是AODV的吞吐量增加缓慢，而COPE、CGAR和MNCLDMR的吞吐量增加更快，COPE、CGAR和MNCLDMR都可以明显的提升吞吐量。因为网络编码可以组合多个数据分组成一个再发送，这样相当于一次发送了多个数据分组，所以能明显的提升吞吐量。

图9和图10显示了不同网络规模下节点编码数量和解码出错数量的变化。从图9和图10中可以看出MNCLDMR、COPE和CGAR这3种编码传输方式的编码次数和解码出错次数均维持在一个比较大的范围内，且MNCLDMR的编码次数和解码出错次数均略小于COPE和CGAR。从总体来看，MNCLDMR解码出错被丢弃的数据分组的数量平均占编码数据分组数量的4.5％左右，COPE解码出错被丢弃的数据分组的数量平均占编码数据分组数量的5％左右，CGAR解码出错被丢弃的数据分组的数量平均占编码数据分组数量的5.5％左右。

5 结束语

本文提出了一种无线mesh网中最小网络编码代价低时延多播路由协议MNCLDMR。MNCLDMR协议引入了拓扑关键节点和网络编码关键节点的概念，以下一跳的节点是否是网络编码关键节点或拓扑关键节点作为路由判据，采用算法MNCLD构造多播树。举例和仿真实验表明，该协议能选择合适的网络编码节点，减少网络编码代价，降低网络时延。在后续的研究工作中，需对该多播路由协议的具体实现做更深入的研究。

[1] AHLSWEDE R, CAI N, LI S R. Network information flow[J]. IEEE Transactions Information Theory, 2000, 46(4): 1204-1216.

[2] ANWAR A H, CHADI B, THIERRY T. Network coding for wireless mesh networks: a case study[C]//IEEE Communication Society. San Francisco, CA, USA, c2006: 173-182.

[3] 陈晨, 董超, 茅娅菲. 无线网络编码感知路由综述[J]. 软件学报, 2015, 26(1): 82-97.

CHEN C, DONG C, MAO Y F. Survey on network-coding-aware routing in wireless network[J]. Journal of Software, 2015, 26(1): 82-97.

[4] 王伟平,陈小专,鲁鸣鸣. 应用累积系数确认的网络编码机会路由协议[J]. 软件学报, 2014, 25(7):1541-1556.

WANG W P, CHEN X Z, LU M M. Network coding based opportun-istic routing using cumulative coding coefficient feedback acknowl-edgments[J]. Journal of Software, 2014, 25(7):1541-1556.

[5] 沈小建,陈志刚,刘立. 无线mesh网络中编码感知且负载均衡的多播路由[J]. 通信学报, 2015, 36(4):2015134.

SHEN X J, CHEN Z G, LIU L. Load balancing multicast routing based on network coding in wireless mesh network[J]. Journal on Communications, 2015, 36(4):2015134.

[6] CHEN J, HE K, DU R. Dominating set and network coding-based routing in wireless mesh networks[J]. IEEE Transactions on Parallel & Distributed Systems, 2015, 26(2):423-433.

[7] LIU H L, SHEN Q R, CHEN Y. An optical multicast routing with minimal network coding operations in WDM networks[J/OL]. Interna-tional Journal of Optics, http://dx.doi.org/10.1155/2014/693807.

[8] RAMI S Y, CHENG W Q. Cost minimization for multi-source mul-ti-sink network coding[C]//The 9th International Conference for Young Computer Scientists. Hunan, China, c2008: 253-258.

[9] DESMOND S L, NIRANJAN R, MURIEL M. Minimum-cost mul-ticast over coded packet networks[J]. IEEE Transactions on Informa-tion Theory, 2006, 52(6): 2608-2623.

[10] 陶少国, 黄佳庆, 杨宗凯. 一种改进的最小代价网络编码算法[J]. 华中科技大学学报(自然科学版), 2008, 36(5): 1-4.

TAO S G, HUANG J Q, YANG Z K. An improved algorithm for minimal cost network coding[J]. Journal of Huazhong University of Science and Technology (Natural Science Edition), 2008, 36(5): 1-4.

[11] 吴强, 范建华, 阚宝强. 低开销的无线网络编码机会路由协议设计[J]. 计算机工程, 2014, 40(2): 21-25.

WU Q, FAN J H, KAN B Q. Design of low overhead opportunistic routing protocol for wireless network coding[J]. Computer Engineering, 2014, 40(2): 21-25.

[12] 卢冀,肖嵩,吴成柯. 基于机会式网络编码的低时延广播传输算法[J]. 电子学报, 2011, 39(5): 1214-1219.

LU J, XIAO S, WU C K. Opportunistic network coding based de-lay-sensitive broadcast transmission algorithm[J]. Acta Electronica Sinica, 2011, 39(5): 1214-1219.

[13] SAMEH S, SHAHROKH V. On minimizing broadcast completion delay for instantly decodable network coding[C]//IEEE ICC. South Africa, c2010: 1871-1875.

[14] 姚玉坤, 易建琼, 温亚迪. 无线单跳网络中的高效低时延网络编码算法[J]. 重庆邮电大学学报(自然科学版), 2012, 24(5): 577-584.

YAO Y K, YI J Q, WEN Y D. Efficient low-delay algorithm for network coding in wireless single-hop networks[J]. Journal of Chongqing University of Posts and Telecommunications (Natural Science Edition), 2012, 24(5): 577-584.

[15] 杨奎武, 郭渊博, 马骏. 基于网络编码的延迟容忍移动传感器网络低时延广播传输机制[J]. 电子与信息学报, 2012, 34(5): 1239-1245.

YANG K W, GUO Y B, MA J. A netcoding-based delay-sensitive broadcast transmission scheme for delay tolerant mobile sensor net-works[J]. Journal of Electronics & Information Technology, 2012, 34(5): 1239-1245.

[16] 张健, 余纯武, 梅峰. 网络编码块时延预测与控制[J]. 武汉大学学报(理学版), 2012, 58(4): 366-369.

ZHANG J, YU C W, MEI F. The prediction and control of block delay under network coding[J]. Journal Wuhan University(Natural Science Edition), 2012, 58(4): 366-369.

[17] 田贤忠, 朱艺华, 缪得志. 无线网络编码增益感知的低时延路由协议[J]. 电子学报, 2013, 41(4): 652-658.

TIAN X Z, ZHU Y H, MIAO D Z. Wireless network coding gain aware routing protocol with low delay[J]. Acta Electronica Sinica, 2013, 41(4): 652-658.

[18] LI H Z, LIU X, HE W B. Delay analysis in practical wireless net-work coding[J]. Wireless Communications and Mobile Computing, 2014, 14:497-515.

[19] ZOHDY M, ELBATT T, NAFIE M. Maximum throughput opportun-istic network coding in two-way relay networks[J]. arXiv cs.IT, 2015, 12(3): 67-73.

[20] 于斌,孙斌,温暖. NS2与网络模拟[M]. 北京:人民邮电出版社, 2007.

YU B, SUN B, WEN N. NS2 and Network Simulation[M]. Beijing: Posts & Telecom Press, 2007.

[21] KATTI S, RAHUL H S, HU W. XORs in the air: practical wireless network coding[J]. IEEE/ACM Transactions on Networking, 2008, 16(3): 497-510.

Minimal coding cost and low delay multicast routing of wireless mesh networks

CHEN Zhi-gang1, SHEN Xiao-jian1,2, LIU Li2

(1. College of Information Science and Engineering, Central South University, Changsha 410083, China; 2. College of Computer and Communication, Hunan University of Technology, Zhuzhou 412007, China)

A minimal network coding cost and low delay multicast routing (MNCLDMR) of wireless mesh networks was presented. The goal of MNCLDMR was to select the appropriate network coding nodes, minimize network coding and reduce network delay. MNCLDMR protocol introduces the concept of topology key nodes and network coding key nodes, serving as the routing metric whether the next hop nodes were network coding key nodes or topology key nodes, using MNCLD algorithm construct multicast tree. Simulation results show that MNCLDMR can achieve expectation goal, form reasonable network coding opportunity and achieve minimal network coding and low delay multicast routing.

wireless mesh networks, minimum cost, network coding, low delay, multicast routing

TP393

A

10.11959/j.issn.1000-436x.2016002

2015-07-02；

2015-11-09

国家自然科学基金资助项目(No.60902044, No.60873082, No.60903058)；湖南省教育厅科研基金资助项目(No.12C0070)

The National Natural Science Foundation of China (No.60902044, No.60873082, No.60903058), The Hunan Provincial Education Department Research Projects (No.12C0070)

陈志刚（1964-），男，湖南益阳人，博士，中南大学教授、博士生导师，主要研究方向为网络计算与分布式处理、计算机网络。

沈小建（1976-），男，湖南永州人，中南大学博士生，主要研究方向为无线mesh网络与网络编码。

刘立（1970-），男，湖北广水人，湖南工业大学副教授，主要研究方向为服务计算、可信计算、网络安全。