无线自组网中基于能量感知的跨层路由算法

邓 敏，徐 方,2+，熊曾刚，叶从欢，夏洪星

(1.湖北工程学院 计算机与信息科学学院，湖北 孝感 432000；2.武汉大学 计算机学院，湖北 武汉 430072)

0 引 言

在自组织网络的环境下，由智能移动设备构成的无线自组网节点受能源约束的影响很大，智能移动设备上日益增长的复杂应用和无线通信给设备带来了越来越大的能量压力[1]。设备因能量耗尽而停止提供服务，出现网络分割的情况，导致网络的一部分不能和网络的另一部分进行正常通信[2]。因此，国内外研究者正致力于研究能量相关的路由协议，期望提高无线自组网中数据传输的能量效率。

最初，在计算路由协议的开销时，主要采用节点的剩余能量进行度量。文献[3]中的路由算法主要考虑节点上的初始能量、传输节点的剩余能量和每一次传输的开销来选择最高效的路径。通过计算路径沿线节点的剩余能量总和，文献[4]说明了MBCR路由协议在路由决策时如何考虑路径上总的剩余能量。文献[5]描述了对MBCR路由进行改进的算法，它综合使用路径上的转发跳数和总体能量消耗，能够进一步提高转发效率。最小能量流失率路由[6]引入节点能量消耗速率进行路由的度量，但是当网络流量变化波动不大时，该方法的计算和评估不够准确。DELAR[7]提出了一种能够跨层感知能量负载的框架，通过考虑节点的剩余能量和网络中节点的密度，能够适合于由多种类型节点组成的异构无线自组网。LAER路由[8]是一种具有链路稳性感知和能量感知的路由算法，通过采用多目标线性规划来优化路由决策。E2路由[9]提出了节点失效度的概念，并结合节点的剩余能量设计了一种灵活高效的路由方法。

目前，智能移动设备在日常生活中的普及，有利于形成新型的无线自组网，而这类网络的路由性能还存在较大的提升空间。人们在生活中使用这些智能节点，并安装了各种应用程序，而应用程序的运行对节点能量效率有一定的影响，进而影响到路由效率，因而在设计这类网络的路由算法时，不仅要考虑节点的剩余能量和链路稳定性，还要进一步考虑应用程序对节点能耗的影响。基于以上分析，本文提出了一种能量感知的路由算法(context-aware energy-efficient routing，CAER)，算法采用跨层设计的思想设计能耗均衡的路由算法，提高网络中的能量使用效率和网络性能。

1 系统模型

1.1 上下文认知自学习模型

本文针对移动设备的特点提出了一种基于上下文认知的自学习模型(context-aware model，CAM)。CAM能动态采集系统中与应用相关的上下文信息，对上下文信息进行学习并优化调整相关参数，从而能动态地预测系统未来的能量消耗信息。首先，模型需要周期性的采样系统使用情况的相关数据，然后设计能量模型，并通过采样的数据来训练该模型，最后根据设备当前的状态计算出应用相关的能量效用值。为了减少模型产生的开销，模型中存储用户应用程序的功率特征信息以减少在系统中进行的采样频率。此外，模型的训练可以在设备充电时运行，从而减少对设备电池的消耗。

CAM模型工作在网络的应用层。当一个新的应用启动时应用程序监测模块可以识别当前应用程序的类别。上下文信息采样模块从操作系统获取所需要的上下文信息，这些信息包括：屏幕的亮度、设备的额定功率值、电池电量，以及设备各组件的工作负载状态，这些组件如中央处理器(CPU)、图形处理器(GPU)、无线局域网接口(WLAN)、蜂窝网络接口(CELL)和显示屏(MON)。应用程序监测模块监测设备上运行的应用程序并获取相关信息，如应用程序的类型、持续时间等。上下文信息处理模块周期性获取上述上下文信息，对上述上下文信息进行融合和推理，计算设备上与应用相关的能量消耗的效用值，为下一步的路由决策提供依据。上下文信息处理模块将经过处理的上下文信息存储在上下文知识库中，上下文知识库主要包含组件负载能耗表、应用负载信息表、监测和推理出的相关上下文信息。上下文知识库中的信息能反映系统的动态变化，为下面的路由设计提供相关的能量约束信息。下面介绍上下文认知自学习模型的3个阶段，分别是：初始化阶段、应用程序监测阶段、应用层能量效用计算阶段。

