基于数据融合的有向传感器网络全覆盖部署*

张聚伟,王 宇,杨 挺

(1.河南科技大学电气工程学院,河南 洛阳 471003;2.西安交通大学系统工程研究所,西安 710049;3.河南科技大学电力电子装置与系统河南省工程实验室,河南 洛阳 471023;4.天津大学电气与自动化工程学院,天津 300072)

基于数据融合的有向传感器网络全覆盖部署*

张聚伟1,2,3*,王 宇1,3,杨 挺4

(1.河南科技大学电气工程学院,河南 洛阳 471003;2.西安交通大学系统工程研究所,西安 710049;3.河南科技大学电力电子装置与系统河南省工程实验室,河南 洛阳 471023;4.天津大学电气与自动化工程学院,天津 300072)

针对有向传感器网络全覆盖问题,基于有向传感器节点概率感知模型提出一种新的有向传感器节点部署结构,通过理论推导,证明了该结构的最优性,引入标准工作方向的概念,使用奈曼-皮尔森准则数据融合方式,以最少的传感器节点实现目标区域全覆盖。仿真结果表明,在随机部署情况下,使用这种新型有向传感器节点调度方式,可以有效提高网络覆盖率,减少网络冗余度,减少网络工作节点个数,延长网络生存期。

有向传感器网络;覆盖;数据融合;概率感知;奈曼-皮尔森

近年来,随着嵌入式系统、微传感技术以及无线通信技术的发展,无线传感器网络在民用与军事领域得到了广泛的应用,覆盖问题是保证无线传感器网络性能的基本问题,一直备受关注[1-3]。由于传感器节点通常具有电源能量低、二次补充能量难、信息采集能耗大的缺点,因此无线传感器网络存在严重的能量约束问题。目前多数覆盖控制的研究成果都是基于满足全向性感知模型的传感器进行的,但在实际应用中,已有多种有向传感器(如视频传感器、超声传感器和红外传感器)被广泛采用,组成有向传感器网络DSNs(Directional Sensor Networks)[4],而传统基于全向覆盖模型的覆盖控制算法无法直接应用于有向传感器网络中,因此设计出合理的有向传感器网络控制算法以增强网络覆盖并有效利用网络能量,从而实现网络高效长期覆盖是DSNs需要解决的关键问题。

Ma等[5]首次提出了有向传感器网络的概念,提出了有向传感器节点感知模型,并且研究了有向传感器网络的部署策略问题。陶丹等[6]引入“质心”概念,将有向传感器网络覆盖增强问题转化为质心均匀分布问题,并利用虚拟势场调整有向传感器节点方向提高网络覆盖率;目前许多学者[7-11]都是在此基础上展开研究的,并取得了一定的进展,然而这类算法容易陷入局部最小点。Chiu等[12]针对有向传感器网络覆盖率增强问题,提出了一种基于虚拟势场的可移动有向传感器网络覆盖率增强算法,定义了4种虚拟力:质心与辅助点之间的斥力、质心与质心之间的斥力、图心与质心之间的吸引力和节点与节点之间的斥力;利用这些相互作用力来调节节点位置从而提高网络覆盖率。

Jiang等[13]将遗传算法应用于有向传感器网络中,提出了一种基于遗传算法的有向传感器网络覆盖增强算法,通过选择、交叉、变异来调整传感器节点主方向,计算每代的适应度并寻找节点的最优感知方向,调整节点感知方向消除网络感知重叠区和感知盲区实现网络覆盖增强。陈莹等[14]针对目前有向传感网中覆盖增强和冗余节点休眠调度算法存在的问题,提出虚拟势场结合学习自动机的覆盖控制算法,首先使用虚拟势场算法调整网络中节点感知方向,随后利用学习自动机在不影响网络覆盖率的情况下休眠网络中的冗余节点,从而降低网络节点冗余度。范兴刚等[15]提出一种虚拟力导向微粒群的有向传感器网络覆盖增强策略VFPSO,建立节点所受虚拟力和调整角度之间的关系模型,通过微粒群算法不断迭代实现网络覆盖增强。谭励等[16]提出一种改进的非均匀有向传感器网络节点部署方法,引入部署中心和矢量引力的概念,增加斥力的非均匀部署属性,从而保证了重点区域的覆盖质量。

