近鄰點(diǎn)聯(lián)合測(cè)距修正粒子群優(yōu)化定位算法*

王　哲， 李　平

(長(zhǎng)沙理工大學(xué) 計(jì)算機(jī)與通信工程學(xué)院，湖南 長(zhǎng)沙 410114)

?

近鄰點(diǎn)聯(lián)合測(cè)距修正粒子群優(yōu)化定位算法*

王哲， 李平

(長(zhǎng)沙理工大學(xué) 計(jì)算機(jī)與通信工程學(xué)院，湖南 長(zhǎng)沙 410114)

針對(duì)在信標(biāo)節(jié)點(diǎn)隨機(jī)分布的環(huán)境中傳統(tǒng)測(cè)距差分修正定位算法對(duì)參考節(jié)點(diǎn)選取過(guò)于單一，導(dǎo)致測(cè)距修正系數(shù)誤差較大的問(wèn)題，提出了一種近鄰點(diǎn)聯(lián)合測(cè)距修正粒子群優(yōu)化的定位算法。它利用一種近鄰點(diǎn)聯(lián)合測(cè)距修正算法得到未知節(jié)點(diǎn)到各信標(biāo)節(jié)點(diǎn)的修正距離，然后通過(guò)一種改進(jìn)的粒子群優(yōu)化 (PSO) 算法對(duì)定位結(jié)果進(jìn)行優(yōu)化，得到未知節(jié)點(diǎn)的估計(jì)位置。仿真結(jié)果表明：改進(jìn)定位算法與傳統(tǒng)算法相比，有效地提高了定位精度和穩(wěn)定性。

無(wú)線傳感器網(wǎng)絡(luò)； 近鄰點(diǎn); 接收信號(hào)強(qiáng)度指示； 差分修正； 粒子群優(yōu)化

0　引　言

無(wú)線傳感器網(wǎng)絡(luò)(wireless sensor networks,WSNs)是一種應(yīng)用廣泛的沒(méi)有基礎(chǔ)設(shè)施的自組織無(wú)線網(wǎng)絡(luò)[1]，其成本低、功耗小，具有優(yōu)良的性能。節(jié)點(diǎn)位置信息成為研究WSNs技術(shù)和應(yīng)用的核心領(lǐng)域之一?；诮邮招盘?hào)強(qiáng)度指示(RSSI)的測(cè)距技術(shù)是通過(guò)在傳播過(guò)程中不斷衰減的信號(hào)強(qiáng)度來(lái)估算距離[2]，在WSNs定位技術(shù)中大量被采用。但對(duì)無(wú)線傳感器來(lái)說(shuō)反射、多徑傳播、天線增益等問(wèn)題都會(huì)對(duì)RSSI產(chǎn)生傳播損耗，如何提高基于RSSI的定位精度是個(gè)難題[3]。

文獻(xiàn)[4]從不同角度研究了基于RSSI的無(wú)線傳感器網(wǎng)絡(luò)測(cè)距模型，引入一種立體式分層思想，提出了一種基于RSSI誤差修正的待測(cè)節(jié)點(diǎn)定位算法，具有良好的穩(wěn)定性。文獻(xiàn)[5]在對(duì)測(cè)距誤差的差分修正中，僅僅選取一個(gè)參考節(jié)點(diǎn)，這對(duì)未知節(jié)點(diǎn)定位決定權(quán)過(guò)大，并且這個(gè)點(diǎn)的選取也不合理。文獻(xiàn)[6]提出了加入罰函數(shù)的粒子群優(yōu)化(PSO)定位算法，該罰函數(shù)的約束條件對(duì)所有信標(biāo)節(jié)點(diǎn)都使用統(tǒng)一的測(cè)距誤差作為測(cè)距修正系數(shù)，這并不合理。

針對(duì)上述算法尚未解決的問(wèn)題，本文提出一種定位誤差較小的基于近鄰點(diǎn)聯(lián)合測(cè)距修正PSO的定位算法。

1　傳統(tǒng)的測(cè)距差分修正定位算法

對(duì)無(wú)線傳感器來(lái)說(shuō)，RSSI易受環(huán)境影響產(chǎn)生顯著的傳播損耗，僅僅考慮兩節(jié)點(diǎn)通信的RSSI來(lái)測(cè)距，可能帶來(lái)較大的誤差。針對(duì)該缺陷測(cè)距差分修正算法可在一定程度上減小這種誤差。

