传感网分簇算法研究及其进展

胡　静　沈连丰

摘要:作为网络拓扑控制的有效方式之一,分簇算法可显著降低无线传感器网络的能量消耗,提高网络吞吐率。文章基于无线传感器网络分簇的架构,对目前主流的分簇算法进行归纳分类。针对无线传感器网络分簇算法设计中存在的难点,文章给出了解决难点的部分成果,并对进一步的研究进行了展望。

关键词:无线传感器网络;分簇算法;拓扑控制;簇头

Abstract: As one of the efficient ways of network topology control, clustering algorithms can reduce the energy consumption of the network and obviously improve the throughput ratio. Based on the architecture of clustering in WSN, the article classifies the representative clustering algorithms. The article analyzes the difficulties and problems in the algorithm design and illustrates some of the results; and further research of this area is foreseen.

Key words: wireless sensor network; clustering algorithm; topology control; cluster head

无线传感器网络(WSN)在军事、环境监测、工业控制、智能家居和城市交通等方面都有重要的实用价值,已成为热点研究领域之一[1]。对应于不同的应用需求,各种WSN在硬件平台、软件系统和通信协议上都存在较大差异。从网络拓扑的角度看,WSN可以被分为平面结构以及分簇结构两大类。平面结构中WSN各节点的地位都是平等的,而在分簇结构中,网络中的节点被划分为若干个称为簇的节点集合,每个簇通常由一个簇头节点和多个成员节点组成,簇头负责管理和控制簇成员节点的工作,同时负责簇内数据收集及簇间数据转发。与平面结构相比,采用分簇结构的WSN具有能量效率高、可扩展性好等优点,但是如何选取簇头、划分簇类,需要合适的分簇算法加以解决。

适用于WSN的分簇算法已成为WSN研究领域的核心技术之一。

1 WSN中的分簇架构

在采用分簇结构的无线传感器网络中,网络节点被划分为若干个簇。每个簇通常由一个簇头节点(CH)以及多个成员节点(MN)组成。成员节点只与簇头通信,簇头与簇头构成高一级的虚拟骨干网,负责簇内的数据融合和簇间数据转发。因为簇头节点的能量消耗较大,通常采用周期性选择簇头节点的方法均衡网络中节点能量的消耗。簇头的集合形成连通统治集(CDS),因为获得最优CDS是NPC问题,因此实际提出的算法均为启发式的。图1给出了分簇结构以及簇内与簇间的数据流向。

WSN采用分簇结构具有如下一些显著的优点:

●在满足一定约束条件情况下(例如覆盖范围与采样精度要求等),簇成员节点可以在某些时间段内关闭通信模块,大幅度减少空闲等待状况的能量消耗,因此可节省能量。

●簇头通常负责采集簇成员发送来的数据,这些数据具有较大的相关性,因此可以采用数据融合算法,在保证信息量的情况下降低数据通信量,降低数据转发的能量开销。

●因为采用层次结构,簇成员只需了解到所属簇头的路由信息,簇头只需了解簇头间的路由信息,因此可降低路由协议的复杂度,减少路由表项数目,路由维护开销也随之降低。

●具有较好的可扩展性能,更加适合于大规模WSN的应用场景。

2 算法分类

国内外学者已经提出了大量分簇算法,分别适应于不同的设计目标与应用环境。根据不同的分类标准,分簇算法可以有多种分类方法。例如,以簇形成是否存在集中控制,可划分为集中式/分布式算法;以是否需要预先获得全球定位系统(GPS)信息,可划分为基于地理位置/不基于地理信息的算法;以每次分簇是否存在一个确定的结果,可划分为确定性/随机性算法,等等。需要指出的是,各种分类方法之间可能互相重叠,即一个特定的分簇算法可以同时具有不同方面的分类特性,例如从图1所示的分簇结构中可以看到该算法属于单层、簇内单跳、簇间多跳。

2.1 集中式/分布式算法

