基于地理定位信息的移动自组网路由协议综述

张鹏明,李洪烈,林成浴

(海军航空工程学院青岛分院,山东 青岛 266041)

1 引 言

20世纪七八十年代提出的Ad Hoc[1]网络最开始主要用于军事目的,其出发点是在无基础设施的战场环境下迅速构建通信网络。Ad Hoc网络没有中心节点,任何节点均可自由移动、进出网络,同时每个节点还具有路由功能,中继转发数据至目的节点。

由于无中心、任何节点均可自由移动,因此Ad Hoc网络具有较强的抗毁性、拓扑动态变化、可多跳覆盖等特点,故一经提出,立即成为军事和民用研究的热点。近年来,民用方面Ad Hoc网络的研究主要集中在民航[2]、智能交通系统[3]和传感器网络[4]等方向,军事方面则主要集中在移动自组网[5]、传感器网络[6]等方向。

移动自组网(Mobile Ad Hoc Network,MANET)是一种典型的Ad Hoc网络,由一些移动的无线节点组成无线通信网络,可广泛用于军事通信、抗灾救灾等场合。由于移动自组网节点的移动特性会使网络拓扑频繁变化,导致已有的路由经常失效,因此路由协议的设计和选取是关键。目前,对移动自组网的研究热点主要集中在路由协议上,本文将对此进行综述。

2 移动自组网路由协议

2.1 移动自组网路由协议的基本设计

由于移动自组网的动态特性,尤其是应用在运输和航空等高动态场合,其对路由协议的要求更加严格,所以必须设计新的路由算法。路由算法的基本设计原则通常是下列原则的一个或多个。

(1)优化

优化指路由算法选择最佳路径的能力,根据设计的metric值来计算。移动自组网由众多自由、移动的节点组成,要求具有优化的算法。

(2)快速收敛

收敛是指网络中的所有节点对最佳路径达成一致的过程。移动自组网的节点可自由出入网络,而且节点自由移动,由此带来路由途径的不断更新,所以要求路由算法必须具有快速收敛的能力;否则,会使网络产生路由环或瘫痪。

(3)有效地控制开销

控制开销是指建立路由和传输数据的管理负载。移动自组网的无线传输带宽有限,控制开销分组不可避免地要消耗掉一部分带宽资源,同时过大的控制开销也会消耗网络传输数据的能力,因此必须尽可能地减小控制开销。

(4)健壮 、稳定

健壮、稳定是指路由算法在出现不正常或不可预见事件的情况下仍能正常工作。移动自组网工作在无线移动模式,信道情况比较复杂,出现突发事件的概率比较大,对路由算法的健壮、稳定要求更加迫切。

(5)灵活

路由算法必须迅速、准确地适应各种网络环境。移动自组网的网络环境可能随时在变,进出网络的各自由节点的情况也不一定完全一致。因此,路由算法的设计必须灵活,能够自动适应诸如带宽、延迟等不一致的情况。

良好的路由协议能够以较低的计算负担、网络控制开销、通信负载、能量消耗、通信时延获得路由信息,因此设计路由协议时也往往从这几方面着手,目前对移动自组网路由算法的设计思路主要有修改现有的常规路由协议以适应不同的应用环境、采用按需的原则设计路由或基于QoS(Quality of Service)设计路由3种。

2.2 移动自组网的路由协议分类

目前已经提出的移动自组网的路由协议种类繁多,划分的标准也不尽相同,通常有以下两种:按照网络的逻辑结构,可分为平面路由和分层路由;按照设计路由时所选取的信息类型,可分为基于拓扑结构的路由协议和基于地理定位信息的路由协议。在此仅按后者进行分类。

(1)基于拓扑结构的路由协议

基于拓扑结构的路由协议其路由选取的信息是基于网络节点之间的拓扑链接,按照发现路由的方式不同,又可分为主动型、按需路由型和混合型3种。

主动型路由协议要求网络中的每个节点都维护一张到其他节点的相对稳定的最新路由表,路由表由网络周期性地广播路由控制数据进行更新,路由表在节点通信之前就已经建立。因此,主动型路由协议在发送数据时,只要目的节点存在于路由表中,查找建立路由所需的时延就很小。但是,随着网络规模的扩大,路由表的信息急剧增加,同时由于主动型路由协议需要周期性地更新路由信息来维护路由表,由此带来网络的控制开销太大,动态变化的网络拓扑更可能使花费较高代价得到的路由信息变成无用信息,从而使路由协议始终处于不收敛状态,因此,该类协议不大适合于移动自组网,一般用在实时和有QoS要求的网络通信。目前,典型的主动型路由协议有DSDV、OLSR等。

