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

1、室內(nèi)定位常用算法概述一. 室內(nèi)定位目的和意義隨著數(shù)據(jù)業(yè)務(wù)和多媒體業(yè)務(wù)的快速增加，人們對定位與導(dǎo)航的需求日益增大，尤其在復(fù)雜的室內(nèi)環(huán)境，如機(jī)場大廳、展廳、倉庫、超市、圖書館、地下停車場、礦井等環(huán)境中，常常需要確定移動終端或其持有者、設(shè)施與物品在室內(nèi)的位置信息。但是受定位時間、定位精度以及復(fù)雜室內(nèi)環(huán)境等條件的限制，比較完善的定位技術(shù)目前還無法很好地利用。因此，專家學(xué)者提出了許多室內(nèi)定位技術(shù)解決方案，如A-GPS定位技術(shù)、超聲波定位技術(shù)、藍(lán)牙技術(shù)、紅外線技術(shù)、射頻識別技術(shù)、超寬帶技術(shù)、無線局域網(wǎng)絡(luò)、光跟蹤定位技術(shù)，以及圖像分析、信標(biāo)定位、計算機(jī)視覺定位技術(shù)等等。這些室內(nèi)定位技術(shù)從總體上可歸納為幾類，

2、即GNSS技術(shù)(如偽衛(wèi)星等)，無線定位技術(shù)(無線通信信號、射頻無線標(biāo)簽、超聲波、光跟蹤、無線傳感器定位技術(shù)等)，其它定位技術(shù)(計算機(jī)視覺、航位推算等)，以及GNSS和無線定位組合的定位技術(shù)(A-GPS或A-GNSS)。由于在室內(nèi)環(huán)境下對于不同的建筑物而言，室內(nèi)布置，材料結(jié)構(gòu)，建筑物尺度的不同導(dǎo)致了信號的路徑損耗很大，與此同時，建筑物的內(nèi)在結(jié)構(gòu)會引起信號的反射，繞射，折射和散射，形成多徑現(xiàn)象，使得接收信號的幅度，相位和到達(dá)時間發(fā)生變化，造成信號的損失，定位的難度大。雖然室內(nèi)定位是定位技術(shù)的一種，和室外的無線定位技術(shù)相比有一定的共性，但是室內(nèi)環(huán)境的復(fù)雜性和對定位精度和安全性的特殊要求，使得室內(nèi)無線

3、定位技術(shù)有著不同于普通定位系統(tǒng)的鮮明特點(diǎn)，而且這些特點(diǎn)是戶外定位技術(shù)所不具備的。因此，兩者區(qū)域的標(biāo)識和劃分標(biāo)準(zhǔn)是不同的?；谑覂?nèi)定位的諸多特點(diǎn)，室內(nèi)定位技術(shù)和定位算法已成為各國科技工作者研究的熱點(diǎn)。如何提高定位精度仍將是今后研究的重點(diǎn)。二. 室內(nèi)定位技術(shù)的國內(nèi)外發(fā)展趨勢室內(nèi)GPS定位技術(shù)GPS是目前應(yīng)用最為廣泛的定位技術(shù)。當(dāng)GPS接收機(jī)在室內(nèi)工作時，由于信號受建筑物的影響而大大衰減，定位精度也很低，要想達(dá)到室外一樣直接從衛(wèi)星廣播中提取導(dǎo)航數(shù)據(jù)和時間信息是不可能的。為了得到較高的信號靈敏度，就需要延長在每個碼延遲上的停留時間，A-GPS技術(shù)為這個問題的解決提供了可能性7。室內(nèi)GPS技術(shù)采用大量的

4、相關(guān)器并行地搜索可能的延遲碼，同時也有助于實(shí)現(xiàn)快速定位。利用GPS進(jìn)行定位的優(yōu)勢是衛(wèi)星有效覆蓋范圍大，且定位導(dǎo)航信號免費(fèi)。缺點(diǎn)是定位信號到達(dá)地面時較弱，不能穿透建筑物，而且定位器終端的成本較高。室內(nèi)無線定位技術(shù)隨著無線通信技術(shù)的發(fā)展，新興的無線網(wǎng)絡(luò)技術(shù)，例如WiFi、ZigBee、藍(lán)牙和超寬帶等，在辦公室、家庭、工廠等得到了廣泛應(yīng)用。紅外線室內(nèi)定位技術(shù)。紅外線室內(nèi)定位技術(shù)定位的原理是，紅外線IR標(biāo)識發(fā)射調(diào)制的紅外射線，通過安裝在室內(nèi)的光學(xué)傳感器接收進(jìn)行定位。雖然紅外線具有相對較高的室內(nèi)定位精度，但是由于光線不能穿過障礙物，使得紅外射線僅能視距傳播。直線視距和傳輸距離較短這兩大主要缺點(diǎn)使其室內(nèi)定

