基于路徑穩定性的MAODV路由協議的改進

李帥　蔡明

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

關鍵詞： 無線自組織網絡； 路由協議； 路徑穩定度； 網絡仿真

中圖分類號： 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 引 言

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

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

1 RS?MAODV路由算法

1.1 算法設計思想

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

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

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

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

1.2 網絡模型和標記

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

1.2.1 鏈路的穩定度SPL

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

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

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

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

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

[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時間間隔內，節點i和節點j的相對位置變化量Δdij為：

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

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

[SPL=1-ΔdijR] （5）

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

1.2.2 路徑的穩定度SPR

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

[SPR=i=1nSPLi] （6）

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

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

式中：SPR為所求路徑的穩定度；SPL1，SPL2，…，SPLm分別表示組成路徑的各段鏈路的穩定度值；ρ1，ρ2，…，ρm-1分別表示各相鄰鏈路之間的相關因子，詳細計算方法見參考文獻[11]；f1（ρ1），f2（ρ2），…，fm-1（ρm-1）分別表示各相鄰鏈路間的相關性結構。這里，相關性結構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）

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

1.3 算法流程概述

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

算法在路由發現階段的操作流程如下：

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

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

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

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

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

2 仿真實驗

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

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

2.1 丟包率

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

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

2.2 端到端延遲

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

從圖5中觀察到，一定節點移動速度下，MAODV協議比RS?MAODV協議的端到端延遲要小，這是因為MAODV協議選擇一條從源節點到多播組的最短連通路徑，使得相應端到端延遲要小。隨著網絡運行時間的增加，網絡拓撲結構發生變化，用于數據傳輸的路徑不斷遭到破壞，網絡擁塞程度加劇，兩種協議對應的端到端延遲均變大。然而RS?MAODV協議由于考慮了所選路徑的穩定性，減少了因節點失效引起的路由恢復和重構的時延，在相同條件下，相比MAODV協議端到端延遲也較小。

3 結 語

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

參考文獻

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

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

[3] 徐文濤，晁愛農.一種移動Ad Hoc網AODV路由協議的改進方法[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] 黃錢飛，萬俊，邱海燕.移動自組織網中基于鏈路預測的路由研究[J].電腦與電信，2012（8）：36?38.

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

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

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

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

[10] 趙繼紅，金依紳.基于移動預測的MESH網絡穩定性算法研究[J].無線通信技術，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] 肖權權，段迅.基于NS2的網絡仿真與性能測試[J].計算機技術與發展，2012，22（4）：25?28.

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