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

（長春理工大學　計算機科學與技術學院，長春　130022）

基于興趣梯度和能量梯度改進的GPSR路由算法

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

（長春理工大學計算機科學與技術學院，長春130022）

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

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

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

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

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

1　相關工作

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

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

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

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

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

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

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

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

圖3　右手法則

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

2　改進算法

2.1興趣梯度和能耗梯度

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

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

圖4改進GPSR算法

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

2.2能耗模型

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

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

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

3　仿真實驗

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

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

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

3.2仿真實驗結果分析

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

圖5　GPSR路由路徑

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

圖6　剩余能量對照圖

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

圖7　有效節(jié)點數(shù)量對比圖

4　結論

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

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

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

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

［4］韓連勝，羅衛(wèi)兵，李南翔.基于地理路由協(xié)議GPSR的研究與改進［J］.計算機工程與應用，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］劉宇，趙志軍，沈強，等.能量感知的GPSR動態(tài)路由負載均衡［J］.計算機工程與應用，2011，47（6）：23-25.

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

［10］李道全，劉海燕，曹齊光，等.基于地理位置的路由算法—GPSR-AD［J］.計算機應用，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

國家自然基金項目（NSCF61275080）

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

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