基于改進(jìn)頭腦風(fēng)暴算法的無(wú)線充電路徑規(guī)劃

邊銳鋒

（武漢理工大學(xué)自動(dòng)化學(xué)院，湖北 武漢430070）

1 引言

在具有充電結(jié)構(gòu)的無(wú)線可充電傳感器網(wǎng)絡(luò)[1]（WRSN）中，節(jié)點(diǎn)主動(dòng)監(jiān)視其自身的剩余能量，當(dāng)其能量水平低于某個(gè)閾值時(shí)，向數(shù)據(jù)中心（DC）發(fā)送充電請(qǐng)求。DC對(duì)請(qǐng)求節(jié)點(diǎn)建立充電調(diào)度隊(duì)列，并將調(diào)度發(fā)送給移動(dòng)充電器（MC）從而進(jìn)行充電服務(wù)。為了減少移動(dòng)充電器在路上的能量消耗，需要合理規(guī)劃移動(dòng)充電器的充電路線。路徑規(guī)劃問題屬于傳統(tǒng)的TSP問題。但是傳統(tǒng)TSP算法并不適用于非接觸式無(wú)線充電的路徑規(guī)劃，未考慮到充電有效圓域的影響。針對(duì)上述算法存在的問題，本文通過引入可行充電圓域的概念對(duì)傳統(tǒng)的TSP算法進(jìn)行相對(duì)應(yīng)的改進(jìn)。

2 有線充電設(shè)備路徑模型

假設(shè)在一個(gè)WRSN系統(tǒng)中存在N個(gè)無(wú)線傳感器，一個(gè)數(shù)據(jù)中心，一個(gè)移動(dòng)充電器。定義傳感器的坐標(biāo)為：

式（1）中：Si為第i號(hào)傳感器對(duì)應(yīng)的坐標(biāo)位置。

當(dāng)不考慮充電半徑R存在的情況下（即為有線充電設(shè)備），此問題則變化為傳統(tǒng)的TSP問題，則MC的充電路線可表示為二維有限序列：

將MC行駛路程作為優(yōu)化目標(biāo)可以得到目標(biāo)函數(shù)如下：

式（3）中：L（Pn）為充電路線Pn對(duì)應(yīng)的總路程；為充電路線中DS對(duì)應(yīng)的二維坐標(biāo)。

即可得整體優(yōu)化模型為：

3 無(wú)線充電設(shè)備的模型建立

3.1 充電半徑不重疊

當(dāng)MC為無(wú)線充電設(shè)備時(shí)，將其無(wú)線充電的有效圓域半徑標(biāo)記為R，且假設(shè)在此有效距離內(nèi)充電場(chǎng)的能級(jí)不隨距離而發(fā)生變化，即只要MC位置坐標(biāo)pm（xm，ym）與傳感器i的位置坐標(biāo)si（xsi，ysi）滿足d（pm，si）≤R時(shí)，其對(duì)傳感器i的充電效率就將等于R（ma/s）。在此情況下，若充電有效距離R滿足：

圖1 充電線路大致圖

顯然在該情況下充電半徑之間互不重疊，該情況下的最短路徑仍然為首尾相連的折線段，且聽蹲點(diǎn)數(shù)量仍然等于傳感器的數(shù)量，即MC的充電路線仍可表示為二維有限序列：

式（5）中：pi（xi，yi）為MC進(jìn)行充電操作時(shí)的停留點(diǎn)位置坐標(biāo)，其必須滿足充電距離約束，且每個(gè)傳感器的可充電范圍內(nèi)至少停留了一個(gè)MC，表示為：

MC在各個(gè)停留點(diǎn)最多對(duì)同一傳感器充電，且不會(huì)在多個(gè)停留點(diǎn)對(duì)同一個(gè)傳感器充電，表示為：

長(zhǎng) 短 時(shí) 記 憶（Long short term memory，LSTM）型RNN模型是傳統(tǒng)RNN的改進(jìn)。它主要解決了RNN模型的梯度爆炸和梯度彌散的問題。如圖2所示。LSTM接受上一時(shí)刻輸出，當(dāng)前時(shí)刻系統(tǒng)狀態(tài)以及當(dāng)前系統(tǒng)輸入，通過輸入門，遺忘門和輸出門更新系統(tǒng)狀態(tài)并輸出最終結(jié)果。

即表示任意兩個(gè)停留點(diǎn)的沖帶你目標(biāo)互不相同，且所有傳感器都需要被充電，即：

式（7）中：S為全部傳感器坐標(biāo)的集合，即表示所有停留點(diǎn)的充電目標(biāo)的集合包含了所有的傳感器。

目標(biāo)函數(shù)仍為MC的充電總路程，即：

整體模型可以表示為：

3.2 充電半徑相互重疊

當(dāng)充電有效距離R較大，多個(gè)傳感器的可充電范圍發(fā)生重疊時(shí)，即R滿足此時(shí)的充電路線如圖2所示。

從圖2中可以看出，當(dāng)可充電區(qū)域相互重疊時(shí)，讓停留點(diǎn)落在重疊區(qū)域內(nèi)。

即使得MC可同時(shí)對(duì)多個(gè)目標(biāo)傳感器進(jìn)行充電。顯然在此規(guī)則之下，若有k個(gè)傳感器的可充電區(qū)域發(fā)生重疊，則對(duì)應(yīng)的停留點(diǎn)數(shù)量將會(huì)變成30-k個(gè)，即充電路線可表示為

