基于能量均衡的自組網(wǎng)改進型混合路由協(xié)議

劉玉軍，王一博，蔡猛

(陸軍裝甲兵學院，北京 100072)

0 引 言

移動自組網(wǎng)絡(Mobile Ad hoc Network, MANET)在無通信基礎設施支持環(huán)境下有著廣闊的應用前景，如軍事、野外探險、自然災害救援通信等領域。便攜型的自組網(wǎng)節(jié)點一般采用電池供電，一旦自身攜帶的電池能量耗盡，不僅節(jié)點本身無法通信，還將影響網(wǎng)絡整體的連通性、服務質量和生存時間。

MANET協(xié)議棧的大部分協(xié)議由傳統(tǒng)網(wǎng)絡協(xié)議修改而來，特別是路由協(xié)議，主要依據(jù)最小代價盡力交付的原則在維系網(wǎng)絡拓撲，這導致無線環(huán)境下協(xié)議開銷較大，必然引起能耗加劇，而且多數(shù)協(xié)議忽略了無線通信功率、節(jié)點能耗對網(wǎng)絡通信質量和網(wǎng)絡生存時間[1,2]的影響。因此，在路由協(xié)議中加入能耗因素，對提升無線移動自組網(wǎng)性能具有重要的研究意義。

1 相關研究

目前，移動自組網(wǎng)中針對能量限制的路由協(xié)議改進主要有負載均衡和能量感知兩類方案。文獻[1]提出了一種能量有效負載均衡的多徑路由算法，該算法考慮了節(jié)點的能量、路由跳數(shù)、網(wǎng)絡拓撲，以及控制關鍵節(jié)點過載等情況，但是沒有考慮傳輸中節(jié)點的能量消耗。文獻[2]和文獻[3]提出了能量優(yōu)化的按需路由協(xié)議，該協(xié)議引入能量感知概念，根據(jù)剩余能量信息選擇路由路徑，均衡了節(jié)點的能量使用情況，但該協(xié)議沒有考慮均衡節(jié)點的負載情況，增加了網(wǎng)絡延時。文獻[4]提出了一種能量感知強制協(xié)作路由協(xié)議，協(xié)議通過檢測節(jié)點的剩余電量，強制剩余電量較多的節(jié)點承擔數(shù)據(jù)轉發(fā)任務，該協(xié)議均衡使用了節(jié)點能量。但加劇了部分節(jié)點的能量消耗。文獻[5]在按需路由的基礎上提出了基于剩余能量感知的多策略路由協(xié)議，該協(xié)議對節(jié)點能量設置多個閾值，根據(jù)剩余能量對應的閾值區(qū)間，均衡節(jié)點的負載，降低節(jié)點能量消耗，延長了網(wǎng)絡的生存時間，但是當節(jié)點能量均處于較低水平時，該協(xié)議的連通率較低。文獻[6]提出了基于網(wǎng)絡負載與能量均衡的多徑路由協(xié)議，融合了能量感知和負載均衡兩方面技術，均衡負載的同時降低節(jié)點的能量消耗，但該協(xié)議通過節(jié)點負載和剩余能量各占一半的方式融合，存在一定局限性。文獻[7] 研究了能量節(jié)約型路由協(xié)議，但協(xié)議需要對網(wǎng)絡條件進行諸多限制，影響了研究成果的適用范圍。

目前，能量均衡路由協(xié)議多數(shù)以AODV、DSV等按需路由為基礎改進，這類方案雖然延長了自組網(wǎng)的生存時間，但是存在較高延時和大型網(wǎng)絡適應性差等問題。

為了克服上述問題，本文擬采用傳輸延遲小、支持較大網(wǎng)絡規(guī)模的優(yōu)化鏈路狀態(tài)路由(Optimized Link State Routing，OLSR)協(xié)議進行改進。但是OLSR協(xié)議在路由建立與維護中消耗了大量的計算、存儲和能量等資源，縮短了網(wǎng)絡的生存時間。為此，本文引入剩余能量和負載均衡相結合的改進方案，控制節(jié)點的能量消耗；改進拓撲控制(Topology Control，TC)消息，引入次優(yōu)多跳路由的思想，有效降低路由OSLR協(xié)議開銷，提高節(jié)點的能量利用效率。

