无线传感器网络能量感知增强树型路由协议研究*

何杏宇，周亦敏，杨桂松*，王 伟

（1.上海理工大学实验室管理与服务中心，上海 200093；2.中国科学院云计算中心，东莞 523808）

无线传感器网络能量感知增强树型路由协议研究*

何杏宇1，周亦敏1，杨桂松1*，王 伟2

（1.上海理工大学实验室管理与服务中心，上海 200093；2.中国科学院云计算中心，东莞 523808）

现有的无线传感器网络路由协议普遍采用设定固定最小能量阈值的方法来避免低剩余能量的节点被选为数据转发节点，以防止因节点过早死亡而导致的网络结构破坏。然而这种方法缺乏应用灵活性。在本研究提出的能量感知增强树型路由协议中，设定了随着网络整体能量下降而动态变化的节点剩余能量阈值，以使得网络中所有节点的能量均衡下降，且采用了同质化加权求和的方法将邻居节点节省的路由跳数和剩余能量同时考虑进路由决策过程。最后，实验结果显示该协议可进一步提高网络稳定性。

无线传感器网络；能量感知增强树；动态剩余能量阈值；同质化加权求和

无线传感器网络WSN（Wireless Sensor Networks）是一种由大量分布式自治传感器节点通过相互合作来感知或监测物理和环境状况的新型网络［1-2］。这些传感器节点本身在存储、计算、通信带宽和能量供应方面的资源受限，其中，传感器节点的有限能量对网络稳定性和网络寿命的限制尤为明显［3］。因此，能量感知和能量效率问题则成为无线传感器路由协议研究中的热点［4-7］。

树型路由TR（Tree Routing）由于它的简单性成为无线传感器网络中一种较为基础的路由策略。但是，树型路由协议的一个主要缺点是随着加入网络的子孙节点的增多，路由跳数的计算量也快速增加。并且，树型路由协议并没有完全利用存储在节点内的邻居表。为了能充分利用邻居表信息，文献［8-9］提出了增强树型路由 ETR（Enhanced Tree Routing）协议。除了父子链路，增强树型路由协议还使用了和一跳邻居节点之间的邻居链路，通过判定使用该邻居链路能够产生出比树型路由跳数更短的路由捷径。虽然这将有效减少系统的存储和计算代价，在网络路由跳数和能量消耗方面会更加优越。但是存在这样一个问题：如果被选择的下一跳节点本身具有较少的剩余能量，那么通过它来转发数据包将会加速该邻居节点的死亡速度，从而导致网络死亡节点个数增加，网络拓扑结构发生变化。

为了避免低剩余能量的节点被选为转发节点，目前的路由协议普遍采用设定固定最小能量阈值的方法来筛去剩余能量较少的节点［10-11］，该方法应用灵活性较差，当固定最小能量阈值设定过大时，不能保障当网络中所有节点的剩余能量都小于最小能量阈值时网络的继续运行。而文献［12］提出的动态能量阈值模型仅和时间相关，并不是直接和网络中的能量变化相关，不能较好地反映了网络节点的实际能量消耗状态。

为此，本研究提出能量感知增强树型路由EAETR（Energy-Aware Enhanced Tree Routing）协议，在使用增强链路的同时，把邻居节点的剩余能量信息同时考虑进路由决策过程，设定随着网络整体能量下降而动态变化的节点剩余能量阈值，该动态的剩余能量阈值直接和网络中能量的变化相关，在网络初期节点初始能量比较高时，动态剩余能量阈值的变化相对快，随着网络能量的消耗，网络中大多数节点的剩余能量都比较低，动态剩余能量阈值变化开始减慢，不仅保证网络中所有节点能量是均衡下降的，直至所有节点的能量都消耗殆尽，避免了个别节点的过早死亡，维持了网络拓扑结构，提高了网络稳定性。另外，本研究中的算法在综合考虑节点剩余能量和节省跳数这两个不同质的单目标时，不同于以往直接加权求和［13-15］，例如，文献［15］中直接将邻居节点个数和节点剩余能量这两个不同质的对象进行加权求和。考虑到不同因素的衡量量化值的差距，本文则是先通过比例的方式分别将这两个不同质的单目标转换为同质化后再进行加权求和，这样更具合理性。

