吳寶瑜,萬 鵬,王高峰,程瑜華

(杭州電子科技大學(xué)電子信息學(xué)院,杭州 310018)

無線傳感器網(wǎng)絡(luò)是由大量具有傳感、數(shù)據(jù)處理和無線通信能力的傳感器節(jié)點(diǎn)組織成為的一個(gè)網(wǎng)絡(luò)結(jié)構(gòu)[1]。網(wǎng)絡(luò)通過傳感器采集所需要的物理信息,發(fā)送給基站中心進(jìn)行數(shù)據(jù)處理,進(jìn)而傳輸給信息采集者。大部分的傳感器采用電池提供能量,為了傳感器網(wǎng)絡(luò)能夠持續(xù)有效地工作,必須定期地對(duì)電池進(jìn)行更換,避免因電池能量耗盡后導(dǎo)致傳感器失效。但有些傳感器網(wǎng)絡(luò)的部署環(huán)境較惡劣,導(dǎo)致傳感器的電池更換不方便。在一些研究中,為延長無線傳感網(wǎng)的網(wǎng)絡(luò)壽命,對(duì)傳感器網(wǎng)絡(luò)采用更好的組網(wǎng)方式和能量均衡算法[2],盡可能地減少能量消耗,但這些方式只是減緩了能量耗盡的過程,并不能從根本上解決能量不足的問題。為應(yīng)對(duì)這一問題,具有無線充電功能的傳感器網(wǎng)絡(luò),即無線可充電傳感器網(wǎng)絡(luò)應(yīng)運(yùn)而生[3-5]。對(duì)于無線可充電傳感器網(wǎng)絡(luò),當(dāng)前采用的無線充電方式可分為靜態(tài)充電方式[6-7]和動(dòng)態(tài)充電方式[8-14]兩種。對(duì)于靜態(tài)充電方式,可以看作充電源是固定不動(dòng)的,傳感器接收來自固定充電源的電磁能量,但由于現(xiàn)有遠(yuǎn)距離電磁輻射充電技術(shù)本身的局限性,很難克服因距離遠(yuǎn)所帶來的能量傳輸衰減問題。隨著磁耦合諧振充電技術(shù)的快速發(fā)展,近距離快速高效地給傳感器無線充電技術(shù)越來越成熟[15-17]。通過配備高容量電池的移動(dòng)小車移動(dòng)至傳感器附近給傳感器充電的動(dòng)態(tài)充電方式受到了很多人的關(guān)注。文獻(xiàn)[8]提出了一種移動(dòng)充電小車的協(xié)作調(diào)度算法,該算法是一種時(shí)空計(jì)費(fèi)調(diào)度算法,通過調(diào)整傳感器的充電優(yōu)先順序,減少死亡節(jié)點(diǎn)的個(gè)數(shù),來保證整個(gè)傳感器網(wǎng)絡(luò)的有效運(yùn)行;文獻(xiàn)[9]提出在大規(guī)模無線傳感網(wǎng)中,根據(jù)不同傳感器節(jié)點(diǎn)的能量需求,優(yōu)化充電小車的個(gè)數(shù),盡可能地減少充電小車的數(shù)量使其達(dá)到最優(yōu);文獻(xiàn)[10]提出充電吞吐量的概念和一種新的充電范例,為移動(dòng)充電小車找到最佳的充電閉合路徑,使其包括最多的傳感器節(jié)點(diǎn)數(shù)量,即小車在周期T的時(shí)間內(nèi),能夠給盡量多提出充電要求的節(jié)點(diǎn)進(jìn)行充電。文獻(xiàn)[11]將小車的路徑規(guī)劃問題論述為一個(gè)旅行商問題TSP(Traveling Salesman Problem),并進(jìn)行分析建模。文獻(xiàn)[12]基于充電小車能量有限的前提,將整個(gè)傳感器網(wǎng)絡(luò)分為不同的充電區(qū)域,充電小車通過給不同區(qū)域的傳感器進(jìn)行充電,對(duì)整個(gè)傳感器網(wǎng)絡(luò)進(jìn)行能量補(bǔ)充。文獻(xiàn)[13]結(jié)合傳感器網(wǎng)絡(luò)中的通信抗干擾技術(shù)和能量補(bǔ)給策略,對(duì)傳感器網(wǎng)絡(luò)進(jìn)行分簇,由于簇頭節(jié)點(diǎn)能量消耗較大,先對(duì)簇頭節(jié)點(diǎn)進(jìn)行能量補(bǔ)充,再對(duì)一般節(jié)點(diǎn)進(jìn)行能量補(bǔ)充,能夠使得傳感器網(wǎng)絡(luò)更好地維持其生命周期。文獻(xiàn)[14]提出一種虛擬骨干網(wǎng)的移動(dòng)能量補(bǔ)給策略,給特定骨干節(jié)點(diǎn)進(jìn)行充電的方式補(bǔ)充能量消耗較大的傳感器節(jié)點(diǎn)。以上的動(dòng)態(tài)充電算法規(guī)劃中,無論是增加充電小車的數(shù)量還是考慮時(shí)空關(guān)系,都是為了解決傳感器能耗特別大導(dǎo)致其生命周期很短,或者是傳感器網(wǎng)絡(luò)規(guī)模較大導(dǎo)致單個(gè)充電小車滿足不了充電需求的問題。但有研究表明,傳感器的能耗一般很低,傳感器的生命周期相對(duì)較長,對(duì)于充電時(shí)效性并無非常苛刻的要求,而且實(shí)際的傳感器網(wǎng)絡(luò)中傳感器的能耗值差異較大[18]。本文著重研究在傳感器網(wǎng)絡(luò)能耗分布不均的情況下,通過對(duì)傳感器能耗進(jìn)行分級(jí),結(jié)合蟻群算法[19]對(duì)路徑的計(jì)算,優(yōu)化充電小車移動(dòng)總路徑,從而減小充電小車的損耗,提高經(jīng)濟(jì)性。

