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

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

1 引言

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

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

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

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

假設在戰(zhàn)術MANET 中每個節(jié)點都配置GPS定位系統(tǒng)，而且本模型中電源的可用時間遠大于通過計算得出的鏈路生存時間。預測式鏈路可用時間算法的核心思想是：相鄰節(jié)點通過GPS系統(tǒng)交換時標和坐標信息，計算節(jié)點間的鏈路生存時間。當中間節(jié)點轉(zhuǎn)發(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的移動方向，則可以根據(jù)位置信息和時間信息計算出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中大圓的半徑，其計算過程如下：

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

2.2 鏈路危險時間

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

2.3 鏈路可用時間

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

假設n1和n2表示網(wǎng)絡中兩個相鄰的節(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）的大?。?/p>

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

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

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

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

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

3 LAT-AODV路由算法

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

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

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

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

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

3.1 鏈路建立過程

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

Figure 2 Data structure of RREQ圖2 RREQ 數(shù)據(jù)結構

3.1.1 路由請求過程

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

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

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

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

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

3.1.2 路由回溯過程

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

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

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

（2）將time＝Route（i，Dst），Lasthop＝i放入新的RREP 數(shù)據(jù)包中，同時初始化本地路由表中到達目的節(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路由協(xié)議路由維護的思想是在鏈路真正斷開前實現(xiàn)路由修復過程，保證數(shù)據(jù)的穩(wěn)定傳輸。當中間節(jié)點檢測到其與下一跳節(jié)點的鏈路可用時間小于鏈路危險時間TW時，節(jié)點即啟動鏈路修復，其修復過程不影響正在傳輸?shù)臄?shù)據(jù)，保證數(shù)據(jù)穩(wěn)定傳輸。

4 仿真與分析

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

Table 1 Experimental parameters表1 實驗參數(shù)

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

Figure 4 Packet delivery ratio圖4 數(shù)據(jù)包投遞率

Figure 5 Network end-to-end throughput圖5 網(wǎng)絡吞吐量

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

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

5 結束語

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

[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網(wǎng)絡：自組織分組無線網(wǎng)絡技術[M].第2版.北京：電子工業(yè)出版社，2006.

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

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

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