普適環(huán)境下基于區(qū)間值模糊理論的指紋定位算法

錢夢(mèng)竹,楊新凱

(上海師范大學(xué) 信息與機(jī)電工程學(xué)院,上海 200234)

1 背景簡(jiǎn)介

自Weiser[1-3]于1991年首次提出了一個(gè)新的計(jì)算時(shí)代——普適計(jì)算時(shí)代,到目前,有關(guān)普適計(jì)算的研究也越來越多,它最主要的特點(diǎn)就是將計(jì)算變成了以人為中心,而不是以計(jì)算機(jī)為中心的計(jì)算,將傳統(tǒng)的計(jì)算設(shè)備溶入生活中,即計(jì)算機(jī)既對(duì)人們“隱身”而又“無處不在”.用戶和計(jì)算機(jī)之間將以一種很自然的方式進(jìn)行交流.當(dāng)然,這也就使得普適計(jì)算成為現(xiàn)今乃至未來計(jì)算的主流.

普適計(jì)算針對(duì)的主要數(shù)據(jù)對(duì)象是上下文信息,上下文[4]就是能用來描述實(shí)體狀態(tài)的信息,它可以是人、時(shí)間、位置或者它們之間的相互關(guān)系等.其中位置上下文是非常重要的一類上下文信息,它是連接虛擬和現(xiàn)實(shí)世界的橋梁[5].因此,定位系統(tǒng)的研究也就成了普適計(jì)算的重要研究課題之一.定位可定義為是一種確定實(shí)體之間位置關(guān)系的機(jī)制.而定位系統(tǒng)就是通過相關(guān)的設(shè)備獲取系統(tǒng)的空間方位屬性,然后運(yùn)用一些算法確定位置信息.而本文作者主要研究的是普適計(jì)算環(huán)境下室內(nèi)無線定位[6]技術(shù),它主要是依據(jù)接收到的無線電信號(hào)的時(shí)間、強(qiáng)度、相位等參數(shù),通過一定的算法來計(jì)算移動(dòng)用戶的位置.

2 普適環(huán)境下的室內(nèi)定位系統(tǒng)簡(jiǎn)介

目前,普適計(jì)算環(huán)境下的室內(nèi)定位系統(tǒng)種類繁多并且差異很大,但其一般的框架是相同的,可大體分為信號(hào)測(cè)量、位置估算和位置求精這3個(gè)階段.

2.1 信號(hào)測(cè)量階段

第一個(gè)階段是信號(hào)測(cè)量階段,首先通過一些信號(hào)媒體測(cè)出未知節(jié)點(diǎn)與參考點(diǎn)之間的距離或角度關(guān)系,進(jìn)而估算兩節(jié)點(diǎn)之間的直線距離.目前的信號(hào)測(cè)量技術(shù)主要有4種,分別是TOA、TDOA、AOA、RSSI,前3種技術(shù)對(duì)設(shè)備的要求都比較高,像TOA是通過測(cè)量?jī)牲c(diǎn)之間的傳播時(shí)間來確定距離,那么就會(huì)產(chǎn)生時(shí)鐘同步誤差和傳播不均的誤差,對(duì)精度影響較大.TDOA雖然消除了DOA產(chǎn)生的誤差,但是仍對(duì)時(shí)鐘同步的要求很高.AOA的定位精度則會(huì)受天線測(cè)角精度影響.而RSSI技術(shù)利用信號(hào)衰減原理.通過檢測(cè)信號(hào)接收端的接收功率,得到傳播耗損模型,計(jì)算節(jié)點(diǎn)間的距離.由于是利用無線網(wǎng)絡(luò)技術(shù),因此成本較低,所以本文作者選用在WiFi環(huán)境下測(cè)量RSSI值(Received Signal Strength Indicator)的方法來進(jìn)行信號(hào)測(cè)量,確定待測(cè)定節(jié)點(diǎn)的坐標(biāo)[7].

2.2 位置估算階段

