張亞明，史浩山，陳客松，程 偉

(1. 西安石油大學電子工程學院 西安 710065；2. 西北工業(yè)大學電子信息學院 西安 710129；3. 電子科技大學電子工程學院 成都 611731)

一種改進的無線傳感器網(wǎng)絡優(yōu)化定位算法

張亞明1,2，史浩山2，陳客松3，程 偉2

(1. 西安石油大學電子工程學院 西安 710065；2. 西北工業(yè)大學電子信息學院 西安 710129；3. 電子科技大學電子工程學院 成都 611731)

節(jié)點定位是無線傳感器網(wǎng)絡實際應用需要解決的關(guān)鍵問題。為了在提高定位精度的同時降低成本，提出了一種改進的粒子群優(yōu)化定位算法。該算法首先提出前攝估計思想，完成未知節(jié)點的區(qū)域估計，縮小并限制可行解空間，以此加快粒子群的搜索速度；然后給出了競爭進化思想的數(shù)學模型，使用該模型和自適應權(quán)重在進一步加快收斂速度的同時增強了算法的全局和局部搜索能力。仿真結(jié)果表明，對比同類算法，該算法能更有效地利用錨節(jié)點信息，降低網(wǎng)絡成本，在計算量顯著減少的同時明顯提高了定位精度，并且具有對測距誤差魯棒性強的優(yōu)點。

競爭進化; 定位; 粒子群算法; 前攝估計; 無線傳感器網(wǎng)絡

節(jié)點定位技術(shù)[1-2]是無線傳感器網(wǎng)絡[3]的一項重要支撐技術(shù)。目前，國內(nèi)外學者已先后提出了多種定位解決方案和算法。因為無線傳感器網(wǎng)絡存在網(wǎng)絡環(huán)境復雜多變、錨節(jié)點不充分、測距不準確等特殊性，學者們將其定位問題轉(zhuǎn)化為約束優(yōu)化類問題[4-11]，并使用智能計算技術(shù)進行求解。如文獻[8]提出的SAL算法，把模擬退火算法(SA)用于無線傳感網(wǎng)絡節(jié)點定位，這是較早嘗試把定位問題轉(zhuǎn)化為優(yōu)化問題的研究之一。該方法的缺點是計算量太大，且定位精度有限。文獻[9]提出將粒子群算法(PSO)用于無線傳感器網(wǎng)絡定位。相對于SAL算法，文獻[9]所提算法表現(xiàn)出較好的定位效果和較低的計算成本，但該算法只是簡單使用PSO算法進行尋優(yōu)定位，并沒有針對無線傳感器網(wǎng)絡的特點做出任何修改。文獻[10-11]在引入PSO算法的基礎(chǔ)上進行了適當改進。文獻[10]在第一階段使用改進的DV-distance算法進行所有節(jié)點位置的粗略估計，第二階段使用PSO算法完成精確估計；文獻[11]則借助遠端錨節(jié)點的位置信息提高網(wǎng)絡中未知節(jié)點的定位成功率。文獻[12]將PSO算法與DV-Hop算法相結(jié)合，用于對DV-Hop算法的定位結(jié)果進行優(yōu)化求精。文獻[13]則分別使用高斯?牛頓算法和PSO算法優(yōu)化節(jié)點位置，并通過物理實驗證明PSO算法的優(yōu)化效果更佳，魯棒性更強。文獻[14]使用競爭進化思想和自適應權(quán)重策略對PSO算法進行改進，并在WSN定位中取得了較好的定位效果。然而，該文獻對于粒子歷史最優(yōu)和種群全局最優(yōu)的計算過程在描述上較為模糊，并未給出具體的數(shù)學模型。

在上述研究的啟發(fā)下，本文提出一種改進的粒子群優(yōu)化定位算法。該算法首先提出前攝估計思想，在搜索尋優(yōu)前以極其簡單的計算為代價合理估計并極大縮小可行解空間；再對競爭進化思想進行了更詳細地闡述，并給出了具體的數(shù)學模型。仿真結(jié)果顯示本文算法在顯著降低計算成本的同時有效提高了定位精度，驗證了算法的有效性和實用性。

