基于煙花算法的WSN按需充電與數據收集策略

牟 青, 馮 琳, 魏振春,2

(1.合肥工業大學 計算機與信息學院,安徽 合肥 230601; 2.安全關鍵工業測控技術教育部工程研究中心,安徽 合肥 230601)

針對無線傳感器網絡(wireless sensor network,WSN)中能量和存儲空間受限的問題,現有的移動充電和移動數據收集解決方案有如下兩類:一類是將移動充電和移動數據收集分別集成在不同的移動設備上進行能量補充和數據收集操作;另一類是將充電模塊和數據收集模塊集成到同一輛小車上,同時對傳感器網絡進行能量補充和數據收集。文獻[1]中對多輛移動小車進行周期性調度的同時為傳感器節點進行充電和數據收集,以盡量少的移動設備保證網絡正常運行;文獻[2]提出將數據收集模塊和能量補充模塊集成到同一輛移動設備上,系統選擇能量較低的節點作為移動小車停留的錨點,移動小車對錨點處的傳感器節點進行能量補充的同時,錨點附近的傳感器節點通過多跳路由的方式將其采集的數據傳輸到移動小車的數據收集模塊上，WSN中的數據通過移動小車傳回基站,有效地利用了移動小車移動方便的特性,在小車為WSN中的傳感器節點進行能量補充的同時完成數據收集任務。文獻[3]將能量補充和移動數據收集任務分派到2輛不同的移動小車上,一輛小車作為無線充電設備來為傳感器節點進行能量補充,另一輛作為移動路由設備來接收傳感器設備采集的數據，這樣的規劃可以保證傳感器節點的能量補充和數據收集任務的時效性,但是需要增加設備的數量,提高WSN中的總能耗;文獻[4]將無線充電模塊和數據收集模塊同時集成到同一輛移動小車上,并提出通信范圍內節點之間可以互相傳輸數據,在充電范圍內每個傳感器節點都能被移動設備充電,該移動設備的充電范圍要小于等于傳感器節點的通信范圍,這樣通信范圍內移動設備就能夠收集傳感器節點產生的數據,最后WSN中收集的數據通過移動設備傳回基站。該方案綜合考慮了傳感器節點的剩余能量和剩余存儲空間,將能量和存儲空間同時作為傳感器節點工作狀態的指標,按照網絡請求和傳感器節點的需求對WSN進行能量補充和數據收集規劃[5-6]。

本文采用移動小車(mobile car,MC)直接到達節點處對傳感器節點進行充電和數據收集[7-9]。本文將傳感器節點分為工作和睡眠2種狀態[10],當節點能量高于最低能量值并且剩余存儲空間大于最低值時,節點處于工作狀態;否則節點處于睡眠狀態,要保證WSN正常工作就要避免節點進入睡眠狀態。本文研究在盡可能多地降低網絡能耗時,保證網絡正常工作。

1 系統模型與問題描述

本文研究場景為一個二維的WSN網絡，包括1個固定基站(base station,BS)、1個移動充電小車MC、n個可充電傳感器節點,S={s1,s2,…,si,…,sn}，每個節點對應的能耗分別為{p1,p2,…,pi,…,pn},數據采集率分別為{q1,q2,…,qi,…,qn}。移動小車在基站時能夠得到每個傳感器節點的位置、電量和內存信息；通過這些信息,使用本文提出的算法小車能確定要操作的節點和小車的移動路徑,然后依次移動到傳感器節點位置對傳感器節點進行充電和數據收集操作,WSN中MC充電與數據收集操作示意圖如圖1所示。

圖1 WSN中MC充電與數據收集操作示意圖

圖1中節點與小車之間的通信通過單跳方式進行。小車根據節點位置和節點的剩余工作時間選擇第t輪需要能量補充與數據收集的節點,小車對節點的能量補充與數據收集在小車到達節點時同時開始,小車對節點充電和數據收集結束離開該節點。當小車遍歷完所有需要能量補充和數據收集的節點后,小車回到基站,這一輪操作結束,小車對節點的能量補充與數據收集操作進入下一輪。

1.1 確定需求節點

節點的選擇是按需聯合充電與數據收集、優化網絡能耗的關鍵。因為網絡中消耗的大部分能量是小車行駛過程中消耗的[11]，并且持續運行的網絡中,當小車到達節點處時,節點的剩余能量和存儲空間越大，小車到達此節點的頻率會越高,小車的移動路徑會明顯增加[4，12],從而增加整個網絡運行的能耗，所以在每一輪操作時選擇出小車要訪問的合適的節點,對整個網絡來說至關重要。

基于以上分析,本文在小車選擇節點方面，主要考慮節點間的距離和節點的剩余工作時間2個方面。

1.2 MC移動充電與數據收集問題描述

在選擇了小車要訪問的節點后,MC對需求節點的訪問便決定了網絡的能耗。

1.2.1 駐站時間

(1)

根據(1)式可得,在第t輪小車駐站時間結束時節點的睡眠時間為:

(2)

(3)

此時節點si的剩余能量與剩余存儲空間分別為:

(4)

(5)

1.2.2MC在節點處停留時間

