0 引言

随着微电子制造业技术的发展，由大量不同的具有感知能力、计算能力和通信能力的微型传感器节点组成的无线传感器网络(Wireless Sensor Network, WSN)技术也迅速发展^[1]。WSN在军事领域、民用领域的应用非常广泛，比如环境监测、工业监测、战场监测、智能家居和医疗监测等^[2-3]。覆盖问题是所有传感器网络的基本问题，反映出无线传感器网络的服务质量^[4]，体现了无线传感器网络的性能。在工作环境比较复杂的区域，无线传感器网络大多采用随机部署传感器节点的方式进行网络的初始部署，这样就会产生大量的节点覆盖重叠区域和盲区，导致网络的覆盖率偏低。此外，由于传感器节点的体积较小、电池不易更换等特点，导致传感器节点的能量非常有限^[5]。因此，如何通过提高网络的覆盖率来提高节点能量的利用率就显得尤为重要。

异构传感器网络的异构性分为节点异构、链路异构和网络协议异构三个方面，其中节点异构对网络的覆盖控制影响最大。节点的异构又可以分为通信能力、感知能力、计算能力等方面的异构。目前，有很多学者已经对有向传感器网络、异构传感器网络和三维平面上的传感器网络的覆盖性能进行了研究。文献[6]在传感器网络的覆盖控制增强问题中，首次引入了虚拟势场的方法来解决问题；文献[7]通过自主调节技术，对网络的覆盖问题进行了优化；文献[8]通过引入质心的概念，提出了基于虚拟势场的有向传感器网络覆盖优化算法(virtual field based coverage algorithm for directional sensor network, PCAFD)，对有向传感器网络节点的往复运动、覆盖盲区和重叠区进行了优化；文献[9]在分析节点主感知方向可调模型的基础上，设计微粒适应值函数和种群进化策略，提出覆盖优化算法提高了有向传感器网络的覆盖率；文献[10]基于邻居节点运动构建有向强栅栏模型，提出覆盖优化算法提高了有向传感器网络的覆盖率。文献[11]改进了虚拟力算法，而且加入了计算几何，提出了一种虚拟力的异构节点网络覆盖增强算法；文献[1]受简单随机抽样理论和最优化算法的启发，提出了一种异构无线传感器网络的覆盖优化算法，大幅度提高了网络覆盖程度；文献[12]在异构无线传感器网络中引入超级节点和普通节点的概念，对普通节点进行状态轮转的覆盖控制算法，提高了网络的覆盖率和连通率；文献[5]在三维空间下，考虑最优覆盖节点集和低能耗，提出了一种三维传感器网络低能耗覆盖算法；文献[13]提出了三维传感器节点的感知模型，在三维空间中结合空间几何理论对网络的覆盖问题进行了研究；文献[14]构建节点三维感知模型，通过调节主感知方向，提出了面向三维感知的多媒体传感器网络覆盖增强算法(Three-Dimensional Perception Based Coverage-Enhancing Algorithm, TDPCA)；文献[15]结合概率和网络最坏覆盖的K覆盖方法来提高网络覆盖率。以上方法，有的只是在二维平面上针对有向传感器网络，或者是针对异构传感器网络进行覆盖控制研究；还有只是针对三维空间上的全向感知的传感器网络进行网络覆盖率的研究。针对三维空间的有向异构传感器网络的覆盖问题进行的研究很少。而事实上，随机部署的传感器节点处于现实的三维空间中，传统算法很难实现网络覆盖率的提高。

本文针对面向三维的节点感知半径异构的有向异构传感器网络节点随机部署时产生的覆盖重叠和覆盖盲区问题，提出了基于粒子群优化算法面向三维的有向异构传感器网络覆盖优化算法(Particle Swarm Optimization based coverage optimization algorithm for Three-Dimensional directional Heterogeneous network, PSOTDH)，通过粒子群优化算法对面向三维的有向异构传感器网络进行三维覆盖重叠区域优化和边界节点优化处理，提高网络的覆盖率。

1 三维有向感知模型及覆盖问题描述 1.1 三维有向感知模型