1 粒子群算法基本原理

粒子群算法[15]是一種基于種群的啟發(fā)式智能進化計算技術(shù)。它是受到飛鳥集群活動的啟發(fā)，進而利用群體智能策略建立的一個簡化模型。與其他傳統(tǒng)智能計算技術(shù)相比，粒子群算法只有簡單幾個參數(shù)，具有實現(xiàn)簡單、易收斂且計算量小等優(yōu)點。

假設(shè)D表示搜索空間(即解空間)維度；P表示粒子種群規(guī)模；Xi=[xi,1,xi,2,,xi,D]和Vi=[vi,1,vi,2,,vi,D]分別表示群體中第i個粒子的位置和速度，則PSO算法的數(shù)學模型可表示為：

可以看到，粒子能在每一次進化中追蹤個體最優(yōu)解pbest和全局最優(yōu)解gbest，進而更新自己的速度和位置。

2 基于改進粒子群的WSN節(jié)點定位

2.1 問題描述

假設(shè)無線傳感器網(wǎng)絡由M個坐標為Mi(xi,yi) (i=1,2,,M)的錨節(jié)點和N?M(M

式中，(x,y)表示未知節(jié)點坐標；di表示未知節(jié)點到第i個鄰居錨節(jié)點的歐式距離表示測距結(jié)果；n為所求未知節(jié)點的鄰居錨節(jié)點數(shù)目。

2.2 粒子群算法的改進

當前有很多文獻從優(yōu)化計算的角度對PSO算法進行了改進，試圖進一步提高其性能[16]。本文結(jié)合WSN定位的特點，在對PSO算法做出合理改進的同時，在算法性能和復雜度之間進行了平衡。首先提出前攝估計思想；接著對競爭進化策略進行了詳細討論，并給出了具體數(shù)學模型。

2.2.1 前攝估計

前攝估計指在執(zhí)行搜索尋優(yōu)之前，對待定位節(jié)點所在區(qū)域進行合理估計，極大縮小并限制可行解空間，為粒子群算法的執(zhí)行減小難度和復雜度，從而達到降低計算量節(jié)約能耗的目的。

采用邊界盒[17]方法實現(xiàn)前攝估計。該方法是指未知節(jié)點以其所有鄰居錨節(jié)點的正方形覆蓋區(qū)域(該正方形覆蓋區(qū)域以相應錨節(jié)點為中心，邊長是節(jié)點最大通信距離的二倍)的交集的幾何中心作為其位置估計的一種算法。該算法的優(yōu)勢是計算矩形交集比計算圓形交集更加簡單易實現(xiàn)，所需計算量最小，可大大節(jié)約傳感器節(jié)點在定位過程中的能耗；缺點是定位精度較低。文獻[18]提出了一種改進方法，即未知節(jié)點在使用邊界盒方法初步確定自身的估計區(qū)域后，通過信息交互獲取通信范圍內(nèi)其他未知節(jié)點的區(qū)域估計信息，再次縮小自己的估計區(qū)域。該方法的不足在于精度提高有限且兩次估計之間有一個較長的等待過程。

本文在文獻[18]基礎(chǔ)上設(shè)計一種改進的估計方法，即未知節(jié)點接收完鄰居錨節(jié)點信息后，先把自身ID及其存儲的所有鄰居錨節(jié)點信息進行廣播(如果該節(jié)點沒有鄰居錨節(jié)點則不廣播)，同時接收其他未知節(jié)點廣播的此類信息，然后再完成估計過程。具體流程如圖1所示。

計算本節(jié)點初次估計區(qū)域為：

計算節(jié)點的最終估計區(qū)域為：

式中，(xi,yi)表示錨節(jié)點坐標；r表示節(jié)點最大通信距離；gleft、gright、gdown和gup表示估計結(jié)果；glefti、grighti、gdowni和gupi表示鄰居未知節(jié)點i的估計結(jié)果。

可以看到，本文方法只需要執(zhí)行極其簡單的加減運算或者min(max)運算即可完成未知節(jié)點位置的區(qū)域估計，為隨后的搜索極大縮小了解空間，減少計算量節(jié)約能耗的同時加快算法全局搜索速度，提高了算法的實用性

為了進一步提高算法性能，特別是進一步增強算法的全局和局部搜索能力，本文算法還使用了競爭進化策略和自適應權(quán)重[14]。

2.2.2 競爭進化

競爭進化策略是在優(yōu)勝劣汰思想的基礎(chǔ)上增加了分裂進化機制，本文在文獻[14]的基礎(chǔ)上對競爭進化策略進行了更深入細致地闡述，并給出了具體的數(shù)學模型。

在種群(簡稱“全局群”，區(qū)別于后面的“局部群”)進化過程中，每代進化完成后，首先計算種群中所有粒子的適應度值；再根據(jù)種群內(nèi)所有粒子的不同適應度值，先淘汰一半性能差的粒子(在下一次迭代運算之前產(chǎn)生同樣數(shù)目的隨機粒子代替淘汰掉的粒子，以保證種群規(guī)模不變)；然后將當前所有剩余粒子作為“優(yōu)選粒子(winner particles)”進行分裂進化。分裂進化就是以每個優(yōu)選粒子當前位置為中心，設(shè)置一個小的搜索范圍，然后引入相互獨立的局部粒子群(簡稱“局部群”)并執(zhí)行局部搜索(即這些局部群會被初始化并執(zhí)行少量的迭代運算)。迭代運算結(jié)束后，各優(yōu)選粒子會將其個體歷史最優(yōu)位置的適應度值和對應的執(zhí)行局部搜索的局部群的全局歷史最優(yōu)位置的適應度值相比較。如果優(yōu)于則用該局部群的全局歷史最優(yōu)位置及其對應的適應度更新相應粒子的個體歷史最優(yōu)位置及其適應度否則該粒子的個體歷史最優(yōu)位置及其適應度不變。判定規(guī)則為(k表示進化代數(shù))：

至此，即完成一次競爭進化。接著全局群內(nèi)所有粒子更新其位置和速度，進入下一次進化。

2.2.3 自適應權(quán)重

在PSO算法中，若w取值較大，則粒子的全局搜索能力較強，有利于粒子跳出局部極小點，但同時也會降低算法的局部搜索能力；若w取值較小，則粒子的局部挖掘能力較強，有利于算法收斂，但同時會降低算法全局搜索能力。本文采用自適應權(quán)重w來保證算法在快速收斂的同時平衡全局和局部搜索能力[14]：

2.3 PECEPSO算法步驟

綜上所述，本文提出了基于前攝估計、競爭進化和自適應權(quán)重的PECEPSO算法，該算法步驟簡要描述如下：

1) 執(zhí)行前攝估計過程，確定搜索空間S。

