基于最小跳數和節點能量的 AODV-HE 路由選擇算法

余翔，彭幟，王詩言，劉利

（重慶郵電大學寬帶移動通信動員中心，重慶 400065）

基于最小跳數和節點能量的 AODV-HE 路由選擇算法

余翔，彭幟，王詩言，劉利

（重慶郵電大學寬帶移動通信動員中心，重慶 400065）

按需路由協議 AODV 中僅以最小跳數作為路由選擇依據，導致網絡資源分配不均及網絡壽命減少。提出了 AODV-HE 算法，該算法優化路由選擇機制，綜合最小跳數和節點剩余能量提出一種反向路由判據權值，并根據此權值選擇最佳路由。 仿真結果表明，該算法能有效提升分組投遞率，降低端到端時延，改善網絡資源分配問題并有效延長網絡壽命。

路由選擇機制；最佳路由；資源分配；網絡壽命

1 引言

Ad Hoc 網絡由同時具有路由和主機功能的節點組成，不利用現有網絡基礎設施就可以實現終端間通信。AODV（Ad Hoc on-demand distance vector，AODV）協 議 是 Ad Hoc網 絡 中 經 典 的 按 需 路 由 協 議［1］。

當源節點沒有到達目的節點的有效路由時就會啟動路由發現過程。AODV 協議是最短路徑協議，僅以最小跳數為路由選擇判據，導致負載較大時關鍵節點過早死亡，另一些節點未得到充分利用，資源分配不均造成網絡壽命變短。

目前，針對 AODV 路由協議的改進算法有很多。 參考文獻［2］根據單 個 節點的能 量 使用情 況 及 全 路徑 能 量 消 耗情況，選擇不同傳輸路徑，提高了路由效率。業務負載較高時，時延改善不佳。參考文獻［3］基于路徑穩定性和能量有效性提出一種新型節點代價函數，在路由開銷和節點死亡率方面有較好表現，但是時延較大。參考文獻［4］根據網絡中不同時期參量的變化情況選擇不同路由，使選路機制達到整體最優化，但在能量均衡選路方面不完善。參考文獻［5］在網絡中產生多個局部路由，增加網絡中的路由冗余度，降低端到端時延，但路由發現頻率有所提高。參考文獻［6］選擇鏈路中節點的平均鄰居數目作為路由選擇比較參數，增加了斷裂鏈路修復成功的概率。源節點可隨時切換更優路由進行數據傳輸，在時延上表現良好，但由于傳輸數據的同時還會尋找更優路由，節點能耗增加。參考文獻［7］提出RAODV 算法，采用逆尋機制，在數據傳輸鏈路斷裂時，源節點從備份路由中選出最優路由進行通信。因此傳輸可靠性較好，但當網絡負載較高時，備份路由失效率高。

針對上述不足，本文提出一種改進協議 AODV-HE（routing algorithm based on minimum hop and energy of node，AODV-HE），該協議綜合考慮最小跳數和節點能量。在尋路階段，中間節點收到 RREQ 報文后，首先通過比較 RREQ 報文中的路由判據權值來建立最優反向路徑，保證該節點路由表項中，建立的反向路徑綜合考慮了最小跳數和節點剩余能量。源節點在一定時間內收到多條路由應答報文 RREP后，根據 RREP中的路由判據權值選擇一條最優路由發送數據。改進后的協議能夠更好的均衡負載，適應拓撲結構的動態變化，降低關鍵節點的能耗，從而延長網絡壽命。實驗表明該改進協議在分組投遞率、路由發起頻率、歸一化路由開銷和平均端到端時延等指標上均有所改善。

2 AODV-HE 路由選擇算法

2.1 能量模型的建立

設源節點為 S，目的節點為 D，網絡中存在一條路徑Ri=r1，r2，…，rm（m≥2），分析數據分組從 r1經由路徑 Ri成功發送到 rm的能量。考慮節點 ri的 4 個參數 ：初 始 能量、當前剩余能量、傳輸功率和接收功率。在該節點能量模型中，節點 初 始 能 量 Einitial均 為 30 J［8］，使 用 NS2 中 能 量 模 塊 ，傳 輸功 率 Es為 0.660 W，接 收 功 率 Er為 0.395 W。 一 條 具 有 m個 節 點 的 路 由 存 儲 轉 發 n bit數 據 時 ，整 條 路 徑 上 節 點 消耗的總能量為：

