无线传感器网络分簇路由协议综述﹡

古 欣，禹继国，王光辉

（①曲阜师范大学 计算机科学学院，山东 日照 276826；②山东大学 数学学院，山东 济南 250100)

0 引言

在实际应用中无线传感器网络（WSN，Wireless Sensor Network）中的大量节点通常能量有限且往往不能再次补充。因此如何合理利用有限能量来延长网络寿命是路由协议设计面临的首要问题。分簇被证明是节省能耗和提高网络寿命的一种基本机制。所谓分簇，就是将节点划分成许多称之为簇的组，每个簇都有一个簇头和许多簇成员[1]。成员将收集到的数据发送给簇头，簇头对数据进行融合后直接或者通过其他簇头发送到基站。

通过分析现有WSNs分簇协议，揭示了分簇算法的本质，并基于分簇算法本身和分簇技术的应用两方面对这些协议进行了分类和介绍，最后引导了下一步的研究方向。

1 分簇的目标和优势

分簇的目标往往根据具体的应用而设定，例如文献[2]中将分簇目标总结为负载均衡、增加连通度、最小化簇数目以及最大化网络寿命等。

对于大规模 WSNs而言，分簇网络拓扑在拓扑管理、可扩展性和能量效率等方面都具有明显优势。

1）分簇可将网络分为多个小规模的网络，从而可降低拓扑管理的难度。

2）较好的可扩展性使分簇更适用于大规模WSN应用场景。

3）簇内引入节点睡眠机制，簇头保持唤醒状态，成员按调度向簇头发送信息，既不影响网络连通性又能节省能量。

4）簇头对数据进行融合，降低了数据冗余，减少了数据通信量。

5）只有簇头参与路由大大减少了路由表尺寸，降低了通信开销和内存开销。

2 基于分簇算法的分类及介绍

近年来分簇算法取得了大量优秀的研究成果。按不同方面可将现有分簇算法进行如下分类。

1）根据算法的执行方式可分为集中式分簇和分布式分簇。集中式分簇算法需要掌握网络全局信息，因此可获得好的簇头分布但在大规模网络中的应用有限。分布式分簇算法中节点根据局部信息独立分簇，开销小，更适合大型网络。

LEACH[3]是最为经典的按轮执行的分布式分簇协议，每轮由簇的建立和数据传输两阶段组成。在前一阶段,节点生成一个[0,1]之间的随机数，若此数小于阈值 T(n)则成为簇头。在后一阶段，成员将数据发送给簇头，簇头对数据进行融合后直接发送至基站。簇头角色全网内周期性轮转。该协议结构简单且不需要较大通信开销，然而它在簇头选举时未考虑节点剩余能量。学者们针对其提出了一些改进协议，如在簇头竞选时文献[4]同时考虑了节点剩余能量和距基站距离的。文献[5]同时考虑了节点位置和剩余能量。

2）根据分簇的层数不同可分为单层分簇和多层分簇。单层分簇将网络分为两层，簇头为高层，成员为低层，所有节点由一层簇头和归属于这些簇头的成员组成，算法实现简单，开销较小。多层分簇中低层簇头通常作为高层簇头的成员，因此可进一步降低节点能耗，但实施复杂且开销较大。

文献[6]采用自顶向下的方式构造多层分簇拓扑。在簇的建立阶段节点以 p1(u)的概率成为第一层簇头，其他节点成为第一层簇成员。第一层簇头通知其成员进行第二层簇头选举，第一层成员以 p2(u)的概率成为第二层簇头，剩余节点成为第二层簇成员，依次进行直到簇内节点数小于等于3时停止。数据传输阶段，T层成员将数据发送到T层簇头，T层簇头对数据进行融合后发送至 T-1层簇头，依此类推，最后由第一层簇头将数据进行融合后发送给基站。

3）根据簇头轮转特点可分为时间驱动型分簇算法和能量驱动型分簇算法。前者指簇头按照一定时间周期在全网内轮转。后者指当簇头能量低于预设能量阈值时在局部轮转。

文献[7]中簇头依据节点剩余能量在簇内选择备份簇头，在簇头能量达到阈值或簇头意外失效的情况下，备份簇头迅速代替原簇头成为新簇头，并接管大部分原簇成员，无法接入新簇头的节点选择加入邻居簇，从而在局部完成拓扑重建工作。

4）根据簇头选举参数可分为以节点 ID、节点度、节点剩余能量和节点相对剩余能量等为簇头竞选参数的分簇算法。

文献[8]以节点相对剩余能量为簇头竞争参数。在簇的建立阶段每个节点 vj广播包含自身 ID和剩余能量的E_Msg消息，同时也收到所有邻居的E_Msg消息。 vj基于此计算自己的相对剩余能量和发送簇头消息的时刻t，若节点在t之前没有收到邻居的簇头消息，则广播簇头消息成为簇头，否则退出簇头竞争。

5）根据簇的大小规模可分为均匀分簇算法和非均匀分簇算法。均匀分簇算法中簇的大小是均匀的。非均匀分簇算法则通过控制簇的大小来均衡簇头间能耗。

文献[9]中的算法是典型的分布式非均匀分簇算法，每轮开始节点 si以T的概率成为候选簇头，每个候选簇头 si根据自身到基站的距离计算它的竞争半径 Rc。并以 Rc为半径广播一条包含自身ID和剩余能量的簇头竞选消息。同时 si根据收到的来自其邻居的簇头竞选消息定期更新自己的簇头邻居集合 si. SCH。如果 si的剩余能量大于 si. SCH中所有节点的剩余能量就广播一条簇头消息宣布成为簇头。

