劉壯，馮欣，張昕，劉妍，張婧，張劍飛

（長(zhǎng)春理工大學(xué)　計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，長(zhǎng)春　130022）

基于興趣梯度和能量梯度改進(jìn)的GPSR路由算法

劉壯，馮欣，張昕，劉妍，張婧，張劍飛

（長(zhǎng)春理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，長(zhǎng)春130022）

針對(duì)貪婪周邊無(wú)狀態(tài)路由（GPSR）算法中能耗不均衡和高能耗問題，提出了一種基于興趣梯度和能量梯度的改進(jìn)的GPSR路由算法。首先，在查詢消息沿路由路徑的傳輸過程中，根據(jù)匯聚節(jié)點(diǎn)與事件區(qū)域節(jié)點(diǎn)發(fā)生數(shù)據(jù)內(nèi)容的匹配程度，確立興趣閾值和能量閾值；然后，當(dāng)路由路徑中的一些節(jié)點(diǎn)接近閾值，網(wǎng)絡(luò)將運(yùn)用右手法則和遞歸貪婪算法提前找出一條新的路由路徑到目標(biāo)區(qū)域，從而使節(jié)點(diǎn)負(fù)載相對(duì)均衡。仿真實(shí)驗(yàn)結(jié)果表明，改進(jìn)的算法減少網(wǎng)絡(luò)能耗和延長(zhǎng)網(wǎng)絡(luò)的生存周期。

GPSR；興趣梯度，能量梯度；網(wǎng)絡(luò)生存周期

無(wú)線傳感器網(wǎng)絡(luò)是由大量的廉價(jià)傳感器節(jié)點(diǎn)組成，節(jié)點(diǎn)之間通過自組織的無(wú)線通信方式進(jìn)行感知、采集和處理監(jiān)測(cè)區(qū)域中被感知對(duì)象的信息，以多跳的方式將數(shù)據(jù)發(fā)送給終端用戶［1］。無(wú)線傳感器網(wǎng)絡(luò)集成許多科學(xué)技術(shù)，如傳感器技術(shù)、信息融合技術(shù)和信息處理技術(shù)，并且廣泛應(yīng)用在環(huán)境監(jiān)測(cè)、軍事研究、工業(yè)生產(chǎn)、醫(yī)療衛(wèi)生、搶險(xiǎn)救災(zāi)等領(lǐng)域［2］。無(wú)線傳感器網(wǎng)絡(luò)具有網(wǎng)絡(luò)靈活性、可擴(kuò)展性、易部署、流動(dòng)性和廉價(jià)性等特點(diǎn)［3］。

在基于地理位置的路由協(xié)議中，每個(gè)節(jié)點(diǎn)都知道自身和它鄰居節(jié)點(diǎn)的地理位置信息，當(dāng)消息傳輸時(shí)，節(jié)點(diǎn)的位置信息通過數(shù)據(jù)包的方式利用貪婪算法傳送給下一跳鄰居節(jié)點(diǎn)［4］。如果中繼節(jié)點(diǎn)無(wú)法找出比自身節(jié)點(diǎn)更近的目標(biāo)節(jié)點(diǎn)的節(jié)點(diǎn)，將產(chǎn)生路由空洞。針對(duì)這個(gè)問題，Brad Karp等人［5］提出GPSR（貪婪周邊無(wú)狀態(tài)路由協(xié)議），該協(xié)議主要是通過鄰居節(jié)點(diǎn)形成的平面網(wǎng)絡(luò)利用周邊無(wú)狀態(tài)模型將數(shù)據(jù)包傳輸給目標(biāo)節(jié)點(diǎn)。

