能量感知的WSN节点分类控制路由算法*

刘 群，白全炜，曾宪华，王 亮

(重庆邮电大学计算机学院，重庆 400065)

无线传感器网络(WSN)是一种新型的无线通信网络，它融合了通信技术，嵌入式计算技术和传感器技术，由大量的传感器节点通过无线介质连接构成，采用自组织的形式配置微型的智能传感器节点，通过节点的协同工作来采集和处理网络覆盖区域中目标信息。传感器节点通常由电池供电，而且在一些应用环境下更换电池或者对电池进行充电是不可行的，所以如何高效，合理地使用能源，尽可能地延长网络的生命期，成为了传感器网络研究的核心问题之一［1－3］。

路由协议在无线传感器网络中起着相当重要的作用，并且其能量消耗也是网络消耗中的主要部分，因此设计一种有效的路由协议是减少网络能量消耗的关键。目前在无线传感器网络中，路由协议分为三类:平面路由、分层路由以及能量感知路由。

在平面路由中所有节点具有相同的地位和功能，它们通过相互之间的局部操作和信息反馈来生成路由。平面路由的优点是简单、易扩散，无须进行任何结构维护工作，不易产生瓶颈效应，因此具有较好的健壮性，典型的平面路由有Flooding Routing［4］，DD(directed diffusion)［5］，SPIN(sensor protocols for information via negotiation)［6］等。平面路由的最大缺点在于:网络中无管理节点，缺乏对通信资源的优化管理，对网络动态变化的反应速度较慢等。

在分层路由中，LEACH算法［7］是第一个基于多簇结构的路由算法，其成簇思想贯穿于其后提出的多个算法中，但是也存在着不足。如在簇头选举的过程中没有考虑到节点的剩余能量，可能能量较低的节点被选为簇头，导致该节点过早死亡。HEED算法［8］在选择簇头时考虑了节点的剩余能量，但需要在一定的迭代次数内与周围邻居节点不断地进行信息交互，因此算法的实现需要额外的通信代价。PEGASIS［9］则将节点组织成链的形式，链的形成由每一个节点或者基站计算得到，因此需要知道网络拓扑的全局信息。

随着无线传感器网络研究的深入，路由协议的研究已从当初避免网络拥塞和保持网络连通性等方面，转而重点研究提高整个网络的利用率、平衡网络流量和能耗、减小通信延时等方面，而能量感知路由则代表着该研究方向。

文献［10］提出了一种能量感知路由协议，EAR(Energy Aware Routing，简称EAR)协议。在该协议中，源节点和目的节点之间建立多条通信路径，每条路由都具有一个与节点剩余能量有关的选择概率，当源节点需要向目的节点传输数据时，协议根据路径的选择概率选择一条路径进行数据传输。但该机制没有考虑对距离(跳数)的优化，且需周期性地实施洪泛查询来进行路由维护，增加协议开销。

文献［11］提出的GEAR协议根据地理位置信息，建立Sink到监测区域的优化路径，支持Sink向监测区所有节点发送查询命令，避免了洪泛传播方式，减少了路由建立的开销。GEAR把节点到监测区域的距离和节点剩余能量定义为估计路由代价，并利用捎带机制获取实际路由代价，进行数据传输的路径优化，形成能量高效的传输路径。协议虽然实现了节点间的负载均衡，但在异构网络中，初始能量较少的节点会较早耗尽能量而失效，影响整个网络的性能。并且随着网络中建立的路由不断增加，在路由方向上的节点耗能增大，其选择代价增大，相应地，路由方向以外的节点会被优先选择，从而出现数据在多个能量旺盛的节点间跳转的现象，称为“折线效应”，其直接的后果就是数据传输的延时增加，网络总能耗增大。

针对GEAR协议的不足之处，本文提出了一种新的能量感知的WSN节点分类控制路由算法CEAR(Classifying Control-based Energy Aware Routing Algorithm fornodesin WirelessSensorNetworks，CEAR)。算法首先定义了能量阈值把普通节点分为骨干节点和独立节点，从而保护初始能量较少的节点。然后骨干节点通过建立骨干路由树来传输数据，独立节点则根据周围邻居节点的不同情况采用不同的选择函数进行下一跳路由;针对部分独立节在传输数据时会出现“折线效应”，算法采用了自适应调整策略，从而消除此折线效应，提高了数据传输的时效性，节约了网络总能耗。

