楊鵬　(浙江工貿(mào)職業(yè)技術(shù)學(xué)院成人教育學(xué)院，浙江 溫州 325000)

熊曾剛　(湖北工程學(xué)院計(jì)算機(jī)與信息科學(xué)學(xué)院，湖北 孝感 432000)

?

基于WiFi的室內(nèi)定位系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)

楊鵬(浙江工貿(mào)職業(yè)技術(shù)學(xué)院成人教育學(xué)院，浙江 溫州 325000)

熊曾剛(湖北工程學(xué)院計(jì)算機(jī)與信息科學(xué)學(xué)院，湖北 孝感 432000)

[摘要]針對(duì)傳統(tǒng)的指紋識(shí)別室內(nèi)定位算法中指紋地圖制作階段需要大量的人工測(cè)量成本和室內(nèi)環(huán)境中無(wú)線信號(hào)不穩(wěn)定等問(wèn)題，設(shè)計(jì)了一套基于K-strongest RSS Index(KSRI)算法的室內(nèi)定位系統(tǒng)。通過(guò)KSRI算法的定位原理、定位模型和定位算法說(shuō)明了其可行性，并進(jìn)行了系統(tǒng)軟件設(shè)計(jì)和系統(tǒng)性能測(cè)試。相比NN(Nearest Neighbor)和KNN(K-Nearest Neighbor)算法，KSRI算法在定位精確度、定位穩(wěn)定性和計(jì)算量等方面均取得了最佳性能?；贙SRI算法的室內(nèi)定位系統(tǒng)可以很好的解決室內(nèi)的定位問(wèn)題，具有很大的使用價(jià)值和應(yīng)用前景。

[關(guān)鍵詞]室內(nèi)定位；指紋識(shí)別；KSRI算法

隨著信息時(shí)代的到來(lái)，導(dǎo)航與通信技術(shù)在互相交融中飛速的發(fā)展，導(dǎo)航系統(tǒng)與通信系統(tǒng)緊密的結(jié)合，使用戶在導(dǎo)航定位信息產(chǎn)生更大的應(yīng)用價(jià)值。GPS在室外定位中得到廣泛的應(yīng)用[1]，但在室內(nèi)或者建筑物密集的室內(nèi)很難搜索到衛(wèi)星信號(hào)，因此，人們提出了許多室內(nèi)定位技術(shù)解決方案，如A-GPS定位技術(shù)[2]、超聲波定位技術(shù)(Ultrasonic)[3]、超寬帶定位技術(shù)(UWB)[4]、紅外線定位技術(shù)(infrared)[5]、藍(lán)牙定位技術(shù)(Bluetooth)[6]、射頻識(shí)別定位技術(shù)(RFID)[7]、ZigBee定位技術(shù)[8]、地磁定位技術(shù)[9]、FM廣播定位技術(shù)[10]和WiFi[11，12]定位技術(shù)等。

目前基于WiFi的室內(nèi)定位系統(tǒng)中，絕大多數(shù)都是基于接收信號(hào)強(qiáng)度(Received Signal Strength，RSS)的指紋識(shí)別算法[13～15]。該算法是一種基于指紋數(shù)據(jù)庫(kù)的匹配定位算法，通過(guò)建立定位區(qū)域信號(hào)強(qiáng)度的指紋數(shù)據(jù)庫(kù)，再與實(shí)時(shí)采集的信號(hào)強(qiáng)度進(jìn)行匹配來(lái)達(dá)到位置估計(jì)的目的。

基于指紋識(shí)別的算法可以分為離線測(cè)試階段和在線定位階段，其定位算法主要有2個(gè)缺點(diǎn)：第一，離線建立指紋數(shù)據(jù)庫(kù)階段需要人工手動(dòng)測(cè)量，人力成本較大；第二，信號(hào)強(qiáng)度容易受到環(huán)境干擾，造成在線定位階段測(cè)量到的信號(hào)強(qiáng)度有波動(dòng)，造成匹配指紋錯(cuò)誤定位誤差較大。為了盡量降低上述2個(gè)缺點(diǎn)帶來(lái)的影響，筆者提出了一種基于K-strongest RSS Index(KSRI)算法的室內(nèi)定位系統(tǒng)的設(shè)計(jì)方案。

