基于自適用權(quán)重的最近鄰居法室內(nèi)定位方法研究

劉宏

(湖南衡陽北方光電信息技術(shù)有限公司，衡陽 421001)

基于自適用權(quán)重的最近鄰居法室內(nèi)定位方法研究

劉宏

(湖南衡陽北方光電信息技術(shù)有限公司，衡陽 421001)

由于室內(nèi)物體的移動導(dǎo)致室內(nèi)定位精度影響整個網(wǎng)絡(luò)數(shù)據(jù)。目前算法所能解決的一般為二維空間，對于三維移動物體的定位精度較差。自適用權(quán)重的最近鄰居法通過賦予鄰居不同權(quán)值求取平均值來確定移動物體的位置，通過周邊三個不同位置的加權(quán)平均值從三個角度來定位移動物體，以此來提高三維移動物體的定位精度，實驗表明自適用權(quán)重的最近鄰居法比傳統(tǒng)的定位算法具有更高的適用性和定位精度。

室內(nèi)定位；定位精度；定位；移動物體

1 定位算法的理論分析

最早的基于無線局域網(wǎng)的定位系統(tǒng)是微軟公司開發(fā)出的RADAR系統(tǒng)。RADAR系統(tǒng)提出依靠信號強度指紋數(shù)據(jù)庫的、采用NNSS-AVGN或者NSS算法來實現(xiàn)定位。RADAR系統(tǒng)包括校準階段和定位階段這兩個階段來實現(xiàn)定位。

校準階段需要建立指紋數(shù)據(jù)庫[1]，又被稱為離線訓(xùn)練階段。創(chuàng)建指紋數(shù)據(jù)庫的步驟如下：

第一步：布置n個無線信號源APl…APn。

第二步：設(shè)置參考點，并且在參考點處收集無線信號。RSSIi表示采集到的第i個AP節(jié)點發(fā)射的無線信號強度值，n個信號構(gòu)成一組信號強度值，例如（RSSI1，RSSI2，RSSI3…，RSSIn）。

第三步：同一個參考點采集X次，然后對每一個AP（ii=l…n）計算信號強度平均值RSSI1，n個信號構(gòu)成一組的信號強度均值

第四步：將該組參考點坐標位置和信號強度均值保存到指紋數(shù)據(jù)庫。

第五步：選則下一個參考點，并且重復(fù)第二步到第四步的過程，一直到滿足系統(tǒng)所需要參考點數(shù)目為止。

NNSS（Nearest Neighbors in Signal Space），又被稱作最近鄰居法[2,3]。在RADAR系統(tǒng)，無線信號空間距離也被稱為為歐氏距離。而與測試點歐氏距離相離最近參考點則被看作為最近鄰。以下是歐氏距離的計算公式：

如果在RADAR系統(tǒng)使用NNSS算法來實現(xiàn)系統(tǒng)的定位功能，定位階段的步驟如下所示：

輸入在校準階段所創(chuàng)建的指紋數(shù)據(jù)庫，n個無線信號發(fā)射點為APl…APn，存在一個待測點，就是定位點。

輸出待測點位置坐標。

第二步：根據(jù)公式（1），計算出該信號強度值與數(shù)據(jù)庫中的各個信號強度值的歐氏距離D，并找出最小D值的指紋數(shù)據(jù)。

第三步：將D值最小的參考點的位置坐標作為待測點的位置坐標。

采用NNSS算法作為定位方式，待測點的估計坐標只能選擇參考點的位置坐標[4,5]，這會導(dǎo)致定位結(jié)果呈離散狀。定位精度也會受到影響。NNSS-AVG（Nearest Neighbors in Signal Space-Average）算法則可以將定位的結(jié)果分散到連續(xù)的空間。在RADAR系統(tǒng)

在公式中，（x,y）表示的是待測點坐標，（xi，yi）表示前k個D值最小的參考點的位置坐標。

根據(jù)線性距離的路徑損耗模型L（d）=ad+lo可以看出[6]，待測點信號強度和發(fā)射點與待測點的距離可以看作為線性關(guān)系。由于室內(nèi)的環(huán)境存在遮擋的情況，所以無線信號傳播模型也存在著很大誤差，但是在無線信號發(fā)射點與待測點距離較短的情況下，我們?nèi)匀豢梢詫⒕嚯x與信號強度的關(guān)系線性化。為了利于討論定位算法性能，在短距離空間內(nèi)，我們可以采用位置的歐氏距離去代替信號強度的歐式距離。

