基于小世界理论和QoS支持的DSR协议*

李向丽，李超超

（郑州大学信息工程学院，河南郑州 450001）

0 引言

在移动自组织（Ad Hoc）网络中，动态源路由（dynamic source routing，DSR）协议是一种应用比较广泛的路由协议。它的优点是简单方便，不需要周期性广播路由分组，路由开销小，仅仅需要维护与通信节点之间的路由［1］。DSR是一种按需路由协议，不需要维护到每个节点的路由表，当有数据要发送时才进行路由发现过程，增大了端到端时延［2］;Ad Hoc节点能量是影响网络性能的关键因素，DSR协议没有考虑节点能量问题［3］;DSR协议仅仅选择跳数作为路由选择的标准，没有考虑其它因素，没有服务质量（QoS）保证［4］。针对DSR协议存在的问题，本文提出改进DSR（improved DSR，IDSR）协议，它可以有效地预测要发送数据的节点，提前进行路由发现过程，探测出该节点所在网络拓扑结构。IDSR选择时延和剩余能量作为选择路径的标准，提供QoS支持。

1 DSR协议概述

DSR协议是一种按需路由协议，包括路由发现和路由维护2个过程。

1.1 路由发现

当源节点有数据要发送时，首先检查缓存中是否存储有到达目的节点的路径。如果有，则按缓存的路径发送分组;否则，启动路由发现过程。源节点广播发送路由请求分组（RREQ）。中间节点收到的RREQ的源地址与标识号和之前收到的相同，就丢弃它;否则，就接收。假如中间节点的缓存中已经有到目的节点的路径信息，或者自己就是目的节点，向源节点发送路由应答分组（RREP）。如果中间节点发现RREQ报文的路由记录中已经包含了自己，就丢弃该报文［5］;否则，中间节点把自己的地址添加到RREQ中，之后把更新过的RREQ分组再广播出去。

1.2 路由维护

源节点发送数据分组过程中，当中间节点发现路由的下一跳节点链路不可达，就向源节点发送一个路由错误报文（RRER）。源节点收到RRER之后，从路由缓存中删除所有经过该节点的路由。同时，在RRER向源节点传输的过程中，收到此报文的中间节点也将路由缓存中含有该错误节点的路由删除。如果源节点的缓存中含有另一条到达目的节点的路由，则用新的路由发送分组;否则，重新进行路由发现过程。

2 IDSR协议

下面描述IDSR的设计思想和实现技术。

2.1 小世界理论与应用

实验表明，一个人要找另一个自己不认识的人，他首先找自己的朋友，朋友再找他的朋友。这样经过5～6层关系就可以找到自己想要找的人。这样的现象就称为小世界现象。不仅仅在人类社会领域存在这样的现象，在计算机网络领域也存在小世界现象。经研究表明，无论什么样的计算机网络，只要是人在使用，就具有小世界特征，Ad Hoc网络也具有小世界特征。一般情况下，任何一个节点的通信对端距离自己6跳以内［1］。

一个节点刚刚已经发送完分组到通信对端，根据局部性原理，预测该节点在不久之后还要发送数据，就把该节点定义为预测点。预测点广播RREQ报文，根据小世界理论，把该RREQ报文的生存时间（TTL）设置为6跳。当TTL减为0，收到RREQ的节点就向源节点回复RREP报文。中间节点记录下RREP报文中所携带的路由。经过上述过程，以预测点为中心的6跳范围以内，每一个节点都记录下了经过自己所能到达的所有节点的路由。

即使预测点在不久之后并没有发送数据，经过该过程之后所得到的节点中缓存信息可以用到其它节点通信中，降低路由发现过程时延。节点在被定义为预测点之前通信过，它的缓存中会有到旧通信对端的路由缓存信息，但新的通信对端和旧通信对端可能不是一个节点，可能之前缓存的路由信息已经过期，所以，预测点提前探测所在网络拓扑结构是有必要的。

2.2 支持QoS的路由

路由发现过程可能会产生多条到达目的节点的路径，DSR只是以跳数作为选择最佳路由的依据。对于有线网络，最小跳数的路由有很好的性能，但是对于Ad Hoc网络，这会使某些节点过早的消耗完能量，影响网络生存周期［4］，跳数最小的路由时延不一定最小。网络QoS是指网络在传输数据流时要满足的一系列服务请求［6］。传输流的QoS需求一般包括包丢失率、端到端时延等［4］。在Ad Hoc网络中，因为某个节点过早消耗完能量会导致整条路径失效而重新发起路由发现过程，增大时延，增加路由开销，降低网络生存周期。所以，本文提出以时延、剩余能量作为最佳路由选择的标准。

