基于ARIMA-ANN預測模型的能量感知路由算法

基于ARIMA-ANN預測模型的能量感知路由算法*

蔡釗，馬林華，宋博，唐紅

(空軍工程大學航空航天工程學院，陜西 西安 710038)

摘要：針對傳統能量感知OLSR協議在減少傳輸功率消耗和均衡節點剩余能量之間不能兼顧的特點,提出了一種新型的基于剩余能量比例和傳輸功率消耗的OLSR路由協議OLSR_RC，它利用上述兩方面的指標構造復合能量開銷，并將其作為路由選擇的度量值。在減小網絡開銷的同時，也防止了部分低電量節點的能量被快速耗盡，延長了網絡的生存周期。此外，新路由還采用ARIMA-ANN組合能量預測模型對節點的剩余電量進行預測，降低了由于拓撲控制(TC)消息丟失對選擇路由所造成的影響。這種新型路由協議在無線傳感器網絡領域有比較廣闊的應用前景。

關鍵詞：OLSR路由；能量感知；復合能量開銷；人工神經網絡-自回歸差分滑動平均組合模型

中圖分類號：TP393 文獻標志碼：A

doi:10.3969/j.issn.1007-130X.2015.06.006

收稿日期：*2014-10-14;修回日期：2014-12-05

作者簡介:

通信地址：710038 陜西省西安市空軍工程大學航空航天工程學院

Address:College of Aeronautics and Astronautics Engineering,Air Force Engineering University,Xi’an 710038,Shaanxi,P.R.China

Anenergy-awareroutingalgorithmbasedonARIMA-ANNforecastingmodel

CAIZhao，MALin-hua，SONGBo，TANGHong

(CollegeofAeronauticsandAstronauticsEngineering,AirForceEngineeringUniversity,Xi’an710038,China)

Abstract:Aiming at the problem that the traditional energy-aware OLSR protocol cannot reduce transmission power consumption and balance the residual energy between nodes at the same time, we develop a new routing protocol called OLSR routing protocol based on residual energy ratio and transmission power consumption (OLSR_RC ). A composite energy cost involving the above two indicators is constructed, and is used as a routing metric. On one hand, the OLSR_RC protocol reduces the total power consumption of the entire network. On the other hand, it prevents the energy of the low-energy nodes from being depleted rapidly. In addition, we adopt the hybrid ARIMA-ANN model for forecasting residual energy level of the nodes, which can reduce the influence on route selection caused by topology control(TC) message loss. The new routing protocol has wide application prospects in wireless sensor networks.

Keywords:OLSRrouting；energy-aware；compositeenergymetrics；hybridARIMA-ANNmodel

1引言

移動自組網絡MANET(MobileAd-hocNETworks)是一種不依賴于固定基礎設施的新型無線網絡，網絡中的節點既可以作為發送或接收終端，也可以作為路由器轉發數據包，具有高度的靈活性和極強的抗毀性。此外，網絡創建極為方便，彌補了傳統蜂窩系統和有線網絡的種種不足。無線傳感器網絡作為移動自組網中一種重要的情形，廣泛地運用在軍事、環境監測等領域。但在大部分應用場景中，無線傳感器由能量有限的電源供電，且不易更換備用電池，故能量消耗成為制約其運行的較大瓶頸，也成為無線傳感器研究的一個熱點。

同時，在某些特定的領域，為了保證傳感器共享和分發數據的實時性，采用先應式路由有著極強的必要性，因為可以減小路由發現時間并提高分組交付率。優化鏈路狀態路由OLSR(OptimizedLinkStateRouting)作為移動自組網中一種重要的先應式路由協議，在龐大且密集的網絡中表現出了良好的性能[1]。但是，其需要所有節點定期地發送TC消息和Hello消息，網絡通信開銷大大增加。針對這種情況，人們提出了許多關于OLSR路由的能量感知改進方法。例如：有結合最小跳數和最大能量的路由[2],有基于能耗均衡和距離因子的分簇路由[3]，不勝枚舉。其中有兩種經典的協議：一種是最低能量路由[4]，它選擇傳輸數據包所需能耗最小的路徑；另一種是最大-最小路由路徑[5]，它選擇剩余能量最大的節點作為選擇路徑上的節點。最低能量路由雖然節省了傳輸數據包的基礎能耗，但是會造成那些傳輸能耗較小的節點的能量很快被耗盡，嚴重危害了網絡的生存周期。而最大-最小路由則有可能因為要避免使用最低能量的節點，而使其周邊多個低電量節點的能量快速耗盡，造成嚴重的網絡分區。為了能夠盡可能延長網絡生存周期[6，7]，我們將采取折衷的方式結合這兩種協議的優點。此外，在網絡負載比較重的情況下，OLSR協議的拓撲消息很容易由于沖突而丟失，并且越是在傳輸TC消息的上游，影響越嚴重。

