一种融合时间和剩余能量激发的分簇优化算法

姜 华， 林加华， 周万府

（楚雄师范学院信息科学与技术学院，云南楚雄675000）

0 引 言

随着无线技术的发展，无线传感器网络（Wireless Sensor Networks，WSN）已广泛应用于军事侦察、智能家居、环境监测、医疗卫生等领域［1-2］。由于应用环境复杂多变，节点无法进行实时供电，这使得能量成为制约WSN长时间运行的瓶颈。并且WSN 以Sink 节点为中心进行数据汇聚传输，Sink 节点的能耗往往较大，会造成转发数据越多的节点能量消耗越大，节点也会越早死亡，形成“节点空洞”［3-4］。LEACH 协议作为一种典型的均匀分簇路由协议［5］，通过簇头轮转来维持节点能量平衡，但这种轮换也仅仅是局部性的，对于距离汇聚节点较远的节点作用较小。文献［6］中从节点入簇和簇间传输两方面设计了一种非均匀分簇路由算法；文献［7］中利用传统的非均匀分簇路由算法对无线网络进行分簇，采用改进蚁群优化算法搜索出无线网络簇间多条路径，提出了一种改进多目标和声搜索的无线网络非均匀分簇路由方法；文献［8］中将改进的粒子群优化算法应用到双层WSN分簇中，利用粒子群优化算法对分簇多目标函数进行求解，以得到的解建立路由树；文献［9］中提出一种改进的基于分簇WSN的数据聚合算法，解决了多跳模式下簇头因负载不同而导致的能耗量差异，但该算法簇间重叠覆盖率较大，节点能量额外浪费较大；文献［10］中提出了一种结合K-means均匀分簇和数据回归的WSN 能量均衡策略，通过K-means聚类选取簇内节点剩余能量最多者当选簇头，采用数据回归方法减少节点与簇首间的通信量，能一定程度上降低节点能耗，但聚类依然以剩余能量多少来选取簇，“能量空洞”问题并没有根本性解决；文献［11］中提出了一种基于时间激发的簇头轮换策略，该策略对节点能量同构的网络有较大能耗提升，对于异构网络，因其未考虑节点间距离能耗而采用统一轮换策略，网络的能效不高；文献［12］中提出了一种基于剩余能量激发的簇头轮换策略，根据网络中节点剩余能量多少进行簇头轮换，让能量剩余多的多承担簇头的转发任务，以平衡整个网络的能耗。但当被选簇头能量较低时，频繁的激发簇头轮换也会使网络浪费过多的能量。

针对无线网中节点能量负载不均，簇头轮换激发机制单一，分簇算法能效较低等问题，本文借鉴文献［11-12］中的分簇思想，提出了一种融合时间和剩余能量激发的分簇算法。

1 网络模型与系统能耗计算

1.1 网络模型

假设N个节点随机部署在M × M区域中，汇聚节点sink负责数据汇总。为方便后续计算，对无线网络作如下假设［13-15］：

（1）传感器节点能量有限，传输链路对称，且节点发射功率因距离可调；

（2）各节点有相同的感知半径Rs和通信半径Rc，并且能将部署区域覆盖和连通，节点间不需知道自身位置；

（3）网络部署后各节点位置不变，汇聚节点居于网络中心，能量足够；

（4）网络周期性收集数据，每轮数据收集，节点都要发送相同数据包长度的数据给簇头；

（5）所有节点时钟同步。

本文选择如图1 所示的无线通信模型，考虑发送电路、接收电路、放大器以及传输的数据字节数，一个无线射频收发器将k bit 数据包发送到距离为d 的另外一个无线收发器。

图1 无线通信模型

发送能耗主要由信号发射电路能耗和放大器电路能耗两部分组成，因此，发送k bit 数据到距离为d 的节点上的能耗：

式中：Etx表示接收单位比特数据所需能耗；εamp1、εamp2表示所采用传输信道模型中的参数；β 表示路径损耗常数，与传播环境有关。当d ＜d0时能耗模型采用自由空间模型，此时β = 2，εamp1= 10 pJ/ bit；当d≥d0时能耗模型采用的是多路衰减模型，此时β = 4，εamp2=0.001 pJ/ bit。对于接收节点，接收k bit数据的能耗：

