多匯聚節(jié)點無線傳感網(wǎng)絡充電路徑多目標優(yōu)化方法*

夏靜山,莊哲民*,Alex Noel Josephraj,鄭大為

(1.汕頭大學電子工程系,廣東 汕頭 515063;2.伊頓電氣集團山特電子(深圳)有限公司,廣東 深圳 518101)

節(jié)點能量消耗管理問題,一直是無線傳感網(wǎng)絡WSN(Wireless Sensor Networks)領域的研究熱點[1-2]。降低節(jié)點能耗,延長網(wǎng)絡生存周期的方法有多種,如采用低能耗路由協(xié)議[3]、優(yōu)化網(wǎng)絡覆蓋算法[4]、提高電池容量等。在多匯聚節(jié)點WSN[5]中,由于匯聚節(jié)點能量消耗速度快且需要長時間持續(xù)穩(wěn)定工作,以上方法均不能保證節(jié)點有持續(xù)的能量供應,尤其在環(huán)境惡劣的重要區(qū)域,比如地下煤礦、隧道、野生動物保護地等,網(wǎng)絡需要工作數(shù)年之久,匯聚節(jié)點需要時刻處理大量且復雜的數(shù)據(jù)并上傳,節(jié)點電池又無法人工更換,一旦某個匯聚節(jié)點能量消耗殆盡,網(wǎng)絡壽命也會隨之結束。鑒于無線能量傳輸技術[6]已較為成熟,因此可以通過無線充電為匯聚節(jié)點補充能量,延長網(wǎng)絡壽命。當網(wǎng)絡中匯聚節(jié)點數(shù)量過多或者分布過于離散時,可對整個網(wǎng)絡區(qū)域進行網(wǎng)格劃分,得到多個子區(qū)域,然后分區(qū)域進行能量補充。在每次能量補充前,需要先對充電路徑進行規(guī)劃:在充電過程中,不僅要保證每個匯聚節(jié)點都能夠正常工作,還要使充電路徑總距離最短、充電消耗總能量最少,而且距離和能量不是相互獨立的,這是一個多目標旅行商問題MOTSP(Multi-Objective Traveling Salesman Problems)。

目前,對MOTSP的算法研究已較為成熟,如遺傳算法[7]、蟻群優(yōu)化算法[8]、模擬退火算法[9]等。Davoodi[10]提出一種求解網(wǎng)格中雙目標和尋找Pareto前沿的確定性算法,該算法得到的最優(yōu)解精度較高,但時間復雜度過高,即時性低;汪勇等[11]以模式理論為基礎,提出一種基因重組法,并采用熵值法確定路程和費用權重,算法計算效率較高,但該算法對于有時變約束條件的問題較為吃力;文獻[12-13]分別采用混合遺傳算法和改進分組遺傳算法來求解MOTSP,二者收斂速度較快,但計算效率偏低;Cornu等[14]提出一種基于多目標集合的攝動分解算法(PDA)來解決MOTSP,PDA結合了分解方法、局部搜索和數(shù)據(jù)擾動的思想,為尋找帕累托鋒的近似解提供了兩階段模塊化框架,該算法應用廣泛,可計算四目標及以上的MOTSP,魯棒性好,但是對于非對稱TSP適用性較低;Xia等[15]將共生有機體搜索算法與模擬退火算法相結合,來解決大型TSP,結合后的算法求解效果很好,但運算復雜度高,即時性偏低。

本文待充電節(jié)點的剩余能量是時變減少的,屬于非對稱鏈路,且即時性要求高,為了保證其在任意時刻均不低于節(jié)點正常工作所需最低能量,本文提出了一種基于能量約束條件的改進多目標優(yōu)化遺傳算法。通過目標轉化和加權,建立多目標優(yōu)化問題模型,并對遺傳算法的選擇、交叉、變異算子作出改進。通過仿真證明了該算法可以有效的延長多匯聚節(jié)點WSN的壽命。

1 基本問題描述