1 能量感知增强树型路由协议

1.1 网络参数定义

在能量感知增强树型路由协议中，能量感知增强链路必须是增强链路，为了判定能量感知增强链路，首先需要确定增强链路的存在以找到相对于树型路由来说更短的路由捷径，然后根据邻居节点的剩余能量信息选择最优的邻居节点为下一跳节点，在进行详细判定之前，为方便阐述现给出以下几个定义：①对网络中任意2个节点Ni和Nj，NCA（Ni，Nj）为Ni和Nj所具有最大网络深度的共同祖先节点；②当前路由决策节点Nm的目的节点为Nd，邻居节点为Nn，若数据包由Nm→Nn→Nd所经过的路由跳数少于树型路由中Nm→Nd所经过的路由跳数，那么Nm到Nn之间存在增强链路；③对当前路由决策节点Nm和它的目的节点Nd，Nm所对应的网络深度为dm，Nd所对应的网络深度为dd，邻居节点Nn对应的网络深度为dn，NCA（Nm，Nd）对应的网络深度为dmd。

同时，一定的网络地址分配机制能够保证任意一个节点的网络地址能够决定它的网络深度，并且任意两个节点Ni和Nj的网络地址能够决定它们的NCA（Ni，Nj）节点的网络深度。

如图1所示，当前路由决策节点Nm的网络深度为dm，目的节点Nd的网络深度为dd，Nm和Nd的共同祖先节点NCA（Nm，Nd）的网络深度为dmd。Nm的邻居为Nn，Nn的网络深度为dn，Nn与Nd的共同祖先节点NCA（Nn，Nd）的网络深度为dnd。

对于网络中任意一对源和目的节点来说，为了判定是否存在邻居节点Nn，使得Nm→Nn→Nd所经过的路由跳数少于树形路由中Nm→Nd所经过的路由跳数，当前路由决策节点Nm将分别计算出树型路由的路由跳数HTR和增强树型路由的路由跳数HETR。数据包经过树型路由到达目的节点Nd所需要的路由跳数HTR为：

在使用邻居表的情况下，Nm将计算出数据包通过一跳邻居节点Nn到达目的节点Nd所需要的路由跳数HETR：

图1 增强链路的判定

那么，相对于树型路由来说，数据包通过与该一跳邻居Nn形成的链路到达Nd所能节省的路由跳数为：

如果ΔH＞0，那么增强链路存在，则路由的下一跳节点Nx是邻居节点Nn，即ΔH=HTR-HETR＞0，并且参数之间满足如下关系：

反之如果ΔH≤0，说明经过Nn并不能形成比树型路由更短的路由捷径，数据包将沿着树型路由路径发送。如图1所示，其中Nm→Nn的虚线表示待判定的增强链路，假如式（4）成立即存在路由捷径，则形成增强链路，否则就抛弃。在图1中，根据式（3）可知ΔH=HTR-HETR=6-4=2，那么增强链路存在且可以通过使用增强链路节省2跳的路由跳数。

1.2 能量感知增强链路的判定

能量感知增强树型路由协议（EAETR）在使用邻居表来寻求路由捷径的时候，如果存在多个邻居节点，EAETR不仅仅考虑通过使用这些邻居节点形成的路由捷径所能节省的路由跳数，而且还把这些邻居节点本身的剩余能量信息考虑进路由决策过程来选择最优的下一跳节点。在EAETR中，根据EAETR协议得到的下一跳邻居节点称为EAETR邻居节点，与EAETR邻居节点之间的链路称为EAETR链路。

