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

近年来，无线传感网络(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的访问路径问题。

2.2 相关变量定义

对于该机制中用到的变量做如表1解释。

表1 定义

Tab.1 Definition

符号 定义

Ti POI覆盖周期

vs MobileSweep的速度

m POIs数量

di,j POI pi与pj之间的欧几里得距离

vf MobileSink的速度

Tf MiniSink的覆盖周期

3 具体算法实现(Specific algorithm implementation)

3.1 POIs分簇

在POIs随机分布于监测区中，考虑到MobileSweep路径的长度，对POIs进行分簇，使同簇中POIs距离较近，不同簇中POIs相距较远。为了操作简便，采用K-means分簇。针对K值无法确定的问题，运用减法聚类进行对其改进，形成分簇算法：基于减法聚类的K-means。算法具体步骤如下：

POIs分簇算法

输入：POIs坐标(xi,yi)集合，形成样本空间。

输出：K个分簇，及每个簇中的POIs集合。

算法过程：

①运用减法聚类确定K值，并找出初始聚类中心集合C。

②在步骤①的基础上执行K-means。

③重新计算聚类中心Z。若聚类准则函数不收敛收敛转到步骤②。

④输出结果。

通过减法聚类，不仅得到较为合理的K值，同时确定了初始聚类中心，减少K-means的迭代次数，使算法效率得到提高。

3.2 MobileSweep与MobileSink访问路径规划

MobileSweep周期性的覆盖POIs，它的路径由访问路径中的POIs连接组成。为了寻找簇内POIs最优访问路径，本文采用遗传算法。

(1)MobileSweep访问路径算法实现

MobileSweep访问路径规划算法

输入：K个簇中的POIs坐标(xi,yi)及控制参数：种群规模N和终止进化代数T。

输出：K条访问路径L={l1,l2,…,lk}及路径长度D={d1,d2,…,dk}。

算法过程：

①根据POIs的位置坐标计算每个簇中POIs的距离矩阵Dis。

②为每个簇随机生成初始种群{C1,C2,…,Cn}，计算各个体的适应度值1/dis(Ci)，并按适应度值对个体进行排序。初始终止进化代数计数器gen=0。

③计算选择概率p。

④根据步骤③，采用“轮盘赌”复制下一代个体。

⑤交叉操作。

⑥变异操作。

⑦gen=gen+1。

⑧如果gen＜T，则转到步骤③；若满足终止条件，算法结束，输出K条路径并保存K条路径的长度。

(2)最少MobileSweep数

假设K条路径集合为L={l1,l2,…,lk}，其对应的长度为D={d1,d2,…,dk}。

已知MobileSweep的速度为vs，第i条遍历路径上的POI的最小覆盖周期为，则第i条路径上的MobileSweep数为：

(1)

那么，K条路径MobileSweep的总量为：

(2)

其中，第i条路径上的移动节点数为muni，那么Sweep Coverage机制中的总节点数为mun*。由公式(2)可知，影响mun*大小的因素有两个di和vs，由于移动节点匀速运动，本文中，我们只考虑路径di长度对最小移动节点数的影响。

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紧密度更高，算法有更强的优越性。

图1 簇中POIs紧密度对比

Fig.1 The compare of closeness of clustering

4.3 MobileSweep及MobileSink路径的生成

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

图2 MobileSweep及MobileSink路径

Fig.2 The path of MobileSweep and MobileSink

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

(1)POIs分布密度对MobileSweep数目的影响

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

图3 区域中POI密度对MobileSweep的影响

Fig.3 The density of POI influenced on MobileSweep

(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的影响较小。

图4 速度对移动节点数量的影响

Fig.4 The influence of speed on mobile sensors

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-)，女，硕士，助教.研究领域：无线传感网络，人工智能.