基于路徑穩(wěn)定性的MAODV路由協(xié)議的改進

李帥　蔡明

摘 要： 在Ad Hoc網(wǎng)絡中，節(jié)點隨意快速的移動通常會造成網(wǎng)絡拓撲結(jié)構(gòu)的劇烈變化，可能導致傳輸鏈路斷裂和路徑的不穩(wěn)定。針對這種情況，在分析現(xiàn)有MAODV路由改進技術(shù)的基礎上，提出了一種改進的、基于路徑穩(wěn)定性的路由協(xié)議（RS?MAODV）。新協(xié)議與MAODV不同的地方在于：考慮構(gòu)成路徑的鏈路間的相關(guān)性，選擇最穩(wěn)定的路由進行數(shù)據(jù)傳輸，以此改善網(wǎng)絡性能。利用NS2仿真工具對改進前后網(wǎng)絡的丟包率及端到端延遲參數(shù)做比較，實驗數(shù)據(jù)表明，改進后協(xié)議的網(wǎng)絡丟包率及端到端延遲均得到改善。

關(guān)鍵詞： 無線自組織網(wǎng)絡； 路由協(xié)議； 路徑穩(wěn)定度； 網(wǎng)絡仿真

中圖分類號： TN915.04?34； TP393 文獻標識碼： A 文章編號： 1004?373X（2015）05?0001?04

MAODV routing protocol improvement based on stability of path

LI Shuai， CAI Ming

（IOT Engineer School， Jiangnan University， Wuxi 214122， China）

Abstract： In Ad Hoc networks， random movement of nodes usually causes severe changes of network topology， which may possibly result in breakage of transmission links and instability of routing path. In view of this situation， based on the analysis of existing MAODV routing improvement technology， an improved routing protocol named RS?MAODV is put forward. The diffe?rence between the new protocol and MAODV lies in that the new routing protocol chooses path with highest stability for data transmission to improve the network performance while considering the correlation between links. The simulation tool NS2 is used to compare the packet loss rate and end?to?end delay parameters before and after improvement. The experiment results that the packet loss rate and end?to?end delay of the improved protocol are better than before.

Keywords： wireless Ad Hoc network； routing protocol； path stability； network simulation

0 引 言

無線自組織網(wǎng)絡，又稱Ad Hoc網(wǎng)絡，是一類由大量移動的、配備有無線收發(fā)裝置的節(jié)點組成的網(wǎng)絡，具有多跳、自組織、分布式等特點[1]。該類型網(wǎng)絡由于布設靈活，不依賴于預設的固定基礎設施，受環(huán)境、氣候、地理位置等因素影響較小，被廣泛應用于災害預警、橋梁工程、生態(tài)監(jiān)測等領域。然而，Ad Hoc網(wǎng)絡中節(jié)點的位置會隨其移動不斷發(fā)生變化，從而造成網(wǎng)絡拓撲變得不穩(wěn)定。這種不穩(wěn)定的變化可能會導致某條正在通信的路由斷裂，甚至有可能造成網(wǎng)絡分段的嚴重后果，因而路由的穩(wěn)定性逐漸成為Ad Hoc網(wǎng)絡中研究的熱點之一。

