第2章 部署技术的发展和评价指标

2.1 发展现状

节点部署是在指定的监测区域内，通过适当的方法部署节点以满足某种特定的需求。节点部署是传感器网络进行工作的第一步，它直接关系到网络监测信息的准确性、完整性和时效性。合理的节点部署不仅可以提高网络的工作效率，也是无线传感器网络研究领域的基本问题之一。目前，关于节点部署的研究中，已经设计出了许多模型和相关算法。这些技术可根据适用环境分为三类：第一类适用于采用确定放置的部署方式；第二类适用于节点不具备移动能力，而且采用随机抛洒的部署方式；第三类适用于节点具备移动能力，采用随机抛洒部署方式。

2.1.1 采用确定放置的部署技术

该技术将监测区域划分为二维或三维网格，并假设传感器节点分布在网格点上，监测目标也出现于网格点上。假设节点的检测模型为0/1模型，即如果节点和网格点间距离不大于检测半径，则节点能感知该网格点，反之，节点无法感知该网格点。如果每个网格点至少被一个节点所覆盖，则网络将覆盖整个监测区域。每个网格点对应一个监测向量，该向量表示该网格点可以被哪些节点感知。如果不同的网格点对应于不同的监测向量，则可根据监测向量对出现在网格点上的目标进行定位。若某个监测向量对应于多个不同的网格点，则网格点间距越小，定位精度越高，在以上模型的基础上，可为每个网格点定义一个取值为0或1的整数变量。若以传感器网络部署的代价为最小优化目标，以每个网格点都至少被一个节点覆盖为约束条件，则可以采用商用整数规划软件求解。若以网络定位精度为最高优化目标，以部署代价为约束条件，则可采用模拟退火算法求解。若假设节点的检测模型为与距离相关的概率检测模型，即节点对网格点的检测概率为e-ad，其中，d代表节点与网格点之间的距离，a反映节点的检测能力。所以d越大，检测概率越小；a越大，节点对网格点的检测能力越弱。如果障碍物出现在节点或网格点之间的连线上，则节点对该网格点的检测概率将降低。另外，每个节点对网格点的检测相互独立。如果每个网格点被检测概率大于指定的阈值，则无线传感器网络的感知范围能覆盖整个检测区域。而且，可将较大的阈值设置到具有较高安全可靠程度的网格点，从而对指定区域进行优先覆盖。在与距离相关的概率检测模型上，一般使用基于贪婪算法的传感器网络部署算法，每次选择一个网格点并在其放置节点，直到满足约束条件。

确定性部署通常应用于网络的状态相对固定或应用环境已知，节点在网络中的位置信息以及节点的密度已知情况下。节点的确定性部署通过对问题进行学抽象，可成为静态优化问题或线性规划问题[1]。在文献［2］中，得出节点部署达到覆盖所需要的最少节点个数并给出了节点相应的位置；在文献［3］中，利用多边形网格来部署节点，以实现最大的连通覆盖。确定性部署能简化问题的解决方案，但在实际的应用中，尤其是大规模、无人监守的恶劣环境中，随机部署显得更具有优势。

2.1.2 采用随机抛洒且节点不具移动能力的部署技术

当监测区域环境恶劣或存在危险时，随机部署是唯一的选择。同样，在大规模应用时，由于节点数量众多、分布密集，采用确定性节点部署技术也不切实际的。此时，可通过飞机、炮弹等载体把节点随机抛撒在监测区域内，节点到达地面以后自组成网。这种随机性主要体现在两个方面[4]：一是节点落在监测区域内的位置具有随机性；二是由于环境的影响，落在区域内的节点状态具有一定的随机性，某些节点可能会在坠落过程中由于损坏而失效。因此，在随机部署策略下，为取得较好的覆盖性能，必须投入大量的冗余节点以达到所需要的节点密度。随机部署方式[5]不能保证部署的节点可以完全覆盖整个监测区域，一般适用于对覆盖要求不太严格的应用环境中。文献［6］采用渐近性分析方法分析了在实际随机部署时带来的问题。文献［7］介绍了三种随机部署模型：简易扩散模型、均匀模型和R-random模型。

2.1.3 采用随机抛洒且节点具移动能力的部署技术

针对区域覆盖的监测应用，基于机器人部署应用中的势场技术，研究人员提出了采用随机抛洒，且节点具备移动能力的部署技术。文献［8］和文献［9］就通过利用节点的有限移动，完成覆盖空洞，达到网络k覆盖的目的。在传感器节点向其他节点移动过程中，把移动节点看成虚拟的带电粒子，假设相邻节点间0点与障碍物之间存在作用力，每个节点根据受力平衡的原理移动一定距离后，平衡态，这时节点能够充分覆盖整个区域。目前，针对该方向已提出一些嵇算法，Zou和Chakrabarty等人提出了VFA算法[10]，其基本思想，一是部署区域中存在障碍物对节点的斥力；二是对覆盖率要求较高的区域产生的引力；三是节点之间产生的引力或斥力。算法计算产生在每个节点上的合力来控制之间的距离及节点的移动。另一种方法是在部署阶段采用拓扑控制技术对节点采取局部分簇策略，每个节点根据周边节点的能量及分布密度等情况，自适应地调整工作模式，从而提高能量的机用率，若定义节点和被跟踪目标间存在作用力，则可使节点根据被跟踪目标的位置和重要性，动态地调整部署，保证在覆盖区域内提高节点跟踪能力。李享等人[11]主要研究了在未知覆盖目标的情况下，如何根据原有的虚拟力算法进行网络节点的三维部署。作者将虚拟力算法从二维空间拓展到三维空间，创新地提出了自适应中心引力和目标斥力网的概念，使传感器节点能够自适应地覆盖未知目标进行有针对性的探测任务，最终实现了对不同形态的复杂目标进行精确覆盖。当然，研究人员也提出过一些基于启发式的算法设计，但这些技术不能有效保证对监测区域的完全覆盖。李轩涯等人[12]提出了面向空中移动传感网的带电粒子群部署模型。作者认为空中移动传感器网络应用领域广阔，动态性强且环境复杂，原有的平面部署策略不再适用，提出的新算法基于带电粒子群思想，能够保证监测区域内重点覆盖与一般覆盖的均衡。Senel等人[13]讨论了水下传感器网络中节点的自部署及最大化覆盖，认为传感器进入水下环境的困难会使该问题更加复杂化。在文中他们提出了一个完全分布式节点部署方案，同时研究了可能对网络产生影响的环境因素，如海流、漩涡和随机表面效应等。