一种改进型DSR-I路由协议的设计与仿真

吴 磊，皮 智

(北方工业大学 计算机学院，北京 100144)

一种改进型DSR-I路由协议的设计与仿真

吴 磊，皮 智

(北方工业大学 计算机学院，北京 100144)

动态源路由协议(DSR)是为移动自组织网络设计的路由协议，性能较优，但是DSR协议中存在路由不稳定、时延大以及能量不平衡等问题。针对DSR的这些不足，通过对DSR协议的研究分析，提出了一种基于权重、链路反馈和均衡能量的DSR改进型路由协议(DSR-I)。在满足权重的路径查找中选择能量高的节点充当中继，在数据包发送的过程中低能量的节点反馈能量状态，源端主动断开旧链路，从而变更路径，并采用NS2平台对DSR和DSR-I进行了仿真实验和性能分析。实验结果表明，改进后的DSR-I路由协议比较明显地改进了原DSR路由协议的性能。

动态源路由协议；移动自组织网络；权重；均衡能量；NS2；仿真

0 引 言

移动自组织网络(Ad hoc Network)是指多个无线收发装置的移动终端节点组成的，不需要依靠通信网络基础设施的自组织和自管理网络[1]。因此，网络中的节点可以通过路由发现机制转发分组，并进行路由维护。近年来，Ad hoc网络以其低成本、低功耗、分布式和自组织的优点，在国内被很多高校、科研单位广泛应用；在国外也受到关注，同时涉及多个学科交叉和相关知识高度集成的热点研究方向。但是网络中的节点通常由电池供电，节点部署的位置往往具有随机性，能量难以再次添加，有些节点可能因自然原因损坏或者被人为破坏。而路由技术是无线自组网的核心技术之一，维护网络的稳健性和均衡网络中能量的消耗是设计一个好的路由协议应该要考虑的首要问题。

DSR协议对延迟、带宽、丢包率和能量等都没有加以限制，即无QoS限制。这会导致网络的节点拥塞、时延大等问题。同时也会导致其中某些节点的能量或者网络的能量被迅速耗尽，造成网络很快分裂，影响整个数据的传输效率，缩短了该网络的生存时间。所以提出了基于权重、链路反馈和均衡能量的DSR改进路由协议DSR-I(DSR-Improve)。

1 DSR协议简介

DSR(Dynamic Source Routing)是为移动Ad hoc设计的，同时是一种简单高效、无线多跳的路由协议。它是一种基于源端的路由协议，给每一个传输分组的头部插入完整的源路由信息，保证传输过程中按完整的路径传输。该方法可以避免环路的产生，并在网络变化和节点移动的情形下，也可以将分组正确地传送，提高了移动通信节点对于网络拓扑动态变化的适应能力[2]。

DSR路由协议包括两个主要机制：第一是路由发现，当源节点需要发送数据时才启动，实现源节点获取到达目的节点的路由信息；第二是路由维护，源节点发送数据到达目的节点时监测此时路由的可用状况，当出现网络拓扑变化导致路由故障时自动寻找另一条路由或者重新发起路由发现过程[3-10]。

2 DSR-I的设计

2.1 基于权重的策略

在分析QoS问题时，为了方便研究，可以把Ad hoc场景下的Ad hoc网络表示成一个加权图G(V,E)。其中，V为Adhoc移动节点的集合;E为代表Adhoc移动节点间形成的链路的集合，且每个Adhoc节点的传输半径相同。假设在给定的源节点与目的节点之间存在路径K(s→i→…→j→d)，该路由需满足以下约束条件:

Bank(k)=min{Bank(s,i),…,Bank(j,d)}

(1)

Delay(k)=Delay(s,d)

(2)

则该Adhoc路由协议可以抽象为在加权图G(V,E)中，在给定的源节点与目的节点之间寻找满足QoS约束要求的可行路由(B≤Band(K),D≥Delay (K))，然后通过计算各条可行路由的权重值Weight，选取Weight值最大的可行路由进行数据传输。针对DSR协议没有考虑的QoS保障，对DSR协议从权重策略方面进行了研究分析。将其DSR路由转发的优先级设计转发的权重公式如下:权重与链路的延时、跳数、能量以及带宽成正比。

Weight=a1×T1+a2×H2+a3×E3+a4×W4

(3)

其中，T1表示延时；H2表示跳数；E3表示能量；W4表示带宽。