(6)

(7)

(8)

要保證網絡正常運行，需要滿足:

(9)

(10)

(11)

MC同時對節點進行能量補充和數據收集操作,當節點的剩余能量和剩余存儲空間都達到其補充的上限閾值時,MC對節點的操作結束。如果有一方先達到上限閾值而另外一方沒有達到上限閾值,那么先達到上限閾值的一方停止能量補充(或數據收集)。數據收集時間為:

(12)

能量補充時間為:

(13)

其中，Ef為節點能量的上限閾值。

MC在節點處的停留時間為:

(14)

(15)

(16)

1.2.3 節點的剩余能量與存儲空間

當小車在這一輪中對所有被選擇要操作的節點進行能量補充和數據收集結束回到基站后,小車開始進行下一輪的數據收集和能量補充操作。

(17)

(18)

要保證網絡正常運行，需要滿足節點在此段時間內的睡眠時間為0,即

(19)

此時由(17)式、(18)式可以得到節點剩余能量和節點的剩余存儲空間分別為:

(20)

(21)

(22)

要保證網絡正常運行，需要滿足節點在此段時間內的睡眠時間為0,即

(23)

(24)

(25)

這一輪花費的總時間為小車在路上行駛的時間,即小車在每個需要能量補充和數據收集的節點處停留的時間和小車在基站停留時間的總和。這一輪花費的總時間mt為:

(26)

1.3 優化目標

本文的優化問題OPT-1為通過合理調度MC,在保證網絡正常運行的前提下,最小化MC單位能耗,即

(27)

s.t.(3)式、(9)式、(19)式、(23)式。

2 算法設計

根據本文建立的WSN充電與數據收集模型和提出的最小化WSN生命周期內每一輪的MC單位能耗的優化目標,本節給出了用來控制MC單位能耗的需求節點判定方案和MC移動路徑規劃策略,并給出具體的算法步驟。

2.1 節點選擇算法

本文采取的是MC對傳感器節點進行按需充電和數據收集的操作,因此在每一輪要確定一部分在本輪中需要被小車進行能量補充與數據收集的節點。本文提出一種根據節點剩余能量和存儲空間以及節點到基站距離來求要被選擇的節點的算法,對這一輪要操作的節點進行選擇。根據節點的位置信息和剩余工作時間,按照本文提出的基于能量需求和數據收集(energy requirement and data collection)的節點選擇(select),S-ERDC算法進行分類。S-ERDC算法是基于K均值聚類算法的節點選擇算法,兩點之間的距離用加權距離來表示,即

di,j=

(28)

其中,di,j為根據節點si(Xi,Yi)、sj(Xj,Yj)的歐式距離和剩余工作時間計算所得的加權距離。根據這個加權后的距離來選擇要被操作的節點,α為加權系數，α∈[0,1)。當α取值為0時，表示在不考慮距離的情況下對節點進行能量補充與數據收集操作。本文中α取0.5。此算法可以通過減少小車的移動距離,來降低網絡能量。

采用本文的方法對節點進行分簇時需要給出初始質心,本文以基站s0和到基站加權距離最遠的點sfar作為初始質心。質心計算公式為:

(29)

其中:ci為要計算的第i個簇的質心;Ci為第i個簇;mi為第i個簇中節點的個數;x為傳感器節點到質心的加權距離。

節點選擇算法是為了確定網絡中在每一輪需要被操作的節點,算法步驟如下。

算法1 S-ERDC算法。

(2) 按照(28)式根據節點剩余能量和存儲空間以及到基站的距離計算所有節點間的加權距離。

(3) 將基站和到基站加權距離最遠的點作為2個簇頭。每個節點到基站的距離為di,0,到基站距離最遠節點的距離為d0,far=find(maxdi,0),到基站距離最遠的節點為sfar。

(4) 得到質心:c1=s0,c2=sfar。

(5) 將每個節點按照其到質心的加權距離,指派到最近的質心,形成C1、C22個簇。

(6) 根據(29)式重新計算每個簇的質心c1、c2,直到質心不發生改變。

(7) 重復步驟(5)、步驟(6)。

2.2 基于煙花算法的MC節點訪問調度算法

在得到需要被訪問的節點后,MC從基站出發遍歷所有需要訪問的節點,然后回到基站。合理規劃MC移動路徑能夠有效地降低MC在移動過程中消耗的能量,這部分消耗能量是網絡消耗總能量的重要組成部分。本文中MC的路徑規劃問題本質上是一個NP-C問題,本文采用改進煙花算法,即差分進化煙花(differential evolution fireworks,DEFW)算法來求解,首先通過煙花爆炸產生火花,然后對爆炸產生的火花進行差分變異操作,得到差分火花,最后在煙花、火花和差分火花中選出下一代種群。因為DEFW算法是在原始煙花算法的基礎上進行改進的,所以本文對改進的火花差分變異操作進行分析。

