一種基于MCB的自適應(yīng)和聲搜索定位算法*

孫 崇， 孫子文

(江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院，江蘇 無錫 214122)

一種基于MCB的自適應(yīng)和聲搜索定位算法*

孫 崇， 孫子文

(江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院，江蘇 無錫 214122)

針對無線傳感器網(wǎng)絡(luò)錨節(jié)點(diǎn)稀疏條件下節(jié)點(diǎn)定位中存在的翻轉(zhuǎn)現(xiàn)象和定位精度問題，提出了一種基于MCB的自適應(yīng)和聲搜索定位算法。通過引入MCB算法中的采樣思想，隨機(jī)產(chǎn)生網(wǎng)絡(luò)拓?fù)浼s束下的未知節(jié)點(diǎn)的坐標(biāo)，引入自適應(yīng)的和聲保留概率和音調(diào)調(diào)節(jié)概率，達(dá)到提高搜索能力和定位精度目的。仿真結(jié)果表明：算法能有效解決翻轉(zhuǎn)現(xiàn)象，提高定位精度，提出的算法在定位精度和計算量方面優(yōu)于對比算法。

無線傳感器網(wǎng)絡(luò)； 定位； 翻轉(zhuǎn)現(xiàn)象； 自適應(yīng)； 和聲搜索算法

0 引 言

由于節(jié)點(diǎn)能量的限制，在無線傳感器網(wǎng)絡(luò)(wireless sensor networks,WSNs)定位中，傳感器節(jié)點(diǎn)都安裝GPS裝置是不現(xiàn)實的，且GPS一般不適合室內(nèi)環(huán)境，因此,只有少量的傳感器節(jié)點(diǎn)安裝了GPS裝置或已知其位置信息,其他大量的傳感器節(jié)點(diǎn)則需要根據(jù)已知位置的節(jié)點(diǎn)與它們之間的距離信息獲得自身的位置信息。無線傳感器網(wǎng)絡(luò)定位方法中，基于測距(range-based)技術(shù)的有接收信號強(qiáng)度指示(received signal strength indication,RSSI)、到達(dá)時間(time of arrival,TOA)、到達(dá)角度(angle of arrival,AOA)或不同信號的到達(dá)時間差(time difference of arrival,TDOA)等[1]。而基于測距的無線傳感器網(wǎng)絡(luò)定位常常會出現(xiàn)翻轉(zhuǎn)現(xiàn)象[2,3]，當(dāng)節(jié)點(diǎn)密度低時，翻轉(zhuǎn)現(xiàn)象尤其突出，從而造成較大的定位誤差。

為了解決翻轉(zhuǎn)問題，最近兩階段基于模擬退火的定位(simulated annealing-based localization,SAL)算法[2]和混合和聲搜索定位算法(harmony search-based localization,HSL)算法[4]被提出。SAL算法在第一階段獲得初始估計節(jié)點(diǎn)位置，在第二階段解決定位中的翻轉(zhuǎn)現(xiàn)象和獲得節(jié)點(diǎn)最終估計位置。HSL算法直接一階段獲得節(jié)點(diǎn)估計位置，并解決定位中的翻轉(zhuǎn)現(xiàn)象。但節(jié)點(diǎn)定位仍存在定位誤差，尤其錨節(jié)點(diǎn)分布不均勻、通信范圍較小時，節(jié)點(diǎn)定位存在較大的定位誤差。

本文采用基于MCB(Monte Carlo localization boxed)的自適應(yīng)和聲搜索定位算法解決上述問題。該算法直接一階段定位節(jié)點(diǎn)位置，通過節(jié)點(diǎn)的拓?fù)浼s束，解決翻轉(zhuǎn)現(xiàn)象。通過引入MCB算法中的采樣思想，隨機(jī)產(chǎn)生網(wǎng)絡(luò)拓?fù)浼s束下的未知節(jié)點(diǎn)的坐標(biāo)，引入自適應(yīng)的和聲保留概率和音調(diào)調(diào)節(jié)概率，從而提高搜索能力和定位精度。