1 問題描述

1.1 模型建立

在一個(gè)L×L大小的二維空間中,部署了一個(gè)無線可充電傳感器網(wǎng)絡(luò),其中包括N個(gè)無線可充電傳感器、一個(gè)移動(dòng)無線充電小車、網(wǎng)絡(luò)中心位置的基站服務(wù)站。網(wǎng)絡(luò)模型如圖1所示。整個(gè)無線可充電傳感器網(wǎng)絡(luò)構(gòu)成一個(gè)無向圖G=(V,E),V={v0,v1,v2,…vN}表示基站和傳感器集合,v0表示基站位置,vi表示傳感器位置,E表示傳感器兩兩之間的鏈路集合。

每個(gè)傳感器的能耗值各不相同,用Pi表示。在無線傳感器網(wǎng)絡(luò)中,無線傳感器的能量消耗功率Pi是與傳感器數(shù)據(jù)的發(fā)送量和接收量以及信息采集直接相關(guān)的,模型如圖2所示[11]。

圖2 傳感器能量消耗模型

圖2中,假設(shè)在t時(shí)刻,i傳感器向j傳感器發(fā)送數(shù)據(jù)的速率為gij(t)bit/s,發(fā)送數(shù)據(jù)的功率因子為Cij,單位為J/bit,那么對(duì)于節(jié)點(diǎn)i來說,t時(shí)刻用于發(fā)送數(shù)據(jù)的功率Ps(t)由式(1)表示,同樣的在t時(shí)刻,節(jié)點(diǎn)i接收k節(jié)點(diǎn)發(fā)送來的數(shù)據(jù)的速率為gki(t)bit/s,相應(yīng)的功率因子為ρ,單位為J/bit,那么在t時(shí)刻接收數(shù)據(jù)的功率Pr(t)由式(2)表示,Pc(t)為傳感器采集信息的能量消耗功率,則在t時(shí)刻,i傳感器的能量消耗功率Pi(t)由式(3)表示:

(1)

(2)

Pw(t)=Ps(t)+Pr(t)+Pc(t)

(3)

從上文的傳感器能量消耗模型可知,每個(gè)傳感器由于發(fā)送與接收數(shù)據(jù)量并不都是一致的,會(huì)產(chǎn)生不同的能量消耗率,則每個(gè)傳感器的能量狀態(tài)都是不同的,具有不同的能量補(bǔ)充需求。