傳統(tǒng)測(cè)距差分修正算法[7]通常令距離未知節(jié)點(diǎn)最近的信標(biāo)節(jié)點(diǎn)為差分參考節(jié)點(diǎn)，其余的每個(gè)信標(biāo)節(jié)點(diǎn)以該參考節(jié)點(diǎn)為基準(zhǔn)，通過(guò)真實(shí)距離和測(cè)量距離計(jì)算得到各自的距離差分修正系數(shù)，利用它來(lái)修正各信標(biāo)節(jié)點(diǎn)到未知節(jié)點(diǎn)的測(cè)量距離從而得到修正距離。然后利用加權(quán)質(zhì)心定位算法得到最終的未知節(jié)點(diǎn)的估計(jì)位置。

2　算法的改進(jìn)與實(shí)現(xiàn)

傳統(tǒng)測(cè)距差分修正算法中各修正系數(shù)的計(jì)算完全依賴距離未知節(jié)點(diǎn)最近的一個(gè)信標(biāo)節(jié)點(diǎn)，若它距未知節(jié)點(diǎn)很近則定位效果較好，但實(shí)際環(huán)境中該條件往往很難滿足，且對(duì)整個(gè)WSNs來(lái)說(shuō)僅選取單個(gè)參考節(jié)點(diǎn)不足以反映每個(gè)信標(biāo)節(jié)點(diǎn)的測(cè)距誤差情況。本文提出一種近鄰點(diǎn)聯(lián)合測(cè)距修正PSO的定位算法，該算法得到的未知節(jié)點(diǎn)到每個(gè)信標(biāo)節(jié)點(diǎn)的修正距離誤差較小，然后利用一種改進(jìn)的PSO算法對(duì)定位結(jié)果進(jìn)行優(yōu)化，有效地提高了定位精度。

2.1近鄰點(diǎn)聯(lián)合測(cè)距修正算法

本文將基于RSSI的測(cè)距序列中距離未知節(jié)點(diǎn)最近的k個(gè)信標(biāo)節(jié)點(diǎn)稱為近鄰k點(diǎn)(Nrtk)，假設(shè)信標(biāo)節(jié)點(diǎn)A1為Nrt1，信標(biāo)節(jié)點(diǎn)A1和A2為Nrt2。

定義1 信標(biāo)節(jié)點(diǎn)Ai與Aj間的測(cè)距誤差因子為ρij，反映兩個(gè)節(jié)點(diǎn)間的測(cè)量距離與真實(shí)距離間的差異,ρij為

(1)

定義2 Nrt1情況下,信標(biāo)節(jié)點(diǎn)Aj到未知節(jié)點(diǎn)的測(cè)距修正系數(shù)為

(2)

式中w1為Nrt1情況下的修正權(quán)重。以Nrt1為重點(diǎn)參考節(jié)點(diǎn)，其余信標(biāo)節(jié)點(diǎn)為一般參考節(jié)點(diǎn)，用φj來(lái)修正未知節(jié)點(diǎn)到第j個(gè)信標(biāo)節(jié)點(diǎn)的距離。

定義3 Nrt2情況下,信標(biāo)節(jié)點(diǎn)Aj到未知節(jié)點(diǎn)的測(cè)距修正系數(shù)為

(3)

式中w2為Nrt2情況下的修正權(quán)重。

從仿真結(jié)果(第3章)看，對(duì)Nrt3及更多的近鄰點(diǎn)，其測(cè)距修正系數(shù)計(jì)算量大、通信能耗增大，且不能帶來(lái)定位精度的提高，因篇幅有限本文重點(diǎn)考慮Nrt1和Nrt2兩種情況。

定義4 未知節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)Aj的測(cè)距修正方程

(4)

通過(guò)式(4)可得到未知節(jié)點(diǎn)到每個(gè)信標(biāo)節(jié)點(diǎn)的修正距離dj。

在節(jié)點(diǎn)定位階段本文采用改進(jìn)的PSO算法來(lái)優(yōu)化定位結(jié)果。PSO算法不僅對(duì)測(cè)量誤差的敏感度非常低，并且能夠快速地找到最優(yōu)解，從而提高定位精度[8]。

