一種基于信標(biāo)的地理信息位置路由協(xié)議的改進(jìn)

摘要：空洞問題一直是無線傳感器網(wǎng)絡(luò)中基于地理信息位置路由協(xié)議研究的一個(gè)熱點(diǎn)。文章對ITGR算法提出了改進(jìn)措施，通過逆路由路徑方向?qū)ふ倚碌男艠?biāo)節(jié)點(diǎn)更新ITGR算法中的信標(biāo)節(jié)點(diǎn)，從而擴(kuò)大ITGR算法的目標(biāo)陰影區(qū)域范圍，減少算法繞空洞時(shí)迂回路徑的長度。OMNeT++4．0仿真表明，改進(jìn)算法可以降低ITGR算法繞空洞的路由路徑的平均跳數(shù)和長度。
關(guān)鍵詞：無線傳感網(wǎng)絡(luò)；路由協(xié)議；地理信息位置路由；信標(biāo)

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

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

2 基于信標(biāo)的地理信息位置路由協(xié)議的改進(jìn)
    本文在ITGR算法基礎(chǔ)上提出信標(biāo)后退算法，試圖擴(kuò)大目標(biāo)節(jié)點(diǎn)的陰影區(qū)域，讓一次信標(biāo)發(fā)現(xiàn)過程發(fā)現(xiàn)更大的目標(biāo)節(jié)點(diǎn)陰影區(qū)域，讓更多的節(jié)點(diǎn)使用信標(biāo)節(jié)點(diǎn)作為間接目標(biāo)節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)，并減少算法進(jìn)入周邊模式的次數(shù)，縮短路由路徑。

    下面我們通過舉例來說明如何擴(kuò)大目標(biāo)節(jié)點(diǎn)陰影區(qū)域范圍。在圖1中，S為源節(jié)點(diǎn)，D為目標(biāo)節(jié)點(diǎn)，陰影區(qū)域?yàn)閂OID區(qū)域(由于陰影區(qū)域中存在障礙物等原因，網(wǎng)絡(luò)無法通過此區(qū)域通信)，P為局部最小節(jié)點(diǎn)，B1為ITGR算法的信標(biāo)節(jié)點(diǎn)，實(shí)線為源節(jié)點(diǎn)S按照ITGR算法發(fā)送數(shù)據(jù)包到目標(biāo)節(jié)點(diǎn)D的路徑，虛線為更新信標(biāo)節(jié)點(diǎn)后的路徑。
    ITGR和GLR算法中定義信標(biāo)節(jié)點(diǎn)為路由算法由周邊模式恢復(fù)到貪婪轉(zhuǎn)發(fā)模式的節(jié)點(diǎn)。假設(shè)用DISTANCE(X，Y)來代表X與Y點(diǎn)之間的距離，B代表信標(biāo)節(jié)點(diǎn)，則信標(biāo)節(jié)點(diǎn)B滿足公式(1)。由圖1可以發(fā)現(xiàn)，不僅僅在信標(biāo)節(jié)點(diǎn)B滿足公式(1)，按照數(shù)據(jù)包所走的路徑往后推，E、C、N、B2點(diǎn)都滿足公式(1)，直到到達(dá)M點(diǎn)，M點(diǎn)并不滿足公式(1)。所以在B2同時(shí)滿足公式(2)與公式(3)
    DISTANCE(B，D)<DISTANCE(P，D)……(1)
    DISTANCE(N，D)<DISTANCE(B，D)……(2)
    DISTANCE(B，D)<DISTANCE(M，D)……(3)
    因此我們可以在ITGR發(fā)現(xiàn)信標(biāo)節(jié)點(diǎn)的路徑上逆向?qū)ふ业谝粋€(gè)DISTANCE(X，Y)的峰值，并將其稱為新信標(biāo)節(jié)點(diǎn)。當(dāng)知道更新過信標(biāo)節(jié)點(diǎn)后，下次S點(diǎn)再發(fā)送數(shù)據(jù)包到D時(shí)，直接將數(shù)據(jù)包發(fā)送給B2，然后由B2轉(zhuǎn)發(fā)給D點(diǎn)。從圖1中可見，未更新信標(biāo)節(jié)點(diǎn)前，數(shù)據(jù)包發(fā)送路徑為實(shí)線代表的路徑，共16跳；更新過信標(biāo)節(jié)點(diǎn)后，數(shù)據(jù)包發(fā)送的路徑為虛線所代表的路徑，共12跳?？梢姼逻^信標(biāo)節(jié)點(diǎn)后，可以節(jié)省路由跳數(shù)。采用ITGR算法，S點(diǎn)第二次向D點(diǎn)發(fā)送數(shù)據(jù)時(shí)，先將數(shù)據(jù)發(fā)送給間接目標(biāo)節(jié)點(diǎn)B1點(diǎn)，但在使用貪婪算法向B1點(diǎn)發(fā)送數(shù)據(jù)的時(shí)候，到達(dá)Z點(diǎn)遇到空洞問題，此時(shí)Z點(diǎn)使用周邊模式向B1轉(zhuǎn)發(fā)數(shù)據(jù)包。而如果采用了更新信標(biāo)算法，S點(diǎn)第二次向D點(diǎn)發(fā)送數(shù)據(jù)的時(shí)候直接將數(shù)據(jù)包發(fā)送給B2，此時(shí)，路由路徑不需要進(jìn)入周邊算法模式，從S到B2和B2到D點(diǎn)都可以直接使用貪婪算法轉(zhuǎn)發(fā)。

    假設(shè)X為射線SB2上的一點(diǎn)，Y為射線SB1上的一點(diǎn)，Z為射線SP上的一點(diǎn)。則ITGR算法中目標(biāo)節(jié)點(diǎn)陰影區(qū)域?yàn)閅B2PZ，如圖2中的斜線區(qū)域；更新信標(biāo)節(jié)點(diǎn)后，目標(biāo)節(jié)點(diǎn)陰影區(qū)域?yàn)閄B2PZ，如圖中的網(wǎng)狀區(qū)域。由圖2可見區(qū)域XB2PZ比區(qū)域YB2PZ更大，說明采用新信標(biāo)節(jié)點(diǎn)可以擴(kuò)大目標(biāo)節(jié)點(diǎn)陰影區(qū)域范圍。

    改進(jìn)后的路由算法描述如下：源節(jié)點(diǎn)向目標(biāo)節(jié)點(diǎn)發(fā)送數(shù)據(jù)時(shí)，按照ITGR算法將數(shù)據(jù)包轉(zhuǎn)發(fā)到B1點(diǎn)，在B1點(diǎn)按照ITGR算法數(shù)據(jù)發(fā)送模式由周邊算法模式恢復(fù)到貪婪算法模式中。我們在此加入LBD(landmark backward discovery)算法，即信標(biāo)節(jié)點(diǎn)后向推移算法。根據(jù)ITGR算法，路由模式mode在B1點(diǎn)將變?yōu)镚REEDY，此時(shí)節(jié)點(diǎn)將采用LBD算法轉(zhuǎn)發(fā)數(shù)據(jù)，算法偽代碼如表1所示。LBD首先判斷信標(biāo)節(jié)點(diǎn)的上一跳節(jié)點(diǎn)是否比信標(biāo)節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的距離更遠(yuǎn)。如果不是，則直接繼續(xù)按ITGR原來算法運(yùn)行；如果是，則更改數(shù)據(jù)包模式并將數(shù)據(jù)包發(fā)送給上一跳節(jié)點(diǎn)，然后按照左手法則依次向回查找距離目標(biāo)節(jié)點(diǎn)，直到查找到新的信標(biāo)節(jié)點(diǎn)或者回傳數(shù)據(jù)包到局部最小節(jié)點(diǎn)。