其 中 ，Ecs為 節 點 發 送 每 比 特 消 息 所 消 耗 的 能 量 ，Ecr為節點接收每比特消息所消耗的能量。

根 據 節 點 能 耗 模 型［9］有 ：

其中，Time 為處理一個分組所需時間：

2.2 復合路由選擇算法

每 個 節 點 的 初 始 能 量 Einitial為 30 J［8］，根 據 多 次 實 驗 可知，源節點到目的節點的最大跳數 Maxhop 為 10，hop 是報文 分 組 到 達 該 節 點 所 需 跳 數 ，Emin是 路 徑 中 最 小 的 節 點 剩余 能 量 ，選擇 Emin越 大 的 路 由 ，網絡的生命周期越長。

設 θ1為路徑中所有節點的平均剩余能量：

對其歸一化處理，得到：

歸一化路徑中最小節點剩余能量，得到：

綜合考慮路由中最小的節點能量和節點的平均能量，設置能量權重函數：

選擇 E值較小的路由，能同時兼顧路徑能量和網絡剩余能量的均衡。

hop是報文分組到達該節點所需跳數，設置跳數權重函數：

選擇 γ值越小的路由，網絡頑健性越高。

對能量和跳數指標提供兩個權重因子 α 和 β，則路由判據權值為：

其中，α+β=1。

W 值越小代表該路由越好，可根據網絡狀態對權重因子 α 和 β的值進行調整。當網絡節點能量剩余不足時，應優先考慮節點生命，故能量的權重較大；網絡規模較大且拓撲結構易變時，跳數的權重較大。

將式（10）等效為：

由于節點的剩余能量為 0時，其不參與數據接收和轉發，相當于隱形節點，故有：

又因為：

所以路由判據函數W的取值范圍：

2.3 AODV-HE 的分組頭改進

在選擇最優路由時，為了綜合考慮跳數和節點能量，需要對原有 AODV 協議分組頭進行改進。在分組頭中增加能量和路由判據權值字段，改進后的 RREQ 和 RREP 格式如圖1所示。

圖1 改進后 RREQ 和 RREP 格式

通過獲取路徑中節點的能量信息，計算出路由判據權值，由此獲得最優路由。

控制報文中字段的增加導致轉發每個路由控制報文所 消 耗 的 能 量 增 大 ，第 2.3 節 中 仿真 顯 示 ，由 于AODV-HE算法選擇的路由頑健性高，路由發起頻率低，用于路由尋找和路由維護的控制報文數量明顯下降，故總能耗下降。

2.4 AODV-HE 算法流程

AODV 協議是最小跳數路由協議，即尋路階段中間節點收到 RREQ 報文后，首先判斷之前是否收到相同報文，若是，則丟棄該報文。這樣會導致一些改進協議在尋路階段效果不夠明顯。即使中間節點根據改進算法可以選擇較優的 RREQ 建立反向路徑，但是尋路流程不改變會造成中間節點仍然選擇首次收到的 RREQ 來建立反向路徑。

AODV 路由協議尋路過程如圖 2 所示，源節點 S 泛洪RREQ 給其鄰節點，接收到 RREQ 的中間節點將首次收到的 RREQ 泛洪給自己的鄰節點，一直到目的節點接收到RREQ 報文為止。假設節點 2 先收到節點 1 轉發的 RREQ，即使節點 4 的剩余能量大于節點 1，節點 2 收到節點 4 的RREQ 報文后也會直接丟棄。這樣會導致針對 AODV 進行改進的算法效果不明顯。

圖2 AODV 路由協議尋路過程

針對該問題，本算法優化尋路流程。中間節點收到RREQ 分組后，根據其中的跳數和節點能量信息，利用算法得出新的路由判據權值W。

對比 RREQ 分組中的權值與節點本地路由表項中的反向路由權值，并將較小值對應的反向路由更新于本地路由表項中，如式（16）所示。更新 RREQ 報文后將其廣播出去，主要流程如圖 3所示。

圖3 RREQ 處理流程

目的節點或有到達目的節點路由的中間節點在收到RREQ 報文后，產生 RREP 報文并將其發往源節點。中間節點在收到 RREP 報文后根據本地路由表項中存儲的反向路由將此 RREP 單播至源節點，源節點選取路由判據權值最小的路由作為最優路由發送數據，主要流程如圖 4所示。