2.2基于改進(jìn)的PSO法優(yōu)化定位結(jié)果

PSO的模型是“速度+位置”，在一個(gè)解空間里有大量的粒子，粒子被看成搜索空間中的一個(gè)點(diǎn)，粒子在飛行過(guò)程中，其速度和位置依靠個(gè)體最優(yōu)值pbest和全局最優(yōu)值gbest不斷進(jìn)行更新，進(jìn)而幫助粒子不斷靠近最優(yōu)解處[9]。若在二維搜索空間中，X=[X1,X2,…,Xm]表示由m個(gè)粒子組成的種群，第i個(gè)粒子的坐標(biāo)為Xi=(xi1,xi2)，速度為Vi=(vi1,vi2)，則速度與位置更新公式如下

Vi(t+1)=wVi(t)+c1r1[pbesti-Xi(t)]+

c2r2[gbest-Xi(t)]

(5)

Xi(t+1)=Xi(t)+Vi(t+1)

(6)

式中c1,c2為加速因子，r1,r2為(0,1)區(qū)間呈均勻分布的隨機(jī)數(shù)，w為慣性權(quán)重，Vi(t),Vi(t+1)分別為粒子的當(dāng)前速度和更新后速度，Xi(t),Xi(t+1)分別為粒子當(dāng)前位置和更新后位置。

優(yōu)秀進(jìn)化算法應(yīng)具備早期較好的全局探索能力和后期好的局部開發(fā)能力，PSO算法中慣性權(quán)重w是平衡粒子的全局及局部搜索能力的關(guān)鍵。為避免粒子在全局最優(yōu)解附近出現(xiàn)振蕩現(xiàn)象，做如下改進(jìn)：隨著迭代次數(shù)的增加，慣性權(quán)重w由最大wmax線性減小到最小wmin，這樣就能夠保證優(yōu)化初期w能在較長(zhǎng)時(shí)間段內(nèi)維持較大值，提高全局搜索能力，而優(yōu)化后期提高局部搜索能力。w表示為

(7)

式中t為當(dāng)前迭代次數(shù)，T為最大迭代次數(shù)。

搜索的后期空間中的粒子常會(huì)處于相對(duì)穩(wěn)定的狀態(tài)，減緩了搜索速度，嚴(yán)重影響了粒子收斂最優(yōu)解的速度，從而陷入局部最優(yōu)[10]。當(dāng)?shù)^(guò)程中檢測(cè)到早熟跡象時(shí)對(duì)種群引入一種非一致性變異調(diào)整，過(guò)程如下：

(8)

(9)

式中Δ(t,y)的表達(dá)式為

Δ(t,y)=y×(1-r(1-t/T)λ)

(10)

式中r為[0,1]的隨機(jī)數(shù)，λ是非一致性的程度，取值范圍一般為[2，5]。

該變異調(diào)整機(jī)制能幫助粒子盡快跳出局部最優(yōu)區(qū)域，進(jìn)而有效地減少無(wú)效迭代次數(shù)，提高了算法的搜索和開發(fā)能力。

改進(jìn)PSO算法步驟如下：

1)搜索域內(nèi)隨機(jī)初始化k個(gè)粒子。

2)根據(jù)式(11)計(jì)算各粒子的個(gè)體目標(biāo)函數(shù)值，各粒子的個(gè)體最優(yōu)位置放于自己的pbest中，群體最優(yōu)位置放于gbest中。個(gè)體目標(biāo)函數(shù)為

(11)

式中(xi,yi)為第i個(gè)信標(biāo)節(jié)點(diǎn)坐標(biāo)，(x,y)為個(gè)體粒子坐標(biāo)，f的極小值為要求的定位坐標(biāo)。

3)更新調(diào)整慣性權(quán)重、粒子的速度和位置，若檢測(cè)到有粒子陷入早熟，采用變異調(diào)整機(jī)制。

4)比較每個(gè)粒子個(gè)體最優(yōu)位置、全局最優(yōu)位置，如果當(dāng)前位置優(yōu)于個(gè)體最優(yōu)位置，則其替換為該粒子的個(gè)體最優(yōu)位置；如果當(dāng)前位置優(yōu)于全局最優(yōu)位置，則其替換為粒子群全局最優(yōu)位置。