令Eam表示融合单位数据所需能量，则将h 个k bit 数据包融合成长度为k数据包所耗能量为

Ecoll表示节点采集单位数据所需能量，则采集k bit 数据所耗能量为

1.2 簇头选举能耗

在整个无线网络中，节点的能耗主要有两部分：①动态分簇过程中所消耗的能量；②分簇稳定后，数据收集与传输所耗能量，这部分能耗为正当消耗，其所占比例越大，说明算法的能效比越高。

设在动态分簇过程中所耗能量为Ec，稳定阶段数据收集与传输所耗能量Ew，则网络能效率为

从上式可以看出，δ越大，稳定阶段所耗能量占比越大；反之亦然。想要提高整个无线网络的能效率，就是在保证稳定阶段必要能耗的前提下尽量降低动态分簇过程中所耗能量。目前簇头选取主要以竞争型为主。假设无线网络中所有节点分为NNum个簇，则簇内节点数n = NNum/ N，经g 轮簇头竞争后，第i 个节点剩余能量为Egi，簇内所有节点的剩余能量为EgAll，则第i个节点能选为簇头的概率

不同簇头选举协议的不同之处在于簇头选举所依据的标准，至于簇头确定后的能耗相差无几。当簇头轮换条件激发后，簇内节点根据汇聚节点sink 对剩余能量统计信息计算自身成为簇头的概率，广播候选簇首消息（COMPETE_HEAD_MSG）在第g 轮簇头选举阶段的一个时间片内一个节点被选为簇头节点的概率为

任何一个分簇内若有一个节点被选为簇头，则其他节点会立马停止对簇头的竞争，根据当前簇头节点信息进行入簇，一个节点在第g 轮簇头选举阶段第t时间片成为簇头的概率

根据式（11）和（12），在第g 轮簇头选举阶段，簇头选举成功所发送的簇首消息的数学期望为

在第g轮簇头选举阶段若有Ni个节点参与过簇头竞争，则有：

因有Ni个节点参与簇头竞争，那么簇内接收候选簇首消息的节点有n - Ni，又因时间片空闲概率为1 -表示在第g 轮簇头选举阶段的一个时间片空闲内平均接收候选簇首消息，则在第g 轮簇头选举阶段簇头选举成功时分簇节点接收簇首消息的数学期望为

根据式（13）和（15），结合式（1），则簇头竞争阶段建立簇头所耗能量估算为

上式等式右边第1 部分表示广播簇头通告帧所耗能量；第2 部分表示接收簇头通告帧所耗能量，这里能耗模型采用自由空间模型，β = 2，εamp1= 10 pJ/ bit。dC表示簇内节点到簇头的平均距离。理想状态下各簇均匀分布，分簇大小为M2/ NNum，分簇半径R = M/

式中：ρ（r，θ）表示节点分布密度，对于节点均匀分布的无线网络，分布密度函数为常量，则

簇头选举成功后，簇内剩余节点就会放弃竞争簇头，转而申请加入该簇，新选定的簇头节点在收到其他节点申请入簇的消息后，以发送确认消息并分配TDMA，这些系统帧也要消耗一定的能量，则在整个簇头竞争阶段最低能耗为：

2 时间和剩余能量激发的分簇算法

2.1 时间激发的分簇算法能效率

文献［11］是基于时间激发的簇头轮换算法，在簇头竞争结束后，新簇头按照时分多址（TDMA）机制对簇内节点分配时间片段，簇内节点在簇头分配的时间片内将需要发送的数据发送给簇头，发送数据帧结构如图2 所示。

图2 TDMA数据帧结构

在稳定阶段，节点会在分配时间片内连续发送s个等长数据帧，在这种簇头时分多址的调度中，未被分配时间片的节点就会进入休眠中，以节省自身能量。分簇在经过s轮数据发送后，自动激发簇头轮换，那么一轮数据传输簇头所耗能量为

式中：dS表示簇头节点到汇聚节点的距离。簇内所有节点将数据传输给簇头所耗能量为

无线网络在传输s 轮数据后进行簇头轮换，则在稳定阶段分簇所耗能量为

根据式（5）、（19）、（20）、（22）可得文献［11］的能效率：