假設(shè)有四個參考點A、B、C、D，點的坐標分別設(shè)為（0，0）、（0，4）、（4，0）、（4，4）。T坐標為（2，2），橫坐標和縱坐標的單位都為米，如圖1所示。A與T的歐氏距離為米，這與B、C、D點與T點之間的歐氏距離相等。如果使用NNSS算法把待測點定位于A，B，C，D點其中任意一點。定位誤差約為米，如果使用NNSS-AVG算法，假設(shè)k=4，用公式2可以估算出待測點的位置為（2，2），誤差為 0 米。的定位階段的第二步中，與NNSS算法步驟只取一個D值最小的參考點不同，采用NNSS.AVG實現(xiàn)室內(nèi)定位時，將歐氏距離值D進行排序，選取k個D值最小的參考點。并且在定位階段的第三步中，把k個參考點的坐標求取平均值，并且由此估算出待測點的位置坐標。以下是待測點坐標計算公式：

圖1 定位誤差分析

這樣看來，NNSS-AVG算法比NNSS算法精度更高，不過在待測點與其中一個參考點相接近時，即假設(shè)參考點 A、B、C、D 點的坐標分別為（0，0）、（0，4）、（4，0）、（4，4），待測點 T 的坐標為（1，0），橫坐標和縱坐標的單位為米，如圖2所示。A、B、C、D點與T的歐式距離分別為1米、4.123米、3米、5米。根據(jù)NNSS算法將，待測點定位于A點即位置坐標為（0，0）的點。根據(jù)公式誤差米。如果使用NNSSAVG算法，假設(shè)k=4，用公式2可以估算出待測點的位置為（2，2），定位誤差為米。這個時候NNSS算法又比NNSS-AVG算法精度更高。這種結(jié)果的原因是T點離A點距離很近，離B、C、D點較遠。T點的真實位置應(yīng)在A點的旁邊，但是由于引入B、C、D點，導(dǎo)致了定位誤差的加大。因此對于不同鄰居，我們不能統(tǒng)一的看待，但是可以通過賦予它們不同權(quán)值代替求取平均值。接下來介紹一種基于權(quán)重的NNSS-AVG算法即WNNSS-AVG算法。

圖2 加權(quán)定位誤差分析

2 自適用權(quán)重的最近鄰居法

NNSS-AVG算法中各個近鄰權(quán)值可以看成1/k，NNSS-AVG算法的加權(quán)方式如公式（3），（4）所示：

在公式（3）中wi表示第i個鄰居權(quán)重。在公式4中D表示信號空間歐氏距離。利用WNNSS-AVG算法，用位置歐氏距離來代替信號強度歐氏距離。假設(shè)k=4，利用公式3、4可以估算出待測點坐標為（0.5，0.33），定位誤差為米，與N算法和NNSS-AVG算法相比，WNNSS-AVG算法的定位精度有了很大幅度的提高。

3 信號強度指紋方法的性能研究

在下面的實驗環(huán)境中，進行Wi-Fi信號的統(tǒng)計特性實驗，并且對NNSS，NNSS-AVG，WNNSS-AVG的定位性能進行研究分析，然后確定Wi-Fi定位系統(tǒng)的最優(yōu)定位引擎方案。

第一步：對整個商場建立一個橫軸為x縱軸為y的二維坐標系。

第二步：選取目標周圍較近三個節(jié)點為參考節(jié)點，計算出它們的坐標，三點的坐標分別為（160，30），（180，18），（168，29）。

第三步：使用基于RSSI模型公式分別對目標節(jié)點與三個參考節(jié)點間進行測距，測出目標到第一個節(jié)點的距離為5米，到第二個點的距離為9米，到第三個節(jié)點的距離為7米。

第四步：采用三邊測量法公式對目標節(jié)點進行定位，此時定位并不精確，本文采用極大后驗概率確定目標在坐標點（162,25）的概率最大。通過以上幾步得到目標的最終坐標（162,25）。

4 實驗及數(shù)據(jù)分析

（1）實驗場地和數(shù)據(jù)收集

實驗所需硬件：一臺紅外線測距儀、4個無線路由器、一臺Android平板電腦。實驗所需軟件：安裝在Android平板電腦上的Wi-Fi指紋采集系統(tǒng)。實驗場所：由一條走廊和一間會議室組成的室內(nèi)場所。選取會議室中的一個墻角作為原點，并且建立橫坐標、縱坐標。在橫軸和縱軸上面每隔0.5米取一點。如圖3所示，在坐標為（3.25，0.5），（0.5，3），（5.5，3），（3.25，5.5）處分別放置4個無線路由器，并分別作標記APl，AP2，AP3，AP4。然后在這個坐標平面上進行實驗，并且對定位結(jié)果進行數(shù)據(jù)分析。

（2）測試數(shù)據(jù)取平均值的實驗

