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

趙 吉, 紀志成

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

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

趙 吉1，2, 紀志成1

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

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

隨機漂移粒子群優化算法；定位；無線傳感器網絡；接收信號強度指示

0 引 言

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

1 RDPSO算法

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

(1)

(2)

(3)

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

(4)

(5)

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

RDPSO算法詳細描述如下：

Beign

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

Do

Fori=1 to 粒子數大小

Iff(xi)

G=min(Pi)

運用式(3)計算得到Cj

Ford=1 toD

end for

end if

end for

end do

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

end

2 基于RDPSO的RSSI定位算法

2.1 問題描述

2.2 定位方法實現步驟

基于RDPSO的RSSI定位算法實現步驟：

1)在區域內隨機部署未知節點和錨節點，錨節點定期發送自身信息，如節點標示ID和未知信息。

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

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

3 實驗仿真

3.1 參數設置

3.2 實驗結果

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

圖1 錨節點比率與平均定位誤差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 算法運行時間與鄰居錨節點數量Fig 4 Running time of algorithms and number of neighbor anchor nodes

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

4 結 論

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

[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] 余成波，張一萌，李洪兵，等.無線傳感器網絡自校正定位算法[J].振動、測試與診斷，2012，32(1)：6-10.

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

[5] 張廣峰，段其昌，劉 政.基于加強學習與聯想記憶粒子群優化算法的節點定位[J].傳感器與微系統，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

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

TP 393

A

1000—9787(2014)10—0141—03

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