改進動態K 的WKNN 的室內定位方法

敬振宇，熊興中，張 維，謝 偉

（1.四川輕化工大學 人工智能四川省重點實驗室，四川 宜賓 644000；2.四川信息職業技術學院，四川 廣元 628000）

0 引 言

室內定位服務（Indoor Positioning Service，IPS），作為一種基于位置的服務，它主要利用無線通信、射頻識別、慣性導航等技術獲取移動端的位置信息，完成對室內環境中人員或物體的位置確定[1]。隨著射頻技術和無線通信技術的快速發展，室內定位服務在日常生活的重要性愈加凸顯。WiFi 的普及以及5G 技術等基站的部署[2]，使得快速傳輸無線數據成為了可能，加之室內定位與人們實際生活息息相關，擁有巨大的商業價值和應用潛力，這些都推動了室內定位的發展。近些年來室內無線定位技術也取得了一些成果，技術不斷推陳出新，定位精度也越來越高；但從整體來看，室內定位如果應用于實際環境中，實現一定精度的定位仍是巨大挑戰。

無線室內定位技術根據信號類型可分為A-GPS 室內定位[3]、行人航位推算室內定位[4]、射頻識別室內定位[5]和WiFi 室內定位[6]。其中，隨著無線網絡的普及，絕大部分室內環境都可利用WiFi 實現定位，并且WiFi 模塊的硬件成本較低，可被集成到各種電子設備中，為室內定位打下硬件基礎。因此，WiFi 定位在室內定位領域中具有舉足輕重的地位。許多研究學者投身于WiFi室內定位技術研究和相關應用，并且提出了多種解決方案?？傮w來說，WiFi 室內定位方法一般分為兩種，一種基于理論模型的信號強度定位，另一種則是基于指紋庫匹配的定位。由于理論模型的應用受環境限制較大，大多數WiFi 室內定位系統都選擇指紋庫方式[7]。在指紋庫定位中，加權K-最近鄰（Weighted K-nearest Neighbor，WKNN）算法[8]應用最為廣泛。該方法利用在線階段得到多個匹配點的位置信息，對獲取的位置信息進行權重計算，最終得到估計點的位置坐標。但實際中K值的確定并不簡單，因此大部分文獻都選擇固定K值或者選取多個K值進行對比。文獻[9]中將K值固定為4；文獻[10-11]中將K值固定為3；文獻[12]中K值固定為4；文獻[13]中選擇了多個K值并對比不同K值下的定位情況；文獻[14]在傳統的WKNN 算法上進行改進，并對改進后的算法在不同K值下進行對比；RADAR[15]對WKNN 中的不同K值對比，并分析不同K值對定位精度的影響，得出結論：定位精度隨著K值的增大而變高，但當K值達到某個值后，定位精度會隨著K值的增加而降低。

上述文章中，都需要對不同K值對比才能確定一個較好的K值。但在實際環境中，同一環境下也可能由于參考點布設位置差異、測試點高度不同等，同一K值的定位效果并不一致。如果K固定一個較大值，可能會將較遠的參考點接納進來，對最終結果產生影響；若K固定一個較小值，可能會使有貢獻點被忽略，同樣也對結果產生影響。因此，不能選擇同一固定K值用于定位，需要動態選擇適當的K值。文獻[16]中提出EWKNN（Enhanced Weighed K-Nearest Neighbor），即動態自適應K，采用歐氏距離的均值動態確定K的取值。文獻[17]在其基礎上增加了對K值為1 的判斷和處理。雖然提出的自適應動態K的方法確實提升了定位精度，但仍舊存在歐氏距離的均值并不能夠最優表示閾值的問題。文獻[16]中，通過RT進行初步的參考點篩選結果對K的獲取影響較大，從而影響最終的定位精度；文獻[17]在此基礎上提出“多雷達搜索策略”的方法確定K值，在某種程度上降低了文獻[16]中RT的影響，但整體定位時間大量增加、性能較差，并且文獻[16]未曾考慮在線階段僅匹配一個的情況，而是直接考慮K≥2 的情況，反而可能會引入誤差。

