基于高斯混合模型的無(wú)線傳感器網(wǎng)絡(luò)定位算法

方 省, 羅 引, 曹 家, 徐 楠, 蔣水賓, 郝艷妮

(1. 天津大學(xué) 經(jīng)濟(jì)與管理學(xué)院, 天津 300072； 2. 中國(guó)科學(xué)院自動(dòng)化研究所, 北京 100190；3. 北京中科聞歌科技股份有限公司, 北京 100000)

隨著物聯(lián)網(wǎng)[1-3]和智慧城市建設(shè)的快速發(fā)展, 人們對(duì)位置服務(wù)需求與日俱增. 無(wú)線傳感器網(wǎng)絡(luò)(wireless sensor networks, WSNs)位于物聯(lián)網(wǎng)(internet of things, IoT)的感知層, 節(jié)點(diǎn)的定位信息是物聯(lián)網(wǎng)實(shí)現(xiàn)和普及的基礎(chǔ)和前提[4]. 距離信息可先由TOA[5],AOA[6],TDOA[7-8],RSSI[9],DV-Hop[10-11]和DV-distance[12]等技術(shù)計(jì)算得出, 然后通過三邊測(cè)量法等定位方法計(jì)算未知節(jié)點(diǎn)的位置. 但由于非視距問題[13-14](NLOS)、 定位環(huán)境及路徑傳播模型等因素影響, 測(cè)量的距離通常存在一定的誤差[15].

針對(duì)距離誤差對(duì)定位的影響, 目前已有許多方法可降低誤差的影響： 1) 根據(jù)定位環(huán)境改善路徑損耗模型參數(shù), 進(jìn)行實(shí)時(shí)估計(jì), 如文獻(xiàn)[16]提出了一種多模型選擇算法, 在分析路徑損耗模型統(tǒng)計(jì)特性的基礎(chǔ)上, 提出了一種進(jìn)行路徑損耗模型的量化方法, 文獻(xiàn)[17]提出了一種根據(jù)環(huán)境變化的RSS室內(nèi)定位方法； 2) 根據(jù)某些方法, 對(duì)于不同的測(cè)距信息給予不同的權(quán)值, 如文獻(xiàn)[18]引入了多個(gè)通信半徑以細(xì)分跳數(shù), 并推導(dǎo)了跳數(shù)隨半徑變化次數(shù)的公式, 通過校正加權(quán)值修正平均跳數(shù)距離對(duì)平均跳距離進(jìn)行加權(quán)處理, 文獻(xiàn)[19]采用最小均方誤差和逆距離加權(quán)法處理平均一跳距離； 3) 采用某種算法篩選出含有誤差的測(cè)距信息, 將其從距離信息中去除. 但在實(shí)際應(yīng)用中, 方法1)過于繁瑣和復(fù)雜, 方法2)效果不佳, 定位結(jié)果仍存在較大誤差.

基于此, 本文提出一種基于高斯混合模型的無(wú)線傳感器網(wǎng)絡(luò)定位算法, 以解決不準(zhǔn)確距離信息對(duì)定位結(jié)果的影響. 通過構(gòu)建混合高斯模型并分析篩選出誤差較大的距離信息, 將其從距離信息集合中剔除, 再對(duì)剩余的距離信息集合利用三邊測(cè)量法和加權(quán)算法計(jì)算未知節(jié)點(diǎn)的位置. 仿真實(shí)驗(yàn)結(jié)果表明, 利用改進(jìn)算法對(duì)距離信息處理, 剔除大誤差距離信息后, 所得到的定位結(jié)果更精準(zhǔn), 誤差更小.

1 高斯混合模型及其參數(shù)估計(jì)

本文使用高斯混合模型(Gaussian mixture model, GMM)擬合由三邊測(cè)量法[20-22]得到的定位結(jié)果集合, 通過模型分析, 找出遠(yuǎn)離中心的定位結(jié)果及定位這些位置所使用的距離信息, 并刪除出現(xiàn)次數(shù)較多的距離信息, 利用剩余的距離信息進(jìn)行位置估計(jì). 假設(shè)p(y|θ)為定位結(jié)果的概率密度函數(shù), 則

用高斯混合模型擬合定位結(jié)果就是將這些定位結(jié)果進(jìn)行分類, 各類別的概率密度函數(shù)可視為一個(gè)服從高斯分布的函數(shù).常用的高斯混合模型參數(shù)估計(jì)算法是最大似然估計(jì)和最大期望(EM)算法.

