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

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

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={s 1 ,
s 2 ,…,s n }和一个无源节点集合 V={1,2,…,m}.无源节点均匀地分布在监控区域R.无源网络的监控周期为T,T可被
分为若干时间槽:{t 1 ,t 2 ,…,t K }.不失一般性地,我们将每一个时间槽当作网络的采样周期.
每个无源节点可以从周围能源环境中获取能量.我们设每个节点 i 在时间槽 t j 可获取的能量为μ i (t j ),同时设
所有无源节点都具有相同的能量存储空间 B.令 B i (t j )为无源节点 i 在 t j 时间槽开始时刻所存储的电量,显然,
B i (t j )≤B.根据 Zhang 等人 [27] 的研究工作,对于任意一个无源节点 i,它可以在时间槽 t j 工作,当且仅当 B i (t j )≥B f .
其中,B f 是保障节点可以工作的最低能量值.一个无源节点在一个时间槽(或采样周期)内可以进行感知、计算、
传输等工作,而在进行这些工作的过程中,无源节点同样需要消耗能量.我们假设:在每一个时间槽,每一个无源
节点的最大能量消耗为Δ [28] ,显然,Δ≤B f .这样,节点 i 在时间槽 t j+1 的电量可以表示为
(
j
Bt )≥ min{ , ( )B B t + x μ ( )t − Δ } (1)
i j+ 1 i j i i j
j
j
j
其中, x ∈ {0,1} 表示节点 i 在时间槽 t j 工作( x = 1)或者休眠( x = ).
0
i i i
不失一般性,我们假设所有 Sink 节点所导出的图为连通图,且所有无源节点具有相同的感知半径 r s .根据无
源节点的特性,我们假设节点可以自主地调整其通信半径的大小 [29] .设每个无源节点的通信半径 r c 具有 L 个等
1
l
级 r ∈ {, ,..., }r r c 2 r c L ,当节点的通信半径处于 l 级时,节点的通信半径为 r ,节点单位时间槽的最大能量消耗为Δ l ,
c
c
c
l′
l
[1]
[1]
且对于任意两个等级 1≤l<l′≤L,我们有 r < r ,Δ l <Δ l ′ .根据 Zhang 等人 的假设,我们设一般情况下 r ≤ 0.5r .
c
s
c
c
i l
对于任意两个无源节点 i,j,如果它们之间的距离 dis(i,j)满足 dis (, )i j ≤ min{ ,r r c j l } ,则我们认为 i,j 之间可以进行
c
有效的通信.这里,l i ,l j 为节点 i,j 通信半径的等级.我们设 r c (i,t)为无源节点 i 在时间槽 t 内的通信半径.
给定一个监控区域R,R可以表示为所有无源节点监控区域的集合 R = ∑ R ,其中,R i 是无源节点 i 的监
∈
iV i
控区域.一般地,我们认为R i 是一个以 i 的位置为圆心、r s 为半径的圆形区域.为了更好地评估对监控区域的覆
盖效果,我们再根据节点的感知半径将监控区域R离散化为若干不同的区块,并为每一个区块分配一个 0 到 1 之
间的权值.区块的权值表示了区块的重要程度,比如,对于一个部署在森林当中、监控森林火灾的网络而言,更加
干燥的区域就需要分配给较高的权重.一个区块的具体定义如下.
定义 1(监控区块). 给定一个监控区域R,R可以被划分为若干不同的监控区域,R={φ 1 ,φ 2 ,…,φ k }.对于任意
一个监控区块φ i ∈R,φ i 需满足以下条件:
(1) φ i 具有一个在 0~1 之间的权重 w i ;