2008一种基于两跳邻居信息的贪婪地理路由算法_王建新

一种基于两跳邻居信息的贪婪地理路由算法

王建新,赵湘宁,刘辉宇

(中南大学信息科学与工程学院,湖南长沙410083)

摘 要: 基于地理信息的路由算法由于其高效、低路由开销和良好的可扩展性等特点,在无线传感器网络中得到比较广泛的应用.许多采用贪婪策略作为其基本数据转发机制的地理路由算法都不可避免会遇到路由空洞现象.针对这个问题,本文提出了一种基于掌握两跳邻居节点位置信息的贪婪地理路由算法 Greedy -2算法.该算法能够使节点提前意识到路由空洞的存在,从而尽可能使数据包及时绕开空洞边界节点,减少路由空洞发生的概率,提高分组到达率.对于Greedy -2算法仍然遭遇路由空洞现象的情况,文章提出了一种基于两跳邻居信息的平面化算法PATN,该算法不需要增加额外的平面化开销,即可将网络平面化以采取边缘恢复机制,在UDG 网络中保证数据可靠传输.仿真结果表明,与基于一跳邻居节点位置信息的贪婪算法相比,Greed y -2算法可以明显减少路由空洞现象发生的次数,在分组到达率和数据传送的路由跳数方面都有着更好的性能.Greedy -2算法与PATN 规则结合后的GPSR -2算法也比GP -SR 算法有着更优化的路由跳数.

关键词: 无线传感器网络;地理路由;贪婪算法;两跳邻居信息;路由空洞;平面化

中图分类号: TP393 文献标识码: A 文章编号: 0372-2112(2008)10-1903-07

A Greedy G eograph ic Routing Algorithm Based on 2-Hop Neigh bors

W ANG Jian -xin,ZHAO Xiang -ning,LI U Hu-i yu

(Sc hool o f In formation Scie nce and Enginee ring ,Central South U ni versity,Changsha,Hunan 410083,China )

Abstract: Geographic routing is widely used in wireless sensor networks du e to its great efficiency,low ro u ting overhead and

good scalability.However,the problem that mo s t of the geo graphic routing algorithms which adopt greedy algorithm as their basic routing strategies have to face is the routing void phenomena .Aiming at this problem,this paper presents a new geo graphic rout -ing algorithm,Greedy algorithm based on the geographic information of 2-hop neighbors (Greedy -2).Greedy -2algorithm makes nodes be aware of the exis tence of voids before the packet reaches a region where the Greedy forwarding fails,so that the packet can bypass the dead -end node ahead of time to reduce the probability of encountering the routing voids.PATN ,a Planarization Algo -rithm based on Two -hop Neighbors,is also introduced.PATN ensures the success of perimeter routing thro ugh the planarization w ithout extra overhead,and guarantees delivery in UDG networks when Greedy -2algorithm fails.Extensive simulation further show s that Greedy -2algorithm can significantly decrease the routing void phenomena.It obtains better performance than Greedy algorithm bas ed on 1-hop neighbors in aspects of the packet delivery rate and the length of routing path.G PSR -2,which combines Greedy -2and PATN algorithms,has less average length of routing path than GPSR.

Key words: wireless sensor networks;geographic rou ting ;greedy algorithm;information of 2-hop neighbors;routing void;

planarization

1 引言

无线传感器网络(Wirele ss Sensor Ne tworks,WSN)是

由部署在监测区域内大量的廉价微型传感器节点,通过

无线通信方式形成的一个多跳的自组织网络系统[1,2].

基于地理位置信息的路由协议已经成为在传感器网络

中广泛应用的路由协议,而且许多地理路由算法都采用

了贪婪算法为其转发数据的基本机制.在实际的传感器网络中,由于网络部署不均匀或是部分传感器节点由于故障或能量耗尽而失效,还有一些环境如沼泽、水塘本身就不适合部署传感器网络,会形成网络中的 空洞 .在依据贪婪算法转发数据包的过程中,数据包可能会到达没有任何邻居节点比自身更接近目的点的区域,导致数据无法继续传输,这种现象称为

