能量感知和鏈路穩(wěn)定度的多徑MANET路由

曾文鋒，戴建輝

（①長沙通信職業(yè)技術學院，湖南 長沙 410015；②華中科技大學 電子與信息工程系，湖北 武漢 430074）

0 引言

移動自組織網(wǎng)絡（MANET，Mobile Ad hoc Networks）[1]是不依賴任何固定的基礎設施，由一組移動節(jié)點組成的自治系統(tǒng)。MANET的移動節(jié)點帶有無線收發(fā)裝置，在網(wǎng)絡中既是主機又兼有路由器的功能，網(wǎng)絡建立展開快捷靈活。路由問題是移動自組網(wǎng)的主要挑戰(zhàn)[2]，由于節(jié)點的隨機運動造成的拓撲結(jié)構(gòu)動態(tài)變化，增加了MANET中路由的難度。MANET中節(jié)點依靠電池供電，節(jié)電能延長網(wǎng)絡的生存時間，而穩(wěn)定的鏈路能夠減少鏈路的頻繁斷裂。因此，鏈路穩(wěn)定和節(jié)能是移動自組網(wǎng)絡由協(xié)議面臨的重要問題[3-4]。

在AOMDV[5-6]協(xié)議的基礎上，綜合考慮節(jié)點的剩余能量和鏈路的穩(wěn)定度，提出了一種基于能量感知和鏈路穩(wěn)定度的多路徑MANET路由協(xié)議(ELMRP，Energy-awareness and Link-steady-degree based Multi-path Routing Protocol for Mobile Ad hoc Networks)。新協(xié)議在路由發(fā)現(xiàn)過程中搜集路徑的能量和穩(wěn)定度信息并計算路徑代價值。根據(jù)路徑代價，在多條節(jié)點不相交路徑中分配數(shù)據(jù)分組流量。該協(xié)議有效地降低并均衡了AOMDV路由協(xié)議的能量消耗，延長了網(wǎng)絡的生存時間，并提高了分組遞送率。

1 AOMDV路由協(xié)議

AOMDV可以用來尋找節(jié)點不相交或鏈路不相交的路由。在節(jié)點路由表中，到同一目的的多條路徑具有相同的序列號。所有不相交路徑中最大的跳數(shù)值稱為廣告跳數(shù)(AHC，Advertised Hop Count)，用來傳播目的節(jié)點的路由廣播。節(jié)點通過接受到的重復的路由廣播，構(gòu)造到目的的多條不相交路徑。為了確保避免環(huán)路，節(jié)點只處理到相同目的節(jié)點的跳數(shù)小于廣告跳數(shù)的路由廣播。因為廣告跳數(shù)使用了最大跳數(shù)值，所以相同序列號的廣告跳數(shù)不會改變。當節(jié)點接受到了序列號更大的路由廣播，刪除所有的下一跳節(jié)點列表并重新初始化廣告跳數(shù)。

AOMDV為了尋找節(jié)點不相交路由，節(jié)點并不立即拒絕重復的RREQ。通過源節(jié)點的不同的鄰居節(jié)點到達的每個RREQ確定了一個節(jié)點不相交路徑。這是因為節(jié)點不廣播重復的RREQ，通過源節(jié)點的不同的鄰居到達中間節(jié)點的兩個RREQ不可能經(jīng)過同一個節(jié)點。當尋找多個鏈路不相交路由時，目的節(jié)點響應接收到的每個RREQ而不考慮它們的第一跳。為了在RREP的第一跳節(jié)點確保鏈路不相交的特性，目的節(jié)點僅對通過不同的鄰居到達的RREQ發(fā)送相應的RREP。在第一跳之后，RREP沿著節(jié)點不相交的反轉(zhuǎn)路由發(fā)送至源節(jié)點。每個RREP的可能會在中間節(jié)點相交，但是不同的反向路由可以保證鏈路不相交特性。