在无线传感器网络中，由于网络的稠密部署，当前路由决策节点会扫描到多个邻居节点，对于当前路由决策节点所扫描到的k（k≥1）个邻居节点来说，并不是通过所有的邻居节点都能形成比树型路由跳数要少的路由捷径，也就是说，在这k个邻居节点中，只有满足式（4）的邻居节点才具备形成路由捷径的条件。那么，EAETR邻居节点必定是从满足式（4）的邻居节点之中进行选择。为了进一步研究，假定有l（1≤l≤k）个邻居节点满足式（4），这些邻居节点用集合N来描述，N=｛N1，N2，…，Ni，…，Nl｝，这里Ni（1≤i≤l）代表第i个可以形成路由捷径的邻居节点。同时，集合H用来描述和这l个邻居相关联的其所能节省的路由跳数，H=｛ΔH1，ΔH2，…，ΔHi，…，ΔHl｝，这里ΔHi（1≤i≤l）代表着通过使用第i个邻居所形成的路由捷径所能节省的路由跳数，该结果可以根据式（3）计算得到。并且，这l个邻居节点所对应的剩余能量值用集合E来表示，E=｛E1，E2，…，Ei，…，El｝，这里Ei（1≤i≤l）意味着第i个邻居本身的剩余能量。很明显，由于网络能量消耗的不均，对于这l个邻居节点来说，通过其所形成的路由捷径所能节省的路由跳数以及其本身所携带的剩余能量可能是不同的。本研究给定节点的动态剩余能量阈值为¯E，只有剩余能量值大于¯E的邻居节点才能承担数据转发的任务。给定网络的初始节点个数Ninitial，网络节点的初始能量Einitial，这里定义¯E为：

这里，α为协调系数用来调整网络节点初始能量Einitial的减小速度，x为节点剩余能量阈值 ¯E的变化次数。这种设计在实际程度上反映了网络节点的能量消耗状态，在网络初期节点初始能量比较高，动态剩余能量阈值¯E的变化可以快一点，随着网络能量的消耗，网络中大多数节点的剩余能量都比较低，动态剩余能量阈值¯E的变化可以开始减慢。

EAETR使用下面的判定过程来找出EAETR邻居节点，并建立当前路由决策节点和EAETR邻居节点之间的EAETR链路。

这里假定有r（r≤l）个邻居节点的剩余能量大于或等于能量阈值，这些邻居节点用集合NT来描述，NT=｛N1，N2，…，Ni，…，Nr｝，1≤i≤r，且NT⊆N。同时，集合HT用来描述和这r个邻居节点相关联的其所能节省的路由跳数，HT=｛ΔH1，ΔH2，…，ΔHi，…，ΔHr｝，1≤i≤r，且HT⊆H。并且，这r个邻居节点所对应的剩余能量值用集合ET来表示，ET=｛E1，E2，…，Ei，…，Er｝，1≤i≤r，且ET⊆E。

可见，对于任意一个这样的邻居Ni∈NT，1≤i≤r，在路由决策过程中，和邻居节点相关联的所能节省的路由跳数和邻居节点本身的剩余能量是两个重要的判定参数，可以把其具有的这两个参数表示为Pi=（ΔHi，Ei），1≤i≤r，用P来表示所有剩余能量大于¯E的邻居所具有的这两个参数的集合，这里P=（P1，P2，…，Pi，…，Pr），1≤i≤r。那么，在EAETR中，选择哪一个这样的邻居作为下一跳节点非常重要。

对于任意一个这样的邻居Ni∈NT，WΔHi用来表示使用第i（1≤i≤r）个邻居形成的路由捷径所能节省的路由跳数在所有r个邻居所形成路由捷径所能节省的路由跳数中所占的比率，这里，

同样，对于任意一个这样的邻居Ni∈NT，WEi用来表示第i（1≤i≤r）个邻居本身的剩余能量在所有r个邻居所具有的剩余能量中所占的比率，这里，

那么，能量感知单元Fi的最大值Fmax可以通过如下公式计算得到，

因此，EAETR将根据式（9）选择能量感知单元具有最大值的邻居节点为最优下一跳节点，该邻居节点即为EAETR邻居，当前路由决策节点Nm将建立与该邻居节点之间的EAETR链路来传输数据包。如图2所示，当前路由决策节点Nm将在自己的r个邻居中选择EAETR邻居来发送数据包到目的节点Nd，根据式（9）判定之后，Nm选择邻居节点N2为下一跳邻居节点，并建立与N2之间的EAETR链路，通过邻居节点N2不仅可以得到比树型路由更短的路由捷径，而且其本身还具有充足的能量转发数据包。

