1. 引言
随着无线视频传感器网络(Wireless Sensor Networks, WSN)技术的不断发展和应用,无线视频传感器节点被广泛应用于环境监测、物联网、智能交通、智能家居等领域[1]-[5]。无线视频传感器节点通常通过无线摄像机进行数据采集,以实现对目标区域的监测和控制。在这些应用中,无线视频传感器节点网络的覆盖率是一个至关重要的指标,它衡量了网络中感兴趣区域被传感器节点有效覆盖的程度。无线视频传感器节点网络的覆盖率直接影响到网络的性能和可靠性。高覆盖率可以提供更准确、可靠的数据采集和信息传输,从而提高应用系统的性能。为了充分利用有限的传感器资源,提高传感器网络的覆盖性能,设计高效的无线摄像机节点部署策略变得至关重要。
无线摄像机传感器网络中节点的分布(位置和方向)将极大地影响摄像机网络的总覆盖范围(Field of View, FOV)。为了解决这一问题,研究人员采用了许多优化算法来进行视频摄像机传感器的部署优化。2005年,Ma等[6]首次提出了有向传感器网络的概念。但其未对传感器网络的更多指标进行研究和讨论,如传感器网络覆盖率等。2007年,Tao等[7]讨论了有向传感器网络的覆盖率,使用了一种基于虚拟势场的有向传感器网络覆盖增强算法(Potential Field Based Coverage-Enhancing Algorithm, PFCEA),将网络覆盖增强问题转化为质心均匀分布问题,同时设计了仿真实验验证了算法的有效性。然而,并未对不同检测目标区域分类讨论,对于目标区域的检测权重变化并未进行仿真实验。对于检测区域的分类,Xu等[8] [9]对其进一步地细化,选用矩形目标检测区域进行仿真实验,将PSO算法(Particle Swarm Optimization)应用于无线传感器网络覆盖问题。同时将PFCEA算法应用于相同模型进行比较,发现了PSO算法对于此类连续性问题具有较大的优势。同年,Zhou等[10]将PSO算法用来求解无线传感器网络覆盖问题,并与分层方法进行比较,明确了PSO算法的具体优势。
为了克服传统PSO算法容易陷入局部收敛、收敛速度慢等不足。近年来,很多研究者致力于改进PSO算法本身。2013年,Xu等[11]对于可移动的传感器节点进行了进一步的探究,使用三种改进的PSO算法进行求解并对比,最终给出了较为合适的PSO改进思路,但其并未讨论关于PSO自身的参数因子改动方案。2015年,Fu等[12]在文章中提出通过改进PSO算法的惯性因子来增强覆盖,并与PFCEA算法进行比较,观察改进的PSO算法的相对优势。同时将节点数量增加,探索并模拟了节点数量达到相对较大规模时的情况。然而,其仅考虑了惯性因子的改进并未考虑学习因子的改进,存在对于自身历史轨迹模仿。2020年,Fu等[13]在文章中提出了同时改进PSO算法中的惯性因子与学习因子的方案,并于PFCEA算法比较,同时探索了节点数量达到相对较大规模时的情况。通过不断减小惯性权重与自我学习程度同时不断增加群体学习程度,在节点数较大的情况下对模型进行了仿真实验。然而,其搜索策略仍较为单一,由于在迭代中后期对于群体学习的程度较高,使得整体对局部最优的逼近速度增加的同时限制了对其的进一步优化,可以看出对整体粒子使用单一策略搜索很容易使其陷入局部最优且难以跳出。
MPSO算法(Multi-Swarm Particle Swarm Optimization,多群体粒子群优化算法),通过引入收缩因子、动态概率等改进办法,其具有提高局部搜索能力、避免陷入局部最优、并行计算优势、适应性调整等优点[14] [15]。本文基于MPSO算法求解有向感知传感器网络覆盖增强问题,提出了改进的MPSO算法,设计多种策略共同寻优。同时,考虑到固定位置的节点模型对于搜索具有一定限制,本文对传感器节点添加了移动轨道,组成可移动的节点模型,增强了优化重叠感知区域与覆盖感知区域的能力。且本文对于不同的初始化节点分布进行了探讨,定义了聚集度的概念,并使用聚集因子生成不同聚集度的初始部署方案,进一步梳理使用算法最大化优化覆盖感知区域的路径。本文对上述研究均设计并实施了仿真实验,以验证所提出的改进MPSO算法的优势。
2. 含移动轨道的节点模型
定义R为半径,CA和CB为两侧边界,d为朝向,其方位角为
,扇形夹角为2α。其轨道圆心为定点D,视频摄像机传感器坐标C(x, y)的运动轨道为圆,围绕圆心D在半径为r的轨道上移动,当r为0时,该模型可退化为固定节点的传感器网络模型。在实际应用中,固定位置的节点模型对于搜索具有一定限制,因此视频摄像头架设的位置设计为可移动轨道也是一种重要的优化策略,可以通过调整摄像头的位置来优化其视野范围和覆盖性能,可旋转节点图如图1。定义向量d的方向角
是向量d与x轴正方向的夹角,
。向量DC的方向角
是向量DC与x轴正方向的夹角
。
Figure 1. Rotatable node with moving orbit
图1. 含移动轨道的可旋转节点
本文采取了网格化处理。传感器覆盖范围通过计算覆盖网格数与总网格数的比值来定义。将检测区域划分为网格,根据在给定条件下传感器能够覆盖的网格数量判断覆盖率。本文在网格模拟的基础上提出重叠率的定义,进一步设计覆盖网格矩阵,对单个网格计算有向摄像机网络节点对其的重复检测次数。传感器覆盖率CR (Coverage rate)和重叠率OR (Overlap rate)的计算公式如下:
(1)
这里Cg表示被覆盖的网格数,Tg表示网格总数。计算已覆盖和未覆盖的网格,组成覆盖网格矩阵。NCg表示单个网格被覆盖的次数,其覆盖次数为覆盖的传感器数量。
3. 求解算法研究
3.1. PSO算法
PSO算法是一种基于群体智能的优化算法,模拟了鸟群或鱼群等生物群体在搜索目标时的行为。它由Eberhart和Kennedy于1995年提出,灵感来源于对鸟群觅食行为的观察[16]。在PSO算法中,将候选解空间中的每个解看作一个粒子。粒子的速度会被引导向当前找到的最优解的方向,同时也受到自身历史经验和全局最优解的影响。通过不断迭代,粒子会逐渐收敛于全局最优解或局部最优解。
其迭代基础流程如下:设xi(t)为第t代的粒子集合,即问题的解的集合,取i的值从1到N,即包含N个粒子。vi(t)为粒子第t代速度。速度和位置更新公式如下:
(2)
其中w是惯性系数,也叫惯性因子,代表对原速度的惯性保持;c1为认知系数,代表对自身位置的认知程度;c2为社会系数,表示对群体位置和行为的跟随程度,即从众程度;r1、r2为(0, 1)之间的相互独立的随机数,t为迭代次数;pi代表第i个粒子的粒子个体历史最佳位置;Gbest代表种群历史最好位置。
3.2. 系数改进的PSO算法
经典PSO算法因其自身性能和收敛速度的不足,常见的改进方法包括引入自适应权重、加入惯性权重因子、使用不同的拓扑结构、引入局部搜索策略等。这些改进方法旨在平衡全局和局部搜索、提高算法的搜索效率和收敛精度,例如IPSO算法(Improved Particle Swarm Optimization) [17]、系数改进的PSO算法[18]等。
改进的方式之一为修改惯性系数、认知系数和社会系数,以此得到具有自适应能力的PSO算法。惯性系数加入自适应惯性权重,根据粒子的搜索历史和群体的全局信息来调整惯性系数。可以根据粒子的适应度值和速度变化情况来动态调整惯性系数,以平衡全局搜索和局部搜索的权衡。在PSO的迭代过程中,逐渐减小惯性系数,从而使粒子在初期有较大的独立探索能力,而在后期有较强的局部搜索能力可以使算法结果迅速收敛。其修改方案如下:
(3)
认知系数和社会系数加入自适应权重,根据个体的历史经验和群体的经验来动态调整认知系数和社会系数。可以根据粒子自身的适应度值和个体或全局最优解的距离来调整这两个系数,以平衡个体经验和群体经验的权衡。在PSO的迭代过程中,逐渐减小认知系数和社会系数,从而使粒子在初期更加注重个体经验,而在后期更加注重群体经验。其修改方案如下:
(4)
其中c1max,c1min,c2max,c2min,wmax,wmin为对应系数最大最小值,MaxIT为最大迭代次数。在(2)中c1,c2,w会根据(3)、(4)随着迭代不断变化,使得粒子群可以在初期采用较大的惯性系数以便更大范围的搜索,快速到达全局最优解的附近,在后期采用较小的惯性系数以便更精细的搜索,使算法更加稳定的收敛至全局最优解。
3.3. 改进的MPSO算法
MPSO算法是一种改进的粒子群优化算法,将种群分为多个独立的群体,并通过多个群体之间的协作和信息交换来提高搜索性能。每个群体由一组粒子组成,每个群体都有自己的速度更新和位置更新策略,并独立地搜索解空间。与传统的PSO算法相比,MPSO具有以下特点:
多样性增强:每个群体独立地搜索解空间,增加了种群的多样性。这有助于避免陷入局部最优解,提高全局搜索能力。
协作与竞争:不同群体之间可以进行信息交换和经验共享,以加速收敛和提高搜索效率。群体之间的协作可以使整个种群更好地探索解空间,并共同寻找最优解。
MPSO中可以调整不同群体的参数设置,如群体数量、粒子数量、速度更新策略等,以适应不同问题的特点和需求。MPSO算法广泛应用于复杂的优化问题,特别是在解空间具有多个局部最优解的情况下。通过引入多个群体和协作机制,MPSO能够提供更好的搜索能力和全局优化性能。
本文中,我们通过引入多群粒子群算法来优化覆盖率,能够充分利用它们在搜索空间和信息交流方面的优势,从而增加搜索的广度和深度,以获取更优的覆盖率解决方案。这种结合算法的方法能够在视频传感器网络中提高覆盖率的效果,并为优化问题的求解提供了一种有力的工具。具体而言,我们将覆盖情况表示为0和1的矩阵。通过适应度函数的计算,我们能够评估每个粒子的适应度,从而确定种群的更新。同时,我们还可以改进覆盖矩阵,将其中的0和1改为覆盖重数,从而得出重叠率。加入重叠率后对应的适应度为:
(5)
Fitness为适应度,p1为覆盖率系数,p2为重叠率系数。由定义可知Fitness越小越好。在迭代过程中,子代的生成遵循MPSO算法迭代规则,在其概念的基础上进行了一定的改动,选择对迭代过程中的w,c1,c2进行变异。方式为将种群分组,对不同的分组采取不同的变异程度,包含固定系数组和可变系数组,可变系数采取了一定的随机性。四组速度和位置的更新遵循式(2)。
第一分组将迭代系数设为固定系数的分组,其系数设置参考文献内容设置为w = 0.729,c1 = 1.49445,c2 = 1.49445;第二组与第三组的参数设置策略为3.2节中的系数改进的PSO策略,即在迭代前期增加或减少个体探索以及迭代后期减少或增加全局探索的分组,第二组设置为迭代前期增加个体探索以及在后期增加全局探索的分组,其参数分配见式(3)、(4);而第三组设置为在迭代前期增加全局探索以及在后期增加个体探索的分组第三组的惯性系数、认知系数和社会系数分配如下:
(6)
第四组则是按照随机函数设置系数的分组,加大其随机权重,以此模拟变异过程,目的在于进一步增加搜索空间。
(7)
3.4. 粒子结构设计
将MPSO算法应用于模型求解的关键在于粒子如何定义,其原因在于微观上的求解迭代过程遵循式(3)。在原传感器节点组成的摄像机网络中,一定数量的有向视频和摄像机传感器的主感知方向的全部摆放方式为其系统状态,将这一状态视作问题模型的解。
预设模型包含数量为N的视频摄像机传感器节点。考虑到摄像机圆心不固定,对于单个摄像机需要两个运动维度,解的形式定义为
。
为传感器主感知方向的方向夹角。对于轨道圆心的位置,通过随机函数在C附近距离r的圆上初始化,之后以此为定点。
3.5. 改进的MPSO算法流程
步骤一:初始化视频传感器网络节点,生成固定转轴和轨道上的传感器位置,记录所有粒子中的DC方向角
。为每个节点随机生成初始的主感知方向,记录其方向夹角
。
Figure 2. Improved MPSO algorithm flow diagram
图2. 改进的MPSO算法流程图
步骤二:初始化粒子个体历史最优状态和全局历史最优状态,以及初始化节点处传感器自身的转向角速度和绕固定转轴的轨道移动角速度。这些速度的取值范围设定在
之间。
步骤三:基于式(2),对所有个体的绕固定转轴的速度和摄像机自身的旋转速度进行更新迭代。
步骤四:根据目标函数计算传感器网络覆盖率与重叠率,并通过适应度函数计算适应值,更新个体历史最佳位置和全局最佳位置。
步骤五:基于式(3) (4) (6) (7)的算法公式来更新惯性因子和学习因子,控制个体在搜索空间中的探索和模仿能力。
步骤六:返回步骤三继续迭代,直至迭代次数达到设定的最大迭代次数MaxIT。最终达到搜索空间中的最优解或接近最优解的位置,具体算法流程如图2。
4. 仿真实验与结果分析
本文采用了MATLAB R2018a软件进行仿真实验。在MATLAB环境中,仿真实验获得了可靠和高效的仿真环境,确保了实验结果的可信度和可重复性,因此我们能够对不同算法在有向视频传感器网络中的应用进行准确的模拟和评估。
通过将传统PSO算法和系数改进的PSO算法应用于固定位置可连续旋转感知方向的传统模型以及可连续移动位置且可连续旋转感知方向的新模型,进行对比实验,旨在验证新模型具有更大的优化空间。此外,还将传统PSO算法、系数改进的PSO算法和本文提出的改进的MPSO算法应用于可连续移动位置且可连续旋转感知方向的新模型,观察其优化过程和结果,以验证改进的MPSO算法的卓越性能。
4.1. 实验参数初始化
对于固定节点模型与圆轨道可动节点模型其二者的适用情况需要精细化区分,我们提出一种利用二维正态分布函数确定节点位置密集程度的描述方法。将所部署的节点位置定义为二维正态分布的对称位置,其表达式为:
其中F表示聚集度函数值,N为节点数,
,
取值为30,X,Y设置为以0起始按照步长为0.5增加至地图边界的地图网格信息,x,y为节点坐标,
为相关系数,取值为0。
为比较聚集度差异带来的影响,需要控制地图传感器节点的聚集程度,其随机部署方法如下:
其中w是地图宽度,h是地图的高度,rand为[0,1]之间的随机数,DF (DensityFactor)为聚集因子,为模拟现实情况,通过控制DF的值来控制节点的聚集效果。
将检测区域定义为500 m × 500 m的平面区域,采用的有向视频摄像机传感器节点数为N = 150,并利用随机函数,将其随机部署在区域内。同时,对于新模型,利用随机函数对各方案生成所有传感器的移动轨道圆心D,计算并保存其初始方位角
。节点的感知半径为R = 50 m,新模型中的节点可移动轨道半径r = R/5,视角范围设置为
,最大迭代次数设置为MaxIT = 200。令覆盖率系数p1 = 1000,重叠率系数p2 = 1,聚集因子DF = 0.4。
将实验分为六组。第一组、第二组、第三组采用固定位置即移动轨道半径为0的可连续旋转感知方向的固定节点模型,第四组、第五组、第六组采用可连续移动位置且可连续旋转感知方向的新模型。同时,第一组与第四组采用传统PSO算法求解,第二组与第五组采用系数改进的PSO算法求解,第三组与第六组采用改进的MPSO算法求解。
4.2. 实验结果与分析
通过随机函数将初始化地图中的有向视频传感器节点位置与朝向初始化,得到优化前的图像。
图3(左)展示了在使用算法优化前的传感器网络节点部署方案的覆盖情况,红色十字为传感器节点,
Figure 3. Sensor network awareness image (left) and aggregation function image (right) before optimization
图3. 优化前传感器网络感知图像(左)与聚集函数图像(右)
Figure 4. Fan-sensing regions in the first (left) and second (right) groups
图4. 一(左)二(右)组扇形感知区域
灰色区域为感知区域。初始覆盖率为57.57%,初始重叠率为200.02%。图3(右)以三维视角演示初始部署方案的聚集程度,初始密集度为1.47。
Figure 5. Fan-sensing regions in the third (left) and fourth (right) groups
图5. 三(左)四(右)组扇形感知区域
Figure 6. Fan-sensing regions in the fifth (left) and sixth (right) groups
图6. 五(左)六(右)组扇形感知区域
图4~6为传感器网络优化后的六组部署检测区域示意图。从图中可看出,通过一组与四组、二组与五组、三组与六组的比较,在同一算法下,可以观察到可移动轨道模型的优势。通过四组、五组和六组的比较可以观察到,对于可移动轨道模型,改进的MPSO算法具有覆盖率更高、重叠率更低的优势。
Figure 7. Aggregate function diagrams in the first (left) and second (right) groups
图7. 一(左)二(右)组聚集函数示意图
Figure 8. Aggregate function diagrams in the third (left) and fourth (right) groups
图8. 三(左)四(右)组聚集函数示意图
Figure 9. Aggregate function diagrams in the fifth (left) and sixth (right) groups
图9. 五(左)六(右)组聚集函数示意图
图7~9为传感器网络优化后的六组聚集函数图。从图中可看出,通过一组与四组、二组与五组、三组与六组的比较,在同一算法下,可以观察到可移动轨道模型对聚集度有更强的优化效果。通过四组、五组和六组的比较可以观察到,对于可移动轨道模型,改进的MPSO算法对聚集度有更强的优化效果。
Figure 10. Comparison of coverage optimization curves
图10. 覆盖率优化曲线对比
Table 1. Six groups of experimental results
表1. 六组实验结果
组别 |
运行时间 |
优化后覆盖率 |
覆盖率提升 |
优化后重叠率 |
重叠率降低 |
第一组 |
279.13 |
62.25% |
5.33% |
185.18% |
14.84% |
第二组 |
277.45 |
62.94% |
5.62% |
184.64% |
15.38% |
第三组 |
278.00 |
63.05% |
5.93% |
183.11% |
16.91% |
第四组 |
282.12 |
63.73% |
6.61% |
180.92% |
19.10% |
第五组 |
281.67 |
64.26% |
7.14% |
180.51% |
19.51% |
第六组 |
284.25 |
64.45% |
7.33% |
178.80% |
21.22% |
通过六组的实验结果(见表1),对于传统的模型,由一组、二组、三组对比可知,改进的MPSO算法相较于PSO算法提升了11.26%,相较于系数改进的PSO算法提升了5.62%;对于可移动节点的模型,由四组、五组、六组对比可知,改进的MPSO算法相较于PSO算法提升了10.89%,相较于系数改进的PSO算法提升了2.66%,因此改进的MPSO算法求解可移动节点的模型,其覆盖率有显著提升(如图10)。
一组、二组、三组的对比实验可知,在没有移动轨道的情况下,改进的MPSO算法的重叠率相较于PSO算法优化了2.07%,相较于系数改进的PSO算法优化了1.53%;四组、五组、六组的实验对比可知,改进的MPSO算法相较于PSO算法优化了2.12%,相较于系数改进的PSO算法优化了1.71%,因此改进的MPSO算法求解可移动节点的模型,其重叠率有显著优化。
4.3. 过程参数对求解的影响
对各过程参数设置变化区间,统一使用本文中的MPSO算法求解。将检测区域规定为500 m × 500 m的平面区域,视角范围设置为
,覆盖率系数p1 = 1000,重叠率系数p2 = 1。
Table 2. Parameter setting
表2. 参数设置
|
模型 |
聚集因子 |
轨道半径 |
感知半径 |
节点数 |
迭代次数 |
对比试验1 |
节点可动 |
0~1.0 |
10 m |
50 m |
150 |
200 |
对比实验2 |
节点可动 |
0.4 |
10~25 m |
50 m |
150 |
200 |
设置DF在[0, 1]间,初始化传感器网络部署,根据表2对生成的初始解进行处理,记录初始覆盖率、优化后覆盖率、初始聚集度、优化后聚集度。不同聚集因子优化后的覆盖率和聚集度结果见表3。
Table 3. Degree of aggregation and coverage rate with different density factors
表3. 聚集因子影响表
聚集因子 |
初始覆盖率 |
优化覆盖率 |
覆盖率增量 |
初始聚集度 |
优化后聚集度 |
0.0 |
65.81% |
71.49% |
5.68% |
1.181219 |
1.124404 |
0.2 |
61.91% |
68.93% |
7.12% |
1.359850 |
1.209438 |
0.4 |
59.86% |
65.73% |
6.09% |
1.437131 |
1.384488 |
0.6 |
55.39% |
59.61% |
4.53% |
2.038812 |
1.999683 |
0.8 |
50.03% |
55.12% |
5.18% |
2.329772 |
2.235442 |
1.0 |
43.54% |
49.51% |
6.22% |
4.921214 |
4.100324 |
由实验可得,随着聚集因子不断增大,初始覆盖率会随之下降,初始聚集度会随之增高,这意味着有效覆盖区域减少,传感器网络的节点彼此之间过于密集,导致感知区域重叠情况十分严重。使用改进的MPSO算法对其优化的幅度也会逐渐降低,这是由于聚集程度过高,即便拥有移动轨道,但其轨道半径长度不足以进一步优化其覆盖区域。因此简单的旋转感知方向无法跳出重叠区域解决重叠率高的情况。 结合前一节的实验,可以直观的感受到,在节点密集的情况下,可移动节点模型的覆盖优势。
对比实验二中设置传感器节点移动轨道半径r于[5 m, 25 m]间,初始化传感器网络部署,始解覆盖率为58.03%,重叠率为201.81%,聚集度为1.403865。根据表2对生成的始解进行处理,记录优化后覆盖率、优化后重叠率见表4。
Table 4. Overlap rate and coverage rate with different orbit radii
表 4. 轨道半径影响表
轨道半径 |
优化覆盖率 |
覆盖率提升 |
优化重叠率 |
重叠率降低 |
5 |
63.80% |
5.77% |
182.88% |
18.93% |
10 |
63.88% |
5.85% |
182.29% |
19.52% |
15 |
63.98% |
5.95% |
180.12% |
21.69% |
20 |
64.79% |
6.76% |
178.85% |
22.96% |
25 |
65.08% |
7.05% |
174.01% |
27.80% |
仿真实验表明,随着半径的增大,覆盖率相应提升,其提升幅度也保持增加;对应的重叠率相应下降,其下降幅度保持增加。此时的聚集因子DF = 0.4,可见,在一定的聚集程度下,较大的活动轨道给予了网络获取更高覆盖率与更低重叠率的可能。
5. 总结
本文对于固定节点传感器模型进行了改进,添加了可移动轨道。在其数量增加组成的传感器网络中,使用网格方法与状态矩阵计算覆盖率与重叠率。为探究初始部署对于优化的影响,进一步的定义了聚集度的概念,并设计了聚集函数以评价部署方案的聚集程度,同时对于初始化部署的过程加入聚集因子进行调控。
在优化算法方面,本文对PSO算法进行改进,设计了含四种不同搜索策略的粒子分群的MPSO算法,并将覆盖率与重叠率组合,定义其适应度函数。在后续仿真实验中,比较了PSO算法、系数改进的PSO算法和改进的MPSO算法在相同模型下求解的表现;比较了不同节点模型在相同算法下求解的表现,实验验证了本文提出的模型和算法的优势。
基金项目
本文由国家自然科学基金项目(11801281),南京邮电大学教学改革研究项目(JG00723JX21, JG00723JX56)资助。