摘要：本文設(shè)計(jì)及實(shí)現(xiàn)了一個基于WiFi 射頻信號強(qiáng)度指紋匹配的移動終端定位系統(tǒng),，并設(shè)計(jì)實(shí)現(xiàn)了一種基于權(quán)重值選擇的定位算法。該算法為每個掃描到的AP 的RSSI 設(shè)定了選擇區(qū)間,，指紋庫中落在此區(qū)間的所有位置點(diǎn)設(shè)平均權(quán)值，最后選取權(quán)重值最大者為待定位點(diǎn)的位置估計(jì),，如有相同權(quán)重值,，則比較信號強(qiáng)度距離，取最小者,，這種算法在一定程度上克服了RSSI 信號隨機(jī)抖動對定位的影響,，提高了定位的穩(wěn)定性和精度。經(jīng)實(shí)驗(yàn)測試,，此系統(tǒng)在4 米范圍內(nèi)具有良好的定位效果,。可部署在展館,、校園,、公園等公共場所，為客戶提供定位導(dǎo)航服務(wù),。定位算法運(yùn)行于服務(wù)端,，客戶端為配備WiFi 模塊的Android 手機(jī)。借助該定位系統(tǒng),，基于Android 系統(tǒng)的移動終端可方便地查詢自身位置,，并獲取各種基于位置服務(wù)。

    1. 引言

    位置信息在人們的日常生活中扮演著重要的作用,。在郊外,、展覽館、公園等陌生環(huán)境中,，使用定位導(dǎo)航信息可為觀眾游覽提供更便捷的服務(wù),；在倉儲物流過程中，對物品進(jìn)行實(shí)時(shí)定位跟蹤將大大提高工作效率,；在監(jiān)獄環(huán)境中,，及時(shí)準(zhǔn)確地掌握相關(guān)人員的位置信息，有助于提高安全管理水平,，簡化監(jiān)獄管理工作,。

    目前全球定位系統(tǒng)（ GPS , GlobalPositioning System）是獲取室外環(huán)境位置信息的最常用方式,。近年來，隨著無線移動通信技術(shù)的快速發(fā)展,，GPS 和蜂窩網(wǎng)絡(luò)相結(jié)合的A-GPS（Assisted Global Positioning System）定位方式在緊急救援和各種基于位置服務(wù)（LBS,Location-Based Services）中逐漸得到了應(yīng)用,。但由于衛(wèi)星信號容易受到各種障礙物遮擋，GPS/APGS 等衛(wèi)星定位技術(shù)并不適用于室內(nèi)或高樓林立的場合,，目前無線室內(nèi)定位技術(shù)迅速發(fā)展,，已成為GPS 的有力補(bǔ)充。

    一般來講,，使用無線信號強(qiáng)度獲取目標(biāo)位置信息的過程,，就是建立無線信號強(qiáng)度和位置信息穩(wěn)定映射關(guān)系的過程?，F(xiàn)有室內(nèi)無線定位系統(tǒng)主要采用紅外,、超聲波、藍(lán)牙,、WiFi（Wireless Fidelity）,、RFID（Radio FrequencyIdentification）等短距離無線技術(shù)。其中基于WiFi 網(wǎng)絡(luò)的無線定位技術(shù)由于部署廣泛且低成本較低,，因此備受關(guān)注,。其中由微軟開發(fā)的RADAR 系統(tǒng)是最早的基于WiFi 網(wǎng)絡(luò)的定位系統(tǒng)。它采用射頻指紋匹配方法,，從指紋庫中查找最接近的K 個鄰居,，取它們坐標(biāo)的平均作為坐標(biāo)估計(jì)。而文獻(xiàn)[5]介紹的室內(nèi)定位系統(tǒng)則基于RSSI 信號的統(tǒng)計(jì)特性,，采用貝葉斯公式,，通過計(jì)算目標(biāo)位置的后驗(yàn)概率分布，來進(jìn)行定位,。

    本文同樣基于WiFi 網(wǎng)絡(luò),，設(shè)計(jì)和實(shí)現(xiàn)了一種無線室內(nèi)定位系統(tǒng)，但與上述定位方法不同,，本文采用了基于權(quán)值選擇的定位算法,，在一定程度上減少了RSS.信號隨機(jī)變化引起的定位誤差，實(shí)驗(yàn)結(jié)果表明,，該系統(tǒng)可獲得較好的定位精度（4 米）,。

    2. 系統(tǒng)設(shè)計(jì)