1.2 初始化阶段

日常生活中，由于人们所携带的移动设备规格存在多样性，同样的应用程序在不同的移动设备上可能产生不同的工作负载，即使是同样的工作负载百分比，也可能在不同的设备上产生不同的能量消耗。因而在初始化阶段需要建立组件负载信息表，使得CAM模型能够适应于不同种类的移动设备。

根据文献[10]研究结果表明，目前的移动设备(如智能手机和平板电脑)的主要耗能组件为：中央处理器(CPU)、图形处理器(GPU)、无线局域网接口(WLAN)、蜂窝网络接口(CELL)、屏幕(MON)。在初始化阶段，首先运行一组预定义的任务在这些组件上产生不同程度的工作负载，然后监测相应的功率消耗。相关研究也表明[11]，只要经过合理的设计，这类在线监测和能量建模对设备正常使用的影响是微不足道的。

在初始化阶段，模型在上下文知识库中建立了一个组件负载能耗表，见表1。该表记录各组件工作负载百分比与能量消耗速率之间的对应关系。在初始化阶段，通过在节点上运行一组预定义的任务来获取各组件的工作负载，设定的负载为5%、25%、50%、75%和100%。使用LCPU(x)、LGPU(x)、LWLAN(x)、LCELL(x)、LMON(x)分别表示CPU、GPU、WLAN、CELL、和MON等组件的工作负载是x%，Preal(x)表示工作负载为x%时从系统采样的功率值。其中，x=5,25,50,75,100。

表1 组件负载能耗

系统的工作负载可以由表1中的组件的工作负载来表示，式(1)给出了当前系统的能量模型，Psys是当前系统的功率消耗。该能量模型考虑了上述提到的所有主要硬件组件的负载与系统能耗的关系。Lcomp(i)表示第i个组件上的工作负载。组件对应的权重Wcomp(i)用来平衡不同的组件对总体效用的影响。我们通过训练能量模型可以得到权重因子Wcomp(i)的值，模型训练的数据来自组件负载能耗表，其中存储了真实的工作负载与在系统中监测到的系统的功率值。式(1)中，C为多元线性回归模型中的常量

(1)

能量模型的误差函数如式(2)所示，训练过程的目标是最小化模型输出值的误差。通过比较模型计算的功率值Pcal(由式(1)计算得出)和从操作系统采样的真实功率值Preal，我们可以获得误差值，然后利用这些误差值调整权重值Wcomp(i)，达到优化能量模型的目的，从而进一步提高模型预测的精度

(2)

在初始化阶段我们设计了能量模型，并且通过对模型的训练取得了较优的权重值Wcomp(i)。在下一阶段，我们将使用工作负载作为模型的输入，使用模型评估系统的能量约束。

如上所述，系统的功率消耗被建模成一个预测模型。我们可以用目前的一些常用的回归方法来求解模型的参数，其中非线性方法有支持向量回归(SVR)和人工神经网络(NN)；线性方法有多元线性回归(MLR)。线性方法的主要优点是易于实现，而非线性方法可能会获得更高的精度。由于移动设备资源受限，采用线性回归能满足该场景的精度和低能耗需求。

1.3 应用程序监测阶段

在监测阶段，我们构建一个应用负载信息表，一旦一个新的应用(表中没有记录的应用)启动，CAM模型记录这个应用程序运行时在各组件上额外产生的工作负载，当应用程序关闭时，计算该应用程序在组件上产生的工作负载的平均值，并把这些应用作为一条新的记录存入应用负载信息表，见表2。

表2 应用负载信息

表2描述了应用负载信息表的基本结构。对于应用程序j，LCPU(j)表示CPU的工作负载，LGPU(j)、LWLAN(j)、LCELL(j)表示了类似的含义。屏幕的工作负载不记录在这个表中，因为屏幕的能耗由其亮度决定，而屏幕的亮度取决于环境的照度和用户的喜好，因此需要单独采集和存储。以上由应用程序产生工作负载可以用一个向量表示，如式(3)所示，PAPP(j)为应用j的功率特征