收稿日期:2007-09-11;修回日期:2008-03-12基金项目:国家自然科学基金(No.60673164);湖南省杰出青年基金(No.06JJ 10009);高等学校博士学科点专项科研基金(No.20060533057);973前期研究专项(No.2008CB317107);新世纪优秀人才支持计划(No.NECT -05-0683) 第10期

2008年10月电 子 学 报ACTA ELECTRO NICA SINICA Vol.36 No.10Oc t. 2008

路由空洞[3,4].

为了解决运用贪婪算法时不可避免会遇到的路由空洞现象,目前的地理路由算法通常采取以下三种恢复机制以继续数据包的传输.

泛洪恢复机制

泛洪机制是应用最早且最为简单的解决路由空洞的方法,当节点运用贪婪算法遇到路由空洞的时候,就将数据包广播给它所有邻居节点[3],如此反复,直到数据达到目的节点或者达到数据包的最大跳数.但是泛洪方式极易产生消息的 重叠 (overlap)和 内爆 (implo-sion)[5],引起网络资源的大量浪费,开销巨大.

回退恢复机制

回退机制是当节点发现自己没有下游节点能将分组传送到目的节点的时候,就向上游节点发送一份延迟时间为无穷大的反向压力信标消息,以表明遇到了路由空洞.上游节点就将到该节点的延迟时间设为无穷,并转向选择另一个下游节点来传送分组.如果所有的下游节点都遇到路由空洞,就继续向再上游的节点发送反向压力信标.文献[6,7]中都用到了这种机制.但是在网络空洞较多的情况下,频繁的回退也会使网络的开销增大,路由长度增加,效率降低.

边缘恢复机制

边缘恢复机制[8]是在平面图的基础上,采用贪婪 面 贪婪的方法进行数据转发.如果贪婪算法遇到路由空洞,则转入边缘恢复模式,遍历最接近的平面子图,直到到达比路由空洞节点更接近于目的点的节点为止,然后继续贪婪路由.文献[9~12]都用到了这种机制.

边缘恢复机制使用图论的最短路径和连通的概念来发现路由,是目前应用较多的一类恢复机制,但是它也具有一定的局限性,最主要方面在于为了避免在沿边缘转发时产生路由环路(routing loop),它需要平面化网络拓扑的支持.目前应用较广的平面化算法主要有以下几种:GG和RNG算法[13,14]、GG/MW和RNG/MW算法[15]、CLDP算法[16].

CLDP(Cross-Link Detection Protocol)算法是至今为止唯一的一种能够适应实际网络复杂环境的平面化算法,保证边缘恢复机制在实际复杂的网络中能够正确地运行.该算法对网络中的每条链路都发送探测包,等待探测包返回之后,确定在去除某条边不影响网络连通性的情况下才将该边删除.CLDP的开销相当大,平均每个节点在网络生存时间里大约需要发送几百个到上千个数据包来进行和维持平面化过程[17].为了降低开销, LCR[18]算法提出了先进行基于GG图的边缘转发,直到遇到路由回路时,才进行局部CLDP平面化的方法来继续数据传输.

无论上述何种平面化方式,都需要额外的开销来建立和维持平面化.每个节点在网络初始都要进行平面化,并且在整个网络生存时间中都需要维持一张网络平面图.

事实上,无论采取何种恢复机制,它们的开销相对于贪婪算法而言都是相当大的.针对这个问题,本文对贪婪算法进行改进,旨在使其尽量减少遇到路由空洞的概率,从而减少采取恢复机制的次数,从总体上提高路由的效率.本文提出了基于掌握两跳邻居节点位置信息的贪婪地理路由算法(Greedy-2算法).Greedy-2算法使每个节点通过多一次的信息交换,掌握两跳范围内邻居节点的地理位置信息.Greedy-2算法在选择下一跳的时候,可以计算两跳范围内的邻居节点位置以优化路由选择,使节点能够提前意识到路由空洞的存在,从而尽可能及时绕开路由空洞节点,大大减少路由空洞发生的概率,显著提高分组到达率,并且降低了路由跳数.

