视频传感器网络中移动目标k覆盖优化算法

，

(浙江工业大学 计算机科学与技术学院，浙江 杭州 310023)

视频传感器网络中移动目标k覆盖优化算法

蒋一波，盛尚浩

(浙江工业大学 计算机科学与技术学院，浙江 杭州 310023)

k覆盖问题作为视频传感器网络中的一个研究热点，引起了许多研究者的关注.针对视频传感器网络中的移动目标k级覆盖问题，结合概率预测思想，充分考虑非匀速移动目标的运动特性和下一时刻目标有可能达到的位置，建立了一种移动目标覆盖概率评估模型，提高了k覆盖的概率.同时，提出了新的基于预测的分布式k覆盖优化算法，传感器节点在通信范围内交换覆盖信息并进行决策.最后通过一系列仿真实验，实验结果验证了该算法和模型的有效性和可行性.

视频传感器网络；移动目标；k覆盖；概率模型

近年来随着图像和计算处理能力的迅猛发展，视频传感器网络(VSNs, Visual sensor networks)因其部署便捷、高精度、高可靠性和易扩展性等性能优势，在监控、安防等领域得到广泛的关注和应用，例如监控系统、交通管制和医疗监护等[1-2].视频传感器网络由许多智能视频传感器节点构成，相较于传统的传感器网络，最大的区别在于节点，视频传感器的节点可以通过调整自己的视域(FoVs, Field-of-views)优化覆盖目标，监测入侵物或者需要重点监控的区域[1,3].视频传感器网络作为一个前沿的研究领域，结合了传感器、视频、通信和分布式处理等众多技术，其显著的优势主要体现在：网络能力增强、媒体信息丰富和处理复杂任务等.

覆盖问题作为传感器网络中的一个重要研究问题，大致可划分为三大类：目标覆盖(Target coverage)、区域覆盖(Area coverage)和栅栏覆盖(Barrier coverage)[4-7].目标覆盖主要研究的问题：如何调度和分配有限的传感器节点覆盖监测区域内的目标，其中每个目标至少被k(k≥1)个不同的传感器节点同时覆盖的问题被归纳为k覆盖[8-9].近些年来有许多国内外学者对目标覆盖问题进行了研究，Liu等[10]提出DKC(Directionalk-coverage)的概念，通过概率论方法构建覆盖质量和传感器节点数量之间的关系模型.Maleks等[11]设计了一种集中式贪心k覆盖算法(CGkCA)，解决了在节点数量不足的情况下进行k覆盖所产生的不平衡的问题.为了解决无线传感器网络中目标跟踪的能耗问题，任静等[12]提出了一种基于预测策略的目标跟踪算法，兼顾能耗的同时降低了目标丢失率，保证了精度.张美燕等[13]设计了一种简单的分布式启发算法，调度在一跳邻居范围内的传感器节点的感知方向，使得更多的目标被k覆盖延长k覆盖时间.蒋丽萍[14]等考虑了实际应用中环境因素对节点感知能力的影响，提出了一种分布式k重覆盖算法KCAPSM，采用了感知概率模型保证监测区域中每一点被k重覆盖.由于视频传感器节点计算处理能有限，大量精准的预测方法会加重节点的能耗负担，需要寻求一种平衡能耗和k覆盖概率的策略.笔者针对非匀速的移动目标，提出了基于预测的移动目标覆盖k覆盖算法，分析移动目标的运动特性，充分考虑下一个时刻目标有可能到达的位置，建立一个覆盖概率评估模型，进而设计了一种分布式k覆盖优化算法.算法在提高目标k覆盖概率的同时降低了传感器节点的能耗，延长整个视频传感器网络的使用寿命.

1 移动目标k覆盖问题

为了更好地阐述非匀速移动目标k覆盖问题，在给出数学模型之前先提出如下假设:

1)视频传感器网络中的传感器节点都是同构的，即节点的各项参数都是相同的.

2)监测区域内的所有传感器节点都是随机投放，且投放之后位置固定.

3)传感器节点可以有效地识别各个目标并获取目标的运动信息，且目标自身带有编号.

4)移动目标在整个运动过程中做变速运动，且移动目标之间不会相互干扰.

1.1 视频传感器模型

视频传感器的感知范围取决于其视域(FoV， Filed of view)，现有的视频传感器节点可以通过三种方式调节其感知范围：水平方向调整感知方向，垂直方向转动感知方向，改变感知半径.研究使用的视频传感器节点限定只能在二维平面内进行转动，传感器节点的感知区域是一个圆心为节点Ps，感知半径为Rs，夹角为α的扇形区域.任意传感器节点可以用一个四元组〈Ps,Rs,α,θ〉来表示，其中Ps代表节点在笛卡尔坐标系中的位置；Rs表示节点的最大感知半径，任何与节点坐标Ps的欧式距离大于Rs的目标都无法被精准感知；α表示节点的最大感知夹角，夹角越大则感知范围越大；θ表示节点的感知方向角，节点可以通过调整自身的感知方向角来优化覆盖效果.