2 改進型OLSR協(xié)議設計方案

OLSR協(xié)議與其他協(xié)議的顯著區(qū)別是引入多點中繼[8](Multi-Point Relay，MPR)，通過算法選擇合適的中繼節(jié)點，可以降低拓撲維護的開銷，但算法造成了MPR節(jié)點業(yè)務和信令負載過重，加速MPR節(jié)點的能量消耗，降低了這些節(jié)點的生存時間。為此本文從能量均衡消耗的角度出發(fā)，在傳統(tǒng)OLSR協(xié)議的MPR節(jié)點決策算法中引入能量代價函數(shù)，將網(wǎng)絡路由維護任務更均勻分散在所有網(wǎng)絡節(jié)點中，實現(xiàn)路由層的能量均衡消耗。

2.1 能量代價函數(shù)設計

在傳統(tǒng)OLSR協(xié)議的基礎上，基于網(wǎng)絡節(jié)點的剩余能量建立一個函數(shù)，對網(wǎng)絡中每一個節(jié)點的信號傳輸進行可量化的能量投遞代價[9]度量，記為C，并將該概念引入到MPR節(jié)點的決策環(huán)節(jié)中。函數(shù)定義如下：

(1)

從表達式(1)可以看出，隨著節(jié)點入網(wǎng)后時間的推移，節(jié)點的剩余電量不斷減少，節(jié)點的能量投遞代價數(shù)C將不斷增大。

OLSR協(xié)議的一個關鍵環(huán)節(jié)是網(wǎng)絡中的MPR節(jié)點的選擇。傳統(tǒng)協(xié)議的決策算法主要是基于網(wǎng)絡最小連通拓撲樹。在節(jié)點能量受限場景下，這種機制將導致部分關鍵位置的網(wǎng)絡節(jié)點承擔了網(wǎng)絡中大部分的拓撲維護和數(shù)據(jù)業(yè)務的中繼任務，從而導致能量消耗速度明顯高于其他節(jié)點，過快出現(xiàn)“死亡”節(jié)點，影響了網(wǎng)絡的整體連通性和通信性能。

本文提出一種基于能量投遞代價C和網(wǎng)絡節(jié)點總能量消耗之和Eall的MPR集合綜合選擇機制，去掉部分非功率高效和剩余電量較小的鄰居節(jié)點，增大節(jié)能路由和能量均衡路由的選擇概率，從而達到網(wǎng)絡節(jié)能和能量消耗均衡的目的。令Ni表示具備發(fā)射功率控制能力的網(wǎng)絡節(jié)點i的信令兩跳擴散的目的節(jié)點集合，則從網(wǎng)絡節(jié)點總能量消耗之和Eall角度出發(fā)，MPR集合選擇的優(yōu)化目標函數(shù)具體為：

(2)

從表達式(2)的優(yōu)化目標函數(shù)可以看出，節(jié)點的剩余電量越小，其能量投遞代價越大，則該節(jié)點被選為MPR節(jié)點的概率就越小。另外該函數(shù)也一定程度考慮了節(jié)點能量的利用率因素，這就使得剩余電量較多和節(jié)點能量利用率更高的節(jié)點更主動承擔更多的網(wǎng)絡拓撲維護和數(shù)據(jù)業(yè)務的中繼傳輸任務，從而在保障能量利用率的基礎上，盡可能均衡使用各網(wǎng)絡節(jié)點能量，有效延長網(wǎng)絡節(jié)點的生存時間。

2.2 控制協(xié)議改進

OLSR的控制協(xié)議主要體現(xiàn)在HELLO和TC消息。結合上述的MPR節(jié)點選擇機制，本文對這兩類消息的協(xié)議內(nèi)容改進如下：

