一种基于网络编码的Ad Hoc网络多路径源选路由算法

刘永广, 张 剑, 陈瑞昭, 姚若河

(1.中国电子科技集团第七研究所，广东广州 510310； 2.华南理工大学电子与信息学院，广东广州 510641； 3.广东轻工职业技术学院，广东广州 510300)

一种基于网络编码的Ad Hoc网络多路径源选路由算法

刘永广1,2,3, 张 剑1, 陈瑞昭3, 姚若河2

(1.中国电子科技集团第七研究所，广东广州 510310； 2.华南理工大学电子与信息学院，广东广州 510641； 3.广东轻工职业技术学院，广东广州 510300)

根据Ad Hoc网络的特性，提出了一个基于网络编码的多路径源选路由算法. 算法借鉴了COPE的思想，实现上通过在中间节点缓存短路径，对具有编码机会的中间节点进行标注，从而获得具有最大编码机会的多条路径. 由于网络编码可以减少数据传输的次数，因此可以有效地提高信道的利用率. NS2环境下的仿真表明，新算法能够有效地平衡网络负载，提高网络的吞吐量.

网络编码； 多路径； 路由

移动Ad Hoc网络在军事、紧急救援和移动办公等领域具有广泛的应用前景，由于网络节点的移动性，导致整个网络拓扑结构随之动态变化，因而Ad Hoc网络路由是一个关键问题. 现行的路由算法大多是按需单路径路由协议，如DSR[1]、AODV[2]等. 这些算法基本上都采用单路径方式传送数据，控制包开销和网络延迟较大，当负载较大时，将面临网络拥塞的问题.

针对以上协议的问题，提出了一些多路径路由算法. 文献[3]提出维护备用路径，当主路径失败时利用备份路径来传输，并不是真正意义上的并行多路径传输. 文献[4]的多路径源路由协议MSR提出了一个基于启发的加权轮询多路径调度机制来分布负载，但没有提供其性能分析模型. 分裂多路径协议SMR[5]算法对DSR协议进行了改进，着重建立和维护最大数目的多条不相交路径，该算法能有效地提高网络的吞吐量，但是由于选择几条固定的路径，容易使其中的某些路径成为交集而变为瓶颈链路. 文献[6]-[10]均采用了文献[5]的思路，所不同的只是不相交路径的发现算法和分流算法. 比如，文献[6]提出了一种多样性的注入方法来发现非交叉路径， 而文献[7]通过改进的最短路径算法找到几条源到目的端的链路不相交最短路径，文献[10]则通过计算网路最大流来计算多条节点不相交路径.

以上提出的协议和算法各有优缺点，这些算法都需要研究路由的发现机制、数据的多路径发送方法以及提取高效的路径集等问题. 而本文抛弃了以前的思路，在多路径传输上采用了网络编码技术，优先考虑网络编码机会较多的路径，减少数据传送的次数，达到了节省网络带宽、提高网络性能的目的.

1 网络编码

网络编码理论最早由AHLSWEDE等人[11]开始研究，他们提出，通过使用网络编码，网络的组播能力可以达到组播树的最大流最小割流量，而这种网络吞吐量是常规路由无法达到的. KATTI 等人[12]成功地把网络编码思想引入到无线多跳单播网络中来，并提出一个应用于实际系统的网络编码算法COPE，该算法利用无线网络中单个节点发送数据时能够被所有邻居节点感知的特点，在两跳范围内进行网络编码，达到了提高系统吞吐量的目的. 一个典型的应用如图1所示，在该图中节点1通过节点2向节点3传送数据x1，而节点3通过节点2向节点1传送数据x2，节点2在没有采用网络编码的情况下需要分别向节点1和节点2传送x2和x1，总共需要传送2次，但是，如果在节点2处对x1和x2进行了网络编码，也就是把两组数据做异或运算并广播出去，则只需传送一次数据，节点1和节点2接收到数据后分别和本节点缓存的x1和x2异或，则可得到各自需要的数据x2和x1.

图1 无线网络编码Fig.1 Wireless network coding

本文提出的基于网络编码的多路径源选路由(MSRBNC)算法就是基于以上无线网络编码思想，从源端找k条到目的端具有最大编码机会的路径，并分别在这些路径上进行传输.

2 基于网络编码的多路径源选路由算法

根据以上的结论，设计了一种多路径源选路由算法，该算法在源和目的节点的多条路径上进行数据传输，路径选择遵循编码机会多的路径优先选择的原则. 以下是该算法的主要过程描述.

2.1路由发现

当源节点需要选择到达目的节点的路由时，和DSR协议一样，由源节点发起路由请求(ROUTE_REQUEST)广播报文. 该报文中包括一个唯一标识源节点的ID号和路由请求序列号. 在本算法中，为了让源端获得多条路径，采用了文献[5]中间节点处理路由请求的方法，具体处理过程如图2所示.