(3)

系统中应用程序产生的总功能值可以由系统中每个应用程序的功率消耗值之和表示。在计算能量约束时，式(4)的计算结果作为能量模型的部分输入，能量模型的输出则是整个系统的功率值

(4)

模型通过监测和更新应用相关的上下文信息提高其自适应能力，使得应用负载信息表能动态反映当前设备的使用情况。当应用负载信息表存在记录的应用启动时，模型考虑表中的数据计算当前的能量约束，运行阶段根据当前设备相关信息对应用负载信息表采用增量更新的方式，CAM对于表中存在的应用，不定期的采样这些应用在各个组件的平均功率，根据式(5)更新一个应用程序对应的功率消耗PAPP(j)(updated)，新的功率消耗PAPP(j)(updated)由两个因素组成，一个是从表中取得的老的功率消耗值PAPP(j)(old)，另一个是刚刚从系统测量到的新的PAPP(j)(new)。使用归一化的权重值(Wold,Wnew)表示两个值对最新工作负载的影响，权重的取值由应用程序的运行持续时间决定。每当一个应用开始运行时，利用式(5)计算应用j对应的功率消耗和新采样的负载值更新应用负载信息表，从而实现上下文认知自学习过程

PAPP(j)(updated)=Wold·PAPP(j)(old)+
Wnew·PAPP(j)(new)

(5)

(6)

相比于定期的硬件级别的监测，本文提出的模型是一个简单和低开销的方法，因为部署了该模型的设备能够识别应用的类型，并结合功能特征和能量模型计算当前应用的能量约束。应用负载信息表中的数据可以用于训练模型，因为它动态记录设备使用的变化情况。

1.4 应用层能量效用计算阶段

由于设备屏幕的亮度与人们的个人喜好相关，在计算设备的功率消耗特征时，应分别考虑应用产生的功率消耗和屏幕产生的功率消耗，则式(1)中表述的能量模型可以转化为式(7)进行表示

Psys=PAPP+WMON·LMON+C

(7)

式(8)中，Uapp描述了应用对应能量约束的效用函数。Psys为式(7)计算出的系统当前功率消耗，Prat为设备的额定功率值

(8)

应用层能量效用不仅考虑应用程序的效用还应考虑网络中节点内的剩余能量情况，在式(9)中，检测时应用程序的实时能耗值用Econs表示，节点总电量用Etotal表示，Ubat为节点剩余能量效用函数，它的取值范围是0到1之间

(9)

(10)

应用层能量效用(Cnode)由节点中应用的效用和节点中剩余能量的效用组成，如式(11)所示。通过使用归一化的权重Wapp和Wbat来协调上述两个因素的贡献

Cnode=Wapp·Uapp+Wbat·Ubat
Wapp+Wbat=1

(11)

经过上述自学习过程中，应用层能量相关的上下文信息被学习和利用，在当前设备中，该过程对每类应用程序在每个硬件组件上产生的工作负载进行监测和采样，然后将应用相关的能量约束存储在应用负载信息表中。此外，每当一个应用程序启动时，新的监测值会被用于更新应用负载信息表，体现了模型的自适应和自学习能力。通过使用这种方法，模型能够处理移动应用市场上的大量应用程序。

2 CAER路由机制

2.1 跨层设计

在传统互联网中，分层设计的思想被广泛使用。在分层设计中，网络各层模块间相对独立使得网络设计较为简单并容易实现。但是，随着移动无线网络的出现，传统分层设计的方法不利于未来普适网络的发展。普适网络要求网络中的节点能感知节点自身和周围环境上下文信息，并以自组织自适合的方式为用户提供服务。而采用跨层设计的方法可以增强网络各层的信息共享，从而能有效提高网络的服务质量和能量效率。在本文提出了CAER路由的跨层设计方案中，网络层在进行路由决策时，可以充分利用应用层，网络层和数据链路层中的上下文信息，使得网络中的数据传输更高效更节能。