图1 视频传感器节点感知模型Fig.1 Perception model of visual sensor node

1.2 问题分析与定义

目前用于目标跟踪的预测方法主要有粒子群滤波、卡尔曼滤波等[11,15]，但是这些方法需要大量的数据迭代计算，且对节点的处理能力要求高.虽然这些技术更加精确，但是这些方法不适合应用于计算能力和资源有限的视频传感器节点.针对上述问题，采用概率预测思想来进行优化，在移动目标运动过程中提前分析其运动到下一个时刻有可能到达的位置，并给出覆盖概率分布.

时刻移动目标最有可能到达的位置是继续以at经过Δt时间运动到的坐标位置.当然下一个时刻目标的加速度会随机变化，但不会发生剧烈的变化，将目标的加速度大小与方向作为两个随机变量，分别用X表示大小变量，Y表示方向偏角，且x∈[amin,amax]，y∈[-π,π]，因此覆盖概率密度函数γ(x,y)满足：

(1)

为了更加直观的展示下一个时刻移动目标落点的概率分布，图2为相同初始条件但加速度不同的情况下概率分布热力对比图.

图2 移动目标落点概率分布对比图Fig.2 Probability distribution of moving target positions

假设当前时刻为t，图2(a)为移动目标在t时刻从原点(0,0)出发，以初速度v0=40,延x轴正方向运动，且加速度大小a0=20，加速度方向与y轴正方向一致；图2(b)为移动目标在t时刻同样从原点(0,0)出发，以初速度v0=40,延x轴正方向，且加速度大小a0=20，但加速度方向与y轴正方向呈30°夹角，经过Δt时间间隔后有可能到达的位置的概率分布.图2中黑色水滴形区域为可能性较大的落点区域，即t+1时刻目标到达该区域的可能性更大，而周围白色区域则表示t+1时刻目标到达该区域的可能性较小.

每个时刻，根据监测要求和容错需求，移动目标至少被k个不同的视频传感器节点所覆盖，结合上述覆盖概率分布函数，笔者的研究目标旨在完成对所有目标的k覆盖同时降低旋转可能带来的能耗损失.通过分析下一时刻移动目标有可能的运动轨迹，根据最优覆盖效果调整节点的感知方向，可以尽可能地提高k覆盖的质量，用尽可能小地旋转能耗代价换取高质量的移动目标k覆盖.

由此建立非线性优化模型为

Δθi,t∈[-ωΔt,ωΔt]∀i=1,2,…,n∀j=1,2,…,m

(2)

(3)

在判断是否达到k覆盖要求时，采用四舍五入取整的计算方式，可以在一定程度上避免多个覆盖概率较小的节点被选中.

2 基于预测的分布式覆盖算法

针对上节所述的移动目标k覆盖问题，由于该问题属于NP完全问题，难以在多项式时间内解决.同时在监测区内采集全局信息存在一定困难，因此需要寻求一种分布式次优解算法[16-19].本节提出了一种基于预测的移动目标k覆盖动态优化算法KPNMOA，充分考虑非匀速移动目标每一个时刻所有可能到达的位置，模拟了所有落点的概率值，在通信范围内与邻居节点交换覆盖信息，依次作出决策.

KPNMOA算法描述：从移动目标进入区域开始，每个时刻，传感器节点Si以当前感知方向角为基准，计算出在可旋转范围内的最优覆盖效果，即能够达到的最大覆盖概率预测值Pmax为

(4)

式中：M为覆盖区域内未满足k覆盖的移动目标个数总和；fij为在覆盖最大的条件下，节点Si对目标Tj分别进行覆盖的概率.在通信范围内广播并接受邻居节点的覆盖信息数据包，包含节点编号ID，最大覆盖概率Pmax，感知方向偏移角度Δθi，目标Tj的覆盖概率fij.算法首先选取覆盖效果最佳的传感器节点先进行决策，然后按照覆盖效果值从大到小依次选取节点进行旋转，算法终止条件为所有节点都已经调整自身的感知视角或者所有移动目标都满足k级覆盖.若某一个移动目标的累积覆盖概率之和大于k时，则判定该目标达到k覆盖要求，下一轮循环无需考虑覆盖.KPNMOA算法流程如下：

Input：每个节点的坐标位置和各自的感知方向

Output：每个节点的感知方向角

