基于穩定鏈路的移動AdHoc網絡路由算法

黃波 張小華

摘 要： 移動自組織網絡（MANETs）是無基礎設施、由移動節點構成的動態網絡。MANETs的移動特性給路由協議的設計提出挑戰。為此，以典型的按需路由（AODV）為基礎，提出基于鏈路穩定的MANETs路由協議，記為LSR。首先，分析了AODV的路由過程和不足，再計算節點能量壽命和鏈路壽命，然后通過比較能量壽命和鏈路壽命，構建候選轉發節點集，最后，從鏈路穩定性角度，選擇下一跳轉發節點。實驗結果表明，提出的LSR協議降低了路由開銷，提升了吞吐量。與AODV相比，LSR協議的路由開銷降低了近50%，吞吐量提高了23%。

關鍵詞： 移動自組織網絡； 路由； 按需路由； 鏈路壽命； 穩定鏈路； LSR協議

中圖分類號： TN915.05?34； TPT393 文獻標識碼： A 文章編號： 1004?373X（2018）17?0090?05

Abstract： The mobile Ad Hoc networks （MANETs） composed of mobile nodes act as the dynamic network without infrastructure， and its mobile characteristic challenges the design of routing protocol. On the basis of the typical Ad Hoc on?demand distance vector （AODV） routing， the stable link based MANETs routing protocol （LSR） is proposed. The routing process and deficiency of AODV are analyzed， and then the energy lifetime and link lifetime of the node are calculated. The candidate forwarding node set is constructed by comparing the energy lifetime with link lifetime. The next?hop forwarding node is selected in term of link stability. The experimental results show that the proposed LSR protocol can reduce the routing overhead and improve the throughput. In comparison with AODV， the routing overhead of LSR protocol is reduced by 50%， and the throughput is improved by 23%.

Keywords： MANETs； routing； on?demand routing； link lifetime； stable link； LSR protocol

0 引 言

節點的移動性是移動自組織網絡（Mobile Ad Hoc Networks，MANETs）[1?2]典型特性。由于節點自由移動，MANETs拓撲呈動態性變化。動態變化的拓撲對數據傳輸路徑提出挑戰。因此，路由技術成為MANETs的研究熱點。由于節點通信半徑有限，節點需要通過多跳傳輸方式才能將數據傳輸至目的節點。換而言之，數據包攜帶節點需要從鄰居節點中選擇某個節點作為下一跳節點，從而逐步建立完整的數據傳輸路徑。將尋找最優的下一跳轉發節點的過程稱為路由發現。

現有的路由協議[4?5]主要有：表格驅動型、按需以及混合型三類。OLSR[3]，DSDV[4]就是典型的表格驅動型路由。按需路由協議典型的有AODV（Ad Hoc On?demand Distance Vector）[5]，ABR[6]。按需路由協議是指只有當節點需要傳輸數據時，才啟動路由發現工作。混合型路由是指結合表格驅動型和按需型特點的路由，典型的有ZRP[7]，CEDAR[8]。

這些協議的主要差異在于路由發現機制的不同。表格驅動型路由是預先建立路由表，然后依據查表傳輸數據包。按需路由是當節點需要傳輸數據包時，通過傳輸路由請求（Route REQuest，RREQ）控制包和路由回復（Route REPly，RREP）包建立路由。

文獻[9]提出了基于鏈路生存時間的改進路由協議（Enhanced Routing Protocol on Ad Hoc On?demand Distance Vector with Speed Variance， SV_AODV）。SV_ AODV路由協議計算每條鏈路的速度方差，再選擇速度方差最小的路徑傳輸數據，提高了鏈路的穩定性。文獻[10]提出了AODV路由的改進協議AODV_D。AODV_D協議考慮了MAC層的節點競爭信息和接口隊列時延，降低了傳輸時延。文獻[11]提出AODV的優化協議，基于單播和廣播結合策略，實現路由探測，通過降低廣播幀數量，增強路由穩定性。文獻[12]提出了基于鏈路質量的改進AODV協議，通過設定鏈路質量閾值，丟棄鏈路質量差鏈路，提高了路徑穩定性。

