能量采集无线传感网络中的概率目标覆盖问题

张 磊 王 然

(杭州电子科技大学计算机学院 浙江 杭州 310018)

0 引 言

网络生命周期用于评估已部署的无线传感网络在满足其应用需求的情况下能够正常工作多长时间，是无线传感网络中一个重要的研究话题。在以前，传感器节点主要是由普通的不可充电的电池供电。这种不可充电的普通传感器节点只有有限的运行时间，当传感器处于休眠状态时，电池的电量并不能得到恢复。近些年来，能够从环境能源中获取能量的可充电传感器节点开始被越来越多地应用到无线传感网络中[1]，可以明显地延长网络生命周期。理论上讲，无线传感网络中可充电节点越多，网络的生命周期越长。但是，由于可充电节点的制作成本比普通传感器的成本要高得多，因此在大型的无线传感网络中全部部署可充电节点是不现实的。一种可行的方法是部署由普通传感器和可以充电的传感器组成的混合无线传感网络[2]。为了充分利用可充电节点的优势，需要对混合无线传感网络中的传感器进行合理的调度。

文献[3]把延长网络生命周期问题建模为最大覆盖集问题，并证明了该问题是NP-Complete问题，同时利用线性规划和贪心策略设计了两种有效的启发式算法。文献[4]把目标连通覆盖问题建模为一个最大覆盖树(MCT)问题，并证明了该问题是NP-Complete的，同时提出了一种有效的快速启发式算法。文献[5]针对k-覆盖和Q-覆盖问题提出了一种使网络寿命最大化的节能方案，通过动态更新传感器的优先级形成不同的覆盖集合，从而延长网络寿命。文献[6]给出了定向传感网络的最大覆盖集问题，并提出了一个基于贪心算法的目标覆盖调度方案，在此基础上又提出了一种基于遗传算法的目标覆盖调度方案，实验表明基于遗传算法的调度方案能更好地延长网络生命周期。文献[7]首次提出了在定向传感网络(DSN)中传感器功率可调的最大网络生命周期问题(MNLAR)，并提出了两种启发式算法来解决这个问题。由于传感器随机部署可能满足不了目标的覆盖要求，文献[8]提出了移动传感器部署的问题(MSD)，通过最小化传感器的移动距离来延长网络生命周期。

上述研究工作的传感器监测模型都是基于0/1圆盘模型，该模型只是对实际监测模型的粗略近似，相较于0/1圆盘模型，概率监测模型能够更好地反映真实环境中传感器的监测情况。文献[9]研究了基于概率监测模型下的栅栏覆盖问题，并引入了流图的概念，在此基础上提出了一种解决多项式时间调度问题的近似算法。文献[10]采用概率监测模型来解决连通目标覆盖问题(CTC)，并提出了一种有效的启发式算法CWGC-PM来延长网络寿命。文献[11]也是基于概率监测模型解决连通目标覆盖问题，与文献[10]不同的是文献[11]是通过图论的方法把连通目标覆盖问题映射成一个流图，并提出了一个有效的近似算法。

近年来，能量采集技术被应用于无线传感网络中，将环境能量转换成电能，可以有效地延长网络寿命[12]。文献[13]提出了在能量采集无线传感网络中的永久性目标覆盖问题，并证明了该问题是NP-Complete问题，同时设计了一个有效的多项式算法来解决该问题。文献[14]首次解决了在能量采集无线传感网络中的连通目标覆盖问题，文中提出了两种解决方案，第一种是基于线性规划的直接求解，第二种是基于贪心策略的启发式方法。文献[15]提出了一个关于能量采集传感器节点部署位置的新问题，他们的目标是通过确定部署位置，最小化放置传感器节点的数量，使网络满足连通目标覆盖的同时保证每个节点的能量收支平衡。文献[16]研究了由普通传感器和太阳能传感器组成的混合无线传感网络的最大生命周期问题，文中提出了一种可信信息覆盖模型，并设计了一种基于优先级的贪婪调度算法(PGS)，但他们并没有考虑网络的连通以及传感器的剩余能量对网络寿命的影响。

