新颖的冗余节点无线传感网能量感知分簇算法*

郑莹，裴芳，董龙明

（1.常德职业技术学院，湖南常德415000；2.湖南机电职业技术学院，长沙410073；3.陆军驻南京地区军事代表室，南京210000）

新颖的冗余节点无线传感网能量感知分簇算法*

郑莹1，裴芳2，董龙明3

（1.常德职业技术学院，湖南常德415000；2.湖南机电职业技术学院，长沙410073；3.陆军驻南京地区军事代表室，南京210000）

针对一类具有冗余节点的无线传感网，提出了一种新颖的能量感知的动态分簇算法NEAC。它基于动态分簇路由机制，根据节点分布密集程度簇内分布一定数量的休眠节点，在数据传输阶段，这些休眠节点不感知和发送数据，当簇首节点的能量消耗达到一定阈值后需要重新轮换簇首，它们被唤醒并根据休眠节点和簇首轮换机制实现快速簇首和休眠节点选举以平衡节点间的能耗。仿真结果表明，与典型的分簇协议相比，NEAC能够更好地平衡节点的能耗，获得更长的网络生存期。

节点冗余，无线传感网，分簇算法，能量感知

0 引言

无线传感网（WSN，wireless sensor network）是由分布在监测区域内的能够采集环境数据、简单数据处理和无线通信的大量传感器节点通过无线通信协议构成的无线多跳ad hoc网络［1］。WSN能够在宽阔恶劣的条件下，实时收集大量详实可靠的一手数据，被广泛应用于工业控制、环境监测、交通管理、国防军事等领域。与传统网络相比，WSN中的节点能够协作地感知、采集、汇总和处理监测区域的各种信息，WSN通常分布密集，节点数量能达到几百至上千，传感器节点体积小，采用电池供电，限制了节点的处理和通信能力。因此，如何高效平衡地使用节点的能量，最大化网络生命期是无线传感网面临的主要挑战，如何设计合理的无线传感网数据收集协议综合平衡节点的能耗，是衡量无线传感网性能的重要因素。

无线传感网在数据收集选择传输路由算法时，通常可采用分簇路由［2］、树型结构路由［3］和链型结构路由［4］。分簇路由具有拓扑管理方便、能量利用高效、数据融合简单的优点。在分簇的数据收集协议中，网络中的节点通常根据某种规则被划归为簇首节点和成员节点。簇首节点管理簇内部成员节点，负责簇内成员节点的数据收集融合处理以及簇间数据转发。簇首节点承担着主要的无线传感网的任务，其失效往往影响整个簇的失效，虽然设计时可以赋予簇首节点高能量，但随着时间的推移，簇首节点由于故障或能量急剧消耗从而导致整个簇失效。如何动态调整簇的规模选择合适的簇首节点成为基于分簇的数据收集协议研究的热点和难点。

国内外研究学者针对分簇的无线传感网数据收集协议相继提出了多种典型的数据收集协议，如：LEACH算法［5］、PEGASID［6］、PEDAP协议［7］。LEACH算法随机选取簇首，成员节点的数据汇聚到簇首节点后发送给基站，减少了与基站直接通信节点数据，协议在每轮随机重新选择簇首，理论上能够将能量消耗均匀地分布在所有节点上，但是，算法很难保证簇首节点在网络中的均匀分布。PEGASID协议根据节点的地理位置形成一条相邻节点间距离最短的链，节点间的通信仅限于相邻节点，可以有效地减少通信距离所消耗的能量，PEDAP协议在PEGASID协议进一步优化，将节点构造一棵最小汇集树，但是需要维护网络全局信息，尤其是节点意外失效时，需要重新广播全局信息。

本文针对一类具有大量冗余节点的无线传感网络，尤其是聚集在一起的节点同时感知同一个区域，不仅产生大量的冗余数据而且还增加了网络的通信负载，并且消耗了节点的能量。通过增加大量冗余节点延迟无线传感网生命周期在当前分簇路由协议中没有产生效果的问题。本文提出了一种新颖的冗余节点无线传感网能量感知分簇算法（NEAC），它基于动态分簇调整机制，根据节点分布密集程度休眠一定数量的节点节约能量，在数据传输阶段，这些休眠节点不感知和发送数据，当簇首节点的能量消耗达到一定阈值后重新轮换簇首和休眠节点，以达到平衡簇内节点能量的消耗，延长网络生命期。

1 NEAC算法描述

本节首先给出NEAC算法的一些假设条件，然后提出节点调整机制，最后介绍NEAC算法的基本原理。

1.1假设条件

NEAC算法针对一类具有大量冗余节点的无线传感网，因此，节点除了大量随机分布在一个方形区域内，并且具有下面的性质：

①唯一的基站部署在无线网外部较远的距离；

②每个节点具有唯一的标识ID，同质，初始时具有相同的能量；

③传感器节点部署后不再移动，且都知道自己的位置，基站BS知道节点的位置信息；

④链路是对称的，两个节点使用相同的能耗水平进行通信；

⑤可根据节点距离的不同调节发射节点的功率，采用文献［7］的能量模型。

