移動錨節點定位WSNs中無標識節點算法研究*

陳 樹， 陸 穎

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

?

移動錨節點定位WSNs中無標識節點算法研究*

陳 樹， 陸 穎

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

針對無線傳感器網絡(WSNs)無標識節點的定位問題，引入移動錨節點收集節點的接收信號強度(RSS)數據序列，利用無監督的聚類算法分析數據確定節點個數，依據錨節點運行的不同駐點，提取最強RSS信號進行圓環交叉搜索并標識覆蓋網格重疊區域，再利用極大值(EM)算法篩選出可能含有未知節點的區域，最后用改進的粒子群優化(PSO)算法最終確定符合聚類個數的最優未知節點坐標。實驗仿真結果表明:該算法在未知節點稀疏分布情況下，可以準確地估算未知節點個數和位置坐標。

聚類算法； 接收信號強度； 圓環； 粒子群優化算法

0 引 言

無線傳感器網絡(WSNs)節點定位技術是無線傳感器網絡應用研究的基礎。夏心江在文獻[1]中運用多次劃分圓環半徑縮小未知節點估算區域的方法提高多靜態錨節點對未知節點的定位精度。在三維空間中文獻[2]利用裝配全球定位系統(GPS)接收器的單個移動錨節點按模型飛行，實現了對未知節點的定位，并大大降低了定位誤差。文獻[3]依據移動錨節點在不同一直線上的3個駐留處接收的接收信號強度(RSS)值進行圓環交叉，圓環覆蓋個數達到3個的網格區域對應節點估算位置。張原在文獻[4]中提出的基于高斯混合模型的期望最大化網格定位算法(Grid-EM-LEGMM)，采用移動錨節點估算了未知節點個數和未知節點坐標。

在上述節點定位算法中，未知節點個數和標識(ID)已經確定，但在實際節點定位的場景中，上述兩個參數是不確定的。

就無標識節點定位而言，移動錨節點在每一駐留位置處接收未知節點發射的混合RSS信號，錨節點對每一駐留位置處接收到的混合RSS信號進行聚類處理，處理效果直接影響后繼節點個數的確定和定位的準確性。區別于以上錨節點通信范圍有限的特性，本文限定移動錨節點通信半徑，利用分裂極大值EM算法聚類接收到的混合信號強度，精確估算未知節點個數并獲取每一駐留位置處最強RSS。隨后依據每一駐留位置處獲得的最強RSS值進行圓環交叉并標識覆蓋網格重疊區域，再利用八鄰域極大值算法篩選出圓環覆蓋個數較多的網格，最后用改進的粒子群優化(PSO)算法剔除無效交叉區域，獲取對應確定節點個數的最佳位置坐標。

1 分裂聚類算法

考慮到未知節點與移動錨節點之間實際傳播信號的多路徑反射特性，本文采用對數距離路徑損耗無線信道模型。鑒于移動錨節點在每一駐留位置處接收到的RSS混合序列服從高斯混合分布[4]，而EM算法[5]可以很好地對高斯混合模型進行參數估計。但是，EM算法的聚類模型個數往往需要事先確定，且聚類過程中被估參數容易陷入局部最優。然而，在實際定位場景中未知節點個數是不確定的，為此，本文在EM算法中引入信息熵來反映這種不確定程度。依據信息熵準則動態地分裂高斯成分，獲取最優聚類個數(未知節點個數)和RSS均值。

信息熵作為檢測一個系統是否混亂的標準，應用于物理、信息理論和數學等不同場所。當信息熵用于評估聚類效果時，信息熵越小，說明同一聚類數據的相似度越高，聚類效果越好。

此外，文獻[6]指出在同方差的變量中高斯成分Y有最大熵，且理論上的最大熵表示為

(1)

(2)

(3)

式中 θi={μi,Σi}，μi和Σi分別對應第i個高斯分布函數的均值和協方差。

本文使用信息熵與最大信息熵之間的比值Spi表示混合模型中第i個高斯成分被估概率密度與實際概率密度之間的吻合程度。

1.1 模型選擇準則

(4)