基于时间激发的簇头轮换有两个瓶颈：一是分簇算法若是应用于异构无线网络中，簇头的轮换是机械的依时间为基准，这种不贴近时间情况的簇头轮换势必会增大簇头竞争阶段的能耗，降低无线网络的能耗率；二是在无线网络的整个寿命周期内，基于时间激发的簇头轮换算法其能效率基本不变。这就无法通过改进算法来提高能效率。

通过简单推导来证明文献［11］中的能效率，将式（23）进行归一化可得：

无线网络中，在网络节点部署完后，簇头在竞争阶段的能耗Ecluster_setup是一定的，而稳定阶段数据的传输所耗能量跟网络模型和节点的通信距离相关，那么在网络模型既定，节点分布均匀的网络里，Ecluster+ Enode可以认为其变化不大。由此可知能效率δTime是一个与数据传输轮数相关的函数，无线网络中，稳定阶段的数据传输轮数也是既定的，这就说明文献［11］的能效率随着传输轮数的增大而降低。

2.2 剩余能量激发的分簇算法能效率

文献［11］是基于时间激发的簇头轮换算法，没有考虑节点自身情况，刻板地以时间单位作为簇头轮换的触发条件，这不适用于节点能量异构的网络。而文献［12］中以节点剩余能量作为簇头轮换的激发条件，让剩余能量多的节点承担簇头，这有利于平衡网络节点能耗不均。在文献［12］中设置一个触发簇头轮换的能量阈值

式中：σ∈［0，1］为调节参数；Erem（i）表示节点当选簇头时所剩能量值。当簇头节点剩余能量低于能量阈值αi时，簇头轮换被激发，无线网络根据节点剩余能量值开始重新选举簇头，此时簇头传输数据所需能量为

式中：Eelec表示节点在竞争簇头阶段所耗能量，在没有网络堵塞时，其主要包括广播候选簇首消息、接收各节点入簇消息、分配时分多址时间片消息等，其下限值

通过上式可以看出，数据传输的轮数随着节点剩余能量而变化，分簇在βg，i轮的数据传输所耗能量为

通过上式可以看出，能效率δrem_Dr不仅与调节参数σ有关，还与节点的剩余能量Egi有关，这样的能效率能实时反映无线网络能耗情况。

但随着被选簇头能量的逐渐降低，簇头轮换的次数将越来越频繁，致使网络浪费过多的能量。下面对簇头轮换前数据传输轮数βg，i进行推导，设

式中：Ea、（Etx+ εamp1dβ）、Eam在无线网络初始化完毕后都是定值，所以数据传输轮数βg，i与（1 - σ）Egi正相关。当节点剩余能量Egi越小，用于稳定阶段数据传输的能量越少，数据传输的轮数也会变少，簇头轮换的频率将加大，簇头竞争阶段的能耗将增多，整个无线网络的能耗率会随着节点能量的减少而降低。这是基于剩余能量激发的分簇算法的重要弊端。

2.3 分簇算法流程

通过分析可知，基于时间和剩余能量激发的分簇算法各有利弊。在节点生命的初期能量充足，基于剩余能量激发的分簇策略能取得较好的能效率；当节点剩余能量不足时，为避免频繁激发簇头轮换而浪费能量，启用基于时间激发的分簇策略更有利于提高无线网络的能效率。

为此，本文融合两者的优点，以两者的能效率大小为界，分别激发簇头竞争的不同策略。当δrem_Dr≥δTime时，融合分簇算法采用剩余能量激发分簇；δrem_Dr＜δTime时，融合分簇算法切换到基于时间激发分簇。δrem_Dr=δTime时：

式中，簇头竞争所耗能量Ecluster和单轮节点数据传输是无线网系统性能耗，其值在网络模型建立后基本不变，那么剩余能量的临界值Ecri的大小仅与调节参数σ和数据传输轮数s 有关，显然这两个参数的大小决定着分簇算法切换的时机。

在网络模型既定，其他参数确定的情况下，各分簇算法的分簇初始建立和稳定数据发送两个阶段都大同小异，主要的区别在簇头竞争阶段。

