李昂　肖甫　李雷

摘 要：通過分析基于WiFi定位的傳統(tǒng)位置指紋算法的不足之處，文中提出了一種旨在提高精度并減小計(jì)算復(fù)雜度的改進(jìn)型KNN算法。通過Android平臺(tái)對該算法進(jìn)行實(shí)現(xiàn)和測試，分析比較K的取值、AP的位置及數(shù)量等因素對定位精度的影響。測試結(jié)果表明，該算法不但能夠保證位置指紋室內(nèi)定位的精度，還能有效減小計(jì)算復(fù)雜度，具有一定的可行性。

關(guān)鍵詞：精度；計(jì)算復(fù)雜度；改進(jìn)型KNN算法；Android平臺(tái)

中圖分類號：TP301；TN92 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號：2095-1302（2018）03-00-05

0 引 言

伴隨著互聯(lián)網(wǎng)應(yīng)用的快速發(fā)展，人們在室內(nèi)停留的時(shí)間越來越多，室內(nèi)位置信息對人們的日常生活愈加重要，因此人們對室內(nèi)定位有著愈發(fā)強(qiáng)烈的需求[1-3]。由于利用GPS和AGPS這兩種定位方式進(jìn)行室內(nèi)定位時(shí)，信號會(huì)受到各種障礙物的遮擋[4]，因此亟待出現(xiàn)新型的室內(nèi)定位方式。

隨著無線局域網(wǎng)絡(luò)（Wireless Local Area Networks，WLAN）遍布各地，智能手機(jī)和平板電腦等個(gè)人電子設(shè)備發(fā)展迅速，這些設(shè)備幾乎都使用WiFi連接網(wǎng)絡(luò)，用戶可使用WiFi進(jìn)行定位[5-7]。iOS，Android和WP是目前三大主流移動(dòng)操作系統(tǒng)。其中，Android系統(tǒng)所占的市場份額日益增大，因此完全可以選擇Android系統(tǒng)作為載體，設(shè)計(jì)基于WiFi的室內(nèi)定位系統(tǒng)[8-11]。本文基于Android平臺(tái)設(shè)計(jì)了一種基于改進(jìn)的位置指紋算法，首先收集采樣點(diǎn)的信號強(qiáng)度值信息，并將其保存到數(shù)據(jù)庫中，然后將定位時(shí)的數(shù)據(jù)和數(shù)據(jù)庫相互對比進(jìn)行估算，得到所要定位的坐標(biāo)信息。

1 基于WiFi的室內(nèi)定位技術(shù)簡介

雖然目前實(shí)現(xiàn)WiFi室內(nèi)定位的方法有很多，但主要使用基于測距的定位方法。其中基于RSSI的定位方法最受關(guān)注[12-16]?；赗SSI的定位算法流程如圖1所示。

2 傳統(tǒng)位置指紋定位技術(shù)

目前，在研究基于WiFi的室內(nèi)定位時(shí)，位置指紋定位技術(shù)使用較多[17-21]，受到了廣泛關(guān)注。

2.1 技術(shù)原理

基于位置指紋定位算法的原理圖如圖2所示。

從圖2可以看出，位置指紋定位算法主要包括離線工作階段和在線工作階段。離線階段即數(shù)據(jù)收集階段，首先選擇一個(gè)區(qū)域，從中選取多個(gè)采樣點(diǎn)，然后收集這些點(diǎn)WiFi信號的強(qiáng)度值RSSI，并將其作為位置指紋保存到指紋數(shù)據(jù)庫中。在這個(gè)指紋數(shù)據(jù)庫中，每個(gè)指紋都由一組RSSI值組成，且對應(yīng)一個(gè)位置坐標(biāo)。在線階段即定位階段，將待測目標(biāo)定位的信息與指紋庫進(jìn)行匹配，最后估算出當(dāng)前位置坐標(biāo)，完成定位[22]。在WiFi環(huán)境下，使用位置指紋定位算法RSSI定位工作過程如圖3所示。

在選取的定位區(qū)域中，l個(gè)采樣點(diǎn)可以收集n個(gè)RSSI值來表示一個(gè)指紋，遍歷所有采樣點(diǎn)并獲得各自的RSSI值，保存于指紋庫中。指紋庫內(nèi)容如式（1）所示：

其中：RSSIji表示在第i個(gè)采樣點(diǎn)所測的WiFi信號的第j個(gè)RSSI值；FPi=（RSSI1i，RSSI2i，…，RSSImi）表示任意一個(gè)位置的指紋數(shù)據(jù)，同時(shí)該指紋數(shù)據(jù)也可用坐標(biāo)（x，y）表示。因此，指紋數(shù)據(jù)與坐標(biāo)相互對應(yīng)，其坐標(biāo)如式（2）所示：

