有向感知可充電傳感器節(jié)點的動態(tài)激活策略*

胡 潔,蘭玉彬

(1.華南農(nóng)業(yè)大學(xué)電子工程學(xué)院,廣州 510642;2.華南農(nóng)業(yè)大學(xué)工程學(xué)院,廣州 510642)

無線傳感器節(jié)點及網(wǎng)絡(luò)在工業(yè)過程、醫(yī)療護(hù)理和智能電網(wǎng)等諸多領(lǐng)域得到了廣泛應(yīng)用,尤其是在環(huán)境監(jiān)測領(lǐng)域被重點關(guān)注;然而,由于監(jiān)測周期長且覆蓋面積廣,往往存在節(jié)點能量消耗不均,網(wǎng)絡(luò)壽命短等問題。已有很多研究致力于提高電池能量的有效利用以延長網(wǎng)絡(luò)生命期,但沒有從根本解決WSN的能量供給問題。監(jiān)測環(huán)境往往地形復(fù)雜,位置偏遠(yuǎn),導(dǎo)致更換節(jié)點電池費時費力,在一些環(huán)境下甚至是不可能的。在不能更換電池的情況下,只有低成本的傳感器節(jié)點才能在現(xiàn)實中大規(guī)模的鋪設(shè)和一次性使用后丟棄;同時,被丟棄的節(jié)點不能有害于生態(tài)環(huán)境,也即不能使用鋰電池或鎘電池。種種限制阻礙了WSN在環(huán)境監(jiān)測中的應(yīng)用。

在這種背景下提出的能量采集技術(shù)[1]將環(huán)境中的太陽能,風(fēng)能,水能甚至是無線電磁波的能量轉(zhuǎn)化為電能,提供了一種有效解決WSN的能量限制問題的方法。近年來,已有一些研究將能量采集無線傳感器網(wǎng)絡(luò)投入到實際的環(huán)境監(jiān)測應(yīng)用中[2-6]。在這些應(yīng)用中,節(jié)點的激活策略是在采集能量的基礎(chǔ)上,合理調(diào)度節(jié)點的激活和休眠以完成監(jiān)測任務(wù)的關(guān)鍵。在能量采集系統(tǒng)中,由于節(jié)點的剩余能量不是單調(diào)遞減的,每個時段的剩余能量跟采集有關(guān),而采集的能量往往具有隨機性,所以節(jié)點的激活-休眠周期安排不能沿用電池供電的WSN的方法。文獻(xiàn)[7]介紹了在太陽能供電的WSN中采用基于強化學(xué)習(xí)的休眠機制來實現(xiàn)區(qū)域的覆蓋;文獻(xiàn)[8]設(shè)計了一種基于采集能量感知的自適應(yīng)采樣機制;文獻(xiàn)[9]為采集太陽能的同構(gòu)節(jié)點設(shè)計了一種最大化系統(tǒng)效率的簡單激活機制。文獻(xiàn)[10]通過對太陽能采集節(jié)點的動態(tài)激活和感知距離調(diào)整來最大化24 h內(nèi)的最低覆蓋質(zhì)量指數(shù);文中提到了傳感器節(jié)點的全向感知范圍和扇形感知范圍,但在算法中只考慮調(diào)整感知的距離,并不調(diào)整感知方向。而隨著傳感器技術(shù)的進(jìn)步,傳感器節(jié)點趨于多樣化,視頻傳感器、超聲傳感器、紅外傳感器等具有方向性的傳感器節(jié)點的應(yīng)用越來越多。相比傳統(tǒng)的全向感知節(jié)點,有向感知傳感器節(jié)點當(dāng)其感知方向可調(diào)時,節(jié)點的激活策略可以獲得更大的自由度,但同時也導(dǎo)致計算更復(fù)雜。文獻(xiàn)[11]假定傳感器節(jié)點可以在360°的方向上隨意轉(zhuǎn)動,設(shè)計了一種啟發(fā)式算法將節(jié)點劃分為多個不交叉的感知集,并為這些感知集分配工作時間,以此在達(dá)到覆蓋要求的條件下延長網(wǎng)絡(luò)生命期。文獻(xiàn)[12]提出的覆蓋方法在滿足不同目標(biāo)覆蓋率要求的前提下,最大化網(wǎng)絡(luò)生命期,該方法適用于感知距離、方向及覆蓋角度異構(gòu)的感知節(jié)點。文獻(xiàn)[13]針對有向傳感器網(wǎng)絡(luò)全覆蓋問題,基于有向傳感器節(jié)點概率感知模型提出一種新的有向傳感器節(jié)點部署結(jié)構(gòu)。到目前為止,鮮有文獻(xiàn)涉及能量采集型有向感知節(jié)點的激活和覆蓋問題。