（1）分簇建立。汇聚节点根据掌握的全网节点信息计算剩余能量并广播给各个节点，节点根据自身剩余能量计算参与簇头竞争的概率Pgi，剩余能量多的节点参与簇头竞争的概率就大，优先广播候选簇首消息（COMPETE_HEAD_MSG）和确认簇头消息（FINAL_HEAD_MSG），对比自身剩余能量后，对于不参与簇头竞争的节点来说，广播退出簇头竞争的消息（QUIT_ELECTION_MSG），这就将自身标记为普通节点，等待新簇产生；依据网络初始化设置所建立的簇数，候选簇头节点继续广播候选簇头消息，一旦周围没有候选节点广播信息，候选簇头就会普通节点根据接收候选簇头消息信号的强弱决定加入哪个簇，并向其发送入簇消息（JOIN_REQ_MSG）或拒绝入簇消息（JOIN_DENY_MSG）。簇头确定后，周围节点不断向簇头节点发送入网申请，直至分簇成立。

（2）数据发送。在数据发送阶段，簇头汇集簇内成员的感知信息发送到汇聚节点sink。簇头节点在进行数据发送前，会将自身剩余能量与剩余能量临界值Ecri进行对比，以确定之后采取何种簇头轮换协议。然后簇头节点广播簇内系统帧，按照时分多址（TDMA）机制对簇内节点分配时间片段，簇内节点在簇头分配的时间片内将需要发送的数据发送给簇头。完成数据收集后，簇头节点将所有数据进行处理经路由传至汇聚节点sink。

（3）簇头轮换。激发簇头轮换的条件不仅有簇头节点的剩余能量还包括网络故障或汇聚节点异常，任何一种条件被激发后，簇头节点都会立即将此消息通知汇聚节点sink。接下来算法启动簇头竞争轮换，簇头会广播簇头重建消息（CLUSTER_REBUILD_MSG）到簇内各节点和汇聚节点sink；簇内节点接收到簇头重建广播消息后将自身剩余能量信息发送给簇头，簇头将收集到的簇内节点剩余能量信息发送给汇聚节点sink，汇聚节点在接收各分簇簇内节点剩余能量的同时广播簇头解除消息（CLUSTER_DISMISS_MSG）到全网，全网启动簇头竞争轮换。簇头竞争轮换伪代码如下：

Step1：Setup（）；/ /初始化无线网络参数

Step2：if（round = 1）then

计算Pgi；/ /如果是第一轮计算节点为簇头的概率Pgi

endif

Step3：广播簇头选择命令；

Step4：CH_Selection（COMPETE_HEAD_MSG，FINAL_HEAD_MSG，QUIT_ELECTION_MSG）；/ /簇头选择

Step5：CH _ Constrution（CH-ADV-MSG，JOIN _ CLUSTER _MSG）；/ /簇头建立

Step6：计算剩余能量的临界值Ecri；

Step7：if（Egi≥Ecri）

｛while（Erem（i）≥σEgi）

Data_Collection（）；/ /接收簇内数据

Data_Transmission（）；/ /簇内数据传输

当前簇头向汇聚节点Sink发起轮换簇头的请求；

当前簇头发送各节点剩余能量到汇聚节点Sink；

goto Step2；

｝

Step8：else执行下一步；

Step9：节点Sink启动基于时间激发的簇头轮换；

Step10：if（round = 1）then

计算Pgi；/ /如果第一轮计算节点为簇头概率Pgi

endif

Step11：CH_Selection（）；/ /分簇选择

Step12：CH_Constrution（）；/ /簇头建立

Step13：Time_Round = s；/ /设定时间分簇轮数

Step14：

while（Time_Round ＞0）

｛

Data_Collection（）；/ /接收簇内数据

Data_Transmission（）；/ /簇内数据传输

Time_Round - -；

｝

Step15：goto Step10；

2.4 分簇算法的复杂性

无线传感网络中节点的能量是有限的，过于复杂的算法会加快消耗节点的能量，缩短整个传感网络的生命周期。根据网络模型中的假设，汇聚节点的能量是足够的，这里可以将复杂的信息处理和计算交给汇聚节点，而算法的复杂度主要由节点间的信息量决定的。

在基于剩余能量激发的簇头轮换中，汇聚节点首先要广播分簇重建帧，然后N 个广播候选簇首消息（COMPETE_HEAD_MSG）和确认簇头消息（FINAL_HEAD_MSG），对比自身剩余能量后，对于不参与簇头竞争的普通节点来说，广播退出簇头竞争的消息（QUIT_ELECTION_MSG）。因此Num - N个普通节点要发送Num - N个入簇消息JOIN_REQ_MSG，因此信息量总和为Num + N + N + N + Num - N = 2（Num +N），所以每轮分簇轮换的复杂度为O（Num）。

