基于量子遺傳的蒙特卡洛節(jié)點(diǎn)定位算法

田浩杉

(蘭州交通大學(xué) 電子與信息工程學(xué)院，甘肅 蘭州 730070)

基于量子遺傳的蒙特卡洛節(jié)點(diǎn)定位算法

田浩杉

(蘭州交通大學(xué) 電子與信息工程學(xué)院，甘肅 蘭州 730070)

針對無線傳感器網(wǎng)絡(luò)(WSNs)節(jié)點(diǎn)定位的問題，提出了一種量子遺傳算法與蒙特—卡洛相結(jié)合的定位算法(QGA-MCL)。將QGA應(yīng)用于MCL中的采樣過濾階段，通過合理的編碼方案、譯碼方案以及量子旋轉(zhuǎn)門對采樣區(qū)域中隨機(jī)產(chǎn)生的量子染色體進(jìn)行操作，提高了樣本尋優(yōu)效率和定位精度,并加快了算法的收斂速度。仿真結(jié)果表明:與蒙特—卡洛定位算法相比，提出的QGA-MCL算法能夠減少約10.2 %的定位誤差，同時，算法的收斂速度也得到了顯著提升。

無線傳感器網(wǎng)絡(luò)； 量子遺傳算法； 蒙特—卡洛定位算法

0 引 言

早在2004年,蒙特—卡洛定位(Monte-Carlo localization，MCL)算法便由機(jī)器人定位中引入到了移動無線傳感器網(wǎng)絡(luò)[1～6](wireless sensor networks,WSNs)中進(jìn)行節(jié)點(diǎn)定位，雖然MCL定位算法拋開了節(jié)點(diǎn)移動性的干擾，甚至節(jié)點(diǎn)移動速度越大定位精度越高，但采樣成功率很低，并且容易出現(xiàn)粒子退化的問題[7]。近年來,很多學(xué)者對其進(jìn)行了改進(jìn)，文獻(xiàn)[8]提出了蒙特-卡洛盒子定位(Monte-Carlo location boxed，MCB)算法，通過錨箱(anchor box)和采樣箱(sample box)縮小采樣區(qū)域,從而提高了采樣效率。但當(dāng)觀測模型分布在錨箱的比重很小時，采樣的成功率仍然很低[9,10]。文獻(xiàn)[11]提出了動態(tài)靜態(tài)網(wǎng)絡(luò)節(jié)點(diǎn)定位(mobile and static sensor network localization，MSL)，算法利用鄰居節(jié)點(diǎn)中定位精度較高的節(jié)點(diǎn)來輔助定位，但其計(jì)算過程非常復(fù)雜，通信耗能也比較大。文獻(xiàn)[12]將DV-Hop引入到了MCL定位中，提出了多跳蒙特—卡洛定位(multi-hop-based Monte-Carlo localization，MMCL)算法，充分利用了錨節(jié)點(diǎn)的信息，在低錨節(jié)點(diǎn)密度的網(wǎng)絡(luò)中表現(xiàn)出了良好的定位性能。上述算法從不同角度對MCL算法進(jìn)行了改進(jìn)，但在網(wǎng)絡(luò)拓?fù)渥兓容^頻繁的高速移動網(wǎng)絡(luò)環(huán)境下，上述算法的穩(wěn)定性和網(wǎng)絡(luò)生存性則存在一定的性能缺陷。

本文在MCL定位算法的基礎(chǔ)上引入了一種通過量子遺傳的方法來提高尋優(yōu)效率，即QGA-MCL算法，算法通過新的尋優(yōu)手段將MCL的樣本采集及過濾階段優(yōu)化，提高了收斂速度和定位精度。

1 MCL基本原理

在WSNs監(jiān)測區(qū)域內(nèi)隨機(jī)部署P個目標(biāo)節(jié)點(diǎn)和M個錨節(jié)點(diǎn)。目標(biāo)節(jié)點(diǎn)具有以下特征：節(jié)點(diǎn)隨機(jī)運(yùn)動；每個節(jié)點(diǎn)運(yùn)動模型獨(dú)立；節(jié)點(diǎn)具有相同的屬性。下面將重點(diǎn)關(guān)注一個目標(biāo)節(jié)點(diǎn)，通過MCL算法來預(yù)測該節(jié)點(diǎn)位置。算法主要通過預(yù)測和過濾2個階段實(shí)現(xiàn)。