5、位的效果很差。當(dāng)標(biāo)識放在口袋里或者有墻壁及其他遮擋時就不能正常工作，需要在每個房間、走廊安裝接收天線，造價較高。因此，紅外線只適合短距離傳播，而且容易被熒光燈或者房間內(nèi)的燈光干擾，在精確定位上有局限性。超聲波定位技術(shù)。超聲波測距主要采用反射式測距法，通過三角定位等算法確定物體的位置，即發(fā)射超聲波并接收由被測物產(chǎn)生的回波，根據(jù)回波與發(fā)射波的時間差計算出待測距離，有的則采用單向測距法。超聲波定位系統(tǒng)可由若干個應(yīng)答器和一個主測距器組成，主測距器放置在被測物體上，在微機(jī)指令信號的作用下向位置固定的應(yīng)答器發(fā)射同頻率的無線電信號，應(yīng)答器在收到無線電信號后同時向主測距器發(fā)射超聲波信號，得到主測距器與各個應(yīng)答

6、器之間的距離。當(dāng)同時有3個或3個以上不在同一直線上的應(yīng)答器做出回應(yīng)時，可以根據(jù)相關(guān)計算確定出被測物體所在的二維坐標(biāo)系下的位置。超聲波定位整體定位精度較高，結(jié)構(gòu)簡單，但超聲波受多徑效應(yīng)和非視距傳播影響很大，同時需要大量的底層硬件設(shè)施投資，成本太高。藍(lán)牙技術(shù)。藍(lán)牙技術(shù)通過測量信號強(qiáng)度進(jìn)行定位。這是一種短距離低功耗的無線傳輸技術(shù)，在室內(nèi)安裝適當(dāng)?shù)乃{(lán)牙局域網(wǎng)接入點(diǎn)，把網(wǎng)絡(luò)配置成基于多用戶的基礎(chǔ)網(wǎng)絡(luò)連接模式，并保證藍(lán)牙局域網(wǎng)接入點(diǎn)始終是這個微微網(wǎng)(piconet)的主設(shè)備，就可以獲得用戶的位置信息。藍(lán)牙技術(shù)主要應(yīng)用于小范圍定位，例如單層大廳或倉庫。藍(lán)牙室內(nèi)定位技術(shù)最大的優(yōu)點(diǎn)是設(shè)備體積小、易于集成在 PD

7、A、PC以及手機(jī)中，因此很容易推廣普及。理論上，對于持有集成了藍(lán)牙功能移動終端設(shè)備的用戶，只要設(shè)備的藍(lán)牙功能開啟，藍(lán)牙室內(nèi)定位系統(tǒng)就能夠?qū)ζ溥M(jìn)行位置判斷。采用該技術(shù)作室內(nèi)短距離定位時容易發(fā)現(xiàn)設(shè)備且信號傳輸不受視距的影響。其不足在于藍(lán)牙器件和設(shè)備的價格比較昂貴，而且對于復(fù)雜的空間環(huán)境，藍(lán)牙系統(tǒng)的穩(wěn)定性稍差，受噪聲信號干擾大。射頻識別技術(shù)。射頻識別技術(shù)利用射頻方式進(jìn)行非接觸式雙向通信交換數(shù)據(jù)以達(dá)到識別和定位的目的。這種技術(shù)作用距離短，一般最長為幾十米。但它可以在幾毫秒內(nèi)得到厘米級定位精度的信息，且傳輸范圍很大，成本較低。同時由于其非接觸和非視距等優(yōu)點(diǎn)，可望成為優(yōu)選的室內(nèi)定位技術(shù)。目前，射頻識別研究