式中 N為數據量總數，其中，第一部分代表似然值，另一部分代表懲罰值。似然值用于很好地擬合樣本數據，而懲罰值用于阻止k值的過度增長[8]。k為待估計聚類個數，若待估計的未知節點數量為M，且需要估計未知節點的二維位置，那么k=2M。在計算過程中，最小BIC對應的k值為最優k值。

1.2 算法步驟

該算法選用BIC準則作為模型選擇函數。假定模型個數從二開始聚類分裂，依據信息熵準則動態分裂高斯成分。具體算法步驟歸納如下：

1)設置起始高斯成分個數k=2，運用K均值算法估算所得的均值，方差和權重作為EM算法中的初始值進行EM算法聚類。

2)依據信息熵準則，計算每一高斯成分的Spi值，最小Spi值對應的第i個高斯成分即為首個急需分裂的成分。

3)使用K均值算法對需分裂的高斯成分進行參數估計，估計參數值作為EM算法中的初始值。

4)成分個數遞加，通過EM算法估算完整數據集的參數值。

5)計算每一次分裂后對應的BIC值，若分裂后BIC值較分裂前小，則跳回至步驟(2)繼續分裂；否則，算法終止，輸出最終確定的k值和對應參數值。

1.3 聚類效果

假定移動錨節點在每一駐留處收集的RSS總數N均為5 000，在某一駐留位置處未知節點實際發射的RSS=[-133,-120,-117,-115,-133]，且高斯成分權重都為0.2時。考慮到高斯白噪聲的緣故，高斯混合樣本數據如圖1所示。圖1(a)和(b)分別對應高斯白噪聲標準差σ為0.3和0.7時的混合樣本數據。

圖1 混合樣本數據Fig 1 Mixed sample data

圖2對應標準差為0.3和0.7時高斯混合序列的最終分裂聚類效果，分裂聚類后的高斯成分最終很好地相互區分開，貼近真實樣本數據。因此，分裂聚類算法在標準差較小和較大情況下都能很好地確定未知節點個數和RSS均值。考慮到移動過程中存在錨節點與若干未知節點距離相近的概率因素，本文選取移動聚類后出現次數最多的個數為未知節點個數。

圖2 聚類效果Fig 2 Clustering effect

2 粒子群尋優搜索算法

在分裂聚類算法確定了未知節點個數，且在各駐留點準確地獲得各RSS均值后，本文依據每一駐留點接收的最強RSS均值，進行圓環搜索，再利用八鄰域極大值算法篩選出區域中圓環覆蓋個數較多的網格，最后用粒子群優化(PSO)算法確定最優未知節點坐標。

2.1 圓環搜索

2.2 網格劃分

本文對覆蓋區域進行網格劃分，錨節點在移動采集點通過圓環覆蓋個數標識對應網格數值。如圖3所示，三部分圓環在某區域內交叉，數字3意味著該網格被3個圓環所覆蓋，實際定位過程中網格被多個圓環覆蓋，因此，較多覆蓋數的網格即為區域未知節點較有可能的位置。圓環交叉搜索網格覆蓋數目較多的區域，再采用八鄰域法獲取二維矩陣中的局部極大值，刪除掉大量無效重疊區域，篩選出區域極值較大的網格。最終使用粒子群算法挑選出最符合聚類未知節點個數且適應度最好的網格，取網格質心位置為未知節點坐標。

圖3 網格覆蓋數目Fig 3 Grid covered number

2.3 粒子群優化算法

標準粒子群算法是一種基于個體極值和適應度的算法，通過迭代搜索至最優解。鑒于標準粒子群算法[9]迭代尋優速度快，可調參數少，而得到廣泛應用。針對其易陷入局部最優的缺陷，本文在標準粒子群算法中引入交叉因子[10]來規避局部極值。

為了增加粒子的多樣性，在搜索過程中采用遺傳算法[11]的交叉思想，加入交叉因子，找尋確定節點個數的最優節點坐標。本文選用BIC準則函數作為適度函數計算粒子的適應度。

3 實驗仿真

