劉 小 園

(羅定職業(yè)技術學院　廣東 羅定 527200)

0　引　言

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

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

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

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

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

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

1　量子粒子群算法

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

2　3D-DVHoP算法原理

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

(1)

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

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

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

圖2　節(jié)點空間拓撲圖

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

(2)

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

(3)

最后根據(jù)最小方差估計法計算節(jié)點M三維坐標:

(4)

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

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

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

3.2　建立目標函數(shù)

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

(5)

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

3.3　算法定位過程

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

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

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

(6)

在t時刻粒子最好個體位置為：

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

(7)

整個粒子群最好全局位置為：

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

(8)

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

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

(9)

(10)

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

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

(11)

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

(12)

整個粒子群最好全局位置為：

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

G(t)=Pg(t)

(13)

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

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

(14)

其中：

(15)

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

(16)

(17)

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

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

3.4　定位偏差評價方式

算法采用平均定位偏差對三維節(jié)點定位精度進行評價，公式為：

(18)

4　仿真測試

4.1　仿真環(huán)境

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

4.2　三維定位偏差測試

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

圖3　定位偏差測試圖

4.3　節(jié)點密度定位偏差測試

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

圖4　節(jié)點密度定位偏差測試圖

5　結　語

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

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

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

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

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

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

[6] 陳三風,陳萬明.基于RSSI誤差分析的無線傳感器網絡定位研究[J].計算機工程與應用,2011,47(14):10-12,75.

[7] 沈軍,黃春華,羅護,等.基于RSSI優(yōu)化的模型參數(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.