基于定向移动的水下传感器网络覆盖算法

杜晓玉,李 辉,周 林

(河南大学a.物理与电子学院;b.民生学院;c.计算机与信息工程学院,河南开封,475004)

基于定向移动的水下传感器网络覆盖算法

杜晓玉a,李 辉b,周 林c

(河南大学a.物理与电子学院;b.民生学院;c.计算机与信息工程学院,河南开封,475004)

覆盖率是衡量无线传感器网络服务质量的重要指标。为提高网络覆盖率,针对水下三维传感器网络模型,提出一种基于定向移动的虚拟力算法。将虚拟力简化为节点只受邻居节点的斥力作用,定义当2个邻居节点的感知圆球相切时,其位置为相对理想位置。节点所受虚拟力大小与节点移动到相对该邻居的理想位置所需移动的距离成正比,而节点移动的距离与节点所受到的虚拟力的合力相关。实验结果表明,该算法能有效地对水下传感器网络的布局进行优化,提高网络覆盖率。

三维传感器网络;覆盖;水下传感器网络;虚拟移动;定向虚拟力算法;感知圆球

1 概述

地球表面约71%被各类水体(河流、沼泽、湖泊、海洋等)覆盖,各类水体能提供未来人类生存所需的食品、原料和生活发展空间,将成为人类可持续发展的物质基础[1]。随着无线传感器网络的迅猛发展,水下传感器网络也受到越来越多的关注。基于虚拟力的网络覆盖算法由文献[2]提出,文献[3]将虚拟力算法应用在无线传感器网络中,有限数量的传感器节点随机抛洒二维空间中,虚拟力算法假定节点之间存在引力和斥力2种虚拟力,虚拟力的大小和节点之间的距离相关。通过计算节点所受虚拟力的合力,确定节点移动的方向及移动的距离,重置节点的位置。经过多次迭代计算使传感器网络的覆盖面积达到最大化。

近几年国内外学者对虚拟力覆盖算法做了大量的研究[4-7],文献[4-5]对虚拟力算法进行修改,文献[4]修改了虚拟力的表达式,节点之间的虚拟力与两点间的距离为线性关系。文献[5]将节点所受的虚拟力限制在门限距离以内,对距离较远的节点所作用的虚拟力忽略不计,从而降低了算法的时间复杂度。文献[6]结合虚拟力算法和差分算法,提出一种解决异构移动无线传感器网络覆盖的虚拟力导向差分优化算法。该算法以网络的有效覆盖率为优化目标,通过异构节点间的虚拟力影响差分算法的位置向量更新过程,提高算法收敛速度。该算法既避免了虚拟力算法导致的网络覆盖率振荡,又使差分算法有目的地向扩大网络覆盖率的目标进化。文献[7]结合虚拟力算法和微粒群算法,提出一种面向无线传感器网络布局的虚拟力导向微粒群优化策略。该策略通过无线传感节点间的虚拟力影响微粒群算法的速度更新过程,指导微粒进化,加快算法收敛。

文献[8-9]将基本的有向感知模型扩展为方向可调感知模型,研究有向传感器网络覆盖增强问题。假定传感器节点的位置不变化,但方向可调,在此基础上,分析了有向传感器网络覆盖增强问题。该算法把传感节点的感知范围用一个“质心”点来替代,质心是质点系中一个特定的点,它与物体的平衡、运动以及内力分布密切相关。传感器节点的位置不变,其传感方向的不断调整可近似地看作是扇形感知区域的质心点绕传感器节点作圆周运动。将待解决问题转化为质心均匀分布问题,质心在虚拟力作用下作扩散运动,逐步消除网络中感知重叠区和盲区,增强整个网络覆盖性能。

虚拟力算法因其灵活性和稳定性而成为目前的研究热点,但是也存在其不足:(1)虚拟力算法需根据节点间距离计算区域中任意2个传感器节点之间的虚拟力,计算量较大。(2)虚拟算法是一种位置的微调算法,需经过多次迭代计算调整才可以达到网络覆盖的最优化。

本文针对水下三维传感器网络设计定向移动的虚拟力覆盖算法,在宏观调控后,应用基于定向移动的虚拟力算法对节点位置进行微调,以提高无线传感器网络的覆盖率。

