多跳无线网络中基于节点编码感知的组播路由协议

姚玉坤,朱丽青,余志龙,徐亚伟,陈曦

(重庆邮电大学移动通信技术重庆市重点实验室, 400065, 重庆)



多跳无线网络中基于节点编码感知的组播路由协议

姚玉坤,朱丽青,余志龙,徐亚伟,陈曦

(重庆邮电大学移动通信技术重庆市重点实验室, 400065, 重庆)

针对在编码感知组播路由协议CAMR中存在中间转发节点因计算编码流对不完全且有错误而导致不能充分发现节点的编码机会,以及RREQ请求分组中存在冗余开销和编码感知度量值重复计算等问题,提出一种适用于多跳无线网络的节点编码感知组播路由协议(node network coding aware multicast routing protocol, NAMP)。NAMP协议对节点编码流对算法进行了优化,以保证所计算出的编码流对具有可解性和完整性。在路由请求阶段,该协议去掉了RREQ分组中因循环添加中间节点的邻居信息和丢包率信息而产生的冗余信息,在路由回复阶段,该协议优化了中间节点收到多个RREP分组的回复方式,在不影响原有数据传输功能的前提下减小了网络开销。仿真结果表明:与CAMR和MAODV两种现有协议相比,NAMP协议提高了网络吞吐量,降低了网络控制开销,其中平均吞吐量提高了25.6%,网络控制开销降低了8.1%。

多跳无线网络;网络编码;编码感知;编码流对;平均吞吐量;控制开销

香港中文大学的Ahlswede等在2000年首次提出网络编码的概念[1],通过网络编码可以达到网络信息传输的理论最大值,在此基础上,人们研究发现在无线多跳网络中能够提前预测节点有无编码机会以及编码能力的大小,这种提前预测的方法称为编码感知,近年来得到了学者的高度关注。文献[2]提出了一种“编码+路由”的DCAR协议,但是DCAR协议没有考虑单个节点编码能力的大小,也不能直接修改用于组播网络。文献[3]提出MORE协议,通过机会路由的思想,避免机会路由中间节点需要协商的弊端,但是由于节点可能会传输一些与其编码系数相关的非新数据编码包给接收节点,而导致网络带宽消耗增加。文献[4]提出了基于遗传算法的编码感知路由,利用遗传算法优秀的寻优能力,找寻具有最大编码机会的路由。文献[5]通过跨层调度的方法,提出了一种编码感知组播MAC协议,但是该协议只是考虑了组播树上节点的编码机会,对于那些非组播树上的节点是否具有更大的编码能力没有考虑。

Alwis等提出了基于无线Mesh网络的内容编码感知组播传输算法[6],该算法利用信道编码和网络编码技术优化数据转发和改善视频组播服务在传输时延、带宽利用等方面的效果,但是由于该算法需要传输冗余的数据来保证视频的质量,因此会增加一定的传输开销。Youghourta等提出了DYGES算法,该算法通过对网络环境中组播流的特性变化自适应调整数据分块的大小,保证每次组播传输具有稳定的时延[7]。

1 问题分析

为了便于问题描述,本文给出如下几个定义。

定义1 双向邻居补图GX由顶点集VX和双向边集合EX组成,GX表示节点X一跳范围内节点构成的邻居图的补图。

定义2 双向边ea,b表示在双向邻居补图GX中的一条沿节点a发出到节点b的流e(a,b)和沿节点b发出到节点a的流e(b,a)组成的双向边。

定义3 流集合eu表示在双向邻居补图GX中,u∈EX,进入到节点u的所有流组成的集合,k条流可以分别用e(1,u),e(2,u),…,e(k,u)表示。

定义4 编码流对为在双向邻居补图GX中,如果两条流能够在节点X处编码,那么这两条流组成一组编码流对。

