基于距離優(yōu)化和改進(jìn)粒子群的節(jié)點(diǎn)定位算法

張 溪，毛永毅，徐 萍

(1.西安郵電大學(xué) 電子工程學(xué)院，陜西 西安 710061；2.火箭軍工程大學(xué) 理學(xué)院，陜西 西安 710025)

0 引 言

在無(wú)線傳感器網(wǎng)絡(luò)定位技術(shù)的兩大分類中，基于測(cè)距的定位算法需要額外的硬件支持才能獲取所需信息，而無(wú)需測(cè)距的定位算法依賴于網(wǎng)絡(luò)間的連通和跳數(shù)值信息，其設(shè)備簡(jiǎn)單、功耗低、效率高[1-3]。

DV-Hop算法作為一種易實(shí)現(xiàn)的典型無(wú)需測(cè)距算法被廣泛應(yīng)用于無(wú)線傳感網(wǎng)絡(luò)定位中[4]，對(duì)于該算法定位精度不高這一問(wèn)題，學(xué)者們不斷探索并嘗試改進(jìn)。文獻(xiàn)[5]用高斯牛頓法替代定位階段的最小二乘法，減少誤差傳播。文獻(xiàn)[6]利用跳距誤差和估計(jì)距離誤差的加權(quán)平均值去修正平均跳距，并引入改進(jìn)粒子群算法計(jì)算未知節(jié)點(diǎn)坐標(biāo)。文獻(xiàn)[7]中對(duì)來(lái)自多個(gè)錨節(jié)點(diǎn)的跳數(shù)值進(jìn)行加權(quán)操作用于平均跳距離的估計(jì)。文獻(xiàn)[8]使用節(jié)點(diǎn)間最小跳數(shù)值和錨節(jié)點(diǎn)的位置信息，通過(guò)細(xì)菌覓食優(yōu)化算法計(jì)算平均距離，使跳距誤差盡可能小。

各類改進(jìn)算法的側(cè)重點(diǎn)在于減小估計(jì)距離誤差和盡可能避免定位階段誤差的累積。因此，本文算法通過(guò)對(duì)節(jié)點(diǎn)間距離的優(yōu)化和改進(jìn)的自適應(yīng)粒子群算法對(duì)DV-Hop算法進(jìn)行改進(jìn)，仿真結(jié)果表明，本文DPDV-Hop算法較原始DV-Hop算法和文獻(xiàn)[6]中的BDV-Hop算法在定位精度方面有更優(yōu)異的表現(xiàn)。

1 DPDV-Hop算法

1.1 估計(jì)距離優(yōu)化

節(jié)點(diǎn)間估計(jì)距離是由平均跳距與跳數(shù)值的乘積所決定的，因此平均跳距的誤差將直接影響估計(jì)距離的精確度。為了能使估計(jì)距離的誤差減小，利用錨節(jié)點(diǎn)間單跳平均誤差對(duì)平均跳距進(jìn)行修正，使之接近真實(shí)值。估計(jì)距離的最終結(jié)果與平均跳距的選取方式存在一定關(guān)系，接收網(wǎng)通范圍內(nèi)所有錨節(jié)點(diǎn)平均跳距并參與運(yùn)算的策略，能考慮全局信息使估計(jì)距離得以優(yōu)化。

1.1.1 平均跳距修正

(1)

(2)

(3)

錨節(jié)點(diǎn)i的單跳平均誤差可由式(4)計(jì)算得出，其中n為錨節(jié)點(diǎn)個(gè)數(shù)

(4)

(5)

1.1.2 多錨節(jié)點(diǎn)平均跳距估計(jì)距離

在估計(jì)節(jié)點(diǎn)間距離階段，DV-Hop算法中待求未知節(jié)點(diǎn)根據(jù)就近原則只接收錨節(jié)點(diǎn)傳遞過(guò)來(lái)的第一個(gè)平均跳距信息。然而網(wǎng)絡(luò)分布是具有隨機(jī)性的，數(shù)據(jù)的單一選擇不可避免的增加了偶然性，以至于影響后期定位。盡可能多地使用網(wǎng)絡(luò)中信息即求到哪一點(diǎn)的估計(jì)距離用該點(diǎn)的平均跳距，不僅能考慮到全局信息而且在一定程度上降低了偶然性，使定位精度有所改善。

