肖靜，薛楠，高員

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

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

肖靜1，薛楠2，高員1

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

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

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

0 引言

人們在日常生活中迫切地需求具體的位置信息，當置身于陌生的環(huán)境中時更是如此，定位技術正是為了滿足人們的這種需求而逐漸地發(fā)展起來的一種技術遙定位技術分為室外定位技術和室內(nèi)定位技術遙在室外定位領域，一般采用GPS技術進行定位，EPS定位系統(tǒng)得到了廣泛的應用曰而在室內(nèi)定位領域，由于GPS信號受到建筑物堯室內(nèi)物品的干擾，信號會出現(xiàn)衰減，定位精度低，因而使用GPS無法滿足室內(nèi)定位的要求遙而WiFi網(wǎng)絡具有通信快速堯部署方便的特點，因此，其在室內(nèi)場所廣受歡迎，將WiFi技術應用于室內(nèi)定位成為了目前的一個研究熱點遙

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

1 位置指紋定位技術

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

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

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

2 匹配算法

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

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

圖1 用戶和信號熱點示例圖

表1USERB和USERC處采集到的信號熱點的信息

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

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

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

表2 信號熱點-信號熱點形式的信號熱點信息

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

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

表3 待定位點USERA信息

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

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

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

3.1 較低的時間復雜度

KNN是一種懶惰算法，離線階段沒有對樣本進行分類，在線階段才去找k個近鄰遙這樣導致了KNN算法的構造模型很簡單，但在對測試樣本分類的系統(tǒng)開銷大，因為要掃描全部訓練樣本并計算距離遙而匹配算法在離線階段采集測量數(shù)據(jù)時已經(jīng)對樣本進行分類，只需要在在線階段與待定位的點進行匹配即可，尤其在需要進行連續(xù)定位的時候，匹配算法的效率會遠遠高于KNN算法遙

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

表4 算法比較一

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

表5 算法比較二

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

表6 算法比較三

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

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

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

4 結束語

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

院

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

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

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

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

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

[6]楊清.基于指紋的無線室內(nèi)精確定位方法研究[D].杭州:浙江大學，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ì)量工程研究中心工程師，碩士，主要從事軟件測試工作。