0 概述

能量消耗问题直接影响着无线传感器网络(Wireless Sensor Network, WSN)的生命周期, 如何降低和均衡传感器节点的能耗, 延长网络生命周期成为WSN研究的热点问题。WSN分簇算法的提出有效降低了无线传感器网络的能量消耗, 延长了网络寿命。低功耗自适应集簇分层(Low Energy Adaptive Clustering Hierarchy, LEACH)^[1]算法以及针对其簇首节点选取的随机性提出的LEACH-C^[2]算法, 是分簇算法的经典算法, 为之后无线传感器网络分簇算法的研究提供了支撑。聚类分析算法能够对大量样本数据, 按照数据之间的相似性进行分类, 与无线传感器网络将网络中的传感器节点进行分簇的思想类似, 因此国内外研究学者将聚类分析算法思想应用到WSN分簇过程中, 对分簇效果进行优化。

文献[3]提出基于改进粒子群聚类的能量均衡无线传感器网络分簇策略, 将网络划分为环状区域, 解决了基站附近节点负载过大造成的节点提前死亡问题。针对模糊C均值聚类算法对初始值敏感的问题, 文献[4]提出一种使用遗传算法改进聚类的WSN分簇算法, 使用遗传算法优化初次簇中心随机选取的情况, 根据适应度函数找到适应度最高的个体, 解码出聚类中心。文献[5]通过优化初始簇中心改进K-means算法对网络进行分簇, 均衡了簇内节点数目。文献[6]提出基于粒子群聚类优化的分簇路由算法, 使用群体智能算法中的粒子群优化算法进行改进, 将节点能量与节点间距离同时加入适应度函数, 计算粒子的最小极值, 得出使得适应度函数最小的全局极值作为聚类中心, 从而延缓首个节点退出网络的时间。针对无线传感器网络能量约束的特点，在分析多种聚类组合算法性能的基础上，文献[7]提出一种基于节点拓扑和能量两类信息，采用改进的SOM+PSO组合聚类算法对WSN节点自组织成簇的方法，在延长网络生命周期和减少能量消耗方面有较好的性能。文献[8]设计的CRACCW算法使用密度聚类算法(CFSFDP)改进无线传感器网络节点分簇, 网络中传感器节点在实际环境部署时不能完全均匀分布的特点为基于密度的聚类算法提供了良好的网络环境基础。以上聚类分析算法应用到WSN分簇过程中均考虑了节点剩余能量、节点间位置或者节点与基站间的距离, 但未将簇内节点数目均匀分布与节点地理位置和节点间位置相结合, 或仅在簇首选举阶段考虑节点位置或节点间距离, 不能较好地均衡和节省网络能量。

本文提出一种基于最优距离和K-means聚类的能耗均衡WSN分簇算法(DBKM)。利用BIRCH算法^[9-11]聚类特征树(Clustering Feature Tree, CF Tree)对网络节点进行集中式分簇, 再采用基于距离的目标函数对分簇结果进行迭代优化, 直至簇内节点数目均衡。

1 系统模型相关理论 1.1 网络模型

本文对无线传感器网络模型^[12]作以下假设:

1) 所有节点在区域范围内随机分布, 节点地理位置不随时间移动, 且节点与基站和其他节点的距离能够通过计算得到。

2) 所有节点初始能量相等, 并可将剩余能量传输至基站, 也能通过基站获取其他簇和整个网络的平均剩余能量。

3) 节点发射功率可调节。

1.2 能量模型

本文采用的网络能耗模型与文献[13]模型相同。发送l bit的信息到距离d处所消耗的能量为:

$ E_{\mathrm{TX}}=\left\{\begin{array}{l}{l \times E_{\mathrm{elec}}+l \times \varepsilon_{\mathrm{fs}} \times d^{2}, d \leqslant d_{0}} \\ {l \times E_{\mathrm{elec}}+l \times \varepsilon_{\mathrm{amps}} \times d^{4}, d>d_{0}}\end{array}\right. $

(1)

其中, E_TX为传输数据信息所消耗的能量, E_elec表示单位比特传输时所消耗的能量, ε_fs表示自由空间模型能耗参数, ε_amp表示多路径放大电路能耗参数, ε_fs和ε_amp的值与系统参数有关, 单位为pJ/bit/m², d₀是节点可以直接通信的距离。

$ d_{0}=\sqrt{\frac{\varepsilon_{\mathrm{fs}}}{\varepsilon_{\mathrm{amp}}}} $

(2)

接收l bit的信息所消耗的能量为:

$ E_{\mathrm{RX}}(l)=l \times E_{\mathrm{elec}} $

(3)

1.3 最优传输距离

无线传感器网络的节点在传输数据信息的过程中, 并非传输距离越近能量消耗越低, 而是具有一定的规律, 根据文献[14]提出的能距比公式可知:

$ E D P(d)=\frac{E}{d}=\frac{10^{-7}}{d}+10^{-10} d $

(4)

其中, E为节点能量, d为节点传输距离。能距比越小, 说明数据发送的能量使用效率越高, 节能效果越好。由式(4)得到的能距比与传输距离的关系如图 1所示。经计算可知, 当节点发送信息时, 将信息发送给距离其d_best=32 m的节点, 发送节点的能量使用效率最高。

2 DBKM算法

本文采用基站集中式分簇的方式。节点部署完成后, 感知位置信息并将其发送至基站, 由基站将网络节点进行分簇, 之后不再进行重新分簇。本文DBKM算法包括聚类特征树建立、分簇结果优化和数据传输3个过程。

聚类特征树建立和分簇结果优化阶段是为了将网络节点分簇, 形成均匀的分簇环境, 主要有以下优点:

1) 对于优化后的最终分簇, 节点能均匀分布到每个簇内, 在后续数据传输阶段可均衡消耗网络能量。

2) 以最优距离d_best分簇, 将簇的大小控制在能量消耗最少的范围内, 簇内节点以最小能量消耗向簇首发送数据信息。

3) 当每个簇的大小都控制在最优传输距离d_best范围内时, 每个簇内节点之间、簇与相邻簇内节点之间的平均距离都能控制在最优传输距离的范围内, 为数据传输阶段提供一个良好的分簇环境。

2.1 聚类特征树建立

聚类特征树是由聚类特征(Clustering Feature, CF)组成的树, 类似于平衡B+树, 是一棵高度平衡的树^[15]。聚类特征是一个三元数组, CF=(N, LS, SS), 其中, N表示CF中样本点个数, LS和SS分别表示样本点属性值的线性和与平方和, CF满足线性关系:CF₁=(N₁, LS₁, SS₁), CF₂=(N₂, LS₂, SS₂), 则CF₁+CF₂=(N₁+N₂, LS₁+LS₂, SS₁+SS₂)。利用线性关系可以记录每个聚类叶子节点中的传感器节点个数, 判断分簇结果均匀程度, 便于后续改进。构建CF Tree有3个重要参数, 非叶子节点的最大CF数B、叶子节点的最大CF数L和簇的最大直径T。本文中样本点即传感器节点, 用集合表示为{X₁, X₂, …, X_N}={(x₁, y₁), (x₂, y₂), …, (x_N, y_N)}, 其中N为网络中的传感器节点个数。

2.1.1 数据预处理

传统聚类特征树的构建过程为:自上而下地扫描CF Tree, 将数据插入到最近的簇中, 数据输入顺序会影响最终分类, 即同一数据因为插入顺序的不同, 可能会被分到不同的簇中, 所以CF Tree的叶节点代表的聚类结果可能不是自然的聚类结果, 应用到无线传感器网络中, 可能导致距离相近的两个传感器节点被分到不同的簇中, 加大数据传输阶段能量消耗。

本文针对此缺陷, 在CF Tree建立前, 将网络中的传感器节点按照由平面二维坐标系的X轴坐标和Y轴坐标表示的传感器节点到基站的欧氏距离排序。排序能够有效减少特征树建立时数据输入顺序不同对成簇结果的影响。

2.1.2 聚类特征树建立过程

聚类特征树建立过程中按照由小到大的顺序扫描由二维坐标表示的传感器节点, 具体过程如下:

1) 选择合适的B、L和阈值T。本文选择最优传输距离d_best作为阈值, 并令B=L=5。

2) 扫描第1个传感器节点作为一个CF元组, 即CF(1, (x₁, y₁), (x₁², y₁²)), 将其作为CF Tree的根节点, 其他数据依次从根节点向下遍历CF Tree, 选择距离数据最近的节点, 直到叶子节点。节点间距离通过欧氏距离进行计算, 即:

$ d\left(X_{i}, X_{j}\right)=\sqrt{\left(x_{i}-x_{j}\right)^{2}+\left(y_{i}-y_{j}\right)^{2}} $

(5)

3) 计算CF元组的半径R, 即:

$ R=\sqrt{\frac{N_{i} \times S S_{i}-L S_{i}}{N_{i}}} $

(6)

其中, N_i、LS_i、SS_i分别为第i(i=1, 2, …)个CF元组中的节点个数、线性和与平方和。然后判断数据插入后CF元组的半径是否超过预先设置的阈值T。若未超过T, 则将数据加入该元组。若超过T, 则判断加入该数据CF元组后叶子节点的CF数是否超过最大数L, 若没有超过L, 则将数据作为新的CF元组插入叶子节点。若超过L, 则分裂此叶子节点, 分裂原则为:选择距离最远的两个CF元组作为新的节点, 剩余CF元组从这两个新的节点中选择距离最近的一个加入。

4) 判断叶子节点的父节点的CF数是否超过最大数B, 若超过, 则分裂此节点, 分裂原则与上述叶子节点的分裂原则相同。

5) 重复上述步骤, 直到所有传感器节点的位置坐标数据都扫描完毕, 加入到CF Tree中。

B=L=5的聚类特征树结构如图 2所示, 其中, CF_i(i=1, 2, …)为CF元组, Child_i(i=1, 2, …)为CF元组中的传感器节点坐标(x, y)。

2.2 分簇结果优化

通过BIRCH聚类特征树建立过程对WSN中的传感器节点进行分簇, 虽然能够有效控制和均衡每个簇的大小, 将每个簇控制在最优传输距离d_best内, 节点能耗最小。由于网络中传感器节点的不均匀分布, 簇内节点数目不能达到均衡, 因此在聚类特征树建立的基础上使用基于目标函数的聚类算法思想进行优化, 改进聚类质量。定义目标函数为:

$ F = \sum\limits_{i = 1}^k {\sum\limits_{{X_i} \in {C_i}} {{{\left( {{x_i} - {x_{{C_i}}}} \right)}^2}} } + {\left( {{y_i} - {y_{{C_i}}}} \right)^2} $

(7)

其中, (x_Ci, y_Ci)为第i个(i=1, 2, …, k, k为分簇个数)簇的质心C_i的二维位置坐标。优化过程如下:

1) 计算出聚类特征树叶子节点所表示的k个分簇的k个质心C_i, 质心计算公式如式(8)所示。

$ C_{i}=\frac{L S_{i}}{N_{i}} $

(8)

其中, N_i、LS_i分别为第i(i=1, 2, …, k)个分簇的节点个数、线性和。

2) 计算节点到k个质心的距离, 并将其加入到最近的簇中。

3) 重新计算每个簇的质心。

4) 重复步骤2)、步骤3), 直到目标函数收敛, 即新的分簇质心与上一次的分簇质心相同或小于等于指定值。

2.3 数据传输

在数据传输时, 簇内节点将数据传输给簇首, 再由簇首以多跳的方式传输到基站。由基站进行分簇后不再进行重新分簇, 每轮只在簇内进行簇首的重新选举, 每轮具体的数据传输路由为:

1) 簇内簇首选举, 簇首为本簇内能量最高的节点。

2) 簇内节点以单跳的方式发送收集数据到本簇簇首。

3) 簇首节点感知自己的剩余能量值res_i和整个网络的平均能量值res, 判断res_i(i=1, 2, …, k)与α×res的大小, 若res_i>α×res, 则直接发送本簇收集到的数据到sink; 否则进入步骤4)。

4) 选择中继节点转发数据。在本簇首与基站节点的方位线上, 簇首节点在其最大通信范围内感知其他簇首节点, 将感知到的簇首节点的能量值res_j(j=1, 2, …, k且j≠i)与整个网络平均能量值进行比较, 若res_j>α×res, 则将此簇首节点加入候选节点集。然后, 判断候选节点集是否为空, 若不为空, 则选择剩余能量最大的节点作为转发节点; 否则进入步骤5)。

5) 在本簇首与基站节点的方位线上, 簇首节点将最大通信范围内感知到的簇首节点的能量值res_j(j=1, 2, …, k且j≠i)与本簇首节点的剩余能量值res_i进行比较, 若res_j>res_i, 则将此簇首加入到本簇首的转发候选节点集。然后, 判断候选节点集是否为空, 若不为空, 则选择剩余能量最大的节点作为转发节点; 否则本簇首直接传输数据到基站。