MAODV[2]是一種經(jīng)典的多播路由協(xié)議，是無線自組織網(wǎng)絡中按需距離矢量路由協(xié)議AODV[3]的多播擴展。MAODV是基于樹轉(zhuǎn)發(fā)結(jié)構(gòu)的多播路由協(xié)議，目前，在路由選擇過程中，采用最大序列號或最少跳數(shù)的路由選擇機制，即在源節(jié)點和目的節(jié)點之間選擇一條最短的連通路徑，很少考慮所選路徑是否穩(wěn)定。在一些MAODV的改進方案中，為保證路徑的穩(wěn)定性，常使用的解決方法是為鏈路建立一條備用鏈路，當原鏈路遭到破壞時使用；要么是根據(jù)鏈路斷裂的時間進行預測，在鏈路斷裂前主動進行修復[4?5]。然而，備用鏈路也不一定穩(wěn)定，組成備用鏈路的節(jié)點也會有移動，仍可能導致備用鏈路的斷裂。另外，在這些方案中，均假設相鄰鏈路間是獨立的，沒有考慮鏈路的相關(guān)性，這與現(xiàn)實中網(wǎng)絡的實際情況不符。因而，在現(xiàn)有穩(wěn)定性理論研究[6?8]的基礎上，同時考慮相鄰鏈路的相關(guān)性和路徑的穩(wěn)定性，提出了一種基于路徑穩(wěn)定性的路由協(xié)議RS?MAODV。在改進后的協(xié)議中，為解決路徑穩(wěn)定性的問題，引入兩個度量值：鏈路穩(wěn)定度SPL；路徑穩(wěn)定度SPR。這兩個度量值分別用來衡量鏈路和路徑的穩(wěn)定程度。在路由選擇過程中，選取最穩(wěn)定的路由作為源節(jié)點和目的節(jié)點間傳輸信息的路徑。

1 RS?MAODV路由算法

1.1 算法設計思想

大多數(shù)路徑穩(wěn)定性算法都基于熵[9]的構(gòu)造理論，用改造后的熵表示路徑的穩(wěn)定性。然而這種熵的構(gòu)造主要是通過局部節(jié)點的運動變化情況決定的，僅考慮了節(jié)點的運動速度，沒有考慮節(jié)點間的距離因素。在改進后的穩(wěn)定性算法中，為提高穩(wěn)定性選擇的準確性，通過鏈路的可持續(xù)時間來預測鏈路的穩(wěn)定度。

穩(wěn)定度被定義為在時間間隔Δt內(nèi)，網(wǎng)絡或局部范圍內(nèi)節(jié)點相對位置的變化程度。在Δt時間內(nèi)，假定互為鄰居的節(jié)點仍在彼此的覆蓋范圍內(nèi)。不難推測出，如果節(jié)點i和其覆蓋范圍內(nèi)的節(jié)點（即鄰居節(jié)點）在Δt內(nèi)相對位置變化程度劇烈，則說明節(jié)點i無線覆蓋范圍內(nèi)的拓撲結(jié)構(gòu)穩(wěn)定性較差，反之穩(wěn)定性越好；如果某條路徑上的節(jié)點與其上、下游節(jié)點在時間間隔Δt內(nèi)相對位置變化劇烈，則說明該節(jié)點與其上、下游節(jié)點組成的鏈路穩(wěn)定性較差，包含這些鏈路的路徑穩(wěn)定性也較差。

在Ad Hoc網(wǎng)絡中，源節(jié)點和目的節(jié)點間的通信往往通過多跳轉(zhuǎn)發(fā)實現(xiàn)的，因此，源節(jié)點到目的節(jié)點的路由通常由一系列鏈路組成，如圖1所示。不難推測，路徑中任一條鏈路的斷開都將導致整條路徑的斷裂和不可用，路徑的穩(wěn)定度主要取決于組成它的各段鏈路的穩(wěn)定度。因此，要計算路徑的穩(wěn)定度SPR，一個可行的求解思路是先求出組成該路徑的每一段鏈路的穩(wěn)定度SPL，然后根據(jù)鏈路和路徑的組成關(guān)系最終求出路徑的穩(wěn)定度。路由的選擇依據(jù)路徑的SPR值來確定。

鏈路的穩(wěn)定度通過鏈路維持時間預測的方式獲取。多數(shù)情況下，為處理方便，均假設網(wǎng)絡中組成路徑的各段鏈路間彼此相互獨立，此時路徑的穩(wěn)定度用鏈路穩(wěn)定度聯(lián)乘法[10]計算得出。然而在實際應用網(wǎng)絡中，相鄰鏈路間往往是相關(guān)的，為此還需要考慮鏈路間的相關(guān)性。這種情形下路徑穩(wěn)定度的計算方法相對復雜，在網(wǎng)絡模型部分詳細給出。

