孙爱晶， 王 磊， 朱鑫鑫

(西安邮电大学 通信与信息工程学院，陕西 西安 710121)

0 引 言

无线传感器网络(wireless sensor networks,WSNs)是一种具有自组织性、可靠性、可移动性、节点间可以通信的无线覆盖网络[1,2]。随着对WSNs在不同应用场景的研究，如安防部署问题、森林火灾检测、水下动态检测等三维的环境下，需对二维模型进行扩展从而构建合适的三维模型。文献[3]针对节点冗余、覆盖率等问题，利用改进的人工鱼群算法(artificial fish-swarm algorithm,AFSA)减少寻优时间获得最优部署方案。文献[4]基于虚拟力算法(virtual force algorithm,VFA)考虑多方面受力完善合力解决三维覆盖重部署问题。文献[5]利用传感器节点半径可调性结合VFA有效地实现三维覆盖。文献[6]针对覆盖空洞，基于AFSA提出采用自适应的视野和步长完成空洞修补。文献[7]基于VFA提出一种可变步长的策略优化WSNs节点部署问题。上述研究均有效解决了覆盖问题，但仍在能耗时间、覆盖复杂度等方面存在不足。

本文针对三维WSNs节点部署问题，建立三维覆盖模型，提出一种基于VFA与AFSA的融合算法获得最优部署模型，并有效提升网络覆盖率。通过VFA获得步长因子，再将步长因子添加至AFSA中各行为策略中，起到约束与规范作用，最终实现最优部署模型。

1 三维网络模型与问题模型

1.1 三维网络模型

本文采用二元感知模型[8]，在某个三维传感器场中，将位于(x,y,z)的S点和位于(i,j,k)的P点之间的欧氏距离dij(x,y,z)与传感器监测半径R进行比较。若dij(x,y,z)>R，则格点未被覆盖，表示为0；否则被覆盖，表示为1。

根据覆盖问题，在检测范围中的目标点可被采集信息，而超出覆盖范围将丢失目标点的信息。因此，本文将基于区域覆盖实际问题的统计模型进一步研究AFSA和VFA覆盖算法，提高网络覆盖率。针对三维覆盖问题，将采用以节点位置为圆心、监测半径R的球域覆盖目标区域，并计算出当前的网络覆盖率。

1.2 三维空间覆盖问题描述

在实际应用环境中，对目标区域有效覆盖是实现网络各种功能的前提。针对三维目标区域覆盖问题，由于传感器节点初始部署时会造成节点分布不均，引起覆盖空洞导致通信受阻，难以达到预期的覆盖率。为了达到覆盖要求，需要对传感器网络中存在的覆盖空洞进行修复，即是利用算法进行一次重覆盖的过程，提高网络覆盖率，实现对三维目标区域的有效监测。受到二维平面覆盖网格划分启发，本文将对三维空间监测区域进行离散化处理，使监测区域由若干网格组成，将目标点抽象为网格点，由此将区域覆盖巧妙地转化为网格点覆盖，可视为点覆盖问题来处理，方便了进一步研究。

定义网络覆盖率：在三维目标监测区域中，所有被工作节点覆盖格点数占整个监测区域总格点数的比例视为网络的覆盖率，用Q来表示。

设定一个100 m×100 m×100 m的三维目标区域M，对其进行立方体网格划分，如图1所示。

图1 立方体网格化

1.3 基于三维覆盖模型的假设

给出本文研究三维空间覆盖问题的相关条件设定，具体如下：

1)所有传感器节点为采用二元感知模型的同构节点，均保证相同的感知半径和通信半径，且节点的通信半径为感知半径的2倍。

2)每个传感器节点均可获得自身坐标信息，可实现空间全方位探测，其探测范围是一个以R为半径的球体，且移动节点能量足够支持移动。

3)这里只研究传感器网络应用层的问题，涉及底层的如数据融合、路由通信等均不讨论。

