[發(fā)明專利]一種預(yù)測式低延時(shí)地理路由方法

有效

• 申請?zhí)枺?/td>: 201410789663.6
• 申請日: 2014-12-19
• 公開（公告）號: CN104394554B
• 公開（公告）日: 2019-07-12
• 發(fā)明（設(shè)計(jì)）人: 李哲濤;歐陽經(jīng)綸;裴廷睿;田淑娟;朱更明
• 申請（專利權(quán)）人: 湘潭大學(xué)
• 主分類號: H04W28/08
• 分類號: H04W28/08;H04W40/02;H04W52/02
• 代理公司: 暫無信息
• 代理人: 暫無信息

本發(fā)明提出一種預(yù)測式低延時(shí)地理路由方法。該方法主要用來解決現(xiàn)有地理路由延時(shí)和網(wǎng)絡(luò)能耗不平衡問題，并提高繞行路由空洞效率。基本步驟為：1）設(shè)定協(xié)議包和鄰居表，每個(gè)節(jié)點(diǎn)以為周期廣播一跳協(xié)議包；2）每個(gè)節(jié)點(diǎn)以為周期對鄰居表進(jìn)行局部更新；3）判斷節(jié)點(diǎn)需處理接收過程還是轉(zhuǎn)發(fā)過程，對應(yīng)執(zhí)行步驟4）或步驟5）；4）首先判斷包的類型，若該包是協(xié)議包，則對鄰居表中進(jìn)行全面更新，否則往節(jié)點(diǎn)的上層傳包；5）節(jié)點(diǎn)對數(shù)據(jù)包進(jìn)行貪婪轉(zhuǎn)發(fā)，若轉(zhuǎn)發(fā)遭遇空洞出現(xiàn)局部極值，則利用切線角度擴(kuò)展搜索法選取錨節(jié)點(diǎn)繼續(xù)貪婪轉(zhuǎn)發(fā)。

技術(shù)領(lǐng)域

本發(fā)明是一種預(yù)測式低延時(shí)地理路由協(xié)議方法，屬于無線傳感器網(wǎng)絡(luò)中地理路由領(lǐng)域。

背景技術(shù)

無線Ad Hoc網(wǎng)絡(luò)是一類無固定基礎(chǔ)設(shè)施的無線局域網(wǎng)，是一類由一些處于平等狀態(tài)的移動(dòng)節(jié)點(diǎn)相互通信組成的臨時(shí)網(wǎng)絡(luò)。Ad Hoc網(wǎng)絡(luò)組成簡單快捷，廣泛應(yīng)用于搶險(xiǎn)救災(zāi)、高危工業(yè)、醫(yī)療急救、軍事領(lǐng)域、環(huán)境監(jiān)測等一些臨時(shí)的重大活動(dòng)中。雖然Ad Hoc網(wǎng)絡(luò)相對方便，但網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)(網(wǎng)絡(luò)中移動(dòng)站簡化為節(jié)點(diǎn))都要參與到其他節(jié)點(diǎn)的路由發(fā)現(xiàn)與維護(hù)，并且由于網(wǎng)絡(luò)拓?fù)漕l繁迅速變化，導(dǎo)致一些固定的網(wǎng)絡(luò)路由協(xié)議并不適用于Ad Hoc網(wǎng)絡(luò)。隨著定位技術(shù)的發(fā)展，處于網(wǎng)絡(luò)中的節(jié)點(diǎn)可以獲取自身、鄰居節(jié)點(diǎn)與目的節(jié)點(diǎn)的地理位置信息，從而出現(xiàn)了基于地理位置的路由算法。自從美國哈佛大學(xué)的Karp等人在2000年ACM MobiCom會(huì)議提出了地理路由GPSR(Greedy Perimeter Stateless Routing)以來，地理路由研究受到國內(nèi)外的高度重視。地理路由具有擴(kuò)展性強(qiáng)、自適應(yīng)性高和收斂速度快等優(yōu)點(diǎn)，與基于網(wǎng)絡(luò)拓?fù)涞穆酚蓞f(xié)議相比，地理路由不需要建立和維護(hù)整個(gè)網(wǎng)絡(luò)的路由表。每個(gè)節(jié)點(diǎn)周期的向鄰居節(jié)點(diǎn)發(fā)送Hello包(或Beacon包)，并且接收鄰居節(jié)點(diǎn)發(fā)送的Hello包，同時(shí)節(jié)點(diǎn)用一張鄰居表來記錄鄰居節(jié)點(diǎn)的位置信息。從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的整個(gè)數(shù)據(jù)傳輸在總體上可概括為兩個(gè)主要步驟：首先獲取目的節(jié)點(diǎn)地理位置，然后選擇下一跳轉(zhuǎn)發(fā)數(shù)據(jù)包。其中，前者由“位置服務(wù)”來獲取目的節(jié)點(diǎn)位置，后者通過中間節(jié)點(diǎn)接力轉(zhuǎn)發(fā)來實(shí)現(xiàn)。

