伍敏君

(中山火炬职业技术学院 光电信息学院，广东 中山 528400)

0 引言

无线电通信、嵌入式、传感器、微电子等技术的迅速发展，使无线传感器网络技术被广泛应用于各领域[1]，如军事安全、农业监测[2-3]、医疗护理、工业生产、交通物流、自然灾害预测等。监测区域内大规模地部署传感器节点，各节点以自组织方式形成无线通信网络[4-5]。节点能量有限且无法及时补充，能量效率是无线传感器网络技术难点问题，合理路由管理可延长网络生命周期[6-8]。分簇的拓扑控制，能大幅度减少数据传输量，降低能耗[9-12]。

低功耗自适应聚类层次算法(LEACH,low energy adaptive clustering hierarchy)[13]是经典的分簇算法，其簇头数量不稳定且分布不均匀，对此提出了固定分簇技术。固定分簇算法能有效地降低分簇开销，均衡各个分簇大小[14]。文献[15]提出基于粒子群(PSO)优化的固定簇类区域路由算法，综合考虑分簇与汇聚节点距离、簇内节点间距、剩余能量等因素。文献[16]提出固定分簇和能量均衡的多跳路由协议，基于遗传模拟退火算法来分簇，簇头选举考虑节点剩余能量和全簇平均能量值，簇间以单跳或多跳方式来通信。文献[17]提出异构网络的固定区域分簇路由算法，网格固定分区内综合考虑节点剩余能量及节点分布情况来选举簇头。文献[18]提出基于网格分簇路由算法，设置能量阈值，当能量低于此阈值的邻居节点个数超过一定量时，采用唯一簇头选举法生成新簇头。

本文针对LEACH算法中簇头分布不均以及数量动态变化而造成网络能耗不均衡的问题，提出一种改进的固定分簇算法(FCA,fixed clustering algorithm)，簇头的选举综合考虑区域的内心距离、位置布局、节点剩余能量等因素，从而达到优化簇头布局、均衡网络能耗、延长网络稳定周期和生命周期的目的。

1 分簇算法

1.1 LEACH算法

LEACH是一种分布式的分簇算法，为了将整个网络的能量消耗更均匀地散布到各个节点中，LEACH算法采用按轮的方式进行划分各分簇，每轮均分为簇的建立阶段和稳定阶段两个阶段。

在簇的建立阶段中，LEACH采用动态分簇的方式划分网络。网络中剩余能量大于零的节点，称为存活节点。在此阶段开始时，LEACH采取随机方式选举簇头，各个存活节点均选取一个[0,1]范围内的随机数。如果此节点产生的随机数低于阈值T(n)，同时此节点在前面1/p轮中还未当选过簇头的，则这个节点在此轮中当选为簇头。其中，节点n在第r轮中的阈值T(n)计算公式为：

(1)

式中，p是簇头占所有节点总数的百分比；G是最近1/p轮中没有当选为簇头的节点集合。

在各个分簇内，只选举一个节点当选簇头，其余节点称为成员节点[19]。每轮中，簇头周期性地更换，当节点在此轮中当选为簇头后，向周围其余节点广播自身成为簇头的消息。其余节点按收到簇头消息的强弱，可知与此簇头的距离长短，据此，其余节点加入距离最近的分簇中，并向该簇头发送加入分簇的请求。

当簇头节点收到其余节点的加入请求后，根据自身簇内加入节点的数量，建立该簇的时分多址(TDMA，time division multiple access)调度表，并把此轮的TDMA调度表发送至其簇内的各成员节点。

稳定阶段也称数据传输阶段，在此阶段中，LEACH算法利用簇头进行数据融合，减少冗余信息，降低网络数据传输量从而节省能耗。首先，簇头节点主要任务是对成员节点进行管理和协调，收集其簇内所有成员节点感知的数据。当各成员节点的TDMA时隙到来时，各自向簇头节点发送自身感知周围环境的数据信息。簇头节点对自身分簇内的所有数据进行压缩融合后转发到汇聚节点[20]。在此阶段中，成员节点不直接与汇聚节点通信。

LEACH算法的簇头选举具有随机性，当能量较低的节点选为簇头时，容易加速节点的死亡，从而影响网络的生命周期。

1.2 LEACH-E算法

在分簇算法中，簇头承担着融合分簇内的数据并向汇聚节点转发的重任，因此簇头消耗的能量远大于成员节点。当能量低的节点当选为簇头后，由于承担数据转发的耗能任务，很容易导致能量消耗过多而死亡。此时，网络中部分节点的死亡，会造成部分区域感知数据的缺失以及网络拓扑结构不稳定。

对此，LEACH-E算法对LEACH作了改进，在簇头选举时，考虑各节点自身的剩余能量以及当前网络的平均能量水平，只有剩余能量大于当前网络平均能量的节点才有资格在此轮中参与簇头竞选。

LEACH-E算法由于考虑了节点能量信息来选举簇头节点，避免了能量较低的节点当选簇头而造成网络拓扑不合理的问题，减缓了网络能量消耗速度。

