基于三角形與位置指紋識別算法的WiFi定位比較

1、【摘 要】WiFi的定位實現(xiàn)主要基于三角形算法和位置指紋識別,文章首先分別對這兩方面從理論上作了介紹,然后通過在校園和市內(nèi)兩種室外環(huán)境的現(xiàn)場實驗,證實了基于WiFi無線定位的可能性,也表明了在室外環(huán)境下基于位置指紋識別的定位性能遠優(yōu)于基于三角形算法。【關(guān)鍵詞】WiFi定位 三角形算法 位置指紋識別 RSS基于三角形與位置指紋識別算法的WiFi定位比較收稿日期:2010-3-15盧恒惠 劉興川 張 超 林孝康 清華大學深圳研究生院1 引言目標的位置信息在各種場合中發(fā)揮著重要作用,如車輛導航、礦井井下人員定位、醫(yī)療看護對象定位、建筑工地管理等。GPS作為全球最廣泛使用的衛(wèi)星導航定位技術(shù),在許多領(lǐng)域

2、得到了推廣應(yīng)用。然而,其信號卻極易受障礙物的干擾和阻斷,在密集的城市地帶、隧道、室內(nèi)等環(huán)境定位不可靠甚至于失效。因此,必須有其它的定位技術(shù)輔助GPS或者單獨在無GPS可用的場合下提供定位服務(wù)。隨著IEEE802.11技術(shù)的成熟,WiFi在世界各地普及,其覆蓋面越來越廣。雖然WiFi并不是為定位而設(shè)計,但接入點(AP或基站定期發(fā)送的信標信號中所含的接收信號強度(RSS信息為定位移動臺提供了可能性,將其應(yīng)用于定位場合受到了學術(shù)界與產(chǎn)業(yè)界的極大關(guān)注。較之現(xiàn)行定位技術(shù)如GPS、蜂窩定位、無跡推算等,基于WiFi的定位具有如下優(yōu)勢1:(1可工作于室內(nèi)、室外等不同場合,為實現(xiàn)無處不在的定位提供了可能性;(

3、2僅依賴于現(xiàn)有的WiFi網(wǎng)絡(luò),無需對其進行任何改動,使用成本低;(3WiFi信號受非視距(NLOS影響小,即使在有障礙物阻擋的情況下也能使用。當前,絕大多數(shù)基于WiFi的定位系統(tǒng)都利用RSS,其方法主要分成兩類:三角形算法和位置指紋識別(fingerprinting算法2。三角形算法利用待測目標到至少三個已知參考點之間的距離信息估計目標位置,而位置指紋識別則通過比較定位所需的信號特征指紋信息獲取目標位置。本文對這兩種方法進行了研究,并在不同的室外環(huán)境下開展實驗測試,對二者的性能進行了比較。2 三角形算法基于三角形算法的WiFi定位可分成兩個階段:測距與定位。2.1 測距階段 待測點首先接收來自

4、三個不同已知位置AP的RSS,然后依照無線信號的傳輸損耗模型將其轉(zhuǎn)換成待測目標到相應(yīng)AP的距離。無線信號在傳輸過程中通常會受路徑損耗、陰影衰落等的影響,接收信號功率隨距離的變化關(guān)系可由信號傳輸損耗模型給出。在城市、郊區(qū)等環(huán)境,傳輸損耗模型通常采用如下簡化模型3:P r (d =K -10lg(d (dBm (1其中,d 代表接收機和發(fā)射機之間的距離,代表非自由空間的損耗系數(shù),K 是如下常數(shù):(=10lg 20lg(0.001r 00P d K d W +(22.2 定位階段 通過三角形算法計算待測點位置,即分別以已知位置的三個AP為圓心,以其各自到待測點的距離為半徑做圓,所得三個圓的交點,如圖

5、1所示: 圖1 三角形算法示意圖設(shè)未知節(jié)點D的坐標為(x ,y ,已知A、B、C 三個點的坐標分別為(x 1,y 1、(x 2,y 2、(x 3,y 3,它們到D的距離分別為d 1、d 2、d 3,則D的位置可由下列方程中的任意兩個求得4:222111(x x y y d += (3222222(x x y y d += (4222333(x x y y d += (5然而,在實際應(yīng)用中,由于測量誤差的存在,三圓交于一點的情況未必出現(xiàn),以致方程組(3、(4、(5無解。在三圓兩兩相交的情況下,有圖2、3兩種典型的無解情況:圖2 方程組無解情況1圖3 方程組無解情況2在這兩種情況下,D點的求解方法

6、如下4:(1根據(jù)方程(3、(4、(5分別求解圓A 與圓B的交點(X ab1,Y ab1、(X ab2,Y ab2,圓A與圓C 的交點(X ac1,Y ac1、(X ac2,Y ac2,及圓B與圓C的交點(X bc1,Y bc1、(X bc2,Y bc2。(2將圓A與圓C的交點代入(x - x 22+(y - y 22,找出距B圓圓心較近的點,設(shè)為(X ac ,Y ac 。同理,求解(X ab ,Y ab 、(X bc ,Y bc 。(3近似計算待測點位置:(,33ab ac bc ab ac bcX X X Y Y Y x y +=(6由上述介紹可知,基于三角形算法的WiFi定位很大程度上依賴

7、于確知的AP位置信息及準確的信號傳輸損耗模型。然而,由于涉及個人隱私等原因,獲知所有AP 的位置信息并不現(xiàn)實。此外,由于影響信號傳輸?shù)囊蛩睾芏?不同環(huán)境下的信號傳輸損耗模型大不相同,建立一個準確的、適合實際應(yīng)用的損耗模型存在著很大的困難。因此,基于三角形算法的無線定位在具體實施中困難重重。3 位置指紋識別算法與通常意義上的指紋識別類似,位置指紋識別依靠表征目標特征的數(shù)據(jù)庫進行識別。其定位過程主要分為訓練與定位兩個階段5,如圖4所示:圖4 基于位置指紋識別的WiFi定位3.1 訓練階段其目標在于建立一個位置指紋識別數(shù)據(jù)庫。首先,選擇合理的參考點分布,確保能為定位階段的準確位置估計提供足夠的信息。

8、接著依次在各個參考點上測量來自不同AP的RSS值,將相應(yīng)的MAC地址與參考點的位置信息記錄在數(shù)據(jù)庫中,直至遍歷關(guān)注區(qū)域內(nèi)所有的參考點。由于受環(huán)境影響,無線信號強度并不穩(wěn)定,為了克服RSS不穩(wěn)定對定位的影響,通常在每個參考點上多次測量取平均。3.2 定位階段給定數(shù)據(jù)庫后,依據(jù)一定的匹配算法將待測點上接收的AP RSS與數(shù)據(jù)庫中的已有數(shù)據(jù)進行比較,計算位置估計值。常用的匹配算法有最近鄰法(NN、KNN、神經(jīng)網(wǎng)絡(luò)等,本文采用簡單的NN算法。假定待測點接收的RSS觀測值為s=ss1,ss2,ss n,數(shù)據(jù)庫中的已有記錄為S i=SS1,SS2,SS Ni,其中n代表待測點上檢測到的不同AP數(shù);i1,N

9、 T,N T為數(shù)據(jù)庫中的記錄數(shù);N i代表第i條記錄中存儲的不同AP數(shù),則NN算法可以表示成下述形式3:L=argmin i1,NT|s-S i| (7其中,|s-S i|代表s和S i之間的歐式距離。4 實測結(jié)果分析為考察三角形和位置指紋識別算法在WiFi定位中的應(yīng)用,本文選取校園和市區(qū)兩個測試點開展了現(xiàn)場實驗:清華大學深圳研究生院及深圳市荔園大廈附近城區(qū)。參考點及待測點的選取如圖5、6所示,其中紅色代表參考點(位置已知,黑色代表待測點(位置未知。在清華大學深圳研究生院選取的參考點和待測點數(shù)分別為307和145,在荔園大廈附近則選取了266個參考點和132個待測點。實測中采用配備了Intel

10、 (R PRO/Wireless 3945 ABG Network Connection網(wǎng)卡的IBM X61筆記本電腦收集WiFi 信息;選用TK-158-USB收集GPS信息,以其作為準確的位置信息,為WiFi定位結(jié)果提供比較基準。軟件部分則采用WirelessMon3.0掃描AP信號,記錄相應(yīng)的MAC、RSS、GPS經(jīng)緯度、時間等信息,選用SQL server 2000建立數(shù)據(jù)庫,利用C+進行定位處理。 圖5 清華深圳研究生院圖6 深圳市荔園大廈周邊城區(qū)4.1 基于三角形算法的WiFi定位基于三角形的定位必須已知AP的位置,因此首先要獲取AP的位置信息。由于每個AP發(fā)出的信號可能被不同的參

11、考點接收,因此利用能檢測到同一AP信號的三個參考點位置,依照三角形算法就能預(yù)先計算出AP位置。其中,信號的傳輸損耗模型依據(jù)實測信號隨距離的變化擬合獲得,變化曲線如圖7所示。相應(yīng)地,待測點的位置則可根據(jù)已知AP的位置,采用同樣的三角形算法獲得。實驗結(jié)果如表1、2所示。圖7 接收信號強度隨距離的變化曲線由表1可知,依照本文的方法并不能計算出所有AP 的位置。然而在AP數(shù)量遠遠超過測試點時,即使不能知道所有AP的位置信息也依舊能夠算出測試點位置。無法確定所有AP位置的可能原因如下:(1接收信號強度除了和距離有關(guān)外,還受到天線高度、天線方向等的影響,本文擬合的信號傳輸損耗模型并沒有考慮除距離外的其它因

12、素,不能準確反映真實情況。(2不同位置處的環(huán)境不同,相應(yīng)的損耗模型也有所差別,用同一模型勢必會引入誤差。由表2可知,基于三角形算法的WiFi定位,其定位性能并不高,定位精度隨著可用AP數(shù)的增加而提高。4.2 基于位置指紋識別的WiFi定位依照前述的位置指紋識別方法,本文通過在參考點上多次測量取平均來建立數(shù)據(jù)庫,每個參考點采樣次數(shù)大于100。實驗結(jié)果如表3:表3 基于位置指紋識別的定位誤差比較最小偏差平均偏差最大偏差清華X方向(m0 6.8428.45清華Y方向(m07.5629.78荔園X方向(m0 2.2423.45荔園Y方向(m0 1.9618.52由表3同樣可以得到表2的分析結(jié)果,對比二

13、者不難發(fā)現(xiàn)基于位置指紋識別的定位精度遠遠高于基于三角形算法的WiFi定位。由于基于位置指紋識別的無線定位并不需要知道AP的位置及準確的信道模型,因此不管在具體實施上還是定位性能上,其較之于基于三角形算法的定位都具有較大的優(yōu)越性。表1 基于三角形算法定位的可用性比較AP總數(shù)位置可算AP數(shù)TP總數(shù)位置可算TP數(shù)清華140101145113荔園20521302132132表2 基于三角形算法的定位性能比較最小偏差平均偏差最大偏差清華X方向(m0.177033.3933144.2904清華Y方向(m0.934027.4355157.4788荔園X方向(m0.547623.734379.8340荔園Y方

14、向(m0.139522.4710 87.0383 RSS/dBmDistance/m參考文獻1Duvallet F, Tews A D. WiFi position estimation in industrial environments using Gaussian processes C. Proc of IEEE RSJ,2008: 2216-2221.2Salvatore Cavalieri. WLAN-based outdoor localization using pattern matching algorithm J. International Journal of Wir

15、eless Information Networks,2007,14(4: 265-279.3Sinan Gezici1. A Survey on Wireless Position Estimation J. Wireless Personal Communications, 2008,44(3: 263-282.4林瑋, 陳傳峰. 基于RSSI的無線傳感器網(wǎng)絡(luò)三角形質(zhì)心定位算法J. 現(xiàn)代電子技術(shù),2009(2: 180-182. 5Binghao Li, Ishrat J Quader, Andrew G Dempster. On outdoor positioning with WiFi

16、 J. Journal of Global Positioning Systems,2008,7(1: 18-26. 【作者簡介】盧恒惠:清華大學深圳研究生院現(xiàn)代通信實驗室在讀博士研究生,主要研究方向包括無線定位、車輛組合定位及車載自組織網(wǎng)等。劉興川:清華大學深圳研究生院現(xiàn)代通信實驗室在讀博士研究生,主要研究方向包括WiFi定位、汽車電子等。張 超:清華大學深圳研究生院現(xiàn)代通信實驗室在讀碩士研究生,主要研究方向為汽車電子。5 小結(jié)本文研究了基于三角形算法及位置指紋識別算法的WiFi無線定位問題,從基礎(chǔ)理論和實際測試兩個方面進行了探討研究。理論分析與實驗結(jié)果均表明,基于WiFi的無線室外定位是可能的;較之于三角形算法,使用位置指紋識別的WiFi定位系統(tǒng)在可用性與定位精度方面都具有較大優(yōu)勢。在本文的實驗環(huán)境與簡單建模下,其定位精度最大可提高92.08%。近日,中國電信山東分公司(下稱“山東電信”鄭重宣布啟動“健康翼計劃”,并發(fā)布了六種相關(guān)手機和服務(wù)?！敖】狄碛媱潯笔且豁椓⒆闫髽I(yè)、服務(wù)大眾、助推社會和諧的民生信息化工程,由山東省衛(wèi)生廳、山東電信,以及包括山東省立醫(yī)院、山東大學第二醫(yī)院、青島市市立醫(yī)院、濟寧第一人民醫(yī)院、千佛山醫(yī)院等省內(nèi)著名醫(yī)院在內(nèi)的機構(gòu)共同打造