二维有向感知模型^[7]是一个扇形的感知区域，以节点位置为扇形的圆心，以感知半径为扇形的半径。它能通过调节扇形区域的主感知方向，使感知区域覆盖到不同的地方。

与二维有向感知模型不同，三维有向感知模型^[16]是由传感器节点的空间坐标、感知半径、传感器视角方向向量的水平方向向量及垂直方向向量组成的圆锥体区域。它能通过调节圆锥体区域的主感知方向，使感知区域绕圆锥区域的顶点切换到不同的方向。三维有向感知模型可以用一个五元组(M_i(x_i, y_i, z_i), B_i(t), α, θ_i, R_i)来表示(如图 1)，其中：M_i(x_i, y_i, z_i)为节点的空间坐标，也就是圆锥区域的顶点；单位向量B_i(t)表示传感器节点t时刻的有向感知方向；α表示传感器节点的感知夹角，大小为方向向量B_i(t)在xoy面上的垂线的夹角；θ_i表示有向传感器节点的感知方向，大小为B_i1(t)与x轴正向的夹角(如图 2)；R_i表示传感器节点的感知半径，也就是圆锥区域的母线长度。特别地，S_i(x_s, y_s, z_s)为圆锥区域底面圆圆心的空间坐标。三维全向感知模型是三维有向感知模型的一个特例，当α=π时，三维有向感知模型就变成了一个三维全向感知模型。

半径异构的有向异构传感器网络满足半径相同的三维有向感知模型，只是有向异构传感器网络节点的感知半径R_i不是一个确定的值。

1.2 三维有向异构传感器网络覆盖问题描述

在对本文的面向三维的有向异构传感器网络覆盖问题进行研究之前，为了研究方便，首先作如下假设：

1)本文研究的为半径不同的有向异构传感器网络节点，但有向异构传感器网络节点满足三维有向感知模型；

2)有向异构传感器网络节点初始部署采用随机部署，且节点一旦初始部署完成节点的位置固定不变；

3)节点可以获取自身的位置坐标和感知方向等信息；

4)节点可以通过绕自身转动的方式来改变节点的主感知方向。

如果有向异构传感器网络节点满足以上假设，在三维空间区域U中随机部署N个有向异构传感器网络节点，节点集可以表示为M_i={M₁, M₂, …, M_N}。当一个传感器节点i正常工作时，传感器网络的覆盖区域为$ {V_i} = \frac{1}{3}{A_i}{H_i} $，其中，A_i为圆锥体的底面积，H_i为圆锥体的高。当N个传感器节点正常工作时，传感器网络的覆盖区域为$ \mathop \cup \limits_{i = 1}^N {V_i} $，则面向三维的有向异构传感器网络的覆盖率可以表示为：

$ {P_1}\left( {{V_i}} \right) = \left( {\bigcup\limits_{i = 1}^N {{V_i}} } \right)/{V_U} \times 100\% $

(1)

由于三维空间的网络覆盖率计算比较复杂，实现难度大。本文把网络覆盖率的计算简化为：在x、y、z三个方向上等间隔地选取离散点，从而将上文提到的面向三维的有向异构传感器网络的覆盖率简化为离散点的计算模型，由此，可以得到简化的面向三维的有向异构传感器网络覆盖率的定义为：

定义1  在三维空间区域U中，随机部署N个正常工作的有向异构传感器网络节点，三维空间区域U中离散的点集合为Ω，任意一个节点i覆盖区域的点集合为Ω_ai，N个节点覆盖区域的点集合为Ω_a。那么，简化的面向三维的有向异构传感器网络的覆盖率P₂(V_i)为N个节点覆盖区域的点集合与三维空间区域U中离散的点集合的比值，即：

$ {\Omega _a} = \bigcup\limits_{1 \leqslant i \leqslant N} {{\Omega _{ai}}} $

(2)

$ {P_2}\left( {{V_i}} \right) = \left\| {{\Omega _a}} \right\|/\left\| \Omega \right\| \times 100\% $

(3)