根据是否存在一个中心控制节点(通常是基站)负责整个网络的簇划分,分簇算法可分为集中式与分布式两类。典型的集中式算法有LEACH-C[2]、APTEEN[3]等。我们提出的基于径向基函数(RBF)的分簇算法[4]也属于此类。中心控制节点通常有持续的电源供应、较高的存储与计算能力,并能获得网络的全局信息(如每个节点的位置以及剩余能量等),因此可以采用复杂的算法获得优化的分簇结果。但是由于普通无线传感器节点能量有限,计算与通信能力不强,因此对于大型的WSN,集中式算法在灵活性、可扩展性以及健壮性等方面存在缺陷,例如很多集中式算法要求获得节点的剩余能量,因为传感器节点运行中能量不断下降,所以必须隔一段时间就得通知中心控制点更新剩余能量信息,这就造成大量额外数据包的传输,使算法的开销过大。

与集中式算法不同,分布式算法一般只需要相邻节点之间互相交换信息,甚至不考虑相邻节点独立作出判断,这类算法简单、高效、灵活,因此更适用于大规模WSN。目前大部分经典的WSN分簇算法如LEACH、HEED[5]等,都属于分布式算法,Hausdorff算法[6]、响应式分布分簇算法(RDCA)[7]也属于这一类。

2.2 基于地理位置/地理位置无关算法

根据是否需要借助GPS获得节点的地理位置,可以将分簇算法分为基于地理位置的算法与地理位置无关算法两类。典型的基于地理位置的算法有GAF[8]等,其他大部分常见的分簇算法,如LEACH与HEED算法等,都不需要借助于地理位置信息。基于地理位置的算法有的需要获得全局信息,有的只需要通过广播包获得相邻节点的位置信息。因为传感器网络节点数量大,单个节点造价低、能量有限,而GPS模块不但成本高而且会额外消耗节点能量,因此为每个节点都配备GPS模块是不经济的。通常的做法是在网络中设置少量信标节点,一般是通过携带GPS定位设备获得自身的精确位置,然后其他传感器节点通过信标节点的位置信息根据一定的定位算法获得自身的位置。常用的定位算法有到达时间(TOA)、到达时间差(TDOA)、接收信号强度指示(RSSI)、到达角度(AOA)和距离向量-跳数(DV-Hop)[9]等。不过在室内、水下或森林等有障碍环境中无法使用GPS系统,使其应用受到一定限制。基于地理位置的分簇算法一般假设节点已知自身的精确位置,而如何获得自身位置信息则不包括在算法内。

2.3 确定性/随机性算法

在网络拓扑结构与每个节点的剩余能量不变的情况下,根据分簇算法是否能取得确定结果,可将其分为确定性与随机性算法。在确定性算法中,节点必须等待某个特定事件发生或某些特定节点已宣布自己的角色(CH还是MN)后,才能做出决定。例如DCA算法[10]必须等待所有权值高于自己的相邻节点宣布成为CH或者加入到某个簇后,才能确定自身是成为CH还是MN。确定性算法的一个不足之处就是收敛时间依赖于网络规模,DCA算法的时间复杂度为O(d ),d 为网络直径(通常用跳数来定义),在最差情况下(节点线性分布),d 可达到

n -1(n为节点个数)。此外网络的鲁棒性不好,如果一个节点在拓扑发现阶段后失效,可能造成其相邻节点陷入无限期等待。为消除这种现象,一些算法,例如ACE算法限制节点在一定次数(如5次后)结束循环等待[11]。

随机性算法根据一定的概率确定节点是否成为簇头。LEACH算法中节点成为簇头的概率仅与过去若干轮次中节点自身的状态有关,HEED算法中的概率与剩余能量有关,还有一些算法同时考虑了节点度等多种参数。随机性算法分簇结果的优化程度通常不如确定性算法,但是收敛速度较快,开销较小,鲁棒性好,特别适合于大规模网络。

2.4 单层/多层算法

根据算法产生的最终拓扑结构,可分为单层和多层算法。单层算法只进行一次分簇,目前提出的大部分分簇算法,如LEACH、HEAD、GAF等都属于此类,而多层算法在前一次分簇选举出的簇头基础上继续进行分簇,选举出第二层簇头和簇成员节点,随后可以进行第三层、第四层等簇头选举。多层算法一般只用于超大规模WSN,算法较为复杂。文献[12]提出了一种多层算法(层数从1到5),该算法以最小化系统整体能量消耗为目标,推导出系统整体能量消耗的解析式,然后通过数值计算求出不同节点密度条件下的最优解。

