0 概述

无线传感器网络(Wireless Sensor Network, WSN)为环境信息的实时采集、传输与处理提供解决方案, 而传感器节点的部署是WSN的基本问题之一^[1-3]。环境监测应用可以划分为2类^[4]:异常事件监测和连续采样监测。异常事件监测, 即传感器监测目的是探测环境区域内异常事件发生的类型以及时空信息, 如地震、森林火灾等; 连续采样监测, 即对区域内环境数据的连续采样以体现区域内环境变化的趋势, 需要满足区域的高覆盖率, 且重点区域需要多重覆盖以提高采样精度, 本文所讨论的环境监测也属于此类。

国内外学者就节点的部署问题展开了相关研究。文献[5]将节点部署问题转化为粒子寻优过程, 但存在迭代过慢或粒子陷入局部解的问题。文献[6-7]以最大化网络覆盖率为目标, 通过对人工蜂群算法进行改进, 使算法具有较快的寻优速度和摆脱局部最优的能力。文献[8]通过引入物理学中的势场力, 认为节点间存在一种作用力, 以力的平衡位置作为节点的最优位置, 该方法迭代速度快, 但覆盖结果并不乐观, 需要结合其他算法进一步改进。文献[9]则将虚拟力算法和智能群算法相结合, 以虚拟力算法进行节点初次部署, 利用果蝇算法进行重部署加以优化, 取得了一定的效果。上述研究均在节点部署应用中取得了不同进展, 但以上算法的应用模型均为传统的二值感知模型或者概率感知模型, 没有考虑到节点感知区域边缘的模糊感知特性, 并且算法均把监测区域视为均匀区域, 没有考虑到目标区域中需要重点监测的区域。而在实际应用中, 环境区域中各个位置所需的监测力度、覆盖程度也因地理因素存在差异性。此外, 文献[10]针对无线Mesh网络骨干节点部署问题提出一种优化算法, 但没有考虑节点之间的干扰及无线网络的可靠性。

针对上述问题, 本文采用模糊感知模型替代传统的概率模型, 以提高对覆盖点的判断准确性, 同时对区域内各点的重要程度进行空间分权, 引入权重描述感知力度。在此基础上, 根据模型特性研究粒子迭代过程中的飞行趋势, 结合权重引力改进粒子更新方程, 利用模糊感知优化评价函数, 提出一种改进的粒子群算法, 以期在减少迭代次数的同时, 提高算法寻优效果和对重点区域的监测能力。

1 模型描述 1.1 基本假设

为保证本文算法能够适用于一般性节点部署, 作以下假设:

1) 假设待监测区域是一个二维平面, 将其抽象为矩形区域。

2) 假设所有的感知节点都是静态的, 在执行算法后一次性部署在区域内。

3) 假设所有的节点软硬件同构, 其通信半径为感知半径的2倍^[11]。

1.2 网格划分

区域网格化是无线传感网络节点部署中常见的一种方法, 其将目标区域按照一定的粒度(m、n等分)划分成若干边长一致的网格, 即将区域离散为一系列的网格点, 用网格点映射局部区域, 根据区域地理特性映射网格点权重, 即将每个网格点Q_i定义为三元组(x_i, y_i, p_i), 其中, p_i表示该网格点映射的空间权重, 由网格点地理特性决定, 其值越大, 代表该点在监测区域中的重要性越强。

显然, 环境监测中的不同区域监测力度、节点的覆盖度都因地理特性存在差异性, 某些环境污染重点区域应具有较大的权重, 而环境参数变化细微的区域应具有较小的权重。空间权重在另一意义上可以抽象为算法空间域中对飞行粒子的引力。

1.3 模糊感知模型

在现有研究中, 众多学者对感知节点感知模型使用最多的是二值感知模型, 也有学者对二值模型进行改进, 建立概率感知模型, 利用联合概率判断节点覆盖情况, 但可靠性低。目前这两种模型均无法准确描述节点的实际感知性能。节点的感知能力受多因素影响, 并无一般规律可循, 通常只有强弱之分, 在一定程度上表现出模糊性。

