基于WSNs的部分覆盖应用的节点唤醒机制*

刘直良,宋三华

(黄淮学院信息工程学院,河南 驻马店 463000)

近期,无线传感网络WSNs(Wireless Sensor Network)已受到广泛关注,且在多个领域内使用,如环境监测、健康医疗以及战场勘测[1-2]。由于WSNs由低能的传感节点构成,无线网络性能和感测系统寿命是许多典型应用的关键。因此,优化能量消耗,提高网络寿命是WSNs的应用基础。

节点活动时期调度策略是提高节点能效的有效手段。即在满足覆盖要求时,将冗余节点步入休眠状态,进而降低能耗。此外,WSNs的全覆盖应用要求监测区域100%的覆盖,而一些其他应用只需要求部分覆盖。这就是所谓的部分覆盖问题[3-5]。例如,当WSNs应用于监测环境的湿度或温度时,只需90%覆盖。因此,通过部分覆盖调度策略可延长网络寿命,如图1所示。

图1 部分覆盖等级

图1描述了四级等级的部分覆盖(80%、50%、60%、90%)。将监测区域划分4个部分,每个部分的覆盖要求不同。其中B2要求90%覆盖,说明此区域是关键区域,而A2区域只需50%覆盖。如果能够控制传感节点的位置的话,可以在B2区域内部署多些传感节点,而在A2区域内部署少些节点,这样可以减少成本。然而,不幸的是,通常是很难控制传感节点位置。

为此,本文分析了WSNs的部分覆盖问题,并针对部分覆盖应用,提出基于学习自动机的节点休眠机制PCLA。PCLA机制充分利用学习自动机的优势去分配节点的活动和休眠状态,进而延长网络寿命。具体而言,先唤醒部分节点和学习网络覆盖图,构成主干网,然后这些节点激活邻居节点,进而满足网络覆盖和连通要求。实验数据表明,提出的PCLA机制能够有效地满足部分覆盖要求。

1 预备工作

1.1 网络模型

假定WSNs可由一个无向连通图表示,且命名为覆盖图CG(Coverage Graph)CG=(V,E),其中V={S0,S1,…,SN}为节点集。每个节点能够感测发生在它感测范围内的事件。假定节点的感测半径和通信半径分别表示为Rs和Rc,而E表示节点间的通信链路集[6]。对于每一对节点Si和Sj,如果Si和Sj均在彼此的通信范围内,则边(Si,Sj)∈E。此外,传感节点Si的感测区域表示为γi,其为以节点Si为中心以Rs为半径的圆。因此,节点Si的覆盖函数Ci(x,y)可定义为:

(1)

1.2 能量模型

引用图2所示的能效模型。向节点传输q比特的消息,且传输距离为d时,所消耗的能量表示为:

(2)

式中:Eelec、Efrris、Etworay均为传输能耗参数[7]。而dco的定义如式(3)所示:

(3)

式中:λ为波长、l为系统损耗。ht、hr分别表示发射天线和接收天线的增益系数。

相应地,对于接收q比特的数据包所消耗的能量:

ERX(q)=qEelec

(4)

图2 无线电能量消耗模型

1.3 学习自动机概述

学习自动机并不是遵循预定的规则,而是依据环境变化自适应调整。学习过程的结果就是调整。学习自动机LA(Learning Automata)就是从可行的动作集内选择最优的动作[8]。具体而言,学习自动机内含有若干个可操作的动作集。一旦某个动作被选中,并应用于环境,则产生一个增强信号。作用于环境后的响应作为反馈,并更新动作概率矢量。通过不断的迭代,学习自动机就能够选择最优的动作。学习自动机与环境的相互作用示意图如图3所示,其中a(n)表示动作集,而β(n)表示输出集(增强信号)。

图3 学习自动机作用于随机环境的示意图

2 PCLA机制

提出PCLA机制的目的在于以最少的活动节点满足网络覆盖要求。首先激活并建立节点集,并由这些节点构成主干网络,同时保证这些节点间的连通。然后,检测部分覆盖是否满足,如果不满足,就激活部分节点,进而满足部分覆盖。PCLA机制由学习阶段和部分覆盖阶段两阶段组成。

2.1 学习阶段

学习阶段的目的在于激活部分节点构成主干网。首先,在网络内广播HELLO消息,其包含了Ps、Pth和Tk信息。其中Ps表示监测区域所要求的覆盖比例。而Pth为门限值,表示LA所选择动作概率的最大值。Tk表示迭代算法的执行次数。一旦接收了此消息,每个节点就获取这些参数,并建立CG。

