一种贪婪地理路由协议的改进算法

孙　磊，张和伟，冯铁军，郭继联

（1.枣庄学院 计算机系，山东 枣庄　277160；2.枣庄科技职业学院 电气工程系，山东 滕州　277500）

一种贪婪地理路由协议的改进算法

孙磊1，张和伟1，冯铁军1，郭继联2

（1.枣庄学院 计算机系，山东 枣庄277160；2.枣庄科技职业学院 电气工程系，山东 滕州277500）

贪婪转发策略广泛应用于无线传感网络（WSNs）的地理路由协议中，但是，该协议存在数据包丢失严重以及在遭遇路由空洞时路由效率低下的不足。为此，提出一种贪婪地理路由协议的改进算法，记为GPSR-I算法。GPSR-I算法在选择下一跳转发节点时，利用节点离目的节点距离、方向以及节点密度信息计算度量值，然后依据该度量值决策下一跳转发节点。仿真数据表明，与GPSR相比，GPSR-I算法能够有效降低平均端到端传输时延、路由开销，并提高了数据包传输率。

无线传感网；路由；GPSR；度量值；贪婪转发

0　引　言

无线传感网络（W ireless Sensor Networks，WSNs）被广泛应用于各类行业，如环境监测、战场勘察、健康医疗以及灾难管理。由于这些应用的需求，多数节点借助定位技术获取自己的物理位置。据此，基于地理位置路由协议广泛应用于WSNs。由于贪婪转发（Greedy Forward，GF）策略简单、高效、易实现，受到广泛关注［1］。

GF策略是利用距离信息转发数据包。数据包携带节点（源节点）在需要向目的节点转发数据包时，它就从其邻居节点中选择离目的节点最近的节点作为下一跳数据包转发节点，并把数据包转发至该节点，该过程一直重复，直到数据包传输至目的节点。由于GF策略在路由发现过程中，只需要邻居节点和目的节点的位置信息，无需其他路由信息，并且避免复杂的路由查询，简单易实现。

然而，GF策略也存在不足之处。在路由过程中，数据包携带节点可能发现邻居节点中没有比自己离目的节点更近的节点，即出现路由空洞。在这种情况下，再也无法利用GF策略转发数据包。为了解决GF策略的路由空洞问题，研究人员提出不少的改进算法［2-3］。这些算法或者是改进选择下一跳转发节点策略，或者是改进处理路由空洞的方案。实际上，解决路由空洞问题最有效的方式就是降低路由空洞的出现频率，即在路由过程中有效地避开空洞。

为此，本文提出了一种贪婪地理路由协议的改进算法——GPSR-I算法。GPSR-I算法在数据转发过程中采用两种转发模式：贪婪转发和边界转发。在贪婪转发时，数据包携带节点首先计算邻居节点的贪婪度量值，其包含节点离目的节点距离、方向和密度信息。然后，从中选择贪婪度量值最小的节点作为数据包下一跳转发节点。当节点遭遇路由空洞时，就进入边界转发模式。在边界转发时，为了降低转发跳数，节点计算邻居节点的边界度量值，并选择边界度量值大的节点转发数据包，进而缩短路由路径。仿真结果表明，提出的GPSRI算法能够有效缩短传输时延、提高数据包传输率。

1　相关工作

贪婪转发被广泛应用于地理信息路由［4-9］。依据这些路由协议的特性可分为三类：

（1）基于边界转发的贪婪路由。利用边界转发策略处理路由空洞问题。例如，GPSR［4］（Greedy Perimeter Stateless Routing）利用GF策略转发数据包。当遇到路由空洞时，就切入边界转发模式，并利用右手规则绕开空洞，直到绕开空洞重新进入GF模式。GOAFR+［10］，GRR［7］，GAR［11］，BVGF［12］均属于这类协议。

