基于量子遺傳的蒙特卡洛節點定位算法

田浩杉

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

基于量子遺傳的蒙特卡洛節點定位算法

田浩杉

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

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

無線傳感器網絡； 量子遺傳算法； 蒙特—卡洛定位算法

0 引 言

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

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

1 MCL基本原理

在WSNs監測區域內隨機部署P個目標節點和M個錨節點。目標節點具有以下特征：節點隨機運動；每個節點運動模型獨立；節點具有相同的屬性。下面將重點關注一個目標節點，通過MCL算法來預測該節點位置。算法主要通過預測和過濾2個階段實現。

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

(1)

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

圖1 傳統MCL采樣區域

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

(2)

式中 S為目標節點周圍的一跳錨節點；T為其周圍的二跳錨節點；r為錨節點的通信半徑；l為采樣粒子；s為錨節點。符合約束條件的采樣區域如圖2、圖3所示。

圖2 一跳和二跳錨節點約束區域

經過一次過濾后剩余的有效采樣點數量不足以達到定位條件，便需在采樣區域內進行重新采集并重復過濾過程，直到有效樣本數達到設定數目為止。

MCL算法雖然在一定程度上解決了粒子在運動狀態下的定位問題，但由于該算法的樣本在采樣區域內隨機產生，導致采樣效率不高，采樣的成功率很低。隨著迭代次數的增加，粒子退化現象變得嚴重。基于此，本文通過新的采樣手段實現快速有效地尋找樣本的最優解。

2 基于量子遺傳算法的MCL節點定位

2.1 量子遺傳算法

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

2.2 量子比特

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

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

(3)

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

(4)

2.3 QGA-MCL實現步驟

1)隨機產生一個M+P個節點的網絡拓撲圖，并對其進行初始化和預處理(M個錨節點，P個目標節點)。

3)對該P條量子染色體依據編碼方案進行編碼操作。

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

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

8)返回步驟(4)，循環計算，直到滿足結束條件(最優個體的適應度達到給定閾值或達到預定的迭代次數)。

9)輸出最優解。

2.4 QGA-MCL算法具體描述

2.4.1 編碼階段

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

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

(5)

進入編碼階段，編碼方案如下

(6)

式中tj1,2=2π×rnd，rnd為(0,1)間的隨機數;P為采樣點個數。

2.4.2 解碼階段

通過MCL階段所確定的采樣區域為

(7)

則在解碼階段有如下的線性關系

(8)

(9)

(10)

(11)

通過解碼手段對每條隨機產生的量子染色體進行x軸分量與y軸分量的轉換。

2.4.3 適應度函數的選取

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

fitnessj(xj,yj)=

(12)

2.4.4 種群更新

種群更新的目的是使所有隨機產生的染色體向當代最優染色體靠攏。對于QGA，種群的更新可以通過量子旋轉門對染色體進行操作實現。常用的量子旋轉門為

(13)

由此對種群進行更新

(14)

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

1)轉角方向

(15)

式中α0,β0為當前全局最優染色體上量子位的概率幅；α1,β1為當前代某染色體上相應量子位的概率幅，則轉角θ的方向選取規則為：當A≠0 時，方向為-sgn(A);當A=0時，方向取正負均可。

2)轉角大小

Δθ=10e-t/maxt

(16)

式中t為遺傳代數。一般轉角的大小可選取0.001π～0.05π。

3 仿真實驗

(17)

圖3描述了在監測區域內，各個錨節點和目標節點在某一時刻的位置信息。各個目標節點在監測區域內相互獨立并以[0,Vmax]的速度隨機運動。

圖3 節點分布

3.1 定位誤差對比

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

圖4 定位誤差對比

3.2 錨節點密度與算法收斂速度的關系

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

圖5 錨節點密度對定位誤差的影響

3.3 節點最大速度Vmax與平均定位誤差的關系

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

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

4 結束語

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

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

[2] 張 品,毛文敏,徐 靜.一種基于迭代投票的無線傳感器網絡安全定位算法[J].傳感器與微系統,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] 鄧成玉,王宇崢,谷曉英,等.基于細菌覓食算法和跳段校正的無線傳感器網絡定位算法[J].燕山大學學報,2014,38(6):544-555.

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

[7] 劉小康,張 翔,方 爽.基于ZigBee無線傳感器網絡的一種室內定位新方法[J].傳感器與微系統,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] 劉志華,李改燕,劉曉爽.基于最小二乘法的蒙特卡洛移動節點定位算法[J].傳感技術學報,2012,25(4):541-544.

[10] 王曙光.無線傳感器網絡的分區域質心定位算法[J].傳感器與微系統,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] 楊 娟,韓雪松.基于遺傳算法優化的節點定位技術[J].制造業自動化,2015,37(2):95-97.

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

[15] 劉 宏,王齊濤,夏未君.基于量子遺傳算法的WSNs三維定位方法[J].廣西師范大學學報,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-)，男，碩士，主要研究方向為無線傳感器網絡節點定位技術。