基于路由长度的多径路由协议

王 顶,王珊珊,席效禹

(西北工业大学电子信息学院,西安710129)

基于路由长度的多径路由协议

王 顶,王珊珊,席效禹

(西北工业大学电子信息学院,西安710129)

针对单径路由协议在高速Ad hoc网络中平均端到端时延和丢包率高的问题,在动态源路由协议的基础上,提出基于邻居节点变化率与路由长度的多径路由协议DSR_HD。利用HELLO消息获得一跳范围内可用邻居数,根据邻居数求得节点的邻居节点变化率。在路由发现过程中,采用路由距离与路由跳数相结合的方法计算路由长度,并选择邻居节点变化率和路由长度低的节点加入路由,从而提高路由的稳定性。仿真实验结果显示, DSR_HD协议可以有效减少数据分组传输的端到端时延及路由开销,提高分组成功投递率。

无线自组织网络;多径路由;路由长度;邻居变化率;DSR_HD路由协议

1 概述

在自组织网络开发应用过程中,与传统网络有很多不同之处。自组网中的设备大多处于高速移动状态,由于节点数量较多,相对速度较快,直接造成网络结构的快速变化,传统路由协议不能很好地适应网络拓扑结构的变化,因此路由算法成为Ad hoc网络中的研究重点。

在Ad hoc网络中,DSR,AODV都是采用一次路由发现,仅选择一条路由策略。但是随着Ad hoc网络研究的不断深入,单径路由协议已经不能满足更高层次的路由要求。单径不能充分利用网络资源,易于产生拥塞,使端到端的时延以及丢包率增加,并且会使某些节点承担的转发任务过重,使能源耗尽,最终导致网络断开,而多径路由算法可以很好地解决这些问题。

本文在动态源路由(Dynamic Source Routing, DSR)协议的基础上提出基于路由长度的路由协议(DynamicSourceRouting Based on Hop and Distance,DSR_HD),采用路由距离与路由跳数相结合的方法,同时利用邻居节点变化率与多径传输数据,实现Ad hoc网络资源的充分利用。

2 DSR协议

DSR协议是最早采用按需路由协议思想的路由协议,主要由 2个机制组成:路由发现和路由维护[1]。

在DSR协议中,采用源路由的方式[2]避免了数据包经过的中间节点不停更新路由,而且允许节点在转发或无意中接收到数据包时,将最新的路由信息存于它的路由缓存器中以备不时之需,减少了路由发现的开销。源主机知道到达目标主机的路径,而且可以自由地从中选择合适的路径来发送数据包。这就使得DSR上的多径路由比基于逐跳的路由协议上的多径路由简单。基于DSR协议的性能表现以及源路由的特征,因此,选择DSR协议进行扩展。

虽然DSR协议有其自身的优点,但是它也有自身的缺点,如:(1)一次路由发现过程可能会产生多条到目的节点的路由,但是只采用一条路径进行传输,造成资源浪费;(2)由于Ad hoc网络拓扑结构变化较快,路由缓存中的过期路由会影响路由选择的准确性。

3 多径路由

3.1 多径路由的定义

多径路由算法[3]是指可以为源节点与目的节点同时提供多条可用路径,并且允许节点选择如何使用这些路径的算法。多径路由可以分为3类[4]:节点不相关多径路由,链路不相关多径路由以及相关多径路由,如图1所示。

图1 多径路由的分类

3.2 多径路由的选择

节点不相关多径路由之间没有公用的节点或链路,其容错能力最强,具有更好的稳定性。链路不相关多径路由的容错能力次之,相关多径路由的容错能力最差。所以本文采用节点不相关多径路由。

3.2.1 路由条数的确定

在被动路由协议中,路由开销主要由路由发现、路由维护以及数据传输造成[5]。

假设移动节点均匀分布在半径为R的网络中,节点的密度为δ,设网络中有N个节点,则N=πR2δ。每个链路发生断裂的概率为μ。假定hs与hm分别为单径与多径路由协议的平均路由跳数。因为单径路由协议采用最短的路径,所以hm＞hs。发生路径断裂处的节点距离源节点的平均跳数为he。设Ac为每个节点活跃链接数。设Nu为多径协议的路由条数,λs,λm分别为单径与多径路由协议的路由发现频率,P为数据包的开销,ε为发送数据包的频率。路由请求分组(Routing Request,RREQ)、路由答应(Routing Reply,RREP)、路由错误(Routing Error, RRER)分组大小分别为Mrq,Mrp,Me。一次路由发现需要时间T完成。设Osl,Oml分别为单径路由协议与多径路由协议的开销。

