基于部署方式的节点部署算法

根据部署方式的不同，节点部署算法可分可为确定性部署和随机性部署两大类。确定性部署通常应用于环境友好或网络状态较为稳定的应用中，传感器节点根据应用需求被置于经过计算和安排后所确定的位置上，通过将节点部署问题抽象为数学问题中的线性规划问题，以网络性能或成本最优化为目标而提出解决方案[19]；而随机部署则较为适用于环境恶劣或人工无法到达的监控环境中，传感器节点通常以抛洒的方式随机分布在目标区域内，节点位置往往是无法确定的。

确定性部署相比随机部署来说具有较优的网络性能，但在规模较大且应用环境十分恶劣的实际部署应用中，确定性部署往往占用了较高的人力成本和时间成本，而随机部署则充分体现了其简单和高效的优点，但同时，目标区域的覆盖性能却无法得到保证。

确定性部署算法

确定性部署被广泛应用于水下传感器网络。针对水下三维环境的节点部署问题，Poduri等人提出了从二维空间到三维空间部署策略的适应性算法，文献[20]围绕着三维空间内的节点部署问题和规划，提出了一系列有效构建三维网络拓扑结构的规则，通过转换为二维问题来实现三维空间的节点部署问题。

在文献[21]中，作者通过计算得出网格部署模型下，满足基本网络覆盖和连通所需要的活动节点数目，该算法为节点部署提供了理论基础，缺点是该方法只可适用于二维环境下的节点部署，无法满足水下无线传感器网络这种具有三维特性的应用需求。

最大平均覆盖算法（MAX_AVG_COV）与最大最小覆盖算法（MAX_MIN_COV）[22]的提出是基于网格部署模型，通过贪心算法策略进行节点部署，根据前驱节点的位置信息，决定下一个节点的布置位置。两种算法都旨在实现最佳网络覆盖，最大平均覆盖算法（MAX_AVG_COV）的目标是最大化网格点的平均覆盖效果，算法考虑的是整体网络的覆盖效果；而最大最小覆盖算法（MAX_MIN_COV）的目标是使得网络中覆盖效果较差的网格点的覆盖效果最大化，算法从优先改善网络局部性能的角度出发，优先把传感器放在性能最差的点上。两种算法用于概率感知模型，节点对目标事件的感知概率随着目标事件与节点间距离而变化，算法未能充分考虑冗余覆盖的问题，使得网络性能未能达到最佳表现，同时，两种算法复杂都较高，为 O(n^4)。

在文献[22]的基础上，蔺智挺等学者提出了一种整体-局部增进算法[23]，该算法的特点是网络初始化后，算法迭代运行，并且每次运行都放置一个传感器到传感器区域中，直到目标区域内所有点都满足覆盖要求或是已配置的传感器数目已达到能配置的传感器的数目的极限时才停止。在每次迭代过程中，算法寻找使网络整体有效覆盖性能改变最大的点，剔除局部冗余，提升了网络的整体性能。

随机部署算法

当目标区域的环境十分恶劣时，比如战争区域、灾害防御地区、或是人类无法靠近的深海等，又或者在进行大规模的网络部署时，节点数目巨大，分布密集，这样的条件下采用确定性部署方式进行网络部署是不实际的甚至不可行的，此时，唯一可采用的方式是利用飞机、大炮等工具将节点以随机方式抛洒至目标区域，节点自组织成网络。

2001 年，作者 González-Banos 在文献[24]中提出了一种基于艺术画廊看守问题的随机部署策略，根据密度公式将传感器节点的位置以极坐标的表示方式建立了一种 R-random 的部署模型，它使用 R 来表示传感器节点与汇聚基站的距离。由于艺术画廊看守问题旨在解决有限边界内的最少覆盖问题，因此该文献在容错方面具有较好的性能，仿真实验表明了 R-random部署节点提升了整个传感器网络的可靠性。由于网络都采用多跳方式传输数据，因此越靠近基站的节点其能耗则越大，所以需在基站周围部署密度较大的节点以实现大量冗余节点，替代那些因能耗殆尽而死亡的节点，以此提升网络生存期，并保障数据的连通性。

在文献[25]中，作者提出了一种加权的节点随机配置算法，解决了在不同的区域内节点耗能速率不同的问题，也就是增加中继节点密度，使更多的中继节点分担负载，这样可以延长网络的平均生命周期。但改算法将大量的中继节点部署于距离基站较远的位置，因此网络的连通性将会受到影响。

虽然采用随机部署方式从某种程度上可提高部署效率并减少人工成本，但节点在网络中的相对坐标无法确定，因而这种部署方式无法保证目标区域具有良好的覆盖效果。因此在确定性部署与随机部署二者之间的选择上，Zhang H [26]围绕着确定性部署与随机部署两种方式究竟孰优孰劣的问题，分析并研究了实现一定程度的覆盖度所需的节点数目，作者分别考查了泊松分布、均匀随机分布、网格分布三种部署策略下维护网络 K 覆盖所需的节点密度，文章最后指出，采用网格部署方式所需的节点密度小于另外两种随机部署策略所需的节点密度，证明了网格部署策略在同等条件下所需的节点数目要优于随机部署策略。