2) 令iter=0(iter表示進化代數(shù))，設(shè)當前種群規(guī)模為ncur，若ncur

3) 對當前種群執(zhí)行一次競爭進化過程；

4) 判斷是否滿足進化終止條件。若滿足，則輸出所保留的最好解作為未知節(jié)點的最優(yōu)位置估計，算法結(jié)束；反之，令iter=iter+1，轉(zhuǎn)入步驟2)。

為不增加硬件成本并保持低功耗特性，本文算法采用RSSI測距技術(shù)完成鄰居節(jié)點間的距離測量。考慮到實際應用中無線信號受環(huán)境影響，其通信范圍模型不是理想圓形，會存在較大的測距誤差，在仿真實驗過程中會充分考慮由此帶來的測距誤差等因素。

3 仿真實驗及分析

3.1 仿真說明

本文利用MATLAB 7.0進行仿真實驗。為驗證算法的有效性和實用性，所有節(jié)點(100個)的坐標在網(wǎng)絡部署區(qū)域(100 m×100 m)內(nèi)隨機生成，并與同類DPSO算法[10]、Standard PSO算法和基于測距的定位算法Improved DV[19]相比較。

實驗評價指標為T次實驗所得未知節(jié)點相對定位誤差(估計坐標與實際坐標之間的距離與節(jié)點通信半徑之比)的算法平均。相關(guān)參數(shù)設(shè)置如下：節(jié)點通信半徑為30 m；PECEPSO算法的全局粒子群規(guī)模為10，最大迭代10次，局部粒子群規(guī)模為2，最大迭代4次；DPSO算法的種群規(guī)模為30，迭代次數(shù)為30；Standard PSO算法的種群規(guī)模為50，迭代次數(shù)為100。