与现有工作不同，本文研究的是在概率监测模型下，由普通传感器和太阳能传感器组成的混合无线传感网络的最大生命周期问题。本文的工作旨在满足连通目标覆盖的同时，尽可能地延长网络寿命。本文考虑了不同的光照强度以及传感器的剩余能量对网络寿命的影响，充分利用了网络中分布不均匀的能量。

本文的主要贡献如下:

(1) 首次探究了在由普通传感器和太阳能传感器组成的混合无线传感网络中基于概率连通目标覆盖下的最大生命周期问题，建立了非线性整型数学模型。

(2) 证明了该问题是一个NP-hard问题，并通过图论的方法设计了一个近似算法。该算法选择唤醒剩余能量更充足且对整个网络贡献更大的节点，因此能够更有效地利用环境能源。

(3) 进行了一系列仿真实验验证了本文算法的有效性。

1 模型与问题定义

1.1 传感器监测模型

传感器的监测模型采用文献[17]中给出的指数衰减概率监测模型，如式(1)中所示。目标的监测概率是与目标跟传感器之间的距离有关的递减函数。

(1)

式中：λ表示与传感器物理特性相关的强度系数；di,j表示传感器i和目标j之间的距离；Rs表示传感器的监测半径。

假如任意一个目标，它的监测概率要求不小于ε，那么对于被传感器集合St所监测到的目标t来说，满足式(2)。

(2)

对式(2)做如下变型:

(3)

由式(3)我们可以给出总监测阈值和传感器监测增益的定义：

定义1监测阈值：

Ψ=-ln(1-ε)

(4)

式中：Ψ表示目标需要满足的最低的监测增益要求。

定义2监测增益：

ψi,t=-ln(1-pi,t)

(5)

式中：ψi,t表示传感器si对目标t的监测增益。

1.2 数据通信与能量消耗模型

传感器监测目标时会持续产生监测数据，数据需要通过传感器传递给基站。在这个过程中，不同的传感器承担着不同的作用，有的传感器只作为监测节点，承担监测目标和传输数据的功能，有的传感器既要承担监测功能又要作为多个传感器节点的中继转发数据，能量消耗会比较高。节点的能量消耗大体可以分为三类，分别为监测数据能耗、传输数据能耗和接收数据能耗。假设监测节点单位时间产生的监测数据为μbit，li,j表示传感器si是否与传感器sj通信，传感器节点单位比特数据产生的监测能耗、传输能耗和接收能耗分别表示为es、et和er，Ωs和Ωr分别表示为监测节点集合以及中继节点集合。我们给出传感器节点的数据通信及能量消耗模型，如式(6)、式(7)所示，fi表示传感器si单位时间内需要转发的数据流量，ei表示传感器si单位时间的能量消耗。

(6)

(7)

1.3 能量采集模型

目标区域由太阳能传感器和普通传感器混合部署，不同的太阳能传感器由于接收光的位置、天气和障碍物的阻挡，导致其所对应的光照强度不同，所以单位时间内收集到的能量也不同。我们使用的是同构的太阳能传感器，不同的太阳能传感器ri在单位时间内收集到的能量可由式(8)表示。

Ei=ω·τ·ξ·δi

(8)

式中：ω表示太阳能电池板的能量转化率；τ为太阳能电池板的表面积；ξ为太阳能节点的充电效率；δi为太阳能辐射强度。

1.4 网络模型

我们在一个长度为L、宽度为W的矩形监测区域中，随机部署N个普通传感器和M个能够收集环境能源的太阳能传感器，所有传感器位置的集合分别为Sc={c1,c2,…，cN}和Sr={r1,r2,…，rM}。同时，随机部署D个需要被监测的目标，目标位置的集合为A={a1,a2,…，aD}，Sc∩A=∅且Sr∩A=∅。