1.2 網(wǎng)絡模型和標記

將網(wǎng)絡抽象為無向圖結(jié)構(gòu)G=（V，E），其中V是網(wǎng)絡中節(jié)點的集合，E是網(wǎng)絡中節(jié)點間有效鏈路的集合。這里假設網(wǎng)絡中所有節(jié)點的特征相似，如其無線覆蓋半徑相等，記為R。有效鏈路指此鏈路為雙工類型的鏈路，雙工鏈路指組成此鏈路的兩節(jié)點相互在對方的無線覆蓋范圍內(nèi)，彼此間進行雙向信息傳輸，鏈路兩端的節(jié)點既是信息的發(fā)送方又是信息的接收方，如圖2所示。

1.2.1 鏈路的穩(wěn)定度SPL

假設節(jié)點i和節(jié)點j在彼此的覆蓋范圍內(nèi)并能互相發(fā)送接收消息，則節(jié)點i，j構(gòu)成的鏈路即稱為有效鏈路，也稱節(jié)點i和節(jié)點j互為鄰居節(jié)點。如果某時刻節(jié)點i移出節(jié)點j的無線覆蓋范圍，則節(jié)點i將接收不到節(jié)點j廣播的位置消息。假設節(jié)點i在時刻tk的位置向量表示如下：

[pos（i，tk）=（xi，yi）] （1）

用同樣的方法求出節(jié)點j在時刻tk的位置向量，那么節(jié)點i和節(jié)點j在時刻tk的相對位置向量為：

[pos（i，j，tk）=pos（i，tk）-pos（j，tk）] （2）

假設互為鄰居的節(jié)點i和節(jié)點j在時刻tk的地理坐標分別為[xi（tk），yi（tk）]和[xj（tk），yj（tk）]，那么在時刻tk，兩節(jié)點之間的距離求解公式如下：

[pos（i，j，tk）=（xi（tk）-xj（tk））2+（yi（tk）-yj（tk））2] （3）

在公式（3）中，由圖2可知，[pos（i，j，tk）∈][0，R]。

那么在Δt=tk-tk-1時間間隔內(nèi)，節(jié)點i和節(jié)點j的相對位置變化量Δdij為：

[Δdij=pos（i，j，tk）-pos（i，j，tk-1）] （4）

由于假設在Δt持續(xù)時間內(nèi)節(jié)點i和節(jié)點j仍互為鄰居節(jié)點，可以推測得知Δdij∈[-R，R]，那么[Δdij∈[0，R]，]即計算出在取值區(qū)間[0，R]上相應的鏈路穩(wěn)定度的值[SPL=Δdij，]其中R表示節(jié)點的無線傳輸半徑。為方便處理，對鏈路穩(wěn)定度的求解公式做一些調(diào)整，處理后穩(wěn)定度求解表達式如下：

[SPL=1-ΔdijR] （5）

式中：[Δdij]表示Δt時間間隔內(nèi)節(jié)點i和節(jié)點j相對位置變化量的絕對值，根據(jù)圖2與式（4）可得SPL的取值區(qū)間為[0，1]。從公式（5）中還可推斷出，SPL值越大，節(jié)點i和節(jié)點j在Δt時間間隔內(nèi)相對位置變化就越小，說明此鏈路越穩(wěn)定，越不容易發(fā)生斷裂；SPL值越小，節(jié)點i和節(jié)點j在Δt時間間隔內(nèi)相對位置變化就越大，節(jié)點i相對節(jié)點j的局部拓撲結(jié)構(gòu)變化劇烈，此鏈路越不穩(wěn)定，發(fā)生斷裂的可能性越大。

1.2.2 路徑的穩(wěn)定度SPR

由上面論述可得知，路徑的穩(wěn)定度是路由選擇最基本的依據(jù)，路徑的穩(wěn)定度取決于構(gòu)成路徑的各段鏈路的穩(wěn)定度。多數(shù)處理模型中，為處理方便，均假設各鏈路彼此間獨立，不存在相關(guān)性關(guān)系，這時可用連乘法得到路徑的穩(wěn)定度。此時，路徑的穩(wěn)定度求解公式如下：

