接收信號(hào)強(qiáng)度指示測(cè)距模型修正與粒子群算法權(quán)重優(yōu)化的節(jié)點(diǎn)定位算法

任克強(qiáng)， 溫曉珍

(江西理工大學(xué)信息工程學(xué)院， 贛州 341000)

無(wú)線傳感器網(wǎng)絡(luò)(wireless sensor network，WSN)是由大量成本低廉、體積微小、分布密集的傳感器節(jié)點(diǎn)組成的網(wǎng)絡(luò)系統(tǒng)，這些傳感器節(jié)點(diǎn)耗能低，能夠收集特定事件的信息送到監(jiān)測(cè)人員處進(jìn)行進(jìn)一步的處理[1]。WSN由于能獲取客觀的物理信息被廣泛運(yùn)用于軍事、工業(yè)及環(huán)境監(jiān)測(cè)等諸多領(lǐng)域[2]。在實(shí)際的應(yīng)用中，準(zhǔn)確的位置信息在WSN監(jiān)測(cè)活動(dòng)中必不可少，沒有位置信息的監(jiān)測(cè)活動(dòng)無(wú)實(shí)際價(jià)值可言[3]。節(jié)點(diǎn)定位作為WSN中的一項(xiàng)重要應(yīng)用，是監(jiān)測(cè)事件的前提，在定位算法中，通常可分為基于距離和距離無(wú)關(guān)兩大類[4]。質(zhì)心算法、APIT(approximate point-in-triangulation test)和DV-Hop(distance vector-hop)等是較常用的距離無(wú)關(guān)的定位算法[5-6]，無(wú)需實(shí)際測(cè)量節(jié)點(diǎn)間距離，硬件開銷較小。相較于距離無(wú)關(guān)的算法，基于距離的定位算法可實(shí)現(xiàn)更高的精度[7-8]。

接收信號(hào)強(qiáng)度指示(received signal strength indicator，RSSI)作為一種較為常用的距離估計(jì)方法，因其較低的設(shè)備部署開銷，在WSN的定位算法中得到了廣泛的應(yīng)用與研究[9]。然而RSSI測(cè)距具有一定的局限性，易受環(huán)境干擾，影響定位的準(zhǔn)確性。在一些文獻(xiàn)中，定位問題視作是一個(gè)非線性無(wú)約束的優(yōu)化問題。粒子群算法(particle swarm optimization, PSO)因其參數(shù)少、計(jì)算簡(jiǎn)便、收斂快速等優(yōu)點(diǎn)受到相關(guān)學(xué)者關(guān)注，以離散粒子群算法(DPSO)為基礎(chǔ)，一些相關(guān)改進(jìn)算法相繼被提出。在粒子群算法中，當(dāng)搜索空間較大時(shí)，自適應(yīng)差的權(quán)重難以在搜索速度和搜索精度之間達(dá)到平衡，因此中外學(xué)者提出了相應(yīng)的改進(jìn)策略。文獻(xiàn)[10]提出一種基于粒子群優(yōu)化的自定位算法，該算法將學(xué)習(xí)因子設(shè)置為線性遞減模式，利用分量變異法跳出自定位搜索停滯時(shí)的局部最優(yōu)，該方法雖然提高了定位性能，但計(jì)算復(fù)雜度也顯著提高。文獻(xiàn)[11]提出一種貝葉斯概率模型，提高了RSSI測(cè)量的精度，但在復(fù)雜的實(shí)際環(huán)境中，所選模型的經(jīng)驗(yàn)參數(shù)作用不大。文獻(xiàn)[12]提出一種基于混合粒子群優(yōu)化算法的室內(nèi)和室外軌道自行車無(wú)線傳感器精確定位技術(shù)，利用對(duì)數(shù)正態(tài)陰影模型進(jìn)行參數(shù)估計(jì)并測(cè)距，然后結(jié)合混合粒子群優(yōu)化-人工神經(jīng)網(wǎng)絡(luò)(PSO-ANN)算法降低測(cè)距誤差，與傳統(tǒng)對(duì)數(shù)正態(tài)陰影模型相比，定位準(zhǔn)確度更高。文獻(xiàn)[13]提出一種基于節(jié)點(diǎn)間測(cè)距的改進(jìn)PSO算法，該算法在基本PSO算法中引入了動(dòng)態(tài)干擾因子和罰函數(shù)，提高了算法的收斂性，避免了在無(wú)效的搜索空間中耗費(fèi)時(shí)間。文獻(xiàn)[14]提出一種優(yōu)化罰函數(shù)的改進(jìn)粒子群定位算法，根據(jù)種群密度改變懲罰因子用于提升收斂速度，然后對(duì)誤差進(jìn)行加權(quán)處理，進(jìn)一步提高定位算法準(zhǔn)確度。文獻(xiàn)[15]提出一種自適應(yīng)優(yōu)化粒子群算法，根據(jù)適應(yīng)度函數(shù)確定的粒子適應(yīng)值調(diào)節(jié)慣性權(quán)重與學(xué)習(xí)因子的取值，并用異步變化法改進(jìn)學(xué)習(xí)因子，但該算法難以跳出局部極值點(diǎn)，較難改善測(cè)試點(diǎn)定位精度。