在监测区域中，存在一个基站o，用于收集所有监测节点所监测到的目标信息，每个目标需要达到最低的概率覆盖要求，同时每个监测节点需要直接或间接地与汇点保持通信(通过中继节点)。

1.5 问题定义

本文主要研究由太阳能传感器和普通传感器组成的无线传感网络的网络生命周期问题。每轮从随机部署的太阳能节点集合Sr和普通节点集合Sc中选择部分节点工作，使A中的每个目标满足最低的概率覆盖要求，且整个网络保持连通。通过K轮的传感器睡眠-唤醒调度，得到其所对应的工作周期集合为{t1,t2,…,tK}，我们的目标是使T=t1+t2+…+tK最大。

本文问题可表示为如下非线性0-1整数规划问题：

(9)

s.t.

0≤Bi≤B∀si∈S

xi∈{0,1}，yi∈{0,1} ∀i=1,2,…，N

li,j∈{0,1} ∀i=1,2,…，N∀j=1,2,…，N+1

mi∈{0,1} ∀i=1,2,…，N

式中：Bi表示传感器si的剩余能量。Bi的计算如下：

Bi=min{(Bi-xi·(ei·tk+yi·Ei·tk)),B}

(10)

yi=0时表示传感器si是普通传感器；yi=1时表示传感器si是太阳能传感器；xi=0时表示传感器si是睡眠状态；xi=1时表示传感器si是被唤醒状态。mi=0时表示处于唤醒状态传感器si不是监测节点，即不执行监测功能；mi=1时表示处于唤醒状态的传感器si是监测节点，即执行监测功能。

式(9)中各约束分别表示：各个传感器的总能量约束、各个状态下传感器的能量约束、任何目标都要满足覆盖要求、任意传感器的收发数据量守恒、到达基站的数据流量与监测目标产生的数据流量相等。

定理1能量采集无线传感网络中概率目标覆盖的最大生命周期问题是NP-hard问题。

证明：在文献[17]中，作者首次提出了以最大化网络生命周期为目标的连通目标覆盖(CTC)问题，并通过将该问题建模为一个最大覆盖树(MCT)问题，证明了其NP完全性。本文研究的是在异构传感器网络中，基于概率覆盖模型下以最大化网络生命周期为目标的连通目标覆盖问题。当太阳能传感器在网络中的能量收集率Ei等于0、目标的监测概率要求ε=e-λRs时，本文研究的问题就转化为文献[17]中的CTC问题，同构连通目标覆盖是异构概率连通目标覆盖的一种特殊情况，因此，能量采集无线传感网络中概率目标覆盖的最大生命周期是NP-hard问题。

2 问题转化与算法

2.1 问题转化

我们通过网络中不同类型的传感器与目标以及汇点之间的抽象关系构建了图P=(S∪A∪{s}∪{t},E)，如图1所示。其中：S表示传感器集合；A表示目标集合；s表示一个虚拟点；t表示汇点(基站)；E表示边的集合。

图1中有三种代表不同关系的边：

(1) 虚拟边：任意目标与虚拟点s相连通的边，边的容量设置为Ψ。即∀ai∈A,∈E，的容量等于Ψ。

(2) 监测边：任意传感器与其监测范围内的目标相连通的边，边的容量设置为ψi,j。即∀si∈S,∀ai∈A，如果di,j∈E，且的容量等于ψi,j。

(3) 通信边：任意传感器与其通信范围内的传感器或者汇点相连通的边，边的容量设置为+∝。即∀si∈S,∀sj∈S∪{t}，如果di,j∈E，且的容量等于+∝。

定义3节点的权值：

(11)

式中：wi表示在网络流图中代表传感器si的节点i的权值。

定义4最优权值最大流问题：在本文构建的网络流图P=(S∪A∪{s}∪{t},E)中，寻找权值最小的节点集合C⊆S，使得子图P′=(C∪A∪{s}∪{t},E′)的最大流等于D·Ψ。

