无线传感器网络分簇路由协议研究

刘兴 杨济海 杨涛 韩晴

摘   要：在无线传感器网络中，分簇型路由在路由协议中占据重要的地位，该协议方便拓扑结构管理，能源利用率高，数据融合简单。文章从簇头生成、簇形成和簇路由3个角度对典型的分簇路由算法LEACH，HEED，EEUC，PEGASIS进行了系统描述，从网络生命周期和节点存活数量等方面，对比了其优缺点，结合该领域的研究现状，指出了未来研究的方向。

关键词：无线传感器网络;分簇;路由协议

无线传感器网络（Qireless Sensor Network，WSN）作为数据采集和处理的新方式，在各行业受到了越来越广泛的应用[1]。它是由大量传感器节点组成的一个自组织无线网络系统，具有数据采集、数据处理、数据存储和无线通信等功能，被广泛应用于军事侦察、环境监测、医疗监控、农业、养殖、空间探索等领域。由于网络中节点的计算能力、存储容量和能量资源有限，使得路由协议的设计成为无线传感器网络的关键技术之一，在WSN路由协议中，分簇型路由协议由于其能量利用率高而受到越来越广泛的应用。

1    无线传感器网络分簇路由算法概述

与其他类型的路由协议相比，分簇路由协议具有更好的性能，是目前研究的重点和热点。分簇路由协议的拓扑结构如图1所示，整个网络被随机分成若干个簇，每个簇由一个簇头节点和若干个成员节点构成，成员节点负责采集数据，并将数据发给对应的簇头节点;簇头节点负责进行数据的汇聚和压缩，并通过一跳或者多跳的方式，将数据发送到基站（Base Station，BS）。

分簇路由协议的重点和核心内容是快速和有效的构建簇结构，本文通过对常用分簇型路由协议进行描述和对比分析，力求明确未来重点研究方向。

2    常用分簇型路由协议分析

2.1  LEACH协议

LEACH协议是首次针对WSN提出的一种自适应聚类路由协议[2]。LEACH协议采用了“轮”的概念，并将每轮通信过程分为簇建立阶段和数据传输阶段。在簇建立阶段，重点实现簇头选举和成簇，簇头选举时，每个节点将生成0～1之间的一个随机数，根据当前轮数计算阈值，如果阈值比随机数大时，则被选举为簇头节点，当选的概率为：

（1）

其中，P是簇头占总节点的比例，R是当前的轮数。簇头节点将选举结果广播到整个网络，使其余节点加入最近的簇。在数据传输阶段，每个簇的成员节点依据TDMA时隙采集并发送数据给簇头节点，簇头节点接收簇内成员节点的数据并进行压缩融合，然后通过一跳或者多跳的方式将数据汇聚到基站。

LEACH协议的优点：（1）采用分布式算法选举簇头，各节点的机会相同，可尽量平衡能量消耗。（2）在簇内的数据融合完成时，传输距离被减小，可在一定程度上节约能量。

LEACH协议的缺点：（1）簇头的成本开销大，需要每轮进行簇头重选。（2）簇头之间的负载不均衡，簇头在整个网络中分布不均，簇内成员节点分布不均。（3）簇内成员节点直接与簇头交换数据，加快了簇头的能量消耗，导致了每个簇的规模有限，不适合大规模网络。

2.2  HEED协议

在簇头选举过程中，HEED协议主要依赖于基本参数和副参数[3]。基本参数是指所选择节点的剩余能量，节点剩余能量越多，该节点成为簇头节点的概率就越大;副参数是指簇内的通信代价，其主要目标是确保最终成簇和簇头之间的负载平衡。在发送相关的竞争信息时，利用公式（2）计算节点的当选概率，即：

（2）

其中，Cprob與Pmin是固定值，Eresident表示节点的剩余能量，Emax表示节点的初始能量（最大值），为了防止收敛速度过慢，设置了剩余能量的最小比率。

与LEACH协议类似，HEED协议也采用了“轮”的概念，但与基本LEACH协议最大的区别是，HEED协议采用了多跳方式与基站通信，而LEACH协议采用的是单跳方式。

HEED协议的优点：（1）簇头分布相对比较均匀，聚类效率高，网络拓扑更科学。（2）簇头选举考虑了剩余能量的影响，引入基本参数、副参数的多重约束，更合理。

HEED协议的缺点：（1）每一轮簇重组都会产生较大的簇头成本。（2）簇的覆盖范围是重叠的，簇间干扰相对严重。

2.3  EEUC协议

