楊 佳， 盛 歡， 許 強

(1.重慶理工大學 電氣與電子工程學院，重慶 400054; 2.重慶工商大學 計算機科學與信息工程學院,重慶 400067)

0 引 言

無線可充電傳感器網(wǎng)絡(wireless rechargeable sensor networks,WRSNs)[1]由于能解決無線傳感器網(wǎng)絡(wireless sensor networks,WSNs)電池能量受限問題而受到廣泛關注，采用無線充電技術(shù) (wireless charging technique,WCT)[2]能夠?qū)W(wǎng)絡節(jié)點及時補充能量，克服惡劣環(huán)境或人為等因素導致的節(jié)點能量不足，從而保證網(wǎng)絡的正常運行。在實際應用中，無線移動充電設備(wireless mobile charging equipment，WCE)的能量是有限的，為了更高效地分配設備自身能量，有必要研究WCE能量受限時的充電路徑規(guī)劃問題。He L等人[3]提出最近優(yōu)先充電算法NJNP，始終選擇距離WCE最近的節(jié)點充電，很好地減少了WCE的移動耗能，但該方法忽略了WCE的充電效率問題。劉蘊嫻等人[4]提出能量收益的路徑規(guī)劃算法MMAS-CM，總是以節(jié)點剩余能量最少的標準來選取下一個充電節(jié)點，但未考慮節(jié)點地理位置對充電順序的重要影響。Xu J等人[5]提出使WCE總消耗值最小的節(jié)點以均衡壽命的方式充電，但該方法沒有合理地估算到請求充電節(jié)點的能量閾值。蔣嬋等人[6]提出綜合考慮節(jié)點的位置和能量信息，在限定的路徑長度下為節(jié)點補充能量的方法。Feng Y等人[7]提出以最小節(jié)點失效率為目標的路徑規(guī)劃算法，雖能有效地減少網(wǎng)絡中節(jié)點的死亡數(shù)量，但沒有考慮到充電節(jié)點之間的優(yōu)先級問題，容易造成WCE充電路徑不合理而消耗太多的移動能量，使WCE的充電利用率較低。以上研究大多數(shù)考慮了WCE的行駛能量和充電能量共用時的充電路徑規(guī)劃，很少綜合考慮其能量分開且均受限[8]時的充電路徑規(guī)劃。

本文提出一種基于節(jié)點充電優(yōu)先級(max-min ant system and charging node priority，MMAS-CNP)的路徑規(guī)劃算法，在WCE行駛距離一定時攜帶有限的充電容量為網(wǎng)絡節(jié)點及時地充電，并合理地估算網(wǎng)絡節(jié)點的能量閾值，綜合考慮節(jié)點的地理位置、剩余能量和能量消耗率[9]這3個因素比較充電節(jié)點之間的優(yōu)先級，從而確定節(jié)點的充電順序，最后采用MMAS算法約束WCE的能量受限問題，以節(jié)點的充電優(yōu)先級為依據(jù)選取下一個充電節(jié)點，最終WCE選擇一條使節(jié)點充電優(yōu)先級最高的路徑來進行能量的補充。

1 系統(tǒng)模型

WRSN充電模型如圖1所示，該網(wǎng)絡由可充電傳感器節(jié)點、基站(base station，BS)、服務站和1個WCE組成[10]。假設在方形網(wǎng)絡區(qū)域內(nèi)，剩余能量低于閾值的節(jié)點被稱為“需要充電的節(jié)點”，反之為“不需充電節(jié)點”， WCE只為“需要充電的節(jié)點”充電并且根據(jù)優(yōu)先級進行選擇。

圖1 網(wǎng)絡充電模型

WCE在行駛過程中主要有3種工作狀態(tài)[11]，分別是移動狀態(tài)、充電狀態(tài)和休假狀態(tài)，如圖2所示。

圖2 WCE狀態(tài)轉(zhuǎn)移

2 確定節(jié)點的能量閾值