針對(duì)復(fù)雜環(huán)境下RSSI波動(dòng)較大及標(biāo)準(zhǔn)PSO算法易陷入局部極值點(diǎn)的問題，采用兩種優(yōu)化策略對(duì)定位算法進(jìn)行改進(jìn)：一是考慮RSSI測(cè)距誤差易積累至定位階段，利用最小化誤差平方和原則，修正RSSI的模型參數(shù)；二在PSO算法中引入非線性慣性權(quán)重，平衡算法的全局與局部探索能力，減少尋優(yōu)過(guò)程中的不必要消耗，防止算法收斂于局部極值點(diǎn)，實(shí)現(xiàn)定位性能的優(yōu)化。

1 RSSI定位及誤差分析

1.1 RSSI定位

基于接收信號(hào)強(qiáng)度指示(RSSI)的測(cè)距理論為：依據(jù)無(wú)線電波或聲波在介質(zhì)中傳播，信號(hào)功率隨距離衰減的原理，將信號(hào)的損耗通過(guò)衰減模型轉(zhuǎn)變成距離，一般分成經(jīng)驗(yàn)?zāi)Ｐ秃屠碚撃Ｐ蛢深怺16]。

(1)信號(hào)傳播的經(jīng)驗(yàn)?zāi)Ｐ汀Ｊ紫仍O(shè)置一個(gè)關(guān)聯(lián)數(shù)據(jù)庫(kù)，錄入并存放測(cè)試點(diǎn)的信號(hào)強(qiáng)度和它們對(duì)應(yīng)的坐標(biāo)(x,y,s1,s2,s3)，然后在定位時(shí)，將測(cè)試點(diǎn)所測(cè)得的信號(hào)強(qiáng)度(s′1,s′2,s′3)與之前數(shù)據(jù)庫(kù)中保存的記錄值進(jìn)行對(duì)比，所測(cè)信號(hào)強(qiáng)度與數(shù)據(jù)庫(kù)記錄值之間的均方差sqrt[(s1-s′1)2+(s2-s′2)2+(s3-s′3)2]最小的點(diǎn)即為所求未知節(jié)點(diǎn)的坐標(biāo)，可進(jìn)行多次測(cè)量以減小誤差。

(2)信號(hào)傳播的理論模型?？紤]實(shí)際復(fù)雜環(huán)境對(duì)信號(hào)傳輸?shù)母蓴_，確定信號(hào)衰減與傳輸距離間的關(guān)系式，根據(jù)測(cè)量的信號(hào)強(qiáng)度，利用對(duì)數(shù)正態(tài)陰影模型(log-normal shadowing model，LNSM)計(jì)算未知節(jié)點(diǎn)與發(fā)射節(jié)點(diǎn)間的距離：

(1)

式(1)中：pd為傳輸距離d的信號(hào)強(qiáng)度；pd0為傳輸距離d0的信號(hào)強(qiáng)度；n為路徑損耗指數(shù)；d0為參考距離，取d0=1 m；Xσ為均值是0的高斯隨機(jī)變量。

1.2 RSSI測(cè)距存在的問題

