能量平衡的无线传感器网络数据采集动态分簇算法

陈宏滨， 陈 琪

(桂林电子科技大学 信息与通信学院，广西 桂林 541004)

随着互联网时代的发展，物联网在工业领域具有广阔的应用前景[1]。由大量部署在监测区域的传感器节点互相通信组成的无线传感器网络是物联网底层的重要技术形式。无线传感器网络中重要的应用之一是数据采集[2]，但是在一些应用场景如军事基地等，传感器节点的能量有限且不便于随时进行补充，因此在无线传感器网络的数据采集过程中，能量使用效率是一个需要关注的问题。

在无线传感器网络中，通常节点数量较多且有些节点之间距离很远，聚类传感器节点是延长传感器网络寿命的重要方法之一[3]。聚类包括对传感器节点进行分簇，然后从每个簇中选出一个簇头，对每个节点的数据进行汇总，再将收集到的数据转发给基站。因此，为了提高网络的生存时间和剩余能量，分簇算法和簇头节点的选择变得越来越重要。在无线传感器网络中数据协议有很多，但基于聚类的分层路由协议由于提高了可扩展性而受到更多的关注。LEACH是经典的低功耗自适应分簇算法[4]，但是簇头的选择仅考虑了概率因素，导致有些能量过低或位置偏远的节点担任簇头，造成能量消耗不均衡，出现路由空洞[5]。在簇头选举方面，梁玉珠[6]设置基于节点剩余能量的时间退避机制，使得高能量节点更容易在簇头选举阶段胜出，提出了由此保存簇头的数量来实现全局能耗的均衡。谢双双等[7]依据节点距离[8]、密度及剩余能量3个方面进行簇头选择，解决了由簇头因素导致的能量消耗不均衡问题。在分簇的有效方式方面，李彬等[9]以sink节点为原点划分角幅度相等区域辅助分簇规则，但是簇头的能量消耗会随着距离的增加而增加。Wei等[10]根据节点到sink节点的距离来确定合适的簇的大小，提出一种分布式聚类算法，启发了本研究考虑能量因素来确定合适簇的大小。当簇的规模较大时，单跳传输比多跳传输会消耗更多的能量[11]。考虑到节点间通信的能量消耗、节点剩余能量、节点到sink节点的距离，Zhang等[12]采用单跳路由和多跳路由相结合的方式在簇头之间进行数据传输，与LEACH算法对比，提高了数据传输效率与网络生命周期，但多跳传输容易导致数据传输延迟。无线传感器网络中引入移动采集器，可避免簇头间的多跳传输，是一种平衡终端节点负载，提高数据采集效率，延长网络生存周期的有效方式[13-14]。Zhang等[15]基于节点密度分簇，使用移动采集器进行簇间数据采集，提出了一种分层路由与移动采集器相结合的算法，在节约能耗与数据采集效率之间有很好的折中效果。Zhao等[16]使用多个簇头来平衡负载，提出一种分布式负载均衡聚类算法，但是当簇头节点过多时，会失去节点分簇的意义。

本研究针对各簇节点数量不同、总剩余能量不同和节点采集数据的速率不同等因素研究基于能量均衡的动态分簇算法(energy balanced dynamic clustering algorithm，简称EBDCA)，主要创新点如下：在簇的初始形成阶段，同时考虑节点的位置与距离因素，以及各簇总能量均衡的问题成簇，根据能量变化情况，采用动态分簇的策略调整分簇情况；在簇内数据传输方式上，弹性考虑节点间距离与能量因素，并根据竞争函数值将节点数据进行分级传输，减少了簇内通信消耗；在簇头选举方面，直接选用簇内一级节点中剩余能量最高的节点作为簇头，避免了距离簇中心很远但剩余能量很大或者距离簇中心很近但剩余能量很小的节点成为簇头。 从而维持了数据采集过程中网络能量的动态平衡，延长了网络生命周期。

1 系统模型

假设在一个正方形区域A中，均匀随机部署n个静态传感器节点X={x1,x2,…,xn}，sink节点位于区域中心。为了方便研究簇间的能量平衡状态，作如下假设：

