基于可靠穩定性評價的MANET多路徑路由優化算法

李智楠 楊曉冬②

?

基于可靠穩定性評價的MANET多路徑路由優化算法

李智楠*①楊曉冬①②

①(哈爾濱工程大學信息與通信工程學院 哈爾濱 150001)②(日本明星大學聯合研究中心 東京 191-8506)

針對移動Ad hoc網絡動態拓撲特性，該文提出一種以可靠路徑穩定度估計為基礎的多路徑路由優化算法。該算法從路徑剩余生存期統計特性出發，充分考慮相鄰鏈路生存期相關性，從而消除已有算法在路徑穩定度估計中存在的理論誤差，并利用優化后的穩定度準則實現路由發現進程的多路徑選取和基于備用路徑支持的快速路由修復。仿真對比結果表明，該算法具有較快的收斂速度，能夠有效提高網絡吞吐量，縮短數據傳輸時延并降低路由開銷，更好地保證較高節點移動度下的數據傳輸穩定性。

移動Ad hoc網絡；路徑剩余生存期；穩定性估計；多路徑路由；路由修復

1 引言

為了緩解移動Ad hoc網絡(MANET)時變拓撲特性對移動傳輸的不利影響，近年來基于鏈路或路徑剩余生存期(Residual Link/Path Lifetime, RLL/ RPL)估計的鏈路動態特性分析[1]及“穩定性”優先路由策略成為了MANET研究關注的重點。雖然現有算法一定程度上實現了網絡優化，但仍存在很多不足。首先，以RLL估計為基礎的路由算法強調鏈路級別的逐跳路由決策[5,6]，造成大量網絡資源及節點能量消耗；其次，路徑穩定性分析中的RPL估計均忽略了由節點共享引起的相鄰鏈路RLL相關性[3,7]，造成的估計誤差使算法在優化能力方面具有很大局限性；另外，上述問題同樣存在于已有的多路徑穩定性路由策略中，限制了算法可靠性。

為了彌補這一不足，本文在充分考慮相鄰鏈路RLL相關性前提下，提出一種以路徑RPL統計特性作為穩定性評價標準的多路徑路由優化算法(RELiability-enhanced Multipath Source Routing, REL_MSR)。該算法基于反應式(reactive)源路由協議，改進了路由發現進程中路由請求(Route REQuest, RREQ)和路由應答(Route REPly, RREP)報文格式及其轉發處理機制，能夠實現備用路徑支持的快速路由修復。

2 RPL統計特性及穩定性標準

該穩定性標準提出的目的在于：(1)在RPL估計中充分考慮相鄰鏈路RLL統計相關性，提高理論建模準確性；(2)提供更可靠的多路徑選取準則，增強MANET動態環境下的通信連續性。

2.1 多條鏈路RLL聯合概率密度分布

目前絕大部分MANET路由優化策略[3,12,13]在RLL與RPL統計特性分析中，為簡化計算或降低算法復雜度，均沿用如下結論：多跳路徑生存期()服從指數分布[3,13]且可由構成該路徑的條鏈路生存期()表示為[12]

以上結論前提條件為：(1) 路徑中各鏈路生存期保持統計獨立[12]；或(2) 路徑跳數足夠多，各鏈路長度足夠大(漸進條件)[13]。如圖1所示，鏈路和生存期同時受共享節點移動性的影響，必然存在相關性，文獻[14]給出了該相關性的仿真證明，因此條件(1)中的獨立性假設并不成立；實際MANET部署受能量供給和通信質量影響，節點傳輸范圍和路徑跳數均受限，因此條件(2)很難滿足。針對上述問題，本文在已有工作[14]基礎上，以充分考慮RLL相關性為前提，提出一種更準確的鏈路及路徑穩定性統計定義方法。根據圖1給出的多跳路徑移動參數，設節點傳輸半徑為,為RLL估計時刻與相對距離，,為速度和方向角，為的RLL(且)。文獻[14]中式(15)給出當固定時的概率密度分布(PDF)表達式：