本文將多匯聚節(jié)點無線傳感網(wǎng)絡充電路徑優(yōu)化問題描述為:在一個多匯聚節(jié)點無線傳感網(wǎng)絡中,維護基站P作為無線充電小車WCC(Wireless Charging Car)行駛路徑的起點和終點,即在某一時刻基站檢測到網(wǎng)絡中有n個匯聚節(jié)點處于設定充電閾值范圍內,需要補充能量,WCC便從P出發(fā),依次對這些節(jié)點進行充電,充電任務完成后返回維護基站P。

我們的求解目標是:找到一條充電路徑,不僅可以使剩余能量越少、能量消耗速度越快的的匯聚節(jié)點優(yōu)先充電,從而保證每個匯聚節(jié)點都能夠正常工作,而且充電路徑總距離最短、消耗WCC的能量最少。由于最低剩余能量約束只限定于匯聚節(jié)點,因此路徑規(guī)劃中不考慮以P為起點和終點的路段,即以第1個充電節(jié)點為路徑起點,最后一個充電節(jié)點為路徑終點。我們假定在遍歷的充電路徑中,對需要充電的節(jié)點,只充電一次。

2 多目標路徑優(yōu)化算法設計

2.1 多目標優(yōu)化數(shù)學模型

為了解決該多目標路徑優(yōu)化問題,我們將節(jié)點優(yōu)先充電的目標轉化為能量約束條件ECC(Energy Constraint Conditions),并建立路徑總距離S和消耗WCC總能量E的數(shù)學模型。假設各匯聚節(jié)點之間完全連通,用Wk={Wk(1),Wk(2),Wk(i),…,Wk(n)}表示第k條充電路徑,k=1,2,…,n!。Wk為節(jié)點1～n的任意一個路徑排列組合,Wk(i)表示該充電路徑上的第i個節(jié)點,Wk(1)即為充電起始節(jié)點。建立模型如下。

①距離目標

設節(jié)點Wk(i)的位置坐標為(xi,yi),則WCC從節(jié)點Wk(i)行駛到節(jié)點Wk(i+1)所前進的距離d[Wk(i),Wk(i+1)]可表示為:

(1)

將任意路徑Wk所對應的路徑總距離S(Wk)作為距離目標函數(shù):

(2)

②能量目標

首先作出以下假設:充電過程開始時,匯聚節(jié)點Wk(i)的初始剩余能量為EIR[Wk(i)];WCC每次充電時,都把該節(jié)點能量充至電池容量Emax[Wk(i)];充電過程結束后,網(wǎng)絡中所有匯聚節(jié)點均不需要充電。

消耗WCC的能量分為兩部分:一部分是WCC在行駛過程中消耗的能量E1(Wk),

(3)

式中:V為WCC行駛速度,RM為WCC行駛時自身能量消耗速度,二者均為常量;

另一部分是為節(jié)點充電而消耗的能量E2(Wk),可通過充電消耗總時間乘以充電速度求得,表達式如下:

(4)

式中:Emax[Wk(i)],RC,R[Wk(i)]分別為電池容量、充電速度、節(jié)點平均能量消耗速度,均為已知參數(shù)。節(jié)點在進行能量補充時,仍然在正常工作,因此在分母中充電速度需要減去節(jié)點能量消耗速度。ER[Wk(i)]為待求量,表示W(wǎng)CC剛到達節(jié)點Wk(i)時,該節(jié)點的剩余能量,可由下式求出:

ER[Wk(i)]=EIR[Wk(i)]-TA[Wk(i)]×R[Wk(i)]
1≤i≤n

(5)

式中:EIR[Wk(i)]為已知的初始剩余能量,TA[Wk(i)]為從充電過程剛開始至WCC剛到達節(jié)點Wk(i)消耗的時間,易知TA[Wk(1)]=0。當i>1時,TA[Wk(i)]表達式如下:

TA[Wk(i)]=TA[Wk(i-1)]+TM[Wk(i)]+
TC[Wk(i-1)],2≤i≤n

(6)

