一種求解無線傳感器網(wǎng)絡(luò)定位問題的改進(jìn)狀態(tài)轉(zhuǎn)移算法

王小榮 彭 炫 李建軍 張 海

（新疆大學(xué)工程訓(xùn)練中心，新疆 烏魯木齊 830047）

1 概述

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

2 基本狀態(tài)轉(zhuǎn)移算法

狀態(tài)轉(zhuǎn)移算法（STA）是一種基于狀態(tài)空間和狀態(tài)轉(zhuǎn)移概念的隨機(jī)優(yōu)化方法。一般來說，在基本STA 中，生成候選解的統(tǒng)一形式定義如下[12]：

2.1 狀態(tài)變換算子

在標(biāo)準(zhǔn)STA 中，通過參考各種類型的狀態(tài)空間變換，使用四個(gè)智能算子來解決連續(xù)優(yōu)化問題。

2.1.1 旋轉(zhuǎn)變換

2.2 規(guī)則鄰域及采樣技術(shù)

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

其中，SE 為搜索強(qiáng)制，表示伸縮變換生成的樣本數(shù)；Best 為當(dāng)前最好解。

3 改進(jìn)狀態(tài)轉(zhuǎn)移算法

本小節(jié)提出了一種改進(jìn)的狀態(tài)轉(zhuǎn)移算法（ISTA）。在ISTA 中，采用統(tǒng)計(jì)方法優(yōu)化狀態(tài)變換算子因子的選擇[13]，然后采用二次插值技術(shù)代替平移變換算子，并提出了一種新的隨機(jī)變異策略，以提高算法跳出局部最優(yōu)解的概率。下面將詳細(xì)介紹這些修改策略。

3.1 最優(yōu)參數(shù)選擇

3.2 二次插值策略

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

3.3 隨機(jī)變異策略

3.4 所提算法的操作流程

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

步驟1 初始化算法參數(shù)；

步驟2 通過統(tǒng)計(jì)方法選擇最優(yōu)伸縮變換算子參數(shù)；

步驟3 執(zhí)行伸縮變換，若伸縮變換產(chǎn)生的最好解優(yōu)于當(dāng)前解，以50%的概率選擇執(zhí)行二次插值或隨機(jī)變異操作，并以貪婪準(zhǔn)則更新當(dāng)前最好解；

步驟4 重復(fù)步驟3，Tp次；

步驟5 重復(fù)步驟2，3 和4。不同的是將伸縮變換替換為旋轉(zhuǎn)變換；

步驟6 重復(fù)步驟2，3 和4。不同的是將伸縮變換替換為坐標(biāo)變換；

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

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

圖1 ISTA 流程圖

4 應(yīng)用于傳感器網(wǎng)絡(luò)定位問題

4.1 ISTA 算法測試

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

表1 幾種算法在四個(gè)基準(zhǔn)函數(shù)上的結(jié)果

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

4.2 應(yīng)用于SNL 問題

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

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

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

圖4 STA 在300 個(gè)傳感器的SNL 問題上獲得的最好結(jié)果

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

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

更具體地說，對(duì)于12 個(gè)傳感器問題，三種算法都找到了最優(yōu)解。從表2 中可以看出，ISTA 得到的統(tǒng)計(jì)結(jié)果顯示，基本STA 消耗的時(shí)間最少，但I(xiàn)STA 獲得的最好值、平均值、最差值和標(biāo)準(zhǔn)差均為最佳。此外，從圖2 中的平均迭代曲線可以明顯看出，ISTA 相比于基本STA 和DSTA 可以更快地收斂到全局最優(yōu)解。此外，對(duì)于兩個(gè)大規(guī)模的SNL 問題，使用基于梯度的優(yōu)化技術(shù)對(duì)這三種算法都進(jìn)行了進(jìn)一步加強(qiáng)。表2 中的統(tǒng)計(jì)結(jié)果表明ISTA的獲得的結(jié)果也是最好的，而STA 和DSTA 都陷入局部最優(yōu)解，這在圖5 和圖6 中也得到了驗(yàn)證。值得強(qiáng)調(diào)的是，在300 個(gè)傳感器的大規(guī)模SNL 問題求解中，ISTA 比基本STA 和DSTA 消耗的時(shí)間少得多。

表2 幾種算法在SNL 實(shí)例上的求解結(jié)果

5 結(jié)論

本文提出了一種改進(jìn)的狀態(tài)轉(zhuǎn)移算法來求解全局?jǐn)?shù)值優(yōu)化和傳感器網(wǎng)絡(luò)定位問題。該算法采用二次插值技術(shù)代替平移算子進(jìn)行局部搜索，提高了STA 的局部搜索能力。另外，采用隨機(jī)新變異策略，減小算法陷入局部最優(yōu)解的可能性。數(shù)值實(shí)驗(yàn)表明，與其他5 種隨機(jī)優(yōu)化算法相比，ISTA 具有更強(qiáng)的局部和全局搜索能力和較快的收斂速度。采用梯度技術(shù)增強(qiáng)的ISTA 在求解大規(guī)模SNL 問題的結(jié)果表明，與基本STA 和DSTA 相比，所提算法的性能也有顯著提高。在未來的工作中，該算法可以擴(kuò)展到多目標(biāo)優(yōu)化、約束優(yōu)化、組合優(yōu)化和更復(fù)雜的現(xiàn)實(shí)問題。