1 定位問題描述

1.1 無線傳感器網(wǎng)絡(luò)中的翻轉(zhuǎn)現(xiàn)象

無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位中，當(dāng)節(jié)點(diǎn)密度較低時會導(dǎo)致翻轉(zhuǎn)現(xiàn)象,翻轉(zhuǎn)現(xiàn)象如圖1所示。圖1中，節(jié)點(diǎn)B，C，D和E是節(jié)點(diǎn)A的鄰居節(jié)點(diǎn)，且節(jié)點(diǎn)B，C，D和E幾乎是共線的，節(jié)點(diǎn)A的估計位置翻轉(zhuǎn)到A′的位置，變成節(jié)點(diǎn)F的鄰居節(jié)點(diǎn)。

圖1 翻轉(zhuǎn)現(xiàn)象

由于翻轉(zhuǎn)現(xiàn)象導(dǎo)致節(jié)點(diǎn)無法精確定位，造成較大的定位誤差。

1.2 適應(yīng)度函數(shù)定義

假設(shè)n個節(jié)點(diǎn)，包括m(m

dij=rij+eij,

(1)

Ni={j∈1,…,n,j≠i:rij≤R},

(2)

(3)

(4)

(5)

2 自適應(yīng)和聲搜索定位模型

2.1MCB待定位節(jié)點(diǎn)初始化產(chǎn)生機(jī)制

采用MCB[6]算法中構(gòu)建錨盒和濾波的采樣思想，產(chǎn)生待定位節(jié)點(diǎn)的初始化坐標(biāo)。采用待定位節(jié)點(diǎn)的一跳、兩跳和三跳鄰居錨節(jié)點(diǎn)以及部署區(qū)域T的信息進(jìn)行構(gòu)建錨盒,待定位節(jié)點(diǎn)i的錨盒表達(dá)式如式(6)

Boxi=

(6)

(7)

式中 (xj,yj)為待定位節(jié)點(diǎn)i的Oi中鄰居錨節(jié)點(diǎn)j的坐標(biāo)，t為Oi中節(jié)點(diǎn)的總數(shù)；lij取值R，2R或3R，分別對應(yīng)待定位節(jié)點(diǎn)i的一跳、兩跳、三跳鄰居節(jié)點(diǎn)(xj,yj)。

采用錨盒和濾波產(chǎn)生待定位節(jié)點(diǎn)初始坐標(biāo)的過程，稱為采樣過程。待定位節(jié)點(diǎn)i的濾波條件[5～7]如式(8)所示

(8)

如果在錨盒內(nèi)隨機(jī)產(chǎn)生的節(jié)點(diǎn)坐標(biāo)滿足濾波條件，則采樣結(jié)束且產(chǎn)生的節(jié)點(diǎn)坐標(biāo)就是待定位節(jié)點(diǎn)的初始坐標(biāo)；否則，重新采樣。

2.2 自適應(yīng)和聲搜索優(yōu)化定位算法

2.2.1 標(biāo)準(zhǔn)和聲搜索算法

受音樂創(chuàng)作過程的啟發(fā)，Geem Z W等人[8～10]提出的一種啟發(fā)式全局搜索算法—和聲搜索算法。樂師們憑借記憶或記錄通過反復(fù)調(diào)整各樂器的音調(diào)，最終獲得一個優(yōu)美的和聲。優(yōu)化問題中的每個變量相當(dāng)于每個樂器的音調(diào)，解向量對應(yīng)于和聲，目標(biāo)函數(shù)全局最優(yōu)即優(yōu)美動聽的音樂。

和聲搜索算法可分為5個步驟[10,11]：

1)設(shè)定和聲搜索算法的基本參數(shù)：變量(音調(diào))的個數(shù)D；各變量(音調(diào))的取值范圍；解向量(和聲)記憶庫的大小HMS；解向量(和聲)保留概率HMCR；變量(音調(diào))調(diào)節(jié)概率PAR；最大迭代次數(shù)NI。