1)各传感器节点位置信息设定为已知，且初始能量不一致，数据采集速率随机；

2)节点一经部署不可移动且节点之间无障碍物；

3)节点之间的通信链路是双向的、对称的；

4)移动采集器搭载了太阳能电池，可以随时进行能量补充。

1.1 网络模型

采用分层的无线传感器网络模型。节点部署后均为静止状态，由一个移动采集器经过各簇头节点对簇内数据进行采集，簇的大小根据节点的能量分布差异而有所不同。各级节点数量逐级递减，节点数据逐级上传，其中三级节点的数据上传至二级节点中，二级节点的数据则上传至一级节点，一级节点数据上传至簇头。传感器网络模型如图1所示。

图1 传感器网络模型

1.2 能耗模型

在传感器网络中，数据传输的通信过程往往是节点能耗产生的主要部分。使用与文献[17]相同的能量模型，假设通信距离为d，根据发射机和接收机之间的距离与阈值d0的大小关系，分别采用自由空间信道(d2的能量耗散)和多路径衰减信道(d4的能量耗散)，传感器单元的能耗率取决于传输距离和数据大小。节点i发送m数据至距离为d的节点j的能耗ETX为

(1)

节点接收m数据所需能量消耗为

ERX=mEelec，

(2)

其中：Eelec为发送/接收1 bit数据的能量损耗；εfs为当d≤d0时发送电路的放大系数；εamp为当d>d0时发送电路的放大系数。

2 EBDCA描述

传感器网络中能量的平衡状态会影响整个网络的生命周期。EBDCA的基本思想就是根据竞争函数构建能量均衡的簇并且根据能量平衡函数是否低于阈值来动态地调节分簇，使得网络内节点能耗动态的维持一个平衡状态。

使用能量比值lb来表示各簇间的能量平衡状态值，根据该比值与阈值l0的比较，判定该网络是否处于能量平衡状态：

(3)

其中：Emax为该网络中最大总能量簇的能量值；Emin为该网络中最小总能量簇的能量值。

在簇的构建阶段，以各簇头为参考，节点根据竞争函数值选择加入哪个簇，竞争函数fij动态考虑了节点的剩余能量以及距离因素：

(4)

其中：λ为竞争函数的权重因子；eres为节点的剩余能量；ditoj为该节点和簇头之间的欧氏距离。

最佳簇头个数kopt的计算式[6]为

(5)

其中：M为网络覆盖范围的半径；d为簇头到sink的距离期望。

2.1 能量平衡动态分簇算法

K-means算法是一种简单且经典的基于距离的聚类算法，其簇头节点有较好的形成簇的基础。但K-means算法的k值不易确定，对于网络的初始分簇个数k，参考文献[18]计算网络总数据量，除以单个节点最大数据承载量vmax，获得初始分簇个数k。K-means算法的另一缺点是分簇仅考虑了距离因素，未考虑能量因素对分簇好坏的影响。在成簇阶段使用由能量与距离因素构成的竞争函数参与簇的形成，并依据能量平衡状态动态控制簇的形成过程，以维持网络的能量平衡状态，延长网络生存周期。设α、β为加入簇节点数量参数，具体算法描述如下：

1) 用K-means算法获取k个簇头的位置信息，将它们标记为C={Ch，i|i=1:k}。

2) 计算各簇头到基站的距离期望，得到最优簇头数kopt，若k≠kopt，则将kopt的值赋给k, 回到步骤1)；若k=kopt，则簇头选定成功。

3) 第一批节点选择簇头加入对应的簇：以选定簇头为参考，着重考虑能量因素，计算普通节点到各簇头的竞争函数f值。假设每个簇应有成员节点有s=n/k个，各簇头吸收其竞争函数的前s/α个节点作为第一批吸收的簇成员节点。

4) 计算已形成的各簇的剩余能量，目前总剩余能量最高的簇的总能量记为Emax，其余各簇目前剩余能量记为Eres，Ci，各簇能量与剩余能量最高簇的能量比值记为li=Eres，Ci/Emax。

