基于WiFi的室內(nèi)定位算法的研究

肖靜，薛楠，高員

（1.工業(yè)和信息化部電子第五研究所，廣東廣州510610曰2.工業(yè)和信息化部電子第五研究所華東分所，江蘇蘇州215000）

基于WiFi的室內(nèi)定位算法的研究

肖靜1，薛楠2，高員1

（1.工業(yè)和信息化部電子第五研究所，廣東廣州510610曰2.工業(yè)和信息化部電子第五研究所華東分所，江蘇蘇州215000）

院隨著現(xiàn)代社會(huì)科技水平的不斷提高和通信技術(shù)的愈加完善，定位技術(shù)受到了用戶越來越多的關(guān)注遙WiFi定位技術(shù)具有在室內(nèi)獲取便利堯覆蓋范圍廣堯信息傳輸速度快和搭建成本低廉等優(yōu)點(diǎn)而得到了廣泛的應(yīng)用遙提出了一種基于WiFi技術(shù)的位置指紋定位算法，稱為快速定位算法，極大地提高了計(jì)算效率，并且仍然能夠保持室內(nèi)定位的精確性遙基于此，設(shè)計(jì)并實(shí)現(xiàn)了應(yīng)用于Android終端的室內(nèi)定位系統(tǒng)遙

院無線保真曰位置指紋定位技術(shù)曰匹配算法

0 引言

人們?cè)谌粘Ｉ钪衅惹械匦枨缶唧w的位置信息，當(dāng)置身于陌生的環(huán)境中時(shí)更是如此，定位技術(shù)正是為了滿足人們的這種需求而逐漸地發(fā)展起來的一種技術(shù)遙定位技術(shù)分為室外定位技術(shù)和室內(nèi)定位技術(shù)遙在室外定位領(lǐng)域，一般采用GPS技術(shù)進(jìn)行定位，EPS定位系統(tǒng)得到了廣泛的應(yīng)用曰而在室內(nèi)定位領(lǐng)域，由于GPS信號(hào)受到建筑物堯室內(nèi)物品的干擾，信號(hào)會(huì)出現(xiàn)衰減，定位精度低，因而使用GPS無法滿足室內(nèi)定位的要求遙而WiFi網(wǎng)絡(luò)具有通信快速堯部署方便的特點(diǎn)，因此，其在室內(nèi)場(chǎng)所廣受歡迎，將WiFi技術(shù)應(yīng)用于室內(nèi)定位成為了目前的一個(gè)研究熱點(diǎn)遙

利用WiFi的信號(hào)強(qiáng)度進(jìn)行定位的技術(shù)主要分為兩種，即傳輸損耗定位法和位置指紋定位法遙前者將信號(hào)強(qiáng)度計(jì)算折耗后轉(zhuǎn)化為距離測(cè)量值并建立數(shù)學(xué)模型，但是，信號(hào)在傳輸?shù)倪^程中由于受到距離堯障礙物等因素的影響而產(chǎn)生的折耗并不能被準(zhǔn)確地估量，所以利用傳輸損耗法難以建立準(zhǔn)確的模型并保持穩(wěn)定的精度曰采用位置指紋法進(jìn)行定位的精度高，但事先需要建立一個(gè)完整堯科學(xué)的數(shù)據(jù)庫幷進(jìn)行維護(hù)遙

1 位置指紋定位技術(shù)

一個(gè)終端發(fā)射的無線信號(hào)經(jīng)過反射和折射產(chǎn)生的多徑信號(hào)在穩(wěn)定的環(huán)境中的任一位置處表現(xiàn)的特征性質(zhì)都是唯一的，這種特征性質(zhì)便可以被用做指紋遙一個(gè)指紋信息關(guān)聯(lián)一個(gè)位置信息即可將采集到的無線信號(hào)轉(zhuǎn)變?yōu)檩敵龅奈恢眯畔ⅲ瑥亩鴮?shí)現(xiàn)定位的功能遙

