有向感知可充电传感器节点的动态激活策略*

胡 洁,兰玉彬

(1.华南农业大学电子工程学院,广州 510642;2.华南农业大学工程学院,广州 510642)

无线传感器节点及网络在工业过程、医疗护理和智能电网等诸多领域得到了广泛应用,尤其是在环境监测领域被重点关注;然而,由于监测周期长且覆盖面积广,往往存在节点能量消耗不均,网络寿命短等问题。已有很多研究致力于提高电池能量的有效利用以延长网络生命期,但没有从根本解决WSN的能量供给问题。监测环境往往地形复杂,位置偏远,导致更换节点电池费时费力,在一些环境下甚至是不可能的。在不能更换电池的情况下,只有低成本的传感器节点才能在现实中大规模的铺设和一次性使用后丢弃;同时,被丢弃的节点不能有害于生态环境,也即不能使用锂电池或镉电池。种种限制阻碍了WSN在环境监测中的应用。

在这种背景下提出的能量采集技术[1]将环境中的太阳能,风能,水能甚至是无线电磁波的能量转化为电能,提供了一种有效解决WSN的能量限制问题的方法。近年来,已有一些研究将能量采集无线传感器网络投入到实际的环境监测应用中[2-6]。在这些应用中,节点的激活策略是在采集能量的基础上,合理调度节点的激活和休眠以完成监测任务的关键。在能量采集系统中,由于节点的剩余能量不是单调递减的,每个时段的剩余能量跟采集有关,而采集的能量往往具有随机性,所以节点的激活-休眠周期安排不能沿用电池供电的WSN的方法。文献[7]介绍了在太阳能供电的WSN中采用基于强化学习的休眠机制来实现区域的覆盖;文献[8]设计了一种基于采集能量感知的自适应采样机制;文献[9]为采集太阳能的同构节点设计了一种最大化系统效率的简单激活机制。文献[10]通过对太阳能采集节点的动态激活和感知距离调整来最大化24 h内的最低覆盖质量指数;文中提到了传感器节点的全向感知范围和扇形感知范围,但在算法中只考虑调整感知的距离,并不调整感知方向。而随着传感器技术的进步,传感器节点趋于多样化,视频传感器、超声传感器、红外传感器等具有方向性的传感器节点的应用越来越多。相比传统的全向感知节点,有向感知传感器节点当其感知方向可调时,节点的激活策略可以获得更大的自由度,但同时也导致计算更复杂。文献[11]假定传感器节点可以在360°的方向上随意转动,设计了一种启发式算法将节点划分为多个不交叉的感知集,并为这些感知集分配工作时间,以此在达到覆盖要求的条件下延长网络生命期。文献[12]提出的覆盖方法在满足不同目标覆盖率要求的前提下,最大化网络生命期,该方法适用于感知距离、方向及覆盖角度异构的感知节点。文献[13]针对有向传感器网络全覆盖问题,基于有向传感器节点概率感知模型提出一种新的有向传感器节点部署结构。到目前为止,鲜有文献涉及能量采集型有向感知节点的激活和覆盖问题。

笔者为采集能量的有向感知传感器节点设计了动态激活及感知方向调度策略,以获得最大的系统平均监测成功率;算法采用了多项式时间的解决方法,并至少能获得最佳激活算法50%的监测成功率。

1 系统模型

本文采用跟文献[14]类似的充放电模型。假定所有传感器节点具有同步时钟,节点有激活,休眠和等待3种状态。在激活状态,感知节点进行感知,通信和计算;一旦节点的能量用完,即进入休眠状态,在休眠状态节点除了充电外不执行其他任务;当电池被完全充好电后,感知节点进入等待状态,等待重新被激活。虽然等待状态的节点需要周期性的唤醒以同步网络状态信息,但因其消耗的能量相比激活状态是非常少的,所以假定等待状态下节点的剩余能量保持不变。本文研究具有相同充放电速度的同构节点,节点的充放电速度记为γr和γd。多项研究表明,采集环境中如太阳能等能量的节点在稳定的天气中,一个时间段(如1 h)的充电速度一般维持恒定。若天气变化,可以根据天气情况设定不同的充电速度。电池容量假定为B,电池从满电到耗尽所有电量的时间为Td=B/γd,而重新充满电所需的时间为Tr=B/γr;所以感知节点的一个充放电时间周期可以表达为T=Td+Tr;充放电的时间比为β=Tr/Td=γd/γr。为研究方便,若β≥1,则假定β为整数;若β<1,则假定1/β为整数;这个假设并不影响后续研究的推导和结论。当β≥1,设定时隙为Td,则一个充放电周期T包含1+β个时隙;若β<1,将时隙设定为Tr,则一个充放电周期包含1+1/β个时隙。如图1所示,本文假定每天的工作时间L可以分为整数个充放电周期L=αT(α为整数);当β≥1时,一个充放电周期中,节点只有一个时隙是激活状态;当β<1时,在一个充放电周期中,节点只需要在一个时隙进入休眠充电,其他时隙激活。例如对于图1(a),β=3,若Td=30 min,则一个充放电周期T=(3+1)×30=120 min,白天的工作时间(12 h)可分为6个充放电周期。

