基于自適用權重的最近鄰居法室內定位方法研究

劉宏

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

基于自適用權重的最近鄰居法室內定位方法研究

劉宏

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

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

室內定位；定位精度；定位；移動物體

1 定位算法的理論分析

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

校準階段需要建立指紋數據庫[1]，又被稱為離線訓練階段。創建指紋數據庫的步驟如下：

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

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

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

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

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

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

如果在RADAR系統使用NNSS算法來實現系統的定位功能，定位階段的步驟如下所示：

輸入在校準階段所創建的指紋數據庫，n個無線信號發射點為APl…APn，存在一個待測點，就是定位點。

輸出待測點位置坐標。

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

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

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

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

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

假設有四個參考點A、B、C、D，點的坐標分別設為（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算法，假設k=4，用公式2可以估算出待測點的位置為（2，2），誤差為 0 米。的定位階段的第二步中，與NNSS算法步驟只取一個D值最小的參考點不同，采用NNSS.AVG實現室內定位時，將歐氏距離值D進行排序，選取k個D值最小的參考點。并且在定位階段的第三步中，把k個參考點的坐標求取平均值，并且由此估算出待測點的位置坐標。以下是待測點坐標計算公式：

圖1 定位誤差分析

這樣看來，NNSS-AVG算法比NNSS算法精度更高，不過在待測點與其中一個參考點相接近時，即假設參考點 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米。根據NNSS算法將，待測點定位于A點即位置坐標為（0，0）的點。根據公式誤差米。如果使用NNSSAVG算法，假設k=4，用公式2可以估算出待測點的位置為（2，2），定位誤差為米。這個時候NNSS算法又比NNSS-AVG算法精度更高。這種結果的原因是T點離A點距離很近，離B、C、D點較遠。T點的真實位置應在A點的旁邊，但是由于引入B、C、D點，導致了定位誤差的加大。因此對于不同鄰居，我們不能統一的看待，但是可以通過賦予它們不同權值代替求取平均值。接下來介紹一種基于權重的NNSS-AVG算法即WNNSS-AVG算法。

圖2 加權定位誤差分析

2 自適用權重的最近鄰居法

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

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

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

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

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

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

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

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

4 實驗及數據分析

（1）實驗場地和數據收集

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

（2）測試數據取平均值的實驗

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

圖3 數據采集的實驗布置1

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

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

5 結語

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

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

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

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

[4]王福豹,史龍.無線傳感網絡中的自身定位系統和算法[J].軟件學報,2005,16（5）:857-868

[5]馬玉秋.基于無線傳感器網絡的定位技術研究及實現[D].北京：北京郵電大學，2006,23-24

[6]田洪強.智能建筑無線傳感器網絡控制節點的設計實現[D].北京：北京交通大學，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-）,男,湖南衡陽人,本科,研究方向為數據挖掘、智能信息處理、紅外跟蹤、紅外制導

2017-08-24

2017-09-10