基于区域分簇的大规模无线传感器网络生命周期优化策略

摘要：针对环境监测、电网冰灾监测等大规模监测系统中监测区域覆盖广、传感器数量大等特性，为节约网络能耗以延长生命周期，提出了一种基于区域分簇的大规模无线传感器网络生命周期优化策略（RCS）。该策略首先利用传感器节点的位置信息进行凝聚的层次聚类（AGNES）算法将大规模网络分区以优化簇首的分布；其次，候选簇首节点竞选簇首成功后进行不均匀分簇，同时加入时间阈值来均衡簇首节点的能耗；最后，采用簇间多跳路由，根据节点剩余能量、与汇聚点距离计算网络能耗代价来构建最小生成树进行路由选择。在仿真实验中，该策略与经典的低功耗自适应分簇（LEACH）协议和能量高效的非均匀分簇（EEUC）算法比较，簇首能耗平均分别减少了45.1%和2.4%，网络生命周期分别延长了38%和3.7%。实验结果表明，RCS在大规模网络中能有效均衡整体网络能耗，显著延长了网络的生命周期。

关键词：无线传感器网络；分区；非均匀分簇；最小生成树；生命周期

中图分类号： TP393

文献标志码：A

0引言

近年来，物联网因其巨大的应用前景已成为各国政府、学术界和工业界极度重视的研究热点。无线传感器网络（Wireless Sensor Network， WSN）是由部署在监测区域内大量传感器节点相互通信形成的多跳自组织网络，是物联网底层网络的重要技术形式。目前大规模无线感知网络在军事、智能交通、环境监测、地震冰灾和现代农业等领域的应用需求非常迫切[1]，而如何有效解决能耗问题[2]，提高网络生命周期一直是其核心研究问题[3]。

现有的物联网中无线感知网络的规模一般都较小，节点数目大多在几十到几百个。而在大规模的监测系统应用背景下，为获取精准的监测数据，通常需在监测范围内布置大量的传感器节点来采集数据，呈现出分布范围广、规模大、数量多且密度不均匀等特征。另外，若大量传感器节点将感知到的数据经过多跳传输到汇聚中心会加快汇聚点周围节点的能量消耗，即产生能量空洞问题[4]，从而缩短了网络生命周期。

针对大规模传感器网络中节点数量多且分布不均匀的情况，提出一种基于区域分簇的大规模无线传感器网络生命周期优化策略（Regional Clusterbased lifetime optimization Strategy， RCS），该策略将大规模网络划分成区以均衡簇首分布，各区彼此独立，区内并行采用不均匀分簇以缓解能量空洞问题；簇间通信时构建基于网络能量代价的最小生成树，合理有效地进行多跳路由。实验结果表明，该算法能有效提高网络运行效率，均衡网络能量消耗，延长网络生存周期。

1相关工作

在无线传感器网络体系结构中，基于分簇的层次式路由具有拓扑管理方便、能量利用高效、数据融合简单等优点[5]。经典的低功耗自适应集簇分层协议（Low Energy Adaptive Clustering Hierarchy， LEACH）[6]随机选举簇首，并以单跳方式让簇首与汇聚点直接通信。基于簇首距汇聚点距离较远，又传感器节点通常由电池供电而受能量约束，研究表明，簇首与汇聚点通信时采用多跳路由更有利于节约能量[7]。Younis等[8]提出的混合式分簇（Hybrid EnergyEfficient Distributed clustering， HEED）协议先根据节点的剩余能量选取簇首，然后以簇内部通信代价的高低竞争选出最终簇首，由于需要在簇半径内进行多次消息迭代，其通信开销也比较显著。文献[9]首次提出利用非均匀分簇解决能量空洞，但其考虑的是一个异构网络，簇首为超级节点，且事先计算好节点部署位置，无动态构造簇的操作。文献[10]提出的聚类方案（EnergyEfficient Clustering Scheme， EECS）中，通过考虑候选簇首到汇聚点的距离远近构造不均匀的簇来均衡簇首负载，但其只是在局部比较节点剩余能量，没有从整体协调节点能耗，并且簇间通信同样采用单跳通信，限制了算法的扩展性，不适合在大规模网络中使用。

Li等在文献[11]中提出了一种将非均匀分簇与簇间多跳路由有机结合的路由协议（EnergyEfficient Uneven Clustering， EEUC），利用非均匀竞争半径使得靠近基站的簇的成员数目相对较小，从而簇首能节约能量以供簇间数据转发使用，均衡网络中所有节点的能量消耗。文献[12]中继承非均匀分簇结构，并在此基础上结合蚁群算法进行路由优化，引入链路可靠性和实时性参数进行多路径搜索，更新信息素并设计下一跳概率公式，但是这样的策略易陷入局部最优。文献[13]则针对网络中耗能不均问题提出一种基于马尔可夫博弈的能量均衡路由算法，定义了能量和信誉值的二元收益函数，给出节点转发的状态转移概率，并根据收益函数进行能量调节，求解出能量和收益之间的均衡系数，促进节点间的合作，实现节点能量的均衡消耗。另外，随着传感器网络应用的拓展，网络服务质量（Quality of Service， QoS）路由算法也成为研究的热点之一[14]。