2 基于VFA与AFSA的融合算法描述

2.1 基于三维空间的VFA

VFA是将监测区域中的节点通过引力、斥力作用进行重部署，使得二次部署的节点均匀排布[9]。若两节点之间距离大于某一阈值，通过虚拟引力使两节点靠近；反之，便会产生虚拟斥力使两节点远离，有效提高网络覆盖率[10]。

一般地，VFA多用于二维空间中节点部署，但在实际三维应用场景均匀部署更加迫切，3D-VFA的提出可以有效根据目标区域的不同形态重新部署从而提高区域覆盖率。设用FpA代表优先覆盖区域对一个传感器节点产生的总吸力，用FpR代表障碍物对一个传感器节点产生的总斥力，用Fpq代表传感器节点之间总引力或总斥力，则一个传感节点受到的总合力可以表示为

2.2 基于三维空间的AFSA

每条人工鱼都携带自身数据和拥有执行系列行为的能力，且对外界的感知是依靠视觉来实现的。根据实际环境做出相应决策，如觅食、聚群、追尾等行为，获得最优解[11]。当前人工鱼在下一时刻的行为取决于自身状态和环境状态，并且还通过自身活动来影响环境，进而影响其他人工鱼活动。一般地，以当前网络覆盖率Q的大小作为评价函数对行为评价。1)觅食行为：是鱼寻找食物并移动至目标位置的一种活动，行动的方向通过视觉或味觉来感知水中的食物量或食物浓度来选择行动的方向[12]。2)聚群行为：主要模拟应自然环境生存法则，鱼自然地聚集成群的一种反应行为。在聚群时需遵守一定规则，即向中心位置靠近、避免拥挤、方向一致[12]。3)追尾行为：是指向视野中最佳位置，在寻优算法中可以理解为是向附近的最优伙伴前进的过程，其中，最优是指该人工鱼自身解空间是当前最优部署方案[12]。4)随机行为：是指自由移动扩大范围地寻找食物或其他人工鱼。

在三维空间网络应用中，自身数据即是一组解空间，通过算法的实现寻取最优鱼，即寻求最优覆盖方案。3D-AFSA的实现是通过循环执行这四种行为，并对行为进行评价，最终寻得最优解，即最优部署方案。

2.3 基于三维空间的融合算法

根据2.1节与2.2节对两个算法进行描述，本文将利用两算法各自特点进行融合，解决三维空间覆盖问题。3D-VFA局部优化效果佳、收敛速度快和使节点均匀分布。3D-AFSA虽有着较强的全局优化效果和鲁棒性，但其搜索时间长、受步长影响较大和易出现不精确最优情况位置的缺陷。因此，本文将结合两种算法，形成优势互补，在3D-AFSA中引入步长因子、权重因子和全局最优信息形成3D融合算法，以获取最优部署方案。

2.3.1 计算步长因子

由式(1)可知，三维目标监测区域中每个节点的受力情况。从X轴、Y轴、Z轴三个方向考虑均会受到这些力，接下来从三个方向对力进行分解：

设节点P的邻居节点集合为Si，集合中的传感器节点用si来表示；虚拟力作用下节点可移动最大步长为Maxstep；所受合力方向与X轴夹角为α，所受合力方向与Y轴夹角为β，所受合力方向与Z轴夹角为θ。则传感器节点P所受的合力Fp表示如下

Fp=∑si∈SiFpi

(2)

则可计算节点沿X，Y，Z坐标轴方向的分力大小，以X方向为例

FpX=∑si∈Si(|Fpi|×cosα)

(3)

可计算出节点P在三个坐标轴方向上的移动步长，以X方向为例

通过虚拟力计算后，可获得所有传感器节点的移动步长向量集合，即是步长因子F，表达式如下

F={(π1X,π1Y,π1Z),(π2X,π2Y,π2Z),…,

(πnX,πnY,πnZ)}