8、的熱點(diǎn)和難點(diǎn)在于理論傳播模型的建立、用戶的安全隱私和國際標(biāo)準(zhǔn)化等問題。優(yōu)點(diǎn)是標(biāo)識的體積比較小，造價比較低，但是作用距離近，不具有通信能力，而且不便于整合到其他系統(tǒng)之中。超寬帶技術(shù)。超寬帶技術(shù)是一種全新的、與傳統(tǒng)通信技術(shù)有極大差異的通信新技術(shù)。它不需要使用傳統(tǒng)通信體制中的載波，而是通過發(fā)送和接收具有納秒或納秒級以下的極窄脈沖來傳輸數(shù)據(jù)，從而具有GHz量級的帶寬。超寬帶可用于室內(nèi)精確定位，例如戰(zhàn)場士兵的位置發(fā)現(xiàn)、機(jī)器人運(yùn)動跟蹤等。超寬帶系統(tǒng)與傳統(tǒng)的窄帶系統(tǒng)相比，具有穿透力強(qiáng)、功耗低、抗多徑效果好、安全性高、系統(tǒng)復(fù)雜度低、能提供精確定位精度等優(yōu)點(diǎn)。因此，超寬帶技術(shù)可以應(yīng)用于室內(nèi)靜止或者移動物體以及人

9、的定位跟蹤與導(dǎo)航，且能提供十分精確的定位精度。 Wi-Fi技術(shù)。無線局域網(wǎng)絡(luò)(WLAN)是一種全新的信息獲取平臺，可以在廣泛的應(yīng)用領(lǐng)域內(nèi)實(shí)現(xiàn)復(fù)雜的大范圍定位、監(jiān)測和追蹤任務(wù)，而網(wǎng)絡(luò)節(jié)點(diǎn)自身定位是大多數(shù)應(yīng)用的基礎(chǔ)和前提。當(dāng)前比較流行的Wi-Fi定位是無線局域網(wǎng)絡(luò)系列標(biāo)準(zhǔn)之IEEE802.11的一種定位解決方案。該系統(tǒng)采用經(jīng)驗(yàn)測試和信號傳播模型相結(jié)合的方式，易于安裝，需要很少基站，能采用相同的底層無線網(wǎng)絡(luò)結(jié)構(gòu)，系統(tǒng)總精度高。芬蘭的Ekahau公司開發(fā)了能夠利用Wi-Fi進(jìn)行室內(nèi)定位的軟件。Wi-Fi繪圖的精確度大約在1米至20米的范圍內(nèi)，總體而言，它比蜂窩網(wǎng)絡(luò)三角測量定位方法更精確。但是，如果定位

10、的測算僅僅依賴于哪個Wi-Fi的接入點(diǎn)最近，而不是依賴于合成的信號強(qiáng)度圖，那么在樓層定位上很容易出錯。目前，它應(yīng)用于小范圍的室內(nèi)定位，成本較低。但無論是用于室內(nèi)還是室外定位，Wi-Fi收發(fā)器都只能覆蓋半徑90米以內(nèi)的區(qū)域，而且很容易受到其他信號的干擾，從而影響其精度，定位器的能耗也較高。ZigBee技術(shù)。ZigBee是一種新興的短距離、低速率無線網(wǎng)絡(luò)技術(shù)，它介于射頻識別和藍(lán)牙之間，也可以用于室內(nèi)定位。它有自己的無線電標(biāo)準(zhǔn)，在數(shù)千個微小的傳感器之間相互協(xié)調(diào)通信以實(shí)現(xiàn)定位。這些傳感器只需要很少的能量，以接力的方式通過無線電波將數(shù)據(jù)從一個傳感器傳到另一個傳感器，所以它們的通信效率非常高。ZigBee