本文對網(wǎng)絡中的節(jié)點采取按需充電的方式，只有當節(jié)點能量低于閾值時，該節(jié)點才會被選擇充電，因此對能量閾值[12]的選取相當重要，閾值過大或過小均會導致網(wǎng)絡性能不佳，故有以下具體分析。

1)WCE攜帶的充電容量Ec

由于WCE的能量受限，因此需保證WCE每次充電服務的節(jié)點數(shù)量不能過少也不能過多，即WCE實際充電服務的節(jié)點數(shù)量應當不大于WCE可充電服務的節(jié)點數(shù)量。因此可得

Ec/Emax×ω≤λTN

(1)

式中ω(0<ω<1)為期望的WCE能量利用率，Emax為節(jié)點的最大能量；在T時間內(nèi)，網(wǎng)絡節(jié)點數(shù)量為N，WCE對“需要充電節(jié)點”的平均到達率為λ，具體取值為

(2)

(3)

將式(2)、式(3)代入式(1)中并化簡得到

(4)

2)網(wǎng)絡的剩余能量

WCE按順序依次為節(jié)點補充能量時，無法保證為所有節(jié)點及時充電，因此節(jié)點在充電之前的剩余能量至少要維持自身的能量消耗。

假設Tw為網(wǎng)絡中N個節(jié)點的總等待時間；TwN為第N個節(jié)點的等待時間，由前N-1個節(jié)點的充電時間和WCE到第N個節(jié)點的移動時間構(gòu)成，即

Tw=Tw1+Tw2+…+TwN

(5)

式中v為WCE的移動速度。若Tw/N為每個節(jié)點的平均等待時間，則節(jié)點在該時間內(nèi)消耗的能量應當不超過能量閾值，因此有

(6)

(7)

3)單個節(jié)點的能量消耗值

當節(jié)點m的剩余能量低于閾值時，為了確保節(jié)點m的存活，應在其最大等待時間tm內(nèi)保證自身的能量消耗足夠，即

tm≤Eth/Rm

(8)

式中tm為WCE移動到節(jié)點m的時間，將其代入式(8)可得到

(9)

綜上，能量閾值的選取公式有式(4)、式(7)和式(9)，但為了使網(wǎng)絡性能更好，選取其中的最大值作為節(jié)點的能量閾值。

3 MMAS-CNP算法求解

3.1 確定節(jié)點的充電順序

充電路徑規(guī)劃問題中最重要的是確定節(jié)點之間的充電順序，而本文提出的MMAS-CNP算法是通過節(jié)點的充電優(yōu)先級實現(xiàn)的，由于影響節(jié)點充電優(yōu)先級的因素較多，本節(jié)將引入中間量—節(jié)點的充電適配度值來進行比較。節(jié)點m的充電適配度值越小，其充電優(yōu)先級越高，那么節(jié)點m被選為下一個充電節(jié)點的概率就越大。

節(jié)點的剩余能量是影響WCE充電路徑規(guī)劃問題的重要因素，能量越低則表示該節(jié)點越需要充電；節(jié)點離BS越近，則表示W(wǎng)CE到達該節(jié)點的路徑和時間越短，WCE越容易為其充電；節(jié)點的能量消耗率越大，表示其能量的消耗速度越快，在相同剩余能量條件下該節(jié)點更需要被及時充電。因此,本文綜合考慮這3個因素計算節(jié)點的充電適配度值，如式(10)所示

(10)

式中fm為節(jié)點m的充電適配度值，δ,μ,φ分別為剩余能量Em,距離Dm和能量消耗率倒數(shù)R′的權(quán)重，其取值為δ=0.4,μ=0.3,φ=0.3。

充電優(yōu)先級Pm=1/fm選取算法如下：

{

1)while (Ethworking status=1) do

2)Input:Em,En,Rm,Rn,Dm,Dn,Pm,Pn

3)Output: Comparison ofPm,Pn

5)Pm>Pn

8)Pm>Pn

9)elsePm

10)end if

11)elsePm

12)end if

}

3.2 WCE能量受限的路徑規(guī)劃