圖1 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

各節(jié)點(diǎn)平均跳距

HopSizeA=(25+20)/(3+4)≈6.428 mHopSizeB=(25+42)/(3+5)≈8.375 mHopSizeC=(20+42)/(4+5)≈6.888 m

使用各節(jié)點(diǎn)平均跳距通過(guò)不同策略估算節(jié)點(diǎn)間距離，結(jié)果見表1。

表1 節(jié)點(diǎn)間實(shí)際距離與估計(jì)距離

觀察表1發(fā)現(xiàn)，提出策略能使估計(jì)距離更接近真實(shí)值。

1.2 改進(jìn)的粒子群算法MI-PSO

1.2.1 粒子群優(yōu)化算法

粒子群優(yōu)化(particle swarm optimization，PSO)算法被Kennedy和Eberhart提出[9]。作為一種基于人口的元啟發(fā)式搜索算法，它模擬了鳥類和魚類在尋找食物方面的協(xié)作行為[10]。PSO算法中的每個(gè)人(即粒子)表示優(yōu)化問(wèn)題的潛在解決方案，而食物源的位置就是全局最優(yōu)解。每個(gè)粒子相互獨(dú)立并隨機(jī)的尋找食物，它們之間還彼此協(xié)作和共享信息，通過(guò)不斷地搜索尋求問(wèn)題的最優(yōu)解。

若目標(biāo)搜索空間為D維，初始粒子數(shù)量為N，則粒子位置矢量可表示為Si=(si1,si2,…siN)，i=1,2,…,N， 粒子速度矢量可表示為Vi=(vi1,vi2,…viD)。 第i顆粒子現(xiàn)階段所處的最優(yōu)位置可表示為pi=(pi1,pi2,…,piN)， 整個(gè)種群的最優(yōu)位置可表示為pg=(pg1,pg2,…,pgN)。 在每一輪的更新中，粒子對(duì)比這兩個(gè)極值來(lái)改變自己的位置和速度，如式(6)所示

(6)

式中：k為粒子當(dāng)前迭代次數(shù)；ω為慣性權(quán)重；c1、c2為加速度常數(shù)；r1、r2為(0，1)內(nèi)的隨機(jī)常數(shù)。

1.2.2 基于成功率PS的自適應(yīng)慣性權(quán)重策略

通常式(6)中的慣性權(quán)重ω為一常數(shù)，ω越大則越利于全局尋優(yōu)值，ω越小則越利于局部尋優(yōu)值。為兼顧全局和局部尋優(yōu)，提出自適應(yīng)慣性權(quán)重策略。

實(shí)現(xiàn)自適應(yīng)權(quán)重策略的重要之處在于每次迭代完成時(shí)需合理評(píng)估群體的位置。而本文提出的粒子成功率PS能表現(xiàn)群體現(xiàn)狀，較高的PS值表示粒子向最佳解決方案靠近，并處于收斂狀態(tài)，而較低的PS值意味著粒子在沒(méi)有很大改進(jìn)的情況下徘徊于最佳解決方案附近。因此，將粒子的成功率PS用于自適應(yīng)地更新速度能有效提升收斂速度。使用粒子面向最佳解決方案的成功計(jì)數(shù)SC來(lái)確定PS的值。若當(dāng)前迭代的適應(yīng)度小于前一次迭代的適應(yīng)度，則將SC值設(shè)置為1，否則將其設(shè)置為0，如式(7)所示

(7)

將所有的SC計(jì)數(shù)累加求和并由式(8)計(jì)算出成功率PS，其中N表示粒子數(shù)量

(8)