2.2 MOWMF算法

最优权值最大流问题的目的是在每一轮传感器选择的过程中寻找有充足剩余能量的传感器组合，同时保证网络连通和覆盖的要求。通过解决多轮最优权值最大流，得到多种传感器睡眠-唤醒调度策略，使网络生命周期得以延长。

针对最优权值最大流问题，本文使用了一种基于FindPathEx增广路径搜索算法的网络流算法，其与传统的网络流算法最大的不同就是在于寻找增广路径的方法。FindPathEx增广路径搜索算法的主要思想是每次都寻找比值ρ最大的增广路径：

(12)

在这种选取策略下，那些流值较大、新增节点的权值较小的路径将会被优先选取出来。根据之前定义的节点的权值可以知道，节点的权值越小，说明节点的剩余能量越大，即节点的能量消耗更小，能量收集更大。这样的选取策略符合现实场景的需求，那些有着高能量收集效率的太阳能节点会被优先选取，能够充分利用环境能源。当ρ=0时，说明网络当前的流量就是最大流，再也找不到新的增广路径。

当我们通过网络流算法确定了合适的传感器集合之后，还需要确定传感器集合的工作时间。在本文中，我们采用了固定长度时间片的方式，让被选出的传感器工作一段固定的时间并更新传感器节点的权值，然后执行新一轮的网络流算法，选出新的合适的传感器集合。MOWMF算法流程如算法1所示。

算法1MOWMF算法

输入：传感器集合S=Sc∪Sr，目标集合A，基站t。

输出：生命周期T，传感器子集C={C1,C2,…，CK}。

1.生成网络流图P=(S∪A∪{s}∪{t},E)；

2.k=1；

3.Ck=∅；

4.sumflow=0；

5.调用算法2寻找一条增广路径o(s,t)，增广路径的流等于f；

6.iff≠0 then

7.sumflow+=f；

8.addTo(o(s,t),Ck)

/*把增广路径o(s,t)中的新增节点添加到集合Ck中*/

9.goto 5；

10.else then

11.ifsumflow≥D·Ψthen

12.C=C∪{Ck}；

13.tk=t0；

14.for each nodeiinCkdo

15.updateBiandwi；

16.ifwi≥1 then

17.tk=min(tk,Bi/ei)；

/*传感器的剩余能量不足以维持一个t0时间片*/

18.T=T∪{tk}；

19.k=k+1；

20.reGenerate(P)；

/*重新生成网络流图*/

21.goto 4；

22.return {T,C}；

FindPathEx增广路径搜索算法利用了优先级队列和广度优先搜索算法，在搜索时使用Node类来记录节点的信息。

class Node { intid; Nodepre; floatflow; floatweight; }

其中：flow表示路径中新增的流值；weight表示新增节点的权值；id表示搜索过程中节点的编号；pre表示前驱节点。在优先级队列中，拥有最大比值flow/weight的节点排在队首，通过每次弹出队首元素来寻找最优的增广路径。FindPathEx搜索算法流程如算法2所示。

算法2FindPathEx搜索算法

输入：P=(S∪A∪{t}∪{t},E)。

输出：增广路径o(s,t)，增广流f。

1.flow=0；

2.priorityQueueQ；

3.node=newNode(s)；

4.Q.push(node)；

5.whileQis not empty do

6.Nodenode=Q.pop()；

7.ifnode.id=tthen

8.flow=node.flow；

9.o(s,t)=getPath(node.pre)

/*根据node.pre计算增广路径o(s,t)*/

10.break；

11.v=node.id；

12.setvvisited；

13.for each neighborsiofvdo

14.ifinot visited andflowof>0 then

15.newNode=newNode(i)；

16.updateEnergy(i)；

/*更新节点的剩余能量*/

17.newNode.flow=min(flowof ,node.flow)；

18.newNode.pre=node；

