一種貪婪地理路由協(xié)議的改進算法

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

關(guān)鍵詞： 無線傳感網(wǎng)； 路由； GPSR； 度量值； 貪婪轉(zhuǎn)發(fā)

中圖分類號： 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 引 言

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

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

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

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

1 相關(guān)工作

貪婪轉(zhuǎn)發(fā)被廣泛應用于地理信息路由[4?9]。依據(jù)這些路由協(xié)議的特性可分為三類：

（1） 基于邊界轉(zhuǎn)發(fā)的貪婪路由。利用邊界轉(zhuǎn)發(fā)策略處理路由空洞問題。例如，GPSR[4]（Greedy Perimeter Stateless Routing）利用GF策略轉(zhuǎn)發(fā)數(shù)據(jù)包。當遇到路由空洞時，就切入邊界轉(zhuǎn)發(fā)模式，并利用右手規(guī)則繞開空洞，直到繞開空洞重新進入GF模式。GOAFR+[10]，GRR[7]，GAR[11]，BVGF[12]均屬于這類協(xié)議。

（2） 基于鄰居節(jié)點選擇的貪婪路由。這類協(xié)議利用不同的指標選擇鄰居節(jié)點，進而完成數(shù)據(jù)包轉(zhuǎn)發(fā)。例如，地理能量感知路由GEAR（Geographical and Energy Aware Routing）[8]計算每個節(jié)點的轉(zhuǎn)發(fā)數(shù)據(jù)包成本，依據(jù)成本選舉下一跳的轉(zhuǎn)發(fā)節(jié)點。類似地，改進的貪婪轉(zhuǎn)發(fā)AGF（Advanced Greedy Forwarding）[6]也對GF進行了改進，在選擇下一跳轉(zhuǎn)發(fā)節(jié)點時，不僅考慮節(jié)點的位置，同時，還考慮了節(jié)點的移動方向以及速度信息。此外，文獻[13]提出了GF?RSSI策略，其利用RSSI信息選擇可靠鄰居節(jié)點，并據(jù)此產(chǎn)生下一跳轉(zhuǎn)發(fā)節(jié)點。

（3） 非地理位置的貪婪路由。該類路由無需節(jié)點的位置信息，例如，OVCR[14]，VAA[15]。它們給節(jié)點設置虛擬坐標，依據(jù)虛擬坐標轉(zhuǎn)發(fā)數(shù)據(jù)包。但是虛擬坐標增加了算法的復雜度，降低了算法的可擴展性。

本文提出的GPSR?I算法屬于第（2）類協(xié)議。首先，GPSR?I算法利用距離、方向以及節(jié)點密度信息計算度量值，選擇下一跳轉(zhuǎn)發(fā)；其次，在處理路由空洞時，也利用度量值選擇下一跳轉(zhuǎn)發(fā)節(jié)點，降低傳輸跳數(shù)。

2 約束條件及問題描述

2.1 約束條件

2.3 問題描述

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

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

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

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

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

3 GPSR?I算法

3.1 貪婪度量值

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

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

此外，分別為距離因素、角度因素、密度因素的權(quán)值系數(shù)。不同的環(huán)境對各因素影響程度不同，可利用權(quán)值系數(shù)體現(xiàn)。

3.2 邊界轉(zhuǎn)發(fā)

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

式中：的含義與式（4）相同；分別為距離因素、角度因素以及密度因素在邊界轉(zhuǎn)發(fā)中的權(quán)值，可依據(jù)不同環(huán)境設定權(quán)值。

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

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

3.3 GPSR?I算法流程

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

4 性能分析

利用Matlab R2012b建立仿真平臺?？紤]1 000 m×1 000 m的方形區(qū)域，傳感節(jié)點數(shù)目=30，節(jié)點通信范圍250 m，節(jié)點移動速度為10～100 m/s。信道帶寬為5 Mb/s，有5條CBR數(shù)據(jù)流，其中CBR數(shù)據(jù)包大小為1 024 B。每次實驗重復100次，取平均值作為最終數(shù)據(jù)。仿真時間為300 s。

為了更充分地分析路由性能，選擇傳統(tǒng)的GPSR[9]，基于角度方向信息的改進協(xié)議A?GPSR，基于雙手法則的改進協(xié)議I?GPSR與本文提出的GPSR?I算法進行比較。主要考查這些協(xié)議的平均端到端時延、數(shù)據(jù)包傳遞率以及路由開銷性能，其中平均端到端傳輸時延表示數(shù)據(jù)包從源節(jié)點傳輸至目的節(jié)點的平均時間；數(shù)據(jù)包傳遞率表示目的節(jié)點成功接收的數(shù)據(jù)包個數(shù)與源節(jié)點發(fā)送的數(shù)據(jù)包個數(shù)之比。數(shù)據(jù)包傳遞率越高，網(wǎng)絡傳輸越可靠。而路由開銷用在網(wǎng)絡內(nèi)路由包流量與總的信息包流量的比值表示。路由開銷越小，表明數(shù)據(jù)流量越大，性能越好。仿真結(jié)果如圖5～圖7所示。