对于Greedy-2算法仍然遭遇路由空洞现象的情况,本文提出了一种基于两跳邻居信息的平面化算法PA TN.该算法不需要增加额外的平面化开销,即可将网络平面化以采取边缘恢复机制,继续数据的传输. Greedy-2算法与P ATN规则结合后的GPSR-2算法比GP-SR[9]算法有着更优化的路由性能以及更低的算法开销.

2 Greedy-2路由算法

为了描述方便,我们首先给出以下定义:

定义1 N(i)-k表示由所有节点i的k跳邻居节点组成的集合,即N(i)-k集合中的所有点到达节点i 恰好需要k跳.

定义2 通过掌握k跳范围内邻居节点的地理位置信息作为路由选择依据的贪婪算法,称为Greedy-k算法(其中k=1,2,3 ).

假设i是当前节点,Greedy-1算法是在集合N(i)-1中选择一个离目的点最近的节点作为下一跳.在找不到距离目的点更近的邻居节点时,就采用泛洪、回退或边缘转发等恢复机制来寻找到达目的节点的路由.Greedy-1算法在网络中存在着较多较大空洞或者网络节点密度比较稀疏的情况下,遇到路由空洞的概率很高,频繁地采用恢复机制来寻找路由,使得网络的开销增大,路由效率降低.

Greedy-1算法只能在分组到达真正空洞边界时才能意识到已经出现了路由空洞现象,此时只能采取恢复机制.针对Greedy-1算法这点不足,如果采用通过邻居节点之间的信息交换,使每个节点掌握k跳范围内邻居节点的地理位置信息的方法,那么在进行贪婪算法时,就可以利用k跳邻的信息优化路由选择,使节点能够提前意识到空洞的存在,从而尽可能及时绕开空洞边界节点,减少路由空洞发生的概率.

1904 电 子 学 报2008年

本章接下来将着重对Greedy -2算法进行探讨,并与Greedy -1算法进行路由性能上的比较.Gree dy -2算法让每一个节点通过两次信息交换,分别将自己和自己一跳邻居节点的地理位置信息广播给自己的一跳邻居节点.这样每个节点都掌握两跳范围内邻居节点的位置信息,并得到N (i )-1集合和N (i )-2集合.在进行贪婪路由选择的时候可以根据两跳邻的信息优化路由选择,降低遇到路由空洞的概率

.我们首先考察以下这个路由实例.如图1所示,源节点S 打算发送数据包至目的点D.图中灰色阴影的区域为空洞区域.若依照Greedy -1算法转发数

据包,S 只考虑集合N (S)-1中的节点,那么S 会将数据包转发给A 点,因为在集合N (S )-1中A 点是距离目的点D 最近的点.但是在集合N (A )-1中没有节点比A 自己距离D 点更近.此时Greedy -1算法就会遭遇路由空洞现象.

同样这种情况,在运用Greedy -2算法时,点S 依据集合N (S)-2计算出C 是集合N (S )-2中离D 最近的节点,且C 比自己离D 更近,于是将分组转发给集合N (S)-1中可以直接到达节点C 的节点,这样就有可能成功绕开A 这个路由空洞点,避免路由空洞现象的发生.

为了充分利用两跳邻居的信息优化贪婪路由选择,我们提出以下Greedy -2算法的路由规则.

Greedy -2路由规则 假设当前节点为c,目的点为d,上一跳节点为p ,Greedy -2算法选择下一跳节点的规则描述如下:

首先在集合N (c)-1中查找是否存在目的点d,若存在,直接将分组发送给d.

在集合N (c)-2中选择距离目的节点最近的节点(假设为j ).

如果j 到d 的距离比c 到d 的距离小,就找到集合N (c)-1中可以直接到达节点j 的节点i ,如果i 满足下列两个条件中的任何一个,就将i 作为下一跳节点.

(a)j 即为d;(b)i 不在集合N (p )-1中,且i 到d 的距离小于p 到d 的距离.

如果找不到合适的i,在集合N (c)-2中选择离d 点次近的节点(设为j ).

重复步骤 ,直到找到合适的i 作为下一跳.

如果当集合N (c)-2中的节点全部遍历完之后仍然未找到符合条件的i ,表示Greedy -2算法遇到了路由空洞,采取边缘恢复机制.

3 Greedy -2算法仿真模拟及性能分析

