牟 青, 馮 琳, 魏振春,2

(1.合肥工業(yè)大學(xué) 計(jì)算機(jī)與信息學(xué)院,安徽 合肥 230601; 2.安全關(guān)鍵工業(yè)測控技術(shù)教育部工程研究中心,安徽 合肥 230601)

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

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

1 系統(tǒng)模型與問題描述

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

圖1 WSN中MC充電與數(shù)據(jù)收集操作示意圖

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

1.1 確定需求節(jié)點(diǎn)

節(jié)點(diǎn)的選擇是按需聯(lián)合充電與數(shù)據(jù)收集、優(yōu)化網(wǎng)絡(luò)能耗的關(guān)鍵。因?yàn)榫W(wǎng)絡(luò)中消耗的大部分能量是小車行駛過程中消耗的[11]，并且持續(xù)運(yùn)行的網(wǎng)絡(luò)中,當(dāng)小車到達(dá)節(jié)點(diǎn)處時(shí),節(jié)點(diǎn)的剩余能量和存儲空間越大，小車到達(dá)此節(jié)點(diǎn)的頻率會越高,小車的移動(dòng)路徑會明顯增加[4，12],從而增加整個(gè)網(wǎng)絡(luò)運(yùn)行的能耗，所以在每一輪操作時(shí)選擇出小車要訪問的合適的節(jié)點(diǎn),對整個(gè)網(wǎng)絡(luò)來說至關(guān)重要。

基于以上分析,本文在小車選擇節(jié)點(diǎn)方面，主要考慮節(jié)點(diǎn)間的距離和節(jié)點(diǎn)的剩余工作時(shí)間2個(gè)方面。

1.2 MC移動(dòng)充電與數(shù)據(jù)收集問題描述

在選擇了小車要訪問的節(jié)點(diǎn)后,MC對需求節(jié)點(diǎn)的訪問便決定了網(wǎng)絡(luò)的能耗。

1.2.1 駐站時(shí)間

(1)

根據(jù)(1)式可得,在第t輪小車駐站時(shí)間結(jié)束時(shí)節(jié)點(diǎn)的睡眠時(shí)間為:

(2)

(3)

此時(shí)節(jié)點(diǎn)si的剩余能量與剩余存儲空間分別為:

(4)

(5)

1.2.2MC在節(jié)點(diǎn)處停留時(shí)間

(6)

(7)

(8)

要保證網(wǎng)絡(luò)正常運(yùn)行，需要滿足:

(9)

(10)

(11)

MC同時(shí)對節(jié)點(diǎn)進(jìn)行能量補(bǔ)充和數(shù)據(jù)收集操作,當(dāng)節(jié)點(diǎn)的剩余能量和剩余存儲空間都達(dá)到其補(bǔ)充的上限閾值時(shí),MC對節(jié)點(diǎn)的操作結(jié)束。如果有一方先達(dá)到上限閾值而另外一方?jīng)]有達(dá)到上限閾值,那么先達(dá)到上限閾值的一方停止能量補(bǔ)充(或數(shù)據(jù)收集)。數(shù)據(jù)收集時(shí)間為:

(12)

能量補(bǔ)充時(shí)間為:

(13)

其中，Ef為節(jié)點(diǎn)能量的上限閾值。

MC在節(jié)點(diǎn)處的停留時(shí)間為:

(14)

(15)

(16)

1.2.3 節(jié)點(diǎn)的剩余能量與存儲空間

當(dāng)小車在這一輪中對所有被選擇要操作的節(jié)點(diǎn)進(jìn)行能量補(bǔ)充和數(shù)據(jù)收集結(jié)束回到基站后,小車開始進(jìn)行下一輪的數(shù)據(jù)收集和能量補(bǔ)充操作。

(17)

(18)

要保證網(wǎng)絡(luò)正常運(yùn)行，需要滿足節(jié)點(diǎn)在此段時(shí)間內(nèi)的睡眠時(shí)間為0,即

(19)

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

(20)

(21)

(22)

要保證網(wǎng)絡(luò)正常運(yùn)行，需要滿足節(jié)點(diǎn)在此段時(shí)間內(nèi)的睡眠時(shí)間為0,即

(23)

(24)

(25)

這一輪花費(fèi)的總時(shí)間為小車在路上行駛的時(shí)間,即小車在每個(gè)需要能量補(bǔ)充和數(shù)據(jù)收集的節(jié)點(diǎn)處停留的時(shí)間和小車在基站停留時(shí)間的總和。這一輪花費(fèi)的總時(shí)間mt為:

(26)

1.3 優(yōu)化目標(biāo)

本文的優(yōu)化問題OPT-1為通過合理調(diào)度MC,在保證網(wǎng)絡(luò)正常運(yùn)行的前提下,最小化MC單位能耗,即

(27)

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

2 算法設(shè)計(jì)

根據(jù)本文建立的WSN充電與數(shù)據(jù)收集模型和提出的最小化WSN生命周期內(nèi)每一輪的MC單位能耗的優(yōu)化目標(biāo),本節(jié)給出了用來控制MC單位能耗的需求節(jié)點(diǎn)判定方案和MC移動(dòng)路徑規(guī)劃策略,并給出具體的算法步驟。

2.1 節(jié)點(diǎn)選擇算法

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

di,j=

(28)

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