在基于RSSI的定位中，通常選用對(duì)數(shù)正態(tài)陰影模型來(lái)描述信號(hào)強(qiáng)度與節(jié)點(diǎn)距離的關(guān)系，但由于實(shí)際應(yīng)用中外在因素的影響，信號(hào)強(qiáng)度與節(jié)點(diǎn)距離之間并沒有明確的對(duì)應(yīng)關(guān)系，這使得基于測(cè)距的RSSI定位算法存在一定的局限性[17]。RSSI測(cè)距過(guò)程受環(huán)境影響較大，理論上信號(hào)強(qiáng)度值進(jìn)行有規(guī)律的變化，距離增大，強(qiáng)度值不斷衰減，而事實(shí)上由于存在溫度、反射及障礙物的干擾，這些環(huán)境的不穩(wěn)定因素會(huì)導(dǎo)致獲取的信號(hào)強(qiáng)度值波動(dòng)較大，隨著環(huán)境的改變，信號(hào)強(qiáng)度測(cè)量的不穩(wěn)定性增大，所得測(cè)量值的準(zhǔn)確度隨之降低。若針對(duì)不同的實(shí)際特定環(huán)境仍選用傳統(tǒng)模型，而不考慮環(huán)境干擾，則易造成測(cè)距誤差。

因此，在原有的對(duì)數(shù)正態(tài)陰影模型基礎(chǔ)上，針對(duì)環(huán)境變化時(shí)RSSI理論測(cè)距模型導(dǎo)致的定位精度不高的問題，對(duì)測(cè)距的模型參數(shù)進(jìn)行修正，可有效改善以上問題，減小定位誤差，提高定位精度。

2 粒子群算法分析

2.1 PSO算法原理

粒子群算法是一種啟發(fā)式的優(yōu)化技術(shù)[18]。因參數(shù)少、收斂快、計(jì)算簡(jiǎn)便而被廣泛應(yīng)用。該算法依靠粒子間相互傳遞信息來(lái)改變自身的飛行狀態(tài)，能夠產(chǎn)生自組織行為從而進(jìn)行快速有效的收斂。標(biāo)準(zhǔn)PSO算法種群中的每個(gè)成員被量化為一個(gè)粒子，粒子的速度根據(jù)本身的歷史信息以及群體的共享信息進(jìn)行動(dòng)態(tài)地調(diào)整。在n維空間中，第i個(gè)粒子的位置和速度分別描述為xi=(xi,1,xi,2,…,xi,n)、v=(vi,1,vi,2,…,vi,n)，粒子個(gè)體與粒子種群所經(jīng)歷的歷史最佳位置分別描述為pbi=(pi,1,pi,2,…,pi,n)、gb=(g1,g2,…,gn)。PSO算法是一種基于迭代的優(yōu)化技術(shù)，在二維搜索范圍中，第t+1次搜索時(shí)粒子將由pb、gb和擾動(dòng)產(chǎn)生新的飛行速度和位置，其更新公式分別為

(2)

(3)

式中：w為慣性權(quán)重；c1、c2為學(xué)習(xí)因子；r1、r2為服從均勻分布的隨機(jī)數(shù)，取值范圍為0～1。

2.2 PSO算法存在的問題

目前，粒子群算法面臨的一個(gè)主要問題是算法在進(jìn)行優(yōu)化定位的過(guò)程中不能有效實(shí)現(xiàn)對(duì)目標(biāo)空間的全局搜索，對(duì)于有多個(gè)局部極值點(diǎn)的函數(shù)，容易導(dǎo)致算法陷入這些點(diǎn)中，得不到正確的結(jié)果，從而降低算法的優(yōu)化性能。在標(biāo)準(zhǔn)PSO算法中，最優(yōu)粒子的位置信息向其他成員進(jìn)行分享，強(qiáng)調(diào)了一個(gè)共同最優(yōu)信息的處理，而忽略了個(gè)體間信息的傳遞。隨著迭代的進(jìn)行，種群中每個(gè)成員間的距離逐漸縮小，粒子急速收斂到所獲得的最優(yōu)位置處，造成算法早熟失效。如何引入相應(yīng)策略處理這類問題，將是提高算法適應(yīng)性的關(guān)鍵。

