引言

水环境对于人类来说较为恶劣, 很难通过传统的人工部署方式在水域中进行大规模的资源勘测和开发等活动, 依靠技术手段来对水环境进行探索这一方式已达成普遍共识^[1,2]. 因此, 水下无线传感网的研究成为目前的研究热点之一^[3]. 水下传感器网络在水质监测、地理信息采集、灾难预防、军事领域应用等方面均具有广泛的应用前景^[4–9].

覆盖问题是研究无线传感器网络的基本问题. 近年来, 国内外有很多比较成熟的覆盖算法. Zou Y等人^[10]最先提出了一种集群分布式的虚拟力覆盖算法和一种新的概率目标定位算法, 用于提高传感器节点初始部署后的覆盖率. 黄俊杰等人^[11]提出三维水下传感网络覆盖优化算法, 利用虚拟力覆盖算法消除网络中的覆盖重叠区和覆盖盲区, 进而提高整个区域的覆盖率. 杜晓玉等人^[12]提出了一种基于虚拟势场的定向移动的覆盖优化算法, 该算法对网络中节点位置进行微调, 多次迭代后节点位置达到稳定, 实现网络的优化覆盖. 王兴民等人^[13]提出一种基于连通树的水下传感网覆盖算法, 由汇聚节点开始构建多个连通子树将网络组织成森林保证网络连通, 通过减小每棵子树内父子节点间覆盖冗余以达到提升整个网络覆盖率的目的. 王雪等人^[14]提出一种无线传感网布局的虚拟力导向微粒群算法, 结合虚拟力与微粒群算法的优点, 在提高网络覆盖率的同时减少算法耗时.

现有的文献中对水环境二维传感网覆盖问题研究较多, 对水下三维传感网问题研究较少^[15]. 本文设计一种基于垂直采样的水下三维传感网覆盖算法(Underwater 3D sensor network coverage algorithm based on Vertical Sampling, UVS), 先对三维监测区域进行平面采样, 将三维传感网覆盖问题转化为二维异构传感网覆盖问题, 再对二维平面进行直线采样, 将二维的覆盖问题转化为一维直线的覆盖问题, 目的是在传感器节点耗能最少的情况下将采样直线更多覆盖, 最终达到提升三维区域传感网的覆盖率.

1 垂直采样算法网络模型

网络由3部分构成, 包括水下感知节点、锚和水面通信节点构成, 如图1所示. 网络初始时, 由飞机或船舶将感知节点、锚和通信节点抛洒到监测区域. 抛洒后锚位置固定, 防止传感器因为海水流动和风力因素偏离目标区域, 从而降低目标区域的覆盖率. 由于初始时节点被锚定, 所以假设传感器节点只能在竖直方向上运动, 不能在水平方向上运动. 然后根据部署算法计算出浮标距离传感器节点缆绳的长度, 利用控制电机调节绳索长度, 达到调节传感器节点位置的目的^[16].

由于在水环境中无线电波衰减严重, 采用无线电波通信需要加装很长的接收天线, 并且通信时的能耗非常大, 不适用于水下传感网这种稀疏环境. 如果采用激光通信的方式, 不仅对节点间对准程度要求非常高, 而且水环境的浊度对激光通信的影响也很大. 而声波通信虽然传播速度不及以上两种通信方式, 但是在水中传播的衰减小、传播距离长^[17]. 综上, 考虑到水环境传感网的这种稀疏环境采用声学通信的方式.

该网络具有如下特点:

(1) 网络分为水面通信节点和水下感知节点两部分. 水下感知节点包括浊度传感器、余氯传感器、PH值传感器等, 负责对水质参数进行监测; 水面通信节点负责与基站进行通信; 水下感知节点通过电缆与水面通信节点相连, 并可以进行通信.

(2) 节点抛洒在监测区域后, 感知节点只能在竖直方向上运动, 不能在水平方向上运动.

(3) 传感器节点加速度为零, 即节点运动时做匀速直线运动, 节点到达稳定状态时速度瞬间为零.

(4) 传感器节点同构, 采用布尔感知模型, 节点的通信半径R_c为感知半径R_s的2倍, 每个节点与基站间至少存在一条通信链路.