式中:TM[Wk(i)]為WCC從節(jié)點Wk(i)的前一個節(jié)點移動到該節(jié)點的行駛時間,TC[Wk(i)]為WCC對節(jié)點Wk(i)的充電時間。式中存在遞歸關系,通過求出前一個節(jié)點的到達時間和充電時間以及從前一個節(jié)點到當前節(jié)點的行駛時間,三者求和,便可求出當前節(jié)點的到達時間。令TM[Wk(1)]=0,當i>1時,TM[Wk(i)]表達式如下:

(7)

WCC對節(jié)點Wk(i)的充電時間TC[Wk(i)],通過充電所補充能量除以真實充電速度來計算,表達式如下:

(8)

聯(lián)合式(5)～式(8),通過不斷遞歸,便可分別求出式(5)～式(8)中的各個待求量,包括ER[Wk(i)],進而求出式(4)中的E2(Wk),則Wk對應的能量目標函數(shù)E(Wk)可表示為

minE(Wk)=E1(Wk)+E2(Wk)

(9)

③等價目標轉化和加權處理

由式(3)可知,E1(Wk)與S(Wk)成正比,因此我們將原雙目標等價轉化為S(Wk)和E2(Wk)的雙目標優(yōu)化。由于在算法中同時設計兩個目標函數(shù)會大大增加算法的復雜度,而且難以得出使兩個目標都同時達到較優(yōu)的結果,因此我們再次對S(Wk)和E2(Wk)進行等價轉化,將S(Wk)轉化為t1(Wk),即WCC到達所有需充電的節(jié)點的行駛時間之和:

(10)

將E2(Wk)轉化為t2(Wk),即所有節(jié)點的充電時間之和:

(11)

式(10)、式(11)可分別通過式(7)、式(8)求解,由于V、RC均為常量,所以該轉化是等價轉化。

然后對目標t1(Wk)和t2(Wk)進行加權,設權重分別為α和β,則由式(10)和(11)線性加權得到多目標優(yōu)化模型的目標函數(shù)為

(12)

式中:α和β滿足α+β=1。取α=β=0.5,并將t(Wk)放大兩倍,即把整個充電過程消耗的總時間TSUM(Wk)作為本文的多目標優(yōu)化模型的目標函數(shù):

(13)

式中的兩個待求量在前文已通過式(7)、式(8)求出。目標函數(shù)確定后,還需要確定能量約束條件ECC,ECC包括:節(jié)點初始剩余能量EIR要低于設定充電閾值Eth;ER在任意時刻都要高于節(jié)點正常工作所需最低剩余能量Emin,即節(jié)點在任意時刻均可正常工作;消耗總能量E(Wk)要小于WCC攜帶總能量EC。ECC表示如下:

(14)

式中:ER[Wk(i)]為WCC剛到達節(jié)點Wk(i)時,該節(jié)點的剩余能量,Emin[Wk(i)]為節(jié)點Wk(i)正常工作所需最低能量。

2.2 改進的多目標路徑優(yōu)化遺傳算法

針對前面提出的多目標優(yōu)化模型,本文采用改進的遺傳算法(Improved Genetic Algorithm,IMGA)來求解。其中式(13)中的TSUM為改進遺傳算法的目標函數(shù)f,當ECC不成立時,設定f為一個較大的常數(shù)C,經(jīng)過多次仿真測試,最終取C=27.5。由于本文優(yōu)化問題是求取最小值,因此適應度函數(shù)與目標函數(shù)為負相關關系,適應度函數(shù)F為:

(15)

式中:A為放大系數(shù),經(jīng)過多次仿真測試,取A=50。另外,本文編碼方式為順序編碼;為了提高種群的狀態(tài)遍歷性,采用隨機方式生成初始種群,種群規(guī)模為popsize,種群規(guī)模不宜太小也不宜太大,取popsize=120,路徑Wk即為種群中的一個個體;采用最大迭代次數(shù)GN作為遺傳算法的終止條件,GN太大會降低算法的即時性,太小會降低算法的性能,取GN=300。

算法具體改進如下。