位置指紋數(shù)據(jù)庫由式（1）和式（2）共同組成。

除了在離線階段創(chuàng)建一個(gè)比較準(zhǔn)確的指紋數(shù)據(jù)庫，在線階段指紋庫的匹配算法也十分重要[23]。常用的匹配算法有最近鄰法、K近鄰法和加權(quán)K近鄰法。

（1）最近鄰算法（NN）

最近鄰算法是一種比較常用的匹配算法，當(dāng)待測目標(biāo)進(jìn)入定位所選區(qū)域時(shí)，可獲得一個(gè)相關(guān)的指紋信息lf=（RSSI1，RSSI2，…，RSSIn），然后將這個(gè)指紋信息與指紋數(shù)據(jù)庫中的信息相匹配，再算出它們之間的距離，其距離如式（3）所示[24，25]，其中距離最小也就是相似度最大指紋信息min（d（lf，F(xiàn)Pi）），即待測目標(biāo)的位置。

式中：RSSIj和RSSIji分別為定位點(diǎn)和指紋點(diǎn)的強(qiáng)度值；n是WiFi信號的個(gè)數(shù)。

最近鄰算法操作十分簡單，且容易實(shí)現(xiàn)，但是其可選擇的參考點(diǎn)較為單一，定位時(shí)容易產(chǎn)生誤差，精度不高。

（2）K近鄰算法（KNN）

相較于最近鄰算法，K近鄰算法可選擇的參考點(diǎn)有所增多。匹配待測目標(biāo)的指紋信息，并找出與指紋數(shù)據(jù)庫中最近鄰的K（K>2）個(gè)指紋信息，通過計(jì)算坐標(biāo)的平均值就可以估算出待測目標(biāo)的位置，其位置如式（4）所示[26，27]：

式中：（xi，yi）是被選擇的第i個(gè)指紋數(shù)據(jù)庫中的信息所對應(yīng)的坐標(biāo)。

（3）加權(quán)K 近鄰法（WKNN）

加權(quán)K近鄰法是對K近鄰法的一種改進(jìn)。K近鄰法選取的K個(gè)最小距離對最后的定位結(jié)果貢獻(xiàn)相同，取平均值，但距離越小對定位結(jié)果坐標(biāo)的貢獻(xiàn)越大。因此，對所取的K個(gè)最小距離進(jìn)行權(quán)值分配，距離越小，權(quán)值越大。K個(gè)權(quán)值ωk之和為1。ωk可自行設(shè)定，也可由式（5）計(jì)算得出[28，29]：

2.2 技術(shù)性能與存在的問題

當(dāng)前的位置指紋算法雖然可以實(shí)現(xiàn)室內(nèi)定位，但該算法依然存在一些問題，主要體現(xiàn)在以下方面：

（1）算法模型過于簡單，僅能滿足較為簡單的室內(nèi)環(huán)境的定位要求。當(dāng)室內(nèi)環(huán)境較為復(fù)雜，如家具等陳設(shè)較多、有移動(dòng)物體或人走動(dòng)時(shí)，該傳統(tǒng)算法的定位精度無法滿足要求。

（2）該算法在線工作階段的運(yùn)算量較大，尤其當(dāng)AP個(gè)數(shù)較多或K取值較大時(shí)，運(yùn)算量急劇增長，無疑增加了該算法的運(yùn)行成本和復(fù)雜度。

3 一種改進(jìn)的KNN算法

考慮到上述傳統(tǒng)位置指紋算法存在的問題，對傳統(tǒng)位置指紋算法作如下改進(jìn)：

（1）面對更復(fù)雜的室內(nèi)環(huán)境，應(yīng)當(dāng)建立更加符合實(shí)際的模型。傳統(tǒng)位置指紋算法的模型主要采用MK模型，如式（6）所示：

L（d）=L+10nlgd+NωLω+NfLf （6）

其中：L表示距離發(fā)射端1 m處的傳播損耗；n是路徑傳播損耗系數(shù)；d是發(fā)射端到接收端的距離；Nω和Nf分別是傳播路徑上穿過的墻壁和地板個(gè)數(shù)；Lω和Lf 分別是墻壁和地板的損耗系數(shù)?？梢?，傳統(tǒng)模型對于室內(nèi)環(huán)境只考慮了墻壁和地板，而對于更復(fù)雜的情況沒有考慮。

