无线传感器网络中覆盖算法研究综述

石 拓，李建中

（哈尔滨工业大学 计算学部，哈尔滨 150001）

0 引言

随着移动通信技术和移动设备的不断发展，物联网技术也取得了长足地进步［1－2］。无线传感器网络（Wireless Senor Network）是物联网（IoT）中的重要组成部分，也是连接物理世界与信息世界的关键技术。一个无线传感器网络可以被部署到一个区域当中，并对该区域中的物理信号（温度、湿度、压力等）进行监控，从而达到收集、分析该区域中的物理信息的目的。一个无线传感器网络由若干无线传感器节点和sink 节点构成。无线传感器节点由自身配置的电池供能，并通过传感器来获取周围环境中的物理信息，再通过通信模块与其它传感器节点或sink 节点进行通信，sink 节点则会将所收集的物理世界的信息上传到云端，供用户进行数据分析与处理。这样，无线传感器网络既可以帮助人们打破物理世界与信息世界之间的信息壁垒，也为万物互联打下了基础。由于无线传感器节点的体积很小，且造价低廉，无线传感器网络可以被大规模地部署到人类很难到达的环境［3］。如：森林、山丘、战场等，并在森林防火、灾情检测、敌情侦查等方面产生了重要的作用。因此，通过无线传感器网络，人们几乎可以对任意环境进行监控。覆盖是传统无线传感器网络中的一个重要问题，覆盖质量是评价网络通信性能和监控性能的重要指标。覆盖问题的解决，对于传感器网络的数据收集、数据聚集、数据查询、数据挖掘等均具有重要的意义。

对于一个传感器节点i，设li为i在监控区域中的位置，rs为该节点的感知半径。一般而言，若监控目标（单个点目标，或者区域目标）处在以li为中心，rs为半径的圆内，则认为该监控目标被节点i所监控（覆盖）。根据覆盖需求的不同，可以将无线传感器网络中的覆盖方式分为3 种：全覆盖、部分覆盖和多覆盖。全覆盖是指网络节点需要对所有监控目标进行覆盖；部分覆盖是指网络节点对所有监控目标的覆盖达到某一给定的覆盖率θ≤1；多覆盖则是对于监控区域内的任意目标（多指点目标），在同一时刻被至少k个传感器节点覆盖（k为给定的正整数）。根据网络部署方式的不同，无线传感器网络中的覆盖问题可以分为两类：基于随机性部署和基于确定性部署的传感器网络中的覆盖问题。随机性部署是指网络节点随机地部署到监控区域，而确定性部署是指网络节点的部署位置是经过人为计算得到的。随机性部署主要针对大规模的无线传感器网络，而确定性部署更偏重于小规模的无线传感器网络。对于基于随机性部署的传感器网络中的覆盖问题，主要研究如何通过合理地调度节点工作对网络的覆盖质量进行优化；而基于确定性部署的传感器网络中的覆盖问题，主要研究如何通过安排节点位置对网络的覆盖质量进行优化。本文所介绍的相关工作见表1。

表1 不同覆盖算法之间的对比Tab.1 The comparison between different coverage algorithms

1 基于随机性部署的传感器网络中的覆盖算法

1.1 全覆盖算法

全覆盖算法的目的，一般是通过调度节点工作以达到在对监控目标全覆盖的前提下，最大化网络寿命。部署在监控区域中的传感器节点数目往往是冗余的，因此，文献［4－8］中的主要策略是，将网络中的传感器节点分为若干不相交的节点集合，并对不同集合中的传感器节点进行轮询调度。当一个集合中的节点处于工作状态时，其它集合中的节点则处于休眠状态。这种策略的目的是最大化网络中的不相交节点集合的个数，从而优化节点的能量消耗，最大化网络寿命。文献［4］中作者证明了最大化网络中不相交节点集合问题是NP－完全的，同时不存在多项式时间内的1.5 近似算法。与以上基于不相交节点集合策略不同，文献［9－10］中通过构造、调度相交的传感器节点集合，来构造网络覆盖。其策略是将传感器节点的能量，按照单位时间内的工作能耗进行划分，并根据划分结果构造不同的节点集合。因为在这种划分策略中充分考虑到了节点中的能量存储，所以基于这种策略可以进一步地延长网络寿命，保证网络覆盖。在文献［11］中，作者则提出了一个基于节点调度的网络覆盖算法。其策略是，节点通过“不工作准则”来判断是否需要工作。“不工作准则”是指，若该节点所监控的区域已经被其邻居节点所覆盖，则该节点可以选择进入休眠状态。这样，通过综合地考虑网络中节点的覆盖区域，以及邻居节点之间的关系，可以有效地调度节点工作，合理地利用节点能量。同时，作者还讨论了当网络中节点感知半径异构时的网络覆盖算法。文献［12］中作者则提出了分化监控的策略，即在满足全覆盖的前提下，为较敏感、重要的监控目标提供更多的监控节点。此外，监控区域和监控周期被分别划分为不同的网格和时间段，传感器节点则根据所处的网格和时间段来进行工作调度。