2 虚拟力算法

在传感器网络中,每一个传感器可以看作其他传感器节点的一个施力者,传感器节点所受虚拟力可以分为引力和斥力2种。如果2个传感器节点相距过近,即节点间距离小于某一门限值,它们之间的作用力为斥力,这可以确保传感器节点之间不会过度集中而使得传感器网络的覆盖率过低。相反如果2个节点之间的距离大于某一门限值,则2个节点之间存在引力作用,引力的作用可以使节点尽可能均匀地分布在部署区域中[3]。图1为虚拟力算法的示意图。

图1 虚拟力算法示意图

任意2个传感器节点之间的虚拟力为:

其中,dij为节点Si和Sj之间的欧几里得距离;dth为两节点之间距离的门限值,由经验值取得;αij为节点Si到节点Sj直线的方位角;ωA和ωR为节点之间虚拟力的参数。门限值dth的大小可以控制多次迭代计算之后节点之间距离的大小。

如果无线传感器节点的传感模型为二元感知模型,感知半径为r,当相邻2个节点之间的距离为2r时,2个节点的感知区域不重叠,这使得传感器节点的利用率达到最大,但是会存在一些区域无法被覆盖,无线传感器网络的覆盖率较低。文献[10]中给出证明当d=3r时,二维平面中无线传感器网络为最优的部署,此时为达到全覆盖时节点间重叠的感知面积最小,因此,设定门限值时应综合考虑无线传感器网络的感知模型及网络中节点部署的密集情况。传感器节点的位置信息已知,并且可以自由的移动,节点根据所受的虚拟合力大小和方向确定移动的距离和移动的方向。

3 水下传感器网络模型

结合水下三维传感器网络的特点,本文提出适用于水下三维空间的模型,如图2所示。

图2 水下传感器网络模型

该模型有以下特点:

(1)水下传感器节点同构,所有节点具有相同的感知节径R,节点的覆盖模型为二元感知覆盖模型,传感器的感知模型为球形;

(2)水面无线通信节点密集分布,且相互之间连通;

(3)覆盖算法执行之前,节点已准确定位,节点位置已知[11];

(4)节点在水平面不可移动,但纵向可自由移动,并可以准确移动到指定位置;

(5)覆盖算法在网络初始化时执行,节点有充足的剩余能量移动到指定的位置。

假设节点部署在三维长方体空间中,节点位置服从均匀分布,空间中任意两点之间的距离为空间两点欧氏距离。相关定义如下:

定义1(感知圆球) 节点在空间的坐标为(x,y,z),节点模型为感知半径为R二元感知模型,则水下传感器节点在三维空间中的覆盖区域是一个圆心为(x,y,z),半径为R的球体,称为感知圆球。

定义2(邻居节点) 节点Si和节点Sj之间的距离为dij,dij＜2R,则称节点Si和节点Sj互为邻居节点。

定义3(相对理想位置) 节点Sj为节点Si的邻居节点,空间中一点为节点Si相对邻居节点Sj的理想位置,其满足以下2个特征:

(1)节点S可沿路径移动至点i,并且在点时,节点Si的感知圆球与节点Sj的感知圆球相切。

(2)在节点Si的路径上所有可以使节点Si的感知圆球与节点Sj的感知圆球相切的点中,点到节点Si的距离最短。

4 基于虚拟移动距离的水下三维覆盖算法

通过仔细分析虚拟力算法的原理,不难发现虚拟力算法中虚拟力的大小与节点的距离密切相关,图3为一种简单的传感器部署情况,即区域中只有2个传感器节点,此时两节点之间虚拟力表现为引力作用,两节点相向移动,直至移动至门限值位置,如图3(b)所示。

图3 仅受引力时节点移动示意图

此时节点的移动对网络覆盖率没有任何积极的影响,因此,本文对虚拟力算法做改进,并提出基于定向移动的覆盖算法(CFD),在该算法中:(1)节点之间只存在斥力作用,不存在引力作用;(2)仅节点间距离小于门限值的2个节点之间存在虚拟力作用,大于门限值的节点之间虚拟力为0。

将定向移动的虚拟力算法应用在水下传感器网络中,节点仅可以在垂直方向自由移动,如图4所示。

