一种基于K-means 的WSN 移动汇聚路由算法*

陈轶林，吴正坤，江凌云

（南京邮电大学 通信与信息工程学院，江苏 南京 210003）

0 引言

无线传感器网络（Wireless Sensor Network，WSN）是当今无线技术领域的关键组成部分。资源受限一直是无线传感器网络的最大特点，网络中节点的计算和存储数据能力较弱，一旦网络中部分节点的能量耗尽，整个网络的性能将受到很大的影响。因此，均衡网络能耗一直是无线传感器网络路由算法研究的热点。WSN 中传感器节点数据往往通过中继节点发送至汇聚（Sink）节点。如图1 所示，在汇聚节点位置固定的情况下，与Sink 距离较近的部分节点往往会承担更多的转发任务。随着时间的推移，这些节点将率先死亡，从而便产生“能量空洞”的问题[1]。

图1 无线传感网络结构

“能量空洞”问题的出现严重影响着网络的生命周期，造成该问题的根本原因是网络中节点能耗不均[2]。为了解决“能量空洞”问题，研究者们提出在层次路由中通过簇头（Cluster Head，CH）节点的轮转，使处于同一集群的节点轮流承担汇聚转发的任务。该方法可以有效均衡网络中节点的能耗，其中最经典的是低功耗自适应分簇协议（Low Energy Adaptive Clustering Hierarchy，LEACH）。通过簇头节点的轮转，该方法一定程度上缓解了“能量空洞”的问题，但依旧存在一定的缺陷。首先，CH 节点位置和数量均不可控，且CH 与Sink 节点间始终以单跳的方式传输数据。若CH 分布在网络的边缘，则会大大增加传输数据的能耗。为了提高网络的能量效率，通过优化成簇的方式和簇头节点的选取策略，研究者们相继提出了ALEACH、LEACH-DCHS、LEACH-C 等路由算法[3]。

为了更好地缓解“能量空洞”问题，21 世纪初R.Shah 等人提出了移动汇聚节点的策略。研究表明，通过Sink 节点的随机或受控移动，可以有效均衡网络能耗，延长网络的寿命[4]。而移动策略的核心是通过规划Sink 节点移动的路径，更好地均衡网络的能耗，延长网络的寿命。本文基于LEACH-C协议提出了一种新的路由算法，在成簇阶段通过K-means 算法对节点进行聚类，并结合节点的位置和能量信息计算通信成本选择合适的簇首。在稳定传输阶段通过汇聚节点的受控移动均衡各集群的通信能耗，延长网络的生命周期。

1 相关工作

近年来，研究者们从多跳传输、网络结构、路由等方面提出诸多有关无线传感器网络的数据采集方案[5]。这些方案大多采用层次路由的结构，网络中的节点被划分至不同的集群，通常称之为簇。每个簇中选取CH 节点融合集群内的数据，再通过Sink 节点收集来自不同集群的数据。在以往的研究中，对于WSN 路由算法的改进通常聚焦于算法中集群的划分、簇间路由的选择以及移动汇聚中对sink 节点的移动路径规划。下面介绍一些具有代表性的方法。LEACH-C[6]协议是为了克服LEACH协议的缺点而提出的，因在WSN 中的适用性而受到了研究者们的高度评价。LEACH-C 的工作原理与LEACH 非常相似，只是在设置阶段，集群和簇首的选择由BS 基站执行[7]。在每一轮的开始，网络中各节点将其位置（使用GPS 技术）及其剩余能量数据发送到Sink，Sink 再根据模拟退火算法进行分簇并选出CH 节点。该方法可以保证集群数量的稳定，且在一定程度上保证了簇头的剩余能量，因此相比LEACH 协议有效提高了网络的能源分配效率[8]。为了进一步均衡网络能耗，文献[8]借鉴了LEACH-C 协议的成簇方式，并结合Sink 节点的受控移动提出了LEACH-CD 算法。该算法沿用了LEACH-C 的集群划分方式，在传输阶段通过Dijkstra 算法计算Sink 节点遍历各个集群的最短路径。与LEACH-C 相比，通过Sink 节点的移动缩短了传输距离，降低了簇首节点的能耗，提高了能量效率，但也造成了数据的延迟问题。为了研究如何通过Sink 节点的移动最大化网络的寿命，文献[9]中提出一种线性模型下最大化无线传感网络寿命的策略。在各节点数据实时传输的前提下，通过控制Sink 节点在各节点处的停留时间均衡不同位置的能量消耗，有效延长了网络寿命。但是，该方法局限于一维的网络模型，仅从停留时间的角度进行了研究和分析。