AOMDV路由協(xié)議的在尋找到達目的結(jié)點的路徑時，不僅是找出一條路徑，而是找出多條路徑存儲起來，根據(jù)規(guī)則選擇其中一條較好的路徑傳輸數(shù)據(jù)分組。與單路由協(xié)議相比具有很大的優(yōu)點：當所采用的路徑中的鏈路斷開時，不用重新進行路由發(fā)現(xiàn)，只需從維護的其它路徑中找出一條來代替就可以了。

2 鏈路穩(wěn)定度

Ad hoc網(wǎng)絡中正在通信的兩節(jié)點，在已知節(jié)點通信范圍、節(jié)點位置、運動方向和速度的條件下，可以預測兩節(jié)點的連接時間。節(jié)點間預期的連接時間，稱為鏈路穩(wěn)定度(LET，Link Expiration Time)[7]。

在Ad hoc網(wǎng)絡中利用移動節(jié)點的全球定位系統(tǒng)(Global Position System, GPS)提供的位置和移動信息，可以計算鏈路連接度LET。LET計算公式定義如下：

式（1）中LET為兩節(jié)點保持連接的預期最大時間，式中r為節(jié)點的信號有效傳輸距離，(xi, yi)、(xj, yj)分別為節(jié)點i、j的坐標，vi、vj為節(jié)點運動速度，θi、θj為運動方向。若節(jié)點運動速度和運動方向確定，則對處于不同位置的兩節(jié)點的連接時間就可通過公式計算出來。當保持連接的兩節(jié)點主機的方向與速度都一致時，LET為無窮大，則可一直保持連接。若LET為負數(shù)，則認為兩節(jié)點不能保持連接。預期連接時間長的鏈路即LET值大的鏈路，具有更高的穩(wěn)定度。

3 ELMRP路由協(xié)議

ELMRP是在AOMDV協(xié)議基礎上的改進。ELMRP引入了路徑的剩余能量和路徑穩(wěn)定度的概念。路徑剩余能量E和路徑穩(wěn)定度S定義如下：

其中，從源節(jié)點的ns到目的節(jié)點nd的路徑P=ns, n1, n2,…,nd，ek為P上中間節(jié)點k的能量，L為路徑P上的鏈路集合，sk為路徑P上鏈路k的穩(wěn)定度。

ELMRP采用了AOMDV的路由發(fā)現(xiàn)機制查找多條節(jié)點不相交路徑，在路由發(fā)現(xiàn)的過程中搜集路徑的剩余能量和路徑穩(wěn)定度的信息，并根據(jù)代價函數(shù)計算路徑的代價。通過在RREQ和RREP分組中分別加入2個字段energy和let，用來傳播路徑的能量和穩(wěn)定度。

源節(jié)點通過向所有的鄰居節(jié)點廣播 RREQ發(fā)起路由發(fā)現(xiàn)過程。若將RREQ到達節(jié)點ni所通過的節(jié)點ni的鄰居節(jié)點記為nj，源節(jié)點為ns，則節(jié)點ni接收RREQ的處理過程如算法1。

算法1：節(jié)點ni接收RREQ的處理算法

路徑P的代價函數(shù)定義如下：

在式(4)中，ρ為權(quán)系數(shù)，決定了路徑剩余能量E和路徑穩(wěn)定度S對于計算代價值的影響。通過改變ρ的值，可以調(diào)整E和S對于代價值的影響。當ρ等于1時，代價值由完全E決定；當ρ等于0時，代價值完全由S決定；當ρ在0和1之間時，代價值按照比例由E和S共同決定。在本文的仿真中ρ取值為0.5。由公式(4)可以看出，剩余能量大和路徑穩(wěn)定度大的路徑具有較小的代價值。

目的節(jié)點接收到RREQ，根據(jù)攜帶的信息生成RREP。丟棄RREQ，沿反向路徑發(fā)送RREP。節(jié)點接受并處理RREP的算法與算法(1)類似，建立多條到目的節(jié)點的節(jié)點不相交路徑，并根據(jù)RREP攜帶的信息計算路徑代價。