令Ψ为PCLA机制建立的节点集,并不断地进行迭代更新。对于每个节点,每个动作αi就是将节点Si添加到Ψ。而动作概率矢量p(n)初始定义为:

(5)

式中:pi(n)表示节点Si的动作概率矢量,而r表示动作集数,在数值上其等于初始阶段的邻居节点数。例如,如果节点Si有5个邻居节点,则节点Si的动作概率矢量初始地设置为{0.2,0.2,0.2,0.2,0.2}。

初始阶段完成后,就先随机地选择一个节点(假定是节点Si)加入Ψ。节点Si为了形成动作集,先向其邻居传播DISCOVERY消息。一旦接收到此消息,节点就向Si回复消息。因此,节点Si就依据所接收到的回复消息构成动作集。动作集尺寸的大小取决于节点度和网络密度。

值得注意的是:随机选择的节点可能位于不同覆盖等级区域。如果选择的节点位于覆盖等级要求低的区域,则只需在Ψ中添加少量节点就可满足覆盖要求。反之,若选择的节点位于覆盖等级要求高的区域,则需要添加更多的节点,才能满足覆盖要求。详情见3.2节中的算法1。

当节点Si完成了动作集后,再依据它的邻居节点的动作概率矢量p(n),选择一个节点加入Ψ,而没有被选中的节点归纳为Γ集。当某一个邻居节点被选中,并加入Ψ后,该节点又重复上述过程,并从非Γ集中选择它的邻居节点加入Ψ。此过程一直重复,直到满足Ψ∪Γ=V。若满足Ψ∪Γ=V,则说明在CG内的每一个节点要么属于Ψ要么属于Γ。

如果没有动作可选(例如,所选节点的所有邻居节点已经包含在Ψ或Γ,并且Ψ∪Γ≠V)。在这种情况下,选择过程需暂停,并重新地随机选择一个节点,重新开始上述过程,直到Ψ∪Γ=V。

一旦构成了节点集,就开始评估Ψ的适应性(suitability)。在每一轮n,集Ψ内的节点数与门限值Tn进行比较。如果|Ψ|

在前者情况中,集Ψ每个节点向它的活动邻居节点广播REWARD消息,再依据式(6)更新动作概率矢量:

(6)

式中:pj(n)表示动作pi(n)的概率。

相反,在后者情况中,就向Ψ集内的活动节点广播惩罚PENALTY消息。一旦收到PENALTY消息,所选动作的概率固定,同时依据式(4)更新动作概率矢量:

(7)

式中:r表示动作数。

更新后,就检测是否满足式(8)的条件。如果满足,就结束学习过程[9]。

(8)

师：说的很好，他在描述这6个面的时候，注意到了从这6个面的形状、大小和位置关系的角度去描述．那12条棱和8个顶点呢？

图4描述了自动学习过程,监测区域内部署了16个传感节点。在最初,随机选择节点S7加入Ψ,然后节点S7就依据动作概率矢量,选择一个邻居节点(S6)加入Ψ。此过程一直重复,直到区域内的所有节点要么在Ψ集内,要么在Γ集内。从图4可知,节点S10、S15在第1轮周期内被选择加入Ψ集内。

因此,集|Ψ|的基数等于4。然后计算Ψ集的节点的剩余能量EΨ。如果EΨ大于当前门限值En,就发送REWARD消息,否则就发送PENALTY消息。一旦收到REWARD消息或PENALTY消息,就依据式(3)或式(4)更新动作概率矢量。

图4 学习阶段

2.2 部分覆盖阶段

学习阶段结束后,PCLA机制就检测是否满足部分覆盖PCO(Partial Coverage)。如果满足PCO条件,就取消FormPartialCoverage()函数的执行。此函数就是激活集Γ的节点去满足PCO的要求,同时估计由集Γ活动节点所能覆盖的元(覆盖的单位区域)数[7]。具体而言,如果节点能够覆盖一个元,且没有其他邻居节点覆盖此元,该节点就被激活。因此,就向该节点发送激活ACTIVATION消息。FormPartialCoverage()函数的伪代码如算法1所示。

图5 算法1的伪代码

此外,图6描述了PCLA机制中的PCO示例。以图4为例,假定学习阶段所提供的节点集不能满足覆盖要求[10],因此,需要添加节点去实现PCO。从图6可知,激活了传感节点S4和S12。

图6 PCO示例

3 性能仿真

3.1 仿真参数及性能指标

