聂芯雨 李勤勤 李 竹*

（山西师范大学物理与信息工程学院，山西 临汾 041004）

1 引言

无线传感器网络(Wireless Sensor Networks，WSN)是一种分布式传感网络，由大量静止或移动的传感器组成，通过无线通信方式形成的一个多跳的自组织网络系统，是21 世纪最重要的技术之一。WSN的网络设置灵活，设备位置可以随时更改，其目的是协作地感知、采集和处理网络覆盖区域中感知对象的信息，并发送给观察者。与传统的网络相比，传感器网络的节点一般采用电池供电，而WSN 节点电池充电和更换困难，因此在保证网络连通性和覆盖度的情况下，合理利用有限的能量，令其进行最长时间的工作成为无线传感器网络路由协议设计考虑的首要目标。

国内外的研究者做了大量研究，将WSN 的路由算法分为平面型路由算法、层次型路由算法和基于定位的路由算法[1]。其中在层次型路由算法方面，提出了LEACH（Low-Energy Adaptive Clustering Hierarchy）算法，本文以LEACH算法为基础，提出了一种新的算法——NLEACH（New-Low-Energy Adaptive Clustering Hierarchy）算法。该算法对LEACH算法的簇头选举机制进行了改进，新的阈值计算方案使剩余能量多的节点能够以大概率担任簇头，使节点能量消耗更合理，节点能够最大限度地存活，从而有效利用了每一个节点的能量，相较于LEACH 算法，延长了网络生命周期，增加了数据传输量。

2 层次型路由协议

无线传感器网络路由协议按照通信的逻辑结构可分为平面型路由协议和层次型路由协议。在层次拓扑机制下，传感器节点可分为骨干网节点和普通节点，骨干网节点是簇头，普通节点是簇内节点，簇头节点对簇内节点负责管理。层次型路由协议较平面型路由协议性能更好，层次型路由协议在运行中簇头节点会对簇内节点发送的数据进行融合，减少不必要的信息传输，降低能量的消耗，而各节点可以等概率地当选为簇头，均衡了网络的能量消耗，延长了网络生存周期。在路由计算中只有部分节点参与其中，大大节省了能量消耗，同时层次型路由协议可用于大规模部署的网络。

3 LEACH协议

3.1 LEACH原理

LEACH协议通过随机选择簇头节点来平均分担网络中的数据传输，使传感器网络中节点能量得以平衡。该协议的执行过程是周期性的，分为两个阶段：簇的建立阶段和数据传输阶段，这两个阶段一起构成一个轮回。为了减少分簇带来的额外能耗，簇稳定阶段远远长于簇形成阶段[2]。在簇的形成阶段，相邻节点动态地形成簇，随机产生簇头；簇头向外广播消息，其它节点收到消息后，选择最近的簇头加入；在数据传输阶段，簇内节点把数据发送给簇头，簇头进行数据融合并把结果发送给汇聚节点。

3.2 簇头选举方式

LEACH 算法选举簇头的过程如下：节点产生一个0～1之间的随机数，如果生成的随机数小于阈值T(n)，就当选为簇头。在每轮循环中，如果节点已经当选过簇头，则把T(n)设置为0，该节点不会再次当选为簇头。未当选过簇头的节点，则将以T(n)的概率当选；随着当选过簇头的节点数目增加，剩余节点当选簇头的阈值T(n)随之增大，节点产生小于T(n)的随机数的概率随之增大，所以节点当选簇头的概率增大。当只剩下一个节点未当选时，T(n)=1，表示这个节点一定当选。T(n)可表示为：

其中，P是簇头在所有节点中所占的百分比，即节点当选为簇头的概率，r是选举轮数，rmod(1/P)代表这一轮循环中当选过簇头的节点个数，G是这一轮循环中未当选过簇头的节点集合[3]。

3.3 网络传输能量模型

LEACH 算法的无线网络传输能量模型主要由发射电路、放大电路和接收电路组成。

节点将Kbit的数据发送到距离为d的接收节点时，发射装置消耗的能量为ETX(K,d)，由发射电路和放大电路消耗的能量所组成[4]：

其中d0为门限距离，其值为分别表示自由空间模型和多径衰减模型下功率放大器的能耗系数；若发射装置到接收节点的距离d≤d0时，功率放大器采用多径衰减模型ξmpd4；d>d0时，功率放大器采用自由空间模型ξfsd2；Eel表示每发送或者接收1bit数据时电路消耗的能量；K表示传输数据包的长度[5]。

接收节点接收Kbit的数据时消耗的能量为[6]：

因此，簇内成员对簇头进行选举时，普通节点发送Kbit的数据到簇头后的剩余能量Ersd为：

Ei是第i个节点的能量（i=1,2,…,100）；dmin为普通节点与簇头的最近距离。

簇头发送Kbit 数据到基站并进行数据融合后的剩余能量为：