单径与多径路由协议的开销随路由跳数变化,如图2所示。当路由条数为2或3时,多径路由协议的开销增加不明显。当路由条数超过3时,多径路由协议的开销急剧增大。所以,一般选2条～3条路径,本文选取2条路径。

图2 路径条数对网络路由开销的影响

3.2.2 多径使用模式

多径的使用有2种基本使用模式,同时使用多条路径或先使用主路径,主路径失效后在使用其他路径。

本文采用轮流发送的方式发送数据包[6]。通过采用这种方式,可以简单地模拟n个数据包同时使用2条节点不相关路径进行传输。

4 基于邻居变化率和路由长度的多径路由

4.1 邻居变化率

在DSR_HD协议中每隔HELLO_INTERVAL广播HELLO消息。节点可以通过接收相邻节点发送来的HELLO消息来与确定其与邻居节点的连通性。

每个节点维护2个邻居表,一个邻居表用来记录邻居节点id和t0时刻与t1时刻该节点与邻居节点的距离,另一个邻居表用来记录与该节点建立过连接的节点id。邻居表建立流程如图3所示。

图3 邻居表建立流程

假设节点n在t0时刻的邻居表集为sn(t0),时刻的t1邻居表集为sn(t1),则节点n的邻居变化率[7]为:

由式(3)可知,邻居变化率是t1-t0时间间隔内和节点保持连接的节点个数与t0时刻和该节点建立过接连的节点个数之比。

NVR越大,说明节点n的局部拓扑结构越稳定,NVR越小,说明节点n的局部拓扑结构变化越剧烈。

通过邻居变化率选择局部拓扑结构变化较小的节点参与数据的转发,减少了路径中发生断裂的概率。

根据NVR的大小节点自动调整发送HELLO消息的周期,当NVR较大时,增大HELLO消息发送的周期,当NVR较小时,减少HELLO消息发送的周期,这样可以适当减少路由开销。

4.2 路由长度

DSR路由协议以路由跳数作为判据标准,虽然非常简单,但是网络中可能存在很多相同跳数的最短路径,这就可能没有选择到最优链路,并且路由跳数少时,源节点与目的节点之间的距离也可能很大,反之,源节点与目的节点之间的距离也可能很小。路由跳数多,路由中使用的节点就增多,造成浪费,源节点到目的节点的距离大,路由链路断裂的概率就大。本文采用路由跳数与路由距离的均衡值路由长度L作为路由判据。

其中,h为路由跳数;s为源节点到目的节点最小跳数;di为第i跳t1时刻两节点间的距离;r为两节点间最大的通信距离;f为纠正因子,它与t0时刻与t1时刻两节点间距离的关系如下:

(1)当前时刻与邻居节点的距离大于上一刻与邻居节点的距离,则说明2个节点在远离,则f=1;

(2)当前时刻与邻居节点的距离小于上一刻与邻居节点的距离,则说明2个节点在靠近,则f= -1;

(3)当前时刻与邻居节点的距离等于上一刻与邻居节点的距离,则说明2个节点保持相对位置不变,则f=0。

经过多次实验,当ω=0.3时,性能较好。为计算路由判据L,必须求得节点间的距离,本文利用在接收分组或消息时通过探测接收信号强度来计算出节点间的距离[8]。

在自由空间中,根据自由空间传播模型,接收信号的强度与节点间距离的平方成反比。按Frri自由空间方程式[9],接收信号的强度与节点间距有如下关系:

其中,pr(d)是接收功率;λ是波长;Gr是接收方天线增益;pt是发送功率;Gr是发送方天线增益;l是系统损耗率;d为发送方到接收方的距离。由式(6)可以得到式(7),从而可以求出路由长度L。

4.3 协议描述

当源节点S需要向目的节点发送数据而缓存中没有到目的节点D的路由时,就会启动路由发现的过程。DSR_HD路由协议的RREQ分组包结构相比于DSR路由协议来说,做了一定的改进,其格式如图4所示。

图4 RREQ分组包结构

4.3.1 路由发现过程

路由发现过程具体如下:

(1)中间节点对RREQ分组的处理

中间节点接收到RREQ分组时,不管缓存中有没有到达目的节点的路由,都不回复RREP分组[10],并且当节点通信范围内包含目的节点时,置RREQ的标志位为1。对RREQ分组的处理和转发过程如图5所示,具体步骤如下:

中间节点接收到RREQ分组后,首先判断该节点的邻居变化率是否超过门限值,如果邻居变化率超过门限值,则说明当前节点的路由不可靠,则直接丢弃该RREQ分组;反之,继续判断该RREQ分组的标志位,如果标志位为1,说明上一节点通信范围内包括目的节点,为减少路由开销,直接丢弃该RREQ分组,如果标志位为0,说明节点通信范围内没有该RREQ分组,该节点在缓存中寻找该RREQ分组的记录,如果没有,则计算路由判据L,并将L与上一跳的地址记录到存储器中,转发数据包。如果中间节点的缓存中有该RREQ分组,计算其路由判据S,并将S与之前存储器的路由长度L进行比较。如果S≥L,则丢弃该RREQ分组。如果S＜L,则判断RREQ分组中携带的上一跳地址与第一次记录的前一节点地址是否相同,如果相同,则丢弃该RREQ分组。反之则转发该RREQ分组。

图5 中间节点对RREQ的处理转发过程

(2)目的节点对RREQ分组的处理

一般的多径路由协议(如SMR)由目的节点控制,源节点只能被动地接受目的节点选择的路由,这样的方式使源节点在有限的几条路径失效时,只能重新启动路由请求,特别是当多条路径同时发送数据时,源节点多条路径中的其中一部分如果断开,只能舍弃这样的路径,退化成单径的方式发送数据。如果能在源节点,而不是目的节点保留充分的网络状态信息,将可以较好地解决该问题。

本文目的节点收到第一个RREQ包后,立刻发送RREP给源节点,通知源节点这条路由为延迟最短的路径,目的节点继续等待接收更多的RREQ,每收到一个这样的 RREQ包,延迟一定时间,再将RREP发送给源节点。这样源节点就可以获得多条路径,然后选择L小的路由,发送数据。

4.3.2 路由维护

本文采用2条路由轮流发送的方式来发送数据包,源节点保留充分的网络状态信息,当发现一条中断时,首先查找缓存,寻找另一条到达目的节点的路由,从而保持2条路由轮流进行数据包的发送,如果找不到到达目的节点的路由,源节点就保持单条路径发送数据包,直到所有路径全部不可用,才重新进行路由发现过程寻找新的路由。所以,本文利用多径路由协议没有增加路由发现的次数,从而减少了路由开销。

5 仿真实验与结果分析

5.1 仿真系统介绍

本文采用NS2网络仿真软件对DSR路由协议与DSR_HD路由协议进行性能比较。

5.2 仿真参数

网络拓扑结构是一个包括20个移动节点的网络模型,节点随机分布在1 000 m×1 000 m的平面区域中,按照设定的速度随机向任意方向移动[11]。节点采用全向天线,默认传输范围为250 m。因为本文讨论的是高速移动的自组网中设备的运动模型,所以将此停留时间设置为0。源节点每隔0.5 s发送一个数据,每隔数据分组为512 Byte,仿真时间为500 s。为了尽可能地保证模拟的一致性,本文采用Setdest Version2中将节点移动速度的最大与最小值设为相同。这样在每个生成的场景中,节点均以固定速度移动。以10 m/s,20 m/s,30 m/s,40 m/s, 50 m/s,60 m/s,70 m/s,80 m/s,90 m/s,100 m/s进行仿真。

5.3 性能参数

性能参数具体如下:

(1)投递率:目的节点正确接收到的数据包占产生数据包的比例。

(2)路由开销比例:路由包(包括RREQ,RREP, RRER等)占全部数据包(正确接收的数据包与路由协议控制包)的比例。

(3)端到端平均时延:从源节点产生的数据包到目的节点收到该数据包的平均时间[12]。

5.4 结果分析

由图6可以看出,DSR路由协议随着节点运动速度的增大,其分组成功投递率呈现下降趋势,而DSR_HD协议则基本没受到速度因素的影响。这是因为DSR_HD路由协议考虑了路由的稳定性,保证了链路的稳定。

图6 分组成功投递率比较

图7显示了路由开销的比较,在低速环境下, DSR_HD的开销要大于DSR。这是因为DSR_HD是多径路由,它在整个通信开始的时要出现2条路由,所以开始的开销要高于DSR。但是在高速环境下,DSR的路由重建率要远大于DSR_HD,DSR_HD可以较好地降低路由重建所带来的时延。

图7 路由开销比较