在切入时间激发的簇头轮换后，无线网络中不再需要判别簇头轮换，而是以时间片作为驱动，其信息量复杂度与基于时间激发的分簇协议无异。由此可见，本文基于时间和剩余能量激发的分簇协议不会增加整个算法的复杂度O（Num）。

3 参数设置与仿真对比

在本文混合分簇协议中，节点的临界剩余能量值Ecri与剩余能量分簇的调节参数σ 和时间激发的分簇传输中数据传输轮数s 息息相关，这两个关键参数决定着时间和剩余能量激发的分簇协议启动切换的时机。为了计算本文协议中的关键参数，设节点分布在（100 × 100）m2的区域内，汇聚节点sink 默认坐标为（50，50），节点总数为200，簇头比例为5%，数据和命令帧的长度为256 bits，εamp1= 10 pJ/ bit，Eam= 5 nJ/ bit，Etx= 50 nJ/ bit。

3.1 时间激发分簇中传输轮数s值

假设从基于剩余能量分簇协议切换到基于时间激发分簇协议的节点剩余能量最小值为Emin，簇头节点在一轮数据传输中所耗能量为Ecluster，普通簇内节点一轮数据传输中所耗能量为Enode，那么簇头和簇内节点在整个传输节点所耗能量为：

在一轮传输中Ecluster包括接收簇内节点信息、融合所接收数据信息以及将融合信息发送到汇聚节点的所有能耗；而在一轮传输中Enode包括簇内节点发送数据到簇头节点所有能耗，故：

根据文献［16］的证明可知，在一个含有n 个节点的分簇中，若一个节点仅充当过一次簇头和n - 1 次普通节点，那么存在一个最大传输轮数s，满足：

节点剩余能量最小值E由汇聚节点统计得，无min线网络既定的情况下，式（40）其他参数很容易确定，由此可以大体计算出时间激发分簇中传输轮数s值。

3.2 剩余能量激发分簇中调节参数σ

基于剩余能量的分簇轮换受能量阈值α 的直接影响，而阈值α的取值不仅与当选簇头的剩余能量有关还与调节参数息息相关。将能量阈值α 按照文献［18］中进行设置，即α = 0.1 J，从剩余能量的分簇轮换所耗能量可以看出，调节参数的大小与簇头通信所耗Ecluster有关。当簇头节点与汇聚节点相近时，Ecluster就小，反之簇头通信所耗Ecluster就大，为了计算调节参数σ与簇头、汇聚节点距离关系，这里设定汇聚节点处于两种不同的位置：一种是处于无线网络区域的中心，即坐标（50，50）；另一种是处于无线网络区域的外围，即坐标（150，50）。以第1 个节点死亡时间来计算无线网络生命周期，考察数据传输轮数与调节参数σ的关系，结果如图3 所示。

图3 数据传输与调节参数的关系

从图3 可以看出，不论汇聚节点处于中心还是无线区域外，σ与数据转发轮数的关系大致相当。都是随着σ的增大，数据传输轮数先增大后减少。当汇聚节点处于网络中心，σ = 0.614 时，取得最大数据传输轮数；当汇聚节点处于网络外，σ = 0.568 时取得最大数据传输轮数。根据对网络模型的假定，本文主要考虑汇聚节点处于无线网络的中心，所以这里设置σ =0.568。

为了检验和对比各分簇算法的性能，应用本文分簇算法改进LEACH协议，在NS2 仿真环境下，将本文改进后的算法与文献［11-12，17］进行对比分析。其中文献［11］中的最优数据传输轮数参考其文章设定，文献［12］的最优最优能量阈值参照文献［18］设置。仿真是在Windows 7 系统的NS2 平台上，CPU：i5-7500@3.4 GHz，RAM：8 GB。根据网络节点能量的不同设置节点能量同构和节点能量异构两种实验环境：

Env1 无线网络节点随机分布在（100 × 100）m2的区域内，各节点能量值为0.5 J，汇聚节点能量足够，分布于网络中心；