图1 充放电周期与时隙

图2 有向感知传感器节点的感知模型

假定在二维平面区域中随机分布有N个可充电有向感知传感器节点S={s1,s2,…,sN}和M个目标监测点O={o1,o2,…,oM}。假定节点的感知方向被划分为3个120°不交叉的扇形区域,分别记为区域1,2和3,如图2所示,有向感知节点可根据覆盖需求在3个扇形覆盖区进行选择。考虑到节点二元监测模型不够准确的缺点,在文献[15-16]等提出的全向节点概率感知模型基础上,笔者将其拓展为有向感知节点的概率感知模型。

假定dn,m为传感器节点sn和目标点om的欧式距离,θn,m为节点与目标点连线与x轴正半轴的夹角。当传感器节点sn的感知范围分别设定在0°～120°,120°～240°,240°～360° 3个扇区时,引入参数asn,hn,om来表示传感器节点sn在其感知方向hn上是否能够覆盖目标点om,能覆盖取值为1,否则为0,如式(1)所示

(1)

式中:dmax是节点的最大感知半径。则当设置感知方向为hn时,传感器节点sn对目标点om的覆盖率为:

p(sn,hn,om)=asn,hn,om·e-λdn,m

(2)

λ表示感知概率随距离变化而逐渐衰减。多个传感器节点同时监测获得的监测率为:

(3)

传感器节点通过协调激活时隙及感知方向来最大化系统覆盖率。一天的工作时间被分隔为整数个时隙,所有目标点在时隙t获得的监测率可以表示为

式中:SX(om,t)表示激活策略X在时隙t激活且能监测到目标点om的有向传感器节点集合。值得注意的是,策略X包括了为节点选择激活时隙及感知方向。则一天时间内,所有目标点获得的总覆盖率为

(4)

2 动态激活算法

根据上一节的分析,此部分将问题分成β≥1和β<1两种情况来讨论。

2.1 充电速度慢于放电速度β≥1

β≥1,即用电速度快于充电速度的情况,这种情况在实际应用中更为常见。此时最大化系统覆盖率的优化问题可以表示为

(5)

针对该问题,笔者提出了一种多项式时间的逐次贪婪节点激活算法SGA(Greedy Node Activation Scheme),算法如表1所示。其中为简要描述算法,假定工作时间L=T=β+1。在这种情况下,每个感知节点在工作时间内,只能在一个时隙和某一个方向上激活。算法如表1所示。

每次循环中选择一个对系统覆盖率增长最大的节点和相应的时隙及方向进行激活,因此算法迭代的次数等于感知节点的数量。SX(om,t)代表当前已分配给时隙t能够覆盖目标点om的感知节点集合,初始设为空集;Sleft是剩余未分配的感知节点集合。算法第5行到第11行计算每一个剩余未分配的节点在每个时隙及每个方向上激活所能带来对系统覆盖率的增加值;第12行找出当前能给系统覆盖率带来最大附加值的节点,对应的激活时隙和方向。第13行把当前激活的节点加入在其激活方向上能够覆盖的所有目标点的感知节点集合,第14行记录当前感知节点的激活方向。符号代表从集合中删除某个元素或子集。值得注意的是,算法虽然假定工作时间L等于一个充放电周期T,当L超过一个充放电周期时,只需要在每个充放电周期重复执行激活算法即可。

表1 逐次贪婪节点激活算法

接下来为证明逐次贪婪节点激活算法的性能,引入次模函数的概念。

根据文献[17],非减次模函数具有以下的特征:

(6)

