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

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

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

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

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

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

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

GPSR；興趣梯度，能量梯度；網絡生存周期

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

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

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

1　相關工作

GPSR是一種經典的地理位置路由協議算法，廣泛應用在Ad-hoc和無線傳感器網絡中，該算法包含兩種形式的數據傳輸方法：貪婪轉發和邊界轉發。

1.1貪婪轉發

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

圖1　貪婪轉發（y是x最近D的鄰居節點）

1.2邊界轉發

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

圖2　貪婪轉發失敗

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

圖3　右手法則

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

2　改進算法

2.1興趣梯度和能耗梯度

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

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

圖4改進GPSR算法

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

2.2能耗模型

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

式中，Eamp為信號放大器的放大系數，εfs為空閑空間能耗，Eelec為發射和接受電子線圈能耗，d為兩個傳感器節點請求數據傳輸的距離。

式中，R為通信半徑，ERx為n位數據接受能耗。

3　仿真實驗

3.1仿真實驗環境及參數

仿真實驗在Matlab R2011b環境下中運行，通過實驗來比較改進算法和GPSR算法網絡能耗和有效傳感器節點數。

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

3.2仿真實驗結果分析

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

圖5　GPSR路由路徑

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

圖6　剩余能量對照圖

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

圖7　有效節點數量對比圖

4　結論

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

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

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

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

［4］韓連勝，羅衛兵，李南翔.基于地理路由協議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動態路由負載均衡［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，FENG 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