GPSR協(xié)議避免了在節(jié)點(diǎn)中建立、維護(hù)和存儲(chǔ)路由表，并且數(shù)據(jù)傳輸延遲小，然而GPSR也存在一些缺點(diǎn)。Nithyanandan L等人［6］提出一種基于能量選擇的最佳路徑算法，旨在改善GPSR中網(wǎng)絡(luò)數(shù)據(jù)的不一致性，并且可以確保在不勻稱的無(wú)線傳感器網(wǎng)絡(luò)中能量均衡的可行性。Shanmuga Raja B等人［7］也采納能量最佳路徑算法，用來(lái)確保節(jié)點(diǎn)之間信息的有效性和節(jié)能性，從而延長(zhǎng)網(wǎng)絡(luò)生存周期。劉宇等人［8］提出一種基于鄰居節(jié)點(diǎn)的動(dòng)態(tài)路由負(fù)載平衡的改進(jìn)算法，可以解決由路由空洞造成的網(wǎng)絡(luò)周期的減少的問題。重點(diǎn)研究節(jié)點(diǎn)能耗的不均衡分布問題并提出一種基于能量梯度的改進(jìn)GPSR路由算法，通過提前設(shè)置的興趣閾值和能量閥值調(diào)節(jié)傳感器的工作狀態(tài)，從而減少節(jié)點(diǎn)無(wú)效，延長(zhǎng)網(wǎng)絡(luò)的周期和提高數(shù)據(jù)傳輸效率。

1　相關(guān)工作

GPSR是一種經(jīng)典的地理位置路由協(xié)議算法，廣泛應(yīng)用在Ad-hoc和無(wú)線傳感器網(wǎng)絡(luò)中，該算法包含兩種形式的數(shù)據(jù)傳輸方法：貪婪轉(zhuǎn)發(fā)和邊界轉(zhuǎn)發(fā)。

1.1貪婪轉(zhuǎn)發(fā)

在GPSR中，源節(jié)點(diǎn)打包目標(biāo)節(jié)點(diǎn)的位置信息，并將信息傳輸給已知位置的鄰居節(jié)點(diǎn)，并且最佳的下一跳應(yīng)該是最接近自身的鄰居節(jié)點(diǎn)，根據(jù)這一原理，數(shù)據(jù)以多跳的方式傳輸?shù)絽R聚節(jié)點(diǎn)［9］。貪婪轉(zhuǎn)發(fā)的具體過程如圖1所示。小虛線圓圈代表節(jié)點(diǎn)x的通信半徑，節(jié)點(diǎn)D代表匯聚節(jié)點(diǎn)，節(jié)點(diǎn)x將節(jié)點(diǎn)y作為下一跳傳輸節(jié)點(diǎn)，此時(shí)節(jié)點(diǎn)y是通過貪婪方法尋找的最接近節(jié)點(diǎn)D的節(jié)點(diǎn)，循環(huán)直到數(shù)據(jù)傳送給節(jié)點(diǎn)D。

圖1　貪婪轉(zhuǎn)發(fā)（y是x最近D的鄰居節(jié)點(diǎn)）

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

在貪婪轉(zhuǎn)發(fā)中，如果節(jié)點(diǎn)不能找到離目標(biāo)結(jié)點(diǎn)較近的下一個(gè)節(jié)點(diǎn)，為避免路由空洞產(chǎn)生，GPSR將運(yùn)用周邊無(wú)狀態(tài)路由解決這一問題［10］。在此過程中，為描述網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，將構(gòu)造平面圖并確保圖的任何兩邊不交叉。如圖2所示，x比其鄰居節(jié)點(diǎn)w和y更接近目標(biāo)節(jié)點(diǎn)D，設(shè)置D為圓中心，D與x的距離作為圓的半徑，可以看到，有兩條路由路徑到達(dá)節(jié)點(diǎn)D：（x→y→z→D）和（x→w→v→D），然而，根據(jù)貪婪算法，節(jié)點(diǎn)x不能傳輸數(shù)據(jù)到節(jié)點(diǎn)y 和w，從而形成路由空洞。

圖2　貪婪轉(zhuǎn)發(fā)失敗

如果中繼節(jié)點(diǎn)發(fā)現(xiàn)路由空洞，它可以利用右手法則找到一個(gè)新的路由路徑。右手法則如圖3所示，從節(jié)點(diǎn)y到節(jié)點(diǎn)x，下一條邊連接頂點(diǎn)x和頂點(diǎn)y，方向從x到y(tǒng)，以逆時(shí)針旋轉(zhuǎn)的方式選擇另一條邊，然后遍歷封閉的多邊形區(qū)域。在圖2中，當(dāng)節(jié)點(diǎn)x發(fā)現(xiàn)路由空洞時(shí)，將通過右手法則形成路由路徑x→w→v→D→z→y→x，邊界轉(zhuǎn)發(fā)完成。

圖3　右手法則