但在LEACH和LEACH-E算法中，均没有考虑簇头位置因素的影响，网络中簇头的分布不均匀，各个分簇大小不均衡。

2 FCA算法

针对LEACH和LEACH-E算法中簇头分布及分簇大小不均的问题，本文提出一种改进算法FCA，以固定方式划分各个分簇，簇头选举过程中引入代价函数，该代价函数综合考虑区域的内心距离、节点剩余能量及位置布局等因素来选举簇头，优化簇头数量和布局，使分簇更加合理。

2.1 网络模型假定

结合实际情况以及无线传感器网络的特性，在本算法中提出以下网络假设：

1)所有节点能够感知自身的坐标位置和剩余能量，部署后不再移动，均能与汇聚节点通信；

2)只有一个汇聚节点，位于网络区域中央处，能量可以补充且不受限；

3)除汇聚节点外，其余节点坐标随机分布，具有相同初始能量且不能补充，有唯一ID号；

4)网络的通信链路具有对称性，即对于同等量的数据，从A点发送到B点所消耗的能量，与从B点发送到A点所消耗的能量一致；

5)节点发射功率可调控，即节点可以根据距离选择不同的传播模型——自由空间传播模型和多路径衰减传播模型。

2.2 能量消耗模型

本文采用通用无线传感器网络节点能量消耗模型，如图1所示，能耗包括发射器传输电路能耗、发射放大电路能耗，以及接收器的接收电路能耗。

图1 节点能量消耗模型

当发送端与接收端之间的距离d小于或等于临界值d0时，采用自由空间传播模型，能量呈d2衰减，能耗系数为εfs；d大于d0时，采用多路径衰减传播模型，能量呈d4衰减，能耗系数为εmp。节点发送Lbit数据的能耗ETX(L,d)与数据包长度L、通信距离d有关，为：

ETX(L,d)=

(2)

式中，Eelec表示发送或接收单位信息所消耗的能量。d0是两种传播模型的临界值，为：

(3)

节点接收Lbit数据的能耗ERX(L)与数据包长度L成正比，为：

ERX(L)=L·Eelec

(4)

2.3 算法描述

2.3.1 固定分簇的划分

以汇聚节点为坐标原点，建立直角坐标系，将M×M的正方形监测区域划分为k个等大小的固定分簇，设网络中节点数量为N，在LEACH 算法中，网络中簇头最优数量kopt为[13]：

(5)

其中:dtoBS为节点到汇聚节点距离，其期望值E[dtoBS]为：

(6)

其中:A为网络区域的面积；x为节点的横坐标；y为节点的纵坐标。

当N=100，M=100时，可得簇头最优数量kopt≈10，簇头比例p=kopt/N≈0.1。本文取k为8，固定分簇的数量接近LEACH算法中的最优簇头数量，将网络区域划分为8个等大小的固定分簇，编号分别为①～⑧，如图2所示。

图2 固定分簇的划分

2.3.2 簇头的选举

分簇算法中网络的拓扑控制主要由簇头来完成，簇头分布对网络性能影响较大。在每个固定分簇中选举一个节点当选簇头，簇头较均衡地散布于网络各个分簇中，避免了监测区域中簇头过于密集或分散的问题，优化了簇头的布局。

簇头选举中考虑节点剩余能量、到分簇区域内心位置的距离等因素。在第r轮中节点i当选簇头代价函数costi(r)为：

(7)

其中:Ei(r)为第r轮中节点i的剩余能量；E0为初始能量；dmax为节点到汇聚节点距离的最大值；diclusterj为节点i到其所在固定分簇区域j(j=1,2,…,8)内心位置的距离。内心位置为各固定分簇内接圆的圆心坐标位置。Ei(r)的值越大，节点剩余能量越充足，costi(r)越大，当选簇头几率越高；diclusterj的值越小，节点i到固定分簇区域内心位置的距离越小，costi(r)越大，当选簇头几率越高。

2.3.3 数据传输阶段

设节点总数为N，划分为k个固定分簇，则平均每个簇内有N/k个节点，其中一个为簇头，其余的(N/k-1)个为成员节点。在数据传输阶段，考虑到传输距离d≤d0，采用自由空间传播模型能耗系数εfs，节点i向其簇头以单跳方式发送Lbit数据所消耗的能量Enon-CHi为：

Enon-CHi=L·Eelec+L·εfs·dtoCHi2

(8)

其中:dtoCHi为成员节点i到簇头的距离。

簇头融合簇内成员节点的数据，并向汇聚节点以单跳方式发送处理后的数据所消耗能量ECH为：

L·εfs·dtoBS2

(9)

其中:EDA为融合1 bit信息所消耗的能量；dtoBS为簇头到汇聚节点的距离值。

各分簇消耗的能量Ecluster为：

(10)

2.3.4 FCA算法流程

FCA算法流程如图3所示，算法按如下步骤实现：

1)在网络初始化时，以汇聚节点为原点，生成坐标系，部署网络中各个节点，生成随机坐标并保存，配置各节点的初始能量；

2)各节点向汇聚节点发送自身的坐标位置、当前的能量水平等信息；

