无线传感器网络高效数据收集算法研究

刘卉，曾利军，高芳，李晓翠（湖南工学院计算机科学与信息学院，衡阳　421002）

无线传感器网络高效数据收集算法研究

刘卉，曾利军，高芳，李晓翠
（湖南工学院计算机科学与信息学院，衡阳421002）

以有界均衡树概念为基础，随机交换节点的数据转发路径，通过负载均衡来实现无线传感器网络数据采集树的寿命最大化。提出一种简单但更为有效的传感器节点交换策略，提高收敛速度。此外，还提出该算法的一种低能耗分布式版本。仿真实验结果表明，该算法可以有效提升数据收集树的寿命，且时间复杂度低于其他当前算法。

无线传感器网络；数据收集；网络寿命；有界均衡树

湖南省科技计划项目（No.2013SK3177、No.2014GK3145）、衡阳市科技计划项目（No.2013KG68）、湖南工学院大学生创新项目（No.H1436）、湖南工学院校级科研项目（No.HY12008）

0　引言

无线传感器网络（WSN）是近年来受到国内外广泛关注的研究热点。无线传感器网络一般部署在条件恶劣或者人类很难进入的环境中。在一个无线传感器网络中，分布着数量庞大的节点，这些节点往往被用户用飞机或汽车运输，然后以随机的方式放人指定区域执行复杂的任务。数据收集是无线传感器网络中最重要的操作之一，能否有效地收集到合适的数据，直接关系到应用的效果。由于WSN是由低功耗和能量受限的传感器节点组成，WSN研究中的一个关键问题是设计有效的节能方案，以最大限度地提高网络寿命。

1　相关工作

节能问题是目前无线传感网中的研究热点，相继有众多的学者提出了一系列方法用于延长无线传感网络寿命的方法，如林恺等人［4］提出一种利用能量预测选择簇头节点的分簇算法：CHEP利用文中建立的传感器节点工作状态转换模型，CHEP算法将所得的剩余能量预测参数作为考虑因素引入阈值的计算，从而使高剩余能量且能耗较慢的节点能够在每一轮中被优先选为簇头节点。仿真结果表明，CHEP能够很好地平衡网络负载，延长网络寿命。曲家庆等人［5］基于拓扑结构的连通和覆盖性建立节点的休眠调度模型，提出了一种优化网络寿命的新方法（CCLO）。该方法设计了一种根据节点剩余能量动态激活一组满足连通覆盖条件的工作节点，当某个节点因能量耗尽而失效时，其邻近的休眠节点将代替失效节点继续维持网络的正常工作。理论分析和仿真表明，CCLO能够快速有效地判别冗余节点，保证无线传感器网络的覆盖性和连通性的同时降低能耗，延长网络寿命。张强等人［5］提出了一种新的数据聚合方案。分别对簇内成员节点和簇头节点进行数据聚合处理，簇内节点引入相对信息熵减少数据量的发送，而簇头节点维持一个反馈比较值，当接收到簇内成员节点发送的数据或得到自身传感器模块的数据时，该值可以用来判断是否转发接收到的数据。通过与LEACH协议的仿真对比实验，结果表明新方案能有效减少网络中的数据包传送数目，降低节点能耗，并显著地延长了网络寿命。

2　系统建模

引入有界均衡树概念，并展示最优有界均衡树如何解决寿命最大化问题。设G=（V，E）图表示在监测区域随机部署的传感器节点，其中V=｛v0，v1，…，vN｝表示与N个传感器节点和Sinkv0对应的顶点；E为表示传感器间（无线）通信链路的边集。假设传感器部署的密度足够大，可以保证G中无区域被隔离。我们称G为N个传感器的连通图。

数据收集树T=（VT，ET）是G=（V，E）的非周期性生成子图，且Vj=V，Ej∈E，其中v0是第0层树Ts的根。设L表示T中节点的最大层数。当需要层数信息l时，节点可以表示为Vj；否则将出于简便考虑而省略下标。在图G的有根生成树T中，节点vi和vj如果有共同的母节点，则它们为姐妹节点。节点vi的子节点集合表示为Ci。设M表示树T中的叶节点集合。在图G的不同数据收集树中，可能有不同的路径从vj通往Sink。我们将Tk表示为图G第k个数据收集树表示Tk中从vi到v0的路径。以节点vi为根的子树表示为T（vi），而节点vi的当前能量预算表示为e。我们将v的数据接收率

