一种新的高能效无线传感器网络数据收集协议*

林梅金 苏彩红 李如雄

（1.佛山科学技术学院 2.广东电网公司佛山供电局）

0 引言

近年来随着传感器技术、低功耗电子器件和射频技术的飞速发展，低成本、低能耗、多功能的微型无线传感节点的大量生产成为发展趋势[1]。传感节点随机或固定地布置在监测环境中，通过特定的协议自组织构成无线传感器网络，协同监测周围环境信息以完成特定任务。而节点通常安装在环境恶劣甚至危险的远程场合中，能源难以更换，这使得如何高效利用节点有限的能量以延长传感器网络寿命，成为网络协议设计中需要考虑的首要因素[2]。为了延长整个网络寿命和提高网络的利用率，较好的途径是寻找一种更好的节省网络节点消耗能量的算法，而分簇正是为了解决这些问题引入对网络分层方法的重要技术[3]。

Heinzelman W. R.等[4]首次提出低能耗自适应分簇算法（low-energy adaptive clustering hierarchy，LEACH）协议应用在无线传感器网络中，该协议以数据为中心构建单层簇，其基本思想是首先按照自组织方式随机选择节点作为簇首节点，普通节点选择离自己最近的簇首节点加入，簇首节点采用分时复用的方式为本簇中每个节点分配数据传输的时间隙。簇首融合簇内成员以及簇首自己收集的数据后发送至基站。LEACH算法以随机方式选择簇首节点常常导致簇与簇之间分布不均匀，并且所有簇首节点均直接与基站通信，导致离基站较远的簇首节点因能量消耗很快先行死亡。针对LEACH协议的不足，文献[5]中提出一种基于链的数据收集协议（power-efficient gathering in sensor information systems，PEGASIS）。在PEGASIS协议中，簇首节点只需和离它最近的邻居簇首节点通信，数据通过多跳传输至基站，从而降低了簇首节点的能耗，与LEACH协议相比，获得了更长的网络寿命。但是，当网络中出现过长的通信链路时，将导致数据传输至基站的能耗增大，不利于延长网络寿命。文献[1]指出协议PEGASIS和低能耗的数据收集及融合方法（power efficient data gathering and aggregation，PEDAP）[6]在网络运行时，由于需要获取所有节点位置和更新路由信息而产生大量能量开销等缺点，提出一种基于分簇和近优最小汇集树的多级路由数据收集协议（energy-efficient data gathering protocol，DEEC-MR），提高网络的可扩展性和可靠性，延长了网络寿命。

借鉴前人研究[1-8,11]的优点，本文提出一种新的高效节能数据收集协议—NDGP。该协议具有以下性质：1) 是一种分布式算法；2) 能实现簇首节点在网络中均匀分布；3) 算法运行能耗低；4) 不要求节点具有特殊的通信能力，即不需要所有节点都能与sink节点直接通信。

1 系统模型

无线传感器网络完成一次网络拓扑构建并且运行一段时间进行数据收集，称为一“轮”。NDGP协议按轮运行，网络中传感节点周期性地充当簇首节点（cluster head, CH）或者普通节点（ordinary node, ON）进行环境监测及数据转发。文中假定将N个无线传感节点随机均匀分布在一个M×M的正方形区域中，并进行了以下几点假设：

1) 所有传感节点部署后位置固定，且被赋予唯一的标号，传感节点的能量有限，而基站有专门的供电系统；

2) 基站部署在监测区域几何中心上，位置固定且是唯一的；

3) 节点配备的无线发射功率模块的发射功率大小可调，即可根据距离来调整发射功率的大小；

signal strength indication, RSSI）。

本文采用文献[9]提出的无线通信模型，节点收、发数据的能耗通过式(1)和式(2)计算。

其中，ETX(i, j)、ERX(i, j)表示节点i发送至节点j、接收到节点j信息的能耗；k表示节点发送或接收的数据位数；Eelec表示无线收发电路消耗的能量；Eamp表示天线增益消耗的能量；di,j表示节点i与节点j的欧氏距离。该模型给出了一个阈值d0（d0是常数，数值取决于使用环境）。当发送节点与接收节点距离小于d0时，发送方发送数据的能量损耗与距离的平方成正比（ε=2），此时能耗模型对应的是自由空间模型；当发送节点与接收节点距离大于d0时，发送方发送数据的能量损耗与距离的四次方成正比（ε=4），此时能耗模型对应的是多路衰减模型。

2 NDGP

NDGP协议按轮运行，每轮由簇生成、簇间多跳路由建立和数据收集三个阶段构成。

在簇生成阶段网络完成簇首节点集、本轮簇内活跃普通节点集和休眠节点集的确定，簇生成之后簇首为簇内活跃成员创建TDMA调度[9]，并把调度方案广播给簇内活跃成员，完成簇内数据的收集。

簇间多跳路由建立阶段生成以基站为根，簇首为节点的链状多跳路由，使得数据在各簇首节点之间以多跳方式传输至基站。

