无线移动Ad-hocd-hoc网的一种新的地理路由方法

江 涛,贺道德

（贵州工程技术应用学院信息工程学院，贵州　毕节　551700）

无线移动Ad-hocd-hoc网的一种新的地理路由方法

江 涛,贺道德

（贵州工程技术应用学院信息工程学院，贵州毕节551700）

分析无线Ad-hoc网现有的几种主要路由算法类型,它们包括proactive类、reactive类。着重分析地理路由算法。对于近年来的研究热点地理路由算法的类型进行分析，其中包括以路径为优化目标、以服务质量为优化目标和以最小能量为优化目标等几种类型。在此基础上，提出了概率路由算法的概念和一个新的算法。理论分析表明，该算法在该领域内是较好的算法。

无线Ad-hoc网；地理位置进行路由；概率路由算法

1　引言

无线Ad-hoc网是网络的一个类别，它指的是这样一类网络：节点可移动，且每个节点都允许根据自己的愿望随时加入或离开网络，部分或所有节点可能随时关机。因此，节点的位置和与网的连接状态都是随机的。

每个节点都具有路由能力，所有节点都既可以担任路由器，又是终端用户。网路没有预先假设的路由中心，没有担任专门角色的设备(如专用路由器、交换机等)。

无线移动网实际上还分几个子类：第一类是纯粹Ad-hoc网(或称移动的Ad-hoc网)，这种类型的Ad-hoc网所有节点都是移动的，简称为MANETs；第二类是WMNs，这种类型的网络由Ad-hoc网+固定网组成；第三类是WSNs，这种类型的Ad-hoc网由带传感器的移动设备+车载Ad-hoc网组成。

本文研究第一种Ad-hoc网的情形，即全移动的Ad-hoc网。

全移动的Ad-hoc网(以下简称Ad-hoc网)更具动态性，网的形成常常是为完成一个特定任务，任务完成以后便解体，网的连接可能仅仅持续一个较短的时间段。

由于节点是全移动的，且每个节点都允许根据自己的愿望随时加入或离开网络，部分或所有节点可能随时关机。因此，节点的位置和与网的连接状态都是随机的。这种网络常出现在战争、地震等紧急情形。另外，无线移动Ad-hoc网还面临干扰、路径丢失、信号衰减等问题。由于受到节点本身发射功率的限制，节点转发包只能局限于它附近的节点。因此，一个包从源节点传递到目标节点需要经过多个节点传递。这种情形简称为多跳(Multihop)。

根据无线移动网的特征，人们提出了两类路由协议。一类称为预先准备(proactive)的协议，一类称为临时处理(reactive)的协议。预先准备的协议通过在网中节点间发送一系列规则的更新信息来实现网络拓扑结构的识别和储存，而临时处理类的协议不在网上发送更新信息来了解网络的拓扑，当某个节点需要发送信息给某个目标节点时，发一个路由信息询问其他节点。这两类协议都有大量的算法。文献[1]、[2]评价了预先准备(proactive)的协议、临时处理(reactive)的协议和体系结构的协议三种基本协议类型，指出临时处理类型的协议较好。

以上方法都因为要了解网络的拓扑结构而需要发送询问信息，使得网上存在许多冗余信息，而且还是依赖拓扑结构，通信和储存方面的成本较高。

近年来，根据无线Ad-hoc网要求高效率、低成本的特性，人们提出了依据节点地理位置进行路由的新方法。这种路由方法是无线网领域内的一个新兴研究热点。这种称为地理位置路由的方法中，包由源节点到目标节点的路由不依赖网络标识或逻辑地址，而是依赖目标的地理位置[3]。这种路由方式不需要端到端的拓扑连接信息，不用构造并走一条简单的静态链路，也不用担心拓扑路径或链接中断等问题。因为传统意义上的路径已经不存在了，同一对节点在不同时间传递包可能经历的是不同的路径。由于不用预存路由表，这种路由方式节省了开销。一个节点只需存储它附近的节点(邻居)的位置信息。

当一个节点收到一个包时，它将查询邻居节点的位置信息表，根据某个地理位置选择原则，选择一个最适合的邻居节点来实现下一跳。

但是，进一步的研究表明，为了更有效地路由，一个节点还是需要除邻居之外的其他节点的位置信息。通常地理路由协议都使用某种位置服务来获得节点的地理位置。这种地理位置服务很多，如[4]提出的格点定位服务。这种服务方法由指定为位置服务器的节点组成，它们的任务是负责接收和存储某些节点的位置信息。当源节点需要知道目标节点的位置时，它将询问这些位置服务器。

有了这些位置信息，地理路由协议仍然可以使用传统的向前策略等方法来路由，所不同的是，路径是依据节点的地理分布而不是拓扑结构来形成的。

2　地理路由协议的研究现状

