戰(zhàn)術MANET中基于鏈路可用時間的AODV路由協議研究＊

周 膠，田 杰，戴晨鋮，李婷君

（武警工程大學研究生管理大隊，陜西 西安 710086）

1 引言

移動Ad Hoc網絡[1]（MANET）是指由一組無線移動節(jié)點組成，不需要依靠現有固定通信網絡基礎設施并能夠迅速投入使用的網絡體系，具有很高的可靠性和靈活性。移動Ad Hoc網絡的高機動性和快速開展使其在加強戰(zhàn)場通信和提高戰(zhàn)場通信系統(tǒng)的生存能力方面有廣泛的應用[2]，戰(zhàn)術MANET 就是MANET 在戰(zhàn)場環(huán)境下的應用。MANET 中移動節(jié)點位置的快速變化導致網絡拓撲結構改變、網絡信息（例如路由表）作廢以及節(jié)點間鏈路斷開[3]。為了保證網絡中數據傳輸的穩(wěn)定性，減少重路由過程，通過研究路由協議在網絡中找到一條相對穩(wěn)定的路徑一直是Ad Hoc網絡研究的熱點[4]。近年來突出鏈路穩(wěn)定性的路由協議[5]、網絡安全的路由協議[6]以及車載自組網路由協議[7]等仍是研究的熱點。

AODV[8]路由協議是一種經典的按需路由協議。在路由發(fā)送過程中，選取路徑時只考慮路由的跳數、新舊程度等，而不能保證選取路徑的相對穩(wěn)定性；在路由維護階段，只有在鏈路斷開時才啟動路由維護過程，降低了數據發(fā)送的穩(wěn)定性。在文獻[9]中，節(jié)點通過計算轉發(fā)角來發(fā)送數據，數據發(fā)送的成功率有所降低，同時計算鏈路失效時間沒有考慮節(jié)點的移動對下一時刻鏈路失效時間的影響。文獻[10]通過能量預測鏈路的可用性，對于鏈路狀況的預測準確度要比GPS（Global Positioning System）定位系統(tǒng)差。

本文在深入研究AODV路由協議的基礎上，針對其選取鏈路的不穩(wěn)定性、路由修復較慢等特點提出一種改進路由協議LAT-AODV，該協議結合GPS系統(tǒng)，能夠與部隊的實際作戰(zhàn)需求充分結合。LAT-AODV路由協議通過GPS定位系統(tǒng)計算鏈路可用時間以及路徑的最大可用時間，使得源節(jié)點在路由建立過程中把路徑的最大可用時間作為選取路徑的標準。在路由恢復階段，通過設定時間觸發(fā)器，當鏈路可用時間低于閾值時則認為鏈路不可用，啟動鏈路修復機制，在鏈路斷開以前切換路徑，保證數據的穩(wěn)定傳輸。

2 預測式鏈路可用時間算法

假設在戰(zhàn)術MANET 中每個節(jié)點都配置GPS定位系統(tǒng)，而且本模型中電源的可用時間遠大于通過計算得出的鏈路生存時間。預測式鏈路可用時間算法的核心思想是：相鄰節(jié)點通過GPS系統(tǒng)交換時標和坐標信息，計算節(jié)點間的鏈路生存時間。當中間節(jié)點轉發(fā)路由請求和路由應答時，通過記錄前幾次的鏈路生存時間，借助隨機停留點模型計算下一段時間鏈路連續(xù)可用的概率，計算鏈路可用時間。

2.1 鏈路生存時間

假設節(jié)點n1、n2為兩相鄰節(jié)點，在t1、t2時刻節(jié)點n1的坐標為（x1n1，y1n1）和（x2n1，y2n1），節(jié)點n2的坐標為（x1n2，y1n2）和（x2n2，y2n2）。在以n1為坐標原點的極坐標中，t1、t2時刻，n2在極坐標系中的坐標為（R1，α1）和（R2，α2），通過計算可得出：

如圖1a所示，點A 和點B 表示n2在t1和t2時刻的位置，圖中的箭頭表示n2相對于n1的移動方向，則可以根據位置信息和時間信息計算出n2相對于n1的運動速度：

Figure 1 Two nodes movement圖1 兩節(jié)點運動方式