3 基于分簇技术应用的算法分类及简述

近年来对基于分簇技术设计的算法也取得了不少研究成果。考虑不同的应用对这类算法进行如下分类。

1）安全分簇。文献[10]提出了基于秘密共享的CA证书方案和自组织证书方案。文献[11]中则提出一种基于簇的平面Merkle哈希树的Sybil攻击防御机制。

2）覆盖度。通常算法是先采用分簇的方式将覆盖区域划分成许多子区域，然后进行细粒度的网络监测与覆盖控制。文献[12]中利用最大熵原理对整个网络进行预分簇得到临时簇头，在保证网络覆盖度的前提下获取各分簇内活跃节点的连通支配集。

3）连通度。基于连通度约束的分簇算法可以保证簇头等骨干节点之间的连通性。文献[13]是利用分簇技术对网络进行划分后在保证网络连通度的前提下，找出可以达到最大覆盖度的最少活动节点数。

4）移动模型。针对网络中由少数节点移动的情况，文献[14]提出一种基于权值的分布式分簇算法，文献[15]提出了一个适用于同时包含固定和移动传感器节点的WSN的移动簇头通信协议。

5）数据收集。分析对以分簇为基础的收集融合算法可以减少网络中的数据传输总量，文献[16]算法提出了一种在分簇路由协议支持下的时间、空间多维度的数据压缩算法。文献[17]设计出一种基于分簇结构的混合型数据收集协议。

6）能量补给。已有的分簇路由协议大都是基于节点能量受限设计的，但现有的一些采能技术已经可以为节点提供适量的能量补给。文献[18]中提出的具有能量补给的分簇路由算法综合考虑了节点的能量起伏变化以及能量补给水平，修正了现有簇头选择机制和非簇头归属机制。

4 结语

通过对现有的大量研究成果进行分类总结。归纳了今后对WSNs研究需关注的几方面问题。

1）如何在网络中出现死亡节点的情况下，仍能保持连通性，使全网能正常运行，是一个有待解决的问题。

4）目前对算法研究所采用的网络模型和能量模型相对过于理想化，与真实网络有一定的差距。

5）当前研究成果通常是基于二维的网络模型，实现向三维空间的扩展也是所面临的问题之一。

6）通过对分簇技术的应用分析可知分簇的安全性问题、网络延迟和跨层优化[19-20]等方面也是今后研究工作的关注点。

[1]周新莲,吴敏,徐建波.无线传感器中一种能量感知的分布式分簇算法[J].计算机研究与发展,2009,46(05):723-730.

[2]ABBASI A A, YOUNIS M. A Survey on Clustering Algorithms for Wireless Sensor Networks[J].Computer Communications,2007:2826-2841.

[3]HEINZELMAN W R, CHANDRAKASAN A. Energy-efficient Communication Protocol for Wireless Microsensor Networks[C]//Proc. of the 33rd Annual Hawaii International Conference on System Sciences.Maui,HI,2000:1-10.

[4]郭强,孙强,李雪,等.无线传感器网络LEACH协议的研究[J].通信技术,2008,41(12): 155-157.

[5]肖刘军,邓平.一种基于位置和能量的WSN改进分簇协议[J].通信技术,2010,43(08): 43-45.

[6]JIN Y,WANG L,KIM Y,et.al. An Energy-efficient Multi-level Clustering Algorithm for Large-scale Wireless Sensor Networks[J]. Computer Networks,2008:542-562.

[7]黄河清,沈杰,姚道远,等.无线传感网自适应能量驱动簇头轮换算法研究[J].电子与信息学报,2009,5(31):1040-1044.

[8]刘明,曹建农,陈贵海.能量感知的无线传感器网络数据收集协议[J].软件学报,2007,18(05):1092-1109.

[9]李成法,陈贵海,叶懋,等.一种基于非均匀分簇的无线传感器网络路由协议[J].计算机学报,2007,30(01):27-36.

[10]CAPKUN S,BUTTYAN L,HUBAUX J P. Self-organized Public-key Management for Mobile ad hoc Network[J]. IEEE Trans. on Mobile Computing,2003,2(01):52-64.

[11]王晓东,孙言强,孟祥旭.WSN中基于簇的Sybil攻击防御机制[J].计算机工程,2009,35(15):129-134.

[12]马小飞,缪亮,范媛媛.基于连通覆盖度的WSN分簇协议[J].计算机工程,2010,36(15):114-116.

[13]MISRA S,KUMAR P M,OBAIDAT S M.Connectivity Preserving Localized Coverage Algorithm for Area Monitoring Using Wireless Sensor Networks.

[14]冯家麟,陈永生,杨萍.一种基于簇的分布式路由协议[J].计算机工程,2010,36(03):89-91.

[15]柴亦飞,高丽强,涂时亮,等.无线传感器网络移动簇头节点节能传输协议[J].计算机工程,2008,34(11):114-116.

[16]尹震宇,赵海,徐久强,等.WSN中基于分簇路由的多维度数据压缩算法研究[J].电子学报,2009(05):1109-1114.

[17]徐建波,李仁发.无线传感器网络中一种新型的混合型数据收集协议[J].计算机研究与发展,2008,45(02):254-260.

[18]樊晓平,杨玺,刘少强,等.具有能量补给的无线传感器网络分簇路由算法[J].计算机工程,2008,34(11):120-128.

[19]虞莉莉,赵跃华.无线传感器网络跨层优化研究[J].通信技术,2008,41(12):.

[20]唐慧,胡向东.无线传感器网络数据融合研究综述[J].信息安全与通信保密,2007(07):62-64,68.