一种基于权重的DSR路由改进算法＊

刘 丽，郭中华，雍 辉

(宁夏大学 物理电气信息学院，宁夏 银川 750021)

Ad Hoc网络是由一组带有无线收发装置的移动节点组成的多跳临时性自组织系统。由于其拓扑结构的时变性，以及无线信道的不确定性，使得其路由算法面临挑战。而节点依靠有限寿命的电池供电，一旦节点的电池能量耗尽，将会影响网络中数据包的转发，进而影响网络性能。因此，如何在节点间选择合适的路由，是Ad Hoc网络的核心问题[1]。现有的经典路由算法，如DSDV[2]、CGSR[3]、AODV[4]、DSR[5]等 都 是 最 短 路 由 ， 即 最 小 跳 数 路由，不考虑能量因素。

目前，Ad Hoc中的节能路由算法主要有两个方向[6]：一是使发送每个数据包耗费的总能量最小；二是尽可能地延长网络的生存时间。参考文献[7]提出的MECR(Minimum Energy Cost Routing)是最小能耗路由协议。由于它总是选择能耗最小的节点，容易使一些关键节点过早地消亡，导致了节点间的能量不均衡和网络的分区；ESR[8](Energy Saving Routing)协议通过引入节点的期望时间(剩余能量和当前传输功率的比值)来延长网络的生存时间，但是传输功率控制的引进将会导致无线设备的硬件改动。本文提出的算法，是在原有的DSR路由算法基础上改进而成的。方案保留DSR的按需路由机制，在选路由的时候，除了最小跳数外，综合考虑每条路由组成节点的剩余能量，提出一种基于权重的路由算法，根据路由权重的大小选取路由，尽量选用跳数少、剩余能量多的路由，从而达到节省能量，延长网络生命的目的。

1 MWSR路由算法

1.1算法的基本思想

该算法综合考虑能量与跳数构建一个路由权重函数，在这两个参数之间寻找一个折中点，选择路由权重值最大的路径传送数据，即期望找到一条组成链路生存时间比较长且跳数又较少的路由作为最后选定的路由，使得在延长网络生存时间的同时，不会牺牲其他一些性能。至于上述两个参数在路由权重函数中的比重，将由加权因子决定。

1.2算法的参数模型

为了便于研究，把Ad Hoc网络定义为图 G=(V，E，t)，其中 V为节点，E为边，t为边的权值，表示对应链路的剩余生存时间，即一条边还能保持通路的时间值。

1.2.1路由的能量参数

本文将路由有效期作为路由的能量参数，即预测路由所有组成链路的剩余生存时间，将其最小值作为该条路由的能量参数。该能量参数可用如下公式表示：

以此为基础构造的路由权重函数可以起到保护剩余能量较低节点的作用。其中，En表示路由rn的能量参数，i，j代表路由 rn中的两个相邻节点，t(i，j)代表节点 i与j之间链路的剩余生存时间值。

链路的剩余生存时间值并不能如节点剩余能量那样直接得到，而是需要通过预测得知。在GSM[9]算法中，链路剩余生存时间值的计算公式为

式(2)在计算时忽略了接收节点被用来作为下一跳还能维持的时间。

为了克服GSM这个弱点，既要考虑发射节点发射该数据所能维持的时间，又要考虑接收节点接收并转发该数据到下一跳还能持续的时间，以两者中较短的时间作为该链路对应的剩余生存时间。因此，该时间权值可由如下公式表示：

1.2.2路由权重函数

为了选择出最佳路由，需要构建一个路由权重函数，该函数的表示形式如下：

式中，rn表示有效路由集 R={r1，r2， …，rN}(1≤n≤N)中的某条路径，ω是加权因子，En表示路由rn的能量参数，Hn表示路由rn的跳数，且有：

从表示形式可看出，此路由权重函数由两部分组成：跳数和能量。之所以将跳数也作为代价函数的参数之一，是因为如果只将能量作为函数的考虑因素，确实可以起到延长网络生存时间的作用，但网络的其他一些性能将会“恶化”很多。而且路由的跳数对节省节点能量也起一些作用，数据传输时所用路由的跳数越少，路由就越稳定，越不容易发生路由“断裂”的情况，从而有效地避免数据重传以及再次发起路由发现过程，这对于节点移动性较强的Ad Hoc网络作用尤为明显。

1.2.3加权因子

加权因子ω决定了跳数和能量这两个参数在路由权重函数中的比重。CMMBCR[11]协议根据网络中节点剩余能量的不同情况采取不同的路由选择策略。借鉴这一思想，加权因子ω的值将根据路由候选集中各条路由组成节点的剩余能量情况来确定。

假设网络中所有节点的初始能量值相同，则有：

式中，vn，l表示 路由 rn中的节点，p(vn，l)表示节 点 vn，l的剩余能量，p0表示节点的初始能量。

可以看出，当各条路由中节点的能量状况较好时，ω值较大，此时跳数在路由权重函数中所占的比重较大，该算法倾向于选择跳数较少的路由；反之，当能量状况较差时，ω值较小，此时能量参数所占的比重较大，该算法倾向于选择有效生存期较长的路由，从而起到保护剩余能量较低的“瓶颈”节点，尽可能延长网络生存时间的目的。

1.3 MWSR路由算法的描述