结合无线传感网络层次路由的特点，本文从集群的划分和Sink 移动策略两方面入手，提出基于K-means 算法的成簇方案，并针对不同的延迟要求在两种场景下分别提出Sink 节点的移动策略。

2 基于K-means 聚类的分簇算法

本文采用K-means 聚类算法，结合LEACH-C协议的一些特性，在初始阶段将网络中的节点划分成不同的集群（簇）。分簇阶段完成后再根据簇内节点与集群中心的距离和节点的剩余能量选择簇头节点。

2.1 WSN 中K-means 算法的应用

K-means 是聚类分析中一种基于划分的算法，具有思想简单、效果好且容易实现的优点[10]。这里采用欧式距离作为衡量数据对象相似度的指标。使用该算法进行集群划分前，需事先规定集群个数并初始化中心点坐标。核心思想是通过计算对象与聚类中心Ci（1 ≤i≤k）的欧式距离，将目标划分到距离最近的聚类中心Ci对应的集群中[11]。划分完成后重新计算不同集群的中心坐标，作为新的中心坐标，通过迭代直至结果稳定或误差平方和局部最小。

计算网络中传感器节点与Ci的欧式距离公式如下：

其中Nj表示网络中的普通节点；Ci为聚类中心；xNj、yNj、xci、yci分别为传感器节点和聚类中心的二维坐标。

衡量聚类结果优劣的最小误差平方和EK-means定义如下：

其中k为集群个数，Qi表示第i个集群，Ci为前者的中心坐标。

在使用K-means 聚类前需先确定聚类个数和初始聚类中心[12]，因此应用于无线传感器网络场景下首先要确定簇的个数和初始聚类中心。本文中WSN 场景下节点部署在M×M范围内的矩形区域。LEACH-C 协议中，研究者给出了最优簇个数的推导，本文中沿用该协议下对最优簇头个数k的定义，公式如下：

其中N为网络中传感器节点的总数；ξf和ξm为受传输距离的影响，不同模型下对应的功率放大系数；dtoBS为簇头节点到汇聚节点的距离。

初始聚类中心的选取直接影响簇的分布，簇的个数确定后还需确定初始聚类中心。为了使簇的分布更合理，文中先随机选择一个节点作为初始聚类中心，之后以距离最大为准则，选择与先前确定的若干中心距离之和最远的节点作为下一个聚类中心。重复该步骤直至完成k个初始聚类中心的设置。

2.2 集群划分与簇首选择

在簇的划分阶段，本文使用K-means 聚类的方法将网络划分成不同的集群（簇），通过LEACH-C 协议中确定最优簇首个数的方法调整初始聚类中心的个数。

新算法在每轮的初始阶段执行以下步骤：

（1）Sink 节点根据K-means 算法完成集群划分；

（2）计算集群的中心坐标，并选择簇头节点；

（3）Sink 节点移动至指定坐标位置；

（4）簇首节点融合集群内各节点数据；

（5）簇首节点向Sink 节点发送数据。

集群划分流程如图2 所示。

图2 集群划分流程

集群划分工作完成后，需为集群指定簇头节点。为了均衡网络的能耗，本文中根据集群中节点的剩余能量Ei和与集群中心的距离di计算通信代价，根据结果选择每轮中的簇头节点。假设网络中各节点初始能量相同，首轮中选择与各集群中心距离最近的节点作为簇首。在之后的每轮传输中，与LEACH-C 算法类似，首先计算集群内节点剩余能耗的平均值Eavg。当剩余能量Ei＞Eavg时，则节点加入簇首的竞选。节点满足剩余能量要求后，根据式（4）计算与Sink 节点通信的代价函数：

本文采用文献[13]中简化的无线硬件能耗模型，模型中传感器节点的能耗与传输距离成反比，功率放大系数随传输距离变化而变化。如式（4）所示，当传输距离超过阈值d0时，能耗受距离的影响更大。传输距离阈值d0的计算公式如下：

簇首选择过程如图3 所示。

图3 簇首选择流程

如图3 所示，通过式（4）计算符合剩余能量要求节点的通信代价，选择函数值最小的节点作为簇头节点。在稳定传输阶段负责融合集群剩余节点的数据，并向sink 节点发送。

3 Sink 节点移动策略

在WSN 下的移动汇聚策略可分为实时数据传输和延迟容忍条件下的数据传输。前者对数据实时性要求较高，各簇首节点直接向Sink 节点传输数据；后者通常应用于实时性要求不高的场景，Sink 节点移动到指定位置，簇首节点收到请求后再进行数据传输。本文针对两种场景分别规划Sink 节点的移动策略。

3.1 实时汇聚的Sink 移动策略

每轮中在集群划分完成后，Sink 节点根据各集群簇首节点坐标计算各簇首节点间的中心坐标，并移动至中心位置进行数据采集。Sink 节点移动位置如图4 所示。

