视频传感器区域覆盖算法

Video Sensor Area Coverage Algorithm

摘要: 视频传感器是一种广泛应用于各类突发事件感知的重要传感器，对保障城市经济和社会的高速发展起到突出作用。为了最大程度地提高视频传感器的覆盖率，根据摄像机的有向感知特性，提出一种基于改进人工蜂群优化的视频传感器监控区域增强算法。该算法受粒子群算法的启发引入全局最优值，改进人工蜂群的搜索策略，提高其开采能力和收敛速度，并利用反向学习思想产生新蜜源替换最差蜜源。结果表明，改进算法能够有效提高监控区域的覆盖率，其性能优于传统方法。

Abstract: Video sensor is an important sensor widely used in all kinds of emergency perception, which plays a prominent role in ensuring the rapid development of urban economy and society. To improve the coverage of video sensor networks, a novel artificial bee colony based on video sensor network monitoring area enhancement algorithm was proposed according to the directional sensing features of Pan-Tilt-Zoom (PTZ) cameras. Inspired by particle swarm optimization (PSO), the algorithm introduces the global optimal value, improves the search strategy of artificial bee colony, improves its mining ability and convergence speed, and uses the idea of reverse learning to generate a new honey source to replace the worst honey source. The results show that the improved algorithm can effectively improve the coverage of the monitoring area, and its performance is better than the traditional methods.

1. 引言

近年来，随着时代的变化，科学技术在不断地进步和发展。视频监控系统也随着嵌入式技术和无线通信技术等技术水平的进步而飞速发展。视频监控系统在很多领域应用十分广泛，例如：环境监控、智能交通、医疗卫生和军事战场等 [1] [2]。随着各行各业对监控网络的投入和建设，现全国已经构建了较为完善的视频安防监控系统，但仍面临许多困难和挑战 [3] [4]，其中视频监控设备布置的科学合理性，成为了影响监控系统应用过程中效能优劣的瓶颈问题，受到了国内外许多研究学者的关注 [5] [6] [7] [8]。

视频监控系统实则是摄像机，是从物理环境中监测并采集视觉信息的视频传感器 [9]。覆盖问题是视频传感器的关键问题。摄像机对环境的感知范围有方向和边界的，传统的传感器部署方法无法适用于有向传感器覆盖。如何提高视频传感器覆盖率是待解决的优化问题。

近年来，众多的学者利用粒子群算法 [10]、人工蜂群算法 [11] [12]、鱼群算法 [13]、遗传算法 [14] 和果蝇算法 [15] 等对传感器节点覆盖进行了探索与研究，但这些算法存在结构复杂、早熟收敛和覆盖率低等问题，为此研究者们陆续提出各种改进方法。文献 [10] 基于传感器有向感知模型，将改进粒子群覆盖优化算法应用到有向传感器网络覆盖增强中，取得了较好的效果，但算法在搜索时易陷入局部极值，影响了进一步优化。文献 [11] 改进人工蜂群算法，将侦察蜂更新策略用一维高斯变异方法代替，该算法与其他进化算法进行了比较，验证了人工蜂群算法在解决无向传感器网络覆盖问题上比其他的进化算法性能更好，但此算法不能直接运用到视频传感器覆盖上。文献 [15] 提出一种具有自适应步长、自适应降维的改进的果蝇优化算法，该算法对全向传感器的覆盖具有增强效果。上述方法在一定程度上能够解决传感器覆盖问题，但智能优化算法本身存在一些缺点，导致其优化的结果不是很理想，因此仍然存在着算法改进的空间，可进一步提高传感器覆盖率。

本文在有限节点数量的情况下，为改善视频传感器网络覆盖性能，将根据摄像机的有向感知特性，提出一种基于改进人工蜂群的视频传感器网络监控区域增强算法，通过调节摄像机的主感方向，提高监控区域的覆盖率。该算法受粒子群算法的启发在种群更新时引入全局最优值，改变原搜索策略，提高蜂群开采能力，并利用反向学习思想替换最差蜜源。与标准人工蜂群算法相比，本文算法可以获得更高的覆盖率。