按需路由型协议只有在网络节点需要发送数据时才开始路由查找,经查找建立路由后,由路由维护程序维护路由,直到数据传输完毕,任务完成后才拆除路由。如果传输数据过程中发生路由中断,则重新开始路由查找。由于只在有数据发送需求时才广播控制数据,网络的控制开销大大减少,节省了一定的网络资源。按需路由协议具有路由发现和动态维护路由的功能,因此能够满足网络的一般动态要求。但是,由于采用的是源驱动的路由机制,发送数据分组时,必须先开始路由查找,再建立路由,会造成一定的时延。在路由查找过程中通常采用全网泛洪方式进行搜索,在一定程度上减弱了其优点。目前,典型的按需型路由协议有AODV、DSR等。

混合型路由协议汲取主动型路由协议和按需型路由协议的优点,利用分层路由协议将网络划分为两层,即内层网络节点维护路由表和外层网络节点采用按需路由协议。在路由维护阶段更新内层网络维护的路由表。该类协议能较好地利用上述两种路由协议的优点,但是节点的计算负载较大,由此带来网络的整体能耗较高,如何开发更好的混合型路由协议以适应大规模移动自组织网络的需求将是以后研究的一个重点。目前,典型的混合型路由协议有ZRP、CEDAR 等。

(2)基于地理定位信息的路由协议

与基于拓扑结构的路由协议不同,基于地理定位信息的路由协议其路由选取是基于地理定位坐标的。这种类型的路由协议更适合移动自组网的高动态要求。

基于地理定位信息的路由协议要求网络中每个节点维护并周期性地更新一张位置信息表,表中包含所有邻居节点的地理定位信息。当节点运动时,发送捎带自身新位置的控制信息到所有邻居节点,邻居节点据此更新自己的位置信息表。由于建立位置信息表的信息量比建立链路查找表要小得多,所以可以有效地减少网络的控制开销。同时,基于地理定位信息的路由协议没有普通路由协议所存在的收敛问题,因此比较适合高动态的通信网络。

3 基于地理定位信息的移动自组网路由协议

目前,典型的基于地理定位信息的移动自组网路由协议有以下几种。

3.1 LAR

LAR(Location Aided Routing)[7]协议是基于DSR(Dynamic Source Routing)路由协议的一种按需路由协议,其主要特点是在所有数据包中均发送地理定位信息,从而有效地利用节点的地理位置信息来减少路由发现过程的网络控制开销。LAR假定网络中的节点知道自身的地理定位信息并且已经获得了目的节点的地理定位信息。基于以上两点,LAR协议将目标节点的查找范围限制为网络中的某一部分区域,即请求区域(Request Zone)。只有在请求区域内的节点才允许转发RREQ消息。即:当路由中间节点收到RREQ包时,该节点首先检查它是否属于该RREQ消息所定义的请求区域,如果属于,判断自身是否是目的节点,是目的节点则返回RREP包,包中含有此刻的时间信息和该节点的地理定位信息,不是则转发该RREQ包;如果不在请求区域内,则丢弃该RREQ包。如果RREQ包中设定的时间用完而该包仍未被送达目的节点,则转发该RREQ包的最后节点向源节点发送RERR包,通知源节点此次路由查找失败,由源节点再次发起路由查找。

LAR协议判断节点是否在请求区域内有两种策略:区域策略和距离策略。区域策略假定源节点 S已经知道了目的节点D在t0时刻的地理定位信息、平均移动速度v,从而可以算出在 t1时刻目标节点D所在的期望区域是以D在上一时刻t0所在的方位为圆心、v(t1-t0)为半径的圆形区域。在路由查找过程,只有在请求区域内的节点才参与路由查找,转发RREQ消息;距离策略根据中间节点和目的节点的距离作为是否转发RREQ消息的判决依据。在路由查找阶段,假设中间节点i判定自己属于请求区域,到目的节点D的距离为Disti,转发RREQ的上一节点 S到目的节点D的距离为Dists,只有满足α Dists+β≥Disti时中间节点i才转发该RREQ包(α、β为待定参数)。

综上所述,LAR协议由于将路由查找限制在请求区中,因而相对于普通泛洪路由具有路由查找快、控制开销小的特点,由于其只提出策略,并不限于某一确定的协议,因而适用范围广。但是必须要有额外获取地理定位信息的设备予以支持,而且以上两种策略都只是源节点对目的节点期望区域的估计。实际上,目标节点可能由于运动情况突变,并不在期望区域内,源节点也有可能一开始并未获得目的节点的地理定位信息,这两种情况均会造成源节点初次路由查找失败,从而迫使源节点采用泛洪的方式在整个网络中进行路由查找。泛洪方式会极大地增加网络开销,降低网络效率。因此,尽可能多地获得目的节点的移动信息,合理有效地设置请求区域、选择最佳位置和数量的路由节点是LAR协议的关键所在。