本文的充電路徑以節(jié)點的最大充電優(yōu)先級為目標進行規(guī)劃，將能量受限問題轉(zhuǎn)化為WCE最大行駛長度Lmax和充電容量Ec受限的NP-hard[13]問題，采用最大—最小螞蟻算法進行求解，主要包括2個內(nèi)容：選擇下一節(jié)點的規(guī)則、信息素的更新規(guī)則[14]。具體實現(xiàn)過程如下：

Step 1 初始化參數(shù)。設Nc_max=400，信息素初始濃度為τmn=τmax=0.9。

Step 2 放置k只螞蟻從基站出發(fā)，令迭代次數(shù)Nc=1，當Nc

Step 3 按照式(11)選擇下一個節(jié)點n。由于螞蟻在不同階段有不同的狀態(tài)轉(zhuǎn)移規(guī)則，因此將引入一個隨機數(shù)q選擇節(jié)點n，其規(guī)則如下

(11)

螞蟻k的轉(zhuǎn)移概率為

(12)

Step 4 計算WCE移動到節(jié)點n的距離(dmn)與WCE為節(jié)點n充電的能量(Emax-En)。

Step 5 選定節(jié)點n后，計算此時WCE將行駛的總路徑長度Ltsp與將為節(jié)點充電的總能量Etsp，判斷是否同時滿足Ltsp≤Lmax且Etsp≤Ec。若是，WCE選擇節(jié)點n并為其充電，并在集合V中剔除該節(jié)點并更新；若否，則跳轉(zhuǎn)到Step 3，重新選擇下一個充電節(jié)點。其中，Ltsp和Etsp的計算公式如下

(13)

(14)

式中dn0為節(jié)點n到基站節(jié)點的距離。En為節(jié)點n的剩余能量，Emax為每個節(jié)點的最大能量。

Step 6 判斷是否所有螞蟻都完成了路徑搜索,若是,跳轉(zhuǎn)到Step 7，若否,則跳轉(zhuǎn)至Step 3。

Step 7 記錄本次迭代中節(jié)點充電優(yōu)先級最高的路徑，并更新這條路徑的信息素。τmn的更新規(guī)則為

(15)

式中

(16)

Step 8 判斷迭代次數(shù)是否達到預設次數(shù)Nc_max，若是則跳轉(zhuǎn)到Step 9，否則跳轉(zhuǎn)至Step 3。

Step 9 輸出此次充電優(yōu)先級最高的路徑。

4 仿真與分析

本文采用MATLAB R2016a軟件進行仿真檢驗與性能分析，為了驗證本文提出的MMAS-CNP算法的可行性和有效性，將其與經(jīng)典的NJNP[3]和MMAS-CM算法[4]對比分析。將100個節(jié)點隨機布撒在200 m的方形區(qū)域內(nèi)，其他參數(shù)設置：基站/服務站位置為(100,100)m，節(jié)點最大能量Emax為10 J，能量閾值Eth為0.4Emax，WCE充電容量Ec為5 000 J，WCE行駛長度Lmax為250 m，WCE移動速度v為5 m/s，WCE充電效率h為200 mJ/s，WCE的移動能耗Δc為4 mJ/s，期待的能量利用率ω為0.8。

4.1 技術(shù)評估指標

本文將通過充電節(jié)點的失效率和網(wǎng)絡壽命這兩個指標來實現(xiàn)：1)充電節(jié)點的失效率：是指由于WCE來不及充電而導致節(jié)點失效死亡的數(shù)量與需要充電節(jié)點的數(shù)量之比。充電節(jié)點的失效率越小，則表示節(jié)點的充電順序安排得越好;2)網(wǎng)絡壽命：是指網(wǎng)絡從開始運轉(zhuǎn)到充電節(jié)點的失效率達到一定值時，網(wǎng)絡停止工作的時間。網(wǎng)絡壽命越長，則表示充電路徑規(guī)劃得越合理。

4.2 仿真結(jié)果分析

