基于空间位置和场景的AdHoc路由协议.pdf

《基于空间位置和场景的AdHoc路由协议.pdf》由会员分享，可在线阅读，更多相关《基于空间位置和场景的AdHoc路由协议.pdf（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、27卷 第2期2010年2月微 电 子 学 与 计 算 机MICROELECTRONICS&COMPUTERVol.27No.2February 2010收稿日期:2008-12-08;修回日期:2009-02-25基金项目:浙江省自然科学基金(Y1080734)基于空间位置和场景的Ad Hoc路由协议朱本浩1,姚明海2(1浙江海洋学院 数理与信息学院,浙江 舟山316004;2浙江工业大学 信息工程学院,浙江 杭州310014)摘 要:在移动Ad Hoc网络中,基于拓扑的路由易发生链路断开,基于地理位置的路由易产生拓扑洞,这都会大大降质路由算法的性能,甚至会出现路由失败的问题.为此文中提出了

2、基于空间位置和场景的Ad Hoc路由协议.该协议算法采用构建空间模型,将场景知识引入路由过程的方法,通过在路由前规避拓扑洞来改善和提高路由性能.仿真结果表明在网络连通度适当的条件下,新的路由协议算法可行和有效的.关键词:空间位置;拓扑洞;Ad Hoc路由协议;SSR协议中图分类号:TP393 文献标识码:A 文章编号:1000-7180(2010)02-0163-04Ad Hoc Routing Protocol Based on the spatial Location and SceneZHU Ben2hao1,YAO Ming2hai2(1 College of Mathematics

3、Physics and Information,Zhejiang Ocean University,Zhoushan 316000,China;2 College of Information Engineering,Zhejiang University of Technology,Hangzhou 310014,China)Abstract:In the mobile Ad Hoc network,the link which governed by the routing protocol based on topology disconnectedeasily,and topology

4、 holes easily happened in the link which governed by the routing protocol based on geographical loca2tion.These two type routing protocol significantly degrade the performance of routing algorithm,even lead to routing fail2ure problems.In this paper,the routing protocol based on spatial location and

5、 scenes has been presented.Through con2structing spatial model which introduce the scenes knowledge in routing process and bypassing the topology holes beforerouting,the routing performance are improved.The simulation results show that the new routing protocol can effectivelyimprove the performance

6、of routing in the proper conditions of network connectivity.Key words:spatial location;Topology hole;Ad Hoc routing protocol;SSR protocol1 引言移动Ad Hoc1是一种不依赖于固定基础设施的无线网络,网络节点之间通过协作来传输信息.节点可以向任意方向自由移动,网络拓扑变化频繁且事先无法预知,如何发现和维持路由,以达到更好的路由效率是目前研究的热点问题.传统的Ad Hoc路由协议主要是基于网络拓扑和基于地理位置的,这些协议建立的路由是由一系列特定的中间转发节点

7、组成.如网络拓扑结构剧烈变化或路径上存有障碍物时,路由就会因有节点不可达,出现我们称作拓扑洞(Topology Hole)的情况,造成通信中断,需重建或恢复路由,这会导致高额的路由开销.在存在拓扑洞的情况下,基于网络拓扑或者地理位置的路由算法会失效,并且由于路由算法的无状态性,这种失效在环境未发生重大变化时会重复发生,从而大大降质路由算法的性能.文中提出一种基于空间位置和场景的Ad Hoc路由协议,构建空间模型,将场景知识引入路由过程,在路由过程前规避拓扑洞,改善和提高路由算法的性能.2 传统路由协议的缺陷基于拓扑的路由协议利用网络中的链路信息来进行包的转发,比较典型的有动态源路由DSR2协议

8、.该协议按需使用泛洪来探测路由,当所用的路由发生链路断开时,而缓存中没有到目的节点的其它路由时,源节点只能再次通过泛洪来寻找到目的节点的路由.这样会导致经常性的全网络泛洪,不仅占用了大量的网络带宽,而且还容易引起控制包和数据包之间的冲突.基于位置的路由协议根据节点的位置信息来选择下一跳,将包朝着目的节点的方向上进行转发.典型的有GPSR3协议,这种协议算法需要知道网络中节点的地理位置信息,每个节点可以通过GPS或其它定位服务来知道自己的位置.由于基于地理位置的路由是基于局部信息做出转发决定,没有必要产生和维护从发送节点到目的节点的全局信息,因此通常认为这种路由算法具有高度的扩展性,对于经常变化

