移動(dòng)錨節(jié)點(diǎn)定位WSNs中無(wú)標(biāo)識(shí)節(jié)點(diǎn)算法研究*

陳 樹(shù)， 陸 穎

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

?

移動(dòng)錨節(jié)點(diǎn)定位WSNs中無(wú)標(biāo)識(shí)節(jié)點(diǎn)算法研究*

陳 樹(shù)， 陸 穎

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

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

聚類(lèi)算法； 接收信號(hào)強(qiáng)度； 圓環(huán)； 粒子群優(yōu)化算法

0 引 言

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

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

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

1 分裂聚類(lèi)算法

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

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

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

(1)

(2)

(3)

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

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

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

(4)

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

1.2 算法步驟

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

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

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

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

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

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

1.3 聚類(lèi)效果

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

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

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

圖2 聚類(lèi)效果Fig 2 Clustering effect

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

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

2.1 圓環(huán)搜索

2.2 網(wǎng)格劃分

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

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

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

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

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

3 實(shí)驗(yàn)仿真

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

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

4 結(jié) 論

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

[1] 夏心江,胡 鋼,王燁華.基于同心圓定位算法的改進(jìn)算法研究[J].計(jì)算機(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ú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法的研究[D].長(zhǎng)春：吉林大學(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] 溫 雅,李 國(guó),徐 晨.一種帶交叉因子的雙向?qū)?yōu)粒子群優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用研究,2013(1):82-85.

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

陳 樹(shù)(1969-)，男，江蘇淮安人，副教授，從事過(guò)程控制與優(yōu)化、現(xiàn)場(chǎng)總線及控制技術(shù)、無(wú)線傳感器網(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

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

TP 393

A

1000—9787(2016)12—0052—03