为了验证Greedy -2算法的路由性能,我们通过仿真模拟,将其与Greedy -1算法进行比较和分析.算法性能的评估标准为:

分组到达率:计算成功到达目的节点的数据分组数占总共发送分组数的比率.

平均路径跳数:计算成功到达目的节点的数据分组从源节点到目的节点经过的路径跳数的平均值.我们采用网络仿真软件NS -2(network simulator)作为仿真平台.传感器网络模型的主要参数如下:在一个长1000m 、宽1000m 的地域范围内,随机散布500~3000个传感器节点,节点平均度的变化范围为3~18.网络满足UDG 条件,MAC 层采用802 11协议,无线传输半径为40m.在200s 的仿真时间里,随机选择节点对发送2000个数据包.每组数据都是由5个随机生成的网络测得数据并取其均值而得.

为了说明Greedy -2算法可以有效避开路由空洞,在比较分析Greedy -2算法和Greedy -1算法性能时,我们在这两种贪婪路由规则遇到路由空洞时就将数据包丢弃,不采用恢复机制.

图2给出节点随机分布网络中Greedy -2算法与Greedy -1算法在分组到达率上的性能比较.从图2可以清楚地看出:Greedy -2的性能较之Greedy -1有了很大的改善,显著提高了分组到达率.这说明Greedy -2算法有效地避免了绝大多数路由空洞现象的发生,及时绕开了路由空洞边界节点,找到正确的路由.特别在网络节点密度比较稀疏(即节点的平均度大约在4~10之间)、网络连通性不太好的时候,Greedy -2有非常明显的改进效果.随着节点密度增大,网络连通性逐渐变好,Greedy -1的分组到达率上升,而Greedy -2的分组到达率也迅速接近100%.在节点平均度为8左右的时候,Greedy -2的分组到达率就已经能达到100%,而Greedy -1在节点平均

1905

第 10 期王建新:一种基于两跳邻居信息的贪婪地理路由算法

度达到12以上,才能基本保证数据的可靠传输.

图3给出了Greedy-1算法与Greedy-2算法在平均路径跳数方面的性能比较.Greedy-1和Greedy-2曲线分别表示两种算法在节点随机分布网络中成功发送分组的平均路径跳数.Greedy-2cp曲线表示选取用Greedy-1算法可以发送成功的节点对,运用Greedy-2算法测得的平均跳数.同时以AOD V算法测得的跳数为最优跳数作为参照.AODV算法[19]是一种按需路由算法,路由路径是通过泛洪的方式而得的,因此在路由跳数上是最少的.

观察Greedy-1和Greedy-2曲线,在较低密度的网络中,Greedy-1比Greedy-2的平均路径跳数短.这是因为此时Greedy-1算法发生路由空洞的概率很高,基本上只能使相距比较近的两个点之间的通信成功,对比Greedy-2算法就可以使距离稍远一些的两个点之间的通信成功.随着网络密度的增加,两种算法都可以逐渐使较远距离节点间的传输成功率增加,因此平均路径跳数逐渐上升.在两种算法分别都能保证100%的分组到达率以后,路由跳数随着网络密度的增大有下降的趋势,此时Greedy-2的跳数就比Greedy-1少一些,体现了其在路由优化方面的性能优势.

在Greedy-2cp曲线与Greedy-1曲线的对比中可看出,在成功收发节点对相同的条件下,随着网络密度的变化,在跳数上Greedy-2算法始终比Greedy-1少,尤其在节点平均度在8~14区间内优势更为明显.Greedy-2算法在两跳范围内选择离目的点最近的节点,会比Greedy-1一跳一跳的选择在跳数上优化一些.但是当网络密度很大时,一跳距离基本上会接近节点的最大通信距离,此时两种算法获得的跳数会比较接近.

基于掌握k跳邻居节点信息的Greedy-k(k=1,2,3 )算法,随着k值增大,每个节点掌握的周围邻居节点信息就越多,在路由选择的时候就能够进行更为全局化的分析,因此得出的路由也将更为优化.具体表现为路由空洞发生的概率将会越少,分组到达率会越高,路由跳数也会更接近最优跳数等.然而随着k越大, Greedy-k比Greedy-(k-1)在路由上优化的效果将越来越不明显.相应地,每个节点获取k跳邻居节点信息的开销也会随之增大,在节点数为n的网络中,这一过程消息复杂度约为O(kn).同时,在节点平均度为d的网络中,存储k跳邻居信息的量级约为O(d k),随着k增大,每个节点的存储量也将呈指数增长.

