基于LEACH的无线传感器网络分簇路由协议的改进研究

齐世霞 薛小伟

（1.延安大学数学与计算机科学学院 陕西省延安市 716000 2.延安大学附属医院 陕西省延安市 716000）

1 引言

无线传感器网络是当前众多学科研究的热点，是实现数据的采集、处理和传输于一体的综合型智能网络，目前正处于蓬勃发展的阶段，随着其应用越来越广泛，对诸多领域都具有巨大影响。无线传感器网络由微传感器节点组成，这些节点既可以获取信息数据，也可以进行网络中继。每个传感器节点都由传感器、微处理器以及无线收发机组成，传感器节点与节点之间互相紧密相连以获取物理数据。传感器节点通过片上微处理器完成复杂任务，通过无线收发机实现互连及数据传输。传感器节点一般都是非动态的，由能量有限的电池提供能源，从而导致网络拓扑在节点位置不变的情况下也可能会因为其能量管理操作而发生动态变化。在这种情况下，使传感器节点功耗最小并保持通信是最重要的，高能效机制的无线传感器网络相对于还依旧依赖电池的系统具有更长的生存周期。在无线传感器网络的网络协议栈中，网络层的研究最多，其路由协议的分类以及具体的解决算法主要分为以下四类，如图1 所示。

图1 ：WSN 路由协议分类

2 基于分层结构的无线传感器网络路由协议

基于分层结构的无线传感器网络路由协议在分层结构中组成簇，分簇算法将通信限制在局部区域且只向剩余的网络部分发送必要的信息，一组节点形成一个簇，簇成员之间通过簇头进行交互。无线通信的不稳定性和传感器网络的特点等这些问题阻碍了应用于WSN 中针对无线自组织网络的路由协议的发展。为了尽可能的降低能耗，使WSN 的生存周期更长，已经提出了许多基于分层结构的路由算法协议，主要包括以下几种常见算法：高效自治算法LEACH，执行过程按“轮”进行，每轮包括两个阶段，即簇的形成阶段和稳定工作阶段，由每个节点根据随机数自主决定是否当簇头，保证各个节点等概率的担任簇头；以节点地理位置为依据的分簇算法GAF，最初应用在Ad Hoc 网络中，采用虚拟单元格划分机制，根据地理位置信息将整个网络划分成很多虚拟小区域，每个小区域内定期选举一个簇头节点，簇头节点为正常工作状态，剩余节点为休眠状态，每个小区域内的节点互相协作；PEGASIS 算法提出了构造节点链来解决簇重叠区域的问题，链的创建采用贪婪算法，选择距离自己最近的邻居节点进行下一跳；混合能量效率分布式分簇HEED算法是，以节点的剩余能量作为首要因素，簇内的通信代价作为次要因素来进行簇头的选择和分簇，按轮进行，每轮包括分簇阶段和网络运行阶段；TEEN 算法采用多级分簇结构，簇内节点将采集到的数据传送给簇头节点，簇头节点对数据进行进一步处理后，再传送给比它高一级的簇头，层层递进，最终将数据传送到汇聚节点，通过设计设置硬门限和软门限两种门限值来提供基于响应的应用，以减少发送数据的次数；APTEEN 算法是在TEEN 算法基础上发展起来的，簇内节点采用时分复用的方式进行数据传输，通过设置软硬两种门限值确定发送数据的时间和频率；TopDisc算法是基于最小支配集模型提出的分簇算法，采用启发式的方法建立骨干网络拓扑，采用颜色标记理论来选择簇头节点，该算法可以在密集部署的传感器网络中快速的形成分簇，但在产生簇头时没有考虑剩余能量的问题；SOP 算法将网络中的节点分为两类，传感器节点是动态的并负责收集数据，路由节点是静态的用于形成主干网；EARSN 协议算法是基于三层体系结构的路由协议，由终端用户在网络运行前就对传感器节点进行分簇且簇头不受能量控制，算法依据两个节点间的能量消耗、延迟最优化等性能指标计算路径代价函数，簇头节点再以此作为链路成本选择最优路径；除了上述算法外，还有GEAR、SPAN、MECH 等分簇算法，各种基于分层结构的无线传感器网络路由协议的性能比较如表1 所示。

