基于能耗最优的LEACH协议的改进

摘 要：针对LEACH协议在簇头选取、数据通信方面的不足，提出改进后的Ad-LEACH协议。根据节点的分类，修正簇头当选概率，使簇头选取均衡了能耗、距离、节点密度的影响。通过节点位置模糊匹配的方法将全网划分为若干个均匀大小的网格。数据传输阶段以能量利用率最高为目的，基于最佳转发距离选择转发节点。仿真结果表明，Ad-LEACH协议有效降低和均衡了网络能耗，达到了能耗最优的目的。
关键词：无线传感器网络；LEACH协议；簇头选取；模糊匹配；网格；转发节
点；能耗最优
中图分类号： TP393 文献标识码：A

1 引言
无线传感器网络（Wireless Sensor Network, WSN）是一种新兴的信息感知和数据采集网络系统，能够实现人与物理世界的通信和信息交互，在众多领域具有广阔的应用前景[1]。由于网络节点采用电池供电，且往往部署于恶劣的、人类难以到达的环境中，节点电能耗尽后难以补充和更换，因此能耗问题是制约无线传感器网络应用和发展的首要问题。
路由协议是组网的基础和数据传输的关键，改进适用于无线传感器网络的路由协议可以有效降低节点的能耗，延长网络生命周期。LEACH协议（低功耗自适应集簇分层型协议，Low Energy Adaptive Clustering Hierarchy）是具有代表性的层次路由，采用区域集中控制的方法，从各区域节点中选出簇头，通过簇头向基站转发簇内信息，与直接传输、最小传输能量等路由相比较，可以有效降低节点能耗[2-3]。
LEACH协议执行过程中，由于部分节点耗能过快、过早死亡会造成网络不完全联通，导致网络性能急剧下降，因此网络能耗不均是LEACH协议需要解决的首要问题。
.
2 LEACH协议
2.1协议原理及分析
LEACH协议按“轮”周期执行，每轮包括簇头选取、簇的形成和数据传输三个阶段。在簇头选取阶段，各节点分配一个介于0~1的随机数，若随机数大于本轮的阈值，节点当选为簇头。簇头选取完成后，簇头向周围节点广播通告自身的簇头状态、ID和本簇的分组头。周围节点根据接收信号的强度确定加入最近距离的簇，并将自身和簇头的ID通知相应的簇头节点。在数据传输阶段，簇头以TDMA方式安排簇内节点的时间调度，节点按分配的时隙将数据传送给簇头，簇头将数据包去冗处理后，按照不同的CDMA代码直接发送给基站。
LEACH协议中，簇内节点仅在分配的时隙内开启无线发送装置进行数据传输，其余时间进入休眠状态，大量节省了节点能耗；同时，簇头在发送数据前经过去冗处理，减小了发送开销。但LEACH协议的簇头选取没有考虑参选节点自身的因素，仅依靠随机数产生，造成簇头分布不均、簇的规模差异大、簇头能耗不均；数据传输过程中，节点能耗与距离呈指数增长，距离基站远处的簇头消耗很大能量直接发送数据至基站，造成能耗过快、过早死亡。

2.2协议相关研究
针对LEACH协议的不足，近年来许多学者进行了研究和改进。针对簇头选取、分布不合理，乔俊峰等在文献[4]中根据节点密度划分簇规模，刘玉华等在文献[5]中结合节点剩余能量和距离等因素改进阈值公式，唐甲东在文献[6]中结合剩余能量和节点密度采用阈值，这些改进从一个方面或者多个方面优化了簇头节点的当选条件，但是对影响因子归纳和定量的全面性存在一定不足。在簇的形成阶段，祁飞等在文献[7]中划分了子网并在子网内均匀分簇，蒋畅江等在文献[8]中通过减小靠近基站的成簇半径实现非均匀分簇，石为人等在文献[9]中提出簇头竞争半径自适应调节成簇的方法，这些改进与簇头选取方案相适应，共同达到均衡簇头能耗的目的。在数据传输策略上，李雅卿等在文献[10]中采用贪婪算法形成多跳的数据传输路径，王国芳等在文献[11]中提出结合剩余能量选择中间节点的簇首多跳算法，张瑞华等在文献[12]中利用位置信息选择能耗最小的最优转发簇头，这些成果表明，LEACH协议的数据传输方式应该由单跳改进为多跳或者单多跳结合，转发节点的选择也要以能耗最小为目标。还有一些研究者讨论了多跳路由中距离和能量的关系，郭书城等在文献[13]中提出能距比的概念并计算出节点的最佳发送距离，李小亚等在文献[14]中讨论了单多跳路由节能优势的临界距离[4-14]。
AD-LEACH协议是在以上研究的基础上，综合考虑影响簇头分布的因素，细分了节点的类型，进行阈值的改进。在簇的形成阶段，节点根据自身坐标计算所属簇的矩阵二维值，通过匹配方式将网络分成若干个均匀的网格。数据传输采用单多跳结合的方式，转发节点的选取结合了最佳转发距离和剩余能量，可调转发收敛的速度，较好地解决了簇头分布和网络能耗不均的问题。