Greedy路由是最常用的路由協(xié)議之一，貪婪轉(zhuǎn)發(fā)模式選擇的標(biāo)準(zhǔn)有距離、跳數(shù)、能耗等單一因素，以及多種因素的綜合，貪婪轉(zhuǎn)發(fā)原理簡單，計(jì)算復(fù)雜度低。節(jié)點(diǎn)在選擇下一跳時(shí)，根據(jù)既定標(biāo)準(zhǔn)選擇最優(yōu)鄰居節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā)(例如以距離為標(biāo)準(zhǔn)時(shí)，轉(zhuǎn)發(fā)節(jié)點(diǎn)可選擇距離目的節(jié)點(diǎn)最近的一跳鄰居節(jié)點(diǎn)作為下一跳)，常見的貪婪轉(zhuǎn)發(fā)機(jī)制有MFR、NFP、GRS、CR和RPF等。目前有研究提出結(jié)合擁塞和距離進(jìn)行貪婪決策的方法，但該方法中節(jié)點(diǎn)在通告擁塞層次時(shí)需要時(shí)刻發(fā)送Hello包，導(dǎo)致大量的信息滯后和更多的能量消耗，這個(gè)問題在重載網(wǎng)絡(luò)中更為突出。局部極值(路由空洞)是貪婪轉(zhuǎn)發(fā)中不可避免的一個(gè)問題，解決路由空洞問題的主要方法是：借助某種非貪婪機(jī)制跳出局部最優(yōu)，例如平面圖避洞中的周邊路由模式、洪泛避洞、啟發(fā)式避洞等。其中周邊轉(zhuǎn)發(fā)利用右手準(zhǔn)則繞洞會(huì)延長整個(gè)路徑長度，產(chǎn)生額外的能耗。洪泛避洞雖然能確保繞行空洞成功，但是能耗較大，浪費(fèi)網(wǎng)絡(luò)資源。啟發(fā)式避洞算法通過利用網(wǎng)絡(luò)拓?fù)湫畔⒑涂斩次恢美@行空洞，但是并不能夠確保成功轉(zhuǎn)發(fā)數(shù)據(jù)包。

本發(fā)明提出一種預(yù)測式低延時(shí)地理路由協(xié)議方法，解決了延時(shí)能耗和通信路徑拉長的問題。第一，針對節(jié)點(diǎn)頻繁地發(fā)送Hello包通告信息而造成端到端延時(shí)和能耗增大的問題，本方法通過節(jié)點(diǎn)的隊(duì)列長度、發(fā)送速率和接收速率來計(jì)算最大發(fā)送延時(shí)，綜合考慮節(jié)點(diǎn)距離和延時(shí)參數(shù)，在轉(zhuǎn)發(fā)數(shù)據(jù)時(shí)選取預(yù)測延時(shí)和距離最優(yōu)的下一跳節(jié)點(diǎn)。第二，針對貪婪轉(zhuǎn)發(fā)中出現(xiàn)局部極值而導(dǎo)致轉(zhuǎn)發(fā)路徑拉長的問題，本發(fā)明提出切線角度擴(kuò)展搜索法確定包的錨節(jié)點(diǎn)，繼續(xù)利用貪婪轉(zhuǎn)發(fā)引導(dǎo)后續(xù)數(shù)據(jù)包的發(fā)送。通過建立錨節(jié)點(diǎn)提前避開空洞，可避免由于遭遇空洞而引起距離延長和跳數(shù)增加問題，降低網(wǎng)絡(luò)能耗。

發(fā)明內(nèi)容