1)t←0;

2) 获取节点位置P;

3) 获取通信范围内邻居节点集合φ;

4) Status←false;//标志位

5) while(true)

6)t←t+1;

7) 计算节点Si可以覆盖且未被k覆盖的目标集合φj

8) 计算移动目标落点分布概率

9) sumj=0;

10) while(Status==false &&φj!=null)

11) 计算节点Si达到最大覆盖效果值时的Δθi和Pmax;

12) 广播并接受覆盖消息数据包

13) 按照fij值大小降序排序，如果一致按|Δθi|值从小到大排序;

14) 选择覆盖效果最好的节点Sa;

15) sumj+=fij;//累加覆盖值

16) if([0.5+sumj]≥k)

目标Tj达到k覆盖;

17) if(Sa==Si){

18) Status=true;

19)θ+=Δθi;//旋转节点

}

20) sleep(Δt);

21) end while;

22) end while;

在保证数据可靠传输的情况下，KPNMOA算法就能在有限时间内终止.算法将覆盖概率函数作为指导，并将加速度纳入函数可以确保大概率评估更加合理，提前作出合理的旋转决策，更好地实现了实时移动目标k覆盖.

3 算法仿真

为了更好地验证KPNMOA算法的可行性和有效性,基于Net Framework开发了仿真平台进行模拟实验研究，给出不同体系下的各种性能对比.在500×500的监测区域内随机投放下N个视频传感器节点进行覆盖工作，每个视频传感器节点规格相同，仿真参数值如表1所示.

表1 传感器节点参数Table 1 Parameters of sensor node

图3展示了当监测区域内出现5个移动目标时的仿真实验过程，每个移动目标的初始速度为10 m/s，且加速度a∈[-5,5].图3记录了KPNMOA算法运行不同时间步长后视频传感器网络中移动目标覆盖情况以及每个移动目标的运动轨迹.

将KPNMOA算法与其他三种算法Continue(节点持续旋转)，DPGKCA[9]算法,MPKCDA[15]算法进行比较，考察了在传感器节点数量，感知半径发生等关键参数变化时对覆盖质量产生的影响.首先给出覆盖质量函数为

(5)

式中：t为时间步长；k为实际k覆盖大小,k覆盖持续时间是评价覆盖质量的重要因素，并采用平均值来进行比较.图4比较了不同传感器节点规模时各算法的覆盖质量，其中节点数量从50～250依次递增20.由图4可知：覆盖质量Q随着节点数量N的增大而增大，显然网络中部署更多节点可以延长k覆盖的时间，同时当节点数量相同时，Continue的效果是最不理想的，KPNMOA随着传感器节点数量增加性能提高优于MPKCDA和DPGKCA.

图4 不同网络规模对覆盖质量的影响Fig.4 Effect of networks size on the coverage quality

图5为不同传感器节点感知半径时四种算法的覆盖质量的对比情况，半径以10为步长从10～90依次递增.覆盖质量Q随节点感知半径R的增加呈现指数级增长，因为伴随感知半径的增加,节点的感知范围快速变大，k覆盖的概率也随之提高.较其他三种算法,随着半径的增加KPNMOA的优势越来越明显.

图6显示了四种算法在感知角度大小变化时的覆盖质量.当感知角度增大时，可覆盖到的目标数量也会增多，因此覆盖质量Q随节点感知角度α的增长呈线性增长，KPNMOA的增长幅度明显高于其他三种算法.

图5 传感器节点感知半径对覆盖质量的影响Fig.5 Effect of sensor node perception radius on the coverage quality

图7给出了四种算法在不同k覆盖要求的情况下的性能比较.Maxk代表了监测区域的安全需求等级，Maxk值越大则每个时刻需要更多的视频传感器节点来跟踪移动目标，该监测区域的安全需求越高.由图7可知：Continue和DPGKCA的覆盖质量不断下降，而MPKCDA和KPNMOA呈先增加后下降变化，其中KPNMOA对k值变化的适应性更强.

图6 传感器节点感知角度对覆盖质量的影响Fig.6 Effect of sensor node perception angle on the coverage quality

图7 不同覆盖要求对覆盖质量的影响Fig.7 Effect of Maxk on the coverage quality

4 结 论

针对视频传感器网络中的移动目标k覆盖问题，首先建立一个覆盖概率评估模型，分析非匀速移动目标的运动轨迹，将加速度纳入概率模型使计算下一个时刻的覆盖概率更加合理，然后设计了一种基于预测的分布式k覆盖优化算法，提高了移动目标的k覆盖概率和覆盖时长.仿真结果显示在不同网络规模、感知半径、感知角度和覆盖要求时KPNMOA均具有更好的性能表现.在下一步工作中，将根据实际环境考虑加入障碍物后的移动目标k覆盖优化问题，并对算法进行改进降低时间复杂度.

