基于位置信息的移動(dòng)P2P路由發(fā)現(xiàn)策略

張尊國(guó)

（中國(guó)移動(dòng)通信集團(tuán)廣西有限公司，南寧 530022）

移動(dòng)自組網(wǎng)（MANET）是有移動(dòng)的可以互相通信的主機(jī)組成的無(wú)線網(wǎng)絡(luò)。在MANET里，網(wǎng)絡(luò)本身在路由和傳輸算法上都是以P2P方式實(shí)現(xiàn)?；贛ANET和P2P的這些特點(diǎn)，提出了在移動(dòng)自組網(wǎng)上建立一個(gè)靈活的、可擴(kuò)展的移動(dòng)P2P系統(tǒng)。MP2P網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)是動(dòng)態(tài)改變的，網(wǎng)絡(luò)中的節(jié)點(diǎn)可以任意地移動(dòng)。移動(dòng)P2P網(wǎng)絡(luò)路由協(xié)議受到節(jié)點(diǎn)移動(dòng)性、節(jié)點(diǎn)本身能量、無(wú)線鏈路的帶寬的限制，移動(dòng)P2P路由策略的優(yōu)劣直接影響到系統(tǒng)的效率。

由于基于位置的路由協(xié)議不用維持端到端的路徑，只要保持目的節(jié)點(diǎn)的最新位置信息就能完成數(shù)據(jù)轉(zhuǎn)發(fā)任務(wù)，因此比傳統(tǒng)的路由協(xié)議更具有優(yōu)越性，它們有更高的分組傳送率、低的路由開(kāi)銷(xiāo)和可擴(kuò)展性等，能適用于各種規(guī)模的MP2P。

1 LAR 路由協(xié)議

LAR(Location Aided Routing)路由協(xié)議通過(guò)使用節(jié)點(diǎn)位置信息來(lái)降低路由請(qǐng)求開(kāi)銷(xiāo)以改善MP2P網(wǎng)絡(luò)路由協(xié)議的性能。位置信息可由全球定位系統(tǒng)(GPS)來(lái)提供，GPS提供的位置坐標(biāo)可能和節(jié)點(diǎn)真實(shí)坐標(biāo)間有些誤差，但假定是精確的。如果節(jié)點(diǎn)S需要尋找一條到節(jié)點(diǎn)D的路由，假設(shè)節(jié)點(diǎn)S知道節(jié)點(diǎn)D在t0時(shí)刻的位置L（Xd，Yd），及平均移動(dòng)速度v，當(dāng)前時(shí)刻為t1，那么從節(jié)點(diǎn)S的角度來(lái)看， 在t1時(shí)刻節(jié)點(diǎn)D的位置應(yīng)該是位于以D（Xd，Yd）為圓點(diǎn)， 半徑為v(t1- t0)的圓內(nèi)，并稱這個(gè)圓為D的期望區(qū)域。

圖1 搜索域和期望域

2 ELAR(Enhanced LAR)路由協(xié)議

LAR協(xié)議通過(guò)目的節(jié)點(diǎn)的位置信息確定請(qǐng)求區(qū)域以降低路由請(qǐng)求開(kāi)銷(xiāo)，當(dāng)不知道目的節(jié)點(diǎn)位置時(shí)，則在整個(gè)網(wǎng)絡(luò)范圍內(nèi)廣播轉(zhuǎn)發(fā)，就會(huì)降低整個(gè)網(wǎng)絡(luò)內(nèi)廣播分組的數(shù)量， 降低了網(wǎng)絡(luò)的通信負(fù)載， 以提高網(wǎng)絡(luò)的性能。另外，由于路由請(qǐng)求分組內(nèi)包含中間節(jié)點(diǎn)的位置信息，目的節(jié)點(diǎn)可利用這一信息對(duì)已獲得的路徑進(jìn)行進(jìn)一步優(yōu)化以提高網(wǎng)絡(luò)性能。

2.1 基于距離的位置路由算法