[SPR=i=1nSPLi] （6）

然而，在實際的Ad Hoc應用網(wǎng)絡中，組成路徑的各鏈路間往往是存在相關(guān)性關(guān)系的。例如，節(jié)點1和節(jié)點2之間存在鏈路時，節(jié)點1和節(jié)點3之間鏈路的存在將使得節(jié)點2、3之間更有可能存在鏈路。此時求解路徑穩(wěn)定度的公式為：

[SPR=SPL1×f（ρ1）×min{SPL1，SPL2}SPL1…fm-1（ρm-1）×min{SPL（m-1），SPLm}SPL（m-1）] （7）

式中：SPR為所求路徑的穩(wěn)定度；SPL1，SPL2，…，SPLm分別表示組成路徑的各段鏈路的穩(wěn)定度值；ρ1，ρ2，…，ρm-1分別表示各相鄰鏈路之間的相關(guān)因子，詳細計算方法見參考文獻[11]；f1（ρ1），f2（ρ2），…，fm-1（ρm-1）分別表示各相鄰鏈路間的相關(guān)性結(jié)構(gòu)。這里，相關(guān)性結(jié)構(gòu)fi（ρi）[（1≤i≤m-1）]利用如下公式求得：

[fi（ρi）=max{SPLi，SPL（i+1）}×ρi+max{SPLi，SPL（i+1）}（2×max{SPLi，SPL（i+1）}-1）×ρi+1] （8）

以上為鏈路穩(wěn)定度和路徑穩(wěn)定度的求解方法，下面詳細介紹算法相應流程。

1.3 算法流程概述

由于網(wǎng)絡中節(jié)點是不斷移動的，所以節(jié)點均配備GPS無線定位裝置，目的是獲取自身的地理位置信息，并定時在其無線覆蓋區(qū)域內(nèi)廣播最新的地理位置信息，鄰居節(jié)點收到后更新相應信息。節(jié)點在向鄰居節(jié)點廣播位置信息時，節(jié)點的跳數(shù)值設置為1，表明此節(jié)點僅向鄰居節(jié)點發(fā)送數(shù)據(jù)包。整體路由過程如圖3所示。

算法在路由發(fā)現(xiàn)階段的操作流程如下：

（1） 當源節(jié)點想要向多播組成員發(fā)送數(shù)據(jù)分組時，源節(jié)點首先會檢查其路由表項中是否含有到達該多播組的路由，如果有的話，會沿此路徑以單播的方式向多播組發(fā)送消息，否則，源節(jié)點會廣播路由請求消息RREQ到其鄰居節(jié)點，用以開啟路由發(fā)現(xiàn)過程。

（2） 中間節(jié)點接收到路由請求消息RREQ后，先檢查自身是否有到達多播組的路由或者是多播組的某個成員節(jié)點，如果是的話，則會檢查自身路由表項中的組序列號是否大于或等于RREQ消息中的序列號；如果兩個序列號相等，則會檢查其路由表項中記錄的跳數(shù)是否小于RREQ消息中的跳數(shù)。如果該節(jié)點路由表項中沒有到達多播組的路徑或不是多播組成員，則繼續(xù)廣播RREQ消息。

（3） RREQ消息到達多播組的成員節(jié)點后，收到RREQ消息的節(jié)點會更新自身路由表項并記錄下序列號。隨后會產(chǎn)生路由回復消息RREP，此消息包含路徑穩(wěn)定度域SPR，用來記錄從多播組成員節(jié)點到達源節(jié)點所經(jīng)路徑的穩(wěn)定度值，初始化SPR=1；另外，還包含路由跳數(shù)域count，用來記錄所經(jīng)路由的跳數(shù)，初始化count=∞。RREP消息會沿相反方向返回至源節(jié)點，中間節(jié)點收到RREP分組后，更新count值并計算相應段鏈路的穩(wěn)定度值，進而計算并更新從多播組成員到該節(jié)點的路徑的穩(wěn)定度值SPR，直到該RREP分組到達多播源節(jié)點。