论文余下部分结构如下:第1部分主要是介绍无线传感器网络的拓扑结构;第2部分从能量阈值、骨干路由树的建立以及独立节点的路由选择三个大的方面具体阐述本文算法;第3部分通过实验验证CEAR算法在均衡节点能量消耗，传送数据包和延时方面都优于GEAR算法;第4部分为总结与展望。

1 WSN拓扑结构描述

无线传感器网络没有底层基础设施。在传感器被放置到监测环境后，传感器自行组织构成网络。其基本网络拓扑可分为 3种［12］，分别是基于簇(Cluster)的分层结构、基于网(Mesh)的平面结构和基于链(Chain)的线结构，其各自的网络拓扑结构如图1所示。

图1 自组织无线传感器网络拓扑图

基于簇的分层结构具有天然的分布式处理能力，簇头就是分布式处理中心，每个簇成员都把数据传给簇头，在簇头完成数据处理和融合，然后由其他簇头多跳转发或直接传给用户节点，簇中的成员是轮流或者每次选择剩余能量最多的成员做簇头。基于网的平面结构传感器节点连成一张网，网络健壮性强，且传输可靠性非常高，个别链路和传感器节点发生失效时，不会引起网络分立，可以同时通过多条信源信宿间路由传输数据。基于链的线性结构传感器节点被串联在一条或多条链上，链尾与Sink节点相连。

2 CEAR路由算法

2.1 能量阈值

Sink节点需要周期性地探测网络的能量情况来生成能量阈值，但探测整个网络所有节点的能量情况会给网络带来更大负担，所以Sink节点只探测周围邻居节点的能量情况，来近似估计整个网络的能量情况，从而生成能量阈值。

定义1能量阈值(Energy Threshold):Sink节点首先对周围邻居节点的剩余能量进行探测［13］，统计并计算各邻居节点剩余能量的均值，该均值为本文的能量阈值，即记

其中，Ni为sink节点周围的第i个邻居节点，n为邻居节点个数为第i个邻居节点的剩余能量。

定义2骨干节点(Mainstay Node，记作MN):如果任意普通节点Ni有Es(Ni)≥ET，那么该普通节点Ni属于骨干节点。其中，Es(Ni)表示节点Ni自身的剩余能量。

定义 3独立节点(Independent Node，记作IN):如果任意普通节点Nj有Es(Nj)＜ET，那么该普通节点Nj属于独立节点。其中，Es(Nj)表示节点Nj自身的剩余能量。

2.2 建立骨干路由树

汇聚节点通过广播路径建立消息，各节点对广播报文内的信息和自身信息进行判断，建立骨干路由树［14］，从而形成数据的主要传输路径。具体步骤如下:

(1)如果节点是汇聚节点，则通过发送MYAGENT_ASK报文对邻居节点的能量情况进行探测，并准备接收MYAGENT_ANSWER报文，从而近似估计出整个网络的能量情况。

(2)如果传感器节点收到MYAGENT_ASK报文，则回复MYAGENT_ANSWER报文来报告自身能量情况。

(3)汇聚节点通过接收MYAGENT_ANSWER报文来获得邻居节点的能量，将这些节点及其能量写入MYAGENT_ENERGY缓冲区，并通过计算均值来获得能量阈值。

(4)汇聚节点将能量阈值放入到MYAGENT_BROAD报文中，对网络进行广播。

(5)如果普通传感器节点收到 MYAGENT_BROAD报文，首先将自身剩余能量与ET进行比较，如果小于ET，则节点被判定为独立节点，转向(6)。否则，通过到汇聚节点的跳数来决定是否将该节点放入骨干路由树中。如果通过判断该节点能够加入到骨干路由树中，则转向(8)，否则继续等待其他节点发送的MYAGENT_BROAD报文。

(6)当节点被判定为独立节点时，就会定时发出MYAGENT_RREQ报文，对邻居节点的情况进行探测，并准备接收MYAGENT_RREP报文，将邻居节点情况写入MYAGENT_RARRAY缓冲区。

(7)如果节点收到MYAGENT_RREQ报文，则回复MYAGENT_RREP报文，来报告自身的路由情况。

(8)当节点被判定可以加入到骨干路由树中，将其在树中的父节点的信息写入father缓冲区，判断该路径上的最小PA(power Available)，并把MYAGENT_BROAD报文中的rp_hop项加1，继续向邻居节点转发该报文。

