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

孫 崇， 孫子文

(江南大學 物聯網工程學院，江蘇 無錫 214122)

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

孫 崇， 孫子文

(江南大學 物聯網工程學院，江蘇 無錫 214122)

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

無線傳感器網絡； 定位； 翻轉現象； 自適應； 和聲搜索算法

0 引 言

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

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

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

1 定位問題描述

1.1 無線傳感器網絡中的翻轉現象

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

圖1 翻轉現象

由于翻轉現象導致節點無法精確定位，造成較大的定位誤差。

1.2 適應度函數定義

假設n個節點，包括m(m

dij=rij+eij,

(1)

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

(2)

(3)

(4)

(5)

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

2.1MCB待定位節點初始化產生機制

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

Boxi=

(6)

(7)

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

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

(8)

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

2.2 自適應和聲搜索優化定位算法

2.2.1 標準和聲搜索算法

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

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

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

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

3)產生新解：每次根據HMCR，PAR和隨機選擇3個規則產生新解。

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

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

2.2.2 和聲保留概率和音調調節概率

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

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

HMCRi=HMCRmax-αgn·Ai/S,

(9)

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

(10)

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

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

(11)

式中PARmin,PARmax分別為音調調節概率的最小值和最大值，gn為當前迭代次數，NI為最大迭代次數。

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

算法的具體實現步驟如下：

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

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

2)產生新解

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

b.當節點i的坐標在和聲記憶庫隨機選擇產生時，根據PAR對節點i的坐標進行局部擾動。

3)更新和聲記憶庫HM

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

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

3 仿真與分析

3.1 仿真與參數設置

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

3.2 仿真結果與分析

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

(12)

1)定位精確度

表1 定位算法性能指標

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

2)翻轉現象

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

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

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

4 結束語

本文提出了一種基于MCB的自適應和聲搜索定位算法，該算法能夠有效地解決無線傳感器網絡錨節點稀疏的節點定位問題，解決翻轉現象。仿真結果表明:本文算法能夠提高定位精度和定位精度一致性，該算法在定位精度和計算量方面優于SAL與HSL算法。

[1] 孫子文,王鑫雨,白 勇，等.基于信度和早熟檢驗的混沌粒子群優化定位算法[J].傳感器與微系統,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].計算機系統應用,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] 劉思遠，柳景青.一種新的多目標改進和聲搜索優化算法[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-)，男，江蘇泗陽人，碩士研究生，研究方向為無線傳感器網絡。