6) 中继节点继续从步骤3)开始选择中继节点, 直到数据传输到基站。

如图 3所示, C₁~C₄表示簇首节点, sink表示基站。当C₁所在的簇平均剩余能量小于网络平均剩余能量时, 会在簇首C₂、C₃、C₄中选择符合条件的簇首作为转发节点, 其中簇首C₂、C₃、C₄与C₁在基站节点同一方位。

3 仿真结果与分析

使用Matlab2014a版本对本文算法进行仿真, 在200 m×200 m的区域内随机部署200个节点, 基站节点在网络中心位置(100 m, 100 m), 每个节点初始能量设为0.5 J。随着数据传输计算能量消耗, 并在簇内节点数目和数据传输结束后的网络剩余能量等方面进行比较。为验证本文算法, 与其他聚类算法进行比较, 网络环境和仿真参数设置与文献[5]相同, 如表 1所示。

3.1 分簇结果比较

为验证使用目标函数后簇内数目的均匀效果, 对于在200 m×200 m的区域内随机部署的200个节点, 分别对目标函数优化前的BIRCH聚类特征树分簇和目标函数优化后的DBKM算法分簇进行比较, 实验结果分别如图 4和图 5所示。

从图 4和图 5可以看出, 网络中的200个节点分成20个簇, 其中每个簇用不同的符号表示。图 4使用目标函数优化前的BIRCH聚类特征树分簇, 可以明显看出分簇后簇内节点分布不均, 而图 5使用目标函数优化后的DBKM算法, 在网络节点分布不匀的情况下, 簇内节点数目也能最大限度地达到均匀分布。

目标函数优化前的BIRCH、目标函数优化后的DBKM算法及簇头比例为0.1的LEACH算法的簇内节点数目分布情况如图 6所示。可以看出, BIRCH算法和LEACH算法存在簇内节点数目小于5及大于16的簇, 而使用DBKM算法的分簇, 簇内节点数目均衡分布在6~15范围, 从而表明DBKM算法簇内节点数目更加均匀。

3.2 网络能耗和生存时间

将DBKM算法、K-means^[5]算法、LEACH算法^[1]和LEACH-C^[2]算法从节点死亡个数和网络剩余能量两方面进行比较。图 7为各轮剩余节点个数的比较。可以看出, LEACH算法、LEACH-C算法和K-means算法第1个节点死亡时间分别在800轮、1 000轮、1 200轮左右, 而DBKM算法第1个节点死亡的时间稳定在1 380轮左右, 分别比LEACH和LEACH-C算法提高了72.5%和38%, 可以看出DBKM算法有效延长了网络寿命。

图 8为各轮节点剩余能量对比。可以看出, DBKM算法在前500轮能量消耗较快, 这是因为初始传输能量时, 大部分簇首节点的剩余能量大于平均剩余能量, 不需要其他节点的转发直接传输数据到基站, 所以能量消耗较快。但是在经过500轮后, DBKM算法的网络平均剩余能量消耗速度远低于其他3种算法, 在算法运行到1 000轮时, DBKM算法的剩余能量比K-means算法高50%左右。在这3种算法节点全部死亡后, DBKM算法的剩余能量还能保持在初始能量的44%左右。

随着算法轮数的增加, 对各轮死亡节点数目和剩余能量的比较可以看出, DBKM算法可有效增长网络节点死亡的时间, 并减缓网络剩余能量的消耗速度, 有效延长网络生命周期。

4 结束语

本文在传感器节点最优传输距离的基础上, 将层次聚类算法思想应用到无线传感器网络分簇算法中, 并通过目标函数优化分簇效果, 使得无线传感器网络的簇内节点数目更加均匀。同时, 在考虑节点剩余能量和地理位置的基础上设计节点转发路由。实验结果表明, 本文算法能够有效均衡网络分簇, 延长网络整体寿命。但为了节省内存和减少计算量, 数据传输阶段的路由仅粗略考虑传感器节点在网络中的大致方位, 因此下一步将设计基于剩余能量与地理位置的簇首选举与路径传输公式, 优化路由路径, 进一步均衡和节省网络能耗。