關于無線可充電傳感器網絡充電路線規劃的研究分析①

史長青, 喻 俊

(中原工學院彼得堡航空學院,河南 鄭州 450007)

0 引 言

無線傳感器網絡[1]中包括若干傳感器以及一個數據中心,傳感器從環境中收集信息后每隔一段時間將收集到的信息發送到數據中心。傳感器正常工作的前提是需要有移動充電器提供滿足其使用要求的電能,出于對移動充電器的能量利用效率的考慮,在移動充電器勻速行駛的前提下需要盡量減少移動充電器的行駛路程,所以優化充電線路是提高充電器能效比的關鍵所在。在優化充電線路時,當給出節點的經緯度且只有一個充電器進行工作時,如何規劃充電線路才可以實現路上的能效降到最低是研究的核心問題。圍繞著無線可充電傳感器網絡充電路線規劃的建模分析,首先建立了無線網絡分布的線路模型,利用python中的geopy庫將經緯度轉化為距離數據,再利用貪婪算法計算運行路徑的最優解,在面對電池容量最優問題時,以移動電源走完一個回路后電池容量剛好達到最低為最優條件,用數值解法結合約束條件求得數值解結果,四車移動充電情況可以視為有時間窗車輛路徑問題(vehicle routing problems with time windows),求得其最小化的優化值即為最優路徑選擇。

常用的移動充電規劃框架具體過程如圖1所示,網絡中的傳感器是隨即部署的,因此需要通過聚類算法得到合適充電的充電停留位置。由于無線傳感器屬于一個微型網絡且分布有多個節點,所以在進行路徑優化之前首先需要的就是對節點進行分簇處理以此來獲取到停留點,將所有的停留點串聯起來也就是所說的充電線路。通俗地說,充電線路優化也就是我們常見的帶有約束的TSP問題[2],通過對其求解可以獲得移動充電器的充電路徑,再選取移動充電器合適的充電方案對網絡中的傳感器節點進行充電。

圖1 移動規劃步驟

.

1 理論原理

無線充電傳感器具體單對單、單對多兩種充電模式。對于前者來說是利用一個充電器對一個網絡節點進行充電;對于后者來說,是利用充電器對網絡中的多個節進行充電的過程,而且由于每個節點距離基站的距離不同,節點的充電順序也不一樣。在對多個節點充電之前,首先需要在基站中完成充電器的電能補充操作,然后根據距離大小先對距離基站最近的節點進行充電并將其視為初始充電節點,完成之后對下一個節點進行充電并以此類推。但是要實現總充電量最小時,移動充電器必須訪問每個傳感器節點一次,而且不重復并最后返回到初始充電節點,形成一個封閉回路,要使移動充電器的行駛路徑最短問題,就是一個典型的TSP問題。

TSP的實質就是路徑規劃問題,它又被稱為旅行商或者旅行推銷員問題,舉例解釋為:有多個城市需要商人途徑且只能途徑一次,如何對路徑進行合理的規劃才能實現路途最短。這一TSP問題的求解方式就是需要將所有的目標點進行全排列即可,雖然方法笨拙可行,但當目標點的數量過多時,其計算步驟與難度也會成指數倍增加,屬于NP完全問題,故該方法不可取。

對于無線充電路徑優化問題來說就如同求解TSP問題一樣,網絡中的節點就是旅行商途徑的城市,每兩個節點連接成一條線并具有相應的距離。如果將所有的連線類比成樹枝,那么整個網絡就成了樹,樹根節點也就是充電起始點。在進行最佳路徑求解時可以根據貪婪算法,首先對節點進行處理并根據鄰邊最短原則將節點進行串聯起來,然后將滿足要求的邊視為初始路徑供后續使用。當在優化計算時,一步一步將每個節點連接起來最終形成一顆完成的書,也就類似于商人途徑過所有的城市,根據這一方法獲取到的樹其路徑是最短的。最后可以根據深度優先原則對整個樹進行查找,最終獲取到符合要求的路徑。

2 算法步驟

算法方面or-tools庫提供了兩種思路,第一種思路是是基于啟發式算法[3]的策略(first solution strategy),這一策略的優點在于搜索的速度比較快,相應的缺點是:這一方法尋找的解只是相對意義上的優秀解,不能保證結果是最優解。第二種思路是啟發式+元啟發[4]的算法,這一算法在初始解的生成過程用啟發式算法計算,后續的元啟發過程在這個解上進行。這一算法搜索時間會相對長一些,但搜索得到的相對最優解要優于基于啟發式搜索的解法。

采用了or-Tools庫給出了最優解和次優解。兩種算法思路:第一解算策略算法(first solution strategy)和引導式本地搜索算法,通過Python的程序包組合,使得在程序里設置一個選擇參數就能轉換算法模式,對比兩種算法的結果后可以得出理論上的最優解。

但是對于第一解算策略算法來說,因為程序的選擇策略問題只能得到一個相對意義上的優秀解,有是最優解的可能性,將其結果與引導式本地搜索算法的結果相互對比印證,主要使用引導式本地搜索算法來解決問題。為了便于求解,先利用python中谷歌開發的geopy庫將經緯度數據轉化為距離數據,把問題轉化為從數據中心出發遍歷所有傳感器位置后再回到數據中心的最短路徑問題。

