一种基于粒子群算法的视频监控网络覆盖优化方法.pdf

82http:/电 力 勘 测 设 计增刊1息化建设中不可或缺的一环。随着监控设施数量的急剧增长，视频监控系统在监控质量、资源管理与成本投入等方面的问题逐渐凸显。其中，监控点位的规划与监控质量密切相关，不合理的布局会导致覆盖盲区、覆盖重叠、视野DOI：10.13500/j.dlkcsj.issn1671-9913.2023.S1.017一种基于粒子群算法的视频监控网络覆盖优化方法赵亚松，王宏胜，赵 乐，王得洪，张 雷(中国电力建设集团贵州电力设计研究院有限公司，贵州贵阳550081)摘要：针对视频监控网络的覆盖优化问题，以提高监控网络的覆盖率和减少设备数量为优化目标，提出一种基于粒子群算法的多目标优化方法。该方法考虑视频监控的有向感知性和可转动的特点，动态控制监控设备的位置和活动范围，并利用粒子群算法对覆盖的里程、设备数量、路段数等多个优化目标进行协同优化。实验结果表明，利用粒子群算法得到的优化结果，能够兼顾多个优化目标，有效提高监控网络的覆盖范围，同时减少设备投入。关键词：视频监控网络；多目标优化；粒子群算法中图分类号：P2 文献标志码：A 文章编号：1671-9913(2023)增刊1-82-09A Video Surveillance Network Coverage Optimization Method Based on Particle Swarm OptimizationZHAOYasong,WANG Hongsheng,ZHAO Le,WANG Dehong,ZHANG Lei(PowerChina Guizhou Electric Power Design&Research Institute Co.,Ltd.,Guiyang 550081,China)Abstract:Aiming at the coverage optimization of video surveillance network,a multi-objective optimization method based on particle swarm optimization is proposed to improve the coverage of the surveillance network and reduce the number of devices.This method considers the directional perception and rotatable characteristics of video surveillance,dynamically controls the location and activity range of surveillance equipment,and uses particle swarm optimization algorithm to co-optimize multiple optimization objectives such as covered mileage,number of equipment,number of intersections,etc.And the experimental results show that the optimization results obtained by using particle swarm optimization can take into account multiple optimization goals,effectively improve the coverage of the monitoring network,and reduce the equipment investment.Keywords:video monitoring network;multi-objective optimization;particle swarm optimization*收稿日期：2023-02-28 第一作者简介：赵亚松(1995)，男，白族，硕士，工程师，主要从事电力测绘等工作。0引言视频监控作为一种有力的安全管理手段，已被广泛应用于社会治安管理，而在智能化产业快速发展的当下，视频监控亦作为一种重要的信息获取手段，成为智慧城市、智慧交通等信83一种基于粒子群算法的视频监控网络覆盖优化方法http:/ 工程勘测 增刊1 缺失等，进而导致构建成本高、监控效果差等问题。因此有必要通过研究监控网络覆盖优化问题，来改善监控布局，达到提升网络覆盖质量、资源利用效率的目的。相较于在视频分析技术上的巨大提升，视频监控系统在设备选址、调度优化、视角构造等方面的研究深度略显不 足1。目前，监控覆盖优化研究主要集中在问题模型的构建、覆盖计算和算法实现等方面。已有研究相继提出了全向感知模型1、有向感知模型2等，可转向的有向感知模型3、三维感知模型4-7等，来对视频监控的位置、朝向、照射范围等特性抽象化表达，同时根据不同的监控场景，设计了基于矢量、栅格8-9等二维数量，和 DEM/DSM、点云、三维模型等三维数 据10-11，以及叠加分析12、可视性分析、空间分析13等方法的覆盖计算方案。在算法实现上，研究中通常将覆盖优化问题转换为多目标优化问题，借助虚拟势场法13-16、权重因子17等理论，并利用最优化算法、启发式算法18-20来对问题进行数学求解。基于上述背景，本研究针对视频监控网络的覆盖优化问题，以道路监控场景为例，提出了一种基于二维有向感知模型和粒子群算法的优化方法，通过提升监控网络的覆盖范围，减少重叠范围和监控数量，达到了优化网络覆盖质量、提高资源利用率的 目标。1监控覆盖模型及优化建模1.1 节点感知模型和覆盖计算节点感知模型即对视频监控的抽象化表达，本文选用了二维有向感知模型，并表示为一个四元组(P，R，v()，)：其中，p(x，y)表示传感器的位置；R 表示感知或监控半径；v()为监控器的主光轴方向，有一定的变化区间；为监控节点的水平视场角大小。对于节点感知模型的覆盖计算，本文规定了相应的判断条件和计算方法，假设某一路段上与监控节点 p 最近的点为 Si，则该路段能被节点 p 有效覆盖的条件是：1)节点 P 与最近点 Si的距离小于节点感知半径 R，如式(1)所示。?vP?v?vPRRoadSi2图1监控感知模型和有效覆盖|PSi|R(1)2)节点 P 到最近点 Si构成的向量和主光轴之间的夹角小于节点视场角 a2，如式(2)所示。PSi，v a2(2)满足上述条件的路段(如图 2 中线段 AB、CD)，即能被监控节点 P 能有效覆盖，线段的长度记作节点 P 能覆盖的道路范围。DAABBCRoadRoad1Road2图2覆盖范围当节点之间存在监控区域重叠时(如图 3中的线段 EF)，同样重叠部分的路段长度计入重叠范围，作为优化的目标之一。EFRoad图3里程重叠84http:/电 力 勘 测 设 计增刊1在上述条件下，本文主要基于二维矢量数据和 GIS 叠加分析来进行覆盖计算，得到覆盖里程、重叠里程、路段数等优化指标。1.2 优化目标建模问题模型的构建主要分为 2 个部分：1)覆盖优化：主要是基于监控节点朝向的调节，将最大化里程覆盖率、路段覆盖率，最小化重叠率作为优化目标，求解监控网络最优的朝向组合。假设网络中监控节点个数为 N，路段总里程为 L，路段数为 K，则模型的决策变量可由一个 N 维向量来表示：X=(D1,D2,Di),i=1,2,N(3)Di vi-min,vi-max(4)式中：Di表示节点 i 的主光轴方向，而 vi-min、vi-max分别表示节点 i 的朝向变化的最小和最大值。由此目标函数可表示为：max F(X)=(RateL(X),Ratec(X)(5)RateL(X)=1L(Ni=1 Length(Xi)-Overlap(X)RateC(X)=1K Cover(X)(6)式中：Xi Rang_D，即各节点的朝向在相应的主光轴区间内变化；RateL(X)、RateC(X)分别表示里程覆盖率、路段覆盖率；Length，Cover，Overlap 分别表示里程长度、覆盖的路段数和重叠里程数。2)监控节点数量优化：主要是基于上一步朝向优化的结果，通过规定一定的里程覆盖率、路段覆盖数指标，筛选监控节点，最小化网络中的节点数量。此时模型的决策变量同样用一个 N 维的向量来表示：Y=(S1,S2,Si),i=1,2,N(7)Si=0，节点 i 未被选中 1，节点 i 被选中 (8)假设最低的里程覆盖率、路段覆盖率标准分别为 minL、minC，则优化模型可表示为：min F(Y)=RateN(Y)(9)RateN(Y)=1N Ni=1 Si(10)S.t.=RateL(Y)minL RateC minC(11)式中：RateN(Y)、RateL(Y)、RateC(Y)分别表示监控节点组合 Y 下的节点利用率，网络里程覆盖率、路段覆盖率。1.3 基于PSO的覆盖优化算法实现粒 子 群 优 化(partical swarm optimization algorithum，PSO)算法是一种群智能的启发式优化算法，因具有较强的收敛性、鲁棒性，较少的参数等特点，被广泛用于函数优化、神经网络训练、高维问题求解类等方面。在粒子群算法中，每一个粒子具有位置和速度属性，前者表示问题的一个可能解，算法求解时，粒子间通过位置的共享来获得个体和群体的最优解，改变粒子运动的方向，进而使整个群体的运动不断趋向于最优的方向，直至寻得问题的最优解。如图 4 所示为粒子群算法优化的基本流程。?N、?x?v?pbest、?gbest?v、?x?/?图4粒子群优化算法流程基于上文构建的问题模型和 PSO 算法的优化流程进行算法实现，同样分为覆盖范围优化和数量优化 2 个部分。85一种基于粒子群算法的视频监控网络覆盖优化方法http:/ 工程勘测 增刊1 1)覆盖优化算法初始化种群规模 N，粒子维数 D；根据有效主光轴区间集合 Range_D 随机生成粒子位置 Xi(x1，x2，xD)，表示节点感知方向；随机生成速度 Vi(v1，v2，vD)，表示节点的感知方向变化量；设定最大速度区间 vmin，vmax，惯性权重区间 wmin，wmax，学习因子、，最大迭代数 T 等参数。计算各粒子的适应度值，并初始化各个粒子的个体最优位置 XpbestD和个体最优值pbest。迭代开始，更新惯性权重、粒子位置、速度，计算各个粒子的适应度值，对感知方向超过边界值的粒子进行边界条件处理，并根据适应度值的大小更新粒子的个体最优位置、最优值，以及全局最优位置和最优值。循环迭代，直至达到最大迭代数 T。最后的全局最优位置和全局最优值即为算法求解的结果，表示各个监控节点最优朝向。2)监控数量优化算法初始化种群规模 N，粒子维数 D；随机生成粒子位置 Xi(x1，x2，xD)，表示节点各节点的选中情况；随机生成速度 Vi(v1，v2，vD)，设定最大速度区间 vmin，vmax，惯性权重wmin，wmax，学习因子 c1、c2，最大迭代数 T 等参数。计算各粒子的适应度值，并初始化各个粒子的个体最优位置和个体最优值 pbest。迭代求解，更新惯性权重、粒子位置、速度，对越界的粒子进行边界条件处理，计算并更新各个粒子的适应度值。算法执行达到最大迭代数 T 时停止。此时的全局最优位置和全局最优值即为算法求解的结果，表示各个监控节点的选中情况。2实验及优化结果分析2.1 需求分析及数据准备为验证上文提出的优化算法的有效性，将某校园内的道路网络作为研究对象，以提升网络覆盖质量和资源利用率为目标，模拟并对区域内的视频监控网络进行覆盖优化。根据研究区内道路和功能区的分布特点，将监测对象分为主/次干道路、支路路口，为达到优化的目的，监控网络应当通过调整监控的位置和朝向，最大化覆盖道路里程和路口数量，并减少网络中的设备数量。实验数据以二维矢量数据为主，分为基础数据集和结果数据集。其中，基础数据集为基于研究区正射影像，通过超图桌面端 GIS 平台制作而成，作为分析的基础，包含 72 个路段的数据，其中主次干道的数量为 16，余下的为各交叉路口的支路路段，道路总里程为 6 822.3 m，以及 98 个候选监控点位；结果数据集主要用于记录运算结果，包括优化后的监控位置、朝向，以及覆盖率、重叠率等信息。由于道路网络的总里程较长，候选监控点数量较多，为减少计算耗时，便于算法参数的调整，如图 5 所示，将道路网络划分为 A、B、C 3 个部分。?A?B?C?图5道路网络划分及监控点位分布各个部分的道路里程、路段数、监控点数量等参数见表 1 所列。表1道路里程和候选点数量道路网络里程长度/m路段数监控点数量A2 503.044 4492735B2 560.648 2282334C1 772.7254 6724312.2 实验参数本文优化算法的实现为通过运用 C#语言，基于超图.NET 组件和 Visual Studio 2015 平台开发完成。实验参数主要分为监控节点感知模86http:/电 力 勘 测 设 计增刊1型参数和粒子群优化算法参数，其中节点感知模型的参数设置见表 2 所列。表2感知模型参数节点感知模型参数取值感知半径R/m50水平视场角/60主光轴偏移角/45粒子群算法参数设置见表 3 所列，其中进行覆盖优化时算法参数为取值 A，进行监控点数量优化时为取值 B。表3PSO算法参数PSO算法参数取值A取值B种群规模N5050惯性权重w0.2,0.90.4,0.8加速系数cc1=c2=1.5c1=c2=1.5粒子最大速度vmax-8,8-10,10最大迭代数T1001002.3 优化结果经算法求解，最终各道路网络的监控覆盖优化结果如图 6 所示。?(a)道路网络A覆盖优化结果 (b)道路网络B覆盖优化结果(c)道路网络C覆盖优化结果图6覆盖优化结果图中灰色扇形表示优化后的监控朝向，扇形内的红色线段为能有效覆盖的路段，黑色线段为未覆盖的路段。对覆盖优化后的监控网络的覆盖率、重叠率和路段覆盖数等进行统计，见表 4所列。基于上述监控网络覆盖优化结果，实验将50%的里程覆盖率和 90%的路段覆盖率作为优化下限，进一步对监控数量进行优化，最终各道路网络的监控数量优化结果如图 7 所示。表4覆盖优化结果统计道路网络 里程覆盖率/%里程重叠率/%路段覆盖数 监控数量A67627/2735B57421/2334C70223/2431?(a)路网A监控数量优化结果 (b)路网B监控数量优化结果(c)路网C监控数量优化结果图7监控数量优化结果87一种基于粒子群算法的视频监控网络覆盖优化方法http:/ 工程勘测 增刊1 图中灰色扇形组成的监控网络即为优化后的方案，黄色扇形为优化过程中被剔除的监控点位。对优化后的监控网络的里程覆盖率、路段覆盖数、监控数量进行统计，结果见表 5 所列。表5监控数量优化结果统计道路网络里程覆盖率/%路段覆盖数监控数量A50.1427/2735 26B50.0921/2134 29C50.6823/2331 202.4 结果分析2.4.1 覆盖优化结果分析根据覆盖优化的目标，算法对于网络的优化效果主要体现在以下 3 个方面：1)各部分监控网络的路段覆盖率均达到了90%以上，道路网络 A 中所有路段均得到覆盖，这表明道路网络中主要的支路路口、交叉路口均得到有效覆盖，满足了对路口的监控需求。2)监控网络的平均里程覆盖率达到了64%，平均里程重叠率为 6%，这表明优化后的监控网络能对大部分道路进行有效覆盖，能够保证监测目标暴露在监控中的时间，同时也很好地限制覆盖重叠率的增长。3)算法对监控朝向的优化，当监控仅有单个可覆盖路段时，大部分监控最终的朝向与道路保持了较小的夹角，如图 8(a)图 8(b)所示，最大化覆盖里程，与实际中道路视频监控的朝向设置特点相符；而在道路交错的地带，监控具有多个可覆盖路段，大部分监控的朝向设置在保证对路口的覆盖的同时，也很好地兼顾了覆盖的里程长度，如图 8(c)图 8(d)所示。虽然优化后的监控布设方案达到了较好的覆盖指标，但也存在一些不足，这与覆盖条件判断、候选节点的位置分布、算法优化倾向等因素相关。首先，判断监控覆盖条件的不能完全适用于各种道路结构。如图 9(a)所示，当存在 2 条并排且距离较近的道路时，由于缺少对道路流向的考虑，最终监控的朝向并不符合实际布设规律；其次，算法在监控主光轴区间边界的收敛情况有一定概率得到差的解，如图 9(b)图 9(c)中覆盖范围较差的覆盖情况。此外，由于未考虑点位布设密度与道路结构的复杂程度的关系，导致道路结构相对复杂时，监控朝向优化倾向于降低覆盖重叠率而非提升覆盖率，如图 9(d)所示。(a)里程覆盖优化效果 (b)朝向优化效果 (c)路段和里程优化效果 (d)路段优化效果 图8 局部覆盖情况(优)(a)朝向不合理点位 (b)低覆盖质量点位 (c)朝向错误点位(d)覆盖重叠点位图9 局部覆盖情况(劣)88http:/电 力 勘 测 设 计增刊12.4.2 监控数量优化结果分析监控数量优化的目的在于剔除网络中冗余的节点，降低网络的构建成本，其优化效果主要表现为对覆盖情况不理想的点位的过滤。从优化结果来看，算法能够很好地减少网络中节点的数量，各道路网络中监控数量有 14%35%的减幅，同时里程覆盖率很好地维持在目标值 50%附近。且相比于优化前，路段覆盖数并未减少，因此算法模型很好地达到了对网络的优化。而对于覆盖优化结果中出现的冗余、覆盖质量较差的点位，该模型也具备良好的过滤能力。如图10(a)图 10(b)中覆盖较差的点位等均被剔除，其中图 10(a)中 1 号点位虽具有较好的里程覆盖，但相较于相邻的 2 个节点，其对网络优化效果提升不大，因此也被纳入剔除的对象中；图 10(c)中 1 号和 2 号点位兼具备覆盖 2 个路段的条件，但由于位置相近，具有较大范围的监控重叠，3、4 号点位同样因为位置相近，导致覆盖质量较差而被剔除。由此可见，该算法模型对于网络中冗余、较差的点位具有一定的过滤能力。同时算法模型也存在一定的局限性。由于算法中缺少对监控点位分布密度的控制，因此在比较两个质量相差不多且相近的监控节点时，有一定的概率将有利于改善监控布局密度的点位剔除。图 11(a)中 2 号点位相比于 1 号点位更符合监控布局的合理性；若算法优先剔除的点位中存在具有较好覆盖里程但冗余的点位，那一些覆盖质量较差的点位会因为最低里程覆盖的限制而被遗漏，如图 11(b)中 3 号点位和 图 11(c)中 1 号点位。(a)相邻监控点剔除 (b)低里程覆盖点过滤(c)覆盖冗余点剔除图10 监控数量优化情况(优)(a)误检高覆盖质量点位 (b)遗漏里程覆盖重叠点位(c)遗漏低覆盖质量点位 图11监控数量优化情况(劣)2.4.3 算法性能分析对于粒子群优化算法等启发式算法的评价，主要通过对稳定性、准确性、运算时间等指标的分析。在覆盖优化实验中，根据各个目标参数在优化过程中的变化，曲线(图 12)从收敛速度上来看目标函数值、里程覆盖率、重叠率参89一种基于粒子群算法的视频监控网络覆盖优化方法http:/ 工程勘测 增刊1 数的优化在迭代 60 次左右收敛速度便减缓并逐渐区域收敛，而路段覆盖率的优化则在 15 次迭代左右便收敛至最优值，且在后续的迭代过程中始终保持稳定，很好地保证了监控网络覆盖路段数量的最大化。收敛速度上出现差异与计算的复杂度有关，由于路段离散分布且数量不多，计算量较少，而里程覆盖率、重叠率的计算则与监控点位的主光轴相关，且主光轴的取值区间是连续的，因此具有较高的组合和计算复杂度，导致收敛速度相对较慢。?A?B?C?1.651.61.551.51.451.41.351.31.251.20102030405060708090100(a)目标函数值变化曲线?A?B?C?0.750.70.650.60.550.50.450.40102030405060708090100(b)里程覆盖率优化曲线?A?B?C?0.10.080.060.040.020.090.070.050.030.010102030405060708090100(c)里程重叠率优化曲线?A?B?C?1.110.90.81.050.950.850.750102030405060708090100(d)路段覆盖率优化曲线图12目标参数优化曲线在算法稳定性上，从各个道路网络的 50 次独立重复实验中，适应度值的最大值、最小值，以及平均值和方差统计结果见表 6 所列。表6算法稳定性测试结果评价指标道路网络A道路网络B道路网络C最大值1.609 204 0331.449 631 3381.638 096 842最小值1.573 532 8791.430 151 4821.591 781 471平均值1.593 187 661.438 296 4811.613 006 449方差0.000 212 8073.802 82E-050.000 202 754从目标函数值的平均值、方差的大小中可以看出各个网络的覆盖优化模型均具有一定的稳定性。从算法运算时间上看，覆盖优化实验中的时间消耗主要集中在叠加求交分析的计算。粒子群规模为 50，粒子维数为 30 时，平均一次迭代时长在 80 s，完成 100 迭代将近消耗了 2 h的时间。而在监控节点优化实验中，由于未涉及空间分析计算，且为离散优化问题，因此运算时间大幅减少，完成 100 次迭代仅需 1.5 s 左右的时间。因此本文采用的算法模型在收敛速度、准确性和稳定性上均具有较好的表现，能够保证多目标优化问题的求解精度，但由于覆盖优化算法模型中目标函数的计算基于叠加分析进行，导致运算时间较长，因此后续该算法模型的优化将主要围绕减少空间分析的运算时间来进行。3结论综上所述，本文提出的基于粒子群算法的优化方法在对视频监控覆盖优化这类多目标优90http:/电 力 勘 测 设 计增刊1化问题进行求解时，达到了良好的优化效果，能够有效提升网络的覆盖质量，减小构建成本，同时基于真实地理场景数据的分析也能为实际应用打下基础。目前，倾斜摄影测量、点云、三维建模等技术已成为测绘行业进行数据采集的重要手段，高质量、高精度的地理数据蕴含较大的信息挖掘和分析的价值，而三维地理数据加入能够使视频监控布局和覆盖优化的研究成果具备更高的应用价值。此外在当下电力工程项目中，视频监控是无人值守变电站、智能线路巡检、自然灾害预警等电网建设中重要的监测手段，其布局的合理性同样影响到项目的运维成本。因此，本文后续研究将以工程应用为目标，基于三维地理数据和三维感知模型，利用可视域分析等 GIS 分析技术，对输电线路运维过程中监控的布局和覆盖优化问题进行 研究。参考文献1 李雯静，胡丹，李楠.基于地理场景的矿区监控选址模型J.金属矿山，2020，531(9)：87-95.2 MA H,LIU Y.On Coverage Problems of Directional Sensor NetworksC/Mobile Ad-hoc and Sensor Networks,First International Conference,MSN 2005,Wuhan,China,December 13-15,2005，Proceedings.DBLP,2005.3 TAO,DAN.A Virtual Potential Field Based Coverage-Enhancing Algorithm for Directional Sensor NetworksJ.Journal of Software,2007.4 MA H,ZHANG X,MING A.A Coverage-Enhancing Method for 3D Directional Sensor NetworksC/2009：2791-2795.5 肖甫，王汝传，孙力娟，等.一种面向三维感知的无线多媒体传感器网络覆盖增强算法J.电子学报，2012(1)：167-172.6 贾子熙，吴成东，张云洲，等.基于三维感知模型的WMSNs最优空间覆盖研究J.东北大学学报(自然科学版)，2015，36(12)：1673-1677.7 杨宇放.基于三维感知模型的多媒体传感器网络覆盖增强算法研究D.沈阳：东北大学，2015.8 M.C.ZHAO,J.LEI,et al.“Surface Coverage in Wireless Sensor Networks”IEEE INFOCOM 2009,Rio de Janeiro,Brazil,2009：109-117.9 孙伟，曹姗姗，唐小明.林火视频监控空间优化布局与评价技术J.自然灾害学报，2013，22(2)：61-69.10 孙建伟.山区视频监控点选址算法研究D.南京：南京师范大学，2015.11 吴明珠.自然保护区视频监控点的优化选址研 究D.上海：华东师范大学，2016.12 曹姗姗.森林防火视频监控布局研究D.哈尔滨：哈尔滨师范大学，2011.13 高飞.视频传感器网络多目标多要素三维覆盖优化调度方法D.南京：南京师范大学，2018.14 ZOU Y,CHAKRABARTY K.Sensor deployment and target localization in distributed sensor networksJ.Acm Transactions on Embedded Computing Systems,2004,3(1)：61-91.15 蒋鹏，金炜东，秦娜，等.基于粒子群优化的视频传感器网络覆盖增强算法J.计算机科学，2014，41(4)：57-61.16 蒋一波，王万良，陈伟杰，等.视频传感器网络中无盲区监视优化J.软件学报，2012，23(2)：310-322.17 ALTAHIR A,ASIRVADAM V S,HAMID N,et al.Camera coverage prioritization to support security monitoringC/International Conference on Intelligent&Advanced Systems.IEEE,2016.18 权恩猛.基于遗传算法的多障碍区域最大覆盖优 化J.工业控制计算机，2017，30(12)：108-110.19 WANG Y,DOU W.A fast candidate viewpoints filtering algorithm for multiple viewshed site planningJ.International Journal of Geographical Information Science,2019(3)：1-16.20 WANG C,QI F,SHIG M.Nodes Placement for Optimizing Coverage of Visual Sensor NetworksC/Conference on Advances in Multimedia Information Processing-pcm.DBLP,2009.(编辑 卢靖冉)