自適應(yīng)慣性權(quán)重因子ω的設(shè)置如式(9)所示，粒子根據(jù)百分比形式的成功率自適應(yīng)地更新慣性權(quán)重

ω=(ωmax-ωmin)×PS+ωmin

(9)

慣性權(quán)重(ωminωmax)的范圍被設(shè)為[0，1]。因?yàn)镻S為成功率，它的值總是在0～1之間，這就使慣性重量在可接受范圍內(nèi)。

1.2.3 變異算子參與運(yùn)算策略

在PSO算法的執(zhí)行過(guò)程中，粒子總是向最優(yōu)解靠攏。若這一最優(yōu)解為局部最優(yōu)解，隨著粒子的逐漸聚集，粒子便難以趨近于全局最優(yōu)解，導(dǎo)致過(guò)早收斂即早熟現(xiàn)象[11]。

(10)

1.2.4 適應(yīng)度函數(shù)設(shè)置

盡管在文章1.1節(jié)對(duì)節(jié)點(diǎn)間估計(jì)距離有所優(yōu)化，但其誤差并沒(méi)有完全消除，考慮到估計(jì)距離所攜帶的誤差，得到式(11)，其中εi,i=1,2,…n表示距離誤差

(11)

(12)

通過(guò)多次迭代使fitness(x,y)的值最小，以提升定位精度。

2 DPDV-Hop算法流程

步驟1 錨節(jié)點(diǎn)利用洪泛機(jī)制向全網(wǎng)廣播自身信息，根據(jù)錨節(jié)點(diǎn)所獲取的位置信息和最小跳數(shù)值計(jì)算平均跳距。

步驟4 若粒子si的變異概率Pc>rand(0～1)， 則執(zhí)行步驟5，否則執(zhí)行步驟6。

步驟6 比較更新后各粒子本次與上次的適應(yīng)度值，由式(7)、式(8)計(jì)算成功率PS并帶入式(9)中更新權(quán)重ω。記錄本次迭代的個(gè)體最優(yōu)位置pi和歷史最優(yōu)位置pg。

步驟7 將步驟6計(jì)算出的權(quán)重帶入式(6)，用于對(duì)速度和位置的更新。

重復(fù)步驟4～步驟7直到達(dá)到最大迭代次數(shù)，輸出最優(yōu)適應(yīng)度值及對(duì)應(yīng)的粒子位置。

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

為了驗(yàn)證改進(jìn)算法的性能，在Windows7的MATLAB R2014a環(huán)境下進(jìn)行仿真實(shí)驗(yàn)。將擁有相同通信半徑的100個(gè)節(jié)點(diǎn)隨機(jī)分布在邊長(zhǎng)為100 m的二維方形區(qū)域內(nèi)，如圖2所示，其中○代表未知節(jié)點(diǎn)，*代表錨節(jié)點(diǎn)。初始化粒子個(gè)數(shù)N為30，最大迭代次數(shù)itmax為100。

圖2 節(jié)點(diǎn)分布

采用歸一化相對(duì)誤差作為性能評(píng)價(jià)指標(biāo)，如式(13)所示

(13)

式中：(xr,yr)表示未知節(jié)點(diǎn)的真實(shí)坐標(biāo)，(xi,yi)表示未知節(jié)點(diǎn)的估計(jì)坐標(biāo)，R表示節(jié)點(diǎn)的通信半徑，N表示未知節(jié)點(diǎn)數(shù)。

就DPDV-Hop算法本身而言，在對(duì)距離優(yōu)化的同時(shí)也利用I-PSO算法替代了定位階段的最大似然估計(jì)法。為了驗(yàn)證這兩方面的改進(jìn)均對(duì)定位精度的提升有所幫助，對(duì)DPDV-Hop算法分步仿真。當(dāng)錨節(jié)點(diǎn)數(shù)占未知節(jié)點(diǎn)數(shù)量的20%，通信半徑逐漸增加時(shí)，觀察每個(gè)改進(jìn)點(diǎn)在上述實(shí)驗(yàn)環(huán)境和初始條件下的定位表現(xiàn)。