虽然上述判定方法可以快速发现邻居节点，但是为了减少判定次数以节省计算量，研究发现该过程存在以下几种情况：如果目的节点Nd是当前节点Nm的邻居节点，则EAETR链路存在且下一跳节点Nx= Nd；如果目的节点Nd不是当前节点的邻居节点，但它是当前节点的祖先节点，那么下一跳节点为父节点Np，即Nx=Np；如果目的节点Nd既不是当前节点的邻居节点又不是其祖先节点，但是它是当前节点的子孙节点，那么下一跳节点为子节点Ns，即Nx=Ns；如果目的节点Nd既不是当前节点的邻居节点又不是其祖先节点，也不是它的子孙节点，而是邻居节点的父节点或子节点，那么EAETR链路存在且下一跳节点为邻居节点Nn，即Nx=Nn；如果目的节点Nd既不是当前节点的邻居节点又不是其祖先节点，也不是它的子孙节点，更不是邻居节点的父节点或子节点，那么对此节点进行EAETR链路判断，若EAETR链路存在，则下一跳节点为邻居节点Nn，若EAETR链路不存在，下一跳节点是当前节点的父节点Np。根据EAETR得到的路由协议如图3所示。

图2 EAETR链路的判定

图3 能量感知增强树型路由协议

2 能量感知增强树型路由协议性能评估

本研究使用OMNet++网络事件驱动仿真软件，利用基于IEEE802.15.4模型的ZigBee网络对TR，ETR和 EAETR协议分别进行仿真，重点分析了EAETR协议在减少网络节点死亡个数和保持网络结构方面的性能。

如图4所示，网络中的死亡节点个数随着网络运行时间不断增加，EAETR能极大缩减网络中死亡节点个数，实验结果表明，相对于TR和ETR协议来说，EAETR协议能够分别缩减大约38%和22%的死亡节点个数。分析该项网络性能的原因在于，ETR协议在选择下一跳邻居节点的时候，不考虑节点的剩余能量信息，低能量节点很快死亡，而EAETR协议在选择下一跳邻居节点的时候，避开了那些剩余能量比较低的节点参与路由决策，并且设置了动态的剩余能量阈值，使得网络中各节点的能量均衡下降，减少了节点死亡过早的概率，提高了网络稳定性，延长了网络的生命期。

图4 网络中死亡节点个数

如图5所示，网络节点的邻居节点个数随着时间发生变化。对于ETR协议来说，随着网络运行，网络中节点的邻居节点个数明显减少。相对来说，EAETR协议中随着网络运行，网络中节点的邻居节点个数几乎不发生变化。显然，EAETR协议因具有动态能量感知特性，有利于网络结构的保持和网络稳定性的提高。

图5 网络中节点的邻居个数

3 结束语

本文提出了能量感知增强树型路由协议，采用了同质化加权求和的方法将邻居节点节省的路由跳数和剩余能量同时考虑进路由决策过程，并通过设定动态的剩余能量阈值，使得网络中各节点的能量均衡下降，避免了节点过早死亡，有利于维持网络结构和提高网络稳定性。

［1］ 赵敏华，李莉，呼娜.基于无线传感器网络的水质监测系统设计［J］.计算机工程，2014，40（2）：92-96.

［2］ 刘文军，樊建席，李春胜，等.基于ZigBee无线传感器网络的智能交通系统设计［J］.传感器技术学报，2013，26（12）：1747-1751.

［3］ 吕涛，施伟斌，范坤坤，等.WSN节点电池供电性能测试研究［J］.传感器技术学报，2013，26（10）：1457-1462.

［4］ Javad Vazifehdan R.Venkatesha Prasad，Ertan Onur，Ignas Niemegeers.Energy-Aware Routing Algorithms for Wireless Ad Hoc Networks with Heterogeneous Power Supplies［J］.Computer Networks，October，2011，55（15）：3256-3274.

［5］ Huang Chennjung，Wang Yuwu，Liao Hsiuhui，et al.A Power-Efficient Routing Protocol for Underwater Wireless Sensor Networks［J］. Applied Soft Computing，March，2011，11（2）：2348-2355.