11、最顯著的技術(shù)特點(diǎn)是它的低功耗和低成本。除了以上提及的定位技術(shù)，還有基于計算機(jī)視覺、光跟蹤定位、基于圖像分析、磁場以及信標(biāo)定位等。此外，還有基于圖像分析的定位技術(shù)、信標(biāo)定位、三角定位等。目前很多技術(shù)還處于研究試驗(yàn)階段，如基于磁場壓力感應(yīng)進(jìn)行定位的技術(shù)。三. 定位算法傳感器節(jié)點(diǎn)的定位算法根據(jù)定位過程中所需信息的不同可分為兩大類： 基于測距(rangebased) 測距無關(guān)(rangefree)測距無關(guān)(rangefree)無需確定距離和角度信息，僅根據(jù)網(wǎng)絡(luò)對通性等信息加以實(shí)現(xiàn)。主要算法有：1. 質(zhì)心算法;2. APIT(approximate point-in-triangulation teat

12、) 近似三角形內(nèi)點(diǎn)測試法3. DV-Hop基于測距(rangebased)測量節(jié)點(diǎn)問點(diǎn)到點(diǎn)的距離或角度信息，使用三邊測量法、三角測量法或最大似然估計法計算節(jié)點(diǎn)位置。主要算法有：TOA(time of arrival)TDOA(Time Difference 0f Arrival)AOA(Angle of Arrival )RSSI(Received Signal Strength Indication)RSSI (Radio Signal Strength Indicator)無線電信號強(qiáng)度，又稱RSSI(Radio Signal Strength Indicator)。已知發(fā)射功率，接受節(jié)點(diǎn)

13、通過接收功率，計算傳播損耗，再通過理論或者經(jīng)驗(yàn)的傳播模型將傳播損耗轉(zhuǎn)換為距離。在自由空間中，距發(fā)射d處的天線接收到的信號強(qiáng)度由下面的公式(1)給出:（1）式中，d為接收端與發(fā)射端之間的距離( m)；d0為參考距離( m)，一般取1 m；Pr(d)是接收端的接收信號功率(dBm)；Pr(d0)是參考距離d0點(diǎn)對應(yīng)的接收信號功率(dBm)； XdBm是一個平均值為0的高斯隨機(jī)變量(dBm)，反映了當(dāng)距離一定時，接收信號功率的變化； n為路徑損耗指數(shù)，是一個與環(huán)境相關(guān)的值。通過測量接收信號的強(qiáng)度，利用這個公式即可計算收發(fā)節(jié)點(diǎn)之間的大概距離31。一旦可以得到參考節(jié)點(diǎn)與未知節(jié)點(diǎn)之間的距離信息，就可以采用

14、三邊測量法或者最大似然估計法計算出未知節(jié)點(diǎn)的位置。在三維空間中，三邊測量法指的己知一個未知節(jié)點(diǎn)到三個以上參考節(jié)點(diǎn)的距離，就可以確定該點(diǎn)的坐標(biāo);三邊測量法在二維空間里可以用幾何圖形表示為:當(dāng)?shù)玫轿粗?jié)點(diǎn)到一個參考節(jié)點(diǎn)的距離時，就可以確定，此未知節(jié)點(diǎn)在以此參考節(jié)點(diǎn)為圓心，以距離為半徑的圓上;如果得到未知節(jié)點(diǎn)到3個參考節(jié)點(diǎn)的距離，則3個圓的交點(diǎn)就是該未知節(jié)點(diǎn)的位置。n的幾種典型值環(huán)境n戶外自由空間2遮蔽的城市空間2.75室內(nèi)視距1.61.8有阻擋障礙的空間46RSSI值采集由于無線信號的非線性時變特性,在同一個點(diǎn)不同時刻采集到的信號強(qiáng)度值是不同的，并且無法判斷哪一個值較為準(zhǔn)確。在距離發(fā)射端1m遠(yuǎn)處的