1定位原理

隨著室內(nèi)環(huán)境中的WiFi無(wú)線網(wǎng)絡(luò)的廣泛普及，利用WiFi信號(hào)進(jìn)行室內(nèi)定位變得更具有可行性，大多數(shù)的室內(nèi)定位技術(shù)都是基于RSS作為位置估計(jì)。在理論上，無(wú)線信號(hào)在自由空間內(nèi)傳播距離d后，接受信號(hào)強(qiáng)度可表示為：

(1)

式中，Pr為接受點(diǎn)的信號(hào)強(qiáng)度；Po為接受點(diǎn)的參考距離；n為由環(huán)境因素決定的路徑損耗指數(shù)； do為參考距離，一般選取1m；Xσ是服從高斯正太分布的隨機(jī)數(shù)。

從信號(hào)衰減的模型(式(1))可以看出，在不同點(diǎn)接收的信號(hào)強(qiáng)度不一樣，就可根據(jù)信號(hào)強(qiáng)度與坐標(biāo)一一對(duì)應(yīng)來(lái)建立指紋地圖。

室內(nèi)環(huán)境中，信號(hào)在傳播過(guò)程中很容易受到不同程度的影響，造成影響的因素主要是非視距傳播、多徑傳播和陰影效應(yīng)。無(wú)線信號(hào)傳播衰減模型很難表征距離和信號(hào)強(qiáng)度間的映射關(guān)系，但是在某一點(diǎn)接收到的信號(hào)強(qiáng)度雖也存在一定的波動(dòng)，但基本上是趨于穩(wěn)定的。這種不同的區(qū)域具有不同的信號(hào)強(qiáng)度可以作為指紋信息，為基于指紋識(shí)別的室內(nèi)定位技術(shù)提供了可能性。

2定位模型

基于指紋識(shí)別的定位算法的定位過(guò)程中，離線測(cè)試階段是在定位區(qū)域選取若干個(gè)參考點(diǎn)，收集參考點(diǎn)的信號(hào)強(qiáng)度并保存在數(shù)據(jù)庫(kù)；在線定位階段則是根據(jù)實(shí)時(shí)采集的信號(hào)強(qiáng)度去匹配數(shù)據(jù)庫(kù)中的值，從而獲得目標(biāo)的位置估計(jì)。

2.1離線測(cè)試

由于移動(dòng)終端在不同方向接收同樣的信號(hào)強(qiáng)度是有差異的，所以建立指紋地圖過(guò)程中需要對(duì)每一個(gè)參考點(diǎn)采集不同方向的指紋信息。指紋地圖Ω表示如下：

(2)

為了減少人工測(cè)量成本，系統(tǒng)開(kāi)發(fā)了基于手機(jī)的指紋地圖管理軟件來(lái)智能地創(chuàng)建指紋地圖。首先上傳定位區(qū)域的平面地圖，然后在平面地圖上選擇需要建立指紋的參考點(diǎn)，開(kāi)始測(cè)量指紋信息，最后保存指紋數(shù)據(jù)。依次類推，就可以很方便的建立指紋地圖。

2.2在線定位

圖1　信號(hào)波動(dòng)

圖2　定位流程圖

為研究室內(nèi)環(huán)境對(duì)信號(hào)干擾的問(wèn)題，筆者以某高?，F(xiàn)代教育中心為定位環(huán)境，對(duì)比了在相同的位置不同的時(shí)間測(cè)量的信號(hào)強(qiáng)度，隨機(jī)的選取整棟樓的3560個(gè)樣本中的100個(gè)樣本作為研究對(duì)象，2次測(cè)量的信號(hào)強(qiáng)度波動(dòng)如圖1所示。

信號(hào)的波動(dòng)是造成定位階段進(jìn)行匹配時(shí)主要的誤差來(lái)源。在對(duì)信號(hào)強(qiáng)度的波動(dòng)研究過(guò)程中，發(fā)現(xiàn)信號(hào)有一定范圍的波動(dòng)，因此設(shè)計(jì)了KSRI算法來(lái)解決錯(cuò)誤匹配的問(wèn)題，從而提高定位的性能。

3基于KSRI的定位算法

與傳統(tǒng)的指紋定位系統(tǒng)一樣，基于KSRI算法的定位系統(tǒng)也分為離線測(cè)試階段和在線定位階段。