表1 ： WSN 路由协议的性能比较

武小年等通过定义节点的能量因子和位置均衡因子建立新的适应度函数，选择出优秀的候选簇头节点，之后再通过优化的自适应学习因子加快其位置更新速度；王宗山等提出一种基于人工蜂群算法的能量高效分簇路由协议，在簇头选举时通过定义能量因子、位置因子和向心率因子设计高效的适应度函数，在稳定传输时通过在每个簇头和基站间寻找合适路径并引入了轮询控制机制来平衡且降低网络能耗；赵东方等提出了基于路由树的分布式自适应动态多跳分簇路由协议DABMC，设置剩余能量和延迟时间来选择簇首，簇间路由为以sink 节点为根节点的动态路由树来选择下一跳；苟平章等通过AGNES 算法进行均匀分簇，然后根据剩余能量、节点与基站之间的距离以及两者的权重因子进行分布式簇头选举，并采用改进后的最短路径优先算法进行多跳路由；王海浪等通过对整个网络区域进行均匀分区优化以及改进综合节点的剩余能量、区域内平均能量、距离基站的距离等多个因素来作为判断是否选择成为簇头节点；张本宏等提出一种基于二分K-means 的均匀分簇算法UCOA，利用二分K-means 算法对整个网络均匀分簇，加入节点的剩余能量、距离因子对簇头选举阈值公式进行改进；王出航等提出一种基于改进遗传算法的WSN 信任感知安全路由方法，采用单个染色体编码进行簇头选择和路由搜索；胡黄水等提出一种结合近邻传播算法AP 和遗传算法的分簇路由协议EAPGA，根据剩余能量、节点间距离、节点到基站的距离以及节点中心度选择最优簇头，再通过簇头能耗偏差和遗传算法进行寻优；和煦等提出一种基于改进正弦余弦算法的分簇路由协议CRISCA，将正弦余弦算法和惯性权重因子进行结合，得到改进的正弦余弦算法进行最优簇头的选择；兰婷婷等设计了一种最优广域WSN 数据聚合模型ODAM，在无线接收器中进行节点间的计算，采用花粉算法FPA 对聚合模型进行优化来确保簇中能量的有效排列；赵小强等提出了一种基于模拟退火SA 算法和改进灰狼优化器GWO的HWSN 路由协议SA-MGWO，在选取簇时根据节点能量的异构性对节点定义不同的适应度函数来计算适应值，之后根据狼群与猎物的距离以及系数向量对该值进行动态更新，最后利用模拟退火算法选取最优簇集；余修武等提出了一种基于萤火虫算法优化模糊C 均值的WSN 路由算法FFACM,在分簇时采用萤火虫算法计算初始聚类中心，建立适应度函数选取簇首节点并动态更新，建立代价函数选择簇间多跳路由，降低簇首节点的负载；李蕾等提出一种基于证据理论加权融合的无线传感器网络路由算法，引入聚类分析算法进行分簇，之后后采用证据理论计算剩余能量、节点间通信距离、通信能耗的权值进行综合评价才选出簇首。

3 基于LEACH协议的无线传感器网络分簇路由协议优化设计思路

3.1 LEACH协议概述

LEACH 主要通过基于簇的操作使WSN 减少功耗，按照轮次周期性的进行执行，每个轮次由分为两个阶段，在一个轮次中保持簇不变但重新选择簇头，每个轮次分为建立阶段和稳态阶段两个阶段。

在建立阶段主要进行簇头选举并进行分簇，在簇的形成阶段，采用循环选举机制，使得各个节点等概率的担任簇头。其选举簇头的过程为：假设网络中有N 个节点，每轮执行过程生产k 个簇。每个节点i 在第r+1 轮选举开始时产生一个0～1 之间的随机数，如果这个数小于设定的阈值P(t)，则该节点被选为簇头节点。阈值P(t)的计算公式为：

