趙 吉, 紀志成

(1.江南大學(xué) 電氣自動化研究所，江蘇 無錫 214122;2.無錫城市職業(yè)技術(shù)學(xué)院 電子信息工程系，江蘇 無錫 214000)

基于隨機漂移粒子群算法的WSNs節(jié)點定位*

趙 吉1，2, 紀志成1

(1.江南大學(xué) 電氣自動化研究所，江蘇 無錫 214122;2.無錫城市職業(yè)技術(shù)學(xué)院 電子信息工程系，江蘇 無錫 214000)

提出了隨機漂移粒子群優(yōu)化(RDPSO)算法，并將該算法應(yīng)用于接收信號強度指示(RSSI)定位算法中，以降低由RSSI測距產(chǎn)生的定位誤差。在仿真實驗中，分別比較了基于RDPSO和PSO的RSSI定位算法。實驗結(jié)果表明：RDPSO算法是在優(yōu)化性能上優(yōu)于PSO算法，有效提高了節(jié)點定位精度，證明該方法收斂速度快，穩(wěn)定性能好，精度高，適用于WSNs節(jié)點定位問題。

隨機漂移粒子群優(yōu)化算法；定位；無線傳感器網(wǎng)絡(luò)；接收信號強度指示

0 引 言

無線傳感器網(wǎng)絡(luò)(wireless sensor networks ,WSNs)憑借全新的信息獲取處理技術(shù)，在軍事應(yīng)用、環(huán)境監(jiān)測、目標跟蹤、智能交通及入侵監(jiān)測等定位相關(guān)的領(lǐng)域具有廣泛的應(yīng)用前景[1]。在這些應(yīng)用中，傳感器節(jié)點的位置信息直接反映了監(jiān)測目標所處的位置，如果沒有具體的位置信息，采集的數(shù)據(jù)就是無效或無意義的[2]，目標監(jiān)測就將失去意義。近年來，已經(jīng)有很多學(xué)者提出了將進化算法和群體智能優(yōu)化算法應(yīng)用于WSNs的節(jié)點定位問題中[3～5]。本文提出了隨機漂移粒子群優(yōu)化(random drift particle swarm optimization,RDPSO)算法，并將該算法應(yīng)用于接收信號強度指示(recieved signal strength indication,RSSI)節(jié)點定位中，以降低由于RSSI測距產(chǎn)生的定位誤差，提高節(jié)點定位精度。

1 RDPSO算法

粒子群優(yōu)化(PSO)算法是一種基于群體進化的高效優(yōu)化算法[6]。但Van已經(jīng)驗證PSO算法不能保證全局收斂[7]。為此,本文提出RDPSO算法。

(1)

(2)

(3)

公式(1)的物理解釋為公式右邊可以分成2個部分，即

(4)

(5)

其中，α1和α2分別為α的初始值和最終值，n為當前迭代次數(shù)和nmax為允許的最大迭代數(shù)。

RDPSO算法詳細描述如下：

Beign

初始化種群的每個粒子的位置向量和速度向量；

Do

Fori=1 to 粒子數(shù)大小

Iff(xi)

G=min(Pi)

運用式(3)計算得到Cj

Ford=1 toD

end for

end if

end for

end do

直到終止條件滿足，最后得到的gbest就是優(yōu)化得到的全局最優(yōu)解。

end

2 基于RDPSO的RSSI定位算法

2.1 問題描述

2.2 定位方法實現(xiàn)步驟

基于RDPSO的RSSI定位算法實現(xiàn)步驟：

1)在區(qū)域內(nèi)隨機部署未知節(jié)點和錨節(jié)點，錨節(jié)點定期發(fā)送自身信息，如節(jié)點標示ID和未知信息。

2)未知節(jié)點接收到錨節(jié)點信息后，根據(jù)RSSI測距算法計算得出與錨節(jié)點之間的距離 。

3)對于錨節(jié)點個數(shù)大于3的未知節(jié)點，采用RDPSO算法進行定位。

3 實驗仿真

3.1 參數(shù)設(shè)置

3.2 實驗結(jié)果

圖1顯示了通信半徑為15 m情況下錨節(jié)點占總節(jié)點比例與平均定位誤差的關(guān)系。從圖1可以看出:隨著錨節(jié)點比例的增加，各種定位算法的平均定位誤差都會逐漸下降。當錨節(jié)點比例達到25 %時，平均定位誤差改變不大，并且兩種算法產(chǎn)生的誤差趨于接近。同時可以看出基于RDPSO算法的定位誤差均比PSO算法得到的定位誤差小。圖2為錨節(jié)點比例為15 %情況下錨節(jié)點通信半徑與平均定位誤差的關(guān)系，可以看出,錨節(jié)點通信半徑增加，未知節(jié)點的鄰居錨節(jié)點數(shù)量增加，網(wǎng)絡(luò)連通度也隨之增大，定位誤差隨之降低。從圖2可以看出:基于RDPSO算法的定位誤差是最小的。為了進一步比較，圖3列出了不同算法的收斂曲線?？梢钥闯鯮DPSO算法收斂速度非常快，基本在運行30次就已經(jīng)能找到最優(yōu)值，而PSO算法則需要60次左右才趨于穩(wěn)定。圖4給出了不同鄰居錨節(jié)點數(shù)量的算法運行時間。從圖4可以看出:隨著鄰居錨節(jié)點數(shù)量增加，RDPSO和PSO算法優(yōu)化時間也逐步增大，但RDPSO算法的效率更高。

