倪克松 丁寧 張哲

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

1 前言

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

實(shí)際工作過程為：

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

（2）尋找下一個(gè)傳感器；

（3）為傳感器充電；

（4）尋找下一個(gè)傳感器。

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

2 問題分析

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

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

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

3 模型假設(shè)

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

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

（2）MC 一旦移動(dòng)到傳感器節(jié)點(diǎn)，能立即對(duì)傳感器進(jìn)行充電；

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

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

4 模型的建立與求解

4.1 單個(gè)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)化為距離進(jìn)行輸出。

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

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

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

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

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

約束條件為：

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

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

表1：?jiǎn)蝹€(gè)MC 運(yùn)作下每個(gè)傳感器最低電容量單位：mA

表2：?jiǎn)蝹€(gè)MC 運(yùn)作下每個(gè)傳感器最低電容量單位：mA

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

使用MATLAB 給出生成各種隨機(jī)數(shù)的命令，運(yùn)用蒙特卡洛模擬對(duì)隨機(jī)數(shù)進(jìn)行枚舉給出初始圈，在多次隨機(jī)生成的300000 個(gè)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，長(zhǎng)度為8.52km，最優(yōu)Hamilton 圈有兩個(gè)，它們路徑長(zhǎng)度相等，路徑方向正好顛倒，其他的Hamilton 圈為次優(yōu)圈。

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

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

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

其中，ki為：

k總為節(jié)點(diǎn)的充電時(shí)間總和，即

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

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

則有

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

令上式的系數(shù)矩陣為A，未知數(shù)向量為S。上述等式的左右兩邊同時(shí)右乘系數(shù)矩陣的逆即可得到解集S，因?yàn)樽畹蛡鞲衅鞴ぷ麟娏縡 為定值，故可求得每一個(gè)傳感器的最低電容量Qi。

下面對(duì)實(shí)際情形進(jìn)行了仿真，對(duì)于充電速率r=10000mA/h，總路長(zhǎng)l=8.52km，f=2mA，MC 移動(dòng)速度v=0.01km/s 的情況下，每一個(gè)傳感器的最低存電量如表1所示。

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

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

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

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

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

模型建立與單個(gè)MC 模型類似。

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

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

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

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

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

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

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

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

最優(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。

定義一個(gè)懲罰因子：

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

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

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

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

5 結(jié)論

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