在MCL算法中時間被分割成等長的離散時間段，用t={1,2,3,…}表示離散的時間，并且假設(shè)僅已知待定位節(jié)點(diǎn)的最大移動速度Vmax。待定位節(jié)點(diǎn)在每一個時間段內(nèi)都要重新定位。

(1)

式中 d(lt,lt-1)為節(jié)點(diǎn)在t時刻和t-1時刻的歐幾里得距離，當(dāng)節(jié)點(diǎn)的最大運(yùn)動速度Vmax越大時，所對應(yīng)的采樣區(qū)域便越大，加大了定位誤差。如果加入了節(jié)點(diǎn)的運(yùn)動模型，根據(jù)運(yùn)動模型來縮小采樣區(qū)域，便會提高采樣效率，減小定位誤差。傳統(tǒng)MCL算法的采樣區(qū)域如圖1所示。

圖1 傳統(tǒng)MCL采樣區(qū)域

2)過濾階段:根據(jù)節(jié)點(diǎn)在t時刻接收的由一跳鄰居錨節(jié)點(diǎn)和二跳鄰居錨節(jié)點(diǎn)所發(fā)送的觀測信息對采樣點(diǎn)進(jìn)行篩選，將不符合要求的過濾掉。對于采樣點(diǎn)l的過濾條件可表示為

(2)

式中 S為目標(biāo)節(jié)點(diǎn)周圍的一跳錨節(jié)點(diǎn)；T為其周圍的二跳錨節(jié)點(diǎn)；r為錨節(jié)點(diǎn)的通信半徑；l為采樣粒子；s為錨節(jié)點(diǎn)。符合約束條件的采樣區(qū)域如圖2、圖3所示。

圖2 一跳和二跳錨節(jié)點(diǎn)約束區(qū)域

經(jīng)過一次過濾后剩余的有效采樣點(diǎn)數(shù)量不足以達(dá)到定位條件，便需在采樣區(qū)域內(nèi)進(jìn)行重新采集并重復(fù)過濾過程，直到有效樣本數(shù)達(dá)到設(shè)定數(shù)目為止。

MCL算法雖然在一定程度上解決了粒子在運(yùn)動狀態(tài)下的定位問題，但由于該算法的樣本在采樣區(qū)域內(nèi)隨機(jī)產(chǎn)生，導(dǎo)致采樣效率不高，采樣的成功率很低。隨著迭代次數(shù)的增加，粒子退化現(xiàn)象變得嚴(yán)重。基于此，本文通過新的采樣手段實(shí)現(xiàn)快速有效地尋找樣本的最優(yōu)解。

2 基于量子遺傳算法的MCL節(jié)點(diǎn)定位

2.1 量子遺傳算法

量子遺傳算法(quantumgeneticalgorithm，QGA)[13]不僅增加了粒子的多樣性，防止粒子退化現(xiàn)象出現(xiàn)，同時,有效縮短了計(jì)算時間且改善粒子定位能力[14]。QGA沒有采用傳統(tǒng)遺傳算法的選擇、交叉、變異等操作方法，而是構(gòu)造量子旋轉(zhuǎn)門作用于量子疊加態(tài)，使其相互干擾，改變旋轉(zhuǎn)角度，更新種群，從而可以通過量子旋轉(zhuǎn)門來實(shí)現(xiàn)對染色體的操作[15]。

2.2 量子比特

量子計(jì)算中采用了|0〉和|1〉表示微觀粒子的兩種基本狀態(tài)，將其稱為量子比特(qubit)。處于兩種基本狀態(tài)的線性組合狀態(tài)稱之為疊加態(tài),表示為

|φ〉=α|0〉+β|1〉，|α|2+|β|2=1

(3)