因此提出一種新的更符合實(shí)際的模型，充分考慮了除墻壁和地板外包括人在內(nèi)的其他障礙物，如式（7）所示：

式（7）與式（6）的不同之處在于最后一項(xiàng)，假設(shè)共有m種障礙物，Pi表示遇到第i種障礙物的概率，可以通過最小二乘法計(jì)算得出；Ni表示穿過第i種障礙物的個(gè)數(shù)，Li表示第i種障礙物的損耗系數(shù)。

（2）針對運(yùn)算量較大的問題，提出一種減少運(yùn)算復(fù)雜度的新方法。經(jīng)試驗(yàn)證明，在RSSI算法中，信號強(qiáng)度的衰減速度與傳輸距離成指數(shù)關(guān)系，即距離小時(shí)衰減快，距離大時(shí)衰減慢。尤其當(dāng)?shù)竭_(dá)一定距離后，其衰減速度趨于平緩，即信號強(qiáng)度變化較小。因此，如果按照傳統(tǒng)KNN算法讓所有的RSSI值都參與到計(jì)算中，勢必會(huì)造成較大的冗余開銷。

基于上述現(xiàn)象，需確定一個(gè)距離閾值，大于該距離時(shí)RSSI變化較小，可以舍棄，而小于該距離時(shí)則為有效點(diǎn)，應(yīng)予以采納。由此可較大程度地減小運(yùn)算量。在實(shí)際仿真中發(fā)現(xiàn)，該門限距離取8 m和10 m時(shí)定位精度差距不大，但運(yùn)算量減小了約50%。

對于運(yùn)算和精度有同樣重要影響的還有AP的個(gè)數(shù)與算法中K的取值。仿真試驗(yàn)表明，AP的個(gè)數(shù)對于精度和運(yùn)算量影響巨大。當(dāng)AP數(shù)量增加且分布較均勻時(shí)，定位的精度較高，但同時(shí)運(yùn)算量較大。而K的取值對于精度和運(yùn)算量的影響則呈現(xiàn)出不同的規(guī)律，并非K的取值越大精度越高。因此，AP的個(gè)數(shù)與K的取值應(yīng)當(dāng)在精度和運(yùn)算量之間權(quán)衡。

綜合上述兩個(gè)方面的改進(jìn)，本文提出了一種用于室內(nèi)定位的改進(jìn)KNN算法。

4 改進(jìn)KNN算法的Android實(shí)現(xiàn)與測試

本文所設(shè)計(jì)的定位系統(tǒng)包括收集部分和定位部分，客戶端為Android移動(dòng)端APP，在運(yùn)行時(shí)用戶首先通過收集模塊將采樣點(diǎn)信號的信息提交給數(shù)據(jù)庫，然后定位時(shí)將定位信息與數(shù)據(jù)庫進(jìn)行匹配，即可估算出位置。這款軟件的理論設(shè)計(jì)內(nèi)容如圖4所示。

4.1 實(shí)現(xiàn)

（1）收集模塊設(shè)計(jì)

當(dāng)位置指紋定位算法處于離線收集階段時(shí)，首先需要選取合適的區(qū)域進(jìn)行信息收集，理論上需要在選取的區(qū)域內(nèi)放置4個(gè)無線路由器，其WiFi信號的強(qiáng)度值RSSI比較穩(wěn)定，測試結(jié)果誤差較小，但本文的收集模塊選用4個(gè)隨機(jī)WiFi信號以及各自對應(yīng)的強(qiáng)度值作為參考點(diǎn)。然后在區(qū)域內(nèi)選取若干個(gè)采樣點(diǎn)，其位置已知，將檢測到的每個(gè)采樣點(diǎn)的4種信號強(qiáng)度值均放入創(chuàng)建的指紋數(shù)據(jù)庫中，此時(shí)指紋庫中的每個(gè)采樣點(diǎn)將由一系列RSSI值組成[30]。如果此時(shí)的室內(nèi)環(huán)境發(fā)生變化，那么RSSI值也將發(fā)生變化且定位出現(xiàn)誤差[31]。收集模塊流程如圖5所示。

（2）定位模塊設(shè)計(jì)

當(dāng)位置指紋定位算法處于在線定位階段時(shí)，首先獲取待測目標(biāo)位置的RSSI值，然后使用本文提出的改進(jìn)KNN算法即可估算出待測目標(biāo)的位置。定位模塊流程如圖6所示。

（3）指紋數(shù)據(jù)庫設(shè)計(jì)

考慮到數(shù)據(jù)量并不龐大，因此選擇SQLite數(shù)據(jù)庫。創(chuàng)建的數(shù)據(jù)庫如圖7所示。