目前,对LAR协议的研究主要集中在优化请求区域、有效选取参与路由的中间节点这两个方向,其本质都是通过减少参与路由的中间节点、提高路由相对稳定性进而提高效率。常采用的有基于概率特性、基于跳数、基于距离、基于位置、基于簇等改进方式。

牟强等人[8]提出了一种IM-LAR算法,通过在RREP包中将地理定位信息根据回送节点的信息进行调整,从而扩大了路由选择的区域,仿真表明该算法能有效地改进LAR协议因为请求区域设置过小而漏选最佳路由的缺陷,从而减少路由查找阶段RREQ包的转发次数,但同时该算法也会增大路由请求泛洪方式发生的概率。Hung[9]等提出了一种基于节点运动方向预测的DLAR协议,选择与源节点运动方向一致或相似性最好的节点作为路由节点,以提高路由相对稳定性。Nabendu Chaki[10]采用Dijkstra算法寻找最短路由路径,在中间节点找不到下一跳邻居节点时,增加该节点不在请求区域内的邻居节点以建立新的路由,从而提高了路由的相对稳定性。Neelesh Gupta[11]等则从节省能量的角度引入GAF(Geographic Adaptive Fidelity)算法改进了LAR协议。

引进概率算法是改进LAR协议的另一种常用方式。由于LAR协议采用区域策略时,在节点密度较高的区域常常会有大量多余的节点进行转发,因而降低了网络的可达性。基于概率的算法通过设置自适应转发概率的机制可以有效地减少节点密度高的区域的转发节点数量,而且并不影响网络的可达性。其基本原理是:当节点收到RREQ包时,先判断该包是否以前转发过,若已经转发过,则丢弃该包;若没有,则以概率Pt来转发该包,每个节点最多只允许转发该包一次。源节点是RREQ包的发出者,Pt通常设为1;中间节点Pt通常取0到1之间的某一个固定值,也可以通过概率分布函数来动态地选取。

基于概率的算法最早由Haas[12]等人提出,该算法在路由查找阶段选取固定的概率 Pt来决定节点是否转发RREQ包。不久Haas等人又提出在连续使用Pt<1之前将前h跳节点的Pt设为1,结果表明该协议能较普通泛洪协议减少35%的负载。H.Al-Bahadili等人将LAR协议的区域策略和基于概率的算法相结合,构成一种适用于移动自组网的路由新算法LAR-1P,仿真表明该算法可以在不影响网络可达性的情况下减少请求区域中的转发节点数量。随后他们[13]对该协议的详细性能进行了分析,证明了LAR-1P协议在节点密度高的区域确实能有效减少转发的节点数量,而在节点密度低的区域则和LAR区域策略的性能相似。

基于概率特性、基于跳数、基于距离、基于位置、基于簇等改进方式的实质都是在与如何选择参与路由的中间节点,中间节点选得过多,则会造成较大的网络负担;选得过少,又容易迫使路由进入泛洪方式,从而降低效率。目前研究方向主要集中在基于距离、基于位置和基于概率特性这3种方式。如何合理选取参与路由的中间节点仍将是LAR协议今后研究的重点。

3.2 RDMAR

相对距离微观发现路由(Relative Distance Microdiscovery Ad Hoc Routing Protocol,RDMAR)协议是由George Aggelou[14]等人提出的一种按需路由协议,其核心思想是在两个节点之间进行路由查找时,采用迭代算法根据平均节点移动速度和节点的路由信息距离上一次更新的时间估计两者之间的当前相对距离(Relative Distance,RD),由此限制那些在源节点为圆心、RD为最大半径的圆内节点才可转发 RREQ包,从而比普通泛洪协议减少了转发RREQ包的节点数量,从而减小了路由负载和拥塞的可能。

按照该协议,每个节点维护一张包含该节点所有可达目的节点的路由表,每个可达目的节点的路由信息包括:当前节点所能到达的目的节点的下一跳节点的路由区域、当前节点与目的节点的相对距离的估计值(跳数)、当前节点关于目的节点路由信息的上一次更新时间(Time-Last-Update,TLU)、当前节点到目的节点有效路由的剩余时间、当前节点到目的节点路由是否有效的标志这5项内容。协议由路由查找和路由维护两部分组成。

(1)路由查找