第2個(gè)階段是位置估算階段,知道了未知節(jié)點(diǎn)到3個(gè)(或3個(gè)以上)參考點(diǎn)的距離,就可以用定位估算的方法來確定未知節(jié)點(diǎn)的坐標(biāo).一般在三維空間中,需要知道到4個(gè)參考點(diǎn)的距離[8],例如全球定位系統(tǒng)(GPS),但是在普適計(jì)算的環(huán)境下,坐標(biāo)系大多是二維空間,只需要知道到3個(gè)參考點(diǎn)的距離就可以確定定位點(diǎn)的坐標(biāo).位置估算的方法主要分為3種:三邊測(cè)量法、場(chǎng)景分析和附近定位.

2.3 位置求精階段

第3個(gè)階段是位置求精階段,也是作者重點(diǎn)研究的階段,本階段要對(duì)求得的節(jié)點(diǎn)坐標(biāo)進(jìn)行位置求精,盡可能地減少誤差,提高定位精度.該階段的算法種類很多,由于WiFi具有部署方便、高速的特點(diǎn),并且目前在筆記本電腦、手機(jī)等通信設(shè)備上都得到廣泛應(yīng)用.由于基于WiFi的室內(nèi)定位算法具有數(shù)據(jù)高維的特性、信號(hào)本身的不穩(wěn)定性、測(cè)量本身的誤差，使得定位過程中所使用的數(shù)據(jù)沒有固定的屬性,也就是說具有模糊性,因此對(duì)該過程中的模糊性進(jìn)行探究,引入?yún)^(qū)間值模糊理論,在原有的基于WiFi的指紋定位算法[9]的基礎(chǔ)上,提出了一種基于區(qū)間值模糊理論的指紋定位算法.

3 基于區(qū)間值模糊理論的指紋定位算法

WiFi無線局域網(wǎng)技術(shù)從20世紀(jì)末開始發(fā)展,目前應(yīng)用最廣泛的是IEEE 802.11系列技術(shù)標(biāo)準(zhǔn).基于WiFi的室內(nèi)定位系統(tǒng)主要包括3個(gè)部分:終端無線網(wǎng)卡、位置固定的WiFi熱點(diǎn)和定位平臺(tái).本系統(tǒng)采用基于信號(hào)強(qiáng)度的指紋定位技術(shù).在算法實(shí)施上分為離線和在線兩個(gè)階段:離線階段基于區(qū)間值模糊理論建立模糊指紋庫(kù);在線階段對(duì)客戶端進(jìn)行實(shí)時(shí)模糊決策定位.其一般模型如圖1所示.

圖1 基于WiFi的室內(nèi)定位離線建庫(kù)階段原理圖

3.1 模糊指紋庫(kù)的建立

首先,將整個(gè)區(qū)域劃分網(wǎng)格(正方形),它們的的位置用xOy坐標(biāo)軸在數(shù)據(jù)庫(kù)中標(biāo)定,把固定的節(jié)點(diǎn)安裝在已知的坐標(biāo)上,然后在每個(gè)網(wǎng)格中收集RSSI值并與它的坐標(biāo)一起存入數(shù)據(jù)庫(kù).這個(gè)階段是非常費(fèi)時(shí)的.

為了算法的精確,至少需要設(shè)置3個(gè)固定節(jié)點(diǎn)(作者選取了4個(gè)固定節(jié)點(diǎn))并且以相同的方法計(jì)算指紋(三邊測(cè)量法),移動(dòng)終端與固定節(jié)點(diǎn)之間的距離是已知的,由無線電傳播模型計(jì)算得到[10].

將離線階段4個(gè)固定節(jié)點(diǎn)測(cè)得的每一個(gè)參考點(diǎn)的RSSI值,記為xi(1≤xi≤n),n為定位區(qū)域內(nèi)設(shè)置參考點(diǎn)的數(shù)目,即xi=(R1i,R2i,R3i,R4i)，其中xi為樣本點(diǎn),R為測(cè)得的RSSI值,設(shè)指紋庫(kù)的樣本空間為X={x1,x2,…,xn},注意一個(gè)樣本點(diǎn)不能被嚴(yán)格地劃分給某一個(gè)區(qū)間,定義樣本點(diǎn)xi屬于第j個(gè)區(qū)間的程度為xij(0≤xij≤1),其中xij為模糊隸屬度,1≤j≤c,c為模糊區(qū)間數(shù),樣本空間X的模糊區(qū)間用模糊矩陣W=(wij)表示,其中wij為矩陣W的第i行第j列元素,代表第i個(gè)樣本點(diǎn)隸屬于第j個(gè)區(qū)間的隸屬度.W具有以下性質(zhì):