4.2 測試方案與結(jié)果分析

（1）測試方案

在本次測試中選取了C104，C108，C112三間教室和大廳作為測試場地。

在這三間教室中，C112面積最大，約10 m×10 m；C104與C108面積較小且相近，約7 m×7 m；而大廳面積與C112相近，但較為空曠，如圖8、圖9所示。計(jì)劃每間教室分別選取4個(gè)角落位置作為采樣點(diǎn)，三間教室共12個(gè)采樣點(diǎn)；而大廳內(nèi)計(jì)劃選取6個(gè)采樣點(diǎn)，如圖10所示。本測試主要檢測在面積大小、AP個(gè)數(shù)、K取值和室內(nèi)環(huán)境均不相同的條件下，所提出的改進(jìn)KNN算法的性能。

（2）測試結(jié)果

教室C104，C108和C112測試結(jié)果見表1所列。

從表1可知，由教室C104和C108所測得的4組數(shù)據(jù)的誤差系數(shù)明顯小于C112的數(shù)據(jù)。

教室C108內(nèi)有人時(shí)的測試結(jié)果見表2所列。

由表2可知，相較于無干擾時(shí)的結(jié)果，有干擾時(shí)得出的定位誤差系數(shù)大，即誤差較大。大廳測試結(jié)果見表3所列。

由表3可知，相較于環(huán)境復(fù)雜的教室，在較為空曠的大廳所獲得的誤差系數(shù)較小，較準(zhǔn)確。

（3）測試結(jié)果分析

a.同一間教室有無干擾時(shí)的結(jié)果對比分析

根據(jù)在教室C108測得的兩組數(shù)據(jù)，對采樣點(diǎn)的真實(shí)位置和定位結(jié)果進(jìn)行對比分析，如圖11所示。

在圖11中，實(shí)心圓表示采樣點(diǎn)的真實(shí)位置，空心圓表示教室內(nèi)無干擾時(shí)定位的結(jié)果，空心三角形表示教室內(nèi)有干擾時(shí)定位的結(jié)果。真實(shí)位置和定位結(jié)果兩點(diǎn)相連，其連線直觀地顯示了兩點(diǎn)間的差距，這種差距即定位誤差。相較于教室內(nèi)有干擾時(shí)的定位結(jié)果，無干擾時(shí)產(chǎn)生的誤差明顯較小。

b.大小相近的教室與空曠空間的結(jié)果對比分析

在教室測試的數(shù)據(jù)里隨機(jī)抽取6組并與在大廳測試的數(shù)據(jù)進(jìn)行對比分析，如圖12所示。

在圖12中，折線1表示教室內(nèi)采樣點(diǎn)的測試誤差系數(shù)，折線2表示大廳內(nèi)采樣點(diǎn)的測試誤差系數(shù)?？梢院苊黠@地看出，折線1的誤差系數(shù)整體比折線2大，因此，在大廳內(nèi)產(chǎn)生的誤差較小。

5 結(jié) 語

本文針對基于WiFi的室內(nèi)定位常用的傳統(tǒng)KNN算法中存在的問題，提出了一種改進(jìn)型KNN算法，在面對更復(fù)雜的室內(nèi)環(huán)境時(shí)可以保證精度，并有效降低運(yùn)算復(fù)雜度。基于Android平臺(tái)對這一改進(jìn)算法進(jìn)行了實(shí)現(xiàn)和測試，測試結(jié)果表明，該算法達(dá)到了預(yù)期效果，具有一定的可行性。

參考文獻(xiàn)

[1] 姜樂水.淺談無線局域網(wǎng)（WLAN）技術(shù)[J].信息技術(shù)與信息化，2012（5）：64-67.

[2] 潘焱，田華，魏安全.無線通信系統(tǒng)與技術(shù)[M].北京：人民郵電出版社，2011：147-148.

[3] 張瑞生，劉曉輝.無線局域網(wǎng)搭建與管理[M].電北京：子工業(yè)出版社，2011：14.

[4] 劉智敏，陽凡林，獨(dú)知行.衛(wèi)星定位原理及應(yīng)用的教學(xué)改革與實(shí)踐[J].測繪工程，2010，19（3）：77-80.

[5] 袁晶.大規(guī)模軌跡數(shù)據(jù)的檢索、挖掘和應(yīng)用[D].合肥：中國科學(xué)技術(shù)大學(xué)，2012.

[6] 王建平，余根堅(jiān)，李曉穎，等.無線網(wǎng)絡(luò)技術(shù)[M].北京：清華大學(xué)出版社，2013：180-181.

