孫　磊，張和偉，馮鐵軍，郭繼聯(lián)

（1.棗莊學(xué)院 計(jì)算機(jī)系，山東 棗莊　277160；2.棗莊科技職業(yè)學(xué)院 電氣工程系，山東 滕州　277500）

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

孫磊1，張和偉1，馮鐵軍1，郭繼聯(lián)2

（1.棗莊學(xué)院 計(jì)算機(jī)系，山東 棗莊277160；2.棗莊科技職業(yè)學(xué)院 電氣工程系，山東 滕州277500）

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

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

0　引　言

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

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

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

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

1　相關(guān)工作

貪婪轉(zhuǎn)發(fā)被廣泛應(yīng)用于地理信息路由［4-9］。依據(jù)這些路由協(xié)議的特性可分為三類(lèi)：

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

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

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

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

2　約束條件及問(wèn)題描述

2.1約束條件

假定無(wú)線網(wǎng)絡(luò)內(nèi)有N個(gè)同構(gòu)節(jié)點(diǎn)，節(jié)點(diǎn)的覆蓋半徑為R。設(shè)定所有節(jié)點(diǎn)在同一平面，用單位圓圖表征網(wǎng)絡(luò)拓?fù)鋱DT：

式中：V為網(wǎng)絡(luò)內(nèi)的節(jié)點(diǎn)集合，表示圖T中的節(jié)點(diǎn)；E是網(wǎng)絡(luò)內(nèi)兩節(jié)點(diǎn)間的通信鏈路，為圖T的邊。

網(wǎng)絡(luò)內(nèi)每個(gè)節(jié)點(diǎn)可利用GPS定位技術(shù)獲取自身的位置信息。同時(shí)，每個(gè)節(jié)點(diǎn)周期地交互HELLO消息，能夠獲取鄰居節(jié)點(diǎn)的位置信息。

2.2定義

鄰居集：假定節(jié)點(diǎn)的通信半徑為R，那么該節(jié)點(diǎn)的鄰居集是指那些在二維平面上與節(jié)點(diǎn)歐式距離小于R的節(jié)點(diǎn)集合。

若節(jié)點(diǎn)i的鄰居集表示為ni：

路由空洞節(jié)點(diǎn)：GF策略中，路由空洞節(jié)點(diǎn)是指那些在傳輸路徑上的節(jié)點(diǎn)，其鄰居集的所有節(jié)點(diǎn)離目的節(jié)點(diǎn)的距離都大于該節(jié)點(diǎn)自己離目的節(jié)點(diǎn)的距離。在這種情況下，利用GF策略無(wú)法找到下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)。若節(jié)點(diǎn)i滿(mǎn)足式（3），則稱(chēng)為路由空洞節(jié)點(diǎn)。

式中D表示目的節(jié)點(diǎn)。

2.3問(wèn)題描述

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

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

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

圖1　邊界轉(zhuǎn)發(fā)模式示意圖

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

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

3　GPSR-I算法

3.1貪婪度量值

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

式中：di表示節(jié)點(diǎn)i離目的節(jié)點(diǎn)的距離；ds表示數(shù)據(jù)包攜帶節(jié)點(diǎn)（源節(jié)點(diǎn)）s離目的節(jié)點(diǎn)的距離。為了簡(jiǎn)化描述，將稱(chēng)為距離因素。θ表示節(jié)點(diǎn)i與目的節(jié)點(diǎn)D連線向量和源節(jié)點(diǎn)s與目的節(jié)點(diǎn)D連線向量的夾角，如圖2所示。

圖2　度量值計(jì)算示意圖

依據(jù)角度計(jì)算公式，可估計(jì)θ值：

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

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

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

假定節(jié)點(diǎn)i的邊界度量值FS_mi定義如下：

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

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

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

圖3　GPSR-I算法的邊界轉(zhuǎn)發(fā)模式

3.3GPSR-I算法流程

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

圖4　GPSR-I算法數(shù)據(jù)包轉(zhuǎn)發(fā)流程圖

4　性能分析

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

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

4.1平均端到端傳輸時(shí)延

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

圖5　平均端到端傳輸時(shí)延

圖6　數(shù)據(jù)包傳輸率

圖7　路由開(kāi)銷(xiāo)

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

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

4.3路由開(kāi)銷(xiāo)

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

5　結(jié)　語(yǔ)

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

［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］羅四維，侯孟書(shū)，周益民.一種新的基于能量消耗速率模型的分簇路由協(xié)議［J］.計(jì)算機(jī)科學(xué)，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，F(xiàn)ENG 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，F(xiàn)ENG 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

國(guó)家自然科學(xué)基金（61462069）

孫磊（1979—），男，碩士，講師。主要研究領(lǐng)域?yàn)殡娮油ㄐ偶夹g(shù)應(yīng)用。

張和偉（1980—），男，研究生，講師。主要研究領(lǐng)域?yàn)橛?jì)算機(jī)科學(xué)與應(yīng)用。

馮鐵軍（1973—），男，研究生，助教。主要研究領(lǐng)域?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)技術(shù)。

郭繼聯(lián)（1966—），男，研究生，副教授。主要研究領(lǐng)域?yàn)閿?shù)據(jù)挖掘和網(wǎng)絡(luò)安全。