为了更好地分析PCLA性能,选择文献[11]所提出的CDS机制和文献[12]所提出的DFS机制作为比较,并进行同步仿真。

3.2 实验1

图7 平均区域覆盖度Dϑ对节点工作率的影响

从图7可知,随着平均区域覆盖度Dϑ的增加,节点工作率φ呈下降趋势。与CDS和DFS算法相比,提出的PCLA机制的工作率φ得到有效地下降,这有利于网络能效的提高。这要归功于PCLA机制尽可能选择少数节点组建主干网络,降低了节点的工作时间。此外,也注意到,当Dϑ=1.5上升至Dϑ=5时,工作率φ得到显著地下降。

3.3 实验2

本次实验分析Ps对活动节点数的影响,且Ps从0.6至0.9变化,实验数据如图8所示。

图8 活动节点数

正如所期望的,3个机制的活动节点数随Ps的增加而上升。原因在于:Ps越大,越需要更多的节点监测兴趣区域。此外,与CDS和DFS相比,提出的PCLA机制的活动节点数得到有效控制,且随着Ps的增加,优势越明显。

图9 网络寿命随Dθ的变化情况

3.4 实验3

最后,分析各机制的网络寿命。其中网络寿命是指从部署网络的时间至网络覆盖首次未满足要求的时间,实验数据如图9、图10所示。

从图9、图10可知,PCLA机制的网络寿命高于CDS和DFS,且比CDS提高的幅度从15%至52%变化。而比DFS的网络寿命提搞了约34%至86%。从这些数据说明,提出的PCLA机制通过自动学习算法优化了节点休眠时间,减少了活动节点数,进而提高了网络寿命。

图10 网络寿命随PS的变化情况

4 总结

针对WSNs的部分覆盖问题,提出基于学习自动机的节点唤醒机制PCLA。PCLA机制先利用学习自动机建立主干网,然后基于部分覆盖要求,唤醒部分节点,进而满足覆盖要求。实验数据表明,提出的PCLA机制能够有效地减少活动节点数,并降低能耗,进而延长网络寿命。

参考文献:

[1] Muruganathan S D,Ma D C,Bhasin R I. A Centralized Energy-Efficient Routing Protocol for Wireless Sensor Networks[J]. IEEE Radio Communications,2011,43(3):8-13.

[2] 陈东海,李长庚. 基于簇头功能分化的无线传感器网络成簇算法[J]. 传感技术学报,2015,28(2):244-248.

[3] 沈艳霞,薛小松. 无线传感网络移动信标节点路径优化策略[J]. 传感器与微系统,2012,31(12):42-46.

[4] Zhao F,Liu J. Collaborative Signal and Information Processing:An Information Directed Approach[J]. Processing IEEE,2013,91(8):1199-1209.

[5] Botta A,de Donato W,Persico V,et al. On the Integration of Cloud Computing and Internet of Things[C]//Proceedings of the IEEE International Conference on Future Internet of Things and Cloud(Fi Cloud),2014:23-30.

[6] Qianqian Y,Shibo H,Junkun L,et al. Energy-Efficient Probabilistic Area Coverage in Wireless Sensor Networks[J]. IEEE Trans Veh Technol,2015,64(1):367-377.

[7] Botta A,de Donato W,Persico V,et al. Integration of Cloud Computing and Internet of Things:A Survey[J]. Future Gener Comput Syst,2016,3(56):684-700.

[8] Mostafaei H,Montieri A,Persico V,et al. An Efficient Partial Coverage Algorithm for Wireless Sensor Networks[C]//2016 IEEE Symposium on Computers and Communication(ISCC)(ISCC2016),Messina,Italy,2016:501-506.

[9] Mostafaei H,Shojafar M. A New Meta-Heuristic Algorithm for Maximizing Lifetime of Wireless Sensor Networks[J]. Wirel Pers Commun,2015,82(2):723-742.

[10] Liao Y,Qi H,Li W. Load-Balanced Clustering Algorithm with Distributed Self-Organization for Wireless Sensor Networks[J]. IEEE Sens,2013,13(5):1498-1506.

[11] Donghyun K,Yiwei W,Yingshu L,et al. 2009. Constructing Minimum Connected Dominating Sets with Bounded Diameters in Wireless Networks[J]. IEEE Trans Parallel Distrib Syst,2016,20(2):147-157.

[12] Wu Y,Ai C,Gao S,et al. p-Percent Coverage in Wireless Sensor Networks,vol.5258 of Lecture Notes in Computer Science[J]. Springer Berlin Heidelberg,2014,3(6):200-211.