(9)所有节点都不停的准备接收各种MYAGENT报文，当不再有MYAGENT报文发送和接收时，骨干路由树建立过程结束，得到的网络结构图如图2所示。

图2 网络结构图

利用路由树生成算法建立骨干路由树，该建树过程融入了源节点到目标节点的最小跳数算法［15］，骨干节点通过骨干路由树进行数据传输，由此可知，骨干节点传输数据时不会出现“折线效应”。

2.3 独立节点的路由选择

2.3.1 能量效用选择函数

如果节点是IN，则要对邻居节点进行周期性的信息探测［16］来获得该节点到汇聚节点的下一跳信息，然后在利用选择函数来选择更优化合理的下一跳节点。IN进行路径探测所获得邻居节点的信息可能出现四种情况，下面对这四种情况分别讨论如下:

(1)如果邻居节点中包含汇聚节点(如图3中虚线区域所示)，则不进行选择函数计算，把汇聚节点作为该节点发送或转发数据的下一跳节点。因为数据直接传送给汇聚节点能减少给其他节点带来的负担及整个网络的能量消耗。

图3 IN的邻居节点包含Sink节点

(2)如果邻居节点中既包含骨干节点又包含独立节点(如图4虚线区域所示)，则对独立节点不予考虑，只考虑骨干节点，如果有几个骨干节点处于同一条路径上，则只保留到达汇聚节点跳数最少的骨干节点，放弃其他节点。最后选择的节点都是各条通往汇聚节点路径上距汇聚节点跳数最少的骨干节点，用Nj表示。

图4 IN的邻居节点包含两类节点

定义4选择函数P与PAj成正比，与dij和Hj成反比。即独立节点INi选择下一跳节点的函数为:

其中，PAj为Nj所在路径上的最小可用能量，dij为节点INi和Nj的直接通信距离，Hj为骨干节点Nj到汇聚节点的跳数。

该IN可以根据选择每个骨干节点的函数值和每项的通信代价［17］计算本身到汇聚节点的代价COST(INj)，该代价可用于其他独立节点选择下一跳节点时的函数计算。由于网络中骨干路由树的覆盖度较高，因此仅对这些经过一跳到达骨干路由树的独立节点进行特殊考虑，其他经过多跳到达骨干路由树的节点不予考虑。

定义5独立节点INj的代价为各个下一跳节点到达汇聚节点通信代价的平均值，即

其中，PAj为最小可用能量，dij为直接通信距离，Hj为骨干节点到汇聚节点的跳数。

(3)如果邻居节点全部是独立节点(如图5虚线区域所示)，并且这些独立节点中含有经过一跳就可到达骨干路由树的节点，则只对这部分节点(用INj表示)进行考虑，放弃其余独立节点。这样可以使数据尽快到达汇聚节点并减少整个网络的能量消耗。

定义6选择函数P与Rj成正比，与dij和Cost(Nj)成反比。即INi的选择函数为:

其中，Rj为独立节点INj的剩余能量，dij为节点INi和INj的直接通信距离，Cost(Nj)为独立节点INj到汇聚节点的代价。

图5 含一跳到达骨干节点的节点

(4)如果邻居节点全部是独立节点(如图6虚线区域所示)，并且这些独立节点都不能经过一跳到达骨干路由树，则根据独立节点INi到独立节点INj的直接通信距离dij以及独立节点INj的剩余能量Rj进行选择函数计算。

定义7独立节点INi的代价选择函数为:

其中，RNj为独立节点INj的剩余能量，dij为直接通信距离，考虑上述决策值在数量级上可能不一致，需要进行归一化，dmax和Rmax分别为到所有邻居节点距离的最大值和剩余能量的最大值;t为权重系数。

图6 不含一跳到达骨干节点的节点

由上述可以看出，邻居节点距离独立节点越近，剩余能量越多，其代价函数值越小，从而被选择为路由节点。该路由选择策略具有良好的方向性和节点能量均衡性［18］。从而使基于节点剩余能量进行数据传输的路由中，能量较多的节点得到充分利用，保护能量较少的节点。

2.3.2 选择函数的自适应调整策略

针对2.3.1节中第4种情况可能会出现“折线效应”，对选择函数中的权重系数t引入自适应调整机制，其计算公式为:

其中，n0为网络第1次建立数据路由的节点跳数;k为“折线效应”判定系数，可取≥1的整数;h为某次数据路由的当前跳数。当h≥kn0时，判定为出现“折线效应”。

在网络运行初期，路由尚未出现“折线效应”时，权重系数t=t0;而当h≥kn0时，出现“折线效应”，权重系数t的值以指数形式增加，如图7所示，增加了距离因子在选择函数P中的重要程度，从而剩余能量较多的节点对路由的吸引力降低，路由的方向性得以改善，“折线效应”开始被抑制;在路由跳数持续增大的情况下，权重系数t会继续增加并趋于1，逐渐降低“折线效应”。当t=1时，路由协议即退化为纯地理信息路由。“折线效应”的消除可以减小路由的延时，降低网络总能耗。

图7 权重系数的变化

3 实验仿真

为了评估本文路由算法的性能，在NS2中分别把GEAR和本文算法进行了仿真。重点通过网络的吞吐量、死亡节点数以及端到端延迟来进行对比分析，仿真结果表明，CEAR算法能够达到预期效果。

在仿真环境中，设置网络范围为150 m×150 m，网络节点数为100并随机分布，汇聚节点处于整个网络的几何中心。仿真中采用NS2提供的CMU无线模块，该模块实现了传输带宽为1 M的802.11协议，Sink节点的初始能量设置为10 J，发送功率为0.5 W，接收功率为 0.4 W，节点的通信距离为40 m，传感器节点的初始能量在1 J～6 J间随机分布。数据包大小为4 000 bit，发送的时间间隔为0.5 s，网络运行时间为 40 s。网络参数k=1、t0=0.5。使用gawk脚本对生成的.tr文件进行分析，仿真实验结果如图8、9、10、11 所示。

图8显示了网络在相同的时间内发送的数据包数量基本相同。

图8 发送包数目对比

图9显示了网络中的数据包接收数量，从图中可见，开始一段时间内，GEAR路由协议算法下的汇聚节点收到的数据包数量要略高于CEAR路由算法。当网络运行一段时间后，CEAR算法中接收数据包的数量逐渐与GEAR路由协议算法持平，在剩余的大部分时间内，CEAR的汇聚节点收包数明显高于GEAR路由协议。因为CEAR算法周期性的生成能量阈值保护了低能量节点，并且骨干节点和独立节点有规则地控制数据传输，尽可能的避免了通信中断，进而使得数据包发送成功率得到较大程度的改善。

图9 接收包数目对比图

图10显示了网络中的死亡节点数，从图中可以看出，网络运行的前一段时间，CEAR算法中的死亡节点数要明显低于GEAR路由协议。而网络运行后期，CEAR路由协议中死亡节点数与GEAR路由协议基本持平，甚至在最后阶段超过了GEAR路由协议。因为CEAR算法使用了能量阈值，随着网络的运行，低能量节点会逐渐增多，所以死亡节点数会出现增多的现象。另外，CEAR算法Sink节点收包数明显高于GEAR路由协议，表明网络运行后期，CEAR算法消耗更多的能量，导致死亡节点数目增多。这从侧面反应了CEAR算法处于正常运行状态的时间要长于GEAR路由协议。

图10 死亡节点数对比图

图11显示了数据包从源节点到Sink节点的传输延时。从图中可知，CEAR算法端到端的平均时延减小，随着节点数增加，网络中的数据流量也会增加，进而造成延时也加大。CEAR算法通过建立骨干路由树和对部分独立节点的选择函数引入自适应调整策略来尽可能的抑制“折线效应”，使源节点和Sink节点之间的路由得到优化，数据包的平均传输路径变短，从而降低了端到端的传输时延。

图11 传输数据包延时对比图

4 总结与展望

本文提出了一种基于能量感知的传感器网络节点分类控制路由算法(CEAR)。该算法根据能量阈值周期性地把普通节点分为骨干节点和独立节点，从而保护低能量节点。骨干节点根据骨干路由树生成算法建立骨干路由树，骨干节点按照骨干路由树进行数据的传输，独立节点根据保存的周围邻居节点信息利用能量效用选择函数选择下一跳节点进行数据传输。对部分选择函数引入自适应调整策略来消除折线效应，从而减小路由的延时，提高路由的时效性。仿真结果表明，CEAR算法克服了GEAR路由协议算法的缺陷，能够进一步均衡能耗，降低数据传输延时，延长网络生命周期。