(2)

(4)

(5)

(7)

進一步利用已知變量可得

(9)

(11)

各鏈路RLL聯合CDF為

(13)

雖然與鏈路獨立條件下的結果相比，本文理論建模復雜度有所增加，但當網絡中路徑跳數較少，各節點遵循統一且較為簡單的移動模型(如)時，很容易得到式(12)的解析解。

圖1 多跳路徑節點移動參數及RLL與RPL相互關系

圖2 ,與的相對速度及空間方位關系

2.2 鏈路及路徑穩定度評價準則

基于上述理論建模，本文進一步給出如下鏈路及路徑穩定度定義：

定義1 鏈路穩定度(Link RELiability, LREL)為鏈路RLL不小于特定時間間隔的概率，對于：

定義2 路徑穩定度(Path RELiability, PREL)為路徑RPL不小于的概率，對于路徑(含條鏈路)：

(15)

以上定義的合理性及優越性在于：(1)節點移動復雜度較低時，移動模型不受限；(2)充分體現了鏈路或路徑在規定時間內保持有效性的能力。另外，文獻[14]中表1給出：忽略鏈路RLL相關性會導致PREL估計值偏高，不利于路由選取。因此，本文所給定義能夠為路由算法提供更準確的穩定性評價標準。

2.3 PREL對網絡性能的影響

從網絡層角度，PREL的重要性主要體現在以下兩方面。首先實際代表某一預期時延為的數據經過路徑的成功傳輸概率。若時間內有個數據被成功接收，則網絡吞吐量可定義為

由式(17)可知：路由算法所選路徑PREL值與TD成反比，進一步證明了提高PREL的重要意義。

3 REL_MSR算法實現

與主動式(proactive)路由協議不同，反應式路由協議只在數據傳輸請求產生時創建節點間路由，節省了路由維護成本。動態源路由協議(Dynamic Source Routing, DSR)是經典的反應式路由協議，其最大特點為：RREQ中可攜帶通信節點間完整路由信息，便于LREL與PREL估計。這是REL_MSR算法優化的基礎。

3.1 RREQ轉發及參數更新

3.2 多路徑選取及RREP發送

REL_MSR算法采用基于LREL和PREL估計的多路徑選取，其特點為：主路徑(MP)和備用路徑(BP)允許“部分相交(partially disjoint)”[4](鏈路共享)。這一準則依據為：(1)節點間嚴格不相交(node disjoint)路徑數量受限于最小割定律[8]，且穩定度往往無法滿足傳輸要求；(2)若允許共享的鏈路足夠穩定，則可消除因單條鏈路斷裂導致多路徑同時失效的可能性，從而保證備用路徑數量和路由修復的有效性。

3.3 路由修復機制

基本源路由協議不具備路由修復機制。當數據傳輸中路徑失效，只能通過RREQ泛洪重啟路由發現進程，造成大量的路由開銷。REL_MSR算法利用備用路徑策略實現快速路由修復，具體方法為：當首先負責數據傳輸的MP失效，斷裂鏈路的上游節點向發送路由錯誤(Route ERRor, RERR)報文，選取PREL最高的BP作為新的MP進行數據續傳，若多條BP同時滿足要求，則選擇其中跳數最少的路徑。

圖3 REL_MSR算法RREQ及RREP報文格式

表1 目的節點處路由選取算法

算法1 目的節點處RREQ處理及路由選取描述： 目的節點收到來自上游節點的RREQ報文1 if () or (RREQ中路徑與已記錄的具有相同(,)的某條路徑重合) or (PREL<)2 丟棄RREQ報文3 else 將添加到RREQ的中4 if (為(,)對應第1條路徑)5 設置該路徑為MP6 為(,)設置選取BP7 else if ((,)路徑記錄已存在) and ()8 丟棄RREQ報文9 else if (與已有(,)路徑嚴格不相交)10 將該路徑加入并記錄其PREL11 else找出與已有(,)路徑的共享鏈路12 if (共享鏈路不包含)13 跳轉到15行14 else計算并設定15 檢驗所有共享鏈路16 if (所有檢驗結果 == 1)17 將該路徑加入并記錄其PREL計算結果18 else丟棄RREQ報文19 end all if