本文針對上述問題提出了一種改進的自適應動態K的WKNN 室內定位方法。首先通過高斯濾波優化離線指紋庫，接著，在線階段采用KNN 匹配得到當前匹配點后，利用加入改進泰勒級數展開法濾除誤差較大的匹配點，從而實現對K值的確定，最終得出定位結果。本文提出的算法較傳統的EWKNN 方法和文獻[17]中的方法性能更優，在定位精度上也高于前者，而且整體定位耗時較短。

1 定位算法分析

1.1 WKNN 算法

指紋定位算法是基于信號強度和距離一一對應的室內定位方法，工作主要可以分為前期建立指紋庫和匹配階段。首先在室內環境部署指紋點，根據各指紋點接收到的信號強度和當前的物理位置信息構建位置指紋數據庫。在第二階段，實時獲得待測點的RSSI 值，將此信息與位置指紋數據庫中的指紋數據依次對比，選擇與其特征值最接近的指紋點作為待測點的估計位置。傳統的位置指紋算法常用最近鄰法對待測點信息和數據庫指紋錄入，但NN 算法將與指紋點特征信息最接近的點作為待測點的估計信息。由于無線信號的傳播特性，該算法容易受噪聲干擾，而K 近鄰算法在NN 算法的基礎上進行改進，相比NN 算法只選擇與待測點特征屬性最接近的指紋點作為待測點的估計信息，提出了選擇K個與待測點特征屬性最接近的指紋點，并將K個指紋點特征信息的均值作為待測點的估計信息。隨著位置指紋算法的發展與改進，在KNN 的基礎上引入了權重思想，將K 近鄰點的特征值加權平均作為待測點的估計信息。改進后的加權K 近鄰算法較傳統的指紋定位算法在定位精度及穩定性方面都有大幅提高。如式（1）所示：

式中：xi是第i個點的橫坐標；yi是第i個點的縱坐標；k為匹配點的個數；x,y是待測點的橫縱坐標；ωi為第i個點的權值[18]。

1.2 泰勒級數展開法

泰勒級數展開法是一種迭代算法，一般用于非線性方程的最優估計問題。主要步驟是在給定的初始值處進行泰勒展開，將錨節點和未知節點之間的測量距離和當前計算出的距離的差值，作為計算未知節點坐標校正量的依據。具體過程如下：定位算法中存在N個確定位置的已知點，坐標分別為(x1,y1)，(x2,y2)，…，(xi,yi)，而待定位節點的真實位置為(x,y)。而測得待定位節點到已知點的實際距離分別為d1，d2，…，di，到已知點的測量距離分別為：D1，D2，…，Di。此時有Di=di+εi，εi為測量誤差。假設未知點的初始估計坐標為(x0,y0)，此時有下述等式：

估計值與真實值有如下關系：

對上式在估計初值(x0,y0)處泰勒展開，去掉高次項后有以下式子：

用矩陣表示為：B=Aδ。

其中：

由矢量矩陣可知，δ=A-1B。判斷當前的δ是否小于設定的門限，如果小于設定門限，此時停止迭代，得到未知點的估計坐標；如果δ大于設定的門限，那么就繼續迭代直到小于門限或迭代次數用盡。

2 定位算法改進

針對在使用指紋庫方式進行測距時，無法避免匹配多個值所帶來的誤差，尤其在指紋庫較大時更容易出現誤差的情況，此時若采用泰勒級數展開法對當前匹配值反饋校正，即可對匹配中誤差較大的值進行濾除，從而提升測距精度。設計思想是基于WKNN 取出歐氏距離最小的前K條指紋后，繼續對前K條指紋進行處理，整個算法分為離線采集階段和在線定位階段。

離線階段中，在定位區域放置m個已知節點，在每一個測量點得出當前已知點的rssi 值，由于rssi 值易受環境影響和易波動的情況，將原本指紋庫經由高斯濾波得到新的指紋庫，如下式所示：

式中：(xn,yn)為測量點的位置，n為測量點的標號；m為已知點的標號；rssinm代表第n個測量點處接收到標號為m的已知點的rssi 值。而在測距階段中，當前未知點接收到的rssi 值為[xx yxrssix1rssix2… rssixm]，其中，xx，yx為未知點的坐標，使用當前接收到的rssi 值與指紋庫進行匹配。具體步驟如圖1 所示。

圖1 改進算法流程圖

步驟1：離線階段采集每個測量點的rssi 值，建立離線指紋庫，并進行高斯濾波，保留出現概率較高的rssi值，提升匹配精度，降低匹配時間。