EEUC协议中簇头选举也考虑了剩余能量的影响[4]，其主要出发点是为了克服均匀分簇的不足、簇头向基站转发数据能量消耗大等不足。为了节约簇头之间传输信息的能量，该协议使用非均匀分簇的竞争机制，使簇根据具体情况分为不同大小的簇，让靠近基站的簇存在较少的成员并且具有小竞争半径。簇半径计算公式为：

（3）

其中，R0是候选簇头竞争半径的最大值;c是簇半径控制参数，介于0～1之间;dmax是节点到BS的最大距离;dmin代表了节点到BS的最小距离;d（i，BS）代表簇头i到BS的距离。

EEUC协议的优点：（1）簇头选举考虑了能耗的不平衡问题，延长了网络的生命周期。（2）簇间的多跳通信减少了网络流量。

EEUC协议的缺点：（1）簇生成过程复杂且成本较大。（2）相对不同基站、不同的簇半径，数据采集与传输存在较大的随机误差。

2.4  PEGASIS协议

PEGASIS协议是在LEACH协议的基础上改进而来的，该协议选择了定期选择簇头的方式，同时节点根据地理位置被串入链，并由贪心算法实现[5]。在该协议中，节点只需要与距离它们最近的邻居节点通信，并且下一个节点将采集到的自身数据和所接收的数据进行融合，然后传送到目的节点。

PEGASIS协议主要包括两个步骤：第一，利用贪婪算法创建链，并且选择距离自身最近的邻居节点作为下一跳节点;第二，数据传输阶段中，在链路上数据按顺序传输，并进行融合处理，最终将由链首将数据直接传送给汇聚节点。其链结构示意如图2所示。

PEGASIS協议的优点：（1）基于地理位置，降低了通信节点的平均距离，减少了簇的成本。（2）利用“令牌”确保数据传输的可靠性。（3）采用数据融合，减少了数据分发量，降低了能量消耗。

PEGASIS协议的缺点：（1）由于节点基于地理位置形成一条链，数据传送扩展性大。（2）簇头选择基本上是一致的，造成簇间干扰大、开销大。

3    常用分簇路由协议比较

综上，本文分析了LEACH，HEED，EEUC，PEGASIS 4种分簇路由协议的基本思想、优势和劣势，结合影响协议的几个因素，对其进行总体对比，如表1所示。

4    结语

根据分簇路由协议的特点，本文对LEACH，HEED，EEUC，PEGASIS 4种典型的分簇路由协议进行了分析，对比了其路由机制的优缺点，并且从簇头选举阶段、成簇阶段、簇维护成本、算法的稳定性等方面进行了总结与比较。结合该领域的研究现状，指出了未来研究的方向。

[参考文献]

[1]AKYILDIZ IF，SU W，SANKARASUBRAMANIAM Y，et al.A survey on sensor networks[J].IEEE Communications Magazine，2002（8）：102-114.

[2]WENDI R H，ANANTHA C，HARI B.Energy-efficient communication protocol for wireless sensor networks[C].Hawaii：Proceedings of the 33rd Annual Hawaii International Conference on System Sciences，2000.

[3]OSSAMA Y，SONIA F.HEED：a hybrid，energy-efficient，distributed clustering approach for ad hoc sensor networks[J].IEEE Transactions on Mobile Computing，2004（4）：366-379.

[4]LI C F，YE M，CHEN G H，et al.An energy-efficient unequal clustering mechanism for wireless sensor networks[C].Singapore：Proceedings of the 2nd IEEE International Conference on Mobile Ad hoc and Sensor Systems，2005.

[5]STEPHANIE L，CAULIGI S R.Pegasis：power efficient gathering in sensor information systems[C].San Francisco：Proceedings of the IEEE Aerospace Conference，2002.

Research on clustering routing protocol for wireless sensor networks

Liu Xing1， Yang Jihai1， Yang Tao1， Han Qing2

（1.State Grid Jiangxi Information & Telecommunication Company， Nanchang 330096， China;

2.School of Electrical Engineering， Northeast Electric Power University， Jilin 132012， China）

Abstract：In wireless sensor networks， clustering routing plays an important role in routing protocol， which is convenient for topology management， high energy efficiency and simple data fusion. In this paper， LEACH， HEED， EEUC， PEGASIS， which are typical clustering routing algorithms， are systematically described from three aspects of cluster head generation， cluster formation and cluster routing. The advantages and disadvantages of LEACH， HEED， EEUC， PEGASIS are compared from the aspects of network life cycle and node survival number. Combined with the research status in this field， the future research direction is pointed out.

Key words：wireless sensor work;clustering;routing protocol