当目的节点收到一个路由请求报文时，就要回复一个路由应答(ROUTE_REPLY)报文，由于在路由发现过程中存在多个到达的请求报文，所以对同一个源请求可能发送多个ROUTE_REPLY报文. 考虑到路由信息的开销，在协议中规定对同一源节点的同一请求，回复报文数量不多于N条. 如果回复数目已经达到N条，则再到达的路由请求报文就会被丢弃.

ROUTE_REPLY报文是实现网络编码感知的关键，ROUTE_REPLY报文中增加一个称为“编码机会”的字段CO，在每个节点中都缓存一个类似图1所示的短路径组，记录可能会经过该节点和其邻居节点的流，中间节点收到ROUTE_REPLY报文时的处理过程如图3所示. 源节点收到一个ROUTE_REPLY报文后，如果缓存中有等待要发送的数据，则立即发送缓存中的数据.

2.2路由和短路径维护

对于单条路径的维护，如果一个节点不能够成功地把数据转发给下一跳,那么该节点就会认为该条路径在此处发生了断链，该节点就会产生一个路由错误 (ROUTE_ERROR)报文， ROUTE_ERROR报文经过的中间节点就会从短路径缓存中找到该报文中含有的短路径，并从缓存中删除. 源节点收到该路由错误报文后，会从路由缓存中删掉所有使用断链链路的路径. 此外，考虑到短路径其实也是一种邻居关系，如果节点在移动过程中邻居关系发生了变化，比如一个节点的某个邻居消失了，则也要查找短路径缓存中是否有和该邻居有关的短路径存在，如果存在，则从缓存中删除该条短路径.

2.3路径选择和数据传输

当有数据要发送到目的节点时，首先查找路由缓存寻找到达目的节点的路由，如果没有到目的节点的路由，则启动2.1节中的路由发现过程. 如果路由存在，算法从路由缓存中的N条路径中找到k条CO最大的路径来传送数据. 算法采用了每包分流的方法，数据到达目的节点后再重组递交. 中间节点收到数据后，如果该节点在报文中被标注为具有编码机会，则报文在该节点中缓存t时间，如果在这t时间内有机会编码，则编码后发送，否则直接发送. 如果该节点没有被标注为具有编码机会，则收到数据后直接转发.

图2 中间节点收到ROUTE_REQUEST报文的处理过程Fig.2 Process of receiving ROUTE_REQUEST packet at media node

图3 中间节点收到ROUTE_REPLY报文的处理过程Fig.3 Process of receiving ROUTE_REPLY packet at media node

3 仿真和性能分析

3.1仿真环境和算法参数

这一部分将通过仿真对算法的性能和参数进行分析. 所有的仿真都在NS-2.31仿真环境下进行，每个节点的传输半径约250 m，Mac层使用IEEE 802.11 DCF，信道带宽2 Mbps,节点移动方式采用Random Waypoint模型. 目的节点回复最大路由个数N=6，源节点选择传输路径个数k=2，有编码机会的中间节点等待编码时间t=2 ms.

3.2性能评估

在性能评估方面，通过和单路径源选路由算法DSR[1]、多路径无编码源选路由算法SMR-1[5]进行比较来考察算法的性能. 采用的仿真场景如表1所示，仿真中节点数36个，暂停1 s，每个场景产生18个CBR流，发送速率每个流每秒1个报文，报文大小512个字节.

表1 性能仿真场景

图4是3个算法在端到端吞吐量上的比较，由图可以看出，在节点处于静止或者半静止状态下(场景0)，3个算法都能获得很大的吞吐量，其中MSRBNC的吞吐量最大，SMR最小，但是非常接近. 在这种低速或者半静止网络中，由于节点之间的位置相对固定，路由缓存中的路径始终处于有效状态，大大减少了路由请求报文和路由回复报文的数量. 在这种情况下，网络的主要额外开销是数据报文的报头开销，DSR协议流状态(Flow State)的采用，使得数据报头开销大幅度减小，有效数据吞吐量增加. 而MSRBNC由于要在有编码机会的节点处延迟等待编码，其延迟最大.

随着节点移动性的增加，DSR协议由于仅保留一条路径，路由和流路径的重新建立使数据在源端缓存时间加长，所以吞吐量急剧下降，且图5中的延迟增长很快，最后达到17 s左右，基本上是SMR和MSRBNC的两倍多. 相反，2个多路径算法由于同时采用多条路径传输，所以控制报文导致的额外开销要小得多. 本文的MSRBNC算法由于进行了网络编码，节省了传输次数，从而节省了带宽，总体端到端吞吐量最大. 另外，场景4在移动速度比较高的情况下MSRBNC存储的短路径很容易失效，编码机会就比较少，没有编码机会的MSRBNC算法就退化为SMR算法，只是由于中间节点的编码等待导致延迟增大.

图4 不同算法端到端吞吐量的比较

Fig.4 Comparison of end-to-end throughput between different algorithms

图5 不同算法端到端平均延迟的比较

Fig.5 Comparison of end-to-end delay between different algorithms