数据收集阶段，网络各节点转换至自己的状态（簇首、活跃节点、休眠节点），各个簇首按照分配好的TDMA调度收集簇内成员节点的数据，融合数据并在既定的时隙将融合数据发送至它的父簇首节点，此阶段持续至本轮结束。为了保证网络的有效工作时间，算法需要网络运行在数据收集阶段时间大大超过其它两个阶段的运行时间。

2.1 簇生成阶段

2.1.1 最优簇半径计算

在无线传感器网络中，簇首节点的数量是衡量一个分簇算法优劣的标准之一[10]。簇半径 RC决定着网络中簇的数量，直接影响整个系统的能耗。根据文献[1]的最优簇半径计算思想，当基站位于监控区域几何中心时，簇首与基站间距离的数学期望值为因此对文献[1]的式(16)进行修改后，可获得网络采集一次数据并传输至基站的总能耗

本文研究了网络节点数80至250变化范围，网络覆盖率大于 90%，此时计算获得使 Etotal为最小的RC分布在62至68之间。为了保证网络较大的覆盖率，且尽可能减少网络能量消耗，本文折中取值RC=65。

2.1.2 簇内活跃节点数计算

无线传感器网络中，传感节点密集部署常常带来网络的冗余以及无线信道干扰等问题。本协议在保证网络覆盖率要求的前提下，采用簇内调度减少工作节点数目的方法，合理利用节点能量，使无线传感器网络的各种资源得到优化分配。

假设在监测区域Area（其面积为A= π RC2）中，布置1个感知半径为RS的传感节点N，可知N的覆盖面积为SN= π RS2，则节点N能监测整个区域Area的概率为PN=(RS/RC)2，Area中任意一点不被节点 N监测到的概率为=1－(RS/RC)2。

在Area中随机且均匀布置k个感知半径为RS的传感节点，则 Area中任意一点不被任何节点监测到的概率为：=（1－(RS/RC)2）k。

以簇首节点为圆心，簇半径 RC为半径的圆形区域中，如果节点的感知半径为RS，则簇内保证以η为概率监测整个簇所需的最少活动节点数为：

2.1.3 簇生成阶段描述

NDGP采用基于竞争机制的分布式簇生成算法，簇生成阶段由基站发起，唤起监测区域内的所有节点同步进入簇生成阶段，并由上一轮数据收集阶段获取网络中节点的最大剩余能量值（emax）信息告知各节点。该消息格式

网络中的传感节点根据接收基站发送信号强度rssi，计算并保存自己与基站的距离rssi (i, bs)。然后，每个节点根据自身的剩余能量ecur(i)以及rssi (i, bs)计算发送竞争簇首的延迟时间tdelay(i)

为了保证最大剩余能量有更大的机率竞争上簇首位置，σ取值[0.9,1]，为了避免两个距离小于 RC的等能量节点在簇首竞争时发生冲突，在tdelay(i)表达式中引入rand (i)微扰动信号。为了避免距离基站过近的节点成为簇首节点，在 tdelay(i)中引入因子

网络中节点i在0至tdelay(i)时间段内不断接收其它节点申明自己为簇首节点的簇首广播消息（CH_msg），消息格式

若延迟 tdelay(i)时间到达，判断没有接收到任何CH_msg，则立即向半径为RC的范围内发送CH_msg，申明自己为簇首。若延迟时间tdelay(i)到达，节点i接收到几帧CH_msg，则选择离基站最近的CH_msg作为自己的簇首节点，并发送Join_CH_msg，消息格式

由tdelay(i)的计算式可知，不等式tdelay(i)＜t0成立，因此在基站发出同步信号后的t0时刻，监测区域Area内的传感节点要么成为簇首节点，要么成为普通节点。此时各簇首根据式(4)计算kmin，并根据簇内成员的 ecur，选择本轮数据采集阶段的活跃节点，并为它们分配通信时隙。

综上所述，可得算法如下：

簇生成阶段后，各簇首通知各成员节点进入休眠状态，在簇间多跳路由建立期间，普通成员不需要参加，只需要簇首成员和基站参与即可。

2.2 簇间多跳路由建立阶段

基站自簇生成阶段发送的同步信号后t0+1时刻，开始向半径为RC的范围内广播建立多跳路由广播消息 FS_msg（FatherSon_message，寻找父子关系消息）。该消息格式

2.3 数据收集阶段

簇间多跳路由建立自基站发送FS_msg同步信号后在 pt1时间内完成，此时基站将数据收集阶段开始的同步信号发至网络中的所有节点。普通活跃节点苏醒并根据簇内TDMA调度时隙将监测数据发至簇首节点，簇首节点将收到的簇内数据融合处理后连同本簇首节点采集的数据转发至其父簇首节点，网络中的普通休眠节点继续休眠保存能量，直到本阶段结束。

3 仿真实验

利用Matlab编写模拟程序，将NGDP协议与文献[1]中的DEEC-MR协议和文献[4]中的LEACH协议进行仿真并比较。网络环境的配置参数如表1所示。在网络实验中，考虑两种网络寿命的定义：第一个节点死亡和最后一个节点死亡的时间，当节点剩余能量小于0.002J时，认为该节点死亡。实验中模拟了节点数量变化对协议性能的影响。

