0 引言

    随着半导体技术、微系统技术、通信技术、计算机技术的飞速发展，集感知、存储、通信功能于一体的无线传感器网络技术及相关研究工作在各个国家轰轰烈烈开展起来^[1]。水下传感器网络（Underwater Sensor Networks，USN）作为传感器网络系统中的一个重要领域，广泛应用于海洋资源的勘测、海水污染的监测、海洋数据的收集以及军事领域的水下监视、侦查等方面^[2-3]。

    相较于传统的陆上传感器网络，水下传感器网络有其自身的特性：水下节点较昂贵，大规模密集部署成本过高，决定了水下传感器网络具有稀疏性；水下传感器网络一般通过声学通信，比一般网络功耗更大，更要考虑能耗的均衡性^[4-5]。在充分考虑水下传感器网络特殊性的前提下，如何使用最少的节点满足网络的覆盖率、如何配置节点提高网络的可靠性、防止网络空洞等问题是水下传感器网络的研究热点。

    文献[6]引入刚性理论，定义了节点域的“刚性-覆盖值”作为水下传感器节点所处位置的评价指标，设计了刚性驱动的节点移动策略，从而构建了完整的节点自组织布置方法。Kemal 等^[8]提出了一种用锚链固定在海底可以调节深度的节点构成的水下传感器网络，可以很容易达到部署效果，但在部署过程中节点的能耗较大，不能很好地确保网络寿命。曾斌等^[9]研究了水下传感器节点的布置问题，提出的水下传感器网络移动方案中考虑了水流的作用，不仅达到了较好的部署效果，而且节约了能量。

    上述方法均有一定的局限性，目前部署效率较高的方式均采用确定性部署，但由于特殊环境的不可达性及大规模水下传感器网络的应用需求，人工进行传感器网络的布置难以顺利实现。对于随机性部署，均采用大量布撒节点的方式，并未事先对已知区域进行一系列理论分析，休眠一些节点对于控制网络成本来说，效果仍然不大。目前针对水下传感器网络随机部署后进行优化的问题研究并不多。

    本文针对三维水下传感器网络特性，利用三维空间填充理论模型结合二维空间虚拟力算法，设计了一种基于网格划分和虚拟力的网络部署策略，在满足网络覆盖率的前提下有效地减少了节点的部署数目，降低网络部署成本。

1 背景知识

1.1 三维感知模型

    传感器节点采用布尔感知模型^[11]，感知范围为以节点为球心，r_s为半径的球体(r_s为传感器节点的感知半径)，即节点只覆盖球体范围以内的事件，无法感知球体范围以外的事件。那么，三维空间中位于点(a_i，b_i，c_i)的事件e_i被位于(x_j，y_j，z_j)的节点s_j覆盖的概率如式(1)。

1.2 覆盖效率

    为了衡量节点覆盖范围的利用率，引入网络覆盖效率CE，定义为区域中所有节点的有效覆盖范围的并集与所有节点覆盖范围之和的比值，如式(3)。

其中A_i为节点S_i的覆盖范围。

1.3 三维最优填充

    文献[12]引入了一个度量标准：体积系数（volumetric quotient），其计算公式如式(4)。

    要节点数目最小，在给定感知半径r的情况下，Voronoi单元体积要最大，所以，要找到空间填充多面体，其体积系数最大。

    文献[12]将立方体、六棱柱、菱形十二面体、截角八面体相比较，分别算出其体积系数大小，结果表明，截角八面体的体积系数最大，为0.683 29，所以截角八面体的Voronoi分割部署策略所需的节点数目最少。

    由此可以推断，对于一个m×n×k的三维区域，用覆盖半径为r的传感器节点覆盖，所需最少节点为N=。由于截角八面体的外接球半径为(b为截角八面体各边的边长)，所以

2 算法描述

2.1 基本假设

    为了便于模型的建立和描述，给出以下假设：

    (1)初始状态下，节点随机分布在水面上，忽略水平面的起伏，忽略障碍物影响。

    (2)传感器节点的感知范围为规则球体，通信半径为感知半径的两倍。

    (3)节点间存在虚拟力(引力和斥力)，在力的作用下，节点可相对运动。

    (4)水下传感器节点能够通过缆绳，在垂直方向上准确地移动到指定深度。