4 性能仿真及分析

運用MATLAB仿真平臺實現MANET建模，將本文REL_MSR算法與另外兩種穩定性路由算法PRMLE[3]和LEBR[6]進行對比。首先比較3種算法的路由發現收斂時間，再進一步通過吞吐量()、平均數據傳輸時延()和路由開銷()的仿真結果比較，驗證本文算法的有效性和優越性。表2給出了3種算法核心思想(不涉及PRMLE算法中繼節點網絡編碼部分)。其中LEBR基于按需距離矢量路由協議(Ad hoc On-demand Distance Vector, AODV)。AODV的 RREQ和RREP報文中只包含其轉發節點的一跳信息。PRMLE本地路由修復機制是指當數據傳輸路徑中某條鏈路穩定度降低時，中間節點可以進行數據緩存并啟動路由發現機制建立與目的節點的新路徑，而REL_MSR算法的路由修復則是由集中控制。

表2 3種算法核心思想及實現方法

算法名稱鏈路穩定性準則路徑穩定性準則算法類別路由修復鏈路相關性 PRMLE鏈路生存期()：相鄰節點接收功率周期性采樣，文獻[3]式(1)~式(18)路徑生存期()：改進DSR單BP中間節點本地修復不考慮 LEBR鏈路有效性(L)：鏈路LL與平均LL之比，文獻[6]式(29)和式(30)路徑有效性(): 改進AODV無BP無不考慮 REL_MSRLREL：式(14)PREL：式(15)改進DSR多BP源節點修復考慮

4.1 算法收斂時間仿真對比