把每个节点的剩余能量分成3个等级［4］;第一等级是指节点的剩余能量大于等于初始能量的50%，这样的节点收到RREQ立即处理，通过相应检查后，再转发出去，没有额外时延;第二等级是指节点的剩余能量大于等于初始能量的10%且小于初始能量50%，这样的节点在处理RREQ前需要一段时延（delay），这段时延与节点剩余能量呈反比，最大值为 0.01 s［7］，delay的计算表达式如式（1）所示

其中，Energy为节点的剩余能量，iniEnergy为节点初始能量;第三等级是指节点剩余能量小于初始能量10%，这样的节点不处理RREQ，把它丢弃，并且该节点也不参与数据传输，只能作为源节点和目的节点［8］。

该方案传输数据的路由尽量选择第一等级的节点，当节点的剩余能量处于第二等级，推迟一个时延转发RREQ，目的节点仅仅处理最先到达的RREQ，并返回RREP，这样降低了使用第二等级节点的可能性，降低节点的消耗的速度。第三等级节点不进行数据传输，避免过度消耗该节点的能量。该方案在选择最佳路由时，同时考虑到路由时延和节点的剩余能量，可以更好地满足QoS的需求，降低端到端时延，延长网络生存周期。

为了说明该方案具体的工作过程，以图1为例进行描述［9］。假设A要向D发送数据，首先检查缓存中是否含有到D的路由信息，假设没有，启动路由发现过程。A广播发送RREQ报文，B收到A节点发来的RREQ，检查自己的剩余能量，假设B节点为第一等级节点，通过对RREQ相应检查后，立即把自己的地址添加到RREQ中，再把更新过的RREQ转发出去。C节点收到该RREQ报文，假设它为第二等级节点，计算delay值，延迟delays把自己地址添加到RREQ报文中，再转发出去。H节点收到广播的RREQ后，发现自己为第三等级节点，立即丢弃RREQ报文。目的节点D处理最先收到的RREQ，并回复RREP报文。

A节点和D节点通信后，把A定义为预测点，猜测新的通信对端距离它6跳之内。A广播发送RREQ报文，TTL为6。当TTL减为0时，收到该报文的节点会向源节点发送RREP，收到RREP的中间节点记录下相应的路由信息。A节点可以得到A-B-C-D-E-F-G，A-H-I-J-K-L-M，A-B-C-I-JK-L，A-H-I-C-D-E-F四条长度为6跳的路径。假设预测准确，不久之后，A有数据要发送到节点F，A节点在缓存中有2条路径可以到达F，一条是A-B-C-D-E-F（记为P1），另一条是A-H-I-C-D-E-F（记为P2）。提前探测网络拓扑结构时，每个节点会记录下收到RREQ报文的时间，并根据自己能量计算转发RREQ的延时。A节点比较P1和P2路径的时延，选择时延较小的一条路径作为主路径，并进行数据传输，剩余的路径作为备选路径。

在此之后，假设P节点有数据要发送到K，P广播发送RREQ报文，M节点已经知道到K节点的路径（M-L-K），收到RREQ后，M发送RREP到P节点。

图1 预测点发现路径Fig 1 Prediction node discovers path

3 仿真实验与性能分析

3.1 仿真模型

以NS2作为仿真平台，对DSR和IDSR协议进行仿真实验。实验节点数为30个，节点在1 000 m×1 000 m区域内移动。仿真时间为100 s，节点运动的速度和初始的位置随机确定。最大移动速度分别为 5，10，15，20，25 m/s。本实验采用CBR（constant bit rate）数据流，包的发送速率为10 个/s，包的大小为512 bytes。

3.2 性能评估参数

为了对DSR协议及改进协议IDSR进行性能比较，选取如下5个评估参数:

1）路由开销:是指节点路由控制分组数（route_sum）和源节点发送的数据包（cbr_sum）的比值［1］。路由开销计算公式如式（2）所示

2）平均时延:定义为从数据包产生到数据成功传输到目的节点所需的时间。

其中，tg为数据报产生的时刻，tr为数据报到达目的节点的时刻。

3）分组成功传输率（packet delivery fraction）:指成功到达目的节点的分组数（recv_pack）占总共发送分组数（send_pack）的比例［10］。计算公式为式（4）所示

4）平均跳数:为分组从源节点到目的节点平均需要的跳数，即转发数据包（fowdpacket）与发送数据包（sendpacket）的比值再加1。计算公式如式（5）所示

5）网络生存周期:为从网络运行开始到第一个节点死亡的时间［6］。

3.3 仿真结果与分析