该算法的前提是基于网络中所有链路均为双向，且节点可以随时提供剩余能量的假设。

假设S为源节点，D为目的节点。一次数据传输过程的主要步骤如下：

(1)利用DSR路由机制进行路由发现，但在RREQ报文中需添加节点最小剩余能量域re、链路最小剩余时间域rt与节点剩余能量和域sum。

(2)D开启一个定时器，保存该时间内收到的所有RREQ报文中的路由。

(3)D根据路由信息计算出每条路由的路由权值W，选出具有最大权值的路由rn。

(4)D沿rn反向路由发送RREP报文到 S，进行数据传输。

2仿真及分析

2.1场景设置

使用NS[12]软件来进行仿真，场景设置如下：在1 000 m×1 000 m的正方形区域内随机分布25个无线节点，节点按照RandomWaypoint模型移动；MAC层协议采用 IEEE 802.ll；使用CBR作为流量源，每条流的通信流量为20 kb/s；节点的无线信号传输模型设为TwoRayGround；节点的初始能量设为200 J，路由损失因子设为4，即如果节点 u和v之间的距离为d，则u发射数据到v需要的能量为d4，接收功率设为 0.l W，监听功率设为 0.08 W；仿真时间1 200 s。

2.2仿真结果与分析

仿真结束之后，对Trace文件进行分析，主要统计端到端平均延时和网络生存时间来衡量网络性能。

图1表示网络的端到端平均延时与节点最大移动速度之间的关系；图2表示死亡节点个数与仿真时间的关系。

图1 端到端平均延时与vmax之间的关系

由图1可以看出，随着网络节点最大移动速度的增加，端到端平均时延总体上呈上升趋势，但MWSR算法的端到端平均延时要比DSR低。虽然DSR协议选取最小跳数的路由发送数据，本应获得更短的时延，但由于DSR协议没有考虑网络节点的负载情况，容易导致网络拥塞，从而加大了网络时延。所以在网络负载较重的情况下，MWSR算法的延时会较短。

由图2可以看出，采用MWSR算法的网络生存时间要比采用DSR协议的网络生存时间长。这是因为该算法把链路的剩余生命期作为选择路由的标准之一，选择路由时尽量避开生命期较短的节点，从而延长了网络的生存时间。而且随着死亡节点数量的增加，该算法的节能效果越明显。通过对图2中的3个图进行对比可以看出，节点最大移动速度vmax越小，算法的节能效果越明显，这说明该算法主要适合于节点移动速度较慢的场合。

图2 不同vmax时死亡节点与仿真时间的关系

本文在原有DSR路由协议的基础上作了一些改进，提出了一种基于权值的节能路由算法。通过综合考虑路由有效期与跳数，构造路由权重函数对路由进行选择，以期达到节能的目的。仿真结果表明，在相同条件下，该算法比基于最小跳数的DSR能节省较多的能量，从而延长了网络的生命周期，同时也减小了网络的端到端延时。但是由于数据包头部附加的信息改变了数据包的结构，增加了数据包的长度，不可避免地会带来额外的开销。

[1]LI Jiang， CORDES D， ZHANG Jing Yuan.Power-aware routing protocols in Ad hoc networks[J].IEEE Wireless Communication， 2005(12)：1536-1284.

[2]MAHESH K M，DAS S R.On-demand multipath distance vector routing in Ad hoc networks[C]//Ninth International Conference on Network Protocols.Washington D.C.，USA：[s.n.]， 2001：14-23.

[3]PERKINS C E，ROYER E M.Ad-hoc on-demand distance vector routing，Proc[C].2nd IEEE Workshop on Mobile Com.Sys.and Apps.，1999：90-100.

[4]RFC3561.Ad hoc on demand distance vector(AODV)routing[DB/OL].http：//www.Ietf.org/rfc/rfc 3561.2003-07-23.

[5]JOHNSON D B， MALTZ D A， BROCH J.DSR：the dynamic source routing protocol for multi-Hop wireless Ad Hoc networks[M].Boston， MA，USA：Addison-Wesley Longman Publishing Co.，Inc， 2001：139-172.

[6]CHEN JiaYing，ZHEN Yang.Modified energy-aware AODV routing for Ad hoc networks[J].Journal of Nanjing University of Posts and Telecommunication， 2004，24(3).

[7]WANG H C，WANG Y H.Energy-efficient routing algorithms for wireless ad-hoc networks，Proc[C].18th IEEE PIMRC，2007.

[8]PENG Jing， TANG Chang Jie， ZHANG Jing， et al.Evolu-tionary algorithm based on overlapped gene expression[C]//ICNC-LNCS3612.Berlin：Springer，2005：194-204.

[9]ORDA A，YASSOUR B A.Maximum lieftime routing algorithms for networks with omnidirectional and directional Antennas[C].Proceedings of the 6th ACM International Symposium on Mobile Ad hoc Networking and Computing Mobi-Hoc’05， May 2005.

[10]楼骥洲.Ad hoc网格的生命周期最大化算法[D].杭州：浙江大学，2006.

[11]TOH C K.Maximum battery life routing to support ubiquitous mobile computing in wireless ad hoc networks[J].IEEE Communications Magazine， 2001(6)：2-11.

[12]秦冀，姜雪松.移动 IP技术与 NS-2模拟[M].北京：机械工业出版社，2006.