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

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

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

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

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

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

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

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

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

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

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

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

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

13、者不難發(fā)現(xiàn)基于位置指紋識(shí)別的定位精度遠(yuǎn)遠(yuǎn)高于基于三角形算法的WiFi定位。由于基于位置指紋識(shí)別的無(wú)線定位并不需要知道AP的位置及準(zhǔn)確的信道模型,因此不管在具體實(shí)施上還是定位性能上,其較之于基于三角形算法的定位都具有較大的優(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參考文獻(xiàn)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ú)線傳感器網(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. 【作者簡(jiǎn)介】盧恒惠:清華大學(xué)深圳研究生院現(xiàn)代通信實(shí)驗(yàn)室在讀博士研究生,主要研究方向包括無(wú)線定位、車輛組合定位及車載自組織網(wǎng)等。劉興川:清華大學(xué)深圳研究生院現(xiàn)代通信實(shí)驗(yàn)室在讀博士研究生,主要研究方向包括WiFi定位、汽車電子等。張 超:清華大學(xué)深圳研究生院現(xiàn)代通信實(shí)驗(yàn)室在讀碩士研究生,主要研究方向?yàn)槠囯娮印? 小結(jié)本文研究了基于三角形算法及位置指紋識(shí)別算法的WiFi無(wú)線定位問(wèn)題,從基礎(chǔ)理論和實(shí)際測(cè)試兩個(gè)方面進(jìn)行了探討研究。理論分析與實(shí)驗(yàn)結(jié)果均表明,基于WiFi的無(wú)線室外定位是可能的;較之于三角形算法,使用位置指紋識(shí)別的WiFi定位系統(tǒng)在可用性與定位精度方面都具有較大優(yōu)勢(shì)。在本文的實(shí)驗(yàn)環(huán)境與簡(jiǎn)單建模下,其定位精度最大可提高92.08%。近日,中國(guó)電信山東分公司(下稱“山東電信”鄭重宣布啟動(dòng)“健康翼計(jì)劃”,并發(fā)布了六種相關(guān)手機(jī)和服務(wù)。“健康翼計(jì)劃”是一項(xiàng)立足企業(yè)、服務(wù)大眾、助推社會(huì)和諧的民生信息化工程,由山東省衛(wèi)生廳、山東電信,以及包括山東省立醫(yī)院、山東大學(xué)第二醫(yī)院、青島市市立醫(yī)院、濟(jì)寧第一人民醫(yī)院、千佛山醫(yī)院等省內(nèi)著名醫(yī)院在內(nèi)的機(jī)構(gòu)共同打造