图4 三维定向移动示意图

若2个节点的感知圆球相交,即dij＜2r,节点Si移动Δdij距离之后,节点Si与节点Sj的感知圆球相切:

节点所受的虚拟力为:

其中,ωR是加权值,可根据经验值来设定;α为方向矢量,值为(0 01),表示z轴正方向。由于没有考虑节点间的虚拟引力作用,算法中必须考虑边界斥力的作用,当节点到边界的距离小于感知半径r时,节点受到边界的斥力作用,但仅限上下边界的斥力作用,如图5所示。

图5 边界受力分析

节点Si到上边界的距离为diu,diu＜r,节点受到上边界的斥力为:

若边界为下边界,则节点所受到的斥力为:

节点所受的虚拟合力为:

节点Si移动的距离为:

根据di的方向和大小可计算移动之后节点Si的坐标为:

按照节点ID号依次计算每个节点所需移动的距离和方向,从而计算出节点的新位置坐标信息。

5 算法描述

本文算法的描述如下:

输入水下传感器网络节点数量n,节点的位置信息Si(xi,yi,zi)(i=1,2,…,n),节点的感知半径r,加权值ωR,ωe

输出节点的新的位置信息newSi(xi,yi,zi) (i=1,2,…,n)

(1)初始化网络,根据节点发送的信息统计每个节点的邻居节点信息并计算到邻居节点的距离。

(2)对网络中第i个节点Si按式(2)～式(5)计算节点的虚拟力。

(3)按式(6)～式(7)计算节点Si所受到虚拟力的合力和所需移动的距离di。

(4)更新节点的位置信息,判断节点是否为网络中最后一个节点,否则返回步骤(2)。

(5)计算本次优化计算节点移动的平均距离d_ave,若d_ave大于门限值dth,返回步骤(1)对网络进行新的迭代优化。

6 仿真实验

为验证CFD算法的有效性,本文利用Matlab进行仿真实验。在实验中,无线传感器节点随机分布在长宽高均为80 m的水下三维的部署区域中。部署节点的总数为N,节点的最大感知半径R为20 m。

图6为覆盖率随节点数量变化时,设定门限值dth为2 m,CFD算法与随机分布时覆盖率对比。由该图可见,经过CFD算法优化之后三维监测区域的覆盖率有明显提高。

图6 覆盖率随节点数量的变化

图7为覆盖率随迭代次数的变化。由该图可见,当节点数量较少时,覆盖率增加较为明显,这是因为水平面节点分布不均匀,节点较多时,节点移动的空间较少,覆盖率增加不明显。

图7 覆盖率随迭代次数的变化

图8为网络中节点在单次算法执行过程中平均移动距离的大小。由该图可见,平均移动距离随迭代次数的增加而减少,最后趋于平衡。这证明随算法迭代次数的增加,网络整体趋于稳定。

图8 平均移动距离随迭代次数的变化

图9为覆盖率随三维水下传感器网络部署区域的深度变化情况。无线传感器节点随机部署三维水下空间,水面区域固定为80×80 m2,水深在60 m～150 m内变化。由该图可见,当水的深度增加时,网络的覆盖率提高较为明显,这是因为水体较深时给节点提供了较大的移动空间。

图9 覆盖率随水深的变化

7 结束语

针对水下三维传感器网络模型,本文提出一种适用于定向移动的虚拟力算法,该算法将虚拟力简化为节点只受邻居节点的斥力作用。通过定义2个邻居节点的相对理想位置,计算传感器节点相对每个邻居节点的虚拟距离,从而计算出节点受到的虚拟力大小、计算节点所受虚拟力的矢量和节点实际移动的距离和方向,更新网络中节点的位置。由实验结果可以看出,本文算法可以有效提高三维传感器网络的覆盖率。

下一步研究方向如下:(1)建立与节点数量和三维空间体积的方程,对网络的整体部署做出估计,从而解决节点在局部达到最优、网络覆盖率较低的问题。(2)设计二维水面的节点部署优化算法,使二维平面的节点均匀分布,再对水下节点位置进行优化部署。

[1] 孙力娟,刘林峰,杜晓玉,等.水声传感器网络拓扑控制技术综述[J].南京邮电大学学报:自然科学版, 2012,32(5):20-25.