图1描述了网络中的应用层、数据链路层和网络层实现信息共享的过程，简要描述了上述网络层如何通过交换上下文信息来实现跨层节能的路由决策。图中灰色背景的模块是重点强调部分，分别是应用层的上下文认知自学习模块、网络层的路由信息处理模块和数据链路层的链路稳定性监测与度量模块。

图1 路由的体系结构

应用层使用应用监测、能耗监测、剩余能量监测3个组件来收集应用与能耗相关的上下文信息，使用上下文认知自学习模型处理收集到的上下文信息。数据链路层部署的链路稳定性监测与度量模块能够分析接收到的无线信号强度，并利用相应的效用函数计算信号强度的效用值。网络层的路由信息处理模块包含上下文信息融合和路由信息处理，该模块接收应用层的能量约束信息和数据链路层链路稳定性信息，跨层共享各类上下文信息进行路由决策。在CAER路由算法的设计中，本文采用跨层设计的方法，使得算法能够综合利用应用层、网络层和数据链路层的信息进行路由设计和数据转发决策，有助于提高网络的服务质量和能量效率。

2.2 路由算法

本文提出的基于能量感知的跨层路由算法是在AODV路由算法[12]的基础上进行的改进，在路由发现阶段采用广播报文的方法，转发节点需要建立和维护路由表，并根据路由表进行数据报文的转发。和AODV算法一样，本算法也包含两个过程，分别是路由发现阶段和路由维护阶段。接下来，本文重点介绍在AODV算法基础上的改进部分。

当源节点需要发送数据时，源节点向周围的邻居节点发送路由请求报文(RREQ)，RREQ报文中包含的主要字段如图2所示，本文在AODV协议RREQ报文的基础上进行了改进，添加了节点的开销(Enode)和链路的开销(Elink)。

图2 RREQ帧格式

节点能量开销Enode的计算方法如式(12)所示，链路稳定性效用值Elink的计算方法如式(13)所示，路由路径上当前节点的序号为k，设源节点的序号为1，沿着路由路径序号k的值依次递增，目的节点的序号用n表示

(12)

(13)

当某个中间节点接收到路由请求时，如果中间节点的路由表中包含有到达目的节点的路由信息，那么中间节点直接返回路由应答报文(RREP)，源节点收到该报文，完成路由发现过程；否则直到目的节点收到路由请求报文(RREQ)。当第一个RREQ报文到达目的节点时，目的节点启动计时器，接收延时T时间内所有的路由请求报文。对于接收到的所有RREQ报文，利用式(14)计算该路径上的效用值(Croute)，取Croute值最小的路径作为数据转发路径，并在该路径上发送路由应答报文(RREP)，完成路由的发现过程

(14)

3 性能评估

3.1 参数设置

利用NS2网络仿真软件，本文评估了CAER路由算法的能量效率和性能。在同样的网络环境中，对比分析了CAER、AODV、LAER和E2算法，为了充分分析路由算法的能量效率，网络中的150个节点被分为3种类型，根据节点上运行的应用程序分为A类节点50个(空闲节点)，B类节点50个(游戏节点)，C类节点50个(视频流节点)。数据传输时，随机选择4对源节点和目的节点，传输速率的比特率分别为150 Kbps、200 Kbps、250 Kbps、300 Kbps 和350 Kbps。仿真实验的持续时间设为120 s，每种实验运行30次。A、B、C这3类节点的功率分别为150毫瓦、350毫瓦和550毫瓦。WiFi接入的功率为400毫瓦，网络中节点的能量初始值为100焦耳。在计算式(11)时，Wapp和Wbat权值分别设为0.4、0.6，体现了应用能效与剩余能量对总效用的实际影响。

3.2 不同运行时间下的能量消耗

A、B、C这3种类型节点的平均能耗情况如图3～图5所示，本文提出的CAER路由在不同程度上为3类节点节省了电能。对于A类节点来说，CAER算法的节能效果最明显，因为A类节点处于空闲状态，节点剩余能量多，为跨层信息共享的路由机制提供了更多的节能空间。以AODV协议为基准进行比较，采用CAER方案可以为A类节点节约18%的能量，为B类节点节约12%的能量，为C类节点节约7%的能量。