本系統(tǒng)可為移動終端客戶在展館、商場,、校園等應(yīng)用場景提供定位服務(wù),。鑒于移動終端受到計(jì)算能力、存儲容量和電池電量等諸多限制,，所以僅完成簡單的信號采集工作,，定位計(jì)算由定位服務(wù)端完成,。

    定位系統(tǒng)的架構(gòu)體系如圖1 所示。服務(wù)端主要負(fù)責(zé)定位計(jì)算和響應(yīng)終端的定位請求,?；谪?fù)載均衡考慮，響應(yīng)位置請求的Web 服務(wù)器和運(yùn)行定位計(jì)算的定位服務(wù)器分離,，數(shù)據(jù)交換方式采用客戶端和Web 服務(wù)器相同的數(shù)據(jù)交換方式,。客戶端依附于具體對象,，主要負(fù)責(zé)采集周邊AP 的無線信號強(qiáng)度,，并向服務(wù)端提交信號特征，服務(wù)器使用客戶端采集的信號特征進(jìn)行定位計(jì)算,，獲得移動終端的位置估計(jì),。

    客戶端和服務(wù)端通信采用標(biāo)準(zhǔn)的HTTP協(xié)議，編程方便,，可擴(kuò)展性好,，客戶端程序功能可根據(jù)需要進(jìn)行擴(kuò)充。

圖1 定位系統(tǒng)網(wǎng)絡(luò)結(jié)構(gòu)

    圖2 為本定位系統(tǒng)的信息交互流程圖,。移動終端向Web 服務(wù)器提交GET 請求,，GET 請求中包含了信號強(qiáng)度特征向量，Web 服務(wù)器收到請求后,，以同樣的方式傳達(dá)給定位服務(wù)器,，定位服務(wù)器查詢數(shù)據(jù)庫，并進(jìn)行相關(guān)的定位運(yùn)算操作,，從而得到移動終端的位置估計(jì),。

             圖2 移動終端與服務(wù)器間的信息交互3. 系統(tǒng)實(shí)現(xiàn)

    3.1. 客戶端設(shè)計(jì)

    本系統(tǒng)客戶端采用Android 系統(tǒng)手機(jī)。

    Android 系統(tǒng)是Google 在2007 年發(fā)布的基于Linux 平臺的開源手機(jī)操作系統(tǒng),。近年來,，基于此平臺的手機(jī)市場占有率不斷提高，加上其良好的開放性和豐富的API 接口,，可以很方便地開發(fā)各種應(yīng)用程序,。

    3.1.1. Android 系統(tǒng)架構(gòu)簡介

    Android 系統(tǒng)架構(gòu)見圖3,它建立于Linux內(nèi)核之上，包含了各種設(shè)備驅(qū)動和管理模塊,，囊括了非常齊全的類庫和框架,，包括輕量級數(shù)據(jù)庫SQLite、瀏覽器Webkit 等,。整個系統(tǒng)建立在Dalvik 虛擬機(jī)上,，應(yīng)用程序使用Java 語言編寫。Android 系統(tǒng)提供了豐富的框架（活動管理,、位置管理等）來管理系統(tǒng)的軟,、硬件資源,，整合了常用的應(yīng)用程序（聯(lián)系人、電話本等）,，并開放了很全面的API 供用戶使用,，整個平臺具有良好的開放性和擴(kuò)展性。

