多等级通信半径的无源传感器网络中的覆盖问题∗

石 拓,李建中,高 宏

(哈尔滨工业大学 计算机科学与技术学院,黑龙江 哈尔滨 150001)

无线传感器网络(wireless senor network)是物联网(IoT)中的重要组成部分,一个无线传感器网络由若干无线传感器节点和Sink 节点构成.无线传感器节点通过自身配置的电池获能,并通过传感器来获取周围环境中的物理信息,再通过通信模块与其他传感器节点或Sink 节点进行通信[1].这样,一个无线传感器网络可以被部署到一个区域当中,从而达到收集、分析该区域中的物理信息的目的.由于无线传感器节点的体积很小,这样,无线传感器网络可以被部署到人类很难到达的环境,比如森林、河流、山丘等.这样,通过无线传感器网络,我们几乎可以对任意环境进行监控.然而,以下两个缺点阻碍了无线传感器网络的大规模部署.

(1) 无线传感器网络的寿命受限.由于无线传感器节点的能量有限,这导致了无线传感器网络的寿命是受限的.对于一个部署在复杂环境中的大型无线传感器网络而言,短暂的网络寿命不但影响了网络的性能,也造成了不必要的经济损失.

(2) 无线传感器节点是环境不友好的.由于无线传感器节点一般采用锂电池作为能量源,当无线传感器节点能量耗尽后,遗留在环境中的废弃电池会对环境造成极大的污染.

为了解决无线传感器网络的这两个问题,Shi 等人[2−5]提出了一种新型的传感器网络结构——无源传感器网络.在无源传感器网络中,每个网络节点配备有可从周围环境中获取能量的能量获取模块,并通过超级电容来存储能量.

•一方面,由于周围环境中的能量是无限的,比如太阳能、风能、射频能量等,这样,从能量上讲,无源传感器网络的寿命是无限长的,从而解决了无线传感器网络的寿命受限的问题.比如在斜拉桥的拉索状态检测应用中,传统的方法是在拉索上部署不同类型的无线传感器节点,但是由于无线传感器节点的寿命有限,需要不断地更换传感器节点中的电池,这就造成了不必要的危险和人工消耗.通过部署无源传感器网络节点,则可以改善这一问题.

•另一方面,由于超级电容从理论上讲是可以无限次充放电的,这样,无源节点的能量存储模块的寿命也是无限长的,从而解决了无线传感器节点环境不友好的缺点.比如在森林火灾监控当中,需要在野外森林中部署大量的无线传感器节点,但是无线传感器节点所配备的锂电池在能量耗尽后,会对自然环境造成严重的污染.如果使用无源传感器网络进行监控,则可以实现环境友好型监控.

综上所述,无源传感器网络可以替代无线传感器网络对环境进行理论上无限长时间的监控.图1 中展示了两种无源节点,其中,图1(a)中的无源节点主要从射频能量源中获取能量,图1(b)中的节点可以从太阳能中获取能量.

Fig.1 Two kinds of battery-free nodes图1 两种无源节点

覆盖问题是传统无线传感器网络中的一个重要问题.覆盖问题的解决,直接关系到了无线传感器网络的数据获取质量.文献[6−15]中均对无线传感器网络中的覆盖问题进行了研究.然而,由于无源传感器网络自身的特点,导致了覆盖问题在无源传感器网络是一个全新的问题.Shi 等人[2,4,5]着重讨论了覆盖问题在无源传感器网络中的特点.相比于无线传感器网络中的覆盖问题,无源传感器网络的覆盖问题具有以下特点.

(1) 优化目标不同.无源传感器网络中的覆盖问题与无线传感器网络中的覆盖问题的优化目标是不同的:在无线传感器网络中,由于传感器节点的能量有限,所以在无线传感器网络当中的覆盖问题的主要目的在于合理化地调度节点工作,从而减少节点的能量消耗,进而最大化网络寿命;然而在无源传感器网络当中,由于无源节点的寿命在能量角度来讲是无限的,这就使得最大化网络寿命成为了一个伪命题.在无源传感器网络当中,我们需要考虑的是如何通过更加合理地使用环境中的能量,来最大化网络的覆盖质量.

(2) 节点调度方式不同:在无线传感器网络当中,在网络生命周期内,传感器节点可以在任意时间工作;然而在无源传感器网络当中,无源节点只有在获取足够能量后才能开始工作.但是由于周围环境能量源具有能量低、能量分布不均匀等特点,导致一个无源节点往往需要很长时间才能获取足够能量,这就使得无源节点无法在任意时刻进行工作.这种特点使得无源传感器网络中的节点调度更加困难,使得无源传感器网络中的覆盖问题成为了一个新的问题.