（2）基于邻居节点选择的贪婪路由。这类协议利用不同的指标选择邻居节点，进而完成数据包转发。例如，地理能量感知路由GEAR（Geographical and Energy Aware Routing）［8］计算每个节点的转发数据包成本，依据成本选举下一跳的转发节点。类似地，改进的贪婪转发AGF（Advanced Greedy Forwarding）［6］也对GF进行了改进，在选择下一跳转发节点时，不仅考虑节点的位置，同时，还考虑了节点的移动方向以及速度信息。此外，文献［13］提出了GF-RSSI策略，其利用RSSI信息选择可靠邻居节点，并据此产生下一跳转发节点。

（3）非地理位置的贪婪路由。该类路由无需节点的位置信息，例如，OVCR［14］，VAA［15］。它们给节点设置虚拟坐标，依据虚拟坐标转发数据包。但是虚拟坐标增加了算法的复杂度，降低了算法的可扩展性。

本文提出的GPSR-I算法属于第（2）类协议。首先，GPSR-I算法利用距离、方向以及节点密度信息计算度量值，选择下一跳转发；其次，在处理路由空洞时，也利用度量值选择下一跳转发节点，降低传输跳数。

2　约束条件及问题描述

2.1约束条件

假定无线网络内有N个同构节点，节点的覆盖半径为R。设定所有节点在同一平面，用单位圆图表征网络拓扑图T：

式中：V为网络内的节点集合，表示图T中的节点；E是网络内两节点间的通信链路，为图T的边。

网络内每个节点可利用GPS定位技术获取自身的位置信息。同时，每个节点周期地交互HELLO消息，能够获取邻居节点的位置信息。

2.2定义

邻居集：假定节点的通信半径为R，那么该节点的邻居集是指那些在二维平面上与节点欧式距离小于R的节点集合。

若节点i的邻居集表示为ni：

路由空洞节点：GF策略中，路由空洞节点是指那些在传输路径上的节点，其邻居集的所有节点离目的节点的距离都大于该节点自己离目的节点的距离。在这种情况下，利用GF策略无法找到下一跳转发节点。若节点i满足式（3），则称为路由空洞节点。

式中D表示目的节点。

2.3问题描述

GF策略属于逐跳分布式转发算法。数据包携带节点依据其一跳邻居节点离目的节点的距离，从中选择一个离目标节点最近的节点作为下一跳转发节点，其目的在于降低传输跳数，缩短路径。

GF策略简单、易实现，但是其常遭遇路由空洞问题。即出现在邻居节点中没有比自己离目的节点更近的节点情况，在这种情况下，GF策略再也没有办法执行，无法选择下一跳节点。通常，一旦出现路由空洞，常采用边界模式转发算法。

如图1所示，节点x遭遇了路由空洞，其邻居节点内没有比自己离目的节点D更近的节点。在这种情况下，节点x只能采用边界转发算法传输数据包。采用右手转发模式，选择x→a→b→c→d路径，当节点d接收了数据包后，此时满足贪婪转发算法，随后便重新启用GF策略传输数据包，直到将数据包传输至目的节点D。

图1　边界转发模式示意图

尽管边界转发能够绕开路由空洞，但是边界转发算法往往增加了传输路径的跳数，即边界转发算法产生的路径不是最优的。这一方面占用过多的节点资源，提高了节点能量消耗；另一方面也增加了传输时延，最终降低了路由性能。

由第1节可知，已有不同的方案解决路由空洞，但是这些方案总是以降低某一性能来换取另一性能。实际上，解决路由空洞的方案应是尽量避免路由空洞的出现。为此，本文提出GPSR-I算法，从两方面改进GPSR协议：首先降低出现路由空洞发生的概率，然后即使出现路由空洞，在边界转发算法中，选择优质的转发路径，减少传输跳数，缩短时延。

3　GPSR-I算法

3.1贪婪度量值

在GPSR-I算法中，选择下一跳转发节点与传统的GF策略不同，不再只考虑节点离目的节点的距离，还考虑了节点密度以及方向信息。将这三项信息融合为一项指标，称为贪婪度量值GF_m。数据包携带节点依据其邻居节点的贪婪度量值，选择贪婪度量值最小的节点作为下一跳节点。假定节点i的贪婪度量值GF_mi定义如下：