離線測(cè)試階段與傳統(tǒng)的方法主要有2個(gè)不同點(diǎn)：該系統(tǒng)的指紋地圖是通過(guò)開(kāi)發(fā)的指紋地圖管理軟件來(lái)進(jìn)行，在每個(gè)參考點(diǎn)測(cè)量指紋信息之后，自動(dòng)保存在軟件的數(shù)據(jù)庫(kù)里；傳統(tǒng)的指紋是選取接受到的信號(hào)強(qiáng)度作為指紋信息，但是該系統(tǒng)是采用每個(gè)參考點(diǎn)的最強(qiáng)信號(hào)的K個(gè)接入點(diǎn)作為指紋特性，該階段是通過(guò)指紋地圖管理軟件來(lái)實(shí)現(xiàn)。

在定位階段，在待測(cè)點(diǎn)檢測(cè)到信號(hào)強(qiáng)度后，選取里面最強(qiáng)信號(hào)的K個(gè)接入點(diǎn)與新建的指紋地圖I匹配來(lái)達(dá)到定位的目的，該階段是通過(guò)室內(nèi)定位軟件來(lái)實(shí)現(xiàn)，系統(tǒng)定位流程如圖2所示。

在匹配指紋地圖過(guò)程中，用KSRI算法來(lái)獲取最佳位置估計(jì)。KSRI算法通過(guò)對(duì)比實(shí)時(shí)檢測(cè)到的最強(qiáng)信號(hào)的接入點(diǎn)與指紋地圖I中對(duì)應(yīng)的接入點(diǎn)進(jìn)行對(duì)比，如果最強(qiáng)信號(hào)的K個(gè)接入點(diǎn)完全一樣，那么對(duì)所有符合要求的參考點(diǎn)對(duì)應(yīng)的坐標(biāo)取平均值，即可以估算出待測(cè)點(diǎn)的位置信息。如果K個(gè)接入點(diǎn)不全部相同，那就取最大相同個(gè)數(shù)的接入點(diǎn)對(duì)應(yīng)的坐標(biāo)來(lái)估算待測(cè)點(diǎn)位置。算法的偽代碼如下：

輸入：指紋地圖I，實(shí)時(shí)檢測(cè)到的指紋信息Indexω

輸出：最佳位置估計(jì)

1.int count=0； 新建鏈表list；

2.for 0 to I.size

3.for 1 to Indexω.size

4.if Indexj==Indexω then

5.count++

6.把指紋地圖I中所有符合要求的APj存入list；

7.end if

8.end for

9.end for

10.對(duì)list中所有AP對(duì)應(yīng)的坐標(biāo)取平均值，即最佳位置估計(jì)

4系統(tǒng)軟件設(shè)計(jì)

圖3　軟件設(shè)計(jì)

系統(tǒng)的軟件主要包括指紋地圖管理軟件和室內(nèi)定位軟件(見(jiàn)圖3)。指紋地圖管理軟件是通過(guò)軟件智能地建立指紋數(shù)據(jù)庫(kù)，可以大量減少的人工成本，提高指紋地圖的創(chuàng)建效率。其主要包括創(chuàng)建指紋地圖和更新指紋地圖2個(gè)功能。創(chuàng)建指紋地圖是在一個(gè)新的室內(nèi)環(huán)境中，通過(guò)該軟件可以高效的建立一個(gè)指紋數(shù)據(jù)庫(kù)；更新指紋地圖功能是在已有的指紋地圖的基礎(chǔ)上，選取部分點(diǎn)來(lái)更新指紋數(shù)據(jù)，由于環(huán)境的變化，可能只是部分參考點(diǎn)的指紋信息有所變化，而不需要重建整個(gè)指紋地圖。

室內(nèi)定位軟件是KSRI定位算法的實(shí)現(xiàn)的載體，用戶安裝了軟件就可以在室內(nèi)環(huán)境中實(shí)現(xiàn)定位的功能。其主要通過(guò)實(shí)時(shí)接收到的指紋信息匹配指紋地圖來(lái)達(dá)到定位的目的。“我的位置”是實(shí)現(xiàn)更新定位位置的功能，隨著手機(jī)的移動(dòng)，位置信息不斷的更新?！鞍姹靖隆笔歉萝浖臄?shù)據(jù)庫(kù)、地圖和新添加的功能。

