基于虚拟力算法的WMSNs覆盖研究

刘 军

(武警工程大学 信息工程系，陕西 西安 710086)



基于虚拟力算法的WMSNs覆盖研究

刘 军

(武警工程大学 信息工程系，陕西 西安 710086)

为了提高无线多媒体传感器网络(WMSNs)区域覆盖率，在传感器节点随机部署后，通过调节传感器节点的感知方向，使节点从感知重叠区域向覆盖盲区转动，提高网络覆盖率。针对现有算法中存在覆盖效率和覆盖率不能统一的问题，提出一种改进的虚拟力覆盖算法(VFARCR)，该算法利用传感器节点感知扇形区域质心点间的斥力调节感知方向，且通过传感器节点间的覆盖冗余度的决定方向调整的大小，虚拟力和覆盖冗余度共同控制传感器的转动。仿真实验表明:该算法提高了覆盖效率和覆盖效果，提高了虚拟力覆盖算法的性能。

无线多媒体传感器网络； 覆盖优化； 虚拟力； 质心

0 引 言

传统的无线传感器网络(wireless sensor networks ,WSNs)只提供简单的感知数据，如温度、湿度、震动等[1～3]。随着WSNs的应用需求越来越广泛以及相关技术不断提高，无线多媒体传感器网络(wireless multimedia sensor networks，WMSNs)应运而生，WMSNs能够提供更复杂的数据，如语音、图像和视频等。所以，相比于传统的WSNs，WMSNs更加全面地反映监测环境的真实情况，能够满足更广泛的需求[4～6]。

在无线多媒体节点的覆盖优化过程中，节点的方向调整规则直接关系到覆盖效率。现有的研究中，节点的方向变化基本上是按固定步长调整[7]或连续性调整[8]，存在计算量较大、优化时间较长，效率相对较低的问题。本文提出一种改进的基于虚拟力覆盖冗余算法(virtual force algorithm related with coverage redundancy,VFARCR)，解决优化精度与优化时间的矛盾。

1 WMSNs覆盖问题研究

1.1 方向可调感知模型

改进文献[8]的感知模型，本文定义五元组表示多媒体传感器的感知模型，即(s,V→i(t),α,Qi,R)，改进的模型如图1所示，其中，s为传感器节点i的位置坐标s(xi,yi)，节点随机部署后，位置坐标不会变动；V→i(t)为传感器节点i在t时刻的感知方向；α为感知中心线距离扇形感知区域两侧边界的夹角，2α为传感器感知区域的夹角；Q为传感器节点i的质心位置坐标Q(xi,yi),在优化调整传感器的方向的过程中，节点的质心坐标会随着感知方向的变化而变化；R为传感器节点的感知半径。

图1 方向可调的感知模型Fig 1 Adjustable directional sensing model

当区域中的点pi被传感器节点si覆盖时，当且仅当满足以下条件：

在该模型的WMSNs覆盖优化中，区域覆盖率p、节点个数N、区域面积A、感知视角α、感知半径R之间的关系满足如下关系(具体推导过程见文献[9])

(1)

2.2 问题描述

假设监测区域的面积为A，传感器节点的位置是均匀分布的，但感知方向V→i(t)是随机的，假定区域中任意两个节点不在同一坐标位置。节点的最近感知半径R和传感区域视角2α都是相同的，即所部署的传感器节点是同构的。部署的节点个数为N，节点集表示为S(s1,s2,…,sN)。Ai(t)表示在t时刻传感器节点在感知向量V→i(t)上区域的覆盖面积，当感知向量值为(V→1(t),V→2(t),…,V→s(t))时，区域的覆盖率可表示为

(2)

所以，WMSNs覆盖增强问题可以表述为：寻找一组解(V→1(t)，V→2(t),…,V→3(t)),使对于初始的(V→1(t),V→2(t),…,V→N(t))，有max{p(V→1(t),V→2(t),…,V→3(t))-p0}。

区域覆盖率p的求解如下

(3)