能量衰减模型随发送距离的远近分为自由空间模型和多路衰减模型：当发送距离在一定阈值d0（d0为常量）内，发送数据的功耗和距离的平方成正比；当发送距离大于d0时，功耗和距离的四次方成正比，当节点向距离d以外的另一个节点发送k个字节的数据时，其所消耗的能量由式（1）计算：

其中，Eelec表示收发电路所消耗的能量，Eamp表示信号放大器消耗的能量。

节点接受数据所消耗的能量由式（2）计算得到。

网络中存在大量随机分布的传感器节点，有些区域聚集着大量的无线传感器节点，如果同时检测同一区域，会造成能量的浪费而且产生大量冗余的数据，占用有限的网络带宽。本文设置休眠半径r和分布密度ρ两个参数控制部分聚集的节点休眠状态以节约节点的能量。

休眠半径r：节点n的休眠半径为r，是指在节点n覆盖半径为r的区域内，其他节点处于休眠状态，不采集也不发送数据。

休眠节点nd：位于休眠区域内的节点。

分布密度ρ：是指在节点n的休眠半径r内分布的节点数目。

如下页图1所示，节点n的休眠半径为r，位于休眠区域内的节点为休眠节点，节点n的分布密度为：5，休眠节点既不采集数据也不向簇头发送数据。所有节点（除基站外）均为同质，假设所有节点的休眠半径相同。休眠半径的大小和分布密度设定可以由网络的应用特点和节点采集特性决定。当休眠半径内分布的节点达到一定分布密度时节点才处于休眠状态。

图1 带有休眠节点的无线传感网分布图

1.2节点分簇

在系统初始化时，NEAC算法将传感网络中所有节点按照区域划分成多个簇，各节点在簇内广播节点的位置和标识信息，然后各节点接收到其他节点广播的消息，得到在休眠半径r内节点的分布密度ρ（如果计算节点跨簇，则忽略）。

簇首节点采用簇间转发方式经过打包压缩拆分等手段汇聚后根据簇间的路由表逐级传输至基站。算法每个簇首节点需要维护两类信息：基本信息和簇间的路由信息。

对任意节点Ni，基本信息包括节点ID、簇首节点ID、剩余能量、休眠节点集合ND，可以用四元组表示：＜Node_ID，CH_ID，Res_Engergy，ND＞

节点ID是统一编码，CH_ID表示簇首节点的ID，可以用来代表整个簇，节点通过CH_ID就可以在簇内将感知到的数据传递给该簇首。剩余能量则是记录节点当前剩余的能量。ND描述了该节点休眠节点的集合，其集合元素个数为该节点的分布密度ρ。

簇间路由信息维护与本簇相邻接监控区域的簇首节点信息，可以用2个队列表示：转发队列TransferQueue和区域邻接队列NeighAreaQueue。这2个队列在系统初始化时构建，转发队列记录了该簇首节点可以将数据转发下一个簇首ID，区域队列记录了与该簇地理相邻的簇首ID，用来动态调整簇的大小。转发队列在传感网节点分簇确定簇首节点后构建，由基站广播一则消息，通过与基站距离的远近构建一条通往基站的链路，为了增强传感网的容错性，通往基站的链路可能不止一路，簇首可以选择多个簇间首节点转发数据传递给基站。

1.3簇首选举及数据转发

簇内簇首选择根据节点关于休眠半径的分布密度大小选择合适的节点作为节点，原则上选择剩余能量和分布密度最大的节点作为簇首节点，可以通过计算公式w=w1*Res_Energy+w2*ρ（w1+w2=1， 0＜w1，w2，＜1）求得w最大值作为簇首节点，当有多个w最大值时可以随机选择某个节点作为簇首节点。分布密度大说明在簇首能量不足时需要更换簇首节点时，可供选取替换的相邻节点多。

在NEAC算法中，簇首节点的数据经过转发队列中的簇首节点转发，最后将数据转发到基站。图2完整地描述了NEAC算法中数据收集并传输到基站的过程。首先，各簇内节点将数据分布汇聚到簇首节点CHi、CHj和CHm中。CHi和CHj、CHj和CHm构成了区域邻接队列，CHj为簇首节点CHi的转发队列，CHm为簇首节点CHj的转发队列。因此，簇首节点CHi将数据由簇内数据汇聚后传递给簇首节点CHj，然后簇首节点CHj将接收到数据和簇内收集的数据汇总打包一并传输给簇首节点CHm，最后，簇首节点CHm将汇总后的数据传输给基站。

图2 簇首节点数据传输路径

1.4簇首动态调整策略

当无线传感网运行一点阶段后，由于簇首节点承担着大量的数据汇总和传输任务，造成能量急剧消耗，当能量消耗至某个极限值时不再具备簇首节点和转发数据的资格。在这种情况下，NEAC算法设置簇首动态调整策略：首先在当前簇首节点的休眠节点集合ND选择能量最高的节点被唤醒作为该簇新的簇首节点，如果休眠集合中节点能量均低于该能量极限值，则需要在簇内重新选取能量高的和分布半径较大的节点作为新的簇首，最大限度地延迟无线传感网的生命周期。该算法伪代码描述如下：