1.2 部分覆盖算法

相比于全覆盖算法，部分覆盖算法仅要求传感器节点对网络中的部分重要监控目标进行覆盖或满足一定覆盖率。文献［13－14］中实验结果表明，部分覆盖相较于全覆盖可以显著地提高网络寿命。文献［15］首次定义了传感器网络中的部分覆盖问题，即θ－覆盖。该问题要求在保证网络连通的情况下，使得网络覆盖率至少为0≤θ≤1。作者证明了该问题为NP－难问题，并分析了在不同通信、感知半径下，满足θ－覆盖的活跃传感器节点数量上界。基于θ－覆盖的理论性质，作者提出了时间复杂度为O（n3）的集中式启发式算法。在初始时刻，算法随机地选取工作的传感器节点；在每一轮迭代中，则选择处于候选路径上具有最大收益的节点进行工作。该算法迭代地进行，直到监控区域达到了θ－覆盖。文献［16］中也采用了这一策略，并提出了集中式和分布式两种算法来解决部分覆盖问题。为了能够区别地对待不同的监控区域，作者将监控区域分成了不同的簇，并通过调度节点来对不同的簇依次进行覆盖。在文献［17］中，作者定义了最大化传感器网络寿命问题，并提出了一个满足传感器网络中部分覆盖的，具有（1＋logn）近似比的集中式近似算法。根据该文中的实验结果，当对传感器网络进行90%覆盖时，网络寿命可以较全覆盖情况下提高至少3.3 倍。文献［18］中则采用了分治思想，来解决传感器网络中的部分覆盖问题。其在基于节点位置信息的分布式PCCP 算法中，首先通过分治思想，将监控区域进行划分，并在每一个划分区域中对传感器节点进行合理调度，从而达到满足网络覆盖率的要求。通过本文的实验结果可以发现，随着覆盖率的逐渐递减，网络寿命随之增加，当覆盖率从0.9 降为0.5 时，网络寿命平均提高了75%。文献［19］中提出了一个基于六边形的部分覆盖算法，来最大化网络寿命。在文中，监控区域被分为了若干单位六边形，而传感器节点则根据所属的六边形被分为若干组。文中通过提出了3 种规则，调度每组中的传感器节点进行工作。该算法可以在牺牲一部分覆盖质量的前提下，显著地提高（约74%）网络的寿命，但无法保证所牺牲的覆盖质量的界限。

1.3 k－覆盖算法

对监控区域进行k－覆盖，是传感器网络中覆盖问题的一个重要分支。一方面，由于传感器节点的不稳定性，为了保障对监控目标的有效覆盖，可以利用多个传感器节点监控同一目标的策略，即每一个监控目标都被至少k个传感器节点所监控；另一方面，由于监控区域中的监控目标的重要性和敏感程度的不同，对于用户较为关心的监控目标，需要利用多个传感器节点对其进行监控。文献［20］首先研究了传感器网络中的k－覆盖问题，并提出了一个基于位置信息的启发式算法，根据不同的应用为监控区域提供不同程度的覆盖，即k－覆盖。然而，该算法无法保证所构造覆盖的大小，即无法保证节点的耗能。在文献［21］中，作者则提出了一个能够保证覆盖大小的启发式k－覆盖算法，证明了算法所构造的覆盖的大小与最优解大小之间存在着O（logn）的近似比。该算法的主要思想是，选择候选路径上具有最大收益的节点进行工作。然而，以上两种算法均只考虑了单个覆盖的构造，并没有考虑如何将网络中节点划分成若干集合，并使得每个集合构成一个网络的k－覆盖。在文献［12］中，作者提出了能量有效的网络覆盖协议。该协议可以提供分化型监控服务。节点可以通过动态地调度工作状态，来为网络提供k－覆盖。虽然该协议可以有效地利用节点能量，但无法保证k ＞2 时的网络覆盖。在文献［22］中，作者将覆盖问题形式化为了一个判定问题，其目标是判断监控区域中的任意一个点是否被至少k个传感器节点所覆盖。文中引入边缘覆盖层级（PCL）的概念。作者证明了整个监控区域可以被传感器网络k－覆盖，当且仅当每个监控区域中的传感器节点都被k－边缘覆盖。基于该工作，文献［23］提出了两个启发式算法，来解决网络的k－覆盖问题。在算法中，网络中节点被划分为了若干集合，每个集合中的节点都可以对监控目标实现k－覆盖，算法通过最大化划分的集合个数来最大化网络寿命。