圖3 Android 系統(tǒng)架構(gòu)圖

    3.1.2. Activity 生命周期

    Android 系統(tǒng)上運(yùn)行的應(yīng)用程序一般包含一個或多個Activity,主要由活動管理器進(jìn)行管理,，Activity 是Android 系統(tǒng)分配和管理資源的基本單位,。每個Activity 都有其對應(yīng)的生命周期（圖4）。

圖4 Activity 生命周期

    onCreate（）方法在活動開始時(shí)調(diào)用,，并依次調(diào)用onStart（）方法和onResume（）方法,，Activity 處于運(yùn)行狀態(tài)，如有新活動啟動,，則調(diào)用onPause（）,，活動轉(zhuǎn)入后臺；如內(nèi)存不足,，活動進(jìn)程則被關(guān)閉,。退出程序則會依次調(diào)用onStop（）和onDestroy（）,。

活動管理器對Activity 的管理體現(xiàn)在不同生命周期對以上幾個方法的調(diào)用上,，用戶可根據(jù)自己的需要重載這幾個方法。一般來講,，主程序類繼承Activity 類,，用戶的功能代碼在重載這些方法中實(shí)現(xiàn)。

    3.1.3. 獲取周邊AP 信號強(qiáng)度

本文采用基于射頻指紋的定位方法,，移動終端需要獲得周圍AP 的RSSI 指紋特征,，Android 系統(tǒng)提供的接口可以很方便地實(shí)現(xiàn)這一功能。

參見圖5 示例代碼片段,。首先建立包含響應(yīng)掃描結(jié)果的接收器（reciever） 并重載onReceive（）方法,，此方法即為收到WiFi 信號的回調(diào)函數(shù)，用戶自定義功能在此實(shí)現(xiàn),；再通過registerReceiver（）方法將receiver 向Android 系統(tǒng)進(jìn)行注冊,，getSystemService（）方法用于獲得操作WiFi 設(shè)備的句柄；最后用startScan（）方法啟動掃描,，當(dāng)獲得掃描結(jié)果后,，系統(tǒng)會觸發(fā)注冊的回調(diào)函數(shù)，完成用戶代碼功能,。

圖5 掃描示例代碼

    實(shí)驗(yàn)結(jié)果表明,，從給出掃描指令，至接收到掃描結(jié)果,，耗時(shí)約400-500ms,考慮到后臺服務(wù)器算法運(yùn)算及網(wǎng)絡(luò)通信開銷,，定位過程耗時(shí)將超過500ms.

    3.1.4. 程序流程

    從程序的功能來看,，客戶端需完成3 個功能：定期掃描并獲得周圍AP 的信號強(qiáng)度指紋特征，向服務(wù)器提交指紋特征信息,，得到定位結(jié)果后更新界面顯示,。程序流程如圖6 所示。

首先程序初始化并建立更新回調(diào)函數(shù),，獲得WiFi 服務(wù)句柄后注冊此回調(diào)函數(shù),，最后啟動掃描進(jìn)程周期掃描，直至系統(tǒng)結(jié)束程序,。

    其中,，回調(diào)函數(shù)首先獲取掃描結(jié)果，并格式化為字符串,，然后通過GET 請求提交給服務(wù)端,，獲得定位結(jié)果后再更新顯示界面。

圖6 程序流程圖

    3.2. 服務(wù)端軟件設(shè)計(jì)

    3.2.1. Web 服務(wù)器

    Web 服務(wù)器用于對外通信,，接收外界的請求,，并返回相應(yīng)的位置信息。

    Web 服務(wù)器運(yùn)行Apache Tomcat 6.0.20,響應(yīng)網(wǎng)絡(luò)的定位請求,，相應(yīng)的軟件設(shè)置參數(shù)為：在%TOMCAT_HOME%webapps 目錄下建立目錄：ExServletWEB-INF,建立web.xml描述文件和classes 文件夾,，web.xml 文件是描述文件，classes 存放后臺處理的類文件,。

    web.xml 中定義了外部引用此服務(wù)的名字和對應(yīng)的類文件,，內(nèi)容片段見圖7。

