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

2016-01-08蔡钊,马林华,宋博等

计算机工程与科学 2015年6期

基于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.