(3) 节点能量获取不稳定.能量可获取网络(energy harvesting network)是无线传感器网络中的一种,在能量可获取网络中[16−18],每个传感器节点可获取固定的能量输入.然而在无源传感器网络中,由于周围环境能量源的不可预测性,导致节点的能量获取速率十分不稳定.这也为无源传输节点的调度造成了极大的困难.

根据以上3 点,我们发现,无源传感器网络中的覆盖问题是一个全新的问题,且现有的在无线传感器网络中的覆盖算法均无法用来解决无源传感器网络中的覆盖问题.Shi[2]在文章中给出了一种解决无源传感器网络中的覆盖问题的方案.然而在这篇文章中[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 dominating set)来保障无线传感器网络的覆盖与连通.但是由于这些工作均没有考虑如何合理地利用能量,且其研究问题的优化目标与无源传感器网络中的覆盖问题不同,导致这些工作无法直接应用到无源传感器网络中来.

1.2 无源节点与无源传感器网络

无源节点是一种新型的物联网节点.Sample 等人[19−21]通过改进RFID 的标签节点,使其成为了一种可以从射频能量中获取能量的无源节点.文献[22,23]中分别提出了一种基于太阳能和风能的无源节点.Dai 等人[24,25]提出了一个基于特定充电桩的无源传感器网络,在这种网络中,无源节点需要从特定的充电桩来获取能量.然而,这些文章或者没有考虑到无源节点的组网问题,或者没有考虑无源传感器网络中的覆盖问题.

1.3 无源传感器网络中的覆盖问题

Shi 等人[2,4,5,26]研究了无源传感器网络中的覆盖问题.在这些文章中,主要考虑了在不同网络结构、不同能量获取方式下的无源传感器网络中的覆盖问题.然而在这些问题中,均没有考虑无源传感器网络中的无源节点的通信半径选择问题.

2 问题定义

2.1 网络模型

一个无源传感器网络(battery-free wireless sensor network,简称BF-WSN)包含了一个Sink 节点集合S={s1,s2,…,sn}和一个无源节点集合V={1,2,…,m}.无源节点均匀地分布在监控区域R.无源网络的监控周期为T,T可被分为若干时间槽:{t1,t2,…,tK}.不失一般性地,我们将每一个时间槽当作网络的采样周期.

每个无源节点可以从周围能源环境中获取能量.我们设每个节点i在时间槽tj可获取的能量为μi(tj),同时设所有无源节点都具有相同的能量存储空间B.令Bi(tj)为无源节点i在tj时间槽开始时刻所存储的电量,显然,Bi(tj)≤B.根据Zhang 等人[27]的研究工作,对于任意一个无源节点i,它可以在时间槽tj工作,当且仅当Bi(tj)≥Bf.其中,Bf是保障节点可以工作的最低能量值.一个无源节点在一个时间槽(或采样周期)内可以进行感知、计算、传输等工作,而在进行这些工作的过程中,无源节点同样需要消耗能量.我们假设:在每一个时间槽,每一个无源节点的最大能量消耗为Δ[28],显然,Δ≤Bf.这样,节点i在时间槽tj+1的电量可以表示为

不失一般性,我们假设所有Sink 节点所导出的图为连通图,且所有无源节点具有相同的感知半径rs.根据无源节点的特性,我们假设节点可以自主地调整其通信半径的大小[29].设每个无源节点的通信半径rc具有L个等级,当节点的通信半径处于l级时,节点的通信半径为节点单位时间槽的最大能量消耗为Δl,且对于任意两个等级1≤l

给定一个监控区域R,R可以表示为所有无源节点监控区域的集合Ri,其中,Ri是无源节点i的监控区域.一般地,我们认为Ri是一个以i的位置为圆心、rs为半径的圆形区域.为了更好地评估对监控区域的覆盖效果,我们再根据节点的感知半径将监控区域R离散化为若干不同的区块,并为每一个区块分配一个0 到1 之间的权值.区块的权值表示了区块的重要程度,比如,对于一个部署在森林当中、监控森林火灾的网络而言,更加干燥的区域就需要分配给较高的权重.一个区块的具体定义如下.

定义1(监控区块).给定一个监控区域R,R可以被划分为若干不同的监控区域,R={φ1,φ2,…,φk}.对于任意一个监控区块φi∈R,φi需满足以下条件:

(1)φi具有一个在0～1 之间的权重wi;

(2) 对于φi中的任意两点p,p′,{j|dis(j,p)≤rs∧j∈V}={j|dis(j,p′)≤rs∧j∈V}.

定义1 中的第2 个条件表明,处于同一个监控区块中的所有点,均可被相同的无源节点集合所监控.图2 中给出了一个监控区块的例子.图2 中具有4 个无源节点,根据无源节点的感知半径,监控区域可以被分为11 个监控区块.对于任意的监控区块φi∈R,我们用ai来表示φi的面积.