5系統(tǒng)性能測(cè)試

為了驗(yàn)證筆者提出的基于KSRI算法的室內(nèi)定位系統(tǒng)，選取了一棟5層的成“工”字行的建筑，在5層的區(qū)域里面總共部署了40個(gè)ARUBA AP-115的無(wú)線接入點(diǎn)。在整棟樓的走廊上選取了89個(gè)指紋參考點(diǎn)，整個(gè)試驗(yàn)過(guò)程中使用三星GALAXY SIII手機(jī)作為定位終端，手機(jī)安裝了開(kāi)發(fā)的指紋地圖管理軟件和室內(nèi)定位軟件。

針對(duì)該試驗(yàn)環(huán)境和數(shù)據(jù)，對(duì)KSRI算法與NN(nearest neighbor)和KNN(K-Nearest Neighbor)算法進(jìn)行了對(duì)比。在對(duì)比過(guò)程中，選取了4樓的22個(gè)參考點(diǎn)的880個(gè)數(shù)據(jù)作為研究對(duì)象。NN算法只選取接收到的所有信號(hào)強(qiáng)度中最強(qiáng)的一個(gè)與指紋地圖Ω進(jìn)行匹配。由于每個(gè)參考點(diǎn)可以接受的AP是有限的，整棟樓只安裝了40個(gè)AP(Access Point)，所以選取K=3來(lái)研究KNN算法的定位精度。在選取3個(gè)最強(qiáng)的信號(hào)之后，每個(gè)信號(hào)分別與指紋地圖中的對(duì)應(yīng)AP的信號(hào)進(jìn)行匹配，再選取3個(gè)最近鄰，然后對(duì)9個(gè)信號(hào)對(duì)應(yīng)的參考點(diǎn)取交集，最后對(duì)交集里面參考點(diǎn)對(duì)應(yīng)的坐標(biāo)取平均值來(lái)得到最終的定位結(jié)果。為保證公平起見(jiàn)，在KSRI算法中，同樣取K=3來(lái)評(píng)估定位的性能。

圖4　3種不同算法的曼哈頓定位誤差

由3種算法的曼哈頓定位誤差、平均誤差和方差對(duì)比(見(jiàn)圖4、圖5、圖6)可知，KSRI算法的曼哈頓定位誤差值小且最穩(wěn)定，平均定位誤差和定位誤差方差的值最小，表明KSRI算法在定位精度和定位的穩(wěn)定性上均優(yōu)于NN和KNN算法。

從獲得信號(hào)強(qiáng)度大小排序之后，筆者對(duì)3種的算法進(jìn)行了計(jì)算量的估計(jì)，以1次數(shù)據(jù)匹配定義為1個(gè)計(jì)算量，在該試驗(yàn)中，同樣選取了4樓的22個(gè)參考點(diǎn)作為研究目標(biāo)，對(duì)比結(jié)果(見(jiàn)圖7)表明，在22次定位過(guò)程中，KSRI的計(jì)算量居中，略高于NN。

圖5　3種不同算法的平均定位誤差　　　　　　　　　　　　圖6　3種不同算法的定位誤差方差

綜合定位精確度、定位穩(wěn)定性和計(jì)算量，很明顯KSRI算法取得了最佳的性能，這為室內(nèi)定位軟件的實(shí)現(xiàn)提供了重要的支撐。

6結(jié)語(yǔ)

筆者設(shè)計(jì)并實(shí)現(xiàn)了基于KSRI算法的室內(nèi)定位系統(tǒng)，相對(duì)于傳統(tǒng)的NN和KNN算法定位精確度和穩(wěn)定性得到了很大的提高，同時(shí)也保證了較低的計(jì)算量。針對(duì)提出的KSRI算法，開(kāi)發(fā)了相應(yīng)的手機(jī)應(yīng)用軟件：指紋地圖管理軟件和室內(nèi)定位軟件。開(kāi)發(fā)的軟件不僅能很方便的創(chuàng)建新的指紋地圖，同時(shí)也可以容易的獲得精確的室內(nèi)位置信息。試驗(yàn)測(cè)試表明，基于KSRI算法的室內(nèi)定位系統(tǒng)可以很好的解決室內(nèi)的定位問(wèn)題，不需要增加額外的硬件設(shè)備，具有很大的使用價(jià)值和應(yīng)用前景。

