1 引言

当今社会, 城镇规模越来越大, 区域状况愈加复杂, 特别是人口密集地区, 复杂的环境给城市安全管理和威胁预防带来了极大挑战^[1], 若没有有效的监控及应急处置预案, 很容易发生危险情况, 威胁人们的生命财产安全, 在这种情况下, 只依靠人力巡逻等简单手段无法应对如此严峻的挑战, 无法做到防微杜渐, 因此有效的监控手段就显得尤为重要^[2], 有效监控的目标就是对重要区域做到全方位无死角监控, 即尽可能提高监控设备网络的覆盖率. 本文针对复杂区域的监控设备覆盖算法进行了研究, 以期能对区域进行更加有效的监控, 预防潜在的威胁. 在区域覆盖算法方面已有一些较为成熟的研究, 从以下几个方面来概括说明, 从区域的角度看, 大部分研究针对二维空间区域, 如著名的艺术馆走廊监控问题^[3]及圆周覆盖问题^[4], 文献[5]提出了一种二维无线传感器网络的覆盖性能提高算法. 从设备的角度看, 大部分研究是针对无线传感器网络^[6,7], 设备之间可以互相通信, 且部署位置不定, 灵活性较大. 从感知区域的角度, 大部分研究中设备感知区域为无向的圆形或球形区域^[8], 从覆盖的目标来看, 大部分的研究是简单的完全区域覆盖, 不考虑实际的复杂场景. 已有的一些三维空间区域的覆盖算法研究成果, 如文献[9]中是将二维空间上的覆盖算法扩展到三维空间, 抽象成数学模型进行研究, 文献[10]中针对移动传感器网络, 提出了一种基于改进粒子群遗传算法的三维覆盖算法. 从已有的研究成果可以看出, 现有研究对有向感知设备的研究较少, 对三维空间复杂区域的研究较少, 即缺乏区域划分, 对区域中障碍物, 重要监控区域的区分不够明确. 本文针对三维空间区域, 考虑区域中的复杂环境, 并为各覆盖区域区分重要程度, 以此计算栅格化后的各区块代表点及临近设备对范围内设备的虚拟作用力, 对有向设备的感知方向进行调节, 以此提高区域覆盖率, 此外, 针对调整部署后的盲区采用贪心策略增加设备节点, 减少节点冗余及重叠覆盖, 并用MATLAB进行仿真实验.

2 感知模型及区域划分

感知模型是指设备的感知区域及作用范围, 与设备类型相关, 不同的设备有不同的感知区域, 常见的二维空间设备感知模型有以下几种: 圆盘感知模型, 概率感知模型, 方向感知模型.

圆盘感知模型: 感知区域是一个以设备节点s为圆心的圆形区域, 区域内某点p被检测到的概率公式如下:

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

(1)

其中, R为设备感知半径, d(s, p)为s与p 之间的欧式距离. 扩展到三维空间则为球体区域.

概率感知模型: 是在圆盘感知模型的基础上进行的改进, 假定在圆内感知概率随该点到圆心的距离增加而衰减, 其感知概率公式如下:

$\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)

其中, $\alpha = d(s,p) - (r - {r_e})$ , $\beta $ , $\lambda $ 是可变参数, 用来刻画衰减概率, r及r_e如图1模型所示.

方向感知模型: 考虑现实中的一些设备, 他们的感知区域并不是一个规则的区域, 也并非360度无死角, 像摄像头的监控区域就是在面对方向上的一定距离内的一片区域. 考虑二维空间上的带方向的设备感知区域, 将其抽象出来如图2所示.

感知概率如下:

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

(3)

其中, $\beta $ 是区域中某点到圆心的连线与方向向量 $V$ 之间的夹角.

三维方向感知模型: 将二维感知模型扩展到三维, 感知区域如图3所示.

三维有向感知区域可以用四元组 $(S,V,R,\alpha )$ 来表示, 其中s(x, y, z)表示设备中心点三维坐标, V代表感知方向, R是感知半径, 圆锥角 $\alpha $ 代表设备感知范围. 本文使用该模型作为设备感知模型.

本文研究以实际城镇区域为背景, 有各种功能分区, 本文中针对四类区域进行研究, 分别是街道, 广场, 住宅区, 障碍物(高墙)^[11]. 将其抽象出来, 在俯视的二维空间上的表示如图4.

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

初始情况下, 三维空间中随机放置一些设备节点, 感知方向也随机, 通过以下算法调整各节点感知方向, 使区域有效覆盖率增加.

算法步骤如下:

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

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

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

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

受力分析示意如图6所示, G是设备质心点, 即受力点.

单个区块代表点或其他设备i对设备j的作用力如式(4)所示:

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

(4)

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

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

$p = \frac{{{s_\Omega }}}{s}$

(5)

其中, ${s_\Omega }$ 表示覆盖的区域面积, $s$ 是区域总面积(只计算有效区域).

并与初始部署时的区域覆盖率作比较, 评估区域覆盖提高的比率.

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

在初始部署及感知方向调整结束后, 仍有可能存在大量盲区, 一是初始部署节点数量有限, 二是设备感知范围有限. 通过在区域内剩余设备可部署位置上部署感知方向合适的节点来补充区域覆盖率.

首先, 以设备感知模型方向向量V代表设备, 由于设备感知方向可在三维空间任意变化, 为了研究方便, 本文将其量化, 以45°为步长, 则在三维空间上共有18个可变位置, 示意图如图7所示.

下面考虑盲区, 假定将使用方向调节算法优化后的设备覆盖不超过50%的栅格化小区块作为盲区, 即盲区由覆盖不超过一半的小区块集合组成.

算法步骤如下:

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

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

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

使用Matlab工具进行仿真实验, 区域设定如表1所示. 其他参数设定如下: 设备感知半径为30, 感知区域角70°, 三维空间环境中预先设置16个设备可部署点, 初始时部署8台设备, 其感知方向随机设置, 并作为随机部署方案与本文提出的改进方案进行对比. 区域栅格化的步长(即小区块的尺寸)从3到10以1为步进单位, 产生共八种栅格化方案. 区域权重设定: 街道为–5, 广场为–3, 居民区为–2, 障碍物为8, 临近设备为1.

检验在不同区域栅格化粒度情形下, 随机部署方案及我们提出的感知方向调整方案和设备增加部署方案在区域覆盖率上的对比情况, 结果如图9所示.

从图9中可以看出, 在实验参数设定下, 随机部署方案覆盖率较低, 只有大约30%左右, 原因是感知方向过于随机, 无法对区域进行有效的监控, 提出的感知方向调整方案则有效增强了区域覆盖, 将区域覆盖率提高到60%左右, 而增加设备部署后, 盲区状况得到有效改善, 区域覆盖率可达90%左右, 不同栅格化方案均能得到同样的对比结果, 证明了算法的可行性及有效性.

6 结语

本文针对现实中的有向监控设备网络, 提出在三维空间区域中结合虚拟力及区域权重的设备监控方向调整算法, 以及基于贪心策略的区域覆盖增强算法, Matlab仿真实验表明, 本文提出的方案能有效提高区域覆盖率, 减少盲区及节点冗余.