当网络中某一节点需要查找到目的节点的路由却没有有效路由时,该节点根据路由表内上一次到目的节点的距离、路由表上一次更新的时间、目的节点的平均移动速度,计算出当前时刻该节点与目的节点的相对距离,由相对距离得出TTL(Time to Live)值,从而将转发RREQ文件的节点限制在以自己为圆心、半径为与相对距离有关的RDM-Radius的圆形范围内。当RDM-Radius为全网络尺寸时,等同泛洪查找。RREQ包在查找区域内逐跳转发,每个收到RREQ的节点在自己的路由表内建立一条到RREQ源节点的反向路径,并在RREQ包中添加本节点的路由信息,设置下一跳信息,继续转发RREQ包,直至RREQ包到达目的节点。

只有当RREQ包到达目的节点后,目的节点才产生应答RREP包。路由查找过程中的任何中间节点都不能产生RREP包,由此可以保证RDMAR协议的路由信息不会过时,同时也减小了网络开销。RREP文件沿各个节点记录的到源节点的反向路径回传至发起路由查找节点,RREP中携带发起路由查找的节点到目的节点的路由信息。中间节点在转发RREP包至路由查找发起节点的同时,也将RREP包发给那些曾转发RREQ包到目的节点却未收到应答的节点。

在路由建立过程中,如果某一节点发现到目的节点的新路由,该节点将自己路由表中的已有路由信息的RD值与新路由比较,若新路由RD值的跳数比原来的小,则将新路由更新到自己的路由表中,如果原先路由表中没有到目的节点的路由,则自动将该路由添加到自己的路由表中。

(2)路由维护

中间节点收到数据包时,按照路由头文件将该数据包转发到下一跳。如果中间节点发现没有前往目的节点的有效路由或是收到RERR包,则按照设定的最大次数重发该数据包,因为路由失效往往可能是由突发噪声、节点进入无线信号衰落区域等暂时因素造成的。如果重传达到最大次数,则该中间节点判断自己与源节点和目的节点之间的距离,若距目的节点近,则该节点自己发起相对微观距离查找,否则通知源节点路由断开,由源节点重新发起路由查找。

RDMAR协议的路由维护可以选择局部修复,因而较其他路由协议可以减小控制开销、降低时延,而且路由查找也限制在请求区内,路由查找速度快,不需要周期性的广播分组,可以有效节省带宽资源。但当节点的运动速度超过源节点的记录速度时,会造成初次查找失败,从而扩大查找范围,增加了初始路由的时延和网络开销。但RDMAR协议不需要额外的GPS设备的支持,在一些特定条件下(如极端战场环境下)会具有更广的使用价值。

RDMAR协议的性能依赖于路由查找算法的成功率,因此对其进行优化改进比较困难。Omar F Hamad[15]等人提出一种分簇的思想,将微观相对距离搜索区域通过算法进一步分成若干区域,但是这种协议只适合学校或运动场等区域特性较强的地方。Nadeem Akhtar[16]等人提出一种多径路由的思想来增加RDMAR协议的健壮性,仿真表明,改进后的协议能提升实时和非实时的数据传输性能。

3.3 GeoCast

地理定位信息寻址路由协议(Geographic Addressing and Routing Protocol,GeoCast)是Julio C.Navas等人[17]提出的一种将信息送到某一地理区域的部分或全部节点的路由协议,它是多播路由协议的一个子集,可以通过将某一特定地理区域定义为多播群组而实现多播功能,具有分级的结构。

实现地理定位信息寻址路由协议的系统由GeoHosts、GeoNodes、GeoRouter3部分组件构成 。GeoRouter(Geographic Routers)负责地理定位信息的路由传送。GeoNodes是地理定位信息寻址路由系统的出入点,负责将接收到的地理定位信息转发给自己的邻居节点。GeoHost负责地理定位信息的发送与接收,告知地理定位信息的有效性、当前节点的地理位置、当前GeoNode的地址。

在地理定位信息寻址路由协议中,地理定位信息在协议中的作用与IP地址在TCP/IP协议中的作用相似,主要目的是把网络协议和地理位置相结合,方便提供一些与地理位置相关的网络服务。地理信息寻址路由协议将地理位置信息引入节点地址和路由,在有效地理区域内提供群组通信,因此可实现组播功能。其具有一定层次和结构,网络扩展性好,但是要求路由节点位置比较固定,其余节点可以是移动的,因而适用范围又受到一定的限制。

