您好,欢迎来到好土汽车网。
搜索
您的当前位置:首页基于链路可用性预测的AODV路由协议研究

基于链路可用性预测的AODV路由协议研究

来源:好土汽车网
维普资讯 http://www.cqvip.com 第29卷第7期 2008年7月 通信学报 1.29 No.7 July 2008 Joufnal on Communications 基于链路可用性预测的AODV路由协议研究 洪利 ,黄庭培 ,邹卫霞 ,李树荣 ,周正 (1.中国石油大学(华东)计算机与通信工程学院, 山东东营257061;2.滁州学院计算机科学与技术系,安徽滁州239012 3.北京邮电大学电信工程学院,北京100876:4.中国石油大学(华东)信息与控制工程学院,山东东营257061) 摘要:传统的AODV路由协议无法适应Ad hoc网络拓扑的高度动态变化。对AODV路由算法进行链路可用性 预测扩展,节点通过接收分组的能量值和链路连续可用时间选择最可靠的路径进行路由,并在链路真正失效之前 启动预先修复过程。仿真结果表明,改进后的AODV协议提高了分组的投递率,降低了分组端到端平均传输延 时,路由协议的可靠性得到改进。 关键词:Ad hoc网络;路由协议;AODV;链路可用性预测 中图分类号:TN913 文献标识码:A 文章编号:1000—436X(2008)07.0118—06 Research of AODV routing protocol based on link availability prediction HONG Lil,HUANG Ting—pei2,ZOU Wei.xia3,LI Shu—rong4ZHOU Zheng3 ,(1.SchoolofComputerScienceandCommunicationEngineering,ChinaUniversityofPetroleum,Dongying257061,China; 2.College of Computer Science nad Technology,Chuzhou University,Chuzhou 239012,China; 3.School ofTelecommunication Engineering,Beijhag University of Posts and Telecommunications,Beijing 100876,China; 4.College of Information nad Control Engineering,China University of Petroleum,Dongying 257061,China) Abstract:The AODV routing protocol could not adapt to high dynamic topology change wel1.According to extend the AODV routing algorithm by the link availability prediction,the nodes selected the most stable path to route based on the power of received packets and the likn continuous availability time,and started hte route maintenance in advance before the likn broken.The simulation results demonstrate that the improved AODV routing protocol increased hte packet deliv— ery ratio and decreases the average end—to—end delay,and hte reliability of hte routing protocol is strengthened. Key words:Ad hoc networks;routing protocol;AODV;likn availability prediction 1引言 设施而临时组建。网络中的各个节点能够以任意可 能的速度和移动模式移动,加上无线收发设备类型 Ad hoc网络是由一组带有无线收发装置的移 多种多样、发送功率的变化、无线信道间的相互干 动节点组成的一个自治系统,不依赖于预设的基础 扰、地形和天气等综合因素的影响,节点间通过无 收稿日期:2007.05.18;修回日期:2008.05—30 基金项目:北京邮电大学泛网无线通信教育部重点实验室基金资助项目(2007102);国家自然科学基金资助项目(60432040, 60572020);北京市自然科学基金资助项目(052021);教育部博士点专项基金资助项目(20060013008) FoundationItems:TheKeyLaboratory ofUniverslaWirelessCommunicaitonLab,BeijingUnivesrity ofPostsandTelecommunications, Ministry of Education,P.R.China(200"/102);The National Natural Science Foundation of China(60432040,60572020);The Natural Sci- ence Foundation ofBeijing(052021);The Specila Foundation for Doctor,Ministry ofEducation(20060013008) 维普资讯 http://www.cqvip.com