Fig.2 An example of the monitor block图2 监控区块的例子

2.2 问题定义

为了有效地监控区域,无源网络需要调度节点,使得在任意时间槽内有无源节点进行工作,并对监控区域进行监控.因此,我们给出如下局部覆盖的定义.

定义2(局部覆盖).给定一个无源传感器网络N(V∪S,E),在时间槽t的覆盖Ct∈V是一个无源节点集合,且满足以下条件.

(1) 对于任意一个无源节点i∈Ct,Bi(t)≥Bf;

(2) 由Ct∪S导出的图Gt(Ct∪S,Et)是一个连通图,且Et={(i,j)|(dis(i,j)≤min{rc(i,t),rc(j,t)})∧(i,j∈Ct)}.

定义2 中的条件(1)表明,在时间槽t的局部覆盖中的所有无源节点均可工作.而第2 个条件表明,由这些节点和Sink 节点所构成的图是连通图,这也保障了在时间槽t内局部覆盖的连通性.显然,对于一个局部覆盖Ct,其所能监控的区域为.根据局部覆盖的定义,我们给出如下全局覆盖(或简称覆盖)的定义:

定义3(全局覆盖(覆盖)).给定一个无源传感器网络N(V∪S,E)、一个监控周期T,一个全局覆盖C={Ct|t∈T}是在监控周期T内的所有局部覆盖的集合.

我们定义如下的覆盖质量来度量一个(局部/全局)覆盖:

定义4(覆盖质量).给定一个全局覆盖C={Ct|t∈T},对于任意局部覆盖Ct∈C,其覆盖质量为

显然,当Q(C)=1 时,监控区域在监控周期内可以被全覆盖.然而,由于无源节点的特点,一个无源节点很难保障在任意时刻都可以工作.这样,如何合理地调度无源节点工作,选取节点的通信半径,从而最大化全局覆盖质量,成为了一个问题.为此,我们定义了通信半径可调整的无源传感器网络覆盖最大化问题(简称CR-MC-BFN).该问题的输入输出如下.

输入:

1.无源节点集合V和Sink 节点集合S;

2.无源节点的能量存储空间B和无源节点可以工作的最小电量Bf;

3.无源节点的感知半径rs;

4.无源节点通信半径的L个等级以及无源节点在不同通信半径下的单位时间槽能量消耗{Δ1,Δ2,…,ΔL};

5.无源传感器网络的监控周期T={t1,t2,…,tK}以及任意无源节点i在不同时间槽tj∈T 获取的能量μi(tj);

6.无源网络所监控的监控区域R={φ1,φ2,…,φm}以及每个监控区块φj∈R的权值wj和面积aj;

输出:一个具有最大覆盖质量的全局覆盖C={Ct|t∈T}.

以下定理证明了CR-MC-BFN 问题是NP-Hard 的.

定理1.CR-MC-BFN 问题是NP-Hard 的.

证明:显然,Shi 等人[2]所研究的问题MC-BFN 是CR-MC-BFN 问题在L=1 时的特例.因为MC-BFN 问题是NP-Hard 问题,所以CR-MC-BFN 问题也是NP-Hard 问题.□

3 CR-MC-BFN 问题的近似算法

因为CR-MC-BFN 问题是NP-Hard 的,我们在这一章提出了一个两阶段近似算法(two-phase approximation algorithm,简称TPA)对其进行求解.该近似算法分为两个阶段,这两个阶段简述如下.

•阶段1:节点工作预调度.在给定区域内基本能量分布(定义5)的情况下,为每个无源节点预分配传输半径,并给出每个无源节点的调度,从而最大化网络的覆盖质量;

•阶段2:节点工作自适应调度.根据节点的实际获能,对阶段1 中为节点预分配的传输半径和工作调度进行自适应式的微调,从而进一步最大化网络的覆盖质量.

在以下两节中,我们将详细地介绍这两个阶段.

3.1 阶段1:节点工作预调度

由于周围能源环境的变化十分复杂,对于一个无源节点,预测该节点在特定时间槽内的能量获取是十分困难的.但是根据能源环境的历史数据,我们可以很容易地预测每个节点可获取能量的最小值.因此,我们可以定义基本能量分布.

定义5(基本能量分布).给定无源节点集合V,监控周期T,一个基本能量分布E={μi|i∈V}满足对于任意μi∈E,μi≤min{μi(t)|t∈T}.

对于一个无源网络,基本能量分布可以从历史数据中很容易地得到.基于基本能量分布,我们可以对网络中节点的工作状态进行提前调度,从而减少节点分布式调度时的能量消耗.我们的节点工作预调度算法大致分为以下两个步骤.

