量子粒子群算法在WSN三維定位中的研究

劉 小 園

(羅定職業(yè)技術(shù)學(xué)院　廣東 羅定 527200)

0　引　言

無(wú)線傳感網(wǎng)絡(luò)定位算法有基于測(cè)距的三邊測(cè)量法、三角測(cè)量法、極大似然估計(jì)法和基于非測(cè)距的DV-HoP算法、質(zhì)心算法、近似三角形內(nèi)點(diǎn)測(cè)試法等,這類算法主要針對(duì)二維區(qū)域節(jié)點(diǎn)定位。在實(shí)際工程應(yīng)用中，傳感節(jié)點(diǎn)往往隨機(jī)空投至三維空間，如森林，海洋，高山等。如何在立體空間實(shí)現(xiàn)對(duì)傳感節(jié)點(diǎn)的精確定位是目前研究的熱點(diǎn)和重點(diǎn)[1]。

Emmons提出一種3D-DVHoP算法，其原理與傳統(tǒng)DV-HoP算法相似。首先利用最短通路計(jì)算三維區(qū)域中各錨節(jié)點(diǎn)之間最小跳數(shù)，再根據(jù)實(shí)際距離計(jì)算平均每跳長(zhǎng)度，將實(shí)際跳數(shù)與平均跳距相乘得到與附近錨節(jié)點(diǎn)之間距離，最后利用四邊測(cè)量或極大似然估計(jì)法計(jì)算節(jié)點(diǎn)三維坐標(biāo)。

3D-DVHoP算法將傳統(tǒng)的二維區(qū)域拓展至立體空間，為節(jié)點(diǎn)三維定位提出算法模型。其和傳統(tǒng)DV-HoP算法類似，根據(jù)網(wǎng)絡(luò)連通情況使用跳數(shù)作為參考距離，實(shí)現(xiàn)簡(jiǎn)單，硬件成本較低，能很好地兼容現(xiàn)有設(shè)備。但其定位精度依賴于具體的網(wǎng)絡(luò)拓?fù)?，?dāng)錨節(jié)點(diǎn)分布不均時(shí)會(huì)產(chǎn)生較大定位偏差。因?yàn)樵谌S空間中，非相鄰錨節(jié)點(diǎn)之間通路并非直線，通過(guò)相鄰節(jié)點(diǎn)之間接力會(huì)導(dǎo)致“繞彎”現(xiàn)象[2]，再利用兩點(diǎn)彎線跳段替代直通距離勢(shì)必帶來(lái)定位偏差，并且在三維空間中表現(xiàn)更為明顯。如圖1所示。

圖1　“繞彎”現(xiàn)象示意圖

由于節(jié)點(diǎn)繞彎現(xiàn)象無(wú)法避免[3-4]，為提高定位精度，業(yè)界提出各類改進(jìn)的3D-DVHoP算法，如基于多重共線性的三維DVHoP定位算法[5]、基于加權(quán)的三維DVHoP算法[6]、基于粒子群優(yōu)化的三維DVHoP算法等[7]，但這類優(yōu)化算法都容易陷入局部最優(yōu)解現(xiàn)象[8]，定位精度雖有提高，但在25th、50th和70th定位偏差均在3%以上[9]，難以滿足工程應(yīng)用需求。

有鑒于此，本文提出一種基于量子粒子群改進(jìn)算法。在尋找鄰居節(jié)點(diǎn)之間的實(shí)際距離與繞彎距離最小誤差時(shí)，利用3D-DVHoP算法結(jié)合量子旋轉(zhuǎn)門變異規(guī)則，計(jì)算距離矩陣和跳數(shù)矩陣函數(shù)評(píng)價(jià)粒子群個(gè)體行為。通過(guò)交叉變異修正個(gè)體粒子速率和狀態(tài)，增加粒子搜索的廣泛性和遍歷性,避免粒子陷入盲目搜索和局部最優(yōu)， 從而導(dǎo)致算法搜索停滯或提前收斂現(xiàn)象。

1　量子粒子群算法

量子粒子群算法是將量子進(jìn)化算法融合到粒子群中產(chǎn)生的一種新算法[10]。算法中個(gè)體粒子位置通過(guò)量子比特進(jìn)行編碼，利用量子旋轉(zhuǎn)門更新粒子位置向量和移動(dòng)速率。在粒子群中，每個(gè)粒子代表搜索空間中的每個(gè)解。在量子粒子群中，量子旋轉(zhuǎn)門通過(guò)量子粒子移位實(shí)現(xiàn)對(duì)搜索空間中兩個(gè)位置的同時(shí)移動(dòng)。因此一個(gè)量子粒子對(duì)應(yīng)于搜索空間中的兩個(gè)解，以此釆增加粒子搜索的廣泛性和遍歷性，提高算法優(yōu)化效率，避免陷入局部最優(yōu)現(xiàn)象。

