基于剩余能量与最小邻近簇半径的成簇算法

张作锋　刘三阳

摘 要：针对LEACH算法在选举簇首时没有考虑节点的剩余能量，并且簇首的分布不均匀，簇内节点与簇首采取单跳通信，从而影响网络生命期的问题，提出了利用剩余能量和最小邻近簇半径调整节点成为簇首的概率，并在簇内对部分节点采取多跳通信的成簇算法。仿真结果表明，该算法有效延长了网络生命期，均衡了簇首的分布，并且改善了簇内的结构。

关键词：簇首；网络生命期；成簇算法；剩余能量

中图分类号：TP393文献标识码：B

文章编号：1004-373X(2009)03-004-03

Clustering Algorithm Based on Residual Energy and Least Adjacent Clustering Radius

ZHANG Zuofeng,LIU Sanyang

(Xidian University,Xi′an,710071,China)

Abstract：As for the problem of LEACH clustering algorithm not considering the residual energy of nodes when selecting cluster heads,and the distributing of the heads not uniformity,members of the cluster communicating with the head by one-hop,which impacts lifetime of the network.A clustering algorithm is proposed which adjusts the probability of becoming cluster head by residual energy and least adjacent clustering radius,and takes multi-hop communicating for some nodes.The results of simulation prove that this algorithm can prolong the lifetime of network and balance distributing of the heads and improve structure of the members of cluster.

Keywords：cluster head;lifetime of network;clustering algorithm;residual energy

0 引 言

无线传感器网络(Wireless Sensor Networks,WSN)由部署在监测区域内的传感器节点组成，它通过无线通信的方式形成一个网络系统，在军事国防、灾难预警、环境控制、信息通信等各个领域都有着十分广泛的应用［1］。传感器节点体积小，能量有限，处理能力低，如何充分利用有限的能量，提高网络生命期是传感器网络面临的首要任务。

人们基于节能的考虑，提出了各种各样的拓扑控制算法。根据网络拓扑结构划分为平面算法和分簇算法［2］。平面拓扑控制算法中，各节点地位相同，通过功率控制简化网络拓扑结构，从而减少冲突、干扰，达到节能的目的。典型算法有COMPOW［3］，LMA和LMN［4］等。分簇算法是无线传感器网络节省能量，延长网络生命期的有效方法。节点分簇的主要思想是根据某种规则选择出一些节点成为簇首，在剩余节点中继续按某种规则选择节点加入簇首，形成簇。

典型的分布式簇首选取算法有LEACH(Low-Energy Adaptive Clustering Hierarchy)［5］，HEED(Hybrid Energy Efficient Distributed Clustering)［6］和DCHS(Low Energy Adaptive Clustering Hierarchy with Deterministic Cluster-Head Selection)［7］等。LEACH算法中，所有节点轮流充当簇首，网络周期性地进行簇首选举，每个周期称为一轮(round)。在每轮中，各节点独立运行公式产生一个数，再生成一个随机数，通过两个数的比较来判断节点是否当选簇首。在每轮中，所有簇首选举后，进入稳定工作阶段。HEED算法中，簇首的选择主要依据主、次两个参数。主参数依赖于节点剩余能量，用于随机选取初始簇首集合，具有较多剩余能量的节点将有较大的概率暂时成为簇首，而最终该节点是否成为簇首取决于剩余能量是否比周围节点多得多；次参数依赖于簇内通信开销。DCHS算法针对LEACH算法中的不足，综合考虑节点当前能量和阈值对簇首选取的影响。

针对LEACH算法的不足和文献只考虑剩余能量的不足，提出了基于剩余能量和最小邻近簇半径的成簇算法(Based on Residual Energy and Least Adjacent Clustering Radius,ECR)，并对簇内结构合理化。通过对LEACH算法的修改，使得最小邻近簇半径小的节点当选簇首的概率降低；剩余能量大的节点当选簇首的概率增大，并与能量消耗模型结合，以降低能量消耗为目的，改善簇内拓扑结构。通过与LEACH算法的比较，仿真结果表明，ECR算法延长了网络生命期，均衡了簇首能耗负担，簇首分布较均匀，簇内结构更加合理。