(1)節(jié)點將根據(jù)自己的剩余電量來自適應決定向鄰居節(jié)點發(fā)送 HELLO 消息的周期。剩余能量投遞代價小于預設的閾值C0時(這里設定為能量消耗一半后)，按正常頻度f0發(fā)送HELLO消息；大于該閾值時，則逐漸降低HELLO消息發(fā)送的頻度f，算法見表達式(3)為:

(3)

根據(jù)HELLO信息，節(jié)點可以獲得：

·鄰居節(jié)點感知(Neighbor sensing)；

·節(jié)點鏈路狀態(tài)檢測：單向鏈路、雙向鏈路或者未確定；

·加入能量字段，檢測節(jié)點剩余能量的投遞代價；

·基于HELLO信息攜帶的鄰居節(jié)點的能量投遞代價C進行MPR 節(jié)點計算。

(2)為進一步降低路由維護的能量消耗，本文引入自適應路由機制，即維護近端節(jié)點之間的高精度路由信息(2跳之內(nèi))，而中遠端節(jié)點之間僅維護次優(yōu)的路由信息，設計思路如下：

設置兩類TC消息并添加信令類型字段便于識別，第一類TC消息用于近端區(qū)域的精準路由，增加TTL字段以設置節(jié)點的精準路由范圍，在范圍內(nèi)發(fā)送一類無失真TC消息，建立精準路由拓撲關系；第二類TC消息用于中遠端路由拓撲關系建立，采用次優(yōu)多跳路由思想，僅記錄節(jié)點的一跳范圍拓撲關系，并降低全網(wǎng)范圍內(nèi)的廣播頻度。

3 協(xié)議實現(xiàn)

本節(jié)從實現(xiàn)層面進一步描述對OLSR協(xié)議的改進內(nèi)容。

3.1 MPR節(jié)點選擇算法實現(xiàn)

令集合N1表示節(jié)點的1跳鄰居節(jié)點集合，N2表示節(jié)點的2跳鄰居節(jié)點集合。標準OLSR協(xié)議的MPR節(jié)點選擇流程具體如圖1所示。

圖1 標準OLSR協(xié)議MPR節(jié)點選擇

對圖2所示的網(wǎng)絡拓撲而言，如果根據(jù)標準OLSR算法，網(wǎng)絡中的節(jié)點7、節(jié)點10和節(jié)點11處于網(wǎng)絡拓撲的中心位置，這些節(jié)點充當其它節(jié)點的MPR節(jié)點以及數(shù)據(jù)業(yè)務中繼節(jié)點的概率很大，因此將很快耗盡能量而成為死亡節(jié)點，導致網(wǎng)絡連接出現(xiàn)中斷。

圖2 基于標準OLSR協(xié)議選擇的MPR節(jié)點集合

而表達式(2)的優(yōu)化函數(shù)的改進型MPR節(jié)點選擇流程如圖3所示：

圖3 改進型MPR節(jié)點選擇

基于圖3的流程可以看出，采用基于能量的改進型OLSR協(xié)議后，在網(wǎng)絡運行初期，網(wǎng)絡節(jié)點的能量基本相同，則節(jié)點7、節(jié)點10和節(jié)點11仍將充當MPR節(jié)點，但隨著這些節(jié)點的剩余能量降低，相應的剩余能量投遞代價將提高。MPR節(jié)點的選擇結果將隨著網(wǎng)絡的運行而不斷發(fā)生變化，其它剩余電量較多的節(jié)點也將逐漸承擔更多比例的網(wǎng)絡管理和數(shù)據(jù)中繼任務，如圖4所示，從而滿足均衡使用各網(wǎng)絡節(jié)點能量的要求，提升網(wǎng)絡整體的生存時間。

圖4 改進型OLSR選擇的MPR節(jié)點集合

3.2 OLSR路由控制消息改進

OLSR協(xié)議采用周期性的路由控制信息交換機制來實現(xiàn)網(wǎng)絡拓撲的維護。這個過程在能量受限的網(wǎng)絡中也需要進行必要的改進以節(jié)約能量。改進如下：

3.2.1 HELLO消息改進