ii表示为一次数据收集周期内从子节点收到的数据量。这里，一次数据收集周期表示Sink从所有传感器节点收集数据的过程。

vi的数据生成率定义为一次数据收集周期内vi生成的数据量。类似地，vi的数据发送率定义为一次数据收集周期内vi发送的数据量。我们将vi的能量损失率ri定义为vi花费在数据收集周期期间的能量。对所有节点，用Et和Ec表示用于数据传输和接收的单位能量。数据生成的能耗则忽略不计［5］。因此，vi的能量损失率为。我们最后定义节点vi的负载γi为 ri与ei的比。请注意，在本文模型中，节点vi的寿命定义为。

图1给出了连通图和三种不同的数据收集树T1，T2，T3。在该图中，节点vi表示为vi。数据收集树边上的数字表示每次数据收集周期沿着该边传输的单位数据量。在该例中，出于简便考虑，假设每个节点的能量预算和数据生成率均为1。根据定义，树的最大负载为3个单位，而树T1，T2为4个单位。因为一个节点的寿命与其负载成反比，所以树T3首个节点能量用完的时间要早于树T1，T2。

图1　连通图和3个可能的数据收集树

3　LM-BBT算法

本文通过利用树变换和节点交换策略来均衡数据收集树的路径负载。以图1为例，通过丢弃边（v2，v7）并加入边（v7，v3）可以将树T1变换为树T2。考虑到以vi为根的子树表示为T（vi），通过这一操作，经由v7将树T （v2）变换为树T（v3）。类似地，我们可以将T（v1）从T（vi）变换到T（v3）上，利用T1获得T3s。出于简便性考虑，我们再次假设对图中的所有节点有ei=1，=1。在T3中，对第1层的每个节点有=2且Rti=3。如果Et=Ec=1，则v1，v2，v3的负载均为5个单位。根据定义3，所有叶节点的路径负载也为5个单位。因此，对T3，路径负载得到了完美的均衡。下面将详细阐述本文提出的基于有界均衡树的网络寿命最大化算法LM-BBT。

LM-BBT算法主要包括3个函数：交换函数，潜在母节点搜索函数和更新树函数。交换函数是LM-BBT的函数，而潜在母节点搜索函数用于当节点被选择用于交换时为其选择合适的母节点。最后，更新树函数可以更新节点的负载及路径负载。

算法1：SWITCH（T）

1为每个vi∈V初始化（γi，σi）；

2为每个vi∈V设置β←0和Pi←1/2；

3设va为负载最高结点；

4 while βa≤βmaxdo

5if max｛σiM｝-min｛σiM｝≤δ then Return T；

6else

7Set α←Ca；将βa加1；

8while α≠Ø do

9按照FIFO次序把结点vj从α中删除；

10W←FINDPOTENTIALPARENTS（G，vj）；

11if W=Ø then α←α∪Cj；

12else

13if SWITCHINGDECISION（pj）then

14从W中均匀选择一个结点作为vj的新母结点

16else α←α∪Cj；

17UPDATETREE（T）；

18设置va为负载最大结点；

19then Return T；

算法1描述了交换函数，其中βi表示γi被选为最高负载节点的次数。此外，βmax表示一个节点可被选择进行交换的最大次数。我们稍后将讨论如何调整βmax以实现收敛。最后，pi表示交换概率。首先，对已知树T的所有节点的负载和路径负载初始化。交换次数初始值和所有节点的初始交换概率分别设为0和1/2（第1-2行）。然后，选择负载最高的节点va（第3行）。持续交换步骤，直到某个节点被选择βmax次（第4行）。此时，while循环终止，返回更新树（第19行）。在循环内，如果到达δ有界条件，则返回树。否则，Vα的子节点插入队列α（第7行），且更新Vαs的计数。第2个循环一直持续，直到队列为空（第8行）。在每一步骤中，将节点vj从队列移除，且队列W中元素均是其潜在母节点（第9-10行）。如果vj无任何潜在母节点，则把vj的子节点加入队列，且考虑这些节点进行后续步骤的交换过程（第11行）。将在本文小节稍后讨论vj的潜在母节点选择问题。如果vj有可与之交换的潜在母节点，则通过交换决策函数根据其当前交换概率来做出随机决策。如果决策结果是进行交换，则以均匀概率从列表中选择节点作为vj的新母节点。否则，vj与其当前母节点保持，把的子节点加入队列供后续处理（第13-16行）。请注意，当vj被交换时，并不考虑对其子节点进行交换，因为在vj交换之后，整个子树T（vj）通过新的母节点转发数据。当队列为空时，表明va子节点的交换已经完成。用新的节点负载和路径负载数值对树进行更新，在下一轮中选择负载最高的节点（第17-18行）。

