东北大学学报:自然科学版   2015, Vol. 36 Issue (12): 1673-1677   PDF (724 KB)    
基于三维感知模型的WMSNs最优空间覆盖研究
贾子熙, 吴成东, 张云洲, 王清嘉    
东北大学信息科学与工程学院,辽宁 沈阳 110819
摘要:无线多媒体传感器网络(WMSNs)的覆盖问题的研究成果大多基于二维感知模型.对于视频节点而言,二维感知模型无法准确地描述其感知范围,监测平面上方的空间通常会被遗漏.因此,提出了空间覆盖的概念,并重新定义了三维感知模型.通过分离两个影响空间覆盖的因素——视频传感器俯仰角和偏向角,采用粒子群优化算法对一重空间覆盖率进行优化.并结合实际应用需求,提出了有效空间覆盖率的概念,保证了对监测目标的有效视频信息收集.最后,通过仿真实验优化,网络的空间覆盖程度得到了明显提高,证明了优化算法的有效性.
关键词无线多媒体传感器网络     空间覆盖     三维感知模型     粒子群优化算法    
3D Sensing Model Based Optimal Space-Coverage Research for WMSNs
JIA Zi-xi, WU Cheng-dong, FENG Yu-chang, WANG Qing-jia     
School of Information Science & Engineering,Northeastern University,Shenyang 110819,China.
Corresponding author: JIA Zi-xi,E-mail: jiazixi@ise.neu.edu.cn
Abstract: The majority of the researches about the coverage problem of wireless multi-media sensor networks(WMSNs) are based on 2D sensing model. For video nodes,2D sensing model cannot describe their sensing range precisely,and the space above the monitoring horizon is generally omitted. Thus,the concept of space coverage was proposed,and a new 3D sensing model was defined. By separating the two factors pitch angles and deflection angles which can seriously influence the space coverage,the Particle Swarm Optimization (PSO) was employed for optimizing the 1-space coverage. By considering the requirements of practical applications,the concept of efficient space coverage was proposed here,which can guarantee the efficient video collection of monitoring targets. At last,the degree of space coverage is significantly improved by means of simulation,which proves the proposed optimization efficient.
Key words: wireless multi-media sensor networks(WMSNs)     space coverage     3D sensing model     PSO         

无线多媒体传感器网络是物联网研究的一个重要分支,也是近年来学术界最为关注的研究热点之一.它的一个突出特点是在传统无线传感器网络中引入了视频信息获取手段.从信息论的角度,WMSNs突破了传统低维信息,如声音、温度、湿度和浓度等的感知局限,转而采集信息量更高的视频信息,使得WMSNs对于周围信息的采集更为丰富全面和确实高效[1,3,3].

当然,视频感知手段的引入也给WMSNs研究带来了新的挑战,尤其是WMSNs中视频节点的覆盖问题已经成为制约其向应用转型的核心科学问题. 在WMSNs中,视频节点的图像采集方式是有向式.与全向式不同,有向式只对一定角度范围内的信息进行采集.因此,如何合理地部署视频节点成为能否覆盖整个监测区域的关键,作为WMSNs研究的基础和核心问题,许多科研机构对其展开了研究[4, 5].

相关研究包括:Nurcan等[6]假设视频节点通过调整自身观测方向可以达到最佳覆盖,并考虑监测区域内障碍物的阻挡,提出了基于可调向感知模型的最优覆盖算法,该算法通过调节视频节点的感知方向,尽量减小障碍物的影响,增强对监测区域的有效覆盖.肖甫等[7]提出了一种网络覆盖增强算法,通过调节二维感知模型的仰俯角和偏向角来实现对监测区域的最优覆盖.吴帅[8]采用全向的球形覆盖模型作为感知模型,该模型是以视频节点为圆心,R为半径的球体,并进一步提出以视频节点为顶点的圆锥形感知模型,通过调节主感知方向来改变覆盖区域.

以上的WMSNs覆盖问题研究多基于二维感知模型.对于传统无线传感器网络来说,节点部署平面与被监测目标基本保持在同一水平面,所以二维感知模型基本上可以准确地描述传感器的感知范围,如文献[7]所示.但是对于WMSNs,其部署平面往往要高于监测目标,即从斜上方俯视监测目标.另一方面,监测目标通常具有一定的高度,而二维感知模型对于监测平面上方空间的覆盖问题则束手无策,这样极易造成监测目标的匹配、定位、跟踪和行为识别等研究无法有效展开.因此,本文提出采用三维感知模型对空间最优覆盖问题展开深入的研究.