針對(duì)以上RSSI在復(fù)雜環(huán)境中測(cè)距誤差較大及標(biāo)準(zhǔn)PSO算法易陷入局部最優(yōu)的問題，利用不同參考點(diǎn)的差值對(duì)RSSI測(cè)距模型的參數(shù)進(jìn)行修正，并對(duì)粒子群算法的權(quán)重進(jìn)行非線性化，提出一種RSSI測(cè)距模型修正及PSO權(quán)重優(yōu)化的定位算法。

3 本文算法

3.1 LNSM參數(shù)估計(jì)及修正

基于RSSI測(cè)距的定位方法往往受到環(huán)境因素的影響，如果在不同環(huán)境中仍按照給定的經(jīng)驗(yàn)值設(shè)置傳播模型參數(shù)，節(jié)點(diǎn)間距離越大，誤差越大。對(duì)數(shù)正態(tài)陰影模型的理想曲線在距離較小時(shí)接近實(shí)際測(cè)量的RSSI值，在距離較遠(yuǎn)時(shí)，由于穿透損失和阻塞效應(yīng)，RSSI的測(cè)量值通常比LNSM所對(duì)應(yīng)的理想值更小。因此，通過(guò)對(duì)測(cè)距模型參數(shù)進(jìn)行修正，來(lái)減小環(huán)境因素對(duì)測(cè)距誤差的影響。

在本文算法中，L個(gè)參考點(diǎn)的RSSI值是在已知坐標(biāo)的m個(gè)測(cè)試點(diǎn)上測(cè)量的，式(1)的可測(cè)量pd設(shè)為Y，已知量-10lgd設(shè)為x，傳播模型參數(shù)pd0和n分別設(shè)為a和b，則測(cè)距模型可擬合為

Y=a+bX+Xσ

(4)

LNSM的參數(shù)估計(jì)是基于最大限度地最小化誤差平方和原則，使得所擬合的函數(shù)值與實(shí)際測(cè)量數(shù)據(jù)之間的誤差最小化：

(5)

要使每個(gè)偏差都盡可能小，可令R最小來(lái)實(shí)現(xiàn)，即求函數(shù)R=R(a,b)在所測(cè)數(shù)據(jù)處取得最小值。

(6)

由此計(jì)算出a、b的表達(dá)式為

(7)

考慮L個(gè)不同參考節(jié)點(diǎn)之間的差異，修正公式(1)中的傳播模型參數(shù)pd0和n為

(8)

根據(jù)LNSM參數(shù)估計(jì)，確定了本文算法的RSSI測(cè)距模型參數(shù)，利用RSSI修正模型進(jìn)行測(cè)距，得出信標(biāo)與未知節(jié)點(diǎn)之間的距離。

假設(shè)A、B和C3個(gè)信標(biāo)節(jié)點(diǎn)的坐標(biāo)分別為(xa,ya)、(xb,yb)和(xc,yc)，以及它們到未知節(jié)點(diǎn)D(x,y)的距離為da、db和dc，則可通過(guò)三邊測(cè)量法來(lái)求出(x,y)的取值：

(9)

由此可得出未知節(jié)點(diǎn)D的坐標(biāo)為

(10)

3.2 非線性遞減權(quán)重優(yōu)化

慣性權(quán)重w的取值大小對(duì)PSO算法的尋優(yōu)過(guò)程起著關(guān)鍵的控制作用，粒子飛行速度的升降依賴于權(quán)重的取值。若給定較高的w，粒子可提速向更大范圍尋找最優(yōu)目標(biāo)，使粒子群體得到發(fā)散，加快算法運(yùn)行的速度，有利于在前期搜索中探測(cè)最優(yōu)目標(biāo)所在的區(qū)域。但若整個(gè)迭代過(guò)程均賦予較高的w值，粒子飛行速度過(guò)快，極易飛越過(guò)所尋找的目標(biāo)，不利于在后期靠近目標(biāo)時(shí)，降低速度進(jìn)行細(xì)致的探索。由此可見，w參數(shù)大小的取值十分關(guān)鍵。目前，采用較多的經(jīng)典線性遞減慣性權(quán)重為

w(k)=wmax-k(wmax-wmin)/Tmax

(11)

式(11)中：wmax、wmin分別為慣性權(quán)重的最高與最低值；Tmax為最大迭代次數(shù)。

