基于位置的Ad Hoc路由协议现状及发展

李 征，杨瑞娟，马罗文

(空军预警学院, 武汉 430019)



基于位置的Ad Hoc路由协议现状及发展

李 征，杨瑞娟，马罗文

(空军预警学院, 武汉 430019)

基于位置的Ad Hoc路由协议因其消除了对拓扑存储的依赖性，降低了相关能耗，提升了网络性能，成为了学者们重点关注的研究领域。介绍了基于位置的Ad Hoc路由协议的概念，分析了几个典型的基础路由协议，总结了现阶段研究面临的问题，归纳了基于地理位置路由协议国内外研究现状及发展趋势。

Ad Hoc；位置路由；路由协议

0 引 言

随着信息化建设的不断推进，以信息获取和信息交互为核心的网络中心战已成为未来战争的基本形式[1]。Ad Hoc网络通信因其机动性、灵活性成为空中战斗平台协同作战、信息交互的可靠方式。Ad Hoc网络是在没有中心基础设施的情况下，由一些具有无线通信能力的移动节点自组织形成的多跳无线移动网络，路由协议作为Ad Hoc网络的关键，通过事先对网络进行规划，达到保证连通性、应对高动态变化、降低节点功耗、提高传输速度、减少传输时延等目的，而基于位置的路由协议更是弥补了传统路由协议的不足，减少了开销、功耗，提高了交付率，对提升Ad Hoc网络的性能起着关键性作用。

1 基于位置的Ad Hoc路由协议

Ad Hoc路由协议按照路由算法分为基于拓扑的路由协议和基于位置的路由协议[2]。基于拓扑的路由算法在网络中使用链路信息来执行报文转发，算法分为主动式和反应式[3]，根据跳数找到最短路径，在大型网络和高动态网络中无法保证报文交付率。基于位置的路由协议便是为解决此类问题而产生的。

基于位置的路由协议包括位置搜索和分组转发2个阶段，通过位置搜索获取目的节点的位置信息；基于不同算法，分组转发有贪婪的分组转发、受限的有向泛洪和分级分组转发3种模式[1]。

基于位置的路由协议具有以下特点：

(1) 每个节点都能确定自己的位置坐标；

(2) 通过使用位置服务器，每个节点都能找到想要通信的其他节点，从该节点接收到的先验包(或其他机制)得到位置信息；

(3) 节点不用存储路由表，只用存储至多固定(一般为1)跳数以内邻居节点的信息；

(4) 一个节点，通过使用定期广播(例如节点标识符、地理坐标信息的信标)可以直接得到通信的节点位置；

(5) 在路由中，每一跳的路由决策都基于当前节点、邻节点、目的节点的位置。

2 典型的基于位置路由协议原理分析

2.1 位置辅助路由(LAR)协议

LAR协议是一种特殊的路由协议，它不是基于位置的路由协议，而是利用位置信息增强反应式路由的路由发现过程。利用信源的位置信息，限制路由发现过程中分组的泛洪范围。其算法类似动态源路由(DSR)(一种典型的基于拓扑的反应式路由)的源路由算法[4]，即只有发送节点知道完整的到目的节点的多跳路由，并储存在缓存内，被发送的数据分组在其分组头内携带源路由信息。当没有目的节点位置信息时，相当于泛洪。

利用位置信息(GPS)于请求区域进行有限泛洪，采用反应式路由机制，确定请求区域，如图1所示。

图1中，S为源节点，D为目的节点，Rz为请求区域，Ez为目的节点可能出现的位置的预测区。方案一的请求区域为目的节点D的预测区Ez和源节点S确定的矩形区域，方案二的请求区域为距离目的节点D更近的节点所在区域。

图1 确定请求区域Rz

确定请求区域后采用区域策略：在请求区域沿途转发RREQ(包含请求区域的边界坐标、当前节点位置、时间等信息)，请求分组到达信宿节点时，发送路由应答分组(包括目的节点当前位置、时间和平均速度)或采用距离策略实现路由发现。