1 研究背景 1.1 三维感知模型

目前,绝大多数的无线多媒体传感器网络覆盖研究采用二维感知模型,如扇形感知模型或梯形感知模型[5],这些模型均用二维图形描述单个视频节点在监测平面的感知区域.二维感知模型是对视频节点感知范围在监测平面投影的高度抽象,可以从一定程度上描述其感知范围,但是仅以此来研究视频节点网络的覆盖范围并不完整.

图1所示,根据梯形感知模型定义,面D1D2D3D4为视频节点P在监测平面上的感知区域.但在实际视频采集过程中,体PD1D2D3D4才是视频节点P真正的覆盖范围.因此,面D1D2D3D4′正上方的空间其实是无法采集到的.显然,仅从面D1D2D3D4出发来研究视频节点的覆盖问题不够准确.

图 1 梯形感知模型示意图 Fig. 1 Illustration of the trapezoid sensing model

本文提出的三维感知模型充分地考虑了监测目标的高度因素,在现有二维感知模型[5]的基础上加入了感知高度信息,使得原有的二维感知平面转化为三维感知体,最大程度还原了视频节点的感知范围,也就保证了监测目标的采集完整性,三维感知模型示意图如图2所示.

图 2 三维感知模型 Fig. 2 3D sensing model

定义1 本文提出的三维感知模型可以用一个四元组{P,O,R,h}表示.其中,P=(x,y,z),表示视频节点P在三维空间中的坐标;O={γ,θ},表示视频节点的主感知方向,设主感知方向的调节空间为Ro.这里,γ为俯仰角,即主传感方向O在垂直方向上的偏移角度;θ为偏向角,即主传感方向O在水平方向上的偏移角度,R={α,β},表示视频节点的摄像头视角.这里,为水平方向感知区域视角;为垂直方向感知区域视角,h为感知高度,即视频节点在z轴上的有效感知范围.根据摄像原理,面D1D2D3D4为视频节点P在监测平面(z=0)上的感知投影,该平面即为原二维感知模型.面D1D2D3D4′为视频节点P在平面(z=h)上的感知投影,该平面与面D1D2D3D4平行.图2中,体D1D2D3D4D1D2D3D4即为视频节点P的三维感知模型.

1.2 感知空间覆盖

根据定义1的三维感知模型,可以获得单个视频节点在监测空间中的覆盖空间,使得研究视频节点网络的最优空间覆盖问题成为可能.首先,需要确定监测空间中的任意一点是否在某一视频节点的感知范围之内.

为了高效处理该问题,将整个监测空间离散化:当z=Δz·k(k=0,1,2,…)时,对应x=Δx·iy=Δy·j的位置选取一个点qi,j,k(i,j=0,1,2,…),其中Δx,Δy,Δz为三个方向上的单位增量.假设针对特定监测空间中点qi,j,k的全集为Ωq,其中至少被视频节点覆盖一次的点集记为Ω1,则监测空间的空间覆盖率C1定义为

根据定义,C1也可以称为视频节点的一重空间覆盖率.在定位和跟踪监测目标时,至少需要两个或两个以上的视频节点同时拍摄到同一目标,因此定义,在监测空间中视频节点覆盖多于一次的点集记为Ω2,对应的二重空间覆盖率为C2=‖Ω2‖/‖Ωq‖.

定义2 由于WMSNs的特殊性,即两个或两个以上视频节点才能完成目标的定位和跟踪研究.鉴于此,在关注一重空间覆盖率的同时,应该保持一定的二重空间覆盖率.因此,本文定义了有效空间覆盖率,其表达式为

有效空间覆盖率反映了监测空间中能有效参与目标跟踪和识别等后续工作的能力,是检验无线多媒体传感器网络能否正常工作的重要指标.而以C1为目标的优化更注重在尽量大的空间内实现视频覆盖,对后续的复杂视频处理考虑不足.

2 最优空间覆盖算法 2.1 空间覆盖增强方案

本文采用空间覆盖增强方案展开研究,所谓空间覆盖增强方案是指:首先在监测空间内随机部署n个视频节点,得到初始一重空间覆盖率,然后通过对视频节点摄像头位置的调节,最大化一重空间覆盖率.在整个过程中,假设视频节点均同构,且保持其位置不变.