為避免傳感器能量耗盡導(dǎo)致網(wǎng)絡(luò)失效,充電小車需定時(shí)地給網(wǎng)絡(luò)中能量小于閾值ETH的傳感器進(jìn)行一對(duì)一的能量補(bǔ)充。若用ES表示傳感器當(dāng)前電池容量,則傳感器生命周期為Ti,易得Ti=(ES-ETH)/Pi。傳統(tǒng)的傳感器網(wǎng)絡(luò)小車充電方式為遍歷全部的傳感器節(jié)點(diǎn),根據(jù)實(shí)際的需求進(jìn)行選擇性充電。但考慮到實(shí)際傳感器網(wǎng)絡(luò)中傳感器能耗值的差異,可選擇能耗值相近的傳感器作為一個(gè)集合,將整個(gè)傳感器網(wǎng)絡(luò)分為若干個(gè)包含不同能耗級(jí)別傳感器的集合,充電小車每次給不同傳感器節(jié)點(diǎn)集合進(jìn)行充電。圖3為充電小車給某一能耗級(jí)的傳感器充電的示意圖。

圖3 小車給某一能耗級(jí)傳感器充電示意圖

1.2 問題定義

我們研究的問題為一個(gè)充電小車周期性充電問題:在一個(gè)周期性的時(shí)間T內(nèi),根據(jù)傳感器能量的需求,分不同的輪數(shù)給傳感器進(jìn)行能量補(bǔ)充,直至能量需求最小的傳感器節(jié)點(diǎn)都被補(bǔ)充過一遍能量。其中充電周期T的定義由式(4)得到。

T=Tp+Tvac+Tc

(4)

式中:TP表示小車充電中移動(dòng)消耗的總時(shí)間;Tvac表示充電小車?？吭诜?wù)站時(shí)間;Tc表示停留在傳感器節(jié)點(diǎn)充電的時(shí)間,優(yōu)化的目標(biāo)為最大化駐站時(shí)間比Tvac/T。文獻(xiàn)[11]證明了最大化駐站時(shí)間比就是最小化移動(dòng)時(shí)間,假定充電小車的移動(dòng)速度是一定的,忽略充電時(shí)間,則最終就是優(yōu)化移動(dòng)路徑使其最小的問題。總移動(dòng)路徑用LTSP來代替,那么問題就轉(zhuǎn)化為TSP問題[20],即小車在對(duì)傳感器節(jié)點(diǎn)進(jìn)行充電過程的路徑規(guī)劃問題,式(4)轉(zhuǎn)變?yōu)槭?5):

T=TTSP+Tvac+Tc

(5)

式中:TTSP為充電小車在充電過程中移動(dòng)的時(shí)間。于是,在一個(gè)充電周期內(nèi),保證每個(gè)傳感器節(jié)點(diǎn)都能夠得到能量補(bǔ)充的情況下。由于充電小車并不是一次性遍歷完所有的傳感器節(jié)點(diǎn),因此每一次遍歷的過程都可看作一個(gè)TSP問題,總移動(dòng)路徑即為每次遍歷路徑的總和。最小化充電小車的移動(dòng)總路徑LTSP成為主要優(yōu)化目標(biāo)。

在小車移動(dòng)時(shí)間TTSP內(nèi),傳感器也會(huì)進(jìn)行能量消耗的過程。為了保證沒有傳感器出現(xiàn)能量耗盡的情況,將前文的能量閾值ETH的確定進(jìn)行充電約束,即保證在小車移動(dòng)時(shí)間內(nèi),每個(gè)傳感器的能量閾值生命周期能夠大于總充電移動(dòng)時(shí)間。如式(6)所示:

ETH/Pi>TTSP

(6)

2 算法分析和設(shè)計(jì)

2.1 算法思想

充電小車對(duì)傳感器網(wǎng)絡(luò)進(jìn)行路徑規(guī)劃的傳統(tǒng)算法優(yōu)化中,小車通常會(huì)一次性遍歷所有傳感器節(jié)點(diǎn),進(jìn)而根據(jù)節(jié)點(diǎn)的充電需求決定是否對(duì)節(jié)點(diǎn)進(jìn)行能量補(bǔ)充,這種按需充電的方式會(huì)大大增加小車不必要的移動(dòng)能量消耗。而在實(shí)際的傳感器網(wǎng)絡(luò)中,能耗分布是很不均衡的。基于此,在相同的時(shí)間周期內(nèi)(即所有傳感器節(jié)點(diǎn)都補(bǔ)充過一遍能量的時(shí)間內(nèi)),將能量補(bǔ)充路徑分成多個(gè)部分進(jìn)行,可使得小車遍歷路徑值有較優(yōu)的計(jì)算結(jié)果。根據(jù)傳感器網(wǎng)絡(luò)的各傳感器的能耗差異,給傳感器網(wǎng)絡(luò)分為能耗級(jí)別不同的集合,基于此,本文提出非固定周期算法和固定周期轉(zhuǎn)移算法兩種算法。對(duì)于非固定周期算法,充電小車根據(jù)每個(gè)能耗級(jí)別中傳感器最小的周期進(jìn)行充電,充電小車每次出動(dòng)的時(shí)間間隔是不固定的。針對(duì)非固定周期算法出動(dòng)頻數(shù)較多的劣勢,進(jìn)一步提出一種固定周期算法,充電小車每次出動(dòng)的時(shí)間是固定的。本文在固定周期算法中,又創(chuàng)新性地提出了將部分能耗級(jí)別低的傳感器向能耗高級(jí)別高的傳感器集合轉(zhuǎn)移的優(yōu)化算法,稱為固定周期轉(zhuǎn)移算法,優(yōu)化總充電小車遍歷路徑值。

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