第7期 洪利等:基于链路可用性预测的AODV路由协议研究 : !: 线信道形成的网络拓扑随时可能发生变化,而且变 化的方式和速度都难以预测。因此,在无线自组网 中选择一条稳定的路径进行路由,避免频繁的重路 由操作,降低网络拓扑动态变化对路由协议性能的 影响,成为Ad hoc网络路由协议研究的热点,尤其 是网络应用需要稳定的连接来保证一定的通信质 量的时候。 AODV[1]路由协议是专门针对Ad hoc网络自身 特点而设计的,具有控制开销和带宽开销小等特 点,但在路由建立过程中仅仅根据路由新旧程度和 路由跳数来选择路由,增加了使用不可靠路由的概 率,同时只有在检测到链路中断后才启动路由维护 过程,不仅增加了延时,还增加了分组丢失的概率, 特别是在拓扑变化频繁时。目前,国内外许多研究 人员对该领域进行了研究,文献【2]提出一种基于相 关性(affinity)的路由选择算法,选择最稳定的链 路而不用那些暂时的链路;文献【3]提出通过信号强 度变化来预测节点问链路的稳定性的方法。但这些 预测方法都是根据现在或过去的状态来衡量将来 的状态,而不能动态跟踪拓扑结构的动态变化,因 为随着时间的推移,现在稳定的链路可能会因为节 点的移动在将来变为不可用。文献[4]利用GPS提 供的节点位置和节点移动速度信息,预测链路的有 效期,这种方法需要额外的辅助设备,并且GPS设 备的使用环境有限。文献【5]提出一种结合无线电波 传播规律和节点移动模型的链路预测模型,通过对 链路状态的预测改进AODV协议,但这种预测没有 考虑节点在将来发生变化的可能。文献f6,7]提出一 种链路可用性预测算法,通过链路可用时间来度量 链路在将来某一段时间内的可用性,然而该预测算 法不能很好地适应拓扑结构的频繁变化。 正是针对上述研究工作的不足,结合对数距离 路径损耗原理和随机停留点移动模型,提出一种链 路可用性预测算法,并根据预测结果改进AODV路 由算法,使得改进后的AODV协议更好地适用拓扑 结构的动态变化。整篇文章组织如下:第2节给出 链路可用性预测算法;第3节阐述基于链路可用性 预测的AODV路由算法(LAP_AODV)的工作原理; 第4节提供了性能仿真结果并对结果进行了比较分 析;第5节是本文结束语。 2链路可用性预测算法 链路可用性预测算法的核心思想是:节点根据 对数距离路径损耗衰减模型估算接收到分组的能 量值,若分组能量值低于某一能量阈值时,即认为 该节点与其前驱节点间的链路进入危险状态,节点 启动链路可用性预测算法,借助随机停留点移动模 型,通过统计分析的方法预测节点在将来某一段时 间内的连续可用时间。 2.1能量阈值 节点对接收到的分组的能量值进行估计,与某 一能量阂值进行比较,并决定是否启动链路可用性 预测过程,因此应合理选择能量阈值,记为 mre。h0ld。 文献f8]指出:当节点间距离较小时,节点问的信号 变化规律符合自由空间模型;节点间距离较大时符 合双射线地面反射模型。然而理论和实际测试结果 表明,无论室内还是室外信道,平均接收信号功率 随距离成对数衰减。下面采用对数距离路径损耗模 型(1og—distance path loss mode1)来估算节点接收到 分组的能量值。对于任意的发送一接收(T-R)距离, 平均大尺度路径损耗可表示为 ———— 厂,,、 PL(dB):PL(do)+10nlogI÷f (1) 其中,n为路径损耗指数, 为参考距离,eL(do) 是通过自由空间模型得到的,计算公式如下 瓦 )=10log㈥=-10logl ctG ̄'I(2) 其中, 为发射天线的发射功率(w), 为接收天线 的接收功率(w);Gt、G为发射天线和接收天线的r 增益; 为自由空间电波波长。 对于典型的LucentWaveLAN环境,节点能识 别的最低能量值为3.65x10 。W,此时的通信范围 为250m。若节点的最大移动速度为v一,路由危险 警告消息或路由出错消息在网络中传输的最长时 间为tm ,则当节点问的距离为(250-V— )m时 的能量值可以定为能量阈值 。 。根据以上条件 可得到如下公式 1olog(3.65×10 ):瓦( )一10nlogf 1“ (3) 0 10log(St ̄。hold x l0 ) :p-L-(do)一10舶gf d1 (4) o 考虑最坏的情形, 为20m/s, 为 维普资讯 http://www.cqvip.com 。120。 通信学报 兰 !鲞 30x30ms=0.9s,由式(3)和式(4)即可得到典型的 LucentWaveLAN环境下的能量阈值 h。ld的值为 =性概率P(tLA)后, 可以得到链路连续可用时间 cA 的计算公式 A=tLA×P(tLA) (8) ( )3 x3.65x10-1 ̄=4.23x10-1 ̄W。 _2.2危险时间 LAP而路径的可用性依赖于组成这一路径的所有 链路的可用性,若路径中某一条链路变为不可用, 则整条路径将变为不可用。假设某一条传输路径 AODV路由协议维护过程所花费的时间 主要由发送路由危险警告(routing dangerous warning)消息或路由出错消息和路由建立组成。考 P={厶, ,…, )是由 l, ,… 这n条链路 组成,则有如下结论 虑最坏的情形即路由危险警告消息或路由出错消 息和路由建立所经过的路由跳数是网络直径 (NET_DIAMETER)的值,考虑到路由建立过程 由路由请求和路由应答2个过程组成,忽略其他的 时间开销,则预测式路由维护过程所经过的总的路 由跳数为3x ENT_DIAMETER。假定网络直径跳数 值为30,每一跳的传输延时为30ms…,则预测式 路由维护过程所需要的总时间为 =3xNET_DIAMETERx30,即为2.7s,因此 危险时间Tw定义为2.7s。 2.3链路可用性确定 用m、n表示网络中可以直接进行通信的2个 节点,m为n的前驱节点, fave1表示节点n在最 近三次周期性的采样来自节点m的信号强度变化 的平均值,用 f ̄llTen 1表示节点,l目前采样到来自 节点m的信号能量值, 表示节点接收到分组的 能量值的变化率, 的计算公式如下 △ 【 ( 一 )一 呻 。)J/△f (5) 若 大于0,表示节点接收到分组的能量值 强,链路未进入危险状态,否则通过以下公式计算 链路可用时间 的值 t :—T Othreshold--—Omn(current)  (6)… 链路可用性概率P(tL )是估计链路从f0时刻 连续可用到f0+ . 时刻的概率,即有 P( )=e{ ̄CZto+ 时刻可用l链路在f0时刻可用} ’则根据随机停留点移动模型的统计特性可得 到链路可用性概率的计算公式L9J 1 P(tLA)= (tLA)=_ L一_一I ,(vtL )dv(7) m k'min Vm’in 估算出节点间的链路可用时间 A和链路可用 cT mini A2'… A j (9) 3 LAP_AoDV路由协议 3.1工作原理 LAP_AODV路由算法主要由三部分组成:链路 可用性预测模块、预测式路由建立模块和预测式路由 维护模块,其中链路可用性预测模块是整个路由算法 的核心。根据链路可用性预测结果,在路由选择过程 中,除了考虑路由新旧程度和路由跳数等传统参数 外,还考虑了路径中各条链路的可用性状态参数。在 路由维护过程中,当预测到链路连续可用时间低于某 一危险时间时,启动预先修复过程,在路由真正失效 之前获得新的路由,完成新旧路由的切换。 LAP_AODV路由算法各部分之间的关系如图1所示。 估算节点 收到分 能量阈值 的能量值 建立模块 小 能 危 于 l路可用 量 险 危 预测模块 阈 时 险 值 间 时 间 页测节点 链路连续 危险时间 测式路由 可用时间 维护模块 图1 LAP_AODV路由算法的结构 LAP_AODV路由算法相对于AODV路由算法 来说,需要解决以下3个关键问题: 1)节点记录并处理接收到分组的能量值。 2)当接收到分组的能量值低于某一能量阈值 时,节点启动链路可用性预测算法,预测链路在将 来某一段时间内连续可用的时间。 3)当链路连续可用时间低于某一危险时间时, 节点启动预先路由修复过程。 3.2预测式路由建立 LAP_AODV路由建立过程在传统AODV路由 维普资讯 http://www.cqvip.com 第7期 洪利等:基于链路可用性预测的AODV路由协议研究 一。121‘ 协议的路由建立过程中添加了链路可用性状态参 数作为选路的标准。在路由选择过程中除了参考路 增益的全向天线,信道容量为2Mbit/s。表1给出 了仿真过程中所使用的环境参数。所有仿真实验结 果均为10次实验的平均值。在相同条件下对AODV 由新旧程度和路由跳数作为选路的标准以外,还考 虑了节点问的链路可用性状态参数。LAP_AODV 协议的路由建立过程主要包括5个子过程:广播路 由请求分组、路由请求分组转发、回复路由应答分 组、路由应答分组转发、路由选择。其中路由请求 和LAP_AODV 2种协议进行了仿真比较。 表1 仿真环境参数 转发和路由选择2个子过程是对原AODV协议中相 应子过程改进后得到的,对部分数据结构也进行了 扩展,其他3个子过程同AODV协议中的相应子过 程一致。在路由请求分组转发过程中,节点需要分析 其与前驱节点问的链路状态,并在路由请求分组中和 路由表中记录链路状态值;在路由选择过程中,根据 路由请求分组中携带的链路状态值,按照路由新旧程 度、链路可用性状态值、路由跳数从高到低的优先级 进行路由选择,其中链路可用性状态值可能是接收分 组的能量值,也可能是链路连续可用时间。 另外,如果中间节点发现源节点和目的节点之 4.2性能度量标准 为了能够全面分析改进前后AODV协议的性 能,本文从以下3个性能度量标准进行了分析。 1)分组投递率 间仅有不可靠路由时,不应该继续丢弃路由请求分 组。LAP_AODV协议仍然在扩展环搜索(expand 目的节点应用层接收到的数据分组总数与源 节点应用层发送的数据分组总数之比,反映了网络 传输的可靠性,分组投递率越大可靠性越高。 2)分组端到端平均传输延时 所有数据分组从源节点发出到目的节点正确 接收所用时间的平均值,反映了路由的有效性。 3)归一化路由开销 irng search)机制中通过路由请求分组的1]rL值进行 判断,当路由请求分组中的1] 值等于网络直径 (NET_DIAMETER)与路由请求转发次数 (NUM_FORWARDS)之差时,认为源节点和目的节 点之间仅有不可靠路由。 3.3预测式路由维护 LAP_AODV路由协议只维护那些正在使用的路 每发送一个数据分组所需要的路由分组数,其 中路由分组每一跳的传输均认为是一个新的路由 分组,反映了网络的拥塞程度和路由效率。 4.3性能分析 由,而不在激活路由上的节点的移动并不会影响该路 由。预测式路由维护实现了无线蜂窝网络中软切换 (Soft-Handoff)的思想,当节点检测到接收分组的能量 值低于危险阈值时,认为链路进入危险期,启动链路 连续可用时间预测过程,估算链路在将来一段时间内 的连续可用时间,若链路的连续可用时间低于警告时 间时,则认为链路即将中断,启动预先修复过程,在 图2显示了分组投递率与节点移动速度之间的 关系。随着节点最大移动速度从lm/s变化到20m/s 时,2种协议的分组投递率都在下降,但都保持在 85%以上,其中LAP_AODV协议的分组投递率更 高,超过AODV协议约3%~5%,在节点移动速度 为20m/s时,LAP_AODV协议的分组投递率达到 链路真正中断之前提前完成新旧路由切换过程。 4仿真分析 4.1仿真环境 90%以上,并且随着节点移动速度的增加, LAP AODV的分组投递率增加程度越明显,这是由 于LAPAODV协议增加了链路可用性预测模块,对 _仿真环境是带有CMU无线扩展的Ns2Il01,在 NS2环境下对改进前后的AODV协议进行了仿真。 网络中各节点问的链路状况进行预测,避免了频繁 的链路断裂,特别是在节点移动速度大,网络拓扑 变化剧烈的情况下,能快速适应拓扑的变化,选择 最稳定的路径进行路由,降低了分组丢失的概率。 在整个无线仿真环境中,50个节点随机地分布在 1 200m ̄1 200m的矩形区域内,每个节点使用相同 的无线收发设备,无线传输半径为250m,采用单 维普资讯 http://www.cqvip.com 通信学报 第29卷 降低了约0.06s,这是因为拓扑变化越快,链路中断 的可能性越大,LAP AODV协议通过对节点间链 路可用性的预测,能够有效地降低因大量的重路由 操作所带来的延时。 图5给出了移动速度为10m/s时分组端到端平 移动速度/(m・s ) 图2最大移动速度一分组投递率 均传输延时与节点停留时间之间的关系,随着停留 时间的增加,2种协议的延时都在减少,这是因为 停留时间越长,网络拓扑结构越稳定,重路由操作 减少,降低了延时;同时,因为预测式路由维护机 图3显示了移动速度为10m/s时分组投递率与 节点停留时间之间的关系。随着节点停留时间的增 加,网络拓扑趋于稳定,2种协议的分组投递率都 在增加。在节点停留时间为0s时,LAP_AODV协 议的分组投递率比AODV协议的高约3%,但是随 着停留时间越大,I,AP AODV和AODV 2种协议 的分组投递率没有太大的差别,这是因为节点移动 程度越低,网络拓扑越来越稳定时,节点间的链路 变化程度降低,当所有节点都静止不动时,节点间 链路可用性预测的作用降低。 停留时间/s 图3停留时间一分组投递率 图4描述了分组端到端平均传输延时和节点最 大移动速度之间的关系,随着节点移动速度的增 加,2种协议的延时都在增加,这是因为节点移动 程度大,网络拓扑结构变化越剧烈,导致更多的链 路中断和新旧路由切换;同时L ODV的延时要 明显低于AODV协议的延时,特别是在节点移动速 度大,网络拓扑结构变化越剧烈时,LAP_AODV协 议表现出更低的延时,在节点移动速度为20m/s时, 移动速率/(m・s ) 图4最大移动速度.分组端到端平均传输延时 制使得LAP_AODV协议的延时要低于AODV的延 时,然而在网络拓扑较稳定的情况下,LAP_AODV 的延时没有太大提高,如在600s时,只提高了约 0.004s,这是因为拓扑越稳定,链路可用性预测的 作用越不明显。 s,茁艘簿 露 释南释囊 O O O O O 停留时间/s 图5停留时间一分组端到端平均传输延时 图6给出了归一化路由开销和节点最大移动速 度之间的关系。随着节点移动速度的增加,拓扑变 化越剧烈,重路由和新旧路由切换的次数增加,导 致更大的路由开销。LAP_AODV协议增加路由危 险警告消息完成预先式路由维护操作,这必然在一 定程度上增加了协议的开销,但是增加的程度不是 很明显。同时,也有可能由于不能发现可靠路由而 导致路由请求的多次重传,增加了路由请求洪泛的 路由开销,特别是节点密度较小或节点的移动程度 较高时。如图5中,节点移动速度为20m/s时, LAP AODV协议的开销比AODV的提高了5%, 但对于应用来说完全是可以接受的。 褪 丑 渣 1 移动速度 m ) 图6屉大移动速度一归一化路由开销 维普资讯 http://www.cqvip.com