2　3D-DVHoP算法原理

3D-DVHoP算法定位過(guò)程分為三個(gè)階段。第一階段，錨節(jié)點(diǎn)向鄰居節(jié)點(diǎn)廣播分組信息，包含自身位置坐標(biāo)、ID以及跳數(shù)字段，獲得網(wǎng)路中其他錨節(jié)點(diǎn)位置信息和跳數(shù)距離，從而估算平均跳離，見(jiàn)式(1)：

(1)

第二階段，錨節(jié)點(diǎn)將平均跳距加入自身分組信息，再次洪泛至整個(gè)網(wǎng)絡(luò)，并計(jì)算其與所有錨節(jié)點(diǎn)之間的參考跳距。

第三階段，根據(jù)與其他錨節(jié)點(diǎn)的參考距離，利用四邊測(cè)量或極大似然估計(jì)法計(jì)算節(jié)點(diǎn)的三維坐標(biāo)。

在立體空間中，設(shè)未知節(jié)點(diǎn)M(x,y,z)附近存在n個(gè)錨節(jié)點(diǎn)，坐標(biāo)分別為(x1,y1,z1),(x2,y2,z2),…,(xn,yn,zn),與節(jié)點(diǎn)M之間距離分別d1,d2,…,dn。如圖2所示。

圖2　節(jié)點(diǎn)空間拓?fù)鋱D

根據(jù)式(1)計(jì)算未知節(jié)點(diǎn)M與其他錨節(jié)點(diǎn)之間參考距離：

(2)

將式(2)中方程組每一行分別減去第n行，并改成“AX=b”線性表達(dá)式，其中：

(3)

最后根據(jù)最小方差估計(jì)法計(jì)算節(jié)點(diǎn)M三維坐標(biāo):

(4)

3　優(yōu)化算法思想和定位過(guò)程

3.1　粒子群優(yōu)化算法和不足

要尋找目的節(jié)點(diǎn)與鄰居錨節(jié)點(diǎn)之間實(shí)際距離與估算繞彎距離的最小誤差，根據(jù)式(4)可以轉(zhuǎn)換為函數(shù)最優(yōu)化問(wèn)題。在粒子群算法中，每個(gè)粒子位置代表函數(shù)優(yōu)化的每個(gè)可行解，粒子根據(jù)目標(biāo)函數(shù)修正當(dāng)前位置和飛行方向，找出全局最優(yōu)解，完成搜索過(guò)程。然而，粒子群算法是一個(gè)正向反饋的過(guò)程，當(dāng)局部信息過(guò)優(yōu)時(shí)容易產(chǎn)生大量粒子聚集導(dǎo)致算法提早收斂，陷入局部最優(yōu)的問(wèn)題。另外，慣性權(quán)重W為(0,1)之間隨機(jī)數(shù)，使得算法早期粒子速度更新沒(méi)有規(guī)律，后期收斂緩慢。因此利用單純的粒子群優(yōu)化求解效果不佳，定位精度有待提高。

3.2　建立目標(biāo)函數(shù)

新算法基于3D-DVHoP第三階段獲得的距離矩陣和跳數(shù)矩陣，采用量子粒子群算法修正節(jié)點(diǎn)估算距離以減少偏差，提高定位精度。為更好地描述量子粒子群算法節(jié)點(diǎn)部署，找到實(shí)際距離與估算繞彎距離之間的最小誤差，建立優(yōu)化目標(biāo)函數(shù)為:

(5)

其中，ci是傳感網(wǎng)絡(luò)節(jié)點(diǎn)路徑成本，C為監(jiān)測(cè)區(qū)域部署的傳感器路徑成本。

3.3　算法定位過(guò)程

新算法首先對(duì)粒子群進(jìn)行量子編碼，利用量子旋轉(zhuǎn)門調(diào)整個(gè)體粒子速率和方向從而確定搜索空間，避免粒子過(guò)早收斂造成局部最優(yōu)。為得到目標(biāo)函數(shù)最優(yōu)解，需要確定量子旋轉(zhuǎn)門變異規(guī)則和適應(yīng)度函數(shù)(適應(yīng)度函數(shù)是與3D-DVHoP算法中得到的距離矩陣和跳數(shù)矩陣相關(guān)的函數(shù))以評(píng)價(jià)粒子群個(gè)體行為，得到尋優(yōu)群體。最后通過(guò)粒子群迭代優(yōu)化尋找到目標(biāo)函數(shù)的最優(yōu)解，從而修正節(jié)點(diǎn)最優(yōu)坐標(biāo)值。新算法具體流程如下：