式中 N为部署在区域中的传感器节点数量。

2 VFARCR算法

2.1 虚拟力分析

改进算法利用邻居节点的斥力优化节点感知方向，斥力的方向为节点感知区域质心的连线方向，斥力大小与两节点间覆盖重叠区域大小成正比，与节点感知质心间的距离的平方成反比,即

(4)

(5)

式中 m为节点i的邻居节点个数。

节点的虚拟力分析为对节点B的受力分析，如图2所示，A，B，C和D为传感器节点，a，b，c和d为其质心点，V→b(t)为节点B的感知方向，节点A对节点B的斥力为F→ab，节点C对B的斥力为F→cb，节点B所受合力为F→b，由于节点D和节点B没有重叠区域，所以，D对B的斥力为0。

图2 节点的虚拟力分析Fig 2 Virtual force analysis of nodes

2.2 覆盖重叠区域面积的计算方法

在节点的感知扇形区域中建立p行q列的网格，如图3所示。具体方法为将节点的感知视角2α均分为q等份，并将节点感知半径R划分为p等份，即将节点感知扇形区域划分为p×q个网格，每个网格中心作为该网格的位置坐标。

图3 重叠区域面积计算Fig 3 Area computation of overlap region

建立网格后，需要判断哪些网格被邻居节点覆盖。定义一个参数Cgijpq，当节点i中的网格被其邻居节点j覆盖，则Cgijpq=1;否则,Cgijpq=0。所以，Mij可以通过下式计算

(6)

节点i的覆盖冗余度可以定义为

(7)

式中 m为节点i的邻居节点个数。

2.3 节点感知方向调整规则

传感器节点感知方向的调整需要考虑两个问题，一是在虚拟力的作用下，往哪个方向调整；二是方向变化的大小问题，即如何规定方向变化大小的依据。

明确节点方向调整的问题后，需要进一步考虑节点在该方向上是如何调整的。本文将覆盖冗余度作为方向变化大小Δθ的依据。文献[8]提出采用固定的Δθ，并未考虑结合覆盖重叠面积与Δθ的关系，根据该文献的研究，对Δθ作以下改进

(8)

式中 Rcagi为节点i的覆盖冗余度，α为感知中心线距离扇形感知区域两侧边界的夹角。当Rcagi很小时，在实际操作中很难实现，所以，设定一个阈值η来实现角度调整的可行性，当Rcagi≥η时，角度进行调整。

3 仿真实验

该仿真实验在Matlab R2008b上进行。参数设置如下：监测区域为500 m×500 m，节点半径R=60 m，感知视角2α=60°，虚拟系数k=1，节点扇形感知区域的划分为10 m×10 m，覆盖冗余度阈值η=0.01。若预期的覆盖率为85 %，根据公式(1)以及所设置的相关参数可求得在该区域中需要的最少节点个数N为

图4为Δθ=1°,Δθ=20°以及Δθ为变化取值时的仿真结果对比。从仿真结果可以看出:当Δθ变化取值时，在算法运行23次时，算法就开始收敛且覆盖率达到了92.4 %，比Δθ=1°时的91.3 %提高了1.1 %，与Δθ=20°时的覆盖性能相比较，当Δθ变化取值时，在算法迭代6次就达到了Δθ=20°的最大覆盖率，且没有出现振荡的情况，稳定性更好。所以，当Δθ变化时，既能达到较理想的覆盖效果，又能提高算法的收敛速度，使算法以较快的速度达到较高的覆盖率。

图4 固定Δθ和变化Δθ的算法收敛性的比较Fig 4 Comparison of algorithm convergence between fixed Δθ and changed Δθ