2.2 问题描述

    初始状态下，节点由飞机、船舶等设备布撒在观测水域，调整浮标与节点间的缆绳长度来确定节点在垂直方向上的位置，由于初始位置与缆绳长度未知，随机部署的水下传感器网络必然存在覆盖空洞和冗余。需要建立一定的模型，将随机部署的节点通过一定的策略部署到相应位置，实现用更少的节点完成目标水域的全覆盖。

    假定有三维水下目标区域R，传感器节点集合S={s₁，s₂，s₃…s_n}，传感器节点数目为n，传感器节点感知半径为r_s。

    如果对于则目标区域R被节点集合S完全覆盖。

    所以，问题可描述为：设计水下传感器网络部署策略，使得实现目标水域完全覆盖所用的传感器节点数n最少。

2.3 基本思想

2.3.1 网格划分

    由三维空间填充理论可知，三维空间的最优覆盖为体心立方格覆盖，如图1。体心立方格的Voronoi单元为截角八面体, 如图2，其俯视图如图3。将体心立方格覆盖投影到二维平面上，即形成一个正方形网格图，边长为a，节点位于网格的顶点和中心。换个角度，可以观察到一张新的网格图（虚线的网格），边长根据几何关系可知，截角八面体边长为b，截角八面体两个相对的正方形面之间的垂直距离为与最初投影得到的正方形网格边长a相等，由此可得b=截角八面体的外接球半径，即传感半径r_s=则转换而得的新的网格图边长即在已知水下传感器节点感知半径的情况下，进行平面网格划分时，网格边长为

2.3.2 虚拟力算法

    由于水下节点价格昂贵，所以无法随机布撒大量节点，这就导致在网格划分时，网格中节点数目相差过大，会直接影响之后的节点深度部署。

    由此引入虚拟力算法^[12]，节点间存在力的作用（引力和斥力）。当节点间距离很近时，为斥力；当节点间距离过大时，为引力。假设节点间最佳距离为d_opt。按照一定的规则设定节点间力的作用和距离之间的关系，计算节点所受的合力，在合力的作用下节点相对运动，由此可以避免节点部署得过于集中或稀疏。图4为节点受力分析图。

    传统的虚拟力算法运用在二维空间，所以假设节点间的最佳距离即可达到应用要求^[13]。但本文为水下传感器网络部署，要向三维空间扩展，水域的深度不同，水平面上每个网格中所需的节点数目不同。假设水域深度为l，每个网格中所需节点数为l/a，即根据所需节点数目，设置节点间最佳距离。保证网格中的节点数目符合应用要求，且较均衡。

    同一网格中的节点要向水下不同深度部署，引入一个参数w表示网格中所需的节点数目，定义为网格的权重，对于一个p×q的网格区域，生成p行q列的矩阵。可以通过网格权重的变化，得知网格中的节点是否达到应用要求。式(7)即为网格的权重。

2.3.3 节点下降深度计算

    由上文可知，水下传感器网络采用体心立方格形式进行部署，所以网格中的节点分为两种，一种是部署在体心立方格的顶点，一种则部署在体心立方格的中心。网格编号采用(i，j)形式，即(1，1)表示第一行第一个网格，(1，2)表示第一行第二个网格，以此类推，(i，j)表示第i行第j个网格。根据网格编号，将网格进行分类，分为两类，A和B。

    A类(1，1)，(1，3)，(1，5)，…，(2，2)，(2，4)，(2，6)，…，(3，1)，(3，3)，(3，5)，…，即i和j同时为偶数或奇数。B类(1，2)，(1，4)，(1,6)，…，(2，1)，(2，3)，(2，5)，…，(3，2)，(3，4)，(3，6)…，即i和j为一奇一偶。

