基于链路质量的移动Ad hoc路由算法

摘要：针对在移动Ad hoc网络中，由于节点移动和能量有限导致节点失效、传输链路不稳定的问题，改进原有链路剩余时间计算方法，并与节点剩余能量结合计算路径质量，将路径质量作为判决条件引入到AODV协议中，最终形成基于链路质量的路由算法。仿真表明改进的算法可提高选择路径的可靠性，降低丢包率和平均端到端时延。

关键词：路由算法； AODV；链路质量

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2013）04-0751-04

Routing Algorithm Based on Link Quality in Moblie Ad hoc Networks

ZENG Ge-ping，CHEN Yue

（ Chongqing University of Posts and Telecommunications， Chongqing 400065，China）

Abstract： Because of node mobility and energy limitation lead to node failure and transmission link instability in Ad hoc Networks， improve original Link Lifetime calculation method， calculate path quality with node residual energy， the path quality as a judgment condition introduced into AODV protocol，Ultimately form routing algorithm based on link quality. Simulation results show that the improved algorithm can improve the selection path reliability and reduce the packet loss rate and the average end-to-end delay.

Key words： routing algorithm； AODV； Link quality

移动Ad hoc网络[1]是一种无线自组织网络，节点间通信无需固定基础设施的支持，广泛应用于战场、应急救援等需快速部署的环境。在该网络中，节点间通过中间节点的帮助以多跳的方式进行通信，由于网络中节点间的移动和能量有限，网络拓扑动态变化可能导致链路断裂、路由重建，从而使数据包丢失重传，网络性能下降。目前基于链路质量的Ad Hoc路由的研究主要在路由协议中增加QoS机制，该文针对现有的链路剩余时间预测方法进行改进，结合数据传输对节点能量的需求，提出一种新的基于链路质量的路由算法。

1 网络模型

给定网络拓扑图G=（V，E），V是网络节点集合， vi∈V表示网络中任意节点，E表示网络中存在的通信链路集合。假设网络中所有节点都能感知自身实时能量状态，附带配置GPS获取节点位置。

2 路径可用性预测算法

该算法的核心思想是：对所选的影响链路质量因子进行预测处理，将不同参数通过一定的规则形成一个单一的度量，并以此作为路由选路的基础。该文选择两个影响Ad Hoc网络的参数：剩余链路时间和节点剩余能量来简化链路质量预测问题，通过将节点当前剩余能量能够满足待传数据的能量需求为基础，并对节点间链路有效维持时间进行预测，通过对路径中的节点的剩余能量瓶颈与路径中各条链路的有效时间的最小值进行处理，形成一个路径质量，比较不同路径的路径质量进行选路。

2.1 节点剩余能量计算

节点剩余能量计算是确定节点能量是否满足数据流对传输节点的能量要求，路由请求时，计算源节点发送的数据流所需能量，在选路时记录中间节点完成当前任务后剩余能量与能量需求进行比较，得出节点能否作为路由中间节点进行数据转发。

本文采用文献[2]中提出的能量消耗模型，Eold表示节点当前能量，Enew表示节点剩余能量，Econsume表示节点消耗能量，由此可得：

[Enew=Eold-Econsume] （1）

节点的能量消耗Econsume主要由数据发送、接收和转发三部分组成，设节点发送一个数据分组所需能量为

[Esen=PsTp=IsVTp] （2）

接收需要消耗的能量为

[Erecv=PrTp=IrVTp] （3）

转发需要消耗的能量为

[Eforw=（Psend+Precv）Tp] （4）

因此节点消耗的能量为

[Econsume=Esend+Erecv+（N-1）Eforw] （5）

其中Psend表示节点发射功率；Precv为接收功率；Tp表示发送或接收数据时间；Is为发送电流；Ir为接收电流，在无线网络环境下传输速率不同的网卡在同等条件下的能量消耗相似，所以取无线网卡工作电压为5V，数据接收状态工作电流Ir=230mA，数据发送状态工作电流Is=330mA。

定义1：一条路径中剩余能量值最小的节点为该路径的能量瓶颈节点，其剩余能量为路径瓶颈剩余能量（记为Path _bn_RE）