對于爆炸產生的火花,一般只是產生在煙花的周圍,這樣不斷迭代容易使得種群陷入局部最優解。本文對煙花爆炸產生的火花進行差分變異,保證產生的火花的多樣性。火花差分變異是對煙花爆炸產生的所有火花進行差分變異操作,其中差分變異是將2個個體的差向量作為第3個個體的隨機變化源,將差向量加權后按照一定的規則與第3個個體求和從而產生變異個體。本文中將一次迭代中產生火花的最優值作為需要變異的個體,產生的火花依次交替作為隨機變異源,如第1個火花與第2個火花作為變異源與本體結合產生第1個變異個體,第2個火花與第3個火花作為變異源與本體結合產生第2個變異個體,依此類推可以產生和火花數目相同的變異個體。火花差分變異過程為:

(30)

其中:X為第g次迭代產生的火花數目;xi,g為第g次迭代產生的第i個火花;xbest,g為第g次迭代產生的最優火花作為的變異本體;F為加權系數;vi,g為第g次迭代中產生的第i個變異火花。

以二維空間為例說明二維向量中火花差分變異過程,如圖2所示。圖2中:xbest為變異本體;x1、x2為第1個、第2個火花;v1為通過(29)式計算得到的第1個差分變異火花。

圖2 二維向量火花差分變異

MC行駛路徑規劃算法是本文核心算法。本文所設計的DEFW算法結合了煙花算法和差分進化算法,具體操作步驟如下。

算法2 DEFW算法。

輸出:f。

(2) 煙花算法種群和參數初始化。

(3) 當i≤I時,對初始種群進行煙花爆炸操作產生n個火花。

(4) 計算每個火花的適應度值f。

(5) 根據(29)式對火花進行差分變異操作得到差分火花。

(6) 計算差分火花的適應度值f。

(7) 對煙花個體進行高斯變異操作。

(8) 根據煙花,火花和差分火花的適應度值f選擇下一代的初始種群。

(9) 迭代次數完成得到目標函數的最終解f。

3 仿真與分析

對本文提出的模型和使用的算法進行實驗仿真,并給出實驗分析。實驗所采用軟硬件系統為i7-8700cup、8 GiB內存、Matlab2017b仿真軟件和Windows10操作系統。

實驗參數為在200 m×200 m的區域,隨機分布20個節點,節點能量為100 kJ,存儲空間為2 GiB,開始充電閾值為1 000 mA·h,開始數據收集閾值為400 Mibit,MC行駛速度及功耗分別為5 m/s、45 J/s。MC充電功率為7.5 W,MC對節點的數據收集速率為1.4 Mibit/s,傳感器節點的數據傳輸功耗為3.5 W。

3.1 不同算法收斂情況比較

(1) 實驗1。本實驗分別采用DEFW算法、原始煙花算法(fireworks algorithm,FWA)、遺傳算法(genetic algorithm,GA),迭代100次求得解的情況。首先生成一組數據:在實驗設定區域內隨機產生20個均勻分布的傳感器節點，節點的能量消耗功率pi為[0.3,0.6]之間的隨機數(單位為W),節點數據采集速率qi為[100,200]之間的隨機數,單位為kibit/s;然后分別采用DEFW、FWA、GA算法對其進行調度并記錄其迭代過程中的目標值,以觀察3種算法的收斂性。DEFW、FWA、GA算法求解的MC單位能耗隨迭代次數變化情況如圖3所示。從圖3可以看出,DEFW、FWA、GA算法求解一輪充電和數據收集操作路徑時,DEFW算法收斂效果更好。

(2) 實驗2。為了防止實驗1具有偶然性,本實驗采用實驗1中的方法隨機產生20組數據,然后對每一組數據分別采用DEFW、FWA、GA算法對其進行調度并得到最終的目標值求解結果。最終20組數據分別使用DEFW、FWA、GA算法求解的MC單位能耗對比如圖4所示。

圖4 20組數據使用3種算法求解的MC單位能耗對比

從圖4可以看出,對20組不同數據分別使用DEFW、FWA、GA算法,DEFW算法求解目標值得到的平均MC單位能耗最低。

3.2 不同調度算法下網絡能耗

本實驗為了驗證同一個WSN中采用DEFW算法在持續多輪對MC進行調度時MC單位能耗變化情況。首先采用實驗1中的方法產生一組實驗數據,然后分別使用DEFW、FWA、GA算法對其進行40輪的充電與數據收集調度,并求出每一輪的目標值ft。DEFW、FWA、GA算法對MC進行40輪的能量補充與數據收集調度下,MC單位能耗的變化情況對比如圖5所示。

圖5 3種算法調度下網絡運行40輪MC單位能耗對比

從圖5可以看出,第4輪操作之后使用DEFW算法的MC調度可以使得MC單位能耗明顯低于使用FWA、GA算法調度得到的結果。

4 結 論

在WSN中傳感器節點能量和存儲空間受限情況下,如何保證傳感器節點在正常工作的同時,降低整個網絡的能耗是近年來WSN 領域研究的重點。本文通過S-ERDC算法來根據當前網絡需求選擇需要操作的節點,然后通過DEFW算法求解MC對節點的最優訪問路徑。仿真結果顯示,本文提出的策略可以有效地解決WSN中能量與存儲空間不足的問題,并且與FWA、GA算法相比能夠明顯降低傳感器網絡的能耗。