為了避免種群最優(yōu)適應度在迭代過程中出現(xiàn)下降的情況,本文采用與最佳個體保存策略相結合的輪盤賭法進行選擇操作。另外,為了提高適應度高的個體的選擇概率和算法運行效率,我們對適應度函數(shù)作一個乘方變換。對于個體Wk,設其適應度為Fk,則該個體被選中的概率Pk為:

(16)

式中:q為乘方變換階數(shù),q過小會導致不同個體被選擇的概率相差較小,過大會增加算法的計算量,本文取q=15。

為了避免交叉操作產(chǎn)生非法路徑,并提高種群多樣性,本文采用交叉點不固定的部分匹配交叉算子(PMX)[16]、隨種群進化階段而變化的交叉概率,并加入親子競爭機制,進行交叉操作。為了提高種群進化效果和后期種群穩(wěn)定性,交叉概率應隨種群進化階段(分為前期、中期、后期)逐步變小,分段交叉概率如下式所示:

(17)

式中gn為算法當前迭代次數(shù),GN為算法最大迭代次數(shù),3個分段分別對應種群進化的前期、中期、后期。

為了提高算法的全局搜索能力,本文采用變異點不固定的逆序變異和互換變異相結合的復合變異方式,并加入親子競爭機制,進行變異操作。變異概率是一個較小的數(shù),依據(jù)種群進化階段設定如下:

(18)

式中gn為算法當前迭代次數(shù),GN為算法最大迭代次數(shù)。

2.3 算法流程圖

IMGA的算法流程圖如圖1所示。從圖1中可以看出,改進后的遺傳算法相比于簡單遺傳算法并沒有增加循環(huán)嵌套部分,而是采用了更優(yōu)的遺傳算子,因此時間復雜度沒有變化,仍為o(n);由于采用了較復雜的遺傳算子,因此計算復雜度相比于簡單遺傳算法有增加,但是大大提高了算法的尋優(yōu)能力和全局搜索能力。

圖1 IMGA算法流程圖

3 仿真實驗

3.1 仿真平臺

本文仿真環(huán)境為MATLAB R2014a,采用MATLAB語言與C語言混合編程,其中程序主體用MATLAB編寫,一些耗時的函數(shù)用C實現(xiàn),對改進的遺傳算法和簡單遺傳算法進行分析比較,得到多目標優(yōu)化問題的最優(yōu)解。

3.2 仿真參數(shù)

在800 m×400 m區(qū)域內,隨機部署一定數(shù)量的匯聚節(jié)點和大量的普通傳感節(jié)點,基站P位置坐標為(400,200)。假設某一刻處于充電范圍內的匯聚節(jié)點數(shù)量為10個。為了使模擬仿真更接近實際情況,提高實驗結果的代表性,在選取這10個節(jié)點時,節(jié)點位置隨機,初始能量異構,能量消耗速度也各不相同;為了避免電池深度放電,延長電池使用壽命,我們設定Emin=0.05Emax,Eth=0.2Emax[6]。節(jié)點的能量參數(shù)和位置參數(shù)分別如表1和圖2所示(這里能量單位為庫倫,C)。

表1 節(jié)點能量參數(shù)

圖2 待充電匯聚節(jié)點位置

圖2中,黑色點即為待充電匯聚節(jié)點,右邊的數(shù)字為節(jié)點編號, 下方的數(shù)字即為節(jié)點位置坐標。考慮實際情況,節(jié)點部署環(huán)境較為惡劣,無線充電小車WCC相關參數(shù)設定如下:EC=26 000 c;V=280 m/h;RM=18 c/h;RC=1 800 c/h。

3.3 仿真結果與分析

3.3.1 最佳充電路徑及算法有效性驗證

運行IMGA可以得到最優(yōu)充電路徑Wbest={2,9,8,10,7,6,5,3,1,4},為了驗證該路徑滿足能量約束條件,可以保證節(jié)點持續(xù)正常工作,我們選取充電過程的4個狀態(tài)(WCC剛到達起始節(jié)點、節(jié)點10、節(jié)點5、終點節(jié)點),來展示未充電節(jié)點的剩余能量ER的變化過程。具體展示如圖3所示。