当不满足B≤Band(K),D≥Delay(K)中的任意一项，则不进行转发，从而删除不满足延时、带宽条件下的路径；权重大的节点获得转发路径的优先级，从而更容易被选中成为网络中的中继节点。

2.2 基于链路反馈的策略

在路径维护的过程中，对链路的生存状态进行预测。由于传统的DSR路由协议是以最小跳数作为度量参数来建立路由，而忽略了路由上链路的传输质量，导致路由整体性能不佳。因此提出选用期望控制报文次数(Expected Control Packet Count，ECPC)作为评估链路质量的度量参数。

如图1所示，假设节点i和j之间可以建立有效的通信传输数据，则ECPC表示在无线网络中节点i和j之间进行一次成功的数据报文传递时，需要的传输次数预期值。ECPC的取值需要通过计算节点之间的前向传输率Pf和反向传输率Ps来获取。假设在一定的滑动窗口时间内，节点i会向节点j发送数据，则节点j成功接收数据的成功率为Pf，当节点j收到数据后会反向给节点i发送应答报文，则节点i接收到应答报文的成功率为Ps，因此此条链路间的ECPC可以通过式(4)计算得到：

(4)

图1 节点i和j之间链路的ECPC值

由于一条路由的ECPC值由该路由上链路之间的ECPC累加值决定。若ECPC累加值越小，则链路间的分组传递率就越高，路由性能就越高效可靠。若链路的状态计算公式为：

flag=Pf×Ps

其中，Pf代表前向传输的概率；Ps为后向传输的概率。flag越高，代表链路的状态越好。

在DSR选出的多向路径中，若Pf×Ps值稳定，则代表链路越稳定。源端收到数据包时，通过比较收到反馈的包，如果源端收到更稳定的路径返回，则源端更新自己的路由表及下一跳。

2.3 基于均衡能量的策略

当能量低于某一值时或者发生链路的中断时，标记链路的状态，置flag为0。在数据包的转发过程中，携带节点的能量信息。当节点的能量低于阈值时，认为节点的能量将消耗完。其他转发节点携带收到的低能量的信息并转发直至数据包的源节点。当源节点接收此数据包时，从路由中表中删除低能量节点的链路。再重新发起路径请求，寻找更优的路径充当中继。能量阈值的反馈作用对网络的链路状态起到了预警作用，从而让源节点主动变更路径。

3 仿 真

3.1 仿真工具和仿真参数的设置

目前国内外大部分研究机构均采用NS2对无线自组网的路由协议进行仿真。移植算法在NS2框架下，设置的场景如下：数据流为创建了一个具有50个移动节点、10对通信连接和每秒钟发送2个分组的，以CBR为业务源的通信场景文件。移动场景设置为一个具有50个节点、节点在每个地点停留0 s(即不停留)、最大移动速度20 m/s、仿真时间300 s、长1 000 m和宽300 m的移动场景文件。其中暂停的时间可变，用于比较DSR路由协议改进前向的参数性能。

为了模拟节点能量的差异性，该测试环境下设置了两种不同概率的能量:一种为普通能量的，设置节点的比率为80%，初始的能量结合TCL脚本设置为80 J；另一种为高能量的，设置的比率为20%，初始的能量结合TCL脚本设置为80 J。仿真参数见表1。

表1 仿真参数

在实验仿真过程中，setdest用来设定节点运动场景文件，cbrgen用来生成传输负载，awk用于从TCL脚本生成的trace文件中提取数据，最后使用Matlab工具绘制成图。

3.2 性能评价指标

节点的分组投递率、路由发起频率、归一化路由开销、平均延时和节点的剩余能量等参数是衡量路由协议性能及网络的重要指标[11-14]。所以对DSR路由协议和DSR-I路由协议也是从这五个方面进行仿真实验和结果分析。

分组投递率(Packet Delivery Ratio)的计算公式为：

(5)

其中，Rni为节点i成功接收的报文数；Sni为节点i成功发送的报文数。

路由发起频率(RouteDiscoveryFrequency)的计算公式为：

(6)

其中，Dni为节点i的路由发现次数；Time为协议的仿真时间。

归一化路由开销(NormalizedRootingLoad)的计算公式为：

Normalized Rooting Load = (SCn+ FCn)/RDn

(7)

其中，SCn为发送的路由报文数；FCn为转发的路由报文数；RDn为接收到的数据报文数。