為了解決上述問題，本文做出以下兩方面改進：(1)在選擇路由的時候，提出了一種基于傳輸功率消耗和節點剩余電量比例的改進路由協議OLSR_RC(OLSRroutingprotocolbasedonResidualenergyratioandpowerComsumptionfortransmission)，在降低網絡開銷的同時，均衡了節點間的能量消耗，最大限度地延長了網絡的生存周期；(2)針對TC消息容易因為沖突而丟失，采用了自回歸差分滑動平均ARIMA(AutoRegressiveIntegratedMovingAverage)模型和人工神經網絡ANN(ArtificialNeuralNetwork)的組合算法[8,9]，預測節點自身剩余能量，并廣播出去，使其他節點可以在沒有收到最新拓撲消息的情況下，利用預測值計算復合能量開銷。

2復合能量開銷的選取

在路由選徑時，結合上述兩種方法的優點，采取一種折衷的方案：在移動自組網運行初期，選取傳輸功率消耗最小的路徑，減少整個網絡的通信開銷；在網絡運行的后期，隨著節點間能量消耗率差異的增大，在進行路由選擇時優先選取剩余能量比例較高的節點，保持整個網絡在能量開銷方面的均衡，延長網絡的生存周期。

在進行建模分析時，為簡化模型做出兩點基本假設：(1)節點沒有能量補給，且其始終處于數據包發送、數據包接收和空閑這三種典型的能量消耗模式之中；(2)每個節點都有其固定的傳輸范圍。基于以上假設，本文設計了進行路由決策的目標函數WR(t)，見式(1)。在路由決策時，選擇目標函數值最小的路徑。

(1)

(2)

其中，R代表由源節點到目的節點的一條路徑，WR(t)為t時刻路由R的目標函數取值;WR_i(t)為t時刻路由R上節點i的目標函數取值，它由傳輸功率消耗部分和節點剩余能量部分構成。在自組網運行初期，節點剩余能量部分相差無幾，傳輸功率消耗對路由選徑影響比較大；在運行后期，剩余能量比例差距不斷增大，逐漸成為路由選擇的首要因素。其中，Pt_i是傳輸功率消耗部分，代表節點i傳輸單位長度的數據報文所需的能耗。公式(2)后兩項是剩余能量部分，前者與各個節點的剩余能量比例有關，體現出節點間能量消耗比例的差異，防止部分節點過早耗盡能量；后者與每個節點的絕對能量消耗有關，可以體現出自組網運行期間各節點的負載情況。通常能耗大說明其在自組網運行中承擔了更多的中繼任務，屬于關鍵節點，我們需要盡量延長他們的生存周期。但是，值得注意的是，這兩者的作用是相互沖突的，應將次要考慮因素(第三項)所占比重減小。K1、K2是比例系數，更改這兩個參數可以調節剩余能量部分的總大小及式(2)后兩項各自所占的比例。在本文中將K1設置為2，K2設置為0.2。Efull_i代表節點i的初始能量，Emax則表示網絡中異構節點的最大初始能量，它作為式(2)中第三項的分母主要是為了進行歸一化。Ri(t)為t時刻節點i的預計剩余能量，其取值可以通過后面所提出的組合預測算法得出。發射功率Pt的設置可以參照式(3)：

(3)