文献[12]建立一种有向传感器模糊感知模型, 将节点感知角度内的区域分为确定感知区域和模糊感知区域, 同时给出了节点数据融合规则, 具有一定的参考价值, 而本文所涉及的传感器均为全向型传感器。因此, 本文在该模型的基础上通过逆推法将传统的概率模型转化为感知节点的模糊模型, 再通过解模糊规则进行确定性覆盖判断。

环境监测区域中的N个感知节点可以表示为S={S₁, S₂, …, S_N}, 任意感知节点S_j位置可以表示为(x_j, y_j), 目标监测点Q_i其位置可以表示为(x_i, y_i)。

定义1  d(Q_i, S_j)为节点S_j与网格点Q_i间的欧几里得距离, 表示如下:

$ d\left(Q_{i}, S_{j}\right)=\sqrt{\left(x_{i}-x_{j}\right)^{2}+\left(y_{i}-y_{j}\right)^{2}} $

(1)

定义2 节点感知概率:

$ P\left( {{Q_i},{S_j}} \right) = \left\{ \begin{array}{l} 1,d\left( {{Q_i},{S_j}} \right) \le {R_{\rm{s}}}\\ {{\rm{e}}^{ - \lambda \left( {d\left( {{Q_i},{S_j}} \right) - {R_{\rm{s}}} + {R_{\rm{e}}}} \right)\beta }},\left| {d\left( {{Q_i},{S_j}} \right) - {R_{\rm{s}}}} \right| \le {R_{\rm{e}}}\\ 0,d\left( {{Q_i},{S_j}} \right) > {R_{\rm{s}}} + {R_{\rm{e}}} \end{array} \right. $

(2)

其中, λ、β为感知概率系数, R_s为感知节点的确定感知半径, R_e为模糊感知范围, 节点模糊感知示意图如图 1所示。

对概率模型进行逆推, 得到节点的模糊距离判断式:

$ {D_i}\left( P \right) = - \frac{{\ln P}}{{\lambda \beta }} + {R_{\rm{s}}} - {R_{\rm{e}}} $

(3)

结合模糊距离判断式对节点模糊感知范围进行模糊化, 映射7种不同的感知模糊等级, 如表 1所示。

1.4 覆盖率模型

模糊感知模型将节点对网格点的感知能力进行模糊化, 但算法计算覆盖率时需要准确的网格点覆盖情况, 因此, 当网格点处于多个节点的模糊区域内时, 对该点进行解模糊处理是有必要的, 且直接关系到算法的运行结果。

定义3 (模糊集) 当网格点Q有几率被节点S_i感知到, 就认为Q与S_i互为邻居节点。根据模糊规则, 统计出网格点Q的模糊集, 记作L(l₁, l₂, …, l_k)。

定义4 (模糊频次集) 根据模糊集L统计出各感知强度的出现次数, 记作N{n₁, n₂, …, n₇}, 其中$\sum\limits_{i=1}^{7} n_{i}=k$。

定义5 (影响度集)  在网格点覆盖情况判定时, 模糊化的多种感知强度在多种程度上影响最终判定结果, 此处定义了7种感知强度的影响权重集, 记作C(c₁, c₂, …, c₇), 其中c₁→∞, c₇=0。

定义6 (覆盖力度) 根据模糊频次集和影响度集计算网格点Q_i的覆盖力度:

$ H_{\mathrm{Q}}=\left|N \cdot \boldsymbol{C}^{\mathrm{T}}\right|=\sqrt{\sum\limits_{i=1}^{7}\left(n_{i} \cdot c_{i}\right)^{2}} \cdot \sqrt{a^{2}+b^{2}} $

(4)

定义7 (确定性覆盖点)  如果感知网内某网格点Q_i的覆盖力度高于临界覆盖力度H_c, 则称该网格点为确定性覆盖点。

解模糊规则即是利用模糊感知模型求得模糊频次集, 计算出网格点覆盖力度, 通过该值大小对该点覆盖情况进行精准判定。

在当前节点部署研究中, 算法评价函数使用最多的还是区域覆盖率, 并没有考虑到重点区域的优先覆盖和k覆盖问题, 本文研究在保证区域覆盖率的同时, 同样关注于重点区域的覆盖情况。因此, 引入加权覆盖率作为本文算法的目标函数, 定义如下:

定义8 (加权覆盖率)  区域网格点权重覆盖率和区域面积覆盖率的加权和:

$ \begin{array}{l} \theta = {\lambda _1} \cdot {f_1} + {\lambda _2} \cdot {f_2} = + \\ \;\;\;\;\;\;{\lambda _1} \cdot \frac{{\sum\limits_{k = 1}^{(m + 1)(n + 1)} {{u_k}} \cdot {p_k}}}{{\sum\limits_{i = 1}^{(m + 1)(n + 1)} {{p_i}} }} + {\lambda _2} \cdot \frac{{\bigcup\limits_{i = 1}^N {{S_i}} }}{S} \end{array} $

(5)

在式(5)中:f₁表示区域权重占比; f₂表示区域面积占比; $u_{k} \subset U\left\{u_{1}, u_{2}, \cdots, u_{(m+1)(n+1)}\right\}$, u_k=1表示Q_k为确定性覆盖点, 否则u_k=0;S表示区域总面积; S_i表示单节点覆盖面积; λ₁和λ₂为权重系数, 两者之和为1。

就加权覆盖率而言:区域网格点权重覆盖率是区域内网格点权重在总权重中的占比, 由于高权重网格点对整体覆盖率的贡献大, 因此在该模型上, 算法更易于优先覆盖高权重点, 以保证重点区域的k覆盖; 区域面积覆盖率的计算是为了防止重点区域内节点的过度冗余减小整体覆盖面积, 其中, 权重系数的选取对算法结果产生一定的影响。

2 节点部署策略

文献[13]证明了本文研究的这一类节点部署问题是NP问题。粒子群算法最早用于解决这一类问题, 其基本核心是利用群体中的个体对信息的共享从而使得整个群体的运动在问题求解空间中产生从无序到有序的演化过程, 但该算法存在2个问题^[2]:迭代过慢和局部早熟。

本文在基于空间权重和模糊感知的优化模型基础上, 研究粒子飞行过程中的一般规律, 利用空间权重优化粒子更新方程, 通过模糊感知优化评价函数, 加快算法收敛速度并使算法具有摆脱局部最优的能力。

2.1 PSO节点部署策略

文献[2]证明了当通信半径大于等于2倍的感知半径时, 满足节点的覆盖即可保证节点的连通, 所以, 在感知节点覆盖中考虑节点的覆盖问题即可保证节点的连通性。

假设群体中有a个粒子X={x₁, x₂, …, x_a}, 粒子群在b维的解空间内飞行, 并通过覆盖率进化函数进行进化以寻找最优位置。其中某一粒子i的位置X_i=(x_i1, x_i2, …, x_ib), 其速度V_i=(V_i1, V_i2, …, V_ib), 该粒子经过的最优位置为P_gi, 种群经过的最优位置P_q, 且全局共享。

单粒子i局部最优位置P_gi更新方程为:

$ P_{gi}^k = \left\{ \begin{array}{l} P_{gi}^{k - 1},\theta \left( {X_i^k} \right) \le \theta \left( {P_g^{k - 1}} \right)\\ X_i^k,\theta \left( {X_i^k} \right) > \theta \left( {P_g^{k - 1}} \right) \end{array} \right. $

(6)

粒子群全局最优位置为:

$ {P_q} = \arg \max \left\{ {\theta \left( {P_{g0}^k} \right),\theta \left( {P_{g1}^k} \right), \cdots ,\theta \left( {P_{ga}^k} \right)} \right\} $

(7)

在迭代过程中, 粒子通过式(6)和式(7)不断更新局部最优解和全局最优解, 并以此为依据更新自身飞行的速度和位置。

$ V_{id}^{k + 1} = wV_{id}^k + {c_1}{r_1}\left( {P_{gd}^k - X_{id}^k} \right) + {c_2}{r_2}\left( {P_{qd}^k - X_{id}^k} \right) $

(8)

$ X_{i d}^{k+1}=X_{i d}^{k}+V_{i d}^{k+1} $

(9)

在式(8)中:c₁和c₂为认知因子和社会因子, 用于调节最大搜索步长; r₁和r₂是区间[0, 1]内的随机数; w为惯性权重, 代表粒子飞行的惯性力; w的大小体现出粒子运动的随机性, 较大的惯性力能够加强粒子的搜索精度, 而较小的惯性力能够加快粒子搜索速度。为了更好地平衡两者, 本文使用递减式对w进行动态调整, 调整规则如下:

$ w(k)=w_{\max }-\left(w_{\max }-w_{\min }\right) \cdot \frac{k}{r u n_{\max }} $

(10)

在式(10)中:w_max和w_min分别为最大、最小惯性权重; k为当前迭代次数; run_max为最大迭代次数。文献[14]证明了最大惯性权重、最小惯性权重分别取0.9、0.4时, 算法性能较好。

2.2 算法优化

上述标准粒子群算法在解决节点部署这一类问题中具有通用性, 但粒子飞行的方向感较弱, 导致算法迭代过慢。本文在引入空间权重和模糊感知对模型进行优化后, 利用该模型特性, 挖掘出粒子飞行的一般性规律。

由于空间权重对加权覆盖率的增益不同, 在另一个意义上, 空间权重体现了解空间内对飞行粒子的引力, 即粒子在飞行过程中总是优先覆盖空间权重较大的点。同时高权重点的引力有助于粒子摆脱局部最优的困境, 有益于算法快速收敛。下文基于这一理论对标准粒子群算法进行改进。

对于群体中的某粒子X_i=(x_i1, x_i2, …, x_ib), b=2N, 对其作如下映射:N个节点的横坐标分别对应粒子的前N维, 纵坐标对应粒子的后N维, 即(x_ik, x_i(N+K))代表一个节点位置。同理, 速度V_i=(V_i1, V_i2, …, V_ib)也以此划分。

如图 2所示, 对于N个感知节点, 在每一次的迭代中, 对应其横纵坐标的速度和位置维度都有向高权重网格点靠拢的趋势, 因此, 利用粒子的这一特性结合空间权重优化粒子的速度更新方程来加快算法迭代速度。

每一次迭代, 粒子中每一个感知节点以搜索半径r搜索邻域内的网格点, 搜索方程如下:

$ \left\{\begin{array}{l}{x_{i k}-r<x_{j}<x_{i k}+r} \\ {x_{i(N+k)}-r<y_{j}<x_{i(N+k)}+r} \\ {d_{k j}<r}\end{array}\right. $

(11)

根据邻域内覆盖点的三元组更新节点邻域的权重矩阵P_i^δ和位置矩阵X_i^δ、Y_i^δ:

$ \mathit{\boldsymbol{P}}_i^\delta = \left[ {\begin{array}{*{20}{c}} {{p_{i1}}}&{{p_{i2}}}& \cdots &{{p_{i\delta }}} \end{array}} \right] $

$ \mathit{\boldsymbol{X}}_i^\delta = \left[ {\begin{array}{*{20}{c}} {{x_{i1}}}&{{x_{i2}}}& \cdots &{{x_{i\delta }}} \end{array}} \right] $

$ \mathit{\boldsymbol{Y}}_i^\delta = \left[ {\begin{array}{*{20}{c}} {{y_{i1}}}&{{y_{i2}}}& \cdots &{{y_{i\delta }}} \end{array}} \right] $

其中, p_i1表示第i个感知节点邻域内的第1个网格点权重值, x_i1表示第i个感知节点邻域内的第1个网格点横坐标。

根据式(12)计算邻域内各网格点和感知节点横坐标差量矩阵:

$ \begin{array}{l} \Delta \mathit{\boldsymbol{X}}_i^\delta = \left[ {\begin{array}{*{20}{c}} {\Delta {x_{i1}}}&{\Delta {x_{i2}}}& \cdots &{\Delta {x_{i\delta }}} \end{array}} \right] = \\ \;\;\;\;\;\;\;\;\;\mathit{\boldsymbol{X}}_i^\delta - \left[ {{x_{i1}},{x_{i2}}, \cdots ,{x_{iN}}} \right] \end{array} $

(12)

ΔX_i^δ代表的是节点和网格点的位置关系, 但没有涉及到网格点权重因素, 粒子在飞行中受到的权重引力同时受权重和距离影响。距离越大, 引力的作用相对弱化, 因此, 将横纵坐标差量矩阵ΔX_i^δ和权重矩阵P_i^δ每一个位置上的值作积, 可得感知节点i在空间中受到的横纵引力阵ΔF_ix:

$ \Delta {\mathit{\boldsymbol{F}}_{ix}} = \Delta \mathit{\boldsymbol{X}}_i^\delta \cdot \mathit{\boldsymbol{P}}_i^{\delta {\rm{T}}} = \left[ {\begin{array}{*{20}{c}} {\Delta {x_{i1}}{p_{i1}}}&{\Delta {x_{i2}}{p_{i2}}}& \cdots &{\Delta {x_{i\delta }}{p_{i\delta }}} \end{array}} \right] $

横纵引力矩阵表示节点在解空间中受到的引力, 对每个节点的横纵引力矩阵求和可得到节点x轴合力F_x=(F_x1, F_x2, …, F_xN), y轴合力F_y同理可得。

力的作用最终会导致粒子轨迹的变化, 将该因素考虑进粒子的速度和位置更新方程, 得到改进式如下:

$ \left\{ \begin{array}{l} V_{id}^{k + 1} = wV_{id}^k + {c_1}{r_1}\left( {P_{id}^k - X_{id}^k} \right) + \\ \;\;\;\;\;\;\;\;\;\;{c_2}{r_2}\left( {P_{gd}^k - X_{id}^k} \right) + {c_3}{r_3}F_{ml}^k\\ X_{id}^{k + 1} = X_{id}^k + V_{id}^{k + 1} \end{array} \right. $

(13)

其中, c₃是引力因子, F_ml^k对应于粒子m的位置向量中第l维改进的距离。F_ml^k表达式如下:

$ F_{ml}^k = \left\{ \begin{array}{l} \frac{{{F_{xl}}}}{{\sqrt {F_{xl}^2 + F_{yl}^2} }}{D_{{\rm{step}}}},1 \le l \le N\\ \frac{{{F_{y\left( {1 - N} \right)}}}}{{\sqrt {F_{x\left( {l - N} \right)}^2 + F_{y\left( {l - N} \right)}^2} }}{D_{{\rm{step}}}},N + 1 \le l \le 2N \end{array} \right. $

(14)

其中, D_step是每次迭代粒子受引力影响移动的最大步长, 最大步长的引入是为了调节引力带来的粒子位置上变化的灵敏度。

2.3 算法设计

粒子评价函数的好坏直接影响算法性能, 本文将空间权重引入到加权覆盖率中, 保证重点区域的覆盖率, 算法评价函数伪代码如下:

算法1 粒子群算法评价函数

输入 网格划分数m、n, 网格点Q_k三元组(x_k, y_k, p_k), 粒子序号i, 感知节点位置(x_i1, x_i2, …, x_i2N), 确定感知半径R_s, 模糊感知距离R_e, 权重系数λ₁、λ₂

输出 加权覆盖率θ(X_i)

初始化 覆盖总权重P_i, 已覆盖权重P

1.For k=1:(m+1)(n+1)

2.For each front N dimenson j of particle i

3.if d_kj≤R_s

4.存储网格点k的确定性节点j;

5.else if R_s < d_kj < R_s+R_e

6.存储网格点k的模糊节点j;

7.根据式(4)计算感知强度;

8.更新模糊频次集N;

9.end

10.end

11.if网格点k有确定性节点

12.P=P+p_k;

13.else if网格点k有模糊节点

14.根据式(5)计算覆盖力度H_Q;

15.if覆盖力度H_Q>临界覆盖力度H_c

16.P=P+p_k;

17.end

18.end

19.end

20.计算节点的总覆盖区域U{S₁, S₂, …, S_N};

21.根据式(6)计算加权覆盖率θ;

基于空间权重和模糊感知的优化粒子群算法WFSPO伪代码如下:

算法2  WFSPO

输入  感知节点个数N, 邻域搜索半径r, 最大、最小惯性权重w_max、w_min, 感知节点初始位置(x₁, x₂, …, x_2N)

输出 感知节点最优位置(x_q1, x_q2, …, x_q2N)

初始化 迭代次数run_max, 认知因子c₁, 社会因子c₂, 引力因子c₃, 惯性权重w, 粒子个数z, 粒子速度V_max、V_min, 区域范围x_min、x_max、y_min、y_max, 局部最优P_i, 全局最优P_q

1.For k=1:run_max

2.根据式(11)计算惯性权重w;

3.For each particle i

4.For each dimenson j

5.根据式(12)以半径r搜索邻居节点;

6.根据式(13)计算引力阵△F_x、△F_y ;

7.根据式(15)计算引力位移F_ml^k;

8.根据式(14)计算第j维速度向量V_ij和位置向量X_ij;

9.if j < N+1

10.限制节点横坐标边界;

11.else if j>N

12.限制节点纵坐标边界;

13.end

14.限制粒子最大、最小速度;

15.end

16.if θ(X_i)>θ(P_i)

17.更新局部最优位置P_i=X_i;

18.end

19.if θ(X_i)>θ(P_q)

20.更新全局最优位置P_q=X_i;

21.end

22.end

3 算法仿真与性能评价

为验证WFSPO算法性能, 使用Matlab R2014a对WFSPO算法进行仿真模拟与分析。仿真模型环境设置:目标区域100 m×50 m, 网格边长10 m, 网格数目5×10, 感知节点确定感知半径R_s=7.5 m, 模糊感知距离R_e=1.5 m, 感知强度的影响权重集C{16, 8, 6, 4, 3, 2, 0}, 临界覆盖力度H_c=8, 邻域搜索半径r=10 m, 最大、最小惯性权重w_max、w_min为0.9、0.4。WFPSO算法参数c₁=c₂=2, c₃=1.6, 最大步长D_step=1 m, 最大迭代次数run_max=30, 感知节点个数N=24。

3.1 算法参数估计

WFSPO算法在选取粒子评价函数时, 引入了加权覆盖率, 用于调节网格点权重覆盖率和区域面积覆盖率。前者粒子进化时倾向于权重较大的网格点, 而后者粒子更关注区域整体的覆盖情况。而权重参数λ₁、λ₂的选取直接影响算法的最终结果。因此, 本文在保持其余参数恒定的基础上, 分析不同λ₂取值下的区域面积覆盖率情况, 如图 3所示。

由图 3可见, λ₂的增加带来区域面积覆盖率的不断提升, 但当λ₂≥0.4时, 区域覆盖率的提升有限。从模型上看, 这是由于当感知节点覆盖大部分网格点时, 也能覆盖较多区域, 即网格点权重覆盖率在一定程度上也保证了区域面积覆盖率。而文献[15]中重点区域覆盖率权重系数为整体覆盖率权重系数的2倍时, 覆盖效果最优的这一论断也恰好应证了这一现象。结合此, 本文反复对λ₁、λ₂进行估计, 最终选取λ₁=0.6, λ₂=0.4。

粒子群算法的粒子数目直接关系到算法收敛速度, 为确定最佳粒子数, 本文研究粒子数目和与算法达到预期覆盖率时的迭代次数之间的关系。粒子数估计结果如图 4所示, 可以看出, 粒子个数越多, 算法收敛越快, 但当粒子个数过多时, 粒子个数对算法收敛速度的影响减弱。

粒子群算法利用粒子的运动性来搜索空间最优, 过少的粒子会使得粒子方向感减弱, 算法随机性过大, 但由于粒子运动的社会认知、自我认知以及权重引力等因素, 粒子运动存在趋势性, 过大的粒子数对算法的增益有限, 反之带来算法迭代的冗余。综合考虑, 本文确定粒子数为10, 对算法做进一步仿真。

3.2 算法仿真

基于上述算法参数的讨论, 实验对研究的模型和参数进行了仿真验证。显然, 算法的运行结果和空间权重分布, 也就是区域重要程度紧密相关。基于此, 本文给出了3种权重分布情况下的对应仿真结果, 如图 5所示。其中:图 5(a)对应重点区域和非重点区域混杂情况, 即权重表现出随机分布的趋势; 图 5(c)对应中心点重点区域, 即中心点权重普遍大于边界; 图 5(e)对应边界重点区域, 即边界的权值均高于重点区域; 图 5(b)、图 5(d)、图 5(f)分别是对应图 5(a)、图 5(c)、图 5(e)3种权重分布情况的WFSPO算法仿真结果。

从整体来看, WFSPO算法在保证所有节点连通的前提下, 能够覆盖大部分网格点, 且保持较好的区域面积覆盖, 尤其在重点区域的覆盖上有较好的表现。通过对比3种权重分布情况下的仿真结果可以发现, 节点覆盖的过程在受权重引力的作用下, 总有向高权重区域靠拢的趋势, 且在重点区域有一定的覆盖冗余, 而节点的覆盖漏洞往往出现在低权重区域, 这在一定程度上保证了重点区域的k覆盖, 且提高了覆盖的容错率。

3.3 性能分析

为进一步分析算法性能, 本文将标准粒子群优化(Particle Swarm Optimization, PSO)算法、虚拟力(Virtual Force, VF)算法^[8]、外推人工蜂群(Extrapolation Artificial Bee Colony, EABC)算法^[6]和本文WFSPO算法进行仿真对比, 如图 6所示。

图 6结果显示, 本文算法经过63次迭代, 加权覆盖率最终稳定为0.94。就覆盖率而言, 本文算法相比标准粒子群算法提升13%, 相比虚拟力算法提升8%, 相比外推人工蜂群算法提升4%。同时, 从算法收敛速度来看, 本文算法对比PSO、VF、EABC算法, 收敛速度各提升40%、14%、33%。PSO算法未考虑到粒子运动空间中的权重引力, 仅靠粒子的自我认知和社会认知引导粒子进化, 导致算法迭代过慢且难以获得全局最优结果; VF算法迭代快但覆盖效果并不理想; 而EABC算法则是对群智能算法的典型改进, 通过外推方程加快迭代并改善寻优效果, 但未充分挖掘模型中的相关特性, 导致效果并不如本文算法。

表 2给出了在100 m×50 m的区域下, 不同感知节点个数下的各算法运行后的覆盖情况, 其中, f₁代表区域权值覆盖率, f₂代表区域面积覆盖率。显然, 随着节点个数的增加, 区域的覆盖率也随之提高。由表 2可以看出, 本文的WFSPO算法在区域覆盖上的表现均优于其他3种算法, 尤其在重点区域覆盖上, 本文算法考虑到了重点区域的优先覆盖, 能够保持较高的重点区域覆盖率, 且当节点数量越少时, 这种优势越明显。例如, 当N=16时, WFSPO算法的区域权值覆盖率比EABC算法、VF算法、PSO算法平均提高30%左右, 其他3种算法由于没有区分区域重要性, 其在重点区域的覆盖上表现出一定的随机性。

WFSPO算法的优势一部分归功于模型中空间权重这一特性, 本文进一步分析模型的模糊感知特性对算法的增益。从理论上看, 节点的模糊感知特性可以使得处于确定感知范围之外的区域在解模糊后有较大覆盖几率, 即模糊感知特性间接增加了节点感知范围。

通过仿真, 对比传统的二值感知模型、概率模型和本文的模糊感知模型在满足相同区域面积覆盖率的基础上, 所需要的平均感知节点个数, 结果如图 7所示。

可以看出, 同理论分析一致, 在满足相同覆盖水平的基础上, 模糊感知利用自身的模糊特性能够节约13%~15%的节点部署个数。

4 结束语

环境监测WSN节点部署策略是目前的研究热点。本文提出基于空间权重和模糊感知的优化粒子群算法WFSPO, 并在此基础上分析算法参数选择问题。仿真结果表明, 该算法能够充分挖掘模型中粒子飞行的特性, 具有较好的寻优能力, 其在保证节点连通性的同时可保持较高的区域覆盖率。下一步将研究节点感知路径中的能量消耗问题, 并且考虑重点区域的k覆盖问题, 根据区域的重要程度改变区域的覆盖范围。