3.2 仿真及分析

3.2.1 不同錨節(jié)點密度時的定位結(jié)果比較

錨節(jié)點的費用比普通節(jié)點高兩個數(shù)量級，所以錨節(jié)點密度將直接關(guān)系到整個網(wǎng)絡成本大小。圖2顯示了不同錨節(jié)點密度時4種算法的定位效果(測距誤差設(shè)為25%)。

在圖2中，隨著錨節(jié)點密度的增大，平均定位誤差都逐漸減小。以定位誤差降低較顯著的Improved DV算法為例，當錨節(jié)點密度為10%時，其定位誤差達40%以上，而當錨節(jié)點密度達到最大的50%時，其定位誤差下降到了12%左右。這是因為錨節(jié)點數(shù)目的增加使網(wǎng)絡中每個未知節(jié)點的鄰居錨節(jié)點個數(shù)也隨之增多，未知節(jié)點可以獲得更多的位置參考信息，更容易被定位且誤差降低。可以看到，基于PSO優(yōu)化思想的3種算法定位誤差降低趨勢相對錨節(jié)點比例增高表現(xiàn)相對穩(wěn)定，其中本文算法定位效果最好，定位精度明顯優(yōu)于同樣基于PSO優(yōu)化思想的DPSO。在相同的定位誤差下，本文算法需要的錨節(jié)點數(shù)也最少，可見本文算法更能充分有效利用錨節(jié)點信息，更能有效節(jié)省網(wǎng)絡成本。

3.2.2 不同通信距離時的定位結(jié)果比較

圖3顯示了在不同通信距離時4種定位算法的定位效果(測距誤差設(shè)為25%)。

由圖3可以看到，因為節(jié)點通信距離變大使得網(wǎng)絡連通度提高，所以各算法的平均定位誤差均逐漸減小。基于PSO優(yōu)化思想的3種定位算法表現(xiàn)依然穩(wěn)定(誤差下降程度相對于通信距離增加程度)，其中本文算法的平均定位誤差始終保持最小，同樣明顯優(yōu)于DPSO算法。另外，在相同的定位誤差下，本文算法所需通信半徑最小，而通信半徑越小，越有利于降低能耗，所以本文算法更有利于節(jié)約能耗，延長網(wǎng)絡壽命，降低網(wǎng)絡維護成本。

3.2.3 不同測距誤差時的定位結(jié)果比較

針對之前提到的實際應用中無線信號會受環(huán)境影響，產(chǎn)生不同程度的測距誤差問題，本文進行了研究分析，如圖4所示。

由圖4可以看到，隨著測距誤差增大，平均定位誤差均逐漸增大，特別是Improved DV算法定位誤差表現(xiàn)明顯，這主要是因為該算法需要累加測距結(jié)果，會造成較大的積累誤差，從而嚴重影響定位精度。而本文算法定位效果依然最好，雖然定位誤差也隨測距誤差增大而增大，但表現(xiàn)相對穩(wěn)定，尤其是當測距誤差較大時，本文算法定位精度仍然很高，可見本文算法的抗誤差性能最強，具有更高的有效性和實用性，能適應更廣泛的應用場合。

3.2.4 算法計算量分析

算法復雜度及抗測量誤差性能比較如表1所示。

在表1中，m表示種群規(guī)模；k表示迭代次數(shù)；n表示本文算法中局部群的種群規(guī)模；l表示本文算法中局部群的迭代次數(shù)。