2. 视频传感器覆盖数学模型

2.1. 有向感知模型

摄像机在某一时刻的实际视域范围是一个三维截头棱锥，为了简化问题，文献 [16] 采用扇形模型表达摄像机的二维视域，如图1，把摄像机的感知模型表示为四元组 $\langle s,v\left(t\right),r,\phi \rangle$，其中 $s\left(x_0,y_0\right)$ 为摄像机节点位置，单位向量 $v\left(t\right)$ 是扇形区域的中轴线，是摄像机的主感知方向，表示在t时刻所处的感知方向，r为感知半径，为摄像机最远感知距离， $\phi$ 是扇形边界和中轴线的夹角，最大视野角度为 $2\phi$，当 $\phi =\pi$ 时，有向感知模型变成全向感知模型。

Figure 1. Directed perception model

图1. 有向感知模型

对空间中任意一点 $p\left(x,y\right)$，若在t时刻被摄像机 $s\left(x_0,y_0\right)$ 覆盖，需要同时满足下面两个条件：

1) 点 $p\left(x,y\right)$ 与摄像机节点 $s\left(x_0,y_0\right)$ 的欧氏距离不大于感知半径；

2) $sp$ 与中轴线 $v$ 的夹角不大于 $\phi$。

判断公式如下所示：

$\{\begin{array}{l}d(s,p)\le r\\ \text{arcos}\left(\frac{sp\cdot v}{\left|sp\right|}\right)\le \phi \end{array}$ (1)

其中， $d\left(s,p\right)=\sqrt{{\left(x_0-x\right)}^2+{\left(y_0-y\right)}^2}$， $\text{arcos}\left(\frac{sp\cdot v}{\left|sp\right|}\right)$ 为 $sp$ 与中轴线 $v$ 的夹角。

2.2. 覆盖数学模型

为了数学化地描述和量化摄像机的覆盖问题，设待监测区域为 $m\times n$ 的矩形区域，在该区域随机投放N个参数相同的摄像机，所有摄像机都满足有向感知模型，初始摄像机随机放置在待检测区域，部署完成后其位置不再改变，但每个摄像机的感知方向可调，调整范围为 $\left[0,2\pi \right]$。

将待监测区域离散化为 $m\times n$ 个像素点，可将整个目标区域的覆盖率转化为像素点的覆盖率。若像素点落在任何一个摄像机感知区域内时，该像素点至少被一个摄像机覆盖，则该像素点被节点监测到的概率为1，反之为0。

设点集 $\left\{s_1,s_2,\cdots ,s_N\right\}$ 是N个摄像机，像素点 $p\left(x,y\right)$ 被摄像机节点集 $s_i$ 覆盖的概率公式如下：

$P_{cov}\left(ind\right)=\{\begin{array}{l}1,\text{if}\{\begin{array}{l}d\left(s_i,p\right)\le r\\ \text{arcos}\left(\frac{s_{i}p\cdot v_i}{\left|s_{i}p\right|}\right)\le \phi \end{array}\\ 0,\text{otherwise}\end{array}$ (2)

式中， $ind$ 是像素点 $p\left(x,y\right)$ 的索引号， $ind\in \left\{1,2,\cdots ,m\times n\right\}$ ； $P_{cov}\left(ind\right)$ 表示第 $ind$ 个像素点是否被某个摄像机覆盖的判断函数。

整个目标区域的覆盖率 $P_{area}$ 由被覆盖像素点个数的总和与总像素点个数的比值来表示，公式如下：

$P_{area}=\frac{{\displaystyle \underset{ind=1}{\overset{m\times n}{\sum }}{P}_{cov}\left(ind\right)}}{m\times n}$ (3)

3. 人工蜂群算法

人工蜂群算法(Artificial Bee Colony Algorithm)是Karaboga在2005年提出一种模仿蜜蜂觅食行为的优化方法。根据蜜蜂在活动中扮演的角色，将其归纳为引领蜂、跟随蜂以及侦察蜂三种类型。蜜源的个数与引领蜂的个数相等，两者一一对应；引领蜂的任务是发现蜜源信息并以一定的概率与跟随蜂分享；跟随蜂依据引领蜂传递的信息，在蜜源附近搜索新的蜜源，并进行贪婪选择。若一个蜜源在经过多次后仍未被更新，则此引领蜂变成侦察蜂，侦察蜂寻找新的蜜源代替原来的蜜源。

该算法用一群蜜源位置被抽象成解空间中的点，每个蜜源都是优化问题的可行解，而蜜源的花蜜量就是相应解的适应值。假设问题的解空间是D维，SN个蜜源，人工蜂群算法寻优主要过程如下：

1) 初始化种群。随机初始化蜜源位置，生成公式如下：

$x_{id}=x_d^{\min }+rand\left(0,1\right)\cdot \left(x_d^{\max }-x_d^{\min }\right)$ (4)

其中， $i\in \left\{1,2,\cdots ,SN\right\}$， $d\in \left\{1,2,\cdots ,D\right\}$，表示第i个蜜源第d个分量上的值； $rand\left(0,1\right)$ 表示 $\left(0,1\right)$ 区间的随机数； $x_d^{\max }$ 和 $x_d^{\min }$ 分别表示第d个分量上的上界和下界。

2) 种群更新。引领蜂随机选择相邻蜜源i并与其产生一个新的蜜源，比较两个蜜源的适应度，用贪婪选择策略保留更好的解，丢弃较差解；跟随蜂根据由引领蜂蜜源适应度信息转化的概率来选择是否对该蜜源进行邻域搜索并更新。引领蜂和跟随蜂的搜索蜜源更新公式如下：

${x^{\prime }}_{id}=x_{id}+{\phi }_{id}\cdot \left(x_{id}-x_{jd}\right)$ (5)

其中， ${\phi }_{id}$ 是区间 $\left[-1,1\right]$ 的随机数； $j\in \left\{1,2,\cdots ,SN\right\},j\ne i$。

3) 概率选择。跟随蜂根据一定概率决定是否选择对引领蜂蜜源进行邻域搜索，选择蜜源的概率正比于其适应度值。概率计算公式如下所述：

