无线传感器网络簇首备份机制研究

蒋青云

(湖南省妇幼保健院信息中心，湖南 长沙 410008)

0 引言

基于不同的应用目的和应用需求，诸多学者已经研究出了多种分簇策略[1-2]，提出了多种有效的分簇算法[3]。然而，在分簇式无线传感器网络中，簇首节点[4]既需担当收集和转发本簇内各普通节点数据的任务，又需对其它离汇聚节点更远的簇首节点所收集的数据进行转发，这可能导致簇首节点因过快消耗能量而死亡。并且，簇首节点本身可能因硬件或软件故障而影响当前的通信状态或行为，例如传感器节点的内存、收发器、寄存器、通信链路及控制程序等故障。无论是簇首节点因能量消耗过多死、过早死亡还是因突发性故障导致节点崩溃，都将导致该簇不能完成数据收集与传输任务[5]，影响了网络的寿命。因此，有必要对簇首节点进行维护，以延长网络的生命周期。

1 簇首备份机制概述

1.1 簇首备份的基本概念

图1 簇首备份与备份簇首转为簇首的过程示意图

扼要地说，簇首备份[6]就是指在分簇形成后，根据某种规则选取出除原簇首外的一个或多个备份簇首，以备原簇首在能量过快消耗或出现故障时能主动承担起该分簇的“领导者”任务。图1给出了簇首备份与备份簇首转为新的簇首的示意图[7]，图中BS表示基站(汇聚节点)，序号为4、8、20的节点分别为簇C1、C2、C3 的簇首节点，序号为 22、19、1 的节点分别为簇C1、C2、C3的备份簇首节点(一个备份簇首节点的情形)，其余的为普通节点。图1中的左图表示簇首未出现故障时的情形，在簇C3中的簇首节点20出现故障后，该分簇内的备份簇首节点1转为新的簇首(如图1中的右图所示)，分簇内各普通节点在新簇首的“领导”下继续工作。

一般情形下，簇首节点承担着相对普通节点更多的数据处理和传输任务[8]，其能量消耗相对较快，故障发生的可能性也相对更大。显然易见，尽管簇首节点突发死亡，但簇内其它普通节点仍能继续进行数据采集，簇的寿命并没有真正结束。采用簇首备份机制可有效地解决因簇首过早死亡而出现的分簇或整个网络的假死亡现象。簇首备份的优势[9]可概括为如下几点:

(1)可有效延长分簇的生命周期;

(2)可提高无线传感器网络的稳定性和整体性能;

(3)能较大幅度地减少因簇首节点出现故障而产生的损失。

1.2 典型的簇首备份机制

簇首备份机制的关键是备份策略，即根据何种规则来选取合适的备份簇首，使网络的整体性能达到最优。根据不同的网络状况和用户需求，典型的簇首备份[10]选取策略主要有考虑覆盖面积[11]的选取法和基于节点度数[12]的选取法。

(1)考虑覆盖面积的选取法。

这里所提到的覆盖面积是指备份簇首的无线电信号所能覆盖到原簇首的通信面积。如图2所示，图中实心节点和虚线圆周分别表示原簇首及其覆盖范围，空心节点和实线圆周表示备份簇首及其覆盖范围，原簇首覆盖范围与备份簇首覆盖范围的公共部分即为备份簇首的覆盖面积，当原簇首出现故障时，备份簇首可保证覆盖面积对应区域中的节点正常通信。

图2 备份簇首的覆盖面积示意图

对于无线传感器网络，因其拓扑结构保持不变，成员节点与簇首之间的距离a也是确定的。这种考虑覆盖面积的选取策略事实上是从通信距离的角度考虑了各成员节点竞争备份簇首的能力。这种考虑覆盖面积的备份簇首选取策略的主要优势是:在整个选取过程中簇首只需根据节点信号的强弱估计对应的节点间距，进而估计出节点的覆盖能力，无需额外的消息传送开销。但这种策略[12]只适合于节点密度较高、分布均匀的情况，当假设不成立时，可能对整体的性能产生较大的影响。

