三维无线多媒体传感器网络全目标覆盖算法

王艳娇，毕晓君，滕志军，邬春明

（1.东北电力大学 信息工程学院，吉林省 吉林市132012；2.哈尔滨工程大学 信息与通信工程学院，哈尔滨150001）

0 引 言

随着无线多媒体传感器网络（Wireless multimedia sensor networks，WMSNs）研究的深入和实际应用的扩展［1－3］，为增强相应覆盖控制算法的实用性和有效性［4－5］，一些学者致力于构建能够描述无线多媒体传感器节点真实感知能力的感知模型。Ma等［6］于2005 年首先设计了基于节点坐标、感知半径、感知方向和感知角度的扇形感知模型，此后，Makhoul等［7－8］先后提出三角形和凸多边形感知模型。其中，扇形感知模型能够较好地描述节点感知性能并且最为简单，是目前最具代表性、应用最多的一种感知模型，但是这些二维有向感知模型由于受到空间局限性以及与真实三维环境之间存在本质差别等因素的影响，无法准确描述节点的空间感知能力，使得基于此展开的覆盖控制方法与实际应用之间存在不小的技术偏差。基于此，某些研究者试图建立面向真实环境的更为准确的三维有向感知模型，如：Ma等［9］于2009年首次提出基于传感器节点位置、主感知方向、水平方向感知范围和垂直方向感知范围的多媒体传感器节点三维感知模型；文献［10］对上述模型进行改进，将主感知方向正交分解为仰俯角和偏向角，大幅降低了计算复杂度。

上述三维有向感知模型虽已具备一定的空间刻画能力，但是其空间覆盖区域与传感器的高度无关，且当其处于某些主感知方向时在二维平面内的覆盖区域没有边界限制，不符合人们的主观认知，此外，无法适应实际三维物理环境的不规则表面覆盖等问题，还不能准确描述节点的感知性能。为此，本文提出一种新的三维有向感知模型。在此基础上，针对典型目标覆盖问题［11］，即求出覆盖全部目标所需的最小传感器数目，设计了一种基于仰俯角优化和偏向角优化的新型目标覆盖算法。仿真结果表明：对比随机部署的方法，本文方法所需的传感器数目大幅下降且比较稳定。

1 新型三维有向感知模型

多媒体传感器节点处于三维物理场景，节点仅能覆盖球形区域的一部分。本文受传统传感器节点的三维模型建立方式（即将二维平面内的圆节点模型旋转拓展至空间得到球形三维感知模型）的启发［12］，将多媒体传感器感知模型中应用最广的扇形模型绕节点旋转一定角度构建新型多媒体传感器三维有向感知模型，具体定义如下：

定义1 多媒体传感器三维有向感知模型可用一个五元数组（P，C，α，β，R）表示，其中，C 为主感知方向（与Z 轴夹角称为仰俯角γ，在X－Y 平面投影为偏向角θ），2α、2β和R 分别为水平感知角度（水平视域）、垂直方向感知角度（垂直视域）和感知半径。

为充分理解本文所提三维有向感知模型的定义，这里给出其具体描述如图1所示。

图1 新的三维感知模型Fig.1 Novel three－dimensional directional perception model

由上述模型可见，其在二维平面内的最大覆盖 范 围 为 距 点P′（P 在X－Y 平 面 内 投 影）以内，且随着传感器被放置高度的增加，覆盖范围逐渐减小，符合人们的主观认知，充分克服了现有两种三维有向感知模型的缺陷，能够更加真实地描述节点感知能力。

2 面向新型三维有向感知模型的目标覆盖问题

定义2 本文研究的目标覆盖问题是指，为实现对二维平面内存在的N 个目标的全面有效监测，在三维场景中随机布撒M 个参数完全相同的传感器，求出覆盖所有目标需要开启工作的最少传感器数目。

对应于本文提出的三维有向感知模型，影响节点覆盖能力的可控变量为主感知方向，那么相应的目标覆盖算法就是求解包含仰俯角和偏向角的 一 个 最 优 组 合［（γ1，θ1），（γ2，θ2），…，（γM，θM）］，在覆盖所有目标的同时，所用变量数目最少。