5) 若li≥l0，则簇头Ch，i暂停一轮吸收新节点加入该簇；若liα)个节点吸收为新的簇成员。

6) 重复步骤4)、5)，直到所有节点均加入簇。

在算法中验证k值是否为最佳kopt的计算需要已知簇头节点坐标，所以要先进行k值的假设，得到簇头信息再进行最佳k值的验证。节点分为多轮加入相应簇头成为簇成员。一方面为了便于对簇间能量平衡状态进行评估，因此在第一轮使得更多的节点加入簇，且竞争函数赋予节点剩余能量更大的权重因子。另一方面为了便于动态调节分簇来维持簇间能量平衡，接下来轮次加入的节点数量将减到较小的比例，同时为了使得新加入的节点不会过于偏离簇中心，增加传输能耗，将赋予距离因素更大的权重因子。

首次成簇后，簇的规模在一定时间内不再改变，整个网络的节点进入稳定工作阶段，成员节点将采集到的数据通过多跳的方式发送至簇头。但为了平衡整个网络的能耗，每T0轮检查一次各簇的能量平衡状态，在满足特定条件，即lb

2.2 簇内节点数据分级算法

在进行簇内数据传输时，将簇内节点分为三级，采用单跳和多跳路由相结合的方式将节点数据上传至簇头节点。 由于单个簇仅有一个簇头，若簇内节点数据全部单跳上传至簇头节点，容易出现数据溢出的情况。本算法设置少量的一级节点作为簇头的辅助节点，帮助缓解簇头节点的负载压力。在网络覆盖范围较大时，会有一部分距离簇中心较远的节点，在直接发送数据至辅助节点时会产生较大的能耗，为此，设置了一部分二级节点作为缓冲带。而剩余那些剩余能量较低且距离簇中心较远的节点则为三级节点，其数据通过多跳传输到至簇头，簇头节点直接与移动采集器通信，最终将数据发送至sink节点。

1) 节点分级。均衡考虑距离与能量因素，计算竞争函数f的值。设a、b为节点比例的参数，将各簇内f值位于前1/a的节点判定为簇的一级节点Ci,1；对尚未分级节点，将f值排在前1/b的节点判定为簇的二级节点Ci,2；剩余各簇内未进行分级节点，则被判定为各簇的三级节点Ci,3。节点级别由高至低依次为Ch，i、Ci,1、Ci,2、Ci,3。

2) 下一跳节点的选择。对于更低一级的各节点数据，均衡考虑能量与距离因素，从三级节点开始以节点为标准依次计算至上一级节点的竞争函数f值，选择f值最大的作为下一跳传输节点，一级节点数据上传至簇头。

3) 将一级节点中剩余能量最高的节点更新为簇头Ch，i。

由于通信阶段的能耗与节点之间的距离成正比，更高一级的节点的通信负载更大，需要有更多的能量保证，因此在节点分级过程中计算节点的竞争函数值时，均衡考虑能量与距离因素。簇头节点负责簇内数据与移动采集器的通信，在能耗方面要求较高，各簇中一级节点的集中性较好，于是将簇头更新为一级节点中剩余能量最高的节点。动态的环境导致节点能量使用效率不同，保持一级节点和簇头的剩余能量对该簇节点的生存状态有重要意义，本算法在每轮数据采集都会执行一次节点分级算法。应当注意的是，一级节点的数量应该控制为较小的比例，因为过多的辅助节点会使得簇内能量均衡但是整个簇的能耗过大。

2.3 算法步骤

在数据采集过程中，簇头为路径规划的参考点，移动采集器根据最短路径则与各簇头节点进行通信。具体算法步骤如图2所示。

图2 算法步骤

