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

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

0 引 言

室內(nèi)定位服務(wù)（Indoor Positioning Service，IPS），作為一種基于位置的服務(wù)，它主要利用無線通信、射頻識別、慣性導(dǎo)航等技術(shù)獲取移動端的位置信息，完成對室內(nèi)環(huán)境中人員或物體的位置確定[1]。隨著射頻技術(shù)和無線通信技術(shù)的快速發(fā)展，室內(nèi)定位服務(wù)在日常生活的重要性愈加凸顯。WiFi 的普及以及5G 技術(shù)等基站的部署[2]，使得快速傳輸無線數(shù)據(jù)成為了可能，加之室內(nèi)定位與人們實(shí)際生活息息相關(guān)，擁有巨大的商業(yè)價值和應(yīng)用潛力，這些都推動了室內(nèi)定位的發(fā)展。近些年來室內(nèi)無線定位技術(shù)也取得了一些成果，技術(shù)不斷推陳出新，定位精度也越來越高；但從整體來看，室內(nèi)定位如果應(yīng)用于實(shí)際環(huán)境中，實(shí)現(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)絡(luò)的普及，絕大部分室內(nèi)環(huán)境都可利用WiFi 實(shí)現(xiàn)定位，并且WiFi 模塊的硬件成本較低，可被集成到各種電子設(shè)備中，為室內(nèi)定位打下硬件基礎(chǔ)。因此，WiFi 定位在室內(nèi)定位領(lǐng)域中具有舉足輕重的地位。許多研究學(xué)者投身于WiFi室內(nèi)定位技術(shù)研究和相關(guān)應(yīng)用，并且提出了多種解決方案?？傮w來說，WiFi 室內(nèi)定位方法一般分為兩種，一種基于理論模型的信號強(qiáng)度定位，另一種則是基于指紋庫匹配的定位。由于理論模型的應(yīng)用受環(huán)境限制較大，大多數(shù)WiFi 室內(nèi)定位系統(tǒng)都選擇指紋庫方式[7]。在指紋庫定位中，加權(quán)K-最近鄰（Weighted K-nearest Neighbor，WKNN）算法[8]應(yīng)用最為廣泛。該方法利用在線階段得到多個匹配點(diǎn)的位置信息，對獲取的位置信息進(jìn)行權(quán)重計(jì)算，最終得到估計(jì)點(diǎn)的位置坐標(biāo)。但實(shí)際中K值的確定并不簡單，因此大部分文獻(xiàn)都選擇固定K值或者選取多個K值進(jìn)行對比。文獻(xiàn)[9]中將K值固定為4；文獻(xiàn)[10-11]中將K值固定為3；文獻(xiàn)[12]中K值固定為4；文獻(xiàn)[13]中選擇了多個K值并對比不同K值下的定位情況；文獻(xiàn)[14]在傳統(tǒng)的WKNN 算法上進(jìn)行改進(jìn)，并對改進(jìn)后的算法在不同K值下進(jìn)行對比；RADAR[15]對WKNN 中的不同K值對比，并分析不同K值對定位精度的影響，得出結(jié)論：定位精度隨著K值的增大而變高，但當(dāng)K值達(dá)到某個值后，定位精度會隨著K值的增加而降低。

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

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

1 定位算法分析

1.1 WKNN 算法

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

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

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

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

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

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

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

其中：

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

2 定位算法改進(jìn)

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

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

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

圖1 改進(jìn)算法流程圖

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

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

將當(dāng)前未知點(diǎn)收到的rssi 值與指紋庫中的每一行rssi值求歐氏距離，即：

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

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

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

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

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

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

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

3 仿真分析與討論

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

圖2 測試空間分布圖

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

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

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

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

表1 待測點(diǎn)的估計(jì)坐標(biāo)和實(shí)際坐標(biāo)

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

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

4 結(jié) 語

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

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