其中Pt、Pr分別為發射功率和接收功率(單位為dB)，d、λ分別為傳輸距離和波長(單位為m)，L是傳輸損耗。在工程實現和仿真中，我們所設置的發射功率，要保證在其通信范圍內所有節點所接收的信號功率不小于其接收靈敏度As，即：

(4)

3ARIMA-ANN組合能量預測模型

在傳感器節點運行期間，由于其受眾多因素的影響，故能量開銷的變化規律既不是平穩過程，也不是純線性或者非線性過程[10]。簡單的統計預測方法，如滑動平均和指數平滑，都不能很好地刻畫這一過程。鑒于ARIMA模型對序列具有良好的線性處理能力，ANN模型具有較強的學習和處理能力，對序列背后的非線性部分有極強的挖掘能力。故在實際應用中，我們將兩者結合起來，構建了一種基于ARIMA模型和ANN模型的組合預測模型。通過使用這兩個模型分別對時間序列的線性及非線性部分建模，更加準確地描述了能量開銷時間序列的復雜結構，并根據遞推公式計算出了節點剩余能量。

3.1基于ARIMA模型的能量預測算法

由于傳感器網絡能量開銷是非平穩序列，不滿足ARMA模型對時間序列的平穩要求，必須對其進行差分，故本文采用ARIMA模型[11]捕捉能量開銷中的線性特征。ARIMA模型是一種處理信號序列的參數化分析方法，模型表達式如下：

(5)

其中，Xi、φi、θi、εi分別表示第i個時間步長內的時間序列取值、自回歸項系數、滑動平均項系數以及白噪聲(零均值平穩隨機信號)。L為滯后算子，即LiXt=Xt-i。p是自回歸階數，q是滑動平均階數，d是將這個序列差分成平穩序列所需的差分次數，通常情況下差分不超過兩次。

求解ARIMA模型時，首先對ARIMA模型進行d次差分，將其轉化為ARMA(自回歸滑動平均)模型，然后根據自相關圖和偏自相關圖確定p、q的初步范圍，最后再采用最小信息準則和相似性準則具體確定模型的最佳階數。在獲悉模型階數的基礎上，通過均方誤差方法或最大似然方法對自回歸項系數和滑動平均項系數進行估值。在得出全部參數后，利用此前多個拓撲周期內的實測值，采用遞歸的方式對能量開銷時間序列取值進行預測，見式(6)：

(6)

(7)

3.2基于ANN模型的能量預測算法

由于無線傳感器網絡在運行中除了周期性地交互數據，還需要快速分發重要的臨時性數據，且有許多意外情況會影響其能量消耗，故其能量開銷序列存在非線性波動。只運用ARIMA模型不能很好地表現其非線性特征，因此我們采用人工神經網絡模型對實際值與預測值間的差值進行優化，盡可能準確描述能量開銷時間序列的復合特征。

人工神經網絡是根據實際輸出與網絡輸出差異最小化的原則，不斷修正神經元連接權值和閾值的智能算法[10，12]，其組成框圖如圖1所示。網絡的輸入共分為兩部分，包括外部輸入量和輸出量延遲序列。在正向傳播過程中，這些輸入信息經過隱含層處理后經過加權匯集到輸出層上，如果網絡層不能得到與預期相符的輸出，則其與實測值之間的差值將會沿原來通路進行反向傳播，用來調整神經元連接權值的大小，以減小誤差。如此反復調整，直到預測誤差小于限定閾值。在仿真中，為降低計算的復雜度，我們所建立的ANN模型中隱含層只進行一步處理，表達式為：

(8)

(9)

其中，et表示人工神經網絡輸出量，xj代表隱含層第j個節點處理后的輸出，αj表示從xj到輸出的權值，εt則為隨機誤差項。q是隱含層節點個數。 Ik、et-i分別代表t時刻第k個外部輸入量取值和t-i時刻輸出序列的取值，wij表示由第i個輸入變量到xj的權值，p是輸入反饋延時步數，σ是隱含層傳遞函數。本文中取q為50，p為30，σ(x)=1/(1+e-x)。

Figure 1　Structure model of artificial neural network 圖1　人工神經網絡結構圖