筆者為采集能量的有向感知傳感器節(jié)點設(shè)計了動態(tài)激活及感知方向調(diào)度策略,以獲得最大的系統(tǒng)平均監(jiān)測成功率;算法采用了多項式時間的解決方法,并至少能獲得最佳激活算法50%的監(jiān)測成功率。

1 系統(tǒng)模型

本文采用跟文獻(xiàn)[14]類似的充放電模型。假定所有傳感器節(jié)點具有同步時鐘,節(jié)點有激活,休眠和等待3種狀態(tài)。在激活狀態(tài),感知節(jié)點進(jìn)行感知,通信和計算;一旦節(jié)點的能量用完,即進(jìn)入休眠狀態(tài),在休眠狀態(tài)節(jié)點除了充電外不執(zhí)行其他任務(wù);當(dāng)電池被完全充好電后,感知節(jié)點進(jìn)入等待狀態(tài),等待重新被激活。雖然等待狀態(tài)的節(jié)點需要周期性的喚醒以同步網(wǎng)絡(luò)狀態(tài)信息,但因其消耗的能量相比激活狀態(tài)是非常少的,所以假定等待狀態(tài)下節(jié)點的剩余能量保持不變。本文研究具有相同充放電速度的同構(gòu)節(jié)點,節(jié)點的充放電速度記為γr和γd。多項研究表明,采集環(huán)境中如太陽能等能量的節(jié)點在穩(wěn)定的天氣中,一個時間段(如1 h)的充電速度一般維持恒定。若天氣變化,可以根據(jù)天氣情況設(shè)定不同的充電速度。電池容量假定為B,電池從滿電到耗盡所有電量的時間為Td=B/γd,而重新充滿電所需的時間為Tr=B/γr;所以感知節(jié)點的一個充放電時間周期可以表達(dá)為T=Td+Tr;充放電的時間比為β=Tr/Td=γd/γr。為研究方便,若β≥1,則假定β為整數(shù);若β<1,則假定1/β為整數(shù);這個假設(shè)并不影響后續(xù)研究的推導(dǎo)和結(jié)論。當(dāng)β≥1,設(shè)定時隙為Td,則一個充放電周期T包含1+β個時隙;若β<1,將時隙設(shè)定為Tr,則一個充放電周期包含1+1/β個時隙。如圖1所示,本文假定每天的工作時間L可以分為整數(shù)個充放電周期L=αT(α為整數(shù));當(dāng)β≥1時,一個充放電周期中,節(jié)點只有一個時隙是激活狀態(tài);當(dāng)β<1時,在一個充放電周期中,節(jié)點只需要在一個時隙進(jìn)入休眠充電,其他時隙激活。例如對于圖1(a),β=3,若Td=30 min,則一個充放電周期T=(3+1)×30=120 min,白天的工作時間(12 h)可分為6個充放電周期。

圖1 充放電周期與時隙

圖2 有向感知傳感器節(jié)點的感知模型

假定在二維平面區(qū)域中隨機分布有N個可充電有向感知傳感器節(jié)點S={s1,s2,…,sN}和M個目標(biāo)監(jiān)測點O={o1,o2,…,oM}。假定節(jié)點的感知方向被劃分為3個120°不交叉的扇形區(qū)域,分別記為區(qū)域1,2和3,如圖2所示,有向感知節(jié)點可根據(jù)覆蓋需求在3個扇形覆蓋區(qū)進(jìn)行選擇?？紤]到節(jié)點二元監(jiān)測模型不夠準(zhǔn)確的缺點,在文獻(xiàn)[15-16]等提出的全向節(jié)點概率感知模型基礎(chǔ)上,筆者將其拓展為有向感知節(jié)點的概率感知模型。

假定dn,m為傳感器節(jié)點sn和目標(biāo)點om的歐式距離,θn,m為節(jié)點與目標(biāo)點連線與x軸正半軸的夾角。當(dāng)傳感器節(jié)點sn的感知范圍分別設(shè)定在0°～120°,120°～240°,240°～360° 3個扇區(qū)時,引入?yún)?shù)asn,hn,om來表示傳感器節(jié)點sn在其感知方向hn上是否能夠覆蓋目標(biāo)點om,能覆蓋取值為1,否則為0,如式(1)所示

(1)

式中:dmax是節(jié)點的最大感知半徑。則當(dāng)設(shè)置感知方向為hn時,傳感器節(jié)點sn對目標(biāo)點om的覆蓋率為:

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

(2)

λ表示感知概率隨距離變化而逐漸衰減。多個傳感器節(jié)點同時監(jiān)測獲得的監(jiān)測率為:

(3)

傳感器節(jié)點通過協(xié)調(diào)激活時隙及感知方向來最大化系統(tǒng)覆蓋率。一天的工作時間被分隔為整數(shù)個時隙,所有目標(biāo)點在時隙t獲得的監(jiān)測率可以表示為