假設在預測的過程中節(jié)點從B 運動到C 的過程中速度不變，當節(jié)點n2運動到C 時即將脫離n1的通信范圍，所以節(jié)點n2從B 運動到C 的時間即為n1n2間鏈路的生存時間。兩節(jié)點間的鏈路生存時間為：

其中，R 表示節(jié)點的通信范圍，即圖1a中大圓的半徑，T＝e （n1，n2）即為鏈路n1n2的鏈路生存時間。

圖1a表示兩節(jié)點距離先近后遠的情況，圖1b表示兩節(jié)點反向運動的情況，R 表示節(jié)點的通信范圍，即圖1b中大圓的半徑，其計算過程如下：

根據以上公式，可以計算出每個節(jié)點與其相鄰節(jié)點鏈路生存時間e（n1，n2）。

2.2 鏈路危險時間

鏈路危險時間是指當鏈路可用時間小于閾值時，即視為鏈路即將斷裂。在路由請求過程中，若鏈路可用時間低于鏈路危險時間，則節(jié)點不轉發(fā)上一跳節(jié)點的路由請求RREQ（Route REQuest），既保證了鏈路的可靠性又限制了路由請求的廣播范圍。在路由維護階段，當鏈路的可用時間低于鏈路危險時間時，啟動路由維護過程，在鏈路真正斷開前進行路由維護，保證數據穩(wěn)定傳輸。LATAODV路由協議的路由維護過程包括：路由危險警告或者路由出錯和路由建立。現考慮最壞的情況，每種消息經過的跳數都是網絡直徑的值，路由建立過程包括路由請求和路由應答，則改進后AODV路由維護過程的總跳數為網絡直徑的三倍。假定鏈路的可用時間小于最大的路由維護時間，則認為鏈路處于一種危險狀態(tài)，實驗選擇的網絡直徑為NET＿DIAMETER，根據文獻[8]可知，每一跳的傳輸時延為30ms，則鏈路危險時間為：

2.3 鏈路可用時間

鏈路的生存時間表示的是某一時刻相鄰節(jié)點可通信的時間，LAT-AODV路由協議通過三個連續(xù)時刻鏈路的生存時間預測在下一段時間內鏈路連續(xù)可用的時間。

假設n1和n2表示網絡中兩個相鄰的節(jié)點，節(jié)點n1記錄與節(jié)點n2最近三個周期中的鏈路生存時間分別為eT-2（n1，n2）、eT-1（n1，n2）、eT（n1，n2），eT-2（n1，n2）表示當前T 時刻計算出的鏈路生存時間，eave（n1，n2）表示三個周期鏈路生存時間的平均值，Δe（n1，n2）表示當前鏈路生存時間變化率，Δe（n1，n2）的計算方法為：

判斷Δe（n1，n2）的大小：

（1）若Δe （n1，n2）≥0，說明兩節(jié)點有靠近的趨勢，則鏈路處于安全狀態(tài)，鏈路可用時間t（n1，n2）計算方法為：

其中α、β、φ 表示歷史信息對將來信息的影響，為了不失一般性，三個參數的取值如下：α＝0.6，β＝0.3，φ＝0.1。

（2）若Δe （n1n2）＜0，表示兩節(jié)點的通信距離有變遠的趨勢，則可根據隨即停留點模型計算鏈路從T 到T＋t時刻連續(xù)可用的概率有[11]：

根據計算出的鏈路可用性概率P（t），鏈路的可用時間為：

其中，α＝0.6，β＝0.3，φ＝0.1。

3 LAT-AODV路由算法

與傳統(tǒng)的AODV 算法相比，LAT-AODV路由算法有以下四點改進：

（1）在路由請求階段，在RREQ 數據包中添加鏈路可用時間和上一跳節(jié)點參數，選擇性轉發(fā)上一跳節(jié)點的路由請求數據包，降低網絡負載，提高所選路徑的可靠性。

（2）在回溯階段，在路由應答數據包RREP（Route REPly）中添加路徑可用時間參數和上一跳節(jié)點參數，記錄每一條路徑的可用時間。

（3）當節(jié)點發(fā)現鏈路生存時間小于鏈路危險時間時，啟動路由恢復機制，在鏈路斷開前切換路徑，保證數據的穩(wěn)定傳輸。