無線傳感器運行期間，網絡的拓撲結構和部分鏈路的狀態會發生一定程度的改變，這些變化都會極大影響節點的能量消耗，使能量開銷時間序列的取值出現較大的波動。為此，本文設計了四個外部輸入量，通過定量描述每個節點周邊鏈路及拓撲結構的變化，盡可能準確預測能量開銷序列的取值。在實際運用中，我們需要通過Hello消息中LinkCode字段來感知變化，并將新增或減少的對稱鄰居節點或MPR選擇節點個數送入對應的外部輸入端口，將其融入能量開銷的預測中。其中節點變化狀況與外部輸入端口的對應情況參見表1。

Table 1　 Corresponding relation table of

當列表中的某種情況發生時，外部輸入端口(I1～I4)的輸入相應置為a、b、c、d。對應的神經元連接權值通過實測值與網絡輸出差值的最小化準則來進行修正。通過多次反向傳輸過程來調整神經元連接權值，最終使輸出誤差小于限定閾值，得出模型具體參數。

3.3組合能量預測算法設計

組合模型建模共分三步，首先利用ARIMA模型對時間序列的線性部分進行建模預測，將這個取值與后續收到的實測值做差，得到時間序列的非線性特性。之后，利用人工神經網絡通過不斷修正神經元連接權值和閾值來近似描述出非線性殘差并進行預測，并將兩部分預測結果求和，得到未來多個拓撲周期內節點能量開銷的預測值。最后將節點開銷的預測值代入公式(10)通過遞推得到節點剩余能量的預測值。

(10)

其中，Ei(t)、Ri(t)分別表示節點i在第t個拓撲周期內的能量開銷預測值和第t個拓撲周期末端的剩余能量預測值。組合預測模型定期或者在預測誤差超過閾值時重新進行擬合。

4OLSR_RC路由協議設計

4.1OLSR_RC路由組成框圖

在OLSR_RC路由中增添了復合能量開銷的計算，并引入了能量預測的機制，故與傳統的OLSR協議相比，增添了三個比較重要的模塊：ARIMA-ANN的組合預測模塊、復合能量開銷管理模塊以及路由表計算模塊，他們之間的關系如圖2所示。

OLSR_RC路由運行時，首先由MAC層統計本節點包括數據包傳輸功率消耗、初始能量和當前電量在內的三個數據，將三個數據通過TC消息共享給其他節點，并將第三個數據傳給ARIMA-ANN的組合預測模塊進行定期擬合。模型預測出本節點剩余能量，并量化到1至255的整數上。這個數一方面通過TC消息共享給其他節點，另一方面保存到復合能量開銷管理模塊。復合能量開銷管理模塊利用接收到的其他節點的初始能量、當前能量(沒有最新的TC消息時使用之前收到的剩余能量預測值)及傳輸功率消耗，進行復合能量開銷計算，并對復合能量開銷存儲模塊中的數據進行更新。同時，復合能量開銷管理模塊判斷實測值與先前預測值之間的誤差是否超過閾值，來決定將計算結果交給路由表計算模塊后，需不需要通知組合預測模型重新進行擬合。路由表計算模塊對原有的Dijsktra算法做出了修改，用復合能量開銷取代跳數，在選擇路由時選取復合開銷最小的路徑。

4.2拓展TC消息格式

OLSR_RC的TC消息只增加了源節點的初始能量、當前能量、剩余能量預測值及拓撲消息發送時刻，共計八個字節，用于其他節點對復合能量開銷的計算，其格式見圖3。

Figure 3　Extended topology control message format 圖3　拓展的TC消息格式

其中，transmit_time字段占用一個字節，存放在TC消息的保留字段，用于消除傳輸中各種延遲所帶來的影響；initial_energy為節點的初始能量；power_cost代表傳輸單位長度數據報文的能量消耗；current為拓撲消息發送時刻的剩余能量；predict_i是距發送時刻2i個拓撲間隔后的剩余能量預測值，通過1～255的整數來表示其大小。通常在沒有收到MPR選擇節點最新發送的TC消息時，使用預測值作為其當前的剩余能量。predict_i-1與pedict_i的間隔為兩個拓撲消息發送周期，故一個TC消息可以預測未來50s的剩余能量，顯著降低由于拓撲消息丟失對路由發現的影響。