圖7　3種不同算法的計(jì)算量

[1]Bulusu N，Heidemann J，Estrin D. GPS-less low-cost outdoor localization for very small devices[J]. Personal Communications，IEEE，2000，7(5): 28～34.

[2] Zandbergen P A. Accuracy of iPhone locations: A comparison of assisted GPS， WiFi and cellular positioning[J]. Transactions in GIS，2009，13(s1): 5～25.

[3] Filonenko V，Cullen C，Carswell J. Investigating ultrasonic positioning on mobile phones[A].Indoor Positioning and Indoor Navigation (IPIN)，2010 International Conference on IEEE[C].2010: 1～8.

[4] Shahi A，Aryan A，West J S，et al. Deterioration of UWB positioning during construction[J]. Automation in Construction，2012(24): 72～80.

[5] Lee C， Chang Y， Park G，et al. Indoor positioning system based on incident angles of infrared emitters[A]. IECON 2004 30th Annual Conference of IEEE[C].2004: 2218～2222.

[6] Li Shuai，Lou Yue-sheng，Liu Bo. Bluetooth aided mobile phone localization: a nonlinear neural circuit approach[J]. ACM Transactions on Embedded Computing Systems (TECS)，2014，13(4): 78.

[7] Montaser A，Moselhi O. RFID indoor location identification for construction projects[J]. Automation in Construction，2014(39): 167～179.

[8] Luo H L. ZigBee-based intelligent indoor positioning system soft computing[J]. Soft Computing， 2014，18(3): 443～456.

[9] Chung J，Donahoe M，Schmandt C，et al. Indoor location sensing using geo-magnetism[A].Proceedings of the 9th international conference on Mobile systems， applica-tions，and services,ACM[C].2011: 141～154.

[10] Chen Yin， Lymberopoulos D，Liu Jie，et al. Indoor localization using FM signals[J]. Mobile Computing，IEEE Transactions on，2013，12(8): 1502～1517.

[11]聶爾豪，于重重，蘇維均，等. WiFi 實(shí)時(shí)定位算法研究[J]. 計(jì)算機(jī)應(yīng)用研究，2014，31(7)：2164～2168.

[12] Ficco M，Esposito C，Napolitano A. Calibrating Indoor Positioning Systemswith Low Efforts[J]. Mobile Computing，IEEE Transactions on，2014，13(4): 737～751.

[13] Jaffe A，Wax M. Single-Site Localization via Maximum Discrimination Multipath Fingerprinting[J]. IEEE Transactions on Signal Processing，2014，62(7): 1718～1728.

[14] Milioris D，Tzagkerakis G，Papakonatantinou A，et al. Low-dimensional signal-strength finger-print-based positioning in wireless LANs[J]. Ad hoc networks，2014，12: 100～114.

[15] Garcia-Valverde T，Garcia-Solala，Hagras H，et al. A fuzzy logic-based system for indoor local-ization using WiFi in ambient intelligent environments[J]. Fuzzy Systems，IEEE Transactions on，2013，21(4): 702～718.

[編輯]辛長(zhǎng)靜

[文獻(xiàn)標(biāo)志碼]A

[文章編號(hào)]1673-1409(2016)07-0067-05

[中圖分類號(hào)]TP391；TP302.1

[作者簡(jiǎn)介]楊鵬(1976-)，男，碩士，講師，現(xiàn)主要從事計(jì)算機(jī)應(yīng)用方面的教學(xué)與研究工作；E-mail：wzypyp@163.com。

[基金項(xiàng)目]湖北省自然科學(xué)基金項(xiàng)目(2014CFB188)；湖北省中青年科技創(chuàng)新團(tuán)隊(duì)項(xiàng)目(T201410)；溫州市2014年公益性科技計(jì)劃項(xiàng)目(G20140059)。

[收稿日期]2015-11-28

[引著格式]楊鵬，熊曾剛.基于WiFi的室內(nèi)定位系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[J].長(zhǎng)江大學(xué)學(xué)報(bào)(自科版)，2016,13(7)：67～72.