算法1高斯混合模型參數(shù)估計(jì)的EM算法.

輸入: 觀測(cè)數(shù)據(jù)y1,y2,…,yN, 高斯混合模型；

輸出： 高斯混合模型參數(shù);

步驟1) 取參數(shù)的初始值開始迭代;

步驟2) E步： 根據(jù)當(dāng)前模型參數(shù), 計(jì)算分模型k對(duì)觀測(cè)數(shù)據(jù)yj的響應(yīng)度為

步驟3) M步： 計(jì)算新一輪迭代的模型參數(shù)為

步驟4) 重復(fù)步驟2)和步驟3), 直到|p(y|θ)-p(y|θ)′|<ε, 其中p(y|θ)和p(y|θ)′為相鄰兩次迭代的結(jié)果, 即前后兩次迭代的結(jié)果小于一定程度即可終止迭代, 通常ε=10-5.

2 算法設(shè)計(jì)

為證明高斯混合模型無(wú)線傳感器網(wǎng)絡(luò)定位算法的合理性和有效性, 本文先介紹三邊測(cè)量法并分析不準(zhǔn)確距離信息對(duì)定位結(jié)果的影響, 以證明提出的算法可提高定位精度.

由于受環(huán)境和非視距問題(NLOS)等因素的影響, 測(cè)得的距離與真實(shí)距離通常有一定的誤差. 為全面分析不準(zhǔn)確信息對(duì)定位的影響, 分別從不準(zhǔn)距離信息的程度(即不準(zhǔn)距離信息所含誤差大小)及不準(zhǔn)距離信息多少(即不準(zhǔn)距離信息占總距離信息的比例)兩方面進(jìn)行分析和對(duì)比.

圖1為當(dāng)不準(zhǔn)距離信息個(gè)數(shù)m=2時(shí), 定位結(jié)果的誤差隨不準(zhǔn)距離信息程度變化的情況. 由圖1可見, 當(dāng)ε>10%時(shí), 隨著ε的增大, 定位誤差(RMSE)也隨著增大； 當(dāng)ε>30%時(shí), 由于距離信息所含誤差過大, 導(dǎo)致三邊測(cè)量定位誤差顯著上升.

圖1 不準(zhǔn)程度對(duì)三邊測(cè)量法的影響Fig.1 Effect of inaccuracy on trilateral measurement

不準(zhǔn)距離信息多少對(duì)定位結(jié)果的影響是指不準(zhǔn)距離信息占全部距離信息比例的不同會(huì)導(dǎo)致定位結(jié)果的不同.為方便, 本文用η表示不準(zhǔn)信息占全部距離信息的比例, 仿真場(chǎng)景設(shè)置與不準(zhǔn)距離程度的仿真條件相同.仿真條件設(shè)置： 不準(zhǔn)程度ε=5%,10%,20%,30%,m的取值范圍為0≤m≤6, 即η從0變化到40%, 由于當(dāng)η>40%時(shí), 測(cè)距信息集中有近1/2的距離信息不準(zhǔn)確, 此時(shí)定位系統(tǒng)性能非常差, 故對(duì)m>6的情況進(jìn)行仿真無(wú)意義.

圖2為不同測(cè)距誤差ε下不準(zhǔn)距離信息大小對(duì)三邊測(cè)量結(jié)果的影響.由圖2可見, 隨著不準(zhǔn)程度ε的增高, 定位誤差隨之增加； 在不準(zhǔn)程度ε確定的情況下, 隨著不準(zhǔn)距離信息數(shù)目的提高, 定位誤差也隨著增加； 剔除不準(zhǔn)距離信息后, 利用三邊測(cè)量法對(duì)剩余距離信息進(jìn)行定位, 定位結(jié)果較精確.因此, 不準(zhǔn)確距離信息增加了定位結(jié)果的誤差, 降低了定位的精準(zhǔn)度.從距離集合中剔除誤差大的距離信息, 利用剩余的距離信息進(jìn)行三邊測(cè)量法定位, 將會(huì)使定位結(jié)果更精確.

圖2 不同測(cè)距誤差ε下不準(zhǔn)距離信息大小對(duì)三邊測(cè)量結(jié)果的影響Fig.2 Effect of inaccurate distance information on trilateral measurement results under different ranging errors ε