经过深入研究,我们发现CAMR协议主要存在以下两个缺陷。①在原协议中,从节点X的双向邻居补图的流集合中随机选出第一条流之后再从剩余的流集合中随机筛出第二条流组成一组编码流对,然后再把第一条流从流集合中删除,继续在流集合中进行下一次循环查找,但是分析发现上述方法会引起两个问题,不能保证所选出的编码流对的完整性。对于第一条流,假如有多条流存在与之组成编码流对的可能,而原算法只选择一条流组成一对编码流对后就删除第一条边,由此会导致在以后的循环查找中不能找到剩余的编码流对,不能保证所选出的编码流对具有可解性。选定流集合中的任意流e(u,v)后,并不是删除进入节点v和发出节点u的边后,再从剩余流集合中任选一条流都可以与e(u,v)组成一组编码流对,CAMR协议随机选择这样的流来进行编码会导致编码包不能被解码。②在CAMR协议的路由请求过程中,中间节点对请求分组RREQ携带的邻居信息和丢包率需要一直添加,这样会导致越到后面中间节点转发的RREQ里面携带的冗余信息越多;在路由回复过程中,如果中间节点收到多个RREP响应分组时,按原协议是中间节点单独对每个RREP分组进行转发,而分析发现这样会导致发送冗余的RREP分组以及携带冗余的信息。

为了解决上述CAMR协议存在的问题,本文提出了一种节点编码感知组播路由协议(node network coding-aware multicast routing protocol,NAMP)。

2 NAMP协议

2.1 NAMP协议提出的新机制

NAMP协议针对CAMR协议中出现的问题以及结合NAMP协议的编码理论分析提出了如下改进:通过优化节点编码流对来解决原协议出现的编码流对寻找不完全和找到错误编码流对的问题,去掉路由请求分组中的冗余字段以及改进路由回复方式。

2.2 NAMP协议编码感知度量值的计算机制设计

根据上述改进机制,NAMP协议通过节点理论编码流算法和计算节点平均缓存队列长度算法来设计NAMP协议的编码感知度量机制。

2.2.1 节点编码流对算法 为了判断节点的编码机会,NAMP协议设计节点编码流对的计算步骤如下。

输入 节点X的双向邻居补图。

步骤1 从EX中选出流集合H,P=∅,其中EX是节点X的双向邻居补图的边集,P是输出的编码流对的集合。

步骤2 任选一条流e(u,v)∈H,K=H-{e}。

步骤3 从集合K中选择进入到节点u的流集合eu,P=P∪{e,eu},如果有i条进入到节点u的流eu,P中需要分别统计这i(i>1)个编码流对,即P=P∪{e,e(1,u)}∪{e,e(2,u)}∪…∪{e,e(i,u)}。

步骤4 从集合K中选择从节点v发出的流集合ev,P=P∪{e,ev},如果有j条从节点v发出的流ev,P中需要分别统计j(j>1)个编码流对,即P=P∪{e,e(1,u)}∪{e,e(2,u)}∪…∪{e,e(j,u)}。

步骤5 在集合K中,如果满足e(w,z)存在于EX中,边ew,z与边eu,v没有公共节点,且双向边eu,w、eu,z、ev,w以及ev,z都不属于EX,那么P满足P=P∪{e,e(w,z)}∪{e,e(z,w)}。

步骤6 在集合K中,如果满足e(w,z)存在于EX中,ew,z与边eu,v没有公共节点,且4条双向边eu,w、eu,z、ev,w、ev,z中有1条属于EX,那么P会满足P=P∪{e,e(w,z)}。

步骤7 在集合K中,如果满足e(w,z)存在于EX中,ew,z与边eu,v没有公共节点,且e(u,w)存在于EX中,e(v,z)存在于EX中,那么P=P∪{e,e(w,z)},同理,如果满足ew,z存在于EX中,ew,z与边eu,v没有公共节点,且eu,z存在于EX中,ev,w存在于EX中,那么此时P为P=P∪{e,e(z,w)}。

步骤8 从流集合H中删除选定流e(u,v),即H=H-{e}。

步骤9 重复步骤2～8直到集合H为空。

步骤10 输出所有可能的编码流对集合P。

2.2.2 节点编码流平均队列长度算法 计算节点编码流平均队列长度算法[2]如下:

(1)删除编码图中缓存队列长度为0的顶点和它们相应的边;

(2)初始化L=0,顶点集V=∅;

(3)在剩余的顶点集中随机选择顶点i;

(4)找到包含顶点i的最大子图;

(5)把节点i的最大子图添加到集合V中;

(6)L=L+max(Li),i∈V;

