基于簇头协作的LEACH-C路由策略研究

天津工业大学电气工程与自动化学院 杨振伟 郭利进

引言

随着计算机和通信技术的快速发展，WSN(无线传感器网络:Wireless Sensor Network)正受到了前所未有的关注和重视[1]。由若干个具备感知、计算和通信能力的节点构成，WSN技术现在已被广泛应用于气象监测、环境监测、深海导航及军事监视等生活的各类领域[2,3]，为确保这些持续性具体监测和数据动态跟踪，WSN工作时间必须要在一定程度上尽可能延长。另一方面，WSN中的成员节点在数据无线传输通信、信息的分析处理、信号传输带宽、电池电量供给以及存储空间等方面都受到了限制，传统路由协议无法直接应用于当前的无线传感器网络。因此，一个优良的路由协议应当涵盖低能耗的数据传输路径，良好的可扩展性、强大的鲁棒性、良好的容错性、良好的稳定性和低延迟性等特征。所以，设计一个高稳定性、强鲁棒性、低能耗的特定路由协议对无线传感器网络的进一步发展意义相当重大[4]。

1 LEACH相关协议

LEACH（低能量自适应聚类层次:Low Energy Adaptive Clustering Hierarchy）协议是一种典型的自适应聚类路由协议，其以数据为中心利用单层簇路由[5]。LEACH协议簇头选举策略及其单跳数据传输也存在一定的弊端，这些弊端对网络性能的影响不可小觑。近些年，基于LEACH路由协议的不断研究与改进，已然然成效显著。文献[6]中提到了LEACH路由协议中簇头选举机制的改进，当前一轮的簇头达到一定条件时，再重新选举簇头，这样便减少了每轮簇头选举所带来的能量消耗。文献[7]中展示了一种多跳式的路由协议，基本原理是让距离较远的节点先选择一个离自己位置最近的节点进行数据的转发，相较于与终端直接通信，距离大大缩短。文献[8]提出在节点分完簇后，接下来在每一个簇内，根据节点之间的相互距离和数据相似度再次进行分组，并在每一个分组内重新选取一个代表节点，其任务是将数据发送给簇头。文献[9]根据能量分布和节点位置信息，引入了代价函数进行簇头的选举，其中，能量更高和位置更优的节点会优先当选为簇头，这样，各个节点的工作任务分配会更加合理。文献[10]采用了一些综合性较强的概率公式来定义阈值函数，使网络负载更加均衡，有效增加WSN的生命周期。

上述基于LEACH的改进算法不同程度上降低了网络能耗，但依然存在很多明显的缺陷，如WSN网络中的簇头分布具有很大的随机性；簇成员的加入仅仅考虑成员节点与簇头的距离，没有考虑该簇头的能量；另外，一个簇内只有一个簇头，簇头由于需要完成信息处理与路由而需消耗较大的能量。所有这些不足导致WSN能耗消耗不均衡，大大影响网络的正常工作时间。

2 改进的算法

2.1 算法描述

本文算法的主要研究思想是研究如何分担WSN簇头的网络能耗，均匀网络簇头分布，优化网络分簇，均衡全局能耗，延长系统有效工作时间。为了弥补传统的LEACH协议存在WSN中簇头分布不均匀和节点能量消耗过于集中等缺陷，本文采用一种改进的LEACH路由算法，即基于主次簇头协作的LEACH路由算法LEACH-C(LEACH-Cooperative)。主要在如下几个方面进行改进：

（1）簇头选取过程：在LEACH簇头选取的基础上，进一步根据距离与能量因素进行次簇头的选择，也即实现同一个簇的双簇头选择（收集处理和发送分开），有效缓解LEACH算法中簇头分布不均、能量消耗过快的不足。

（2）簇的创建过程：在传统LEACH路由算法中簇成员的确定是以与“准簇头”距离的因素来确定加入规则，但是这样容易造成整个监测区域簇的分布不均匀，进而导致采集信息高度的相关性和冗余性。在本文提出的LEACH-C路由协议中，利用成员节点与主次簇头（具体为主次簇头之间的虚拟坐标）之间的距离选择加入不同的簇，能够有效克服能耗消耗过于集中的缺陷，为了避免采集信息的冗余性和进一步降低系统能耗，采用临近距离内休眠机制。

（3）特殊节点处理：无线传感器网络节点部署的随机性，可能造成个别区域节点分布严重不均匀，存在游离节点即在参考距离内没有归属任何一个簇，基于此，本文也提出了游离节点的主次协作传输或选择加入最近的簇的规则进行信息的采集与路由。