上述优化无线传感器网络生命周期的方法主要可以归纳为：1）现有的算法在感知节点庞大的情况下，因网络内每个节点需参与簇首竞争进行比较，整个网络消息量会因此骤增，效率不高。2）节点竞选簇首时考虑其剩余能量虽有利于均衡网络能耗，但在节点分布密集程度不同时可能当选的簇首不理想，不能均衡节点能耗。

因此，本文提出的基于区域分簇的大规模无线传感器网络生命周期优化策略RCS是在传感器节点数量庞大、分布不均的情况下先划分网络进行局部并行分簇，不仅减少通信量，提高运行效率，也能均衡簇首分布。采用不均匀分簇，并设置时间阈值控制簇首竞争的比例，提高竞争效率。在簇间通信时综合考虑簇首节点之间的通信能耗、剩余能量和与Sink的距离来构建基于网络能量代价的最小生成树进行多跳路由，均衡簇首能耗，从而有效延长网络生命周期。

2大规模传感器网络的区域划分策略

2.1网络模型及假设

考虑在一个矩形监测区域内随机部署n个传感器，周期性监测周围环境进行数据采集，汇聚点Sink位于区域中心。假设此时网络能覆盖全部监测区域。si表示第i个传感器节点，则节点集合为S={si1≤i≤n}。有以下假设：

1）所有节点都是同构的，且都有唯一的ID；

2）节点部署后均不会发生位置移动，可通过某种定位算法获知自身的地理位置；

3）链路对称，若已知对方发射功率，可根据接收信号强度指示（Received Signal Strength Indication， RSSI）计算其到发送者的近似距离；

4）根据接收者的距离远近，节点可以自由调整其发射功率以节约能量消耗。

2.2能耗模型

无线传感器网络中节点的能耗来源主要有数据的采集、融合与传输，其中数据传输所消耗的能量远远大于其他部分的能耗[16]。因此，本文主要考虑网络中数据传输能耗，采用典型的无线通信能量耗费模型，见式（1）。节点发送l比特的数据到距离为d的位置，其能耗为：

ETx（l，d）=

lEelec+lεfsd2，d

lEelec+lεmpd4，d≥d0 （1）

其中，Eelec表示发射电路损耗的能量。若传输距离小于阈值d0，功率放大损耗采用自由空间模型；若传输距离大于等于阈值d0时，采用多路径衰减模型。εfs、εmp分别为这两种模型中功率放大所需的能量。同样，节点接收l比特的数据消耗的能量为：

ERx（l）=lEelec（2

此外，用EDA表示融合单位比特数据消耗的能量，即簇首节点进行簇内数据融合的时候，每处理1b的数据需要的能量损耗为EDA。

2.3网络分区

在已有算法的初始阶段，网络中所有节点都要在全局内进行判断是否成为簇首节点，并在簇首选定后以自组织的方式形成簇，这就需要一系列的广播和设置工作。在节点数目庞大且分布不均匀的情况下，由于所有节点都要参与比较，从总体上看，整个系统发送的广播数量非常多。图1给出本文网络分区拓扑示意图，感知节点随机分布在监测区域内，有密集程度区分，Sink节点位于区域中心。

本文采用层次聚类算法先将大规模网络划分为若干子区，各区独立选举簇首和分簇以提高并行效率，减少所有节点的能耗。在网络分区阶段，节点首先将自己的位置信息发送给汇聚点，由汇聚点根据节点间的距离将整个网络划分为多个子区域，规定每个节点只隶属于一个区。划分结束后，由汇聚点向节点广播子区划分的相关信息，最后由各个节点根据这些信息及其位置确定所属的子区。划分好的子区在整个网络生命周期内固定不变，以减少频繁分簇的能量消耗。

由式（1）可知，节点之间数据传输的能耗与距离密切相关，所以分区时采用凝聚的层次聚类方法――AGNES（Agglomerative Nesting）[17]，基于节点间距离对各节点进行聚类划分网络，划分后的各子区内节点分布相对均匀。需要注意的是，这里只考虑距离因素，而对其他可能对网络生命周期也有影响的因素如剩余能量不作考虑，因为节点的剩余能量是实时变化的，这样会导致分区也要动态变化。为防止过度拟合，减少离群点对聚类结果的影响，需设定阈值M（M∈（0，1）），即当被聚类的节点数占总数的比值为M时，聚类停止。这样，将分布相对均匀的节点划分到一个区域里，各区节点只需进行局部通信来竞选簇首，既改善簇首分布不均匀问题，又减少了通信代价。

