MC最優(yōu)移動充電路徑規(guī)劃

倪克松 丁寧 張哲

（青島理工大學(xué) 山東省青島市 266520）

1 前言

無線可充電傳感器網(wǎng)絡(luò)WRSN 在計算技術(shù)、無線通信和嵌入式技術(shù)領(lǐng)域中有廣泛的應(yīng)用場景。WRSN 包括三個部分：一個數(shù)據(jù)中心（DC）、若干傳感器和單個或多個移動充電器（MC）。

實際工作過程為：

（1）MC 離開數(shù)據(jù)中心；

（2）尋找下一個傳感器；

（3）為傳感器充電；

（4）尋找下一個傳感器。

移動充電器的能源一部分用在為29 個傳感器進行充電，另一部分在路上消耗。為使移動充電器在移動過程中實現(xiàn)能量消耗最小化，需要對其進行移動路線規(guī)劃。問題提出：分別在單個和多個MC 運作情況下求解最優(yōu)路徑，使得MC 能耗最小，并求解兩種最優(yōu)路徑下系統(tǒng)正常工作的每個傳感器最小電容量。

2 問題分析

（1）通過對單個MC 移動路徑的調(diào)度和優(yōu)化，使得其走過的路徑長度盡量的短。把不同的傳感器抽象成節(jié)點，已知每個節(jié)點的經(jīng)緯度，可以得到每個節(jié)點到任意節(jié)點以及到數(shù)據(jù)中心之間的距離。由于MC 的移動路徑必然是一個過每個點的閉合路徑，即是一個Hamilton 圈，最優(yōu)圈即為最優(yōu)路徑。

（2）當(dāng)MC 的移動路徑已經(jīng)固定時，根據(jù)已有的節(jié)點能量消耗速率、傳感器最低工作閾值f，MC 移動速率v 以及充電速率r，即可以唯一確定對于某一個節(jié)點所需要的最低電容量。

（3）在第二問的基礎(chǔ)上，引入虛擬起始節(jié)點，將4 個MC 移動規(guī)劃問題轉(zhuǎn)換為單個MC 規(guī)劃問題。在該最優(yōu)路徑下求解滿足系統(tǒng)正常運行各個MC 路徑上的傳感器最低電容量，傳感器節(jié)點被分為4 組，增加約束4 個MC 工作周期相同，求解模型與問題二相似。

3 模型假設(shè)

為了便于解決問題，提出如下假設(shè)：

（1）MC 可攜帶的能量足夠大，可以完成一個周期的充電任務(wù)；

（2）MC 一旦移動到傳感器節(jié)點，能立即對傳感器進行充電；

（3）充電過程中前一MC 回到數(shù)據(jù)中心，后一MC 馬上出發(fā)；

（4）該無線傳感網(wǎng)絡(luò)圖為強連通圖，即任意兩個節(jié)點之間都存在路徑。

4 模型的建立與求解

4.1 單個MC情景下的最優(yōu)路徑及最小電容量

首先，附件1 中的數(shù)據(jù)中心及傳感器的位置通過地球上的經(jīng)緯度坐標(biāo)給出。將地球近似為標(biāo)準(zhǔn)球體，以零經(jīng)度零緯度分別作為笛卡爾坐標(biāo)系的x 軸與y 軸，在坐標(biāo)系中尋找最優(yōu)路徑，后再轉(zhuǎn)化為距離進行輸出。

取地球半徑R 為6371km，設(shè)第i 個節(jié)點(xi,yi)與第j 個節(jié)點(xj,yj)之間的距離為lij，轉(zhuǎn)換公式為：

可通過兩點間距離公式計算，各節(jié)點的直角坐標(biāo)計算各點的平面距離。

移動充電器從數(shù)據(jù)中心x1出發(fā)，每節(jié)點恰通過一次，最終回到起始點x1，即不重復(fù)地行遍所有節(jié)點再回到出發(fā)點，其形成的閉環(huán)圖形為一個典型的Hamilton 圈[1]。問題轉(zhuǎn)化為典型的TSP 問題，利用改良圈算法來解決該問題。

已知傳感器節(jié)點個數(shù)為29，rij=0 或1，其中：

則有目標(biāo)函數(shù)Z 為：

約束條件為：

目標(biāo)函數(shù)式（3）表示移動充電器所經(jīng)過的路程之和的最小值。

