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

  • 投稿Arth
  • 更新时间2017-07-25
  • 阅读量531次
  • 评分4
  • 11
  • 0
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的访问路径问题。

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