关于GeoCast研究的论文较多借鉴了单播路由协议的思想。GeoCast协议的研究目前主要集中在城市智能交通系统中的应用,关于多播信号的跨地理区域连续传播是该协议研究的一个热点。Zhu[18]等人针对现有的地理定位信息寻址路由协议很少能支持不同地理区域间的操作,提出了基于地理定位信息辅助和基于簇拓扑结构的GMIDR(Geo-Assisted Multicast Inter-Domain Routing)协议。该协议能在保持高效路由的同时,实现不同地理区域间的可靠多播路由。Yoh Shiraishi[19]等人则针对移动自组网中节点可能移动到多播区域外造成多播数据不能持续传输的问题,提出了一种将Geocast和GPSR(Greedy Perimeter Stateless Routing)两者相结合的模式,通过该模式可以实现多播信息的不间断传递。Ting Wang[20]等人提出了“摆渡(Ferry)”方案,通过地理定位信息选择出网络中特定区域的部分节点作为“渡船”,帮助传递多播信息,从而解决了多播信息连续传递的问题。

3.4 DREAM

移动距离效应路由(Distance Routing Effect Algorithm for Mobility,DREAM)协议是 Basagni等人[21]提出的一种基于距离效应和地理定位信息的路由协议。所谓距离效应是指两个节点间的距离越远,它们之间的相对运动看起来就越慢。

DREAM协议具有按需型路由协议的工作方式。在协议中,每个节点维护包含网络中其他节点地理定位信息的路由表(地理定位信息可由GPS等定位设备得到)。当网络中某个节点(源节点)需要传递信息到目的节点时,源节点根据自己路由表中目的节点的地理定位信息解算出目的节点的方向,然后将数据传往自己在目的节点方向的一跳邻居节点,所有邻居节点继续采用相同的方式传递数据到自己的下一跳邻居节点,直至信息传递至目的节点。

该协议的关键在于找到目的节点的方向,而目的节点的方向取决于地理定位信息在网络中的传播方式。在DREAM协议中,每个节点是根据当前自身相对于其他节点的位置来传递控制信息的。其依据可以是以下两点。

(1)控制信息更新频率

根据距离效应,两个节点相隔的距离越远,其相对运动看起来更慢,因此两个节点相互地理定位信息的更新频率比那些相对距离近的节点低。可以根据源节点发送的信息传送距离的远近来设定一个控制信息的“年龄”,更新频率可以据此设定。

(2)节点运动速率

节点运动越快,需要广播自己地理定位信息的频率就越高。因此,每个节点可以根据自身运动速率来有效地选择自身控制信息的更新频率。

由于DREAM协议选取距离和运动速率作为度量值,在网络中不存在大量控制信息的交换,也不存在按需路由协议的延迟,所以具有高效、节省带宽、无环、高健壮性、适合移动网络的优点。但是,由于节点的地理定位信息需要在全网络传递,因此,当网络规模达到一定程度或网络内节点的运动速度较快时,控制开销会显著增加,故该协议的扩展性不强,因此目前对DREAM协议的研究相对较少。Hu等人[22]将DREAM协议与边界传输算法相结合,提出了一种应用于水下声学移动组网的 BFDREAM协议。Bakhouya等人[23]采用实际运动模型,对DREAM协议在不同交通负载和不同速度下的智能交通系统的性能进行了仿真,得出DREAM协议随着交通负载的增加效率降低比较明显,对节点运动速度的增加反应则不那么明显。

3.5 GPSR

贪婪型转发和沿周边转发路由(Greedy Perimeter Stateless Routing,GPSR)协议是 Brad Karp等人[24]提出的一种用于无线数据报网络的基于地理定位信息的路由协议。GPSR协议要求每个节点周期性地向其邻居节点广播自己的地址和地理定位信息,每个节点只保存自己邻居节点的路由信息,因此路由表中仅含一跳的、最小的拓扑信息。为进一步减小控制开销,各个节点的地理定位信息捎带在数据分组中进行传送。

源节点在发送数据分组时,将目的节点的地理位置信息也捎带进去,因此每个中间节点可以根据自己保存的路由信息来选择最佳(地理位置上离目的节点最近)的下一跳贪婪型转发节点,下游节点继续采用这种方式,直至数据分组成功传递到目的节点。

只要条件允许,GPSR协议优先采用贪婪型转发模式,而当贪婪型转发模式失效时,则转入沿周边转发模式,即沿着自己转发的路由空洞(在该节点的传输范围内,没有比该节点离目的节点更近的节点)周边采用右手法则寻找新的路由。右手法则的基本思想是按照顺时针方向遍历一个封闭多边形区域的内部边线,若在封闭多边形区域的外部时,则以反时钟方向遍历。在GPSR协议中,右手法则的使用是通过启发式算法来完成的。当节点采用沿周边转发模式发送数据分组时,只要条件满足,可以自动转回贪婪型转发模式,直到数据分组发送到目的节点。