圖7 web 服務(wù)器web.xml 代碼片段

    3.2.2. 定位服務(wù)器

    定位服務(wù)器用于運(yùn)行算法,，硬件配置參數(shù)為,，CPU:Intel Core2 Duo E7500 2.93GHz,內(nèi)存：2G,網(wǎng)卡：Marvell Yukon 88E8057 PCI-EGigabit Ethernet Controller.軟件配置參數(shù)為，操作系統(tǒng)：Windows XP Professional SP3,Web服務(wù)器：Apache Tomcat 6.0.20.相應(yīng)的軟件配置參數(shù)與web 服務(wù)器類似,，web.xml 中代碼片段見圖8.

圖8 定位服務(wù)器web.xml 代碼片段

    3.3. 客戶端與服務(wù)端通信

    客戶端與服務(wù)端都接入Internet,通過標(biāo)準(zhǔn)的HTTP 協(xié)議通信,，簡化設(shè)計(jì)的同時(shí)，也為以后Web 方式的應(yīng)用留下了設(shè)計(jì)空間,。

    服務(wù)端Servlet 用于響應(yīng)客戶端的請求,，客戶端只需在GET 請求中提交指紋信息即可獲得定位結(jié)果。圖9 列出了客戶端從定位服務(wù)器中獲取位置信息的Java 示例代碼,。其中url包含了服務(wù)器的IP 地址和RSSI 指紋信息,，getConnection（）方法是向服務(wù)器發(fā)出GET 請求，服務(wù)器將返回位置信息,，獲得輸入流后讀出位置信息,，并更新界面顯示即完成整個通信過程。由于使用HTTP 協(xié)議,，實(shí)現(xiàn)方法簡單,，適用于多種編程語言,。

圖9 客戶端獲取位置信息的通信示例代碼

    4. 定位算法

    由于室內(nèi)環(huán)境復(fù)雜，WiFi 無線信號具有較強(qiáng)的時(shí)變特性圖10.無線信號傳播衰減模型難以很好的表征距離與信號強(qiáng)度間的映射關(guān)系,，本文采用基于射頻指紋匹配定位方法,，它具有較好的定位魯棒性。

圖10 信號強(qiáng)度的時(shí)變特性

    指紋匹配方式定位算法建立在實(shí)驗(yàn)數(shù)據(jù)基礎(chǔ)上,，它主要包括離線訓(xùn)練和在線定位兩個階段,，其中離線訓(xùn)練階段的任務(wù)是建立射頻信號強(qiáng)度向量和客戶端位置間的一一對應(yīng)關(guān)系，形成一個指紋庫（radio map）,，定位階段則使用實(shí)時(shí)采集的信號強(qiáng)度向量去匹配訓(xùn)練階段構(gòu)建的指紋庫,，從而獲得目標(biāo)的位置估計(jì)。

    現(xiàn)有的基于射頻指紋匹配定位方法主要包括確定型和概率型兩種,。其中確定型定位算法一般在指紋庫中選擇與實(shí)時(shí)采集的射頻指紋距離最小的幾個點(diǎn)的質(zhì)心作為目標(biāo)的位置估計(jì),。確定型定位算法的計(jì)算效率較高，但精度較低,。概率型定位算法一般采用貝葉斯估計(jì)理論,，通過不同的似然函數(shù)，如基于核函數(shù)的似然函數(shù),，計(jì)算目標(biāo)位置的后驗(yàn)概率,，并取后驗(yàn)概率最大的位置點(diǎn)作為目標(biāo)的最終位置估計(jì)。概率型定位算法具有較高的定位精度和定位魯棒性,，但計(jì)算量相對較大,。