3 仿真實驗和性能比較

采 用 的 仿 真 平 臺 NS2（Network Simulator，version2），它是一種面向對象的網絡仿真器，本質上是一個離散事件模擬器，是目前網絡研究領域應用最為廣泛的網絡仿真軟件之一。比較 AODV、RAODV 和 AODV-HE 路由協議在分組投遞率和平均端到端時延方面的性能。每次結果取 10次實驗的平均值。

圖4 RREP 處理流程

3.1 仿真環境配置

仿 真 場 景 使 用 Random Waypoint模 型 ，無 線 信 號 傳 輸模 式 為 Propagation／TwoRayGround。每 個 節 點 通 信 范 圍 為550 m，節 點 運 動區 域 為 1 000 m×300 m，仿 真 時 間 為 600 s，流量數據分組類型為 CBR 方式，通信節點對數為 10。

3.2 路由算法性能標準

·分組投遞率

·平均端到端時延

3.3 仿真流程

安裝 NS2 系統后，復制 AODV 文件夾，并且將其命名為 AODV-HE， 修 改 AODV-HE 目 錄 下 的 源 代 碼 并 將AODV-HE 作為一個新協議注冊進 NS2 系統中。 然后在 tcl文件中設定仿真協議，生成場景文件和流量文件，利用gwak 腳本得到仿真數據。最后利用繪圖命令 gnuplot將得到的仿真數據繪制于一張圖上。仿真流程如圖5所示。

圖5 仿真流程

3.4 仿真結果及分析

3.4.1 節點最大速度不同時協議性能的比較

圖6 為權重因子相等即 α=β=0.5 時，節點最大速度分別 是 2 m／s、4 m／s、6 m／s、8 m／s、10 m／s、12 m／s、14 m／s、16 m／s、18 m／s、20 m／s 時 的 數 據 分 組 投 遞 率 、端 到 端 時 延 仿 真結 果 。

圖6 節點速度不同時的分組投遞率和端到 端 時 延（α=β=0.5）

由圖 6 可以看出，節點最大速度較低時，網絡拓撲變化不大，3種協議分組投遞率相近。 隨著節點移動速度加快，網 絡 拓 撲 變 化 激 烈 ，AODV-HE 分 組 投 遞 率 明 顯 優 于RAODV 和 AODV。因為 AODV-HE 選擇的路由更穩定，均衡了網絡負載，延長關鍵節點生命，數據發送成功率更高。節點速度的增大導致 RAODV 協議的備份路由失效率增加，優勢逐漸減弱。網絡拓撲結構變化激烈，鏈路斷裂次數增多，3 種協議的平均端到端時延呈上升趨勢。AODV-HE的時延最低，這是由于 AODV-HE 綜合性路由判據使選擇的路由具有更好的頑健性，鏈路斷裂次數少，保持連接的時間長，避免了重復尋找路由以及修復斷裂路由造成的時延。

3.4.2 CBR 發送速率不同時協議性能的比較

權重因子相等即 α=β=0.5 時，分別使用 10 種 CBR 發送速度：2 分 組／s、4 分 組／s、6 分組／s、8 分 組／s、10 分 組／s、12 分 組／s、14分組／s、16 分組／s、18 分組／s、20 分組／s 時 ，數 據 分 組 投 遞 率 和 端到端時延仿真結果如圖7所示。

圖7 CBR 速 率 不 同 時 3 種 協 議 性 能 比 較（α=β=0.5）

由圖 7 可知，CBR 發送速率較低時，RAODV 備用路由有效率高，AODV-HE 選擇的路由頑健性高，故 RAODV 和AODV-HE 優勢明顯。CBR 數據發送速率增加，網絡負載加重，導致碰撞和擁塞概率增加，3 種協議分組投遞率下降。流量負載加重使節點能耗增加，鏈路斷裂次數增多。AODV-HE 選擇路由時考慮了最小節點剩余能量，穩定性高，路由保持連接時間長，分組投遞率高。CBR 發送速率較低時 3 種協議的平均端到端時延相差不大。CBR 發送速率增大導致節點能量消耗迅速，生命周期變短，路由頻繁斷裂，平均端到端時延明顯增加。RAODV 時延明顯增大是因為流量負載增多使其備份路由失效率高，路由尋找和維護花費時間大。AODV-HE 時延明顯低于 RAODV 和 AODV，是因為 AODV-HE 選擇的路由更加穩定，關鍵節點的生命周期長，減少了再次發起路由尋找和路由維護所需時間。