式中 α，β為一對復(fù)數(shù)，稱為量子態(tài)的概率幅；|α|2和|β|2分別為量子態(tài)中2個基本態(tài)的選擇概率。因而，量子最終處于何種狀態(tài)由2個概率幅決定，可以簡化表示為

(4)

2.3 QGA-MCL實(shí)現(xiàn)步驟

1)隨機(jī)產(chǎn)生一個M+P個節(jié)點(diǎn)的網(wǎng)絡(luò)拓?fù)鋱D，并對其進(jìn)行初始化和預(yù)處理(M個錨節(jié)點(diǎn)，P個目標(biāo)節(jié)點(diǎn))。

3)對該P(yáng)條量子染色體依據(jù)編碼方案進(jìn)行編碼操作。

5)以p0為目標(biāo)，用量子旋轉(zhuǎn)門對種群中量子染色體予以更新，更新時根據(jù)方向準(zhǔn)則變換，大小為10e-t/maxt(t為代數(shù))。

7)在遺傳過程中，判斷種群是否需要變異。若連續(xù)數(shù)代最優(yōu)個體均無任何變化且未達(dá)到適應(yīng)度閾值時，便對種群進(jìn)行變異操作，采用量子非門手段。

8)返回步驟(4)，循環(huán)計(jì)算，直到滿足結(jié)束條件(最優(yōu)個體的適應(yīng)度達(dá)到給定閾值或達(dá)到預(yù)定的迭代次數(shù))。

9)輸出最優(yōu)解。

2.4 QGA-MCL算法具體描述

2.4.1 編碼階段

對于每一個隨機(jī)采集的樣本點(diǎn)(xj,yj)，用量子染色體呈現(xiàn)。由于考慮的是二維空間，需要通過2個量子位表示染色體，因此，本文直接用量子位的概率幅進(jìn)行編碼。

在初始化階段，樣本點(diǎn)偏向x軸和y軸的概率相同。所有P條染色體的概率幅為

(5)

進(jìn)入編碼階段，編碼方案如下

(6)

式中tj1,2=2π×rnd，rnd為(0,1)間的隨機(jī)數(shù);P為采樣點(diǎn)個數(shù)。

2.4.2 解碼階段

通過MCL階段所確定的采樣區(qū)域?yàn)?/p>

(7)

則在解碼階段有如下的線性關(guān)系

(8)

(9)

(10)

(11)

通過解碼手段對每條隨機(jī)產(chǎn)生的量子染色體進(jìn)行x軸分量與y軸分量的轉(zhuǎn)換。

2.4.3 適應(yīng)度函數(shù)的選取

按照適應(yīng)度函數(shù)的設(shè)計(jì)原則，在QGA搜索求解過程中，常常求解最小值。針對平均誤差值的研究，假設(shè)di為根據(jù)測距手段測量出的目標(biāo)節(jié)點(diǎn)與錨節(jié)點(diǎn)i之間的距離，為已知量，采樣區(qū)域內(nèi)所有采樣點(diǎn)的坐標(biāo)為(xj,yj)；錨節(jié)點(diǎn)的坐標(biāo)為(xi,yi)。適應(yīng)度函數(shù)值最小的為當(dāng)代染色體的最優(yōu)解

fitnessj(xj,yj)=

(12)

2.4.4 種群更新

種群更新的目的是使所有隨機(jī)產(chǎn)生的染色體向當(dāng)代最優(yōu)染色體靠攏。對于QGA，種群的更新可以通過量子旋轉(zhuǎn)門對染色體進(jìn)行操作實(shí)現(xiàn)。常用的量子旋轉(zhuǎn)門為

(13)

由此對種群進(jìn)行更新

(14)

旋轉(zhuǎn)門的轉(zhuǎn)角大小和方向可以改變，與此同時,其也影響著算法的收斂速度。

1)轉(zhuǎn)角方向

(15)

式中α0,β0為當(dāng)前全局最優(yōu)染色體上量子位的概率幅；α1,β1為當(dāng)前代某染色體上相應(yīng)量子位的概率幅，則轉(zhuǎn)角θ的方向選取規(guī)則為：當(dāng)A≠0 時，方向?yàn)?sgn(A);當(dāng)A=0時，方向取正負(fù)均可。