本文采用快速選擇的定位算法，訓(xùn)練階段指紋特征采用RSSI 均值,，定位階段采用逐次累加的RSSI 均值與指紋庫匹配的方法，從而大大降低了運(yùn)算的復(fù)雜度,。

    4.1. 算法描述

    指紋特征采用每個AP 的RSSI 均值,，即：

    也就是，訓(xùn)練階段對同一位置點(diǎn)采集的每個AP 的多次數(shù)據(jù)取平均,，定位階段也是如此,，區(qū)別在于訓(xùn)練階段采集數(shù)據(jù)多，以便得到盡量多的信息,，定位階段采集的數(shù)據(jù)少,，減少定位延時(shí)，一定程度上提高了實(shí)時(shí)性,。

    指紋匹配采用快速選擇的方式,。偽碼如下：

    對每個掃描到的AP 的RSSI 值，設(shè)定一個選擇區(qū)間[RSSI-σ,，RSSI+σ],σ為多次實(shí)驗(yàn)的經(jīng)驗(yàn)值,，在指紋庫中查找滿足此區(qū)間范圍的位置點(diǎn),，若有n 個位置點(diǎn)落在此區(qū)間范圍，則這些位置點(diǎn)分別取權(quán)值為1/n,其他的位置點(diǎn)則取權(quán)值為0;對所有AP 做如上處理后,，選出權(quán)值最大的位置點(diǎn)為估計(jì)位置,。如有多個位置點(diǎn)權(quán)值一樣，則比較信號強(qiáng)度距離,，取最小者,。

    4.2. 算法分析

    本文的算法是建立在RSSI 統(tǒng)計(jì)特性相對穩(wěn)定的基礎(chǔ)上，從圖11 中可以看出,，RSSI 值的直方圖分布與正態(tài)分布曲線近似,，因此均值在一定程度上代表了RSSI 特征。這也避免了單次掃描的信號強(qiáng)度中某個AP 的RSSI 不穩(wěn)定造成的定位結(jié)果偏差,。

圖11 RSSI 的統(tǒng)計(jì)特性

    時(shí)間復(fù)雜度分析：一次掃描有m 個AP,前期訓(xùn)練階段有n 個位置點(diǎn),，則要進(jìn)行m 次選擇，每次選擇遍歷n 個位置點(diǎn),，時(shí)間復(fù)雜度為O（m*n）,，遇到權(quán)值一致的情況，要進(jìn)行二次選擇,，最壞情況再比較n 次,，時(shí)間復(fù)雜度為O（n），所以總的時(shí)間復(fù)雜度為O（m*n）,。

    5. 實(shí)驗(yàn)

    5.1. 實(shí)驗(yàn)過程

    實(shí)驗(yàn)在計(jì)算所6 層進(jìn)行,，見圖12,在南北兩側(cè)走廊總共采集了24 個位置點(diǎn)，距離約4米,，加上在645 房間,，總共25 個位置點(diǎn)的數(shù)據(jù)。掃描周期1s,掃描次數(shù)120 次,。采集數(shù)據(jù)耗時(shí)約1 小時(shí),。

    圖12 實(shí)驗(yàn)環(huán)境

    本實(shí)驗(yàn)主要為驗(yàn)證定位準(zhǔn)確性，所以定位時(shí)采用多次掃描的均值作為信號特征,。共選取了6 個位置點(diǎn)作為實(shí)驗(yàn)的位置點(diǎn),。測試次數(shù)約為50 次，掃描周期為2s,運(yùn)行界面見圖13.

    5.2. 實(shí)驗(yàn)結(jié)果

    各實(shí)驗(yàn)位置點(diǎn)的結(jié)果見圖14.各個隨機(jī)測試位置點(diǎn)的定位準(zhǔn)確率都較高,。

    6. 總結(jié)

    本文基于Android 智能手機(jī)平臺,，設(shè)計(jì)并實(shí)現(xiàn)了一種基于WiFi 信號的移動終端定位系統(tǒng)，并提出了一種基于權(quán)值選擇的定位算法,，一定程度上克服RSSI 信號隨機(jī)擾動帶來的定位誤差,，經(jīng)過實(shí)際環(huán)境的測試，多次定位實(shí)驗(yàn)的精度在4 米左右，適當(dāng)調(diào)整AP 的布置可以進(jìn)一步定位精度,。本系統(tǒng)可方便地部署到展館,、校園等實(shí)際場景中。