﻿ 有向监控设备三维区域覆盖算法
 计算机系统应用  2019, Vol. 28 Issue (3): 196-200 PDF

Three-Dimensional Area Coverage Algorithm for Directional Monitoring Equipment
DING Zhi-Qiang, WANG Lei, ZHANG Bing-Yue
Department of Automation, School of Information Science and Technology, University of Science and Technology of China, Hefei 230027, China
Foundation item: Innovation Fund of Chinese Academy of Sciences (High-tech Program CXJJ-17-M139)
Abstract: Most of the research on the coverage of existing equipment area aims at two-dimensional undirected sensing area. The location of equipment is often set randomly. The coverage of complex space environment is low, which is difficult to meet the needs of practical applications such as safety monitoring. The study puts forward the algorithm of adjusting the direction of the equipment in combination with the virtual force and the regional weight in the three-dimensional space region, increasing the effective coverage of the area, and finally giving the deployment of the additional equipment based on the greedy strategy to further enhance regional coverage. The experimental results show that the proposed scheme can greatly improve the regional coverage at a small cost.
Key words: three-dimensional coverage     direction device     regional weight     virtual force     greedy

1 引言

2 感知模型及区域划分

 $\Pr (s,p) = \left\{ \begin{array}{l} 1,\;\;\;\;\;d(s,p) \le R\\ 0,\;\;\;\;\;{\text{其他}} \end{array} \right.$ (1)

 $\Pr (s,p) = \left\{ \begin{array}{l} 0,\;\;\;\;\;\;\;\;\;\;d(s,p) \ge r + {r_e}\\ {e^{ - \lambda {\alpha ^\beta }}},\;\;\;\;r - {r_e} \le d(s,p) < r + {r_e}\\ 1,\;\;\;\;\;\;\;\;\;\;d(s,p) < r - {r_e} \end{array} \right.$ (2)

 图 1 概率感知模型

 图 2 方向感知模型

 $\Pr (s,p) = \left\{ \begin{array}{l} 1, \;\;\;\;\;\;d(s,p) \le R{\text{且}}\beta \le \alpha \\ 0, \;\;\;\;\;\;{\text{其他}} \end{array} \right.$ (3)

 图 3 三维方向感知模型

 图 4 区域划分

3 基于虚拟力的感知方向调整方案

1) 区域划分, 将三维空间区域划分出如图4所示的四部分, 覆盖算法设计时只考虑覆盖除障碍物外的有效区域[12].

2) 区域栅格化, 将划分出的四部分区域分割成紧邻的细粒度立方体方块, 每个小方块的中心作为区块代表点, 即虚拟力作用点, 示意图如图5.

3) 设备部署, 根据实际, 设备可部署位置相对固定, 仿真时随机设置一些可部署点, 并放置一些感知方向随机的设备.

4) 计算虚拟合力, 每台设备的一定范围内的区块代表点及其他设备对该设备具有力的作用, 计算所有这些点对设备作用的合力.

 图 5 区域栅格化

 图 6 受力分析

 ${F_{ij}} = \frac{k}{{{d_{ij}}^2}}W$ (4)

5) 调整设备方向, 将设备围绕设备点转动, 使设备感知方向 $V$ 与力的作用方向 $W$ 平行.

6) 计算区域覆盖率, 区域覆盖率算法如式(5)所示:

 $p = \frac{{{s_\Omega }}}{s}$ (5)

4 基于贪心策略的补充部署方案

 图 7 设备感知方向量化

 图 8 区域划分规格

1) 确定可部署位置上未部署设备的节点集合 $A = \left\{ {{a_1},\;{a_2},{a_3}, \cdots } \right\}$ , 以及以栅格化区块组成的盲区 $B = \left\{ {{b_1},\;{b_2},{b_3}, \cdots } \right\}$ .

2) 计算集合A中每个元素在18个量化感知方向上分别可包含的盲区区块数量, 求出其最大值, 集合表示为 ${A_m} = \left\{ {{a_{1m}},\;{a_{2m}},{a_{3m}}, \cdots } \right\}$ .

3) 使用类似贪心算法的思想, 在集合Am中选择值最大的元素, 即选择能覆盖尽可能多的盲区区块的可部署节点作为选定部署点, 并且将选中点相应的在集合A中的元素去除.

4) 若集合A为空, 则结束算法, 否则跳到步骤2)循环执行.

5 仿真实验设计及结果分析

 图 9 实验结果

6 结语

 [1] 刘军奎. 转型背景下城市治理与安全问题探析. 北京城市学院学报, 2010(6): 6-10. DOI:10.3969/j.issn.1673-4513.2010.06.003 [2] 王幸, 吴星琦. 城市安全管理中新型监控设备设计和应用的关键. 现代工业经济和信息化, 2015(9): 49-51. DOI:10.3969/j.issn.2095-0748.2015.09.018 [3] Lee D, Lin A. Computational complexity of art gallery problems. IEEE Transactions on Information Theory, 1986, 32(2): 276-282. DOI:10.1109/TIT.1986.1057165 [4] 范高俊. 无线传感器网络覆盖性能评估与提高[博士学位论文]. 长沙: 国防科学技术大学, 2009. [5] 杨阳. 无线传感器网络三维空间覆盖技术研究[硕士学位论文]. 南京: 南京邮电大学, 2013. [6] 左明. 无线传感器网络三维空间覆盖算法研究[硕士学位论文]. 长沙: 中南大学, 2012. [7] 孙振龙. 三维环境下无线传感器网络覆盖方法研究[硕士学位论文]. 大连: 大连理工大学, 2013. [8] 张磊. 面向无线传感器网络的三维覆盖策略研究[硕士学位论文]. 南京: 南京邮电大学, 2013. [9] 刘孝卿. 面向移动传感器网络的三维覆盖控制方法研究[硕士学位论文]. 杭州: 杭州电子科技大学, 2010. [10] 李娜, 向凤红, 毛剑琳, 等. 多障碍场景的有向传感器网络覆盖优化算法. 计算机工程, 2015, 41(4): 19-25. DOI:10.3969/j.issn.1000-3428.2015.04.004 [11] 季荣涛. 基于威胁分析的战场空间划分及其在航迹规划中的应用[硕士学位论文]. 南京: 南京大学, 2016. [12] 党小超, 汪红梅, 郝占军. 与区域划分及虚拟力相关的三维覆盖算法. 计算机工程与应用, 2017, 53(2): 107-111. DOI:10.3778/j.issn.1002-8331.1502-0105