步驟2：在線階段，根據接收到的rssi 值，與指紋庫中的指紋匹配得到式（11），在指紋庫中采用WKNN 方式進行匹配，保留前k個指紋點。

將當前未知點收到的rssi 值與指紋庫中的每一行rssi值求歐氏距離，即：

式中：Oj代表未知點和第j個測量點的歐氏距離；rssixi為當前未知點接收到的第i個已知點的rssi 值，rssiji則意為指紋庫中在第j個測量點收到第i個已知點的rssi 值。接著，對求得的Oj進行從小到大排序，僅保留前k個，即：

步驟3：根據前k個指紋點和已知點求出距離di，即其中(xj,yj)為當前指紋庫里已知點坐標，(xi,yi)為未知點估計坐標。di為當前未知點和已知點的測量距離。

步驟4：由泰勒級數展開式可得[19]：

考慮在實際定位中，歐氏距離越小的已知點對實際定位貢獻度越大。因此，采用一正定對角矩陣體現：式（14）變為：

Q為權重矩陣，其相應行對矩陣B中不同測距信息產生影響，從而對最終估計點坐標產生影響，如此可達到提高精度的目的。矩陣A，B，δ分別如式（7）～式（9）所示，此時Q為：

步驟5：解得δ若小于門限值[20]，保留未知點的估計坐標。此時依據距離差公式，由未知點的估計坐標和匹配的指紋點坐標再次求距離為門限值，此時該點為干擾點。

步驟6：最終剩下的匹配點按照歐氏距離取權重，得出最終的未知點估計坐標。

3 仿真分析與討論

本文通過實地測試來評估當前算法的定位性能。測試環境為一室內環境。室內環境：實驗區域為20×20的方形區域，有書桌等障礙物，使用i(i=2,3,…,6)個參考點，分別為信標1（0，0），信標2（10，0），信標3（20，0），信標4（0，20），信標5（10，20），信標6（20，20）。具體分布示意圖如圖2 所示。

圖2 測試空間分布圖

如圖2 所示：黑色圖形代表參考點的位置，黑色點代表未知點。在離線階段每隔1 m 取一個指紋點。接下來將和文獻[16-17]中的定位方法進行定位性能對比。隨機選取10 個點，每個點測量100 次，取其平均值。測試結果如表1 所示。

接著，在測試環境中任意選取100 個未知節點，分別采用文獻[16-17]中的自適應動態K和WKNN 改進算法估計坐標值，并與實際坐標值計算估計定位誤差進行比較。不同算法實際測試結果如圖3 所示。

從圖3 的結果可以得出，改進算法的定位誤差相較于文獻[16-17]中的算法更小并且集中。在此測試環境下，文獻[16]的平均定位誤差為1.81 m，文獻[17]中的算法的定位誤差為1.34 m，而改進的WKNN 定位算法定位誤差為0.89 m。測試結果表明，改進算法有效地減少了定位誤差。

最后，分析整體定位測試的誤差分布，如圖4 所示是文獻[16-17]及改進WKNN 算法的誤差范圍概率分布圖。其中，橫坐標是誤差范圍，縱坐標是誤差范圍內的概率分布。

表1 待測點的估計坐標和實際坐標

圖3 不同算法實際測試結果圖

實際測試可知，文獻[16]中的算法定位誤差最大，而改進的WKNN 算法的定位誤差最小。由圖4 可得，當定位誤差在1.5 m 內時，文獻[16]的概率分布大概是0.37，而改進的WKNN 算法的概率分布大概是0.80。顯然，在誤差距離相同時，改進算法比WKNN 具有更好的概率分布。

4 結 語

本文針對固定K值所帶來的額外誤差及傳統EWKNN 方式所存在的定位性能問題，分析研究WKNN算法和泰勒級數展開法，將這兩種方法結合，提出新的動態自適應K值確定方案，研究表明提出的算法比文獻[16-17]的動態K算法定位誤差更小，且平均定位精度更高，而且定位時間開銷增加不大。但文中信標節點布置是比較規范的，并未考慮到隨機布設信標節點的情況。下一步需要研究如何在信標節點隨機分布時減少未知節點的定位誤差。

圖4 不同算法實際測試CDF 結果圖