在式（1）中，r 表示选举轮次数，k 表示选举的簇头数目，N 表示网络中的总节点数，C(t)=0 表示节点i 已经当选过簇头，C(t)=1 表示还未当选过簇头，即只有在以前的轮次中没有做过簇头的节点才能成为当前轮次的簇头；在式（2）中，R(i)为0～1 之间的一个随机数，P(i,r)表示节点i 在第r 轮次成为簇头的概率。当选举轮次数r=N/k 时，一个循环选举周期结束，所有节点都正好当选过一次簇头。在节点成为簇头后，采用CSMA 的MAC 协议向邻居节点广播通告自己成为簇头的消息，避免多个簇头的广播发生碰撞。

在稳定阶段，进行数据传输，簇内节点在各自分配的时隙内向簇头节点发送数据，其他时间睡眠以减少消耗，簇头节点一直保持活跃，进行数据融合等任务并将处理结果发送给汇聚节点。在持续工作一段时间后，网络重新选取下一轮次的簇头并建立新簇。为了节省资源降低功耗，LEACH 稳定阶段的持续时间要比建立阶段的时间长。

3.2 LEACH算法的优化思路

LEACH 算法将簇头责任分配给具有更高剩余能量的节点，且使所有节点可以等概率的担任簇头，避免了簇头过分消耗能量，提高了整个网络的生存时间，但是它由每个节点产生的随机数对比设定的阈值来确定是否成为簇头节点，每个周期选举生成的簇头的数量和位置都会发生改变，除此之外，周期性的选举簇头过于频繁，引发的通信量也耗费了大量能量。

在LEACH 协议的基础上，在簇头节点选取时引入成本函数，每个节点的成本被定义为一个函数，这个函数表示为：

在式（3）和（4）中，E(s)表示节点j 的剩余能量，E(x,y)为节点所在感知区域的剩余总能量，C 为节点i 的感知区域。

簇头的选择基于每个节点的感知成本，一个簇内成员的节点只能发送信息到相应的簇头，从节点i 到汇聚节点的一条路的感知成本可以定义为：

在式（5）和（6）中，C(s,s)是每条链路的成本，C(s)是基于成本函数的节点成本，E(s,s)和E(s,s)分别是发送和接收一个分组数据消耗的能量。通过在式（5）和（6）就可以得到一条簇头到汇聚节点的最小成本路径。

基于成本函数的操作执行可以分为六个阶段：

第一阶段：节点和其邻居节点交换剩余的能量信息，每个节点计算自己的感知成本。

第二阶段：簇头选择阶段，邻居范围内最小成本且能量大于一定阈值的节点被选为簇头。

第三阶段：建立簇头和汇聚节点之间的端到端路径，网络中任何节点通过最小成本路径从汇聚节点收到路由并发现消息。

第四阶段：形成簇，每个非簇头节点选择最近的簇头然后通过发送一个入簇消息加入该簇。

第五阶段：激活传感器节点。

第六阶段：每个活动节点收集自身信息并上报给簇头，簇头汇聚来自簇内多个传感器节点的数据并发送给汇聚节点。

4 结语

从无线传感器网络的发展现状来看，在国内外，基于分层结构的WSN 路由协议一直在不断地发展且取得了不错的研究成果。本文针对传统的LEACH 协议在簇头节点的选择及拓扑结构上的缺点，提出了一种改进的LEACH 算法的优化设计思路，采用基于成本函数的方法进行簇头的选择和路由的建立，得到簇头节点到汇聚节点的最小成本路径，在感知范围和生命周期之间有一个较好的平衡。在今后的研究工作中，需要在有限的条件下，实现真实WSN 系统的搭建，以便进一步研究该优化改进算法的性能，从而使簇头节点的通信路径选择更加科学合理。