在GPSR算法中，傳感器節(jié)點(diǎn)選擇路由路徑僅需知道自身、鄰居節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)的地理位置，而不需要維持整個(gè)網(wǎng)絡(luò)的拓?fù)鋱D，從而減少了連接能耗。同時(shí)，采用貪婪算法可以減少路由路徑跳數(shù)和縮短數(shù)據(jù)傳輸中路由路徑步數(shù)，進(jìn)而可以減少整個(gè)無(wú)線傳感器網(wǎng)絡(luò)中的能耗和提高路由路徑質(zhì)量的效率，并且延長(zhǎng)網(wǎng)絡(luò)的生存周期。

2　改進(jìn)算法

2.1興趣梯度和能耗梯度

在無(wú)線傳感器網(wǎng)絡(luò)應(yīng)用中，傳感器節(jié)點(diǎn)隨機(jī)部署，節(jié)點(diǎn)能量有限，因此，減少能耗和延長(zhǎng)網(wǎng)絡(luò)生存周期成為關(guān)鍵問題。為解決這一問題，提出一種基于興趣梯度和能量梯度改進(jìn)的GPSR路由算法。

在改進(jìn)算法中，當(dāng)查詢路徑建立后，在數(shù)據(jù)傳輸?shù)倪^程中，興趣閾值Ithreshold根據(jù)匯聚節(jié)點(diǎn)與事件區(qū)域節(jié)點(diǎn)發(fā)生數(shù)據(jù)內(nèi)容的匹配程度確定，匹配程度越高，說明未來(lái)在此路徑上發(fā)生數(shù)據(jù)傳遞的概率越大，那么閾值設(shè)的越低，否則越高。能量閾值Ethreshold根據(jù)路由路徑能量損耗數(shù)據(jù)包和傳感器節(jié)點(diǎn)剩余能量確定，為固定值。每次數(shù)據(jù)傳輸時(shí)，路由路徑上的每個(gè)傳感器節(jié)點(diǎn)都將其剩余能量與 Ethreshold相比較，同時(shí)判斷傳遞數(shù)據(jù)內(nèi)容是否與Ithreshold相等，隨著路由路徑上能量的消耗，若某個(gè)節(jié)點(diǎn)的剩余能量Erest不大于Ethreshold，并且 Irest不小于 Ithreshold，算法將利用右手法則避開這個(gè)節(jié)點(diǎn)并重新修改當(dāng)前路徑，然后避開的節(jié)點(diǎn)仍在監(jiān)測(cè)區(qū)域，它僅收集外界數(shù)據(jù)而不能傳輸其它傳感器節(jié)點(diǎn)的數(shù)據(jù)，因此，傳感器節(jié)點(diǎn)的負(fù)載周期將會(huì)延長(zhǎng)并且網(wǎng)絡(luò)中的能耗可以均勻分擔(dān)。

圖4改進(jìn)GPSR算法

圖4所示，在沒有產(chǎn)生路由空洞時(shí)，貪婪路由路徑是S→x→y→z→h→j→i→D，當(dāng)節(jié)點(diǎn)y滿足興趣閾值與能量閾值的限定時(shí)，分別以D和y為中心畫兩個(gè)圓，圓的半徑分別是節(jié)點(diǎn)D和節(jié)點(diǎn)y的通信半徑之間的距離，利用右手法則和遞歸貪婪算法直到路由路徑到達(dá)目標(biāo)節(jié)點(diǎn)D，此時(shí)在重疊區(qū)域找到最佳的下一跳節(jié)點(diǎn)a。改進(jìn)算法的新的路由路徑為S→x→a→z→h→j→i→D，此外，若出現(xiàn)路由空洞，改進(jìn)算法利用右手法則找出新的路由路徑。

2.2能耗模型

模型采用Heinzalman提出的無(wú)線通信能耗模型［11］。無(wú)線傳感器網(wǎng)絡(luò)中n位數(shù)據(jù)傳輸能耗記為ETx，公式（1）所示。

式中，Eamp為信號(hào)放大器的放大系數(shù)，εfs為空閑空間能耗，Eelec為發(fā)射和接受電子線圈能耗，d為兩個(gè)傳感器節(jié)點(diǎn)請(qǐng)求數(shù)據(jù)傳輸?shù)木嚯x。

式中，R為通信半徑，ERx為n位數(shù)據(jù)接受能耗。

3　仿真實(shí)驗(yàn)

3.1仿真實(shí)驗(yàn)環(huán)境及參數(shù)

