一种基于位置信息辅助的移动自组织网络路由算法

周翔



一种基于位置信息辅助的移动自组织网络路由算法

周翔

东南大学 网络与信息中心, 江苏 南京 210096

在移动自组织网络中，由于节点的移动没有固定的模式，很多情况下无法得到稳定的网络拓扑，因此传统的无线多跳网络路由协议很难直接运用于移动自组织网络。本文分析了基于地理位置的路由模型，引入移动节点的当前位置信息和目标位置信息，结合报文的投递目标进行在报文转发中做最优路由选择。基于影响路由选择的三个要素：移动节点目标位置与报文目标位置的距离、移动节点目标位置与报文目标位置的夹角和移动节点本身的移动速度，提出了一种基于位置信息辅助的移动自组织网络路由算法(LIBR)。仿真结果表明，所提算法在转发成功率、转发延时以及转发次数等性能参数方面与现有的路由算法相比，具有更好的性能表现。

移动自组织网络；路由算法；路由选择；位置信息辅助

移动自组织网（Mobile Ad hoc Networks, MANETs）是由一组可自由移动和相互通讯的节点，通过自动配置组成的多跳无线通讯网络，不需要提前布置任何固定的网络基础设施。随着研究的发展，移动自组织网络的应用越来越广泛，如军事战场上[1]，深空环境下[2]和游牧监控网络[3]等。移动自组织网络具有特殊的网络结构配置，由于节点高移动性所导致的拓扑频繁变化，使得节点之间不能频繁进行通信，从而任意节点之间的链路无法保持稳定，因此传统的多跳无线路由协议无法运用于移动自组织网络中。

近年来，在移动自组织网络的路由研究方面，国内外许多研究机构对基于地理位置信息的路由协议展开了研究。基于地理位置信息的路由的主要思想是将消息转发给特定的地理位置，而不是一般路由算法中的以特定节点为目标。现有的基于地理位置信息的路由协议，主要是基于与目标位置距离的方法，把消息距离目标位置的路程作为判定下一个中继的标准[4-7]。但是对于大规模的移动自组织网络来说，基于距离的路由方法并不能够获得很好的表现，主要原因有以下几点：1）移动自组织网络中的高移动性导致了距离快速地变化，进而降低了算法的性能表现；2）这样的算法需预先知道网络的拓扑，对于在大规模的移动自组织网络中这样的知识难以获取；3）现有的算法没有考虑到节点本身具有的一些有用的路由信息，比如说当前节点的目的地，可以通过一些方法提前获得，比如车辆的导航系统以及出租车乘客提供的目的地址。

本文通过考察移动节点和消息的位置信息（包当前位置信息和目标位置信息），将这些信息运用到移动自组织网络的路由算法中，在了解了移动节点和消息的当前位置和目标位置后，路由算法总是将消息转发给更有可能移动到消息目标投递区域的节点，减少了无效的投递，增加路由算法的投递成功率和转发延迟，提高路由转发效率。移动节点的当前位置信息可以通过全球定位系统（Global Positioning System, GPS）[8,9]获得。由于是基于地理位置的路由，所以消息的目标位置信息在消息生成时已经确定。移动节点目标位置可以通过一些方法间接获得，随着科技的不断发展，现在的车辆上一般都配备有导航系统，在一段行程开始前会设置目标位置。此外，还有一种情景是城市交通中的出租车和公交车，公交车的目标位置是相对固定的；出租车在有乘客的情况下，目的地通常都是固定的，所以我们也可以假设预先了解到了移动节点的目标位置。

本文的组织结构如下：第2部分介绍与分析移动自组织网路由算法以及基于位置信息辅助的路由算法的相关工作；第3部分提出了的基于位置信息辅助的移动自组织网络路由算法；第4部分通过仿真实验，将提出的路由算法与其他路由算法进行比较分析；第5部分给出本文的结论。

1 相关工作

1.1 传统移动自组织网络路由算法