3 Ad-LEACH协议
3.1簇头选取过程
影响簇头在网络分布和能耗的因素主要有节点能量、和基站的距离、节点密度等。簇头节点必须具有足够高的能量，用以处理和转发本簇数据，同时簇头的分布需要考虑节点密度和多条路由引入的“热区”问题。Ad-LEACH协议区分出三类特殊节点，包括：Ⅰ型高能节点；Ⅱ型“热区”节点；Ⅲ型密集区域节点，通过提高特殊节点的当选概率，均衡簇头的负担。
网络中非特殊的节点为普通节点，阈值公式与LEACH协议相同，表示为：

对于特殊节点，做出以下定义：
定义1：若节点能耗率与网络平均能耗率的商差值 小于0，满足公式

（1）
则该节点为Ⅰ型高能节点，其阈值公式为 。
其中， 为网络节点的总数， 为所有节点剩余能量的总和， 为节点 的剩余能量。
定义2：若节点与基站的距离小于最远节点和基站距离的20%，满足公式
（2）
则该节点为Ⅱ型“热区”节点，其阈值公式为 。
其中， 为网络节点和基站的最远距离， 为节点 与基站的距离。
定义3：若节点通信半径内节点密度超出网络平均节点密度50%，满足公式
（3）
则该节点为Ⅲ型密集区域节点，其阈值公式为 。
其中， 表示节点 通信半径内的存活节点数， 表示标准规模簇所含节点数。
定义4：若节点满足公式（1）、（2）、（3）中两项及以上，则该节点为交集节点，其阈值公式 通过加权方式确定。 、 、 分别为Ⅰ、Ⅱ、Ⅲ型节点的加权值，且 ； 、 、 。例如节点 满足Ⅰ型和Ⅱ型的条件，其阈值公式为 ，其中 。
与LEACH簇头选取的目前改进方案相比，AD-LEACH从造成能耗失衡的根源出发，按照节点自身特点进行了分类，并有针对性地改进了簇头当选概率，使簇头选取更合理性、网络能耗更均匀。

3.2分簇过程
在簇头选取过程中，AD-LEACH已经权衡了节点能量、位置等因素的影响，采用不均匀分簇的方法会造成因素之间影响失衡，并不适用于AD-LEACH。
AD-LEACH协议通过节点位置模糊匹配的方式将网络分成若干个相同大小的网格。矩形网络区域长为 ，宽为 ，将长边划分为 等分，宽边划分为 等分，网络被等分为 个矩形网格。为了保证网格内节点可靠通信， 、 的选值满足约束条件 ， 为节点的通信半径。如图1所示，按照矩阵排列给所有网格分配一个二维值 。
对于网络中任意两个节点 和 ，坐标分别为 、 ，若 ， 为取整函数，则满足模糊匹配条件。
所有节点计算自身所属网格的二维值，满足位置匹配条件的节点划分在同一网格。

