文獻(xiàn)標(biāo)識(shí)碼: A
DOI:10.16157/j.issn.0258-7998.2017.03.019
中文引用格式: 武一,,張冀釗. 基于Android平臺(tái)改進(jìn)的室內(nèi)WiFi定位算法的研究[J].電子技術(shù)應(yīng)用,2017,,43(3):77-79.
英文引用格式: Wu Yi ,,Zhang Jizhao. Research of improved indoor WiFi localization algorithm based on Android platform[J].Application of Electronic Technique,,2017,43(3):77-79.
0 引言
隨著通信技術(shù)和智能科技的不斷發(fā)展,定位技術(shù)在日常生活中發(fā)揮著越來(lái)越大的作用,,人們對(duì)定位服務(wù)的需求逐漸增大,。室外定位GPS以及基站定位技術(shù)已經(jīng)發(fā)展成熟,,出現(xiàn)了多種室內(nèi)定位技術(shù),如:RFID(射頻識(shí)別),、WiFi,、藍(lán)牙,、紅外線等,。定位方法有基于到達(dá)時(shí)間(TOA),、基于信號(hào)強(qiáng)度(RSS)、基于到達(dá)角度(AOA)的方法[1],,還有一些通過(guò)加速度傳感器等手機(jī)內(nèi)的集成傳感器件來(lái)實(shí)現(xiàn)定位[2]?,F(xiàn)階段,,智能手機(jī)相當(dāng)普及,WiFi也基本覆蓋大多數(shù)公共場(chǎng)所,,WiFi定位無(wú)需額外的硬件需求,,具有低成本,、低功耗、高精度等特點(diǎn),,因此其在眾多定位方法中具有很大的優(yōu)勢(shì),。
本文通過(guò)掃描室內(nèi)的WiFi信息,在Android平臺(tái)上通過(guò)改進(jìn)的指紋匹配定位方法實(shí)現(xiàn)室內(nèi)定位,。
1 WiFi位置指紋定位方法
1.1 指紋定位方法
基于WiFi無(wú)線網(wǎng)絡(luò)的定位技術(shù)有很多,,其中以基于信號(hào)強(qiáng)度RSS的定位技術(shù)最為常用[4],。在基于RSS的定位技術(shù)中位置指紋定位方法較為普遍,。位置指紋定位方法[5]分為數(shù)據(jù)采集階段和實(shí)時(shí)定位階段兩部分,。在數(shù)據(jù)采集階段,在區(qū)域內(nèi)均勻地選擇N個(gè)數(shù)據(jù)采集點(diǎn),,在每個(gè)采集點(diǎn),,通過(guò)安卓手機(jī)采集所有AP的RSS信息,并將所有RSS信息以及該點(diǎn)的坐標(biāo)(x,,y)存入數(shù)據(jù)庫(kù)[6],,等待第二階段調(diào)用。在實(shí)時(shí)定位階段,,用戶在未知位置發(fā)出定位請(qǐng)求,,安卓手機(jī)采集該點(diǎn)AP的RSS信息并傳送至數(shù)據(jù)庫(kù),通過(guò)匹配算法以及第一階段采集的RSS數(shù)據(jù)得到位置坐標(biāo)(x,,y)反饋給用戶,,定位完成[7]。
在第二階段定位過(guò)程中,,kNN算法是較為常用的一種傳統(tǒng)匹配算法,。
1.2 kNN算法(最鄰近算法)
臨近算法即k最鄰近分類算法(kNN,k-NearestNeighbor)[8],,核心思想是:如果一個(gè)樣本在特征空間中的k個(gè)最相鄰的樣本中的大多數(shù)屬于某一個(gè)類別,則該樣本也屬于這個(gè)類別,,并具有這個(gè)類別上樣本的特性,。
在kNN算法中要準(zhǔn)確選擇參數(shù)k的值,,當(dāng)k較小時(shí),選擇臨近點(diǎn)數(shù)量較小,,不能準(zhǔn)確地確定參考點(diǎn)的類別,,增大了誤差;當(dāng)選擇k較大時(shí),,則會(huì)選擇較遠(yuǎn)的點(diǎn),,導(dǎo)致定位結(jié)果不準(zhǔn)確。因此,,應(yīng)多次測(cè)量決定參數(shù)k的值,。本實(shí)驗(yàn)經(jīng)多次測(cè)試,k為3時(shí)誤差最小,,因此k取3,。
APn代表定位區(qū)域內(nèi)的n個(gè)WiFi熱點(diǎn)。在數(shù)據(jù)采集階段,,在第i個(gè)位置采集n個(gè)WiFi的RSS信息,,i=1,2,,3,,…,m,,m為參考點(diǎn)個(gè)數(shù),,每個(gè)WiFi熱點(diǎn)采集多次RSS取平均值。Rij為在第i個(gè)位置采集到的第j個(gè)WiFi的RSS的平均值,,j=1,,2,3,,…,,n;n為WiFi個(gè)數(shù),,(xi,,yi)為i點(diǎn)的實(shí)際坐標(biāo)。在定位階段,,在待定位點(diǎn)測(cè)得第j個(gè)WiFi的RSS平均值為Rj,,則Rij與Rj之間距離為:
2 改進(jìn)算法WR-kNN
由于室內(nèi)物品較多以及人員的不斷走動(dòng),使得室內(nèi)環(huán)境變得復(fù)雜,,人員以及物品的阻擋使WiFi信號(hào)發(fā)生衰減[10],,加大了室內(nèi)的定位難度。本文通過(guò)對(duì)距離進(jìn)行加權(quán)[11]以及去除無(wú)用組來(lái)增加定位精度,。在離線階段對(duì)掃描得到的數(shù)據(jù)進(jìn)行加權(quán),,加大有用數(shù)據(jù)的權(quán)重,,在進(jìn)行定位匹配時(shí),預(yù)先將數(shù)據(jù)按照RSSI均值大小升序排序,,取前k個(gè)數(shù)據(jù)進(jìn)行運(yùn)算,,減少了運(yùn)算量,降低了小數(shù)據(jù)對(duì)結(jié)果的影響,。
2.1 加權(quán)kNN
首先對(duì)kNN算法中參考點(diǎn)與待測(cè)點(diǎn)之間的距離進(jìn)行加權(quán),。kNN算法中,參考點(diǎn)與待測(cè)點(diǎn)的距離越接近,,相似度越高,,在定位中貢獻(xiàn)越大。加大貢獻(xiàn)大的距離的權(quán)值,,減小貢獻(xiàn)小的距離的權(quán)值,,有助于提高定位精度。因此,,短距離賦予較大的權(quán)值wj,,長(zhǎng)距離賦予較小的權(quán)值wj:
因此在第i個(gè)位置采集到的第j個(gè)WiFi的平均RSSI值為Rijwj。dj為兩點(diǎn)之間的距離,,當(dāng)參考點(diǎn)離待測(cè)點(diǎn)越近時(shí)dj越小,,相對(duì)應(yīng)的權(quán)值wj越大,該參考點(diǎn)所采集的RSSI值越大,,對(duì)定位影響越大,,因此可以提高定位的精度。
2.2 數(shù)據(jù)排序
在定位階段,,數(shù)據(jù)庫(kù)調(diào)出采集的RSSI數(shù)據(jù),,對(duì)待測(cè)點(diǎn)的數(shù)據(jù)與數(shù)據(jù)庫(kù)調(diào)出的數(shù)據(jù)進(jìn)行一一對(duì)比,選取較為接近的k個(gè)數(shù)據(jù)作為相似組,,利用相似組的數(shù)據(jù)通過(guò)質(zhì)心算法得到最終的待測(cè)點(diǎn)的位置坐標(biāo),。本文改進(jìn)是在數(shù)據(jù)調(diào)用之前首先將所有采集的數(shù)據(jù)Rijwj通過(guò)Comparator接口進(jìn)行升序的排列,數(shù)據(jù)庫(kù)中數(shù)據(jù)將按照由大到小的順序在組中排列,,在調(diào)用數(shù)據(jù)時(shí),,只選取組中前n個(gè)較大的數(shù)據(jù),然后與待測(cè)點(diǎn)掃描數(shù)據(jù)進(jìn)行匹配,,選取較為接近的k個(gè)數(shù)據(jù)進(jìn)行定位,。此方法不僅消除了無(wú)用組信息對(duì)定位的干擾,還對(duì)數(shù)據(jù)組進(jìn)行了刪減,,刪除了對(duì)定位結(jié)果貢獻(xiàn)較小的數(shù)據(jù)組,,可以使系統(tǒng)快速地得出定位結(jié)果,提高了系統(tǒng)的定位效率,。
Comparator接口為Java中的一個(gè)對(duì)集合或者數(shù)組對(duì)象進(jìn)行排序的比較器,。Comparator接口的實(shí)現(xiàn)函數(shù)為int compare(Object o1,,Object o2),排序分為升序和降序排列,。當(dāng)o1<o2返回-1(負(fù)數(shù))、o1=o2返回0,、o1>o2返回1(正數(shù))時(shí),,則為升序排列;當(dāng)o1<o2返回1(正數(shù)),、o1=o2返回0,、o1>o2返回-1(負(fù)數(shù))時(shí),則為降序排列,。改進(jìn)算法中首先將數(shù)據(jù)放入Gro.Entry<Integer,,Integer>中,通過(guò)compare(Gro.Entry<Integer,,Integer>o1,,Gro.Entry<Integer,Integer>o2)函數(shù)進(jìn)行升序排列,。
3 實(shí)驗(yàn)
3.1 離線數(shù)據(jù)采集階段
實(shí)驗(yàn)區(qū)域內(nèi)部有10個(gè)AP,,每隔2.5 m采樣一次,共有12個(gè)采樣點(diǎn),。首先測(cè)試WiFi信號(hào)穩(wěn)定性,。隨機(jī)選取一個(gè)WiFi信號(hào),每隔10 s掃描一次,,結(jié)果如圖1所示,。
如圖1所示,WiFi信號(hào)強(qiáng)度基本分布在-77 dBm~-83 dBm之間,,個(gè)別時(shí)間有較大波動(dòng),,總體較為穩(wěn)定。采集時(shí)采用平均值作為數(shù)據(jù)儲(chǔ)存,,可減小較大波動(dòng)帶來(lái)的影響,,并可以作為定位所需的參考數(shù)據(jù)。
離線數(shù)據(jù)采集階段,,在采樣點(diǎn),每個(gè)AP采樣10次,,將RSS的平均值計(jì)入數(shù)據(jù)庫(kù)。將RSSIj表示第j個(gè)AP的RSSI平均值,,MACi表示第i個(gè)采樣點(diǎn)的10個(gè)AP的mac地址集合,,(xi,,yi)表示第i個(gè)采樣點(diǎn)坐標(biāo),。Ri={RSSIi1,,RSSIi2,…,,RSSIi10}表示第i個(gè)采樣點(diǎn)所采集的10個(gè)AP的RSSI平均值的集合。數(shù)據(jù)庫(kù)中一個(gè)完整信息為[Ri,,MACi,,(xi,,yi)],。
3.2 在線定位階段
在線定位階段,,隨機(jī)選取7個(gè)測(cè)試點(diǎn)進(jìn)行定位,,在每個(gè)測(cè)試點(diǎn)定位3次,,取坐標(biāo)平均值作為最后測(cè)試結(jié)果,如圖2所示,。圖2分別顯示了測(cè)試點(diǎn)坐標(biāo)即定位結(jié)果,、原坐標(biāo)即測(cè)試點(diǎn)所在的正確坐標(biāo)以及傳統(tǒng)算法定位所得的坐標(biāo)。如圖所示,,改進(jìn)后的坐標(biāo)相對(duì)傳統(tǒng)算法所得坐標(biāo)更加靠近原坐標(biāo),。宏觀上來(lái)看,改進(jìn)算法相比傳統(tǒng)算法更加精確,。
分別基于改進(jìn)算法WR-kNN以及傳統(tǒng)算法所得定位結(jié)果進(jìn)行誤差分析,得到如圖3所示的誤差分布圖,。由圖可看出改進(jìn)算法誤差皆小于傳統(tǒng)算法誤差,。表1為誤差數(shù)據(jù),,分別對(duì)應(yīng)圖3中7個(gè)采樣點(diǎn),。
由表1可以得出,傳統(tǒng)算法平均誤差為2.55 m,,最小誤差1.48 m,,最大誤差4.09 m,誤差波動(dòng)較大,。由于傳統(tǒng)算法中直接采用即時(shí)數(shù)據(jù),室內(nèi)環(huán)境復(fù)雜,,人員走動(dòng)頻繁,因此WiFi信號(hào)波動(dòng)較大,,不加以處理直接存入數(shù)據(jù)庫(kù),,使得定位結(jié)果與實(shí)際差距較大,。傳統(tǒng)定位算法較為復(fù)雜,,累積誤差較大,選取匹配對(duì)象不科學(xué),,導(dǎo)致定位結(jié)果出現(xiàn)偏差,,且定位時(shí)間較長(zhǎng),。WR-kNN算法在數(shù)據(jù)采集時(shí)通過(guò)多次采集數(shù)據(jù)取均值,然后對(duì)其進(jìn)行加權(quán)處理,,避免了信號(hào)波動(dòng)帶來(lái)的影響,同時(shí)減小了遠(yuǎn)距離AP帶來(lái)的誤差,。定位階段通過(guò)對(duì)調(diào)用的數(shù)據(jù)進(jìn)行預(yù)處理,精簡(jiǎn)了定位流程,,減小了定位所需時(shí)間,提高了效率,,同時(shí)減小了累積誤差,。因此改進(jìn)算法誤差較小,,平均誤差僅為1.93 m,,相對(duì)傳統(tǒng)算法平均誤差減少了0.62 m,,誤差在2 m左右波動(dòng),,較為穩(wěn)定。
4 結(jié)束語(yǔ)
本文采用一種改進(jìn)的kNN算法研究了基于Android平臺(tái)的指紋室內(nèi)定位,。離線定位階段,,通過(guò)對(duì)采集的數(shù)據(jù)進(jìn)行加權(quán),,增大有用數(shù)據(jù)的權(quán)值,,減小無(wú)用數(shù)據(jù)的權(quán)值,;在線定位階段,通過(guò)對(duì)調(diào)用的數(shù)據(jù)預(yù)先進(jìn)行排序,,去除無(wú)用組,減小不穩(wěn)定信號(hào)對(duì)定位結(jié)果的影響,。實(shí)驗(yàn)表明,該改進(jìn)算法定位結(jié)果較為精確,,相對(duì)傳統(tǒng)算法提高了0.62 m。由于實(shí)驗(yàn)環(huán)境較為復(fù)雜,,人員較多,,AP較多且部署較為隨機(jī),,因此對(duì)實(shí)驗(yàn)結(jié)果有影響。如果在較為空曠且AP部署較為規(guī)范的實(shí)驗(yàn)場(chǎng)地,,定位結(jié)果將更加精確,。
參考文獻(xiàn)
[1] 倪巍,,王宗欣.基于接收信號(hào)強(qiáng)度測(cè)量的室內(nèi)定位算法[J].復(fù)旦學(xué)報(bào)(自然科學(xué)版),,2004,,43(1):72-76.
[2] RANTAKOKKO J,RYDELL J,,STROMBACK P,et al.Accurate and reliable soldier and first responder indoor positioning:multisensor systems and cooperative localization[J].Wireless Communications,,IEEE,,2011,,18(2):10-18.
[3] 梁元誠(chéng).基于無(wú)線局域網(wǎng)的室內(nèi)定位技術(shù)研究與實(shí)現(xiàn)[D].成都:電子科技大學(xué),,2009.
[4] 崔斌,趙西安.一種基于傳播模型和位置指紋的混合室內(nèi)定位方法[J].測(cè)繪通報(bào),,2015(6):35-38,,43.
[5] 張明華,,張申生,,曹健.無(wú)線局域網(wǎng)中基于信號(hào)強(qiáng)度的室內(nèi)定位[J].計(jì)算機(jī)科學(xué),,2007,34(6),;68-71.
[6] 張儷文,汪云甲,,王行風(fēng).仿射傳播聚類在室內(nèi)定位指紋庫(kù)中的應(yīng)用研究[J].測(cè)繪通報(bào),,2014(12):36-39.
[7] 張明華.基于WLAN的室內(nèi)定位技術(shù)研究[D].上海:上海交通大學(xué),2009.
[8] YANG Z,,WU C,,LIU Y.Locating in fingerprint space: wireless indoor localization with little human intervention[C].Proceedings of the 18th Annual International Conference on Mobile Computing and Networking.ACM,2012:269-280.
[9] 張曉亮,,趙平,徐冠青,,等.基于一種優(yōu)化的KNN算法在室內(nèi)定位中的應(yīng)用研究[J].電子設(shè)計(jì)工程,2013,,21(7):44-46.
[10] 楊凱,郭英,,畢京學(xué).基于安卓平臺(tái)的室內(nèi)實(shí)時(shí)定位[J].測(cè)繪科學(xué),2015,,40(6):125-128.
[11] 陳振洲,,李磊,姚正安.基于SVM的特征加權(quán)KNN算法[J].中山大學(xué)學(xué)報(bào)(自然科學(xué)版),,2005,,44(1):17-20.
作者信息:
武 一,,張冀釗
(河北工業(yè)大學(xué) 電子信息工程學(xué)院,天津300400)