一種基于信標的地理信息位置路由協議的改進

摘要：空洞問題一直是無線傳感器網絡中基于地理信息位置路由協議研究的一個熱點。文章對ITGR算法提出了改進措施，通過逆路由路徑方向尋找新的信標節點更新ITGR算法中的信標節點，從而擴大ITGR算法的目標陰影區域范圍，減少算法繞空洞時迂回路徑的長度。OMNeT++4．0仿真表明，改進算法可以降低ITGR算法繞空洞的路由路徑的平均跳數和長度。
關鍵詞：無線傳感網絡；路由協議；地理信息位置路由；信標

0 引言
近年來，隨著低功耗、微型化GPS的發展，以及三邊測量等定位技術的日趨成熟，使得基于地理信息位置的路由算法日益成為研究的熱點。而且在無線傳感網絡中，很多應用都與節點的位置信息有關，甚至某些應用必須知道節點的位置信息后，傳感器節點采集的信息才有真正的價值和意義。例如，在環境監測中，需要知道被監測點的位置信息；在森林火災監測和煤礦安全事故監測中，需要知道發生險情的位置信息；在跨海大橋橋梁安全監測中，橋梁擺動的幅度需要精確知道其位置偏移信息。以地理信息位置為導向的路由同時具有很強的路由導向性。以往傳統的路由需要存儲大量的路由表或者在整個網絡內泛洪路由請求數據包來尋找數據包發送的路徑，而基于地理信息的位置路由，可以縮減路由請求的泛洪區域，甚至取消泛洪，大大降低整個網絡的能耗、擁塞，使得網絡的生存時間得以提高、網絡的規模得以提升。

1 相關算法研究
在基于地理信息位置路由算法依靠單跳鄰居節點和目標節點的位置信息來確定路由，路由選擇比本節點更接近于目標節點的鄰居節點作為下一跳節點。但當網絡中存在空洞的時候，該種貪婪算法有可能失效。對此，很多文章提出繞過空洞的解決方法，這些算法大體可以分為三類：局部泛洪機制、消息回退機制和面路由機制。其中以GPSR算法應用最為基礎和廣泛。
GPSR算法結合了貪婪轉發路由和周邊路由，源節點先用貪婪轉發策略發送數據包，當數據包到達局部最小節點時，算法進入周邊模式，即節點采用右手法則選擇下一跳節點。在周邊模式中如果一個節點到目標節點的距離小于局部最小節點到目標節點的距離，則在此算法由周邊模式恢復到貪婪算法模式中，依次重復直到到達目標節點。
雖然當源節點和目標節點存在連接的時候，GPSR算法總能保證數據包的發送，但GPSR算法存在三角路由問題和盲目路由問題。對此GLR算法將算法由周邊模式恢復到貪婪轉發模式的節點稱為信標節點(landmark)，源節點在知道到達目標節點的信標節點位置信息后，可以直接將數據發送到目標節點而不經過局部最小節點，從而優化三角路由問題。同時信標節點的發現過程采用前向發現與后向發現相結合的方式，避免盲目路由問題時數據包繞整個網絡轉發的情況。
相對于GLR一個目標節點對應一個信標緩存的情況，ITGR算法提出目標陰影區域的概念。通過一次信標發現過程，發現到目標節點路徑上的信標節點和局部最小節點后；通過源節點、局部最小節點、信標節點的平面直線方程不等式組劃定目標節點陰影區域的范圍，一個信標節點對應目標陰影區域范圍內的所有節點。ITGR算法大大降低信標緩存的大小，并且減少信標發現過程，降低了控制開銷。

2 基于信標的地理信息位置路由協議的改進
本文在ITGR算法基礎上提出信標后退算法，試圖擴大目標節點的陰影區域，讓一次信標發現過程發現更大的目標節點陰影區域，讓更多的節點使用信標節點作為間接目標節點轉發數據，并減少算法進入周邊模式的次數，縮短路由路徑。

下面我們通過舉例來說明如何擴大目標節點陰影區域范圍。在圖1中，S為源節點，D為目標節點，陰影區域為VOID區域(由于陰影區域中存在障礙物等原因，網絡無法通過此區域通信)，P為局部最小節點，B1為ITGR算法的信標節點，實線為源節點S按照ITGR算法發送數據包到目標節點D的路徑，虛線為更新信標節點后的路徑。
ITGR和GLR算法中定義信標節點為路由算法由周邊模式恢復到貪婪轉發模式的節點。假設用DISTANCE(X，Y)來代表X與Y點之間的距離，B代表信標節點，則信標節點B滿足公式(1)。由圖1可以發現，不僅僅在信標節點B滿足公式(1)，按照數據包所走的路徑往后推，E、C、N、B2點都滿足公式(1)，直到到達M點，M點并不滿足公式(1)。所以在B2同時滿足公式(2)與公式(3)
DISTANCE(B，D)DISTANCE(P，D)……(1)
DISTANCE(N，D)DISTANCE(B，D)……(2)
DISTANCE(B，D)DISTANCE(M，D)……(3)