式（5）是由C 中刪去邊xixi+1和xjxj+1，添加邊xixj和xi+1xj+1而得到的。然后適當(dāng)修改C 以得到具有較小權(quán)的另一個Hamilton 圈，這種方法為改良圈算法。若則以Cij代替C，Cij為C 的改良圈，以此不斷進行改進直到無法進行，即得最優(yōu)圈。

表1：單個MC 運作下每個傳感器最低電容量單位：mA

表2：單個MC 運作下每個傳感器最低電容量單位：mA

改良圈算法得到的結(jié)果幾乎不是最優(yōu)的，為得到更高的精確度，可以選擇不同的初始圈C，重復(fù)進行幾次，以得到更優(yōu)結(jié)果[1]。采用蒙特卡洛模擬生成一個隨機的初始圈，在大量Hamilton 圈中選擇長度最小的圈即為最優(yōu)圈，假設(shè)最優(yōu)圈的長度為L(x)，L(x)滿足下列目標(biāo)函數(shù)為：

使用MATLAB 給出生成各種隨機數(shù)的命令，運用蒙特卡洛模擬對隨機數(shù)進行枚舉給出初始圈，在多次隨機生成的300000 個Hamilton圈中，得到的最優(yōu)圈為1→18→21→20→19→26→27→3 0→22→24→25→29→23→5→4→6→11→14→17→28→16→13→9→12→15→7→8→10→3→2→1，長度為8.52km，最優(yōu)Hamilton 圈有兩個，它們路徑長度相等，路徑方向正好顛倒，其他的Hamilton 圈為次優(yōu)圈。

由附件2 可知每個傳感器節(jié)點的經(jīng)緯度和能量消耗速率，移動充電器的移動速度為v(m/s)、充電速率為r(m/s)。

設(shè)當(dāng)MC 移動到每個傳感器時，該傳感器的電量恰好為f(mA)，第i 個節(jié)點的能量消耗速率為pi，滿足r>pi即MC 充電速率大于傳感器能量消耗速率。

其中，Qi為第i 個節(jié)點的電池容量，l總為充電路線的總長，ki表示第i個節(jié)點的充電時間。不等式左邊表示第i個節(jié)點的生存時間，不等式右邊表示第i 個節(jié)點從充完電到下一次充電的時間。

其中，ki為：

k總為節(jié)點的充電時間總和，即

MC 的路程總長l總與移動速率v、充電速率以及每個傳感器節(jié)點的能量消耗速率p、剩余電池容量f 已知。將（8）、（9）式代入（7）式即可得只含未知量Qi的不等式，則問題就轉(zhuǎn)化為求解滿足不等式的最小Qi，即

對于每一個，都有對應(yīng)的一個上述形式的最優(yōu)化問題。這些問題的限制條件構(gòu)成了一個不等式組。為了便于表達，下面令Si為第i 個節(jié)點的可充電容量，ki第j 個節(jié)點的充電速率與能量消耗速率之差，即

則有

顯然，對于任意一個i，當(dāng)且僅當(dāng)公式（15）中的不等式取等號時，Si取得最優(yōu)解。于是對于得到的非齊次一維線性等式組，經(jīng)過整理后可以用矩陣表示如下：

令上式的系數(shù)矩陣為A，未知數(shù)向量為S。上述等式的左右兩邊同時右乘系數(shù)矩陣的逆即可得到解集S，因為最低傳感器工作電量f 為定值，故可求得每一個傳感器的最低電容量Qi。

下面對實際情形進行了仿真，對于充電速率r=10000mA/h，總路長l=8.52km，f=2mA，MC 移動速度v=0.01km/s 的情況下，每一個傳感器的最低存電量如表1所示。

4.2 多個MC情景下的最優(yōu)路徑及最小電容量

為達到MC 充電效率的最大化目的[2]，需要多個移動充電器之間相互配合或者獨立負責(zé)一部分傳感器節(jié)點的充電。

為了減少總行程長度，會有m-1 個MC，每個MC 總是只經(jīng)過最接近起始節(jié)點的m-1 節(jié)點中的一個就回到了出發(fā)節(jié)點，剩余的n-m+1 個節(jié)點只由一個MC 遍歷。由于這種方法不符合實際需要，所以規(guī)定每個MC 允許經(jīng)過的節(jié)點不超過一個上限值。

引入m-1 個虛擬起始節(jié)點，其中m 為移動充電器的數(shù)量，并且設(shè)虛擬節(jié)點的坐標(biāo)為數(shù)據(jù)中心的坐標(biāo)[3]，分別為xn+1…,xn+m-1，即將MTSP 問題轉(zhuǎn)化為TSP 問題。