5) 當(dāng)粒子的個(gè)體目標(biāo)函數(shù)值足夠小或已達(dá)到最大迭代次數(shù)時(shí)，停止更新，最優(yōu)解的位置為未知節(jié)點(diǎn)的估計(jì)位置;否則,返回步驟(2)繼續(xù)更新。

3　算法仿真和分析

本文采用Matlab實(shí)驗(yàn)平臺(tái)進(jìn)行算法仿真實(shí)驗(yàn)。

3.1仿真環(huán)境與參數(shù)設(shè)定

仿真的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)如下：網(wǎng)絡(luò)中的所有節(jié)點(diǎn)都是隨機(jī)生成的，在同一個(gè)的網(wǎng)絡(luò)環(huán)境中進(jìn)行100次仿真實(shí)驗(yàn)，對(duì)實(shí)驗(yàn)結(jié)果取平均值。采用對(duì)數(shù)-常態(tài)分布無(wú)線傳播模型模型計(jì)算RSSI[11]，網(wǎng)絡(luò)參數(shù)如表1所示。

表1　仿真參數(shù)

3.2近鄰點(diǎn)聯(lián)合測(cè)距修正算法的誤差分析

由圖1和圖2可知,在節(jié)點(diǎn)通信半徑小或信標(biāo)節(jié)點(diǎn)個(gè)數(shù)少的情況下，Nrt1測(cè)距修正的平均測(cè)距誤差較低;反之,Nrt2測(cè)距修正的平均測(cè)距誤差較低。為達(dá)到取長(zhǎng)補(bǔ)短的效果，對(duì)測(cè)距修正系數(shù)做進(jìn)一步的平衡改進(jìn)。

圖1　平均測(cè)距誤差與節(jié)點(diǎn)通信半徑Fig 1　Average ranging error and communication radius of node

圖2　平均測(cè)距誤差與信標(biāo)節(jié)點(diǎn)個(gè)數(shù)Fig 2　Average ranging error and beacon node number

通過(guò)聯(lián)合Nrt1和Nrt2兩種測(cè)距修正系數(shù)求和取平均值來(lái)進(jìn)行改進(jìn)，則測(cè)距修正系數(shù)統(tǒng)一為

j>1

(12)

3.3實(shí)驗(yàn)結(jié)果分析

本文與測(cè)距差分修正算法WCLADC[12]和同類型的測(cè)距結(jié)合PSO的定位算法IPSO-IRSSI[8]進(jìn)行比較。

由圖3可以看出:在相同信標(biāo)節(jié)點(diǎn)數(shù)下本文算法的定位誤差明顯小于WCLADC和IPSO-IRSSI算法，在相同定位精度下本文算法需要的信標(biāo)節(jié)點(diǎn)數(shù)最少，可見本文算法更加充分的利用信標(biāo)節(jié)點(diǎn)信息。

圖3　本文算法與其它算法比較Fig 3　Comparison of algorithm of this paper with other algorithms

針對(duì)基于RSSI的測(cè)距會(huì)受環(huán)境影響的問(wèn)題，由圖4可以看出：隨著平均測(cè)距誤差的增大，平均定位誤差也相應(yīng)的增大，但本文算法對(duì)測(cè)距距離進(jìn)行了比WCLADC更合理的修正，有效地降低了測(cè)距誤差的影響，在相同的平均測(cè)距誤差時(shí)本文算法的平均定位誤差比其它算法降低了不少，尤其當(dāng)測(cè)距誤差較大時(shí)，本文算法的抗誤差性更強(qiáng)。本文有效地解決了傳統(tǒng)WCLADC算法測(cè)距修正的的局限性，實(shí)現(xiàn)了更加精準(zhǔn)的修正。

圖4　測(cè)距誤差對(duì)定位誤差的影響Fig 4　Effect of ranging error on positioning error

圖5描述了本文PSO與傳統(tǒng)PSO算法的收斂特性。由該圖可以明顯看出：傳統(tǒng)PSO需要迭代18次才能夠收斂，相比較下，本文PSO收斂速度更快，迭代10次就可以達(dá)到收斂的效果，節(jié)約了能耗。

圖5　本文PSO收斂特性Fig 5　Convergent characteristic of PSO of this paper

4　結(jié)束語(yǔ)

