0 引言

    隨著通信技術(shù)和智能科技的不斷發(fā)展,，定位技術(shù)在日常生活中發(fā)揮著越來越大的作用，人們對定位服務(wù)的需求逐漸增大,。室外定位GPS以及基站定位技術(shù)已經(jīng)發(fā)展成熟,，出現(xiàn)了多種室內(nèi)定位技術(shù)，如：RFID(射頻識別),、WiFi,、藍(lán)牙、紅外線等,。定位方法有基于到達(dá)時間(TOA),、基于信號強(qiáng)度(RSS)、基于到達(dá)角度(AOA)的方法^[1],，還有一些通過加速度傳感器等手機(jī)內(nèi)的集成傳感器件來實現(xiàn)定位^[2]?，F(xiàn)階段，智能手機(jī)相當(dāng)普及,，WiFi也基本覆蓋大多數(shù)公共場所,，WiFi定位無需額外的硬件需求，具有低成本,、低功耗,、高精度等特點，因此其在眾多定位方法中具有很大的優(yōu)勢,。

    本文通過掃描室內(nèi)的WiFi信息,，在Android平臺上通過改進(jìn)的指紋匹配定位方法實現(xiàn)室內(nèi)定位。

1 WiFi位置指紋定位方法

1.1 指紋定位方法

    基于WiFi無線網(wǎng)絡(luò)的定位技術(shù)有很多,，其中以基于信號強(qiáng)度RSS的定位技術(shù)最為常用^[4],。在基于RSS的定位技術(shù)中位置指紋定位方法較為普遍。位置指紋定位方法^[5]分為數(shù)據(jù)采集階段和實時定位階段兩部分,。在數(shù)據(jù)采集階段,，在區(qū)域內(nèi)均勻地選擇N個數(shù)據(jù)采集點,，在每個采集點，通過安卓手機(jī)采集所有AP的RSS信息,，并將所有RSS信息以及該點的坐標(biāo)(x,，y)存入數(shù)據(jù)庫^[6]，等待第二階段調(diào)用,。在實時定位階段,，用戶在未知位置發(fā)出定位請求，安卓手機(jī)采集該點AP的RSS信息并傳送至數(shù)據(jù)庫,，通過匹配算法以及第一階段采集的RSS數(shù)據(jù)得到位置坐標(biāo)(x，y)反饋給用戶,，定位完成^[7],。

    在第二階段定位過程中，kNN算法是較為常用的一種傳統(tǒng)匹配算法,。

1.2 kNN算法(最鄰近算法)

    臨近算法即k最鄰近分類算法(kNN,，k-NearestNeighbor)^[8]，核心思想是：如果一個樣本在特征空間中的k個最相鄰的樣本中的大多數(shù)屬于某一個類別,，則該樣本也屬于這個類別,，并具有這個類別上樣本的特性。

    在kNN算法中要準(zhǔn)確選擇參數(shù)k的值,，當(dāng)k較小時,，選擇臨近點數(shù)量較小，不能準(zhǔn)確地確定參考點的類別,，增大了誤差,；當(dāng)選擇k較大時，則會選擇較遠(yuǎn)的點,，導(dǎo)致定位結(jié)果不準(zhǔn)確,。因此，應(yīng)多次測量決定參數(shù)k的值,。本實驗經(jīng)多次測試,，k為3時誤差最小，因此k取3,。

    AP_n代表定位區(qū)域內(nèi)的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ù),，(x_i，y_i)為i點的實際坐標(biāo),。在定位階段,，在待定位點測得第j個WiFi的RSS平均值為R_j，則R_ij與R_j之間距離為：

2 改進(jìn)算法WR-kNN

    由于室內(nèi)物品較多以及人員的不斷走動,，使得室內(nèi)環(huán)境變得復(fù)雜,，人員以及物品的阻擋使WiFi信號發(fā)生衰減^[10]，加大了室內(nèi)的定位難度,。本文通過對距離進(jìn)行加權(quán)^[11]以及去除無用組來增加定位精度,。在離線階段對掃描得到的數(shù)據(jù)進(jìn)行加權(quán)，加大有用數(shù)據(jù)的權(quán)重,，在進(jìn)行定位匹配時,，預(yù)先將數(shù)據(jù)按照RSSI均值大小升序排序，取前k個數(shù)據(jù)進(jìn)行運算,，減少了運算量,，降低了小數(shù)據(jù)對結(jié)果的影響。