由于节点设定初始能量不一致，为了获得能量动态平衡的分簇，在分簇阶段采用了“自顶向下”的方式，在节点分级阶段采用“自底向上”的方式。“自顶向下”即先确定簇头位置再进行簇的形成。具体过程为先确定簇头位置，再根据竞争函数值进行节点吸收入簇，通过对能量值的比较结果动态调节分簇进程，最终形成能量平衡的分簇。“自底向上”即在节点分级阶段由低一级节点向更高一级节点进行路径选择，数据最终到达簇头节点。移动采集器通过最短路径[18]的方式遍历簇头，直接对簇头节点数据进行采集并发送至sink节点。重新分簇的原则为：分簇成功后，每T0轮计算一次lb，若lb

3 仿真结果

本仿真在MATLAB R2018a环境下运行。在仿真实验中，300个传感器节点随机均匀分布在1 km×1 km范围内，结果表现了进行2 000轮数据采集的性能。各节点的初始能量为1 J，数据生成速率随机，节点初始能量不一致，Eelec为50×10-9J/bit，εfs为10×10-12J/bit，单个节点最大数据承载量vmax为8×104bit，α=3，β=10，a=8，b=3/5，T0=50。为了验证EBOCA在能量平衡方面的优越性，将EBDCA与经典LEACH、HMDC[18]算法在数据量、簇能耗方差、死亡节点数、节点剩余能耗方差与死亡节点数乘积几个方面进行比较。

图3为节点采集的总数据量随着采集轮数的变化。在同样的初始条件下，EBDCA采集的数据量远多于LEACH算法，略多于HMDC算法。由于EBDCA考虑的是网络整体能量平衡，其性能优势会随着采集轮数的增加而更加明显。

图3 节点采集的总数据量对比

图4为各簇的能耗方差随着数据采集轮数的变化。簇能耗方差很好地体现了各簇能耗与簇均能耗之间的偏离程度，簇能耗方差越小，表明整个网络各簇的能量消耗越均衡。显然EBDCA中簇能耗方差远远小于LEACH算法。在数据采集初始阶段，EBDCA处于整个网络能量的平衡调整阶段，因此能耗方差略大与HMDC算法，但随着数据采集轮数增加，整个网络能量平衡的状态趋于稳定，EBDCA的簇能耗方差在绝大多数轮次都处于优势，浮动幅度相对稳定，且远小于HMDC与LEACH算法。

图4 簇能耗方差对比

图5为累计死亡节点数随数据采集轮数的变化。LEACH、HMDC、EBDCA的第一个死亡节点分别出现在第100、110、400轮左右。而且，在数据采集进行到2000轮时，EBDCA的死亡节点数仅为LEACH算法的12.1%，HMDC算法的59.3%。由此可看出，EBDCA有效地延长了无线传感器网络的生命周期。

图5 死亡节点数对比

图6为节点剩余能量方差与死亡节点数乘积随着数据采集轮数的对比。节点剩余能量方差很好地体现了无线传感器网络中各节点的能量状态，节点剩余能量方差越小，各簇内的能量平衡状态越好。在一定的采集轮数下，死亡节点越少，整个网络的能量平衡状态越好。LEACH节点由于前期死亡节点数量较大，后期死亡节点数量会很小，在1 750轮后，剩余能量方差与死亡节点的乘积出现明显下降趋势。EBDCA的节点剩余能量方差与死亡节点乘积的值总是低于LEACH与HMDC算法。随着采集轮数的增加，EBDCA的性能优势更加明显。

综上所述，EBDCA在保证一定数据采集量的前提下，很好地均衡了整个网络的能量消耗，使得无线传感器网络的生命周期得到延长。

图6 节点剩余能量方差与死亡节点数乘积对比

4 结束语

提出了一种基于能量平衡的传感器网络数据采集动态分簇算法，以能量为参考构建能量平衡的分簇，并定期检查平衡状态，动态调整分簇。在簇内节点分级进行数据传输时，同时考虑节点间距离与能量因素进行分级，使得簇内节点能量消耗也处于一个更加均衡的状态。仿真结果表明，与LEACH、HMDC算法相比，提出的EBDCA在保证一定的数据采集量前提下，簇间能耗更加均衡，存活节点的剩余能量分布更加均衡，网络生命周期得到延长，且随着数据采集轮数的增加，EBDCA的性能优势更加明显。