貪婪算法[5],又稱貪心算法(Greedy Algorithm)。對于該算法而言,之所以稱之為“貪婪”,是因為它不考慮后續過程的影響,而是將最有利于本次計算的參數作為最佳選項進行求解,最終獲取到局部最優解。該算法側重于當前狀態的選擇,忽略了后續影響,故無后效性是其最大的特征。

在求解TSP問題時可以使用貪婪算法進行,具體步驟為:首先在多個城市中隨機挑選一個作為初始參考對象,然后以其為中心進行下一個城市的選擇,而且要保證每次選擇的城市距離初始參考對象的距離應最小,當所有的城市選擇完之后,本次求解過程終止。在選擇城市的時候,不考慮后續的影響,只考慮滿足本次要求的城市,也就是說本次選擇的城市路徑距離最短。雖然通過上述方法不能獲取到最佳路徑,但在一定程度上簡化整個計算過程。而且這一方法更加適用于目標(城市)數量較少的問題,該方法得到的路徑長度通常情況下不大于最佳路徑的1.15倍。

要使用引導式本地搜索算法來解決問題,必須為給定問題定義解決方案功能。定義解決方案特征以區分具有不同特征的解決方案,以便可以識別和避免圍繞局部最優的相似區域。解決方案功能的選擇取決于問題的類型,并且在某種程度上還取決于本地搜索算法。對于每個功能Fi定義為一個函數Ci。每個功能Fi與一個懲罰函數Pi相關聯,以局部極小值記錄要素出現的次數,而功能函數直接來自于目標函數。例如,在旅行商問題中,“旅行是否直接從城市X到城市Y”可以定義為要素。X和Y之間的距離可以定義為成本。

在實現級別,為每個功能定義一個指標功能,指示當前解決方案中是否存在該功能。當指示值解為1時該功能成立,值為0時該功能不成立。

在算法步驟之前先對相應對的物理量和數學符號作出如下說明:

表1 符號說明

上述流程可以歸結為以下步驟:

第一步:通過Python的geopy庫將經緯度數據轉化為距離數據并存儲在數組數組{LA1A2}中,在數組基礎上建立距離矩陣,若用distances表示兩點間的距離。那么該問題本質上就是從初始點0出發,經過所有的點最終回到初始0并使得途徑路徑最短。求解空間就是利用Python算法中的geopy庫對矩陣中的經緯度進行換算,實現所有點的排列組合并得到最佳的距離矩陣。

第二步:運用Python的or-Tools的RoutingModel解決TSP問題。

第三步:傳入一個計算距離的回調函數,設定初始可行解的求解方案為first_solution_strategy(選項為PATH_CHEAPEST_ARC)和Local_search_options(選項為GUIDED_LOCAL_SEARCH),就可以使用SolveWithParameters進行求解[6]。

3 實驗及結果分析

算法在Python的IDE上編程,在PC機上已經實現,程序通過上述算法步驟實現了對最優路徑的規劃情況,第一解算策略算法得出的結果如圖2所示:

圖2 啟發式搜索路徑結果

圖3 移動充電器模擬運行圖(啟發式)

引導式本地搜索算法得出的結果如圖4所示:

圖4 引導式+元啟發路徑結果

圖5 移動充電器模擬運行圖(啟發式+元啟發式)

如圖2所示,第一解算策略算法(啟發式搜索)路徑結果為:0 -> 2 -> 1 -> 9 -> 7 -> 6 -> 11 -> 14 -> 15 -> 27 -> 16 -> 13 -> 12 -> 8 -> 10 -> 5 -> 3 -> 28 -> 24 -> 23 -> 29 -> 26 -> 25 -> 18 -> 19 -> 20 -> 17 -> 21 -> 22 -> 4 -> 0,得出的移動充電器移動最短距離為12033 m。而圖2是啟發式搜索路徑結果圖。

如圖4所示,引導式本地搜索算法(啟發式+元啟發式搜索)路徑結果為:0 -> 2 -> 1 -> 9 -> 7 -> 6 -> 14 -> 11 -> 8 -> 12 -> 15 -> 27 -> 16 -> 13 -> 10 -> 5 -> 3 -> 4 -> 22 -> 28 -> 24 -> 23 -> 21 -> 29 -> 26 -> 25 -> 18 -> 19 -> 20 -> 17 -> 0,得出的移動充電器運行的最短距離為11469 m。而圖5是啟發式+元啟發式搜索路徑結果圖。

對比以上結果發現,采用基于貪婪算法的引導式本地搜索算法可以得到的路徑選擇是理論上的最優路徑選擇。

4 結 語

進行無線充電路徑優化計算時,將路徑圖視為網絡結構圖進行,并將傳感器的經緯度與地球半徑結合起來獲取到每兩個節點之間的距離。然后將問題轉化為找到一個從數據中心出發,依據現有路徑遍歷網絡圖的每一個節點后再回到數據中心的最短路徑問題。在貪婪算法的基礎上逐步進行求解,最終獲取到最佳路徑,使得充電器在充電時能效最小。