一種貪婪地理路由協議的改進算法

摘 要： 貪婪轉發策略廣泛應用于無線傳感網絡（WSNs）的地理路由協議中，但是，該協議存在數據包丟失嚴重以及在遭遇路由空洞時路由效率低下的不足。為此，提出一種貪婪地理路由協議的改進算法，記為GPSR?I算法。GPSR?I算法在選擇下一跳轉發節點時，利用節點離目的節點距離、方向以及節點密度信息計算度量值，然后依據該度量值決策下一跳轉發節點。仿真數據表明，與GPSR相比，GPSR?I算法能夠有效降低平均端到端傳輸時延、路由開銷，并提高了數據包傳輸率。

關鍵詞： 無線傳感網； 路由； GPSR； 度量值； 貪婪轉發

中圖分類號： TN915.04?34； TPT393 文獻標識碼： A 文章編號： 1004?373X（2016）11?0016?05

Abstract： 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.

Keywords： WSNs； routing； GPSR； measurements； greedy forwarding

0 引 言

無線傳感網絡（Wireless Sensor Networks，WSNs）被廣泛應用于各類行業，如環境監測、戰場勘察、健康醫療以及災難管理。由于這些應用的需求，多數節點借助定位技術獲取自己的物理位置。據此，基于地理位置路由協議廣泛應用于WSNs。由于貪婪轉發（Greedy Forward，GF）策略簡單、高效、易實現，受到廣泛關注[1]。

GF策略是利用距離信息轉發數據包。數據包攜帶節點（源節點）在需要向目的節點轉發數據包時，它就從其鄰居節點中選擇離目的節點最近的節點作為下一跳數據包轉發節點，并把數據包轉發至該節點，該過程一直重復，直到數據包傳輸至目的節點。由于GF策略在路由發現過程中，只需要鄰居節點和目的節點的位置信息，無需其他路由信息，并且避免復雜的路由查詢，簡單易實現。

然而，GF策略也存在不足之處。在路由過程中，數據包攜帶節點可能發現鄰居節點中沒有比自己離目的節點更近的節點，即出現路由空洞。在這種情況下，再也無法利用GF策略轉發數據包。為了解決GF策略的路由空洞問題，研究人員提出不少的改進算法[2?3]。這些算法或者是改進選擇下一跳轉發節點策略，或者是改進處理路由空洞的方案。實際上，解決路由空洞問題最有效的方式就是降低路由空洞的出現頻率，即在路由過程中有效地避開空洞。

為此，本文提出了一種貪婪地理路由協議的改進算法——GPSR?I算法。GPSR?I算法在數據轉發過程中采用兩種轉發模式：貪婪轉發和邊界轉發。在貪婪轉發時，數據包攜帶節點首先計算鄰居節點的貪婪度量值，其包含節點離目的節點距離、方向和密度信息。然后，從中選擇貪婪度量值最小的節點作為數據包下一跳轉發節點。當節點遭遇路由空洞時，就進入邊界轉發模式。在邊界轉發時，為了降低轉發跳數，節點計算鄰居節點的邊界度量值，并選擇邊界度量值大的節點轉發數據包，進而縮短路由路徑。仿真結果表明，提出的GPSR?I算法能夠有效縮短傳輸時延、提高數據包傳輸率。

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 約束條件

2.3 問題描述

GF策略屬于逐跳分布式轉發算法。數據包攜帶節點依據其一跳鄰居節點離目的節點的距離，從中選擇一個離目標節點最近的節點作為下一跳轉發節點，其目的在于降低傳輸跳數，縮短路徑。

GF策略簡單、易實現，但是其常遭遇路由空洞問題。即出現在鄰居節點中沒有比自己離目的節點更近的節點情況，在這種情況下，GF策略再也沒有辦法執行，無法選擇下一跳節點。通常，一旦出現路由空洞，常采用邊界模式轉發算法。

如圖1所示，節點遭遇了路由空洞，其鄰居節點內沒有比自己離目的節點更近的節點。在這種情況下，節點只能采用邊界轉發算法傳輸數據包。采用右手轉發模式，選擇路徑，當節點接收了數據包后，此時滿足貪婪轉發算法，隨后便重新啟用GF策略傳輸數據包，直到將數據包傳輸至目的節點

盡管邊界轉發能夠繞開路由空洞，但是邊界轉發算法往往增加了傳輸路徑的跳數，即邊界轉發算法產生的路徑不是最優的。這一方面占用過多的節點資源，提高了節點能量消耗；另一方面也增加了傳輸時延，最終降低了路由性能。

由第1節可知，已有不同的方案解決路由空洞，但是這些方案總是以降低某一性能來換取另一性能。實際上，解決路由空洞的方案應是盡量避免路由空洞的出現。為此，本文提出GPSR?I算法，從兩方面改進GPSR協議：首先降低出現路由空洞發生的概率，然后即使出現路由空洞，在邊界轉發算法中，選擇優質的轉發路徑，減少傳輸跳數，縮短時延。