表1 仿真实验参数

3.1 网络拓扑

图1是网络节点数为600时，NDGP协议生成的网络拓扑结构图，可以看出本协议生成的簇分布均匀，簇首可以经过多跳链接至基站。

3.2 能耗比较

本文对比了不同算法采集一次数据并传输至基站的能耗随网络节点数的变化情况。图2是几种算法在不同网络节点数下的能耗对比图，该曲线情况反映了网络数据收集的效率。由图2可看出，LEACH协议的能耗最高，其原因是该协议将数据从簇首传送至基站采用单跳方式。NDGP协议相比DEEC-MR协议，当网络节点数越大，NDGP的效率比协议DEEC-MR运行效率更好，原因是NDGP协议中保存冗余节点能量的机制比DEEC-MR要好。

图1 网络拓扑结构图

图2 能耗对比图

3.3 网络寿命比较

仿真研究当监控区域的节点数量增加时，网络寿命的变化情况见图3和图4。无线传感器网络协议的性能常常以首个节点死亡时间为主要依据，首个节点死亡出现得越晚，死亡时间越集中，则协议的性能越好。LEACH协议根据概率选择簇首的算法使得簇覆盖面随着节点密度的增加而减小，这种办法无法有效利用簇首的数据融合优势，因此LEACH协议的网络寿命并没有随着网络节点数量的增加而明显提高。NDGP协议中节点开始死亡的时间晚于DEEC-MR协议，死亡时间的集中程度NDGP协议在节点密度高的场合略优于 DEEC-MR协议，但两者均大大优于LEACH协议。NDGP协议运行总轮数比DEEC-MR、LEACH协议多，其主要原因是：1）NDGP协议在簇首多跳建立阶段有防止孤立簇的机制，这有利于避免因多跳路由引起的能量空洞而造成网络运行中止的现象；2) 在保证用户覆盖率的前提下，NDGP协议有令网络内冗余节点进入休眠状态的机制，从而有效地延长了网络寿命，并且该机制在网络节点密度大的场合优势更加明显。

图3 节点数与网络寿命（第一个节点死亡）

图4 节点数与网络寿命（最后一个节点死亡）

4 结论

本文针对大规模无线传感器网络中收集数据的需要，提出一种新的高能效数据收集协议—NDGP。该协议在簇的生成阶段可保证高剩余能量的节点成为簇首节点，采用微扰动的办法解决了竞争簇首时通信堵塞的问题，成功实现均匀分簇。NDGP协议通过簇首节点执行

数据融合和数据收集阶段冗余节点进入休眠状态等机制，从而有效地节省网络的能耗。仿真结果表明：与LEACH协议和DEEC-MR协议相比较，NDGP具有更好的运行效率和更长的网络寿命，更适合于高密度、大规模无线传感器网络的应用。然而，在节点均匀分布的网络运行后期，由于靠近基站的簇首节点承担了更重的数据转发任务，导致这些簇首节点会先行死亡。因此，NDGP也不可避免地存在监控网络能量空洞的问题。

[1] 史久根,胡小博.高效节能的无线传感器网络数据收集协议[J].电子测量与仪器学报,2012,26(5)： 437-444.

[2] 杜冬梅,张志,何青,等.无线传感器网络节能技术分析[J].仪器仪表学报,2006,27(6)：366-367.

[3] 刘铁流,巫咏群.基于能量优化的无线传感器网络分簇路由算法研究[J].传感技术学报,2010,24(5)：764-769.

[4] Heinzelman W R, Chandrakasan A, Balakrishnan H.Energy-efficient communication protocol for wireless micro-sensor networks[C]. 33rdAnnual Hawaii International Conference on System Sciences, Hawaii, 2000： 1-10.

[5] Lindsey S，Raghavendra C．Pegasis： Power-efficient gathering in sensor information systems[J]．IEEE Transactions on Parallel and Distributed Systems, 2002,13(9)：924-932.

[6] Tan H O,Korpeoglu I. Power efficient data gathering and aggregation in wireless sensor networks[J]. ACM SIGMOD Record, 2003,32(4)：66-71.

[7] 蒋畅江,石为人,唐贤伦,等. 能量均衡的无线传感器网络非均匀分簇路由协议[J].软件学报, 2012, 23(5)： 1223-1232.

[8] Xiang M, Shi WR, Jiang CJ, et al. Energy efficient clustering algorithm for maximizing lifetime of wireless sensor networks.AEU-Int’l Journal of Electronic and Communication, 2010,64(4)：289-298.

[9] 龚海刚,刘明,余昌远,等.无线传感器网络环境下基于事件驱动应用的节能 TDMA 协议[J].电子学报,2007,35(10)：1843-1848.

[10] 郭士琪.无线传感器网络分簇算法研究综述[J].经营管理者,2012(9)：367-367.

[11] Zhixin Liu, Qingchao Zheng, Liang Xue, et al. A distributed energy-efficient clustering algorithm with improved coverage in wireless sensor networks[J]. Future Generation Computer Systems, 2012,28(5)：780-790.