基于优化对象的节点部署算法

在第二章，我们论述了部署方案的评价指标分别有良好的区域覆盖能力、数据信息的可达性和较长的网络生存期。本节将针对部署算法的这三个评价指标的优化对象的不同，从基于覆盖的部署、基于网络连通的部署和基于能量有效性的部署三个类别来对现有算法研究成果进行论述。

基于区域覆盖的部署算法

实现目标区域的覆盖面积最大化是无线传感器网络部署问题的基本目标，因此区域覆盖也已经成为了许多学者研究的出发点。针对目前 WSNs 应用中经济成本和客观环境的限制，在文献[27]中，作者研究了随机部署方式下有限无线传感器网络在目标区域内的覆盖概率的最大值和最小值，并提出了线性网络环境下实现最大覆盖概率的部署策略，但该部署策略仅适用于线性网络下对移动目标的监测环境。文献[28]将区域覆盖问题划分为面积覆盖、点覆盖和栅栏覆盖问题三大类并分别进行了阐述，面积覆盖问题主要研究的是如何实现覆盖面积最大化的问题；点覆盖旨在考查实现网络中个别目标的覆盖问题；栅栏覆盖的研究目标是如何降
低未知入侵发生的概率，它涉及运动检测。

文献[29]使用网格方法来进行覆盖率的计算，覆盖率的估算通过目标区域中被节点所覆盖的网格数与目标区域的网格总数量之比实现，目标区域所划分的网格数目决定了覆盖率的计算复杂度和结果的精确度，网格被划分得越细，最后计算所得的覆盖率其精确度越高，当然计算过程的开销也更大，如图 3.1 所示，同样 6 个节点，网格划分为 4×4 时所计算得出的覆盖率为 100%，而划分为 8×8 时所得的覆盖率为 98%。

文献[10]针对水下无线传感器网络的应用特性，提出一种节点可自我进行深度调节的算法，节点通过深度调节机制调整其在水下的深度，以实现水下三维环境覆盖率的最大化。初始阶段被部署与水底环境的各个传感器节点通过各自的 ID 号选取簇首节点，簇首节点负责通知该簇内其他节点的调节深度，通过判断节点间是否存在覆盖重叠区域来对节点进行分组管理，存在覆盖重叠的节点彼此分至不同的组号中，组号决定了节点将来被分配至水中的深度；待分组结束后，节点根据自己所在的组号移至水中相应的深度。该算法假设节点在水下环境只具备垂直方向上的移动性，由于簇首担当了对簇内其他成员节点转发管理指令的职责，因而造成了簇首节点的能耗将大于成员节点，而簇首节点的选举在只可在网络初始阶段即节点处于水底二维环境下进行，若簇首节点的死亡将造成整个簇内成员节点的瘫痪。

基于网络连通性的部署算法

良好的网络连通性能够保证传感节点所采集到的信息准确及时的传递到使用终端。目前的研究文献中，关于网络连通性的问题多是在实现覆盖的前提下，通过增大节点通信半径来实现的，例如当 RT是 RS的比例 r>1 时，只需实现良好的网络覆盖，节点之间的连通性就能得到保障。然而，在节点通信能力相比感知能力较差的情况下，例如 RT=RS的情况下，网络的连通性能则无法得到保障。

文献[15]围绕着多连通问题展开研究，结合三维空间部署特性和对点阵模式的研究，提出了三维空间下实现 1-连通、2-连通 3-连通、4-连通的部署模型。文章所提的部署模型基于点阵模式，通过对相应模型中节点的通信半径和感知半径之间关系的研究，考查节点部署位置对网络中 K 连通效果的影响，该文所提出的最优模型实际是以 RT/RS比例为前提，在相应的RT/RS比例关系下，对应相应的模型，其最优性限制于节点通信半径与感知半径间的比例关系。

基于能量有效性的部署算法

节点的分布密度和其在网络中所处的位置通常会直接影响到整体网络的生命周期，在节点分布过于密集的情况下，数据通信链路容易出现拥塞，使得网络传输负载失衡，从而造成通信负载瓶颈；另外，由于网络多采用多跳方式进行数据转发，因此在节点均匀分布的情况下，靠近基站的节点的能量耗损速度相对较快，从而造成整个网络的能量瓶颈问题。

文献[30]研究了具有最大生存期节点的部署问题。作者提出一种模型使得每个节点可以周期性地向基站发送数据报告。将每个周期数据采集所需的能耗作为衡量网络生命周期长短的标准，作者把问题转化为通过平衡节点负载，最小化每个节点每轮的平均能耗。文章假设网络采用大量的传感节点来传送探测数据，并且谨慎的选择后继节点使得数据传送所需的总能量最小。一种有效的算法是重新部署节点，从而形成最有效的拓扑结构。节点按其接近兴趣点的程度，被按降序挑选出来，算法在所有的传感器节点之间迭代，在每一步迭代中，传感器节点检查自己是否能作为后继节点传输数据。新地址的选择是基于运输流量，实际上，节点的重新部署是通过接近下游邻节点的方式以降低能量消耗。只有在网络的覆盖性不受影响的情况下，才允许重新部署传感器节点[31]。

