基于聚类的二阶段无线传感网络Sweep Coverage机制

成璐

摘 要：作为WSN网络覆盖中的热点问题之一，Sweep Coverage旨在以较少的传感节点覆盖所有的兴趣点（POIs）。针对现有Sweep Coverage机制中存在的不足，本文提出一种基于聚类的二阶段网络覆盖机制：数据感知阶段，采用通过减法聚类改进的K-means算法对POIs分簇，并寻求各簇中访问POIs的近似最优路径；数据传输阶段，寻求数据传输节点的最优访问路径。实验表明，在相同网络场景下，本文提出的二阶段网络覆盖机制有较好的效果。

关键词：Sweep Coverage；数据感知；数据传输；K-means

中图分类号：TP212.9 文献标识码：A

1 引言（Introduction）

近年来，无线传感网络（WSNs）备受关注，而覆盖问题成为WSN中的一个热点问题。在一些特定的场景中，如巡回检查中，我们更关注事件频发点POI（Point of Interest）的覆盖问题[1]。在这些场景中，采用移动传感节点周期性的访问POIs并完成对信息的采集。

为了解决这类问题，文献[1]中首次将Sweep Coverage的概念引入WSN中，同時定义了Sweep Coverage问题：在POI覆盖周期的约束下，如何以更少的移动节点覆盖POIs，降低网络覆盖成本。Weifang Cheng等论证Sweep Coverage是NP难题。文献[1]中提出了集中式的CSWEEP算法和分布式DSWEEP算法。CSWEEP算法简便易行，但要求POI覆盖周期相同，在大规模网络中并不适用。DSWEEP算法更加灵活，但移动节点总是倾向于访问距离自身较近的POIs，难以确保信息的及时采集。另外，文献[3]提出多移动传感节点协调覆盖POIs的MinExpand算法，该算法结构简单、速度快，但是该算法无法对数据延迟的考虑。文献[5]同时考虑POI的感应和传输延迟限制，但并没有考虑使用移动节点的数量，不适用于较大规模的网络。

鉴于目前Sweep Coverage中存在的不足与缺陷，本文同时考虑POIs感应延迟限制和传感节点的传输延时限制，形成二阶段Sweep Coverage机制，通过对移动传感节点的有效控制来解决无线传感器网络中的Sweep Coverage问题。

2 基于聚类的二阶段Sweep Coverage机制描述

（Description of two-stage sweep coverage

mechanism based on clustering）

2.1 网络部署

为了模拟真实场景，假定POIs在监测区随机分布。在该场景下，同时考虑移动节点对POIs的覆盖和节点收集到的数据实效性和有用性形成一个二阶段的Sweep Coverage机制：数据感知阶段，通过减法聚类改进的K-means对POIs进行分簇，再用遗传算法对各簇中的POIs进行路径规划，得到MobileSweep（感知节点）的较优移动路径，从而以较少的MobileSweep覆盖所有POIs；数据传输阶段，由MobileSink（传输节点）收集MiniSink（存储节点）处的信息并将其送回Sink。此处MobileSink的访问路径问题可以规约成MobileSweep的访问路径问题。

3.3 MobileSink访问路径规划

数据传输阶段，MobileSink的路径和感知阶段POIs的路径相似，但是考虑到聚类之后，簇的个数远小于POIs数，因此在设计MobileSink访问路径时，直接运用遗传算法寻求MobileSink的最优访问路径。

4 实验 （Experiment）

4.1 试验设置

假设监测区域大小为500×500[8]，汇聚节点设置在区域边界，即在仿真区域的（0，0）处。对POI数量从50到150不等随机分布在监测区域的场景进行试验。POI的通信范围为2m，MobileSweep、MobileSink有足够大的数据传输带宽，可以在较短的时间内完成数据的感知和相互之间的数据传输。同时假设MobileSweep、MiniSink、MobileSink数据缓冲区足够大，且传感节点的能量充足。根据最少移动节点数算法，假设所有簇中的最小覆盖周期相等，所有POI的覆盖周期均相等且等于簇中最小的POIs的覆盖周期。