位置指紋定位一般分為離線階段和在線階段遙離線階段需要在待定位的區(qū)域中采集無線信號(hào)信息，將在參考點(diǎn)采集的無線信號(hào)的信息和參考點(diǎn)的空間位置存入數(shù)據(jù)庫中曰在線階段需要在待定位區(qū)域中的一個(gè)位置處采集無線信號(hào)信息，通過匹配算法輸出所在的空間位置遙

采用位置指紋定位技術(shù)，可以利用現(xiàn)有的AP熱點(diǎn)，不需要增加其他設(shè)備，而且定位的精度高，但是需要在離線階段建立數(shù)據(jù)庫，而且對(duì)數(shù)據(jù)庫的更新維護(hù)需要花費(fèi)大量的時(shí)間遙

2 匹配算法

根據(jù)測(cè)量結(jié)果可知，WiFi信號(hào)的強(qiáng)度一般分布在-30～120 dBm之間，負(fù)號(hào)后面的數(shù)值越小則信號(hào)的強(qiáng)度越大遙即使在日常生活中我們也能發(fā)現(xiàn)WiFi信號(hào)時(shí)好時(shí)壞，事實(shí)上，WiFi信號(hào)的強(qiáng)度具有時(shí)變的特性，所以采用位置指紋定位的方法進(jìn)行定位時(shí)在在線階段不能直接地使用WiFi信號(hào)強(qiáng)度進(jìn)行匹配，本文采用將WiFi信號(hào)強(qiáng)度的大小轉(zhuǎn)化為信號(hào)熱點(diǎn)之間的關(guān)系記錄并進(jìn)行匹配遙

圖1為用戶和信號(hào)熱點(diǎn)的示例圖，該環(huán)境由ROOM1和ROOM2兩個(gè)房間組成，兩個(gè)房間中分布了USERA堯USERB和USERC 3個(gè)用戶，房間外部存在AP1堯AP2堯AP3堯AP4堯AP5和AP66個(gè)信號(hào)熱點(diǎn)遙首先，在離線階段采集USERB和USERC處的信號(hào)強(qiáng)度，所得到的結(jié)果如表1所示遙

圖1 用戶和信號(hào)熱點(diǎn)示例圖

表1USERB和USERC處采集到的信號(hào)熱點(diǎn)的信息

表1為在同一地點(diǎn)多次采集的信號(hào)信息取平均值后的結(jié)果，按照信號(hào)強(qiáng)度的值由大到小進(jìn)行排序遙考慮到信號(hào)熱點(diǎn)-信號(hào)強(qiáng)度這組值在在線階段難以進(jìn)行匹配，所以將其轉(zhuǎn)化為信號(hào)熱點(diǎn)-信號(hào)熱點(diǎn)的形式遙具體的操作是將比信號(hào)熱點(diǎn)的信號(hào)強(qiáng)度小X dBm的信號(hào)熱點(diǎn)作為該信號(hào)熱點(diǎn)的值遙

表2為根據(jù)信號(hào)熱點(diǎn)-信號(hào)強(qiáng)度形式的數(shù)據(jù)轉(zhuǎn)化形成的信號(hào)熱點(diǎn)-信號(hào)熱點(diǎn)數(shù)據(jù)遙考慮到WiFi信號(hào)的時(shí)變特性，此處X取的值為10遙此時(shí)離線階段的工作完成遙

在線階段采用的匹配算法如下所述:

表2 信號(hào)熱點(diǎn)-信號(hào)熱點(diǎn)形式的信號(hào)熱點(diǎn)信息

