姜延濤

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

1 課題來源

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

2 多路路由算法分析

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

3 基于成本函數(shù)的后備路徑路由算法實現(xiàn)

3.1 成本函數(shù)中相關(guān)參數(shù)的定義及計算

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

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

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

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

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

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

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

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

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

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

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

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

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

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

struct MobilityData{

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

4.1 仿真環(huán)境

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

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

（1）數(shù)據(jù)包投遞率（Packet Delivery Ratio）

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

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

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

4.2 仿真結(jié)果與性能分析

移動速度：

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

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

［1］陳代武.計算機網(wǎng)絡(luò)技術(shù)[M].北京:北京大學(xué)出版社,2009:290-292.

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

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