一種求解無線傳感器網絡定位問題的改進狀態轉移算法

王小榮 彭 炫 李建軍 張 海

（新疆大學工程訓練中心，新疆 烏魯木齊 830047）

1 概述

傳感器網絡定位（SNL）問題廣泛應用于無線傳感器網絡的控制和監測中，如在給定的無線電范圍內收集環境數據（溫度、振動運動、濕度），以及庫存管理等[1]。無線傳感器網絡是一組分布在一定地理區域的傳感器，網絡中傳感器的準確位置是影響應用效率的關鍵。具體來說，對于一個有n 個無線傳感器的網絡，SNL 問題是在給定一些傳感器對之間的距離和ma個已知傳感器（稱為錨）的精確位置的條件下，估計m 個未知傳感器的位置，其中n=m+ma,m?ma。需要注意的是，錨的位置可以通過全球定位系統（GPS）或在部署過程中的人工處理來獲得，但其代價昂貴，而且有物理條件的限制，因此錨的數量很少。目前的大多數研究是通過最小二乘法將SNL問題轉化為一個非凸優化問題來求解[2]。要準確定位未知傳感器，主要有三個難點:第一，距離測量可能包含噪聲。第二，很難找到SNL 問題的充分條件。第三，已經證明SNL 問題是NP-hard 問題[3]。在過去的十年中，人們提出了許多基于梯度的方法來近似求解SNL 問題。其中，半定規劃（SDP）松弛法往往不能準確地得到SNL 問題的最優解[4]。因此，由SDP 方法得到的解通常四舍五入為次最優解。由于距離測量可能包含某種噪聲，因此SDP 得到的次優解不可靠且魯棒性較差。與SDP 松弛相比，二階錐規劃（SOCP）松弛法得到的解略差，但結構簡單，消耗時間短，常被用作SNL 問題的預處理[5]。另一方面，據我們所知，雖然元啟發式算法在近幾十年發展迅速，一些隨機優化方法也被應用于SNL 問題，但其效果并不理想。例如粒子群優化算法解決SNL 問題時，傳感器的數量限制在100 個以內[6]。值得一提的是，文獻[2]采用了一種動態轉移算法來解決SNL 問題。雖然能夠解決100 個以上傳感器的SNL 問題，但魯棒性較差，解決大規模的SNL 問題耗時較長。狀態轉移算法是近年來提出的一種隨機優化方法[7]。不同于許多基于種群的元啟發式算法，如遺傳算法、粒子群算法、蟻群算法，它是一種基于個體的搜索技術。由于STA 搜索能力強大，易于實現，其已被廣泛應用于許多工程領域，如風電功率預測[8]、圖像分割[9]、混沌系統參數辨識[10]等。雖然STA 在解決許多優化問題方面具有很好的表現，但其仍存在一些不足[11]。例如，在求解某些復雜基準函數時，基本STA 求解精度低，收斂速度慢。在解決大規模SNL 問題時，魯棒性較差，甚至無法得到可行解。鑒于基本STA 的不足，本文提出了一種改進的狀態轉移算法。首先采用統計方法對STA 的參數進行選擇。然后采用二次插值技術增強其局部開發能力，提高求解精度。此外，為了減小算法陷入局部最優解的概率，設計了一種新的變異策略來提高全局探索性能。最后采用基于梯度的方法對算法進行加強，并成功地應用于300 個傳感器的大規模SNL 問題。

2 基本狀態轉移算法

狀態轉移算法（STA）是一種基于狀態空間和狀態轉移概念的隨機優化方法。一般來說，在基本STA 中，生成候選解的統一形式定義如下[12]：

2.1 狀態變換算子

在標準STA 中，通過參考各種類型的狀態空間變換，使用四個智能算子來解決連續優化問題。

2.1.1 旋轉變換

2.2 規則鄰域及采樣技術

不難理解，對于一個特定的解，理論上可以使用某種狀態變換算子生成無限多個候選解，從而形成一個規則鄰域。顯然，列出所有候選解決方案是不實際的，考慮到STA 中每個算子的狀態轉移矩陣是隨機生成的，算子生成的候選解也是隨機的，不是唯一的，且任何兩個解都相互獨立。在此基礎上，將生成的候選解視為樣本，通過選取具有代表性的樣本來反映鄰域的整體特征。例如，在伸縮變換中，獨立執行擴展運算符SE 次，其偽代碼如下：

其中，SE 為搜索強制，表示伸縮變換生成的樣本數；Best 為當前最好解。

3 改進狀態轉移算法

本小節提出了一種改進的狀態轉移算法（ISTA）。在ISTA 中，采用統計方法優化狀態變換算子因子的選擇[13]，然后采用二次插值技術代替平移變換算子，并提出了一種新的隨機變異策略，以提高算法跳出局部最優解的概率。下面將詳細介紹這些修改策略。

3.1 最優參數選擇

3.2 二次插值策略

雖然STA 具有很強的搜索性能，在許多工程領域得到了廣泛的應用，但在某些問題上仍然存在收斂速度慢的缺點。例如，在求解一些基準函數時，如Rosenbrock 函數，基本STA 在后期收斂緩慢，這也是許多啟發式算法的一種現象。此外，研究發現平移變換算子的局部搜索能力不是很強，而二次插值[14]（QI）方法具有很強的局部搜索能力。因此，采用QI 方法代替平移變換算子來增強STA 的局部搜索能力。QI 生成候選解的公式如下：

3.3 隨機變異策略