9、的拓扑具有较好的鲁棒性.但如果网络拓扑变化过于剧烈,在报文未到达目的节点时,目的节点因位置发生变化而与前面的节点形成路径环.由于初始面并不会再次到达,GPSR无法判断路径环的发生,从而报文将在路径环间反复传递直到达到最大hop数,导致路由过程失败.路径上有障碍物存在时影响也非常明显,它会增加路由算法的开销,导致网络拓扑信息及时更新更加困难.当算法使用“过期”的信息时,基于地理位置的Ad Hoc路由算法就可能出现路由失败.由以上分析可以看出,新的路由协议要求不应基于网络拓扑和地理位置,必须能有效地规避拓扑洞.文中引入空间模型的概念,一方面空间模型的静态性避免了动态更新网络拓扑的巨大开销,另一方面

10、利用空间模型与网络拓扑的近似性能有效地规避拓扑洞的产生.3 基于空间位置和场景的路由协议3.1 空间模型的构建空间模型是对存储在电子地图里原始数据的一种封装,为高层应用提供有效的数据处理4.电子地图、空间模型与路由协议之间的关系如图1所示.图1 电子地图、空间模型与路由协议之间关系图空间模型可以通过电子交通图等地理信息系统(GIS)提取数据的方式构建.解释器自动将GIS数据转换成标准的地理数据格式存储.空间模型图可作为网络拓扑的一个近似描述.当网络节点密度足够大时,空间模型图与平面化的网络拓扑是一致的.因此,可以利用空间模型图来选择适当的路由,规避因轨道因素引发的拓扑洞.为了更好的描述空间模型

11、,在基于空间位置和场景的Ad Hoc路由协议(Spatially situation andscenes Routing,SSR)中,引入图距离的概念.以静态的空间模型图模拟动态的网络拓扑,以图距离代替欧几里德距离,这构成了SSR协议的基本思路.完整的SSR协议包括邻节点检测、GSR规划和基于GSR的报文前传三个基本操作.3.2SSR路由协议邻节点检测主要是提供节点邻域知识,为后续的报文前传提供必要的支持.与GPSR协议一样,SSR协议的邻节点检测机制也采用beacon方式.每个节点周期地向MAC广播地址发送beacon.beacon中携带着发送节点的网络ID以及当前坐标位置.为了避免同一时刻

12、发送的beacon引起碰撞,beacon的发送间隔以0.5B的大小抖动,当节点的传感器接收到其它节点的bea2con时,即意味自身处于beacon发送节点的通信范围内.对邻节点列表中的每个节点,如果在一定时间范围内没有收到来自该节点的beacon,则认为到该节点的直接链路失效,从而将该节点从邻节点列表中去除.SSR是一个基于源路径的路由协议.SSR中使用的源路径称作GSR.GSR基于已经建立的空间模型,由一系列空间定位点构成.这些空间定位点指定了从源节点到目的节点路径的大致形状.一般空间模型图是连通的,即图中任意两点间至少存在一条路径.空间模型图的每条边被赋予了一定的权函数.权函数是应用相关的

13、,它可以是节点之间的图距离,最短经历时间,或者期望经历时间等.GSR嵌入在数据报文的报头中随着数据报文一起发送,每一个定位点以坐标形式存入报头.由于报头的存储空间有限,SSR协议提供了限制GSR长度的机制.限制GSR长度的机制有两种:(1)删节GSR中定位点序列以适应报头存储空间的大小;(2)缩短GSR中定位点序列,产生新的定位点序列仍可指示路径的大致形状.生成的GSR指定了报文前传路径的大致形状,461微电子学与计算机2010年报文沿着定位点指定的方向传输.当某一节点接收到数据报文时,首先检查自身与当前激活的定位点之间的图距离.如果该距离大于预设的阈值,则接收节点将从邻节点列表中选择合适的节

14、点作为下一跳的目的节点.如果接收节点与当前激活的定位点之间的图距离小于阈值,接收节点将标记当前激活的定位点不再有效,而激活下一个定位点,向新的定位点前传报文.上述过程被重复执行直至到达目的节点附近.传统的Ad Hoc路由协议总是试图避免路径环的出现,以防止出现报文在网络的部分节点中反复传递而使得传输失败或者严重降质,必须使用附加机制来避免.而在SSR协议中,没有去刻意避免路径环的出现.由于SSR协议中报文将被前传给图距离更接近于下一个定位点的邻节点,这种确定性的报文前传方式防止了报文在部分网络节点间无休止传递的现象的发生.4 仿真实验为评价SSR的算法性能,文中采用带CMU无线扩展的Ns-2仿