(2)基于节点度数的选取法。

众所周知，由于无线电传输无方向性，所以节点可以通过在自己的接收范围内监听周围信号来确定邻居节点数[13]。如图3所示，当节点A与节点B进行数据通信时，在节点A的通信范围内的节点C、D均可通过监听信号的办法来确定自己与A的邻居关系，对网络中的其它节点也是如此。

图3 节点确定邻居关系的示意图

根据发现网络中邻居节点的思想，可设计如下的备份簇首选取策略:

Step1 簇内各节点通过监听的方法得到自己的邻居关系，设节点的度数为Dn;

Step2 簇内各节点将自己邻居数上报给本簇的簇首，得到最大簇娄TD;

Step3 簇首根据收到的各个节点的节点度数，选取度数最大的节点，若Dn＜TD，则不进行簇首备份，否则以该节点备份簇首进行备份。

对于无线传感器网络，在大多情形下，节点部署后不再移动，因此各节点的邻居关系是在部署后就已经确定了的。这种基于节点度数的选取法考察了节点的邻居数目，从通信距离看，发现的邻居节点数，从一定程度上反映出能与该节点进行直接通信的成员节点数的多少。这种选取策略的主要技术优势是:对成员节点没有特定的要求，且能适应网络的拓扑变化情形，实现起来非常简单，但是，各个成员节点在发现邻居与上报自身的节点度数时需要发送大量的控制消息，需要一定的额外开销，且随节点数目的增多而递增，因此这种策略通常只适用于节点密度较低的场合。

2 基于综合指标的簇首备份机制

本文在研究上述两种机制的基础上，提出一种基于综合指标的无线传感器网络簇首备份机制。对于分簇式无线传感器网络，其数据收集任务[14]的完成与分簇的生命有着紧密的联系。簇首备份是一种很好的延长分簇生命周期，提升网络整体的性能的方法。

在无线传感器网络中，设分簇j内第i个节点xi的节点度数为Degree(xi)(按上文提到的节点度数选取的方法确定)，其剩余能量为Eresidual(xi)，综合指标Syn_Indexj(xi)的计算公式[15]:

式中，φ1、φ2为权重因子，λ1、λ2、λ3为大于等于 0 的系数，其值根据具体场景和应用来确定，分别用来衡量节点的剩余能量、度数及通信代价三者在实际场景和应用中的权重。对簇j中的所有节点均按公式(1)计算出相应的综合指标值Syn_Indexj(xi)(i=1，2，...，n，表示簇 j内的节点数)，再从大到小排列成Syn_Indexj(xi1)、Syn_Indexj(xi2)、Syn_Indexj(xi3)、…、Syn_Indexj(xin)。根据排队后的综合指标值，即可实施备份簇首的选取机制。这种备份簇首选取策略，合理地结合了节点的剩余能量、节点度数与节点通信代价，能有效地克服无备份簇首情形下分簇提前死亡的问题，有效地延长了网络生命，提升了网络的整体性能。该簇首备份机制的详细流程示意图如图4所示。

图4 簇首备份机制示意图

3 仿真与结果分析

为了便于比较分析，将本文提出的簇首备份机制引入到典型的基于K-均值聚类分簇算法KMC[16]中，并将此算法简称BH-KMC(Backup Cluster-Head for KMC)。笔者对分簇策略BH-KMC的分簇过程进行了模拟仿真，并就其性能与经典分簇策略LEACH[17]和KMC算法[18]进行比较分析。为了消除网络拓扑对策略性能评价的影响，在不同的节点密度情形下，各进行50次实验，取50次实验结果的平均值来比较分析。主要仿真实验参数如表1所示。

表1 模拟实验参数表

簇的平均生存时间是整个过程中各个簇生存时间的平均值，该指标从整体的角度上反映了分簇的稳定性。本文在节点密度和节点通信半径不同的网络环境下分别进行了仿真，得到节点密度与簇平均生存时间关系和节点通信半径与簇平均生存时间关系如图5、图6所示。

图5 簇平均生存时间与节点密度关系示意图