3.4.3 α 與 β對 AODV-HE 協議的影響

在路由選擇判據權值的設計和分析中，考慮到 α和 β在不同情況下的取值對協議的性能影響。圖 8是 α和 β在不同取值情況下 AODV-HE 的性能仿真結果。

圖8 AODV 與 α 和 β 不同時的 AODV-HE 協議性能比較

由圖 8 可知，在 CBR 發送速率較低的情況下，α=0.2、β=0.8 時協議性能最好。 這是由于 CBR 速率較低時，網絡負載低，協議更傾向于選擇跳數較少的鏈路，又由于其結合了能量因素，選擇的路由更穩定，避免了鏈路斷裂后再次尋找路由帶來的時延，故分組投遞率和時延的性能最好。隨著 CBR 速率增大，網絡中數據分組碰撞概率增大，鏈路斷 裂 次數增多 ，AODV-HE 協議 在 α=0.8、β=0.2 時優勢逐漸明顯。這是由于在網絡流量加重的情況下，其選擇的路由頑健性更高，使得數據分組投遞率最高，時延最小。

3.4.4 改進后的路由控制報文損益情況

節點生存時間是指，仿真開始到節點能量耗盡為止。網絡生存時間是所有節點生存時間的均值，即：

由于 AODV-HE 協議在路由請求報文 RREQ 分組中增加 3 個字段，在路由應答報文 RREP 分組中增加了一個字段，故每處理一個路由控制報文的耗能會較 AODV 中的多。但是，由于 AODV-HE 協議選擇的路由綜合了最小跳數和節點能量，選擇的路由頑健性高，不易斷裂。AODV-HE 協議通過實時更新最佳反向路由，保證了尋找的中繼節點質量，減少了維護路由或重新尋找路由的次數，從而降低了網絡中路由控制報文總數。節點需要轉發的路由控制報文數量減小，導致節點能耗降低，生存時間延長。網絡中節點的生存時間延長，故網絡的生存時間延長。仿真結果如圖9所示。

圖9 不同 CBR 速率下網絡生存時間比較

4 結束語

節點能量有限直接 影響到 Ad Hoc 網絡的性能和穩定性。本文提出基于最小跳數和節點能量的 AODV-HE 路由選擇算法，根據最小跳數和網絡中最小節點剩余能量，設置反向路由判據權值，過濾掉多余路由控制報文。節點通過路由判據權值選擇更優上一跳節點建立反向路由。中間節點在尋路階段接收到 RREQ 報文后，將更優的 RREQ 報文發送節點更新為自己的反向節點，使得路由選擇依據綜合了最小跳數和節點剩余能量，保證路由的頑健性，使網絡中節點得到充分利用，平衡了網絡資源的分配。 理論和仿真結果顯示，通信頻率適中時該算法在分組投遞率和平均端到端時延上有較好表現，有效平衡了網絡負載，提升網絡性能。

參考文獻：

［1］ KUMAR R，GUPTA M.Route stability and energy aware based AODV in MANET ［C］／／The International Conference on High Performance Computing and Applications，Dec 22-24，2014，Bhubaneshwar，India.New Jersey：IEEE Press，2014：1-5.

［2］ 鄭 石，吳 偉 強，張 欽 宇，等. 基 于 能 量 感 知 的 Ad Hoc 路 由 算法研 究［J］. 通信學報，2012，33（4）：9-16. ZHENG S，WU W Q，ZHANG Q Y，et al.Research on energy-aware Ad Hoc routing protocols ［J］.Journal on Communications，2012，33（4）：9-16.

［3］ 張 明 華，張 帆. 無 線 Ad Hoc 網 絡 中 基 于 穩 定 性 和 能 量 有 效性的 路 由 選 擇 算 法 研 究 ［J］. 齊 魯 工 業 大 學 學 報，2015，6（2）：82-86. ZHANG M H，ZHANG F.Research on routing protocols based on stability and energy efficiency in Ad Hoc networks ［J］. Journal of QILU University of Technology，2015，6（2）：82-86.