现有文献大多采用节点确定感知模型,建模方便,计算机仿真时效率高、速度快,但与实际应用还存在一定差距,同时传感器节点感知方向的调整具有不确定性,没有根据有向传感器节点感知模型特点对网络进行部署。因此本文基于概率感知模型的节点部署方案,提出一种新型的部署结构,采用Neyman-Pearson准则对网络概率感知区域的感知数据进行数据融合提高网络数据可靠度,对网络进行休眠调度,提高算法执行效率,延长网络的生存期。

1 预备知识

1.1 有向传感器网络概率感知模型

目前使用最多的有向传感器节点感知模型为四元组(Pi,R,v(t),α)[6,17],为了表示有向传感器节点概率感知模型,在四元组加入概率范围参数d。此时概率感知模型可用(Pi,Rs,v(t),α,d)表示,如图1所示,其中d表示概率感知范围参数。

图1 有向传感器节点概率感知模型

当目标点p与传感器节点s之间的欧式距离Rs

P(s,p)=eλ[Rs-l(s,p)]

(1)

λ为传感器节点的可调参数;设Rf=Rs+d,则目标点p被节点s感知到的概率为:

(2)

式中,θi表示点p与节点si感知方向v(t)的夹角;α表示节点si传感边界与其传感向量v(t)的夹角。则目标点p不被网络中任一节点si感知到的概率为:

(3)

1.2 奈曼-皮尔森准则

网络在部署后传感器节点对其概率感知范围内的目标是依概率进行判定的,会存在的一定的判定误差,使用奈曼-皮尔森准则对网络中的不确定区域进行数据融合,减小判定误差,提高网络对概率区域的感知能力。在传感器节点检测问题中,假设有‘目标不存在’和‘目标存在’两种假设,分别用H0和H1表示[18-19]。

当Rs

对于实际目标存在而判为目标存在概率为检测概率pd,容易验证:

pd=1-pm

(4)

一般情况下希望两类错误pf和pm都尽量小,但这是相互矛盾的,因为:

p(D1|H0)=∫R1f(x|H0)dx

(5)

p(D0|H1)=1-∫R1f(x|H1)dx

(6)

在给定概率密度函数f(x|H0)、f(x|H1)时,要是pf(D1|H0)变小,则判决域R1应变小,从而pm(D1|H0)变大;反之亦然。

奈曼-皮尔森准则就是在pf=p(D1|H0)≤τ(0<τ<1)的约束条件下,使得p(D0|H1)达到最小,或pd=p(D1|H1)达到最大,其中τ为错误率。

定理1 在分布式传感器网络中,在给定的第1类错误概率pf(D1|H0)≤τ情况下,要使检测概率pd=p(D1|H1)达到最大,奈曼-皮尔森数据融合规则需满足式(7):

(7)

式中:f(D|H1)和f(D|H0)分别为目标点被网络感知到的概率密度函数和不被网络感知到的概率密度函数,结合(3)式:

(8)

(9)

证明:

为了证明式(7)能够在一定错误率τ∈[0,1]的情况下达到最大的检测概率,引用拉格朗日(Lagrange)乘数法,定义目标函数:

L=p(D0|H1)+μ(p(D1|H0)-τ)

(10)

式中:μ为Lagrange乘子。将式(5)、式(6)代入式(10)得到:

L=[1-∫R1f(x|H1)dx]+[∫R1f(x|H0)dx-τ]

(11)

经变换得到:

L=(1-μτ)+∫R1[μf(x|H0)-f(x|H1)]dx

(12)