用圖G=(N，E)表示一個(gè)移動(dòng)P2P網(wǎng)絡(luò)，其中N是網(wǎng)絡(luò)中所有節(jié)點(diǎn)的有限集合， E是連接兩個(gè)可直接通信節(jié)點(diǎn)的邊集，在圖中采用分層的體系結(jié)構(gòu)，節(jié)點(diǎn)分為兩類：簇頭節(jié)點(diǎn)(CH)和成員節(jié)點(diǎn)(MN)。成員節(jié)點(diǎn)和簇頭直接通信，簇頭之間通過(guò)多跳方式通信。

2.2 路由發(fā)現(xiàn)

當(dāng)NS想發(fā)送數(shù)據(jù)分組到ND，首先執(zhí)行LAR協(xié)議，如果在Request zone內(nèi)路由發(fā)現(xiàn)不成功， NS不進(jìn)行簡(jiǎn)單的洪泛機(jī)制，而是在Request zone之外觸發(fā)新的路由發(fā)現(xiàn)：

（1）NS首先在Request zone之外廣播位置請(qǐng)求(LREQ，Location Request) 詢問(wèn)ND的地理位置。一旦收到LREQ，簇頭節(jié)點(diǎn)在其位置數(shù)據(jù)表中查詢ND。如果找到，節(jié)點(diǎn)就將帶有IC值的位置應(yīng)答(LREP，Location Reply)返回至NS，否則將返回位置錯(cuò)誤(LERR，Location Error) 。

（2）如果NS收到LERR，表明不存在此ND，路由發(fā)現(xiàn)過(guò)程結(jié)束。如果是LREP，NS取出ND的位置信息和IC值，并發(fā)送路由請(qǐng)求(RREQ)。初始時(shí)，RREQ中的PrePos是NS的位置信息，隨著路由發(fā)現(xiàn)的進(jìn)行，PrePos就是NI的位置信息。轉(zhuǎn)發(fā)算法過(guò)程如下：中間節(jié)點(diǎn)NI收到路由請(qǐng)求分組RREQ，首先查看SeqN序列號(hào)，判斷是否重復(fù)接受，若為重復(fù)節(jié)點(diǎn)，直接丟棄。若是第一次接受的節(jié)點(diǎn)，判斷是不是目的節(jié)點(diǎn)，是則返回RREP分組，源節(jié)點(diǎn)NS收到RREP，得知路由已經(jīng)建好，可以進(jìn)行數(shù)據(jù)傳輸。

（3）NI收到RREQ ，在確認(rèn)自己不是ND后，會(huì)先檢查IC值，看ND的位置信息是否能繼續(xù)用于路由發(fā)現(xiàn)。如果IC值不同，說(shuō)明位置信息已經(jīng)過(guò)時(shí)，這時(shí)NI就會(huì)在本地發(fā)起路由搜索。NI將緩存此RREQ并廣播LREQ。在收到LREP后檢查相關(guān)距離。否則，將直接開(kāi)始檢查相關(guān)距離。

圖2 中間節(jié)點(diǎn)轉(zhuǎn)發(fā)流程圖

（4）在相關(guān)距離檢查期間，NI比較自己到ND的距離和其N(xiāo)P到ND的距離，若滿足：

NI才能轉(zhuǎn)發(fā)，否則RREQ將被NI丟棄。這里D (NI，ND)表示NI和ND之間的幾何距離，δ和是常量系數(shù)。通過(guò)設(shè)置δ和可以自適應(yīng)地調(diào)整相關(guān)距離的檢測(cè)，即調(diào)整轉(zhuǎn)發(fā)條件。