如果假设第i(i=1,2,…,n)个视频节点的感知方向为Oi.可以将空间覆盖增强过程转化为求一重空间覆盖率C1的最大值:

由于O={γ,θ},因此式(3)等价于以俯仰角γ和偏转角θ为自变量的优化函数.根据γθ的定义,就单个视频节点而言,γ与该节点的覆盖空间体积具有函数关系,θ则与其无关.可见,γθ分别是独立变量,之间不具有函数关系.因此,可以分别通过自变量γθ对式(3)进行优化.

2.2 基于俯仰角γ的节点最优空间覆盖

根据本文提出的感知模型定义,可以直观地得出俯仰角γ与视频节点的覆盖空间成正相关,即随着γ的增大,该节点覆盖空间相应增大.但是,为了更好地检测具有一定高度的目标,这里更关注视频节点对于竖直覆盖空间的检测,因此提出以三维感知模型中竖直覆盖空间的体积作为优化目标.如图3所示,体D′1D′2D′3D′4D1D2D3D4为三维感知模型,体A′B′D3′D4′D1D2BA为竖直 覆盖空间,其中A′D1,D4A,D3B,B′D2分别垂直于面D1D2D3D4和面D1D2D3D4′.

图 3 竖直覆盖空间A′B′D3D4D1D2BA Fig. 3 Vertical coverage space A′B′D3D4D1D2BA

根据实际物理设备,同时也为了便于研究,针对三维感知模型做出如下假设:视频节点的部署高度为5m,摄像头的有效感知范围为10m,覆盖高度h为2m.俯仰角γ的取值范围是[0,π/3],水平方向视角α和垂直方向视角β均为π/6,因此,如果俯仰角γ取值大于π/3时,摄像头的部分观测范围将高于水平面.另外,偏转角θ取值范围是[0,2π),由于俯仰角与偏向角正交,可认为对于单个节点偏向角的取值并不影响覆盖空间的体积,因此这里设定偏向角为0°,即主方向Ox轴同向.

根据以上假设,可以得到γ和视频节点的竖直覆盖空间体A′B′D′3D′4D1D2BA的体积Vv的函数关系.通过分析,当俯仰角γ=0.79时,Vv取值最大.因此,该俯仰角对应的覆盖空间为 最优.

2.3 基于偏向角θ的全局最优空间覆盖

在确定了俯仰角γ之后,将针对偏转角θ对全局空间覆盖进行优化.该问题是一个典型NP-hard问题,因此本文采用粒子群优化算法实现优化.此时,最优空间覆盖问题由式(3)转化为

其中,n为视频节点个数,因此粒子群优化算法的搜索空间为n.

该粒子群优化算法的目标函数为式(1),但在实际计算中,采用离散化形式计算点集Ωq.式(1)也转化为

其中:‖Ω1(z)‖表示竖直方向坐标为z时对应的一次覆盖点集.‖Ωq(z)‖表示竖直方向坐标为z时的点全集,本文研究的检测空间为立方体,因此‖Ωq(z)‖为常量.

在2.2节中,俯仰角γ的最优值已经获得,根据三维感知模型定义,可以确定单个视频节点三维感知空间的尺寸.根据空间几何原理,可得

式(6)中,φΔz(k)表示竖直方向上从Δz·k变化到Δz·(k+1)时对应点集的变化比例系数.根据分析可知φΔz(k)不是线性函数,因此本文提出的三维感知模型与梯形二维感知模型5]也不存在线性关系,从而证明了三维感知模型提出的必要性.为了简化计算可以将式(5)转化为

其中,ξ=1+φΔz(0)+φΔz(0)φΔz(1)+…+φΔz(0)φ Δz(1)…φΔz(kmax-1).与式(5)相比较,式(7)极大地减轻了粒子群优化算法的计算量,使得快速获得全局最优解成为可能.

针对定义2有效空间覆盖率,优化目标转化为C2/C1,该目标的最优解将保证WMSNs对监测空间内移动目标进行有效的跟踪和识别.相应的目标函数也转化为

将式(7)代入式(8)得

可以采用与一重最优空间覆盖问题相同的粒子种群,以式(9)为目标函数展开优化处理.

3 仿真实验验证