EDA为簇头数据融合1bit 数据所消耗的能量。其中EDA、Eel、ξfs、ξmp和K按照表1进行初始化。

表1 LEACH算法部分仿真参数

3.4 LEACH协议的不足

LEACH 算法主要通过随机选取簇头，平均分担通信中的数据传输来延长生命周期，它能够保证各节点等概率担任簇头。但在选取簇头的过程中，因为簇头需要完成数据融合、与汇聚节点通信等工作，工作耗能大，LEACH 算法没有考虑到节点的剩余能量与节点成为簇头的关系，选举簇头存在很大的随机性，任何节点都可以等概率当选簇头，如果能量低的节点担任簇头，在稳定工作阶段消耗能量过多时，节点能量会提前衰减，导致节点死亡速度加快，各节点的能量消耗没有合理地均衡分配，网络利用率偏低，随之网络生命周期缩短。

4 LEACH改进算法

4.1 改进方案

针对LEACH 协议的不足，在阈值计算中引入了表征节点剩余能量与系统剩余总能量之间比值关系k倍的剩余能量因子，将改进算法简称为NLEACH，改进公式（1）如下：

其中Etot是当前轮数所有节点的剩余能量总和；在簇头选取的阈值计算方案中考虑了剩余能量因子，其中参数k越小，剩余能量因子越小，生命周期越长，数据传输量越大，簇头数越少，经过多次试验，参数k的取值范围为8~27。对于不同剩余能量的节点而言，剩余能量高的节点能够以大概率当选为簇头，使簇头选举机制更为合理，节点能量消耗较为均衡，从而有效地利用了每一个节点的能量，节点死亡时间延迟，网络生命周期延长。

4.2 程序流程图

图1 是NLEACH 算法的程序流程图。NLEACH 算法每轮包括簇的建立阶段和数据传输的稳定阶段。开始时先按表1对其中的参数值进行初始化。接着进行簇的建立，每个节点随机选择0～1之间的数值，计算节点的剩余能量，如果剩余能量为0，则该节点死亡，如果选取的数值小于公式（6）得到的阈值，该节点被选为簇头，并向全网广播成为簇头的信息。其余节点接收到簇头的广播信息后，根据广播信号强度决定要加入的簇，并按照簇头分配的时间片将采集到的数据发送给簇头[7]，簇头将数据融合，发送到汇聚节点。

5 仿真实验分析

利用MATLAB作为分析工具，设计以下仿真系统：传感器节点总数为100，均匀分布在100m×100m 的被测区域中，sink节点位于(50，50)，循环次数r=5000。所有节点初始能量相同，初始值为0.5 J，数据包长度为4000 bit，发送和接收数据1bit数据消耗的能量为50 nJ/bit。对生命周期和数据传输进行仿真实验，实验在LEACH算法达到最优的情况下进行，经过多次实验后，得出参数k的取值范围为8~27。图2 为取k=8，k=15，k=27时得出的结果。

图2 是k为8、15、27 时的NLEACH 算法和LEACH 算法存活节点数和数据传输量及产生簇头数随时间的变化对比，横坐标表示时间，即当前的轮数r，纵坐标分别表示每一轮的存活节点数、数据传输量和产生簇头数。当存活节点数为0时，表示该无线传感器网络的所有节点死亡，即无线传感器网络生命结束，对应时刻的数据传输量达到最大值。

经过多次实验，结果表明：在参数k的取值范围8~27 之间，网络的生命周期会得到延长。k越小，网络生命周期越长，数据传输量越大，簇头数越少。k<8时，簇头数不合理，产生的簇头数几乎为0；k>27时，网络的生命周期几乎得不到延长。

表2 两种算法节点的生命周期（轮）5次实验对比（k=15时）

选取k=15 的条件下，经过5 次实验的对比，得到表2 的数据。LEACH算法节点的生命周期平均为2966轮，而改进的NLEACH算法节点生命周期平均为3199轮，由此可知，改进后的NLEACH 算法相较于LEACH 算法大约延长了7.856%的网络生命周期。

表3 两种算法传输的总数据量（bit）5次实验对比（k=15时）

选取k=15 的条件下，经过5 次实验的对比，得到表3 的数据。NLEACH 算法的数据传输量平均为158366.8bit，而LEACH算法的数据传输量平均为50495.2bit，故NLEACH算法与LEACH算法相比，数据传输量增长了大约214.28%。

6 结论

在LEACH 算法的基础上，NLEACH 算法通过引入节点剩余能量与系统剩余总能量之间比值关系的k倍剩余能量因子，改进了LEACH 算法的簇头选举机制。NLEACH 算法的簇头选举机制使得传输过程中剩余能量多的节点以大概率担任簇头，使节点能量消耗更合理，从而有效地利用了每一个节点的能量，引入参数k，其取值在8~27的范围内，在簇头数更合理的情况下，使算法的性能更加完善。仿真实验表明，参数k越小，剩余能量因子越小，网络生命周期越长，数据传输量越大。