2.5 簇内单跳/多跳算法

根据簇内MN到CH的跳数,可分为簇内单跳与簇内多跳算法,也可采用单跳算法的MN直接与CH进行通信,而多跳算法中的MN可通过其他MH中继与CH进行通信。LEACH、HEED等算法采用单跳方式,而Max-min D等算法使用多跳方式。

Mhatre等对簇内单跳和多跳的情况做了深入研究[13],提出以簇内第一个节点死亡作为簇的生命周期(不考虑CH的能耗)并假设所有MN的初始能量相同。单跳情况下,离CH越远的MN越早耗尽能量;多跳情况下,如果MN的发射功率相同,则离CH最近的MN因为负担的中继任务最重故消耗的能量最多。其分析存在的缺陷是只考虑了节点发送以及接收状态下消耗的能量,没有考虑空闲状态下的能量消耗。目前很多WSN引入节点睡眠/唤醒机制,在无感知以及数据传送的情况下关闭射频电路以节省能量。当引入这种机制后,网络拓扑会发生动态变化,很难给出一个确定性的解析式,一般只能采用概率分析的方法并通过仿真得出结果。当采用单跳模式时,MN与CH的通信可以采用TDMA方式,每个MN分配一个时隙,数据传送只在指配的时隙中进行,其余时间处于睡眠状态,大大降低了节点处于空闲状态的时间(如LEACH)。而采用多跳模式时,因为节点还需考虑数据中继问题,不可避免会耗费较多的等待时间。从这一点上看,单跳方式与多跳方式相比具有一定优势。

3 分簇算法设计难点

从网络协议分层上看,分簇算法可以看做是拓扑控制的一大类,位于MAC层与网络层之间。在算法设计中,需要考虑网络连通性、CH轮转频率、簇半径优化以及节点同步等一系列问题,对这些问题的深入研究可以从跨层设计的角度,结合MAC层、网络层甚至应用层进行。

3.1 连通性问题

WSN中,保持节点到基站的连通性是极为重要的。对于采用分簇结构的无线传感器而言,连通性问题包括MN到CH(簇内通信)以及CH到基站(簇间通信)两个层次的连通性。如前所述,簇内通信分为单跳与多跳两种模式,一般由成簇算法确保连通性问题。而簇间通信需要通过虚拟骨干网进行,根据构成虚拟骨干网的节点不同,可将簇间通信分为两大类。大部分虚拟骨干网完全由CH节点构成(如HEED算法),为保证连通性,这一类算法要求节点发射功率可调,且CH的密度和覆盖范围满足一定的条件[14];另一些虚拟骨干网则由CH和簇边缘的网关节点(GN)构成,如CEC算法[15],一般适用于使用固定发射功率的网络。两类方法相比,前者的优势在于非CH节点在没有感知及数据发送任务时可以进入睡眠状态,因此更加节省能量。连通性所带来的簇半径以及簇间通信范围的优化选取问题仍然是分簇算法研究的一个重点。

3.2 MAC层设计

通常进行分簇算法分析和仿真时都假设信道是无冲突的,而在实际情况下,尤其是单信道环境下,冲突和干扰不可避免。分簇算法经常使用TDMA模式的MAC层协议,使用TDMA方式虽然能够消除簇内通信冲突,对相邻簇之间的簇间冲突却无能为力,当CH为进行簇间通信而提高发射功率时,这种冲突带来的影响更为明显。使用CDMA方式可以使簇内通信与簇间通信并发进行成为可能,但CDMA器件价格昂贵,难以在强调低成本的无线传感器节点中大规模使用。如何设计与选用合适的MAC层协议降低冲突与干扰,也是分簇算法研究的难点之一。

3.3 簇头轮换机制

WSN的设计以最大化网络生命期为最终目标,因而使各节点尽可能均衡地消耗能量极为重要。而分簇算法中一般CH的能量消耗大大高于MN,容易造成CH节点因为能量耗尽而提前死亡,为避免这一情况出现,一种方式就是采用簇头轮换机制,使各节点每隔一段时间轮流担任簇头,从而使各节点剩余能量尽可能接近相等。簇头轮换机制通常独立于分簇算法,与分簇算法互为补充。常见的簇头轮换机制有被动与主动式两种。前者每隔固定时间引发,后者需要预先设定一个阀值,当监视的参数低于或者超过某阀值时引发重新分簇,常见的阀值有节点剩余能量、节点度等。无论是被动还是主动式簇头轮换机制,选择合适的参数都会对算法的最终结果产生重要影响。如果簇头轮换过于频繁,则会带来大量的额外开销和网络中断;如果簇头轮换频率过低,则可能造成某些节点能量过早耗尽。因此,只有进行合理的折中才能获得最优化的网络生命期。