为了便于数学分析，这里给出其相应的数学定义，具体如下：

式中：S′为所选的传感器集合；A 和S 分别为目标集合和传感器集合；a为某目标；xijk为传感器i工作在仰俯角j 和偏向角k 的主感知方向上。约束条件保证所有目标都被覆盖以及每个传感器至多工作在一个方向上。

确定目标是否被节点覆盖是从数学上解决覆盖问题的关键，为此，这里需明确本文提出的三维有向感知模型的目标覆盖条件。

按照该模型的定义，其在水平监测区域的投影相当于一个扇形绕顶点旋转后的横截面，具体如图2所示。

图2 三维有向感知模型的横截面图Fig.2 Cross－sectional figure of novel three－dimensional directional perception model

受到α和β 的限制，不同的仰俯角只会获得如图2所示的图形中的一部分，通过推导发现水平监测区域会出现如图3所示的6种投影图形。

图3中γ1和γ2分别对应于如图4所示的两种临界状态，满足如下关系：

限于篇幅，这里仅以最为复杂的投影图形（图3（e））为例说明目标节点的覆盖判别方法。为便于分析说明，给出图3（e）相应的空间位置分布，如图5所示。其中，∠P′PO3＝γ＋β、PP′＝z、∠P′PO1＝β－γ、PD4＝PD6＝R、∠D1PO1＝∠N2PP′＝∠D4PO2＝∠D6PO3＝α。

判断目标是否被节点覆盖的方法如下：在满足式（2）的基础上，位于D5D3N1N2D4D6内部（即在有向线段D5D6的右侧、有向线段N1D3右侧、N1N2左侧及N2D4左侧），或处于四边形D1D2N1N2内（在有向线段D1D2右侧、D2N1右侧、N1N2右侧及N2D1右侧）。

图3 水平投影情况Fig.3 Horizontal projection situation

图4 临界条件示例Fig.4 Critical condition

图5 图3（e）的空间信息Fig.5 Spatial information of Fig.3（e）

以判断目标T（X′，Y′）在有向线段D5D6左侧或右侧为例说明判别上述位置关系的实施方法，具体如下：目标T 关于P′的相对坐标为T′（X′－x，Y′－y）＝T′（x0，y0），D5、D6的坐标分别记为（xD5，yD5）、（xD6，yD6）。若D1＞0，在有向线段D5D6的右侧；否则在该有向线段左侧。其中，A1＝yD6－yD5、B1＝xD5－xD6、C1＝xD6yD5－xD5yD6、D1＝A1x0＋B1y0－C1。

为实施上述目标覆盖方案，必须明确图5中处于二维平面内的相应各点坐标，具体如下：

其中：

3 面向新型三维有向感知模型的目标覆盖算法

对于本文设计的多媒体传感器三维感知模型，为实现所有目标的有效覆盖，如果直接同时优化主感知方向中的仰俯角和偏向角，复杂度过高，对算法效率等要求过高，难以求得满意结果。考虑到主感知方向中的仰俯角γ影响其在水平方向的投影覆盖面积，偏向角θ影响其投影图形的朝向。如果调整仰俯角γ保证每个传感器在水平方向的覆盖面积最大，就可以使每个传感器覆盖尽可能多的目标，再综合调整各传感器投影图形的朝向，就可以达到目标覆盖算法的要求，即用尽量少的传感器覆盖所有的目标，复杂度大幅降低。基于上述分析，将目标覆盖算法分成仰俯角优化和偏向角优化两部分。

3.1 仰俯角优化

仰俯角γ的大小决定传感器在水平方向的投影覆盖面积大小，投影覆盖面积越大，传感器所能覆盖的目标就会越多，越有利于用较少的传感器覆盖所有的目标。这里把投影覆盖面积达到最大的仰俯角称为最优仰俯角。

由图3中的三维感知模型的水平投影情况可以看出，当γ2＜2β时，只会出现图3（a）（b）的情况，投影面积最大时对应图3（b）的情况，此时，γ＋β＝γ2，即γ＝γ2－β；而当γ2＞2β时，投影面积最大应出现在图3（d）（e）和（f）中，而图3（d）（f）对应的最佳仰俯角为γ＝γ2－β和γ＝γ1－β，可以看作是图3（e）的边界情况。为此仅计算图3（e）面积即可求出最优仰俯角。