本文針對反應式路由算法改進，為了考察算法收斂速度，比較REL_MSR與PRMLE, LEBR算法的路由發現收斂時間，即路由建立時間[15](平均完成單個(,)路由請求的耗時)。仿真實現方法為：(1)將個移動節點隨機分布于面積為100 m×100 m的區域內，各算法以=5 s為周期執行單次路由發現，共進行100次；(2)各周期(,)隨機選取，于周期初始時刻廣播RREQ，當成功接收規定數量的RREP報文時，路由發現結束；(3)單周期內各節點移動速度和方向服從均勻分布(V~U(0,max),且保持恒定；(4)各算法每隔記錄路由發現耗時，最終取100次輸出記錄的平均值作為結果。

為了排除網絡協議棧其他各層因素(如節點間通信退避機制，傳輸帶寬配置)、單個節點計算延遲及路由表存儲對算法性能評估的影響，仿真進一步假設：(1)路由發現過程中只有可以發送RREP報文，中間節點只負責報文轉發和處理；(2) RREQ在各轉發節點所需更新時間統一設為20 ms，即轉發同步(不考慮各算法在計算所需參數時的復雜度差異)；(3)相鄰節點報文傳輸耗時均為40 ms；(4)PRMLE和本文REL_MSR算法處RREP接收(路徑選取)時限為60 ms，仿真為LEBR算法設置相同的路徑選取時限，目的是使其在單次路由決策中選出最優路徑；(5)鏈路斷裂條件為兩節點間距離大于傳輸半徑=15 m，若負責RREP傳輸的鏈路在其經過前發生斷裂，則路由建立失敗，需立即重新廣播RREQ再次嘗試路由發現。

圖4 節點數變化時仿真結果

圖5 節點移動度變化時仿真結果

4.2 網絡性能指標仿真對比

現考慮算法改進對網絡整體性能影響，首先做如下假設：(1)仿真中不考慮MAC層及物理層環境影響(如信道衰落或亂序造成的傳輸誤差)，數據到達即視為正確接收；(2)鏈路具有足夠帶寬避免網絡擁塞；(3) RREP報文均能被正確接收；(4)路由修復允許數據續傳，無需重啟路由發現；(5)若路由發現重新啟動，則丟棄數據流中已接收到的部分，等待重傳；(6)各節點隨機移動模型相同：V。

仿真參數設置如表3所示。仿真中應用層采用的每個CBR數據流預期傳輸時延(time slot)。本文REL_MSR算法及估計中取。為算法預設因子，設置目的在于：理論上規定并保證各鏈路(路徑)RLL(RPL)值大于。仿真中設。其次，各組參數下系統在仿真周期()初始時刻分配60個數據請求(含不同,)，后輸出并記錄各項性能指標，仿真截止(100)后各指標取其所有輸出值的均值作為最終統計結果。最后，仿真中若路由發現進程重啟3次后數據傳輸仍無法完成，則數據丟失。另外，設PRMLE算法用于功率采樣的HELLO報文發送周期為1 (time slot)。

表3 網絡性能仿真參數設置

參數名稱參數設置 仿真區域400 m×400 m 節點數600~800 仿真周期100 time slot 仿真運行時間100 數據類型固定速率數據流(CBR) 單個數據尺寸100 packets 發送速率2 packet/time slot 路由協議PRMLE/LEBR/REL_MSR 路徑選取時限Timer =2 (time slot) 節點傳輸半徑50 m 節點最小速率0 節點最大速率1~6 m/s

綜上所述，圖6-圖11的仿真結果充分驗證了本文算法的有效性及優越性：與現有算法相比，REL_MSR算法充分考慮了相鄰鏈路RLL相關性，能夠建立更準確、可靠的穩定性評估準則，使數據傳輸依賴于生存期更長的路徑，有效減弱節點高速移動對數據傳輸造成的不利影響，具有更強的適應性，并且在提高網絡，縮短數據的同時保證較低的，實現穩定性與資源利用的合理兼顧。

圖6 節點數變化時仿真結果

圖7 節點數變化時仿真結果

圖8 節點數變化時仿真結果

圖9 節點移動度變化時仿真結果

圖10 節點移動度變化時仿真結果

圖11 節點移動度變化時仿真結果

5 結束語

本文在路徑RPL統計特性分析基礎上，充分考慮相鄰鏈路RLL相關性，提出一種優化的路徑穩定性評估準則，進而提出一種基于可靠路徑穩定度估計的多路徑路由優化算法。仿真對比結果表明：與已有穩定性路由算法相比，本文算法能夠提供更可靠的路徑穩定性評估準則，在網絡拓撲動態性較高的情況下依然能夠保持較快的收斂速度，并且能夠有效降低節點移動度上升對數據傳輸造成的不利影響，在提高MANET網絡吞吐量，縮短數據傳輸時延，減少路由開銷方面具有重要意義。

[1] 鄭博, 黃國策, 張衡陽. 三維移動Ad hoc網絡鏈路動態性研究[J]. 電子與信息學報, 2011, 33(11): 2605-2609. doi: 10.3724/SP.J.1146.2011.00191.

ZHENG Bo, HUANG Guoce, and ZHANG Hengyang. Link dynamics in three-dimensional mobile Ad hoc networks[J].&, 2011, 33(11): 2605-2609. doi: 10.3724/SP.J.1146.2011.00191.

[2] MOUSSAOUI A and BOUKEREAM A. A survey of routing protocols based on link-stability in mobile ad hoc networks[J]., 2015, 47: 1-10. doi: 10.1016/j.jnca.2014.09.007.

[3] WU Dapeng, WANG Ruyan, and ZHEN Yan. Link stability- aware reliable packet transmitting mechanism in mobile ad hoc network[J]., 2012, 25(12): 1568-1584. doi: 10.1002/dac.1323.

[4] SALEEM M, ULLAH I, KHAYAM S A,. On the reliability of ad hoc routing protocols for loss-and-delay sensitive applications[J]., 2011, 9(3): 285-299. doi: 10.1016/j.adhoc.2010.07.012.

[5] AKBARI TORKESTANI J and MEYBODI M R. A link stability-based multicast routing protocol for wireless mobile ad hoc networks[J]., 2011, 34(4): 1429-1440. doi: 10.1016/j.jnca. 2011.03.026.

[6] LEI Lei, WANG Dan, ZHOU Liang,. Link availability estimation based reliable routing for aeronautical ad hoc networks[J]., 2014, 20: 53-63. doi: 10.1016/ j.adhoc.2014.03.005.

[7] WU Dapeng, ZHOU Jianer, and WANG Ruyan. Received signal strength based link lifetime estimating mechanism in MANET[C]. IEEE Conference Anthology, Chongqing, China, 2013: 1-4. doi: 10.1109/ANTHOLOGY.2013.6784986.

[8] SANTOS M A S, PORRAS D E T, SILVEIRA R M,. Multipath source routing strategies for video transmission in ad hoc wireless networks[J]., 2014, 21(3): 859-869. doi: 10.1007/s11276-014-0823-x.

[9] KUMAR C N and SATYANARAYANA N. Multipath QoS routing for traffic splitting in MANETs[J]., 2015, 48: 414-426. doi: 10.1016/j.procs. 2015.04.115.

[10] YI J, ADNANE A, DAVID S,. Multipath optimized link state routing for mobile ad hoc networks[J]., 2011, 9(1): 28-47. doi: 10.1016/j.adhoc.2010.04.007.

[11] YANG Wenjing, YANG Xinyu, YANG Shusen,. A greedy-based stable multi-path routing protocol in mobile ad hoc networks[J]., 2011, 9(4): 662-674. doi: 10.1016/j.adhoc.2010.09.004.

[12] Trivi?o-Cabrera A, García-de-la-Nava J, Casilari e,. Application of path duration study in multihop ad hoc networks[C]. IFIP Advances in Information and Communication Technology, Prague, Czech Republic, 2007: 63-74. doi: 10.1007/s11235-008-9094-0.

[13] HAN Y, LA R J, Makowski a m,. Distribution of path durations in mobile ad hoc networks-Palm’s theorem to the rescue[J]., 2006, 50(12): 1887-1900. doi: 10.1016/j.comnet.2005.10.005.

[14] LI Zhinan and HAAS Z J. On residual path lifetime in mobile networks[J]., 2016, 20(1): 185-188. doi: 10.1109/LCOMM.2016.2520467.

[15] FENG Renjian, LI Tongling, WU Yinfeng,. Reliable routing in wireless sensor networks based on coalitional game theory[J]., 2016, 10(9): 1027-1034. doi: 10.1049/iet-com.2015.0884.

Optimized Multipath Routing Algorithm for MANET Based on Reliable Stability Estimation

LI Zhinan①YANG Xiaodong①②

①(,,150001,)②(,191-8506,)

To deal with dynamic network topology in Mobile Ad hoc NETworks (MANETs), a reliability-enhanced multipath source routing algorithm is proposed based on accurate path stability estimation. In order to eliminate theoretical errors existing in current approaches, statistical properties of residual path lifetime are exploited by fully introducing correlation among neighboring links’ residual link lifetime. Optimized link and path stability metric is then provided to realize a multipath-enabled routing discovery procedure and a backup path-support fast routing recovery mechanism. Simulation results show that the proposed routing algorithm can achieve fast routing discovery convergence, increase network throughput, reduce data transmission delay, and lower routing overhead. Furthermore, high network reliability can be well guaranteed even under high node mobility degree.

Mobile Ad hoc NETworks (MANETs); Residual path lifetime; Stability estimation; Multipath routing; Routing recovery

TN929.5

A

1009-5896(2017)03-0605-08

10.11999/JEIT160462

2016-05-09；改回日期：2016-11-21；

2017-01-11

李智楠 zhinan5447@163.com

李智楠： 女，1987年生，博士生，研究方向為無線通信系統理論、MANET路由優化算法.

楊曉冬： 男，1963年生，教授，博士生導師，主要研究方向為現代通信系統技術與理論、現代天線技術.