基于节点剩余能量分布的簇头选择算法

李 龙，刘建明，李宏周，彭智勇

（1.桂林电子科技大学电子工程与自动化学院，广西桂林541004；2.桂林电子科技大学计算机科学与工程学院，广西桂林541004）

0 引 言

无线传感器网络［1］是由大量随机部署的传感器节点通过无线电通信构成的自组织网络，目的是感知、监测、采集和处理网络覆盖围内的相关环境参数，并最终传递给观察者。网络中的传感器节点拥有的能量十分有限，因此，在不影响网络整体功能的前提下，尽可能高效地利用节点的能量以最大限度延长网络的生存时间成为无线传感器网络设计中的核心问题。为此，Wendi Rabiner Heinzelman等人在网络路由层面提出了LEACH（low energy adaptive clustering hierarchy）算法［3，4］。

LEACH协议将整个网络划分为逻辑上的层次结构，按功能将网络中的节点区分为簇头节点和普通节点。其基本思想是周期性地随机选择部分节点成为簇头节点，负责收集其他节点发送的数据并与基站通信；其他普通节点按照通信距离的远近选择较近的簇头节点入簇，并在自己所属的时间片内将收集到的数据直接发送给本簇的簇头。由于簇头节点需要收集本簇内所有节点的数据，并进行数据融合以及发送给基站，使得此类节点的能耗较大、更容易死亡，因此在具体选择簇头的过程中应该充分考虑这一现象，力求将整个网络的能量消耗尽可能平均地分配到每个传感器节点，从而达到降低网络能源消耗、提高网络整体生存时间的目的。本文以LEACH协议为基础，提出了一种新的簇头选择算法，该算法在选举簇头的过程中考虑所有节点的剩余能量分布情况，并根据节点自身剩余能量将节点归类，不同类别的节点拥有不同的阈值T（n），即当选为本轮簇头节点的概率不同，最终使得网络中所有节点的能耗更加均衡。基于NS2的仿真结果表明，该算法可以更好平衡网络中各节点的能量消耗，在延长网络生存时间、提高网络数据吞吐量等方面都有比较好的表现。

1 LEACH路由协议

1.1 网络模型

按照节点的功能不同，LEACH协议将构成整个网络的节点分为3类:簇头节点、簇内节点、基站节点。其网络模型如图1所示，其中各种节点的详细属性设定如下［4，6］:

（1）基站节点的位置固定，原理监测区域，并且具有充足的能量供应，即研究中不考虑基站的能量消耗；

（2）除基站节点外，其他节点具有完全相同的物理结构、初始能量，并且能量供应有限；

（3）所有节点随机分布在监测区域内，并且节点是静止的；

（4）节点可感知自身的剩余能量；

（5）节点总是有数据要发送；

（6）相邻节点收集到的数据具有相似性，可以通过数据融合减少通信量；

（7）网络中的所有节点可以相互通信，且都使用单跳通信。

1.2 无线通信能耗模型

本文中在计算节点能耗的时候，使用的是文献［4］中提供的无线通信能耗模型，即一阶无线电模型，如图2所示。

图1 LEACH协议网络模型

图2 一阶无线电模型

该模型中，数据发送端节点的能耗包含发送电路能耗、放大电路能耗，数据接收端节点的能耗只包含接收电路能耗。

本文中设定发送电路以及接收电路的能耗为Eelec＝50nJ/bit，放大电路的能耗为εamp＝100pJ/bit/m2。

据此便可求得数据发送端节点的能耗为ETx（k，d）＝Eelec＊k＋εamp＊k＊d2；数据接收端节点的能耗为ERx（k）＝Eelec＊k。

其中，k为节点间传送的数据量，单位为bit；d为节点间通信距离。相较于数据发送、接收时的能耗，节点在闲置、休眠时的能耗可以忽略不计。

1.3 工作流程