2.1 加權(quán)kNN

    首先對kNN算法中參考點與待測點之間的距離進(jìn)行加權(quán),。kNN算法中,，參考點與待測點的距離越接近，相似度越高,，在定位中貢獻(xiàn)越大,。加大貢獻(xiàn)大的距離的權(quán)值，減小貢獻(xiàn)小的距離的權(quán)值,，有助于提高定位精度,。因此，短距離賦予較大的權(quán)值w_j,，長距離賦予較小的權(quán)值w_j：

因此在第i個位置采集到的第j個WiFi的平均RSSI值為R_ijw_j,。d_j為兩點之間的距離，當(dāng)參考點離待測點越近時d_j越小,，相對應(yīng)的權(quán)值w_j越大,，該參考點所采集的RSSI值越大,，對定位影響越大，因此可以提高定位的精度,。

2.2 數(shù)據(jù)排序

    在定位階段,，數(shù)據(jù)庫調(diào)出采集的RSSI數(shù)據(jù)，對待測點的數(shù)據(jù)與數(shù)據(jù)庫調(diào)出的數(shù)據(jù)進(jìn)行一一對比,，選取較為接近的k個數(shù)據(jù)作為相似組,，利用相似組的數(shù)據(jù)通過質(zhì)心算法得到最終的待測點的位置坐標(biāo)。本文改進(jìn)是在數(shù)據(jù)調(diào)用之前首先將所有采集的數(shù)據(jù)R_ijw_j通過Comparator接口進(jìn)行升序的排列,，數(shù)據(jù)庫中數(shù)據(jù)將按照由大到小的順序在組中排列,，在調(diào)用數(shù)據(jù)時，只選取組中前n個較大的數(shù)據(jù),，然后與待測點掃描數(shù)據(jù)進(jìn)行匹配,，選取較為接近的k個數(shù)據(jù)進(jìn)行定位。此方法不僅消除了無用組信息對定位的干擾,，還對數(shù)據(jù)組進(jìn)行了刪減，刪除了對定位結(jié)果貢獻(xiàn)較小的數(shù)據(jù)組,，可以使系統(tǒng)快速地得出定位結(jié)果,，提高了系統(tǒng)的定位效率。

    Comparator接口為Java中的一個對集合或者數(shù)組對象進(jìn)行排序的比較器,。Comparator接口的實現(xiàn)函數(shù)為int compare(Object o1,，Object o2)，排序分為升序和降序排列,。當(dāng)o1<o2返回-1(負(fù)數(shù)),、o1=o2返回0、o1>o2返回1(正數(shù))時,，則為升序排列,；當(dāng)o1<o2返回1(正數(shù))、o1=o2返回0,、o1>o2返回-1(負(fù)數(shù))時,，則為降序排列。改進(jìn)算法中首先將數(shù)據(jù)放入Gro.Entry<Integer,，Integer>中,，通過compare(Gro.Entry<Integer，Integer>o1,，Gro.Entry<Integer,，Integer>o2)函數(shù)進(jìn)行升序排列。

3 實驗

3.1 離線數(shù)據(jù)采集階段

    實驗區(qū)域內(nèi)部有10個AP,，每隔2.5 m采樣一次,，共有12個采樣點,。首先測試WiFi信號穩(wěn)定性。隨機(jī)選取一個WiFi信號,，每隔10 s掃描一次,，結(jié)果如圖1所示。

    如圖1所示,，WiFi信號強(qiáng)度基本分布在-77 dBm～-83 dBm之間,，個別時間有較大波動，總體較為穩(wěn)定,。采集時采用平均值作為數(shù)據(jù)儲存,，可減小較大波動帶來的影響，并可以作為定位所需的參考數(shù)據(jù),。

    離線數(shù)據(jù)采集階段,，在采樣點，每個AP采樣10次,，將RSS的平均值計入數(shù)據(jù)庫,。將RSSI_j表示第j個AP的RSSI平均值，MAC_i表示第i個采樣點的10個AP的mac地址集合,，(x_i,，y_i)表示第i個采樣點坐標(biāo)。R_i={RSSI_i1,，RSSI_i2,，…，RSSI_i10}表示第i個采樣點所采集的10個AP的RSSI平均值的集合,。數(shù)據(jù)庫中一個完整信息為[R_i,，MAC_i，(x_i,，y_i)],。