基于随机部署的传感器网络中覆盖算法可以总结为，在达到延长网络寿命的同时，使得网络对监控目标实现一定规模的覆盖。所有现存算法均着重考虑如何合理地调度节点，使得节点在监控目标的同时减少耗能。然而，由于传感器节点自身能量受限，使得这类算法的输出结果具有一定的限制。

2 基于确定性部署的传感器网络中覆盖算法

当传感器节点数目较少时，可以通过合理地部署节点的位置来保障网络覆盖。在文献［24］中，作者采用基于网格的节点部署策略，提出了一个感知模型，用来度量不同位置的感知效率。其次，文中将监控区域划分为不同的网格，并根据感知模型，来判断需要部署节点的网格。该算法基于贪心策略，并迭代运行。在每一轮迭代中，通过贪心策略来部署传感器节点的位置，迭代在网络的覆盖目标达成时终止。文献［25］研究了水下无线传感器网络中最小化节点数目的全覆盖节点部署算法。在这种网络中，传感器节点需要部署在海底，利用最少的传感器节点达到最大的覆盖，文中将监控区域划分成了三角网格，根据三角网格，就可以仅通过调整节点之间的距离关系来调整节点对目标的覆盖。作者经实验证明：当感知半径r与三角网格的边长d满足d ＝时，则可以满足全覆盖的要求。文献［26］的研究中，不仅考虑了部署节点对区域的覆盖，同时也考虑了节点之间的连通关系。该文的目的是在监控区域中部署节点，并在保障对监控区域全覆盖、网络连通的前提下，最小化部署的节点数量。该研究中提出的算法保障了网络的强联通，即当网络中有节点死亡时，不影响网络的连通性。文献［27］中则考虑了当网络中存在多个sink 节点时的节点部署问题。该工作在保障网络覆盖、连通的前提下，达到最小化部署节点数量的目的。在该研究中，节点被分为两类：一类为感知节点（负责感知、监控目标区域），另一类则为中继节点（负责保障网络的连通）。其算法分为两个主要步骤：第一步，通过部署感知节点来保障节点对监控目标区域的覆盖；第二步，则通过部署中继节点来保障网络的连通。在这两步中，算法通过采用贪心策略和生成树策略，来近似地减小所部署的节点数量。在文献［28］中，作者考虑了传感器网络中的k－覆盖m－连通问题，即通过部署传感器节点，使得监控区域中的每个监控目标都被至少k个传感器节点所覆盖；同时，网络中的每个传感器节点都与至少m个其它节点所连通。这一目的保障了网络的稳定性。当网络中有节点死亡时，因为有冗余节点的存在，并不会影响网络的功能。为了解决该问题，文中作者提出了一个基于遗传算法的框架。

与基于随机性部署的传感器网络中的覆盖算法不同，在确定型部署的传感器网络中的覆盖算法，将注意力集中在如何最小化部署的节点规模上。然而，如何将节点部署与节点调度想结合，研究网络寿命与节点位置之间的潜在关系，从而进一步地优化传感器网络仍然是一个待解决的问题。

3 结束语

网络覆盖是无线传感器网络领域保证感知数据完整性和网络连通性的一个重要技术，对于无线传感器网络中的诸多应用，包括感知数据查询处理、感知数据收集、感知数据聚集、感知数据挖掘等均具有重要的意义。研究者们在无线传感器网络中的覆盖问题上已深耕多年，存在多种不同的覆盖算法。本文对现有的无线传感器网络中的覆盖算法按照不同的网络拓扑、不同的覆盖类型进行了总结与分析，对于这些现存算法进行了总结，对现有工作的优缺点进行了分析，望对相关问题的进一步研究提供了有效依据。