LEACH协议定义了“轮（round）”的概念来细化网络的工作流程，如图3所示，一轮包括簇的生成和数据传输两个阶段［4］。

在簇的生成阶段，每个节点自主选择是否成为当前轮的簇头，若成为簇头则通过CSMA MAC协议以相同的传输能量向整个网络广播自己成为簇头的消息；其他非簇头节点根据接收到的多个广播消息的强度来决定加入哪个簇，并通过CSMA MAC协议将自己加入该簇的信息报告给相应的簇头；簇头节点收到所有的非簇头节点想要加入该簇的信息后，基于本簇内加入的节点数目创建TDMA调度，并通知簇内节点。在数据传输阶段，簇内节点在分配好的时隙内把采集到的数据发送给簇头，簇头对收集到的数据进行融合、压缩后转发至基站节点。

图3 LEACH协议的工作流程

为提高能量的利用效率，减少频繁分簇带来的能量消耗以及信息传递的延时，每一轮中的数据传输阶段要远远长于簇的生成阶段。

从LEACH协议的工作流程我们也可以看出，在每一轮中，只有在簇的生成阶段选择合适的簇头，并以簇为单位对网络进行合理的分割，才能在接下来的数据传输阶段提高网络的整体效率，并最终延长网络的生存时间。

2 随机簇头选择算法

在LEACH协议中提供了一种簇头节点的选取原则:在簇的生成阶段，每个节点都拥有阈值T（n），同时会生成一个（0，1）之间的随机数，如果该随机数小于阈值T（n），则该节点当选为本轮中的簇头。节点阈值T（n）的计算公式如下

其中，p是期望的簇头数在所有节点中占的百分比，r是轮数，G是最近1/p轮中未当选过簇头的节点集合。

关于LEACH协议中的簇头选择算法，科研人员已经进行了许多探索，在文献［5］中提出了一种基于节点剩余能量的簇头选择算法，该算法更改了簇头选择过程中的节点阈值T（n）的计算方法，添加了乘性因子E＿current/E＿max，得出新的计算公式

其中，E＿current是当前节点的剩余能量，E＿max是当前网络中节点剩余能量的最大值，p、r、G的含义与前面相同。

显而易见，上述式（2）中之所以添加乘性因子E＿current/E＿max，是将所有节点的剩余能量默认为服从线性分布，目的是使得剩余能量大的节点，有更大的概率当选为本轮簇头。但是通过仿真可以发现，某一时刻网络中所有节点的剩余能量之间没有必然的规律（如图4所示），可视为随机分布，在这种情况下，若求取阈值的过程中只考虑两个节点的剩余能量E＿current、E＿max不足以体现整个网络的能耗情况，节点间能量消耗的均衡性不够理想。

图4 节点剩余能量分布

3 基于节点剩余能量分布的簇头选择算法

为更好的解决上面提到的问题，使得节点间的能量消耗更加均衡，本文在充分考虑节点剩余能量的分布的情况下，结合节点自身的剩余能量情况，提出基于节点剩余能量分布的簇头选择算法。

网络运行过程中，LEACH协议会周期性地、不间断地进行簇头的选择，同样的，新算法也会周期性地要求基站进行以下工作:收集网络内节点的剩余能量信息、求取剩余能量平均值E＿average，并统计剩余能量高于该平均值的节点的数量num＿HaveMoreEnergy，此类节点被视为高能量节点，反之视为低能量节点；在统计完成后，基站会将统计结果面向全网广播，其中统计信息中含有以下数据:所有节点的平均剩余能量、高能量节点数、理想簇头数等。

新算法的核心思想就是基站周期性地收集网络的剩余能量情况并获得统计信息，若统计信息中高能量节点的数量大于理想簇头节点数num＿clusters，则簇头节点全部从高能量节点中选出，否则，num＿HaveMoreEnergy个高能量节点全部担任簇头，有（num＿clusters－num＿HaveMoreEnergy）个簇头节点按照某一特定概率从低能量节点中选出。