在文献[10,11]（WCNC）中提出了基于泛洪的多副本路由算法，从源节点开始产生消息，并且将副本转交给每一个相遇的节点，尽可能覆盖到每一个网络中的节点以提高传输成功率。尽管泛洪路由在没有条件约束的场景中路由效果是最优的，但在实际的应用场景中泛洪路由算法带来的巨大的网络负载使其无法运用在大多数真实场景中。为了降低泛洪路由带来的网络负载，文献[12]提出了PROHET路由算法，该算法利用节点间的历史相遇记录信息来预测未来转发的可能性。PROHET中的路由指标是节点成功地从源节点转发到目标节点的可能性，即报文总是转发给更有可能遇到目标节点的移动节点。除此之外，为了控制报文副本在网络中的数量，文献[13,14]提出了基于K-副本的Spray-and-Wait算法和Spray-and-focus算法，有效控制网络中副本数量的同时降低了网络负载并提高了转发效率。另外，单副本的路由算法也有许多相关的研究成果，用于减少路由的开销。文献[15]基于节点间相关联的信息提出了MED算法，该算法对每对节点相遇的期望时间进行量化处理，生成节点之间联系的加权图，最后利用Dijkstra算法计算节点间最短路径；文献[16]提出了SimBet算法，该算法基于社会关系定义了中心性和相似度的概念，通过计算所遇节点的向心性和相似度来决定是否向其转发报文，主要利用社会网络中呈现出的“小世界”的现象来增加消息的转发成功率。

1.2 基于地理位置的路由算法

基于地理位置的路由算法的研究也具有相当长的历史。在较早的文献[4]中，只有单副本路由被考虑进来。为了提高转发成功率，多副本路由开始被广泛使用，运用最多的就是泛洪路由算法，被许多基于地理位置的路由算法采用。文献[6]提出了基于泛洪路由算法的方法，该方法在消息源节点和目标位置之间定义了方形的转发区域，在路由选择中消息总是转发给离目标位置距离更近的节点来增加转发成功率。文献[17]引入了泰森多边形来帮助转发区域的选择。另外，文献[5]提出了基于分簇的路由方法，具体方法是将网络区域划分为逻辑网格，在网格中挑选出簇头作为网关进行数据的转发。在文献[5]的基础上，文献[7]引入了额外的簇头，用于收集移动节点的消息并转发到目标位置。然而分簇算法带来的问题是簇头的负载增加而导致的网络瓶颈。除此之外，文献[18,19]利用车辆本身带有的一些位置信息来辅助路由选择，比如说车辆中一般安装有GPS系统和导航系统，这些额外的信息可以用来提高路由效率。本文提出的基于地理位置信息辅助的路由算法是综合利用节点本身以及消息的位置信息和目标位置信息进行路由选择。

2 基于位置信息辅助的移动自组织网络路由算法

2.1 网络模型

基于地理位置的移动自组织网络路由算法与传统的移动自组织路由算法的区别在于前者是以地理位置或地理区域为转发目标的路由算法，而后者的目标是网络中的节点。基于地理位置的移动自组织路由算法的目的是基于移动节点的移动特性实现地理位置之间的报文信息的转发。报文在指定的地理位置产生并且报文以另外一个地理位置为目标。我们假设移动节点可以存储携带这些报文并且在移动到下一个地理位置时由路由算法决定是否卸载缓存中的一个或多个报文。同时，移动自组织网络中的移动节点的频繁相遇可以为报文的快速转发带来一些潜在的机会，所以移动节点与移动节点之间也会进行交互来提高报文的转发成功率。

假设网络中有个具体的地理位置，并且在这些位置都是相对固定的，假设L代表位置的地理位置。除此之外，我们假设在这些位置上都有接受无线传感器网络信号的节点，我们称之为静态节点。这些静态可以通过无线信号和移动节点进行通信。本文中将由这些静态节点代替指定的转发位置进行路由转发，并且假设这些静态节点的缓存足够大。上文中我们提到在一个指定的地理位置产生的报文是以另外一个地理位置为目标，所以假设消息的目标位置为()。另外，假设网络中具有个移动节点，并且这些移动节点都知道自己的当前位置以及目标地点的信息，其中结点当前位置用L来表示，目标位置用()来表示（图1）。