wijwij∈[0,1] ，

(1)

(2)

(3)

(4)

定義目標(biāo)函數(shù)為Jλ(w,z),則:

(5)

(6)

(7)

式中,λ為模糊指數(shù),λ>1,zj表示第j個(gè)區(qū)間的區(qū)間中心,式(6)表示樣本點(diǎn)xi到區(qū)間中心zj的線距離.模糊區(qū)間的劃分計(jì)算目標(biāo)函數(shù)在(1)～(3)式的約束條件下的最小值.其流程圖如圖2所示.

圖2 確定模糊區(qū)間的算法流程

通過圖2的迭代過程,可以完成對(duì)于離線階段采集的RSSI值的模糊區(qū)間的劃分:共分為n個(gè)區(qū)間,每個(gè)區(qū)間中都有k(1≤k≤n)個(gè)樣本值,且第j個(gè)區(qū)間中心為zj.這n個(gè)區(qū)間的數(shù)據(jù)一起構(gòu)成了本定位系統(tǒng)的模糊指紋庫(kù).該指紋庫(kù)詳細(xì)描述了特定環(huán)境中無線信號(hào)的RSSI值與空間位置之間的對(duì)應(yīng)關(guān)系并存儲(chǔ)在中心服務(wù)器中.

3.2 模糊決策定位

該階段定位系統(tǒng)開始監(jiān)控移動(dòng)設(shè)備并收集RSSI指紋.進(jìn)行匹配指紋,并儲(chǔ)存下RSSI的值.如果獲得的測(cè)量值與存儲(chǔ)的指紋相匹配,就實(shí)現(xiàn)了定位.本算法計(jì)算的是最鄰近的數(shù)值,如果對(duì)應(yīng)的坐標(biāo)有兩個(gè),那么就用兩坐標(biāo)的平均值來表示.把指紋匹配問題類比于模糊決策的問題,并運(yùn)用模糊決策理論進(jìn)行建模,來獲得更為準(zhǔn)確的定位結(jié)果,并且增強(qiáng)了室內(nèi)定位系統(tǒng)的抗干擾能力.

在線階段,首先進(jìn)行區(qū)間的匹配,將測(cè)得的移動(dòng)端的4組RSSI值記為xm(m≥1的整數(shù),x表示第m個(gè)移動(dòng)客戶端),即xm={r1m,r2m,r3m，r4m},其中r表示在線階段測(cè)得的RSSI值.通過計(jì)算得到的xm和數(shù)據(jù)庫(kù)中c個(gè)區(qū)間的模糊隸屬度,然后,選取最大模糊隸屬度所對(duì)應(yīng)的第j個(gè)區(qū)間,并在此區(qū)間中進(jìn)行模糊決策,實(shí)現(xiàn)移動(dòng)客戶端位置的確定.

分別計(jì)算實(shí)際測(cè)量得到的xm中的4個(gè)數(shù)值,以及指紋庫(kù)第j個(gè)區(qū)間個(gè)參考值xi中對(duì)應(yīng)的4個(gè)數(shù)值之間的歐式距離vpq,vpq為因素指標(biāo)值,即

vpq=|rlm-Rli|,l=1,2,3,4 .

(8)

把計(jì)算所得的所有因素指標(biāo)值構(gòu)成如下的因素指標(biāo)矩陣:

(9)

計(jì)算相對(duì)偏差值μpq,即

(10)

(11)

根據(jù)具體的情況設(shè)定一個(gè)門限值θ,令

(12)

選取dp≤θ時(shí)的K個(gè)值所對(duì)應(yīng)的參考點(diǎn),然后,根據(jù)式(13)計(jì)算其對(duì)應(yīng)坐標(biāo)的平均值,作為移動(dòng)客戶端的估算位置:

(13)