其中:(B₁(t), B₂(t), …, B_i(t), B_N(t))为N个节点的感知方向组成的一个感知方向向量组。提高网络的覆盖率就是找到一组N个节点感知方向的向量组(B₁(t), B₂(t), …, B_i(t), B_N(t))，使N个节点覆盖区域的点集合为Ω_a最大，进而使函数P₂(V_i)达到最大值。

2 PSOTDH

在三维空间中随机部署有向异构传感器节点后，传感器节点的位置就固定不变，只能通过改变节点的主感知方向来提高网络的覆盖性能。而且，初始部署以后产生了大量的三维覆盖重叠区域和三维边界节点，这就导致了网络的覆盖率偏低。此外，大多二维平面的覆盖优化算法在三维空间中对网络覆盖性能的优化效果不好。

因此，针对以上问题，把网络覆盖率作为优化函数，在三维有向感知模型中引入三维重叠质心、三维有效质心和三维边界质心的概念，通过粒子群优化算法对三维重叠覆盖区域、三维有效覆盖区域和三维边界节点的分布进行优化，以提高面向三维的有向异构传感器网络的覆盖率。

2.1 重叠覆盖区域优化

为了研究方便，本文作以下定义：

定义2  在三维研究区域U中，异构节点i和j的距离为：

$ dis = \sqrt {{{\left( {{x_i} - {x_j}} \right)}^2} + {{\left( {{y_i} - {y_j}} \right)}^2} + {{\left( {{z_i} - {z_j}} \right)}^2}} $

定义3  两个异构节点之间，仅考虑通信距离，若两个异构节点i和j的距离小于2R_i(R_i≤R_j，R_i、R_j分别为节点i和j的感知半径)时，则两个节点是可以相互通信的，称节点i和j为互为异构邻居节点。

定义4  若节点i和j为互为异构邻居节点，那么节点i的三维覆盖区域为Ω_ai和节点j的三维覆盖区域为Ω_aj的交集为两个节点的三维重叠覆盖区域，即Ω_ai∩Ω_aj。其中，把节点的三维重叠覆盖区域的质心称为三维重叠质心。

定义5  若节点i和j为互为异构邻居节点，节点i三维覆盖区域的集合去掉节点的三维重叠覆盖区域，就称为节点i的三维有效覆盖区域，即$ {\Omega _{ai}} - \mathop \cap \limits_{j = 1,j \ne i}^N {\Omega _{ai}} $。其中，把节点i的三维有效覆盖区域的质心称为三维有效质心。

如图 3，节点i和j为互为异构邻居节点。不同的研究区域有不同的质心，则异构节点i的三维有效覆盖区域为Ω_ai1，异构节点j的三维有效覆盖区域为Ω_aj1；异构节点i和j的三维重叠覆盖区域为Ω_aij。则节点i的三维有效质心为O(Ω_ai1)，三维重叠质心为O(Ω_aij)。

在三维空间U中，指定的质心是离散分布的。其中，指定的质心的坐标O(x, y, z)可以通过离散方法求得，公式如下：

$ O\left( {x,y,z} \right) = O\left( {\frac{1}{{num}}\sum\limits_{i = 1}^{num} {{x_{_i}}} ,\frac{1}{{num}}\sum\limits_{i = 1}^{num} {{y_{_i}}} ,\frac{1}{{num}}\sum\limits_{i = 1}^{num} {{z_{_i}}} } \right) $

(4)

其中：x_i为离散的粒子的x轴坐标；y_i为离散的粒子的y轴坐标；z_i为离散的粒子的z轴坐标；num为离散的粒子数目。

通过粒子群优化算法优化三维重叠质心和三维有效质心的分布，使三维重叠质心和三维有效质心分布更加均匀，以达到提高网络覆盖率的作用。设初始随机部署N个有向异构传感器网络节点，产生了m个三维重叠质心或者三维有效质心，m个三维重叠质心粒子或者三维有效质心粒子组成了一个群体。各个三维重叠质心或者三维有效质心在三维空间中的坐标可以表示为M_i(M_i1, M_i2, …, M_id, M_iD)(D=3)。三维重叠质心或者三维有效质心i(i=1, 2, …, m)的速度表示为ν_i=(ν_i1, ν_i2, …, ν_id, ν_iD)(D=3)。在每次优化迭代中，三维重叠质心或者三维有效质心通式(5)、(6)来更新位置和速度：

