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

趙 吉, 紀(jì)志成

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

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

趙 吉1，2, 紀(jì)志成1

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

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

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

0 引 言

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

1 RDPSO算法

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

(1)

(2)

(3)

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

(4)

(5)

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

RDPSO算法詳細(xì)描述如下：

Beign

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

Do

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

Iff(xi)

G=min(Pi)

運(yùn)用式(3)計(jì)算得到Cj

Ford=1 toD

end for

end if

end for

end do

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

end

2 基于RDPSO的RSSI定位算法

2.1 問(wèn)題描述

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

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

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

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

3)對(duì)于錨節(jié)點(diǎn)個(gè)數(shù)大于3的未知節(jié)點(diǎn)，采用RDPSO算法進(jìn)行定位。

3 實(shí)驗(yàn)仿真

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

3.2 實(shí)驗(yàn)結(jié)果

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

圖1 錨節(jié)點(diǎn)比率與平均定位誤差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 算法運(yùn)行時(shí)間與鄰居錨節(jié)點(diǎn)數(shù)量Fig 4 Running time of algorithms and number of neighbor anchor nodes

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

4 結(jié) 論

本文研究了基于RDPSO算法和PSO算法的RSSI的WSNs節(jié)點(diǎn)定位問(wèn)題。本文簡(jiǎn)單介紹了RDPSO算法思想來(lái)源及其算法過(guò)程，并利用RDPSO算法和PSO算法優(yōu)化RSSI模型測(cè)距定位算法。通過(guò)仿真實(shí)驗(yàn)結(jié)果比較表明：基于RDPSO算法的RSSI節(jié)點(diǎn)定位方法具有更好的定位精度和定位性能，收斂速度快，穩(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ú)線傳感器網(wǎng)絡(luò)自校正定位算法[J].振動(dòng)、測(cè)試與診斷，2012，32(1)：6-10.

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

[5] 張廣峰，段其昌，劉 政.基于加強(qiáng)學(xué)習(xí)與聯(lián)想記憶粒子群優(yōu)化算法的節(jié)點(diǎn)定位[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

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

TP 393

A

1000—9787(2014)10—0141—03

趙 吉(1980-)，女，江蘇無(wú)錫人，博士后，主要研究方向?yàn)檫M(jìn)化計(jì)算、人工智能。