三邊測(cè)量法需要3個(gè)距離信息, 當(dāng)距離信息集合中多數(shù)距離都在合理的誤差范圍內(nèi)時(shí), 通過三邊測(cè)量法得到的一系列定位結(jié)果之間的差距很小, 它們集中在一片密集的區(qū)域.但當(dāng)測(cè)距信息中含有較大誤差, 即通過三邊測(cè)量所對(duì)應(yīng)的3個(gè)距離信息只要有一個(gè)含有較大的誤差時(shí), 則所得到的位置將偏離該區(qū)域, 本文據(jù)此通過高斯混合模型分析對(duì)偏離密集區(qū)域的定位結(jié)果進(jìn)行分析, 剔出大誤差距離信息.

高斯混合模型中K值的選擇對(duì)定位精度和運(yùn)行時(shí)間有影響, 子高斯模型過多會(huì)延長(zhǎng)算法的運(yùn)行時(shí)間, 對(duì)位置樣本點(diǎn)A中樣本的分析將更詳細(xì), 定位精度有所提高； 子高斯模型過少會(huì)縮短算法的運(yùn)行時(shí)間, 但模型過于簡(jiǎn)單, 對(duì)于位置樣本點(diǎn)A中樣本的分析會(huì)粗糙, 定位精度低.通過仿真實(shí)驗(yàn)可知選擇K=2最合適.

定位結(jié)果高斯混合模型建立的過程： 概率密度函數(shù)為

基于上述分析, 本文利用高斯混合模型對(duì)三邊測(cè)量法得到的一系列定位結(jié)果建模, 并對(duì)建模結(jié)果進(jìn)行分析, 可知集合B和C所含的定位結(jié)果偏離真實(shí)定位結(jié)果, 根據(jù)一個(gè)定位結(jié)果中含有3個(gè)距離信息, 分析可得B和C所含有的距離信息有較大誤差, 再通過反向分析可得出含有誤差較大的距離信息.將誤差較大測(cè)距信息從距離信息集合中剔除, 利用剩余距離信息集合進(jìn)行定位分析和計(jì)算.該方法必須滿足已知位置節(jié)點(diǎn)數(shù)目必須超過6個(gè), 這樣通過三邊測(cè)量方法將會(huì)產(chǎn)生足夠多的定位結(jié)果樣本, 而錨節(jié)點(diǎn)多于6個(gè)的情況在應(yīng)用中是普遍現(xiàn)象[19].

加權(quán)定位算法表示為對(duì)定位集合A, 假設(shè)由任意3個(gè)節(jié)點(diǎn)通過三邊測(cè)量法得到的未知節(jié)點(diǎn)坐標(biāo)為(xn,yn), 其由di,dj,dk三個(gè)測(cè)距信息獲取, 針對(duì)定位集合A的加權(quán)定位算法[18]求得節(jié)點(diǎn)(x,y)為

基于高斯混合模型的定位算法步驟如下：

2) 根據(jù)高斯混合模型輸出的最終結(jié)果找出元素個(gè)數(shù)最少的子高斯模型φ2, 其含有的定位結(jié)果集合為B和距離φ1中心最遠(yuǎn)的定位結(jié)果集合C;

3) 找出集合B和C中定位結(jié)果所包含的點(diǎn), 由于每個(gè)點(diǎn)對(duì)應(yīng)著3個(gè)距離信息, 通過分析找出所對(duì)應(yīng)距離信息集合中出現(xiàn)頻率最高的前m個(gè)距離信息, 假設(shè)d1,d2,…,dm即為誤差較大的距離信息;

4) 對(duì)剩余的距離信息進(jìn)行三邊測(cè)量法, 得到一系列定位結(jié)果, 對(duì)其進(jìn)行高斯模型擬合, 得高斯模型的均值μ=(μx,μy), 對(duì)定位結(jié)果進(jìn)行加權(quán)定位, 用(x,y)表示;

本文取δ=0.5 m.閾值的設(shè)置使算法適應(yīng)性更強(qiáng), 若m設(shè)置過小, 則不能將不準(zhǔn)確距離信息全部剔除, 需通過估計(jì)位置與高斯模型中心的歐氏距離判斷是否需要繼續(xù)剔除不準(zhǔn)確信息, 使得出的定位精度更高, 與真實(shí)值的位置更接近.

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

(1)

3.1 不同測(cè)距誤差分布下算法的有效性