算法在路由選擇階段的操作流程如下：

多播源節(jié)點以廣播方式發(fā)送路由請求消息RREQ以后，會等待一段時間。在這個時間段內(nèi)，多播源將不斷接收返回的RREP分組，同時會記錄下分組中的最大序列號和最大路徑穩(wěn)定度，并更新相應路由信息。之后源節(jié)點會發(fā)送激活消息MACT到提供最大序列號和最大路徑穩(wěn)定度的鄰居節(jié)點，用于激活該節(jié)點成為路徑的上游節(jié)點。被選中的鄰居節(jié)點收到MACT消息后將激活路由表項中相應到組地址的路由項，并把MACT消息轉(zhuǎn)發(fā)給下一跳路由節(jié)點，這樣一步一步進行下去，最終激活從多播源到多播組某成員的路徑上的所有中間節(jié)點的路由項。

2 仿真實驗

仿真實驗采用NS2[12]網(wǎng)絡模擬軟件作為仿真工具，在Ubuntu的操作環(huán)境下，對本文提出的改進協(xié)議RS?MAODV和MOADV路由協(xié)議進行了仿真比較。本文采用的NS2版本是2.35，通過NS2軟件的仿真實驗，比較了不同移動速度下兩協(xié)議對應的丟包率和端到端時延。

仿真環(huán)境設置如下：仿真場景長1 500 m，寬300 m；節(jié)點無線傳輸半徑為100 m；MAC層協(xié)議：IEEE 802.11；節(jié)點數(shù)50個，其中源節(jié)點個數(shù)為1個。節(jié)點移動速度范圍設置為1～10 m/s；數(shù)據(jù)類型為CBR，分組大小為512 B，發(fā)包速率為2 packets/s。在仿真環(huán)境下運行，使用Linux環(huán)境下awk[13]工具對網(wǎng)絡模擬產(chǎn)生的追蹤tr文件進行數(shù)據(jù)計算和分析，比較了不同移動速度下協(xié)議改進前后相應的丟包率和端到端時延。

2.1 丟包率

丟包率指數(shù)據(jù)包丟失數(shù)量與應接收數(shù)據(jù)包總數(shù)的比值。在無線多播情形中，假設單個源節(jié)點向包含N個目的節(jié)點的多播組傳送a個分組，多播組收到分組總數(shù)為b個，則丟包率為[（Na-b）Na。]實驗中考察了不同移動速度下MAODV和RS?MAODV協(xié)議的丟包率情況，實驗結(jié)果如圖4所示。

通過圖4可以看出，隨著網(wǎng)絡中節(jié)點移動速度的增加，MAODV和RS?MAODV協(xié)議的丟包率均增加。這是因為隨著節(jié)點移動速度的增加，網(wǎng)絡拓撲結(jié)構(gòu)變化劇烈，已有鏈路可能遭到破壞，網(wǎng)絡中擁塞程度加劇，分組間碰撞的可能性增大，整個網(wǎng)絡性能隨之下降。然而，在同一移動速度下，RS?MAODV協(xié)議由于每次選擇局部拓撲變化小的路徑進行數(shù)據(jù)傳輸，使得相同條件下路由中斷和重構(gòu)次數(shù)減少，丟包率也相應較小。

2.2 端到端延遲

端到端延遲是指數(shù)據(jù)包的接收時間和發(fā)送時間之差。實驗中測定了不同移動速度下兩種協(xié)議的端到端延遲，實驗結(jié)果如圖5所示。