2.2 贪婪的分组转发

建立路由时初始化采用贪婪算法，贪婪周边无状态路由(GPSR)协议算法模式如表1所示。

表1 GPSR算法

GPSR可以实现无状态路由，即每个节点的状态和寻址算法复杂度与总的可达节点数及拓扑结构的变化率无关[4]，是当前位置路由协议研究的基础，现阶段大部分的改进路由协议均是在GPSR协议的基础上完成的。

2.3 受限的有向泛洪(DREAM)协议

2.3.1 位置服务

每个节点通过泛洪“位置分组”来使其它节点的位置库(包含所有节点的位置信息：节点标识、相对于本节点的方向和距离、表项产生时间)得到更新，每个分组包括一个生存时间(TTL)字段(指定IP包被路由器丢弃之前允许通过的最大网段数量)，用于控制分组的传送距离。TTL低，分组发送频度高，其根据移动速率动态调整更新频度。

2.3.2 分组转发

DREAM协议的分组转发是典型的受限的有向泛洪[4]，获取期望域的算法同LAR。如图2，利用切线找到转发域，中间节点一跳转发至所有邻节点直至到达目的节点。节点数目多，数据量大，耗能也大；其优点是保证了无环路由，有较好的鲁棒性。

图2 DREAM协议转发域

2.4 分级区域路由(HARP)协议

HARP协议是典型的2级(区域内，区域间)区域混合路由协议，采用距离动态路由(DDR)算法：节点与邻居周期性交换拓扑信息，根据拓扑结构分布式地产生树集合，集合中每棵树形成一个区域，网络被划分为不重叠的动态区域集合。算法展示如图3所示。

图3 HARP协议算法

图3中，HARP协议算法是在区域内采用先验式路由，区域间网关节点处采用反应式路由，每个移动节点维护同一区域内所有节点的路由信息，形成区域分级的路由策略。

3 位置路由协议面临的关键性问题

国内外对于传统的Ad Hoc路由协议有着相对深入的研究与应用，但对位置路由协议的研究相对落后。经过研究总结可以分析出当前Ad Hoc网络大致存在以下问题：

(1) 分布式环境使得网络功能必须实现寻址、认证等功能，以保证链路的连通性，无线信道可能存在单向信道，为常规路由协议带来认知单向性、路由单向性、汇点不可达等影响，所以路由选择是一个很重要的问题。

(2) 无线信道质量较差，带宽有限，误码率高，链路质量和链路容量起伏波动，导致其实际吞吐量很低，节点的移动会造成链路断开，尤其是在高动态情况下。

北京城市道路交通的发展代表了我国城市交通领域的现状，为缓解北京交通拥堵问题，从2016年起北京市交通委员会连续两年发布《北京市缓解交通拥堵行动计划》[1-2]，力求针对重点区域、突出问题，对症下药缓解交通拥堵.

(3) 节点活动的随机性，时间、位置变化的信道和速率不可预测的随机数据到达使得在无线网络中充分利用不同资源、尽可能有效地传送数据是一个非常艰巨而重要的目标。

(4) 移动性使得路由表更大，为维护路由表就必须增加控制信息，导致有效带宽减少，限制了网络扩展性，同时导致收敛时间长、时延太大。

(5) 设备限制，包括电池容量、节点功耗，所以最重要的系统设计是节能。

(6) 安全性差，更容易受到窃听或者入侵、拒绝服务等网络攻击。

这些问题成为研究位置路由协议亟待解决的关键性问题。

4 位置路由协议发展趋势

