WSN中利用广义学习自动机和休眠机制的部分覆盖方法

周剑敏，胡海刚，钱云霞

(1.浙江国际海运职业技术学院， 浙江 舟山 316021; 2.宁波大学， 浙江 宁波 315800)

无线传感器网络(wireless sensor networks，WSN)被广泛用于监测、医疗和环境监测等多个领域[1]。由于WSN节点自带的能量比较少，为此系统生存时间[2-3]是WSN应用中的关键问题。其中，寻找节点的最优位置、降低能量消耗是科研人员研究的主要方向。

区域覆盖问题可以分为全覆盖和部分覆盖(也称为百分比覆盖)[4-8]。全覆盖需要持续监测整个感兴趣区域，部分覆盖不需要全覆盖整个监测区域，只要保证网络的覆盖比例达到一定的值即可。部分覆盖中通过节点休眠机制，在保证服务质量的同时大量减少工作节点个数，从而延长网络的生命周期。

为了提高部分覆盖时WSN的网络寿命，学者提出了多种覆盖方法。例如，文献[9]中设计了一种分散覆盖方式，可以在监控网络区域的同时保持网络连通性，保证一定比例的覆盖。文献[10]中分析了期望的覆盖率和工作传感器的最小数量之间的关系，设计了能量感知部分覆盖协议，根据节点的剩余能量选择最小工作传感器数量。文献[11]提出一种完全分布式的方法，每个传感器节点不需要任何地理信息来寻找冗余节点，并把它们置于睡眠状态。但是，这些方法在时间复杂性方面的效果不是很理想[12]。连通支配集(CDS)是一种连通图，使得每个顶点要么在子集中，要么与子集中的顶点相邻。文献[13]提出在网络中创建CDS的虚拟主干。文献[14]为了解决WSN中部分覆盖问题，基于CDS构建网络，并结合了一种贪婪方法pPCA，构建一种以分布式方式运行的CpPCA-CDS算法。这种解决方案的主要缺点是依赖深度首次搜索(DFS)，严重影响时间复杂度(本文将CpPCA-CDS简称为DFS)。文献[15]提出了一种分布式自适应睡眠调度算法，每个节点使用剩余能量水平和汇聚节点的反馈来调度其邻居节点的活动。

本文提出了一种WSN中基于广义学习自动机(generalized learning automata，GLA)[5]的部分覆盖方法。其主要创新点在于：① 通过GLA来选择一组节点，构建能够满足预设约束的主干节点网络；② 根据网络覆盖要求和节点能耗，动态评估各休眠节点的覆盖能力，选择合适节点进行激活，实现以最少数量节点满足要求。仿真结果表明：提出的方法在激活的节点数和网络寿命方面有更好的性能。

1 网络模型

WSN可以通过一个无向连通图来建模，即CG=(V,E)。其中V={S0,S1，…,SN}包含所有随机部署的节点，每个节点的感测和通信范围分别定义为半径为Rs和Rc的圆。E表示节点之间的通信链路的集合。对于任意一对节点u和v，当且仅当u和v在彼此的通信范围内时，边(u,v)∈E。更确切地说，节点Si的感测区域γi定义为以Si为圆心、Rs为半径的圆。如果点(x,y)位于节点的感测区域，则点(x,y)被Si覆盖。那么，节点Si的覆盖函数Ci(x,y)可定义为：

(1)

(2)

其中j∈cells是区域划分的单元格之一。

那么，约束条件可以写成：

(3)

表1总结了网络模型中所用符号和定义。

表1 符号和定义

部分覆盖中根据检测区域的重要性，设置不同的覆盖范围，从而使WSN的使用寿命更长。图1显示了部分覆盖问题的示例,该感兴趣的区域分为9个单元，需要不同的覆盖水平。例如，第1个单元有一半的关键领域，覆盖要求为50%。

图1 具有不同覆盖率的WSN部分覆盖

2 广义学习自动机(GLA)

2.1 学习自动机

学习自动机(learning automata，LA)旨在从一组允许的行动中选择最佳行动，它使用由环境生成的答复来更新其动作概率向量。环境由一个三元组(α,β,c)表示，其中：α表示有限输入集合(动作)；β表示输出集合(强化信号)；c表示一组惩罚概率，每个元素ci对应于一个输入行为αi。变量结构学习自动机由(β,α,T)表示，其中：β表示输入集合；α表示动作集合；T表示学习算法。它实际上是一个概率向量，目的是修改以上所述动作的递推关系。