(7)去掉集合V中的所有顶点和对应的边;

(8)再次将顶点集V置空,V=∅;

(9)重复步骤(3)～(8)直到所有顶点都去掉;

(10)最后得到L的长度就是节点X的平均编码长度。

由于无线链路的稳定性对数据的成功传输有着直接影响,因此提出将节点的链路质量和编码能力作为路由度量,定义度量值为

(1)

式中:E(l)表示链路l上的期望传输次数;L表示链路l发送节点缓存的平均编码长度;A表示链路l的有效带宽。

2.3NAMP协议路由发现

NAMP协议采用MAODV组播路由协议[9]作为设计基础,并针对本文研究的编码机会感知的需要进行了改进。在路由发现阶段采用Cl作为路由度量选择。为确定Cl的值,NAMP协议需要新增HELLO_Prob包用以路由探测。

通过HELLO_Prob探测包周期性发送,每个节点可以获得Cl度量中的E、B和L的值。

2.3.1 路由请求阶段 NAMP协议的路由请求过程有以下3个步骤。

步骤1 组播源广播路由请求消息RREQ,RREQ消息需要携带节点的邻居信息和对应的丢包率并将上一跳节点添加到路径表F中。

步骤2 中间节点收到RREQ分组后的操作。

中间节点收到RREQ消息后,首先判断是否接收过该RREQ,若已经接收过,则直接丢弃;否则,继续添加中间节点的上一跳节点信息到路径表F中,用中间节点自身的邻居节点信息和对应的丢包率替换原来RREQ对应的信息,中间节点暂存此时的路径表F,然后广播RREQ。每个节点周期性广播HELLO_Prob包,获取该节点各条链路的E值与有效带宽B。

步骤3 目的节点收到RREQ消息后不删除从不同路径收到的RREQ消息,这样获得多条可能到达目的节点的路径。

2.3.2 路由回复阶段 NAMP协议的路由请求过程有以下4个步骤。

步骤1 收到RREQ消息的目的节点单播回复RREP消息到组播源节点,在RREP消息中有一条组播源到目的节点的完整路径信息Ff。

步骤2 中间节点判断其邻居节点是否有多个是目的节点,如果是,在等待收到多个RREP分组后,将RREP消息中的Ff与节点以前暂存的路径信息F进行比较,如果F∈Ff,则此中间节点通过节点编码流对算法、节点编码流平均队列长度算法以及式(1)计算出节点到下一条链路的编码感知度量值Cl,并将已收到的多个RREP中对应链路的C值与Cl一起添加到一个RREP消息中,然后单播回复。

步骤3 如果中间节点在已回复过RREP的情况下,再次收到从不同路径转发来的RREP消息,此时不再计算自己到下一条链路的Cl值,直接将该RREP消息回复给下一节点。

步骤4 源节点收到一个RREP消息后就获取了到达一个目的节点的路径Ff,以及每条链路上的Cl值,源节点在收到所有目的节点回复的RREP消息后,源节点就获得了到达所有目的节点的一个Mesh结构以及该结构每条边的Cl值。在此Mesh结构的基础上,利用最小生成树的方法,源节点计算出一棵包含所有目的节点的最小生成树,并按照此最小生成树发送数据。

3 NAMP协议性能的理论分析

假定网络中有N个组播源节点,且每个中间节点可以对来自N条流的数据进行缓存。

3.1 节点平均吞吐量

由于组播接收节点接收的数据块大小是一样的,所以平均吞吐量其实是和节点平均传输时延成反比的。假设组播接收节点的个数为h,整个数据块大小为M,则平均吞吐量为

(2)

式中:Di表示节点的传输时延。由于NAMP协议的节点传输时延D小于CAMR协议的节点传输时延,所以NAMP协议的平均吞吐量大于CAMR协议的平均吞吐量。

3.2 节点转发RREQ开销

假设每个节点的平均邻居节点个数为B,在RREQ中,一个邻居节点信息和对应的丢包率所占的大小分别为s1和s2,在CAMR协议中,中间节点需要不断添加其邻居信息到RREQ中,转发W个RREQ到目的节点所带的开销为

R1=B(s1+s2)+2B(s1+s2)+…+W(s1+s2)=

0.5W(W+1)B(s1+s2)

