基于改进PSO的视频传感器网络覆盖增强算法

An Effective Coverage Enhancement Method for Video Sensor Network Based on Improved PSO

摘要: 感知覆盖反映了网络的感知服务质量，是进行其它研究的基础和先决条件。针对传统粒子群优化算法(PSO: Particle Swarm Optimization)，算法模型采用固定的参数，使得算法收敛速度较慢或无法收敛到最优解的问题，本文将改进的PSO算法应用于视频传感器网络感知覆盖中，通过改进PSO模型的惯性因子和学习因子，使得算法在初期具有较大的惯性，在节点局部范围内大幅度搜索，可以提高收敛速度；在末期惯性较小，以较小的步长在全局最优位置附近搜索，可以使算法最终收敛于全局最优，提高网络覆盖率。实验表明，本文算法收敛速度快，覆盖率明显提升。

Abstract: Coverage rate can reflect the sensing quality of sensor networks. It is the foundation and precondition for other related researches. The unchangeable parameters of traditional PSO algorithm may lead to slow convergent speed or being unable to converge to the optimal solution. In this paper, an improved PSO is proposed and applied to the coverage enhancement of video sensor network. By improving the inertia weight and learning factors, the algorithm has larger inertia at starting period. The nodes search in the local region with bigger steps and improve the convergent speed. At later stage, smaller inertia will lead to the algorithm searches near the optimal point with small steps. Then, the algorithm has high possibility to converge to the global optimal solution and improve the coverage rate. Experimental results show that the proposed method has high converging speed, and the coverage rate is improved effectively.

1. 引言

无线传感器网络具有可快速部署、可自组织和隐蔽性强等特点，因此十分适合应用于环境监测、交通控制、战场侦察等方面。由于视频传感器可以提供直观的图像数据，近年来，随着视频传感器技术的发展和成本的降低，视频传感器网络得到了越来越多的应用。覆盖增强作为传感器网络中的一个基本问题，众多国内外学者开展了这方面的研究 [1] [2] [3] [4]，大多数相关研究中，传感器节点都满足全向感知模型。然而，视频传感器只能感知有限角度范围内的区域，是一种方向受限的有向传感器，因此，现有的节点覆盖研究成果不能直接应用于无线视频传感器网络，于是，出现了针对无线视频传感器网络的覆盖研究。

文献 [5] 率先提出了有向感知模型的概念，并研究了有向传感器网络覆盖完整性及连通性问题。基于虚拟势场的方法 [6] [7] [8] 是研究较多的有向传感器网络覆盖增强方法，在有向感知模型的基础上引入虚拟势场，并利用质心受力将方向调节问题转化为质心均匀分布问题，通过消除网络中感知重叠区和盲区实现整个有向传感器网络覆盖的有效增强。但是，当节点所受的力达到平衡时，但节点方向不能再动，节点不一定处于最优方向 [9]，因而影响覆盖率。为了克服基于虚拟势场的依法的不足，Xu等人 [9] [10] 提出利用PSO方法解决视频传感器网络的优化覆盖问题。但是由于所采用的PSO算法本身的不足，上述基于PSO的方法存在容易陷入局部收敛、收敛速度慢等不足 [11]。

本文为了克服上述基于PSO方法的不足，提出了一种新的视频传感器网络覆盖增强算法，该算法对PSO算法的惯性因子和学习因子进行改进，实验表明，本文算法比传统方法收敛速度更快，覆盖效果更好。

2. 基于PSO算法的有向传感器网络覆盖增强

2.1. 视频传感器网络模型

本文采用与文献 [9] 相似的视频传感器节点模型，如图1所示。视频传感器节点C的位置为 $\left(x,y\right)$，视场角大小为 $2\alpha$， $\theta$ 为主感知方向 $d$ 的方位角，节点的感知半径为R。视频传感器网络中的节点采用随机部署的方法确定各节点的位置和初始感知方向，节点的感知方向360˚可调。扇形ABC所在的区域为当前节点的感知区域，整个网络的感知覆盖率定义为：

$CR=\frac{CA}{TA}$ (1)

其中CR表示网络覆盖率(Coverage Rate)；CA表示被覆盖到的总面积(Covered Area)，包括被一个或多个视频传感器节点覆盖的所有区域；TA是目标区域的总面积(Total Area)。