从图2可以看出,Greedy-2算法在网络节点平均度为4 6时遭遇路由空洞的概率仅为17%.从图3中可以清楚地看出Greedy-2算法的平均路径跳数已经非常接近最优跳数.折衷网络性能和算法开销,我们选择Greedy-2算法.

GPSR算法在Greedy-1算法遇到路由空洞的时候,将网络进行平面化,并采取边缘恢复机制,直到绕过空洞,到达比路由空洞节点更接近于目的节点为止,就转回Greedy-1算法继续进行路由.对于Greedy-2算法仍然遇到路由空洞的时候,我们采取与GPSR相同的边缘恢复机制.然而在进行平面化的过程中,由于我们已经掌握了两跳邻居信息,就无需花费额外的平面化开销即可建立正确的平面化子图,支持边缘恢复机制成功的运行.下面将详细介绍基于两跳邻居信息的平面化算法PA TN以及结合Greedy-2和P ATN的路由算法GPSR-2.

4 基于两跳邻居信息的平面化算法PATN

当贪婪算法遇到路由空洞的时候,转入边缘恢复机制,遍历最接近的平面子图,继续数据包的传输.在采取边缘恢复机制之前,需要先将网络进行平面化,消除交叉链路,并在网络的每个节点中都维持着平面拓扑图,避免采取边缘转发时遇到路由回路.

本文提出了一种基于两跳邻居信息的平面化算法(Planarization Algorithm based on Two-hop Neighbors, PA TN).PA TN通过简单的本地化算法进行网络平面化,避免了额外的平面化开销.

为了描述方便,我们首先给出以下定义:

定义3 P(i)-1表示由节点i的所有1跳邻居节点组成的集合.P(i)-2表示由节点i的所有两跳可达的邻居节点组成的集合.

PA TN平面化规则描述如下:

PAT N规则1 当前节点u,对处于集合{P(u)-1 P(u)-2}中的邻居v(如图4所示),找到在集合P(u)-1中可直接到达v的点w,从路由中将三角形 uvw三条边uw、wv和uv中最长的边删除.考虑到一种情况,如果uw、wv和uv三条边一样长,就约定删除有着较小节点id号的两个点之间的连线.图4中,由于在 uvw中uv最长,所以将边uv删除.

PAT N规则2 在按照PATN规则1执行完平面化过程之后,对于点A,如果在集合N(A)-2中存在某点C(如图5所示),仍然能够分别通过集合N(A)-1中两

1906 电 子 学 报2008年

个不同的点B 和D 可达,就分别计算边AB 和边CD ,边AD 和边BC 是否相交.如果存在相交的情况,就将相交的

两条边中较长的一边从路由中删除.如果相交的两条边长度相等,就约定删除有着最小id 号的节点所在的那条边.

在网络满足UDG 条件假设下,通过P ATN 规则1可以得到正确的平面化子图.

在不满足UDG 条件的实际网络中,往往存在一些小障碍物,使原本处于通信范围内的两点之间无法直接通信,如图6中的点w 和点v.GG 和RNG 平面化算法运用在非UDG 网络中的结果往往造成网络的不连通.例如图6中,按照GG 或者RNG 算法,u 计算出w 和v 之间的距离小于最大通信距离,就以为它们之间是连通的,仍然会将边uv 删除,结果造成网络不连通,u 和w 都无法与v 通信.GG/MW 和RNG/MW 算法要删除边uv,先考察在u 和v 的GG 和R NG 区域里是否存在一个点,该点对u 和v 都可见.图6中w 点对u 可见,对v 不可见,于是uv 就得以保留.然而,通过P ATN 规则1,这种情况的判断就变得更为简单,这三个点中对于任何一个点而言,都不存在集合{P(i)-1 P(i )-2}(i =u,v,w )中的点,故而不会删除任何边,保证了网络的连通性.