式中：di表示节点i离目的节点的距离；ds表示数据包携带节点（源节点）s离目的节点的距离。为了简化描述，将称为距离因素。θ表示节点i与目的节点D连线向量和源节点s与目的节点D连线向量的夹角，如图2所示。

图2　度量值计算示意图

依据角度计算公式，可估计θ值：

此外，α，β，γ分别为距离因素、角度因素、密度因素的权值系数。不同的环境对各因素影响程度不同，可利用权值系数体现。

3.2边界转发

利用3.1节的度量值选择下一跳转发节点，可以降低出现路由空洞的概率，但是不可能完全避免路由空洞的出现。一旦源节点发现自己属于路由空洞节点，就进入边界转发模式。为了缩短通信跳数，提高传输效率，提出的GPSR-I算法进入边界转发模式后，计算边界度量值FS_m，并选择边界度量值大的节点作为下一跳转发节点。

假定节点i的边界度量值FS_mi定义如下：

式中：di，ds，θ，ni，N的含义与式（4）相同；α1，β1，γ1分别为距离因素、角度因素以及密度因素在边界转发中的权值，可依据不同环境设定权值。

源节点选择边界度量值最大的节点作为下一跳的转发节点。由于路由空洞的存在，距离对转发节点的选择影响较小，而角度因素影响较大。大的角度可以快速绕开路由空洞，降低传输跳数。同时，尽量选择密度较高的节点作为下一跳转发节点。为此，α1，β1，γ1系数分别为0.2，0.5，0.3。

如图3所示，源节点x要向目的节点D传输数据包，发现自己为路由空洞节点。无法采用贪婪转发算法，若采用GPSR的基于右手规则的边界转发，可依据x→a→b→d路径避开路由空洞。不难看出，此路径跳数较多，不利于降低数据传输时延。而采用GPSR-I算法基于边界度量值，源节点x比较邻居节点的边界度量值，选择边界度量值大的节点作为转发节点。依据式（7）可知，节点d的边界度量值最大，将其作为下一跳转发节点，极大地降低了边界转发的跳数，提高了数据传输效率。

图3　GPSR-I算法的边界转发模式

3.3GPSR-I算法流程

本节从数据包携带节点角度描述数据包转发流程。一旦接收了数据包，若自己不是目的节点，则需要寻找下一跳的转发节点。因此，首先判断自己是否为目的节点，若是目的节点就结束数据传输过程。否则，就需寻找下一跳转发节点。先判断自己是否为路由空洞节点，若是进入贪婪转发模式，利用式（4）选择下一跳转发节点，否则就进入边界转发模式，利用式（7）选择下一跳转发节点。选好转发节点后，就向其转发数据，具体流程如图4所示。

图4　GPSR-I算法数据包转发流程图

4　性能分析

利用Matlab R2012b建立仿真平台。考虑1 000 m× 1 000 m的方形区域，传感节点数目N=30，节点通信范围Rs=250 m，节点移动速度为10～100 m/s。信道带宽为5 Mb/s，有5条CBR数据流，其中CBR数据包大小为1 024 B。每次实验重复100次，取平均值作为最终数据。仿真时间为300 s。

为了更充分地分析路由性能，选择传统的GPSR［9］，基于角度方向信息的改进协议A-GPSR，基于双手法则的改进协议I-GPSR与本文提出的GPSR-I算法进行比较。主要考查这些协议的平均端到端时延、数据包传递率以及路由开销性能，其中平均端到端传输时延表示数据包从源节点传输至目的节点的平均时间；数据包传递率表示目的节点成功接收的数据包个数与源节点发送的数据包个数之比。数据包传递率越高，网络传输越可靠。而路由开销用在网络内路由包流量与总的信息包流量的比值表示。路由开销越小，表明数据流量越大，性能越好。仿真结果如图5～图7所示。

4.1平均端到端传输时延