LEACH-C的详细流程如图1所示。基于分簇路由方式的无线传感网络，簇头选取和确定在无线传统中起着至关重要的作用。如表1所示，WSN各成员节点都拥有并维护一份属于自身的路由属性表。路由表中，网络节点被唯一编号，并用字段ID表示，该字段在网络初始化时被随机标记；Alive表示网络节点状态是否存活，“0”和“1”分别表示消亡和存活；Sleep表示网络节点是否为休眠状态，“0”和“1”分别表示休眠和活跃；Head-1字段代表WSN节点是否成为主簇头，其中0(1)代表“否”或“是”，在WSN初始化阶段，Head-1字段都默认为“0”；同样，Head-2字段代表WSN节点是否成为协作簇头即次簇头，其中0(1)代表“否”或“是”，在WSN初始化阶段，Head-2字段都默认为“0”；表2-1中的Active-1和Active-2字段代表WSN节点是否参与主簇头或者次簇头的选取，“0”代表该成员在本轮簇头（主簇头和次簇头）选举过程没有当选，或没有收到簇头(包括次簇头)的广播信息，或收到至少两个簇头(包括对应的次簇头)的广播信息，则节点标记为网络中的游离节点。“1”字段表示节点当选为主或次簇头，或在给定距离范围内仅收到一个簇头广播消息，该字段的初始默认值为“0”；字段Cluster表示该WSN成员节点是否已经成功加入网络中的某个簇，取值为“1”（已入簇）或者“0”（未入簇），该字段初始值标记为“0”。该改进协议LEACH-C路由属性表是在WSN刚开始初始化时被植入对应初始值，同时在WSN的簇创建过程和稳定过程中被读取和改写。

图1 LEACH-C路由协议流程图

表1 WSN成员节点路由属性表

2.2 协作簇头的确定

为避免LEACH能量消耗过快以及簇头节点分布集中,本路由算法兼顾主簇头和次簇头剩余能量和相对距离,相对位置等因素,基于局部集中法则选取“簇头对”,对于拥有成员个数为N的WSN,预设“簇头对”节点占整个WSN网络节点的比例为P，WSN系统初始化后，基站为网络中的节点分配分簇参考距离Rre1

字段Active-1为“0”的节点首先产生随机小数，当小于预先设定的阈值（公式2-1）时，则该节点当选为候选主簇头；首先当选候选主簇头节点则为第一个主簇头，随即该节点广播消息并且将其Head-1的属性置为“1”。同时，“主簇头”根据Rre22=，通过广播为其周围网络节点发放对应次簇头选择参考距离Rre2。Active-2字段为“0”的网络节点根据接收的广播信息确定是否成为次节点，当“准次簇头”接收到主簇头的广播信息后加权自身剩余能量因素启动定时器，首先定时完成的节点广播消息确定为次簇头节点，同时将自身Head-2属性值设置为“1”。进一步，基站记录下网络中的已经产生的“簇头对”数目，在Rre1内的节点接收到消息后将其Active-1和Active-2字段属性值设置为1，该节点本轮将不再参与主簇头或者次簇头的竞选。依照这样的过程，依次产生其他“簇头对”，由BS控制WSN网络中本轮产生“簇头对”个数。当“簇头对”个数达到P*N后，本轮“簇头对”选取结束。

公式（2-1）和公式(2-2)中的各个参数具体含义为：S表示监测区域WSN的面积，N为WSN中节点数目，P表示WSN中簇头节点的所占百分比，M为分块距离参考参数，一般选择为2-5，具体为当主簇头节点与基站较远的时候，M选择较小值，此处考虑是簇与基站较远，需要较远次簇头进行信息路由。

2.3 LEACH-C簇的形成规则

在“簇头对”的确定过程中遵循每个“簇头对”节点的参考（本章采用的是主次节点中间坐标为簇的虚拟中心坐标）范围内不再产生其他“簇头对”。这样WSN网络中就有可能存在部分非簇头成员节点在给定的参考半径Rre1内没有“簇头对”，或者在参考范围内存在多个“簇头对”，此成员节点称为游离节点，如图2所示。路由属性表中字段Active-1和字段Active-2属性值为1的非簇头节点，此时应根据公式（2-3）计算参数最小的d值，参考距离内最近的距离“簇头对”入簇；而对于字段Active-x（字段Active-1和字段Active-2）的属性值为0的非簇头节点，在该阶段根据公式(2-3)分别计算各自入簇阈值Tclu，选择计算阈值Tclu最大的主簇头节点入簇，即选择距离较短、剩余能量较高的主簇头节点入簇。

图2 LEACH-C中的节点入簇示意图