本文研究了AODV協議的不足，然后針對移動自組織的特性，提出基于鏈路穩定的MANETs路由協議，記為LSR（Link Stable Routing）。LSR協議充分考慮了MANETs的移動特性，從鏈路的穩定性角度選擇下一跳轉發節點。實驗數據表明，提出的LSR協議能夠有效地提高數據包傳輸率，并降低了端到端傳輸時延。

1 AODV協議及問題描述

相對于其他反應式路由，AODV協議具有一定的優勢，具體而言，AODV協議是利用局部廣播發現路由。當節點需要傳輸數據包，它首先向鄰居廣播RREQ包。一旦是第一次收到RREQ包，鄰居節點就將自己信息加入RREQ包，并轉播，直到目的節點接收到RREQ包。

源節點與目的節點間可能存在多條路徑，因此，目的節點可能會收到來自不同路徑傳輸的RREQ包。目的節點就沿著傳輸RREQ包的路徑回復包，進而告知源節點，數據路徑通道已建立。

圖1顯示了AODV路由發現過程，其中圖1a）表述了RREQ的傳輸過程，圖1b）表示RREP的傳輸過程。具體而言，若源節點1需要傳輸數據包，就向鄰居節點廣播RREQ控制包，再由鄰居節點轉播，直到目的節點8接收到RREQ包。當目的節點8接收RREQ包后，就沿著傳輸RREQ包回復RREP包，即目的節點8沿著[8→5→2→1]向源節點1回復RREP控制包。源節點一旦接收了RREP，就意味著路由發現階段完成。

相比于其他反應式路由，AODV路由具有一定的優勢，如較低的控制開銷和按需特性[13]。但是對于移動自組織網絡而言，節點移動是一個重要特性。而傳統的AODV協議并沒有考慮到節點移動。基于AODV的改進RAODV協議考慮了節點的移動性。此外，節點能耗也是一個必須考慮的因素。其中MAODV?X考慮了節點能耗問題，將節點能耗融入鏈路的穩定性。然而，這些協議在路由發現過程中，只是單一考慮了節點移動或節點能耗。

為此，提出LSR協議。與傳統的AODV協議不同，LSR協議考慮了節點移動和能耗問題。同時，LSR協議不再建立從源節點至目的節點整條路徑，而是引用了基于位置路由的思想，從鏈路穩定性角度選擇下一個轉發節點。

2 LSR協議

LSR協議中節點通過交互HELLO消息，獲取網絡拓撲信息，并且每個節點傳輸半徑為[R]，覆蓋范圍為圓形。通過交互節點的局部信息，可計算節點能量消耗率，再計算節點能量壽命，然后計算鏈路壽命，最后，計算鏈路的穩定性。最終選擇最穩鏈路傳輸數據包。整個LSR協議框圖如圖2所示。

2.1 能量消耗率

首先，計算節點的剩余能量。假定節點[i]的初始能量為[Ei]。若節點[i]每傳輸一個數據包所需的能量為[Ti]，每接收一個數據包所消耗的能量為[Rk]。因此，在時刻[t]，節點[i]的剩余能量[REit]為：

2.2 鏈路的穩定性

2.3 下一跳轉發節點

假定源節點[S]需要轉發數據包，據此，節點[S]先向其鄰居節點廣播RREQ包，其包含了節點速度和位置。鄰居節點接收RREQ后，分別依據式（3）和式（9）計算能量壽命和鏈路穩定性，并將這些信息載入RREP，向源節點[S]回復RREP。

通過多次接收RREP后，源節點[S]就從鄰居選擇中選擇一個最合適的節點作為下一跳轉發節點。為此，源節點[S]選擇在節點能量壽命區間具有鏈路最穩定的節點作為下一跳節點。

具體而言，假定源節點[S]的一跳鄰居節點集為[NS]。源節點[S]就分別比較一跳鄰居節點（假定節點[i∈NS]）的能量壽命與鏈路壽命。只有能量壽命大于鏈路壽命的節點才能作為候選轉發節點集[ψS]，如式（10）所示。反之，若能量壽命小于鏈路壽命，即數據在傳輸過程中，節點能量消耗殆盡，這將導致鏈路中斷。

2.4 路由發現流程

