陳 樹， 陸 穎

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

?

移動錨節(jié)點定位WSNs中無標(biāo)識節(jié)點算法研究*

陳 樹， 陸 穎

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

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

聚類算法； 接收信號強度； 圓環(huán)； 粒子群優(yōu)化算法

0 引 言

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

在上述節(jié)點定位算法中，未知節(jié)點個數(shù)和標(biāo)識(ID)已經(jīng)確定，但在實際節(jié)點定位的場景中，上述兩個參數(shù)是不確定的。

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

1 分裂聚類算法

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

信息熵作為檢測一個系統(tǒng)是否混亂的標(biāo)準(zhǔn)，應(yīng)用于物理、信息理論和數(shù)學(xué)等不同場所。當(dāng)信息熵用于評估聚類效果時，信息熵越小，說明同一聚類數(shù)據(jù)的相似度越高，聚類效果越好。

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

(1)

(2)

(3)

式中 θi={μi,Σi}，μi和Σi分別對應(yīng)第i個高斯分布函數(shù)的均值和協(xié)方差。

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

1.1 模型選擇準(zhǔn)則

(4)

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

1.2 算法步驟

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

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

2)依據(jù)信息熵準(zhǔn)則，計算每一高斯成分的Spi值，最小Spi值對應(yīng)的第i個高斯成分即為首個急需分裂的成分。

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

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

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

1.3 聚類效果

假定移動錨節(jié)點在每一駐留處收集的RSS總數(shù)N均為5 000，在某一駐留位置處未知節(jié)點實際發(fā)射的RSS=[-133,-120,-117,-115,-133]，且高斯成分權(quán)重都為0.2時?？紤]到高斯白噪聲的緣故，高斯混合樣本數(shù)據(jù)如圖1所示。圖1(a)和(b)分別對應(yīng)高斯白噪聲標(biāo)準(zhǔn)差σ為0.3和0.7時的混合樣本數(shù)據(jù)。

圖1 混合樣本數(shù)據(jù)Fig 1 Mixed sample data

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

圖2 聚類效果Fig 2 Clustering effect

2 粒子群尋優(yōu)搜索算法

在分裂聚類算法確定了未知節(jié)點個數(shù)，且在各駐留點準(zhǔn)確地獲得各RSS均值后，本文依據(jù)每一駐留點接收的最強RSS均值，進(jìn)行圓環(huán)搜索，再利用八鄰域極大值算法篩選出區(qū)域中圓環(huán)覆蓋個數(shù)較多的網(wǎng)格，最后用粒子群優(yōu)化(PSO)算法確定最優(yōu)未知節(jié)點坐標(biāo)。

2.1 圓環(huán)搜索

2.2 網(wǎng)格劃分

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

圖3 網(wǎng)格覆蓋數(shù)目Fig 3 Grid covered number

2.3 粒子群優(yōu)化算法

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

為了增加粒子的多樣性，在搜索過程中采用遺傳算法[11]的交叉思想，加入交叉因子，找尋確定節(jié)點個數(shù)的最優(yōu)節(jié)點坐標(biāo)。本文選用BIC準(zhǔn)則函數(shù)作為適度函數(shù)計算粒子的適應(yīng)度。

3 實驗仿真

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

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

4 結(jié) 論

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

[1] 夏心江,胡 鋼,王燁華.基于同心圓定位算法的改進(jìn)算法研究[J].計算機科學(xué),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] 張 原.基于高斯混合模型的無線傳感器網(wǎng)絡(luò)節(jié)點定位算法的研究[D].長春：吉林大學(xué),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ì)志成.基于量子行為粒子群優(yōu)化算法的定位技術(shù)研究[J].傳感器與微系統(tǒng),2012,31(5):58-61.

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

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

陳 樹(1969-)，男，江蘇淮安人，副教授，從事過程控制與優(yōu)化、現(xiàn)場總線及控制技術(shù)、無線傳感器網(wǎng)絡(luò)及通信等領(lǐng)域的研究工作。

陸 穎,通訊作者，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