为了使L达到最小,则要求被积函数μf(x|H0)-f(x|H1)小于0的点全部落入R1中,且R1中的点使被积函数μf(x|H0)-f(x|H1)小于0,因此,有:

R1={x|μf(x|H0)-f(x|H1)<0}

(13)

从而可以得到判决准则为:

(14)

当满足式(14)时判决H1为真;否则判决H0为真。显然在满足式(7)的时候检测概率最大。

则对于目标点的判定规则为:

(15)

式中

τ=lnμ

(16)

2 算法描述

2.1 算法假设

同现有向传感器网络部署算法一样,本文作如下假设:①所有的有向传感器节点同构,即所有节点的感知半径Rc、通信半径Rc,且Rc=2Rf;②传感器节点随机部署后可以确定自己的位置坐标、感知方向和所有邻居节点的位置信息;③节点位置不能移动,但感知方向可以调整;④在构成的有向传感器网络中,传感器的通信方向是全向的。

2.2 部署结构

文献[20]提出一种有向传感器网络全覆盖部署结构如图2所示,这种结构能够实现全覆盖,但冗余度比较高;对此本文提出一种新的部署结构,在实现网络全覆盖的同时降低网络冗余度,如图3所示。

图2 平铺结构

图3 本文提出结构

定义1 节点冗余度

节点重叠覆盖面积SR比上节点覆盖面积SZ,则节点冗余度为:

η=SR/SZ

(17)

图2和图3部署结构的节点冗余度分别为:

(18)

(19)

则:

(20)

定理2 在有向传感器网络平铺覆盖部署中采用图3部署结构最优。

证明:

对于图3中的排列为最优的证明从几何角度证明,如下:

对于任意角度为2φ的扇形如下:

通过几何图形图4(a)～4(c)可以直观的看到,横向最优模型如图4(c)所示;而对于纵向最优则要考虑多个扇形组合的情况如图4(d)所示:扇形4的圆心只有在另一个扇形的圆弧上移动时才是最优的,此时看不出处于那个位置是最优的;再看5个扇形组合如图4(e):可以看出扇形5是跟随扇形4移动的,移动过程中仅与扇形1和扇形3有重叠,因此只需要计算出移动过程中处于那个位置的时候重叠面积最小。

图4 几何证明

如图4(e)所示设第5个扇形与第1个扇形相交的角度为β则与第3个扇形相交的角度为φ-β则可算出重叠面积为SR:

(21)

φr2为恒定值,为求的SR最小值可转化为:

(22)

求D的最大值,则对D以β求偏导得:

(23)

当D′=0时D最大,得到:

cosβ-cos(2φ-β)=0

(24)

得:

φ=β

(25)

在φ=β时SR最小,明显得证。

证毕

定义2 标准工作方向

网络中有向传感器节点工作在部署算法预设的工作方向上,此时预设的工作方向被称为有向传感器节点的标准工作方向。

本文预设标准方向设置为:φ1=π/2,φ2=3π/2。设α1=|ω-π/2|,α2=|ω-3π/2|,其中ω表示传感器方向v(t)与坐标轴x的夹角;比较α1,α2,如果α1<α2则该传感器节点标准工作方向为φ1,否则为φ2。

定义3 邻居节点

网络中处于有向传感器节点Si二倍感知半径内的传感器节点称为有向传感器节点Si的邻居节点。

2.3 问题分析

由于本文是以有向传感器节点概率感知模型为基础的部署策略,如果严格按照2.2节部署结构会出现如图5所示情况:目标区域A,B,C仅处于单个传感器节点的概率感知范围内,会存在一定的判定误差。为了提高网络中概率感知区域对目标感知数据的可靠性,对部署结构进行一些改动,如图5(b)所示:此时目标区域A,B,C分别处于多个传感器节点概率感知范围内,使用1.2节数据融合模型对多传感器感知数据进行融合,提高网络感知能力。

图5 问题分析