$P_i=\frac{fi{t}_i}{{\displaystyle \underset{j=1}{\overset{SN}{\sum }}fi{t}_j}}$ (6)

其中， $fi{t}_i$ 是可能解 $X_i=\left\{x_{i1},x_{i2},\cdots ,x_{iD}\right\}$ 的适应值。

4) 种群淘汰。在引领蜂和跟随蜂阶段，用计数器记录蜜源在种群中被保留的次数，若计数器没有超过给定的阈值，则跟随蜂转变为引领蜂，并执行引领蜂搜索，以尝试更新当前的蜜源，假设当前蜜源未被更新，此时计数器自增1；若计数器超过阈值，说明当前蜜源没有更新为更好的蜜源，则丢弃该蜜源，与该蜜源相对应的引领蜂变成侦察蜂，然后通过公式(1)重新产生一个新解，相应的人工蜂群蜜源的计数器重置为0。

4. 改进的人工蜂群算法

4.1. 搜索策略的改进

考虑到粒子群算法局部搜索能力强，而基本人工蜂群算法局部搜索能力较弱，其牺牲了开采能力，侧重于提高探索能力，为此借鉴粒子群算法思想改进人工蜂群算法。在粒子群算法 [10] 中，粒子速度更新公式有三部分组成，其中一部分为“社会共享”，是让粒子在种群最优值附近搜索，反映种群粒子间的信息共享和相互合作。改进思想是将全局最优解的信息引入到引领蜂和跟随蜂的搜索策略中，进一步提高算法的开发能力，加强粒子间的信息交流。改进后引领蜂和跟随蜂搜索蜜源的公式：

