一种基于多跳与按数据量-距离分发的LEACH协议优化

潘 华， 陈佳品， 丁 凯， 林凤德

(1.上海交通大学微纳电子学系，上海 200240； 2.近地面感知与探测重点实验室，江苏 无锡 214000)

0 引言

无线传感器网络(Wireless Sensor Networks,WSN)[1]是由多个节点组成的自组织网络。在军事、航天等领域有极为广泛的应用，本文的背景是基于一个智能雷场项目的雷场节点寿命研究。智能雷场是通过对一片雷场区域内的地雷上安装传感器节点，达到实时收集战场态势信息以及使地雷之间能够相互通信，最终能够产生一种选择性智能爆炸的效果。而雷场节点指的就是安装了具有无线通信功能的传感器节点的地雷。由于在军事领域，传感器节点一般都是一次性部署而不进行维护，其寿命通常由电池能量决定，然而，WSN自身的特点决定了一旦某个节点由于能量耗尽而死亡，将会导致网络拓扑结构的变化，甚至可能导致通信中断等不可靠行为发生。如何最大限度地降低雷场节点的能量消耗，对延长整个雷场网络的寿命至关重要。在这种情况下，国外研究者提出了低能量自适应聚类路由(LEACH)协议[2-3]——一种最早的分簇路由协议。本文在深入理解LEACH协议的基础上，结合以上几点因素，对LEACH协议进行改进，目的是得到一种更加节能的路由协议。

1 LEACH协议描述

LEACH协议定义了“轮”的概念[4]，协议以轮为周期执行，每一轮的过程包括分簇和稳定两个阶段。在分簇阶段，WSN各个节点随机生成一个0～1之间的数字，然后将该数字与一个设定的阈值公式得出的值进行比较，若该随机数小于阈值，并且该节点在前1/p(p为当前轮中节点成为簇头的比例)轮内未当选为簇头节点，则该节点被选为本轮的簇头节点。其中，阈值的算式为[5]

(1)

式中：p为成为簇头的期望百分比；r为当前轮数；mod为取模符号；G为在最后1/p轮中还未成为簇头的节点集合。

当簇头选取完毕后，簇头向周围节点广播自身的簇头状态、ID等信息，节点根据接收到的消息强度决定加入哪个簇，并告知相应的簇头，完成簇头的建立过程。然后，簇头节点采用TDMA的方式[6]，为簇内成员分配传送数据的时隙。

在稳定阶段，传感器节点价格采集的数据传送到簇头节点。簇头节点对采集的数据进行数据融合后再将信息以单跳方式传送到汇聚节点，按照不同的CDMA代码直接发送给基站。

但是，LEACH协议存在以下问题[7]：

1) LEACH协议算法中，簇头的选取是随机的,而没有考虑到节点当前的能量，有可能剩余能量很小的节点仍然被选为簇头，导致该节点过早死亡，引发再组网等一系列问题，降低网络生存周期;

2) 簇头与基站之间直接单跳通信，当距离较远时，能量消耗成指数增长，造成簇头节点过早死亡，进而降低网络生命周期;

3) 簇头的选取无法保证节点在空间上均匀分布，在某些可能的情况下，形成的簇头节点可能聚集在某一个小范围内，导致某些节点无法加入任何簇。

2 改进后的LEACH协议

改进后的LEACH协议(IMP-LEACH)与LEACH算法有如下相同的网络模型[8]。

1) 传感器节点随机分布在某一片方形区域，基站唯一;

2) 部署之后所有节点(包括基站)的位置不变;

3) 各个传感器节点的初始能量相同，且已知节点任何时刻的剩余能量，基站能量不受限。

在上面的模型中，文献[9]给出了几个定义：邻居节点、前邻节点、前簇头节点。

针对LEACH协议的诸多缺点，本文根据协议的几个过程，对每一个过程提出以下改进，整体算法步骤如下所述。

1) 在判断是否为簇头的过程中，加入节点当前能量这个考量因素，提出

(2)

式中：Eicurrent为节点i当前能量；Eavg为系统节点当前平均能量;α定义为能量距离因子，取值为2或4，取决于节点间距离d。

2) 在簇头选取的过程中，不同簇头节点能量的不同会导致其通信距离的不同，同时，不同能量的簇头节点，其所能容纳的节点数也不同，在节点选择加入簇头的过程中，综合考虑以上两点，给出如下定义。

