WSN 中基于节点密度优化的DB-K-means 分簇算法

2021-04-24胡光远李昊

网络安全技术与应用 2021年4期

◆胡光远李昊

（1.南京六九零二科技有限公司江苏 210009；2.近地面探测技术重点实验室江苏 214035）

1 研究现状

无线传感器网络技术针对恶劣环境与无人区域的感知监测已经成为必不可少的技术。在传统WSN 中，网络结构有平面结构和分簇结构两种。分簇结构适用于大规模网络中，依靠节点的自适应分簇以及数据融合传输实现感知信息的收集与传输。当前对于分簇结构最常用的路由协议为低能量自适应分层路由协议LEACH 算法，因此对LEACH 协议的改进方法一直是国内外学者的研究热点[1]。

文献[2]中介绍了LEACH 协议的相关研究，并针对LEACH 算法的缺陷提出改进的LEACH 算法，传感器将自己的节点剩余能量和位置信息发送给基站，由基站根据发送信息确定合适的簇头数量。文献[3]中，作者提出将K-means 均匀分簇和数据回归的WSN 能量均衡策略进行结合，采用数据回归的方法来减少普通节点与簇首的通信量，以达到降低功耗的作用。文献[4]中，作者提出一种基于K-means 的WSN 移动汇聚路由算法，该算法通过K-means 聚类将网络中的节点划分至不同的集群，选择通信成本最低的节点作为各集群的簇首.稳定传输阶段通过移动Sink 进行数据采集，针对不同的延迟分别规划Sink 节点的移动轨迹。文献[5]中介绍了一种基于Mini Batch K-Means和SVM 的入侵检测方案。该方法利用特征库和异常行为样板库进行Mini Batch K-Means 分簇，取得簇头作为各簇的代表样本设置权值，将其传入SVM 训练器作为训练数据，这样可以有效解决如K-Means，KNN，SVM 等传统分簇算法在大数据样本集数据分析中面临的低效率问题。文献[6]提出一种基于LEACH 协议，K-means 聚类和蚁群算法的WSN 改进路由算法.首先在预处理阶段利用K-means 聚类算法将散布的节点分成多个簇，通过聚类减少数据发送量.其次，利用蚁群算法支持多路径的特点，在数据传输阶段形成簇首间多路由机制。文献[7]提出一种改进的基于加权优化树的路由算法，将树型结构应用于分簇路由算法中.根据节点的剩余能量，可用内存，相邻节点的距离，信道质量设定数据传输代价，并以此为基础对树型拓扑结构进行加权优化，分布式地在簇内创建树型网络拓扑结构.改进的算法降低了网络中数据传输的总代价。文献[8]该路由算法首先基于对网络能耗的理论分析确定WSN 的最佳簇头数目，然后利用二分k-means基于最优簇头数目对节点进行分簇。

传统算法包括改进的LEACH 算法均是根据簇头数决定分簇数。显然，该方法存在一定的随机性，簇头数的过多和过少都不能够有效发挥LEACH 协议的性能。因此，针对传统算法没有根据传感器节点的分布特性确定分簇数目的缺陷，提出DB-K-means 分簇算法，算法首先根据传感器节点的分布密度确定最优分簇数目，进一步对网内所有存活节点进行分类，如核心、边缘、孤立节点，然后从核心节点中进行簇头选举。避免了因随机选举簇头陷入局部最优解的情况。完成簇头选举后，利用K-means 算法完成所有存活节点的建簇。

2 系统模型

2.1 网络模型

假设WSN 网络中，有K个传感器节点随机分布在一个N×Nm2的正方形区域中，基站距离WSN 网络很远，能量不受限。每个传感器节点不可移动且初始能量均等，且都可以直接与基站进行通信。每个传感器节点都能感知到自身剩余能量和位置信息，都有机会当选簇头，承担数据融合与传输的任务。

图1 WSN 系统模型

2.2 能量模型

本文采用与如图2 所示的能量模型图。传感器节点发送lbit 的数据消耗能量由发射损耗和功率放大两部分构成。一个节点经过距离d发送lbit 数据的能耗如下：

其中，l是数据包长度，Eelec是节点能量，εfs和εmp为能量参数，d为节点到基站的传输距离，d0是传输距离的阈值，一般取值为εfs/εmp。当传输距离d小于d0时，采用自由空间信道模型。反之，采用多径信道模型。

图2 能量模型

3 LEACH 分簇及K-means 分簇

3.1 LEACH 协议流程

LEACH（Low Energy Adaptive Clustering Hierarchy）是第一个基于分簇概念实现的路由协议。首先，LEACH 协议将网络分成若干个簇，每个簇由簇头节点和其他节点构成，节点负责将自身感知到的数据信息发送至所在簇的簇头，簇头承担数据融合和将融合后的数据发送至汇聚节点或基站的任务。簇头承担的任务量明显重于节点，因此，簇头的选择对WSN 网络生命周期是至关重要的。

图3 LEACH 协议流程图