$ {v_{id}} = \omega {v_{id}} + {c_1}{r_1}\left( {{p_{bestid}} - {M_{id}}} \right) + {c_2}{r_2}\left( {{g_{bestid}} - {M_{id}}} \right) $

(5)

$ {M_{id}} = {M_{id}} + {v_{id}} $

(6)

其中:p_bestid为个体i此时的最优解；g_bestid为整个种群找到的最优解；ω为惯性权重，通常取ω=1；c₁和c₂为学习因子，通常取c₁=c₂=2；r₁和r₂取值为^[0,1]范围内的随机数。

2.2 边界节点优化

在三维区域U中，初始随机部署完成以后，普遍会产生一些到边界的距离小于感知半径的节点，这些节点就被称为三维边界节点。三维边界节点大部分的覆盖区域在研究区域的边界以外，因此三维边界节点的存在导致了网络的覆盖率偏低，尤其是在有向异构传感器网络中，三维边界节点的半径可能会很大，这样就造成了网络资源的极大浪费。针对以上问题，PSOTDH提出了面向三维的有向异构传感器网络三维边界节点优化方法，以解决三维边界节点带来的覆盖问题。

图 4为三维边界区域示意图。节点i为三维边界节点，三维边界节点的覆盖区域分为两个部分：三维边界区域Ω_ai1和三维有效覆盖区域Ω_ai2。其中，三维边界区域的质心称为三维边界质心，如图 4中O(Ω_ai1)；O(Ω_ai2)则为三维有效质心。

类比2.1节提出的三维重叠区域优化分析，通过粒子群优化算法对三维边界质心和三维有效质心的分布进行优化，使三维边界质心分布到边界以内，且使三维边界质心和三维有效质心的分布更加均匀，提高网络的覆盖率。此外，三维边界节点优化以后，不再参加其他优化。设l个三维边界质心粒子或者三维有效质心粒子组成了一个群体，各个三维边界质心或者三维有效质心在三维空间中的坐标可以表示为M_i(M_i1, M_i2, …, M_id, M_iD)(D=3)。三维边界质心或者三维有效质心i(i=1, 2, …, l)的速度表示为ν_i=(ν_i1, ν_i2, …, ν_id, ν_iD)(D=3)。在每次优化迭代中，三维边界质心或者三维有效质心通过式(5)、(6)来更新位置和速度。

2.3 PSOTDH描述

PSOTDH主要包括两个部分：三维重叠区域优化和三维边界节点优化。其具体描述如下。

输入：面向三维的有向异构传感器网络节点的个数、位置坐标信息、半径信息、感知方向信息和感知夹角信息。

输出：各个面向三维的有向异构传感器网络节点最后的感知方向。

1)  初始化面向三维的有向异构传感器网络，设置优化次数t=0，获取节点M_i(x_i, y_i, z_i)的位置坐标信息、半径信息、感知方向信息和感知夹角信息，计算网络的初始覆盖率P₀；

2)  规定PSOTDH算法的循环次数T；

3)  While(t < T)

4)  for i=1:N

5)    if(节点M_i是三维边界节点)

6)      初始化三维边界节点的三维边界质心和三维有效质心的最优适应值p_bestid=P₀；

7)      初始化全局的最优适应值g_bestid=P₀；

8)      初始化三维边界节点感知角度的调节速度；

9)       While(节点M_i是三维边界节点)

10)         根据式(5)、(6)对三维边界节点的覆盖区域的三边界区域和三维有效覆盖区域进行优化，获取p_bestid和g_bestid；

11)         调整三维边界节点的主感知方向；

12)      end；

13)      end；

14)     if(节点M_i与异构邻居节点之间存在三维覆盖重叠区域)

15)      初始化节点M_i与异构邻居节点的三维重叠质心和三维有效质心的最优适应值p_bestid=P₀；

16)      初始化全局的最优适应值g_bestid=P₀；

17)      初始化节点M_i与异构邻居节点的感知角度的调节速度；