2 性能分析

2.1参数设置

本文采用基于Java的DTN仿真工具ONE（Opportunistic Network Environment）［8］进行仿真实验。为了验证本文协议的有效性，分别对LEACH［2］、MTP［5］和NEAC 3种协议分布从能耗和网络生存周期进行对比。实验中各项参数设置如表1所示。每次轮巡节点是否发送数据包是随机的，模拟真实传感网环境的数据收集，网络中随机分布大量冗余的无线传感网节点。

表1 实验参数列表

2.2实验结果及分析

无线传感网络生命期主要关心网络中第1个节点的死亡时间和最后一个节点的死亡时间，为了比较3种算法的优劣，同时关心网络中第1个节点死亡时间和最后一个节点死亡时间，仿真结束时间定义在最后一个节点死亡时间，完整的网络生命期仿真结果如图3所示。这次选取网络中节点个数为300。

图3 网络生命周期仿真结果

网络能量的均衡性主要考虑网络运行中每轮网络能量的消耗情况，图4显示了网络能量消耗的仿真结果。

从图4中可以看出，NEAC算法的能量消耗曲线比LEACH和MTP更加平滑，这说明NEAC算法的能量均衡性比LEACH和MTP要优良，同时，NEAC的曲线总是位于LEACH和MTP的下方，因为NEAC算法在每轮中总有节点处于休眠状态，这样能够节约能量，延长网络的使用寿命。

3 结论

本文提出了一种针对一类存在大量冗余节点的无线传感网能量感知分簇算法（NEAC）。该算法针对无线传感网中冗余节点，有选择性地选择聚集密集的节点设置为休眠状态以节约节点的能量和节约网络传输带宽，仿真实验结果表示该算法能够有效地降低节点的能耗和延长网络生命周期。簇首节点的选取和簇间路由的优化能够提高无线传感网的数据采集和数据传输效率，如何设计更加智能合理的簇间路由策略，使其在能耗、网络生存期和数据传输延迟等方面具有较优的性能是下一步研究的重点和方向。

［1］VIDYASAGAR P，ATIF S，ELIZABETH C.Wireless sensor networks：a survey［C］//International Conference on Advanced Information Networking and Applications Workshops. Bradford，United Kingdom，2009：636-641.

［2］郑相全.无线自组网技术实用教程［M］.北京：清华大学出版社，2004.

［3］CALLAWAY E H.无线传感器网络［M］.马伟明，王永斌，译.北京：电子工业出版社，2007.

［4］DU K，WU J，ZHOU D.Chain-based protocols for data broadcasting and gathering in the sensor networks［C］//In：Proc.of the International Parallel and Distributed ProcessingSymposium，2003.

［5］HEINZELMANWR，KULIKJ，BALAKRISHNANH. Adaptive protocols for information dissemination in wireless sensor networks［C］//Proceeding of the 5th Annual International Conference on Mobile Computing and Networking. New York：ACM Press，2001：174-185.

［6］LINDSEY S，RAGHAVENDRA C S.Pegasis：Power-effi

cient gathering in sensor information systems［C］//Proceeding of IEEE Aerospace Conference 2002.Los Alamitos，CA： IEEE Computer Society Press，2002：1-6.

［7］HEINZELMAN W B，CHANDRAKASAN A P，BALAKRISHNAN H.An application-specific protocol architecture for wireless microsensor networks［C］//IEEE Transactions on Wireless Communications，2002，1：660-670.

［8］KERANEN A，OTT J，KARKKAINEN T.The ONE simulator for DTN protocol evaluation［C］//SIMUTools’09：Proceedings of the 2nd International Conference on Simulation Tools and Techniques，New York，NY，USA，2009.

Novel Energy-Aware Clustering Algorithm for WSN with Redundant Nodes

ZHENG Ying1，PEI Fang2，DONG Long-ming3
（1.Changde Vocational Technical College，Changde 415000，China；2.Hunan Mechanical and Electrical Polytechnic，Changsha 410073，China；3.Nanjing Military Representative Office of PLA Army，Nanjing 210000，China）

This paper proposes a novel energy-aware clustering algorithm for wireless sensor network with redundant nodes，called NEAC.It is based on clustering routing mechanism and distributes certain number of dormant nodes according to the intensive distribution of cluster nodes. These dormant nodes do not perceive and send any data during data transmission phase.When the energy consumption of cluster head nodes reaches a certain threshold and needs to be replaced，those dormant nodes around the cluster heads are waken up and then cluster head nodes and dormant nodes are rapidly elected again according to the cluster head rotating mechanism，which can balance energy consumption of WSN.Simulation results show that compared with typical clustering protocols，NEAC can balance the energy consumption of nodes better，and thus increase the lifetime of WSN.

redundant nodes，wireless sensor network，clustering algorithm，energy-aware

TP393.02

A

1002-0640（2016）11-0104-04

2015-10-09

2015-11-17

湖南省教育厅课题（13C258）；湖南省常德市科技局基金资助项目（2014JF11）

郑莹（1977-），女，湖南常德人，副教授。研究方向：网络安全、无线传感网。