国内外针对传统路由协议如OLSR、DSDV、DSR、AODV等的研究较成熟，国外Amirhossein Moravejoshariehl、Hero Modares等[5]，国内陈立等对这些路由协议进行了改进和仿真比对研究[6]，节点仿真速度达到400 m/s，成功投递率也达到90%以上。相对于传统路由协议，基于位置的路由协议发展较为落后。基于位置的路由是基于节点实际的物理位置进行路由[3]，消除了对拓扑存储的依赖性[7]和相关能耗，利用低成本的GPS，更适合应对无线Ad Hoc网络中的高动态特性，具有更好的扩展性，即为第3部分中的关键性问题(4)、(5)提供解决方案。2012年Fraser Cadger等人撰写的文献[7]对已有的地理路由领域的文献提供了一个广泛综合的理论调查：地理路由协议不仅消除了高拓扑维护能耗，还消除了高路由请求信息。这也意味着节点不用担心路径或者链路的断开(传统意义上的路径并不存在)，这样一来，依照网络情况的不同，从同一源节点到目的节点的线路可以有不同的选择，更好地适应了高动态网络，即解决了问题(1)、(2)。

针对基础位置路由协议，许多研究人员提出了改进版协议，其中效果较好的是2014年Zhong Dong等人提出的将网络拓扑控制机制与Ad Hoc网络中已存在路由协议OLSR协议结合的PLAR协议[8]，改善了航空Ad Hoc网络的路由路径持续时间，有效减少了高动态下路由路径中断的可能性，即解决问题(1)、(2)。在95%相似度真实环境的情况下仿真，双向飞行状态下的路由路径可用率为66.93%，较OLSR的45.27%有了很大提高，接近OLSR在单向飞行状态下的可用率(72.18%)。

地理路由协议设计最突出和流行的2种方法是贪婪转发和面路由，这两者有各自的优缺点。

在采用贪婪转发模式的领域中，针对网络中存在的诸如无法通信的区域——“空隙”和E.Schiller等人描述的“凹节点”(源到目的的路由在某一节点会发生信息回传)[9]这些问题，J. Na、D.Soroker等人提出了GLR地理地标路由协议[10]、地标[11]、生成树[12]、势场[13-14]、GDSTR贪婪分布式生成树[15]、RS螺旋扫描算法改进[16-18]等方法。相关讨论得出，贪婪转发是地理路由的一种常用方法。尽管投递成功率不高，它仍旧因其高效和简单而大受欢迎。但这些协议的仿真速度始终未能超过30 m/s，且只适用于二维平面。

另外，关于协议失败后的恢复策略，2001年到2010年间诸多学者提出了以面路由为基础的恢复策略[19-23]，能有效恢复路由，保证交付，但增大了网络开销和时延。

同时，混合型路由也大受欢迎，其想法是结合贪婪转发的高效性和面路由的交付保证，潜在的缺点包括切换到面路由然后切换回来的开销(一旦本地最大恢复，大多数混合协议通常会返回贪婪转发)依赖于反应恢复技术(即等待，而不是试图避免它)和用二者互换的方法解决问题潜在的失败性。2003年F.Kuhn等人提出的GOAFR贪婪自适应面路由[24]及其改进版GOAFR+、2005年B.Leong等人提出的PVEX路径矢量交换协议、OPVFR协议[25]、GPVFR协议(三方面结合路由)均是这一领域的代表。其中，GOAFR+拥有无征兆的最坏情况下的最有性，而GPSR经常被用作开发其他协议的基础。

地理路由协议的另一个重要方面是维度，具体来说，网络是二维的(即一个平面的高度差是可以忽略不计的)还是三维的(如一个多层次的区域，一座山或大的建筑物，有显著的高度差和经纬度，还有空中平台间的Ad Hoc网络)。虽然大多数地理路由协议是二维的，使用两坐标，最近需要的协议能够在三维环境中使用。这是标准的感知能力(二维)充分配合三维网络需求的地理路由协议。例如，单位圆盘图呈一二为欧式空间，而面对依靠平面化技术的路由会失败的面路由并不能应用于三维曲面[26]。反过来又促使研究领域的三维地理路由。2008年R. Flury等人使用单位球图，即三维版本的单位圆盘图作为一个基本模型设计三维路由[27]。而E. Lebhar等人则修改二维路由协议，通过投影某些节点到一个平面上(实际上是一个虚拟平面)，从而使面路由被应用到非平面地形[28]。就未来Ad Hoc路由协议的发展趋势来说，三维地理路由仍然是一个新兴的研究领域。