由于P ATN 规则判断两点之间是否连通,并不是通过它们的位置信息计算是否处于通信范围之内而得的,而是通过获取两跳邻居信息时,邻居之间的信息交换而得的实际连通信息,故而可以减少受到非UDG 网络中障碍物带来的误差的影响.

因此,我们可以得出以下结论:在非UDG 网络中,通过P ATN 规则1和规则2平面化的结果比GG 、R NG 、GG/MW 、R NG/MW 等平面化算法有着更高的正确性.

综上所述,PATN 算法利用已掌握的两跳邻居信息,不需要增加额外的开销即可对网络进行平面化.在网络满足UDG 条件的前提下,PATN 算法可以完全正确地进行平面化,保证边缘转发的成功及数据的可靠传输,平面化的结果与RNG/MW 平面化算法相同,但是开销比RNG/MW 平面化算法小.在非UDG 网络中,PATN 平面

化算法也能够对绝大多数复杂的交叉链路状况进行正

确的平面化,比RNG/MW 平面化的结果有着更高的准确性,确保在实际复杂的网络环境中有着较高的边缘转发成功率.

5 GPSR -2算法仿真模拟及性能分析

将Greedy -2算法与P ATN 规则结合,在Greedy -2算法遇到路由空洞的时候,就利用已掌握的两跳邻居信息,运用PA TN 算法进行网络平面化,并采取边缘恢复机制继续数据的传输,我们称之为GPSR -2算法,并将其与GPSR 算法进行性能比较,其中GPSR 采用RNG/MW 的平面化方式.

仿真环境设置与第三章相同.由于两种算法在UDG 网络中都能保证数据的可靠传输,因此仅采用平均路径跳数评价协议性能.

5 1 GPSR -2算法的性能

考察网络中存在不同大小和不同数量的空洞情况下,GPSR 算法与GPSR -2算法的平均路径跳数.仿真结果如图7所示.

(1)空洞大小对平均路径跳数的影响

考察当网络存在不同大小空洞的情况下,两种算法的平均路径跳数对比.我们在节点随机分布的网络中,人为设置一个空洞,空洞大小分别为200m 200m 、250m 250m 和300m 300m.尽管在UDG 网络中PATN 平面化的结果与RNG/MW 相同,两种算法在进行边缘转发时跳数相差不大.但是从图7(a )中可以清楚地看出,

1907

第 10 期王建新:一种基于两跳邻居信息的贪婪地理路由算法

GPSR-2比GPSR在平均路径跳数方面的优势,在节点密度比较低的网络中,平均路径跳数少了5跳以上,尤其当网络空洞边长增大时,跳数上的优势更为明显,原因主要有两个: Greedy-2算法在空洞增大时仍然保证了比较高的分组到达率,而Greedy-1算法的分组到达率却下降的比较明显,大大增加了采取边缘恢复机制的次数. 边缘恢复机制绕着空洞周边转发数据,跳数会随着网络空洞边长增大而增加.特别是按照右手法则选择绕洞的路径,将有一半的几率会选择绕着较远的半边走,当网络空洞边长增大时,这种错误方向选择带来的跳数上的消耗也随之明显增加.

(2)空洞数量对平均路径跳数的影响

在节点随机分布的网络中,人为增加空洞数量,考察两种算法分别在低密度(节点平均度为8)和高密度(节点平均度为18)的环境中的平均路径跳数.其中空洞数量分别为0个、2个、5个、10个,大小为50m 50m,空洞随机分布,部分空洞区域有可能重叠.结果如图7 (b)所示,随着网络空洞数量增加,路由过程中遇到路由空洞的几率也大大增加,频繁的采用边缘恢复机制绕着空洞周边走使得路由跳数增长.然而由于Greedy-2算法比Greedy-1算法大大提高了分组到达率,减少了采取边缘恢复机制的次数,所以空洞个数的增加对GPSR-2算法的路由跳数的影响并没有如GPSR算法一样显著.在低密度网络中,当网络空洞数量为10个的时候, GPSR-2算法比GPSR算法在跳数上能够相差近10跳左右,即使在高密度网络中也能相差5跳左右.