采用本文的方法對節(jié)點(diǎn)進(jìn)行分簇時(shí)需要給出初始質(zhì)心,本文以基站s0和到基站加權(quán)距離最遠(yuǎn)的點(diǎn)sfar作為初始質(zhì)心。質(zhì)心計(jì)算公式為:

(29)

其中:ci為要計(jì)算的第i個(gè)簇的質(zhì)心;Ci為第i個(gè)簇;mi為第i個(gè)簇中節(jié)點(diǎn)的個(gè)數(shù);x為傳感器節(jié)點(diǎn)到質(zhì)心的加權(quán)距離。

節(jié)點(diǎn)選擇算法是為了確定網(wǎng)絡(luò)中在每一輪需要被操作的節(jié)點(diǎn),算法步驟如下。

算法1 S-ERDC算法。

(2) 按照(28)式根據(jù)節(jié)點(diǎn)剩余能量和存儲空間以及到基站的距離計(jì)算所有節(jié)點(diǎn)間的加權(quán)距離。

(3) 將基站和到基站加權(quán)距離最遠(yuǎn)的點(diǎn)作為2個(gè)簇頭。每個(gè)節(jié)點(diǎn)到基站的距離為di,0,到基站距離最遠(yuǎn)節(jié)點(diǎn)的距離為d0,far=find(maxdi,0),到基站距離最遠(yuǎn)的節(jié)點(diǎn)為sfar。

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

(5) 將每個(gè)節(jié)點(diǎn)按照其到質(zhì)心的加權(quán)距離,指派到最近的質(zhì)心,形成C1、C22個(gè)簇。

(6) 根據(jù)(29)式重新計(jì)算每個(gè)簇的質(zhì)心c1、c2,直到質(zhì)心不發(fā)生改變。

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

2.2 基于煙花算法的MC節(jié)點(diǎn)訪問調(diào)度算法

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

對于爆炸產(chǎn)生的火花,一般只是產(chǎn)生在煙花的周圍,這樣不斷迭代容易使得種群陷入局部最優(yōu)解。本文對煙花爆炸產(chǎn)生的火花進(jìn)行差分變異,保證產(chǎn)生的火花的多樣性。火花差分變異是對煙花爆炸產(chǎn)生的所有火花進(jìn)行差分變異操作,其中差分變異是將2個(gè)個(gè)體的差向量作為第3個(gè)個(gè)體的隨機(jī)變化源,將差向量加權(quán)后按照一定的規(guī)則與第3個(gè)個(gè)體求和從而產(chǎn)生變異個(gè)體。本文中將一次迭代中產(chǎn)生火花的最優(yōu)值作為需要變異的個(gè)體,產(chǎn)生的火花依次交替作為隨機(jī)變異源,如第1個(gè)火花與第2個(gè)火花作為變異源與本體結(jié)合產(chǎn)生第1個(gè)變異個(gè)體,第2個(gè)火花與第3個(gè)火花作為變異源與本體結(jié)合產(chǎn)生第2個(gè)變異個(gè)體,依此類推可以產(chǎn)生和火花數(shù)目相同的變異個(gè)體?；鸹ú罘肿儺愡^程為:

(30)

其中:X為第g次迭代產(chǎn)生的火花數(shù)目;xi,g為第g次迭代產(chǎn)生的第i個(gè)火花;xbest,g為第g次迭代產(chǎn)生的最優(yōu)火花作為的變異本體;F為加權(quán)系數(shù);vi,g為第g次迭代中產(chǎn)生的第i個(gè)變異火花。

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

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

MC行駛路徑規(guī)劃算法是本文核心算法。本文所設(shè)計(jì)的DEFW算法結(jié)合了煙花算法和差分進(jìn)化算法,具體操作步驟如下。

算法2 DEFW算法。

輸出:f。

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

(3) 當(dāng)i≤I時(shí),對初始種群進(jìn)行煙花爆炸操作產(chǎn)生n個(gè)火花。

(4) 計(jì)算每個(gè)火花的適應(yīng)度值f。

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

(6) 計(jì)算差分火花的適應(yīng)度值f。

(7) 對煙花個(gè)體進(jìn)行高斯變異操作。

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

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

3 仿真與分析

對本文提出的模型和使用的算法進(jìn)行實(shí)驗(yàn)仿真,并給出實(shí)驗(yàn)分析。實(shí)驗(yàn)所采用軟硬件系統(tǒng)為i7-8700cup、8 GiB內(nèi)存、Matlab2017b仿真軟件和Windows10操作系統(tǒng)。

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

3.1 不同算法收斂情況比較

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

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

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

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

3.2 不同調(diào)度算法下網(wǎng)絡(luò)能耗

本實(shí)驗(yàn)為了驗(yàn)證同一個(gè)WSN中采用DEFW算法在持續(xù)多輪對MC進(jìn)行調(diào)度時(shí)MC單位能耗變化情況。首先采用實(shí)驗(yàn)1中的方法產(chǎn)生一組實(shí)驗(yàn)數(shù)據(jù),然后分別使用DEFW、FWA、GA算法對其進(jìn)行40輪的充電與數(shù)據(jù)收集調(diào)度,并求出每一輪的目標(biāo)值ft。DEFW、FWA、GA算法對MC進(jìn)行40輪的能量補(bǔ)充與數(shù)據(jù)收集調(diào)度下,MC單位能耗的變化情況對比如圖5所示。

圖5 3種算法調(diào)度下網(wǎng)絡(luò)運(yùn)行40輪MC單位能耗對比

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

4 結(jié) 論

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