即在待定位的位置以信號(hào)熱點(diǎn)-信號(hào)強(qiáng)度的形式采集此處的WiFi信號(hào)信息，隨后將其轉(zhuǎn)化為信號(hào)熱點(diǎn)-信號(hào)熱點(diǎn)的形式遙然后，與在離線階段采集到的每一處信息進(jìn)行匹配，匹配規(guī)則如下:AP熱點(diǎn)都相同的情況下，存在相同的AP熱點(diǎn)的信號(hào)熱點(diǎn)的值最大的即為待定位點(diǎn)最可能所在的地點(diǎn)遙為了進(jìn)一步地提高匹配效率，可以先將采集到的待定位數(shù)據(jù)轉(zhuǎn)化成信號(hào)熱點(diǎn)-信號(hào)熱點(diǎn)數(shù)據(jù)，然后將待定位點(diǎn)的前兩個(gè)信號(hào)熱點(diǎn)與離線階段采集的數(shù)據(jù)庫中的數(shù)據(jù)的前兩個(gè)信號(hào)熱點(diǎn)進(jìn)行比較，當(dāng)兩個(gè)信號(hào)熱點(diǎn)都不相同時(shí)則放棄與此數(shù)據(jù)進(jìn)行進(jìn)一步的匹配，這樣一來便可以大幅度地提高匹配效率遙

離線階段采集的待定位點(diǎn)USERA的信息如表3所示遙

表3 待定位點(diǎn)USERA信息

根據(jù)所采集到的待定位點(diǎn)USERA的信息，按照匹配規(guī)則，USERB的得分為9，USERC的得分為0，則USERA點(diǎn)更可能存在于USERB處遙

3 匹配算法的優(yōu)勢(shì)

目前在室內(nèi)定位領(lǐng)域普遍使用的是KNN定位算法遙運(yùn)用K近鄰法首先需要知道在線階段測(cè)量得到信號(hào)強(qiáng)度均值[s1，s2，噎，sn]和在離線階段采集得到的信號(hào)均值[S1，S2，噎，Sn]之間的距離遙假定待定位區(qū)域存在m個(gè)參考點(diǎn)，n個(gè)AP熱點(diǎn)，Sij為待定位區(qū)域中第i個(gè)參考點(diǎn)處的第j個(gè)AP熱點(diǎn)的信號(hào)強(qiáng)度均值，sj為在線階段測(cè)量得到的第j個(gè)AP熱點(diǎn)的信號(hào)強(qiáng)度均值，i=1，2，噎，m，j=1，2，噎，n遙AP熱點(diǎn)的距離可以采用如下公式表示:

3.1 較低的時(shí)間復(fù)雜度

KNN是一種懶惰算法，離線階段沒有對(duì)樣本進(jìn)行分類，在線階段才去找k個(gè)近鄰遙這樣導(dǎo)致了KNN算法的構(gòu)造模型很簡單，但在對(duì)測(cè)試樣本分類的系統(tǒng)開銷大，因?yàn)橐獟呙枞坑?xùn)練樣本并計(jì)算距離遙而匹配算法在離線階段采集測(cè)量數(shù)據(jù)時(shí)已經(jīng)對(duì)樣本進(jìn)行分類，只需要在在線階段與待定位的點(diǎn)進(jìn)行匹配即可，尤其在需要進(jìn)行連續(xù)定位的時(shí)候，匹配算法的效率會(huì)遠(yuǎn)遠(yuǎn)高于KNN算法遙

待定位區(qū)域中存在N個(gè)AP熱點(diǎn)，在在線階段對(duì)一個(gè)在離線階段采集的點(diǎn)判斷是否為待定位點(diǎn)所需要進(jìn)行比較的次數(shù)如表4所示遙

表4 算法比較一

在離線階段采集得到的點(diǎn)是M個(gè)的情況下，在線階段進(jìn)行匹配所需要進(jìn)行的總的比較次數(shù)如表5所示遙

表5 算法比較二

引入匹配算法中的優(yōu)化，根據(jù)排列組合的規(guī)律，在N個(gè)AP熱點(diǎn)的情況下，某兩個(gè)AP至少一個(gè)排在前兩位的情況有4（N-1）浴-2種，而總的排列組合情況為N浴種，則某兩個(gè)AP至少一個(gè)排在前兩位的概率約為4/N遙引入優(yōu)化后在線階段進(jìn)行匹配所需要進(jìn)行的總的比較次數(shù)如表6所示遙