仿真實(shí)驗(yàn)在Matlab R2011b環(huán)境下中運(yùn)行，通過實(shí)驗(yàn)來(lái)比較改進(jìn)算法和GPSR算法網(wǎng)絡(luò)能耗和有效傳感器節(jié)點(diǎn)數(shù)。

實(shí)驗(yàn)中監(jiān)測(cè)區(qū)域?yàn)?00m*300m，隨機(jī)部署90個(gè)傳感器節(jié)點(diǎn)，通信半徑為75m，信標(biāo)節(jié)點(diǎn)所占比例為30%，初始能量為0.5J，節(jié)點(diǎn)（300，300）是匯聚節(jié)點(diǎn)，左下方是事件區(qū)域。

3.2仿真實(shí)驗(yàn)結(jié)果分析

圖5所示，路由路徑首次建立，星狀節(jié)點(diǎn)代表90個(gè)傳感器節(jié)點(diǎn)，圓狀節(jié)點(diǎn)代表匯聚節(jié)點(diǎn)。左下角黑色虛線包圍的區(qū)域?yàn)槭录^(qū)域，黑色實(shí)線代表路由路徑。匯聚節(jié)點(diǎn)發(fā)送查詢信息到事件區(qū)域，根據(jù)反方向的查詢信息路徑，建立路由路徑。

圖5　GPSR路由路徑

在無(wú)線傳感器網(wǎng)絡(luò)中，網(wǎng)絡(luò)中剩余能量是評(píng)價(jià)其性能的一個(gè)關(guān)鍵因素，因此，實(shí)驗(yàn)執(zhí)行的目的就是比較兩種算法中每輪中剩余能量。圖6所示，橫坐標(biāo)代表輪數(shù)，縱坐標(biāo)代表網(wǎng)絡(luò)中所有節(jié)點(diǎn)剩余能量。虛線代表事件區(qū)域利用GPSR算法由于能量耗盡而失效之前每輪中網(wǎng)絡(luò)中剩余能量，實(shí)線代表利用改進(jìn)算法的剩余能量。從圖6可以總結(jié)出，改進(jìn)算法能降低網(wǎng)絡(luò)能耗并且延長(zhǎng)網(wǎng)絡(luò)生存周期。

圖6　剩余能量對(duì)照?qǐng)D

當(dāng)事件區(qū)域內(nèi)的節(jié)點(diǎn)由于能量耗盡而失效時(shí)，網(wǎng)絡(luò)中有效傳感器節(jié)點(diǎn)是評(píng)價(jià)路由算法的另一個(gè)重要因素。圖7所示，橫坐標(biāo)代表實(shí)驗(yàn)輪數(shù)，縱坐標(biāo)代表存活節(jié)點(diǎn)數(shù)量。虛線代表事件區(qū)域內(nèi)所有傳感器節(jié)點(diǎn)使用GPSR算法每輪的存活節(jié)點(diǎn)數(shù)，實(shí)線代表改使用進(jìn)算法每輪存活節(jié)點(diǎn)數(shù)。從圖7中可以得出，1100輪之前，GPSR算法和改進(jìn)算法在事件區(qū)域內(nèi)的傳感器節(jié)點(diǎn)存活數(shù)量相當(dāng)，1100輪之后，兩算法相比，改進(jìn)算法的節(jié)點(diǎn)存活數(shù)量明顯優(yōu)于原算法。所以使用改進(jìn)算法中有效節(jié)點(diǎn)數(shù)明顯多于使用GPSR算法。

圖7　有效節(jié)點(diǎn)數(shù)量對(duì)比圖

4　結(jié)論

為解決高能耗和GPSR算法中能量不均衡問題，提出了一種基于興趣梯度和能量梯度改進(jìn)的GPSR算法。GPSR是一種地理路由算法，改進(jìn)后的路由算法設(shè)計(jì)查詢信息傳輸和事件傳輸?shù)膫鬏敊C(jī)制，并利用右手法則和邊界轉(zhuǎn)發(fā)策略預(yù)測(cè)和避免了路由空洞。在新的算法中，通過查詢發(fā)送消息和提前設(shè)置閾值建立興趣梯度和能量梯度路徑，然后，如果當(dāng)前傳感器節(jié)點(diǎn)能量接近閾值，根據(jù)右手法則及迭代貪婪算法重新建立路由路徑。這種新的算法考慮到路由路徑的能耗不均衡問題，并且為了避免一些節(jié)點(diǎn)由于能量過度消耗而造成失效，設(shè)計(jì)了動(dòng)態(tài)更新路由路徑機(jī)制。因此，能耗分布在整個(gè)網(wǎng)絡(luò)中，可以降低了網(wǎng)絡(luò)能耗。仿真實(shí)驗(yàn)結(jié)果表明，改進(jìn)的算法能夠延遲傳感器節(jié)點(diǎn)的失效，降低網(wǎng)絡(luò)能耗和延長(zhǎng)網(wǎng)絡(luò)生存周期。