GPSR协议由于采用了贪婪型转发模式,因此只依赖一跳邻居节点的信息,大大减小了网络的控制开销,提高了路由的稳定性,同时采用了沿周边转发模式,可以有效地防止路由空洞的出现,所以比较适合在节点密度大的自组网中使用。但贪婪型转发模式所选择的节点依据是地理位置距离目的节点最近,因而路由的选择并非一定最佳,少数情况下,得到的路由可能是一条很长的路径。贪婪型转发模式只依赖一跳邻居节点的地理定位信息,节点的运动速度过大时,容易出现邻居节点移动出节点的传输范围,从而导致丢包情况的发生。由于无线信道的传输特性,GPSR协议还容易出现节点和邻居节点无法正常通信,从而导致节点误删邻居节点的路由信息。

GPSR协议的健壮性已经得到充分证明,目前其研究主要集中在改进协议的仿真运动模型、改进路由协议以适用不同应用需求这两个方向。不同的运动模型导致对现实模拟的近似程度不同,因此模型的设计和选取对路由协议的仿真至关重要。Majid Shakeri[25]采用不同的移动模型(Random Waypoint Model(RWM)、Fluid Traffic Model(FTM)、Intelligent Driver Model with Intersection Management(IDM-IM))对GPSR、SIFT和GOSR 3种协议在城市智能交通系统中的性能进行了分析,结果表明RWM、FTM两种模型不适合用来模拟仿真城市智能交通系统,只有IDM-IM模型可以采用,同时作者还表明城市地形会降低GPSR协议的性能。N.Premalatha等人[26]则采用GPSR协议用于路由,采用新的冲突避免、ACK顺序机制和分裂算法,提出了一种适用于自组网的QoS模型。现有的GPSR协议只有经过改进才能应用于城市智能交通系统,由于城市交通系统具有一定的规律性,目前研究的方向多为引入城市电子地图信息系统改进GPSR协议的运动模型,进而改进GPSR协议的实用性能。

Nguyen[27]等人针对城市智能交通系统高动态的特点,提出了一种GPSR-MA-LA协议。该协议要求节点周期性地广播自己的地理定位信息,同时采用节点负载均衡路由算法,将节点的运动性和负载均衡综合考虑。通过NS-2仿真表明,该协议能比GPSR协议有效地降低丢包率,减小时延。SUN等人[28]针对城市智能交通系统中由于交通工具的不规则分布导致GPSR性能低下的现象,采用电子地图信息辅助进行改进,仿真表明该方案确实能降低丢包率。Shu[29]等人针对GPSR协议地理定位信息的更新时间间隔难题(需满足不同网络密度和应用需求),采用NAU(Neighbor-Awareness Position Update)根据节点的邻居节点数量和地理方位来动态设置GPSR协议的地理定位信息更新时间间隔,将BGF(Beacon-assist Geographic Forwarding)策略与GPSR协议相结合,提出适用于城市智能交通系统的GPSRN&B协议。如何合理设置GPSR协议的地理定位信息更新时间间隔以使GPSR协议适用于不同的场景仍是今后GPSR协议应用于城市智能交通系统研究的一个重点方向。

总之,上述几种典型的基于地理定位信息的路由协议都是通过某种策略限制参与路由的节点数量,从而减小网络的控制开销和负载。LAR和RDMAR协议由于将路由查找区域限制在一定的请求区域内,参与路由的节点少,因而路由查找速度快、控制开销小,随着网络规模的增大,路由的成功率和可靠性显著增加,因而网络的可扩展性能好,但如果初始查找时无法获取目的节点地理定位信息或地理定位信息不准确,两者都需要扩大查找范围或等同于全网泛洪方式,从而会增加网络延迟和开销,因而适用于节点密度中等或高的网络。GeoCast协议由于可以分层,因而其网络扩展能力更强,适用于规模较大的网络,同时还可以实现多播功能,但由于某些节点的位置需要相对固定,因而适用性受到一定限制。DREAM协议每个节点均需要维护路由表,因此路由的稳定性较其他协议强,但当网络规模扩大时,其控制开销会急剧增大,因而网络的扩展性较其他协议差,只适用于规模较小的网络。GPSR协议依靠的是一跳协议,网络控制开销较其他协议小,但是其路由长度不是最优,而且在路由过程中,较其他协议容易遭遇“路由空洞”和“隐蔽终端”的问题,不过已有较多的学者就这一问题进行了研究,提出了众多解决方案。目前已有的研究表明:LAR协议和GPSR协议具有较强的健壮性,移动性能也较其他协议强,因而其适用的网络较多,当前已有学者试着将两者应用到航空领域。

4 总结与展望

移动自组网的动态特性使得传统的路由协议不再适用,必须开发新的路由协议才能满足需求。现有的研究大多只就移动自组织网络的某一路由协议进行研究。本文首先介绍了路由协议的设计基本原则,并按设计路由时选取的信息类型进行了分类。然后对当前典型的基于地理定位信息的移动自组网路由协议的原理和关键点进行了解析,对近年来的研究情况进行了分析归纳,指明了当前研究的主要思路和热点方向,希望能给以后的研究提供借鉴和帮助。

