0 引言

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

    本文通過掃描室內的WiFi信息，在Android平臺上通過改進的指紋匹配定位方法實現室內定位。

1 WiFi位置指紋定位方法

1.1 指紋定位方法

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

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

1.2 kNN算法(最鄰近算法)

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

    在kNN算法中要準確選擇參數k的值，當k較小時，選擇臨近點數量較小，不能準確地確定參考點的類別，增大了誤差；當選擇k較大時，則會選擇較遠的點，導致定位結果不準確。因此，應多次測量決定參數k的值。本實驗經多次測試，k為3時誤差最小，因此k取3。

    AP_n代表定位區域內的n個WiFi熱點。在數據采集階段，在第i個位置采集n個WiFi的RSS信息，i=1，2，3，…，m，m為參考點個數，每個WiFi熱點采集多次RSS取平均值。Rij為在第i個位置采集到的第j個WiFi的RSS的平均值，j=1，2，3，…，n；n為WiFi個數，(x_i，y_i)為i點的實際坐標。在定位階段，在待定位點測得第j個WiFi的RSS平均值為R_j，則R_ij與R_j之間距離為：

2 改進算法WR-kNN

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

2.1 加權kNN

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

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

2.2 數據排序

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

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

3 實驗

3.1 離線數據采集階段

    實驗區域內部有10個AP，每隔2.5 m采樣一次，共有12個采樣點。首先測試WiFi信號穩定性。隨機選取一個WiFi信號，每隔10 s掃描一次，結果如圖1所示。

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

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

3.2 在線定位階段

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

    分別基于改進算法WR-kNN以及傳統算法所得定位結果進行誤差分析，得到如圖3所示的誤差分布圖。由圖可看出改進算法誤差皆小于傳統算法誤差。表1為誤差數據，分別對應圖3中7個采樣點。

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

4 結束語

    本文采用一種改進的kNN算法研究了基于Android平臺的指紋室內定位。離線定位階段，通過對采集的數據進行加權，增大有用數據的權值，減小無用數據的權值；在線定位階段，通過對調用的數據預先進行排序，去除無用組，減小不穩定信號對定位結果的影響。實驗表明，該改進算法定位結果較為精確，相對傳統算法提高了0.62 m。由于實驗環境較為復雜，人員較多，AP較多且部署較為隨機，因此對實驗結果有影響。如果在較為空曠且AP部署較為規范的實驗場地，定位結果將更加精確。

參考文獻

[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] 梁元誠.基于無線局域網的室內定位技術研究與實現[D].成都：電子科技大學，2009.

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

[5] 張明華，張申生，曹健.無線局域網中基于信號強度的室內定位[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] 張曉亮，趙平，徐冠青，等.基于一種優化的KNN算法在室內定位中的應用研究[J].電子設計工程，2013，21(7)：44-46.

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

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

作者信息:

武  一，張冀釗

(河北工業大學 電子信息工程學院，天津300400)