在各種因素的干擾下導(dǎo)致單次的取值可能會存在誤差較大情況。通過Wi-Fi信號強度概率分布實驗，我們可以得知通過多次的取值，并且計算位置的平均值能降低單次取值所引起的誤差。因此，在實驗的測試數(shù)據(jù)收集中，分別在45個測試點各選取了30組信號強度數(shù)據(jù)。然后從各個點的數(shù)據(jù)中，選取出連續(xù)的3組或10組數(shù)據(jù)，求取平均值后來作為一個計算數(shù)據(jù)。并且每個點取2個計算數(shù)據(jù)，計算在WNNSS-AVG算法存在的定位誤差。最后與只選取了一組數(shù)據(jù)作為計算數(shù)據(jù)的情況進行對，對比情況如表1所示。

圖3 數(shù)據(jù)采集的實驗布置1

表1 WNNSS-AVG不同取值方案位置誤差（米）統(tǒng)計

通過數(shù)據(jù)分析，1組、3組、10組方案平均誤差分別為1.3138米、1.2628米和1.2076米。在0.5米內(nèi)，1組、3組、10組方案的定位誤差累積率分別為20.12%、12.123%、17.81%。在1.5米內(nèi)，1組、3組、10組方案的定位誤差累積率分別為65.47%、63.41%、64.39%。從該定位算法誤差累積的概率分布圖可以看出，在1.5米內(nèi)，3組和10組的方案并沒有優(yōu)于1組的方案。但是在2米之后，3組和10組的方案明顯優(yōu)于1組。在2米之內(nèi)，l組、3組、10組方案定位誤差的累積率分別為78.98%、86.76%、85.67%。3組和10組方案的最大定位誤差都在4米以內(nèi)，然而1組的方案有1.21%概率定位誤差在4米以上。

5 結(jié)語

以目前的Wi-Fi室內(nèi)定位的水平，允許存在2米之內(nèi)的定位誤差。所以使用3組和10組的方案可以有效防止系統(tǒng)出現(xiàn)4米以上的較大誤差。但是考慮系統(tǒng)的實時性，系統(tǒng)每選取一組數(shù)據(jù)大約需要1秒的時間，如果選擇10組的方案，定位時間將會大于10秒。綜合考慮定位誤差和實時性，因此室內(nèi)定位方案應(yīng)該選擇3組方案的WNNSS-AVG算法比其他算法的適用性和精度都要高。

[1]魏葉華,李仁發(fā).無線傳感網(wǎng)絡(luò)中的一種二階段定位算法[J].計算機應(yīng)用與軟件,2012,30（2）:204-207

[2]黃學(xué)青,房鼎益.基鄰居篩選的質(zhì)心迭代定位算法[J].杭州電子科技大學(xué)學(xué)報，2011,28（6）:59-62

[3]汪煬,黃劉生.一種基于RSSI校驗的無線傳感網(wǎng)絡(luò)節(jié)點定位算法[J].小型微計算機系統(tǒng),2012,30（1）:59-62

[4]王福豹,史龍.無線傳感網(wǎng)絡(luò)中的自身定位系統(tǒng)和算法[J].軟件學(xué)報,2005,16（5）:857-868

[5]馬玉秋.基于無線傳感器網(wǎng)絡(luò)的定位技術(shù)研究及實現(xiàn)[D].北京：北京郵電大學(xué)，2006,23-24

[6]田洪強.智能建筑無線傳感器網(wǎng)絡(luò)控制節(jié)點的設(shè)計實現(xiàn)[D].北京：北京交通大學(xué)，2010,59-62

Abstract：The positioning accuracy affects the whole network data due to the movement of indoor objects.At present,the algorithm can solve the twodimensional space,and the positioning accuracy of 3D moving objects is poor.Adaptive weighted nearest neighbors method by giving differ?ent weights to neighbors are normalized to determine the position of the moving object,through the surrounding a weighted average of the three different position from three angles to locate the moving objects,in order to improve the positioning precision of the 3D moving object,the experiments show that the adaptive weight nearest neighbors method than the traditional localization algorithm has higher applicability and localization accuracy.

Keywords：Indoor Localization;Positioning Accuracy;Positioning;Moving Object

Research on the Nearest Neighbors Localization Method Based on Adaptive Weighted

LIU Hong

（Hunan Hengyang North Photoelectric Information Technology Co.Ltd.,Hengyang 421001）

1007-1423（2017）26-0029-04

10.3969/j.issn.1007-1423.2017.26.007

劉宏（1980-）,男,湖南衡陽人,本科,研究方向為數(shù)據(jù)挖掘、智能信息處理、紅外跟蹤、紅外制導(dǎo)

2017-08-24

2017-09-10