基于改進頭腦風暴算法的無線充電路徑規劃

邊銳鋒

（武漢理工大學自動化學院，湖北 武漢430070）

1 引言

在具有充電結構的無線可充電傳感器網絡[1]（WRSN）中，節點主動監視其自身的剩余能量，當其能量水平低于某個閾值時，向數據中心（DC）發送充電請求。DC對請求節點建立充電調度隊列，并將調度發送給移動充電器（MC）從而進行充電服務。為了減少移動充電器在路上的能量消耗，需要合理規劃移動充電器的充電路線。路徑規劃問題屬于傳統的TSP問題。但是傳統TSP算法并不適用于非接觸式無線充電的路徑規劃，未考慮到充電有效圓域的影響。針對上述算法存在的問題，本文通過引入可行充電圓域的概念對傳統的TSP算法進行相對應的改進。

2 有線充電設備路徑模型

假設在一個WRSN系統中存在N個無線傳感器，一個數據中心，一個移動充電器。定義傳感器的坐標為：

式（1）中：Si為第i號傳感器對應的坐標位置。

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

將MC行駛路程作為優化目標可以得到目標函數如下：

式（3）中：L（Pn）為充電路線Pn對應的總路程；為充電路線中DS對應的二維坐標。

即可得整體優化模型為：

3 無線充電設備的模型建立

3.1 充電半徑不重疊

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

圖1 充電線路大致圖

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

式（5）中：pi（xi，yi）為MC進行充電操作時的停留點位置坐標，其必須滿足充電距離約束，且每個傳感器的可充電范圍內至少停留了一個MC，表示為：

MC在各個停留點最多對同一傳感器充電，且不會在多個停留點對同一個傳感器充電，表示為：

長 短 時 記 憶（Long short term memory，LSTM）型RNN模型是傳統RNN的改進。它主要解決了RNN模型的梯度爆炸和梯度彌散的問題。如圖2所示。LSTM接受上一時刻輸出，當前時刻系統狀態以及當前系統輸入，通過輸入門，遺忘門和輸出門更新系統狀態并輸出最終結果。

即表示任意兩個停留點的沖帶你目標互不相同，且所有傳感器都需要被充電，即：

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

目標函數仍為MC的充電總路程，即：

整體模型可以表示為：

3.2 充電半徑相互重疊

當充電有效距離R較大，多個傳感器的可充電范圍發生重疊時，即R滿足此時的充電路線如圖2所示。

從圖2中可以看出，當可充電區域相互重疊時，讓停留點落在重疊區域內。

即使得MC可同時對多個目標傳感器進行充電。顯然在此規則之下，若有k個傳感器的可充電區域發生重疊，則對應的停留點數量將會變成30-k個，即充電路線可表示為

圖2 充電路線示意圖

4 嵌入隨機梯度下降算法的頭腦風暴算法

4.1 頭腦風暴算法（BSO）

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

4.2 隨機梯度下降算法

在無線充電半徑R＞0時，采用隨機梯度下降（SGD）對BSO的目標函數L（Pk）進行尋優，采用單個訓練樣本的損失來近似平均損失，即：

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

模型參數θ的更新公式為：

式（9）中：η為學習率。

將求得的θ代入到目標函數中求得最短路徑后，作為適應度帶入到基因中并執行頭腦風暴算法。

5 實驗結果

為了驗證算法的可行性，選取1個數據中心、29個傳感器以及1個MC作為前提條件。對于有線充電設備，當R=0時，采用頭腦風暴算法解決傳統TSP問題，其結果如圖3所示。總距離為11 482.802 89 m。

其充電設備規劃路線為：

傳統的TSP算法并不能解決帶有充電半徑存在的TSP問題，使用改進的頭腦風暴算法進行求解可得。

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

當R≥88.53 m時可同時對多個傳感器充電。總距離為9 251.937 8 m，移動路徑如圖5所示。

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

6 結語

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

圖3 頭腦風暴算法解決傳統TSP結果圖

圖4 改進頭腦風暴解決非接觸式TSP結果圖

圖5 移動路徑示意圖

圖6 對算法的迭代次數進行分析

圖7 對算法進行靈敏度分析