[1] MUNISHWAR V P, ABU-GHAZALEH N B. Coverage algorithms for visual sensor networks[J]. ACM transactions on sensor

networks,2013,9(9):1-36.

[2] 周晓,李杰,边裕挺.基于无线传感网络的环境温度监测系统设计[J].浙江工业大学学报,2013,41(4):440-443

[3] 刘唐，彭舰，杨进.异构延迟容忍移动传感器网络中基于转发概率的数据传输[J].软件学报，2013(2):215-229.

[4] GUVENSAN M A, YAVUZ A G. On coverage issues in directional sensor networks: a survey[J].Ad Hoc networks,2011,9(7):1238-1255.

[5] CARDEI M, DU D Z. Improving wireless sensor network lifetime through power aware organization[J]. Wireless networks,2005,11(3):333-340.

[6] YANG Y, AMBROSE A, CARDEI M. Coverage for composite event detection in wireless sensor network[J]. Wirelesscommunications and mobile computing,2011,11(8):1168-1181.

[7] SUNG T W, YANG C S. Voronoi-based coverage improvement approach for wireless directional sensor networks[J].Journal of network and computer applications，2014，39(1):202-213.

[8] 陶丹，马华东.有向传感器网络覆盖控制算法[J].软件学报，2011，22(10):2317-2334.

[9] 蒋一波,陈琼,王万良，等.视频传感器网络中基于移动目标轨迹预测的k级覆盖增强算法[J].传感技术学报,2014(7):956-963.

[10] LIU L, MA H D, ZHANG X. On directionalk-coverage analysis of randomly deployed camera sensor networks[C]//IEEE International Conference on Communications. New York: IEEE Press,2008:2707-2711.

[11] MALEKS M B, SADIK M M, RAHMAN A. On balancedk-coverage in visual sensor networks[J]. Journal of network &computer applications,2015,72:72-86.

[12] 任静,熊庆宇,石为人.一种基于预测策略的目标跟踪算法研究[J].传感技术学报,2011,24(10):1496-1500.

[13] 张美燕,蔡文郁.无线视频传感器网络有向感知k覆盖控制算法研究[J].传感技术学报,2013,26(5):728-733.

[14] 蒋丽萍,王良民,熊书明,等.基于感知概率的无线传感器网络k重覆盖算法[J].计算机应用研究,2009,26(9):3484-3489.

[15] 俞立,王铭,董齐芬，等.基于无线传感网的目标跟踪算法及实验系统设计[J].浙江工业大学学报,2012,40(6):649-652

[16] 蒋一波,陈琼,王万良,等.视频传感器网络中多路径k级覆盖动态优化算法[J].仪器仪表学报,2015,36(4):830-840.

[17] ISLAM M M, AHASANUZZAMAN M, RAZZAQUE M A, et al. Target coverage through distributed clustering in directional sensor networks[J]. Eurasip journal on wireless communications and networking,2015(1):167.

[18] JING A, ABOUZEID A A. Coverage by directional sensors in randomly deployed wireless sensor networks[J]. Journal of combinatorial optimization,2006,11(1):21-41.

[19] 张文安,薛东国,俞立.面向节能的无线多传感器H∞融合估计[J].浙江工业大学学报,2014,43(3):237-242.

Optimizedmovingtargetsk-coveragealgorithmforvisualsensornetworks

JIANG Yibo, SHENG Shanghao

(College of Computer Science and Technology, Zhejiang University of Technology, Hangzhou 310023, China)

As a research hotspot in Visual Sensor Networks(VSNs),k-coverage problem has aroused general attention of many researchers. Aiming at the problem of moving targetsk-coverage problem in visual sensor networks, we propose a new target coverage probability evaluation model for non-uniform motion, which consider all the possible locations of every target at the next moment and the motion behavior of non-uniform motion objects by using probabilistic prediction theory. This method can increase the probability ofk-coverage. A new predictive distributedk-covering optimization algorithm is proposed. Sensor nodes exchange coverage information and make decisions in communication range. Finally, through a series of simulation experiments, the experimental results verify the effectiveness and feasibility of the algorithm and model.

visual sensor networks; moving targets;k-coverage; probability mode

2017-02-15

国家自然科学基金资助项目(61402415)

蒋一波(1982—)，男，浙江杭州人，副教授，研究方向为计算机网络控制与管理、无线传感网络监控系统等，E-mail：jyb106@zjut.edu.cn.

TP393

A

1006-4303(2017)06-0615-06

(责任编辑：陈石平)