當源節點[i]需要向目的節點[d]傳輸數據包時，先向鄰居廣播RREQ控制包。接收了RREQ控制包后，首先檢測是廣播ID，若之前已接收過同樣的ID，則丟棄。否則進一步判斷自己是否是目的節點，如果是，就直接回復RREP控制包，否則就計算能量壽命和鏈路壽命，并將這些信息載入RREP，再向源節點[i]回復RREP控制包。源節點接收多個RREP包后，依據式（10）構建一跳候選轉發節點集，然后再依據式（11）產生下一跳轉發節點，整個流程如圖3所示。

3 數值分析

3.1 仿真場景

為了更好地分析LSR協議性能，通過NS2建立實驗平臺。[N]個節點隨機分布于1 000×1 000區域，且以Random Waypoint作為節點的移動模型，移動速度為[?]，且[R=250] m，節點初始能量為1 873 J。每次實驗獨立重復50次，取均值作為最終實驗數據。仿真時間為800 s。

為了衡量LSR協議性能，選擇AODV，SV?AODV和AODV_D作為參照。同時考查路由開銷、吞吐量和端到端傳輸時延方面的性能。其中路由開銷是指每接收一個數據包所需的控制開銷；吞吐量是指單位時間內平均每個節點所接收的數據量；端到端傳輸時延是指平均傳輸一個數據包所需的時間。

3.2 實驗數據

3.2.1 路由開銷

首先分析路由開銷隨節點數的變化情況，其中，[N]從50～200變化，且節點移動速度[?=10 m/s]，實驗數據如圖4所示。

從圖4可知，路由開銷隨節點數的增加而增加。這主要是因為：節點越多，網絡密度越大，信道資源競爭越激烈，提升了控制包的冗余數。此外，節點數越多，傳輸路徑的跳數可能也越多，這也增加了控制包數。與AODV，SV?AODV和AODV_D相比，LSR協議的路由開銷得到有效控制。

圖5分析了路由開銷隨節點移動速度的變化情況。其中節點數為150，節點移動速度為從0～20 m/s變化。從圖5可知：移動速度的加快，加速了拓撲變化，增強了路徑的不穩定性，導致需頻繁地建立數據包傳輸路徑，最終增加了路由開銷；AODV協議的路由開銷最多，這主要是因為AODV采用泛洪機制建立路由；LSR路由開銷最少，原因在于LSR路由在建立路由時考慮了節點的移動問題，并且總是選擇最穩定的路由傳輸數據包。

通過圖4，圖5實驗數據可知，與AODV，SV?AODV和AODV_D協議相比，提出的LSR協議能有效地控制路由開銷。原因在于SV?AODV協議采用固定概率轉播數據包，并沒有依據網絡信息決策是否轉發數據包。與SV?AODV協議相比，AODV_D協議的路由開銷得到控制，但仍高于LSR。

3.2.2 吞吐量

圖6，圖7分別描述了吞吐量隨節點數和節點移動速度變化情況。在圖6的實驗中，節點數[N]從50～200變化，且節點移動速度[?=10] m/s；而在圖7實驗中，[N]為150，且節點移動速度從0～20 m/s變化。

從圖6可知，節點數的增加降低了吞吐量。原因在于：節點數越多，網絡資源競爭越激烈，影響了數據傳輸的流暢性。與AODV，SV?AODV和AODV_D協議相比，LSR協議的吞吐量最高，比AODV_D協議提高了近30%。這主要歸功于LSR協議是基于鏈路穩定性選擇下一跳轉發節點。

圖7的數據與圖6類似。節點移動速度的變化減少了網絡吞吐量，原因在于：移動速度的增加，加劇網絡拓撲變化，必然降低路徑穩定性。盡管如此，LSR協議仍能保持較高的吞吐量。

3.2.3 端到端傳輸時延

圖8，圖9分別描述了端到端傳輸時延隨節點數和節點移動速度變化情況。在圖8的實驗中，節點數[N]從50～200變化，且節點移動速度[?=10] m/s；而在圖9實驗中，[N]為150，且節點移動速度從0～20 m/s變化。