1 基本概念及相关知识

1.1 传感器网络生命期

根据服务类型的不同，传感器网络生命期的定义也不相同。这里定义从节点部署开始到第一个节点死亡为止。

1.2 最小邻近簇半径

在LEACH算法中，节点依据概率和一个阈值来决定是否成为簇首节点。假设已经选择了m个簇首，当选举第m+1个簇首时，要考虑当前节点到m个簇首的最小距离R(i)。这个距离定义为最小邻近簇半径。

用公式表示为:

R(i)=min1≤j≤mi≠j{dist}(1)

其中：node(i)为节点i；C(j)为簇首节点j；dist为欧氏距离。

1.3 LEACH算法

在LEACH算法中，对每一个节点i设定了一个阈值T(i):

T(i)=p1-pmod(r,1/p),i∈G

0,其他(2)

其中：p为簇首节点占网络节点总数的百分比；r为当前轮数；G表示网络中最近1/p轮未当选簇首的节点的集合。

LEACH算法如下：

设有n个节点：

Step1:r=1:rmax(rmax为最大轮数值);

Step2:对于node(i)∈G,根据式(2)算出T(i)，node(i)麲，则T(i)=0;

Step3:对于node(i)产生一个0~1之间的随机数rand(i);

Step4:比较rand(i)与T(i)，若rand(i)

Step5:若i>n即本轮簇首选举完成，进入稳定工作阶段;

Step6:若r

1.4 能量消耗模型

这里采用文献［9］所采用的无线信道模型及其能量公式。发送方传输l比特信息到距离为d的接收方时，发送能量开销为：

ETx(l,d)=lEelec+lεfsd2,d

lEelec+lεmpd4,d≥do(3)

其中，do为环境因素决定的一个常数；Eelec为传感节点电子能量消耗；εfs为自由空间无线电子信号放大所消耗能量；εmp对应于多径衰落信道。即：当节点间距离d

接收方接收l比特的信息,需要接收能量开销为：

ERx(l)=lEelec(4)

2 ECR算法

2.1 簇首选举的改进

由于LEACH算法没有考虑到节点剩余能量的影响，并且随机选取簇首使得其分布不均匀。考虑修改式(2)和每个节点相应的随机数(rand)，使得能量和最小邻近簇半径对于簇首选举的概率都有所影响，则对于每个节点i有一个新的阈值：

T(i)=p1-pmod(r,1/p)flag,i∈G

0,其他(5)

其中：

flag=exp(R(i)/Rd)-1)， R(i)≠0

1，其他(6)

由式(5)和式(6)知，R(i)越小，则T(i)越小，即当前节点距离某个簇首的距离小于一个阈值Rd，则其成为簇首的可能性就降低。

根据剩余能量的大小，对于rand的修改式如下：

rand(i)=rand(i)exp(7)

其中：rand(i)为对于节点i所产生的随机数；E(i)为节点i的剩余能量；E0为节点的初始能量。由式(7)知，节点剩余能量越大，rand(i)越小，则其值小于阈值T(i)的可能性越大，所以剩余能量越大的节点当选簇首的概率也就越大。

2.2 簇内结构的改进和ECR算法

由于在LEACH算法中，簇内节点与簇首单跳通信。此时，有部分节点与簇首距离大于式(3)中的do值，考虑让这部分节点采取多跳通信，让其与簇内最近成员节点通信，则可降低网络能量消耗，减轻簇首负担，均衡节点能量消耗。

由于概率的影响，某轮可能没有节点充当簇首，故设定簇首总数为num，使得每轮中的簇首数目大于num值。设节点数为n，下面给出ECR算法：

Step1:r=1:rmax(rmax为最大轮数值);

Step2:对于node(i)∈G,根据式(5)算出T(i)，node(i)麲，则T(i)=0;

Step3:对于node(i)，按式(7)产生一个0~1之间的随机数rand(i);

Step4:比较rand(i)与T(i)，若rand(i)