•步骤1(节点集合划分算法):将无源传输节点分为k个不相交的集合D={D1,D2,…,Dk},为每个集合中的无源节点分配通信半径,使得对于任意Dj∈D,Dj∪S的导出图是连通的,并且最大化目标函数:

•步骤2(节点集合调度算法):调度步骤1 中的k个集合,从而最大化网络的覆盖质量.我们在以下两个章节中介绍这两个步骤中的具体操作.

3.1.1 步骤1:节点集合划分算法

步骤1 中主要存在两个问题:1) 如何确定k的具体值;和2) 如何分割节点并分配节点的通信半径,从而最大化目标函数.为了解决这两个问题,步骤1(见算法1)中按照如下子步骤进行.

Step 1(Line 1～Line 2):设k的最大值为kmax=max{(Δl/μj)|1≤l≤L∧μj∈E},最小值为

Step 2(Line 3～Line 18):对于任意k,且kmin≤k≤kmax,重复以下步骤.

(1) (Line 4～Line 5):对于每个无源节点i∈V,为其分配通信半径,其中,

需要指出的是:对于无源节点i而言,若不存在满足条件的通信半径等级时,则不考虑该节点.

(2) (Line 6～Line 17):设D1=D2=…=Dk=∅,并运行以下步骤.

3.1.2 步骤2:节点集合调度算法

设D={D1,D2,…,Dk}为步骤1 中的返回结果,则步骤2 按照如下构造全局覆盖:

对于任意时间槽(采样周期)tj∈T,如果jmod (k+1)=m,则Ctj=Dm,即

3.2 阶段2:节点工作自适应调度

在阶段1 当中,我们根据网络中的基本能量分布,对无源节点进行了预调度,并得到了一个全局覆盖C.然而,在阶段1 中所取得的全局覆盖的主要依据是每个无源节点的静态的基本能量分布.如果单独依赖阶段1 中的全局覆盖,则会造成节点存储能量无法充分利用的后果.因此在这一阶段,我们将根据网络中每个节点的实时能量获取以及节点自身所存储的能量,自适应地调度节点进行工作,从而最大化全局覆盖质量.

阶段2 包含以下两个步骤.

•Step 1:对于任意一个无源节点i∈V和任意的时间槽t∈T,如果i∈Ct,则i在时间槽内工作.

•Step 2:对于任意一个无源节点i∈V和任意的时间槽t∈T,如果i∉Ct,则i按照如下情况判断在时间槽t

内的工作状态:

(a) 如果∀1≤l≤L,都有Bi(t)−Δl+kμi

(b) 如果∃1≤l≤L,并满足以下两个条件:

则对于每一个满足该条件的l,为其分配权值wl=λ/Δl,其中,

这里,λ值表示如果将节点i加入Ct之后,可能继续加入Ct中的无源节点的个数.令满足条件(1)、条件(2)},并且调度节点i在时间槽t工作(即Ct=Ct∪{i}),通信半径为

这样,根据阶段1 和阶段2,TPA算法即可完成对无源节点的调度.该算法的时间复杂度、近似比将在下一章节给出.

3.3 TPA算法的性能分析

3.3.1 时间复杂度

在阶段1 中,共有kmax−kmin次迭代.在每一次迭代中,需要构造k个不相交的无源节点集合.构造无源节点集合的过程也需要进行迭代,并且并在每一次迭代中选取一个无源节点.因此,为了构造这些无源节点集合,需要进行最多|V|次迭代.同时,在每次迭代中需要计算每一个无源节点对应于不同的不相交节点集合的权值.这样,构造不相交无源节点集合的时间复杂度为O(k|V|2),其中,kmin≤k≤kmax.因此,阶段1 的时间复杂度为

在阶段2 中,在每一个时间槽内需要确定每一个无源节点的状态,判断该节点是否满足可以工作的条件.这样,至多有|V|个节点满足工作条件.对于每一个满足条件的无源节点,需要计算其权值,计算权值的过程的时间复杂度为O(L).这样,在阶段2 的时间复杂度为O(L|T||V|).

3.3.2 算法近似比

引理1.设为阶段1 的输出结果,且D为阶段1 中步骤1的输出结果,则有Q(C)=U(D).