路由开销与移动速度的关系如图2所示。在速度不断变化过程中，IDSR路由开销低于 DSR，尤其当速度为25 m/s时，IDSR的路由开销远远低于DSR。如图3所示，IDSR比DSR平均时延要小，尤其当速度为15 m/s时，IDSR的平均时延远远小于DSR。虽然IDSR的预测点提前进行路由发现过程会产生许多路由控制分组，但是，如果预测准确，可以省去路由发现过程，即使预测不准确，提前探测到的路由信息可以提供给其它需要通信的节点。在选择路由时，考虑到节点剩余能量，防止某个中间节点过早消耗完能量，重新发起路由发现过程。所以，IDSR协议的路由开销低于DSR，时延小于DSR。

如图4所示，在速度不断变化过程中，IDSR协议的分组成功传输率高于DSR。如图5所示，IDSR的平均跳数小于DSR。尤其当节点速度大于15m/s时，IDSR的平均跳数远远小于DSR。IDSR在选择路由时，尽量选择剩余能量多的节点，这样不会因为某个节点过早消耗完能量而导致整条路径失效，选择的路由生存周期长，可以传输更多的数据，防止丢包，提高分组成功传输率，降低平均跳数。

节点数与网络生存周期的关系如图6所示。每个节点的初始能量为20 J，传输功率为1.0 W，接收功率为0.8 W，待机功率为0.1 W，最大移动速度为15 m/s。IDSR协议的网络生存周期大于DSR协议，尤其当节点数为20时，IDSR的网络生存周期远远大于DSR。在路由发现过程中，优先选择剩余能量较多的节点，降低使用剩余能量较少的节点可能性，第三等级节点不参与传输数据，它只能作为源节点或目的节点，避免节点能量过度消耗。所以，IDSR的网络生存周期和DSR相比有明显提高。

图2 不同速度的路由开销Fig 2 Node velocity vs route cost

图3 不同速度的平均时延Fig 3 Node velocity vs average delay

图4 不同速度的分组成功传输率Fig 4 Node velocity vs packet delivery fraction

图5 不同速度的平均跳数Fig 5 Node velocity vs average no.of hops

图6 不同节点的网络生存周期Fig 6 Node velocity vs network life time

4 结论

IDSR协议通过预测要发送数据的节点，提前进行路由发现过程，可以减少端到端时延;应用小世界理论，限制RREQ报文传输的范围，避免过多浪费网络带宽资源;以时延和剩余能量作为路由选择的标准，提供QoS支持。仿真实验表明:改进后的IDSR协议在路由开销、平均时延、分组成功传输率、平均跳数和网络生存周期方面的性能都优于DSR协议。

［1］李向丽，魏凯敏，吕何平.一种具有小世界特征和冲突避免的DSR协议［J］.小型微型计算机系统，2010，31（8）:1546-1548.

［2］Al-Mekhlafi Z G，Hassan R.Evaluation study on routing information protocol and dynamic source routing in Ad-Hoc network［C］//Proceedings of 2011 7th International Conference on IT in Asia（CITA），Kuching Sarawak，2011:1-4.

［3］Sheng Linyang，Shao Jinbo，Ding Jinfeng.A novel energy-efficient approach to DSR-based routing protocol for Ad Hoc network［C］//Proceedings of 2010 International Conference on Electrical and Control Engineering，Wuhan，2010:2618-2620.

［4］Xu Zhen，Xiao Juan.Energy-aware and delay-aware QoS routing in mobile Ad Hoc networks［C］//Proceedings of IEEE ICCP，Leshan，2012:511-515.

［5］Sen J.An analysis of routing disruption attack on dynamic source routing protocol［C］//Proceedings of IEEE Wireless Communication，Vehicular Technology，Information Theory and Aerospace ＆Electronic Systems Technology（Wireless VITAE），Chennai，2011:1-5.

［6］文 浩，林 闯，任丰原，等.无线传感器网络的QoS体系结构［J］.计算机学报，2009，32（3）:432-440.

［7］Baisakh，Patel N R，Kumar S.Energy conscious DSR in MANET［C］//Proceedings of IEEE International Conference on Parallel，Distributed and Grid Computing，Solan，2012:784-789.

［8］Rajgopal G，Manikandan K，Sivakumar N.QoS routing using energy parameter in mobile Ad Hoc network［J］.International Journal of Computer Applications，2011，22（4）:11-17.

［9］马志欣，赵鼎新，谢显中，等.车载通信网中基于DSR分层机制的移动代理路由策略研究［J］.重庆邮电大学学报:自然科学版，2011，23（2）:207-213.

［10］Sarkar S，Datta R.A trust-based protocol for energy-efficient routing in self-organized MANETs［C］//Proceedings of IEEE India Conference（INDICON），Kochi，2012:1084-1089.