[Path_bn_RE=min（REvi）] （6）

由于移动Ad Hoc网络是由多个能量受限的节点组成，因此应选取满足数据包传输能量需求的节点作为中继节点。

2.2 节点运动模型及链路剩余时间预测

定义2：组成路径的各条链路中链路剩余时间最小的链路为该路径的瓶颈链路，其链路剩余时间为路径瓶颈链路剩余时间（记为Path_bn_RLL）。

考虑如图1所示的网络模型：设节点S为源节点，B为目的节点，A为它们的邻居节点，坐标分别为（xS，yS）、（xA，yA）、（xB，，yB），速率与方向分别为[vS]、[θS]，[vA]、[θA]，[vB]、[θB]，节点A要作为S和B节点的中间节点，必须满足：A在S的通信范围之内；B不在S的直接通信范围之内，因此定义SA链路的寿命定义为节点A处于节点S的传输范围内时间和节点运动过程中距离dAB小于距离dSB的时间。

图 1 链路剩余时间预测模型

根据文献[3]，节点A处于节点S通信范围的时间预测为：

[t*=[-（ab+cd）+（a2+c2）r2-（ad-bc）2]/（a2+c2）]r表示传输范围，[a=vAcosθA-vScosθS] ，[b=xA-xS]，[c=vAsinθA-vSsinθS]，[d=yA-yS]。

另一方面，节点B作为中间节点，dSB应大于dAB因此链路剩余时间计算的临界条件为dSB等于dAB； 设dSB=dAB的时刻为t，由文献[4]得：

[t=[（ag+bh-ce-df）]±e2（a2+b2-d2）+f2（a2+b2-c2）+g2（c2+d2-b2）+h2（c2+d2-a2）+2（cdef+agbh）-（cd+df）（ag+bh）]/（e2+f2-g2-h2）]

其中

[a=xB-xSe=vBcosθB-vAcosθAb=yD-ySf=vBsinθB-vAsinθAc=xB-xAg=vBcosθB-vScosθSd=yB-yAh=vBsinθB-vSsinθS]

因此，链路LinkSA的链路剩余时间为：

[RLLSA=min（t*，t）]

因此，路径的瓶颈链路剩余时间为：

[Path_bn_RLL=min（RLLij）]

其中，RLLij为路径中的相邻节点Vi与Vj之间的链路剩余时间。

2.3 路径质量计算

定义3：路径质量，用Path_qualityi表示存在的路由中i条路径的路径质量，Path_bn_REi表示i条路径的路径瓶颈剩余能量，Path_bn_RLLi表示第i条路径的路径瓶颈剩余链路时间，HopCouti表示第i条路径的跳数，则：

[Path_qualityi=（w1×Path_bn_REi+w2×Path_bn_RLLi）/HopCounti]

其中，w1，w2为对应的加权系数，其大小体现不同参数的重要性，且满足w1+w2=1；加权系数的大小可以根据不同的环境来设定，这样使得算法更加灵活。

3 PQR-AODV路由协议

本算法与标准的AODV算法比较，存在以下几点不同：

1）RREQ包中增加能量需求度量In_node_energy_req、Path_bn_RE以及路径瓶颈链路剩余时间Path_bn_RLL字段；

2）RREP包中增加一个1bit标志位区分子路径修复通知的RREP与路由发现应答和路径质量字段Path_quality；

3）Hello包中需要增加节点位置信息字段。

4）增加一个Notice消息，在路径修复过程中充当通知消息。

当网络中节点有通信需求时，但又没有直接可用的路由，源节点生成路由请求包（RREQ）并广播该报文从而开始路由发现过程，算法描述如下。

1）RREQ处理步骤

第一步：节点收到RREQ报文后，首先判断是否重复收包，是则丢弃该报文结束处理，否则转第二步；

第二步：检查判断该节点是否为目的节点，是则转第三步，否，则转第四步；

第三步：计算路径质量并回复RREP报文，转第六步；

第四步：判断节点记录的剩余能量REnew是否大于In_node_energy_req，若是，则转到第五步；否，则丢弃RREQ报文，转第六步；