假設區域中部署多個未知節點，未知節點全部分散在300 m×300 m的區域中，發射信號強度Pt=10 dB，在距離發射節點1 m處路徑損耗強度Pt0=45.6 dB，駐留位置處收集到的混合RSS序列總數N都為5 000，取邊長為0.4 m的網格進行區域劃分。通信半徑足夠大的移動錨節點按預先設定的軌跡移動，且在其中的180個采集位置處接收相同數目的RSS序列時，該算法在Matlab中的實驗仿真結果，如圖4所示。

圖4 節點定位效果示意圖Fig 4 Diagram of node localization effect

4 結 論

本文提出的聚類圓環搜索定位算法很好地解決了無標識環境中未知節點的定位問題。實驗仿真結果表明:該算法定位誤差較低，具有很好的可行性。

[1] 夏心江,胡 鋼,王燁華.基于同心圓定位算法的改進算法研究[J].計算機科學,2012(6):68-71.

[2] Fu Y J,Lee T H,Chang L H,et al.A single mobile anchor localization scheme for wireless sensor networks[C]∥IEEE International Conference on High Performance Computing and Communication & IEEE International Conference on Embedded Software and Systems,IEEE,2011:946-950.

[3] Chen Y S,Ting Y J,Ke C H,et al.Efficient localization scheme with ring overlapping by utilizing mobile anchors in wireless sensor networks[J].ACM Transactions on Embedded Computing Systems,2013,12(2):112.

[4] 張 原.基于高斯混合模型的無線傳感器網絡節點定位算法的研究[D].長春：吉林大學,2010.

[5] Mistry D,Joshi S,Agrawal N.A novel jitter separation method based on Gaussian mixture model[C]∥2015 International Conference on Pervasive Computing(ICPC),IEEE,2015:1-4.[6] Li Y,Li L.A novel split and merge EM algorithm for Gaussian mixture model[C]∥2009 the Fifth International Conference on Natural Computation，IEEE Computer Society,2009:479-483.

[7] Hirose K,Kawano S,Konishi S,et al.Bayesian information criterion and selection of the number of factors in factor analysis mo-dels[J].J Data Sci,2011(2):243-259.

[8] Wu J,Hamdan H.Model choice for binned-EM algorithms of fourteen parsimonious Gaussian mixture models by BIC and ICL criteria[C]∥2013 International Conference on System Science and Engineering(ICSSE),IEEE,2013:351-356.

[9] 趙 吉,紀志成.基于量子行為粒子群優化算法的定位技術研究[J].傳感器與微系統,2012,31(5):58-61.

[10] 溫 雅,李 國,徐 晨.一種帶交叉因子的雙向尋優粒子群優化算法[J].計算機應用研究,2013(1):82-85.

[11] 鄧 力.基于遺傳算法WSNs節點定位算法研究[J].計算機仿真,2011,28(9):161-164.

陳 樹(1969-)，男，江蘇淮安人，副教授，從事過程控制與優化、現場總線及控制技術、無線傳感器網絡及通信等領域的研究工作。

陸 穎,通訊作者，E—mail：995143615@qq.com。

Research on algorithm of non-identity node localization with mobile anchor node in WSNs*

CHEN Shu， LU Ying

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

Aiming at localization problem of nodes without identification in wireless sensor networks(WSNs),introduce received signal strength(RSS) data sequence which gathered by mobile anchor node,use unsupervised clustering algorithm to determine the number of unknown nodes,and extract the strongest RSS signal achieved by anchor node at different stationary point,to carry out ring crossing search for identifying the grid overlapping area.Then, pick out the area which may contain unknown nodes by using the maximum value algorithm.Finally,the improved particle swarm optimization(PSO)algorithm determines the unknown nodes' coordinates which is most consistent with the number of clusters.Simulation results show that the algorithm can accurately estimates the number and localization of unknown nodes in the sparse environment.

clustering algorithm; received signal strength(RSS); ring; particle swarm optimization(PSO)algorithm

10.13873/J.1000—9787(2016)12—0052—03

2016—01—06

江蘇省六大人才高峰基金資助項目(2012—WLW—006)

TP 393

A

1000—9787(2016)12—0052—03