2)初始化解向量(和聲)記憶庫HM。

3)產(chǎn)生新解：每次根據(jù)HMCR，PAR和隨機(jī)選擇3個規(guī)則產(chǎn)生新解。

4)更新和聲記憶庫HM：若新解優(yōu)于記憶庫中最差解，則新解替換最差解，獲得新的和聲記憶庫。

5)判斷是否滿足終止條件，若不滿足，重復(fù)步驟(3)，(4);否則，終止迭代，輸出最優(yōu)解。

2.2.2 和聲保留概率和音調(diào)調(diào)節(jié)概率

進(jìn)化算法在進(jìn)化前期處于隨機(jī)搜索階段，難以得到有益的結(jié)果[11]，但在隨機(jī)搜索階段種群的分布寬廣是否充足對后續(xù)進(jìn)化結(jié)果的優(yōu)劣有重要影響。

一般而言，在前期種群分布越寬廣后續(xù)進(jìn)化結(jié)果越好。因此，和聲保留概率HMCR由小到大變化[12]，在優(yōu)化的前期，較小值有利于加強(qiáng)全局搜索能力，在和聲記憶庫外進(jìn)行搜索，拓寬種群的分布，減少后期陷入局部最優(yōu)，后期的較大值有利于對和聲記憶庫進(jìn)行充分搜索，找到最優(yōu)解。基于錨盒大小與部署區(qū)域大小的新的和聲保留概率HMCR為

HMCRi=HMCRmax-αgn·Ai/S,

(9)

式中HMCRmax為和聲保留概率的最大值，α為常數(shù)，滿足α∈[0,1]，gn為當(dāng)前迭代次數(shù)，S為部署區(qū)域面積，T=[0,1]×[0,1]?Z2時，S=1。Ai為待定位節(jié)點(diǎn)i的錨盒面積，Ai的表達(dá)式如式(10)所示

(10)

音調(diào)調(diào)節(jié)概率PAR的調(diào)節(jié)由小到大[13,14]，在優(yōu)化的前期，較小值有利于進(jìn)行全局搜索，后期的較大值有利于加強(qiáng)局部搜索能力，增加解的多樣性，避免陷入局部最優(yōu)。音調(diào)調(diào)節(jié)概率PAR[13,14]公式如式(11)

PAR=PARmin+(PARmax-PARmin)gn/NI,

(11)

式中PARmin,PARmax分別為音調(diào)調(diào)節(jié)概率的最小值和最大值，gn為當(dāng)前迭代次數(shù)，NI為最大迭代次數(shù)。

2.2.3 自適應(yīng)和聲搜索定位算法描述

算法的具體實現(xiàn)步驟如下：

1)初始化基本參數(shù)與和聲記憶庫HM

通過MCB待定位節(jié)點(diǎn)產(chǎn)生機(jī)制產(chǎn)生HMS個解，加入解向量(和聲)記憶庫。

2)產(chǎn)生新解

a.節(jié)點(diǎn)i的坐標(biāo)根據(jù)HMCRi在和聲記憶庫隨機(jī)選擇HMS個解中一個節(jié)點(diǎn)i的坐標(biāo)或在變量取值范圍內(nèi)通過MCB待定位節(jié)點(diǎn)產(chǎn)生機(jī)制產(chǎn)生。

b.當(dāng)節(jié)點(diǎn)i的坐標(biāo)在和聲記憶庫隨機(jī)選擇產(chǎn)生時，根據(jù)PAR對節(jié)點(diǎn)i的坐標(biāo)進(jìn)行局部擾動。

3)更新和聲記憶庫HM

若新解優(yōu)于記憶庫中最差解，則新解替換最差解，獲得新的和聲記憶庫。

4)判斷是否滿足終止條件，若不滿足，重復(fù)步驟(2)、步驟(3);否則，終止迭代，輸出最優(yōu)解。

3 仿真與分析

3.1 仿真與參數(shù)設(shè)置

