王　哲， 李　平

(長沙理工大學 計算機與通信工程學院，湖南 長沙 410114)

?

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

王哲， 李平

(長沙理工大學 計算機與通信工程學院，湖南 長沙 410114)

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

無線傳感器網(wǎng)絡； 近鄰點; 接收信號強度指示； 差分修正； 粒子群優(yōu)化

0　引　言

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

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

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

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

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

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

2　算法的改進與實現(xiàn)

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

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

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

定義1 信標節(jié)點Ai與Aj間的測距誤差因子為ρij，反映兩個節(jié)點間的測量距離與真實距離間的差異,ρij為

(1)

定義2 Nrt1情況下,信標節(jié)點Aj到未知節(jié)點的測距修正系數(shù)為

(2)

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

定義3 Nrt2情況下,信標節(jié)點Aj到未知節(jié)點的測距修正系數(shù)為

(3)

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

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

定義4 未知節(jié)點到信標節(jié)點Aj的測距修正方程

(4)

通過式(4)可得到未知節(jié)點到每個信標節(jié)點的修正距離dj。

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

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

PSO的模型是“速度+位置”，在一個解空間里有大量的粒子，粒子被看成搜索空間中的一個點，粒子在飛行過程中，其速度和位置依靠個體最優(yōu)值pbest和全局最優(yōu)值gbest不斷進行更新，進而幫助粒子不斷靠近最優(yōu)解處[9]。若在二維搜索空間中，X=[X1,X2,…,Xm]表示由m個粒子組成的種群，第i個粒子的坐標為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ū)間呈均勻分布的隨機數(shù)，w為慣性權(quán)重，Vi(t),Vi(t+1)分別為粒子的當前速度和更新后速度，Xi(t),Xi(t+1)分別為粒子當前位置和更新后位置。

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

(7)

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

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

(8)

(9)

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

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

(10)

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

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

改進PSO算法步驟如下：

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

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

(11)

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

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

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

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

3　算法仿真和分析

本文采用Matlab實驗平臺進行算法仿真實驗。

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

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

表1　仿真參數(shù)

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

由圖1和圖2可知,在節(jié)點通信半徑小或信標節(jié)點個數(shù)少的情況下，Nrt1測距修正的平均測距誤差較低;反之,Nrt2測距修正的平均測距誤差較低。為達到取長補短的效果，對測距修正系數(shù)做進一步的平衡改進。

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

圖2　平均測距誤差與信標節(jié)點個數(shù)Fig 2　Average ranging error and beacon node number

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

j>1

(12)

3.3實驗結(jié)果分析

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

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

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

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

圖4　測距誤差對定位誤差的影響Fig 4　Effect of ranging error on positioning error

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

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

4　結(jié)束語

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

[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].華中科技大學學報,2013,41(2):197-200.

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

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

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

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

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

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

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

[11] 岳菲菲，關(guān)維國，鄒德君，等.基于RSSI差分修正的WSNs定位算法[J]．遼寧工業(yè)大學學報:自然科學版,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

湖南省教育廳資助重點項目(14A004)

TP 212

A

1000—9787(2016)08—0130—04

王哲(1989-)，男，湖北黃岡人，碩士研究生，研究方向為無線傳感器網(wǎng)絡。

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