第7期 洪利等:基于链路可用性预测的AODV路由协议研究 : 望: 图7给出了移动速度为10m/s时路由开销和节 点停留时间之间的关系,随着停留时间的增加,2 种协议的路由开销都在降低,并且降低的幅度比较 明显,这是因为节点移动程度越低,节点间的链路 状态变化程度越低,减少了重路由和新旧路由切换 次数;同时,停留时间较小时,LAP_AODV的路 [4】SU W,GERLA M.IPv6 flow handoff in Ad—hoe wireless networks using mobility prediction[A].Proc IEEE GLOBECOM[C].Rio DeJa— neiro,Brazil,1999.271—275. [5】 年梅,王能.通过链路实效预测机制提高AODV协议的性能[J】.计 算机应用,2005,25(6):1251—1256. NIANM,WANGN EnhancingAODVperformancebylinkbreakage prediction mechanism[J].Computer Applications,2005 25(6): 1251.1256. 由开销比AODV的要高,但随着停留时间的增加, LAP AODV和AODV之间的路由开销相差不是很 明显,在停留时间为0s时,LAP—AODV的开销仅 [6】JIANG S M.An e ̄anced prediction—based link availability estimation orf MANET[J].IEEE Transactions on Communications,2004,52(2): 比AODV的约提高了约3%,但这在应用中也是完 全可以接受的。 据 丑 瀣  :1 善 停留时间/S 图7停留时间,归一化路由开销 5结束语 高度动态变化的拓扑结构制约着Ad hoc网络 路由协议的性能,如何提高路由协议的稳定性显得 尤为重要。本文提出一种基于链路可用性预测的 AODV路由协议,通过对节点间链路的可用性的预 测,尽量降低拓扑结构动态变化对路由协议性能的 影响。仿真结果表明,基于链路可用性预测的 AODV协议能够避免频繁的链路中断,从而减少重 路由操作的次数,提高数据分组的投递率,降低分 组端到端平均出传输延时,提高了网络的性能,但 在一定程度上增加了归一化路由开销。本文将进一 步研究不同应用环境下节点的不同移动规律,建立 针对具体应用环境的节点移动的数学模型,以降低 预测算法的复杂性,提高预测的精确度。 参考文献: [1】 PERKINS C E,MROYER E.DAS S.Ad,hoe On,Demand Distance Vector(AODV)Routing[S].RFC 3561,2003. [2】TOH C K.Assoeiativity—based routing for Ad—hoe networks[J】.Wire, less Personal Communications Journal,1997,4(2):103—139. [3】 PAUL K,BANDYOPADHYAY S,MUKHERJEE A.et a1.Communi, cation aware mobile hosts in Ad,hoe wireless networks 】.Personal Wireless Communication。IEEE ICPWC’99[C1.1999.83,87. 183—186. [7】JIANG S M,HE D J,RAO J Q.A prediction—based link availability estimation for routing me ̄cs in MANET[J].IEEE/ACM Transactions on Networking,2005,13(6):1302—1311. [8】RAPPAPORT T S.Wierless Communications:Principles nad Practices [M】.第2版.北京:电子工业出版社(影印版),2004.105—139. RAPPAPORT T S.Wireless Communications:Principles and Prac— itces[M].Second Edition,Beijing:Eelectronics Industry Press,2004. 105—139. [9】 B肿STETTER C,HARTENSTEIN H,PEREZ—C0STA X.Steohas- tic properties of the random waypoint mobility model[J]. ACM/Kluwer Wireless Networks,2004,1O(5):555・567. [10】The network simulator-ns一2[EB/OL].ht【p://www.isi.edu/nsnam/ns. November 2006. 作者简介: 洪利(1969.),男,江西赣州人,博 士,中国石油大学(华东)计算机与通信 工程学院副教授,主要研究方向为无线通 信、无线通信传感器网络、下一代网络等。 黄庭培(1980.),女,土家族,湖北建始人,硕士, 滁州学院助教,主要研究方向为无线自组网。 邹卫霞(1972.),女,博士,山西运城人,主要研究 方向为无线通信、超宽带(UWB)、认知无线电等。 李树荣(1966.),男,山东诸城人,博士,中国石油 大学(华东)教授、博士生导师,主要研究方向为控制理论 与控制工程,信息处理等。 周正(1945一),男,上海人,北京邮电大学教授、博 士生导师,主要研究方向为短距离无线通信、超宽带无线通 信、智能信号处理及通信网络优化等。 

因篇幅问题不能全部显示,请点此查看更多更全内容

Copyright © 2019- howto234.com 版权所有 湘ICP备2022005869号-3

违法及侵权请联系:TEL:199 1889 7713 E-MAIL:2724546146@qq.com

本站由北京市万商天勤律师事务所王兴未律师提供法律服务