SAL算法中的參數(shù)設(shè)置[5,8]為：初始溫度T0=0.1，終止溫度Tf=10-11，擾動次數(shù)P=10，Markov鏈長度系數(shù)Q=2,冷卻因子α=0.8，收縮因子β=0.94。HSL算法中的參數(shù)設(shè)置[4]為：和聲記憶庫的大小HMS=50，最大迭代次數(shù)I=2000，和聲保留概率HMCR=90 %，音調(diào)調(diào)節(jié)概率PAR=1 %，隨機(jī)選擇概率PSR=1 %。本文算法中的參數(shù)設(shè)置為：和聲記憶庫的大小HMS=50，最大和聲保留概率HMCRmax=99.44 %，最大音調(diào)調(diào)節(jié)概率PARmax=99.44 %，最小音調(diào)調(diào)節(jié)概率PARmin=0.56 %，最大迭代次數(shù)NI=105。

3.2 仿真結(jié)果與分析

為了評價算法的定位性能，采用標(biāo)準(zhǔn)定位誤差(NLE)，公式如式(12)

(12)

1)定位精確度

表1 定位算法性能指標(biāo)

表1所示仿真結(jié)果為通信半徑R分別為0.13,0.15,0.17 m時不同場景下， SAL算法、HSL算法和本文算法均通過20次仿真結(jié)果的標(biāo)準(zhǔn)定位誤差值的平均值、最小值和標(biāo)準(zhǔn)差。在所有仿真場景中，從參數(shù)設(shè)置中可知，本文算法的適應(yīng)度函數(shù)計算次數(shù)為NI=105，HSL算法的適應(yīng)度函數(shù)計算次數(shù)[4]為105，SAL算法的平均適應(yīng)度函數(shù)計算次數(shù)[5,8]為7.1×105。從表1可以看出：本文算法標(biāo)準(zhǔn)定位誤差值的平均值比SAL算法和HSL算法更小，本文算法標(biāo)準(zhǔn)定位誤差值的標(biāo)準(zhǔn)差同樣比SAL算法和HSL算法更小，即本文算法定位精度一致性較好，與適應(yīng)度函數(shù)計算次數(shù)相同的HSL算法比，本文算法標(biāo)準(zhǔn)定位誤差值的最小值方面均優(yōu)于HSL算法，與適應(yīng)度函數(shù)計算次數(shù)較大的SAL算法比，通信半徑較小時，本文算法在標(biāo)準(zhǔn)定位誤差值的最小值方面優(yōu)于SAL算法。本文算法總體上提高了定位精度。

2)翻轉(zhuǎn)現(xiàn)象

圖2是本文算法在通信半徑R=0.15 m時的定位效果圖，圖3是SAL算法同樣在通信半徑R=0.15 m時第一階段的定位效果圖，從2圖和圖3對比中可以看出：SAL算法在R=0.15 m時第一階段節(jié)點(diǎn)定位存在較多翻轉(zhuǎn)現(xiàn)象，如圖3中右下角的一些節(jié)點(diǎn)，且由于節(jié)點(diǎn)的翻轉(zhuǎn)導(dǎo)致其他節(jié)點(diǎn)無法精確定位。本文算法在R=0.15 m時有效解決了定位的翻轉(zhuǎn)現(xiàn)象，實現(xiàn)節(jié)點(diǎn)精確定位。

圖2 本文算法在R=0.15 m時定位效果

圖3 SAL算法在R=0.15 m時第一階段定位效果

4 結(jié)束語

本文提出了一種基于MCB的自適應(yīng)和聲搜索定位算法，該算法能夠有效地解決無線傳感器網(wǎng)絡(luò)錨節(jié)點(diǎn)稀疏的節(jié)點(diǎn)定位問題，解決翻轉(zhuǎn)現(xiàn)象。仿真結(jié)果表明:本文算法能夠提高定位精度和定位精度一致性，該算法在定位精度和計算量方面優(yōu)于SAL與HSL算法。