图4 Sink 节点位置

如图4 所示，Sink 节点受控移动，每轮集群划分完成后Sink 计算目标位置坐标，使其始终处于各簇头节点坐标的中心位置。该方法旨在均衡不同集群每轮传输过程中的能耗，避免部分集群因簇首与Sink 节点距离过远而造成能量快速耗尽的问题。

3.2 延时容忍的Sink 移动策略

针对实时性要求不高的应用场合，通常采用的策略是假设节点具有一定缓存数据的能力，Sink 节点移动到目标附近后，CH 再向其发送缓存的数据。本文中通过控制Sink 节点的移动轨迹，使其在每一轮中遍历每个集群。移动轨迹如图5 所示。

图5 Sink 节点移动轨迹

如图5 所示，每轮集群划分完成后，稳定传输阶段簇首节点收集簇内节点数据并缓存。Sink 节点依次移动至各集群中心并发送请求，受到请求后簇首节点再将融合的数据向集群中心发送。该策略通过控制Sink 节点的移动，缩短了与CHs 间的通信距离，从而有效降低了传输阶段的能耗。

4 仿真结果及分析

为了验证提出的移动汇聚算法的性能，本文将提出的算法分别与Sink 节点位置固定条件下的LEACH 协议和LEACH-C 协议进行了比较。

4.1 实验环境与参数

本文通过MATLAB 建立仿真模型。在集群划分阶段，对比使用K-means 聚类分簇算法和传统LEACH 算法时的簇头分布情况，并分析不同算法下网络剩余能量和存活节点数量随轮数的变化。仿真参数如表1 所示。

表1 仿真参数

4.2 结果分析

节点随机分布在目标区域内，中心坐标处的“×”代表Sink 节点。每轮中成为簇首的节点会被黑色叉号标记。若节点能量耗尽，该节点将被标记为点。图6 和图7 分别显示了两种算法在仿真过程中簇首的分布情况。

LEACH 协议中簇首随机选取的机制并没有考虑集群位置的分布，会造成集群位置分布不均和集群个数不稳定的问题。如图6 所示，通过簇首节点的分布可以看出集群的划分很不合理，部分区域节点离簇首节点距离很远，很大程度上增加了节点在传输阶段的能耗。相比之下如图7 所示，采用K-means 聚类算法进行集群划分的结果更为理想，各集群中心坐标相对均匀地分布在网络中，且集群数量稳定可控，在此基础上进行数据传输可以更好地均衡网络中节点的能耗。因此，使用K-means 聚类的集群划分方式优化了分簇的结果。

图6 LEACH 协议下簇首节点分布情况

图7 K-means 聚类算法下集群中心分布

表2 实验对比了4 种算法中不同节点死亡情况对应的轮数。可以看到，LEACH 算法因为其簇首选择的随机性导致网络中节点死亡较快，而LEACH-C 协议相比前者由Sink 节点指定簇首节点，优先考虑节点的剩余能量，相比随机的机制更为合理，一定程度上提高了网络的能量效率。本文提出使用K-means 聚类算法进行集群划分的策略，在选取簇首时将剩余能量与通信距离作为参考，通过比较通信代价函数的方式使簇首的选取更为合理，同时集群的分布较LEACH 更均匀，因此节点死亡数相同时完成的传输轮数更多。由于LEACH-KTD 算法在延时容忍的场景下大大缩短了Sink 节点与簇首的通信距离，相较前面几种方法生命周期明显更长。

表2 生命周期对比

图8 是仿真实验中使用LEACH、LEACH-C 及本文提出的两种算法时网络剩余总能量的变化趋势。LEACH-C 与本文提出的LEACH-K 算法均提高了高能节点当选簇首的概率，延缓了节点的死亡。LEACH-K 较前者簇首分布更合理且结合了Sink 节点的移动，因此网络剩余总能量更高。而延时容忍场景下的LEACH-KTD 算法则不考虑数据的延时，通过Sink 节点的移动大大缩短了通信距离，相同轮数下网络剩余能量最多。综上，通过K-means 聚类算法进行集群划分并结合Sink 节点的受控移动可以有效均衡网络能耗，延长网络的生命周期。

图8 网络剩余能量对比情况

5 结语

本文在LEACH-C 协议的基础上提出了一种新的基于K-means 聚类算法的分簇策略，优化了网络中集群的分布和簇首节点的选取方式。同时，针对数据延时要求不同的场景，分别提出了Sink 节点的移动接收策略。MATLAB 仿真结果显示，本文提出的成簇策略能够有效控制簇首的数量与分布。可见，结合Sink 节点的受控移动能有效降低传输能耗，延长网络的生命周期。