本文從理論原理和實(shí)驗(yàn)基礎(chǔ)對(duì)傳統(tǒng)差分修正算法進(jìn)行了全面的分析，提出了一種近鄰點(diǎn)聯(lián)合測(cè)距修正PSO的定位算法來(lái)提高定位精度。通過(guò)上述仿真結(jié)果分析：本文定位算法沒(méi)有額外的硬件要求和大幅的計(jì)算量，在定位精度等指標(biāo)上比傳統(tǒng)算法提高20 %，說(shuō)明是符合設(shè)計(jì)要求的，對(duì)于節(jié)點(diǎn)隨機(jī)分布的WSNs來(lái)說(shuō)，該算法是一種更好的定位方案。

[1]DengZhongliang，YuYanpei，YuanXie.Situationanddevelopmenttendencyofindoorpositioning[J].ChinaCommunications，2013(3):42-55.

[2]BahlP,PadmanabhanVN.RADAR,aninbuildingonRF-baseduserlocationandtrackingsystem[C]∥IEEEComputerandCommunicationsSocietiesConference,2000:775-784.

[3]胡巧玲，提高基于WLAN的室內(nèi)定位系統(tǒng)的適用性分析[J].華中科技大學(xué)學(xué)報(bào),2013,41(2):197-200.

[4]關(guān)博,東超.立體式RSSI無(wú)線傳感器網(wǎng)絡(luò)定位算法[J].北華大學(xué)學(xué)報(bào):自然科學(xué)版,2013,14(1):112-116.

[5]劉政.基于接收信號(hào)強(qiáng)度指示的誤差自校正定位算法[J].傳感技術(shù)學(xué)報(bào),2014,27(7):970-975.

[6]蔡紹濱，高振國(guó).帶有罰函數(shù)的無(wú)線傳感器網(wǎng)絡(luò)粒子群定位算法[J].計(jì)算機(jī)研究與發(fā)展,2012,49(6):1228-1234.

[7]程偉，史浩山.基于差分修正的傳感器網(wǎng)絡(luò)傳加權(quán)質(zhì)心定位算法[J].系統(tǒng)仿真學(xué)報(bào),2012,24(2):389-393.

[8]馮秀芳，呂淑芳.基于RSSI和分步粒子群算法的無(wú)線傳感器網(wǎng)絡(luò)定位算法[J].控制與決策,2014,29(11):1-7.

[9]KennedyJ,EberhartR.Particleswarmoptimization[C]∥IEEEInternationalConferenceonNeuralNetworks,Perth,1995:1942-1948.

[10] 王亞子，楊建輝.改進(jìn)粒子群算法的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位[J].計(jì)算機(jī)工程與應(yīng)用,2014,50(18):99-102.

[11] 岳菲菲，關(guān)維國(guó)，鄒德君，等.基于RSSI差分修正的WSNs定位算法[J]．遼寧工業(yè)大學(xué)學(xué)報(bào):自然科學(xué)版,2012,3 (6):364-367．

[12] 花超,吉小軍，蔡萍.基于RSSI差分修正的加權(quán)質(zhì)心定位算法[J].傳感器與微系統(tǒng),2012,31(5):139-141.

PSO localization algorithm based on joint ranging modification of neighbor node*

WANG Zhe， LI Ping

(School of Computer and Telecommunications,Changsha University of Science and Technology,Changsha 410114,China)

Aimed at the problem that in the beacon nodes randomly distributed environment,reference node selection by traditional difference correction localization algorithm is too single,which cause that ranging modification coefficient has big error,propose a PSO localization algorithm based on joint ranging modification of neighbor node.The algorithm uses a joint ranging modification algorithm of neighbor node to get the modified distance from the unknown node to each beacon node,and then use an improved PSO algorithm to optimize the positioning result,obtain estimated position of unknown node.Simulation results show that the proposed algorithm has obvious improvement of positioning precision and achieve good stability,compared with traditional positioning algorithm.

wireless sensor networks(WSNs); neighbor node; RSSI; difference correction; particle swarm optimization(PSO)

2015—10—20

湖南省教育廳資助重點(diǎn)項(xiàng)目(14A004)

TP 212

A

1000—9787(2016)08—0130—04

王哲(1989-)，男，湖北黃岡人，碩士研究生，研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)。

DOI:10.13873/J.1000—9787(2016)08—0130—04