[2] Howard A,Matari C M J,Sukhatme G S.Mobile Sensor NetworkDeploymentUsingPotentialFields:A Distributed,Scalable Solution to the Area Coverage Problem[M]//Asama H,Arai T,Fukuda T.Distributed AutonomousRoboticSystems5.Fukuoka,Japan: Springer,2002:299-308.

[3] Zou Yi,Chakrabarty K.Sensor Deployment and Target Localization Based on Virtual Forces[C]//Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications.San Francisco,USA: IEEE Press,2003:1293-1303.

[4] Yu Xiangyu,Huang Weipeng,Lan Junjian,et al.A Novel Virtual Force Approach for Node Deployment in Wireless Sensor Network[C]//Proceedings of the 8th International Conference on Distributed Computing in SensorSystems.Hangzhou,China:[s.n.],2012: 359-363.

[5] 黄俊杰,孙力娟,王汝传.基于虚拟势场和覆盖影响因子的三维传感器网络覆盖增强算法[J].通信学报, 2010,31(9A):16-21.

[6] 李 明,石为人.虚拟力导向差分算法的异构移动传感器网络络覆盖策略[J].仪器仪表学报,2011,5(5): 1043-1050.

[7] 王 雪,王 晟,马俊杰.无线传感器网络络布局的虚拟力导向微粒群优化策略[J].电子学报,2007, 35(11):2038-2042.

[8] 陶 丹,马华东,刘 亮.基于虚拟势场的有向传感器网络覆盖增强算法[J].软件学报,2007,18(5): 1152-1163.

[9] Xiao Fu,WangJing,SunLijuan,etal.Coverage Enhancement Strategy Based on Novel Perception and Co-evolution for Multimedia Sensor Networks[J]. Chinese Journal of Electronics,2013,22(1):135-140.

[10] Pompili D,Melodia T,Akyildiz I F.Three-dimensional and Two-dimensional Deployment Analysis for Underwater Acoustic Sensor Networks[J].Ad Hoc Networks, 2009,4(7):778-790.

[11] Mo L,Peng-Jun W,Frieder O.Coverage in Wireless Ad Hoc SensorNetworks[J].IEEETransactionson Computers,2003,52(6):753-763.

编辑 金胡考

Coverage Algorithm Based on Fixed-directional Movement for Underwater Sensor Network

DU Xiaoyua,LI Huib,ZHOU Linc
(a.School of Physics and Electronics;b.Minsheng College;c.College of Computer and Information Engineering, Henan University,Kaifeng 475004,China)

The coverage is a fundamental issue and an important indicator of the service quality in Wireless Sensor Network(WSN).For three-dimensional underwater sensor network model,an virtual force algorithm based on directional movement is proposed that simplifies virtual force as the repulsion force only by neighboring nodes.This paper defines the ideal position relatively of the two nodes’position while one of sensing spheres of two neighboring nodes is tangent to the other.Virtual force is proportional to the distance moved from original position to the ideal position.The movement distance is determined by the resultant of virtual force which acts on the node.Experimental results show that the algorithm can effectively optimize the layout of underwater sensor networks and improve the network’s coverage rate.

three dimensional sensor networks;coverage;underwater sensor networks;virtual movement;fixeddirectional virtual force algorithm;sensing sphere

杜晓玉,李 辉,周 林.基于定向移动的水下传感器网络覆盖算法[J].计算机工程, 2015,41(2):76-80.

英文引用格式:Du Xiaoyu,Li Hui,Zhou Lin.Coverage Algorithm Based on Fixed-directional Movement for Underwater Sensor Network[J].Computer Engineering,2015,41(2):76-80.

1000-3428(2015)02-0076-05

:A

:TP393

10.3969/j.issn.1000-3428.2015.02.015

河南省教育厅科学技术研究基金资助重点项目(14B510024);河南大学科研基金资助项目(2013YBZR004)。

杜晓玉(1979-),女,讲师,主研方向:无线传感器网络定位及覆盖技术,阵列信号处理;李 辉,助教、硕士;周 林,副教授、博士。

2014-03-18

:2014-05-08E-mail:dxy@henu.edu.cn