5 2 算法开销

在算法复杂度方面,由于Greedy-2算法利用两跳邻居信息进行下一个转发节点的选择,其复杂度比Greedy-1算法高.在平面化的过程中,P ATN与RNG/MW 的算法复杂度基本相同.

下面选取节点的消息负载作为指标,将GPSR-2算法与GPSR算法进行比较.

基于地理位置信息的路由算法需要掌握邻居节点的位置信息,因此邻居之间需要发送信息包告知对方自己的位置.Greedy-2算法掌握两跳邻居节点的信息时,需要多一次的交换过程,把自己已掌握的所有邻居的位置告诉给自己的邻居.在节点数为n的网络中,这一过程的消息复杂度大约为O(2n).在平面化过程的开销方面,PA TN平面化算法利用已掌握的两跳邻居节点位置信息即可进行网络平面化,不需要增加额外的开销.这样,GPSR-2的消息复杂度就为O(2n).

对于GPSR算法而言,执行贪婪算法之前每个节点发送一次报文与邻居之间交换地理位置信息,这一过程消息复杂度大约为O(n).平面化的开销方面选取在UDG网络中与PATN算法结果相同的RNG/MW平面化算法作为对比.该算法在平面化的过程中,对于网络中每一条边是否保留,该边的两个节点之间都至少需要进行两次信息交换,平面化过程的消息复杂度大约为O(2e),e为网络中边的个数.在节点平均度为d的网络中,2e=dn.这样,GPSR总的消息复杂度大约为O(n +dn).由此可见,GPSR-2算法的消息负载小于GPSR,随着网络密度的增大,GPSR-2在算法开销方面的优势将更为明显.

6 结论

本文针对地理路由算法中易出现的路由空洞问题,提出了一种基于掌握两跳邻居节点信息的贪婪地理路由算法 Greedy-2算法.该算法能够使节点提前意识到路由空洞的存在,从而尽可能使数据包及时绕开空洞边界节点,减少路由空洞发生的概率,提高分组到达率.对于Greedy-2算法仍然遭遇路由空洞现象的情况,文章提出了一种基于两跳邻居信息的平面化算法PA TN,该算法不需要增加额外的平面化开销,即可将网络平面化以采取边缘恢复机制继续数据的传输.PATN算法在网络满足UDG条件的前提下,可以完全正确地进行平面化,保证边缘恢复机制的成功及数据的可靠传输,平面化的结果与R NG/MW平面化算法相同,但是开销比RNG/MW平面化算法小.在非UDG网络中,PA TN平面化算法也能够对绝大多数复杂的交叉链路状况进行正确的平面化,比RNG/MW平面化的结果有着更高的准确性,确保在实际复杂的网络环境中有着较高的边缘转发成功率.仿真结果表明,与Greedy-1相比,Greedy-2算法在分组到达率和数据传送的路由跳数方面都有着更好的性能,Greedy-2算法与P ATN规则结合后的GPSR-2算法也比GPSR算法在有着更优化的路由跳数.

参考文献:

[1]任丰原,黄海宁,林闯.无线传感器网络[J].软件学报,

2003,14(7):1282-1291.

Ren FY,Huang HN,Lin C.Wireless sensor netw orks[J].Jour-nal of Software,2003,14(7):1282-1291.(in Chinese)

[2]崔莉,鞠海玲,苗勇等.无线传感器网络研究进展[J].计

算机研究与发展,2005,42(1):163-174.

Cui Li,Ju Hailing,M iao Yong,L i T ianpu,Liu Wei,Z hao Ze.

Overview of wireless sensor networks[J].Journal of Computer Resear ch and D evelopment,2005,42(1):163-174.(in Ch-i nese)

[3]G Finn.Routing and addressing problems in large metropolitan-

scale internet works[R].V irginia:Information Sciences Ins t-i tute,1988.

[4]KARP B.Greedy perimeter state routing[R].V i rg inia:U SC/

Information Sciences Institute,1998.

1908 电 子 学 报2008年

[5]Heinzelman WR,Kulik J,Balakrishnan H.Adaptive protocols

for information dissemi nation in wireless sens or networks[A].

