孫 崇， 孫子文

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

一種基于MCB的自適應和聲搜索定位算法*

孫 崇， 孫子文

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

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

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

0 引 言

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

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

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

1 定位問題描述

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

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

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

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

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

假設n個節(jié)點，包括m(m

dij=rij+eij,

(1)

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

(2)

(3)

(4)

(5)

2 自適應和聲搜索定位模型

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

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

Boxi=

(6)

(7)

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

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

(8)

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

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

2.2.1 標準和聲搜索算法

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

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

1)設定和聲搜索算法的基本參數(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和隨機選擇3個規(guī)則產(chǎn)生新解。

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

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

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

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

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

HMCRi=HMCRmax-αgn·Ai/S,

(9)

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

(10)

音調(diào)調(diào)節(jié)概率PAR的調(diào)節(jié)由小到大[13,14]，在優(yōu)化的前期，較小值有利于進行全局搜索，后期的較大值有利于加強局部搜索能力，增加解的多樣性，避免陷入局部最優(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為當前迭代次數(shù)，NI為最大迭代次數(shù)。

2.2.3 自適應和聲搜索定位算法描述

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

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

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

2)產(chǎn)生新解

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

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

3)更新和聲記憶庫HM

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

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

3 仿真與分析

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

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

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

(12)

1)定位精確度

表1 定位算法性能指標

表1所示仿真結(jié)果為通信半徑R分別為0.13,0.15,0.17 m時不同場景下， SAL算法、HSL算法和本文算法均通過20次仿真結(jié)果的標準定位誤差值的平均值、最小值和標準差。在所有仿真場景中，從參數(shù)設置中可知，本文算法的適應度函數(shù)計算次數(shù)為NI=105，HSL算法的適應度函數(shù)計算次數(shù)[4]為105，SAL算法的平均適應度函數(shù)計算次數(shù)[5,8]為7.1×105。從表1可以看出：本文算法標準定位誤差值的平均值比SAL算法和HSL算法更小，本文算法標準定位誤差值的標準差同樣比SAL算法和HSL算法更小，即本文算法定位精度一致性較好，與適應度函數(shù)計算次數(shù)相同的HSL算法比，本文算法標準定位誤差值的最小值方面均優(yōu)于HSL算法，與適應度函數(shù)計算次數(shù)較大的SAL算法比，通信半徑較小時，本文算法在標準定位誤差值的最小值方面優(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é)點定位存在較多翻轉(zhuǎn)現(xiàn)象，如圖3中右下角的一些節(jié)點，且由于節(jié)點的翻轉(zhuǎn)導致其他節(jié)點無法精確定位。本文算法在R=0.15 m時有效解決了定位的翻轉(zhuǎn)現(xiàn)象，實現(xiàn)節(jié)點精確定位。

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

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

4 結(jié)束語

本文提出了一種基于MCB的自適應和聲搜索定位算法，該算法能夠有效地解決無線傳感器網(wǎng)絡錨節(jié)點稀疏的節(jié)點定位問題，解決翻轉(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].計算機系統(tǒng)應用,2011,20(7):244-248.

[11] 喬 英,高岳林,江巧永.改進的多目標和聲搜索算法[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] 劉思遠，柳景青.一種新的多目標改進和聲搜索優(yōu)化算法[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

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

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

TP 393

A

1000—9787(2015)04—0119—04

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