2)轉(zhuǎn)角大小

Δθ=10e-t/maxt

(16)

式中t為遺傳代數(shù)。一般轉(zhuǎn)角的大小可選取0.001π～0.05π。

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

(17)

圖3描述了在監(jiān)測區(qū)域內(nèi)，各個錨節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)在某一時刻的位置信息。各個目標(biāo)節(jié)點(diǎn)在監(jiān)測區(qū)域內(nèi)相互獨(dú)立并以[0,Vmax]的速度隨機(jī)運(yùn)動。

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

3.1 定位誤差對比

實(shí)驗(yàn)設(shè)定測距誤差為20 %，連通度為5，共測得120個數(shù)據(jù)，仿真結(jié)果如圖4所示。從仿真結(jié)果可看出：QGA-MCL算法的定位誤差比傳統(tǒng)MCL算法要小。具體為：QGA-MCL的平均定位誤差約為17.5 %，其最大定位誤差比最小定位誤差高約8.7 % ；MCL算法的平均定位誤差約為27.74 %，其最大定位誤差比最小定位誤差高約15 %；QGA-MCL比傳統(tǒng)MCL的平均定位誤差降低了約10.24 %。由此得出：QGA-MCL算法的定位精度和穩(wěn)定性比MCL算法高。

圖4 定位誤差對比

3.2 錨節(jié)點(diǎn)密度與算法收斂速度的關(guān)系

如圖5所示，在不同錨節(jié)點(diǎn)密度的情況下，各類MCL算法的收斂速度均會有所提高，為使最終解的適應(yīng)度值達(dá)到所設(shè)定的閾值，QGA-MCL算法在相同錨節(jié)點(diǎn)密度的情況下明顯較傳統(tǒng)MCL算法的搜索速度快,在很大程度上提高了算法效率，避免了傳統(tǒng)MCL算法中對相同粒子的重復(fù)操作。

圖5 錨節(jié)點(diǎn)密度對定位誤差的影響

3.3 節(jié)點(diǎn)最大速度Vmax與平均定位誤差的關(guān)系

圖6為隨著目標(biāo)節(jié)點(diǎn)Vmax的變化，不同類型MCL算法平均定位誤差的變化曲線。從圖中可看出：隨著Vmax的增大，各類MCL算法的平均定位誤差之間的差異逐漸縮小。最大速度在定位過程中的2個階段影響定位精度:1)預(yù)測階段，采樣區(qū)域與節(jié)點(diǎn)的最大速度有關(guān)，隨著Vmax加大將導(dǎo)致采樣樣本的準(zhǔn)確度下降。最大速度對基于MCL的所有算法的影響均相同。2)每個時間段，節(jié)點(diǎn)的平均速度越大，目標(biāo)節(jié)點(diǎn)能夠接收到的觀測信息就越多[13]，進(jìn)而濾除更多不符合條件的樣本。QGA-MCL算法的采樣階段是在采樣區(qū)域中隨機(jī)產(chǎn)生量子染色體，對染色體進(jìn)行迭代尋優(yōu)的過程。所以，目標(biāo)節(jié)點(diǎn)的速度越大，觀測到的關(guān)于采樣區(qū)的信息就越多。

圖6 最大速度對定位誤差的影響

4 結(jié)束語

在MCL算法的基礎(chǔ)上，引入了QGA進(jìn)行粒子快速尋優(yōu)，提出了QPS-MCL算法，雖然在染色體編碼譯碼時由于計(jì)算量消耗了較多能量，但在很大程度上，提高了算法效率，避免了復(fù)雜的樣本采集和過濾。通過仿真實(shí)驗(yàn)證明：相比于MCL和MCB，算法在不同錨節(jié)點(diǎn)密度和運(yùn)動速度下有著良好的定位性能，定位精度有所提高。

[1] Shi H,Wang W.Game theory for wireless sensor networks:A survey[J].Sensors,2012,12(7):9055-9097.