(5)

2.3.2 融合步长因子

1)3D融合算法步长改进

算法中步长参数设置影响仿真结果的精确度，对算法的收敛性造成影响。那么具体改进如下

step=Minstep+(Maxstep-Minstep)/Maxstep

(6)

2)3D融合算法行为改进

3D-AFSA应用全局最优解不佳，结合3D-VFA获得步长因子添加至行为移动准则中，并配上权重因子，其中w2为步长因子权重，具体改进如下。

针对随机行为移动准则改进有

针对聚群行为移动准则改进有

w2×F

(8)

针对追尾行为移动准则改进有

w2×F

(9)

2.3.3 3D融合算法流程描述

Step1 鱼群初始化设置。设置人工鱼数量K、传感器节点数N和步长等参数。初始化每条鱼，随机产生人工鱼自身的解空间。

Step2 公告牌设定。计算当前每个个体的自适应度，即网络覆盖率，并将最优覆盖率记录在公告板上。

Step3 根据虚拟力算法计算虚拟力步长因子F，式(5)。

Step4 觅食行为。若目标位置优于当前位置，直接向位置进行移动，否则按式(7)随机移动。

Step5 聚群行为。满足该行为执行需求，按式(8)执行，那么向目标中心位置靠拢；否则返回Step4。

Step6 追尾行为。满足该行为执行需求，按式(9)执行，那么向目标局部最优位置方向移动；否则返回Step4。

Step7 分别计算觅食、聚群和追尾行为网络覆盖率函数值，使用评价函数评比，获得当前状态下的最优鱼位置。

Step8 更新公告牌。本次迭代的网络覆盖率与公告牌的值进行对比、更新。

Step9 终止条件判断。若满足则输出全局最优解，否则返回Step3。

Step10 算法终止，输出最优结果。

3 仿真实验与结果分析

3.1 仿真环境设置

本文利用MATLAB仿真环境下，模拟三维传感器网络的部署优化过程，验证本文所提出的融合算法的优化性能。通过仿真实验若单纯采用随机抛洒方式，则约需要500个传感器节点才能达到98 %的覆盖率。假设在100×100×100的正方体的目标监测区域内随机抛洒60个可移动传感器节点进行部署优化，其中传感器节点半径R为15 m，之间有效的通信距离为2R，分别使用三种算法进行仿真实验。

具体仿真主要参数设置如表1。

表1 主要参数设置表

3.2 仿真结果与分析

在固定的实验环境下，分别使用3D-VFA、3D-AFSA和3D融合算法对三维目标监测区域进行仿真，其结果如图2所示。由图2和图3仿真覆盖结果图来看，3D-VFA、3D-AFSA和融合算法仿真相比初始覆盖率均有效的提升了网络覆盖率。而融合算法的使用，使得节点排布均匀，结合了虚拟力使节点快速均匀分布的优势和鱼群算法全局优化效果佳的优点。从覆盖率数值变化来看，融合算法使得网络覆盖率提高更加明显。

图2 仿真结果

图3 不同算法评估对比

由图3(b)所示，从移动总能量损耗方面对3D融合算法进行评估，3D融合算法能耗相比于其他两个算法位于中间位置，多次试验之后能耗基本在一定内区间内趋于稳定，表明本文3D融合算法稳定性和均衡较好，适用于三维空间覆盖环境。

综合以上多方面分析与对比，本文提出的3D融合算法可以有效提高网络覆盖率，适用于三维空间覆盖优化问题。

4 结 论

本文提出了一种3D融合算法，建立三维覆盖模型，有效提升了三维空间的覆盖率，并且使得最终的传感器节点排布均匀，进一步的提高了网络服务。在今后的工作中，将从节点使用数量和混合网络结构方面考虑问题，把固定节点与可移动节点之间的比例作为一个重要的参考因素，继

续对本文算法及应用模型进一步研究和优化。