改進動態(tài)K 的WKNN 的室內(nèi)定位方法

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

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

0 引 言

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

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

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

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

1 定位算法分析

1.1 WKNN 算法

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

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

1.2 泰勒級數(shù)展開法

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

估計值與真實值有如下關(guān)系：

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

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

其中：

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

2 定位算法改進

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

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

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

圖1 改進算法流程圖

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

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

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

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

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

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

考慮在實際定位中，歐氏距離越小的已知點對實際定位貢獻度越大。因此，采用一正定對角矩陣體現(xiàn)：式（14）變?yōu)椋?/p>

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

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

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

3 仿真分析與討論

本文通過實地測試來評估當前算法的定位性能。測試環(huán)境為一室內(nèi)環(huán)境。室內(nèi)環(huán)境：實驗區(qū)域為20×20的方形區(qū)域，有書桌等障礙物，使用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 次，取其平均值。測試結(jié)果如表1 所示。

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

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

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

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

圖3 不同算法實際測試結(jié)果圖

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

4 結(jié) 語

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

圖4 不同算法實際測試CDF 結(jié)果圖