2.2.1 能耗分級(jí)

給定傳感器集合V之后,給出對(duì)應(yīng)每個(gè)傳感器的能耗值Pi,則每個(gè)傳感器的生命周期Ti=(ES-ETH)/Pi,找出其中最大值Tmax和最小值Tmin,計(jì)算(Tmax-Tmin)/Tmin的值,并向上取整可得待充電的傳感器集合的分級(jí)數(shù),記為k。由此可得能耗分級(jí)后的傳感器集合VV={VV1,VV2,…,VVk},VVk表示集合V中生命周期值在kTmin和(k+1)Tmin之間的傳感器節(jié)點(diǎn)。

2.2.2 非固定周期算法

在進(jìn)行能耗分級(jí)之后,找出網(wǎng)絡(luò)中具有最小剩余生命周期傳感節(jié)點(diǎn)所在的能耗級(jí),充電小車對(duì)此能耗級(jí)中的所有傳感器采用蟻群算法[19]進(jìn)行充電路徑計(jì)算。第i個(gè)傳感節(jié)點(diǎn)的剩余生命周期定義為(Ei-ETH)/Pi,其中Ei為能耗級(jí)中第i個(gè)傳感節(jié)點(diǎn)的剩余電池能量。在充電小車完成一次充電后,算法將更新網(wǎng)絡(luò)中各傳感節(jié)點(diǎn)的剩余生命周期,并重新尋找具有最小剩余生命周期傳感節(jié)點(diǎn)的能耗級(jí),然后進(jìn)行充電。算法過程描述如下:

輸入:{v0,v1,v2,…vN},Pi,ES

輸出:LTSP

①根據(jù)(ES-ETH)/Pi計(jì)算生命周期;

②計(jì)算(Tmax-Tmin)/Tmin的值,并向上取整,求得能耗分級(jí)數(shù)k,以及相應(yīng)的能耗分級(jí)后的傳感器集合VV={VV1,VV2,…VVk};

③根據(jù)(Ei-ETH)/Pi求得每個(gè)傳感節(jié)點(diǎn)的剩余生命周期;

④找出具有最小剩余生命周期傳感節(jié)點(diǎn)的能耗級(jí)VVi并給其中的傳感器充電;

⑤用蟻群算法ACATSP(VVi)計(jì)算每次充電路徑值;

⑥重復(fù)步驟③,④,⑤直至全部的節(jié)點(diǎn)都被補(bǔ)充過一遍能量;

⑦求小車總遍歷路徑LTSP=∑ACATSP(VVi)

算法中每次選取的VVi是根據(jù)具體能耗級(jí)的最小剩余生命周期確定的。從能耗級(jí)最低的VV1開始,直到能耗級(jí)最高的VVk被充電的過程中,有些VVi可能被多次充電,即出現(xiàn)充電小車的出動(dòng)次數(shù)較多,導(dǎo)致充電移動(dòng)資源浪費(fèi)的問題。為減小這種移動(dòng)資源的浪費(fèi),提出了固定周期轉(zhuǎn)移算法,進(jìn)一步優(yōu)化小車總移動(dòng)路徑。

2.2.3 固定周期轉(zhuǎn)移算法

第1階段算法描述如下:

輸入:{v0,v1,v2,…vN},Pi,ES

輸出:LTSP

①根據(jù)(ES-ETH)/Pi計(jì)算生命周期;

②計(jì)算(Tmax-Tmin)/Tmin的值,并向上取整,求得能耗分級(jí)數(shù)k,以及相應(yīng)的能耗分級(jí)后的傳感器集合VV={VV1,VV2,…,VVk};