Env2 无线网络节点随机分布在（100 × 100）m2的区域内，各节点能量值随机在［0.1 J，1 J］，汇聚节点能量足够，分布于网络中心。

3.3 网络生存时间对比

网络生存时间是衡量分簇协议的一个重要指标，但对网络生存时间的定义也不同：一种是以第1 个节点死亡时间为网络生存时间［19］；另一种以低于存活节点比例的时间为网络生存时间［20］。这里以第2 种定义形式计算网络生存时间。图4 显示了4 种算法在能量同构和能量异构环境上的网络生存时间。

图4 4种算法在不同环境下的网络生存时间

在能量同构还是在能量异构中，本文分簇算法对比文献［11-12，17］均取得更好的网络生存时间。在能量同构环境下，以剩余能量作为激发簇头轮换的文献［12］反而节点存活数下降的更快，这是由于各节点的能量是相同的，节点剩余能量差别较小，频繁的簇头轮换加剧了节点能量的消耗；而文献［11］是以时间片激发簇头轮换，这种策略本身就忽略了节点能量的差异，节点的能耗相对平均，节点存活数的降幅和网络生存时间相较于文献［12］有较好的结果；文献［17］以“能者多劳”原则选择簇头，意在均衡节点的能耗，在同构环境下结果与文献［11］相近，但到网络生存后期，剩余能量多的节点工作时间更长，一定程度上延长了网络生存时间；本文分簇算法前期以时间片激发分簇为主，后期以剩余能量激发分簇，较大程度上延长了网络生存时间。

在异构环境下，4 种分簇算法所获得的网络生存时间长短不一，差距较大。本文分簇算法和文献［17］相较于文献［11，12］一定程度上提升了网络生存时间。以时间片激发簇头轮换的文献［11］效果最差，这是由于节点能量不一，固定的时间片激发轮换过早使能量低的节点早死；文献［12］以剩余能量大小为激发条件，较好均衡了节点能量不一的现实，但在后期节点能量普遍较低时，频繁的更换簇头会加快节点能量消耗；而文献［17］中剩余能量多的节点当簇头的次数和时间越多，这虽然能使节点能耗均衡，但也会造成剩余能量多的节点死在当簇头的过程中。

3.4 网络能效率对比

提高无线网络的能效率一定程度上可以延长无线网络生存时间。图5 为4 种算法在能量同构和能量异构上的能效率。从图可以看出，随着数据传输轮数的加大，各算法的网络能效率都呈现下降的趋势，总体上本文分簇算法比文献［11-12，17］有较高的网络能效率。在图5（a）节点能量同构环境下，数据传输前期，文献［11］的能效率要高于文献［12］，但随着节点能量的耗尽，机械的依靠时间片激发分簇会增加网络无用的能量消耗，所以在数据传输后期，文献［12］的能效率反而高于文献［11］，本文分簇综合文献［11-12］的思想，平均能效率相较于文献［11-12，17］分别提高了至少28.62%、39.91%和13.94%。

在图5（b）节点能量异构环境下，随着数据传输轮数的加大，各算法的网络能效率都呈现下降的趋势，由于节点的能量不一，文献［11］依靠时间片激发分簇会增加网络无用的能量消耗使剩余能量少的节点早死，所以数据传输后期无线网络失效，能效率变为0；随着节点剩余能量降低，文献［12］分簇频率加大，无用消耗也随之增加，能效率会在传输后期下降更快，但总体上要强于文献［11］；文献［17］是以固定的网络延时Tm为基准，剩余能量越多的簇头工作时延越长，这种设计在异构环境中与文献［12］思想相似，在网络运行前期，簇头转换次数较少，能效率较高，但到后期能效率也会较快降低；在本文分簇算法平均能效率相较于文献［11-12，17］分别提高了至少48.22%、37.14%和20.23%。

图5 4种算法在不同环境下的网络能效率

4 结 语

本文提出了一种融合时间和剩余能量激发的分簇算优化算法。分析了基于时间和剩余能量激发分簇算法能效率受限的原因，重新定义剩余能量阈值，并以此作为激发簇头竞争的临界条件，避免网络后期节点能量降低时簇头频繁竞争带来的能耗，从而整体上提高整个无线网络的能效率。仿真实验表明，与其他3 种簇头轮换算法相比，本文算法不仅有较高的能效率，还大大延长了网络生存时间。