目前，无线传感器网络路由算法的研究是非常广泛的，不少新颖的想法被相继提出。然而，大多数都还停留在理论研究阶段，网络环境设置相对简单，与真实的复杂场景相比还有很大差距。本文也只是做了一定的理论设计，算法的现实可行性还要进一步验证。在本文的基础上，有很多值得继续研究和探讨的地方:能量阈值不是通过全网节点的能量情况来计算的，如果能够设计出更优的公式计算出最理想的能量阈值，对于延长网络生命周期将会具有更加重要的意义;另外本文的仿真实验方案稍显简单，要进一步提高算法的有效性，在后续工作中，最好能够在一些比较典型的异构网络中对算法进行模拟实验。

［1］Akyildiz I F，Su W，Sankarasubramaniam Y，et al.A Survey on Wireless Sensor Networks［J］.IEEE Communication Magazine，2009，40(8):102－114.

［2］于海斌，曾鹏，梁群.智能无线传感器网络系统［M］.北京:科学出版社，2006:215－278.

［3］李建中，高宏.无线传感器网络的研究进展［J］.计算机研究与发展，2008，45(1):1－15.

［4］Hedetniemi S，Liestman A.A Survey of Gossiping and Broadcasting in Communication Networks［J］.Network，2002，18(4):319－349.

［5］Shah R C，Rabaey J M.Energy Aware Routing for low Energy Ad hoc Sensor Networks［C］//Proc.of the IEEE Wireless Communications and Networking Conference.New York，USA:［s.n.］，2006.

［6］Kulik J，Heinzelman W，BalakrishnanH.Negotiation Based Protocolsfor Disseminating Information in Wireless Sensor Networks［J］.Wireless Networks，2009，8(2/3): － .

［7］Sun Yong，lingBo，ZhangZonglin.EnergyEfficientNode Placement Method of Wireless Sensor Networks Based on Uneven Ring Belt Model［J］.Chinese Journal of Sensors and Actuators，2008，19(4):1287－1289.

［8］YOUNIS O，FAHMY S.A Hybrid Energy Efficent Distributed Clustering Approach for Ad_Hoc sensor Networks［J］.IEEE Transcations on Mobile Computing，2004，3(4):660－66.

［9］Karlof C，Wagner D.Secure Routing in Wireless Sensor Networks:Attacks and Mountermeasures.The 1st IEEE Int’1 Workshop on Sensor Network Protocol and Applications，Anchorage，Alaska，2007.

［10］Shan R C，Mabaey J.Energy Aware Routing for Low Energy Ad Hoc Sensor Networks［C］//Wirless Communication and Networking Conf(WCNC 2002)，Florida，USA，2002.

［11］Yu V，Govindan R，Estrin D.Geographical and Energy Aware Routing:a Recursive Data Dissemination Protocol for Wireless Sensor Networks［R］.http://graphics.stanford.edu/courses/cs428－03－spring/papers/reading/Networking/Estringeo－routingo1.pdf，2009－03－15.

［12］张学，陆桑璐，陈贵海.无线传感器网络的拓扑控制［J］.软件学报，2008，18(4):943－954.

［13］KIM M，JEONG E，BANG Y C，et al.Multipath Energy-Aware Routing Protocol in Wireless Sensor Networks［C］//INSS 2008:Proceedings of the 5th International Conference on Networked Sensing Systems.Kanazawa［s.n.］，2008:127－130.

［14］李翔，阎新芳，孙雨耕，等.无线传感器网络中簇树骨干网的构建及算法［J］.传感技术学报，2006，19(4):1279－1283.

［15］郝晓辰，窦晶晶，刘浩然，等.基于链路质量的WSN代价均衡路由选择算法［J］.电子与信息学报，2010，32(5):1212－1218.

［16］Conti M，Francesco M D，Passarella A，et al.Energy Conservation in Wireless Sensor Networks:A Survey［J］.Ad Hoc Networks，2009，(7):537－568.

［17］刘群，先兴平，郭松涛.无线传感器网络路由中合作性重复博弈模型的研究［J］.传感技术学报，2010，23(9):1322－1327.

［18］黄旗明，刘笑.均衡能耗和时延的无线传感器网络组内融合机制研究［J］.传感技术学报，2009，22(1):126－130.