由图3（e）的空间位置关系（见图5）可得到其在二维平面内的投影图形的面积计算公式，具体表述为：

式（3）是非线性的复杂函数，传统数学方法（如梯度下降法、最小二乘法等）很难求得理想结果，进化算法由于不受函数形式限制，越来越多地应用于此类问题的求解。差分进化算法［13］就是该领域最具前沿、最有代表性的算法，大量实验及文献指出该方法的连续函数优化性能已超越现有较为优秀的遗传算法、粒子群算法等，为此，这里采用差分算法求解最优γ使S 最大。

3.2 偏向角优化

经仰俯角优化后，各个传感器节点都具有固定的、最大覆盖面积的投影图形，如果随机获取偏向角，某些节点很可能未覆盖任何目标或者相邻的多个节点覆盖相同目标，造成资源浪费，不符合目标覆盖算法的设计要求。为此，必须优化偏向角调整各节点的投影图形朝向，它的调整受到相邻节点的彼此制约，是一个非常复杂的NP－Hard问题。其数学本质是优化各个传感器节点的偏向角，在这种状态下，挑选其中的kk 个传感器（kk最小）实现覆盖全部目标的目的。鉴于差分进化算法的优化优势，这里也采用该方法优化节点偏向角。该问题与普通优化问题不同的是，其适应度函数不具有明确的数学形式。为此，本文根据实际需求建立如下两种适应度函数求解方式。

方式一：利用进化算法求解。

基于上述分析可知，该问题的适应度为挑选最优的部分传感器实现目标覆盖，可以通过如下方式实现：优化传感器顺序，达到所有目标被完全覆盖的前kk 个传感器就是该问题最终选择的传感器组合，而kk 就是适应度值。这一实现方式本身就是一个组合优化的过程，对于此类问题，现在广泛采用遗传算法（Genetic algorithm，GA）进行求解，鉴于该问题与TSP 问题的本质相似性，对于各种改进GA，这里选用实数编码、交换序交叉操作的遗传算法［14］求取适应度值。

方式二：随机计算。

随机计算的方式如下：设置一定的循环次数，在每次循环中，随机产生一个传感器顺序，从第一个传感器开始，逐个保留使覆盖目标增多的传感器，直至达到所有目标被有效覆盖，参与计算的传感器数目就是该问题的适应度值。

对比两种适应度计算方式可以发现：方式一的结果更为准确，但是计算复杂、耗时长、不适宜大规模问题的求解；方式二的结果虽然不一定是最优的，但是计算简单，适合于大规模问题的求解。因此，在大规模目标覆盖问题的求解中采用方式二计算适应度，而对于小规模目标覆盖问题或对时间要求不高时，选用方式一精确计算适应度值。

3.3 目标覆盖算法

利用优化算法实现面向三维有向感知模型的无线多媒体传感器网络的目标覆盖的步骤具体如下：

步骤1 初始化相关参数：区域边界D；传感器相关参数，包括β、α、γ和θ的取值范围及传感器数目M；目标数目N；种群数目PN；迭代次数Maxiter等。

步骤2 在区域内随机布撒传感器及目标。

步骤3 按3.1节中方法优化各传感器仰俯角，得到最优仰俯角集合｛γ1，γ2，…，γM｝。

步骤4 初始化遗传算法相关参数，产生有关传感器偏向角的初始种群。

步骤5 采用3.2节中方法计算适应度值，即该种已定偏向角配合状态下，达到目标覆盖所需的最少传感器数目。

步骤6 按照DE／current－to－best／1模式以及逐维单点交叉策略进行变异操作和交叉操作，得到新个体。

步骤7 按3.2节计算新个体的适应度值，并将其与原目标个体比较，保留适应度值更优个体。

步骤8 结合全部更优个体形成新的迭代种群。

步骤9 判断是否满足终止条件，若满足，则输出传感器编号及相应仰俯角、偏向角；若不满足，则转至步骤6。