（5）當(dāng)一個(gè)己經(jīng)建立的路徑由于節(jié)點(diǎn)移動(dòng)導(dǎo)致路徑中斷時(shí)，中斷鏈路上游節(jié)點(diǎn)發(fā)送RREQ分組進(jìn)行局部路由中斷修復(fù)。如果中斷鏈路上游節(jié)點(diǎn)在一定時(shí)間內(nèi)沒(méi)有收到目的節(jié)點(diǎn)回復(fù)的RREP分組，則中斷節(jié)點(diǎn)發(fā)送RERR分組給源節(jié)點(diǎn)，由源節(jié)點(diǎn)判斷是否重新發(fā)起路由發(fā)現(xiàn)過(guò)程。由于禁止中間節(jié)點(diǎn)直接回復(fù)RREP分組，只允許目的節(jié)點(diǎn)回復(fù)RREP分組，因此可保證中斷節(jié)點(diǎn)到目的節(jié)點(diǎn)之間修復(fù)路徑的穩(wěn)定性。

3 性能評(píng)估

3.1 仿真實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)平臺(tái)為Pentium Ⅳ CPU 3.0 GHz、512 MB RAM的PC機(jī)，利用Windows XP操作系統(tǒng)下基于Cygwin的平臺(tái)，仿真軟件為NS2.30，基本場(chǎng)景模擬了50個(gè)移動(dòng)節(jié)點(diǎn)隨機(jī)分布在1000 m×1000 m的區(qū)域內(nèi)。節(jié)點(diǎn)隨機(jī)選擇移動(dòng)方向并作連續(xù)移動(dòng)，最大移動(dòng)速度從5 m/s逐步遞增到50 m/s，步長(zhǎng)為5 m/s。隨機(jī)的選擇源節(jié)點(diǎn)和目的節(jié)點(diǎn)，鏈路帶寬為10 kbit/s，節(jié)點(diǎn)的傳輸半徑為250 m。調(diào)整節(jié)點(diǎn)的位置更新周期為2 s，距離更新門(mén)限D(zhuǎn)UT=100 m，δ=1，=0。每次實(shí)驗(yàn)的仿真時(shí)間為600 s。IC初始值設(shè)置為0。

3.2 性能參數(shù)

仿真主要根據(jù)下面兩個(gè)指標(biāo)來(lái)進(jìn)行性能度量：

(1) 分組投遞率：應(yīng)用層信宿接收的分組數(shù)與信源發(fā)送的分組數(shù)之比，反映了網(wǎng)絡(luò)傳輸?shù)目煽啃裕哆f率越高，可靠性越大。

（2）路由控制開(kāi)銷(xiāo)：網(wǎng)絡(luò)內(nèi)所有節(jié)點(diǎn)發(fā)出的控制分組總和與目的節(jié)點(diǎn)收到的全部數(shù)據(jù)分組的比值。本文算法中控制分組包括位置控制分組（LREQ，LREP）以及路由控制分組（RREQ，RREP，LERR）。

3.3 實(shí)驗(yàn)結(jié)果分析

通過(guò)變化節(jié)點(diǎn)的移動(dòng)最大移動(dòng)速度分別是0 m/s，5 m/s，10 m/s，15 m/s，20 m/s，25 m/s，30 m/s，35 m/s，40 m/s，45 m/s，50 m/s。我們將本章提出的ELAR算法與基于MPP模型的EDSR路由算法進(jìn)行實(shí)驗(yàn)對(duì)比，考察網(wǎng)絡(luò)分組投遞率、路由控制開(kāi)銷(xiāo)的變化情況。

圖 3 分組投遞率

圖3表示移動(dòng)速度不同情況下的分組投遞率結(jié)果，表明隨著移動(dòng)速度的增加，節(jié)點(diǎn)的位置變化加劇，節(jié)點(diǎn)間的連接變得更加脆弱，由此導(dǎo)致分組投遞率下降。從圖中可以看出本文提出的ELAR算法優(yōu)于EDSR路由算法，這是由于EDSR缺乏對(duì)目的節(jié)點(diǎn)位置信息的定位，采用整個(gè)網(wǎng)絡(luò)的泛洪路由，缺乏目的節(jié)點(diǎn)的位置指導(dǎo)，降低了尋路的成功率，影響了投遞率。本文算法把路由發(fā)現(xiàn)過(guò)程與節(jié)點(diǎn)的位置信息聯(lián)系起來(lái)，使請(qǐng)求區(qū)域的確定更加準(zhǔn)確，縮小了廣播區(qū)域，同時(shí)利用簇頭節(jié)點(diǎn)維護(hù)位置信息，通過(guò)設(shè)置距離更新門(mén)限，把節(jié)點(diǎn)位置信息不準(zhǔn)確性的影響降到最低，選擇Qpath值小的進(jìn)行簇路由選擇，因此路由的穩(wěn)定性高，從而獲得比較好的分組投遞率。