設(shè)移動(dòng)客戶端的實(shí)際位置坐標(biāo)為(x′,y′)和估算位置坐標(biāo)(x,y)之間的距離為其定位誤差,用Δ表示:

(14)

Δ的大小可以評(píng)估定位系統(tǒng)的性能,Δ的值越小,則說明系統(tǒng)的性能越好.

4 實(shí) 驗(yàn)

在一個(gè)300 m2的樓層的4個(gè)位置固定上4個(gè)無線接入點(diǎn)(AP,Access Point),采用IEEE 802.11標(biāo)準(zhǔn)的移動(dòng)設(shè)備,構(gòu)建一個(gè)基于區(qū)間值模糊理論的WiFi室內(nèi)定位系統(tǒng)實(shí)驗(yàn)平臺(tái).

圖3是樓層的結(jié)構(gòu)圖,黑色的虛線表示實(shí)驗(yàn)路徑,黑點(diǎn)表示參考點(diǎn),間隔大約為5 m,用模糊理論的方法建立指紋庫(kù);移動(dòng)端沿著實(shí)驗(yàn)路徑約1 m/s的速度收集AP的RSSI值,進(jìn)行WiFi定位,如圖3所示.

通過圖4和圖5的對(duì)比,可以看出加入了區(qū)間值模糊理論,定位路徑更加接近真實(shí)的實(shí)驗(yàn)路徑,定位精度提高了很多.

圖3 試驗(yàn)路徑圖

圖4 傳統(tǒng)的指紋定位圖

圖5 基于區(qū)間值模糊理論的指紋定位圖

5 結(jié)束語

在普適計(jì)算的環(huán)境下,本文作者提出了一種基于區(qū)間值模糊理論的高精度、低開銷的實(shí)時(shí)指紋定位算法.該算法選取無線環(huán)境(WiFi)下的RSSI值作為參數(shù),分兩個(gè)階段來實(shí)現(xiàn)室內(nèi)定位:離線模糊建庫(kù)階段和在線實(shí)時(shí)模糊決策階段來實(shí)現(xiàn)對(duì)移動(dòng)客戶端位置的確定.并通過對(duì)比發(fā)現(xiàn),該算法具有更高的定位精度和可靠性,為普適計(jì)算環(huán)境下的各類研究提供更為精確的位置上下文信息.

參考文獻(xiàn):

[1] WEISER M.The computer for the twenty first century[J].Scientific American,1991,265(3):94-104.

[2] WEISER M.Some computer science issues in ubiquitous computing[J].Communications of the ACM,1993,36(7):74-78.

[3] WEISER M.Hot topics-ubiquitous computing[J].IEEE computer,1993,26(10):71-72.

[4] WEI L,XUE L,DAO L H.A survey on context awareness[C].Computer science and Science system(CSSS) International Conference,Nanjing:IEEE,2011.

[5] ESTRIN D,CULLER D,PRISTER K,et al.Connecting the physical world with pervasive network[J].Pervasive Computing,2002,1(11):59-69.

[6] 付維權(quán),孫志仁,曹奇英. 普適計(jì)算及其定位感知系統(tǒng)[J].計(jì)算機(jī)工程與設(shè)計(jì),2004,25(7):1200-1203.

[7] ABOODI A,WAN T.Evalution of WiFi-based indoor(WBI) positioning algorithm[C].Moblie Ubiquitous and Interlligent Computing(MUSIC) Third FTRA International Conference,Vancouver BC:IEEE,2012.

[8] HIGHTOWER J,BORRIELLO G,WANT R.Spot ON:An Indoor 3D location sensing technology based on RF singal strenghth[R].Techical Report UW CSE Seattle WA,USA:University of Washington,2000:1-16.

[9] SABHAN F,HASBULLAH H,et al.Tndoor positioning inBluetooth networks using fingerprinting and lateration approach[C].International Conference on Information Science and Applications International Conference,Jeju Island:IEEE,2011.

[10] LIU H,DARABI H,BANERJEE P,et al.Survey of wireless indoor positioning techniques and systems[J].IEEE Transcations on System Man and Cybernetics Part C:Applications and Reviews,2007,37(6):1067-1080.