将本文VFARCR算法与文献[7]提出的PFCEA算法和文献[10]所提出的VCFCEA算法覆盖性能进行比较。仿真结果如图5所示。三种算法最终的覆盖率都相差不大，均在91 %左右。但VCFCEA算法的覆盖效率最低，覆盖率增长率最缓慢，最少需要迭代25次才能达到最大的覆盖率；PFCEA算法优化效率比VCFCEA算法更高，在算法迭代30次基本达到最大的覆盖率，但算法会出现震荡的现象；本文VFARCR算法运行21次时开始收敛，基本达到最大覆盖率，且不出现震荡。这主要是该算法解决了虚拟力与调整角度大小相互牵制的矛盾，将覆盖冗余度与调整方向的大小关联起来，解决了采用固定步长算法难以收敛的问题。

图5 算法性能比较Fig 5 Comparison of algorithm performance

4 结 论

针对WMSNs覆盖优化过程中节点转动角度调整策略存在的不足，本文提出一种改进的虚拟力算法，改进算法有两点创新：一是将节点间的虚拟力与它们之间的重叠块面积关联起来，使虚拟力的大小随着重叠块的大小变化，优化了虚拟力的构造；二是将节点转动角度的大小与覆盖冗余度关联起来，解决了固定转动角度中覆盖效果与覆盖效率难以统一的矛盾。仿真实验表明:改进算法具有有效性，且与同类算法相比较，具有明显的优越性。

[1] Akyildiz L E,Su W L,Sankamsubramanizm Y,et al.A survey on sensor networks[J].IEEE Communications Magazine,2002,40(8):102-114.

[2] Liu B，Towsley D．A study of the coverage of large-scale sensor networks[C]∥IEEE International Conference on Mobile Ad-Hoc and Sensor Systems，MASS’04，2004:475-483．

[3] 赵 旭,雷 霖,代传龙.无线传感器网络的覆盖控制[J].传感器与微系统,2007,26(8):62-66.

[4] Akyildiz I F,Vuran M C.Wireless multimedia sensor network-s[M].New York:John Wiley &Sons Ltd,2008:49-59.

[5] Almalkawi I T.Wireless multimedia sensor networks:Current trends and future directions[J].Sensors,2010,10(7):6662-6717.

[6] 王晓晨,冯秀芳,辛 英.WMSNs中目标覆盖算法与通信策略研究[J].传感器与微系统,2013,32(8):32-34.

[7] 何 璇,郝 群,宋 勇.一种移动无线视频传感器节点的覆盖算法[J].传感技术学报,2009,22(8):1163-1168.

[8] Tao D,Ma H D,Liu L.A virtual potential field based coverage-enhancing algorithm for directional sensor networks[J].Journal of Software,2007,18(5):1152-1163.

[9] 肖 甫,王汝传,叶晓国,等.基于改进势场的有向传感器网络路径覆盖增强算法[J].计算机研究与发展，2009,46(12):2126-2133.

[10] 张 璐.无线多媒体传感器网络覆盖技术研究[D].西安：西安电子科技大学,2014.

Research on WMSNs coverage based on virtual force algorithm

LIU Jun

(Department of Information Engineering Engineering University of CAPF,Xi’an 710086,China)

In order to improve area coverage rate of wireless multimedia sensor networks(WMSNs),after sensor nodes are randomly deployed,by regulating sensing direction of sensor nodes,enable node rotates from perception overlapping areas to cover blind areas,so as to enhance network coverage rate.Aiming at problem of existing algorithms that coverage efficiency and covering rate can’t be unified,propose an improved virtual force algorithm related with coverage redundancy(VFARCR),the algorithm using sensor nodes to sense repulsion between the centroid point of fan-shaped area,adjust sensing direction,and size of direction adjusting is determined by coverage redundancy,virtual force and coverage redundancy control rotating of sensor collectively.Simulation results show that the algorithm improves coverage efficiency and coverage effect and improve performance of virtual force covering algorithm.

wireless multimedia sensor networks(WMSNs);coverage optimization;virtual force;centroid

10.13873/J.1000—9787(2016)11—0074—03

2015—12—03

TP 393

A

1000—9787(2016)11—0074—03

刘 军(1963-)，男，北京人，硕士，教授，研究生导师，从事无线数据通信、电子技术应用、战场态势感知方面研究工作。