Page 300 - 《软件学报》2021年第8期

2582 Journal of Software 软件学报 Vol.32, No.8, August 2021

(1) 优化目标不同.无源传感器网络中的覆盖问题与无线传感器网络中的覆盖问题的优化目标是不同的:
在无线传感器网络中,由于传感器节点的能量有限,所以在无线传感器网络当中的覆盖问题的主要目
的在于合理化地调度节点工作,从而减少节点的能量消耗,进而最大化网络寿命;然而在无源传感器
网络当中,由于无源节点的寿命在能量角度来讲是无限的,这就使得最大化网络寿命成为了一个伪命
题.在无源传感器网络当中,我们需要考虑的是如何通过更加合理地使用环境中的能量,来最大化网
络的覆盖质量.
(2) 节点调度方式不同:在无线传感器网络当中,在网络生命周期内,传感器节点可以在任意时间工作;然
而在无源传感器网络当中,无源节点只有在获取足够能量后才能开始工作.但是由于周围环境能量源
具有能量低、能量分布不均匀等特点,导致一个无源节点往往需要很长时间才能获取足够能量,这就
使得无源节点无法在任意时刻进行工作.这种特点使得无源传感器网络中的节点调度更加困难,使得
无源传感器网络中的覆盖问题成为了一个新的问题.
(3) 节点能量获取不稳定.能量可获取网络(energy harvesting network)是无线传感器网络中的一种,在能
量可获取网络中 [16−18] ,每个传感器节点可获取固定的能量输入.然而在无源传感器网络中,由于周围
环境能量源的不可预测性,导致节点的能量获取速率十分不稳定.这也为无源传输节点的调度造成了
极大的困难.
根据以上 3 点,我们发现,无源传感器网络中的覆盖问题是一个全新的问题,且现有的在无线传感器网络中
[2]
的覆盖算法均无法用来解决无源传感器网络中的覆盖问题.Shi 在文章中给出了一种解决无源传感器网络中
[2]
的覆盖问题的方案.然而在这篇文章中 ,作者并没有考虑具有多等级通信半径的无源节点.一个具有多等级通
信半径的无源节点可以自主地调整自己的通信半径,而不同的通信半径具有不同的能量消耗.这样,无源节点具
有更多地自主性,并可以更合理地利用所获得的环境能量.比如,当网络节点密度比较高,或者环境中能量源比
较弱时,无源节点可以将自己的通信半径调为较低的等级,从而减少不必要的能量消耗;而当网络节点密度比较
低,或者环境中能量源比较强时,无源节点则可以采用较高等级的通信半径,通过提高通信半径来增强网络的连
通性.然而,由于上述提到的 3 个无源网络的特点,如何合理地调度无源节点工作、调整无源节点的通信半径等
级,成为了一个更加困难的问题.在本文中,我们提出了通信半径可调整的无源传感器网络覆盖最大化问题
(CR-MC-BFN).
本文的贡献简介如下:
(1) 我们定义了通信半径可调整的无源传感器网络覆盖最大化问题(CR-MC-BFN),证明了 CR-MC-BFN
问题是 NP-Hard 问题.
(2) 我们提出了一个两阶段近似算法(two-phase approximation algorithm,简称 TPA)来解决 CR-MC-BFN
问题.我们分析了 TPA 算法的时间复杂度,并证明了 TPA 算法的近似比.
(3) 我们通过模拟实验来验证算法的性能.我们首先提出了一个基于贪心策略的朴素算法,并将 TPA 算法
与其进行比较.根据实验结果,TPA 算法是有效的、可靠的.
本文第 1 节总结相关的工作.第 2 节给出问题的明确定义.第 3 节给出该问题的近似算法,并分析算法的时
间复杂度和近似比.第 4 节研究如何在无源传感器网络中解决 k-覆盖的问题.第 5 节通过模拟实验验证算法的
性能.第 6 节总结全文.

1 相关工作

1.1 网络覆盖

覆盖问题是传感器网络中的一个重要问题.覆盖问题的目的,是要保障传感器网络中传感器对监控目标的
有效覆盖.在无线传感器网络的研究中,存在着大量的关于覆盖问题的研究 [7−15] .这些研究中,覆盖问题的主要目
标就是合理地节省传感器节点的电量消耗,进而最大化网络的寿命.在文献[13,15]中,作者考虑了一种边界覆盖
问题,在这种问题中,覆盖区域为一条给定的路.而在文献[10−12]中,作者希望通过构造连通支配集(connected