基于高斯混合模型的無線傳感器網絡定位算法

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

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

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

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

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

1 高斯混合模型及其參數估計

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

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

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

輸入: 觀測數據y1,y2,…,yN, 高斯混合模型；

輸出： 高斯混合模型參數;

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

步驟2) E步： 根據當前模型參數, 計算分模型k對觀測數據yj的響應度為

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

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

2 算法設計

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

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

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

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

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

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

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

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

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

定位結果高斯混合模型建立的過程： 概率密度函數為

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

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

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

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

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

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

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

3 仿真實驗

(1)

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

仿真環境設置： 將錨節點隨機分布在100 m×100 m的監測區域中, 未知節點U位于坐標為(50,50)位置處, 假設未知節點能接收與15個錨節點的距離信息.

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

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

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

表1 當測距誤差服從不同分布時, 兩種算法定位誤差的仿真結果

由表1可見, 無論測距誤差ε服從均勻分布還是正態分布, 改進算法對于測距信息中不存在不準距離信息的情況也適用.當m增大時, 去除誤差大的前m個測距信息, 隨著m的增大, 改進算法所得的定位結果與真實定位結果更接近.

3.2m值對定位結果的影響

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

表2 當m取不同值時不同算法定位誤差的仿真結果

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

3.3K值對定位結果的影響

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

表3 當K=2,3時不同算法定位誤差的仿真結果

3.4 改進算法與三邊測量法的定位精度對比

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

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

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

3.5 DV-Hop算法的仿真分析

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

圖5為當通信半徑R=20,30 m時改進的DV-Hop算法與原DV-Hop算法的定位精度隨錨節點數目變化的情況. 由圖5可知： 通信半徑R=30 m大于R=20 m時的定位精度, 這是因為當通信半徑增大時, 未知節點可通信的錨節點數目增多, 即得到的測距信息更多, 當測距信息更多時可獲得的定位結果更精確； 改進DV-Hop定位算法的定位誤差遠小于原DV-Hop算法的定位誤差, 這是因為改進算法提高了定位精度, 使定位結果與真實定位結果更接近.

圖5 當R=20,30 m時不同算法定位精度隨錨節點個數的變化Fig.5 Positioning accuracy of different algorithms changes with number of anchor nodes when R=20,30 m

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