四个协议的平均端到端传输时延如图5所示。从图5可知，提出的GPSR-I算法的时延低于GPSR，AGPSR以及I-GPSR协议。这主要是因为GPSR-I算法在选择下一跳转发节点时考虑了缓解数据包堵塞以及路由空洞等因素，同时，在边界转发时，融合角度因素，缩短了传输跳数。此外，平均端到端传输时延随着节点的移动速度的增加，时延也随之增加。原因在于移动速度的增加，加速了网络拓扑的变化，进而增加了传输时延。

图5　平均端到端传输时延

图6　数据包传输率

图7　路由开销

4.2数据包传输率

图6描述了数据包传输率随节点移动速度变化曲线。从图6可知，提出的GPSR-I算法的数据包传输率优于GPSR，I-GPSR以及A-GPSR协议。这主要归功于GPSR-I算法高的通信成功率，在选择下一跳节点时，有效降低遭遇路由空洞的概率，进而提高了传输数据包的数量。而A-GPSR和I-GPSR协议尽管考虑了方向、双手法则，但它们考虑的因素过于片面，改善数据传输率具有局限性。此外，在节点移动速度较低时，A-GPSR协议的数据传输率优于I-GPSR协议，而随着速度的提升，I-GPSR协议数据传输率快速增加，反而优于A-GPSR协议。这些变化原因在于A-GPSR协议主要利用依据节点的移动方向决策下一跳转发节点，在节点移动速度较慢时，能够改善路由性能。而I-GPSR协议是利用边界转发模式处理路由空洞问题，能够有效应对节点的高速移动场景。

4.3路由开销

四个协议的路由开销如图7所示。从图7可知，GPSR-I算法的路由开销最低，并且随节点速度变化波动小，在整个速度变化区间内，保持低的路由开销。而GPSR协议的路由开销随节点移动速度增加而上升，I-GPSR协议的路由开销随速度变化缓慢但比较大，原因在于I-GPSR协议利用双手法则决策路由，开销较大。此外，注意到图7在节点移动速度较缓慢时，四个协议的路由开销性能相近。但是随着节点移动速度的加快，GPSR协议的路由开销迅速增加，这主要是因为节点速度的加快，加速了网络拓扑结构的变化，增加链路断裂的概率，增加了路由开销。而提出的GPSR-I算法在边界转发模式下，降低遍历传输跳数，控制了路由开销，对速度变化具有稳健性。

5　结　语

路由空洞一直是基于贪婪转发的地理路由协议中的一个难题，受到研究人员的密切关注。为此，本文提出了贪婪地理路由协议的改进算法——GPSR-I。GPSR-I算法在贪婪转发模式时，计算邻居节点的贪婪度量值，其蕴含了距离、方向以及密度信息，并择优选择贪婪度量值小的节点作为下一跳转发节点；当节点遇到路由空洞时，采用边界转发模式，并计算邻居节点的边界度量值，选择边界度量值大的节点作为下一跳，降低传输跳数。仿真结果表明，提出的GPSR-I算法能够提高数据包传输率，降低开销，缩短了传输时延。

［1］MISRA S，KRISHNA P V，SARITHA V.LACAV：an energyefficient channel assignment mechanism for vehicular Ad Hoc networks［J］.Journalofsupercomputing，2012，62（3）：1241-1262.

［2］罗四维，侯孟书，周益民.一种新的基于能量消耗速率模型的分簇路由协议［J］.计算机科学，2012，39（6）：46-50.

［3］BANERJEE I，CHANAK P，RAHAMAN H，etal.Effective fault detection and routing scheme for wireless sensor networks［J］. Computers&electrical engineering，2014，40（2）：291-306.

［4］SEADA K，HELMY A，GOVINDAN R.On the effect of localization errors on geographic face routing in sensor networks ［C］//Proceedings of the 3rd International Symposium on Information Processing in Sensor Networks.［S.l.］：ACM，2004：71-80.

［5］LEE S，BHATTACHARJEE B，BANERJEE S.Efficient geographic routing in multi-hop wireless networks［C］//Proceedings of the 6th ACM International Symposium on Mobile Ad Hoc Networking and Computing.［S.l.］：ACM，2005：230-241.