4.2 基于减法聚类的K-means分析

当监测区域中POIs个数为80时，分别运用原始K-means聚和基于减法聚类的K-means对POIs分簇。从图1可以看出，运用减法聚类改进的K-means分簇后，簇内POIs紧密度更高，算法有更强的优越性。

4.3 MobileSweep及MobileSink路径的生成

MobileSweep访问路径和MobileSink路径如图2所示。

4.4 参数设置对MobileSweep数量的影响

（1）POIs分布密度对MobileSweep数目的影响

设置MobileSweep速度vs=3m/s，最小覆盖周期Ts=100s，如图3所示，在相同条件下，本文算法所需MobileSweep数量明显少于MinExpand。

（2）移动速度对节点数目的影响

增加节点的移动速度，会在一定程度上影响所需的节点数。当POI的覆盖周期Ts=100s时，设置MobileSweep的速度为vs=3m/s和vs=5m/s。从图4可以看出，随着MobileSweep速度的增加，所需MobileSweep的数量显著下降。通常情况下，MobileSink的功率要远远大于MobileSweep，因此速度也比较大。当相同覆盖周期下，设置MobileSink的速度为vf=10m/s和vf=15m/s。随着MobileSink速度的增加，所需MobileSink数目增加平稳，且增幅较小。因此速度对MobileSink的影响较小。

5 结论（Conclusion）

本文在原来完全动态的网络模型中加入静止MiniSink形成一个二阶段网络Sweep Coverage机制。实验证明，运用该机制，可以有效防止感应延时和传输延时，并且一定程度上减少了移动节点数目，降低了无线网络覆盖成本。由于对于真实场景中的一些情况欠缺考虑，下一步，计划在真实的场景中进行验证本文提出的覆盖机制，同时考虑有无Sink节点对数据传输阶段的影响，从而对Sweep Coverage进行完善。

参考文献（References）

[1] Weifang Cheng，et al.Sweep coverage with mobile sensors[J].Parallel and Distributed Processing，2008.IPDPS 2008.IEEE International Symposium on，2008：1-9.

[2] Min Xi，et al.Run to potential：Sweep coverage in wireless sensor networks[J].International Conference on Parallel Processing，2009：50-57.

[3] Junzhao Du，et al.On sweep coverage with minimum mobile sensors[J].International Conference on Parallel and Distributed Systems，2010：283-290.

[4] Zhenya Zhang，et al.MTSP based solution for minimum mobile node number problem in sweep converge of wireless sensor network [J].International Conference on Computer Science and Network Technology，2011：1827-1830.

[5] Dong Zhao，Huadong Ma，Liang Liu.Mobile Sensor Scheduling for Timely Sweep Coverage[J].Wireless Communications and Networking Conference，2012：1771-1776.

[6] Barun Gorain，Partha Sarathi Mandal.Point and Area Sweep Coverage in Wireless Sensor Networks[J].Modeling & Optimization in Mobile，Ad Hoc & Wireless Networks，2013：140-145.

[7] Shu L，et al.A sweep coverage scheme based on vehicle routing problem[J].Telkomnika，2013，11（4）：2029.

[8] 林鋒，王伟，周激流.MASC：一种基于移动辅助节点的Sweep Coverage机制[J].四川大学学报（工程科学版），2010，06：119-125；132.

[9] 刘晨光，林锋，周激流.一种基于A-means聚类算法的Sweep Coverage机制[J].计算机应用研究，2012，03：1051-1053.

[10] 李小康，林峰，周激流.一种Sweep Coverage问题的插入启发式算法[J].四川大学学报（自然科学版），2015，01：74-78.

作者简介：

成 璐（1988-），女，硕士，助教.研究领域：无线传感网络，人工智能.