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

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

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

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

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

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

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

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

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

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

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

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

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