圖4 路由控制開(kāi)銷(xiāo)

圖4表示路由控制開(kāi)銷(xiāo)和節(jié)點(diǎn)運(yùn)動(dòng)速度的關(guān)系，隨著節(jié)點(diǎn)移動(dòng)性增強(qiáng)，路由控制開(kāi)銷(xiāo)都有所增加。當(dāng)節(jié)點(diǎn)的移動(dòng)速度小于20 m/s的時(shí)候，位置比較穩(wěn)定，ELAR協(xié)議的控制分組數(shù)目包括位置控制分組（LREQ，LREP）以及路由控制分組（RREQ，RREP，LERR）兩部分比EDSR路由協(xié)議控制分組多，從而影響了其控制開(kāi)銷(xiāo)。但隨著節(jié)點(diǎn)移動(dòng)速度的增強(qiáng)，EDSR的路由開(kāi)銷(xiāo)增長(zhǎng)速度高于本文的算法，節(jié)點(diǎn)移動(dòng)速度增強(qiáng)，鏈路斷裂的可能性增強(qiáng)，EDSR協(xié)議要不斷的進(jìn)行泛洪路由發(fā)現(xiàn)策略，產(chǎn)生更多的路由分組，極大的增加路由負(fù)載。ELAR協(xié)議位置控制分組保證了節(jié)點(diǎn)的位置信息準(zhǔn)確性，減少路由分組的請(qǐng)求數(shù)量。當(dāng)節(jié)點(diǎn)的移動(dòng)速度大于20 m/s的時(shí)候，本文算法更適合移動(dòng)P2P網(wǎng)絡(luò)。

4 總結(jié)

本章基于位置輔助的路由協(xié)議（LAR），提出了一種帶路徑優(yōu)化的增強(qiáng)型（ELAR）協(xié)議。通過(guò)在每個(gè)路由請(qǐng)求分組中攜帶源端點(diǎn)及每個(gè)中間節(jié)點(diǎn)的位置信息，使節(jié)點(diǎn)獲得其它節(jié)點(diǎn)的位置便于其縮小路由請(qǐng)求區(qū)域。當(dāng)在位置輔助路由協(xié)議路由發(fā)現(xiàn)失敗時(shí)避免采用全網(wǎng)洪泛機(jī)制，采用基于距離的位置路由改進(jìn)算法，設(shè)置距離更新門(mén)限來(lái)達(dá)到節(jié)點(diǎn)位置信息實(shí)時(shí)性與更新負(fù)載的平衡。實(shí)驗(yàn)結(jié)果表明對(duì)于移動(dòng)P2P網(wǎng)絡(luò)有較低的分組投遞率和有較好的路由控制開(kāi)銷(xiāo)。

[1] 鄭少仁，王海濤等. Ad Hoc網(wǎng)絡(luò)技術(shù)[M]. 北京：人民郵電出版社，2005.

[2] 陳貴海, 等. 對(duì)等網(wǎng)絡(luò)：結(jié)構(gòu)、應(yīng)用與設(shè)計(jì)[M]. 北京：清華大學(xué)出版社，2007.

[3] 歐中洪, 宋美娜, 戰(zhàn)曉蘇, 宋俊德. 移動(dòng)對(duì)等網(wǎng)絡(luò)關(guān)鍵技術(shù)研究[J]. 軟件學(xué)報(bào), 19(1):126-140.