式中:SX(om,t)表示激活策略X在時隙t激活且能監(jiān)測到目標(biāo)點om的有向傳感器節(jié)點集合。值得注意的是,策略X包括了為節(jié)點選擇激活時隙及感知方向。則一天時間內(nèi),所有目標(biāo)點獲得的總覆蓋率為

(4)

2 動態(tài)激活算法

根據(jù)上一節(jié)的分析,此部分將問題分成β≥1和β<1兩種情況來討論。

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

β≥1,即用電速度快于充電速度的情況,這種情況在實際應(yīng)用中更為常見。此時最大化系統(tǒng)覆蓋率的優(yōu)化問題可以表示為

(5)

針對該問題,筆者提出了一種多項式時間的逐次貪婪節(jié)點激活算法SGA(Greedy Node Activation Scheme),算法如表1所示。其中為簡要描述算法,假定工作時間L=T=β+1。在這種情況下,每個感知節(jié)點在工作時間內(nèi),只能在一個時隙和某一個方向上激活。算法如表1所示。

每次循環(huán)中選擇一個對系統(tǒng)覆蓋率增長最大的節(jié)點和相應(yīng)的時隙及方向進(jìn)行激活,因此算法迭代的次數(shù)等于感知節(jié)點的數(shù)量。SX(om,t)代表當(dāng)前已分配給時隙t能夠覆蓋目標(biāo)點om的感知節(jié)點集合,初始設(shè)為空集;Sleft是剩余未分配的感知節(jié)點集合。算法第5行到第11行計算每一個剩余未分配的節(jié)點在每個時隙及每個方向上激活所能帶來對系統(tǒng)覆蓋率的增加值;第12行找出當(dāng)前能給系統(tǒng)覆蓋率帶來最大附加值的節(jié)點,對應(yīng)的激活時隙和方向。第13行把當(dāng)前激活的節(jié)點加入在其激活方向上能夠覆蓋的所有目標(biāo)點的感知節(jié)點集合,第14行記錄當(dāng)前感知節(jié)點的激活方向。符號代表從集合中刪除某個元素或子集。值得注意的是,算法雖然假定工作時間L等于一個充放電周期T,當(dāng)L超過一個充放電周期時,只需要在每個充放電周期重復(fù)執(zhí)行激活算法即可。

表1 逐次貪婪節(jié)點激活算法

接下來為證明逐次貪婪節(jié)點激活算法的性能,引入次模函數(shù)的概念。

根據(jù)文獻(xiàn)[17],非減次模函數(shù)具有以下的特征:

(6)

不難證明,本文式(3)所表示的系統(tǒng)覆蓋率符合非減次模函數(shù)特性,即:當(dāng)激活節(jié)點為空集時,監(jiān)測成功率為0;當(dāng)加入的感知節(jié)點越多,監(jiān)測成功率越高;但隨著激活節(jié)點的增加,后加入節(jié)點帶來的收益增加值是遞減的。

定理1當(dāng)β≥1時,在系統(tǒng)覆蓋率上,逐次貪婪節(jié)點激活算法SGA至少能獲得最佳激活算法效益的50%。

(7)

(8)

情況2s1?Ai。此時,假定最佳激活算法將s1分配在時隙i′中激活,若將s1從時隙i′中移除,重新分配到時隙i,令其他所有感知節(jié)點維持原來的分配,這仍然是問題P′的一種解。由于系統(tǒng)覆蓋率符合次模函數(shù)特征以及SGA算法的貪婪特性,使得以下不等式成立

(9)

根據(jù)本文的貪婪算法以及次模函數(shù)特點,移除s1的最大損失是z,不等式左邊表示將s1從時隙i′中移除后最低的系統(tǒng)覆蓋率;不等式右邊表示將s1重新分配到i時隙后能夠獲得的最高系統(tǒng)效益,根據(jù)次模函數(shù)特性,該不等式成立。

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

(10)

以上證明是基于工作時間L=T的前提,當(dāng)L=αT,α為整數(shù)時,在每個充放電周期T執(zhí)行一次逐次貪婪激活算法。接下來要證明當(dāng)L=αT時,也能獲得至少為最優(yōu)激活算法一半的性能。

定理2當(dāng)L=αT,α為整數(shù)時,逐次貪婪激活算法至少能獲得最優(yōu)激活算法一半的性能。

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

表2 逐次貪婪節(jié)點休眠算法