圖3 最優(yōu)路徑分狀態(tài)展示圖

圖3中,黑、白色節(jié)點分別表示未充電節(jié)點、已充電節(jié)點,黑色節(jié)點下方的數(shù)字即為當前狀態(tài)下該節(jié)點的剩余能量ER。綜合比較4個狀態(tài)可以看出,未充電節(jié)點剩余能量在不斷減少,但始終沒有低于表1中設定的最低值Emin。另外,由式(9)可以求出該路徑消耗WCC總能量為23 991.36 c,小于WCC攜帶總能量EC。因此該路徑能夠滿足能量約束條件,可以有效的延長網(wǎng)絡壽命。

3.3.2 IMGA與SIGA性能對比

我們從最優(yōu)解精度、種群收斂速度、種群進化效果3個方面來評價 IMGA和SIGA的性能。IMGA和SIGA運行結果如圖4所示。

圖4 兩算法運行結果

圖4(a)中,實線代表IMGA運行得到的最優(yōu)路徑;虛線代表SIGA運行得到的最優(yōu)路徑。

①最優(yōu)解精度POS

將IMGA運行200次,得到200條最優(yōu)路徑,我們取其中對應目標函數(shù)f值最小的路徑作為本文多目標優(yōu)化問題的理論最優(yōu)路徑WTH,WTH= {2,9,8,10,7,5,6,4,3,1}。由式(13)可得f(WTH)=21.83 h,IMGA、SIGA得到的f(Wbest)分別為21.87 h、22.07 h,則IMGA、SIGA的最優(yōu)解精度分別為99.82%、98.90%,優(yōu)化率0.92%。

②種群收斂速度SPC

算法取得最優(yōu)解的代數(shù)越早,種群收斂速度就越快。從圖4(b)可以看出,IMGA、SIGA約分別在第14、101代取得最優(yōu)解,因此IMGA種群收斂速度要優(yōu)于SIGA,優(yōu)化率為86.14%。

③種群進化效果EPE

在算法迭代過程中,如果種群平均解逐漸逼近種群最優(yōu)解,則算法的種群進化效果較好。從圖4(b)可以明顯看出,IMGA的種群進化效果要優(yōu)于SIGA,計算得二者EPE分別為99.41%、95.15%,優(yōu)化率4.26%。

對比結果如表2所示。

表2 算法性能對比

3.3.3 與單獨考慮距離、單獨考慮能量兩種方法結果比較

由于本文對距離和能量多目標優(yōu)化進行了量綱轉化和加權處理,因此為了驗證本文方法的優(yōu)越性,我們將本文方法與單獨考慮距離和單獨考慮能量兩種方法進行比較。在分別得到最優(yōu)路徑Wbest后,根據(jù)式(2)、式(5)、式(9)、式(13)可分別求出S、ER、E、TSUM。3種方法結果對比如表3所示。

表3 3種方法結果對比

從表3中可以看出,單獨考慮距離方法得到的最優(yōu)路徑對應的S比本文方法小很多,但是節(jié)點9和8能量已消耗殆盡,達不到我們延長網(wǎng)絡壽命的目的;單獨考慮能量方法得到的最優(yōu)路徑對應的E比本文的方法要少0.039%,但是S卻比本文方法多10.78%,導致TSUM比本文方法多了將近1 h,得不償失。因此,本文采取的方法是要優(yōu)于其他兩個方法的。

4 結束語

多匯聚節(jié)點無線傳感網(wǎng)絡中的匯聚節(jié)點需要長時間持續(xù)工作,但節(jié)點能量有限,因此需要通過持續(xù)的能量補充延長網(wǎng)絡壽命。本文采用移動充電小車來對節(jié)點進行充電,并設計了一種多目標充電路徑優(yōu)化方法,通過改進的遺傳算法對充電路徑進行最優(yōu)規(guī)劃,得到一條最佳充電路徑。通過實驗也表明了,該方法可以有效地延長整個網(wǎng)絡的生存周期,而且可以較好的降低能量補充成本。