第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
本站由北京市万商天勤律师事务所王兴未律师提供法律服务