19.Q.push(newNode)；

20.return {flow,o(s,t)}；

3 模拟实验

在本节中，我们模拟了一个由普通传感器和太阳能传感器组成的混合无线传感网络，所有的传感器均匀分布在随机部署了若干个目标的矩形区域中，区域面积固定在200 m×150 m。为了方便，我们把每个太阳能传感器的光照强度设置为[0,480] W/m2之间的随机数。通过一系列仿真实验对MOWMF算法进行了性能评估，并与其他相关算法进行了对比。表1为实验相关的仿真参数及其数值。

表1 实验参数

3.1 不同参数对算法性能的影响

我们通过改变相关的实验参数来探究不同因素对MOWMF算法的影响，这些参数包括了太阳能传感器所占的比例、覆盖要求、传感器的总数量等。对于所有的实验结果，我们均进行了100次模拟实验，最终取平均值。

在图2中，我们主要考虑的是太阳能传感器所占的比例对算法性能的影响。我们把目标数量固定在40，传感器的总数量为200～400，覆盖要求设置为0.8。可以看出，随着传感器总数量的增加，网络寿命也在延长，而在传感器总数量相同的情况下，太阳能传感器所占比例越大，网络寿命也越长。这是因为传感器数量越多，可以完成目标覆盖要求的传感器组合也就越多。另一方面，由于太阳能传感器可以收集能量，延长使用寿命，所以太阳能传感器所占的比例越高，网络寿命也就越长。

图3中显示了目标的覆盖要求对算法性能的影响。目标数量和传感器的总数量分别固定在40和300。可以看出，目标的覆盖要求越高，网络生命周期越短。这是因为随着覆盖要求的提高，平均每个目标需要被更多的传感器所监测，网络中被唤醒的传感器数目增多，传感器的能量消耗增加，从而使网络寿命变短。

3.2 与其他相关算法的比较

针对延长由普通传感器和太阳能传感器组成的混合无线传感器网络的网络生命周期问题，我们将MOWMF算法与文献[2]中提出的基于优先级的贪婪调度算法(PGS)以及基于优先级的随机选择算法(PRAN)进行了比较。由于这两种算法对应的模型与本文模型有一些差异，我们这里只采用其算法思想应用到本文的模型中。

我们把目标数量固定在40，传感器的总数量为200～400，太阳能传感器所占比例为20%，覆盖要求设置为0.8。如图4所示，在传感器数量以及太阳能传感器所占比例相同的情况下，MOWMF算法要优于另外两种。PGS算法是基于优先级的贪婪调度策略，该算法把传感器集合分为已被唤醒的传感器集合、未被唤醒的太阳能传感器集合和未被唤醒的普通传感器集合三类，每次都从优先级更高的集合中选择传感器。PGS并未考虑传感器的剩余能量，这样就容易导致在阴天或者夜晚太阳能光照强度很弱的时候使太阳能节点更快地耗尽能量。MOWMF算法是根据传感器的剩余能量、能量消耗、能量收集通过网络流的方法来选择更优的传感器节点。

图5统计了在不同的算法场景下传感器的平均剩余能量。可以看出，本文算法在算法执行完成之后传感器的剩余能量更少，能量利用率更高。这也进一步说明了MOWMF算法的有效性。

4 结 语

本文基于概率连通目标覆盖模型研究了在能量采集无线传感网络中的生命周期问题，经过分析发现该问题是一个NP-hard问题。为了解决这个问题，我们根据传感器的剩余能量、能量消耗和太阳能传感器的能量收集定义了传感器的权值，并通过图论的方法提出一个有效的近似算法。我们进行了一系列的仿真实验，比较了太阳能传感器所占的比例、传感器的总数量和覆盖要求等不同因素对网络生命周期的影响，并通过与相关算法的比较证明了本文算法的有效性。未来将考虑增大那些剩余能量较高的太阳能节点的工作功率，从而进一步提高环境能源的利用率。