证明:首先,根据阶段1 中Step 2 的通信半径构造方法,即对于任意无源节点i,其通信半径为,且li=max{l|,我们可知:若节点i可以在时间槽tj工作,则其工作后的能量满足.这样,无源节点i在tj+k时间槽的能量满足.这样,无源节点在tj+k时间槽一定可以工作.因此,根据覆盖C的构造,在集合Dm中的无源节点可以在时间槽tm,tm+k,tm+2k,…工作.

一般而言,|T|>>k,因此我们可以认为|T|>>nk,其中,n为正整数.这样,根据覆盖C的构造,覆盖C可被认为是集合D中的无源节点集合的循环工作.显然,在每一个循环中,其覆盖质量为U(D).这样,在n个循环后的覆盖质量为

定理2.设C,C′分别为阶段1 和阶段2 的输出结果,则有Q(C′)≥Q(C)=U(D).

证明:显然,在阶段2 中的节点调度并没有减少不相交无源节点集合D1,D2,…,Dk中的节点,因此我们有Q(C′)≥Q(C).又根据引理1,我们有Q(C′)≥Q(C)=U(D).□

引理3.给定一个k′值,我们定义问题P为:构造k′个不相交的无源节点集合D={D1,D2,…,Dk′},满足每个无源节点的通信半径,其中且每个集合中的无源节点与Sink 节点的导出图为连通图,并最大化U(D).设Do为该问题的最优解,D′为阶段1 返回的结果,则有

证明:在阶段1 中,会按照k值从kmin到kmax的顺序,根据贪心思想,迭代地构造不相交的无源节点集合,并选取目标函数值最大的k值.这样,对于阶段1 不同k取值所得到的目标函数值,我们有U(D′)=max{Uk|kmin≤k≤kmax},其中,Uk=U({D1,D2,…,Dk}),且D1,D2,…,Dk为阶段1 中当k值为k时的输出结果.

这样,当k=|Do|=k′时,我们有U(D′)≥Uk′.又因为目标函数U(⋅)对于任意k值都是次模的(引理2),这样,我们有从而有

根据Shi[2]中的定理4 和定理5,我们给出以下两个定理.在这两个定理中,我们将给出TPA算法的近似比.设Co为本问题的最优解,CA为TPA算法输出的解.

定理3.给定一个无源传感器网络的无源节点集合V和监控周期T,令:

证明:同样地,构造与定理3 中同样的全局覆盖,该定理可证.□

值得注意的是:与Shi 等人[4,5,26]的工作不同,我们的问题定义与TPA算法中并没有对网络拓扑和环境中能量源做出假设和特殊规定,所以TPA算法在理论上可适用于具有不同的拓扑结构和不同能量源的无源传感器网络,TPA算法在无源传感器网络中是一个普适的算法.

4 k-覆盖扩展

在以上章节中,我们认为:若一个监控区块被至少一个无源节点所监控,则该区块就被该无源节点所覆盖.然而在另一些场景中,由于环境更加恶劣,导致无源节点的可靠性降低.因此,对于任意一个监控区块而言,需要多个无源节点共同对其进行监控才可以实现完全覆盖,这种覆盖方式被称为k-覆盖[30].为了解决这一问题,在本节中,我们主要讨论如何扩展CR-MC-BFN 问题和TPA算法,使其可以解决在无源传感器网络中的k-覆盖问题.

在k-覆盖中,我们认为:在一个采样周期(时间槽)内,一个监控区块可以被覆盖当且仅当其被至少k个无源节点监控.显然,在k-覆盖中局部覆盖与全局覆盖的定义保持不变.然而,无源节点能量的不稳定性使得无源节点无法持续工作,k-覆盖的要求使得覆盖的难度加大,因此我们需要重新定义覆盖质量.

定义5(k-覆盖质量).给定一个全局覆盖C={Ct|t∈T},对于任意局部覆盖Ct∈C,其覆盖质量为

这样,通信半径可调整的无源传感器网络k-覆盖最大化问题(简称k-CR-MC-BFN)可描述如下:给定一个无源传感器网络,一个常数k,一片监控区域和一个监控周期,输出一个全局覆盖,最大化k-覆盖质量.

显然,CR-MC-BFN 问题是k-CR-MC-BFN 问题在k=1 时的子问题.因此,k-CR-MC-BFN 问题也是NP-难问题.为了解决k-CR-MC-BFN 问题,我们提出了k-TPA算法.k-TPA算法基于TPA算法,根据k-覆盖质量的定义,我们只需将TPA算法中的目标函数改为如下形式,而其他步骤则保持不变:

综上,我们就解决了在无源传感器网络当中的k-覆盖问题.

5 实验结果

5.1 朴素算法

在介绍实验结果之前,我们首先提出了如下基于贪心策略的朴素算法(naïve algorithm),用来与TPA算法进行对比.

该算法在任意时间槽t内构造局部覆盖Ct.在任意时间槽t,该算法将局部覆盖Ct初始化为空集(Line 3),并执行以下步骤.

Step 1(Line 4～Line 12):当Ct≠V,或存在V−Ct中的节点i,且Bi(t)≥Bf时,重复以下子步骤.

(1) 对于任意i∈V−Ct且Bi(t)≥Bf,设置节点i在时间槽t的通信半径为.这一步的目的是尽量减少无源节点的能量消耗;

(2) 对于满足步骤(1)中条件的无源节点i,如果集合Ct∪{i}∪S的导出图是连通图,则说明将无源节点i加入局部覆盖Ct后,覆盖的连通性可以得到满足,这样,为无源节点i分配权值:ui=Q(Ct∪{i})−Q(Ct);否则,为无源节点i分配权值ui=−1;

(3) 对于所有i∈V−Ct且Bi(t)≥Bf,选取权值最大的无源节点,并加入局部覆盖Ct当中.

Step 2(Line 13):将Step 1 中所得到的局部覆盖Ct加入全局覆盖C中.

Step 3(Line 14):根据基本能量分布更新无源节点的能量,即:对于i∈Ct,Bi(t+1)=min{Bi(t)+μi−Δ1,B};对于i≠Ct,Bi(t+1)=min{Bi(t)+μi,B}.在更新无源节点的能量之后,进行下一时间槽的局部覆盖的构造.

5.2 实验设置

我们采用模拟实验的方式来验证我们的算法.我们假设监控区域为一个50m×50m 的方形区域,监控周期最长为225 分钟,并被分为45 个时间槽,即每个时间槽为5 分钟.我们采用不同的无源节点来构成不同的无源传感器网络来验证算法.我们假设无源节点的能量存储空间B的大小在3mJ 到9mJ 之间,感知半径在3m 到7m 之间.此外,对于每一个无源节点,我们假设其通信半径具有5 个等级,分别为,且对于不同的通信半径等级,无源节点在一个时间槽的能量消耗满足:

同时,对于每一个无源节点,我们假设无源节点可以工作的最小的能量为3mJ,即Bf=3mJ.此外,我们假设每个无源传输节点在每个时间槽内可以从周围能源环境中获取0.1mJ～0.6mJ 的能量.这样,我们随机地部署200～1 000 个无源节点到监控区域当中,并构成若干个同构的无源传感器网络,并在这些网络中运行TPA算法来验证该算法的性能.

在下面的实验当中,我们将研究无源传感器网络中不同的系统参数值对于覆盖质量的影响.这些系统参数包括网络中节点的密度、周围能源环境的优劣、无源节点的感知半径、无源节点的能量存储空间、监控周期的长度以及能量获取速率不均衡程度.同时,为了保证实验的客观性,我们将TPA算法的实验结果与算法2 中的朴素算法以及Shi[2]提出的DSC算法在同样的实验环境下进行对比.DSC算法中,无源节点具有相同的通信半径,且无法自适应地调节自身的通信半径大小.DSC算法具有以下两个步骤.

•步骤1:将无源传感器网络中的无源节点根据节点的通信半径与感知半径分为k=Δ/μmin个不相交集合,并最大化无源节点对监控区域的覆盖率.其中,μmin为所有节点在单位时间槽内获取的最小能量.

•步骤2:无源节点根据实际的能量获取速率和被分配到的节点集合进行自适应地调度,从而进一步最大化节点对监控区域的覆盖率,提高覆盖质量.

5.3 不同系统参数对覆盖质量的影响

5.3.1 网络密度的影响

在这个系列的实验中,为了研究网络密度对覆盖质量的影响,我们模拟了6 种无源传感器网络,这6 个无源传感器网络的网络节点数量分别为100,200,300,500,700,1000.同时,我们假设在这6 种无源传感器网络中,无源节点的电量存储空间为6mJ,监控周期长度为40 个时间槽(200 分钟),每个无源节点在一个时间槽内最少获能为0.2mJ,感知半径为5m.在这6 种无源传感器网络中,我们分别运行朴素算法、TPA算法和DSC算法,并计算每个算法所得到的覆盖质量.实验结果如图3 所示.图3 展示了3 种不同算法在不同无源网络下所得覆盖质量的平均值、最大值和最小值.

Fig.3 Impact of number of nodes图3 节点数量的影响

根据图3,随着节点数量的不断增加,网络的节点密度不断增大,3 种算法所得到的覆盖质量都在不断上升.这是因为在无源节点的感知半径不变的情况下,增加网络节点的密度,会增加无源节点对监控区域的覆盖冗余,即同一块监控区域可以被更多的无源节点所覆盖.同时我们发现,TPA算法得到的覆盖质量远好于朴素算法和DSC算法.在大部分情况下,TPA算法所得到的覆盖质量的最小值均大于朴素算法与DSC算法在相同网络参数下的最大值.平均而言,TPA算法所得到的覆盖质量比DSC算法得到的覆盖质量高23.8%,比朴素算法得到的覆盖质量平均高98.7%.这是因为在TPA算法中,节点可以自适应地调整自己的通信半径,从而达到了更合理利用能量的效果,进而增加了节点工作的可能性,增加了网络的覆盖质量.

5.3.2 能量获取速率的影响

为了研究能量获取速率对全局覆盖质量的影响,在这一组实验当中,我们控制网络中的节点数量不变,将网络中的节点数量设置为200 个,将无源节点的感知半径设置为5m,设置Bf=3mJ,B=6mJ.根据这些系统参数,我们生成6 种无源传感器网络,在这6 组无源传感器网络中,我们让每个节点在单位时间槽内的最小能量获取从0.1mJ 不断增加至0.6mJ,从而来验证最小能量获取速率对覆盖质量的影响.同样地,我们在这6 组无源传感器网络中分别运行TPA、朴素算法以及DSC算法.图4 给出了这3 种算法在不同网络中覆盖质量的最大值、平均值和最小值.

Fig.4 Impact of the energy recharging rate图4 能量获取速率的影响

显然,当能量获取速率不断增加时,3 个算法所得到的覆盖质量都不断增加;且在不同的网络参数下,TPA算法所得到的覆盖质量的最小值均大于相同参数下的DSC 与朴素算法的最大值.当能量获取速率从0.1mJ 增加到0.6mJ 时,TPA算法所得到的覆盖质量增加了2.72 倍.另一方面,TPA算法所得到的覆盖质量在每种能量获取速率下均优于朴素算法和DSC算法所得到的覆盖质量.根据图4 中的实验结果,TPA算法的性能比DSC算法的性能高26.4%,比朴素算法高39.5%.

5.3.3 感知半径的影响

节点的感知半径是影响网络覆盖质量的重要因素.在这组实验中,我们构造5 组不同的无源传感器网络,在这5 组不同网络中的无源节点具有不同的感知半径,分别为3m,4m,5m,6m 和7m.同样的,我们设置网络中的其他参数分别为B=6mJ,Bf=3mJ,|V|=200,且每个节点在每个时间槽的最小获能为0.2mJ.在图5 中,我们展示了将3种算法在这5 组网络中分别运行后的统计结果,并记录了在不同网络下,3 种算法所取得的覆盖质量的最大值、最小值和平均值.

Fig.5 Impact of sensing radius图5 感知半径的影响

显然,当无源节点的感知半径逐渐增大时,3 种算法所取得的覆盖质量也不断增加.然而,我们同样发现,当节点的感知半径非常小,即为3m 时,3 种算法所得到的覆盖质量基本相同.但是,随着无源节点的感知半径逐渐增加,TPA算法所获取的覆盖质量迅速增加.当感知半径从3m 增加到7m 时,TPA算法所得到的覆盖质量增加了约4.3 倍.然而对于朴素算法,随着感知半径的增加,覆盖质量的增加速度并不高.根据实验数据的统计结果,TPA算法所获取的覆盖质量比朴素算法所获得的覆盖质量平均高45%,比DSC算法所得到的覆盖质量平局高30.4%.

5.3.4 能量存储空间的影响

显然,当无源节点配备较大的能量存储器件(一般为超级电容)时,节点可以工作更长的时间.为了研究不同大小的能量存储空间对全局覆盖质量的影响,我们考虑了7 种不同的无源节点,并根据这7 种无源节点构造了7组同构的无源传感器网络.这7 种不同的无源节点分别配备不同大小的能量存储器件,能量存储空间大小分布从3mJ 到9mJ.在构造的7 组同构的无源传感器网络中,网络节点数目均为200,无源节点在每个时间槽内的最小能量获取为0.2mJ,感知半径为5m,节点可工作的最小能量为Bf=3mJ.同样地,我在这7 组网络中分别运行TPA、DSC 和朴素算法,并记录3 个算法在不同网络下的覆盖质量的最大值、平均值和最小值.图6 中表示了这3 种算法的运行结果.

Fig.6 Impact of the size of B图6 B 值大小的影响

根据图6 中的实验结果,当能量存储空间不断增加时,朴素算法所取得的覆盖质量不断增加,而DSC,TPA算法所取得的覆盖质量随能量存储空间的变化并不明显.这是因为在DSC 和TPA算法构造覆盖时,并没有考虑能量存储空间;而朴素算法由于采用贪心算法,在监控周期的初始,十分依赖能量的存储空间.当能量存储空间从3mJ 增长到9mJ 时,TPA算法所取得的覆盖质量仅增加了约1.11 倍.因此,我们可以说TPA算法是不受能量存储空间所影响的.因此,对于不同的能量存储空间,TPA算法均可以保障稳定的覆盖质量.根据图6 中的实验结果,TPA算法的性能比DSC算法平均高31.9%,比朴素算法的性能平均高80.38%.

5.3.5 监控周期长度的影响

在无源传感器网络中,由于网络寿命在能量上来讲是无限的,因此,研究监控周期对网络覆盖质量的影响是必要的.在这组实验中,我们固定无源节点的参数,将无源节点的感知半径设为5m,能量存储空间设为6mJ,节点工作的最低电量为Bf=3mJ,在每个时间槽内的能量获取量为0.2mJ.同时,我们设置网络中节点的数量为200.为了研究监控周期的影响,我们将网络的监控周期从20 个时间槽不断增加到45 个时间槽,并在不同的监控周期下分别运行TPA,DSC 和朴素算法.图7 中记录了3 种算法在不同监控周期长度下的全局覆盖质量的最大值、最小值和平均值.

我们发现,TPA算法和DSC算法在任意长度监控周期下所取得的覆盖质量的最大值、平均值以及最小值的变化并不明显.这是因为TPA算法和DSC算法首先计算了k个节点集合,并在整个监控周期中不断调度同样的k个节点集合,这样,两种算法所取得的覆盖质量主要取决于这k个节点集合所获得的覆盖质量.相反地,由于朴素算法仅根据每个时间槽内的节点能量来调度节点工作,这就导致了当监控周期变长,节点初始能量被消耗殆尽后,所取得的覆盖质量不断降低.总体而言,TPA算法所取得的覆盖质量平均是朴素算法的覆盖质量的1.73倍,是DSC算法所取得的覆盖质量的1.36 倍.

Fig.7 Impact of the length of monitoring duration图7 监控周期长度的影响

5.3.6 能量获取速率不均衡程度的影响

能量获取速率的不均衡程度,是影响无源网络覆盖质量的重要因素.为了探究能量获取不均衡程度的影响,我们利用μmax−μmin的值来衡量能量分布的不均衡程度.其中,μmax,μmin分别为节点在一个时间槽内所获能量的最大值与最小值.在这组实验中,我们假设每个无源节点在单位时间槽内所获得的能量在[μmin,μmax]中随机变化.我们固定μmax=0.6mJ,并将μmin的值从0.6mJ逐渐减小到0.1mJ.显然,当μmax−μmin的值越大,节点的能量获取速率的不均衡程度就越严重.在这组实验中,我们固定网络中节点的数目为200,将无源节点的感知半径设为5m.

为了研究能量获取速率不均衡程度的影响,我们将μmax−μmin的值从0mJ 逐渐增大到0.5mJ,在不同的网络参数下运行TPA,DSC 和朴素算法,并记录3 种算法所取得的覆盖质量的最大值、最小值和平均值.实验结果记录在图8 中.

Fig.8 Impact of the energy deviation图8 能量偏移的影响

显然,根据图8 中的实验结果,我们发现,随着能量获取不均衡程度的逐渐加深,3 种算法说获得的覆盖质量不断降低,并且每种算法所取得的覆盖质量的最大值与最小值之间的差距也逐渐加大.当μmax−μmin的值从0 增加到0.5 时,TPA算法所取得的覆盖质量降低了越31%.这说明随着能量获取不均衡程度的加大,网络中节点工作状态更加不稳定.然而,我们也可以发现,TPA算法在不同的不均衡程度下所取得的覆盖质量均优于DSC算法与朴素算法.总体而言,TPA算法的性能比DSC算法的性能高20%,比朴素算法高30%.这是因为TPA算法在第二阶段中充分考虑了网络中能量获取不均衡时的情况,并自适应地调整了在阶段一中所得到的节点的调度,从而使得TPA算法在节点获能不均衡时,也能保障一定的覆盖质量.

6 总结

在本文中,我们提出了一个基于多等级通信半径的无源传感器网络中的覆盖问题.在这个问题中,无源传感器网络中的节点可以自适应地调整自己的通信半径,从而进一步合理地使用获取的能量.我们证明了该问题是NP-Hard 问题,并提出了基于贪心策略的TPA算法来解决这个问题.我们分析了该算法的时间复杂度,并证明了该算法具有一个合适的近似比.此外,我们还通过模拟实验来对算法的性能进行评估.为此,我们还提出了一个与TPA算法进行对比的朴素算法.基于我们的实验结果,我们验证了TPA算法的有效性和可靠性.在本文中,监控区域中环境能量源的基本能量分布主要基于历史数据.这一数据的准确与否,对于本文所提出的算法具有关键的影响.若该数据误差较大,则会影响无源节点的调度.在未来的工作中,我们将研究如何减少对周围环境能量源历史数据的依赖,从而进一步提高算法的性能与效率.