[1] 孫子文,王鑫雨,白 勇，等.基于信度和早熟檢驗的混沌粒子群優(yōu)化定位算法[J].傳感器與微系統(tǒng),2013,32(9):129-133.

[2] Kannan A A,Mao G,Vucetic B.Simulated annealing-based wireless sensor networks localization with flip ambiguity mitigation[C]∥IEEE Vehicular Technology Conference(VTC),Melbourne:IEEE,2006:1022-1026.

[3] Kannan A A,Fidan B,Mao G.Analysis of flip ambiguities for robust sensor network localization[J].IEEE Trans Veh Technol,2010,59(4):2057-2070.

[4] Manjarres D,Del Ser J,Gil-Lopez S,et al.On the application of a hybrid harmony search algorithm to node localization in anchor-based wireless sensor networks[C]∥Intelligent Systems Design and Applications (ISDA),Cordoba:IEEE,2011:1014-1019.

[5] Baggio A,Langendon K.Monte Carlo localization for mobile wireless sensor networks[J].Ad Hoc Networks,2008,6(5):718-733.

[6] Hu L X,Evans D.Localization for mobile sensor networks[C]∥ACM MobiCom’04,Philadelphia:ACM SIGMobile,2004:45-57.

[7] Vecchio M,López-Valcarce R,Marcelloni F.A two-objective evolutionary approach based on topological constraints for node loca-lization in wireless sensor networks[J].Applied Soft Computing,2012,12(7):1891-1901.

[8] Geem Z W,Kim J H,Loganathan G V.A new heuristic optimization algorithm:Harmony search[J].Simulation,2001,76(2):60-68.

[9] Geem Z W.Music-inspired harmony search algorithm:Theory and applications[M].Berlin:Springer,2009.

[10] 雍龍泉.和聲搜索算法研究進(jìn)展[J].計算機(jī)系統(tǒng)應(yīng)用,2011,20(7):244-248.

[11] 喬 英,高岳林,江巧永.改進(jìn)的多目標(biāo)和聲搜索算法[J].計算機(jī)工程,2012,38(18):144-146.

[12] Xiang W I,An M Q,Li Y Z,et al.An improved global-best harmony search algorithm for faster optimization[J].Expert Systems with Applications,2014,41(13):5788-5803.

[13] Mahdavi M,Fesanghary M,Damangir E.An improved harmony search algorithm for solving optimization problems[J].Applied Mathematics and Computation,2007,188(2):1567-1579.

[14] 劉思遠(yuǎn)，柳景青.一種新的多目標(biāo)改進(jìn)和聲搜索優(yōu)化算法[J].計算機(jī)工程，2010,46(34):27-30.

A self-adaptive harmony search localization algorithm based on MCB*

SUN Chong, SUN Zi-wen

(School of Internet of Things Engineering,Jiangnan University,Wuxi 214122,China)

Aiming at problem of flip ambiguity and localization precision,a self-adaptive harmony search algorithm for wireless sensor networks(WSNs) node localization is proposed.Based on the Sampling Theory of Monte Carlo localization boxed (MCB),the coordinates of unknown nodes are generated randomly under the restriction of the network topology constraints,in order to improve the search ability and the localization precision,introduce adaptive harmony memory considering rate (HMCR) and pitch adjusting rate (PAR).Simulation results show that the algorithm can effectively address the flip ambiguity and improve the localization precision,and the algorithm outperforms,in terms of localization precision and computational complexity compared with otherst.

wireless sensor networks(WSNs); localization; flip ambiguity; self-adaptive; harmony search algorithm

2015—01—22

國家自然科學(xué)基金資助項目(61174032)；江蘇省自然科學(xué)基金面上項目(BK20131107)

10.13873/J.1000—9787(2015)04—0119—04

TP 393

A

1000—9787(2015)04—0119—04

孫 崇(1990-)，男，江蘇泗陽人，碩士研究生，研究方向為無線傳感器網(wǎng)絡(luò)。