﻿ 基于垂直采样的水下三维传感网覆盖算法
 计算机系统应用  2019, Vol. 28 Issue (2): 125-131 PDF

1. 西安理工大学 计算机科学与工程学院, 西安 710048;
2. 西安理工大学 自动化与信息工程学院, 西安 710048

Underwater 3D Sensor Network Coverage Algorithm Based on Vertical Sampling
ZHANG Tong1, MA Xin-Yuan2, ZHAO Tai-Fei2
1. Faculty of Computer Science and Engineering, Xi’an University of Technology, Xi’an 710048, China;
2. Faculty of Automation and Information Engineering, Xi’an University of Technology, Xi’an 710048, China
Foundation item: Scientific Research Program of Education Bureau, Shaaxi Province (17-JF024); Hydraulic Science and Technology Program, Shaaxi Province (2016s1kj-30)
Abstract: In order to solve the problem of low coverage rate when nodes are deployed randomly in underwater three-dimensional (3D) sensor networks, an underwater 3D sensor network coverage algorithm based on vertical sampling is designed to improve the coverage and connectivity of underwater 3D sensor network. The coverage algorithm of underwater 3D sensor network based on vertical sampling firstly samples the 3D monitoring area in vertical plane, and then samples the plane in a straight line, which transforms the coverage problem of 3D space into the optimal problem of linear coverage. From the local to the whole, the goal of optimizing the coverage of the whole 3D network is achieved. The simulation results show that in the 100 m×100 m×100 m 3D monitoring area, the vertical sampling algorithm can increase the coverage by about 4%~28% compared with the 3D random deployment strategy, and the maximum degree of increase is obtained when the number of nodes is 40.
Key words: water environment     sensor network     coverage algorithm     vertical sampling     network coverage

1 垂直采样算法网络模型

 图 1 三维水下传感网模型

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

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

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

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

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

 图 2 三维空间传感器节点分布示意图

 图 3 三维空间垂直采样示意图

 ${r_i} = \sqrt {{R^2} - {{\left( {{y_0} - {y_i}} \right)}^2}}$ (1)
 图 4 垂直平面覆盖示意图

 图 5 感知圆球与采样平面相交示意图

 图 6 感知圆与采样直线相交示意图

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

(1)优化后感知圆可将采样直线完全覆盖. 如果优化后n个感知圆可将直线MN覆盖完全, 即感知圆与采样直线相交所得的线段集合的并集包含采样直线的线段集合X={0≤x≤l}, l是矩形监测区域的长度. 如果优化后直线l可被感知圆完全覆盖, 则每个感知圆si与直线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)

 $\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 算法描述

4 算法仿真与性能分析

 图 7 覆盖率与采样步长的关系

 图 8 覆盖率与节点个数的关系

 图 9 UVS算法与CTDA算法对比

 图 10 感知半径不同时覆盖率与迭代次数的关系

 图 11 节点数不同时覆盖率与迭代次数的关系

 图 12 节点平均移动距离与迭代次数的关系

5 结束语

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

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

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

 [1] 李岩. 我国的水环境现状研究. 科技风, 2016(18): 139. [2] 杜晓玉. 面向水环境监测的传感网覆盖算法研究[博士学位论文]. 南京: 南京邮电大学大学, 2015. [3] Karjee J, Jamadagni HS. Information estimation with node placement strategy in 3D wireless sensor networks. IETE Journal of Research, 2017, 63(4): 523-535. DOI:10.1080/03772063.2017.1299044 [4] Kim D, Cano JC, Wang W, et al. Underwater wireless sensor networks. International Journal of Distributed Sensor Networks, 2014, 2014: 860813. [5] Yick J, Mukherjee B, Ghosal D. Wireless sensor network survey. Computer Networks, 2008, 52(12): 2292-2330. DOI:10.1016/j.comnet.2008.04.002 [6] Huang CF, Tseng YC. The coverage problem in a wireless sensor network. Mobile Networks and Applications, 2005, 10(4): 519-528. DOI:10.1007/s11036-005-1564-y [7] 刘丽萍, 王智, 孙优贤. 无线传感器网络部署及其覆盖问题研究. 电子与信息学报, 2006, 28(9): 1752-1757. [8] 任丰原, 黄海宁, 林闯. 无线传感器网络. 软件学报, 2003, 14(7): 1282-1291. [9] 李世伟, 王文敬, 张聚伟. 基于潜艇深度的水下传感器网络部署. 传感技术学报, 2012, 25(11): 1613-1617. DOI:10.3969/j.issn.1004-1699.2012.011.026 [10] Zou Y, Chakrabarty K. Sensor deployment and target localization based on virtual forces. IEEE INFOCOM 2003. Twenty-Second Annual Joint Conference of the IEEE Computer and Communications Societies. San Francisco, CA, USA, 2003, 1293-1303. [11] 黄俊杰, 孙力娟, 王汝传, 等. 三维水下传感器网络覆盖优化算法. 南京邮电大学学报(自然科学版), 2013, 33(5): 69-74. [12] 杜晓玉, 孙力娟, 郭剑, 等. 异构无线传感器网络覆盖优化算法. 电子与信息学报, 2014, 36(3): 696-702. [13] 王兴民. 水下传感器网络覆盖控制算法研究[硕士学位论文]. 杭州: 杭州电子科技大学, 2015. [14] 王雪, 王晟, 马俊杰. 无线传感网络布局的虚拟力导向微粒群优化策略. 电子学报, 2007, 35(11): 2038-2042. DOI:10.3321/j.issn:0372-2112.2007.11.002 [15] 李享, 李轩涯. 基于虚拟力的三维部署技术研究. 科学技术与工程, 2013, 13(9): 2412-2420. DOI:10.3969/j.issn.1671-1815.2013.09.020 [16] Detweiler C, Doniec M, Vasilescu I, et al. Autonomous depth adjustment for underwater sensor networks: Design and applications. IEEE/ASME Transactions on Mechatronics, 2012, 17(1): 16-24. DOI:10.1109/TMECH.2011.2175003 [17] 郭忠文, 罗汉江, 洪锋, 等. 水下无线传感器网络的研究进展. 计算机研究与发展, 2010, 47(3): 377-389.