公式（2-3）中各参数表示含义分别为：参数d表示当前节点到“簇头对”中间节点的距离，dmax表示任意两成员节点的最大距离，Einit表示网络节点能量初始值，Ecur则表示节点剩余能量。

传统的LEACH路由协议中，由于簇头直接路由信息至基站，这样就会导致远离基站的簇在信息路由阶段消耗大量的能量，进而导致WSN网络的能量消耗过快，且网络能量消耗不均衡，导致WSN的有效监测时间较短。基于此，在此改进的LEACH-C协议中，主簇头负责与簇内普通成员节点进行通信，即搜集普通成员节点采集的信息：降低节点信息的冗余度同时节省节点能量，LEACH-C路由协议在簇内部让低能量节点轮流进入休眠，进而有效延长网络有效工作时间。在此改进的LEACH-C协议中，WSN中的次簇头节点主要负责与主簇头节点以及WSN网络中的基站节点进行通信，当主簇头离基站较远时，为了有效提高系统的能量均衡和网络生存周期，次簇头的参考距离中的M参数一般取较小值，也即确保次簇头与主簇头之间距离较大以期与基站距离较近，这样可有效弥补由于该簇与基站距离远传输信息消耗的能量大的缺陷。

3 LEACH-C仿真分析

针对WSN仿真平台Atos-SensorSim进行实验分析提出的LEACH-C路由协议，将本章提出的LEACH-C路由协议与传统的LEACH路由协议进行仿真分析。参数具体设置如：在500m*200m监测范围中随机分布200个网络节点。基站坐标位于网络中心，即（250,100）位置的WSN，本实验参数如表2

表2 LEACH-C参数的配置表

3.1 WSN的生命周期分析

首先分析WSN中存活节点数目与分簇轮数之间的关系，为比较本章所提的协作簇头路由算法，即LEACH-C协议的性能特征，图3中画出了传统的LEACH路由协议所对应的曲线。

图3 网络存活节点数与轮数之间关系

根据图3可得出如下的结论：（1）所提的LEACH-C协作簇头路由算法显著提高了WSN中节点的存活率，即在本参数设置条件下，传统的LEACH路由协议在第22轮左右时，WSN系统开始出现消亡节点，但改进的算法LEACH-C出现消亡节点大约在82轮；（2）分簇轮数为300之前，传统的LEACH路由算法的节点存活率大约在50%，也即网络有一半左右节点开始不能正常工作，而本文所提出改进的协作簇头路由协议LEACH-C路由协议节点存活率高于60%，整体网络中正常工作的节点存活率平均提高了10%以上。基于以上分析，可看出当基站位于随机分布WSN网络中心处，所提的改进算法，LEACH-C路由协议能大大提高了WSN网络节点存活率，有效延长了网络有效工作时间。

3.2 LEACH-C网络能耗分析

图4进一步分析WSN网络总能量消耗与分簇轮数之间的关系，为便于比较分析，在此也画出了传统的LEACH路由协议对应的关系图。

从图4显示结果可以看出，所提的新算法LEACH-C在网络能耗的统计上低于传统的LEACH路由算法。在设置的具体仿真环境场景中，传统的LEACH路由协议在轮数18轮左右时，网络能耗大约是2000J，而此时的LEACH-C的网络能耗只有800左右。进一步分析可以发现，随着运行轮数的增加，所提的LEACH-C路由算法性能优势更加明显，也即随着轮数增加(持续到80轮左右)LEACH-C的能量消耗优相对于传统的LEACH差距更加扩大，进一步说明所提算法的优越性。在轮数250以后，相较于LEACH算法，改进的LEACH-C算法相对传统的LEACH路由算法，网络能量消耗大约节省920J。根据以上分析可知，所提基于簇头协作的路由算法LEACH-C协议通过分摊网络簇头负载，有效均衡网络簇头节点的负载分配，进一步降低了WSN网络总能量消耗。

4 结语

本文首先详细分析和讨论经典的WSN分簇路由协议——LEACH路由协议。总结LEACH路由协议的不足：网络中的能量消耗不均衡、网络中的节点局部负载过大、网络中釆集的数据具有很高的冗余度和相关度、簇头选择方式不合理、特殊节点没有充分考虑等等。在此基础上提出了一种改进的分层路由算法：基于协作簇头的LEACH-C路由协议。在主簇头选定的情况下根据相对距离与剩余能量进行次簇头的选择，系统中每个节点维护自身路由属性表，WSN中的节点根据距离和能量两个因素选择入簇；在信息传输阶段，采用休眠机制和远距离簇头路由方式进一步降低系统能耗；最后通过仿真分析得到LEACH-C相对于传统的LEACH协议能够有效延长网络工作时间，均衡网络负载。