2.4 休眠唤醒策略

本文算法中节点被大规模抛洒到目标区域,节点采用休眠唤醒策略进行调度。节点工作状态分两种:休眠和工作。节点休眠侦听状态标记为0,工作状态标记为1,网络部署完毕后,用nwork表示工作节点数目。网络唤醒任意节点,确定第1个节点位置(如图6中的S1节点),在选取后续工作节点时,被唤醒的节点处于当前节点的水平或者垂直方向上。

横向唤醒方式如图6(a)所示:网络随机唤醒任意节点S1,节点坐标S1(x0,y0),根据节点S1的坐标以及1.3节部署结构可以确定虚拟节点a(x2,y2),b(x3,y3)的坐标:

(26)

(27)

纵向唤醒方式如图6(b)所示:对于已唤醒的节点S1(x0,y0),根据节点S1的坐标可以确定虚拟节点c(x4,y4)的坐标。

(28)

唤醒距离虚拟节点a(x3,y3),b(x2,y2),c(x4,y4)最近且与标准工作方向相符的传感器节点S3,S2,S4进行工作。

得出结论:在横向唤醒方式中被唤醒的节点与基点的感知方向是相反的,纵向唤醒方式中被唤醒的节点的感知方向应该与基点的感知方向是同向的。

2.5 算法步骤

Step1 初始化所有传感器节点参数,所有节点工作状态为1,节点交换消息,确认本节点所处位置和邻居节点位置。

Step2 每个节点根据2.2节中标准工作方向调整规则调整自身感知方向。

Step3 如果所有节点的感知方向都满足标准工作方向,节点工作状态为0。

Step4 从部署区域左下角开始,随机唤醒一个节点,使其工作状态为1,根据式(26)～式(28)计算出其横向和纵向虚拟节点。

Step5 比较虚拟节点和网络中实际节点位置,若虚拟节点位置不存在实际节点,则唤醒距离虚拟节点最近、且感知方向相同的节点,若存在则唤醒该实际节点,标记其工作状态为1。

Step6 以新唤醒的节点执行Step4,若计算出的虚拟节点位置在监测区域内,则执行Step5,否则结束该步骤。

Step7 工作节点对目标区域进行监测,结合节点概率感知模型根据推导的数据融合判定式(15)对目标区域进行判断。

3 仿真分析

图7 部署图

图7为对本文算法的一次实例仿真图,可以看出本文利用休眠唤醒策略随机唤醒一个节点,然后根据这个节点的标准工作方向和坐标根据2.1节方法计算下一个被唤醒的节点的坐标和方向,最终能够取得良好的覆盖效果,图中传感器节点蓝色为确定感知边界,黑色为概率感知边界。

图8显示采用本文算法与PFCEA算法以及随机部署在满足覆盖率达到85%时传感器感知角度变化的情况下需要的工作节点的个数,从图中可以看出在覆盖率相同时不同的传感器角度的情况下本文算法的工作节点数明显少于PFCEA算法以及随机部署。这是因为PFCEA算法是以虚拟力为基础的部署算法,节点受力容易陷入局部最小点使得网络冗余度较高;而本文使用新的部署结构,引入节点标准工作方向,可以从很大程度上降低网络冗余度,在满足对目标区域的覆盖率的同时可以有效的减少网络工作节点个数。

图8 感知角度与工作节点个数

图9显示在工作的节点个数为200时不同算法覆盖率随时间t的变化关系,由于本文算法采用逐个唤醒的策略可以看出在t<25时本文算法覆盖率小于随机部署以及PFCEA算法,在收敛速度上会稍慢一些,但本文算法覆盖率随时间t几乎是以线性快速增长着,在t>36时本文算法覆盖率大于PFCEA算法以及随机部署。本文部署算法通过休眠唤醒策略实现最优结构部署,使用节点概率感知,并且使用奈曼-皮尔森准则对网络中的概率感知区域进行数据融合,提高网络对不确定区域的感知数据可靠性,从而提高网络覆盖率。