4 算法测试及结果分析

为充分验证本文提出的面向三维感知的无线多媒体传感器网络的目标覆盖算法的有效性和先进性，这里进行了大量实验，所有实验在硬件配置为Intel Centrino Duo，CPU：T7250、1G 内存、主频为2.0 GHz 的计算机上进行，程序采用MATLAB R2007编写。主要包括以下几方面内容：①本文提出的算法能够解决目标覆盖问题；②验证本文所提两阶段目标覆盖方法的有效性；③将本文提出的目标覆盖与其他几种部署方法进行比较，说明本文方法的先进性。

实验场景与文献［10］一致：监测区域为500 m×500m 的矩形区域，传感器参数完全相同，仰俯角，偏向角，水平感知视角和垂直感知视角均为120°，感知半径为100 m，随机布撒传感器节点数目为M，高度信息z∈［5，12］，覆盖N 个目标。

实验一 验证能有效解决目标覆盖问题

不失一般性，这里模拟两个目标覆盖问题，随机布撒参数完全相同的传感器节点和目标，问题一和问题二中传感器数目和目标数目分别为100、10和400、100。这两个问题中传感器和目标位置如图6所示。

图6 传感器节点和目标节点的位置Fig.6 Position of the senor node and the target node

对于上述两个目标覆盖问题，利用本文算法优化后，所调用的传感器在水平面的投影及相应覆盖的目标如图7所示。

图7 本文算法处理目标覆盖问题的效果Fig.7 Effect of the proposed targets coverage algorithm

本文算法参数设置如下：种群数目和迭代次数分别为50 和100，对于小规模目标覆盖问题，即目标数目为10时，选用3.2节中方法一作为适应度计算方式，而对于目标数目为100的大规模覆盖问题，适应度计算方式选为3.2节中方法二。

从图7可以看出：经本文算法调整以后，对于小规模目标覆盖问题，即目标数目为10时，仅用5个传感器就能实现目标覆盖；而对于大规模目标覆盖问题，即目标数为100时，仅需要28个传感器就可实现目标覆盖。

由此可见，本文算法能够解决目标覆盖问题。

实验二 验证两阶段目标覆盖方法的有效性

为验证本文所提分步优化仰俯角和偏向角的目标覆盖策略的有效性，将其与综合调整主感知方向（即同时优化偏向角和仰俯角）的目标覆盖方法进行比较。

固定目标数N 为10、20、30至100的位置，在各目标位置下传感器数目都为200，两种方法都采用3.2节中方法二计算适应度值，其中，综合调整主感知方向的方法是指对俯仰角和偏向角统一进行优化。

鉴于公平性原则，当两种算法处理相同问题时，即传感器数目和目标数目相同时，保持传感器和目标的位置相同，且保证算法的函数评价次数相同，此外，为避免随机性对算法评价造成的不良影响，各算法都独立运行10次。本文算法的参数设置如下：种群数目为50，迭代次数为100。在各种情况下，综合调整主感知方向的方法以及本文所提算法覆盖所有目标所需的传感器节点数目如图8所示。

图8 两种方法的性能比较Fig.8 Comparison of the performance of two methods

从图8可以看出：在覆盖少量目标时（如目标为10和20时），本文采用分别优化仰俯角和偏向角的目标覆盖方法与直接调整主感知方向的方法所需传感器数目相同，而随着目标数目的增多，本文方法所需传感器数目明显减少，且目标数目越多优势越明显。这是由于对于不太复杂的小目标覆盖问题，直接优化主感知方向的方法复杂度不是很高，一般方法尚且能够满足其复杂度要求，可求得较好结果，然而对于复杂情况，该方法的复杂度过高，对算法效率及运行机制要求过高，一般方法很难求得优异结果，而经本文方法简化后，复杂度大幅降低，即可求得更佳结果。

综上所述，对于复杂的目标覆盖问题，与直接优化主感知方向的方法相比，本文所提仰俯角和偏向角分别优化的目标方法更为有效。

实验三 验证本文方法的先进性