[7] 黎連業(yè)，王安，李龍.無線網(wǎng)絡(luò)與應(yīng)用技術(shù)[M].北京：清華大學(xué)出版社，2013：104-105.

[8] 姜莉.基于WiFi室內(nèi)定位關(guān)鍵技術(shù)的研究[D]. 大連：大連理工大學(xué)，2010.

[9] 陳典全.LBS中基于軌跡的用戶行為特征分析[J].全球定位系統(tǒng)，2011，36（6）：58-61.

[10] 羅紀(jì)清，萬恩秀.超聲引導(dǎo)下不同定位方法在體外碎石中的應(yīng)用[J].檢驗(yàn)醫(yī)學(xué)與臨床，2017，14（2）：261-263.

[11] 宋偉清，周廉，白濤，等.基于逐元暗電流抑制的紅外線探測器讀出電路研究[J].紅外，2015，36（4）：13-19.

[12] 熊永平，孫利民，牛建偉，等.機(jī)會(huì)網(wǎng)絡(luò)[J].軟件學(xué)報(bào)，2009，20（1）：124-137.

[13] 龔世雄.淺析RFID技術(shù)及其應(yīng)用[J].中國科技信息，2013（3）：52-53.

[14] 高仁強(qiáng)，張曉盼，熊艷，等.模糊數(shù)學(xué)的WiFi室內(nèi)定位算法[J].測繪科學(xué)，2016，41（10）：142-148.

[15] 盧恒惠，劉興川，張超，等.基于三角形與位置指紋識(shí)別算法的WiFi定位比較[J].移動(dòng)通信，2010，34（10）：72-76.

[16] 李揚(yáng).WiFi技術(shù)原理及應(yīng)用研究[J].科技信息，2010（6）：241.

[17] 賀遠(yuǎn)華，黎洪生.距離幾何的TOA無線定位算法[J].計(jì)算機(jī)工程與應(yīng)用，2010，46（12）：112-114.

[18] 魯?shù)び?，高春利，劉浩?基于無線時(shí)鐘同步的超寬帶TDOA定位系統(tǒng)設(shè)計(jì)[J].節(jié)能， 2017，36（1）：66-68.

[19] S TOMIC，M BEKO， D RUI，et al. Distributed RSS-AoA based localization with unknown transmit powers[J].IEEE wireless communication letters， 2016，5（4）：1.

[20] 薛衛(wèi)星，邱衛(wèi)寧，花向紅，等.RSSI信號特征值對WiFi室內(nèi)定位精度的影響分析[J].測繪地理信息，2016，41（4）：23-26.

[21] 孫學(xué)康，劉勇.無線傳輸與接入技術(shù)[M].北京 ：人民郵電出版社，2010：298-301.

[22] 趙小東.Android平臺(tái)下基于無線信號強(qiáng)度的定位系統(tǒng)的實(shí)現(xiàn)[D]. 哈爾濱：哈爾濱工業(yè)大學(xué)，2011.

[23] 王淑婷.基于位置指紋的WiFi定位算法研究[D].長春 ：吉林大學(xué)，2015.

[24] CHEN L， L? M， QIAN Y. A personal route prediction system based on trajectory data mining[J].Information sciences an international journal. 2011，181（7）：1264-1284.

[25] 王陽，葉芝慧，馮奇，等. 基于Android的室內(nèi)WiFi定位系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[J].電子測量技術(shù)，2016，39（9）：16-19.

[26] 王考杰，鄭雪峰，宋一丁，等.面向軌跡數(shù)據(jù)流的KNN近似查詢[J].計(jì)算機(jī)工程，2011，37（16）：17-20.

[27] 李偉.Android中人為改變程序生命周期的研究[J].計(jì)算機(jī)應(yīng)用與軟件，2013，30（9）：205-207.

[28] 羅利.基于Android的WiFi室內(nèi)定位技術(shù)研究[D].成都：西南交通大學(xué)，2014.

[29] 卞國龍，黃海松，葛至崢，等.無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位技術(shù)的優(yōu)化[J].激光雜志，2017，38（3）：69-74.

[30] 張建平.基于WiFi的室內(nèi)定位系統(tǒng)設(shè)計(jì)和算法研究[J].自動(dòng)化技術(shù)與應(yīng)用，2016，35（12）：53-56.

[31] MAHAJAN R，BALASUBRAMANIAN A，VENKATARAMANI A，et al. Interactive WiFi connectivity for moving vehicles[J].Proceeding of sigcomn，2013， 38（4）：427-438.