線性遞減權(quán)重難以避免帶來(lái)一些問題，粒子在后期搜索中與最優(yōu)目標(biāo)的距離逐漸縮小，需賦予持續(xù)較小的慣性權(quán)重值w來(lái)減緩粒子的飛行速度，使粒子不斷靠近最優(yōu)目標(biāo)所在位置，而線性遞減權(quán)重的下降趨勢(shì)過(guò)于陡峭，粒子容易飛越過(guò)最優(yōu)解。

(12)

式(12)中：wmax、wmin為慣性權(quán)重的最高與最低值，取wmax=0.9、wmin=0.4；t為當(dāng)前迭代次數(shù)；Tmax為最大迭代次數(shù)；λ為收斂因子，當(dāng)λ取值較大時(shí)，粒子速度減小，有助于粒子的探索在極值點(diǎn)附近進(jìn)行；當(dāng)λ取值較小，慣性權(quán)重值增大，粒子速度加快，能夠擴(kuò)大搜索范圍。當(dāng)?shù)螖?shù)t=0時(shí)，函數(shù)值為初始權(quán)重值wmax=0.9，隨著搜索的進(jìn)行，權(quán)重值呈非線性遞減趨勢(shì)，當(dāng)達(dá)到最大迭代次數(shù)Tmax時(shí)，權(quán)重降為0.4，有利于局部搜索。本文所提出的非線性遞減權(quán)重策略符合尋優(yōu)過(guò)程，具有較理想的尋優(yōu)性能。

已知未知節(jié)點(diǎn)D(x,y)周圍有N個(gè)信標(biāo)節(jié)點(diǎn)，第q個(gè)信標(biāo)節(jié)點(diǎn)坐標(biāo)為(xq,yq)，本文優(yōu)化粒子群算法的適應(yīng)度函數(shù)取為

(13)

4 仿真結(jié)果與分析

為測(cè)試本文定位算法的性能，采用MATLAB R2016b仿真平臺(tái)對(duì)本文定位算法的測(cè)距模型參數(shù)pd0和n進(jìn)行確定；分析不同的慣性權(quán)重對(duì)算法的影響；并從測(cè)距誤差、信標(biāo)節(jié)點(diǎn)密度、迭代次數(shù)3個(gè)方面對(duì)DPSO算法、文獻(xiàn)[14]的PSOAPF算法和本文算法的性能進(jìn)行仿真實(shí)驗(yàn)對(duì)比。仿真的空間取100 m×100 m的二維區(qū)域，節(jié)點(diǎn)總數(shù)為100，信標(biāo)節(jié)點(diǎn)占30%，通信半徑為R=30 m，粒子群各參數(shù)設(shè)為M=30，c1=1.5，c2=1.2，各實(shí)驗(yàn)分別進(jìn)行100次測(cè)試，結(jié)果取平均值。

以節(jié)點(diǎn)平均定位誤差Eave作為算法的評(píng)價(jià)標(biāo)準(zhǔn)：

(14)

首先通過(guò)實(shí)驗(yàn)建立RSSI的測(cè)距模型，在本文實(shí)驗(yàn)環(huán)境中，在距離為di=0.2i(i=1,2,…,50)的4個(gè)參考點(diǎn)和40個(gè)測(cè)試點(diǎn)間對(duì)RSSI值測(cè)量100次，得到各個(gè)間距di處的RSSI值，取測(cè)試的平均值與di進(jìn)行擬合，得出校正的pd0值和n值，圖1為通過(guò)MATLAB平臺(tái)得到的擬合曲線。

圖1 RSSI測(cè)試值的擬合曲線Fig.1 The fitting curve of the RSSI test value

在實(shí)驗(yàn)測(cè)試中，RSSI測(cè)距模型參數(shù)修正為pd0=-37.02；n=2.04。如果干擾因素發(fā)生改變，可重新調(diào)整參數(shù)值。

圖2為迭代過(guò)程中兩種慣性權(quán)重取值大小的變化情況，wa為線性權(quán)重，wb為本文提出的非線性權(quán)重。

圖2 慣性權(quán)重的變化比較Fig.2 Comparison of performance changes of w