3.2 在線定位階段

    在線定位階段，隨機(jī)選取7個測試點進(jìn)行定位,，在每個測試點定位3次,，取坐標(biāo)平均值作為最后測試結(jié)果，如圖2所示,。圖2分別顯示了測試點坐標(biāo)即定位結(jié)果,、原坐標(biāo)即測試點所在的正確坐標(biāo)以及傳統(tǒng)算法定位所得的坐標(biāo)。如圖所示,，改進(jìn)后的坐標(biāo)相對傳統(tǒng)算法所得坐標(biāo)更加靠近原坐標(biāo),。宏觀上來看，改進(jìn)算法相比傳統(tǒng)算法更加精確,。

    分別基于改進(jìn)算法WR-kNN以及傳統(tǒng)算法所得定位結(jié)果進(jìn)行誤差分析,，得到如圖3所示的誤差分布圖,。由圖可看出改進(jìn)算法誤差皆小于傳統(tǒng)算法誤差。表1為誤差數(shù)據(jù),，分別對應(yīng)圖3中7個采樣點,。

    由表1可以得出，傳統(tǒng)算法平均誤差為2.55 m,，最小誤差1.48 m,，最大誤差4.09 m，誤差波動較大,。由于傳統(tǒng)算法中直接采用即時數(shù)據(jù),，室內(nèi)環(huán)境復(fù)雜，人員走動頻繁,，因此WiFi信號波動較大,，不加以處理直接存入數(shù)據(jù)庫，使得定位結(jié)果與實際差距較大,。傳統(tǒng)定位算法較為復(fù)雜,，累積誤差較大，選取匹配對象不科學(xué),，導(dǎo)致定位結(jié)果出現(xiàn)偏差,，且定位時間較長。WR-kNN算法在數(shù)據(jù)采集時通過多次采集數(shù)據(jù)取均值,，然后對其進(jìn)行加權(quán)處理,，避免了信號波動帶來的影響,，同時減小了遠(yuǎn)距離AP帶來的誤差,。定位階段通過對調(diào)用的數(shù)據(jù)進(jìn)行預(yù)處理，精簡了定位流程,，減小了定位所需時間,，提高了效率，同時減小了累積誤差,。因此改進(jìn)算法誤差較小,，平均誤差僅為1.93 m，相對傳統(tǒng)算法平均誤差減少了0.62 m,，誤差在2 m左右波動,，較為穩(wěn)定。

4 結(jié)束語

    本文采用一種改進(jìn)的kNN算法研究了基于Android平臺的指紋室內(nèi)定位,。離線定位階段,，通過對采集的數(shù)據(jù)進(jìn)行加權(quán)，增大有用數(shù)據(jù)的權(quán)值,，減小無用數(shù)據(jù)的權(quán)值,；在線定位階段,，通過對調(diào)用的數(shù)據(jù)預(yù)先進(jìn)行排序，去除無用組,，減小不穩(wěn)定信號對定位結(jié)果的影響,。實驗表明，該改進(jìn)算法定位結(jié)果較為精確,，相對傳統(tǒng)算法提高了0.62 m,。由于實驗環(huán)境較為復(fù)雜，人員較多,，AP較多且部署較為隨機(jī),，因此對實驗結(jié)果有影響。如果在較為空曠且AP部署較為規(guī)范的實驗場地,，定位結(jié)果將更加精確,。

參考文獻(xiàn)

[1] 倪巍，王宗欣.基于接收信號強(qiáng)度測量的室內(nèi)定位算法[J].復(fù)旦學(xué)報(自然科學(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] 梁元誠.基于無線局域網(wǎng)的室內(nèi)定位技術(shù)研究與實現(xiàn)[D].成都：電子科技大學(xué)，2009.

[4] 崔斌,，趙西安.一種基于傳播模型和位置指紋的混合室內(nèi)定位方法[J].測繪通報,，2015(6)：35-38，43.

[5] 張明華,，張申生,，曹健.無線局域網(wǎng)中基于信號強(qiáng)度的室內(nèi)定位[J].計算機(jī)科學(xué)，2007,，34(6),；68-71.

[6] 張儷文，汪云甲,，王行風(fēng).仿射傳播聚類在室內(nèi)定位指紋庫中的應(yīng)用研究[J].測繪通報,，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è)計工程，2013,，21(7)：44-46.

[10] 楊凱,，郭英，畢京學(xué).基于安卓平臺的室內(nèi)實時定位[J].測繪科學(xué),，2015,，40(6)：125-128.

[11] 陳振洲，李磊,，姚正安.基于SVM的特征加權(quán)KNN算法[J].中山大學(xué)學(xué)報(自然科學(xué)版),，2005，44(1)：17-20.

作者信息:

武  一,，張冀釗

(河北工業(yè)大學(xué) 電子信息工程學(xué)院,，天津300400)