從圖5中觀察到，一定節(jié)點移動速度下，MAODV協(xié)議比RS?MAODV協(xié)議的端到端延遲要小，這是因為MAODV協(xié)議選擇一條從源節(jié)點到多播組的最短連通路徑，使得相應端到端延遲要小。隨著網(wǎng)絡運行時間的增加，網(wǎng)絡拓撲結(jié)構(gòu)發(fā)生變化，用于數(shù)據(jù)傳輸?shù)穆窂讲粩嘣獾狡茐?，網(wǎng)絡擁塞程度加劇，兩種協(xié)議對應的端到端延遲均變大。然而RS?MAODV協(xié)議由于考慮了所選路徑的穩(wěn)定性，減少了因節(jié)點失效引起的路由恢復和重構(gòu)的時延，在相同條件下，相比MAODV協(xié)議端到端延遲也較小。

3 結(jié) 語

本文在研究前人MAODV協(xié)議改進技術(shù)的基礎上，提出了一種改進的、同時考慮相鄰鏈路的相關(guān)性和路徑穩(wěn)定性的路由協(xié)議RS?MAODV。在RS?MAODV路由協(xié)議中，引入鏈路穩(wěn)定度和路徑穩(wěn)定度兩參數(shù)，保證了選擇的從源節(jié)點到多播組之間的路由是最穩(wěn)定的，一定程度上提高了路徑的穩(wěn)定性，改善了網(wǎng)絡的性能。但求解穩(wěn)定度時需要計算操作，無疑增加了不必要的開銷，下一步工作將集中在減少網(wǎng)絡開銷上。

參考文獻

[1] 閆麗麗，彭代淵，高悅翔.Ad Hoc網(wǎng)絡中認證路由協(xié)議的改進及其安全性分析[J].電子科技大學學報，2011，40（4）：578?581.

[2] 蔚成英，戴翠琴，雷芳.基于改進MAODV協(xié)議的WMN的組播路由算法[J].計算機與數(shù)字工程，2012，40（1）：25?28.

[3] 徐文濤，晁愛農(nóng).一種移動Ad Hoc網(wǎng)AODV路由協(xié)議的改進方法[J].計算機應用與軟件，2013，30（3）：225?228.

[4] ZHAO Xin， CHOU Chun?tung， GUO Jun， et al. Protecting multicast sessions in wireless mesh networks [C]// Proceedings of the 31st IEEE Conference on Local Computer Networks. [S.l.]： IEEE Press， 2006： 111?116.

[5] 黃錢飛，萬俊，邱海燕.移動自組織網(wǎng)中基于鏈路預測的路由研究[J].電腦與電信，2012（8）：36?38.

[6] 夏輝，賈智平，張志勇，等.移動Ad Hoc網(wǎng)絡中基于鏈路穩(wěn)定性預測的組播路由協(xié)議研究[J].計算機學報，2012，36（5）：926?935.

[7] 余夕亮，陶洋，黃宏程.基于路徑穩(wěn)定性的MANET路由協(xié)議研究與改進[J].計算機工程與應用，2012，43（36）：157?159.

[8] 嚴秋實，萬曉瑜，樊自甫.基于路徑穩(wěn)定性的MAODV改進路由協(xié)議[J].計算機工程，2010，36（20）：93?95.

[9] 徐建娥，王新華，朱硯生.Ad Hoc網(wǎng)絡中基于熵的QoS多播路由研究[J].電腦知識與技術(shù)，2008，7（4）：1634?1636.

[10] 趙繼紅，金依紳.基于移動預測的MESH網(wǎng)絡穩(wěn)定性算法研究[J].無線通信技術(shù)，2012，7（4）：6?10.

[11] ZHANG Hui， DONG Yu?ning. A novel path stability computation model for wireless Ad Hoc networks [J]. IEEE Procee?dings， 2011， 12（14）： 928?931.

[12] 肖權(quán)權(quán)，段迅.基于NS2的網(wǎng)絡仿真與性能測試[J].計算機技術(shù)與發(fā)展，2012，22（4）：25?28.

[13] 藺紹良，龍海南.基于穩(wěn)定性的AODV協(xié)議的研究與仿真[J].微型機與應用，2013，32（20）：48?50.