LEACH协议簇头选择算法的改进与研究

章春华，陈宏伟

（湖北工业大学计算机学院，湖北 武汉430068）

无线传感器网络（WSN），在一个区域内布置无限个能量有限的传感器节点，形成一个无线网络且每个节点能够自行采集区域中的信息，发送站基站节点对信息进行处理.

由于无线传感器自身的局限性［1］，如：1）节点的分布广泛并且数目很多，每个节点想要维护整个网络的信息是不可能的；2）节点基本上采用电池供电，能量有限且存储空间有限；3）网络节点如果消耗能量过大，则容易造成无效节点，从而导致网络的部分瘫痪，无法有效传递信息.因此，传统的有限网络中的一些路由算法以及Ad Hoc网络中常用的DSDV、AODV等路由算法由于没有考虑到无线传感器网络节点的局限性，并不适合自身局限性过多的传感器网络.设计新的无线传感器路由协议势在必行.

随着科技的不断发展，大量新的路由协议被提出，平面路由协议和层次路由协议是现有的比较流行的两类传感器路由协议.

典型的平面路由协议［2］有：DD、SAR、SPIN 等，其优点在于协议简单，所有节点的地位平等，具有良好的健壮性.平面路由的最大缺点是网络中没有管理节点，难以对通信的资源进行优化管理，同时节点协同工作的算法复杂，不利于网络的动态拓扑.

层次路由协议［3］，将传感器网络中的节点按照某种算法分成一些小的集合，每一个集合都有一个领导节点和多个非领导节点，领导节点不断地收集非领导节点传递过来的信息并将信息传递给上一级的节点，层次路由协议也有很多不足，需要不断改进，使路由机制达到最大的利用率.

本文提出对经典层次路由协议LEACH进行进一步的优化，重点在对LEACH簇头选择算法的改进，从而改进整个无线网络，提高网络的生命周期和数据传输成功率.

1 Leach算法概述

LEACH （Low Energy Adaptive Cl ustering Hierarchy）是典型的分层分簇路由协议.其基本思想是：以循环的方式随机选择簇首节点，将整个网络的能量负载均衡平均分配到每个传感器节点中，从而达到降低网络能源消耗、提高网络整体时间的目的.

LEACH在运行的过程中不断地循环执行簇的重构过程，每个簇重构的过程可以用“轮”的概念来描述.每个轮可以分为两个阶段：簇的建立阶段和传输数据的稳定阶段.簇的建立过程又分为4个阶段：簇首节点的选择、簇首节点的广播、簇的建立和调度机制的生成［4］.

簇首节点具体的选择办法是：传感器网络会根据某些因素计算出一个阈值，那么当每一轮选举簇首节点的时候，每个传感器节点会随机在0～1之间选择一个值，如果传感器节点选择的值小于阈值

那么这个节点会被选为簇首节点.式（1）中，p是网络中簇头数和总节点数的百分比；r是当前的选举轮数；G是最近1／p不是簇头的节点集.

选定簇首节点后，将簇首节点的信息广播到整个网络.网络中的其他节点根据接收信号强度来决定加入哪个簇，并通知相应的簇首节点，完成了簇的建立.最后，簇首节点采用TDMA方式为簇中的每个节点分配向其传输数据的时间片.

数据的传送是在稳定阶段开始的.传感器节点将数据传送到簇首节点后，簇首节点对簇中所有节点所采集的数据进行信息的融合，然后传送给BS（基站）.

2 簇头选择算法的改进

2.1 算法的提出

研究表明，簇头节点的个数对网络的生存周期和网络的总体能耗有很大影响.原有的LEACH协议簇头选择算法依赖于传感器节点所产生的随机数，随机数的不稳定性导致传感器节点数量和分布的区域位置都呈现极不稳定的状态.计算出来的最优簇头数目Kopt是一个期望值，在现实的传感器网络环境中，簇头的个数可能会远远偏离期望值Kopt，选出的簇头个数过少时，分层分簇的概念就没有了，簇首节点也会因为能耗问题提前死亡，无法平衡整个网络的能耗；反之，簇首数目过多，因为簇首节点要和基站进行数据的传输，增大了网络的节点的功耗.

从上面的分析可知：如何得到最优的簇首数是协议的关键，其思想是在选择最优簇首的同时保证节点的能耗最小，并且，整个网络的能量损耗均匀地分布在所有节点上.

本文将簇建立阶段产生的能耗考虑到整个网络的能耗中去，提出了一个新的最优簇头数目选择算法KoptG.

2.2 算法的详细描述

2.2.1 最优簇头数推导 有N个节点分布在M×M的区域内，假设最优的簇头数目为K，代表传感器节点被划为K个簇，每个簇内有N／K个节点，其中，N／K－1个非簇首节点，一个簇头节点，传感器网络中的每个节点都有相同的处理能力和通信能力，且每个节点的发射功率是可控制的，节点每次传送1 bit的数据.

在笔者提出的最优簇首数目算法中，整个网络的能耗分为两个部分.

第一部分：选择阶段的能耗

簇头节点的能耗

式（2）中，第一个大括号表示簇头节点传送广播信息的能耗；第二部分是同一个簇内节点接收数据的能耗；第三部分是簇首节点告知非簇首节点TDMA和CDMA消息的能耗.

非簇首节点的能耗式（3）中，第一部分是接收簇首广播信息消耗的能耗；第二部分是相应的簇首节点，传输消息的能耗；第三部分是接收簇首节点确认消息的能耗.