③求得小車每次遍歷的集合VX={VX1,VX2,…,VXk};

第2階段:遍歷一遍VX集合中的各個(gè)VV變量,找出只出現(xiàn)一次的VV集合,假設(shè)有M個(gè),按照VVi的下標(biāo)值從小到大排列并依次由集合C′1,C′2,…,C′M來代替,隨后按下標(biāo)從大到小地進(jìn)行集合間傳感器節(jié)點(diǎn)轉(zhuǎn)移。具體過程如下:初始化i=1,將C′M中的傳感器元素每次轉(zhuǎn)移i個(gè)到C′M-1中,每轉(zhuǎn)移一次,計(jì)算一次遍歷的總路徑值LTSP,將路徑值減小的轉(zhuǎn)移節(jié)點(diǎn)記錄下來;令i=i+1,在路徑值減小的轉(zhuǎn)移節(jié)點(diǎn)中每次轉(zhuǎn)移i個(gè)到C′M-1中,同樣計(jì)算每次遍歷的總路徑值;這樣,直到找到最小路徑值對(duì)應(yīng)的最優(yōu)轉(zhuǎn)移節(jié)點(diǎn)及個(gè)數(shù)。

然后對(duì)C′M-1和C′M-2進(jìn)行上述類似的轉(zhuǎn)移過程,直至得到最優(yōu)路徑下的最優(yōu)轉(zhuǎn)移節(jié)點(diǎn)及個(gè)數(shù);最后,直到完成C′2到C′1的轉(zhuǎn)移過程。取最優(yōu)的轉(zhuǎn)移組合以及在這個(gè)轉(zhuǎn)移組合下的最優(yōu)轉(zhuǎn)移節(jié)點(diǎn),將此時(shí)的最優(yōu)路徑數(shù)LTSP作為最終算法優(yōu)化后的路徑數(shù)。

第2階段算法描述如下:

輸入:VX

輸出:LTSP

①找出VX集合中只出現(xiàn)一次的VV變量,個(gè)數(shù)記為M;將每個(gè)變量值從小到大排序并由C′1,C′2,…,C′M代替;

②初始化i=1,將C′M中的元素每次i個(gè)轉(zhuǎn)移到C′M-1中,每轉(zhuǎn)移一次計(jì)算一次LTSP值,記錄路徑值減小的轉(zhuǎn)移節(jié)點(diǎn);

③令i=i+1,從路徑減小的元素里每次轉(zhuǎn)移i個(gè)節(jié)點(diǎn),直到找出最小路徑值下的最優(yōu)節(jié)點(diǎn)轉(zhuǎn)移數(shù);

④對(duì)C′M-1和C′M-2重復(fù)步驟2和步驟3的過程,得到最優(yōu)節(jié)點(diǎn)轉(zhuǎn)移數(shù),直到計(jì)算完C′2和C′1;

⑤對(duì)比每個(gè)轉(zhuǎn)移組合下的路徑值,選取最優(yōu)轉(zhuǎn)移組合下的轉(zhuǎn)移節(jié)點(diǎn)數(shù);

⑥更新VX集合,得到此集合下最小值LTSP。

這里要說明的一點(diǎn)是,倘若經(jīng)過第2階段算法的轉(zhuǎn)移規(guī)則之后,并不能使小車的路徑數(shù)有所減少,不進(jìn)行第2階段的轉(zhuǎn)移過程。

為了便于理解第2階段的轉(zhuǎn)移過程,下面用一個(gè)具體的例子來說明節(jié)點(diǎn)轉(zhuǎn)移算法的轉(zhuǎn)移過程:

無線可充電傳感器網(wǎng)絡(luò)中有一個(gè)位于中心的基站服務(wù)站和10個(gè)傳感器節(jié)點(diǎn)v1～v10,根據(jù)能耗值的不同,將整個(gè)傳感器網(wǎng)絡(luò)分成了3個(gè)能耗級(jí)別VV1,VV2,VV3。3個(gè)能耗級(jí)別所對(duì)應(yīng)的充電周期為T,2T,3T,于是對(duì)于充電小車每次遍歷的路徑集合分別為VX1=VV1,VX2=VV1∪VV2,VX3=VV1∪VV3,如圖4所示為不同能耗級(jí)傳感器集合,圖5(a)～(c)為一個(gè)周期內(nèi)總共3次不同的遍歷路徑示意圖。