目前为止，人们对地理路由方法也进行大量的研究。地理路由方法有很多，例如贪心向前法和面路由法，这两类方法是以源节点到目标节点的路径为优化目标的。也有许多以其他参数为优化目标的，例如以服务质量为目标的地理路由协议，节省能量的路由协议，三维空间的地理路由协议，考虑安全性的地理路由协议，以及各种方法的改进方法。[5]

贪心向前法的基本思想是在每一跳中，把包传给离目标节点最近的邻居。这种方法简单易行，效率好。最坏情况下的时间复杂度为O(d2)，d为源节点到目标节点的距离。贪心向前法的缺点是当一个节点不能找到一个比它自己离目标节点更近的节点时，它必须丢包。针对这个缺陷，产生了许多改进的方法。

面路由法是以平面图为模型建立的一种方法。算法始终跟踪与源节点到目标节点的连线相交的面，通过这些面上的节点传递信息，直到最终将信息传递到目标节点。它的复杂度为O(n)，n为网络的节点数。

除了以上两类方法，还有其他的地理路由方法。例如地理辅助路由法（LAR），使用位置来决定一个“请求区”，目标节点被认为是在该区域，然后传递包到该区域。

尽管地理路由的方法摆脱了拓扑结构的随机性问题，但它还存在节点位置的随机性问题。没有考虑节点位置的随机性，仅从固定地理位置结构来寻找到的最短路径很难保证是实际上的最短路径，因为位置的分布是随机的，如图1所示。（图中虚线表示预想的路径，实线表示实际的路径。）

图1　节点的移动路径随时改变

这是到目前为止我们所看到的研究文献共同的不足。为了寻找实际上的最短路径，应该从概率的角度来寻找最短路径。

3　考虑概率因素的地理路由算法

下面考虑的仍是地理路由算法，仍然以优化路径为目标。但这里加入了概率的因素，即寻求概率意义上的最短路径。称这样的方法为概率地理路由方法。

3.1全移动的Ad-Hoc网络的随机图模型

设G=(V，E，W)，V为节点集，E为边集，这里我们考虑图G为完全图，即任意一对节点之间均有一条边。W为边权值，表示两节点之间的距离。由于节点是移动的，任何时刻任意一对节点之间的距离值W是随机变化的。这样的图上任意一对节点间的最短路径也是随时变化的。我们的目标是要找到任意一对节点之间概率上最大的最短路径。

就我们看到的资料，从概率的模型上考虑最短路径的路由算法还非常少，更没有形成一个类别。文献[6]从数学的角度研究了平面上随机点集上的最短路径的概率分布，指出其最短路径是服从泊松分布的Markov链，并证明了概率上的最短路径的性质。

3.2移动网的概率最短路径及数学证明

文献[6]从概率的角度出发，采用Delaunay图作为模型，证明了节点的地理位置分布、分布图上的路径都是服从泊松分布的随机过程，且是Markov过程，并证明了源到目标节点连线（以下简称连线）为概率上的最短路径，即连线为最短路径的概率最大，并且在连线附近形成的最短路径长度不超过4/π‖s-t‖，这里‖s-t‖是源节点到目标节点的欧几里德距离（这里省略了数学证明的过程）。

在此基础上，他们提出了一个找到概率上最短路径的邻居节点选择原则：在选择下一跳时，选择靠近连线最近的邻居，如图2所示。

图2　选择靠近源-目标节点最近的邻居

3.3我们所做的工作

首先，如果我们这样假设：考虑节点的移动距离Δx与通信距离S相比，要小得多的情形下，即：

则可以粗略地认为节点移动的距离Δx可以忽略，即认为节点是近似静止的，不移动的。在这个假设下，显然我们看到，两节点间的最短路径就是两节点的连线。再考虑到节点的发射功率限制，下一跳自然应选择邻居中最靠近连线的节点。

以上的简化模型实际上间接地论证了文献[6]的结论的正确性。

其次，我们综合面路由法、文献[6]提出的概率方法、以及我们这里的简化模型，发现在确定下一跳的节点时，选择“两节点连线附近节点”的选择策略，是这几种方法一致推荐的方法。这表明该方法是有效的，是好算法。

另外，我们引用文献[6]的结论，看到这个方法获得的最短路径是概率较大的最短路径。

3.4概率最短路径路由算法

综上所述，我们得到概率上最短路径的路由算法如下：

(1)在功率允许的情况下，直接沿着两节点的连线方向将包发到目标节点即可。

(2)在功率不允许的情况下，根据以下原则找多跳节点：

(a)沿着两节点的连线方向，找靠近连线最近的节点；

(b)如果所选节点失效(不在线)，则找次靠近连线的节点，以此类推。

(3)传递信息到找到的节点。

(4)循环以上方法，直到将信息传递到目标节点。

注意到，由于节点A和邻居节点B移动速度相对于电信号速率要慢得多，所以发包的时间Δt内，A、B的位置变化可以忽略不计，如图3所示。

图3　发包过程A、B有位移

这里提出的算法最大的特点是简单，丢包的可能性小，真正实现了最短路径传送。这个算法的时间复杂度为O(m*n)，m为平均邻居数，n为多跳次数。算法的效率高。