在HELLO消息的保留字段(即Reserved字段)中加入節(jié)點計算好的剩余能量投遞代價C。節(jié)點通過改進的HELLO信息交換鏈路信息和剩余能量投遞代價，根據(jù)交換的HELLO信息建立新的鄰居節(jié)點信息庫，并加入鄰居節(jié)點的剩余能量投遞代價。更改后的HELLO消息格式如表1所示：

表1 HELLO消息格式

3.2.2 TC消息改進

為降低信令開銷和能量消耗，TC消息設置兩類信令類型并設置信令類型字段，第一類信令分組將在信令分組中設置TTL 字段來控制信令的擴散范圍，主要進行局部擴散，建立精準路由，默認TTL的值為128(可根據(jù)實際應用調整)。其信令分組格式如表2所示：

表2 第一類TC消息格式

此外，第二類信令并不設置TTL字段，主要用于中遠端節(jié)點的次優(yōu)路由維護，其分組格式如表3所示：

表3 第二類TC消息格式

節(jié)點接受TC消息后，首先判斷信令類型，若第一類則記錄源節(jié)點到本節(jié)點的精準路由拓撲關系；若第二類則僅記錄TC消息的源地址和上一跳節(jié)點地址，后轉發(fā)該TC分組。

圖5給出了基于上述路由機制的維護結果。

圖5 近端和中遠端拓撲關系圖

由于節(jié)點可能從多個節(jié)點重復接收到同一消息，為避免同一消息重復處理的能量消耗，每個節(jié)點將設置一個基于時間有效性的復制集合，該集合可以避免消息的重復處理和轉發(fā)。改進如下：

(1)如果第一類消息的 TTL 小于等于 0 或消息是接收節(jié)點自身發(fā)送的，該消息必須立刻丟棄；

(2)如果節(jié)點接收到?jīng)]有消息的分組信令數(shù)據(jù)(如分組長度小于分組包頭長度)，則這個分組數(shù)據(jù)必須立刻丟棄；

(3)如果分組信令數(shù)據(jù)在復制集合中已經(jīng)存在一個記錄，表明該消息已經(jīng)進行處理，則這個數(shù)據(jù)必須立刻丟棄；

(4)如果信令數(shù)據(jù)為有效信令，則根據(jù)信令類型進行相應的處理。

4 仿真實驗

為驗證本文提出的改進型協(xié)議性能，對改進型協(xié)議和傳統(tǒng)OLSR協(xié)議進行仿真和分析。

4.1 仿真場景描述

為減少仿真結果的偶然性，設置了3個仿真場景。場景一：16節(jié)點的4跳網(wǎng)絡；場景二：16節(jié)點的8跳網(wǎng)絡；場景三：32節(jié)點的4跳網(wǎng)絡。場景的用戶分布模型依次如圖6-圖8所示：

圖6 16節(jié)點4跳

圖7 16節(jié)點8跳

圖8 32節(jié)點4跳

4.2 仿真結果與分析

三個仿真場景下傳統(tǒng)OLSR協(xié)議和本協(xié)議在網(wǎng)絡建網(wǎng)時間、全網(wǎng)轉發(fā)吞吐量的性能仿真結果如下：

(1)場景一的仿真結果

圖9a 傳統(tǒng)OLSR建網(wǎng)時間

圖9b 改進型協(xié)議建網(wǎng)時間

圖10a 傳統(tǒng)OLSR全網(wǎng)轉發(fā)吞吐率

圖10b 改進型協(xié)議全網(wǎng)轉發(fā)吞吐率

(2)場景二的仿真結果

圖11a 傳統(tǒng)OLSR建網(wǎng)時間

圖11b 改進型協(xié)議建網(wǎng)時間

圖12a 傳統(tǒng)OLSR全網(wǎng)轉發(fā)吞吐率

圖12b 改進型協(xié)議全網(wǎng)轉發(fā)吞吐率

(3)場景三的性能仿真結果

圖13a 傳統(tǒng)OLSR建網(wǎng)時間

圖13b 改進型協(xié)議建網(wǎng)時間

圖14a 傳統(tǒng)OLSR全網(wǎng)轉發(fā)吞吐率

圖14b 改進型協(xié)議全網(wǎng)轉發(fā)吞吐率