圖1 錨節(jié)點比率與平均定位誤差Fig 1 Anchor nodes ratio and average localization error

圖2 通信半徑與平均定位誤差Fig 2 Communication radius and average localization error

圖3 算法收斂曲線Fig 3 Convergence curve of algorithms

圖4 算法運行時間與鄰居錨節(jié)點數(shù)量Fig 4 Running time of algorithms and number of neighbor anchor nodes

由此可以看出:由于RDPSO提高了算法的隨機搜索能力，增強了粒子的多樣性，在RSSI定位算法中使用RDPSO算法可以進一步提高定位精度，并且收斂速度和穩(wěn)定性方面要優(yōu)于PSO算法。

4 結(jié) 論

本文研究了基于RDPSO算法和PSO算法的RSSI的WSNs節(jié)點定位問題。本文簡單介紹了RDPSO算法思想來源及其算法過程，并利用RDPSO算法和PSO算法優(yōu)化RSSI模型測距定位算法。通過仿真實驗結(jié)果比較表明：基于RDPSO算法的RSSI節(jié)點定位方法具有更好的定位精度和定位性能，收斂速度快，穩(wěn)定性高，證明了該方法的有效性。

[1] Agre J,Clare L.An integrated architecture for cooperative sensing networks[J].IEEE Computer Magazine,2000,33(5):106-108.

[2] Patwari N,Ash J N,Kyperountas S,et al.Locating the nodes:Cooperative localization in wireless sensor networks[J].IEEE Signal Processing Magazine,2005,22(4):54-69.

[3] 余成波，張一萌，李洪兵，等.無線傳感器網(wǎng)絡(luò)自校正定位算法[J].振動、測試與診斷，2012，32(1)：6-10.

[4] 陳星舟，廖明宏，林建華.基于粒子群優(yōu)化的無線傳感器網(wǎng)絡(luò)節(jié)點定位改進[J].計算機應(yīng)用，2010，30(7)：1736-1738.

[5] 張廣峰，段其昌，劉 政.基于加強學(xué)習(xí)與聯(lián)想記憶粒子群優(yōu)化算法的節(jié)點定位[J].傳感器與微系統(tǒng)，2013，32(3)：72-73.

[6] Kennedy J,Eberhart R C.Particle swarm optimization[C]∥Proceedings of the IEEE International Joint Conference on Neural Networks,1995:942-1948.

[7] Van den Bergh F.An analysis of particle swarm optimizers [D].Pretoria:University of Pretoria,2001.

[8] Omar M A.Elementary solid state physics:Principles and applications [M].4th ed.Boston:Addison-Wesley,1994.

[9] Clerc M,Kennedy J.The particle swarm explosion:Stability and convergence in a multi-dimensional complex space [J].IEEE Trans on Evolutionary Compute,2002,6(1):58-73.

WSNs node localization based on random drift particle swarm optimization algorithm*

ZHAO Ji1，2, JI Zhi-cheng1

(1.Institute of Electrical Automation, Jiangnan University, Wuxi 214122,China;2.Department of Electronic Information Engineering,Wuxi City College of Vocational Technology,Wuxi 214000,China)

Random drift particle swarm optimization(RDPSO) algorithm is presented and applied to RSSI localization algorithm，in order to reduce positioning errors generated by RSSI ranging.In simulation experiments,RSSI localization algorithm based on RDPSO is compared with that based on particle swarm optimization(PSO).Experimental results indicate that RDPSO algorithm is superior to PSO algorithm in optimizing performance,which improves positioning precision of nodes,it is proved that the method has fast convergence speed,good stability and high precision.which is suitable for WSNs node localization problem.

random drift particle swarm optimization(RDPSO) algorithm; localization; wireless sensor networks(WSNs); RSSI

10.13873/J.1000—9787(2014)10—0141—03

2014—02—17

國家自然科學(xué)基金資助項目(61300149)；江蘇省博士后基金資助項目(1101124C)；2012年江蘇省高校青藍工程資助項目；江蘇省青藍工程資助項目(2012—16)

TP 393

A

1000—9787(2014)10—0141—03

趙 吉(1980-)，女，江蘇無錫人，博士后，主要研究方向為進化計算、人工智能。