最后，有关路由协议的评判标准也有相关研究：文献[29]针对问题(2)、(3)提出了一个认知无线电Ad Hoc网络的联合费用、信道和路由选择(JRCRS)的方法。其度量标准为中继工作负载、中继节点和目的节点间的距离、初级和次级用户间的信道间干扰。由此可见，研究出更多、更贴切的路由性能评判标准也是未来发展的方向之一。

5 结束语

Ad Hoc路由关键技术问题近年来已成为国际上有关机群协同作战的一个热点问题，特别是在无人机参与信息化战争主战场之时，基于其高动态、网络拓扑结构复杂还有三维立体空间分布[30]，使得Ad Hoc路由技术的研究成为重中之重。在此方面，现阶段有关基于位置的Ad Hoc路由协议仍有许多问题亟待解决，比如：

(1) 交付率低的问题。高动态、三维立体空间分布使得节点间通信时链路质量受到很大影响，很大程度上影响了路由发现和维护。

(2) 路径稳健性差的问题。同样的因素导致路径稳健性差，无法保证传输可靠性。

(3) 端到端时延大的问题。如何快速查找路径，并且查找出最短、最优路径是未来一个重要的研究方向。

由于Ad Hoc网络在军事领域的应用，国内外对此项目也正在进行深入研究，研究好Ad Hoc路由协议对未来信息化战争空中平台的联合、体系作战来说至关重要。

[1] 陈瑶,梁加红,邹顺,曹娟.无人机Ad Hoc网络拓扑控制算法研究[J].计算机仿真，2010,27(7):33-37.

[2] 王金龙,王呈贵.Ad Hoc移动无线网络[M].北京：国防工业出版社,2004.

[3] 陈星林,曾曦.移动Ad Hoc网络——自组织分组无线网络技术[M].北京：电子工业出版社,2012.

[4] 郭丽芳,李鸿燕.无线Ad Hoc网络移动模型大全[M].北京：人民邮电出版社,2014.

[5] MORAVEJOSHARIEHL A,MODARES H,SALLEH R,MOSTAJERAN E.Performance analysis of AODV,AOMDV,DSR,DSDV routing protocols in vehicular Ad Hoc network[J].Research Journal of Recent Sciences,2013,2(7):66-73.

[6] 陈立,杨瑞娟,潘平俊,黄美荣.Ad Hoc高动态路由协议仿真与研究[J].现代防御技术,2015,43(5):111- 115.

[7] CADGER F,CURRAN K,SANTOS J,et al.A survey of geographical routing in wireless Ad Hoc networks[J].IEEE Communications Surveys & Tutorials,2013,15(2):621-653.

[8] ZHONG D,ZHU Y,YOU T,et al.A New Data Transmission Mechanism in Aeronautical Ad Hoc Network[M],2014.

[9] SCHILLER E,STARZETZ P,ROUSSEAU F.Binary waypoint geographical routing in wireless mesh networks[C]//Proceedings of The 11th International Symposium on Modeling,Analysis and Simulation of Wireless,2008:252-259.

[10]NA J,KIM C.GLR:a novel geographic routing scheme for large wireless ad hoc networks[J].Computer Networks the International Journal of Computer & Telecommunications Networking,2006,50(17):3434- 3448.

[11]BOSE P,MORIN P,STOJMENOV I,et al.Routing with guaranteed delivery in ad hoc,wireless networks[C]//International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications,2010:609-616.

[12]GABRIEL K R,SOKAL R R.A new statistical approach to geographic variation analysis[J].Systematic Zoology,1969,18(3):259-278.

[13]NA J,SOROKER D,KIM C K.Greedy geographic routing using dynamic potential field for wireless Ad Hoc networks[J].IEEE Communications Letters,2007,11(3):243-245.

[14]KUHN F,WATTENHOFER R,ZOLLINGER A.Asymptotically optimal geometric mobile Ad Hoc routing[C]//Proceedings of The 6th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications,2002:24-33.