2 基于采样的三维水下传感网部署算法

三维监测区域传感器节点分布如图2所示, 图中球体为传感器节点的感知范围.

由于对三维空间水平平面采样求解困难, 采用对垂直平面采样的方式进行网络的覆盖优化. 首先对三维监测区域在垂直方向进行平面采样, 如图3所示, 图中圆形为采样平面与感知球体相交得到的截面. 图3(a)中, 矩形EFGH为三维监测区域中与xz轴平行的一个垂直采样平面, 平面方程为y=y₀. 图3(b)中, 矩形EFGH为三维监测区域中与yz轴平行的一个垂直采样平面, 平面方程为x=x₀. 虽然感知球体同构, 但由于球心距采样平面的距离不同, 所以感知球体与采样平面相交的圆的大小不同, 采样截面可以看作平面异构传感网.

如图4所示, 矩形EFGH为三维监测区域中的一个垂直截面. MN为截面中一条平行于z轴的直线. 图中, (s₁, s₂, s₃, …, s_n)是与直线MN相交的n个异构感知圆, 代表n个水下传感器节点. 对应三维空间中感知圆球的圆心坐标为(x_i, y_i, z_i), 如图5所示, 感知圆球与采样平面相交的感知圆的半径为:

$ {r_i} = \sqrt {{R^2} - {{\left( {{y_0} - {y_i}} \right)}^2}} $

(1)

如图6所示, 感知圆与采样直线MN相交的上交点纵坐标为z_ih=z_i+r_i, 下交点的纵坐标为z_il=z_i–r_i. 则感知圆s_i与直线MN的两个交点分别为(x₀, z_il)、(x₀, z_ih), 其中, z_il<z_ih. n个感知圆与采样直线相交所得的交点为(x₀, z_1l), (x₀, z_1h), (x₀, z_2l), (x₀, z_2h), (x₀, z_3l), (x₀, z_3h), …, (x₀, z_nl), (x₀, z_nh). 感知圆与采样直线相交所得的线段可以表示为: Z₁={z/z_1l≤z≤z_1h}, z₂={z|z_2l≤z≤z_2h}, z₃={z|z_3l≤z≤z_3h}…={z|z_nl≤z≤z_nh}.

优化后感知圆与长度为l的采样直线MN相交的线段总长度L可表示为:

$ L = \sum\limits_{i = 1}^n {\left( {{z_{ih}} - {z_{il}}} \right)} $

(2)

感知圆对直线的覆盖需分两种情况讨论: 第一种情况是感知节点移动后, 感知圆可将采样直线完全覆盖, 即L≥l. 第二种情况是感知节点移动后, 感知圆不能将采样直线完全覆盖, 即L≤l.

(1)优化后感知圆可将采样直线完全覆盖. 如果优化后n个感知圆可将直线MN覆盖完全, 即感知圆与采样直线相交所得的线段集合的并集包含采样直线的线段集合X={0≤x≤l}, l是矩形监测区域的长度. 如果优化后直线l可被感知圆完全覆盖, 则每个感知圆s_i与直线l的下交点至少在另一个感知圆上交点的下边, 上交点至少在另一个感知圆下交点的上边. 式(3)为约束条件:

$ \left\{ \begin{array}{l} \min \left( {{z_{1l}} + \Delta {d_1},{z_{2l}} + \Delta {d_2}, \ldots ,{z_{nl}} + \Delta {d_n}} \right) < 0\\ {z_{2l}} + \Delta {d_2} < {z_{1h}} + \Delta {d_1}\\ {z_{3l}} + \Delta {d_3} < \max ({z_{1h}} + \Delta {d_1},{z_{2h}} + \Delta {d_2})\\ \;\;\;\;\;\;\;\;\;\; \vdots \\ {z_{nl}} + \Delta {d_n} < \max \left( {{z_{1h}} + \Delta {d_1},{z_{2h}} + \Delta {d_2}, \cdots ,{z_{(n - 1)h}} + \Delta {d_{n - 1}}} \right)\\ \max \left( {{z_{1h}} + \Delta {d_1},{z_{2h}} + \Delta {d_2}, \cdots ,{z_{nh}} + \Delta {d_n}} \right) > l \end{array} \right. $

(3)

其中, △d_i表示第i个传感器移动的距离, l为矩形区域的长度. 由于式(3)为非线性二次规划, 求解困难, 为方便求解, 依据感知圆位置顺序不变时, 对采样直线l完全覆盖所需移动距离之和小于改变顺序时移动的距离之和, 将非线性约束条件转化为线性约束条件进行求解.

根据部署算法优化之后, 感知圆可以完全覆盖采样直线, 约束条件转化为任意一个感知圆与采样直线l相交的下交点在上一个感知圆上交点的下边, 任意一个感知圆的上交点在下一个感知圆下交点的上边, 约束条件为:

$ \left\{ \begin{array}{l} \min \displaystyle\sum\limits_{i = 1}^n {\Delta d_i^2} \\ {z_{1l}} + \Delta {d_1} \le 0\\ {z_{2l}} + \Delta {d_2} \le {z_{1h}} + \Delta {d_1}\\ {z_{3l}} + \Delta {d_3} \le {z_{2h}} + \Delta {d_2}\\ \;\;\;\;\;\;\;\;\;\; \vdots \\ {z_{nl}} + \Delta {d_n} \le {z_{(n - 1)h}} + \Delta {d_{n - 1}}\\ {z_{nh}} + \Delta {d_n} \ge l \end{array} \right. $

(4)

(2)优化后感知圆不能将采样直线完全覆盖. 如果优化后n个感知圆不能将直线l覆盖完全, 式(4)无解. 在这种情况下, 当感知圆互不相交时, 感知圆对采样直线的覆盖程度最大, 即任意一个感知圆与采样直线相交的下交点在上一个感知圆上交点的上边, 任意一个感知圆与采样直线相交的上交点在下一个感知圆下交点的下边, 约束条件为:

$ \left\{ \begin{array}{l} \min \displaystyle\sum\limits_{i = 1}^n {\Delta d_i^2} \\ {z_{1l}} + \Delta {d_1} \ge 0\\ {z_{1h}} + \Delta {d_1} \le {z_{2l}} + \Delta {d_2}\\ {z_{2h}} + \Delta {d_2} \le {z_{3l}} + \Delta {d_3}\\ \;\;\;\;\;\;\;\;\;\; \vdots \\ {z_{(n - 1)h}} + \Delta {d_{n - 1}} \le {z_{nl}} + \Delta {d_n}\\ {z_{nh}} + \Delta {d_n} \le l \end{array} \right. $

(5)

3 算法描述

三维水下传感器网络覆盖算法具体描述如下:

步骤1. 设置监测区域范围 $L \times W \times H$ 、传感器节点个数N、感知半径Rs、通信半径Rc、采样次数、最大迭代次数;

步骤2. 初始化网络, 随机部署传感器节;

步骤3. 对垂直平面进行平面采样, 依此判断每个感知圆球与采样平面是否相交, 如果相交, 则根据式(1)计算感知圆球与采样平面相交形成圆的圆心位置和圆的半径, 并保存;

步骤4. 判断感知圆与采样直线相交的线段总和和L与采样直线长度l的大小关系, 若L≥l, 则根据式(4)计算新的节点移动位置, 若L<l, 则根据式(5)计算新的节点移动位置;

步骤5. 循环迭代, 当达到最大迭代次数时跳到步骤6, 否则跳到步骤3;

步骤6. 算法结束.

4 算法仿真与性能分析

为了验证基于采样的水下三维传感网覆盖算法的有效性, 在MATLAB环境下对垂直采样算法进行仿真. 在 $100\;{\rm{m}} \times 100\;{\rm{m}} \times 100\;{\rm{m}}$ 的三维监测区域随即部署若干传感器节点, 取节点感知半径R_s为30 m, 应用基于垂直采样的水下三维传感网覆盖算法对传感器网络进行优化部署.

图7为节点数不同时覆盖率与采样步长的关系. 当采样步长选取较小时, 相邻两个采样平面、采样直线之间的距离较小, 优化结果会互相影响, 这样不仅会增加算法的运算量, 而且对覆盖率还会造成负影响. 当采样步长选取过大时, 无法对整个监测区域的覆盖情况进行优化, 同样覆盖率不能得到有效的提高. 综合这两方面的因素考虑, 选取采样步长为10米.

图8为感知节点数不同时, 随机部署与迭代两次的UVS算法的网络覆盖率的比较. 从图中可以看出在节点数相同时, UVS算法可以显著地提高网络覆盖率.

图9为UVS算法与基于连通树的深度调节(Conected Tree Depth Adjust, CTDA)算法^[13]进行比较. UVS算法与CTDA算法模型相同, 均为在水下三维空间中, 传感器节点仅在垂直方向运动. 其中, 节点数均为50个, 感知半径为30 m. 在迭代次数为3时, UVS算法的网络覆盖率为91%, CTDA算法的网络覆盖率为83%. 从图中可以看出, UVS算法的收敛速度比CTDA算法更快, 并且覆盖程度比CTDA算法更好.

图10为节点感知半径不同时网络覆盖率随迭代次数的变化. 其中, 四条曲线的传感器节点数均为40个, 采样步长为10 m. 考虑到节点的感知半径不定, 如果采样步长也不定将无法对不同半径时的网络覆盖率进行比较, 因此只考虑采样步长为10 m的情况. 在迭代次数为5时, R_s=30的覆盖率为76%, R_s=40的覆盖率为86%, R_s=50的覆盖率为91%, R_s=60的覆盖率为94%. 从图中可以看出, 在迭代次数相同时, 感知半径越大覆盖率越大. 在迭代次数为0到2时, UVS算法对网络覆盖率的提升效果最好, 经过3次迭代之后, 覆盖率只在小幅度范围内变化, 说明算法的收敛速度很快.

图11为节点数不同时时网络覆盖率随迭代次数的变化. 其中, 传感器节点的感知半径为30 m, 采样步长为10 m. 在迭代次数为5时, N=30的覆盖率为77%, N=40的覆盖率为86%, N=50的覆盖率为92%, N=60的覆盖率为96%. 从图中可以看出, 在迭代次数相同时, 节点数量越多网络覆盖率越大. 迭代次数从0增加到2时, 网络覆盖率增长得最快, 随着迭代次数的增加网络覆盖率先快速增长然后趋于平稳, 经过3次迭代网络就已经能到达较好的覆盖率. 当迭代次数大于3时, 覆盖率只在小范围内变化.

图12为节点平均移动距离随迭代次数增长的变化, 算法每迭代一次会更新传感器节点的位置信息, 传感器节点移动到算法每次迭代后优化的位置. 从图中可以看出, 算法前两次迭代节点移动距离较大, 从第三次迭代开始随着迭代次数增加节点移动距离减少, 并且变化不大. 可以看出算法前两次迭代的效果最明显, 说明算法收敛速度很快.

5 结束语

针对水环境传感器节点随机部署时产生覆盖空洞和覆盖冗余并且覆盖率较低的问题, 本文采用一种基于采样的水下三维传感网覆盖算法. 通过对基于垂直采样的水下三维传感网覆盖算法进行仿真, 对节点个数、节点半径与覆盖率的关系进行分析, 得出以下结论:

(1)与随机部署策略相比, 基于采样的水下三维传感 网覆盖算法可以显著提高网络覆盖率. 与CTDA算法相比, UVS算法的收敛速度更快, 并且覆盖程度比CTDA算法更好.

(2)在传感器节点数一定而节点感知半径不同时, 随着迭代次数增加, 网络覆盖率先快速增加然后趋于平稳. 在感知半径不同而节点数相同时, 感知半径越大覆盖率越大. 在迭代次数为0到2时, UVS算法对网络覆盖率的提升效果最好, 经过3次迭代之后, 覆盖率只在小幅度范围内变化, 说明算法的收敛速度很快.

(3)算法前两次迭代节点移动距离较大, 从第三次迭代开始随着迭代次数增加节点移动距离减少, 并且变化不大.

针对水下三维传感网覆盖问题, 设计了基于垂直采样的水下三维传感网覆盖算法, 下一步将考虑降低网络的能耗.