由圖2可見，隨著迭代的進(jìn)行，兩種慣性權(quán)重值均不斷降低，在迭代次數(shù)0≤t≤15時(shí)，wb的下降速度大于wa，隨著搜索的進(jìn)行，迭代后期wb曲線逐漸趨向水平，在15

圖3通過(guò)仿真實(shí)驗(yàn)測(cè)試在信標(biāo)節(jié)點(diǎn)密度為15%時(shí)，測(cè)距誤差變化情形下DPSO算法、文獻(xiàn)[14]的PSOAPF算法及本文算法的平均定位誤差情況。

圖3 測(cè)距誤差與平均定位誤差的關(guān)系Fig.3 The relationship between the ranging error and the mean positioning error

由圖3可見，測(cè)距誤差越大，3種算法的平均定位誤差也越大，表明測(cè)距誤差的積累容易對(duì)定位階段產(chǎn)生不利影響。其中，DPSO算法的整體平均定位誤差最大，PSOAPF算法次之，本文算法的平均定位誤差最低。在測(cè)距階段產(chǎn)生20%的誤差時(shí)，實(shí)驗(yàn)得出DPSO與PSOAPF兩種算法的平均定位誤差為31.3%和26.2%，而本文算法低至19.8%，在相同測(cè)距誤差下，本文算法的平均定位誤差低于DPSO算法與PSOAPF算法，定位性能更佳。

圖4通過(guò)仿真實(shí)驗(yàn)比較DPSO算法、文獻(xiàn)[14]的PSOAPF算法以及本文算法在不同的信標(biāo)節(jié)點(diǎn)密度下的性能表現(xiàn)。

圖4 不同信標(biāo)節(jié)點(diǎn)密度的平均定位誤差Fig.4 Mean positioning error of different beacon node density

圖4表明，3種算法在仿真空間信標(biāo)節(jié)點(diǎn)數(shù)目越多時(shí)，所獲未知節(jié)點(diǎn)的信息越全面，定位越精確。其中，當(dāng)控制仿真區(qū)域內(nèi)信標(biāo)節(jié)點(diǎn)占比為14%時(shí)，DPSO的平均定位誤差最高，達(dá)到28.01%，相比之下，PSOAPF和本文算法的平均定位誤差值下降明顯，分別為23.3%和20.01%。由此可知，DPSO算法的平均定位誤差雖有下降趨勢(shì)，但誤差值整體較高，效果最差；PSOAPF算法次之，本文算法的平均定位誤差最小，表現(xiàn)的性能最好。

圖5表示在不同迭代次數(shù)下，當(dāng)測(cè)距誤差為20%時(shí)，DPSO算法、文獻(xiàn)[14]的PSOAPF算法以及本文算法的適應(yīng)值比較情況。由圖5可見，迭代至10～20次時(shí)，3種算法相繼收斂。其中DPSO算法的收斂性能最差，在迭代約18次才趨于收斂，PSOAPF算法則在迭代約12次適應(yīng)度值曲線就呈水平狀態(tài)，出現(xiàn)收斂趨勢(shì)，比DPSO算法收斂性能更良好，而本文算法在迭代大約10次則迅速收斂，在3種算法中收斂性能最優(yōu)。

圖5 不同迭代次數(shù)的適應(yīng)度比較Fig.5 Fitness comparison of different iterations

5 結(jié)論

提出一種融合RSSI測(cè)距模型參數(shù)修正與PSO權(quán)重優(yōu)化的改進(jìn)定位算法，采用不同參考點(diǎn)的差值對(duì)RSSI測(cè)距模型的參數(shù)進(jìn)行修正以及對(duì)粒子群算法的權(quán)重進(jìn)行非線性化兩種策略來(lái)提升改善算法性能。為了測(cè)試驗(yàn)證本文改進(jìn)策略的成效，在不同條件下對(duì)算法進(jìn)行了仿真測(cè)試比較。仿真結(jié)果顯示，在硬件條件不變的情況下，本文定位算法的表現(xiàn)優(yōu)于DPSO算法與PSOAPF算法，具有更好的收斂性能及更高的節(jié)點(diǎn)定位精度。如何進(jìn)一步改善提升算法的性能，是后期要重點(diǎn)研究的工作。