3.4 节点休眠/唤醒机制

采用节点休眠/唤醒机制,使非活跃节点尽可能处于睡眠状态可以大大延长节点电池寿命。WSN在节点部署时一般是高度冗余的,即只需要一部分节点处于活跃状态就可以完成任务,这是引入休眠/唤醒机制的前提条件。

WSN是应用相关的,不同应用层业务适宜采用的休眠/唤醒机制也有所不同。对于周期性数据采集网络(例如用于环境监测的网络),非CH节点在不需要进行感知或者与CH通信时将尽可能地处于休眠状态。对于突发事件监测网络(例如用于森林防火、入侵检测等),CH可将所属的MN划分为若干个冗余组,通知各组轮流进入睡眠状态,同时保持其中一个组处于活跃状态。还有一种方式是在分簇之前就预先选择一个可以覆盖目标区域的节点集,对这些节点集内部的节点进行分簇,分簇产生的CH和MN始终处于活跃状态,而节点集外的节点进入睡眠状态以节省能量。

4 新的分簇算法

4.1 Hausdorff算法

Hausdorff算法也是一种基于节点位置、通信有效性和网络联通性的分布式数据收集算法。该算法分为3部分:首先,由Hausdorff算法将节点分成几个静态的簇,用欧几里德距离来计算两个点之间的距离,用Hausdorff距离来计算两个点集之间的距离,该算法将Hausdorff距离作为分簇的量度。其次,在整个网络生命中分簇只执行一次,而每个簇中的簇首是由簇中的成员最优地轮换调度,该算法基于节点的剩余能量和其周围邻居节点的接近程度,采用一种贪婪算法在每个周期选择簇首。第3,簇首之间构成网络骨架定期地收集、融合和转发数据到基站,它们之间的通信是采用最小功耗路由算法,其中利用了Dijkstra最短路径算法。图2显示了传感器节点数目从300变化到600时的Hausdorff分簇算法和HEED协议不同情况下的网络生命期,图2(a)和图2(b)的纵坐标分别表示第一个节点与第二个节点死亡时所经历的轮次,从图2可以看出,无论节点的密度是多少,Hausdorff分簇算法的性能均优于HEED协议。

4.2 RDCA分簇算法

基于负载平衡的响应式分布分簇算法(RDCA)也属于分布式算法。该算法对DCA算法进行了改进,不需预先得知节点自身及其他节点的位置信息,而仅根据局部拓扑信息快速进行分布式的簇头选举,并根据代价函数进行簇的划分,适用于周期性获取信息的WSN。分析与仿真表明,该算法具有良好的负载平衡性能和较小的协议开销,与LEACH协议相比,能够减少能量消耗,网络生存期大约延长了40%。图3为相同拓扑环境和初始能量下DCA算法与RDCA算法(Closest)一次实验的分簇结果,图中清楚可见RDCA算法(Closest)具有更好的负载平衡性能。

4.3 基于RBF的分簇算法

该算法属于集中式/基于地理位置的分簇算法,适用于较小规模的WSN。分簇决策由基站通过计算得出,同时在算法执行前每个节点均已获知自己的地理位置。当基站收集到网络中所有节点的剩余能量以及位置信息后,建立由输出层、隐层、输出层3个层次构成的RBF神经网络对每个节点成为簇头的概率进行计算,其中输入向量X由节点剩余能量、覆盖半径内的节点个数、节点至覆盖半径内其他节点距离的均方差、节点位置4个分量组成,RBF用于隐层,输出向量Y包含该节点成为簇头的概率。基站根据网络中的全部节点个数确定簇头个数k,并选出概率最高的k个节点成为本轮次的簇头。算法所使用的RBF神经网络结构如图4所示。

5 结束语