表6 算法比較三

因此，AP熱點(diǎn)的數(shù)量越多，匹配算法的效率就越突出遙

3.2 較小受到錯(cuò)誤數(shù)據(jù)的影響

K近鄰算法采用了多次方運(yùn)算，錯(cuò)誤的數(shù)據(jù)會(huì)在進(jìn)行多次方運(yùn)算后被放大，直至對(duì)最終的結(jié)果造成不可忽視的影響遙而匹配算法首先會(huì)對(duì)采集得到的數(shù)據(jù)進(jìn)行兩個(gè)不同AP熱點(diǎn)信號(hào)強(qiáng)度的比較，將大小相差超過10 dB的AP取出，這一步驟會(huì)使錯(cuò)誤的數(shù)據(jù)有極大的幾率被縮小，即使錯(cuò)誤的數(shù)據(jù)經(jīng)過該步驟處理后未被過濾，在匹配階段其對(duì)最后的得分的影響也是非常微小的遙

4 結(jié)束語

本文提出了一種匹配算法，并將其應(yīng)用到了安卓平臺(tái)上，實(shí)現(xiàn)了一款利用WiFi信號(hào)進(jìn)行室內(nèi)定位功能的應(yīng)用程序遙該算法不僅擺脫了傳統(tǒng)定位所需要明確的信號(hào)發(fā)送端的位置的局限性，保證了在不竊取AP熱點(diǎn)位置等敏感信息的前提下實(shí)現(xiàn)定位的功能，而且比一般的位置指紋定位算法運(yùn)算量更小，保障了系統(tǒng)的靈活性，可以應(yīng)用于智能手機(jī)等新興移動(dòng)終端遙如何進(jìn)一步地提高匹配算法的計(jì)算效率，進(jìn)一步地提高室內(nèi)定位的精度是值得研究的問題遙

院

[1]王小平.無線傳感器網(wǎng)絡(luò)定位技術(shù)研究[D].長沙:國防科學(xué)技術(shù)大學(xué)，2010.

[2]URNETTE E.Hello，Android:introducing Google爺s mobile development platform[M].London:Pragmatic Bookshelf，2010.

[3]吳彬，李俊娥.無線傳感器網(wǎng)絡(luò)在室內(nèi)定位中的應(yīng)用研究[J].計(jì)算機(jī)科學(xué)，2013，40（5）:115-117.

[4]王春東.基于802.11的室內(nèi)定位算法研究[J].計(jì)算機(jī)工程，2007，33（7）:94-95.

[5]李昊.位置指紋定技術(shù)[J].山西電子技術(shù)，2007，36（5）:84-87.

[6]楊清.基于指紋的無線室內(nèi)精確定位方法研究[D].杭州:浙江大學(xué)，2011.

Research on Indoor Positioning Algorithm Based on WiFi

XIAO Jing1，XUE Nan2，GAO Yuan1
（1.CEPREI，Guangzhou 510610，China曰2.CEPREI-EAST，Suzhou 215000，China）

With the continuous improvement of the level of science and technology in modern society and the increasing perfection of communication technology，positioning technology has been paid more and more attention.WiFi positioning technology has the advantages of convenient access in the room，wide coverage，high information transmission speed and low building cost，so it has been widely used.A location fingerprint positioning algorithm based on WiFi technology，namely fast positioning algorithm，is proposed，which greatly improves the computational efficiency，and can still maintain the accuracy of indoor positioning.Based on this，the indoor positioning system applied to the Android terminal is designed and implemented.

WiFi曰location fingerprint positioning technology曰matching algorithm

院TN 926+.24

院A

院1672-5468（2017）03-0044-04

10.3969/j.issn.1672-5468.2017.03.009

院2016-10-09

院肖靜（1982-），女，湖北襄陽人，工業(yè)和信息化部電子第五研究所軟件質(zhì)量工程研究中心工程師，碩士，主要從事軟件測(cè)試工作。