图6 簇平均生存时间与节点通信距离关系图

从图5及图6可以看出随着节点密度和节点通信半径的增加，BH-KMC和KMC算法的平均生存时间是递增的，LEACH由于节点密度和通信半径的增加的影响而略有下降。可以发现，在不同的环境下BH-KMC算法的簇平均生存时间始终高出其他两种策略。实验表明BH-KMC算法在簇平均生存时间上都高于其他两种算法一倍以上。

4 结束语

本文提出了一种基于综合指标的无线传感器网络簇首备份机制。在基于综合指标的簇首备份机制中，通过节点剩余能量、节点度数、通信代价三者构建一种有效的综合指标，并根据此综合指标对簇内成员节点进行排序，选取具有优秀的综合指标值的成员节点作为备份簇首节点，并保持簇首与备份簇首不断轮换。实验表明BH-KMC算法在簇平均生存时间上都高于其他两种算法一倍以上。这意味着整个分簇可以在更长的时间内稳定地工作，表明采用该机制的分簇无线传感器网络可有效地降低簇首故障所带来的损失，加强了分簇的稳定性，延长了网络寿命，使得网络整体性能得到优化。

[1]李莉，董树松，温向明.无线传感器网络中的分簇算法[J].无线通信技术，2006，15(3):47-51，62.

[2]崔莉，鞠海玲，苗勇，等.无线传感器网络研究进展[J].计算机研究与发展，2005，42(1):163-174.

[3]唐勇，周明天，张欣.无线传感器网络路由协议研究进展[J].软件学报，2006，17(3):410-421.

[4]Younis O，Fahmy S.Distributed clustering in Ad-hoc sensor networks:A hybrid，energy efficient approach[C]//Proc.IEEE INFOCOM 2004.Hong Kong，China，2004.

[5]沈波，张世永，钟亦平.无线传感器网络分簇路由协议[J].软件学报，2006，17(7):1588-1600.

[6]徐建波.无线传感器网络分布式分簇和节能的数据收集协议研究[D].长沙:湖南大学，2008.

[7]朱光辉，张修如，刘卫彪.无线传感器网络中能量有效的加权分簇算法[J].传感器与微系统，2007，26(12):102-105.

[8]Lindsey S，Raghavendra C S.PEGASIS:Power-efficient gathering in sensor information systems[C]//Proc of the IEEE Aerospace Conf.Montana:IEEE Aerospace and E-lectronic Systems Society.2002:1125-1130.

[9]李莉，温向明.无线传感器网络中分簇算法能量有效性分析[J].电子与信息学报，2008，30(4):966-969

[10]Gupta I，Riordan D，Sampalli S.Cluster-head election using fuzzy logic for wireless sensor networks[C]//Proc.of the 3rd Annual Communication Networks and Services Research Conf.Halifax:IEEE Computer Society，2005:255-260.

[11]陈嘉宁，谢高岗，张大方，等.BH-3hBAC:一种稳定的MANET分簇策略[J].系统仿真学报，2008，20(6):1523-1528.

[12]陈嘉宁.基于备份的移动自组织网络分簇策略研究[D].长沙:湖南大学，2007.

[13]徐强，汪芸.容错节能无线传感器网络中可靠覆盖问题的解决方案[J].软件学报，2006，17(s):184-191.

[14]夏心锋，孙燕.基于聚类的无线传感器网络的分簇算法研究[J].南京师范大学学报:工程技术版，2008，8(2):81-84.

[15]蒋青云.无线传感器网络分簇算法与簇首备份机制研究[D].长沙:中南大学，2009.

[16]陈洁洁，樊晓平，瞿志华，等.基于减法聚类的无线传感器网络分簇路由算法[J].信息与控制，2008，37(4):435-438，444.

[17]张源.一种基于LEACH协议的节能型分簇路由算法[J].计算机与现代化，2009(12):133-136.

[18]Ahmad A，Dey L.A k-mean clustering algorithm for mixed numeric and categorical data[J].Data ＆ Knowledge Engineering，2007，63(2):503-527.