(3)

在NAMP协议中,RREQ只包含节点自己的额外信息,即转发W个RREQ所带的开销为

R2=B(s1+s2)+B(s1+s2)+…+B(s1+s2)=

WB(s1+s2)

(4)

由式(3)与(4)比较可得R1>R2,说明对于CAMR协议而言,其节点转发RREQ消息所产生的控制开销(即网络消耗)要大于NAMP协议所产生的控制开销。

4 仿真实验及分析

采用业内主流的OPNET14.5软件进行建模和仿真,相同场景条件下,从数据分组平均端到端时延、数据分组传送成功率以及平均吞吐量等方面,将提出的NAMP协议与CAMR协议以及MAODV协议进行性能分析与比较。

4.1 仿真环境及参数设置

仿真实验采用的网络模型是100个节点随机分布在1 000 m×1 000 m的矩形区域,在这100个节点中随机选择不同个数的节点按照MAODV路由协议的要求加入一个组播树中形成组播网络,改变组播组的成员数使组播组成员在5～30之间变化。无线信道传输模型采用two-ray模型,链路层协议为IEEE 802.11b,上层通过CBR流量生成器产生整个网络仿真的数据。节点的平均传输范围设置为250 m,分组大小为1 kb。

4.2 仿真结果及分析

4.2.1 节点平均吞吐量 如图1所示,当组播组的成员数变化时,NAMP和CAMR协议的平均吞吐量虽然都是随着组播组成员数的增大而明显增加,但是NAMP协议的平均吞吐量大于CAMR协议和MAODV协议。分析其原因主要是由于CAMR协议在中间节点计算可能的编码流对的时候简单地删除寻找过的编码流,却可能遗漏某些实际存在的编码流对,而CAMR协议能寻找到所有可能的编码流对且更准确的编码流对,使得节点编码机会更大,当组播组成员数增加时,编码机会也进一步增加;对于MAODV协议,由于没有捕获编码机会,其吞吐量没有太大变化,不会随着组播组成员数的增大而明显增加。

图1 平均吞吐量随组播组成员数的变化

4.2.2 RREQ控制开销 3种协议的仿真结果如

图2所示。图2表明,NAMP、CAMR和MAODV协议的RREQ控制开销均会随着组播组成员数的增大而呈上升趋势。其中,NAMP协议的RREQ控制开销小于CAMR协议的控制开销,但是大于MAODV协议的RREQ控制开销,原因是相对于CAMR协议,NAMP协议去掉路由请求分组中不必要的邻居节点和丢包率信息,故开销减小,而在MAODV协议中,中间节点转发的RREQ消息不需要携带邻居节点和丢包率信息,所以NAMP协议的控制开销比MAODV协议的大。

图2 RREQ控制开销随组播组成员数的变化

4.2.3 RREP控制开销 由图3可知,随着组播组成员数的增加,RREP控制开销也随之增加,但是NAMP协议的增长趋势明显小于CAMR协议,其原因是:相较于CAMR协议,NAMP协议在回复RREP消息且中间节点的邻居节点有多个目的节点时,中间节点会把收到的多个RREP消息中的编码感知度量值添加到一个RREP消息中继续转发,且对于已经转发过RREP消息的中间节点,再次收到来自不同路径的RREP消息时不再将自身下一条链路的编码感知度量值添加到RREP中进行转发,故RREP控制开销减小。

图3 RREP控制开销随组播组成员数的变化

4.2.4 平均端到端时延 由图4可知,NAMP协议的平均端到端时延小于CAMR和MAODV协议,这是由于在NAMP协议中的中间转发节点缓存的平均队列长度经过编码感知后小于CAMR协议,而MAODV协议没有采用编码技术,节点缓存的平均队列长度又大于CAMR协议,故在节点中的平均传输时延D的比较结果是MAODV协议大于CAMR协议,CAMR协议大于NAMP协议。

图4 平均端到端时延随组播组成员数的变化

5 结 论