Step5:若i>n且num≥4，则本轮簇首选举完成，进入稳定工作阶段；此时节点发送信息时的能量消耗按式(3)计算；节点接收信息时的能量消耗按式(4)计算；节点与簇首通信，簇首与基站通信；转Step7。

Step6:若i>n且num<4，则按rand(i)的取值由大到小选取对应的节点为簇首，直到num=4，本轮簇首选举完成，进入稳定工作阶段；转Step7。

Step7:若r

3 仿真实验

3.1 参数设定

由Matlab 7.1进行仿真实验，在区域为100 m的正方形范围内，对100个节点进行仿真。其他参数设置如下：

基站坐标：(50 m,50 m)；p=0.05；Eo=0.5 J；

Eelec=50 nJ/b；εfs=10 pJ/b/m2；

εmp=0.001 3 pJ/b/m4；l=4 000 b;do=45 m;

Rd=xm2=1002；由ECR算法有如下仿真结果，如图1，图2所示。

图1 ECR算法的一个实例图

3.2 仿真结果分析

由图1、图2可看出簇首分布较均匀。当所分簇数目较少时，由于簇首能耗负担过大，则簇内部分节点采取了多跳通信，即图2所示。

由表1知ECR算法有效延长了网络生命期，降低了网络的能量消耗。

图2 ECR算法改变簇内结构的一个实例图

表1 不同的初始能量对应的生命期

Eo算法生命期 /轮

0.5J

LEACH783

ECR828

1.0J

LEACH1529

ECR1801

4 结 语

按照针对LEACH算法的不足，提出了ECR算法，结合节点剩余能量和最小邻近簇半径调节节点选择簇首的概率，通过对能量模型的分析，对簇内部分节点采取多跳通信。仿真结果表明，ECR算法有效地提高了网络生命期，均衡了网络中节点的能量消耗，促进了簇首分布均匀化。

参考文献

［1］Cui L,Ju H L,Miao Y,et al.Overview of Wireless Sensor Networks［J］.Journal of Computer Research and Development,2005,42(1):163-174.

［2］孙利民.无线传感器网络［M］.北京:清华大学出版社,2005.

［3］Narayanaswamy S,Kawadia V,Sreenivas R S,et al.Power Control in Ad-Hoc Networks:Theory,Architecture,Algorithm and Implementation of the COMPOW Protocol.In:Proc.of the European Wireless Conf..Florence,2002:156-162.

［4］Kubisch M,Karl H,Wolisz A,et al.Distributed Algorithms for Transmission Power Control in Wireless Sensor Networks.Proc.of the IEEE Wireless Communications and Networking Conf..New York:IEEE Press,2003:16-20.

［5］Heinzelman W,Chandrakasan A,Balakrishnan H.Energy-efficient Communication Protocol for Wireless Wensor Networks［A］.Proceedings of the Hawaii International Conference on System Sciences.Piscataway.IEEE,2000.

［6］Younis O,Fahmy S.HEED:A Hybrid,Energy-efficient,Distributed Clustering Approach for Ad Hoc Sensor Networks［J］.IEEE Trans.on Mobil Computing,2004,3(4):366-379.

［7］Handym J,Haasem,Timmerma-NN D.Low Energy Adaptive Clustering Hierarchy with Deterministic Cluster-head Selection［A］.Proceedings of the 4th IEEE Conference on Mobile and Wireless Communications Networks.Stockholm:IEEE Communications Society,2002:368-372.

［8］张怡,李云,刘占军,等.无线传感器网络中基于能量的簇首选择改进算法.重庆邮电大学学报,2007,19(5):613-616.

［9］Heinzelman W,Chandrakasan A,HBalakrishnan.An Application Specific Protocol Architecture for Wireless Microsensor Networks［J］.IEEE Trans.on Wireless Communications,2002,1(4):660-670.

作者简介

张作锋 男，1982年出生，黑龙江人，硕士研究生。主要研究领域为无线传感器网络。

刘三阳 男，1959年出生，陕西西安人，教授，博士生导师。主要研究方向为最优化计算方法，网络优化，无线传感器网络等。

注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。