18)      While(节点M_i与异构邻居节点之间存在三维覆盖重叠区域)

19)         根据式(5)、(6)对节点M_i与异构邻居节点的三维重叠区域和三维有效覆盖区域进行优化，获取p_bestid和g_bestid；

20)         调整节点M_i与异构邻居节点的主感知方向；

21)      end；

22)    end；

23)    获取面向三维的有向异构节点M_i以及邻居节点的位置、感知方向相关信息；

24)    t←t+1；

25)  end；

3 仿真结果与分析

在Matlab R2012a环境中，对面向三维的有向异构传感器网络节点的覆盖进行优化仿真。仿真参数设定如表 1所示。

在Matlab R2012a中，根据表 1进行仿真，得到面向三维的有向异构传感器网络70个节点的初始覆盖图，如图 5所示，以及网络的初始覆盖率P₀=41.13%。如图 6所示，经过PSOTDH算法1次优化以后，网络的覆盖率提高到P₁=47.25%；经过PSOTDH算法5次优化以后，网络的覆盖率提高到P₅=53.89%；经过PSOTDH算法10次优化以后，网络的覆盖率提高到P₁₀=61.43%；经过PSOTDH算法25次优化以后，网络的覆盖率提高到P₂₅=68.95%。从初始覆盖率P₀=41.13%，经过1次优化后覆盖率提高幅度为6.12%，优化效果很明显。分别经过5次、10次、25次优化以后，提高幅度分别为12.76%、20.30%、27.82%。随优化次数的增加，覆盖率的提高幅度变缓。25次迭代以后，有向异构传感器网络的覆盖率提高了27.82%，覆盖达到最优。

如图 6所示，经过PSOTDH算法的25次优化以后，面向三维的有向异构传感器网络的覆盖率得到了大幅度的提升。特别是前15次优化以后，网络的覆盖率就达到了65.83%，提升幅度达到了24.70%，说明PSOTDH算法的优化速度很快。而且从第15次优化以后，网络覆盖率的提升变缓，但依然有缓慢的提升，说明PSOTDH算法具有良好的收敛性。

在表 1参数情况下将本文的算法PSOTDH和以前研究中提出的算法PCAFD^[8]、TDPCA^[14]进行性能的对比。从图 6中可以清楚地看出，本文提出的PSOTDH算法在第一次优化就可以大幅度地提高面向三维的有向异构传感器网络的覆盖率，而且整个过程的优化效果比PCAFD、TDPCA算法的优化效果要好。

在规定的三维研究区域随机部署50、70、90、110个无线传感器节点，感知半径R_i为[50,80 ]范围内30、50、70、90个随机数，其他仿真参数仍如表 1所示，可以得到不同传感器个数下，经过三种算法PCAFD、 TDPCA、PSOTDH各25次优化以后网络的传感器数目对覆盖率的影响，如图 7所示。从图 7可以看出，无论传感器个数部署的多少，经过25次优化以后，算法PSOTDH对面向三维的有向异构传感器网络的覆盖问题的优化效果都要好于其他两种算法。

通过对三种算法PCAFD、 TDPCA、PSOTDH的仿真结果的对比，能够看出本文提出的PSOTDH能够大幅地提高面向三维的有向异构无线传感器网络覆盖率，而且具有良好的优化速度和收敛性。

4 结语

本文针对面向三维的有向异构传感器网络随机部署节点后产生的覆盖重叠区和盲区问题，受到粒子群优化算法的启发，在建立新的三维有向感知模型的基础上，引入三维重叠质心、三维有效质心和三维边界质心的概念，提出了基于粒子群优化算法面向三维的有向异构传感器网络覆盖优化算法PSOTDH；然后通过Matlab仿真验证了算法的有效性，与PCAFD和TDPCA的对比显示，本文提出的PSOTDH，能够大幅度提高面向三维的有向异构无线传感器网络覆盖率，而且具有良好的优化速度和收敛性。本文没有考虑覆盖区域里有障碍物的情况，但是在现实生活中面向三维的有向异构传感器往往部署在具有障碍物的环境中，后期工作中将进一步对此进行讨论和研究。