图 1 节点移动模型

在本文中，我们只考虑基于地理位置的移动自组织网络中的单播网络模型，即单条消息只有一个确定位置。另外，我们假设节点的移动模型是改进的随机路点（Random Way Point, RWP）模型[20]，RWP模型随机地选择目标节点位置并按随机的速度沿直线移动到该位置并产生下一路点循环重复以上的步骤进行移动。我们改进的地方在于将按直线路径移动改为沿随机路径移动到目标位置，这样能过更适用于我们提出的算法。

2.2 算法实现

基于车辆本身的地理位置信息以及报文的地理位置信息我们设计并实现了一种基于地理位置信息辅助的移动自组织网络路由算法（Location Information Based Routing, LIBR）。LIBR算法的主要思想是将报文更快、更准地转发到目标位置。如果能够尽可能多地解到移动节点的运动趋势，对于基于地理位置信息的路由算法的性能的提高有很大帮助。在所有节点做报文的路由选择是需要考虑周全，因此我门列出了3个最有可能影响路由选择的因素：

1）移动节点目标位置与报文目标位置的距离：如果移动节点能够将报文转发至离报文目标位置更近的地方，在路由选择上这样的移动节点应该具有较大的优先级；

2）移动节点目标位置与报文目标位置的夹角：考虑到移动节点分布的不均匀性以及移动节点目标位置的随机分布，可能没有办法将报文通过捎带或者简单的一两跳将报文转发到目标位置，此时需要考虑到节点当前的目标方向（不同于移动方向，该方向向量由移动节点的当前位置和目标位置构成）；

3）移动节点的移动速度：移动节点的速度将影响报文转发的速率，移动越快的节点将会被赋予更高的路由优先级，这样不仅能够使报文具有更高的概率投递给优势更大的下一跳节点，并且加快报文在网络中的传播速率，从而提高报文的转发成功率。

算法LIBR

输入:n,n,m

输出:n

1:ifnwithin(m) then

2:n¬n

3: else if(n,m)>(n,m) then

4:n¬n

5: else

6:n¬n

7: end if

8: end if

9: returnn

其中++=1，显然(n,m) (0,1)，根据三个因素的重要程度对、和分别进行调整，考虑到方向因素相对较为重要，本文中三个数值的取值分别是0.5、0.25以及0.25。

LIBR算法的核心在于计算移动节点和待转发消息的转发概率值，路由总是选择概率值高的移动节点作为下一跳转发节点，这样才能够保证报文更快、更准确地转发到目标位置。

由于移动自组织网络本身具有的一些特性，LIBR算法能够充分利用各个移动节点的相遇机会来不断增加概率值。显然倒数第二跳的节点具有最高的报文转发概率值，所以LIBR算法的高效性得以保证。

3 仿真实验

下面，将对所提出的算法进行性能评估与分析，本文使用ONE[21]仿真平台进行实验。首先需要获得节点的相遇信息和移动路径信息，然后输入到ONE仿真器中进行仿真，最后获得ONE输出的性能参数对算法进行评估与分析。为了对比本文提出的算法，我们加入了一些经典算法进行对比，仿真中涉及的路由算法包括：1）泛洪路由算法（Epidemic）；2）基于二分方法Spray-and-wait的副本路由算法（简称SAW），设置了两个不同的值进行对比；3）基于距离的地理位置路由算法（Geo-Dist）[22]。

本文假定在一个方形的大小为500 m×500 m的区域中进行试验。移动节点的移动模型采用改进的RWP模型，移动速度在5 m/s~10 m/s之间随机选择，随机停留时间在5~10 s之间取值。假设节点间的通信半径为20 m，设置报文的TTL值为1300 s。为了对比各个算法的性能表现，即设置不同的报文产生速率来观察算法在不同的网络负载下的表现情况，范围是1 pkt/s~5 pkt/s，此外节点的缓存大小被设置为固定值20 pkt。我们从三个方面来评估算法的性能表现：报文投递成功率、报文的平均投递延迟和报文的总转发次数。为了消除仿真中数据的随机性，每个结果都是来自于1000组测试结果的均值。