源節(jié)點接收到RREP，路由發(fā)現(xiàn)過程完成，源節(jié)點和目的節(jié)點間建立起多條節(jié)點不相交路徑，源節(jié)點開始向目的節(jié)點發(fā)送數(shù)據(jù)分組。ELMRP路由協(xié)議在發(fā)送數(shù)據(jù)分組時，選擇了與AOMDV路由協(xié)議不同的策略。

AOMDV路由協(xié)議中，所有的數(shù)據(jù)分組都經(jīng)過跳數(shù)最小的路徑傳輸。因而在最小跳數(shù)路徑上的各節(jié)點，能量消耗的速度比其他不相交路徑上的節(jié)點更快，導致了各不相交路徑上的節(jié)點的剩余能量不平衡。而在ELMRP路由協(xié)議中，根據(jù)路徑的代價值，在多條結(jié)點不相交的路徑上分配數(shù)據(jù)分組的流量。對于代價值小的路徑，即路徑的剩余能量和路徑穩(wěn)定度的路徑，具有更大的數(shù)據(jù)流量。

在圖1所示的網(wǎng)絡拓撲中，源節(jié)點A到目的節(jié)點E有3條節(jié)點不相交的路徑，AOMDV中所有的數(shù)據(jù)分組都沿著跳數(shù)最小的路徑A－F－G－E發(fā)送。而ELMRP路由協(xié)議中數(shù)據(jù)分組在A－B－C－D－E，A－F－G－E和A－H－I－J－E三條路徑中按照代價值分配數(shù)據(jù)分組流量。

ELMRP路由選擇機制可以描述為：對于給定的源節(jié)點ns和目的節(jié)點nd，所有可能的路徑集合P，對于多條節(jié)點不相交路徑，選擇滿足的n條路徑。EL MRP中數(shù)據(jù)分組選擇第i條節(jié)點不相交路徑pi的概率probi如下：

圖1 一個網(wǎng)絡拓撲結(jié)構(gòu)

4 協(xié)議仿真

4.1 仿真環(huán)境

我們在NS2[8-9]仿真軟件上實現(xiàn)了ELMRP。仿真場景由100個移動節(jié)點組成，隨機分布于1000 m×1000 m的矩形區(qū)域；鏈路層采用IEEE802.11協(xié)議；節(jié)點停留時間為0；利用setdest生成7個仿真場景，節(jié)點平均移動速度分別為1 m/s，2.5 m/s，5 m/s，7.5 m/s和 10 m/s。

通信模型采用CBR數(shù)據(jù)源，共有50個通信對，數(shù)據(jù)分組大小為512 byte，發(fā)送分組速率1 packet/s。

4.2 仿真結(jié)果

在5個不同的場景中對ELMRP協(xié)議與AOMDV協(xié)議分別進行了仿真試驗，對產(chǎn)生的 trace文件進行處理分析，著重于網(wǎng)絡生存時間，分組遞送率路由發(fā)現(xiàn)頻率的比較。

協(xié)議的網(wǎng)絡生存時間比較如圖2所示。隨著節(jié)點運動速度的增加，兩種協(xié)議的網(wǎng)絡生存時間的曲線均呈下降的趨勢。在所有的5個仿真場景中，ELMRP比AOMDV的具有更長網(wǎng)絡生存時間，最大的差距到達40 s。AOMDV由于數(shù)據(jù)分組集中于最短的路徑發(fā)送，因而最短路徑上的各節(jié)點比其它路徑上的節(jié)點的電池能量消耗更快，更早消耗完電池能量；而ELMRP按照路徑能量和穩(wěn)定度計算出的代價值，在多條不相交路徑中分配數(shù)據(jù)分組的流量，較穩(wěn)定并且剩余能量較大的路徑上承擔較多的分組流量，均衡了各個路徑上節(jié)點的能量消耗速度，因而延長了網(wǎng)絡生存時間。