如图2所示，经过聚类后，图1的整个网络会被划分成3个密集程度不同的子区。在数据传输过程中，子区内的感知节点将数据传给竞选出的簇首再传给汇聚点Sink；而对于子区之外的感知节点，称为离群点，在数据传输过程中，选择距其最近的簇并将数据传输给区内与其最近的节点或是直接传给汇聚节点Sink。

3分布式的区域内分簇策略

从图2中可以看出，监测区域内感知数据需以多跳的方式传送到汇聚点，易导致在汇聚点周围形成能量空洞，进而无法将感知数据送达到汇聚点，严重影响网络寿命[2]。实验结果[18]表明，一个传感器网络生命结束后，总的节点剩余能量超过90%。本文经过上述网络分区后将网络划分为若干个子区，各区彼此独立，而区内依据局部竞争，采用分布式的不均匀分簇策略以缓解能量空洞问题，有助于提高竞选效率，延长网络生命周期。

3.1分簇策略

本文分布式的区域内分簇策略按周期性进行数据采集，每轮包括设置和稳定两个阶段，在设置阶段完成簇首竞选和组簇的工作，数据的收集和融合处理、簇间通信则在稳定阶段进行。在设置阶段开始时，汇聚点Sink广播一条用于网络初始化的消息，节点根据接收到的消息强度计算与 Sink的距离。

3.1.1 竞选簇首

同EEUC[10]中，参与竞选的候选节点都维护一个邻居节点表，见表1，并按一定规则竞争出最终簇首。

表1中，id字段为节点的唯一标识；state字段表示节点状态，为“Candidate”；Eres是邻居节点的剩余能量；dtosk是邻居节点到汇聚点Sink的距离长度。

规则1在竞选过程中，若候选簇首si宣布其竞选获胜，则在si的竞争半径内的所有候选簇首均不能成为最终簇首，需要退出竞选过程。

而候选簇首si的邻居节点集合包括与si具有规则1所约束的竞争关系的所有候选簇首节点，其定义如下：

定义1在RCS簇首竞选算法中，候选簇首si的邻居节点集合si.Neb为：

si.Neb=

{sj|sj是候选簇首，d（si，sj）

每个候选簇首的竞争范围为Rcomp[9]，见式（3）：

[12]MIAO C， CHEN Q， CAO J， et al. Energy balanced uneven clustering algorithm based on ant colony for wireless sensor network[J]. Journal of Computer Applications， 2013， 33（12）： 3410-3414. （缪聪聪 陈庆奎 曹剑炜，等. 基于蚁群的无线传感器网络能量均衡非均匀分簇路由算法[J]. 计算机应用， 2013， 33（12）： 3410-3414.）

[13]DONG R， MA Z， GUO Y， et al. A Markov game theorybased energy balance routing algorithm[J]. Chinese Journal of Computers， 2013， 36（7）：1500-1508. （董荣胜，马争先，郭云川，等. 一种基于马尔可夫博弈的能量均衡路由算法[J]. 计算机学报， 2013， 36（7）：1500-1508.）

[14]KONG Y， YAO J， ZHANG M. QoS multicast routing optimization algorithm in Ad Hoc networks based on MMAS with lifetime estimation[J]. Journal of Chinese Computer Systems， 2015，36（1）：44-48. （孔宇彦，姚金涛，张明武. Ad Hoc网络基于寿命估算MMAS的QoS组播路由优化算法[J]. 小型微型计算机系统，2015，36（1）：44-48.）

[15]ZHAO T， GUO T， YANG W. Energy balancing routing model and its algorithm in wireless sensor networks[J]. Journal of Software， 2009，20（11）：3023-3033.（赵彤，郭田德，杨文国. 无线传感器网络能耗均衡路由模型及算法[J]. 软件学报，2009，20（11）：3023-3033.）

[16]HAN J W， KAMBER M. Data mining： concepts and techniques [M]. 2nd ed. FAN M， MENG X， translated. Beijing： China Machine Press， 2007： 263-266. （HAN J W， KAMBER M. 数据挖掘：概念与技术[M].2版.范明，孟小峰，译.北京： 机械工业出版社，2007： 263-266.）

[17]LIAN J， NAIK K， AGNEW G B. Data capacity improvement of wireless sensor networks using nonuniform sensor distribution[J]. International Journal of Distributed Sensor Networks， 2006， 2（2）： 121-145.

[18]HEINZELMAN W B， CHANDRAKASAN A P， BALAKRISHNAN H. An applicationspecific protocol architecture for wireless microsensor networks[J]. IEEE Transactions on Wireless Communications， 2002， 1（4）：660-670.