［6］NAUMOV V，BAUMANN R，GROSST.An evaluation of intervehicle Ad Hoc networks based on realistic vehicular traces ［C］//Proceedings of the 7th ACM International Symposium on Mobile Ad Hoc Networking and Computing.［S.l.］：ACM，2006：108-111.

［7］KERMARREC A M，TAN G.Greedy geographic routing in large-scale sensor networks：a minimum network decomposition approach［C］//Proceedings of the Eleventh ACM International Symposium on Mobile Ad Hoc Networking and Computing.［S.l.］：ACM，2010：161-170.

［8］YU Y，GOVINDAN R，ESTRIN D.Geographical and energy aware routing：a recursive data dissemination protocol for wireless sensor networks［R］.Los Angeles：UCLA Computer Science Department，2011：36-42.

［9］LIYujun，YANG Y，LU Xianliang.Rules of designing routing metrics for greedy，face，and combined greedy-face routing［J］. IEEE transactions on mobile computing，2010，9（4）：582-595.

［10］KUHN F，WATTENHOFER R，ZHANG Y，et al.Geometric Ad-Hoc routing：of theory and practice［C］//Proceedings of the Twenty-second Annual Symposium on Principles of Distributed Computing.［S.l.］：ACM，2003：63-72.

［11］LIU W J，FENG K T.Greedy routing with anti-void traversal for wireless sensor networks［J］.IEEE transactions on mobile computing，2009，8（7）：910-922.

［12］XING Guoliang，LU Chenyang，PLESS Robert，et al.Impact of sensing coverage on greedy geographic routing algorithms ［J］.IEEE transactions on parallel and distributed systems，2006，17（4）：348-360.

［13］PHAM N N，YOUN J，WON C.A comparison of wireless sensor network routing protocols on an experimental testbed ［C］//Proceedings of 2006 IEEE International Conference on Sensor Networks，Ubiquitous，and Trustworthy Computing. Taichung，China：IEEE，2006，2：276-281.

［14］HSU M T，LIN Y S，CHANG Y S，et al.Reliable greedy forwarding in obstacle-aware wireless sensor networks［C］//Proceedings of the 9th International Conference on Algorithms andArchitectures for Parallel Processing.Taipei，China：Springer，2009：797-808.

［15］JOSHI G P，KIM SW.A distributed geo-routing algorithm for wireless sensor networks［J］.Sensors，2009，9（6）：4083-4103.

An im p roved algorithm of greedy geographic routing p rotocol

SUN Lei1，ZHANG Hewei1，FENG Tiejun1，GUO Jilian2
（1.Department of Computer，Zaozhuang University，Zaozhuang 277160，China；2.Department of Electrical Engineering，Zaozhuang Vocational College of Science and Technology，Tengzhou 277500，China）

The greedy forwarding strategy is widely used in geographic routing protocol of wireless sensor networks （WSNs）.Since the protocol has the problem of low routing efficiency in cases of routing void and serious packet loss，an improved algorithm of greedy perimeter stateless routing（GPSR-I）is proposed.The distance and direction from the target node and node density information are used to calculate the measurements when the GPSR-I algorithm is used to select the next-hop forwarding node，and then the next-hop forwarding node is determined.The simulation results show that，in comparison with the GPSR algorithm，the GPSR-I algorithm can effectively reduce the average end-to-end transmission delay and routing overhead，and improve the packet transmission rate.

WSNs；routing；GPSR；measurements；greedy forwarding

TN915.04-34；TPT393

A

1004-373X（2016）11-0016-05

10.16652/j.issn.1004-373x.2016.11.005

2015-09-15

国家自然科学基金（61462069）

孙磊（1979—），男，硕士，讲师。主要研究领域为电子通信技术应用。

张和伟（1980—），男，研究生，讲师。主要研究领域为计算机科学与应用。

冯铁军（1973—），男，研究生，助教。主要研究领域为计算机网络技术。

郭继联（1966—），男，研究生，副教授。主要研究领域为数据挖掘和网络安全。