第二部分：数据的传送阶段.

在数据的传输阶段，一个簇头节点的能耗

非簇首节点将数据传送到簇首节点的能耗

因此，在一个簇内消耗的能耗

式中，第一部分是簇头选择消耗的能耗；第二部分是数据传送消耗的能耗.

那么，K个簇消耗的总能耗为：将式（5）代入式（6）中，并对 K求导，即得最优簇头数目

2.2.2 LEACHG算法思想 通过以上的推导，得到最优的簇头数，下一步提出新的簇首选择算法LEACHG.思想是：利用距离关系将所有节点群组化，使得群组的数量和算法中期望的簇头个数相同，这样导致簇头的实际个数与期望的簇头个数相同.

无线传感器网络区域内的节点按下面的步骤被分为组，且成组的个数与最优簇头的个数相同，具体的实现方法（图1）如下：

图1 成组算法流程图

1）根据最优簇头个数Kopt，决定成组的个数k；

2）基站（BS）广播一条很短的信息包；

3）网络中的节点一旦接受到基站发送来的信息，就将自己的当前信息，如位置和节点的ID号，回送给基站；

4）根据节点信息回送给基站的时间片，基站选择一个信息返回时间最长的节点作为组头（Group Head），然后基站将组头的ID号，组内的成员个数发送给网络中的每个节点；

5）组头节点再发送一个短信息包给WSN；

6）当网络中的节点收到短信息后，反馈自己的节点信息；

7）组头节点根据节点反馈信息时间片的长短，选取时间片最快的－1个节点作为自己的组内成员，同时组节点再发送一个信息包括组ID以及组内节点的ID号给WSN，一旦一个节点加入到组内，这个节点就不能再加入别的组内；

8）组头（GH）节点根据节点反馈的信息，选择一个反馈时间片最长的节点作为下一个组头节点，同样发送组头ID和组ID号给WSN.

重复5－8阶段，直到组的个数与Kopt相等.

当达到与Kopt相等的组的个数后，各个组内的成员就根据相应的簇头选择算法选出簇头，然后进入数据的传输稳定阶段.

3 仿真结果与分析

本文的仿真基于NS2仿真平台.首先，设置相关的实验环境进行仿真，得到有用的leach.energy和leach.alive文件，leach.alive和leach.ener gy文件详细记录了仿真的过程以及每一节点的死亡、存活，节点能耗；然后，用提供的awk语言编写提取leach.alive和leach.energy文件信息数据的脚本文件；最后，利用NS自带的画图软件gnuplot生成图表，对生成的图表进行分析，比较改进后的LEACH协议.

仿真的过程中，为了更准确地比较提出算法的优劣，采用完全相同的参数和节点分布文件同时模拟LEACH、LEACHG协议，本仿真采用的网络模型是一个在100 m×100 m的区域内随机地分布100个WSN节点，其部分实验参数设置：节点数，100；节点初始能量，2 J；仿真区域，100 m×100 m；信道带宽，1 Mb／s；发送／接收1bit能耗，50 nJ／bit；传输放大器能耗，10 pj／bit／m2；数据融合能耗，50 nJbit／signal；数据包大小，100 bytes.

图2 网络生存周期

图2显示了两种协议的网络生存周期.从图中的数据可以看出，第一个节点死亡时间LEACHG要晚于LEACH协议，当全部节点死亡时，LEACHG比LEACH多运行了几轮.新的LEACHG协议将簇首阶段的能耗考虑进去，并通过成组算法得出了最优的簇首数，导致传感器节点的能耗能更加均匀地分布到所有的节点中去，避免了单个节点因为能量的消耗过大而过早地死亡，从而影响了网络的生存周期.本实验只设置了100个节点，当传感器节点更多，WSN的规模更大时，LEACHG的效果会更佳.

4 结论

本文将簇首选举阶段的能耗计算到整个网络的能耗中去，得出了最优簇首个数的计算公式，而后提出了成组的簇首选择算法LEACHG，并在NS2仿真工具上进行了仿真.分析的结果表明，相比于原来的LEACH协议，LEACHG能够有效地平衡网络中的能耗，提高整个网络的生存周期.

［1］Al Karaki J N，Kamal A E.Routing techniques in wireless sensor networks［J］.IEEE Wireless Communications，2004，11（6）：6－28.

［2］Mhatre V，Rosenber g C.Design guidelines for wireless sensor networks：communication，clustering and aggregation［J］.Ad Hoe：Networ ks，2004，2（1）：45－63.

［3］Heinzel man W R，Chandrakasan A，Balakrishnan H.An applicationspecific protocol for wireless microsensor networks［J］.IEEE Transactions on Wireless Communication，2002，1（4）：660－670.

［4］Wendi B，Heinzel man W R，Balakrishnan H.An application specificpr otocol architecture for wireless micr osensor networ ks［J］.IEEE Transactions on Wireless Communications，2002，1（4）：660－670.

［5］Jan F，Akyildiz，Weilian S，etal.Asuivey on r outing protocols for wireless sensor networks［J］.IEEE Communicaitons Magazine，2004，40（8）：102－114.

［6］Li Qing，Zhu Qingxin，Wang Mingwen.Design of distribute denergy efficient clustering algorithm for wirelesssensor networ ks［J］.Co mputer communication，2006（29）：2 230－2 237.