（4）在計算路徑可用時間時，若一條完整的路由路徑中的某一條鏈路不可用，則整個路徑也變得不可用，因此一條路由的可用時間依賴于整個路徑中最小的鏈路可用時間。

3.1 鏈路建立過程

LAT-AODV路由協議需要在RREQ 數據包中添加上一跳節(jié)點Lasthop 和鏈路可用時間Li-fetime 兩參數。如圖2所示，Lasthop 表示上一跳節(jié)點序列號，Lifetime 表示上一跳節(jié)點通過預測式鏈路可用時間算法計算出來的鏈路可用時間。LAT-AODV路由協議同時需要在節(jié)點路由條目中添加LRoutetime項，表示當前傳輸路徑的可用時間。

Figure 2 Data structure of RREQ圖2 RREQ 數據結構

3.1.1 路由請求過程

源節(jié)點廣播RREQ 數據包發(fā)送路由請求。中間節(jié)點i接收到RREQ 數據包，其工作過程如圖3所示。

Figure 3 Progress of routing request圖3 路由請求過程

（1）判斷接收到的RREQ 數據包中鏈路可用時間和鏈路危險時間的大小，若Lifetime＞TW進入（2）；否則說明該鏈路不可靠，不進行數據轉發(fā)。

（2）判斷路由表中是否有從節(jié)點i到達目的節(jié)點的路徑，若有則初始化RREP數據包，并回溯至源節(jié)點；否則進入（3）。

（3）節(jié)點i計算與其相鄰節(jié)點的鏈路可用時間，轉發(fā)新的RREQ 數據包，將本節(jié)點序列號和計算的鏈路可用時間添加到新RREQ 數據包對應的域。

3.1.2 路由回溯過程

在RREP數據包中添加上一跳節(jié)點Lasthop和路徑可用時間time。路徑可用時間time表示上一跳節(jié)點到目的節(jié)點的路徑持續(xù)可用時間Route（Lasthop，Dst）。

中間節(jié)點i接收到RREP 數據包時工作過程如下：

（1）節(jié)點i計算其與上一跳節(jié)點的鏈路可用時間t（i，Lasthop），比較t（i，Lasthop）和Route（Lasthop，Dst）的大小，選取較小的作為路徑可用時間Route（i，Dst）。

（2）將time＝Route（i，Dst），Lasthop＝i放入新的RREP 數據包中，同時初始化本地路由表中到達目的節(jié)點的路由LRoutetime＝Route（i，Dst），繼續(xù)回溯。

當源節(jié)點S 接收到RREP時，Route（S，Dst）＝min｛t（S，Lasthop），Route（Lasthop，Dst）｝。源節(jié)點S 比較所有回溯的路徑，選取Route（S，Dst）最大的路徑為到達目的節(jié)點的路由，同時修改LRoutetime＝Route（S，Dst）。

3.2 路由維護過程

LAT-AODV路由協議路由維護的思想是在鏈路真正斷開前實現路由修復過程，保證數據的穩(wěn)定傳輸。當中間節(jié)點檢測到其與下一跳節(jié)點的鏈路可用時間小于鏈路危險時間TW時，節(jié)點即啟動鏈路修復，其修復過程不影響正在傳輸的數據，保證數據穩(wěn)定傳輸。

4 仿真與分析

仿真實驗采用NS-2.35[12]，實驗在1 000m×1 000m的矩形仿真場景中選取40個節(jié)點，節(jié)點的移動速度變化范圍為10m／s～35m／s，仿真實驗參數參見表1。

Table 1 Experimental parameters表1 實驗參數

實驗中兩組算法性能比較結果如圖4～圖6所示。

Figure 4 Packet delivery ratio圖4 數據包投遞率

Figure 5 Network end-to-end throughput圖5 網絡吞吐量

Figure 6 Network end-to-end delay圖6 端到端時延