Figure 1. Model of video sensor node

图1. 视频传感器节点模型

2.2. 基于PSO的覆盖增强方法

粒子群算法是一种解决复杂问题近似解的优化算法，具有简单、高效和易于实现的特点，常常为NP难问题提供一种较优方案。设 $x_i\left(n\right)$ 表示粒子i在n时刻的位置， $v_i\left(n\right)$ 表示粒子i在n时刻的速度，则粒子的速度和位置更新可由式(2)和(3)得到。

$v_i\left(t+1\right)=w{v}_i\left(t\right)+c_1{r}_1\left(P_i-p_i\left(t\right)\right)+c_2{r}_2\left(G_{best}-p_i\left(t\right)\right)$ (2)

$x_i\left(t+1\right)=x_i\left(t\right)+v_i\left(t+1\right)$ (3)

其中w表示对原有速度的惯性作用，称为惯性因子； $c_1$ 表示对个体自身位置的认知程度，称为认知系数； $c_2$ 是对群体内社会行为的跟踪程度，称为社会系数； $r_1$ 、 $r_2$ 为(0, 1)之间的独立随机数，t为迭代次数； $P_i$ 和 $G_{best}$ 分别为粒子和粒子群的历史最好位置。

文献 [9] 定义 $x=\left({\theta }_1,{\theta }_2,\cdots ,{\theta }_N\right)$，即节点的感知方向为粒子，目标函数由式(1)的网络覆盖率得到。对粒子位置的更新过程，就是对节点感知方向的调节和搜索过程。文中对速度v的大小不作限制。

3. 改进PSO算法及其应用

3.1. 改进的PSO算法

式(2)中 $c_1$ 和 $c_2$ 为学习因子，又称加速因子，分别用于调节微粒向局部最优和全局最优的进化步长。在文献 [9] 中取 $c_1=c_2=1.49445$，表明算法对局部和全局最优使终保持相同的倾向。实际上，较大的 $c_1$ 和较小的 $c_2$ 使得粒子在算法初期搜索粒子的可能位置，更加强调粒子的局部最优值；较小的 $c_1$ 和较大的 $c_2$ 使得粒子在算法后期快速收敛到全局最优。因此，加速因子可定义为：

$c_1=c_{1\max }-t\ast \left(c_{1\max }-c_{1\min }\right)/MaxIT$ (4)

$c_2=c_{2\min }+t\ast \left(c_{2\max }-c_{2\min }\right)/MaxIT$ (5)

其中 $c_{1\max }$， $c_{1\min }$， $c_{2\max }$， $c_{2\min }$ 分别为两因子的最大值和最小值，由式(5)和(6)可以看出， $c_1$ 和 $c_2$ 为随着的迭代过程而变化，算法最开始，拥有最大的 $c_1$ 和最小的 $c_2$，算法最后相反，拥有最小的 $c_1$ 和最大的 $c_2$。

由式(2)可以看出，对于PSO算法，较大的惯性因子w利于粒子进行全局搜索，而较小的w利于搜索局部最优值。传统PSO算法的惯性因子为常数，在文献 [9] 中取 $w=0.729$，表明粒子群对于全局和局部一直保持同样的重视程度。若在搜索初期，粒子群能以更大的惯性因子进行搜索，则能使算法能快速到达全局最优解附近；而在搜索后期能以较小的惯性搜索，能使算法稳定收敛至全局最优解，因此，w可被定义为：

$w\left(t\right)=w_{\max }-\frac{\left(w_{\max }-w_{\min }\right)\times t}{MaxIT}$ (6)

其中 $w_{\max }$ 和 $w_{\min }$ 分别为惯性因子的最大值和最小值， $MaxIT$ 为规定的最大迭代次数。式(4)表明，惯性因子随着迭代次数的增加而减小，第一次迭代时，其值为 $w_{\max }$ ；最后一次迭代时，值为 $w_{\min }$。

3.2. 本文视频传感器网络覆盖增强算法步骤

基于以上分析和研究，本文基于改进PSO的视频传感器网络覆盖增强算法步骤可描述如下：

第1步：随机部署N个视频传感器网络节点，随机产生各节点的初始主感知方向 $x\left(0\right)=\left({\theta }_1,{\theta }_2,\cdots ,{\theta }_N\right)$，并视为粒子。