鉴于目前并未见到基于三维有向感知模型的目标覆盖算法相关成果发表，这里仅能将本文方法与随机部署方法进行比较，其中，随机部署方法是指俯仰角、偏向角在规定范围内随机变化，在某种部署状态下，覆盖所有目标所需的最少传感器节点数目。为保证对比的全面性和完整性，这里进行复杂度和覆盖效果两方面的对比。对于时间复杂度的比较，限于篇幅，仅统计传感器数目为200，目标数目分别为20、40、60、80及100时的算法运行时间。为对比的公平性，保证两种方法的函数评价次数均为2000，两种方法的时间复杂度比较如表1所示。为充分对比两种算法的覆盖效果，这里进行大量实验，参数设置及实验方式与实验二相同，比较结果如图9所示。

表1 传感器数目为200时两种方法的时间复杂度比较Table 1 Comparison of time complexity of the number of sensors＝200

图9 两种方法的性能比较Fig.9 Comparison of the performance of two methods

由表1中数据可以看出：无论是随机方法还是本文方法，随着目标数目的增多，算法的运行时间都有所增加，这是符合实际情况的。无论对于哪种目标覆盖情况，与随机方法相比，本文方法所需的时间都略长，但相差不大，且目标数目越多，两者之间的差别越少。

由图9可以得到以下结论：①目标数目相同时（见图9（b）），无论是随机部署还是本文所提算法，当传感器数目增加时，所需的传感器数目都会减少，这是因为当传感器部署密度增大时，会使一些传感器的某些方向更加“优秀”，即占据更好的位置，从而能覆盖更多的目标点并使许多边缘目标点集中化；②布撒相同数目传感器节点时（见图9（a）），目标数目越多，达到目标覆盖所需的传感器数目也越多，这与实际情况也是一致的；③无论上述哪种覆盖情况本文方法所需的传感器数目都比随机部署要少，特别地，当目标数目为40、随机抛撒传感器数目为50或60时，随机方法很难实现全目标覆盖，而本文方法可以求得较为满意的结果，且情况越为复杂，本文算法的优越性越明显。

综上所述，与随机部署方法相比，本文建立的基于仰俯角和偏向角优化的两阶段目标覆盖算法所需时间略长，但覆盖效果的优势十分明显。

为进一步验证本文采用差分进化算法对仰俯角和偏向角进行优化的正确性，将其与模拟退火方法、遗传方法以及粒子群算法进行比较。固定目标数N 为25、75和125的位置，在各目标位置下改变传感器数目为150、250和350，模拟不同的目标覆盖问题。具体参数设置及实验方式同上，其性能比较结果（包括算法精度、效率和稳定性）如表2所示。

表2 四种目标覆盖方法的性能比较Table 2 Comparison of performance of four targets coverage algorithms

从表2中数据可以得出以下结论：

（1）在所求解精度方面，当覆盖目标数目较少时（如目标数目为25），本文方法所需传感器数目明显比其他3种方法更少，而随着目标数目的增加，4种方法所用传感器数目相差不大，本文算法所需数目略少，说明本文方法在覆盖效果方面具有一定优势。这是由于在目标数目较少时，本文方法由于自身运行机制较好，能够突破其他几种方法在一定程度上陷入局部最优的僵局、并快速收敛到较优结果，而随着目标数目的增多，问题复杂度急剧增高，对算法要求也越高，几种方法的运行效率都有所下降。

（2）在稳定性方面，本文方法在处理小目标覆盖问题（如目标数目为25）时，算法十分稳定，每次都能取得最优结果，而对于大目标覆盖问题，与其他3种方法的方差相差不大，都较小，说明本文方法相对十分稳定。

（3）在运行效率方面，对于相同的覆盖问题，在相同函数评价次数内，本文方法的运行时间明显小于其他3种方法，说明本文方法在运行效率方面优势明显。

综上所述，与采用其他方法执行进化策略的目标方法相比，本文方法能更为稳定地获得优异结果，且在运行效率方面优势明显，说明了本文选择差分进化算法作为进化策略构建目标覆盖算法的正确性。

5 结束语

