基于LEACH协议的分簇算法设计

摘要：基于对LEACH算法的研究，提出助理簇头ASCH算法。该算法能够在无线传感器网络中，根据簇头节点所处的地理位置、剩余能量及簇内成员节点数目，动态决定是否需要在簇内产生助理簇头，并在需要产生助理簇头的簇内选择合适的节点来减少簇头通信能耗，同时解决某些簇头与基站通信可能存在困难的问题，从仿真结果可见此算法能有效均衡及降低网络能耗，达到延长网络的生存时间的目的。

关键词：无线传感器网络；LEACH算法；分簇算法；助理簇头；通信能耗

0 引言

在层次路由协议中，无线传感器网络被划分成多个簇，每个簇由一个簇头节点（Cluster Head）及多个簇内成员节点（Cluster Member）构成，多个簇头形成高一级网络。在高一级网络中，又可以再分簇，再次形成更高一级网络，一直到最高级的汇聚节点为止。

层次结构中，每个簇的形成常常是基于节点能量及与簇头的接近程度。簇头不仅要负责簇内信息的采集及融合处理，还要负责簇间的数据转发，它的可靠性和稳定性对于整个网络性能影响较大，信息的收集和处理也将消耗簇头的大部分能量。

1 LEACH协议

LEACH（Low Energy Adaptive Clustering Hierarchy）是为无线传感器网络设计的一种低功耗自适应的层次路由协议。它的基本思想是以循环方式随机选取簇头，将网络的能量负载平均的分配到每一个节点之上，从而降低能耗和延长网络生命周期。主要是通过随机选择簇头节点，平均的分担转发通信任务来实现。

LEACH算法中通过引入“轮（Round）”的概念，每轮由构建阶段（Set-up）以及稳态阶段（Stead-state）构成。构建阶段中节点被分成若干簇，且产生相应簇头；稳态阶段中数据从非簇头节点被发给簇头节点，在簇头节点上处理后发给汇聚节点。在簇的构建阶段，簇头节点的选择根据所需的簇头总数以及迄今为止每一个节点已成为簇头的次数来决定。具体选择办法是每一个节点选择0~1之间的一个随机数，如选的a小于某阈值T(n)，那这个节点就成为簇头节点。T(n)

T(n)= p[]1-r mod1[]p,n∈G0,其它情况[JY]（1）

公式1的p是簇头数与总节点数的百分比；r是当前轮数；G是前r轮中未

为簇头节点之后，广播自己成为簇头节点的消息，非簇头节点根据接收信号强度来确定要加入到哪个簇中，并且通知该簇头节点将成为它的一个成员节点。簇头回复一个TDMA消息给簇内的成员节点。稳态阶段，各节点在其时隙内把所监测到的数据发给

簇头，簇头节点将接收到的数据融合，最后把结果发给汇聚节点。

LEACH使用随机选簇头节点方式，避免了簇头节点消耗过多能量，采用数据融合方法来有效减少通信量，因此和一般的多跳路由协议和静态聚类算法相比，可将网络生命周期延长15%。但LEACH协议是假设所有节点都可以直接与簇头、汇聚节点通信，采用连续数据发送的模式及单跳路径选择的模式，所以在大范围监测应用中是不适合的，即使是在小规模网络中，距离汇聚节点远的节点由于大功率通信，也会导致生存时间比较短；并且动态地分簇也带来了拓扑变化和大量广播这样额外的开销，会耗费过多能量。

此外，LEACH假设簇内成员节点在属于它们的时隙内都有数据发给簇头，但实际情况有可能是节点只在监测到事件后才会发送。而且，LEACH中簇头节点都是随机的产生的，并不考虑节点剩余能量，有可能导致剩余能量少的簇头节点的能量尽早耗尽。

2 问题描述

LEACH是在无线传感器网络中最早提出的路由协议，并且是比较常用的分簇路由协议，LEACH协议可以使得所有节点在一个周期内都担任一次簇头，均衡的分担能耗，但簇头节点都是随机产生的，并不考虑节点地理位置，无法保证簇头节点均匀分布，有可能产生的大部分簇头节点集中在某一区域，或所产生的

簇头节点分布在离基站较远的区域的情况，而与基站距离较远时进行通信，将消耗过多能量，簇头可能会快速死亡，影响传感器网络的生命周期；另外，协议中簇头的选择没有考虑节点的剩余能量，有可能导致某些剩余能量小的节点能量提早的耗尽；并且，由于随机的选举簇头则簇头需负担的簇内节点数不同，个别簇内节点相对较多的簇头负担会过重，网络的负载平衡度随之下降。

3 助理簇头ASCH算法

许多分簇算法在节能方面都相当有成效，但是往往存在着簇头节点负担相对过重的问题，本文是从减轻簇头负担，以降低能耗这方面考虑，提出了助理簇头算法ASCH（Assistant Cluster Head），此算法以LEACH为基础，在其基础上进行改进，算法根据簇头节点的剩余能量，簇头距离基站的远近以及簇内成员节点数目等因素产生阈值公式，来确定是否需要在簇内产生助理簇头ASCH，所选择的助理簇头负责转发本簇簇头的数据给基站，起到一个转发数据之功能，以此来分担簇头节点的负担，均衡能耗；然后，在需要产生助理簇头的簇内的非簇头节点中选择ASCH的时候，根据各成员节点发送数据的能耗以及它们自身的剩余能量情况，选择出合适的节点成为本簇的助理簇头ASCH。

3.1 网络类型说明

传感器节点随机的分布于一个正方形区域内，对该传感器网

络假设如下：①每一个节点都有唯一ID，且节点初始能量相等；

②传感器节点部署后，不会随时间推移而移动；③基站位于离传感器区域较远的地方；④每一个节点都能与网络中其他任一个节点通信，也能与基站直接通信；⑤节点可根据接收信号强度计算它到发射点的近似距离。

3.2 ASCH的产生阈值

在网络的部署阶段，基站需向网内广播信号，每一个节点在接收到此信号之后，由接收信号强度来计算它与基站的近似距离。算法仍采用LEACH算法构建阶段的簇头节点选择及成簇的方式，先是产生出簇头节点并形成簇，然后再产生助理簇头。而关键首先考虑的问题是要在哪些簇内产生助理簇头，那么助理簇头ASCH的产生从3个方面来考虑，即簇头节点的剩余能量、簇头与基站的距离，及其簇内成员节点的数目。一般情况下，在簇头剩余能量较少，离基站较远，以及簇内成员节点较多的簇内需产生助理簇头ASCH。由此，可定义产生助理簇头ASCH的阈值T-{AS}

T-{AS}=c•E-{re}[]E-{max}•d-{max }-d-{(c,b)}[]d-{max}•N-{total}-N-i[]N-{total}[JY]（2）

其中，0