作为网络拓扑控制的有效方式之一,分簇算法的使用可以显著降低通信开销,并且有利于与数据融合等技术结合,进一步降低能量消耗。软硬件技术的进一步提高使传感器节点的计算能力增强而硬件成本下降,这也为引入性能更强而复杂度较高的算法提供了前提条件。根据近年来分簇算法的发展趋势,我们认为如下几点值得进一步深入研究。

(1)更精确的仿真模型

目前的分簇算法研究更多的基于以时间为单位的能量消耗模型[16]。现在越来越多的节点可利用太阳能电池等能量收集技术进行能量补充,针对此类节点需要根据硬件参数设计特殊的节点能量模型。此外,目前在仿真中普遍采用的自由空间与多径衰落模型过于简单,在实际的网络部署中还需要考虑天线高度、地形地貌、植被覆盖等情况,采用更接近于实际使用环境的链路质量模型。

(2)异构网络的分簇算法

具有更高计算能力、更多能量补充的节点在簇头选举过程中更易于成为簇头。在实际应用的传感器网络系统中,存在多种异构节点。以节点异构为前提,设计兼有平面结构和分簇结构优点的新型数据传输模式,也是一个很有应用前景的研究方向。

(3)QoS性能

大量对WSN分簇算法的研究均以能量有效性及负载平衡作为算法性能的度量标准,但未来的研究应进一步考虑分簇算法对网络QoS性能的影响,尤其是在数据流量动态变化的情况下。在涉及到图像以及视频传输的多媒体WSN中,设计能量感知的QoS分簇算法更加值得关注。

此外,无线传感器网络作为一种与应用高度相关的网络,引入跨层设计机制,与MAC、网络层甚至应用层实现联合优化,进一步提高网络的容错性,降低冲突与干扰,与休眠/唤醒机制相结合,与网络覆盖、数据融合等问题联合考虑等,都是分簇算法需要进一步研究的课题。

6 参考文献

[1] AKYILDIZ I F, SU W, SANKARASUBRAMANIAM Y, et al. Wireless sensor networks: A survey[J]. Computer Networks Journal, 2002,38:393-422.

[2] HEINZELMAN W B, CHANDRAKASAN A P, BALAKRISHNAN H. An application-specific protocol architecture for wireless microsensor networks[J]. IEEE Transactions on Wireless Communications, 2002,1(4):660-670.

[3] MANJESHWAR A, AGRAWAL D P. APTEEN: A hybrid protocol for efficient routing and comprehensive information retrieval in wireless sensor networks[C]//Proceedings of 16th International Parallel and Distributed Processing Symposium(IPDPS02), Apr 15-19,2002,Fort Lauderdale, FL,USA.Los Alamitos, CA,USA:IEEE Computer Society, 2002:195-202.

[4] ZHU Xiaorong, SHEN Lianfeng. RBF-based cluster-head selection for wireless sensor networks[J]. Journal of Southeast University (English Edition), 2006,22(4):451-455.

[5] YOUNIS O, FALMY S. HEED: A hybrid, energy-efficient, distributed clustering approach for Ad hoc sensor networks[J]. IEEE Transactions on Mobile Computing, 2004,3(4): 366-379.

[6] ZHU Xiaorong, SHEN Lianfeng, YUM T S P. Hausdorff clustering and minimum energy routing for wireless sensor networks[J]. IEEE Transactions on Vehicular Technology, 2009,58(2):990-997.

[7] 胡静, 沈连丰, 宋铁成, 等. 新的无线传感器网络分簇算法[J]. 通信学报, 2008,29(7):20-26.

[8] XU Y, HEIDEMANN J, ESTRIN D. Geography-informed energy conservation for ad hoc routing[C]//Proceedings of 7th Annual International Conference on Mobile Computing and Networking (MOBICOM01), Jul 16-21,2001, Rome, Italy. New York, NY,USA:ACM, 2001:70-84.

[9] HE T, HUANG C, BLUM B M, et al. Range-free localization schemes for large scale sensor networks[C]//Proceedings of 4th ACM International Symposium on Mobile Ad Hoc Networking and Computingin(MobiHoc03,Jun 1-3,2003, Annapolis,MD,USA.New York, NY, USA:ACM, 2003:81-95.