由圖8可知，節點數的增加加大了端到端傳輸時延，原因在于：節點數的增加，加劇了網絡資源的競爭，破壞了數據傳輸的流暢性。從圖9可知，LSR協議的端到端傳輸時延最低，這主要是因為LSR協議在選擇下一跳轉發節點時，充分考慮了節點的移動速度及鏈路的穩定性，增強了LSR協議對節點移動的強健性。

4 結 論

針對MANETs的數據傳輸問題，提出基于鏈路穩定的MANETs路由協議LSR。LSR從節點能量和鏈路穩定性出發，旨在選擇穩定路徑傳輸數據包。依據節點移動以及能量消耗速度，計算能量壽命和鏈路壽命，再構建候選轉發節點集，最后，擇優選擇下一跳轉發節點。仿真數據表明，提出的LSR協議能夠有效地降低時延，并提高吞吐量。

參考文獻

[1] CHITRAXI R， URVIK U， TWINKLE P M. Simulation of VANET using ns?3 and SUMO [J]. International journal of advanced research in computer science and software engineering， 2014， 4（2）： 563?569.

[2] ANDREA G， GIANLUIGI F. Irresponsible AODV routing [J]. Vehicular communications， 2015， 3（2）： 47?57.

[3] EI W， BEN G， SAFA H. MOLSR： mobile?agent based optimized link state routing protocol [C]// 2015 International Wireless Communications and Mobile Computing Conference. Pisca?taway： IEEE， 2015： 355?360.

[4] PERKINS C E， BHAGWAT P. Highly dynamic （DSDV） for mobile computers routing [C]// Proceedings of 1994 the ACM SIGCOMM. New York： ACM， 2014： 234?244.

[5] LEE S J， BELDING E M， PERKINS C E. Ad Hoc on?demand distance?vector routing scalability [J]. ACM mobile computing and communications， 2012， 6（3）： 94?104.

[6] TOH C K. Associativity?based routing for Ad Hoc mobile networks [J]. Wireless personal communications， 2010， 4（2）：103?139.

[7] HAAS Z J， PEARLMAN M R. The performance of query control schemes for the zone routing protocol [J]. IEEE transactions on networking， 2001， 9（4）： 427?438.

[8] SINHA P， SIVAKUMAR R， BAHRGHAVAN V. CEDAR： a core extraction distributed Ad Hoc routing algorithm [J]. IEEE journal on selected areas in communications， 1999， 17（8）： 1454?1466.

[9] 曹文君，薛善良.一種適用于城市車載網的改進的AODV協議[J].計算機與現代化，2016，23（7）：98?103.

CAO Wenjun， XUE Shanliang. An improved AODV routing protocol for urban vehicular Ad Hoc networks [J]. Computer and modernization， 2016， 23（7）： 98?103.

[10] 劉大勇，趙春江.基于AODV的農田無線傳感器網絡路由和休眠算法[J].微電子學與計算機，2015（10）：115?120.

LIU Dayong， ZHAO Chunjiang. A wireless sensor network routing and sleeping algorithm in agriculture based on AODV [J]. Microelectronics & computer， 2015（10）： 115?120.

[11] 蔡菁，朱余兵.一種基于AODV改進的城市車載自組網絡路由協議研究[J].計算機工程與科學，2013，35（1）：61?66.

CAI Jing， ZHU Yubing. An improved AODV routing protocol in urban vehicular ad hoc networks [J]. Computer engineering and science， 2013， 35（1）： 61?66.

[12] BUTT M R， AKBAR A H. LABILE： link quality?based lexical routing metric for reactive routing protocols in IEEE 802.15.4 networks [J]. Journal of supercomputing， 2012， 62（1）： 84?104.

[13] LEI Q， WANG Xiaoqing. Improved energy?aware AODV rou?ting protocol [C]// 2009 International Conference on Information Engineering. [S.l.： s.n.]， 2009： 18?21.

[14] HAFEEZ K， ZHAO L， LIAO Z， et al. Impact of mobility on VANETs′ safety applications [C]// 2010 IEEE Global Telecommunications Conference. Piscataway： IEEE， 2013： 1?5.

[15] ZHAO M， LI Y， WANG W. Modeling and analytical study of link properties in multi?hop wireless networks [J]. IEEE tran?sactions on communications， 2012， 60（2）： 445?455.