15、真器进行了仿真实验.仿真中比较了SSR、DSR和GPSR的性能差异.仿真中对每个通信半径均使用了6个随机产生的运动模型,生成三种协议在该环境下的仿真结果,最后得到的结果是对这6次仿真结果的平均.下面分别是报文传输率、报文传输时延、报文平均前传次数与节点通信半径之间的关系图,相关的参数表如表1所示.表1SSR协议仿真参数表参数值仿真时间900s节点数目100场景大小2500m1000m通信半径50250m节点移动速度3060km/h节点停留时间1030s业务类型CBR业务流量2Kbps报文大小64byte连接数20图2所示,当通信半径小于100m时,DSR协议的报文传输率与GPSR协议相当;而当

16、通信半径进一步增大时,DSR协议要高出GPSR协议约15%.SSR协议则要高出GPSR协议40%以上,高出DSR协议30%以上.这表明SSR协议可以规避拓扑洞的特点得以显现出来,能有效地提高和改善路由性能.图2 报文传输率与节点通信半径关系图图3所示,在所有场景中SSR协议的传输时延显著低于GPSR协议.这是因为GPSR协议的主要思想是节点从其邻节点集中选择距网关节点最近的节点作为下一跳节点;遇到拓扑洞,则采用周边转发模式进行迂回选路.而SSR协议能够提前规避拓扑洞,当前传报文失败时,SSR协议选择丢弃报文,降低了传输时延,提高了算法效率.图3 报文传输时延与节点通信半径关系图图4显示了3种协

17、议报文传输过程中的平均前传次数.DSR协议表现出相对较高的hop数,这是因为DSR路由请求采用洪泛方式,相邻节点路由请求消息会发生传播冲突并重复广播,数据报文频繁地经历缓存、前传过程,增加了每次成功传输的hop数.当通信半径小于150m时,SSR协议的平均前传次数与GPSR协议相比较少,而两者的报文传输率近似.这表明了在较低的节点密度下GPSR协议可以通过perimeter forwarding模式传输大部分报文,而SSR协议则通过规避拓扑洞的方式更直接地传输报文.561 第2期朱本浩,等:基于空间位置和场景的Ad Hoc路由协议图4 报文平均前传次数与节点通信半径关系图5 结束语文中分析了基

18、于拓扑和基于地理位置的路由协议在网络拓扑结构剧烈变化和有障碍物存在时易产生拓扑洞的缺陷,介绍了空间模型的构建及使用,提出了SSR路由协议的设计过程.仿真结果表明在网络连通度适当的条件下,SSR协议有效规避拓扑洞使得路由算法性能可以得到有效改善.但是,影响报文成功传输率的直接因素依然是Ad Hoc网络链路支持,由于SSR协议不能保证GSR上存在有效链路连接,这影响了SSR协议的传输质量.如何提高SSR协议的传输质量是下一步研究的方向.参考文献:1张国庆,慕德俊,许钟,等.一种高效的按需路由协议安全性改进方法J.微电子学与计算机,2008,25(5):138-142.2 Perkins C E,R

19、oyer E M.Ad-hoc on demand distancevector routingCProceedings of 2nd IEEE Workshop onMobile Computing Systems and Applications.New Or2leans:IEEE Computer Society,1999:90-100.3 Karp B,Kung H T.Greedy perimeter stateless routing forwireless networksCProceedings of ACM-IEEE Mobi2Com00.USA:Boston,MA:ACM/

20、IEEE,2000:243-254.4 Jing Tian,Han L,Rothermel K,et al.S patially awarepacket routing for mobile Ad Hoc inter-vehicle radio net2worksCProceedings of the IEE 6th Intl Conf.Shang2hai:Intelligent Transportation Systems,IEEE,2003:12-15.作者简介:朱本浩 男,(1974-),硕士,讲师.研究方向为ad hoc网络、路由算法.姚明海 男,(1963-),博士,教授.研究方向为

21、计算机控制技术、计算机网络等.(上接第162页)2蔡兴国,初壮.用遗传算法解算机组组合的研究J.电网技术,2003,27(7):36-39.3王宜怀.小型水轮发电机组优化运行系统的设计与实现J.微电子学与计算机,2003,20(8):99-103.4 Storn R,Price K.Differential evolution a simple and effi2cient heuristic for global optimization over continuous spacesJ.Journal of Global Optimization,1997,11(4):359-431.5 K

22、ennedyJ,Eberhart R.Particle swarm optimizationC/Proceedings ofIEEE Conference On Neural Networks.Perth,Australia,1995:1942-1948.6 Yin P Y.Genetic particle swarm optimization for polygonalapproximation of digital curvesJ.Pattern recognition andimage analysis,2006,16(2):223-233.作者简介:赵 昕 男,(1965-),工程师.研究方向为系统集成与优化计算.李 剑 男,博士,讲师.研究方向为智能计算与电力市场.661微电子学与计算机2010年