算法2中的潜在母节点搜索函数可以返回已知节点vi的潜在母节点列表。具体来说，如果它的路径负载低于vj的路径负载且相关幅度超过δ，则vj的相邻节点vi加入相应的潜在母节点列表。在每次交换过程中，算法3中的树更新函数可以获得树中每个节点vi的新数值（γi，σi）。

算法2：FINDPOTENTIALPARENTS（G，vj）

1for G中vj的任意相邻结点vido

3Return W；

算法3：UPDATETREE（T）

1对T按照自下而上遍历顺序为所有vi∈V计算γi；

2对T按照自上而下遍历顺序为所有vi∈V计算σi。

4　结语

本文提出一种高效的随机交换算法LM-BBT，通过负载均衡来实现无线传感器网络数据收集树的寿命最大化。本文方法以有界均衡树概念为基础，随机交换节点的数据转发路径。我们提出一种简单但更为有效的传感器节点交换策略，提高了收敛速度。我们还提出了本文算法的一种低能耗分布式版本。仿真结果证明，本文算法可以有效提升数据收集树的寿命，且时间复杂度低于其他当前算法。在下一步工作中，我们将研究δ对各种场景下寿命的影响。此外，我们还将把交换概率描述为不同网络参数（例如密度、度数）的函数，以降低收敛时间。

［1］钱志鸿，王义君.面向物联网的无线传感器网络综述［J］.电子与信息学报，2013，35（1）∶215-227.

［2］Aderohunmu F A，Paci G，Brunelli D，et al.An Application-Specific Forecasting Algorithm for Extending WSN Lifetime［C］.Distributed Computing in Sensor Systems（DCOSS），2013 IEEE International Conference on.IEEE，2013∶374-381.

［3］Asorey-Cacheda R，García-Sánchez A J，García-Sánchez F，et al.On Maximizing the Lifetime of Wireless Sensor Networks by Optimally Assigning Energy Supplies［J］.Sensors，2013，13（8）∶10219-10244.

［4］林恺，赵海，尹震宇，等.一种基于能量预测的无线传感器网络分簇算法［J］.电子学报，2008，36（4）∶824-828.

［5］Buragohain C，Agrawal D，Suri S.Power Aware Routing for Sensor Databases［C］.INFOCOM 2005.24th Annual Joint Conference of the IEEE Computer and Communications Societies.Proceedings IEEE.IEEE，2005，3∶1747-1757.

Wireless Sensor Networks；Data Gathering；Lifetime of Networks；Bounded Balanced Tree

Research on Efficient Data Gathering Algorithm for Wireless Sensor Networks

LIU Hui，ZENG Li-jun，GAO Fang，LI Xiao-cui
（Department of Computer and InformationScience，Hunan Institute of Technology，Hengyang 421002）

Based on the concept of the bounded balanced trees，our algorithm randomly switches the data forwarding paths of nodes，and the lifetime of data gathering tree of WSN is maximization through the load balancing.Provides a simple yet effective switching strategy for the sensor nodes，resulting into faster convergence.Presents a distributed implementation of our scheme with low energy overhead.The simulation results confirm that our approaches can significantly increase the lifetime of data collection trees with a lower time complexity than other existing schemes.

1007-1423（2016）20-0010-04

10.3969/j.issn.1007-1423.2016.20.002

刘卉（1980－），女，湖南衡阳人，硕士，副教授，研究方向为无线传感器网络、智能信息处理

曾利军（1976-），男，湖南邵东人，副教授，硕士研究生，研究方向为数据挖掘、最优控制、智能信息处理

高芳（1994－），女，湖南衡阳人，本科，在校学生，研究方向为无线传感器网络

李晓翠（1986-），女，湖南衡阳人，讲师，硕士研究生，研究方向为智能信息处理

2016-04-12

2016-06-30