2.4 算法流程

    (1)目标水域进行网格划分，网格边长设定为将所有网格进行编号。

    (2)节点由飞机、船舶等设备随机布撒到水域平面上以后，运行虚拟力算法，避免节点过于集中或稀疏。

    (4)根据网格编号确定网格类型与网格中节点编号N，由中心实体计算出每个节点下降深度，发送消息给水域所有节点，消息内容包括：网格类型、节点编号、节点下降深度。节点收到消息后，调整自身缆绳长度，部署到相应的水下深度。

3 实验仿真

3.1 网络权重的比较

    图5、图6由网格权重矩阵可以看出，随机布撒的节点分布不均匀，有些区域节点过于密集，有些区域节点未达到应用要求。

    运行虚拟力算法后，随机布撒在水面的节点分散均匀，节点分布图如图7所示，网格的权重矩阵如图8。

3.2 网络覆盖效率的比较

    部署节点数目由120到240（每隔20取一次）。每次部署运行10次仿真，取均值。图9显示了随着节点数目的递增，随机部署策略和本文部署策略的网络覆盖效率变化对比情况。可知在本文的部署策略下，网络的覆盖效率明显高于随机部署，在节点数目在200以上时基本实现全覆盖，而随机部署240个节点时，覆盖效率也仅达到90%，由此可见，本文策略实现了使用较少的节点达到更高的网络覆盖效率。

4 结论

    本文针对三维水下传感器网络的应用要求，提出了一种基于网格划分和虚拟力的网络部署策略。该策略的特点是基于三维空间填充多面体问题，将三维水下传感器网络部署问题简化为二维水平面预部署问题，套用成熟的二维传感器网络部署模型，引入传统的二维传感器网络虚拟力算法，完成水平面传感器节点的预处理。通过控制水平面节点在垂直方向的移动，生成Voronoi分割单元为截角八面体的体心立方格水下监视网络。在实现网络全覆盖的同时，本文部署策略使用的节点数目更少，有效地减少了网络的搭建成本。下一步工作将针对水下传感器网络受水流、水生物影响更易失效的特点，在如何引入移动节点，提高网络的可靠性，防止网络空洞的问题上作进一步研究。

参考文献

[1] 孙利民，李建中.无线传感器网络[M].北京：清华大学出版社，2005.

[2] Li Shiwei，Wang Wenjing，Zhang Juwei.An underwater sensor network deployment algorithm based on submarine depth[J].传感技术学报，2012，25(11)：1613-1617.

[3] MARI C D.Securing underwater wireless communication networks[J].IEEE Wireless Communications，2011：22－28.

[4] ONUR E，ERSOY C，DELIC H，et al.Surveillance wireless sensor networks：Deployment quality analysis[J].IEEE Network，2007，21(6)：48-53.

[5] ONUR E，ERSOY C，DELIC H.Analysis of target detection probability in randomly deployed sensor networks[J].IEEE Communication Letters，2007，11(10)：778-780.

[6] 夏娜，郑语晨，杜华争，等.刚性驱动水下传感器节点自组织布置[J].计算机学报，2013，36(3)：494-505.

[7] ALAM S M，HAAS Z J.Coverage and connectivity in three-dimensional networks[C].Proceedings of the 12th annual international conference on Mobile computing and networking，2006：346-357.

[8] Kemal Akkaya，Andrew Newell．Self-deployment of sensors for maximized coverage in underwater acoustic sensor networks[J]．Computer Communications，2009(32)：1233－1244.

[9] 曾斌，钟德欢，姚路.考虑水流影响的水下传感器网络移动算法研究[J].计算机应用研究，2010，27(10)：3926-3931.

[10] 王长生.水下传感器网络节点布置方法研究[D].合肥：合肥工业大学，2011.

[11] 李世伟，王文敬，张聚伟.基于潜艇深度的水下传感器网络部署[J].传感技术学报，2012，25(11)：1613-1617.

[12] 田一鸣，陆阳，魏臻，等.无线传感器网络虚拟力覆盖控制及节能优化研究[J].电子测量与仪器学报，2009(11)：65-71.

[13] 李享.基于空中传感网的三维部署研究[D].太原：中北大学，2013.