第五步：判断节点记录的剩余能量是否大于Path_bn_RE，否，则将Path_bn_RE更新为REnew的值；判断该节点与上游节点的链路剩余时间RLL是否大于Path_bn_RLL，否，则将Path_bn_RLL更新为RLL的值。

第六步：结束。

2）路径修复

路由修复借鉴了蜂窝网络中的切换思想，路径上的节点实时监测剩余能量和链路剩余时间，若低于危险阀值，发送Notice消息，通知原节点建立备份路由；继续监测节点链路信息，若低于切换阀值，则认为链路即将断裂，切换路由到备份路由，保证数据传输

4 仿真分析

本文利用NS2[8]对AODV协议与改进协议的性能进行了比较，仿真场景如下：节点运动模型采用Random way’point model ，30个网络节点随机分布在800[×]800m2的矩形区域内，节点分别以（5，10，15，20，25，30）m/s五种速度移动，节点无线覆盖范围为250m，节点初始能量为250J，仿真时间为300s，分别对不同的权值进行模拟，仿真采用固定包速率的流量源，以每秒5个数据包的速率发送，每个包的大小为512字节。

4.1 仿真结果及分析

本仿真场景主要对比节点移动状态下三种路由协议的性能，分别对比丢包率、平均端到端时延以及控制信息开销三个方面。

如图2所示，随着节点移动速度的增加，两种协议包丢失率都相应增加。这是由于节点移动速度增大，节点链路断链概率增大，路由断链修复次数增多，包丢失率上升。改进路由协议由于加入链路质量选路机制且对路径修复机制进行改进，在路径失效前进行路由修复，降低了节点因能量耗尽而引起的路由失效对数据传输的影响，其包丢失率比AODV小。

如图3，在平均端到端时延方面，两种协议均随节点移动速度增加而增加，节点移动速度较小时，改进协议与AODV近似，随着节点移动速度的增加，改进协议端到端时延明显优于AODV路由协议，这是由于节点移动速度增大，改进协议选择路由可靠性比于AODV高，路径断裂概率降低，且采用的路径修复策略能进一步缩小路径修复时间，从而进一步降低端到端时延。

5 结束语

由于移动Ad hoc网络的移动性和节点能量有限传输路径失效导致网络性能下降，该文提出基于链路质量的路由算法。在路由发现过程中，通过考虑节点剩余能量和链路质量提高所选路由稳定性，并提出基于节点剩余能量的路由修复机制通过预测提前发起路由修复，有效防止路由失效所产生的丢包问题。仿真结果表明改进后的算法选择的路径具有更好的可靠性，降低了平均端到端时延以及丢包率。

参考文献：

[1] Toh C-K. Ad hoc mobile wireless networks： protocols and systems[M].New Jersey： Prentice Hall， 2002.

[2] WANG Yu.Collision avoidance in multi-hop Ad hoc networks[C].Proc of the 10th IEEE International Symposium on Modeling Analysis and Simulation of Computer and Telecom unications Systems（MASCOTS’02）.USA：IEEE，2002.

[3] Chen Y，Wang G，Peng S.Link Lifetime-Based Segment-by-Segment Routing Protocol in MANETs[C].International Symposium on Parallel and Distribute Processing with Applications.2008

[4] Hadi Noureddine， Hamed Al-Raweshidy.A New Link Lifetime Prediction Method for Greedy and Contention-based Routing in Mobile Ad Hoc Networks[C].10th IEEE International Conference on Computer and Information Technology，2010.

[5] 陈林星，曾曦，曹毅.移动Ad Hoc网络--自组织分组无线网络技术[M].北京：电子工业出版社，2006：4-1.

[6] 刘元安，唐碧华.Ad Hoc网络中的路由算法[M].北京：北京邮电大学学报，2004，27（2）：1-7.

[7] 黄蕾，刘利祥.Ad Hoc网络寻路阶段的合作激励机制研究[J].计算机学报，2008，31（2）：262-269.

[8] 徐雷鸣，庞博，赵耀.NS与网络仿真[M]北京：人民邮电出版社，2003.