張尊國

（中國移動通信集團廣西有限公司，南寧 530022）

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

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

1 LAR 路由協(xié)議

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

圖1 搜索域和期望域

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

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

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

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

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

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

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

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

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

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

（4）在相關距離檢查期間，NI比較自己到ND的距離和其NP到ND的距離，若滿足：

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

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

3 性能評估

3.1 仿真實驗環(huán)境

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

3.2 性能參數(shù)

仿真主要根據(jù)下面兩個指標來進行性能度量：

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

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

3.3 實驗結果分析

通過變化節(jié)點的移動最大移動速度分別是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路由算法進行實驗對比，考察網(wǎng)絡分組投遞率、路由控制開銷的變化情況。

圖 3 分組投遞率

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

圖4 路由控制開銷

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

4 總結

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

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

[2] 陳貴海, 等. 對等網(wǎng)絡：結構、應用與設計[M]. 北京：清華大學出版社，2007.

[3] 歐中洪, 宋美娜, 戰(zhàn)曉蘇, 宋俊德. 移動對等網(wǎng)絡關鍵技術研究[J]. 軟件學報, 19(1):126-140.