本文针对CAMR协议中寻找编码感知流不完全、路由请求信息中存在冗余开销以及重复计算编码感知度量值的问题,提出了一种节点编码感知组播路由协议NAMP。NAMP协议分别对节点编码流对算法和路由发现算法进行了优化,确保所计算出的编码流对具有可解性和完整性,同时,去掉了RREQ中的冗余信息并优化了RREP的回复方式,提高了网络吞吐量,减小了网络开销。仿真结果表明,与CAMR和MAODV两种现有协议相比,NAMP协议的平均网络吞吐量提高了25.6%,网络控制开销降低了8.1%。但是,NAMP协议在发送数据时没有考虑节点的发送速率,在未来工作中,我们将重点考虑节点发送速率对于编码感知度量值设计的影响。

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

[2] LE Jilin, LUI J C S, CHIU D M. DCAR: distributed coding-aware routing in wireless networks [J]. IEEE Transactions on Mobile Computing, 2010, 9(4): 596-608.

[3] CHACHUlLSKI S, JENNINGS M, KATTI S, et al. Trading structure for randomness in wireless opportunistic routing [M]. New York, USA: ACM, 2007: 172-181.

[4] SHAO Xing, WANG Ruchuan, XU Hai, et al. Genetic algorithm based coding aware routing for wireless mesh networks [J]. Advances in Information Sciences and Service Sciences, 2012, 4(5): 752-763.

[5] CHOID J, BANG H, LEE C. Network coding-aware multicast optimization in multi-hop wireless networks [C]∥Proceedings of the 2014 IEEE International Conference on Consumer Electronics. Piscataway, NJ, USA: IEEE, 2014: 466-467.

[6] DE C, ARACHCHI H K, FEMANDO A, et al. Content and network-aware multicast over wireless networks [C]∥Proceedings of the 2014 10th IEEE International Conference on Heterogeneous Networking for Quality, Reliability, Security and Robustness. Piscataway, NJ, USA: IEEE, 2014: 122-128.

[7] BENFATTOUM Y, MARTIN S, AGHA K A. QoS for real-time reliable multicasting in wireless multi-hop networks using a generation-based network coding [J]. Computer Networks, 2013, 57(6): 1488-1502.

[8] 黄传河, 杨文忠, 王博, 等. 无线Mesh网中编码感知组播路由协议CAMR [J]. 计算机研究与发展, 2011, 48(6): 1000-1009. HUANG Chuanhe, YANG Wenzhong, WANG Bo, et al. CAMR: network coding-aware muticast routing protocol in wireless mesh networks [J]. Journal of Computer Research and Development, 2013, 48(6): 1000-1009.

[9] ROYER E M. Multicast operation of the Ad-hoc on-demand distance vector protocol [C]∥Proceedings of the Annual International Conference on Mobile Computing and Networking. New York, USA: ACM, 1999: 207-218.

(编辑 武红江)

A Multicast Routing Protocol Based on Node Network Coding-Aware for Multi-Hop Wireless Network

YAO Yukun,ZHU Liqing,YU Zhilong,XU Yawei,CHEN Xi

(Key Laboratory of Mobile Communications Technology of Chongqing, Chongqing University of Posts and Telecommunications, Chongqing 400065, China)

A multicast routing protocol based on node network coding-aware (NAMP) is proposed to address some problems in the current CAMR (network coding-aware multicast routing) protocol for wireless mesh networks. These problems are the incomplete and erroneous searching of coding flow at middle node, the existence of redundant information of RREQ packet, and the repeated calculation of coding-aware measurements. The NAMP protocol optimizes the algorithm of node coding flow, and ensures the solvability and integrity of the calculated coding flow. The protocol removes the redundant information of RREQ during the routing request stage, and optimizes reply ways of an intermediate node when it receives multiple RREP packets in the routing phase. The network control overhead is also decreased without affecting the original data transmission function. Simulation results and comparisons with existing CAMR and MAODV schemes show that the NAMP improves the average throughput and reduces network control overhead, respectively, and that the average throughput is improved by more than 25.6% and the network control overhead decreases by more than 8.1%.

multi-hop wireless network; network coding; coding-aware; pair of coding flow; average throughput; control overhead

2015-06-01。

姚玉坤(1964—),女,教授。

长江学者和创新团队发展计划资助项目(IRT1299);重庆市自然科学基金资助项目(cstc2012jjA40040)。

10.7652/xjtuxb201510013

TP393

A

0253-987X(2015)10-0079-05