${x^{\prime }}_{id}=x_{id}+{\phi }_{id}\left(x_{id}-x_{jd}\right)+c\cdot rand\left(0,1\right)\left(x_g-x_{id}\right)\text{,}j\ne i$ (7)

其中 $g\in \left\{1,2,\cdots ,D\right\}$，c是非负常数， $x_g$ 是全局最优解。

4.2. 最差蜜源的替换

在算法迭代过程中，引领蜂和跟随蜂每代新蜜源可能基于最差的蜜源产生，这在一定程度上影响了算法的收敛速度，且不利于获得最优蜜源。于是考虑用反向学习策略构造蜜源，最差的蜜源用新产生的蜜源替换。反向学习策略的基本思想: 对于一个可行解，计算与其对应的反向解，对这两类解进行排序，选取较优的一个作为下一代个体。其中反向解的定义 [17] 如下：

设 $G=\left(x_1,x_2,\cdots ,x_m\right)$ 是M维空间中的一个点，且 $x_1,x_2,\cdots ,x_m\in R$， $x_i\in \left[a_i,b_i\right]$，则其反向解 $G^{\prime }=\left({x^{\prime }}_1,{x^{\prime }}_2,\cdots ,{x^{\prime }}_m\right)$ 定义为：

$x_i{}^{\prime }=a_i+b_i-x_i\text{,}i=1,2,\cdots ,m$ (8)

新的蜜源计算公式：

${x^{\prime }}_{id}=x_d^{\min }+x_d^{\max }-rand\left(0,1\right)\cdot x_{id}$ (9)

其中， $x_i$ 为最坏蜜源， ${x^{\prime }}_i$ 为新生蜜源。

5. 改进的人工蜂群算法流程

用摄像机主感知方向 $\left\{v_1,v_2,\cdots ,v_D\right\}$ 代替算法中的更新位置， $P_{area}$ 作为目标优化函数。每个摄像机节点在完成初始部署后，其位置不再发生变化，通过不断调整感知方向来增强视频传感器网络对待监测区域的覆盖率。改进的人工蜂群算法步骤如下：

1) 初始化N个摄像头的位置和感知方向，其初始位置和方向是随机值，待监测的区域L，感知半径r，感知视角 $2\phi$，阈值limit，最大迭代次数mc，初始蜂群数量SN，trail初始是零向量。

2) 把待监测区域网格离散化，由公式(2)和(3)计算摄像机初始覆盖概率 $P_0$。

3) 引领蜂根据公式(7)更新摄像头主感知方向 $v_i,i=1,2,\cdots ,SN$，计算此时覆盖概率，若优于原概率，则原感知方向替换成更新的感知方向；否则不改变感知方向，对应trail中第i个元素自增1。

4) 跟随蜂根据公式(6)计算选择概率，并对引领蜂进行选择，此时跟随蜂变成引领蜂，执行步骤3)。

5) 在连续搜索过程中，如果某个感知方向没有更新计数trail大于阈值limit时，则与感知方向对应的引领蜂变成侦察蜂，根据公式(4)产生一个新的感知方向，trail对应分量置为0。

6) 在SN个解中找出最差解 $x_i$，对应每个分量 $j,j\in \left\{1,2,\cdots ,N\right\}$，根据公式(9)对其更新，更新解为 ${x^{\prime }}_i$，计算适应值。若 ${x^{\prime }}_i$ 的适应值优于 $x_i$ 的适应值，则 $x_i={x^{\prime }}_i$，且trail对应分量置为0，否则保留 $x_i$。

7) 当迭代一次结束后，把搜索过程的最好的解记录下来。

8) 判断是否满足循环结束条件，若满足则输出最优解，否则执行步骤3)。

6. 仿真实验