3)以汇聚节点分中心，划分8个固定分簇区域并编号；

4)各个节点根据自身的坐标信息，加入固定分簇，并保存所在的分簇编号等信息；

5)各个分簇分别计算并保存自身分簇区域内心位置的坐标信息；

6)计算第r轮中节点i当选簇头代价函数costi(r)，求出各分簇中的最大值；

7)各分簇区域中代价函数取值最大的，在该轮中当选簇头，其余为成员节点；

8)簇头向簇内成员节点发送其簇头状态的广播消息，以及TDMA调度表；

9)进入稳定阶段，各成员节点向簇头发送感知的数据，簇头融合簇内数据后，向汇聚节点发送数据；

10)本轮分簇结束，进入下一轮。

图3 FCA算法流程图

3 仿真实验与结果分析

3.1 仿真环境

本文采用Matlab R2014a软件对LEACH、LEACH-E、FCA算法进行仿真分析。仿真场景如图4所示，正方形区域范围为(-50，-50)～(50，50)，部署100个节点，图中“▲”为汇聚节点，位于坐标原点处，“○”为节点，坐标随机产生。节点初始能量E0为0.5 J，簇头比例p为0.08，发送或接收单位数据能耗Eelec为50 nJ/bit，自由空间传播模型能耗系数εfs为10 pJ/bit/m2，多路径衰减传播模型能耗系数εmp为0.001 3 pJ/bit/m4，数据包长度L为4 000 bit。

3.2 仿真结果分析

3.2.1 簇头分布

LEACH和LEACH-E算法其中一轮簇头分布情况，如图5和图6所示，“□”为簇头，“○”为成员节点，“--”为节点与簇头的单跳通信。可见，LEACH和LEACH-E中簇头分布随机，某些区域簇头过于密集，某些区域内无簇头，使得节点加入分簇时，离其簇头距离过大。

图5 LEACH簇头分布

图6 LEACH-E簇头分布

FCA算法其中一轮簇头分布情况，如图7所示，“□”为簇头，“○”为成员节点，“--”为节点与簇头的单跳通信，“-·”为各个固定分簇的划分，可见，各簇头分布较均匀，基本分布在各固定分簇的区域中央位置，避免由边缘处节点当选簇头而导致簇内通信距离过大的问题。

图7 FCA簇头分布

3.2.2 分簇大小

LEACH、LEACH-E、FCA算法各分簇的节点数量如表1所示。

表1 各算法分簇节点数量

LEACH算法划分了9个分簇，分簇节点数均值为E(n)=11.1，标准差为σ=4.93。LEACH-E算法划分了6个分簇，分簇节点数均值为E′(n)=16.7，标准差为σ′=8.16。FCA算法划分了8个分簇，分簇节点数均值为E″(n)=12.5，标准差为σ″=2.45。

可见，LEACH、LEACH-E簇头选举未考虑节点位置因素，分簇大小不均衡，标准差较大。FCA算法各分簇节点数目较稳定，分簇大小均衡，标准差较小。

3.2.3 每轮簇头数量

LEACH、LEACH-E、FCA算法中每轮的簇头数量统计如图8所示。LEACH、LEACH-E中每轮簇头数量不稳定，分布在1～14之间。FCA算法采用固定分簇技术，每轮中簇头数量比较稳定，簇头数量为8的轮数有1 757次。

图8 每轮簇头数量统计

3.2.4 稳定周期、半衰周期和生命周期

LEACH、LEACH-E、FCA三种算法的节点存活数随时间变化情况如图9所示。

图9 每轮的节点存活情况

1)稳定周期，即网络运行开始后首节点死亡的时间。LEACH、LEACH-E、FCA的稳定周期分别为1 007轮、1 135轮、1 658轮。FCA对比LEACH延长了64.65%，对比LEACH-E延长了46.08%。

2)半衰周期，为网络中50%节点死亡时间。LEACH、LEACH-E、FCA的半衰周期分别为1 220轮、1 189轮、2 366轮。FCA对比LEACH延长了93.93%，对比LEACH-E延长了98.99%。

3)生命周期，描述了从网络开始工作到全部节点死亡的时间段。LEACH、LEACH-E、FCA的生命周期分别为1 509轮、1 257轮、2 501轮。FCA对比LEACH算法延长了65.74%，对比LEACH-E算法延长了98.97%。

3.2.5 网络能量消耗情况对比

LEACH、LEACH-E、FCA三种算法的网络剩余总能量随时间变化情况如图10所示。FCA算法采用固定分簇技术，簇头选举综合考虑节点剩余能量和位置的因素，有效均衡了网络能量消耗，其每轮中网络剩余总能量均比LEACH、LEACH-E算法高。

图10 每轮的网络能量消耗情况

4 结束语

本文提出一种改进的固定分簇算法，将网络划分为等大小的分簇，簇头选举的代价函数考虑区域内心距离、节点剩余能量及位置信息综合因素，以优化簇头数量和布局。仿真结果表明，改进后的算法有效均衡了网络能耗，实现延长网络稳定周期、半衰周期以及生命周期的目的。