圖3表示錨節(jié)點(diǎn)數(shù)為20，分步加入距離優(yōu)化和I-PSO算法后，通信半徑從20 m～50 m的平均定位誤差曲線。觀察發(fā)現(xiàn)，通信半徑從20 m～40 m這一階段3條曲線整體呈下降趨勢(shì)，這是由于網(wǎng)絡(luò)連通度提升所導(dǎo)致的，而在半徑大于40 m后表現(xiàn)出的上升趨勢(shì)，是由于過(guò)大的通信半徑使平均跳距誤差增大帶來(lái)的影響。因此，不必一味要求過(guò)大的通信半徑，應(yīng)合理選取。且這兩個(gè)方面改進(jìn)均降低了算法的定位誤差，在加入I-PSO算法后的效果尤為明顯，故DPDV-Hop算法是可行的。

圖3 通信半徑不同時(shí)平均定位誤差曲線

圖4 錨節(jié)點(diǎn)數(shù)不同時(shí)平均定位誤差曲線

為了驗(yàn)證DPDV-Hop算法的優(yōu)越性，在不同錨節(jié)點(diǎn)數(shù)、通信半徑下，對(duì)DV-Hop算法、文獻(xiàn)[6]中的BDV-Hop算法與本文DPDV-Hop算法分別進(jìn)行仿真，對(duì)比結(jié)果給予分析。

(1)不同錨節(jié)點(diǎn)數(shù)

圖4表示節(jié)點(diǎn)通信半徑為30 m，錨節(jié)點(diǎn)數(shù)從5-30時(shí)3種算法的平均定位誤差曲線。觀察發(fā)現(xiàn)，3種算法的誤差曲線隨錨節(jié)點(diǎn)的增加而降低，在錨節(jié)點(diǎn)數(shù)小于20時(shí)下降尤為明顯，之后趨于平穩(wěn)。這是由于錨節(jié)點(diǎn)密度的增大使其之間的跳數(shù)減小，這就有效減小了因高跳數(shù)所帶來(lái)的誤差累積，減少了距離誤差。經(jīng)計(jì)算，DPDV-Hop算法的平均定位誤差比BDV-Hop算法和DV-Hop算法分別相對(duì)減少了39.97%和13.58%。

(2)不同通信半徑

圖5表示錨節(jié)點(diǎn)數(shù)占總節(jié)點(diǎn)數(shù)20%情況下，通信半徑從20 m～50 m時(shí)3種算法的平均定位誤差曲線。觀察發(fā)現(xiàn)，當(dāng)通信半徑小于40 m時(shí)3種算法的曲線均處于下降趨勢(shì)，大于40 m后又緩慢上升，導(dǎo)致此現(xiàn)象的原因與圖3所分析的原因一致。且從圖5中可明顯看出，DPDV-Hop算法在任何通信半徑下的定位表現(xiàn)均優(yōu)于與之對(duì)比的2種算法。經(jīng)計(jì)算，不同通信半徑下DPDV-Hop算法的平均定位誤差比DV-Hop算法和BDV-Hop算法分別相對(duì)減少了40.56%和14.74%。

圖5 通信半徑不同時(shí)平均定位誤差曲線

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

本文算法利用單跳平均誤差修正了平均跳距，采用多錨節(jié)點(diǎn)平均跳距估計(jì)節(jié)點(diǎn)間距離，使估計(jì)距離得以優(yōu)化。利用粒子成功率PS動(dòng)態(tài)調(diào)節(jié)粒子群優(yōu)化算法的慣性權(quán)重ω，加速收斂。產(chǎn)生變異算子并擇優(yōu)處理，避免早熟現(xiàn)象。用I-PSO算法的自適應(yīng)迭代尋替代最大似然估計(jì)算法，降低了距離誤差對(duì)最終定位的影響。仿真結(jié)果表明，本文算法在不增加硬件開銷的基礎(chǔ)上，提升了定位精度，適合在實(shí)際中應(yīng)用。