端到端平均延时(AverageDelay)的计算公式为：

(8)

其中，N为成功传输的数据报文的总数；Rti为第i个报文接收的时间；Sti为第i个报文发送的时间。

能量模型是采用NS2.34版本自带的，NS2中实现的能量模型是一个节点属性，能量模型也表示了一个移动主机的能量水平[15-18]。在开始仿真时，所有节点的能量模型对应一个能量初始值，模拟过程中还会产生每个包发射和接收的能耗。

3.3 仿真结果对比与分析

分组投递率的仿真实验结果对比如图2所示。

图2 DSR和DSR-I分组投递率对比

从图2可以看出，当暂停时间越大，表明节点移动性越慢，当节点的移动暂停时间为300 s，而仿真的总时间为300 s，表明节点不移动，此时分组投递率的成功率越高。当节点的移动暂停时间为0 s时，节点一直在移动，此时分组投递率的成功率较低，丢包率比较明显。DSR-I由于考虑基于链路的反馈作用，相对于DSR选出的路径更加稳定，表现为接收的分组投递率高。

路由发起频率的仿真实验结果对比如图3所示。

从图3可以看出，当暂停时间越大，表明节点移动的越缓慢，路径变更不明显，由此带来的路由发起频率越低。DSR-I由于考虑到网络中节点的能量以及链路的质量通信情况，相比DSR进行了预警信息，并且主动变更了即将断开的链路与通信质量不佳的链路，因此路径变更的概率减小，表现为DSR-I路由协议发起的频率较低。

图3 DSR和DSR-I路由发起频率对比

归一化路由开销的仿真实验结果对比如图4所示。

图4 DSR和DSR-I归一化路由开销对比

从图4可以看出，当暂停时间越大，表明节点移动性越慢，路由越稳定，路由开销越小。DSR-I由于考虑到网络中节点的能量以及链路的质量通信情况，由于网络中节点的能量消耗完或者节点的移动，更易于对链路的变化进行快速响应。因而选出的路径更加稳定，需要用于控制包来变更路径的变化指令更少，表现为DSR-I路由协议开销降低。

端到端平均延时的仿真实验结果对比如图5所示。

图5 DSR和DSR-I平均延时对比

从图5可以看出，当暂停时间越大，表明节点移动性越慢，路由越稳定，端到端的平均延时越小。当节点的移动暂停时间为0 s时，节点一直在移动，由于路径的不断变更，端到端的平均延时越大。DSR-I考虑到删除带宽较小、延时较大、跳数较大等的路径，剔除了一些不满足最佳QoS的次要路径，从而选出的路径为优化后的结果，表现为DSR-I端到端的延时更短。

节点的剩余能量仿真实验结果对比如图6所示。

图6 DSR和DSR-I节点剩余能量对比

从图6可以看出，DSR-I选择出来的路径更加稳定，用于路由发起的控制包减少，网络中的能量避免了因侦听到过多的控制广播而产生大量的能量消耗。使得DSR-I相比DSR，网络中的节点剩余能量得到更好的节省，进一步延长了网络的生存时间。

4 结束语

DSR是为无线Ad hoc网络设计的路由协议，但是没有QoS保障。当节点的能量有差异化时，容易选中能量低的节点充当中继，从而影响网络的生存时间。其次，能量低的节点在能量将耗尽时，也无法感知网络的链路即将变更信息。

在分析总结国内外针对DSR协议所做相关工作的优缺点的基础上，文中提出一种基于权重、链路反馈和均衡能量的DSR-I改进协议。

DSR-I路由协议在查找路径、正向发送路由请求的过程中，选择带宽、时延、跳数、能量四个方面的因素，满足时延和带宽要求并且剩余能量大的节点充当中继节点的权重较高，延时较低，从而获得比较高的优先级。在数据包发送的过程中，低能量的节点反馈能量状态，并且剩余能量大，获取链路质量好的反向路径。当能量较低或者通信质量不好时，主动报告源端，源端主动断开旧链路，从而变更路径。仿真结果表明，改进后的DSR-I协议有效地改进了DSR路由不稳定、时延大和能量不平衡等缺点，有效地提升了DSR的性能。

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

[2] 张简丽，许洪光.基于DSR的路由协议综述[J].通信技术，2009,42(1)：137-139.