近年来由于WiFi技术的兴起,使得移动自组网技术在民用领域的需求不再那么迫切,民用方面移动自组网的研究主要集中在一些需要临时通信而没有基础设施的场合,如城市智能交通系统、救援、民航等领域;军事方面,移动自组网的研究已经遍布各个领域,水下组网、陆地战场组网、航空组网都已成为研究的对象,特别是航空自组网,由于其高动态的特性和迫切的需求(无人机控制、战机组网等),更是重点的研究方向。基于地理定位信息的路由协议由于采用地理定位信息作为路由的辅助手段,相对于传统自组网路由协议可以大大减小网络的控制开销、减小时延、提高路由的可靠性,增强网络的可扩展性,因而更适用于高动态的应用场合,但是高动态的运动环境带来拓扑的频繁变化,对路由协议的收敛性和可靠性提出了更高的要求,如何利用地理定位信息开发出更加快速可靠的路由协议必将成为未来移动自组网技术发展的重点。目前,国内外对这方面的研究大多是基于以上协议的改进或扩展,随着研究的深入,可以就该方向做进一步的研究。此外,一些基于地理定位信息的移动自组网路由协议如具有移动预测机制的路由协议DV-MP(Distance Vector with Mobility Prediction)、FORP(Flow Oriented Routing Protocol)、基于路径的简单前向协议(Simple Forwarding over Trajectory,SIFT)等由于其特殊性也可以引起适当的关注。

[1] Murphy A L,RomanG C,Varghese G.An exercise in formal reasoning about mobile communications[C]//Proceedings of 1998 IEEE Ninth International Workshop on Software Specification and Design.Ise-Shima:IEEE,1998:25-33.

[2] KarrasK,Kyritsis T,Amirfeiz M,et al.Aeronautical Mobile Ad hoc Networks[C]//Proceedings of the 14th European Wireless Conference.Prague:IEEE,2008:1-6.

[3] Tee C A T H,Lee A C R.Survey of Position Based Routing for Inter Vehicle Communication System[C]//Proceedings of First International Conference on Distributed Framework and Application.Penang:IEEE,2008:174-182.

[4] Lambrou T P,Panayiotou C G.A Survey on Routing Techniques supporting Mobility in Sensor Networks[C]//Proceedings of the 5th International Conference on Mobile Ad-hoc and Sensor Networks.Fujian:IEEE,2009:78-85.

[5] Rohrer J P,Jabbar A,Egemen K,et al.Airborne Telemetry Networks:Challenges and Solutions in the ANTP Suite[C]//Proceedings of Military Communications Conference.San Jose,CA:IEEE,2010:74-79.

[6] Okamoto S,Sycara K.Augmenting ad hoc networks for data aggregation and dissemination[C]// Proceedings of 2009 Military Communication Conference.Boston,MA:IEEE,2009:1-7.

[7] Ko Young-Bae,Vaidya N H.Location-Aided Routing in mobile Ad hoc networks[J].Journal of Wireless Network,2000,6(4):307-321.

[8] 牟强,姚丹霖,姚宗福.一种改进的LAR方向路由算法[J].微电子学与计算机,2011,28(4):30-33.MOU Qiang,YAO Dan-lin,YAO Zong-fu.An Improved Direction Routing Algorithm Based on LAR[J].Microelectronics&Computer,2011,28(4):30-33.(in Chinese)

[9] Jang Hung-Chin,Hung Chih-Chia.Direction Based Routing Strategy to Reduce Broadcast Storm in MANET[C]//Proceedings of 2010 IEEE International Computer Symposium.Tainan:IEEE,2010:445-450.

[10] Chaki N.LAR2P:A Location Aided Reactive Routing Protocol for Near-Optimal Route Discovery in MANET[C]//Proceedings of 2010 International Conference on Computer Information Systems and Industrial Management Applications.Krackow:IEEE,2010:259-264.

[11] Gupta N,Gupta R.Proposed Energy Conserving Routing Technique using LAR[C]//Proceedings of 2011 International Conference on Computational Intelligence and Communication Systems.Gwalior:IEEE,2011:626-630.

[12] Al-Bahadili H,Al-Basheer O,Al-Thaher A.A Location Aided Routing-Probabilistic Algorithm for Flooding Optimization in MANETs[C]//Proceedings of Mosharaka International Conference on Communications,Networking and Information Technology.Amman Jordan:IEEE,2007:6-8.