由表1分析各算法進化計算量如下：按照3.1節(jié)的參數(shù)設(shè)置，標準粒子群算法的種群規(guī)模m=50，進化次數(shù)k=100，所以該算法總的個體進化計算量可表示為a=m×k=50×100=5 000 次；DPSO算法種群規(guī)模m=30，進化次數(shù)k=30，所以該算法總的個體進化計算量可表示為a=m×k=30×30=900 次；而本文算法的全局群規(guī)模m=10，進化次數(shù)k=10，局部群規(guī)模n=2，進化次數(shù)l=4，再考慮到全局群在每次迭代中只有一半最優(yōu)粒子會進行局部搜索，本文算法總的個體進化計算量可表示為a=m×k×n×l/2 =10×10×2×4/2= 400 次。

由表1可以看到，本文算法復雜度最大，但是通過上述進化計算量分析和仿真實驗結(jié)果(見圖2～圖4)可以看到，本文算法達到更高定位精度的同時所需的進化計算量最小。這主要得益于本文對前攝估計、競爭進化及自適應權(quán)重等方法的使用。其中前攝估計方法使得算法的搜索空間由整個網(wǎng)絡覆蓋區(qū)域縮小到一個較小的范圍，為粒子群算法的執(zhí)行減小難度和復雜度，使得算法得以更快地找到最優(yōu)解；競爭進化和自適應權(quán)重方法使得算法收斂速度進一步加快的同時增強了其全局和局部搜索能力。

如果對定位精度的要求不高，則迭代運算量還可進一步調(diào)小。這樣在節(jié)約能耗的同時提高定位精度，而且有著極好的抗測距誤差性能，本文算法的有效性和實用性已經(jīng)得到充分證明和體現(xiàn)。

4 結(jié) 束 語

針對無線傳感器網(wǎng)絡節(jié)點定位問題，本文提出一種基于前攝估計思想、競爭進化思想和自適應權(quán)重的優(yōu)化定位算法。前攝估計思想通過改進的邊界盒方法來合理估計節(jié)點所在區(qū)域，縮小并限制了可行解空間，在減小計算量的同時加快了算法全局搜索速度；競爭進化思想與自適應權(quán)重相結(jié)合在保證算法進一步加快收斂的同時增強了算法的全局和局部搜索能力。仿真實驗表明，新算法在明顯提高定位精度的同時能夠有效降低網(wǎng)絡成本、節(jié)約能耗，并具有對測距誤差魯棒性強的優(yōu)點。

[1] BOUKERCHE A, OLIVEIRA H A B, NAKAMURA E F, et al. Localization systems for wireless sensor networks[J]. IEEE Wireless Commun, 2007, 14(6): 6-12.

[2] PANWAR A, KUMAR S A. Localization schemes in wireless sensor networks[C]//Proc 2nd International Conference on Advanced Computing & Communication Technologies. Rohtak, Haryana: IEEE, 2012: 443-449.

[3] AKYILDIZ I F, SU W, SANKARSUBRAMANLAM Y. Wireless sensor networks: a survey[J]. Computer Networks, 2002, 38(4): 393-422.

[4] ZHU S H, DING Z G. Distributed cooperative localization of wireless sensor networks with convex hull constraint[J]. IEEE Trans on Wireless Commun, 2011, 10(7): 2150-2161.

[5] LOW K S, NGUYEN H A, GUO H. A particle swarm optimization approach for the localization of a wireless sensor network[C]//Proc IEEE International Symposium on Industrial Electronics. Cambridge, USA: IEEE, 2008: 1820-1825.

[6] WANG S, HU H S, KLAUS M M. Optimization and sequence search based localization in wireless sensor networks[C]//Proc 3rd International Conference on Emerging Security Technologies. Lisbon, Portugal: IEEE, 2012: 155- 160.

[7] CHENG Y, WANG X, CAELLI T, et al. Optimal nonlinear estimation for localization of wireless sensor networks[J]. IEEE Transactions on Signal Processing, 2011, 59(12):5674-5685.

[8] KANNAN A A, MAO G, VUCETIC B. Simulated annealing based wireless sensor network localization[J]. Journal of Computers, 2006, 1(2): 15-22.

[9] GOPAKUMAR A, JACOB L. Localization in wireless sensor networks using particle swarm optimization[C]//Proc IET International Conference on Wireless, Mobile and Multimedia Networks. Mumbai, India: IET Press, 2008: 227-230.