變量定義如下：n 為給定的節(jié)點數(shù)，m 為MC 個數(shù)，N=n+m-1為總的節(jié)點數(shù)即實際節(jié)點與虛擬節(jié)點之和，i,j 為節(jié)點序號，lij為節(jié)點i 到節(jié)點j 的距離，其中虛擬節(jié)點之間和虛擬節(jié)點與數(shù)據(jù)中心之間的距離為無窮大；emax表示MC 允許經(jīng)過的節(jié)點數(shù)量的上限，其中，為一條經(jīng)過所有節(jié)點的環(huán)路。則MTSP 轉(zhuǎn)化為TSP 后的最優(yōu)圈長度L(x)模型為：

模型建立與單個MC 模型類似。

分別對4 個MC 的移動路線標(biāo)號為①②③④，并求各自組內(nèi)傳感器模型類比于問題二，約束條件如下所示：

其中，k總為每一組路線的充電時間總和，l總為每一組路線下4個MC 的移動距離之和，ki表示第i 個節(jié)點的充電時間，各個變量的關(guān)系見問題二中模型的建立部分。

實際問題路徑長度不同，充電節(jié)點數(shù)也不完全一致，每個MC的工作周期不同，為了保證4 個MC 的周期相同，建立模型：

通過標(biāo)準(zhǔn)差來限制MC 的充電節(jié)點數(shù)（工作能力），模型為

式（18）中zj為每條MC 路徑中節(jié)點數(shù)，為4 條路徑的平均節(jié)點數(shù)，標(biāo)準(zhǔn)差越小，MC 工作能力越接近。

由問題二得一個周期內(nèi)主要工作時間在MC 移動過程中。求解滿足不等式的每個傳感器節(jié)點的最小電容量

（1）對MC 充電能力不加以限制時，只考慮MC 工作，不考慮工作能力和工作效率時，3 個MC 只對一個傳感器節(jié)點進行充電后就回到了數(shù)據(jù)中心，剩下節(jié)點都由一個MC 來進行充電，但這種方式不切實際。

（2）對MC 能力進行限制時，使每個MC 工作能能力盡量相同，以每個MC 充電節(jié)點數(shù)的離差來衡量小車的工作能力，進行了多次仿真求解，每次在蒙特卡羅模擬給出的300000 個初始圈中尋找最優(yōu)Hamilton 圈，路徑總長越短越好，最常路徑越短越好，這兩個優(yōu)化目標(biāo)需同時滿足。

最優(yōu)路徑為：①：1→5→22→24→25→29→23→4→1；②：1→3→9→12→15→7→8→10→2→1；③：1→21→19→26→27→30→20→18→1；④：1→6→11→14→17→28→16→13→1。

定義一個懲罰因子：

評價指標(biāo)=路徑長度+懲罰因子×4 個MC 路線經(jīng)過的節(jié)點個數(shù)的離差，即評價指標(biāo)越小，雙目標(biāo)優(yōu)化效果越優(yōu)。

該最優(yōu)路徑的路徑總和為10.27km，最長路徑為2.24km，評價指標(biāo)為1.24，4 個MC 對應(yīng)的節(jié)點個數(shù)分別為7、8、7、7 條，該路徑的評價指標(biāo)最小。

在該最優(yōu)路徑下，對每條路線上的最小電容量進行求解，結(jié)果為表2。

表2中各傳感器節(jié)點的最低電容量比較小，原因：①傳感器節(jié)點消耗功率非常??；②模型可以等價于MC 一直在工作，電容量較小時即可保證系統(tǒng)正常運行。

5 結(jié)論

本文將蒙特卡洛算法與改良圈算法相結(jié)合，多次搜索得到Pareto 最優(yōu)解；單個MC 路徑被分為4 條MC 路徑，路徑變短，工作周期變短，傳感器等待下一次充電時間變短，每個傳感器的最低電容量變小，有利于電池制作成本的降低，有較大的商業(yè)價值。接下來的研究方向：各個傳感器節(jié)點的能量消耗功率不同，應(yīng)從剩余能量最小的節(jié)點優(yōu)先進行充電[2]，以此為優(yōu)先約束條件，考慮這樣運作的MC 的充電效率影響和能量損耗，達到將MC 能量更多地用于充電過程的目標(biāo)。