[13] Al-Bahadili H,Maqousi A.On the Effect of Nodes Desnity on the Performance of the LAR-1P Route Discovery Algorithm[C]//Proceedings of 2011 IEEE Jordan Conference on Applied Electrical Engineering and Computing Technologies.Amman,Jordan:IEEE,2011:1-6.

[14] Aggelou G,Tafazolli R.RDMAR:A Bandwidth-efficient Routing Protocol for Mobile Ad Hoc Networks[C]//Proceedings of the 2nd ACM International Workshop on Wireless Mobile Multimedia.Seattle,Washington:ACM,1999:26-33.

[15] Hamad O F,Kang Mi-Young,Jeon Jin-Han,et al.Neural Network′s k-means Distance-Based Nodes-Clustering for Enhanced RDMAR Protocol in a MANET[C]//Proceedings of 2008 IEEE International Symposium on Signal Processing and Information Technology.Sarajevo:IEEE,2008:192-197.

[16] Akhtar N,Tafazolli R.Traffic-based Multipath Routing for Mobile Ad hoc Networks[C]//Proceedings of 2004 International Workshop on Wireless Ad-Hoc Networks.Oulu,Finland:IEEE,2004:201-206.

[17] Navas JC,Imielinski T.Geocast-geographic addressing and routing[C]//Proceedings of the 3rdAnnual ACM/IEEE International Conference on Mobile Computing and Networking.Buapest,Hungary:IEEE,1997:66-76.

[18] Zhu Konglin,Zhou Biao,Fu Xiaoming,et al.Geo-assisted Multicast Inter-Domain Routing(GMIDR)Protocol for MANETs[C]//Proceedings of 2011 IEEE International Conference on Communications.Kyoto:IEEE,2011:1-5.

[19] Shiraishi Y,Takahashi O,Miki R.A Geocast-based Multicast Method for Continuous Information Delivery in MANET[C]//Proceedings of 2010 International Conference on P2P,Parallel,Grid,Cloud and Internet Computing.Fukuoka:IEEE,2010:511-516.

[20] Wang Ting,Low Chor Ping.A Ferry Scheme for Geocast in MANETs[C]//Proceedings of the 5thAnnual ICST Wireless Internet Conference.Singapore:IEEE,2010:1-8.

[21] Basagni S,Chlamtac I,Syrotiuk V R,et al.A Distance Routing Effect Algorithm for Mobility(DREAM)[C]//Proceedings of the 5th Annual ACM/IEEE International Conference on Mobile Computing and Networking Mobicom.Dallas:ACM,1998:76-84.

[22] Hu Hongning,Liu Zhong,Yang Bin.BFDREAM:A new routing protocol for deep sea acoustic network[C]//Proceedings of 2010 IEEE 10th International Conference Signal Processing.Beijing:IEEE,2010:2377-2381.

[23] Bakhouya M,Gaber J,WackM.Performance Evaluation of DREAM Protocol for Inter-vehicle Communication[C]//Proceedings of 1st International Conference on Wireless Communication,Vehicle Technology,Information Theory and Aerospace&Electronic Systems Technology.Aalborg:IEEE,2009:289-293.

[24] Brad Karp,Kung H T.GPSR:Greedy Perimeter Stateless Routing for Wireless Networks[C]//Proceedings of the 6th Annual International Conference on Mobile Computing and Networking.Boston:IEEE,2000:243-254.

[25] Shakeri M.Simulation and Evaluation of Routing Protocols in Vehicular Ad Hoc Network[C]//Proceedings of 2011 Eighth International Conference on Wireless and Optical Communications Networks.Paris,France:IEEE,2011:1-3.

[26] Premalatha N,Natarajan A M.Congestion Control and QoS Enhancement of Ad hoc Networks[C]//Proceedings of 2010 International Conference on Communication and Computational Intelligence.Erode,India:IEEE,2010:40-46.

[27] Nguyen T D,Van T P,Trong T D,et al.A Load-balanced and Mobility-aware Routing Protocol for Vehicular Ad-hoc Networks[C]//Proceedings of 2011 International Conference on Advanced Technologies for Communications.Danang,Vietnam:IEEE,2011:36-39.

[28] SUN Shupeng,HU Jianming,LUO Xixi,et al.Improved GPSR in Inter-Vehicle Communication[C]//Proceedings of 2010 International Conference on Communications and Mobile Computing.Shenzhen:IEEE,2010:259-265.

[29] Shu Wenjie,Wang Ping,Guo Aihuang,et al.Enhanced GPSR using Neighbor-Awareness position Update and Beacon-assist Geographic Forwarding in vehicular ad hoc networks[C]//Proceedings of 2009 IEEE Intelligent Vehicles Symposium.Xi′an:IEEE,2009:1143-1147.