第二步確定粒子位置狀態(tài)。在一個(gè)n維搜索空間，有m個(gè)粒子(表示目標(biāo)函數(shù)的可能解)組成的群體，其中在t時(shí)刻第i個(gè)粒子位置為：

Xi(t)=?xi,1(t),xi,2(t),…,xi,n(t)」

(6)

在t時(shí)刻粒子最好個(gè)體位置為：

Pi(t)=?Pi,1(t),Pi,2(t),…,Pi,n(t)」

(7)

整個(gè)粒子群最好全局位置為：

G(t)=?G1(t),G2(t),…,Gn(t)」

(8)

第三步對(duì)粒子群進(jìn)行量子化編碼。定義量子比特，其狀態(tài)可為:

|τ〉=αij|0〉+βij|1〉

(9)

(10)

其中，αij,βij表示為種群中所有染色體基因。

第四步建立適應(yīng)度函數(shù)評(píng)價(jià)個(gè)體粒子行為狀態(tài)。適應(yīng)度函數(shù)值越小，表示適應(yīng)度越好。適應(yīng)度評(píng)價(jià)函數(shù)為：

(11)

其中，Dij為傳感網(wǎng)絡(luò)中相鄰節(jié)點(diǎn)i與j之間真實(shí)距離，dij是相鄰節(jié)點(diǎn)i與j之間估算的參考距離;djk是相鄰節(jié)點(diǎn)j與k之間估算的參考距離。由式(10)得到粒子i最好個(gè)體位置為：

(12)

整個(gè)粒子群最好全局位置為：

g=argmin{f[Pi(t)]}

G(t)=Pg(t)

(13)

第五步計(jì)算個(gè)體粒子位置。將粒子個(gè)體最佳位置和整個(gè)粒子群體最佳全局位置進(jìn)行比較，從而更新個(gè)體粒子位置：

Xi,j(t+1)=pi,j(t)+|Cj(t)-|Xi,j(t)

(14)

其中：

(15)

第六步利用量子旋轉(zhuǎn)門修正個(gè)體粒子速率和狀態(tài)，避免陷入局部最優(yōu)。定義量子旋轉(zhuǎn)門U(θ)，利用量子旋轉(zhuǎn)門不同旋轉(zhuǎn)角度對(duì)量子染色體實(shí)施變異操作，并對(duì)個(gè)體粒子行為狀態(tài)進(jìn)行修正。令：

(16)

(17)

重復(fù)第五步和第六步，粒子通過(guò)判斷群體最佳全局位置，結(jié)合量子旋轉(zhuǎn)門的變異操作不斷更新當(dāng)前位置和飛行速率，最終找到全局最優(yōu)解，完成搜索過(guò)程，根據(jù)目標(biāo)函數(shù)尋找到未知節(jié)點(diǎn)與錨節(jié)點(diǎn)之間實(shí)際距離與估算繞彎距離的最小誤差。

第七步根據(jù)3D-DVHoP算法，利用最小方差計(jì)算節(jié)點(diǎn)M三維坐標(biāo)。

3.4　定位偏差評(píng)價(jià)方式

算法采用平均定位偏差對(duì)三維節(jié)點(diǎn)定位精度進(jìn)行評(píng)價(jià)，公式為：

(18)

4　仿真測(cè)試

4.1　仿真環(huán)境

仿真環(huán)境采用基于網(wǎng)格節(jié)點(diǎn)放置模型，節(jié)點(diǎn)在100×100×100三維區(qū)域內(nèi)隨機(jī)分布，未知節(jié)點(diǎn)數(shù)量70，錨節(jié)點(diǎn)數(shù)量30，節(jié)點(diǎn)通信半徑20，初始化粒子群規(guī)模200，加速系數(shù)c1=1，c2=1，最大迭代次數(shù)k=800，利用MATLAB7.0軟件對(duì)算法仿真比較。

4.2　三維定位偏差測(cè)試

三維空間中新算法與3D-DVHoP經(jīng)典算法定位偏差見(jiàn)圖3所示。由于錨節(jié)點(diǎn)非均勻分布，3D-DVHoP在計(jì)算平均跳距時(shí)會(huì)產(chǎn)生誤差，并且錨節(jié)點(diǎn)密度越小，定位偏差越大。圖3中某些區(qū)域錨節(jié)點(diǎn)密度較低，3D-DVHoP計(jì)算的最大偏差高達(dá)23.87%。新算法利用量子粒子群尋找實(shí)際距離與估算距離之間的最小誤差值，從而修正定位結(jié)果，平均定位偏差明顯小于3D-DVHoP算法。