第2步：将粒子的初始位置作为粒子和粒子群的历史最好位置P_i和G_best取 $v_1\left(1\right)=v_2\left(1\right)=\cdots =v_N\left(1\right)=vs$ 作为粒子各维的初始速度。

第3步：基于式(3)，即 $x_i\left(t+1\right)=x_i\left(t\right)+v_i\left(t+1\right)$ 对粒子各维进行迭代，得到新一代粒子 $x\left(t+1\right)$。

第4步：将式(1)作为粒子群的目标函数，计算网络覆盖率，更新粒子和粒子群的历史最好位置 $P_i$ 和 $G_{best}$。

第5步：基于式(4)到式(6)计算惯性因子和学习因子，并利用式(2)计算粒子新的速度。

第6步：返回第3步继续迭代，直至迭代次数达到 $MaxIT$。

4. 实验及分析

为了验证本文视频传感器网络覆盖增强算法的性能，进行了三种类型的实验，并与文献 [9] 中传统基于PSO的视频传感器网络覆盖增强算法进行比较。实验一中给出了算法的收敛性能和覆盖增强效果，实验二验证了部署的节点个数和覆盖增强效果间的关系。

实验1：为了便于比较，采用与文献 [9] 相似的实验环境，监测区域为长宽均为500 m的平面区域，150个节点随机部署在监测区域内。节点的感知范围半径R为50 m，视场角大小为 $2\alpha ={90}^{\circ }$，最大迭代次数 $MaxIT$ 为1000。根据多次实验效果，本文算法中的惯性因子的最大值和最小值 $w_{\max }$ 和 $w_{\min }$ 分别取0.9和0.1，学习因子 $c_{1\max }=c_{2\max }=3$， $c_{1\min }=c_{2\min }=1$。

覆盖效果如图2所示，图2(a)为初始网络覆盖效果，图2(b)为文献 [9] 中算法的最终覆盖效果，图2(c)为本文算法的最终覆盖效果，图中覆盖到的区域采用灰色表示，颜色越深，该区域被覆盖的重数越高，可以看出，本文算法有被重覆盖的区域较少，即一重覆盖的区域较大，因而有较高的覆盖率。

图3给出了随着迭代次数增强，两种算法网络覆盖率的变化曲线。可以看出，本文算法由于改进了惯性因子和学习因子，使得在算法初期偏向于局部区域的大幅度搜索，对网络覆盖率的提升速度较快，且本文算法收敛速度快，在迭代515次后收敛，覆盖率为0.543；而文献 [9] 中的算法在迭代753次后收敛，覆盖率为0.532。而在算法后期本文算法减慢搜索速度，使得算法能收敛于全局最优，因而最终本文算法的覆盖率较高。

实验2：在实验一其他参数不变的条件下，使部署的节点的个数N从50变化到250，两种算法的覆盖率和收敛的迭代次数情况如表1所示。可以看出，在N较小的条件下，由于网络的多重覆盖情况较少，两种算法的覆盖率相似；在N越大时，多重覆盖的区域面积越大，本算法的收敛速度优势越明显，覆盖率也更高。

(a) (b) (c)

Figure 2. Coverage results. (a) Original distribution; (b) Coverage result of [9]; (c) Result of proposed method

图2. 覆盖效果图。(a) 初始覆盖效果；(b) 文献 [9] 覆盖效果；(c) 本文算法覆盖效果

Figure 3. Curves between coverage rate and iteration time

图3. 网络覆盖率随迭代次数变化曲线

Table 1. Coverage rate and convergent time with different number of nodes

表1. 不同节点数时覆盖率和收敛时间比较

5. 结论

粒子群算法具有适于解决连续空间多维函数优化问题，能快速收敛至全局最优解的特点。本文将微粒群智能优化方法应用到有向传感器网络的覆盖优化中，通过改进惯性因子和学习因子，使得算法在初期在较大幅度内搜索，并倾向节点的局部最优，算法的收敛速度较快；算法在后期在小范围内搜索，并倾向于全局最优，使得算法的覆盖率较高。实验验证了本算法收敛速度快、覆盖率高，在节点数目较多时，算法性能提升更明显。

基金项目

国家自然科学基金项目资助项目(61662049, 61763033)。