仿真環(huán)境設(shè)置： 將錨節(jié)點(diǎn)隨機(jī)分布在100 m×100 m的監(jiān)測(cè)區(qū)域中, 未知節(jié)點(diǎn)U位于坐標(biāo)為(50,50)位置處, 假設(shè)未知節(jié)點(diǎn)能接收與15個(gè)錨節(jié)點(diǎn)的距離信息.

在本文仿真場(chǎng)景中, 未知節(jié)點(diǎn)接收到的15個(gè)距離信息{d1,d2,…,d15}所包含的誤差εi(i=1,2,…,15)(當(dāng)ε>50%時(shí), 測(cè)距誤差較大, 對(duì)定位結(jié)果影響過大, 故仿真不予考慮)分別服從均勻分布和正態(tài)分布, 仿真結(jié)果如圖3所示.由圖3可見, 無(wú)論測(cè)距誤差服從均勻分布還是正態(tài)分布, 所得定位結(jié)果均較相近.從而驗(yàn)證了在不同測(cè)距誤差分布下本文算法都有效.

圖3 不同測(cè)距誤差分布下定位結(jié)果的對(duì)比Fig.3 Comparison of positioning results under different ranging error distributions

表1為計(jì)算中m分別取1,2,3, 高斯混合建模分析剔除誤差較大的1,2或3個(gè)信息(該仿真算法不包含基于高斯混合模型定位算法中的步驟5)進(jìn)行自適應(yīng)調(diào)整m值), 然后使用三邊測(cè)量法和加權(quán)算法求其定位結(jié)果.

表1 當(dāng)測(cè)距誤差服從不同分布時(shí), 兩種算法定位誤差的仿真結(jié)果

由表1可見, 無(wú)論測(cè)距誤差ε服從均勻分布還是正態(tài)分布, 改進(jìn)算法對(duì)于測(cè)距信息中不存在不準(zhǔn)距離信息的情況也適用.當(dāng)m增大時(shí), 去除誤差大的前m個(gè)測(cè)距信息, 隨著m的增大, 改進(jìn)算法所得的定位結(jié)果與真實(shí)定位結(jié)果更接近.

3.2m值對(duì)定位結(jié)果的影響

當(dāng)m設(shè)置過小時(shí), 算法會(huì)根據(jù)定位結(jié)果與聚類中心的歐氏距離進(jìn)行調(diào)節(jié), 其對(duì)定位結(jié)果的影響較小, 只需多次迭代花費(fèi)更多的時(shí)間； 如果m設(shè)置過大, 大于含有不準(zhǔn)距離信息的個(gè)數(shù)時(shí), 考慮是否會(huì)對(duì)定位結(jié)果產(chǎn)生影響.不失一般性, 仿真環(huán)境與3.1相同, 不準(zhǔn)確距離信息數(shù)目n=3,ε=20%, 分別取m=1,2,3,4,5, 然后使用三邊測(cè)量法和加權(quán)算法求其定位結(jié)果, 定位誤差仿真結(jié)果列于表2.

表2 當(dāng)m取不同值時(shí)不同算法定位誤差的仿真結(jié)果

由表2可見: 當(dāng)m=1,2,3時(shí), 定位結(jié)果非常接近, 驗(yàn)證了算法對(duì)于閾值δ設(shè)置的合理性; 當(dāng)m=4,5時(shí), 雖然大于不準(zhǔn)確距離信息的個(gè)數(shù), 但對(duì)于定位結(jié)果的影響較小, 誤差波動(dòng)不大.驗(yàn)證了在合理的取值范圍內(nèi),m的取值不會(huì)對(duì)定位結(jié)果有較大影響.

3.3K值對(duì)定位結(jié)果的影響

K值的大小將對(duì)定位精度和運(yùn)行時(shí)間產(chǎn)生影響, 為得出合適的K值進(jìn)行仿真對(duì)比. 仿真環(huán)境與3.1相同, 不準(zhǔn)確距離信息數(shù)目n=3,ε=20%.當(dāng)K值分別取2,3時(shí), 計(jì)算其RMSE, 結(jié)果列于表3. 由表3可見, 當(dāng)K=3時(shí), 定位誤差比K=2時(shí)小, 但其波動(dòng)浮動(dòng)較小, 而運(yùn)行時(shí)間延長(zhǎng)浮動(dòng)較大, 權(quán)衡兩者對(duì)定位的影響, 本文選擇K=2.

表3 當(dāng)K=2,3時(shí)不同算法定位誤差的仿真結(jié)果