对于每一个节点来说，该节点接收来自基站的数据广播，判断网络整体能耗情况并结合自身剩余能量情况生成阈值T（n），然后与随机数RandomRange｛0 1｝相比较，判定自身是否担任本轮中的簇头，图5为该簇头选择算法的具体流程图。

图5中T（n）＿式（1）的具体公式为

图5中T（n）＿式（2）的具体公式为

图5 流程

4 仿真分析与比较

4.1 仿真参数设置

为了评估本文中提出的簇头选择算法的合理性以及有效性，并在节点能量消耗、网络数据吞吐量以及网络存活时间等方面与其他研究人员提出的簇头选择算法相比较，本文以NS2为仿真平台分别对LEACH中的簇头选择算法、文献［5］中提出的簇头选择算法、本文中提出的基于节点剩余能量分布的簇头选择算法进行数十次仿真，并对仿真结果进行分析比较。仿真场景中详细的参数设置见表1。

表1 仿真参数设置

4.2 仿真结果

本文基于相同的仿真场景，分别对前文中提到的3种簇头选择算法进行了仿真。仿真主要对比了将不同的簇头选择算法应用到WSN时，网络在生存时间、数据吞吐量、节点生存时间、节点平均能耗等多个方面的表现。

4.2.1 网络生存时间

由于节点能量受限，网络生存时间成为衡量该网络性能的指标之一。为此，本文分别对应用不用簇头选择算法的网络进行10次仿真，并对仿真数据进行综合分析，得出图6中的仿真结果对比图。

在仿真的过程中，如果存活节点的数量小于理想簇头节点数，即认为网络死亡，仿真结束。当网络中分别应用LEACH协议中的簇头选择算法（式（1））、文献［5］中介绍的簇头选择算法（式（2））、本文中提出的基于节点剩余能量分布的簇头选择算法时（图5），网络生存时间的平均值分别为551s、608s、653s，可见本文中提出的新算法在提高网络的生存时间方面有比较大的优势。

4.2.2 存活节点数

图7中绘制的是10次仿真过程中首个死亡节点的出现时间对比图。图8为10次仿真过程中节点平均存活数。从图7中的仿真结果得出，分别将3种不同的簇头选择算法（排序同上）应用到网络中的时候，首个死亡节点出现时间的平均值分别为370s，400s，410s。从图8可以看出，若网络在簇头选择过程中使用本文中提出的新算法，其存活节点数在整个网络的生存时间内都明显高于应用其他簇头选择算法的网络。

4.2.3 节点的平均能耗

随着仿真过程的进行，节点的能耗不断增加，若能耗大鱼2J，则节点死亡。图9中绘制的是整个仿真过程中，随着网络运行时间不断加长，所有节点的平均能耗情况。从图中可见，由于应用了新的簇头选择算法，网络中节点的平均能耗明显降低，能量利用更加均衡合理，相应地延长了网络的生存时间。

4.2.4 网络数据吞吐量

本文不仅在网络生存时间、节点能耗方面对新的簇头选择算法进行了分析，还对比了在应用不同分簇算法时网络的数据吞吐量，如图10所示。本文中统计的数据吞吐量是在网络死亡后，基站节点所成功接收到的全部数据量。分别对应用不同簇头选择算法（排序同上）的网络进行10次仿真，得出网络数据吞吐量的平均值分别为44720bit、45960bit、47420bit。显而易见，本文中提出的簇头选择算法在提高网络的数据吞吐量方面表现尤为突出。

图7 首个死亡节点的出现时间

图8 存活节点数

图9 所有节点的平均能耗

图10 网络数据吞吐量

综合以上仿真结果可见，相比于其他的簇头选择算法，本文中提出的基于节点剩余能量分布的簇头选择算法在平衡节点能耗、延长网络生存时间、提高网络数据吞吐量多个方面都有比较大优势。