當節(jié)點的移動速度從10m／s增加到35m／s時，LAT-AODV路由協議的包投遞率降低了32個百分點，AODV路由協議的包投遞率降低了41個百分點；LAT-AODV路由協議的網絡吞吐量降低了36個百分點，AODV路由協議的網絡吞吐量降低了48 個百分點；LAT-AODV路由協議的網絡時延增加了500ms，AODV路由協議的網絡時延增加了630ms。當節(jié)點的移動速度增加到25m／s以后，節(jié)點的快速移動導致網絡的拓撲結構快速變換，鏈路穩(wěn)定性降低，兩種協議的網絡性能都顯著降低。但是，LAT-AODV路由協議的性能要明顯高于AODV路由協議，這是因為LATAODV 在路由建立過程中充分考慮路徑的穩(wěn)定性，在路由維護階段對可能斷開的鏈路提前進行路由維護，保證了數據的穩(wěn)定傳輸。

5 結束語

本文在AODV路由協議的基礎上，運用鏈路可用時間算法，提出LAT-AODV路由協議。基于GPS定位系統(tǒng)，利用位置信息計算鏈路的可用時間，在路由建立階段為源節(jié)點找到路徑可用時間最大的路由，在路由維護階段對可能斷開的鏈路提前維護，保證數據的穩(wěn)定傳輸。仿真實驗表明，LATAODV路由協議在數據包投遞率、網絡吞吐量、端到端時延方面有顯著的提高。下一步在鏈路可用時間計算上，根據鏈路生存時間的變化趨勢，通過擬合函數計算下一時間段的鏈路可用時間，驗證新算法得出的LAT-AODV路由協議性能。

[1]Chen Lin-xing，Zeng-xi.Mobile Ad hoc networks：Self-organizing packet radio network technology[M].Beijing：Publishing House of Electronics Industry，2006：4-11.（in Chinese）

[2]Sharret I P.WIN-T—The army's new tactical intranet[C]∥Proc of IEEE MILCOM'99，1999：1383-1387.

[3]Jun Luo，Hubaux J-P.Joint sink mobility and routing to maximize the lifetime of wireless sensor networks：The case of constrained mobility[J].IEEE Transactions on Networking，2010，18（3）：871-884.

[4]Tyagi S，Chauhan R.Performance analysis of proactive and reactive routing protocols for ad hoc networks[J].International Journal of Computer Applications，2010，1（14）：27-30.

[5]Rajendiran M，Srivatsa S K.Stable route link in on-demand multicast routing protocol for ad hoc networks[J].Procedia Engineering，2012，38：1391-1398.

[6]Qabajeh L K，Kiah M L M，Qabajeh M M.A more secure and scalable routing protocol for mobile ad hoc networks[J].Security and Communication Networks，2012，6（3）：286-308.

[7]Bhaumik M，DasGupta S，Saha S.Affinity based clustering routing protocol for vehicular ad hoc networks[J].Procedia Engineering，2012，38：673-679.

[8]Perkings C，Belding E，Royer B，et al.RFC365l，Ad hoc ondemand distance vector（AODV）routing[S].IETF，2003.

[9]Xia Zi-jun，Liu Chun-feng，Zhao Zeng-hua，et al.Routing algorithm in vehicular Ad Hoc network based on link prediction[J].Computer Engineering，2012，38（4）：110-111.（in Chinese）

[10]Hong Li，Huang Ting-pei，Zou Wei-xia.Research of AODV routing protocol based on link availability prediction[J].Journal on Communications，2008，2.（7）：118-123.（in Chinese）

[11]Bettstetter C，Hartenstein H，Perez-costa X.Stochas-tic properties of the random waypoint mobility model[J].ACM／Kluwer Wireless Networks，2004，10（5）：555-567.

[12]Ke Zhi-heng，Cheng Rong-xiang，Deng De-xie.Simulation of NS2—Multimedia and wireless communication networks[M].Beijing：Publishing House of Electronics Industry，2009.（in Chinese）

附中文參考文獻：

[1]陳林星，曾曦，曹毅.移動Ad Hoc網絡：自組織分組無線網絡技術[M].第2版.北京：電子工業(yè)出版社，2006.

[9]夏梓峻，劉春鳳，趙增華，等.基于鏈路預測的VANET路由算法[J].計算機工程，2012，38（4）：110-111.

[10]洪利，黃庭培，鄒衛(wèi)霞，等.基于鏈路可用性預測的AODV路由協議研究[J].通信學報，2008，2.（7）：118-123.

[12]柯志亨，成榮祥，鄧德雋.NS2仿真實驗——多媒體和無線網絡通信[M].北京：電子工業(yè)出版社，2009.