劉宏

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

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

劉宏

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

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

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

1 定位算法的理論分析

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

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

第一步：布置n個(gè)無(wú)線信號(hào)源APl…APn。

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

第三步：同一個(gè)參考點(diǎn)采集X次，然后對(duì)每一個(gè)AP（ii=l…n）計(jì)算信號(hào)強(qiáng)度平均值RSSI1，n個(gè)信號(hào)構(gòu)成一組的信號(hào)強(qiáng)度均值

第四步：將該組參考點(diǎn)坐標(biāo)位置和信號(hào)強(qiáng)度均值保存到指紋數(shù)據(jù)庫(kù)。

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

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

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

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

輸出待測(cè)點(diǎn)位置坐標(biāo)。

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

第三步：將D值最小的參考點(diǎn)的位置坐標(biāo)作為待測(cè)點(diǎn)的位置坐標(biāo)。

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

在公式中，（x,y）表示的是待測(cè)點(diǎn)坐標(biāo)，（xi，yi）表示前k個(gè)D值最小的參考點(diǎn)的位置坐標(biāo)。

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

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

圖1 定位誤差分析

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

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

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

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

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

3 信號(hào)強(qiáng)度指紋方法的性能研究

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

第一步：對(duì)整個(gè)商場(chǎng)建立一個(gè)橫軸為x縱軸為y的二維坐標(biāo)系。

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

第三步：使用基于RSSI模型公式分別對(duì)目標(biāo)節(jié)點(diǎn)與三個(gè)參考節(jié)點(diǎn)間進(jìn)行測(cè)距，測(cè)出目標(biāo)到第一個(gè)節(jié)點(diǎn)的距離為5米，到第二個(gè)點(diǎn)的距離為9米，到第三個(gè)節(jié)點(diǎn)的距離為7米。

第四步：采用三邊測(cè)量法公式對(duì)目標(biāo)節(jié)點(diǎn)進(jìn)行定位，此時(shí)定位并不精確，本文采用極大后驗(yàn)概率確定目標(biāo)在坐標(biāo)點(diǎn)（162,25）的概率最大。通過(guò)以上幾步得到目標(biāo)的最終坐標(biāo)（162,25）。

4 實(shí)驗(yàn)及數(shù)據(jù)分析

（1）實(shí)驗(yàn)場(chǎng)地和數(shù)據(jù)收集

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

（2）測(cè)試數(shù)據(jù)取平均值的實(shí)驗(yàn)

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

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

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

通過(guò)數(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組的方案并沒(méi)有優(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é)語(yǔ)

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

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

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

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

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

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

[6]田洪強(qiáng).智能建筑無(wú)線傳感器網(wǎng)絡(luò)控制節(jié)點(diǎn)的設(shè)計(jì)實(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-）,男,湖南衡陽(yáng)人,本科,研究方向?yàn)閿?shù)據(jù)挖掘、智能信息處理、紅外跟蹤、紅外制導(dǎo)

2017-08-24

2017-09-10