[10] NAMIN P H, TINATI M A. Node localization using particle swarm optimization[C]//Proc 7th International Conference on Intelligent Sensors, Sensor Networks and Information Processing. Adelaide, SA, South Australia: IEEE, 2011: 288-293.

[11] CHUANG P J, WU C P. Employing PSO to enhance RSS range-based node localization for wireless sensor networks[J]. Journal of Information Science and Engineering, 2011, 27(5): 1597-1611.

[12] CHEN X, ZHANG B L. Improved DV-Hop node localization algorithm in wireless sensor networks[EB/OL]. (2012-07-19). http://dx.doj.org/10.1155/2012/213980.

[13] GUO H, LOW K S, NGUYEN H A. Optimizing the localization of a wireless sensor network in real time based on a low-cost microcontroller[J]. IEEE Trans Ind Electron, 2011, 58(3): 741-749.

[14] 張亞明, 史浩山, 程偉, 等. 一種無線傳感器網(wǎng)絡中的進化定位機制[J]. 西北工業(yè)大學學報, 2013, 31(4): 633-638. ZHANG Ya-ming, SHI Hao-shan, CHENG Wei, et al. A novel evolution localization mechanism in WSN[J]. Journal of Northwestern Polytechnical University, 2013, 3(4): 633-638.

[15] KENNEDY J, EBERHART R C. Particle swarm optimization[C]//Proc IEEE International Conference on Neural Networks. Perth, Australian: IEEE, 1995: 1942-1948.

[16] HU M, WU T, WEIR J D. An adaptive particle swarm optimization with multiple adaptive methods[J]. IEEE Trans Evolut Comput, 2013, 17(5): 705-720.

[17] SIMIC S N, SASTRY S. Distributed localization in wireless adhoc networks[R]. University of California Technical Report, 2002.

[18] 王行甫, 劉志強, 黃秋原, 等. WSN中一種改進的邊界盒定位算法[J]. 計算機工程, 2011, 37(20): 57-59. WANG Xing-fu, LIU Zhi-qiang, HUANG Qiu-yuan, et al. Improved bounding-box localization algorithm in WSN[J]. Computer Engineering, 2011, 37(20): 57-59.

[19] WANG D H, JIA H D, CHEN F X, et al. An improved dv-distance localization algorithm for wireless sensor networks[C]//Proc 2nd International Conference on Advanced Computer Control. Shenyang: IEEE, 2010: 472 -476.

編 輯 張 俊

An Improved Optimization Localization Algorithm in WSNs

ZHANG Ya-ming1,2, SHI Hao-shan2, CHEN Ke-song3, and CHENG Wei2
(1. School of Electronics Engineering, Xi’an Shiyou University Xi’an 710065;2. School of Electronics and Information, Northwestern Polytechnical University Xi’an 710129;3. School of Electronic Engineering, University of Electronic Science and Technology of China Chengdu 611731)

Node localization of wireless sensor networks (WSNs) is a key problem in the practical applications. To improve the localization accuracy and reduce the cost, an improved localization algorithm based on particle swarm optimization (PSO) is proposed. In the algorithm, the idea of proactive estimate is introduced to estimate the area of nodes, reduce and restrict the solution space, so as to quicken the search speed of particles, and then the idea of competition evolution and adaptive weighting are used to enhance the global and local search ability when accelerating convergence speed. Simulation results show that, compared with other similar methods, the proposed algorithm can make more effective use of anchor node information, reduce the cost of network, and increase positioning accuracy while significantly reducing the calculation amount. Moreover the algorithm shows robust for communication ranging error.

competition evolution; localization; particle swarm optimization; proactive estimation; wireless sensor networks

TP393

A

10.3969/j.issn.1001-0548.2015.03.007

2013 ? 04 ? 22；

2015 ? 01 ? 12

國家自然科學基金(U1233103, 61401360, 61301092)

張亞明(1980 ? )，男，博士，講師，主要從事無線通信、無線傳感器網(wǎng)絡關(guān)鍵技術(shù)等方面的研究.