需要說明的是，新增的八個字節在發送消息中所占的整體比例不大。假設節點A的接口地址僅有一個，對稱節點數nsym為10，MPR節點數nmpr為4，鏈路碼類型數nLC為4，TC和Hello消息發送間隔采用默認值，則節點A在一秒內的平均控制消息發送量可由下式計算：

(11)

新增TC控制消息數據量為：

(12)

新增數據量占總發送控制消息的比例為：

(13)

由上式可知，新增數據量在總發送控制消息中所占的比例很小。同時，由于大多數控制消息的數據空間并沒有被充分利用，故由于協議改進而新增的發送消息量還要遠低于1.58%， 改進路由的新增協議開銷可以近似忽略。

5協議仿真性能分析

5.1仿真環境設置

本文利用ns2作為仿真測試平臺，測試了網絡在不同流量負載、移動速度和拓撲結構的條件下，節點的最低能量水平和平均剩余能量。表2定義了仿真時的網絡基礎配置。仿真不同拓撲結構時，同構網絡設置50個節點，功率配置參數按照表3中的集合1，異構網絡設置五個集合，每個集合包含10個節點，各集合的功率配置參數參照表3進行設置。

Table 2　 Basic network configuration

Table 3　 Power consumption parameters of

5.2仿真結果及分析

5.2.1節點最低剩余能量比較

從圖4～圖7可以看出，不論是由同構節點還是異構節點構成的網絡，在不同節點運動速度和不同數據傳輸速率的情況下，具有能量預測功能的OLSR_RC協議中的節點最低能量均好于OLSR協議的情況，并且隨著節點運動速度加快和數據傳輸速率提升，兩種協議之間的差距會進一步增大。實驗結果表明，新路由避免了網絡運行中對部分節點的過度使用，有效均衡了網絡負載。

Figure 4　Lowest energy level of the heterogeneous nodes at the packet rate of 40 kbps 圖4　數據包速率為40 kbps時異構節點最低剩余能量

Figure 5　Lowest energy level of the heterogeneous nodes at the packet rate of 50 kbps 圖5　數據包速率為50 kbps時異構節點最低剩余能量

Figure 6　Lowest energy level of the homogeneous nodes at the packet rate of 40 kbps 圖6　數據包速率為40 kbps時同構節點最低剩余能量

Figure 7　Lowest energy level of the homogeneous nodes at the packet rate of 50 kbps 圖7　數據包速率為50 kbps時同構節點最低剩余能量

5.2.2節點平均剩余能量比較

由圖8～圖11可知，在節點平均剩余能量方面，OLSR_RC路由明顯優于傳統OLSR協議，其在均衡節點間剩余能量的同時兼顧發送數據所消耗的能量，減小了網絡的總能耗，提高了節點平均剩余能量水平，延長了節點的生存周期，其能量保護性能明顯優于OLSR協議。

Figure 8　Average energy level of the heterogeneous nodes at the packet rate of 40 kbps 圖8　數據包速率為40 kbps時異構節點平均剩余能量

Figure9　Average energy level of the heterogeneous nodes at the packet rate of 50 kbps 圖9　數據包速率為50 kbps時異構節點平均剩余能量

Figure 10　Average energy level of the homogeneous nodes at the packet rate of 40 kbps 圖10　數據包速率為40 kbps時同構節點平均剩余能量

Figure 11　Average energy level of the homogeneous nodes at the packet rate of 50 kbps 圖11　數據包速率為50 kbps時同構節點平均剩余能量

6結束語

本文提出了具備能量預測功能的能量感知路由協議OLSR_RC，它用一種結合節點傳輸能耗和剩余能量的復合開銷代替了跳數，改進了路由發現中Dijkstra算法。同時，建立了ARIMA-ANN組合預測模型對節點剩余能量進行預測，降低了由于TC消息丟失對路由選擇所造成的影響。仿真結果表明，OLSR_RC協議降低了網絡總能耗，均衡了節點間的流量負載，延長了網絡的生存周期。

參考文獻:

[1]DeRangoF,CanoJC,FotinoM,etal.OLSRvsDSR:Acomparativeanalysisofproactiveandreactivemechanismsfromanenergeticpointofviewinwirelessadhocnetworks[J].ComputerCommunication,2008,31(16):3843-3854.

[2]LiPing,DaiJin.Anovelenergy-savingroutingalgorithminWSN[J].ComputerEngineeringScience,2014,36(7):1275-1278.(inChinese)

[3]ZhangShi-yue,WuJian-de,WangXiao-dong,etal.Anenergycomsumptionbalancedclusteringroutingalgorithmforwirelesssensornetwork[J].ComputerEngineering,2014,40(8):6-9.(inChinese)

[4]TariqueM,TepeK.Minimumenergyhierarchicaldynamicsourceroutingformobileadhocnetworks[J].AdHocNetworks,2009,7(6):1125-1135.

[5]BertazziL,GoldenB,WangXing-yin.Min-MaxvsMin-Sumvehiclerouting:Aworst-caseanalysis[J].EuropeanJournalofOperationalResearch,2015,240(2):372-381.

[6]WeiXiao-hai,ChenGuo-liang,WanYing-yu,etal.Optimizedprioritybasedenergyefficientroutingalgorithmformobileadhocnetworks[J].AdHocNetworks,2004,2(3):231-239.

[7]ThamaraiP.PredictingroutelifetimeformaximizingnetworklifetimeinMANET[C]//Procof2012InternationalConferenceonComputing,ElectronicsandElectricalTechnologies,2012:792-797.

[8]ZhangGP.TimeseriesforecastingusingahybridARIMAandneuralnetworkmodel[J].Neurocomputing,2003,50 (1):159-175.

[9]KhasheiM,BijariM.AnovelhybridizationofartificialneuralnetworksandARIMAmodelfortimeseriesforcasting[J].AppliedSoftComputing,2011,11(2):2664-2675.

[10]BaiYan,MaGuang-si.Trafficpredictionandanalysisbasedonthegreyradialbasisfunctionneuralnetworkmodel[J].ComputerEngineering&Science,2008,30(10):122-124. (inChinese)

[11]GuoZhi-hao,MalakootiS,CameliaS,etal.Multi-objectiveOLSRforproactiveroutinginMANETwithdelay,energy,andlinklifetimepredictions[J].AppliedMathematicalModeling,2011,35(3):1413-1426.

[12]YolcuU,EgriogluE,AladagCH.Anewliner&nonlinearartificialneuralnetworkmodelfortimeseriesforecasting[J].DecisionSupportSystem,2013,54(3):1340-1347.

參考文獻：附中文

[2]李平,戴勁.無線傳感器網絡中的節能路由算法研究[J].計算機工程與科學,2014,36(7):1275-1278.

[3]張詩悅，吳德建，王曉東,等.一種能耗均衡的無線傳感器網絡分簇路由算法[J].計算機工程,2014,40(8):6-9.

[10]白燕,馬光思.基于灰色徑向基神經網絡模型的流量預測與分析[J].計算機工程與科學,2008,30(10):122-124.

蔡釗(1990-),男,北京人，碩士生，研究方向為網絡通信技術。E-mail:laziofly1214@163.com

CAIZhao,bornin1990,MScandidate,hisresearchinterestincludesnetworkcommunicationtechnology.

馬林華(1965-),男,陜西漢中人，博士，教授，研究方向為編碼理論、抗干擾通信和寬帶網絡通信。E-mail:Malinhua1965@163.com

MALin-hua,bornin1965,PhD,professor,hisresearchinterestsincludecodingtheory,anti-interferencecommunication,andbroadbandnetworkcommunications.

宋博(1970-),男,陜西西安人，碩士，副教授，研究方向為寬帶網絡通信。E-mail:songbo1970@163.com

SONGBo,bornin1970,MS,associateprofessor,hisresearchinterestincludesbroadbandnetworkcommunications.

唐紅(1967-),女,上海人，碩士，高級實驗師,研究方向為信道編碼與調制。E-mail:tanghong1965tanghong@163.com

TANGHong,bornin1967,MS,seniorexperimentalist,herresearchinterestincludeschannelcodingandmodulation.