［4］ TERDAL S P，MYTRI V D.Multiple metrics based load balancing routing protocol for mobile ad hoc networks［C］／／The Asian Himalayas International Conference on Internet（AH-ICT ’09），Nov 3-5，2009，Kathmundu，Nepal.New Jersey：IEEE Press，2009：1-5.

［5］ 杜青松，朱江，張爾揚. 基于閑時逆尋和路由學習機制的優化 AODV 路由協議［J］. 通信學報，2011，32（8）：64-71. DU Q S，ZHU J，ZHANG E Y.Optimized AODV routing protocol based on reverse route search in leisure time and route learning［J］.Journal on Communications，2011，32（8）：64-71.

［6］ 梁建 武. 移動 Ad Hoc 網 絡 AODV 路由 協 議的 研究 與 優化［J］.重慶 大 學 學 報，2015，38（4）：152-158. LIANG J W.Research and optimization of AODV routing protocols in mobile Ad Hoc network ［J］.Journal of Chongqing University，2015，38（4）：152-158.

［7］ 王龍峰.RAODV：一種基于擁塞跳數改進的 AODV 路由協議［J］.計算 機 與 現 代 化，2013（8）：133-136. WANG L F.RAODV：An improved AODV routing protocol based on congestion hop count ［J］. Computer and Modernizatioon，2013（8）：133-136.

［8］ XING Y H.A dynamic programming solution for QoS routing in wireless ad hoc network with energy constraints ［J］.The Journal of China University of Posts and Telecommunications，June 2010，19（Suppl.1）：33-37.

［9］ BAEK S J，VECIANA G D.Spatial energy balancing in large-scale wireless multihop networks ［C］／／The 24th Annual Joint Conference of the IEEE Computer and Communications Societies（INFOCOM 2005），March 13-15，2005，Miami，Florida，USA.New Jersey：IEEE Press，2005：126-137.

［10］EZREIK A，GHERYANI A.Design and simulation of wireless network using NS-2 ［C］／／The 2nd International Conference on Computer Science and Information Technology，April 28-29，2012，Singapore.Beijing：China Academic Journal Electronic Publishing House，2012：157-161.

［11］KHARRAZ M， SARBAZI-AZAD H.On-demandmulticast routing protocol with efficient route discovery ［J］.Network and Computer Applications，2012，35（3）：942-950.

AODV-HE routing algorithm based on minimum hop and energy of node

YU Xiang，PENG Zhi，WANG Shiyan，LIU Li
Broadband Mobile Communication Mobilization Center，Chongqing University of Posts and Telecommunications，Chongqing 400065，China

AODV routing protocol takes the minimum hop as the only basis in route selection，causing the uneven allocation of resources and reduction in network lifetime.A routing algorithm based on minimum hops and energy of node （AODV-HE）was proposed.By integrating both minimum hop and residual energy of each node，the algorithm optimized the routing mechanism and presented a selection weight of reverse routing，based on which the best route was chosen.Simulation results show that the algorithm can effectively increase packet delivery ratio and reduce the end-end delay，and it can also improve the allocation of network resources and extend network lifetime.

routing mechanism，best route，allocation of resources，network lifetime

s： The National Science and Technology Specific Program of China （No.2015ZX03004004），Project Foundation of Chongqing Municipal Education Committee （No.KJ1500426），Youth Foundation of Chongqing University of Posts and Telecommunications （No.A2014-96）

TN915

：A

10.11959／j.issn.1000-0801.2016123

余翔（1964-），男，博士，重慶郵電大學教授，國防研究院院長，主要研究方向為無線通信系統。

彭幟（1991-），女，重慶郵電大學碩士生，主要研究方向為無線通信系統。

王詩言（1986-），女，博士，重慶郵電大學副教授，主要研究方向為無線通信網絡、圖像處理。

劉利（1992-），女，重慶郵電大學碩士生，主要研究方向為無線通信系統。

2016-01-12；

：2016-04-06

彭幟，372436151@qq.com

國家科技重大專項“新 一代 寬 帶無 線 移動 通信 網 ”基 金資 助項 目 （No.2015ZX03004004）；重 慶 市 教委 項 目（No.KJ1500426）；重 慶郵電大學青年科學基金資助 項 目（No.A2014-96）