［6］ Sudip Misra，Sanjay K Dhurandher，Mohammad S Obaidat，et al.An Ant Swarm-Inspired Energy-Aware Routing Protocol for Wireless Ad-Hoc Networks［J］.Journal of Systems and Software，November， 2010，83（11）：2188-2199.

［7］ Basma M Mohammad El-Basioni，Sherine M Abd El-Kader，Hussein S Eissa，et al.An Optimized Energy-Aware Routing Protocol for Wireless Sensor Network［J］.Egyptian Informatics Journal，July，2011，12（2）：61-72.

［8］ Wanzhi Qiu，Efstratios Skafidas，Peng Hao.Enhanced Tree Routing for Wireless Sensor Networks［J］.Ad Hoc Networks，May，2009，7（3）：638-650.

［9］ 黄学哲，邓庆绪，李传文，等.采用邻居节点的改进ZigBee路由选择算法［J］.东北大学学报：自然科学版，2013，34（12）：1703-1706.

［10］董亮，张灵，陈云华.基于限制广播的ZigBee分布式动态能量均衡协议［J］.传感器技术学报，2014，27（8）：1120-1124.

［11］曹建玲，刘文朋，彭双，等.一种基于能耗均衡的ZigBee网络高效混合路由算法［J］.电讯技术，2013，53（10）：1352-1356.

［12］王俊杰，陈其工，江明，等.LR-WPAN捷径式能量均衡树路由算法研究［J］.计算机工程与应用，2012，48（23）：95-98.

［13］蒋培成，陈鸣，李兵.一种优化ZigBee性能的综合加权选路算法［J］.小型微型计算机系统，2013，34（9）：2014-2017.

［14］赵跃华，崔琳洁.一种基于信誉和能量综合评价模型的ZigBee网络［J］.无线通信技术，2013，22（4）：42-47.

［15］邓亚军，邓利军.无线传感器网络的能量有效加权分簇算法［J］.计算机工程与设计，2011，32（4）：1216-1219.

［16］Park J，Sahni S.An Online Heuristic for Maximum Lifetime Routing in Wireless Sensor Networks［J］.IEEE Transactions on Computers，2006，55（8）：1048-1056.

何杏宇（1984-），女，上海理工大学实验员，主要研究方向为物联网与无线传感器网络，xy_he@usst.edu.cn；

杨桂松（1982-），男，上海理工大学讲师，主要研究方向为无线传感器网络、机会网络、物联网与嵌入式系统设计等，gs_yang@aliyun.com。

Research on Energy-Aware Enhanced Tree Routing Protocol for Wireless Sensor Networks*

HE Xingyu1，ZHOU Yimin1，YANG Guisong1*，WANG Wei2
（1.Lab Management and Service Center，University of Shanghai for Science and Technology，Shanghai 200093，China；2.Cloud Computing Center，Chinese Academy of Science，Dongguan，523808，China）

To avoid network structure being destroyed by early death of nodes with low residual energy for being selected as forwarding nodes，the current wireless sensor network routing protocols generally use a fixed residual energy threshold approach.However，this approach lacks flexibility in application.An Energy-Aware Enhanced Tree Routing（EAETR）protocol is proposed in this study，in which a dynamic residual energy threshold is set to change as node energy decreases so that network energy declines in a balanced way，and a homogenization weighted sum is used to consider both saving hops and residual energy of a neighbor node in the routing decision process.Stimulation results show that the protocol can further improve network stability.

Wireless Sensor Networks；energy-aware enhanced tree；dynamic residual energy threshold；homogenization weighted sum EEACC：6150P

TP393.04

A

1004-1699（2015）04-0551-06

10.3969/j.issn.1004-1699.2015.04.017

项目来源：国家自然科学基金项目（61472256，61202376）；上海市工程中心建设项目（GCZX14014）；上海市重点科技攻关项目（14511107902）；上海市一流学科建设项目（XTKX2012）；沪江基金研究基地专项项目（C14001）

2014-07-30 修改日期：2015-01-21