鉴于现有的多媒体传感器网络目标覆盖算法都是针对理想的二维感知模型设计的，其理论研究结果与实际应用之间存在较大的技术偏差，本文从实际角度出发，在现有三维感知模型中加入感知范围，提出一种新型三维感知模型，并设计了一种基于仰俯角优化和偏向角优化的目标覆盖算法。实验仿真结果表明，与随机部署方法相比，本文方法能够用更少的有向传感器节点实现所有目标的覆盖。由此可见，本文提出的目标覆盖算法能够有效解决目标覆盖问题，具有一定的工程应用前景。

［1］Khuntia P，Pattnaik P K.Target coverge management protocol for wireless sensor network［J］.Journal of Theoretical and Applied Technology，2012，35（1）：20－25.

［2］Yang L，Xin H.Research on key technologies to target coverage algorithm in wireless sensor networks［J］.International Journal of Digital Content Technology and its Applications，2012，6（17）：542－550.

［3］凡高娟，孙丽娟，王汝传，等.距离辅助的无线传感器网络节点覆盖判别模型［J］.通信学报，2010，31（8）：127－133.Fan Gao－juan，Sun Li－juan，Wang Ru－chuan，et al.Distance－assistant node coverage identification model for wireless sensor networks［J］.Journal on Communications，2010，31（8）：127－133.

［4］Wang X，Ma J J，Wang S.Distributed energy optimization for target trackong in wireless sensor networks［J］.IEEE Transactions on Mobile Computing，2009，9（1）：73－86.

［5］Ai C，Santosh K，Ten H L.Local barrier coverage in wireless sensor networks［J］.IEEE Transactions on Mobile Computing，2010，10（4）：491－504.

［6］Ma Hua－dong，Liu Yong－he.Correlation based video processing in video sensor networks［C］∥2005International Conference on Wireless Networks，Communications and Mobile Computing，New York，USA，2005：987－992.

［7］Makhoul A，Saadi R，Pham C.Coverage and adaptive scheduling algorithms for criticality management on video wireless sensor networks［C］∥The 4th ACM Int＇l Workshop on Performance Monitoring，Measurement，and Evaluation of Heterogeneous Wireless and Wired Networks，St.Petersburg，2009：54－60.

［8］Adriaens J，Megerian S，Potkonjak M.Optimal worst－case coverage of directional field－of－view sensor networks［C］∥Proc of the 3rd Annual IEEE Conf on Sensor，Mesh and ad hoc Communications and Network，Reston，VA，2006：336－345.

［9］Ma H D，Zhang X，Ming A L.A coverage－enhancing method for 3Ddirectional sensor networks［C］∥Proceeding of 28th IEEE Conference on Computer Communications IEEE INFOCOM 2009，Washington，2009：2791－2795.

［10］肖甫，王汝传，孙丽娟，等.一种面向三维感知的无线多媒体传感器网络覆盖增强算法［J］.电子学报，2012，40（1）：167－172.Xiao Fu，Wang Ru－chuan，Sun Li－juan et al.Coverage－enhancing algorithm for wireless multi－media sensor networks based on three－dimensional perception［J］.Acta Electronica Sinica，2012，40（1）：167－172.

［11］Jian W，Changyong N，Ruimin S.Priority－based target coverage in directional sensor networks using agenetic algorithm［J］.Computers and Mathematics with Applications，2009，57（1）：1915－1922.

［12］任秀丽，程艳蕾，徐泽明.无线传感器网中三维覆盖控制和节点调度的研究［J］.小型微型计算机系统，2012，33（8）：1681－1684.Ren Xiu－li，Cheng Yan－lei，Xu Ze－ming.Coverage control and node－scheduling for three－dimensional wireless sensor networks［J］.Journal of Chines Computer Systems，2012，33（8）：1681－1684.

［13］Tatih T M，Bulut O，Quan P，et al.A differential evolution algorithm for median cycle problem［C］∥2011 IEEE Symposium on Differential Evolution（SDE），Paris，France，2011：1－7.

［14］Herera F，Lozano M.Gradual distributed real－coded genetic algorithms［J］.IEEE Transaction on Evolutionary Computation，2000，4（1）：43－63.