5 结束语

本文中提出了一种基于节点剩余能量分布的簇头选择算法，并使用NS2仿真软件对该算法进行了验证，通过仿真数据可以发现，相比于其他簇头选择算法，该算法可以更好平衡网络中节点的能量消耗，在延长网络生存时间、提高网络数据吞吐量等方面都有比较好的表现，与仿真前的设想一致。

不可忽略的是，该算法的实现需要节点周期性地获取自身的剩余能量并上传到基站，基站统计分析全局的能量信息之后再广播给所有节点，这会增加网络中控制信息的发送量，给数据的传递带来延时，这是接下来需要进一步改进的地方。除此之外，LEACH协议在其他方面还需进一步研究，例如，簇头的分布位置不合理、簇的规模不均匀等。

［1］Liu X.A survey on clustering routing protocols in wireless sensor networks［J］.Sensors，2012（12）:11113－11153.

［2］Meenakshi Sharma，Kalpana Sharma.An energy efficient extended LEACH（EEELEACH）［C］//International Conference on Communication Systems and Network Technologies，2012:377－382.

［3］ZHANG Yabin.Research on layered－clustering routing and simulation platform for underwater sensor network［D］.Guilin:Guilin University of Electronic Technology，2012（in Chinese）.［张亚斌.水下传感器网络分层－分簇路由与仿真平台研究［D］.桂林:桂林电子科技大学，2012.］

［4］DAI Sisi，TANG Junhua，ZHANG Aixin.Gossiping－based directed diffusion for wireless sensor network［J］.China Infor－mation Security，2010（4）:45－49（in Chinese）.［戴思思，唐俊华，张爱新.基于Gossip算法的定向扩散协议研究［J］.信息安全与通信保密，2010（4）:45－49.］

［5］HUANG Jiayi，CHENG Lianglun.Balanced energy clustering algorithm of WSN which cluster region were adjusted adaptively［J］.Application Research of Computers，2012（29）:4276－4279（in Chinese）.［黄加异，程良伦.一种聚类区域自适应调整的WSN能耗均衡分簇算法［J］.计算机应用研究，2012（29）:4276－4279.］

［6］Hyunsook Kim.Cluster head selection scheme for minimizing the changes of the cluster members considering mobility in mobile wireless sensor networks［C］//ICACT，2013.

［7］Deng S，Li J，Shen L.Mobility－based clustering protocol for wireless sensor networks with mobile nodes［J］.Wireless Sensor Systems，2011（1）:39－47.

［8］Andrey K，Ahmed S.Prediction－based clustering algorithm for mobile wireless sensor networks［C］//International Conference on Advanced Communication Technology.Phoenix Park，2012:1209－1215.

［9］YANG Ming，XU Ruichen，JIANG Ting.A cluster head selection mechanism based on historical information［J］.Communications Technology，2011，44（11）:97－99（in Chinese）.［杨明，许瑞琛，蒋挺.一种基于历史信息的簇头选取机制［J］.通信技术，2011，44（11）:97－99.］

［10］HUANG Tao，YANG Ning，ZHANG Zhijiang，et al.Analysis and simulation of LEACH and its evolution routing protocols［J］.Radio Communications Technology，2009（35）:4－7（in Chinese）.［黄韬，杨宁，张智江，等.LEACH及其演进路由协议分析与仿真［J］.无线电通信技术，2009（35）:4－7.］

［11］Asaduzzaman，Hyung Yun Kong.Energy efficient cooperative LEACH protocol for wireless sensor networks［J］.Journal of Communications and Networks，2012，12（4）:358－365.

［12］TIAN Wei，YANG Zhen.Research on WSN geographic routing algorithm［J］.China Communications，2010，7（3）:153－157（in Chinese）.［田炜，杨震.WSN地理位置路由算法研究［J］.中国通信，2010，7（3）:153－157.］