圖15a 傳統(tǒng)OLSR網(wǎng)絡中心區(qū)和邊緣節(jié)點的電量消耗曲線

圖15b 改進型協(xié)議網(wǎng)絡中心區(qū)和邊緣節(jié)點的電量消耗曲線

比較3個場景的仿真結果(圖9a至圖14b)可以看出，本文提出的混合路由協(xié)議，在建網(wǎng)時間和網(wǎng)絡吞吐率上獲得了與傳統(tǒng)路由協(xié)議相當?shù)男阅?。在?jié)點電量消耗效果方面，圖15a和圖15b則分別給出了使用傳統(tǒng)OLSR協(xié)議和本文改進型協(xié)議，在相同的業(yè)務負荷時，場景1中一個網(wǎng)絡中心區(qū)節(jié)點和一個邊緣節(jié)點在同時滿電量(歸一化為1)入網(wǎng)后，隨著仿真時間的推移各自的剩余電量情況。可以看出傳統(tǒng)協(xié)議中網(wǎng)絡中心區(qū)的節(jié)點一直充當MPR節(jié)點，能量消耗速率明顯快于邊緣節(jié)點，很快電量耗盡導致節(jié)點死亡；協(xié)議改進后，雖然入網(wǎng)初期中心區(qū)節(jié)點的電量消耗速率還是明顯高于邊緣節(jié)點，但隨著時間推移，邊緣節(jié)點將逐漸取代中心節(jié)點來承擔更多網(wǎng)絡責任，從而導致雙方能量消耗速率出現(xiàn)轉變，實現(xiàn)了節(jié)點能量的均勻消耗，比起傳統(tǒng)協(xié)議，相同入網(wǎng)電量和相同業(yè)務負荷場景下，節(jié)點的生存周期增加了一倍。

5 結 語

本文針對能量受限網(wǎng)絡，完成了基于能量均衡Ad Hoc網(wǎng)絡的混合路由協(xié)議設計與實現(xiàn)。對傳統(tǒng)的OLSR路由協(xié)議算法進行了深入的分析與改進，實現(xiàn)了表驅動路由協(xié)議與能量感知和負載均衡的結合，并引入次優(yōu)多跳路由的思想，改善了OLSR路由協(xié)議路由開銷較大和各節(jié)點能量消耗不均衡的問題，延長了網(wǎng)絡的生存周期。

[1] 李曉鴻等. 一種最大化Ad Hoc網(wǎng)絡生存期的拓撲控制算法.計算機研究與發(fā)展，2013，50(3):461-471.

[2] 袁韻潔等. 一種自適應功率控制的信道預約多址接入?yún)f(xié)議.西安電子科技大學學報(自然科學版),2013,40(2)：181-186.

[3] 樊志平等.無線傳感網(wǎng)絡能量有效負載均衡的多路徑路由策略. 小型微型計算機系統(tǒng),2013,34(2):254-257.

[4] K.Sumathia,A.Priyadharshinib.ENERGY OPTIMIZATI- ON IN MANETS USING ONDEMAND ROUTING PROTOCOL, Procedia Computer Science,2015,47:460-470.

[5] AL-Gabri Malek,Chunlin LI, Zhiyong Yang,Naji Hasan.A.H,Xiaoqing Zhang. Improved the Energy of Ad Hoc On-Demand Distance Vector Routing Protocol. IERI Procedia,2012,2:355-361.

[6] Abeer Ghandera, Eman Shaaban.Power Aware Coopera- tion Enforcement MANET Routing Protocols. Procedia Computer Science,2015,73:162-171.

[7] 鄭石等. 基于能量感知的ad hoc 路由算法研究.通信學報，2012，33(4)：9-16.

[8] 秦軍等. 一種基于組合度量的OLSR 擴展鏈路狀態(tài)路由協(xié)議.計算機技術與發(fā)展,2013,23(4):47-54.

[9] 劉半藤等.基于移動—能量代價函數(shù)的無線自組織網(wǎng)絡路由測量研究.傳感技術學報，2017,12(4)：15-19.