对于一个特定的节点i，其所能加入的簇头节点集合CH需满足以下两个条件。

条件1满足

N(CH)={CHCH∈V,d(i,CH)

(3)

式中，d(i,CH)

条件2在满足条件1的情况下，进行如下运算

(4)

式中:{CHiCHi∈CH};Emin为使节点存活所需要的最小能量;ECHi为簇头节点i当前剩余能量;n为当前加入簇头节点i的节点个数;E(i,n)为当有n个节点加入簇头节点i时，每个节点所能分配的能量。通过计算可以得到一系列的E(i,n)值，则当E(i,n)取最大值时节点选择加入，至此，节点i的簇头选取过程结束。

3) 在数据传输阶段，有如下能量消耗模型[10]：传感器节点能耗模型主要包括：感知消费、通信消费和数据处理消费，其中，通信能耗占主要部分，也是研究的对象。根据已知文献资料，簇头节点i发送l比特数据到距离d处的基站所需要消耗的能量为[11]

ETx(l,d)=l·Eelec+l·εamp·dα

(5)

式中:Eelec为发射和接收电路的单位能量消耗；εamp为传输放大电路的能量消耗；α为多路径损失指数，当传输距离小于某一个阈值时，使用自由空间模型的功率放大损耗，α取值为2；当传输距离大于或等于阈值时，其值为4，使用多径衰减模型进行功率放大损耗。

显然，当传输距离大于某一个阈值时，会导致能量消耗成指数增长，因此，本文在数据传输阶段的突破点即为此，参考文献[9]，并在其基础上进一步优化了数据分发规则，其基本思想是：利用簇头节点的邻接信息表，选择一个CH作为另一个CH的中继节点来传输数据。根据上面的能量公式，很容易证明采用转发中继模型能够取得更优的能量耗散效果，如文献[9]所采用的模型，基本思想为找到簇头CH0的前邻簇头节点，将数据按照下式进行转发

(6)

在此，本文认为：距离簇头节点越远的节点承担越少的数据转发任务是一种更加优化的选择。证明如下：首先，通过基站存储的节点位置信息，对d1,d2,…,di,…,dm进行排序，并假设距离由小到大排序结果为：d1,d2,…,di,…,dm，在此条件下，提出改进后的数据分发公式为

(7)

容易证明m的取值不会影响最终的结果，为简化证明，仅以m=3来代表证明，过程如下。

当m=3时

(8)

而

(9)

两式相减,即

(10)

总结整个算法过程的要点有：

1) 考虑节点能量和距离因素，重新定义阈值公式;

2) 通过新阈值公式初步查找符合条件的簇头节点;

3) 簇头节点和普通节点之间双向选择过程，综合考虑节点通信范围和簇头节点当前能量;

4) 根据新的数据分发思想进行多跳数据传输。

3 仿真与分析

实验采用Matlab模拟运行改进后的算法，同时将仿真结果与经典LEACH算法进行比较。实验中用到的参数如表1所示。

表1 模型相关初始参数

存活节点个数比较与死亡节点比例比较分别如图1、图2所示。

图1 存活节点个数与循环次数关系Fig.1 Number of alive node vs number of cycles

图2 死亡节点比例与循环次数关系图Fig.2 Proportion of dead nodes vs number of cycles

从仿真结果可以得知，改进后的LEACH协议(IMP-LEACH)在相同循环次数下存活节点个数明显比改进之前的多，并且从横轴可以得知，原LEACH协议在大约1239次循环之后就再无存活节点了，而改进后这一数值提高到了1768，说明改进后的协议能极大地延缓节点死亡时间；通过仿真结果导出的数据所制作的节点死亡比例与循环次数的关系图同样可以看出，改进后的协议在延长节点寿命方面有重大提升，尤其是进入传感器网络运行后期阶段，这种差异更加明显。

4 总结

本文在已有的相关LEACH协议基础上做了深入改进，在簇头选取的过程中增加考虑簇头节点当前能量及其簇内节点个数，综合考虑簇头与节点之间的选择，在数据传输阶段，采用新的多跳数据传输方式，并从数学角度证明了新的数据传输方式更加节能。最后，通过对协议算法的仿真研究，得出了与预期一致的实验观点，证明了改进后的协议在延长WSN网络寿命方面确实有重大提升。