WRSN充電路徑規(guī)劃的問題研究中， WCE對節(jié)點的充電效率和網(wǎng)絡的節(jié)點數(shù)量對充電路徑都有一定的影響。若WCE對節(jié)點充電的效率越高，則說明在單位時間內(nèi)WCE為節(jié)點補充的能量越多，WCE充電速率越快，節(jié)點完成充電的時間越短。若網(wǎng)絡中節(jié)點數(shù)量越多，則說明需要充電的節(jié)點數(shù)量也越多，WCE的充電負擔就越重，那么WCE來不及為節(jié)點充電而死亡的節(jié)點數(shù)量越多，充電路徑就越不合理。

4.2.1 WCE的充電效率

將WCE對節(jié)點的充電效率從[100,300]mJ/s進行調(diào)試，其他參數(shù)保持不變，分析網(wǎng)絡性能的變化情況如圖3(a)和圖3(b)所示。

圖3 不同充電效果的影響

如圖3(a)所示，隨著WCE充電效率的增大，3種路徑規(guī)劃算法的充電節(jié)點失效率均在降低，而MMAS-CNP算法與其他兩種算法相比，充電節(jié)點的失效率都是最低的，這是由于在節(jié)點的充電順序選取中，合理地考慮了節(jié)點的剩余能量和能量消耗率對充電順序的影響，使得剩余能量越低、能量消耗越快的節(jié)點優(yōu)先被選擇充電。隨著WCE的充電效率越高，WCE完成充電的節(jié)點數(shù)量越多，充電節(jié)點的失效率也隨之降低。當充電效率達到175 mJ/s之后，充電節(jié)點的失效率的下降趨勢比較平緩，這是由于WCE此時已經(jīng)能滿足大部分節(jié)點的充電需求，當充電效率達到225 mJ/s時，充電節(jié)點的失效率接近于0。如圖3(b)所示，3種算法的網(wǎng)絡壽命都隨著WCE充電效率的增大而升高，而MMAS-CNP算法由于充電節(jié)點失效率降低，WCE能為更多存活的節(jié)點補充能量而延長了網(wǎng)絡壽命。

4.2.2 節(jié)點的數(shù)量

將網(wǎng)絡的節(jié)點數(shù)量從[25,200]進行調(diào)試，其他參數(shù)保持不變，分析網(wǎng)絡性能的變化情況如圖4所示。

圖4 不同網(wǎng)絡節(jié)點數(shù)量的影響

如圖4(a)所示，節(jié)點數(shù)量較少時，WCE的充電任務比較簡單，能為全部需要充電的節(jié)點補充能量，因此充電節(jié)點的失效率很低。當節(jié)點數(shù)量在75～200范圍內(nèi)，MMAS-CNP的節(jié)點失效率最低，這是因為節(jié)點數(shù)量越多，需要被充電的節(jié)點數(shù)量就越多，因此,節(jié)點的充電順序很重要，而MMAS-CNP算法優(yōu)先考慮了節(jié)點所能等待的時間和地理位置，使得那些急需充電和距離較近的節(jié)點能及時得到WCE的充電服務，從而降低了充電節(jié)點的失效率。如圖4(b)所示，若網(wǎng)絡節(jié)點的數(shù)量越多，則表示需要充電的節(jié)點越多，此時WCE的充電負擔越沉重，而每一次WCE所充電的節(jié)點能量是一定的，因此,WCE會更加來不及為節(jié)點充電而導致節(jié)點死亡個數(shù)增多，從而導致網(wǎng)絡失效而停止工作，網(wǎng)絡壽命則越短。

5 結(jié)束語

為了規(guī)劃一條合理的充電路徑，本文在確定節(jié)點的能量閾值后，考慮到節(jié)點充電優(yōu)先級對充電順序的影響，分別對節(jié)點的剩余能量、地理位置和能量消耗率賦予相應的權(quán)值并計算比較，最后在WCE最大行駛長度和一定的充電容量下運用最大最小螞蟻算法進行路徑規(guī)劃。該方法降低了充電節(jié)點的失效率，提高了網(wǎng)絡壽命，但網(wǎng)絡規(guī)模更大時，單個WCE將無法完成所有的充電任務，因此，需要考慮多個WCE為網(wǎng)絡節(jié)點補充能量的情況。