基于最小跳數(shù)和節(jié)點能量的 AODV-HE 路由選擇算法

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

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

基于最小跳數(shù)和節(jié)點能量的 AODV-HE 路由選擇算法

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

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

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

路由選擇機制；最佳路由；資源分配；網(wǎng)絡壽命

1 引言

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

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

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

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

2 AODV-HE 路由選擇算法

2.1 能量模型的建立

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

其 中 ，Ecs為 節(jié) 點 發(fā) 送 每 比 特 消 息 所 消 耗 的 能 量 ，Ecr為節(jié)點接收每比特消息所消耗的能量。

根 據(jù) 節(jié) 點 能 耗 模 型［9］有 ：

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

2.2 復合路由選擇算法

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

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

對其歸一化處理，得到：

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

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

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

hop是報文分組到達該節(jié)點所需跳數(shù)，設置跳數(shù)權重函數(shù)：

選擇 γ值越小的路由，網(wǎng)絡頑健性越高。

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

其中，α+β=1。

W 值越小代表該路由越好，可根據(jù)網(wǎng)絡狀態(tài)對權重因子 α 和 β的值進行調整。當網(wǎng)絡節(jié)點能量剩余不足時，應優(yōu)先考慮節(jié)點生命，故能量的權重較大；網(wǎng)絡規(guī)模較大且拓撲結構易變時，跳數(shù)的權重較大。

將式（10）等效為：

由于節(jié)點的剩余能量為 0時，其不參與數(shù)據(jù)接收和轉發(fā)，相當于隱形節(jié)點，故有：

又因為：

所以路由判據(jù)函數(shù)W的取值范圍：

2.3 AODV-HE 的分組頭改進

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

圖1 改進后 RREQ 和 RREP 格式

通過獲取路徑中節(jié)點的能量信息，計算出路由判據(jù)權值，由此獲得最優(yōu)路由。

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

2.4 AODV-HE 算法流程

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

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

圖2 AODV 路由協(xié)議尋路過程

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

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

圖3 RREQ 處理流程

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

3 仿真實驗和性能比較

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

圖4 RREP 處理流程

3.1 仿真環(huán)境配置

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

3.2 路由算法性能標準

·分組投遞率

·平均端到端時延

3.3 仿真流程

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

圖5 仿真流程

3.4 仿真結果及分析

3.4.1 節(jié)點最大速度不同時協(xié)議性能的比較

圖6 為權重因子相等即 α=β=0.5 時，節(jié)點最大速度分別 是 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 時 的 數(shù) 據(jù) 分 組 投 遞 率 、端 到 端 時 延 仿 真結 果 。

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

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

3.4.2 CBR 發(fā)送速率不同時協(xié)議性能的比較

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

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

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

3.4.3 α 與 β對 AODV-HE 協(xié)議的影響

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

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

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

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

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

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

圖9 不同 CBR 速率下網(wǎng)絡生存時間比較

4 結束語

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

參考文獻：

［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 網(wǎng) 絡 中 基 于 穩(wěn) 定 性 和 能 量 有 效性的 路 由 選 擇 算 法 研 究 ［J］. 齊 魯 工 業(yè) 大 學 學 報，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］ 杜青松，朱江，張爾揚. 基于閑時逆尋和路由學習機制的優(yōu)化 AODV 路由協(xié)議［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 網(wǎng) 絡 AODV 路由 協(xié) 議的 研究 與 優(yōu)化［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：一種基于擁塞跳數(shù)改進的 AODV 路由協(xié)議［J］.計算 機 與 現(xiàn) 代 化，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，F(xiàn)lorida，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-），男，博士，重慶郵電大學教授，國防研究院院長，主要研究方向為無線通信系統(tǒng)。

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

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

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

2016-01-12；

：2016-04-06

彭幟，372436151@qq.com

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