3.4 所提算法的操作流程

通過以上討論和分析，ISTA 算法的完整步驟描述如下：

步驟1 初始化算法參數；

步驟2 通過統計方法選擇最優伸縮變換算子參數；

步驟3 執行伸縮變換，若伸縮變換產生的最好解優于當前解，以50%的概率選擇執行二次插值或隨機變異操作，并以貪婪準則更新當前最好解；

步驟4 重復步驟3，Tp次；

步驟5 重復步驟2，3 和4。不同的是將伸縮變換替換為旋轉變換；

步驟6 重復步驟2，3 和4。不同的是將伸縮變換替換為坐標變換；

步驟7 直到滿足迭代的終止條件，迭代完成，輸出最優值。

為了形象的表達ISTA 算法的步驟，圖1 給出了ISTA 的流程圖，其中A，B，C 模塊分比執行Tp次。

圖1 ISTA 流程圖

4 應用于傳感器網絡定位問題

4.1 ISTA 算法測試

實驗中采用的4 個基準函數的理論最優值均為0。從表1 中的統計結果可以觀察到，相比于基本STA 以及兩種STA 的變體，ISTA 在4 個測試函數上都獲得了最好的平均值和標準差。特別是對于山谷型函數Rosenbrock，ISTA 可以獲得不錯的精度解，這表明二次插值技術可以增強STA 的局部開發能力，加快搜索速度，使得算法快速收斂。另外，對于多峰函數Pathological，STA，DSTA 和POSTA 都陷入了局部最優解，但ISTA 也可以獲得全局最優解，這表明隨機變異策略可以增強算法的全局探索能力。從ISTA，HHO 和SMA 的對比結果可以看出，3 種算法除了在函數Pathological 上獲得了相同結果以外，ISTA 在其他的三個測試函數上均獲得了最好的結果。從圖2 中幾種算法的平均迭代曲線也可以形象地看出，ISTA 收斂速度快于其他5 種對比算法，且獲得了更高的精度解，這證明所提算法在求解效率以及尋優精度方面均具有明顯優勢。

表1 幾種算法在四個基準函數上的結果

圖2 幾種算法的平均迭代曲線圖

4.2 應用于SNL 問題

顯然，由于非凸優化問題存在局部最優解，而STA 具有良好的全局搜索能力，為了進一步加強算法后期的搜索效率使其更適合求解SNL 問題，本文采用基于梯度的技術對ISTA 進行加強以提高其搜索效率，并將其應用于大規模SNL 問題的求解。

傳感器實例由SFSDF[17]隨機創建，它是一個用于解決SNL 問題的MATLAB 軟件包。本研究創建了3 個具有4 個錨點a= (0,0),a= (0,1),a= (1,0),a=(1,1)的SNL實例，傳感器均產生在區間[0,1]范圍內。第一個實例有12 個傳感器，無線電范圍設置為1，無噪聲添加。另外兩個都是大規模的SNL 問題，分別有100 和300 個傳感器，使用的無線電范圍是0.3，噪聲系數是0.001。在解決12 個傳感器的SNL 問題時，ISTA 不使用基于梯度的方法進行強化，實驗結果與標準STA 和DSTA 進行了比較。所有算法的最大評價函數設置為1e5，搜索范圍設置為[0,10]，其他參數設置與數值實驗中的相同。但在解決大規模的SNL 問題時，采用了基于梯度的優化技術來提高算法的搜索效率。所有算法獨立運行20 次，3 個SNL實例的實驗結果見表2 和圖3-6。

圖3 三種不同算法在12 個傳感器上的平均迭代曲線

圖4 STA 在300 個傳感器的SNL 問題上獲得的最好結果

圖5 STA, DSTA and ISTA 在100 個傳感器的SNL 問題上獲得的最好結果

圖6 STA, DSTA and ISTA 在300 個傳感器的SNL 問題上獲得的最好結果

更具體地說，對于12 個傳感器問題，三種算法都找到了最優解。從表2 中可以看出，ISTA 得到的統計結果顯示，基本STA 消耗的時間最少，但ISTA 獲得的最好值、平均值、最差值和標準差均為最佳。此外，從圖2 中的平均迭代曲線可以明顯看出，ISTA 相比于基本STA 和DSTA 可以更快地收斂到全局最優解。此外，對于兩個大規模的SNL 問題，使用基于梯度的優化技術對這三種算法都進行了進一步加強。表2 中的統計結果表明ISTA的獲得的結果也是最好的，而STA 和DSTA 都陷入局部最優解，這在圖5 和圖6 中也得到了驗證。值得強調的是，在300 個傳感器的大規模SNL 問題求解中，ISTA 比基本STA 和DSTA 消耗的時間少得多。

表2 幾種算法在SNL 實例上的求解結果

5 結論

本文提出了一種改進的狀態轉移算法來求解全局數值優化和傳感器網絡定位問題。該算法采用二次插值技術代替平移算子進行局部搜索，提高了STA 的局部搜索能力。另外，采用隨機新變異策略，減小算法陷入局部最優解的可能性。數值實驗表明，與其他5 種隨機優化算法相比，ISTA 具有更強的局部和全局搜索能力和較快的收斂速度。采用梯度技術增強的ISTA 在求解大規模SNL 問題的結果表明，與基本STA 和DSTA 相比，所提算法的性能也有顯著提高。在未來的工作中，該算法可以擴展到多目標優化、約束優化、組合優化和更復雜的現實問題。