为验证改进的人工蜂群算法在摄像机覆盖中的效果，用MATLAB R2018b进行仿真实验，并与随机部署、人工蜂群算法、粒子群算法进行对比实验，进而说明本文所给的算法在摄像机覆盖增强中具有有效性。

6.1. 相同摄像机数量的对比实验

采用的主要参数具体如下：待监测区域为500 m × 500 m，传感器节点感知半径 $r=60$，监测区域内摄像机节点个数 $N=110$， $\phi =\pi /4$。为了验证给出的改进算法的效果，将随机部署、人工蜂群算法(ABC)、标准粒子群算法(PSO)和本文改进算法四个部署效果进行比较，得到的最终优化结果如表1所示，部署效果图如图2~5所示。

Figure 2. Initial random deployment coverage map

图2. 初始随机部署覆盖图

Figure 3. Coverage graph of particle swarm optimization

图3. 粒子群算法覆盖图

Figure 4. Coverage map of artificial bee colony algorithm

图4. 人工蜂群算法覆盖图

Figure 5. Improved algorithm coverage graph

图5. 改进算法覆盖图

Table 1. Coverage of the same number of nodes in different algorithms

表1. 不同算法相同节点数量覆盖率

从表1可以看出，采用改进人工蜂群算法的视频传感器网络覆盖率达到了85.9%，与粒子群算法相比提高了10.7%，与标准人工蜂群算法相比提高了8.3%，与随机部署相比提高了16.5%，从部署效果图中观察到，视频传感器网络覆盖率得到了改善。

本小节设置的参数和文献 [10] 中实验1的待监测区域、感知半径、摄像机个数和感知视野相同，本文算法覆盖优于文献中的实验1结果；重新设置参数，待监测区域不变、 $r=70$ 、 $N=90$ 和感知视野不变与文献 [10] 实验2环境相同，再进行对比。通过图6看出在迭代到13步时，覆盖率达到83.47%，比文献中的最大覆盖率83.21%高，迭代继续，最终覆盖率达到88.43%，比文献 [10] 有大约5%的提升。

Figure 6. Improved algorithm iteration graph

图6. 改进算法迭代图

为了比较算法的收敛速度，画出算法迭代收敛曲线如图7所示，可以看出本文改进人工蜂群算法收敛速度最快，在迭代89步后算法基本收敛。

Figure 7. Iterative graph of each algorithm

图7. 各个算法迭代曲线图

6.2. 不同摄像机数量的对比实验

为了进一步验证改进人工蜂群算法在摄像机覆盖中的效果，做不同节点数量下的覆盖率进行了对比实验，其他参数不变，得到的结果如表2所示，节点数量与覆盖率的关系变化绘制成曲线图，如图8。

从表2和图8均可以看出，节点数量较少时覆盖率较低，随着节点量增多，覆盖率在上升；在五种节点不同的情况下，本文改进人工蜂群算法的覆盖率均比另外两种算法所得的覆盖率高，在一定程度上验证了改进人工蜂群在摄像机覆盖中的优越性。

Figure 8. Graph of node number and coverage rate

图8. 节点数量与覆盖率曲线图

Table 2. Coverage of different number of nodes

表2. 不同节点数量的覆盖率

7. 结论

结合摄像机特有的有向感知模型，本文把改进的人工蜂群算法应用到解决视频传感器覆盖增强问题中。在种群更新阶段引入全局最优蜜源，引领蜂和跟随蜂在其附近搜索，来提高开发能力，并利用反向学习思想产生新蜜源替换迭代结束后的最差蜜源。实验结果表明，该算法在提高视频传感器网络的覆盖率及算法的收敛性方面均优于传统算法，能有效改善摄像机的覆盖率。本文针对理想的二维感知模型给出的算法虽然可以提高摄像机的覆盖性能，但调整其主感知方向后仍然存在感知重叠区，并且实际中摄像机监控是在三维空间进行，为此下一步的工作将是研究在不同场景下三维视频传感器覆盖，减少感知重叠区，进一步提高视频传感器的覆盖性能。