令αi(k)∈α，它表示经过LA后被选中的动作，p(k)表示在第k个循环处的动作概率向量。令a和b分别表示奖励和惩罚参数，其中奖励参数能判定动作概率值的增加数量，惩罚参数能判定动作概率值的减少数量。r是LA的动作次数。根据动作概率向量p(k)，自动机随机选择一个动作αi(k)，并在环境中执行。式(4)表示动作概率向量p(k)在αi(k)的奖励更新，式(5)表示动作概率向量p(k)在αi(k)的惩罚更新。当a=b时，式(4)和式(5)可以看作线性奖励-惩罚LR-P机制；当a≥b时，式(4)和式(5)可以看作线性奖励-ε惩罚LR-εP机制；当b=0时，式(4)和式(5)可以看作线性奖励-无为LR-I机制，此时，动作概率矢量不会因选定操作受到的惩罚而改变。

(4)

(5)

2.2 广义学习自动机

LA算法的优点是无需样本数据的先验知识，并且具有较强的抗噪声能力。但是，LA存在学习速度缓慢的问题。与此相比，广义学习自动机(GLA)是较快的一种，GLA是对传统LA结构进行修改，使其可以直接使用单个LA实现分类。

GLA利用(X,Y,R,u,g,T)等变量来描述，其中X表示输入集合，Y={y1,y2,…,yr}表示不同的类别，R表示强化信号，它的值有两种：0或1；u表示GLA的状态向量，g表示概率函数，T表示学习计划，其作用是更新u。GLA中的概率函数g和状态向量u将输入集合X变为动作Y的概率分布，如式(6)所示。

(6)

在GLA中，u(k)和x(k)的值决定了Y的概率分布。当系统给定一个概率函数g时，GLA的目标是要得到一个合理的u值，使得在所有样本向量通过概率函数g后所生成的动作概率分布中，较高的概率对应正确的动作。GLA中，对于某一时刻k，学习步骤如下。

1) 输入一个随机样本x(k)。

2) 根据由x(k)、u(k)和g生成的动作概率分布，选出一个动作α(k)∈Y作为环境的输出。

3) 在该环境中生成一个信号β(k)作为GLA的反馈，β(k)的值表示α(k)的正确与否，当β=1时，代表α(k)正确，当β=0时，代表α(k)错误。

4) GLA根据x(k)、u(k)、β(k)、α(k)以及T的值更新u(k)，得到u(k+1)。

令样本向量x⊂RN，当r=2时，u是一个N维向量，这种情况下，概率函数g用式(7)所示函数表示。

(7)

GLA学习得到最优的状态向量u，并根据它获得β的期望值f(u)=E[β|u]的最大值，T的选择如式(8)所示。

i=1,2,…,N

(8)

式(8)中，ui代表u的第i个维度，其初始值为u(0)=[0,0,…,0]T，λ代表步长。GLA沿着f(u)的梯度方向更新u(k)，得到u(k+1)。

3 基于GLA的有限区域覆盖方法

所提出方法的主要思想是首先确定一组节点来构建一个能保证所有节点之间连接的主干网。如果部分覆盖不满足，则激活其他节点。该方法包括两个阶段：主干节点网络构建阶段和节点调度覆盖阶段。

3.1 主干节点网络构建

该阶段的目的是选择数量有限的一组节点作为主干。这个阶段包括一个迭代过程，目的在于发现一个与预定义的约束匹配的主干节点集合。当选定的主干网满足约束条件或满足预定义的停止条件时，该阶段结束。

为了以分布的方式执行提出的方法，给出以下参数定义。

1)Ps，即感兴趣区域中覆盖范围的期望比例。

2)Pthreshold，Ψ集合中的每个节点上GLA算法选择动作的最大概率阈值，作为执行主干构建阶段的第1个停止条件。

3)Tk，算法的循环次数，作为执行主干构建阶段的第2个停止条件。

4)Γ，Ψ集合中未被选中的邻居节点组成的集合。

5)EΨ，Ψ集合中节点的平均剩余能量。

6)n，算法的周期数，用来检查停止条件。

7)Tn，在主干构建阶段的第n个周期，所选择的Ψ集合中节点数量的一个动态阈值，初始值为|V|。

8)En，在主干构建阶段的第n个周期中，所选择的Ψ集合中节点平均剩余能量的一个动态阈值，初始值为0。

这组全局变量是在初始化步骤开始时建立的，并在网络内广播包含Ps、Pthreshold、Tk值的HELLO消息。接收到这个消息后，在每个节点上启动初始化过程，并从CG获取一个信息以便知道节点的邻居。这是整个算法的一个关键步骤，因为它从网络的CG开始寻找合适的节点，最终的目标是满足部分覆盖的要求。

对于每个节点，每个动作αi表示将相邻节点Si添加到Ψ中。动作概率向量p(n)被初始化如下：

(9)