首先考察投递成功率，如图2所示，随着报文生成速率的增加，投递成功率都会有不同程度的下降，这是因为报文的增加使得缓存有限的节点产生丢包现象。特别是多副本算法，由于拷贝数量的增加让原本就紧张的缓存资源无法承受过高网络负载而丢失大量报文。但是在报文负载较低时，多副本路由算法的表现较好，特别是泛洪路由算法和取值较大时的SAW算法。可以清楚地看出我们提出的LIBR算法在不同的网络负载情况下表现均很不错，特别是在5 pkt/s的报文产生速率下依然能够保持90%以上的投递成功率。另外，Geo-Dist算法只考虑了距离因素，所以投递率比LIBR算法低一些，但是也能够保持在比较高的水准。

图 2 报文生成速率vs.投递成功率

其次，我们考察报文的平均投递延迟，从图3中可以看出，多副本路由算法具有更低的延迟，这是由于网络中同一报文有多个副本的存在，使得报文能够更快地寻找到目标位置。但是多副本网络中会有大量的报文丢失现象，所以随着报文生成速率的增加，网络中存在的时间越长的报文就越容易被丢弃，最终导致了平均延迟的降低现象。LIBR算法和Geo-Dist都具有较高的延迟，这是由于单副本路由算法存在的普遍问题，不过本文提出的算法相比Geo-Dist具有更低的投递延迟，所以在做路由选择时全面地利用节点和报文的信息可以用来降低投递延迟。

最后考察报文的累积转发次数，从图4可以看出，多副本路由算法具有更多的转发次数，特别是泛洪路由算法，这样的结果是显而易见的。更多的转发次数意味着更多的能量消耗，这也是泛洪路由算法无法广泛运用于实际场景的一个主要原因。本文提出的算法与Geo-Dist具有相近的转发次数，并且LIBR算法的表现得稍微好一些，这是由于我们提出的算法中报文的有效转发次数增加并且不断累计的结果。

图 3 报文生成速率vs.平均投递延迟

图 4 报文生成速率vs.转发次数

综上所述，本文提出的算法在投递成功率表现最为出色，在不同的网络负载下都能够获得很高的投递成功率，在转发次数方面也具有良好的表现，尽管在投递延迟方面的表现稍微差一些，但是从总体上来看，LIBR算法和本文所列出的其他算法相比，具有更好的表现。

4 结语

本文首先简单的介绍了基于地理位置的移动自组织路由算法的研究现状，通过对移动节点本身具有的一些位置信息的发掘，提出了一种基于位置信息辅助的移动自组织网络路由算法。然后加入了仿真实验，测试所提出算法的性能表现，并与现有的一些算法进行了对比分析，实验结果表明我们的算法可以较好的提高消息的投递率、降低网络负载以及更快、更准确地将报文投递到目标位置。在以后的工作中将考虑将我们的算法运用到实际的运用场景中，进一步验证所提算法的实用性能。

[1] McMahon A, Farrell S. Delay-and disruption-tolerant networking[J]. Internet Computing, IEEE, 2009,13(6):82-87

[2] Burleigh S, Hooke A, Torgerson JL,. Delay-tolerant networking: an approach to interplanetary internet[J]. IEEE Communications Magazine, 2003,41(6):128-136

[3] Doria A, Uden M, Pandey DP. Providing connectivity to the saami nomadic community[C]. Proc. 2nd Int. Conf. on Open Collaborative Design for Sustainable Innovation, 2002

[4] Ko YB, Vaidya NH. GeoTORA: A protocol for geocasting in mobile ad hoc networks[C]. Proc. IEEE Int. Conf. on Networking Protocols, 2000:240-250

[5] Liao WH, Tseng YC, Lo KL,. “GeoGRID: A geocasting protocol for mobile ad hoc networks based on grid[J]. J. Internet Tech., 2000,1(2):23-32

[6] Ko YB, Vaidya NH. Flooding-based geocasting protocols for mobile ad hoc networks[J]. Mobile Networks and Applications, 2002,7(6):471-480