不难证明,本文式(3)所表示的系统覆盖率符合非减次模函数特性,即:当激活节点为空集时,监测成功率为0;当加入的感知节点越多,监测成功率越高;但随着激活节点的增加,后加入节点带来的收益增加值是递减的。

定理1当β≥1时,在系统覆盖率上,逐次贪婪节点激活算法SGA至少能获得最佳激活算法效益的50%。

(7)

(8)

情况2s1∉Ai。此时,假定最佳激活算法将s1分配在时隙i′中激活,若将s1从时隙i′中移除,重新分配到时隙i,令其他所有感知节点维持原来的分配,这仍然是问题P′的一种解。由于系统覆盖率符合次模函数特征以及SGA算法的贪婪特性,使得以下不等式成立

(9)

根据本文的贪婪算法以及次模函数特点,移除s1的最大损失是z,不等式左边表示将s1从时隙i′中移除后最低的系统覆盖率;不等式右边表示将s1重新分配到i时隙后能够获得的最高系统效益,根据次模函数特性,该不等式成立。

综合情况1,情况2和情况3,得到式(8)成立。

(10)

以上证明是基于工作时间L=T的前提,当L=αT,α为整数时,在每个充放电周期T执行一次逐次贪婪激活算法。接下来要证明当L=αT时,也能获得至少为最优激活算法一半的性能。

定理2当L=αT,α为整数时,逐次贪婪激活算法至少能获得最优激活算法一半的性能。

2.2 充电速度快于放电速度β<1

表2 逐次贪婪节点休眠算法

在先将所有节点在整个充放电时间激活的假设下,算法第1部分从第1行到第17行,逐次把节点的最佳感知方向确定下来,能给系统覆盖率带来最大增益的节点和感知方向优先确定;第14行记录感知节点的感知方向。执行完算法第1部分,SX(om)代表基于选择的感知方向下,能覆盖目标点om的感知节点集合。算法第2部分从第18行到第29行,逐次把给系统覆盖率带来最小损失的节点及对应时隙找出来,令该节点在对应的时隙进入休眠充电。算法结束后SY(om,t)代表了在时隙t激活的能监测目标点om的所有感知节点集合,hsi代表了感知节点si的感知方向,注意感知方向在一个充放电周期都维持不变。

在任意工作时间内,我们只需要以一个充放电为周期重复执行SGI算法,就可以实现整个工作时间段的节点激活和休眠调度。用证明定理1和定理2类似的方法,还可证明当β<1时,逐次贪婪休眠算法SGI至少能获得最优激活算法50%的性能,基于本文篇幅限制,这里不再展开说明。

3 算法验证和仿真

本节对逐次贪婪激活算法和逐次贪婪休眠算法在MATLAB仿真平台上进行验证。

仿真中设置目标点的个数M=5,分别位于二维坐标平面上(0m,0m),(-100m,100m),(100m,100m),(-100m,-100m)及(100m,-100m)。感知节点随机分布在以坐标原点为中心,半径150m的圆内,采用图2所示的感知模型,设dmax=70m,λ=0.02。本节仿真SGA或SGI算法在系统平均覆盖率方面的性能,并与最优激活方法进行比较(最优激活方法在仿真中是对所有可能的激活方案进行遍历得到的)。系统平均覆盖率定义为对所有目标点在所有时隙覆盖率的平均值:

(11)

首先假定β≥1,即充电速度慢于用电速度时,假定Td=15min,Tr=45min,则时隙设为15min,一个充放电周期为1h,每个充放电周期节点只工作1个时隙,其余3个时隙进入休眠充电。图3仿真当感知节点的个数从50上升到250个时,有向感知节点用SGA方法激活及采用最优激活分别获得的系统平均覆盖率。上一节的理论证明有向感知节点采用SGA激活至少能获得最优激活算法50%的性能,这是下限值,很多情况下往往大大超出这个下限,在图3的仿真中SGA的性能已经跟最优激活的性能接近。

图3 M=5,β=3时系统的平均覆盖率

接着仿真β<1,即充电速度快于用电速度时,假定Td=45min,Tr=15min,时隙设为15min,一个充放电周期为1h,每个充放电周期节点用一个时隙充电,在其余3个时隙激活。图4考查随着感知节点数目增加,逐次贪婪休眠算法SGI与最优激活算法的系统平均覆盖率。仿真验证了SGI算法的性能能较多超出最优算法性能的一半;且随着感知节点数目的增加,两者的差距快速缩小。

图4 M=5,β=1/3时系统的平均覆盖率

