基于地理位置的貪婪周邊無狀態(tài)路由算法理論及應用研究.pdf

1、本論文是針對國家自然科學基金項目“基于空氣、冰與水物理特性差異的冰層生消過程與力學強度連續(xù)在線檢測原理研究”(51279122)研究過程中的一項技術難題而開展的研究。為了實現(xiàn)對黃河春季開河時對河道局部區(qū)域內(nèi)浮動冰凌整體及內(nèi)部物理狀態(tài)變化的實時監(jiān)測與預報，我們采用專用的冰情檢測傳感器與無線數(shù)據(jù)傳輸技術結(jié)合構(gòu)成的無線傳感器網(wǎng)絡來解決這一難題。由于構(gòu)成無線傳感器網(wǎng)絡的各節(jié)點具有地理位置浮動的特點，如何解決節(jié)點間的相互協(xié)調(diào)，利用節(jié)點有限的局部信

2、息來實現(xiàn)節(jié)點間數(shù)據(jù)正確、及時的交付，實現(xiàn)無線傳輸鏈路的負載均衡，最大化無線冰凌測報傳感器網(wǎng)絡的生命期成為實現(xiàn)對黃河中上游河道冰凌災害預警系統(tǒng)建設（在對海洋或近海浮冰、大型水利水電樞紐工程水庫內(nèi)浮冰的監(jiān)測與此類似）的一項關鍵技術。本論文通過對這一問題的專向理論研究，希望為解決這一工程應用難題提供一種新的解決途徑。
　　 用于冰凌測報的無線傳感器網(wǎng)絡與傳統(tǒng)的通信網(wǎng)絡相比，在路由節(jié)點的部署方式、能量消耗、容錯性、擴展性等諸多領域有著很

3、大的不同。其中，如何利用有限的局部信息選擇下一跳路由轉(zhuǎn)發(fā)節(jié)點的路由問題成為了無線傳感器網(wǎng)絡技術中極具挑戰(zhàn)性的研究熱點和難點。在解決這一問題的諸多現(xiàn)有路由協(xié)議中，由哈佛大學研究人員Brad Karp和H.T.Kung于2000年提出的基于地理位置的貪婪周邊無狀態(tài)路由協(xié)議GPSR(Greedy PerimeterStateless Routing)是一種特別適用于無線數(shù)據(jù)報網(wǎng)絡的路由協(xié)議。其原因是:(1)由于GPSR協(xié)議所采用的貪婪轉(zhuǎn)發(fā)模式

4、是運行于網(wǎng)絡平面化之前的無線網(wǎng)絡拓撲之上，GPSR協(xié)議可以充分利用無線網(wǎng)絡的通信鏈路，實現(xiàn)數(shù)據(jù)包轉(zhuǎn)發(fā)的高效性;(2)當GPSR協(xié)議在轉(zhuǎn)發(fā)數(shù)據(jù)包的過程中，無法從當前路由節(jié)點的鄰節(jié)點中找到比自己更接近目的節(jié)點的下一跳轉(zhuǎn)發(fā)節(jié)點時，即在數(shù)據(jù)包貪婪轉(zhuǎn)發(fā)過程中出現(xiàn)空洞(void)現(xiàn)象時，GPSR協(xié)議的貪婪轉(zhuǎn)發(fā)模式失效。GPSR協(xié)議能夠自動轉(zhuǎn)入平面周邊遍歷模式，采用加百利圖GG（Gabriel Graph）或相對鄰域圖RNG（Relative Nei

5、ghborhood Graph）算法來構(gòu)造平面圖，結(jié)合右手規(guī)則，對數(shù)據(jù)包進行轉(zhuǎn)發(fā)。所以，GPSR協(xié)議的平面周邊遍歷模式能夠在其貪婪轉(zhuǎn)發(fā)模式失效時避免整個協(xié)議的失敗，提高了無線傳感器網(wǎng)絡中信息傳輸?shù)目煽啃?。正是GPSR協(xié)議的這兩大特性使其成為基于地理位置的無線路由協(xié)議中的典范。
　　 然而，GPSR協(xié)議的平面路由模式在實際應用中，由于錯誤的地理位置信息會導致與單元圖假設發(fā)生沖突，導致網(wǎng)絡拓撲平面化過程不準確，從而會產(chǎn)生三種錯誤的結(jié)

6、果:(1)當平面圖某一連接鏈路中斷時會導致平面子圖中的連接鏈路被刪除;(2)位于某一連接鏈路兩端的節(jié)點就其連接是否屬于平面圖存在爭議（如:單向鏈路不屬于平面圖）;(3)在平面子圖中出現(xiàn)了兩條交叉的鏈路。這些錯誤必然會導致路由失敗，在源和目的節(jié)點之間無法找到路徑，使得周邊轉(zhuǎn)發(fā)模式重新變?yōu)镚PSR協(xié)議的技術瓶頸。
　　 本文結(jié)合冰凌測報無線傳感器網(wǎng)絡中傳感器節(jié)點能量受限、節(jié)點隨著冰凌的產(chǎn)生與流動會出現(xiàn)在河道斷面局部觀測區(qū)域的冰凌測報

