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

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

隨著物聯(lián)網(wǎng)[1-3]和智慧城市建設(shè)的快速發(fā)展, 人們對位置服務(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ù)計算得出, 然后通過三邊測量法等定位方法計算未知節(jié)點(diǎn)的位置. 但由于非視距問題[13-14](NLOS)、 定位環(huán)境及路徑傳播模型等因素影響, 測量的距離通常存在一定的誤差[15].

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

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

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

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

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

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

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

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

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

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

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

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

2 算法設(shè)計

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.5 DV-Hop算法的仿真分析

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

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

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

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