LEACH 协议的工作流程如图XX 所示，LEACH 协议是具有自适应和自组织特性地，在每一轮循环中，都是自适应分簇和自组织建簇，进入到稳定阶段后，就可以完成数据融合与汇聚节点的数据传输任务。

3.2 LEACH 的分簇

LEACH 是最经典的一个低能量自适应分簇路由协议。每轮都是随机选择簇头进行簇间信息传输。区域内的节点感知收集信息后发送给各自簇头（Cluster Head，CH），CH 将感知到的信息数据转发到汇聚节点（Sink）或基站。使得终端用户可以在终端设备上获取检测区域的信息。

3.3 K-means 分簇

K-means 算法流程如下图4 所示。

3.4 分簇算法缺陷分析

尽管LEACH 算法有低能量，自适应分簇，但是LEACH 协议的缺点也是很明显的。

首先簇头的选举是随机地，其次分簇的数目也是随机地，如果簇数太多，会增加节点的消耗，反之，簇数太少，会加重簇头的业务压力。因此这些缺陷会导致簇内节点数不均衡，可能会导致网络负载不均衡和加剧损耗网络生命周期。

4 DB-K-mesan 分簇

4.1 密度相关概念

本小节首先介绍一下基于无线传感器件的密度的几个相关概念和密度分布[9]。

eps：节点扫描区域半径。

minpts：节点扫描区域内的阈值节点数。

Neps(k)：节点k的邻域信息。

dis(k,c)：节点k与簇头c间的连接度量。

节点属性：节点k如果满足Neps(k)≥minpts，称节点k为核心节点，如果1＜Neps(k)＜minpts，称节点k为一般节点，如果Neps(k)=1，称节点k为孤立节点。

直接密度可达：如果节点k与节点j满足j∈Neps(k)，则节点j到节点k直接密度可达。

密度可达：如果存在节点链o1o2...on，o1=k，on=j，节点链中的当前节点oi可由上一个节点oi-1直接密度可达，那么节点k到节点j密度可达。

密度相连：如果节点k与节点j均可由节点o直接密度可达，那么节点k与节点j密度相连。

4.2 密度分布

针对传统LEACH 协议在建簇时的簇头选举随机的缺陷，提出一种基于节点分布密度选取簇头的方式，算法流程如图5 所示。

图4 K-means 分簇算法

图5 DB-K-means 分簇算法

如上图所示，首先对传感网内的所有节点进行属性判断，核心节点显然更适合作为簇头，因为核心节点比较密集，反映了传感网内节点的整体分布，因此可以根据直接密度可达、密度可达、密度相连关系构成G 个核心节点簇，这些核心簇反映了网络的整体分布，避免了簇数的随机设置过大，浪费整个网络资源，或者簇数过小，不能发挥分簇路由协议的优势。

核心节点中的簇头更新准则参考以下加权度量准则，有效避免了簇头选举的随机性和容易陷入局部最优解的缺陷。簇头度量权重更新准则：

R=a1x1+a2x2+a3x3

其中，a1a2a3分别为节点剩余能量x1，节点到簇头的欧式距离x2，节点密度可达的节点数x3的权重值，其和为1。因此节点的R值越高，该节点成为最优簇头的可能性最大。

5 仿真分析

5.1 仿真参数

为了验证本文提出的DB-K-means 的性能，利用MATLAB 软件设计仿真验证分簇算法在WSN 网络中的性能，设计仿真参数如下表1 所示：

表1 仿真参数表

针对DB-K-means 算法，本文设计节点的扫描范围半径eps=5，节点扫描区域内的阈值节点数Minpts=15。

5.2 仿真结果

在WSN 网络性能分析中，剩余存活节点数，网络剩余能量是两个重要衡量指标。在表的仿真条件下，图6 与图7 分别对比了DB-Kmeans 分簇与基于K-means 的LEACH 协议的性能指标：网络存活节点数与剩余总能量。

图6 网络总耗能与轮数的关系

图6 为两种算法下网络剩余生存节点数与网络轮数的性能曲线。随着轮数的增加，三种算法的生存节点数都显著下降，当轮数达到600 轮时，K-means 算法仅存几个节点在工作，600 轮时存活节点143，此时DB-K-means 仍然还有183 个节点在工作。DB-K-means 分簇与建簇有效改善了网络的生存周期，统计可得到，DB-K-means 分簇算法的生命周期比k-means 分簇算法更长。

图7 为对比了DB-K-means 与K-means 分簇算法下网络剩余生存节点数与网络轮数的性能曲线。随着轮数的上升，网络剩余能量显著下降，但是DB-K-means 算法的下降幅度远低于K-means 分簇算法，但是随着轮数接近600 轮时，DB-K-means 分簇算法下的网络剩余总能量很接近K-means 算法，这是由于随着存活节点数的减少，节点分布较为发散，DB-k_means 算法性能接近k-means，但是想仍有较高的剩余能量。显然，DB-K-means 能够有效改善网络生存周期。