Proceedings of the ACM M obiCom 99[C].Seattle:ACM Press,1999.174-185.

[6]He T,Stankovic J A,Lu C,Abdelzaher T F.SPEED:a stateless

protoco l for rea-l time commu nication in sensor networks[A].

In:Proc23rd Int l Conf on Distribu ted Computing Sy s tems

[C].Los Alamitos,U SA:IEEE Computer Society,2003.46-

55.

[7]De Couto DSJ,Robert M orris.Lo cation proxies and intermed-i

ate node forwarding for practical geographic forwarding[R].

Boston:MIT Laboratory for Compu ter Science,2001.

[8]Evangelos Kranakis,Harvinder Si ngh,Jorge d3016640b52acfc788ebc902pass

routing on geometric networks[A].In Proceedi ngs of the11th Canadian Conference on Computational Geometry[C].V an-couver:CiteSeer.IST Press,1999.51-54.

[9]B Karp,HT Kung.GPSR:greedy perimeter stateless routing for

w i reless sensor networks[A].In Pro ceedings of the6th Annual ACM/IEEE International Conference on Mobile Compu ting and Networking[C].Boston:ACM Press,2000.243-254.

[10]Pro s enjit Bose,Pat M orin,Ivan Stojmenovic,Jorge Urrutia.

Routing with guaranteed delivery in ad hoc wireless networks

[A].In Proc.ACM DIALM Workshop[C].Seattle:ACM

Press,1999.48-55.

[11]Fabian Kuhn,Roger Wattenhofer,Yan Zhang,Aaron

Zo llinger.Geometric ad-hoc ro u ting:of theory and practice

[A].In Proceedings of PODC2003[C].Boston:ACM

Press,2003.63-72.

[12]B L eong,S Mitra,B.L iskov.Path vector face routing:geo-

graphic routi ng with local face information[A].In Proceedi ngs of ICNP2005[C].Bo s ton:IEEE Press,2005.147-158. [13]KR G abriel,RR Sokal.A new statistical approach to geograph-

ic variation analysis[J].Systematic Z oology,1969,18(3):259 -278.

[14]G T oussaint.The relative neighborhood graph of a finite planar

set[J].Pattern Reco gnition,1980,12(4):261-268.

[15]B K arp.Challenges in geographic routing:sparse networks,ob-

stacles,and traffic provisioning[R].Piscataway:DIM ACS Workshop on Pervasive Networki ng,2001.

[16]Y J K im,R Go vindan,B Karp,S Shenker.Geographic routing

made practical[A].In Proceedings of N SDI2005[C].CA: ACM Press,2005.217-230.

[17]Y J K im,R Go vindan,B Karp,S Shenker.On the pitfalls of

geographic face routing[A].In Proceedings of DIAL-M-POM C2005[C].Cologne:ACM Press,2005.34-43. [18]Y J K im,R Go vindan,B Karp,S d3016640b52acfc788ebc902zy cross-link re-

moval for georaphic routing[A].Proceeding s of the4th Inter-national Conference on Embedded Networked Sensor Systems

[C].Boulder:ACM Press,2006.112-124.

[19]Charles E Perkins,Elizabeth M Belding Royer,Samir R Das.

Ad hoc on-demand distance vector(AODV)routing[EB/ OL].d3016640b52acfc788ebc902/rfc/rfc3561.txt,2003-07.

作者简介:

王建新 男,1969年12月生于湖南邵阳.

2001年毕业于中南大学,获计算机应用技术专业

博士学位.现任中南大学信息科学与工程学院计

算机理论与软件系主任,教授、博士生导师.主要

研究领域为计算机网络、网络优化理论、计算机

优化算法.

E-mail:jxwang@d3016640b52acfc788ebc902

赵湘宁 女,1983年1月出生于福建福州.

2005年毕业于中南大学电子信息工程系.现为中

南大学通信与信息系统专业硕士研究生,主要从

事无线传感器网络的路由算法方向的研究.

E-mail:oceanfly130@d3016640b52acfc788ebc902

1909

第 10 期王建新:一种基于两跳邻居信息的贪婪地理路由算法

本文来源：https://www.bwwdw.com/article/81uq.html