[3] 赵菊敏，张子辰，李灯熬，等.基于LEACH路由协议的多跳节能路由算法[J].计算机测量与控制，2014,22(5)：1506-1509.

[4] Zhang Dongli,Jiao Wencheng,Zheng Jianling.Research and improvement of DSR protocol in Ad hoc network[C]//Proc of 2010 2nd international conference on industrial and information systems.[s.l.]:[s.n.],2010:242-244.

[5] 李 梅，周继鹏.基于负载均衡的DSR路由协议改进[J].计算机应用研究，2011,28(1)：256-258.

[6] 沙 毅，张 婷，陈 进，等.基于流量的Ad hoc网络负载均衡路由协议[J].东北大学学报:自然科学版，2010,31(3)：350-353.

[7] 刘 荣，王 东，李晓鸿．移动Ad Hoc网络中基于剩余生存时间的链路稳定性路由协议[J]．计算机工程与科学，2012, 34(12) 9-15．

[8] 杨东勇，陈晓倩，顾东袁．一种节能的无线传感器网络路由协议的设计与实现[J]．计算机工程与科学，2010, 32(4) 110-113．

[9] 邓亚平,杨 佳,胡亚明.动态分簇的异构传感器网络安全路由协议[J].重庆邮电大学学报：自然科学版,2011,23(3):336-342.

[10] 田 敏,刘占军,李 云,等.一种基于节点度数的Ad Hoc网络稳定路由协议[J].重庆邮电大学学报：自然科学版,2007,19(5):558-561.

[11] 王鲁光，贾智平，李 新.AODV和AOMDV路由协议性能分析与比较[J].计算机应用，2010,30(3)：740-744.

[12] 李向丽，李超超.基于小世界理论和QoS支持的DSR协议[J].传感器与微系统，2014,33(2)：43-46.

[13] Ahmad S,Awand I.Performance analysis of DSR & extended DSR protocols[C]//Proceedings of IEEE military communications conference.[s.l.]:IEEE,2007.

[14] 叶海滨，张华熊，马汉杰，等.基于NS2的能量模型的研究[J].工业控制计算机，2013,26(1)：77-79.

[15] 朱 睿，吕秋冬，张连芳.基于DSR协议的区域路由研究[J].微计算机信息，2007,23(3-3)：114-116.

[16] 王 英，黄 群，李 云，等.一种新的协作的路由协议:C-DSR[J].计算机应用研究，2013,30(7)：2148-2150.

[17] Tamilarasi M,Palanuivelu T G.A strategy to reduce the control packet load of MANETs with bidirectional links using DSR[J].International Journal of Network Management,2008,18(4):365-376.

[18] Gupta A.MIKBIT-Modifiled DSR for MANET[C]//Proc of IEEE 4th international conference on internet multimedia services architecture and application.[s.l.]:IEEE,2010.

Design and Simulation of an Improved DSR-I Routing Protocol

WU Lei，PI Zhi

(Computer Institution,North China University of Technology,Beijing 100144,China)

The DSR is a protocol designed for Ad hoc network,which possesses good performance.But it has problems including instable routing,long delay and unbalanced energy.Aimed at these shortages of DSR,through the research and analysis to DSR,an improved routing protocol is proposed based on weight,link feedback and equilibrium energy.The main idea is that nodes with higher energy are selected to act as a repeater in the path of meeting the weight and nodes with lower energy are used to feed back energy state in the process of data packets transmission.The source disconnects actively with the old link,thus changing the path.The NS2 platform is used to make a simulation experiments and performance analysis between DSR-I and DSR.These simulation results show that the improved DSR-I protocol promotes the performance obviously compared with the original DSR.

DSR;Ad hoc network;weight;equilibrium energy;NS2;simulation

2015-05-28

2015-08-31

时间：2016-01-26

北京市自然科学基金资助项目(4131001)；中央支持地方专项(PXM2014_014212_000097)；北京市属高等学校创新团队建设与教师职业发展计划项目(IDHT20130502)作者简介：吴 磊(1963-)，男，副教授，硕士研究生导师，研究方向为嵌入式系统和无线通信技术；皮 智(1990-)，男，硕士研究生，研究方向为嵌入式技术。

http://www.cnki.net/kcms/detail/61.1450.TP.20160126.1522.076.html

TP391.9

A

1673-629X(2016)02-0017-05

10.3969/j.issn.1673-629X.2016.02.004