室內(nèi)定位常用算法概述

室內(nèi)定位常用算法概述一.室內(nèi)定位目的和意義隨著數(shù)據(jù)業(yè)務(wù)和多媒體業(yè)務(wù)的快速增加，人們對定位與導(dǎo)航的需求日益增大，尤其在復(fù)雜的室內(nèi)環(huán)境，如機場大廳、展廳、倉庫、超市、圖書館、地下停車場、礦井等環(huán)境中，常常需要確定移動終端或其持有者、設(shè)施與物品在室內(nèi)的位置信息。但是受定位時間、定位精度以及復(fù)雜室內(nèi)環(huán)境等條件的限制，比擬完善的定位技術(shù)目前還無法很好地利用。因此，專家學(xué)者提出了許多室內(nèi)定位技術(shù)解決方案，如A-GPS定位技術(shù)、超聲波定位技術(shù)、藍牙技術(shù)、紅外線技術(shù)、射頻識別技術(shù)、超寬帶技術(shù)、無線局域網(wǎng)絡(luò)、光跟蹤定位技術(shù)，以及圖像分析、信標(biāo)定位、計算機視覺定位技術(shù)等等。這些室內(nèi)定位技術(shù)從總體上可歸納為幾類，即GNSS技術(shù)(如偽衛(wèi)星等)，無線定位技術(shù)(無線通信信號、射頻無線標(biāo)簽、超聲波、光跟蹤、無線傳感器定位技術(shù)等)，其它定位技術(shù)(計算機視覺、航位推算等)，以及GNSS和無線定位組合的定位技術(shù)(A-GPS或A-GNSS)。由于在室內(nèi)環(huán)境下對于不同的建筑物而言，室內(nèi)布置，材料結(jié)構(gòu)，建筑物尺度的不同導(dǎo)致了信號的路徑損耗很大，與此同時，建筑物的內(nèi)在結(jié)構(gòu)會引起信號的反射，繞射，折射和散射，形成多徑現(xiàn)象，使得接收信號的幅度，相位和到達時間發(fā)生變化，造成信號的損失，定位的難度大。雖然室內(nèi)定位是定位技術(shù)的一種，和室外的無線定位技術(shù)相比有一定的共性，但是室內(nèi)環(huán)境的復(fù)雜性和對定位精度和平安性的特殊要求，使得室內(nèi)無線定位技術(shù)有著不同于普通定位系統(tǒng)的鮮明特點，而且這些特點是戶外定位技術(shù)所不具備的。因此，兩者區(qū)域的標(biāo)識和劃分標(biāo)準(zhǔn)是不同的?；谑覂?nèi)定位的諸多特點，室內(nèi)定位技術(shù)和定位算法已成為各國科技工作者研究的熱點。如何提高定位精度仍將是今后研究的重點。二.室內(nèi)定位技術(shù)的國內(nèi)外開展趨勢室內(nèi)GPS定位技術(shù)GPS是目前應(yīng)用最為廣泛的定位技術(shù)。當(dāng)GPS接收機在室內(nèi)工作時，由于信號受建筑物的影響而大大衰減，定位精度也很低，要想到達室外一樣直接從衛(wèi)星播送中提取導(dǎo)航數(shù)據(jù)和時間信息是不可能的。為了得到較高的信號靈敏度，就需要延長在每個碼延遲上的停留時間，A-GPS技術(shù)為這個問題的解決提供了可能性[7]。室內(nèi)GPS技術(shù)采用大量的相關(guān)器并行地搜索可能的延遲碼，同時也有助于實現(xiàn)快速定位。利用GPS進行定位的優(yōu)勢是衛(wèi)星有效覆蓋范圍大，且定位導(dǎo)航信號免費。缺點是定位信號到達地面時較弱，不能穿透建筑物，而且定位器終端的本錢較高。室內(nèi)無線定位技術(shù)隨著無線通信技術(shù)的開展，新興的無線網(wǎng)絡(luò)技術(shù)，例如WiFi、ZigBee、藍牙和超寬帶等，在辦公室、家庭、工廠等得到了廣泛應(yīng)用?！t外線室內(nèi)定位技術(shù)。紅外線室內(nèi)定位技術(shù)定位的原理是，紅外線IR標(biāo)識發(fā)射調(diào)制的紅外射線，通過安裝在室內(nèi)的光學(xué)傳感器接收進行定位。雖然紅外線具有相對較高的室內(nèi)定位精度，但是由于光線不能穿過障礙物，使得紅外射線僅能視距傳播。直線視距和傳輸距離較短這兩大主要缺點使其室內(nèi)定位的效果很差。當(dāng)標(biāo)識放在口袋里或者有墻壁及其他遮擋時就不能正常工作，需要在每個房間、走廊安裝接收天線，造價較高。因此，紅外線只適合短距離傳播，而且容易被熒光燈或者房間內(nèi)的燈光干擾，在精確定位上有局限性?！暡ǘㄎ患夹g(shù)。超聲波測距主要采用反射式測距法，通過三角定位等算法確定物體的位置，即發(fā)射超聲波并接收由被測物產(chǎn)生的回波，根據(jù)回波與發(fā)射波的時間差計算出待測距離，有的那么采用單向測距法。超聲波定位系統(tǒng)可由假設(shè)干個應(yīng)答器和一個主測距器組成，主測距器放置在被測物體上，在微機指令信號的作用下向位置固定的應(yīng)答器發(fā)射同頻率的無線電信號，應(yīng)答器在收到無線電信號后同時向主測距器發(fā)射超聲波信號，得到主測距器與各個應(yīng)答器之間的距離。當(dāng)同時有3個或3個以上不在同一直線上的應(yīng)答器做出回應(yīng)時，可以根據(jù)相關(guān)計算確定出被測物體所在的二維坐標(biāo)系下的位置。超聲波定位整體定位精度較高，結(jié)構(gòu)簡單，但超聲波受多徑效應(yīng)和非視距傳播影響很大，同時需要大量的底層硬件設(shè)施投資，本錢太高?！{牙技術(shù)。藍牙技術(shù)通過測量信號強度進行定位。這是一種短距離低功耗的無線傳輸技術(shù)，在室內(nèi)安裝適當(dāng)?shù)乃{牙局域網(wǎng)接入點，把網(wǎng)絡(luò)配置成基于多用戶的根底網(wǎng)絡(luò)連接模式，并保證藍牙局域網(wǎng)接入點始終是這個微微網(wǎng)(piconet)的主設(shè)備，就可以獲得用戶的位置信息。藍牙技術(shù)主要應(yīng)用于小范圍定位，例如單層大廳或倉庫。藍牙室內(nèi)定位技術(shù)最大的優(yōu)點是設(shè)備體積小、易于集成在PDA、PC以及中，因此很容易推廣普及。理論上，對于持有集成了藍牙功能移動終端設(shè)備的用戶，只要設(shè)備的藍牙功能開啟，藍牙室內(nèi)定位系統(tǒng)就能夠?qū)ζ溥M行位置判斷。采用該技術(shù)作室內(nèi)短距離定位時容易發(fā)現(xiàn)設(shè)備且信號傳輸不受視距的影響。其缺乏在于藍牙器件和設(shè)備的價格比擬昂貴，而且對于復(fù)雜的空間環(huán)境，藍牙系統(tǒng)的穩(wěn)定性稍差，受噪聲信號干擾大?！漕l識別技術(shù)。射頻識別技術(shù)利用射頻方式進行非接觸式雙向通信交換數(shù)據(jù)以到達識別和定位的目的。這種技術(shù)作用距離短，一般最長為幾十米。但它可以在幾毫秒內(nèi)得到厘米級定位精度的信息，且傳輸范圍很大，本錢較低。同時由于其非接觸和非視距等優(yōu)點，可望成為優(yōu)選的室內(nèi)定位技術(shù)。目前，射頻識別研究的熱點和難點在于理論傳播模型的建立、用戶的平安隱私和國際標(biāo)準(zhǔn)化等問題。優(yōu)點是標(biāo)識的體積比擬小，造價比擬低，但是作用距離近，不具有通信能力，而且不便于整合到其他系統(tǒng)之中。——超寬帶技術(shù)。超寬帶技術(shù)是一種全新的、與傳統(tǒng)通信技術(shù)有極大差異的通信新技術(shù)。它不需要使用傳統(tǒng)通信體制中的載波，而是通過發(fā)送和接收具有納秒或納秒級以下的極窄脈沖來傳輸數(shù)據(jù)，從而具有GHz量級的帶寬。超寬帶可用于室內(nèi)精確定位，例如戰(zhàn)場士兵的位置發(fā)現(xiàn)、機器人運動跟蹤等。超寬帶系統(tǒng)與傳統(tǒng)的窄帶系統(tǒng)相比，具有穿透力強、功耗低、抗多徑效果好、平安性高、系統(tǒng)復(fù)雜度低、能提供精確定位精度等優(yōu)點。因此，超寬帶技術(shù)可以應(yīng)用于室內(nèi)靜止或者移動物體以及人的定位跟蹤與導(dǎo)航，且能提供十分精確的定位精度?！猈i-Fi技術(shù)。無線局域網(wǎng)絡(luò)(WLAN)是一種全新的信息獲取平臺，可以在廣泛的應(yīng)用領(lǐng)域內(nèi)實現(xiàn)復(fù)雜的大范圍定位、監(jiān)測和追蹤任務(wù)，而網(wǎng)絡(luò)節(jié)點自身定位是大多數(shù)應(yīng)用的根底和前提。當(dāng)前比擬流行的Wi-Fi定位是無線局域網(wǎng)絡(luò)系列標(biāo)準(zhǔn)之IEEE802.11的一種定位解決方案。該系統(tǒng)采用經(jīng)驗測試和信號傳播模型相結(jié)合的方式，易于安裝，需要很少基站，能采用相同的底層無線網(wǎng)絡(luò)結(jié)構(gòu)，系統(tǒng)總精度高。芬蘭的Ekahau公司開發(fā)了能夠利用Wi-Fi進行室內(nèi)定位的軟件。Wi-Fi繪圖的精確度大約在1米至20米的范圍內(nèi)，總體而言，它比蜂窩網(wǎng)絡(luò)三角測量定位方法更精確。但是，如果定位的測算僅僅依賴于哪個Wi-Fi的接入點最近，而不是依賴于合成的信號強度圖，那么在樓層定位上很容易出錯。目前，它應(yīng)用于小范圍的室內(nèi)定位，本錢較低。但無論是用于室內(nèi)還是室外定位，Wi-Fi收發(fā)器都只能覆蓋半徑90米以內(nèi)的區(qū)域，而且很容易受到其他信號的干擾，從而影響其精度，定位器的能耗也較高?！猌igBee技術(shù)。ZigBee是一種新興的短距離、低速率無線網(wǎng)絡(luò)技術(shù)，它介于射頻識別和藍牙之間，也可以用于室內(nèi)定位。它有自己的無線電標(biāo)準(zhǔn)，在數(shù)千個微小的傳感器之間相互協(xié)調(diào)通信以實現(xiàn)定位。這些傳感器只需要很少的能量，以接力的方式通過無線電波將數(shù)據(jù)從一個傳感器傳到另一個傳感器，所以它們的通信效率非常高。ZigBee最顯著的技術(shù)特點是它的低功耗和低本錢。除了以上提及的定位技術(shù)，還有基于計算機視覺、光跟蹤定位、基于圖像分析、磁場以及信標(biāo)定位等。此外，還有基于圖像分析的定位技術(shù)、信標(biāo)定位、三角定位等。目前很多技術(shù)還處于研究試驗階段，如基于磁場壓力感應(yīng)進行定位的技術(shù)。三.定位算法傳感器節(jié)點的定位算法根據(jù)定位過程中所需信息的不同可分為兩大類：?基于測距(range—based)?測距無關(guān)(range—free)測距無關(guān)(range—free)無需確定距離和角度信息，僅根據(jù)網(wǎng)絡(luò)對通性等信息加以實現(xiàn)。主要算法有：1.質(zhì)心算法;2.APIT(approximatepoint-in-triangulationteat)近似三角形內(nèi)點測試法3.DV-Hop基于測距(range—based)測量節(jié)點問點到點的距離或角度信息，使用三邊測量法、三角測量法或最大似然估計法計算節(jié)點位置。主要算法有：TOA(timeofarrival)TDOA(TimeDifference0fArrival)AOA(AngleofArrival)RSSI(ReceivedSignalStrengthIndication)RSSI(RadioSignalStrengthIndicator)無線電信號強度，又稱RSSI(RadioSignalStrengthIndicator)。發(fā)射功率，接受節(jié)點通過接收功率，計算傳播損耗，再通過理論或者經(jīng)驗的傳播模型將傳播損耗轉(zhuǎn)換為距離。在自由空間中，距發(fā)射d處的天線接收到的信號強度由下面的公式(1)給出:〔1〕式中，d為接收端與發(fā)射端之間的距離(m)；d0為參考距離(m)，一般取1m；Pr(d)是接收端的接收信號功率(dBm)；Pr(d0)是參考距離d0點對應(yīng)的接收信號功率(dBm)；XdBm是一個平均值為0的高斯隨機變量(dBm)，反映了當(dāng)距離一定時，接收信號功率的變化；n為路徑損耗指數(shù)，是一個與環(huán)境相關(guān)的值。通過測量接收信號的強度，利用這個公式即可計算收發(fā)節(jié)點之間的大概距離[31]。一旦可以得到參考節(jié)點與未知節(jié)點之間的距離信息，就可以采用三邊測量法或者最大似然估計法計算出未知節(jié)點的位置。在三維空間中，三邊測量法指的己知一個未知節(jié)點到三個以上參考節(jié)點的距離，就可以確定該點的坐標(biāo);三邊測量法在二維空間里可以用幾何圖形表示為:當(dāng)?shù)玫轿粗?jié)點到一個參考節(jié)點的距離時，就可以確定，此未知節(jié)點在以此參考節(jié)點為圓心，以距離為半徑的圓上;如果得到未知節(jié)點到3個參考節(jié)點的距離，那么3個圓的交點就是該未知節(jié)點的位置。n的幾種典型值環(huán)境n戶外自由空間2遮蔽的城市空間2.7~5室內(nèi)視距1.6~1.8有阻擋障礙的空間4~6RSSI值采集由于無線信號的非線性時變特性,在同一個點不同時刻采集到的信號強度值是不同的，并且無法判斷哪一個值較為準(zhǔn)確。在距離發(fā)射端1m遠(yuǎn)處的接受端采集100次信號，對結(jié)果進行分析，見圖1。圖1在距離發(fā)射端1m處的接受端采集100個RRSI值的結(jié)果比擬由圖1可見，即使在同一點，采集到的RSSI值也有很大的不同。但根本都在一個范圍內(nèi)波動。由于采集信號的隨機性，采集的RSSI參數(shù)并不能直接用于運算，需要對其進行處理。方法有：1.均值法2.高斯分布法節(jié)點定位計算方法〔可以參考的算法〕1)最小二乘法用最小二乘法來估算節(jié)點位置坐標(biāo)也是無線定位中一種經(jīng)常采用的方法。最小二乘法的突出優(yōu)點是只需要一個假定的信號傳播模型和信號觀測值，計算簡單，易于實現(xiàn)。1，2，3等n個節(jié)點的坐標(biāo)分別為(x1，y1)，(x2，y2)，(x3，y3)…(xn，yn)，它們到節(jié)點D的距離分別為d1，d2，d3···dn，假設(shè)節(jié)點D的坐標(biāo)為(x，y)。從第一行開始分別減去最后一行，得：使用最小二乘法得：這里的向量X就是移動節(jié)點的坐標(biāo)。2〕三角質(zhì)心法在圓周定位模型中，三角質(zhì)心法是一種較易實現(xiàn)、便于理解的算法。三角質(zhì)心法的原理如下：在圓周定位模型中，理論上如果知道移動節(jié)點到三個信標(biāo)節(jié)點的物理距離，用這三個信標(biāo)節(jié)點做三個圓的圓心，到移動節(jié)點的物理距離為半徑，畫三個圓，這三個圓與移動節(jié)點都應(yīng)該是相交的，即三個圓的公共交點就是移動節(jié)點MS的位置。但在實際中，由于噪聲的影響，信號遇到障礙物以后的急劇衰落，測量工具帶來的誤差等原因，在圓周模型中的三個圓是不可能相交于一點的。由于在室內(nèi)環(huán)境下，周圍的障礙物等對電磁波信號的吸收，一般使得接收機接收到的信號強度值會小于預(yù)計的信號強度值，反映到推導(dǎo)出來的移動節(jié)點到信標(biāo)節(jié)點的估計距離上，結(jié)果就是所畫的三個圓的半徑都偏大。這一種情況應(yīng)該算是最為常見的情況，如下列圖2所示：圖2中畫出來的三個圓一共有三個交點，形成一個三角形區(qū)域。所求的移動節(jié)點MS的位置就在這三個圓的公共交集區(qū)域內(nèi)。通過取三角形的質(zhì)心，作為移動節(jié)點MS的估計位置。圖2基于圓周模型的三角質(zhì)心法3〕加權(quán)三角質(zhì)心算法通過對無線電傳播路徑損耗模型的分析,可以發(fā)現(xiàn)利用普通質(zhì)心算法,沒有反映出信標(biāo)節(jié)點對節(jié)點位置的影響力的大小,影響了定位精度.文中設(shè)計了加權(quán)質(zhì)心算法,它的根本思想是:在質(zhì)心算法中,通過加權(quán)因子來表達信標(biāo)節(jié)點對質(zhì)心坐標(biāo)決定權(quán)的大小,利用加權(quán)因子表達各信標(biāo)節(jié)點對質(zhì)心位置的影響程度,反映它們之間的內(nèi)在關(guān)系.通過下式中的加權(quán)因子來表達這種約束力。4〕加權(quán)質(zhì)心算法普通的質(zhì)心算法同上面所描述的三角質(zhì)心算法有所不同，它不需要知道未知節(jié)點到錨節(jié)點的距離。加權(quán)質(zhì)心算法就是質(zhì)心算法的根底上加上一個權(quán)值，提高定位精度。公式如下：其中，為未知節(jié)點估計位置的坐標(biāo)，為錨節(jié)點j的坐標(biāo)，為權(quán)值。為未知節(jié)點i與錨節(jié)點之間的距離，g是一個可以根據(jù)實際環(huán)境進行調(diào)節(jié)的參數(shù)。5〕改良的加權(quán)質(zhì)心算法此方法對上面的的表達式進行了改良。如下圖，RNi(i=1~9)是任意放置的錨節(jié)點。未知節(jié)點j能夠接收到RNm(m=1~4)的數(shù)據(jù)包。我們把其中一個接收信號強度最大的錨節(jié)點定義為RNmax，其信號強度為Pmaxj(d)，再將它與其他信號進行相減，得可見光Lifi通信定義：可見光無線通信〔稱為LiFi——