其中，r表示动作集计数，为初始化步骤中的邻居节点数量。例如，如果节点Si有5个相邻节点，则该节点的动作概率向量初始设置为{0.2,0.2,0.2,0.2,0.2}，这意味着节点Si有5个等概率的动作。

主干构建阶段的主要目标是在网络区域Aϑ中寻找冗余传感器节点。在每个节点上运行GLA有助于识别合适的主干。在初始化步骤之后，随机选择节点并添加到Ψ中。

每个传感器Si为了形成它的动作集，向它的邻居传播DISCOVERY消息。一旦接收到消息，每个节点就回复发送者Si，根据其从邻居接收到的消息来形成动作集。因此，每个节点上GLA的动作集大小取决于相应节点的网络密度，一个节点上的GLA根据它的行动概率向量p(n)来选择一个邻居，并添加到Ψ中，而其他未被选择的邻居被添加到另一个集Γ。然后，被选择的这个节点迭代这个选择过程。

这个过程一直持续到Ψ∪Γ=V。 注意，在这一步之后，CG中的每个节点都属于Ψ或Γ。在每个节点选择GLA的动作之后，它更新其数据结构(即全局变量的值)。在这个阶段，如果没有可用的动作，则选择过程被追溯并从另一个节点重新开始，以最终确保主干节点的成功选择。而且，在节点被选择之后，每个节点的GLA通过禁用与被选节点对应的动作来修剪其动作集合。这样就不能再选择已被选择的节点，避免了循环的产生，也提高了算法的收敛速度。

一旦确定了候选主干节点集合Ψ，就评估Ψ的适用性。在每个周期n，将Ψ中的节点数量与阈值Tn进行比较。如果|Ψ|

上述过程一直持续到停止条件满足为止。下面详细描述这个停止条件。首先，计算上一个周期中所选节点的概率。这个概率值Ps可被定义为在上一个周期中每个节点的GLA所选动作的概率的乘积。它可以计算如下：

(10)

主干构建阶段的算法流程如算法1所示。

算法1:基于GLA的区域覆盖执行过程

输入：

CG=(V,E)，网络连通图；Ps，期望的部分覆盖；α，行动概率向量更新的奖励参数；Tn，动态阈值；En，能量阈值。

输出：

Ψ，选择的节点；Γ，未选择的节点。

初始化：

在网络中广播HELLO消息；

ForV中的所有节点，执行：

Ψ=φ；

初始化Tk和Pthreshold；

发送DISCOVERY消息；

End for

重复执行

随机选择一个节点Si并激活；

重复执行

whileSi不活动时，则

激活的节点被追溯以找到具有可用动作的自动机；

End while

Ψ=Ψ∪Si；

Si根据其p(n)选择一个邻居节点Sj；

每个自动机修剪它的动作集以避免循环；

Sj被激活；

Γ=Γ∪未被选择的Si的邻居节点；

Si=Sj；

直到|Ψ∪Γ|<|V|；

计算EΨ；

if |Ψ|En，则

Tn=|Ψ|；

En=EΨ；

βi(n)=0 ∀i|Si∈Ψ；

向Ψ中所有被选中的节点发送REWARD消息；

else

βi(n)=1 ∀i|Si∈Ψ；

向Ψ中所有被选中的节点发送PENALTY消息

end if

当达到停止条件时，结束；

向Ψ中所有的节点发送ACTIVATION消息；

执行FormPartialCoverage()；

3.2 节点激活覆盖阶段

在主干构建阶段结束时，需要检查获得的主干网络是否满足部分覆盖要求。如果不满足，则调用FormPartialCoverage()函数。这个函数激活Γ中的休眠节点来满足部分覆盖的要求。具体而言，FormPartialCoverage()利用覆盖函数，并通过激活Γ中的每个节点来评估覆盖性能，以识别需要激活哪些节点，如算法2所示。

算法2:FormPartialCoverage()的执行过程

输入：

CG=(V,E)；Ps

输出：

Ψ；Γ

ForΓ中的所有节点Sj，执行

ifΨ不满足条件Ps，则

ifSj的邻居节点不能覆盖此区域，则

Ψ=Ψ∪Sj；

向Sj发送ACTIVATION消息；

else

停用Sj；

end if

end if

end for

4 仿真实验分析

4.1 仿真设置

文献[13]和文献[14]的方法都是利用覆盖图模型，通过不同算法来获得主干网络，实现WSN部分覆盖要求。其中，文献[13]提出的基于CDS的算法首先利用CDS算法构造CDS主干节点集，然后在应用中根据需求使用一些非CDS节点来满足部分覆盖。文献[14]则是利用CpPCA-CDS算法(DFS)来构建主干集。这些覆盖方法与本文方法的主体思想类似。因此，根据网络资源和覆盖要求，在NS-2仿真平台上比较了这3种方法的性能。