图1 网格二维值分布示意图
3.3数据传输过程
AD-LEACH协议采用基于最佳转发距离的数据传输方式，包括以下过程：
（1）定义距离阈值 ，若簇头节点 与基站的距离小于 ，节点采用单跳方式，直接与基站通信，完成数据传输。
（2）若簇头节点 与基站的距离大于 ，先完成簇内数据处理。网格内的簇头接收本簇节点的数据包，若一个网格包含多个簇头，普通节点的数据包发送至距离最近的簇头。
（3）簇内数据处理完成后，各个网格中的簇头成为待转发节点，进行簇外数据传输，采用多跳方式，选择合适的转发节点，将数据传送至基站。
多跳方式的流程图如图2所示：
以簇头节点 为圆心， 和 为外径和内径作圆环，在圆环区域内选择最佳转发节点，其中， 为最佳转发距离，当节点选择距离为 的节点转发数据时，节点的能量利用率最高， 、 分别为外径和内径的增补量，控制节点搜索面积。
若圆环区域内有 个簇头，剩余能量分别为 、 …… ，和基站的距离分别为 、 …… ，为了使数据尽快转发到基站，通过距离条件加快收敛，距离条件为 ，其中， 为待转发节点与基站的距离， 为距离衰减因子，调节转发收敛的速度。
对于符合距离条件的M个簇头，将它们与基站的距离值从大到小排序，分别计分1、2……M；剩余能量值从小到大排序，分别计分1、2……M，定义距离的权重为 ，能量的权重为 。若节点 的距离计分为 ，能量计分为 ，则其总得分为 ，总得分最高的候选簇头当选为转发节点。
若圆环中不含簇头或不含满足距离条件的簇头时，选择圆环中的普通节点作为转发节点。为了减少计算开销，加快摆脱圆环无合适簇头的状况，，使当选节点尽量靠近基站，距离条件 中距离衰减因子取得较小些， 。在满足距离条件的普通节点中选取能量最高的作为最佳转发节点。

图2 Ad-LEACH协议的数据传输流程图
3 仿真结果及分析
3.1 环境模型
本文采用NS2对AD-LEACH协议进行仿真，并与LEACH进行对比。节点总数为100，随机分布于100m×100m的区域，基站位置为（0m，0m），节点初始能量均为2J，最佳簇头百分比为5%，仿真时间为600s。能量模型与LEACH相同， ， ， ， 。
3.2 结果与分析
图3是LEACH协议改进前后网络存活节点数与时间关系的仿真结果，图4
是网络总能耗与时间关系的仿真结果，图5是数据包发送总数与时间关系的仿真结果。
由图3可知，LEACH中出现第一个死亡节点的时间为400s左右，最后一个节点死亡时间为530s左右，而AD-LEACH中第一个和最后一个节点死亡时间分别为430s和590s左右，从 FND的角度获得了7.5%的性能提升，从LND的角度延长了11.32%的网络寿命。图4中AD-LEACH的能耗曲线更为平滑，反映能耗速率比较稳定。对比图3和图4，第400s～530s时间段，LEACH网络和AD-LEACH网络的能耗差异并不大，但是AD-LEACH网络中存活节点数目明显高于LEACH网络，反映了AD-LEACH的节点能耗更加均匀，有效解决了LEACH中部分节点过早死亡，导致网络性能下降的问题。从图5中可以看出，AD-LEACH网络的吞吐量也有了较大提高，提高了62.5%左右。
通过网络性能的对比，体现了AD-LEACH协议在降低和均衡节点能耗、延长网络寿命方面取得了较好的实验效果。

图3 网络存活节点数目与时间关系

图4 网络总能耗与时间关系

图5 数据包发送总数与时间关系

5 结束语
AD-LEACH协议目的在于降低和均衡网络能耗，实现能耗最优，为此针对LEACH工作机制的不足做出了改进，包括：1）分析了节点的特点并进行分类，从造成簇头选取不合理的客观原因出发，有针对性地进行阈值的修正。2）通过节点位置信息，采用匹配方式将网络分为相同大小的网格。3）在最佳转发距离附近的圆环区域寻找转发的中间节点，兼顾了转发节点的剩余能量和转发效率。
仿真结果表明，改进后的协议有效延长了网络生命周期，均衡了节点能耗，改进效果较为明显，但是对基站所处位置对网络性能的影响以及数据传输的开销分析尚未探究，将作为下一步工作的重点。