因此，对于全移动的Ad-Hoc网络来说，我们认为这是一个较好的路由算法。

4　实验结果及讨论

我们以多跳数为优化目标。实验随机产生50个节点的图2个，125节点的图2个，320节点的图2个。随机图接近均匀分布。每个图取2对节点，节点对取自网络周边上。表中的多跳数是2个图上4对节点的平均多跳数。我们设置网络覆盖的地理范围相同，节点数增加，从而节点密度增加，则适当调小节点的发射功率范围。节点功率范围分别约为网络半径的1/4，1/8，1/16。实验结果如表一所示。

表一　实验结果

实验结果表明，本文提出的概率算法在静态图上性能略差于贪心向前算法，接近贪心向前算法。但是，如果将图的动态性考虑进去，概率算法的确是好算法，贪心向前算法没有考虑概率因素。

5　结论与进一步的工作

本文研究了无线Ad-hoc网的路由问题。分析比较了目前为止的各种算法。提出了一个简单的路由算法。面路由法，文献[6]提出的概率方法，和我们这里的简化模型，都一致得到两节点连线附近的选择策略，表明该方法是有效的，是好算法。由于是概率上的最短路径，因此也是概率上的最小能量路径，也是最小多跳次数的路径，因为这几个参数是一致的[9][10]。

进一步的工作是研究概率算法的节能效能。另外，文献[7]指出基于Delaunay剖分图不适合于Ad Hoc网的建模。如果是这样，是否可把随机分布的点集模型（也就是Delaunay图）改为用文献[8]提出的随机弧长模型，这些都是进一步可做的工作。

[1]Muamer N.Mohammed,Norrozila Sulaiman,“Performance Analysis of DSR,AODV On-Demand Routing Protocols in Mobile Ad Hoc Networks”[J].Advanced Science Letters,2014(l):359-363.

[2]Liliana Enciso Quispe etc.,“Behavior of Ad Hoc routing protocols,Analysed for emergency and resue scenarios,on a real urban area”[J].Expert Systems with Applications,2014(41):2565-2573.

[3]I.Stojmenovic and X.Lin,“Power-aware Localized routing in Wireless Networks”[J].IEEE Trans.Parellels Distrib.Syst.,2001(11):1122-1133.

[4]J.Li,J.Jannotti etc.，”A scalable Location service for geographica Ad hoc routing”InProc.6thannual int. conf.on Mobile Compt.&Networking,ser.MobiCom’oo[M].New York:NY,USA:ACM,2000: 120-130.

[5]F.Cadgar,Kevin Curran etc.,“A survey of geographical Routing in Wireless Ad-hoc Networks”[J]. IEEE communications and Tutorials,2013(2):Second Quarter.

[6]F.Baccelli.K.Tchoumatehenko and S.Zuyev,“Markov Pths on the Possion–Delaunary Graph with Application to Routing in Mobile Networks”[J].Adv.Appl.Prob.(SGSA).2000(32):1-18.

[7]Fabian Kuhn etc.,“An Algorithmic Approach to Geographic Routing In Ad Hoc and Sensor Networks”[J].IEEE/ACM TRANACTION ON NETWORKING,2008(1):FEBRUARY.

[8]Mohammed Hessan Olya,“Applying Dijkstra algorithm for general shortest path problem with normal Probability distribution arc length”[J].J.Operational Research,2014(21):2.

[9]Lina Yuan,“Research on energy-saving strategies for Wireless Sensor Networks”[C]//2013年贵州省计算机学会年会论文集，2013.

[10]Ivan Stojmenovic,Xue Lin,“Power–Aware Localized Routing in Wireless Networks”[J].IEEE Trans. On Parallel and Distributed Systems,2001(11):Nov.

A New Routing Algorithm for Wireless Mobile Ad-hoc Network

JIANG Tao,HE Dao-de
（School of Information Engineering of Guizhou University of Engineering Science,Bijie, Guizhou551700,China）

Analyzing several main types of routing algorithm of wireless Ad-hoc network,we get proac⁃tive and reactive types,with emphasis on geographical routing algorithm.Analyzing types of routing algo⁃rithm of geographical routing the current research hotspot of the recent years,it concludes types of optyimiza⁃tiom target basing on routing,service quality and minimum energy.In this paper we have analyzed various routing methods of wireless Ad-hoc network，and proposed a new idea on probabilistic routing，and present a new method that is a better method by now.

Ad-hoc Network;Geographical Routing;Probabilistic Routing

TP391.4

A

2096-0239（2016）02-0150-05

（责编：彭麟淋责校：明茂修）

2016-01-25

江涛(1963-),男,贵州纳雍人,贵州工程技术应用学院信息工程学院副教授。研究方向：图算法。

贺道德(1979-),男，湖南常德人,贵州工程技术应用学院信息工程学院讲师。研究方向：网格与Web Service。