仿真中，在WSN内随机部署节点的总数为N，感兴趣区域的总面积Aϑ，每个节点的感测范围为Rs，通信范围为Rc，覆盖要求为Ps。假设所有节点的感测和通信范围相同，且每个节点的能量相对消耗为w。表2总结了仿真中使用的仿真参数和覆盖要求。其中，网络平均区域覆盖度Dϑ表示同时覆盖特定区域的多个节点的数量，覆盖度越高，数据可靠性越强。

表2 仿真参数及覆盖要求

4.2 结果分析

4.2.1平均区域覆盖度和覆盖要求与工作节点比例的关系

首先评估平均区域覆盖度Dϑ和覆盖要求Ps与工作节点数量比例φ的关系。定义3种不同的配置：Dϑ=4、Dϑ=3和Dϑ=2。此外，在3种不同的覆盖要求水平下测试了3种算法：Ps=0.6、Ps=0.8和Ps=1.0。

图2显示了当考虑到不同的覆盖要求(Ps=0.6、Ps=0.8和Ps=1.0)时，平均区域覆盖度Dϑ的变化对工作节点比例φ的影响。对于这3种算法，在同样的覆盖要求Ps下，φ随着Dϑ的增加而上升。这是因为在较高的覆盖度下，同一块区域需要多个传感器同时覆盖，为此所需的传感器数量较多。另外，当Dϑ=4和Ps=1时，并没有仿真结果，这是因为在这种配置下没有算法满足连接要求。

相同条件下，本文方法始终优于其他两种算法，所需的节点数量都是最少的，能有效延长网络的使用寿命。

图3显示当考虑到不同的平均区域覆盖度(Dϑ=4、Dϑ=3和Dϑ=2)时，覆盖要求Ps的变化对工作节点比例φ的影响。可以看到，在同样的平均区域覆盖度Dϑ下，φ随着Ps的增加而呈现上升趋势。这是因为覆盖面积要求的增加，需要激活更多的节点来满足严格的覆盖约束。

同样，在各种情况下，本文方法所需的节点数量都最少。因为其对节点执行了更高效的选择，并持续检查激活节点的适用性，直到满足部分覆盖要求。例如，当Dϑ=2，且Ps从0.8增加到1时，本文方法的性能降低的比例最小，所需工作节点数量的比例增长了12%，而CDS和DFS分别增长了约20%和30%。

图2 不同的覆盖要求Ps下，平均区域覆盖度Dϑ对工作节点比例的影响

图3 不同的平均区域覆盖度Dϑ下，覆盖要求Ps对工作节点比例的影响

以上仿真结果显示了本文方法可以更好地利用资源。当有更多的传感器可用时(例如Dϑ=2)，能获得比其他算法更好的性能，这是因为其使用最小可能数量的节点作为主干节点，以达到部分覆盖要求并保证它们之间的连通性。

4.2.2平均区域覆盖度和覆盖要求与网络寿命的关系

图4和图5比较了用不同的平均区域覆盖度Dϑ和覆盖要求Ps时3种方法的网络寿命。由图4、5可以看出：较大的平均区域覆盖度会使3种方法的网络寿命更长。相反，较大的覆盖要求会使3种方法的网络寿命变短。

本文方法能获得比CDS和DFS更长的网络寿命，在各种情况下的平均值上，平均寿命分别比CDS和DFS提高了16%和37%。因为本文方法通过GLA算法选择了具有较高覆盖能力的主干节点集合，并其在激活空闲节点时，选择了具有最小可能重叠的节点，因此需要更少的节点来满足覆盖要求。另外，在某些情况下，只需主干节点就能达到所需的覆盖要求，减少了活动节点的数量，并且保证在随后的周期中可以调度更多的空闲节点。而CDS和DFS算法在构建主干网络和激活空闲节点时，会存在较多的节点覆盖区域重叠情况，这就增加了节点数量，降低了网络效率。

图4 不同的覆盖要求Ps下，平均区域覆盖度Dϑ对网络寿命的影响

图5 不同的平均区域覆盖度Dϑ下，覆盖要求Ps对网络寿命的影响

5 结束语

为了解决WSN部分区域覆盖的问题，提出了一种基于广义学习自动机的有限区域覆盖方法。通过构建主干网络和自适应节点激活策略，使用最少数量的节点，使其能够覆盖感兴趣区域的所需部分，并保持活动节点之间的连通性。仿真实验结果显示：该方法在工作节点比率和网络寿命方面显示出更好的性能。在使覆盖范围更加严格的情况下，性能下降速度比其他解决方案更慢。