在场景2下对每个节点转发的报文数量(不包括控制报文)进行了统计，数据的统计结果如表2所示. 由表2可以看到，DSR协议在该场景下转发的数据报文数量最大，但端到端吞吐量却不大. 在负载均衡方面，本文算法标准差最小、均衡性最好,提高了网络资源的利用率.

表2 转发数据报文数量统计

4 结论

本文提出了一种基于网络编码的多路径源选路由算法，算法利用了中间节点的编码机会，达到了节约网络资源，提高吞吐量的目的. 如何评估编码带来的延迟和编码带来的转发次数减少增益之间的关系，并从理论和实践上对路径的选择做出指导，是进一步需要研究的方向.

[1] JOHNSON D, MALTZ D A. The Dynamic Source Routing Protocol (DSR) for mobile Ad Hoc networks for IPv4[EB/OL]. IETF mobile Ad Hoc Networks Working Group, 2007(4):1-107.[2009-10-08]. http:∥www.ietf.org/rfc/rfc4728.txt.

[2] PERKINS C E, ROYER E M. Ad Hoc On-Demand Distance Vector (AODV) routing [EB/OL].IETF mobile Ad Hoc Networks Working Group,2003(7):1-37.[2009-10-08]. http:∥www.ietf.org/rfc/rfc3561.txt.

[3] NASIPURI A, DAS S R. On-Demand multi-path routing for mobile Ad Hoc networks[C]∥IEEE ICCCN’99. Boston, USA, 1999: 64-70.

[4] WANG L, ZHANG L F, SHU Y T, et al. Multipath source routing in wireless Ad Hoc networks [C]∥Canadian Conf On Electrical and Computer Engineering. Edmonton, Canada, 2000:479-483.

[5] LEE S J, GERLA M. Split multipath routing with maximally disjoint paths in Ad Hoc networks[C]∥IEEE ICC 2001. Helsinki, Finland, 2001:3201-3205.

[6] PEARLMAN M R, HAAS Z J, SHOLANDER P, et al. On the impact of alternate path routing for load balancing in mobile Ad Hoc networks[C]∥ACM MobilHoc, 2000. Chicago,USA, 2000:3-10.

[7] SOHN S, MARK B L, BRASSIL J T. Congestion-triggered multipath routing based on shortest path information[C]∥IEEE Int Conference on Computer Communications and Networks (ICCCN). Arlington, USA， 2006:191-196.

[8] BANNER R, ORDA A. Multipath routing algorithms for congestion minimization[J]. IEEE/ACM Transactions on Networking, 2007,15(2): 413-424.

[9] LIU M, XU Z Y, YANG J L, et al. Collision-Constrained minimum energy node-disjoint multipath routing in Ad Hoc networks[C]∥Wireless Communications, Networking and Mobile Computing (WiCom 2006). WuHan, China, 2006: 1-5.

[10] 陈跃泉,郭晓峰,曾庆凯,等.AMR:一个基于网络最大流的Ad-Hoc多路径路由算法[J].电子学报,2004,32(8):1297-1301.

CHEN Yuequan, GUO Xiaofeng, ZENG Qingkai, et al. AMR: A multipath routing algorithm based on maximum flow in Ad-Hoc networks [J].Acta Electronic Sinica,2004, 32(8):1297-1301.

[11] AHLSWEDE R, CAI N, LI S Y, et al. Network inform ation flow[J]. IEEE Trans on Information Theory, 2000, 46(4): 1204-1216.

[12] KATTI S, RAHUL H, KATABI D, et al. XORs in the Air: Practical Wireless Network Coding[C]∥ACM Sigcomm 2006. Pisa, Italy, 2006:243-254.

Keywords： network coding; multi-path; routing

【责任编辑 庄晓琼】

AMULTI-PATHSOURCEROUTINGALGORITHMFORAdHocNETWORKSBASEDONNETWORKCODING

LIU Yongguang1,2,3， ZHANG Jian1， CHEN Ruizhao3， YAO Ruohe2

(1. NO.7 Research Institute, China Electronics Technology Group Corporation, Guangzhou 510310, China;2. Institute of Electronics & Telecommunications, South China University of Technology, Guangzhou 510641, China;3. Guangdong Industry Technical College, Guangzhou 510300, China)

According to the characters of Ad Hoc networks, a multi-path source routing algorithm based on network coding is presented. The algorithm refers the idea of COPE. In realization, the multiple paths having maximum coding opportunity are found by caching short paths in medium nodes and labeling the medium nodes which have coding opportunity. Because network coding reduces data’s transmission time, the algorithm can improve channel utilization effectively. Simulations under NS2 environment show that the new algorithm has better performance in balancing the network load and improving network throughput.

2010-01-25

刘永广(1972—)，男，河北石家庄人，博士，广东轻工职业技术学院高级工程师，主要研究方向：信息网络理论与技术、路由算法及优化等,Email: Liu.yongguang@gmail.com.

1000-5463(2010)03-0042-05

TP393

A