[2] 張 品,毛文敏,徐 靜.一種基于迭代投票的無線傳感器網(wǎng)絡(luò)安全定位算法[J].傳感器與微系統(tǒng),2015,34(12):118-120.

[3] Yusuke Wada,Takamasa Higuchi,Hirozumi Yamaguchi,et al.Accurate positioning of mobile phones in a crowd using laser range scanners[C]∥2013 IEEE 9th International Conference on Wireless and Mobile Computing,2013:430-435.

[4] ZeKavat Buehrer．Handbook of position location: Theory,practice and advance[M].Hobker:John Wiley & Sons,2012: 359-395．

[5] 鄧成玉,王宇崢,谷曉英,等.基于細(xì)菌覓食算法和跳段校正的無線傳感器網(wǎng)絡(luò)定位算法[J].燕山大學(xué)學(xué)報,2014,38(6):544-555.

[6] 金 純,王升剛,尹遠(yuǎn)陽.WSNs中一種基于移動新標(biāo)檢測的定位算法[J].傳感器與微系統(tǒng),2014,33(2):142-145.

[7] 劉小康,張 翔,方 爽.基于ZigBee無線傳感器網(wǎng)絡(luò)的一種室內(nèi)定位新方法[J].傳感器與微系統(tǒng),2013,32(11):29-32.

[8] Baggio A,Langendoen K.Monte Carlo localization for wireless sensor networks[C]∥Proc of 2nd Int'l Conf on Mobile Ad Hoc and Sensor Networks,MSNs 2006,Hong Kong,Springer Verlag,2006:718-733.

[9] 劉志華,李改燕,劉曉爽.基于最小二乘法的蒙特卡洛移動節(jié)點(diǎn)定位算法[J].傳感技術(shù)學(xué)報,2012,25(4):541-544.

[10] 王曙光.無線傳感器網(wǎng)絡(luò)的分區(qū)域質(zhì)心定位算法[J].傳感器與微系統(tǒng),2014,33(12):149-151.

[11] Rudafshani M,Datta S.Localization in wireless sensor net-works[C]∥Proceedings of the 6th International Symposium on Information Processing in Sensor Networks,Cambridge,MA,USA,2007:51-60.

[12] Yi Jiyong,Won Yangsung,Cha Hojung.Multi-hop-based Monte Carlo localization for mobile sensor networks[C]∥Proceedings of The 4th Annual IEEE Communications Society Conference on Sensor,Mesh and Ad Hoc Communications and Networks,San Diego,California,USA,2007:163-171.

[13] 楊 娟,韓雪松.基于遺傳算法優(yōu)化的節(jié)點(diǎn)定位技術(shù)[J].制造業(yè)自動化,2015,37(2):95-97.

[14] 董躍鈞,李國偉.量子遺傳優(yōu)化粒子濾波的WSNs目標(biāo)跟蹤算法[J].科學(xué)技術(shù)與工程,2013,13(12):3305-3309.

[15] 劉 宏,王齊濤,夏未君.基于量子遺傳算法的WSNs三維定位方法[J].廣西師范大學(xué)學(xué)報,2015,33(4):49-54.

Monte Carlo node localization algorithm based on quantum genetic

TIAN Hao-sha

(School of Electronic and Information Engineering,Lanzhou Jiao Tong University,Lanzhou 730070,China)

A new node localization algorithm is proposed for wireless sensor networks(WSNs),which combines quantum genetic algorithm with the Monte Carlo localization(QGA-MCL).QGA is applied to the sampling filtering stage in MCL.Operate the quantum chromosomes which is random generated in sampling area by reasonable encoding scheme,decoding scheme and quantum rotating gate.Simulation results demonstrate that compared with Monte Carlo localization algorithm,the proposed QGA-MCL algorithm can reduce positioning error about 10.2 %,and meanwhile,the convergence speed of algorithm is improved significantly.

wireless sensor networks(WSNs); quantum genetic algorithm(QGA); Monte Carlo localization(MCL)algorithm

10.13873/J.1000—9787(2017)09—0125—04

2016—09—09

TP 393

A

1000—9787(2017)09—0125—04

田浩杉(1992-)，男，碩士，主要研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位技術(shù)。