图3 A类节点的平均能量消耗

图4 B类节点的平均能量消耗

图5 C类节点的平均能量消耗

3.3 网络生存时间

图6描述了在不同数据传输率下使用各算法的网络生存时间，随着网络中数据传业务的增加，网络负载不断增大，能量消耗也在逐渐加大，因而随着传输速率的增加，网络生存时间逐渐缩短。因为AODV算法没有考虑能量消耗等因素，其在生存时间上的表现最差，考虑了能量信息的其它3种路由算法能不同程度的提高网络生存时间。以AODV为基准，CAER算法平均提高网络生存时间大约20%，而LAER和E2分别提高了大约12%和15%。

图6 网络生存时间

4 结束语

能量受限是无线网络的重要特征之一，对于移动自组网络更是如此。本文研究的无线自组网节点主要由人们携带的智能通信设备组成(如智能手机、平板电脑)，受限于目前的电池技术，智能通信设备的电能仅能维持较短的时间，然而智能通信设备上应用程序的不断增加，进一步加快了设备上的能量消耗，从而降低了网络的生存时间，当网络中某个节点因能量耗尽而停止工作，可能会导致网络分割，进而影响整个网络的性能。本文主要针对由智能移动设备组成的无线自组网，研究基于能量感知的跨层节能路由算法。该算法采用跨层设计的思想综合利用数据链路层、网络层和应用层的上下文信息，提高了网络中能量的使用效率和生存时间，实现了能量效率与网络性能之间的平衡。

[1]Yao Y,Cao Q,Vasilakos A V.EDAL:An energy-efficient,delay-aware,and lifetime-balancing data collection protocol for heterogeneous wireless sensor networks[J].IEEE/ACM Transactions on Networking,2015,23(3):810-823.

[2]Priya S S,Krishnan H M.Energy aware span routing protocol in mobile Ad Hoc networks[J].Wireless Communication,2016,8(1):11-16.

[3]Pantazis N A,Nikolidakis S A,Vergados D D.Energy-efficient routing protocols in wireless sensor networks:A survey[J].IEEE Communications Surveys & Tutorials,2013,15(2):551-591.

[4]Bade S,Kumar M,Kamat P.A reactive energy-alert algorithm for manet and its impact on node energy consumption[J].International Journal of Computer Applications,2013,71(18):1-6.

[5]Varaprasad G,Narayanagowda S H.Implementing a new power aware routing algorithm based on existing dynamic source routing protocol for mobile ad hoc networks[J].IET Networks,2014,3(2):137-142.

[6]Gandhi C,Arya V.A survey of energy-aware routing protocols and mechanisms for mobile ad hoc networks[M].India:Springer India,2014:111-117.

[7]Hu L,Yuan’an L,Dongming Y,et al.Study of capacity region and minimum energy of delay-tolerant unicast mobile ad hoc networks using cell-partitioned model[J].Wireless Communications & Mobile Computing,2016,16(7):825-849.

[8]De Rango F,Guerriero F,Fazio P.Link-stability and energy aware routing protocol in distributed wireless networks[J].IEEE Transactions on Parallel and Distributed Systems,2014,23(4):713-726.

[9]Ramrekha TA,Talooki VN,Rodriguez,et al.Energy efficient and scalable routing protocol for extreme emergency ad hoc communications[J].Mobile Network Appl,2015,17(2):312-324.

[10]Ahmad R W,Gani A,Hamid S H A,et al.A survey on ener-gy estimation and power modeling schemes for smartphone applications[J].International Journal of Communication Systems,2016,12(3):22-33.

[11]Li D,Halfond W G J.An investigation into energy-saving programming practices for android smartphone app development[C]//Proceedings of the 3rd International Workshop on Green and Sustainable Software.ACM,2014:46-53.

[12]Ahmed A,Hanan A,Osman I.AODV routing protocol working process[J].Journal of Convergence Information Technology,2015,10(2):1-10.