[15]LEONG B,LISKOV B,MORRIS R.Geographic routing without planarization[C]//Symposium on Networked Systems Design and Implementation,2006:25-25.

[16]RUHRUP S,STOJMENOVIC I.Contention-based georouting with guaranteed delivery,minimal communication overhead,and shorter paths in wireless sensor networks[J].Idpds Proceedings of The IEEE Parallel & Distributed Processing International Symposium,2010(2):1-9.

[17]KALOSHA H,NAYAK A,RUHRUP S,et al.Select-and-protest-based beaconless georouting with guaranteed delivery in wireless sensor networks[J].Proceedings of IEEE INFOCOM,2008,18(1):346-350.

[18]RUHRUP S,KALOSHA H,NAYAK A,et al.Message-efficient beaconless georouting with guaranteed delivery in wireless sensor,Ad Hoc,and actuator networks[J].IEEE/ACM Transactions on Networking,2010,18(1):95-108.

[19]KIM Y J,GOVINDAN R,KARP B,et al.Geographic routing made practical[J].Symposium on Networked Systems Design & Implementation,2005(2):217- 230.

[20]FREY H,STOJMENOVIC I.On delivery guarantees of face and combined greedy-face routing in ad hoc and sensor networks[C]//International Conference on Mobile Computing and Networking,MOBICOM 2006,Los Angeles,Ca,Usa,2006:390-401.

[21]DAS S,LIU H,NAYAK A,et al.A localized algorithm for bi-connectivity of connected mobile robots[J].Telecommunication Systems,2009,40(3):129-140.

[22]BARRIE R L,FRAIGNIAUD P,NARAYANAN L,et al.Robust position-based routing in wireless Ad Hoc networks with irregular transmission ranges[J].Wireless Communications & Mobile Computing,2003,3(3):141-153.

[23]LEBHAR E,LOTKER Z.Unit disk graph and physical interference model:putting pieces together[J].Proceedings of International Symposium on Parallel & Distributed Processing,2009(2):1-8.

[24]KUHN F,WATTENHOFER R,ZOLLINGER A.Worst-case optimal and average-case efficient geometric Ad Hoc routing[J].Mir Proceedings of Acm Sigmm International Workshop on Multimedia Information Retrieval,2003(3):283-290.

[25]LEONG B,MITRA S,LISKOV B.Path vector face routing:geographic routing with local face information[C]//IEEE International Conference on Network Protocols.IEEE,2005:147-158.[26]ABDALLAHAE,FEVENST,OPATRNYJ.Highdeliveryrateposition-basedroutingalgorithmsfor3DAdHocnetworks[J].ComputerCommunications,2008,31(4):807-817.

[27]FLURYR,WATTENHOFERRR.Randomized3Dgeographicrouting[C]//Proceedings-IEEEINFOCOM,2008:834-842.

[28]JIL,TANGF,YANGY,etal.Jointrate,channelandrouteselectionforcognitiveradioadhocnetworks[C]//WirelessCommunicationsandNetworkingConference.IEEE,2015:1-13.

[29]PENGSC,WANGGJ,HUZW,etal.Survivabilitymodelingandanalysison3DmobileAdHocnetworks[J].JournalofCentralSouthUniversityofTechnology,2011,18(4):1144-1152.

Present Situation and Development of Ad Hoc Routing Protocol Based on Position

LI Zheng,YANG Rui-juan,MA Luo-wen

(Air Force Early Warning Academy,Wuhan 430019,China)

Ad Hoc routing protocol based on position eliminates the dependence on topology storage,debases the correlative energy consumption,improves the network performance,becomes the research domain that the scholars pay much attention on.This paper introduces the concept of Ad Hoc routing protocol based on position,analyzes several typical basal routing protocols,summarizes the problems faced with at present,concludes the present situation and development trend of routing protocol based on geographic position at home and aboard.

Ad Hoc;geographic routing;routing protocol

2016-01-15

TP393

A

CN32-1413(2016)05-0101-05

10.16426/j.cnki.jcdzdk.2016.05.026