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