基于鏈路穩(wěn)定性預測的Ad Hoc網絡路由算法研究

姜延濤

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

1 課題來源

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

2 多路路由算法分析

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

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

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

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

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

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

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

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

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

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

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

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

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

節(jié)點的地理位置坐標定義為

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

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

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

struct MobilityData{

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

4.1 仿真環(huán)境

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

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

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

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

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

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

4.2 仿真結果與性能分析

移動速度：

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

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

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

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

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