圖4 不同能耗分級(jí)圖

圖5 小車充電遍歷路線示意圖

圖6(a)～(c)為進(jìn)行第2階段算法的轉(zhuǎn)移規(guī)則之后得到的路徑遍歷示意圖。轉(zhuǎn)移之后的節(jié)點(diǎn),由于能耗小于集合中其他的傳感器節(jié)點(diǎn),即生命周期大于其他的節(jié)點(diǎn),則不影響其本身的能量補(bǔ)充過程。從圖中可以看出,由于v7特別靠近v3v4,將原屬于VV3的v7節(jié)點(diǎn)轉(zhuǎn)移到VV2中,可以減小路徑值。圖5(a)和圖6(a)路徑相同,圖5(b)和圖6(b)差距很小,轉(zhuǎn)移前與轉(zhuǎn)移后的路徑值主要為圖5(c)和圖6(c)的大小比較,很明顯后者較小,即轉(zhuǎn)移后的路徑值會(huì)變小。當(dāng)傳感器節(jié)點(diǎn)數(shù)較多時(shí),可以使用節(jié)點(diǎn)轉(zhuǎn)移規(guī)則找出最適合的轉(zhuǎn)移方式。

圖6 轉(zhuǎn)移節(jié)點(diǎn)后小車充電遍歷路線示意圖

2.3 算法復(fù)雜度分析

本文研究的問題本質(zhì)是一個(gè)NP-hard問題。能耗分級(jí)階段,主要是根據(jù)能耗進(jìn)行分類,只要計(jì)算完傳感器節(jié)點(diǎn)的個(gè)數(shù)即可,算法時(shí)間復(fù)雜度為O(1)。在求解TSP問題階段,時(shí)間復(fù)雜度很大,采用蟻群算法,能夠較好地解決TSP問題,但是算法的復(fù)雜度并沒有降低,其復(fù)雜度為O(2n·n2)[20]。但是在此過程中由于采用了分級(jí)策略,減小了每次的n值,能夠減小算法的計(jì)算量。在節(jié)點(diǎn)轉(zhuǎn)移過程中,只考慮上一級(jí)向下一級(jí)逐級(jí)轉(zhuǎn)移的節(jié)點(diǎn)轉(zhuǎn)移方式,由于是k級(jí)的能耗分級(jí),規(guī)則定義可轉(zhuǎn)移所有節(jié)點(diǎn),則所需的時(shí)間復(fù)雜度為O(n2)。

3 仿真實(shí)驗(yàn)與結(jié)果分析

為驗(yàn)證本文所提出的非固定周期算法和固定周期轉(zhuǎn)移算法的有效性,這里將它們與傳統(tǒng)周期遍歷算法[14]進(jìn)行了比較。參照文獻(xiàn)[14]中對(duì)傳感器網(wǎng)絡(luò)中的參數(shù)設(shè)置,將傳感器網(wǎng)絡(luò)布置在1 000 m×1 000 m 大小的正方形區(qū)域內(nèi),傳感器的電池容量為10 kJ,基站服務(wù)站的位置和小車的初始位置為中心位置,坐標(biāo)為(500 m,500 m)。在仿真的過程中,通過改變傳感器的個(gè)數(shù),傳感器的能耗值范圍,比較算法的路徑值。

在上文中的多種傳感器個(gè)數(shù)以及能耗范圍設(shè)置下的仿真實(shí)驗(yàn)中,由于TSP問題的復(fù)雜度與傳感器個(gè)數(shù)n相關(guān),考慮到計(jì)算量,這里選取了一組能耗級(jí)別為3級(jí),傳感器個(gè)數(shù)為20的路徑遍歷仿真結(jié)果。

圖7為傳統(tǒng)周期遍歷算法小車充電路徑圖。

圖7 傳統(tǒng)周期遍歷算法路徑圖

圖8(a)～(c)為非固定周期算法小車充電路徑圖。

圖8 非固定周期算法充電路徑圖

圖9(a)～(c)為固定周期轉(zhuǎn)移算法小車充電路徑圖。

圖9 固定周期轉(zhuǎn)移算法充電路徑圖