图9 覆盖率与时间t

图10是3种算法工作节点冗余度与覆盖率的关系对比图,在满足相同覆盖率的时候,本文算法的工作节点冗余度低于PFCEA算法以及随机部署,而且本文算法工作节点冗余度随覆盖率的增加所收到的影响波动较小。这也印证了本文算法采用的部署结构能够有效降低网络中工作节点的冗余度。

图10 工作节点冗余度

由于传感器节点通常具有电源能量低、二次补充能量难、信息采集能耗大的缺点,因此传感器网络存在严重的能量约束问题。假设每个有向传感器节点的初始能量都为30 J,数据包的大小为100 byte,节点在通讯过程中传输一个数据包需消耗0.05 J的能量,接收一个数据包消耗0.0l J的能量,节点感知方向调整单位角度1°所消耗的能量为0.1 J;则网络经过3种算法部署后节点平均剩余能量对比图如图11所示。

图11 节点平均剩余能量

从图11可以看出,在相同的参数设置下,网络在经过3种算法部署后的平均节点剩余能量,与随机部署相比本文算法以及PFCEA算法节点平均剩余能量都较低,这是因为为了取得更好的部署效果,本文算法以及PFCEA算法皆对传感器节点感知方向进行了调整,而节点感知方向的调整会消耗节点自身一部分能量;PFCEA算法以虚拟力为基础对传感器感知方向进行调整,这是一个动态调整过程,节点在部署过程中会根据自身受力情况会实时调整,会出现摆动现象,所以PFCEA算法在调整过程中会消耗大量节点能量。而本文算法节点调整只需要调整为标准工作方向即可,没有动态调节过程,因此相较于PFCEA算法节点会损失更少的能量,从而延长节点使用寿命。

4 结论

本文研究了有向传感器网络全覆盖问题,在分析有向传感器节点概率感知模型的基础上,提出一种新型的有向传感器节点部署结构,与现有研究成果中节点感知方向调整具有随机性不同,本文根据有向传感器节点感知模型结构特性引入标准工作方向的概念,结合休眠调度策略对网络节点进行调度形成最优结构,使用奈曼-皮尔森准则数据融合方式,并证明了部署结构的冗余度最小,以较少的传感器节点实现目标区域全覆盖。仿真结果表明,随机部署情况下,与已有算法相对比,本文算法使用这种新型有向传感器节点调度方式,可以有效提高网络覆盖率,减少网络冗余度,减少网络工作节点个数,延长网络生存期。

[1] Kulkarni R V,Forster A,Venayagamoorthy G K. Computational Intelligence in Wireless Sensor Networks:A Survey[J]. Communications Surveys and Tutorials,IEEE. 2011,13(1):68-96.

[2] Amac G M,Gokhan Y A. On Coverage Issues in Directional Sensor Networks:A Survey[J]. Ad Hoe Networks,2011,9(7):1238-1255.

[3] Borges L M,Velez F J,Lebres A S. Survey on the Characterization and Classification of Wireless Sensor Network Applications[J]. Communications Surveys and Tutorials,IEEE. 2014,16(4):1860-1890.

[4] 陆克中,冯禹洪,毛睿,等. 有向传感器网络覆盖增强问题的贪婪迭代算法[J]. 电子学报 2012(4):688-694.

[5] Ma Hudong,Liu Yonghe. On Coverage Problems of Directional Sensor Networks[C]//Proc of the Int Conf on Mobile Ad-Hoc and Sensor Networks. Berlin:Springer,2005:721-731.

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

[7] 陶丹,马华东,刘亮. 视频传感器网络中路径覆盖增强算法研究[J]. 电子学报,2008,36(7):1291-1296.

[8] Niu Yunfei,Peng Li,Zhang Wei. Dynamic Vision Sensor Networks Self-Deployment with Two-Step Virtual Potential Field[C]//Control and Decision Conference(CCDC),2010 Chinese. 2010:4134-4138.