圖2 網(wǎng)絡生存時間比較

協(xié)議的分組遞送率比較如圖3所示。在節(jié)點低運動性的場景中，兩種協(xié)議都表現(xiàn)了較好的性能，均在90%以上。隨著節(jié)點運動加劇，協(xié)議的分組遞送率下降。ELMRP比AOMDV的分組遞送率平均提高了約3%。ELMRP在評價路徑質(zhì)量計算代價值時，考慮了路徑的穩(wěn)定度，穩(wěn)定的路徑分配了更多的流量，因而減少了路由失效的次數(shù)，提高了數(shù)據(jù)分組遞送率。

圖3 分組遞送率比較

協(xié)議的路由發(fā)現(xiàn)頻率比較如圖4所示。從圖4可以看出，ELMRP路由發(fā)現(xiàn)頻度在 5個場景中均低于 AOMDV。ELMRP路由協(xié)議中除了路徑上節(jié)點的剩余能量，穩(wěn)定度也是路由評價的標準之一。在路由發(fā)現(xiàn)的過程中建立的多條節(jié)點不相交路徑中，穩(wěn)定的路由具有更小的代價值。數(shù)據(jù)分組更多的通過穩(wěn)定的路徑，因而減少了路由失敗的次數(shù)并避免了再次的路由發(fā)現(xiàn)。

圖4 路由發(fā)現(xiàn)頻度比較

5 結(jié)語

移動自組織網(wǎng)絡中的路由問題一直以來是研究的熱點領域。本文在AOMDV的基礎上提出了一種新的按需路由協(xié)議ELMRP。該路由協(xié)議充分考慮路徑的剩余能量和穩(wěn)定度，在多條不相交路徑中根據(jù)代價值分配網(wǎng)絡數(shù)據(jù)分組流量。較穩(wěn)定并且剩余能量較大的路徑上承擔較多的分組流量，因而均衡網(wǎng)絡中各節(jié)點的能量消耗速度，延長了網(wǎng)絡的生存時間，提高了分組遞送率，降低了路由發(fā)現(xiàn)頻度。

[1] RAMANATHAN R, REDI J.A Brief Overview of Mobile Ad hoc Networks:Challenges and Directions[J].IEEE Communications Magazine,2002, 40(05): 20-22.

[2] 陳世奎, 李臘元.移動自組網(wǎng)路由協(xié)議AODV的性能研究[J].交通與計算機, 2006, 24(06): 122-124.

[3] 葛安峰,王華,王海龍.基于鏈路穩(wěn)定性的 MANET組播路由協(xié)議[J].計算機工程與應用, 2011, 47(12): 75-79.

[4] 朱斌,曾孝平,廖紅云,等.能量高效與移動預測的路由算法分析[J].重慶大學學報, 2010, 33(10): 88 - 93.

[5] MARINA M K, DAS S R.On-Demand Multipath Distance Vector Routing in Ad hoc Networks[J].Mobile Computing and Communications Review, 2002, 6(03): 92-93.

[6] MARINA M K, DAS S D.On-demand Multipath Distance Vector Routing in Ad Hoc Networks[C].Proceedings of IEEE International Conference on Network Protocols (ICNP 2001),Riverside, USA, 11-14, 2001:14-23.

[7] LEE Sung-Ju, SU William, GERLA Mario.Wireless Ad Hoc Multicast Routing with Mobility Prediction [J].Mobile Networks and Applications, 2001, 6(04): 351-360.

[8] 于斌,孫斌,溫暖,等.NS2與網(wǎng)絡模擬[M].北京:人民郵電出版社,2007: 1-5.

[9] 黎方正.基于 NS2的航空自組網(wǎng)節(jié)點移動模型仿真研究[J].通信技術, 2009, 42(01): 186-188.