图8显示了平均端到端延时的比较,在低速环境下,网络拓扑结构变化缓慢,DSR路由协议中由于某个节点移动而引起多条路径断裂的优势就不是很明显,从而DSR在时延方面表现略优于DSR_HD。但是在高速环境下,DSR_HD优于DSR路由协议。

图8 平均端到端时延比较

综上所述,在拓扑结构变化较快的网络中,DSR_ HD路由协议在提高分组成功投递率、降低端到端延时和控制路由开销方面都有显著提高,DSR_HD路由协议比DSR路由协议能更好地适应拓扑结构变化快速的网络,所以,DSR_HD路由协议更加适合高速移动的自组网。

6 结束语

本文在DSR协议和多径路由思想的基础上,提出了 DSR_HD路由协议。该协议通过定期发送HELLO消息,排除路由长度过长并且邻居变化率较大的路由,减少路由开销,而且源节点建立了相对完备的网络拓扑结构。仿真实验证明了该协议的可行性与可靠性,在平均端到端的延时、分组投递率、路由开销等方面均具有较好的性能。

[1] 王金龙.Ad Hoc移动无线网络[M].北京:国防工业出版社,2004.

[2] 邵 琳,阮颖平,彭 宏.Ad hoc网络中一种新的基于DSR的多路由算法[C]//中国电子学会第十七届信息论学术年会论文集.西安:[出版者不详],2010: 339-345.

[3] Nasipuri A,Castaneda R,Das S R.Performance of Multi-path Routing for On-demand Protocols in Mobile Ad Hoc Network[J].Mobile Networks and Application, 2001,6(4):339-349.

[4] Mueller S,Tsang R P,Ghosal D.Multipath Routing in Mobile Ad Hoc Networks:Issues and Challenges[M]// Calzarossa M C,Gelenbe E.Performance Tools and Applications to Networked Systems.Berlin,Germany: Springer,2004:209-234.

[5] Pham P P,Perreau S.Performance Analysis of Reactive Short-est Path and Multipath Routing Mechanism with Load Balance[C]//Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies.[S.l.]:IEEE Press,2003:251-259.

[6] 郭晓峰,陈跃泉,陈贵海.一种累计多路径移动自组网络路由策略[J].软件学报:自然科学版,2004,15(4): 594-603.

[7] 刘 兵,高 强,曾长安.一种改进型的Ad hoc网络值分簇算法[J].华北电力大学学报,2007,34(5): 99-102.

[8] 蒋世林.基于节点相对移动性的自适应按需组播路由协议的研究与实现[D].沈阳:东北大学,2011.

[9] 安辉耀,王新安,李 挥,等.移动自组网中的先进路由算法与路由协议[M].北京:科学出版社,2009.

[10] 朱 伟.Ad hoc网络独立多路径路由的研究与改进[D].济南:山东大学,2006.

[11] 柯志亨,程荣祥,邓德隽.NS2仿真实验-多媒体和无线网络通信[M].北京:电子工业出版社,2009.

[12] 张现芳.基于SMR的多路径协议的分析和优化[J].移动通信,2012,36(6):45-48.

编辑 陆燕菲

Multipath Routing Protocol Based on Routing Length

WANG Ding,WANG Shan-shan,XI Xiao-yu
(College of Electronic and Information,Northwestern Polytechnical University,Xi'an 710129,China)

Aiming at the shortcomings that signal path protocol has high end-to-end delay and packet loss rate in highspeed environments,this paper modifies the Dynamic Source Routing(DSR)protocol,and by using the HELLO message,the number of neighbors can be obtained.According to the number of neighbors,it can calculate the neighbor change ratio.During the routing discovery,it can calculate the length of the routing by using the method of routing distance and routing hops combination,and choose the neighbor node whose neighbor change ratio and route length are lower join the routing.So it can choose the high degree of stability of routing.Simulation results show that under the high-speed environment the algorithm can control the end to end delay of data packet transmission,dramatically increase the successful package delivery ratio and reduce routing overhead.

Ad hoc network;multipath routing;routing length;neighbor change ratio;DSR_HD routing protocol

1000-3428(2014)09-0082-05

A

TN915.04

10.3969/j.issn.1000-3428.2014.09.017

西北工业大学基础研究基金资助项目(GBKY1011)。

王 顶(1973-),男,副教授、博士,主研方向:宽带无线通信;王珊珊、席效禹,硕士研究生。

2013-08-12

2013-10-11E-mail:wangshanshan42587@163.com