由圖7、圖8和圖9可以看出,固定周期轉(zhuǎn)移算法在一個(gè)周期T內(nèi)只需要出動(dòng)3次,總的路徑值最少;傳統(tǒng)周期遍歷算法也出動(dòng)3次,但每次遍歷所有傳感器節(jié)點(diǎn),所以路徑值最多;非固定周期算法每次遍歷傳感器的路徑值較少。由于非固定周期算法的特點(diǎn),圖8(a)的移動(dòng)方式需要2次的充電過程,加上(b)、(c)各1次,小車總的出動(dòng)頻數(shù)為4次,計(jì)算得到的總路徑值比固定周期算法得到的總路徑值多。

圖10和圖11進(jìn)一步給出了在不同傳感器數(shù)量、不同能耗分級(jí)下算法的有效性。圖10為各節(jié)點(diǎn)能耗在0.1 J/s～0.3 J/s(對(duì)應(yīng)能耗分級(jí)為3級(jí))范圍內(nèi)隨機(jī)取值,三種算法在傳感器個(gè)數(shù)為20,25,30,35時(shí),相同時(shí)間內(nèi)(由于傳感器最小能耗都為0.1 J/s,則每個(gè)傳感網(wǎng)絡(luò)的生命周期都相同)小車遍歷的充電路徑值。圖11為在保證傳感器網(wǎng)絡(luò)的個(gè)數(shù)為30時(shí),在0.1 J/s～0.3 J/s,0.075 J/s～0.3 J/s,0.06 J/s～0.3 J/s,0.05 J/s～0.3 J/s(分別對(duì)應(yīng)能耗分級(jí)為3級(jí),4級(jí),5級(jí),6級(jí))四種能耗分布下(每個(gè)傳感器網(wǎng)絡(luò)的最小能耗都不同,則每個(gè)傳感器網(wǎng)絡(luò)都具有不同的生命周期)三種算法小車遍歷的充電路徑值。從圖10和圖11可以看出,本文提出的2種算法都要比傳統(tǒng)的算法的路徑值要小。

圖10 小車總路徑與傳感器數(shù)圖

圖11 小車總路徑與分級(jí)數(shù)圖

圖12給出了3種算法在不同能耗分級(jí)數(shù)下小車出動(dòng)頻數(shù)的比較,可以看到,在相同的時(shí)間周期內(nèi),固定周期轉(zhuǎn)移算法與傳統(tǒng)周期遍歷算法的出動(dòng)頻數(shù)是一樣的,出動(dòng)頻數(shù)都為能耗級(jí)數(shù)的值,而非固定周期算法的小車出動(dòng)頻數(shù)較多,隨著能耗分級(jí)的增加,次數(shù)增加更加明顯。

圖12 小車出動(dòng)頻數(shù)比較圖

固定周期轉(zhuǎn)移算法在相同的周期時(shí)間內(nèi),小車遍歷的路徑值是最少的;傳統(tǒng)周期遍歷算法由于要遍歷全部的傳感器節(jié)點(diǎn),必然浪費(fèi)了大量的移動(dòng)能量消耗;非固定周期算法由于較多的出動(dòng)頻數(shù),即使每次遍歷節(jié)點(diǎn)較少,相對(duì)于固定周期轉(zhuǎn)移算法,同樣會(huì)增加不必要的移動(dòng)能量消耗。綜上所述,固定周期轉(zhuǎn)移算法無論在充電移動(dòng)總路徑上,還是小車出動(dòng)頻數(shù)上,較其他兩種算法都具有優(yōu)勢。

4 結(jié)束語

本文基于無線可充電傳感器網(wǎng)絡(luò)的能耗差異,提出兩種能耗分級(jí)的充電規(guī)劃算法。一種是非固定周期算法,另一種是結(jié)合節(jié)點(diǎn)轉(zhuǎn)移規(guī)則得到的固定周期轉(zhuǎn)移算法。與傳統(tǒng)的周期性小車充電算法不同,兩種算法能夠根據(jù)傳感器網(wǎng)絡(luò)的能耗狀態(tài),給傳感器網(wǎng)絡(luò)分級(jí)充電。在與傳統(tǒng)算法比較的過程中,在相同的參數(shù)條件下,能夠減小充電小車遍歷路徑值。其中,固定周期轉(zhuǎn)移算法能夠得到更小的路徑值。仿真結(jié)果表明算法在求解最優(yōu)路徑值上的優(yōu)異性能。在以后的研究中,可以尋找最優(yōu)的能耗分級(jí)數(shù)以及更有效的節(jié)點(diǎn)轉(zhuǎn)移方法,進(jìn)一步優(yōu)化遍歷路徑值。