3.4 改進(jìn)算法與三邊測(cè)量法的定位精度對(duì)比

針對(duì)在不同誤差ε和不同大誤差測(cè)距信息數(shù)目的情況下, 為驗(yàn)證改進(jìn)算法的有效性和實(shí)用性, 進(jìn)行改進(jìn)定位算法和三邊測(cè)量法所得定位誤差的仿真對(duì)比, 結(jié)果如圖4所示. 仿真環(huán)境與3.1相同.

圖4 定位誤差隨不準(zhǔn)距離信息個(gè)數(shù)的變化Fig.4 Positioning errors vary with number of inaccurate distance information

由圖4可見： 隨著測(cè)距誤差增大, 大誤差測(cè)距信息數(shù)目增多, 三邊測(cè)量定位法受到的影響越大, 性能下降, 導(dǎo)致定位誤差越大, 精度更低; 改進(jìn)定位算法所得定位結(jié)果基本不隨大誤差測(cè)距信息的增大而增大, 在測(cè)距誤差逐漸增大和不準(zhǔn)測(cè)距信息數(shù)目逐漸增多的情況下, 改進(jìn)定位算法剔除大誤差測(cè)距信息后, 定位誤差有明顯減少, 提高了定位精度.

3.5 DV-Hop算法的仿真分析

為驗(yàn)證改進(jìn)定位算法應(yīng)用的廣泛性和合理性, 將改進(jìn)定位算法應(yīng)用到DV-Hop算法中, 對(duì)改進(jìn)DV-Hop算法與原始DV-Hop算法所得定位誤差進(jìn)行對(duì)比, 結(jié)果如圖5所示. 仿真環(huán)境參數(shù)設(shè)置為： 在80 m×80 m的區(qū)域上布置80個(gè)節(jié)點(diǎn), 通信半徑分別為20 m和30 m, 其中K=2, 考慮到錨節(jié)點(diǎn)數(shù)目的不同, 當(dāng)錨節(jié)點(diǎn)數(shù)目小于10時(shí)m設(shè)置為2, 當(dāng)錨節(jié)點(diǎn)數(shù)目大于10小于20時(shí)m設(shè)置為3, 當(dāng)錨節(jié)點(diǎn)數(shù)目大于20小于30時(shí)m設(shè)置為4, 當(dāng)錨節(jié)點(diǎn)數(shù)目大于30小于40時(shí)m設(shè)置為4.

圖5為當(dāng)通信半徑R=20,30 m時(shí)改進(jìn)的DV-Hop算法與原DV-Hop算法的定位精度隨錨節(jié)點(diǎn)數(shù)目變化的情況. 由圖5可知： 通信半徑R=30 m大于R=20 m時(shí)的定位精度, 這是因?yàn)楫?dāng)通信半徑增大時(shí), 未知節(jié)點(diǎn)可通信的錨節(jié)點(diǎn)數(shù)目增多, 即得到的測(cè)距信息更多, 當(dāng)測(cè)距信息更多時(shí)可獲得的定位結(jié)果更精確； 改進(jìn)DV-Hop定位算法的定位誤差遠(yuǎn)小于原DV-Hop算法的定位誤差, 這是因?yàn)楦倪M(jìn)算法提高了定位精度, 使定位結(jié)果與真實(shí)定位結(jié)果更接近.

圖5 當(dāng)R=20,30 m時(shí)不同算法定位精度隨錨節(jié)點(diǎn)個(gè)數(shù)的變化Fig.5 Positioning accuracy of different algorithms changes with number of anchor nodes when R=20,30 m

綜上所述, 本文在分析不準(zhǔn)確距離信息對(duì)定位影響的基礎(chǔ)上, 結(jié)合高斯混合模型提出了一種提高定位精度的定位算法. 該算法通過高斯混合模型擬合定位結(jié)果, 剔除大誤差測(cè)距信息, 結(jié)合三邊測(cè)量定位法對(duì)剩余的距離信息集合得到定位估計(jì)集合, 再對(duì)定位估計(jì)集合進(jìn)行加權(quán)處理, 得到離未知節(jié)點(diǎn)真實(shí)位置較近的坐標(biāo). 仿真結(jié)果表明, 改進(jìn)算法削弱了不準(zhǔn)測(cè)距信息對(duì)定位結(jié)果的影響, 定位精度有顯著提高, 與真實(shí)位置更接近.