7、無線傳感器網(wǎng)絡拓撲結(jié)構(gòu)不斷變化這一特性，提出了對GPSR路由協(xié)議的改進策略GPSRI(GPSR-Improved)，并借助網(wǎng)絡模擬器NS2(Network Simulator2)，對GPSR算法以及改進的路由策略GPSRI進行了模擬仿真實驗，對路由算法中涉及到的關鍵參數(shù)的相關實驗數(shù)據(jù)進行了處理分析。模擬仿真實驗及評估結(jié)果表明，GPSRI在數(shù)據(jù)包轉(zhuǎn)發(fā)的路由跳數(shù)、源和目的節(jié)點間端到端的傳輸時延方面與GPSR相比有較大的性能改進。在改進策略G

8、PSRI中，不但解決了GPSR協(xié)議平面路由模式產(chǎn)生的瓶頸問題，而且從無線傳感器網(wǎng)絡路由協(xié)議可靠性的角度出發(fā)，實現(xiàn)了節(jié)點不相關的多路徑。本文圍繞以下三個方面對改進的路由策略GPSRI進行了具體的研究與探索:
　　 (1)在GPSR協(xié)議中，右手法則保證了數(shù)據(jù)包在平面周邊遍歷模式中能夠走出空洞。但是，如果在路由過程中頻繁遭遇空洞現(xiàn)象時，GPSR協(xié)議做出的路由選擇具有一定的隨意性，而正是這種隨意性又會導致發(fā)現(xiàn)路由的跳數(shù)較多，不能保證GP

9、SR協(xié)議以較小的代價走出空洞。本文詳細分析了GPSR協(xié)議由貪婪轉(zhuǎn)發(fā)模式轉(zhuǎn)入平面周邊遍歷模式解決空洞問題的過程，并在改進的路由策略GPSRI中提出了解決空洞問題的回退策略。據(jù)此策略，GPSRI可以在從源到目的節(jié)點的數(shù)據(jù)包轉(zhuǎn)發(fā)過程中，成功地找到數(shù)據(jù)包的轉(zhuǎn)發(fā)路徑。實驗證明回退策略能夠更加有效地解決平面路由模式中的空洞問題。
　　 (2) GPSR協(xié)議有可能在錯誤的路徑上走得很遠。因為GPSR協(xié)議中創(chuàng)建RNG和GG平面圖的兩種平面化算法

10、都依賴于節(jié)點的當前鄰節(jié)點集的最新位置信息。如果鄰節(jié)點沒有移入或移出路由節(jié)點的信號輻射范圍，僅僅是在當前路由節(jié)點的信號輻射范圍之內(nèi)移動，那么，當前的拓撲平面化信息將不是最新的。當單元圖的平面化信息變得陳舊時，對于準確的周邊模式數(shù)據(jù)包的轉(zhuǎn)發(fā)將失去作用，必然導致GPSR協(xié)議可能一直在錯誤的路徑上轉(zhuǎn)發(fā)數(shù)據(jù)包。本論文提出的GPSRI改進策略在運用回退策略有效地解決GPSR平面路由模式中出現(xiàn)的空洞現(xiàn)象的基礎上，提出了基于節(jié)點混雜模式的環(huán)路徑優(yōu)化算法

11、，實現(xiàn)了盡量使用最短或較短路徑來完成數(shù)據(jù)包的傳輸，從而保證在改進的路由策略GPSRI中可以獲得最小的或較小的端到端的傳輸時延。
　　 (3) GPSR協(xié)議使用邊界轉(zhuǎn)發(fā)的前提是:事先構(gòu)造一個平面圖來描述網(wǎng)絡拓撲，要求該平面圖中任意兩條邊都不相交，GPSR協(xié)議構(gòu)造平面圖的方法是利用GG或RNG平面圖算法來刪除網(wǎng)絡拓撲圖中交叉的邊。但是，在GG和RNG平面圖算法的運行過程中，如果傳感器節(jié)點間存在某種特殊模式的障礙時可能會破壞圖的連通性

12、，從一個平面無法到達另一個周邊轉(zhuǎn)發(fā)平面，從而導致目的節(jié)點不可達，影響到了GPSR協(xié)議實現(xiàn)數(shù)據(jù)交付的可靠性。在本文提出的改進策略GPSRI中實現(xiàn)了多條節(jié)點不相關路徑，進一步提高了無線冰凌測報傳感器網(wǎng)絡中數(shù)據(jù)交付的可靠性。
　　 針對在海洋浮冰或黃河中上游河道的冰凌測報傳感器網(wǎng)絡系統(tǒng)構(gòu)建過程中傳感器節(jié)點能量受限、節(jié)點隨著冰凌的產(chǎn)生與流動會出現(xiàn)在河道斷面局部觀測區(qū)域的無線冰凌測報網(wǎng)絡拓撲結(jié)構(gòu)不斷變化這一特性，采用本文提出的對貪婪周邊無