在文献[32]中，节点在“休眠”-“活跃”两种状态间转换，在满足应用需求的前提下，非必要节点进入休眠状态，而其余节点继续保持活跃状态继续为网络服务；若因节点能量耗尽而退出网络，或应用需求的改变使得当前活跃节点数量无法满足应用需求，休眠节点进入活动状态。作者提出了一种可根据网络状态对节点进行动态管理的协议，以实现应用所规定的覆盖率和连通度目标，并对节点状态进行管理。通过几何关系的研究，考查覆盖率和连通率间的关系，并结合 SPAN 协议为网络覆盖率和连通率提供保障。

文献[33]研究了节点密度对网络生命期的影响，作者从部署角度考虑，分析得出网络生命期的解析公式。并通过研究发现网络生命期并非随节点数量的增加而成比例的增长，因此需要仔细筛选一定数量的节点来平衡网络的成本。考虑到当第一个节点死亡时网络就会中断，作者将问题转化为确定节点的数目并确定它们的位置来保持网络长时间运行。最后提出了两步的解决方案。首先，固定传感器节点的数量，通过多变量非线性问题来解决网络的优化部署，使其达到最长的网络生命期；然后，减少传感器节点数量同时实现最长网络生命期。该文献以固定传感器节点数目为前提，考察节点在网络中的位置，以形成生命期最长的网络拓扑结[31]。

基于部署特性的节点部署算法

静态部署算法

静态网络的运行模式通常是通过预先设定的路由线路传递数据，在进行节点部署工作之前，首先根据应用特性和节点在网络中所发挥的作用来确定其在网络中所处的位置，待部署方案确定之后，方案将独立于网络的状态并且贯穿于整个网络生命周期内。在目前的应用中，可将节点按功能大致地分为四类：传感节点、中继节点、簇首节点和基站节点（汇聚节点）。

静态部署算法的缺点仅在网络初始阶段进行节点位置预判断，而节点的最佳位置的评估往往与网络的数据传输率、节点的感知能力、数据路径距离大小等因素息息相关，静态部署方式往往不考虑节点部署后的移动情况，因此无法根据应用需求对网络部署进行修补以改善网络性能。

文献[34]对异构网络下的节点进行确定性部署分析，采用分簇下的节点部署方案，网络中存在两种节点，一种是普通节点（Regular Sensor Nodes, R-SN），这类节点受通信、存储能量和计算方面的限制。另一类是高端复杂节点(High-endsophisticated sensor nodes，H-SN)，即簇头节点，这类节点具有充分的资源。

动态部署算法

在某些情况下网络状态是变化的，例如当新节点的加入或某节点能量耗尽时，网络拓扑结构和网络生存期会相应地发生变化，而静态部署策略并未能考虑到网络运行的这些动态变化，因此，为了适应网络的这种变化以实现网络性能的优化，需考虑采用动态方式。

在文献[35]中，节点具有移动性，待部署于目标区域后，各节点利用各自的排斥力朝着与邻节点相反的方向移动直至节点所受的来自各方向的排斥力达到平衡，因而这种方法减少了节点间的覆盖重叠区域。然而这也必然增加了节点的能耗，同时，该文献并未考虑网络的连通性。2005 年，作者 Howard 在文献[35]的基础上延伸了对网络连通率的研究[36]，考查节点通信范围内的邻居节点数目并以节点间的吸引力来保证网络的连通性能。文献[35,36]算法的优点是执行起来简单易行，无须对环境进行预处理，且算法具有较强的鲁棒性，适用于大规模的节点部署应用；缺点是网络过于依赖节点的移动性，节点的能耗将是一个十分严重的问题。

类似地，Zou 和 Chakrabarty 学者所提出的 VFA 算法也是基于节点移动功能模块的增加[37]，然而不同于文献[35]采用的一次性对节点进行移动，VFA 首先进行移动的模拟仿真，在确定移动后节点所处的位置后，节点一次性地移至该点，节点间移动距离的计算通过簇首节点完成，节点不单具有排斥力，还具有相互间的吸引力，在节点间距过密是通过排斥力扩大覆盖面积；当节点间距过疏时通过吸引力减少覆盖漏洞。该算法简单易用，可实现目标区域快速覆盖，部署效率较高，算法复杂度根据节点数目和目标区域面积变化，在划分为 n×m个网格的给定区域内部署 k 各节点的算法复杂度为 O(nmk)。

文献[9]引入一种新的传感器网络结构，提出了基于表面随机配置的水下无线传感器网络节点部署方法：在进行网络初始配置时，在水平面上随机布置一定数量的节点，然后根据每个节点调整空间内的邻居节点深度安排其自身深度，尽可能使水下三维空间得到充分的覆盖。

各类部署算法比较