基于鏈路穩定性預測的Ad Hoc網絡路由算法研究

姜延濤

（中國人民解放軍65631部隊60分隊，遼寧 北鎮121300）

1 課題來源

移動Ad Hoc網絡[1]是一種多跳、自組織、分布式的無線網絡，它不需要集中式的網絡管理和基礎設施。針對Ad Hoc網絡的特點，國內外學者提出了很多路由協議。相對于單徑路由協議而言，后備路徑路由協議更能滿足容錯、路由可靠性要求，因而成為該領域的研究熱點。本文討論將成本函數應用到后備路由選擇中，再結合地理位置預測模型預測鏈路穩定性來確定主備路由，利用此算法改進AODV協議。最后通過軟件仿真的手段，論文實現了LS-BPR協議，并評價了它的路由性能。通過仿真驗證算法性能。

2 多路路由算法分析

隨著對Ad Hoc網絡的研究的不斷深入，單路路由協議的研究己經相對成熟。但是，簡單的單路路由協議還不能滿足容錯、路由可靠性等更高層次的路由要求。多路路由恰恰是解決這些問題的一個很好的途徑。

3 基于成本函數的后備路徑路由算法實現

3.1 成本函數中相關參數的定義及計算

在這里提出一種BPR（Backup Path Routing）算法，它是引入了成本函數作為后備路徑的選擇原則。在主路徑確定之后，再通過主路徑和所選路徑計算成本函數值，來確定需要的后備路徑。

為了能夠找到一個路由可靠度的衡量標準，我們需要一個近似的計算公式，來對路由有效期進行計算和比較。為此，BPR算法引入了成本函數的概念。給定備份路由對(λ,λ′)，當路徑長度|λ′|越小；節點相似度L(λ,λ′)越小；獨立子路徑R(λ,λ′)越大時，備份路由對的路由有效期都會越長，路徑就會越可靠。因此用備份路由對(λ,λ′)的成本函數值C(λ,λ′)的啟發式來估算路由可靠度。成本函數值與路由有效期成反比，C(λ,λ′)的值越小，備份路由對就越可靠。

定義:假設λ是主路徑,λ′是后備路徑，L(λ,λ′)是主備路徑對(λ,λ′)的鏈路相似度,R(λ,λ′)是主備路徑對(λ,λ′)不相交子路徑的數目,|λ′|表示后備路徑λ′的總跳數，則主備路徑對的(λ,λ′)的成本函數定義為:

由于主路徑上節點由于頻繁的移動造成無線鏈路發生斷裂時，由于后備路徑與主路徑公用節點的數目較少，所以也就降低了后備路徑也同樣發生斷裂的可能性，所以最可靠的后備路徑就要選擇使C(λ,λ′)值最小的后備路徑。

3.2 基于鏈路穩定性預測的后備路徑選擇算法研究

基于ARIMA模型分析方法的基本思路是：對于非平穩的時間序列，用若干次差分使其成為平穩序列，再用ARMA(p,q)模型對該平穩序列建模，之后經反變換得到原序列。并且根據樣本自相關函數、偏自相關函數的統計特性來判斷隨機序列適合哪一模型，進而確定模型階數[2]。

為了使用ARIMA模型改善BPR算法的性能，所以本文提出了基于運動軌跡預測鏈路穩定性的后備路徑路由算法LS-BPR（Link Stability Prediction Algorithm based on Backup Path Routing）。

LS-BPR算法的基本思想是，在確定源節點到目的節點的后備路徑時，考慮節點的移動性所帶來的鏈路穩定性的變化和鏈路的傳輸延遲，用鏈路有效時間來衡量鏈路穩定性，利用ARIMA預測模型預測節點移動性，提前得知下一時刻該節點的地理位置[3]，即能夠提前預測節點的運動軌跡，減少了后備路徑在下一時候斷開的可能性。通過GPS系統獲取節點的地理位置，形成一段時間序列，然后利用ARIMA預測模型對地理位置進行預測，得到下一時刻的地理位置，從而獲取一個節點的運動軌跡。

3.3 下一時刻地理位置的使用

在QualNet中，不存在GPS模塊，但是可以通過其他方法獲取到節點的地理位置，如下方法。

節點的地理位置坐標定義為

通過snt/qualnet/5.0/main/node.cpp文件我們知道節點當前地理位置為：

由于QualNet中只對二維拓撲進行仿真，那么在實際中，z坐標的值為0。

在snt/qualnet/5.0/include/mobility.h中增加定義了移動節點MobilityData的所存儲的歷史地理位置的信息：

struct MobilityData{

4 基于鏈路穩定性預測的后備路徑路由協議仿真與分析

4.1 仿真環境

根據移動自組網在實際中的應用，本文使用QualNet進行仿真，采用以下仿真場景進行仿真分析，仿真區域是在1500m×1500m的矩形區域，區域內隨機分布35個節點。節點的移動方式采用隨機路點移動方式，符合Random Waypoint模型，每個節點的移動速度最大值可調節，設備移動間隔尺寸為1m。發送CBR數據包，每個包大小為512字節，網絡流量以固定比特率CBR(Constants Bit Rate)產生，采用單信道，帶寬為2Mbps，仿真時間為100s，每個節點使用相同的無線收發設備，采用單一增益的全向天線，仿真比較LS-BPRAODV與AODV的性能。

為了反映不同路由協議在所設置場景下的網絡性能，本文選用平均端到端時延和數據包投遞率作為性能指標，分別從節點最大速度參數變化著手，研究以下兩種性能指標的變化規律：

（1）數據包投遞率（Packet Delivery Ratio）

分組投遞率是成功傳遞到目的端的數據包數與發送端成功發送的數據包數之比。該指標反映了接收方受網絡拓撲變化影響的程度。

（2）平均端到端時延(AverageEndtoEndDelay)

平均端到端時延是從源節點成功到達目的節點的所有數據分組的端到端時延的平均值。

4.2 仿真結果與性能分析

移動速度：

35個節點的最大移動速度分別為5m/s，10m/s,15m/s,20m/s,25m/s,30m/s,35m/s,40m/s時，移動方向隨機，共發100個數據包，每個CBR數據包大小為512字節，暫停時間20秒,發包率為1包/秒。仿真結果顯示當節點移動速度增加時，兩種協議的傳輸時延都在增大。這是因為節點的運動速度越大，網絡拓撲變化越激烈，那么路由斷裂的可能性大大增加，路由斷裂次數也大大增加，從而導致數據發送需要的等待時間增長，傳輸時延增加。由圖可得，但從圖中可以發現LS-BPR AODV受節點最大移動速度的影響相對較小。

仿真結果還顯示數據包投遞率與最大速度之間的關系。當節點運動速度增加時，LS-BPRAODV與AODV的投遞率都在降低。這是因為節點移動速度越大，網絡局部拓撲變化越激烈，造成路由中斷次數增加，目的節點不可達的現象增多，從而造成網絡的丟包率增加。由圖可得，LS-BPRAODV的丟包率要明顯低于AODV，這是因為在前者的路由算法中，加入了成本函數與地理位置預測算法。LS-BPRAODV偏向于利用丟包率更低的后備路由。同時，加入地理位置預測后，能夠提前預知鏈路的斷裂，減少路由中斷的次數。通過這兩種機制的同時作用，提升了數據包投遞率。

［1］陳代武.計算機網絡技術[M].北京:北京大學出版社,2009:290-292.

［2］王黎明,王連,楊楠.應用時間序列分析[M].上海:復旦大學出版社,2008:1-85.

［3］林彥汝,周繼鵬.基于地理位置的AdHoc路由協議[J].計算機應用,2011(1):225-228.