3 GPSR?I算法

3.1 貪婪度量值

在GPSR?I算法中，選擇下一跳轉發節點與傳統的GF策略不同，不再只考慮節點離目的節點的距離，還考慮了節點密度以及方向信息。將這三項信息融合為一項指標，稱為貪婪度量值。數據包攜帶節點依據其鄰居節點的貪婪度量值，選擇貪婪度量值最小的節點作為下一跳節點。假定節點的貪婪度量值定義如下：

注意到式（4），將稱為角度因素。顯然，越小，節點離目的節點的垂直距離越小。式（4）中第三項表示節點的鄰居節點數，為網絡內總的節點數。反映了節點的周圍的節點密度情況，稱為密度因素。在選擇下一跳節點時，盡量從高密度區域內選擇下一跳轉發節點，降低發生路由空洞的概率。節點密度可依據在規定時間內，接收到HELLO消息的數量計算。

此外，分別為距離因素、角度因素、密度因素的權值系數。不同的環境對各因素影響程度不同，可利用權值系數體現。

3.2 邊界轉發

利用3.1節的度量值選擇下一跳轉發節點，可以降低出現路由空洞的概率，但是不可能完全避免路由空洞的出現。一旦源節點發現自己屬于路由空洞節點，就進入邊界轉發模式。為了縮短通信跳數，提高傳輸效率，提出的GPSR?I算法進入邊界轉發模式后，計算邊界度量值，并選擇邊界度量值大的節點作為下一跳轉發節點。

式中：的含義與式（4）相同；分別為距離因素、角度因素以及密度因素在邊界轉發中的權值，可依據不同環境設定權值。

源節點選擇邊界度量值最大的節點作為下一跳的轉發節點。由于路由空洞的存在，距離對轉發節點的選擇影響較小，而角度因素影響較大。大的角度可以快速繞開路由空洞，降低傳輸跳數。同時，盡量選擇密度較高的節點作為下一跳轉發節點。為此，系數分別為0.2，0.5，0.3。

如圖3所示，源節點要向目的節點傳輸數據包，發現自己為路由空洞節點。無法采用貪婪轉發算法，若采用GPSR的基于右手規則的邊界轉發，可依據路徑避開路由空洞。不難看出，此路徑跳數較多，不利于降低數據傳輸時延。而采用GPSR?I算法基于邊界度量值，源節點比較鄰居節點的邊界度量值，選擇邊界度量值大的節點作為轉發節點。依據式（7）可知，節點的邊界度量值最大，將其作為下一跳轉發節點，極大地降低了邊界轉發的跳數，提高了數據傳輸效率。

3.3 GPSR?I算法流程

本節從數據包攜帶節點角度描述數據包轉發流程。一旦接收了數據包，若自己不是目的節點，則需要尋找下一跳的轉發節點。因此，首先判斷自己是否為目的節點，若是目的節點就結束數據傳輸過程。否則，就需尋找下一跳轉發節點。先判斷自己是否為路由空洞節點，若是進入貪婪轉發模式，利用式（4）選擇下一跳轉發節點，否則就進入邊界轉發模式，利用式（7）選擇下一跳轉發節點。選好轉發節點后，就向其轉發數據，具體流程如圖4所示。

4 性能分析

利用Matlab R2012b建立仿真平臺。考慮1 000 m×1 000 m的方形區域，傳感節點數目=30，節點通信范圍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，A?GPSR以及I?GPSR協議。這主要是因為GPSR?I算法在選擇下一跳轉發節點時考慮了緩解數據包堵塞以及路由空洞等因素，同時，在邊界轉發時，融合角度因素，縮短了傳輸跳數。此外，平均端到端傳輸時延隨著節點的移動速度的增加，時延也隨之增加。原因在于移動速度的增加，加速了網絡拓撲的變化，進而增加了傳輸時延。

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 energy?efficient channel assignment mechanism for vehicular Ad Hoc networks [J]. Journal of supercomputing， 2012， 62（3）： 1241?1262.

[2] 羅四維，侯孟書，周益民.一種新的基于能量消耗速率模型的分簇路由協議[J].計算機科學，2012，39（6）：46?50.

[3] BANERJEE I， CHANAK P， RAHAMAN H， et al. 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 loca?lization 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]// Procee?dings of the 6th ACM International Symposium on Mobile Ad Hoc Networking and Computing. [S.l.]： ACM， 2005： 230?241.

[6] NAUMOV V， BAUMANN R， GROSS T. An evaluation of inter?vehicle 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 Compu?ting. [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] LI Yujun， 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 and Architectures for Parallel Processing. Taipei， China： Springer， 2009： 797?808.

[15] JOSHI G P， KIM S W. A distributed geo?routing algorithm for wireless sensor networks [J]. Sensors， 2009， 9（6）： 4083?4103.