在先將所有節(jié)點在整個充放電時間激活的假設(shè)下,算法第1部分從第1行到第17行,逐次把節(jié)點的最佳感知方向確定下來,能給系統(tǒng)覆蓋率帶來最大增益的節(jié)點和感知方向優(yōu)先確定;第14行記錄感知節(jié)點的感知方向。執(zhí)行完算法第1部分,SX(om)代表基于選擇的感知方向下,能覆蓋目標(biāo)點om的感知節(jié)點集合。算法第2部分從第18行到第29行,逐次把給系統(tǒng)覆蓋率帶來最小損失的節(jié)點及對應(yīng)時隙找出來,令該節(jié)點在對應(yīng)的時隙進(jìn)入休眠充電。算法結(jié)束后SY(om,t)代表了在時隙t激活的能監(jiān)測目標(biāo)點om的所有感知節(jié)點集合,hsi代表了感知節(jié)點si的感知方向,注意感知方向在一個充放電周期都維持不變。

在任意工作時間內(nèi),我們只需要以一個充放電為周期重復(fù)執(zhí)行SGI算法,就可以實現(xiàn)整個工作時間段的節(jié)點激活和休眠調(diào)度。用證明定理1和定理2類似的方法,還可證明當(dāng)β<1時,逐次貪婪休眠算法SGI至少能獲得最優(yōu)激活算法50%的性能,基于本文篇幅限制,這里不再展開說明。

3 算法驗證和仿真

本節(jié)對逐次貪婪激活算法和逐次貪婪休眠算法在MATLAB仿真平臺上進(jìn)行驗證。

仿真中設(shè)置目標(biāo)點的個數(shù)M=5,分別位于二維坐標(biāo)平面上(0m,0m),(-100m,100m),(100m,100m),(-100m,-100m)及(100m,-100m)。感知節(jié)點隨機分布在以坐標(biāo)原點為中心,半徑150m的圓內(nèi),采用圖2所示的感知模型,設(shè)dmax=70m,λ=0.02。本節(jié)仿真SGA或SGI算法在系統(tǒng)平均覆蓋率方面的性能,并與最優(yōu)激活方法進(jìn)行比較(最優(yōu)激活方法在仿真中是對所有可能的激活方案進(jìn)行遍歷得到的)。系統(tǒng)平均覆蓋率定義為對所有目標(biāo)點在所有時隙覆蓋率的平均值:

(11)

首先假定β≥1,即充電速度慢于用電速度時,假定Td=15min,Tr=45min,則時隙設(shè)為15min,一個充放電周期為1h,每個充放電周期節(jié)點只工作1個時隙,其余3個時隙進(jìn)入休眠充電。圖3仿真當(dāng)感知節(jié)點的個數(shù)從50上升到250個時,有向感知節(jié)點用SGA方法激活及采用最優(yōu)激活分別獲得的系統(tǒng)平均覆蓋率。上一節(jié)的理論證明有向感知節(jié)點采用SGA激活至少能獲得最優(yōu)激活算法50%的性能,這是下限值,很多情況下往往大大超出這個下限,在圖3的仿真中SGA的性能已經(jīng)跟最優(yōu)激活的性能接近。

圖3 M=5,β=3時系統(tǒng)的平均覆蓋率

接著仿真β<1,即充電速度快于用電速度時,假定Td=45min,Tr=15min,時隙設(shè)為15min,一個充放電周期為1h,每個充放電周期節(jié)點用一個時隙充電,在其余3個時隙激活。圖4考查隨著感知節(jié)點數(shù)目增加,逐次貪婪休眠算法SGI與最優(yōu)激活算法的系統(tǒng)平均覆蓋率。仿真驗證了SGI算法的性能能較多超出最優(yōu)算法性能的一半;且隨著感知節(jié)點數(shù)目的增加,兩者的差距快速縮小。

圖4 M=5,β=1/3時系統(tǒng)的平均覆蓋率

4 結(jié)束語

在采集環(huán)境能量供電的有向感知傳感器網(wǎng)絡(luò)中,節(jié)點的激活及感知方向設(shè)置關(guān)系到對目標(biāo)點的覆蓋和監(jiān)測成功率。筆者提出的逐次貪婪激活算法SGA和逐次貪婪休眠算法SGI能在充電速度慢于耗電速度及充電速度快于耗電速度兩種不同情況下,規(guī)劃節(jié)點的激活休眠及感知方向選擇,以最大化系統(tǒng)平均覆蓋率。理論證明,SGA和SGI算法至少能獲得最佳調(diào)度算法50%的效益;仿真驗證,在大部分情況下,SGA和SGI算法的系統(tǒng)平均覆蓋率遠(yuǎn)超過最佳調(diào)度算法的50%。將來的工作包括考慮讓節(jié)點在未完全充滿電時也可進(jìn)入激活狀態(tài),以及充放電速率不同的異構(gòu)節(jié)點的激活調(diào)度算法。

[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] 張聚偉,王宇,楊挺. 基于數(shù)據(jù)融合的有向傳感器網(wǎng)絡(luò)全覆蓋部署[J]. 傳感技術(shù)學(xué)報,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.