圖2 充電路線示意圖

4 嵌入隨機(jī)梯度下降算法的頭腦風(fēng)暴算法

4.1 頭腦風(fēng)暴算法（BSO）

本文使用頭腦風(fēng)暴算法求解的步驟如下：①初始化。根據(jù)題目，在接的可行域中隨機(jī)選擇n個(gè)個(gè)體xi，作為優(yōu)化問題的初始解，其中n=1，2，…，N，確定最大迭代次數(shù)Lmax，設(shè)定算法終止條件。②聚類。用dck-means聚類算法將n個(gè)個(gè)體分成m個(gè)類，計(jì)算每個(gè)個(gè)體的適應(yīng)度函數(shù)值，適應(yīng)度最好的個(gè)體記為該類的中心個(gè)體。③編譯。隨機(jī)產(chǎn)生一個(gè)[0，1]之間的隨機(jī)數(shù)Po1，若大于預(yù)先設(shè)定的概率參數(shù)Po，隨機(jī)選中一個(gè)類的中心個(gè)體，替換為隨機(jī)產(chǎn)生的新個(gè)體。④生成新個(gè)體。首先產(chǎn)生[0，1]之間的隨機(jī)數(shù)pa1，與預(yù)先設(shè)定的概念參數(shù)p1進(jìn)行比較，跟會(huì)員結(jié)果選擇一下方式產(chǎn)生候選個(gè)體xs。⑤改進(jìn)。在頭腦風(fēng)暴的算法中，在傳感器中所處位置建立可行圓域，當(dāng)停留點(diǎn)位于可行充電圓域內(nèi)部的時(shí)候，將其所對(duì)應(yīng)的傳感器列入到禁忌傳感器范圍中。

4.2 隨機(jī)梯度下降算法

在無(wú)線充電半徑R＞0時(shí)，采用隨機(jī)梯度下降（SGD）對(duì)BSO的目標(biāo)函數(shù)L（Pk）進(jìn)行尋優(yōu)，采用單個(gè)訓(xùn)練樣本的損失來(lái)近似平均損失，即：

式（8）中：P為中心位置；θ為參數(shù)方程圓周上的角度；為pi到pi+1點(diǎn)的直線距離。

模型參數(shù)θ的更新公式為：

式（9）中：η為學(xué)習(xí)率。

將求得的θ代入到目標(biāo)函數(shù)中求得最短路徑后，作為適應(yīng)度帶入到基因中并執(zhí)行頭腦風(fēng)暴算法。

5 實(shí)驗(yàn)結(jié)果

為了驗(yàn)證算法的可行性，選取1個(gè)數(shù)據(jù)中心、29個(gè)傳感器以及1個(gè)MC作為前提條件。對(duì)于有線充電設(shè)備，當(dāng)R=0時(shí)，采用頭腦風(fēng)暴算法解決傳統(tǒng)TSP問題，其結(jié)果如圖3所示。總距離為11 482.802 89 m。

其充電設(shè)備規(guī)劃路線為：

傳統(tǒng)的TSP算法并不能解決帶有充電半徑存在的TSP問題，使用改進(jìn)的頭腦風(fēng)暴算法進(jìn)行求解可得。

當(dāng)0＜R＜88.53 m每個(gè)MC在任意位置最多同事給一個(gè)傳感器充電，假設(shè)充電半徑為50 m，通過本文的算法可以解得總距離為11 051.789 2 m。改進(jìn)頭腦風(fēng)暴解決非接觸式TSP結(jié)果如圖4所示。

當(dāng)R≥88.53 m時(shí)可同時(shí)對(duì)多個(gè)傳感器充電。總距離為9 251.937 8 m，移動(dòng)路徑如圖5所示。

可以發(fā)現(xiàn)相較與傳統(tǒng)的TSP算法，本文中的算法可以充分考慮到充電半徑的影響，減少了MC在線路上的能耗。最后對(duì)算法的迭代次數(shù)進(jìn)行分析，如圖6所示。對(duì)算法進(jìn)行靈敏度分析，如圖7所示。從圖6中可以看到，在趨近于300次迭代次數(shù)的時(shí)候，尋得最優(yōu)解。從圖7中可以看到，在充電半徑不斷增大的情況下，最短路徑的下降曲線較為平滑，靈敏度處于比較好的狀態(tài)。

6 結(jié)語(yǔ)

本文中提出的算法可以有效解決非接觸式的路徑規(guī)劃，算法普適性，在實(shí)際應(yīng)用中可有效降低充電周期，減少線路能耗。本算法在充電半徑過大的時(shí)候會(huì)引起最優(yōu)解局部震蕩，使得收斂速度在半徑過大時(shí)較慢，但是仍能得出最優(yōu)解。

圖3 頭腦風(fēng)暴算法解決傳統(tǒng)TSP結(jié)果圖

圖4 改進(jìn)頭腦風(fēng)暴解決非接觸式TSP結(jié)果圖

圖5 移動(dòng)路徑示意圖

圖6 對(duì)算法的迭代次數(shù)進(jìn)行分析

圖7 對(duì)算法進(jìn)行靈敏度分析