［1］孫利民，李建中，陳渝.無(wú)線傳感器網(wǎng)絡(luò)［M］.北京：清華大學(xué)出版社，2005：3-4.

［2］胡智慧，劉智.基于LTE無(wú)線傳感器在智能電網(wǎng)的應(yīng)用研究［J］.長(zhǎng)春理工大學(xué)學(xué)報(bào)：自然科學(xué)版，2014，37（2）：80-83.

［3］姚先連，胡貞，呂曉玲.無(wú)線傳感器網(wǎng)絡(luò)中卡爾曼濾波在移動(dòng)目標(biāo)跟蹤中的研究［J］.長(zhǎng)春理工大學(xué)學(xué)報(bào)：自然科學(xué)版，2011，34（3）：88-92.

［4］韓連勝，羅衛(wèi)兵，李南翔.基于地理路由協(xié)議GPSR的研究與改進(jìn)［J］.計(jì)算機(jī)工程與應(yīng)用，2007，43（36）：160-162.

［5］Brad Karp，Kung H T.Greedy perimeter stateless routing for wireless networks［C］.The Sixth Annual International Conference on Mobile Computing and Networking，Boston，2000（8）：243-254.

［6］Nithyanandan L，Sivarajesh G，Dananjayan P.ModifiedGPSRprotocolforwirelesssensornetworks ［J］.International Journal of Computer and Electrical Engineering，2010，4（2）：324-328.

［7］Shanmuga Raja B，Prabakaran N，Sarma Dhulipala V R.Modified GPSR based optimal routing algorithm for reliable communication in WSNs［C］.International Conference on Devices&Communications，2011：1-5.

［8］劉宇，趙志軍，沈強(qiáng)，等.能量感知的GPSR動(dòng)態(tài)路由負(fù)載均衡［J］.計(jì)算機(jī)工程與應(yīng)用，2011，47（6）：23-25.

［9］吳三斌，王小明，楊濤，等.改進(jìn)的GPSR模型及其仿真分析［J］.計(jì)算機(jī)工程與應(yīng)用，2011，47（8）：100-104.

［10］李道全，劉海燕，曹齊光，等.基于地理位置的路由算法—GPSR-AD［J］.計(jì)算機(jī)應(yīng)用，2009，29（12）：3215-3232.

［11］Heinzelman W B，Candraksan A P，Balakrishnan H.An application specific protocol architecture for wireless microsensor network［J］.IEEE Transactions on Wireless Communications，2002（4）：660-670.

An Improved GPSR Routing Algorithm Based on Interest Gradient and Energy Gradient

LIU Zhuang，F(xiàn)ENG Xin，ZHANG Xin，LIU Yan，ZHANG Jing，ZHANG Jianfei

（School of Computer Science and Technology，Changchun University of Science and Technology，Changchun 130022）

To solve the unbalanced and high energy consumption of greedy perimeter stateless routing（GPSR）algorithm，an improved routing algorithm based on interest gradient and energy gradient is proposed.First，during the transmission of query message along a routing path，an interest threshold and an energy threshold are established according to the matching degree of data content between sink node and the node in event area，and then if some nodes are approaching any thresholds，network uses right-hand rule and recursion greedy algorithm to find out a new routing path to target area，so nodes can get relatively balanced load among neighbor nodes.Simulation experiments show that the improved routing algorithm reduces the energy consumption of network and extends the lifecycle of network.

GPSR；interest gradient；energy gradient；lifecycle of network

TP393

A

1672-9870（2016）03-0132-04

2016-01-13

國(guó)家自然基金項(xiàng)目（NSCF61275080）

劉壯（1980-），男，講師，E-mail：lz1227@live.cn

馮欣（1973-），男，副教授，E-mail：fengxin@cust.edu.cn