本文仿真实验环境为50×50的检测区域,在其中随机均匀部署50个视频节点,且部署高度均为5,俯仰角γ设定为0.79,偏转角θ为[0,2π)内均匀分布,水平方向视角α和垂直方向视角β均为π/6,即水平方向和垂直方向视角均为π/3.初始部署情况俯视图如图4所示.

图 4 初始部署情况 Fig. 4 Schematic diagram of the initial deployment

图4可以看出,由于偏转角θ为随机设定,即使通过俯视图,依然能够直观得出该部署的一重空间覆盖率不足,图4所示的一重空间覆盖率C1为21.40%,有效空间覆盖率C2/C1为48.14%.该部署下多重覆盖统计图如图5所示.

图 5 覆盖次数统计图 Fig. 5 Statistical chart of the covering number

实验采用粒子群优化算法首先针对一重空间覆盖率C1进行优化,粒子种群为50个节点的偏转角.优化后的多重覆盖统计图如图6所示.其中,一重空间覆盖率C1提升为57.77%.

图 6 优化C1统计图 Fig. 6 Statistical chart of the optimal C1

针对有效空间覆盖率为优化目标,优化结果如图7所示.优化后的有效空间覆盖率C2/C1为67.41%.

图 7 优化C2/C1统计图 Fig. 7 Statistical chart of the optimal C2/C1

最后,实验针对不同数量视频节点进行仿真,仿真结果如图8所示.

图 8 不同数量节点的统计结果 Fig. 8 Simulation result of the deployment under varying nodes

图8可以看出,一重空间覆盖率C1和有效空间覆盖率C2/C1经过优化都有了明显提高,而且随着节点数量的增加,提高的幅度也有所增加.与二维覆盖率不同,当空间覆盖率为60%时,其覆盖程度可以满足绝大多数的后续应用研究.

4 结 语

本文进行了基于三维感知模型的WMSNs空间覆盖研究,旨在通过对主感知方向的优化,获得全局最优空间覆盖.首先提出了针对视频节点的三维感知模型,然后重新定义了空间覆盖的概念,详述了最优空间覆盖算法,明确了空间覆盖增强策略,并将两个优化剥离开,分别对俯仰角和偏转角进行优化,同时针对WMSNs的工作特点,提出了一重最优空间覆盖和有效空间覆盖的概念.最后,通过仿真实验验证了本文算法的有效性.

参考文献
[1] Akyildiz F,Melodia T,Chowdhury K.A survey on wireless multimedia sensor networks[J].Computer Networks,2007,51 (4):921-960.(1)
[2] Tian Y,Li S,Wang J.Wireless bioradar sensor networks for speech detection and communication [C]// 2013 International Conference on Biomedical Engineering (ICBE 2013).Beijing,2013:37-41.(1)
[3] Yildiz E,Sisikoglu E,Mustafa Y.Optimal camera placement for providing angular coverage in wireless video sensor networks[J].IEEE Transactions on Computers,2014,63(7):1812-1825.(1)
[4] Newell A,Akkaya K,Yildiz E.Providing multi-perspective event coverage in wireless multimedia sensor networks [C]//35th IEEE Conference on Local Computer Networks (LCN).Denver,2010:464-471.(1)
[5] Liu L,Zhang X,Ma H.Localization-oriented coverage in wireless camera sensor networks[J].IEEE Transactions on Wireless Communications,2011,10(2):484-494.(4)
[6] Nurcan T,Wang W.Self-orienting wireless multimedia sensor networks for occlusion-free viewpoints [J].Computer Networks,2008,52(13):2558-2567.(1)
[7] 肖甫,王汝传,孙力娟,等.一种面向三维感知的无线多媒体传感器网络覆盖增强算法[J].电子学报,2012,40(1):167-172.(Xiao Fu,Wang Ru-chuan,Sun Li-juan,et al.Coverage-enhancing algorithm for wireless multi-media sensor networks based on three-dimensional perception[J].Acta Electronica Sinica,2012,40(1):167-172.)(2)
[8] 吴帅.基于三维感知的无线多媒体传感器网络覆盖增强机制研究[D].南京:南京邮电大学,2012.(Wu Shuai.Research on coverage-enhancing algorithm or 3D wireless multimedia sensor networks[D].Nanjing:Nanjing University of Posts and Telecommunications,2012.)(1)