圖3　定位偏差測(cè)試圖

4.3　節(jié)點(diǎn)密度定位偏差測(cè)試

錨節(jié)點(diǎn)密度與定位偏差測(cè)試結(jié)果見(jiàn)圖4所示。所有優(yōu)化算法定位偏差都隨節(jié)點(diǎn)密度增大而減小，滿足共性規(guī)律，但當(dāng)錨節(jié)點(diǎn)數(shù)量小于40時(shí)算法差異明顯。其中3D-DVHoP直接將彎線跳段距離替代直通距離，算法定位偏差最大?；诙嘀毓簿€性的三維DVHoP定位算法、基于加權(quán)的三維DVHoP算法和基于粒子群優(yōu)化的三維DVHoP算法，采用不同技術(shù)修正非相鄰節(jié)點(diǎn)之間的“繞彎”誤差，但找到的解并非全局最優(yōu)解，陷入局部最優(yōu)問(wèn)題。新算法平均定位偏差最小，當(dāng)節(jié)點(diǎn)數(shù)量大于55時(shí)偏差趨于收斂，在25th、50th和70th距離偏差值分別是1.25米、0.6米和0.5米，均在1.5%以內(nèi)。

圖4　節(jié)點(diǎn)密度定位偏差測(cè)試圖

5　結(jié)　語(yǔ)

3D-DVHoP在三維空間利用彎線跳段距離替代直通距離，因節(jié)點(diǎn)“繞彎”現(xiàn)象導(dǎo)致較大定位偏差，已有改進(jìn)算法在修正偏差時(shí)已無(wú)法找到全局最優(yōu)解，或多或少的存在算法提前收斂現(xiàn)象。本文提出一種基于量子粒子群改進(jìn)算法，通過(guò)判斷粒子群體最佳全局位置和量子旋轉(zhuǎn)門變異操作修正個(gè)體粒子速率和狀態(tài)，找出節(jié)點(diǎn)實(shí)際距離與估算繞彎距離之間的最小誤差以提高定位精度，算法相對(duì)復(fù)雜，但定位結(jié)果更為精確。

[1] 曾子維,張超.一種質(zhì)心與DV-Hop算法相結(jié)合的WSN節(jié)點(diǎn)定位算法[J].計(jì)算機(jī)應(yīng)用與軟件,2015,32(11):130-133.

[2] 劉士興,黃俊杰,劉宏銀,等.基于多通信半徑的加權(quán)DV-Hop定位算法[J].傳感技術(shù)學(xué)報(bào),2015,28(6):883-887.

[3] 涂巧鈴,牟小燕,宋佳.一種改進(jìn)的DV-Hop改進(jìn)算法[J].重慶理工大學(xué)學(xué)報(bào)(自然科學(xué)版),2014,28(11):84-88.

[4] 高文根,陳其工,江明,等.基于距離補(bǔ)償模型的改進(jìn)DV-Hop定位算法[J].計(jì)算機(jī)工程,2015,41(3):32-36.

[5] 劉文遠(yuǎn),王恩爽,陳子軍.無(wú)線傳感器網(wǎng)絡(luò)中DV-Hop定位算法的改進(jìn)[J].小型微型計(jì)算機(jī)系統(tǒng),2011,32(6):1071-1074.

[6] 陳三風(fēng),陳萬(wàn)明.基于RSSI誤差分析的無(wú)線傳感器網(wǎng)絡(luò)定位研究[J].計(jì)算機(jī)工程與應(yīng)用,2011,47(14):10-12,75.

[7] 沈軍,黃春華,羅護(hù),等.基于RSSI優(yōu)化的模型參數(shù)實(shí)時(shí)估計(jì)定位算法[J].計(jì)算機(jī)工程與設(shè)計(jì),2012,33(2):464-468.

[8] Chen H,Sezaki K,Deng P,et al.An improved DV-Hop localization algorithm with reduced node location error for wireless sensor networks[J].IEICE Transactions on Fundamentals of Electronics,Communications and Computer Science,2008,E91-A(8):2232-2236.

[9] Savarese C,Rabaey J M,Langendoen K.Robust Positioning Algorithms for Distributed Ad-Hoc Wireless Sensor Networks[C]//Proceedings of the General Track of the Annual Conference on USENIX Annual Technical Conference,2002:317-327.

[10] Sun G,Qiao G,Xu B.Corrosion monitoring sensor networks with energy harvesting[J].IEEE Sensors Journal,2011,11(6):1476-1477.