[9] Ji Peng,Jiang Jingqi. A Coverage Detection and Re-Deployment Algorithm in 3D Directional Sensor Networks[C]//Control and Decision Conference(CCDC),2015:1137-1142.

[10] 蒋一波,王万良,陈伟杰,等. 视频传感器网络中无盲区监视优化[J]. 软件学报,2012(2):310-322.

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

[12] Chiu Kuo Liang,Cheng Yen Chung,Chuan Feng Li. A Virtual Force based Movement Scheme for Area Coverage in Directional Sensor Networks[C]//2014 Tenth International Conference on Intelligent Information Hiding and Multimedia Signal Processing(IIH-MSP). 2014:718-722.

[13] Jiang Yibo,Yang Jinwei,Chen Weijie,et al. A Coverage Enhancement Method of Directional Sensor Network Based on Genetic Algorithm for Occlusion-Free Surveillance[C]//2010 International Conference on Computational Aspects of Social Networks(CASoN). 2010:311-314.

[14] 陈莹.曹立志. 基于虚拟势场和学习自动机的有向传感网覆盖控制[J]. 系统工程与电子技术,2015(5):1177-1184.

[15] 范兴刚,王恒,张兆娟,等. 一种基于虚拟力导向微粒群的有向传感器网络覆盖增强策略[J]. 传感技术学报,2015,28(11):1720-1726.

[16] 谭励,杨朝玉,杨明华,等. 改进的非均匀有向传感器网络节点部署方法[J]. 传感技术学报,2015,28(12):1835-1840.

[17] Tao D,Mao X F,Tang S J,et al. Strong Barrier Coverage Using Directional Sensors with Arbitrarily Tunable Orientations[C]//2011 Seventh International Conference on Mobile Ad-Hoc and Sensor Networks. Beijing:2011. 68-74.

[18] Plata-Chaves J,Lazaro M,Artes-Rodriguez A. Optimal Neyman-Pearson Fusion in Two-Dimensional Sensor Networks with Serial Architecture and Dependent Observations[C]//2011 Proceedings of the 14th International Conference on Information Fusion(FUSION). July 2011:1-6.

[19] 潘泉,程咏梅,梁彦,等. 多源信息融合理论及应用[M]. 北京:清华大学出版社,2013:124-135.

[20] 赵静,曾建潮. 无线多媒体传感器网络感知模型与数量估计[J]. 软件学报,2012(8):2104-2114.

Full Coverage Deployment Algorithm of Directional Sensor Network Based on Data Fusion*

ZHANGJuwei1,2,3*,WANGYu1,3,YANGTing4

(1.Electrical Engineering College,Henan University of Science and Technology,Luoyang He’nan 471023,China;2.System Engineering Institute,Xi’an Jiaotong University,Xi’an 710049,China;3.Power Electronics Device and System Engineering Laboratory of Henan,Henan University of Science and Technology,Luoyang He’nan 471023,China;4.School of Electrical Engineering and Automation,Tianjin University,Tianjin 30072,China)

For the problem of the directional sensor network full coverage,a new directional sensor node deployment algorithm is proposed based on probabilistic sensing model,and the optimality of the structure is proved by theoretical deduction. In order to achieve full coverage of the target area with the least sensor nodes,the concept of the standard work direction is introduced,and the Neyman-Pearson standard data fusion method is used. The simulation results show that the proposed method can effectively improve the network coverage,reduce the network redundancy,reduce the number of working nodes,and prolong the lifetime of the network.

DSNs;coverage;data fusion;probabilistic sensing;Neyman-Pearson

项目来源:国家自然科学基金(61040010);航空科学基金(20115142005)

2016-05-14 修改日期:2016-08-21

TP393

A

1004-1699(2017)01-0139-07

C:7230

10.3969/j.issn.1004-1699.2017.01.025