4.1 平均端到端傳輸時延

四個協(xié)議的平均端到端傳輸時延如圖5所示。從圖5可知，提出的GPSR?I算法的時延低于GPSR，A?GPSR以及I?GPSR協(xié)議。這主要是因為GPSR?I算法在選擇下一跳轉(zhuǎn)發(fā)節(jié)點時考慮了緩解數(shù)據(jù)包堵塞以及路由空洞等因素，同時，在邊界轉(zhuǎn)發(fā)時，融合角度因素，縮短了傳輸跳數(shù)。此外，平均端到端傳輸時延隨著節(jié)點的移動速度的增加，時延也隨之增加。原因在于移動速度的增加，加速了網(wǎng)絡拓撲的變化，進而增加了傳輸時延。

4.2 數(shù)據(jù)包傳輸率

圖6描述了數(shù)據(jù)包傳輸率隨節(jié)點移動速度變化曲線。從圖6可知，提出的GPSR?I算法的數(shù)據(jù)包傳輸率優(yōu)于GPSR，I?GPSR以及A?GPSR協(xié)議。這主要歸功于GPSR?I算法高的通信成功率，在選擇下一跳節(jié)點時，有效降低遭遇路由空洞的概率，進而提高了傳輸數(shù)據(jù)包的數(shù)量。而A?GPSR和I?GPSR協(xié)議盡管考慮了方向、雙手法則，但它們考慮的因素過于片面，改善數(shù)據(jù)傳輸率具有局限性。此外，在節(jié)點移動速度較低時，A?GPSR協(xié)議的數(shù)據(jù)傳輸率優(yōu)于I?GPSR協(xié)議，而隨著速度的提升，I?GPSR協(xié)議數(shù)據(jù)傳輸率快速增加，反而優(yōu)于A?GPSR協(xié)議。這些變化原因在于A?GPSR協(xié)議主要利用依據(jù)節(jié)點的移動方向決策下一跳轉(zhuǎn)發(fā)節(jié)點，在節(jié)點移動速度較慢時，能夠改善路由性能。而I?GPSR協(xié)議是利用邊界轉(zhuǎn)發(fā)模式處理路由空洞問題，能夠有效應對節(jié)點的高速移動場景。

4.3 路由開銷

四個協(xié)議的路由開銷如圖7所示。從圖7可知，GPSR?I算法的路由開銷最低，并且隨節(jié)點速度變化波動小，在整個速度變化區(qū)間內(nèi)，保持低的路由開銷。而GPSR協(xié)議的路由開銷隨節(jié)點移動速度增加而上升，I?GPSR協(xié)議的路由開銷隨速度變化緩慢但比較大，原因在于I?GPSR協(xié)議利用雙手法則決策路由，開銷較大。此外，注意到圖7在節(jié)點移動速度較緩慢時，四個協(xié)議的路由開銷性能相近。但是隨著節(jié)點移動速度的加快，GPSR協(xié)議的路由開銷迅速增加，這主要是因為節(jié)點速度的加快，加速了網(wǎng)絡拓撲結(jié)構(gòu)的變化，增加鏈路斷裂的概率，增加了路由開銷。而提出的GPSR?I算法在邊界轉(zhuǎn)發(fā)模式下，降低遍歷傳輸跳數(shù)，控制了路由開銷，對速度變化具有穩(wěn)健性。

5 結(jié) 語

路由空洞一直是基于貪婪轉(zhuǎn)發(fā)的地理路由協(xié)議中的一個難題，受到研究人員的密切關(guān)注。為此，本文提出了貪婪地理路由協(xié)議的改進算法——GPSR?I。GPSR?I算法在貪婪轉(zhuǎn)發(fā)模式時，計算鄰居節(jié)點的貪婪度量值，其蘊含了距離、方向以及密度信息，并擇優(yōu)選擇貪婪度量值小的節(jié)點作為下一跳轉(zhuǎn)發(fā)節(jié)點；當節(jié)點遇到路由空洞時，采用邊界轉(zhuǎn)發(fā)模式，并計算鄰居節(jié)點的邊界度量值，選擇邊界度量值大的節(jié)點作為下一跳，降低傳輸跳數(shù)。仿真結(jié)果表明，提出的GPSR?I算法能夠提高數(shù)據(jù)包傳輸率，降低開銷，縮短了傳輸時延。

參考文獻

[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] 羅四維，侯孟書，周益民.一種新的基于能量消耗速率模型的分簇路由協(xié)議[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.