4 结束语

在采集环境能量供电的有向感知传感器网络中,节点的激活及感知方向设置关系到对目标点的覆盖和监测成功率。笔者提出的逐次贪婪激活算法SGA和逐次贪婪休眠算法SGI能在充电速度慢于耗电速度及充电速度快于耗电速度两种不同情况下,规划节点的激活休眠及感知方向选择,以最大化系统平均覆盖率。理论证明,SGA和SGI算法至少能获得最佳调度算法50%的效益;仿真验证,在大部分情况下,SGA和SGI算法的系统平均覆盖率远超过最佳调度算法的50%。将来的工作包括考虑让节点在未完全充满电时也可进入激活状态,以及充放电速率不同的异构节点的激活调度算法。

[1] Priya S,Inman D J. Energy Harvesting Technologies[M]. New York:Springer,2009.

[2] Mihajlovic Z,Joza A,Milosavljevic V. Energy Harvesting Wireless Sensor Node for Monitoring of Surface Water[C]//2015 21st International Conference on Automation and Computing(ICAC),2015:1-6.

[3] Srujana B S,Neha Mathews P,Harigovindan V P. Multi-Source Energy Harvesting System for Underwater Wireless Sensor Networks[C]//Proc of the International Conference on Information and Communication Technologies. Kochi,India,2014:1041-1048.

[4] Rodriguez de la Concepcion A,Stefanelli R,Trinchero D. A Wireless Sensor Network Platform Optimized for Assisted Sustainable Agriculture[C]//2014 IEEE Global Humanitarian Technology Conference,2014:159-165.

[5] Konstantopoulos C,Koutroulis E,Mitianoudis N. Converting a Plant to a Battery and Wireless Sensor With Scatter Radio and Ultra-Low Cost[J]. IEEE Transactions on Instrumentation and Measurement,2016(65):388-398.

[6] Wu X,Lee D W. An Electromagnetic Energyharvesting Device Based on High Efficiency Windmill Structure for Wireless Forest Fire Monitoring Application[J]. Sensors and Actuators A:Physical,2014(219):73-79.

[7] Chen H B,Li X Y,Zhao F. A Reinforcement Learning-Based Sleep Scheduling Algorithm for Desired Area Coverage in Solar-Powered Wireless Sensor Networks[J]. IEEE Sensors Journal,2016,16(8):2763-2774.

[8] Srbinovski B,Magno M. An Energy Aware Adaptive Sampling Algorithm for Energy Harvesting WSN with Energy Hungry Sensors[J]. Sensors,2016,16(4):448.

[9] Tang S J,Li X Y,Shen X,et al. Cool:On Coverage with Solar-Powered Sensors[C]//International Conference on Distributed Computing Systems,2011,6574(4):488-496.

[10] Gaudette B,Hanumaiah V,Krunz M. Maximizing Quality of Coverage Under Connectivity Constraints in Solar-Powered Active Wireless Sensor Networks[J]. ACM Trasactions on Sensor Networks,2014,10(4):59.

[11] Jia J L,Dong C L,He X G. Sensor Scheduling for Target Coverage in Directional Sensor Networks[J]. International Journal of Distributed Sensor Networks,2017,13(6):1-12.

[12] Lin T Y,Santoso H A,Wu K R. Enhanced Deployment Algorithms for Heterogeneous Directional Mobile Sensors in a Bounded Monitoring Area[J]. IEEE Trasactions on Mobile Computing,2017,16(3):744-758.

[13] 张聚伟,王宇,杨挺. 基于数据融合的有向传感器网络全覆盖部署[J]. 传感技术学报,2017,30(1):139-145.

[14] Kar K,Krishnamurthy A,Jaggi N. Dynamic Node Activation in Networks of Rechargeable Sensors[J]. ACM Trasactions on Networking,2006,14(1):15-26.

[15] Zou Y. Coverage-Driven Sensor Deployment and Energy-Efficient Information Processing in Wireless Sensor Networks[D]. USA:Duke University,2004.

[16] Dhillon S S,Chakrararty K. Sensor Placement for Effective Coverage and Surveillance in Distributed Sensor Networks[C]//Proceedings of Wireless Communications and Networking Record. New York,USA:IEEE Press,2003:1609-1614.

[17] Fujishige S. Submodular Functions Optimization. Annals of Discrete Mathematics[M]. Amsterdam,The Netherlands:Elsevier,1991.