15、接受端采集100次信號，對結(jié)果進(jìn)行分析，見圖1。圖1 在距離發(fā)射端1m處的接受端采集100個RRSI值的結(jié)果比較由圖1可見，即使在同一點(diǎn)，采集到的RSSI值也有很大的不同。但基本都在一個范圍內(nèi)波動。由于采集信號的隨機(jī)性，采集的RSSI參數(shù)并不能直接用于運(yùn)算，需要對其進(jìn)行處理。方法有：1. 均值法2. 高斯分布法節(jié)點(diǎn)定位計算方法（可以參考的算法）1) 最小二乘法用最小二乘法來估算節(jié)點(diǎn)位置坐標(biāo)也是無線定位中一種經(jīng)常采用的方法。最小二乘法的突出優(yōu)點(diǎn)是只需要一個假定的信號傳播模型和信號觀測值，計算簡單，易于實(shí)現(xiàn)。已知1，2，3等n個節(jié)點(diǎn)的坐標(biāo)分別為(x1，y1)，(x2，y2)，(x3，y3)(xn，

16、yn)，它們到節(jié)點(diǎn)D的距離分別為d1，d2，d3···dn，假設(shè)節(jié)點(diǎn)D的坐標(biāo)為(x，y)。從第一行開始分別減去最后一行，得：使用最小二乘法得：這里的向量X就是移動節(jié)點(diǎn)的坐標(biāo)。2）三角質(zhì)心法 在圓周定位模型中，三角質(zhì)心法是一種較易實(shí)現(xiàn)、便于理解的算法。三角質(zhì)心法的原理如下：在圓周定位模型中，理論上如果知道移動節(jié)點(diǎn)到三個信標(biāo)節(jié)點(diǎn)的物理距離，用這三個信標(biāo)節(jié)點(diǎn)做三個圓的圓心，到移動節(jié)點(diǎn)的物理距離為半徑，畫三個圓，這三個圓與移動節(jié)點(diǎn)都應(yīng)該是相交的，即三個圓的公共交點(diǎn)就是移動節(jié)點(diǎn)MS的位置。但在實(shí)際中，由于噪聲的影響，信號遇到障礙物以后的急劇衰落，測量工具帶來的誤差等原因，在

17、圓周模型中的三個圓是不可能相交于一點(diǎn)的。由于在室內(nèi)環(huán)境下，周圍的障礙物等對電磁波信號的吸收，一般使得接收機(jī)接收到的信號強(qiáng)度值會小于預(yù)計的信號強(qiáng)度值，反映到推導(dǎo)出來的移動節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)的估計距離上，結(jié)果就是所畫的三個圓的半徑都偏大。這一種情況應(yīng)該算是最為常見的情況，如下圖2所示：圖2中畫出來的三個圓一共有三個交點(diǎn)，形成一個三角形區(qū)域。所求的移動節(jié)點(diǎn)MS的位置就在這三個圓的公共交集區(qū)域內(nèi)。通過取三角形的質(zhì)心，作為移動節(jié)點(diǎn)MS的估計位置。圖2 基于圓周模型的三角質(zhì)心法3）加權(quán)三角質(zhì)心算法通過對無線電傳播路徑損耗模型的分析, 可以發(fā)現(xiàn)利用普通質(zhì)心算法, 沒有反映出信標(biāo)節(jié)點(diǎn)對節(jié)點(diǎn)位置的影響力的大小, 影

18、響了定位精度. 文中設(shè)計了加權(quán)質(zhì)心算法, 它的基本思想是: 在質(zhì)心算法中, 通過加權(quán)因子來體現(xiàn)信標(biāo)節(jié)點(diǎn)對質(zhì)心坐標(biāo)決定權(quán)的大小, 利用加權(quán)因子體現(xiàn)各信標(biāo)節(jié)點(diǎn)對質(zhì)心位置的影響程度, 反映它們之間的內(nèi)在關(guān)系. 通過下式中的加權(quán)因子來體現(xiàn)這種約束力。4）加權(quán)質(zhì)心算法普通的質(zhì)心算法同上面所描述的三角質(zhì)心算法有所不同，它不需要知道未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的距離。加權(quán)質(zhì)心算法就是質(zhì)心算法的基礎(chǔ)上加上一個權(quán)值，提高定位精度。公式如下：其中， 為未知節(jié)點(diǎn)估計位置的坐標(biāo)， 為錨節(jié)點(diǎn)j的坐標(biāo)，為權(quán)值。為未知節(jié)點(diǎn)i與錨節(jié)點(diǎn)之間的距離，g是一個可以根據(jù)實(shí)際環(huán)境進(jìn)行調(diào)節(jié)的參數(shù)。5）改進(jìn)的加權(quán)質(zhì)心算法此方法對上面的 的表達(dá)式進(jìn)行了改進(jìn)。如圖所示，RNi (i=19)是任意放置的錨節(jié)點(diǎn)。未知節(jié)點(diǎn)j能夠接收到RNm(m=14)的數(shù)據(jù)包。我們把其中一個接收信號強(qiáng)度最大的錨節(jié)點(diǎn)定義為RNmax，其信號強(qiáng)度為Pmaxj(d)，再將它與其他信號進(jìn)行相減，得可見光Lifi通信定義：可見光無線通信（