3 仿真結(jié)果
    本文使用離散仿真器OMNeT++4．0對ITGR算法和更新信標(biāo)后的ITGR+LBD算法進(jìn)行仿真對比。整個(gè)實(shí)驗(yàn)網(wǎng)絡(luò)為1500m×2000m，網(wǎng)絡(luò)內(nèi)隨機(jī)分布200到400個(gè)節(jié)點(diǎn)，每次仿真增加50個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)保持靜止?fàn)顟B(tài)，網(wǎng)絡(luò)中間存在一個(gè)900m×200m的空洞，空洞上方的一個(gè)源節(jié)點(diǎn)向空洞下方的10個(gè)目標(biāo)節(jié)點(diǎn)各發(fā)送10次數(shù)據(jù)。

    仿真主要測量平均路由跳數(shù)和路由路徑平均長度，仿真結(jié)果如圖3和圖4所示。由圖3可見更新信標(biāo)節(jié)點(diǎn)后，平均路由跳數(shù)最少減少9.4 6％，最多減少21．92％，平均減少15．18％。由圖4可見，更新信標(biāo)節(jié)點(diǎn)后，路由路徑平均長度最少減少6．46％，路由路徑平均長度最多減少15．72％，平均減少11．03％。采用ITGR算法第二次向目標(biāo)節(jié)點(diǎn)發(fā)送數(shù)據(jù)的時(shí)候首先使用貪婪算法轉(zhuǎn)發(fā)到信標(biāo)節(jié)點(diǎn)。但當(dāng)網(wǎng)絡(luò)中存在窄帶型空洞的時(shí)候，使用貪婪算法向信標(biāo)節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)有可能重新遇見空洞，造成迂回路徑。而采用新的信標(biāo)節(jié)點(diǎn)后，由于新的信標(biāo)節(jié)點(diǎn)一般位于窄帶型空洞的兩端，所以有效地減少了向信標(biāo)節(jié)點(diǎn)發(fā)送數(shù)據(jù)的時(shí)候重新遇見空洞的問題，縮短了路由路徑長度。另外當(dāng)后移了信標(biāo)節(jié)點(diǎn)后擴(kuò)大了目標(biāo)節(jié)點(diǎn)陰影區(qū)域，使得更多的目標(biāo)節(jié)點(diǎn)可以使用已發(fā)現(xiàn)的信標(biāo)節(jié)點(diǎn)，避免了二次重復(fù)信標(biāo)發(fā)現(xiàn)。仿真實(shí)驗(yàn)結(jié)果證明了采用新的信標(biāo)節(jié)點(diǎn)后，可以降低路由路徑的平均跳數(shù)和路由路徑的長度。

4 結(jié)論
    本文提出一種ITGR的改進(jìn)算法，通過逆著到目標(biāo)節(jié)點(diǎn)的路由路徑方向選擇新的中信標(biāo)節(jié)點(diǎn)，可以擴(kuò)大ITGR算法中目標(biāo)節(jié)點(diǎn)陰影區(qū)域范圍，減少算法進(jìn)入周邊模式的次數(shù)，改進(jìn)的算法既能有效地繞過空洞，又能有效地縮短繞空洞時(shí)路由路徑的迂回長度。仿真實(shí)驗(yàn)表明，當(dāng)網(wǎng)絡(luò)中存在窄帶型空洞時(shí)，更新信標(biāo)節(jié)點(diǎn)可以有效降低ITGR算法的路由跳數(shù)并縮短路由路徑的長度。