[7] Imieliński T, Navas JC. GPS-based geographic addressing, routing, and resource discovery[J]. Communications of the ACM, 1999,42(4):86-92

[8] Dommety G, Jain R. Potential networking applications of global positioning systems (GPS)[R]. Computer Science, 1998:22-42

[9] Parkinson BW, Gilbert SW. NAVSTAR: global positioning system – ten years later[J]. Proceedings of the IEEE,1983, 71(10):1177-1186

[10] Spyropoulos T, Psounis K, Raghavendra CS. Single-copy routing in intermittently connected mobile networks[C]. IEEE Secon First IEEE Communications Society Conference on sensor & Ad Hoc Communications & Networks, 2004:235-244

[11] Tseng Y, Ni S, Chen Y,. The broadcast storm problem in a mobile ad hoc network[J]. Wireless networks, 2002,8(2-3):153-167

[12] Lindgren A, Doria A, Scheln O. Probabilistic routing in intermittently connected networks[J]. Acm Sigmobile, 2003,7(3):19-20

[13] Spyropoulos T, Psounis K, Raghavendra CS. Spray and wait: an efficient routing scheme for intermittently connected mobile networks[C]. Proc. of Acm Sigcomm Workshop on Delay-Tolerant Networking, 2005:252-259

[14] Spyropoulos T, Psounis K, Raghavendra C. Spray and focus: Efficient mobility-assisted routing for heterogeneous and correlated mobility[C]. Proc. of IEEE PERCOMW, 2007:79-85

[15] Jones EPC, Li L, Schmidtke JK,Practical routing in delay-tolerant networks[J]. , IEEE Transactions on Mobile Computing, 2007,6(8):943-959

[16] Daly EM, Haahr M. Social network analysis for information flow in disconnected delay-tolerant MANETs[J]. IEEE Transactions on Mobile Computing, 2009,8(5):606-621

[17] Stojmenovic I, Ruhil A, Lobiyal D. Voronoi diagram and convex hull based geocasting and routing in wireless networks[J]. Wireless communications and mobile computing, 2006,6(2):247-258

[18] Leontiadis I, Mascolo C. GeOpps: Geographical opportunistic routing for vehicular networks[C]. IEEE International Symposium on World of Wirele Mobile & Multimedia Networks, 2007:1-6

[19] Cheng P, Lee K, Geria M,. GeoDTN+Nav: geographic DTN routing with navigator prediction for urban vehicular environments[J]. Springer Mobile Networks and Applications, 2010,15(1):61-82

[20] Lin G, Noubir G, Rajaraman R. Mobility models for ad hoc network simulation[C]. Twenty-third Annual Joint conference of the IEEE Computer and Communications Societies, 2004:454-463

[21] Keränen A, Ott J, Kärkkäinen T. The ONE simulator for DTN protocol evaluation[C]. International Conference on Simulation Tools and Techniques, 2009:55

[22] Hall R. An improved geocast for mobile ad hoc networks[J]. IEEE Trans. on Mobile Computing, 2011,10(2):254-266

A Mobile Ad hoc Networks Routing Algorithm with Location Information

ZHOU Xiang

210096,

In Mobile Ad hoc Networks, since the mobile node does not exist a fixed pattern, it is unable to obtain a stable network topology in many cases. So traditional wireless multi-hop routing protocols are difficult to apply in MANETs directly. By analyzing the geographic-based routing model, mobile nodes’ current information and the destination information is introduced to help the optimal routing selection. Based on three main factors of the routing selection, i.e., the distance between node’s destination and message’s destination, the angle between node’s moving direction and message’s forwarding direction and the moving speed of mobile node, we propose a location information based routing algorithm. Simulation results show that the proposed algorithm outperform the existing routing algorithms in delivery rate and other performance parameters.

Mobile Ad hoc Networks; routing algorithm; routing selection; location information based

TN929.5

A

1000-2324(2018)05-0856-06

10.3969/j.issn.1000-2324.2018.05.027

2017-09-20

2017-10-25

周翔(1984-),男,硕士,助理工程师,主要从事网络研究与数据中心建设工作. E-mail:xzhou@seu.edu.cn