普適環境下基于區間值模糊理論的指紋定位算法

錢夢竹,楊新凱

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

1 背景簡介

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

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

2 普適環境下的室內定位系統簡介

目前,普適計算環境下的室內定位系統種類繁多并且差異很大,但其一般的框架是相同的,可大體分為信號測量、位置估算和位置求精這3個階段.

2.1 信號測量階段

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

2.2 位置估算階段

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

2.3 位置求精階段

第3個階段是位置求精階段,也是作者重點研究的階段,本階段要對求得的節點坐標進行位置求精,盡可能地減少誤差,提高定位精度.該階段的算法種類很多,由于WiFi具有部署方便、高速的特點,并且目前在筆記本電腦、手機等通信設備上都得到廣泛應用.由于基于WiFi的室內定位算法具有數據高維的特性、信號本身的不穩定性、測量本身的誤差，使得定位過程中所使用的數據沒有固定的屬性,也就是說具有模糊性,因此對該過程中的模糊性進行探究,引入區間值模糊理論,在原有的基于WiFi的指紋定位算法[9]的基礎上,提出了一種基于區間值模糊理論的指紋定位算法.

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

WiFi無線局域網技術從20世紀末開始發展,目前應用最廣泛的是IEEE 802.11系列技術標準.基于WiFi的室內定位系統主要包括3個部分:終端無線網卡、位置固定的WiFi熱點和定位平臺.本系統采用基于信號強度的指紋定位技術.在算法實施上分為離線和在線兩個階段:離線階段基于區間值模糊理論建立模糊指紋庫;在線階段對客戶端進行實時模糊決策定位.其一般模型如圖1所示.

圖1 基于WiFi的室內定位離線建庫階段原理圖

3.1 模糊指紋庫的建立

首先,將整個區域劃分網格(正方形),它們的的位置用xOy坐標軸在數據庫中標定,把固定的節點安裝在已知的坐標上,然后在每個網格中收集RSSI值并與它的坐標一起存入數據庫.這個階段是非常費時的.

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

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

wijwij∈[0,1] ，

(1)

(2)

(3)

(4)

定義目標函數為Jλ(w,z),則:

(5)

(6)

(7)

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

圖2 確定模糊區間的算法流程

通過圖2的迭代過程,可以完成對于離線階段采集的RSSI值的模糊區間的劃分:共分為n個區間,每個區間中都有k(1≤k≤n)個樣本值,且第j個區間中心為zj.這n個區間的數據一起構成了本定位系統的模糊指紋庫.該指紋庫詳細描述了特定環境中無線信號的RSSI值與空間位置之間的對應關系并存儲在中心服務器中.

3.2 模糊決策定位

該階段定位系統開始監控移動設備并收集RSSI指紋.進行匹配指紋,并儲存下RSSI的值.如果獲得的測量值與存儲的指紋相匹配,就實現了定位.本算法計算的是最鄰近的數值,如果對應的坐標有兩個,那么就用兩坐標的平均值來表示.把指紋匹配問題類比于模糊決策的問題,并運用模糊決策理論進行建模,來獲得更為準確的定位結果,并且增強了室內定位系統的抗干擾能力.

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

分別計算實際測量得到的xm中的4個數值,以及指紋庫第j個區間個參考值xi中對應的4個數值之間的歐式距離vpq,vpq為因素指標值,即

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

(8)

把計算所得的所有因素指標值構成如下的因素指標矩陣:

(9)

計算相對偏差值μpq,即

(10)

(11)

根據具體的情況設定一個門限值θ,令

(12)

選取dp≤θ時的K個值所對應的參考點,然后,根據式(13)計算其對應坐標的平均值,作為移動客戶端的估算位置:

(13)

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

(14)

Δ的大小可以評估定位系統的性能,Δ的值越小,則說明系統的性能越好.

4 實 驗

在一個300 m2的樓層的4個位置固定上4個無線接入點(AP,Access Point),采用IEEE 802.11標準的移動設備,構建一個基于區間值模糊理論的WiFi室內定位系統實驗平臺.

圖3是樓層的結構圖,黑色的虛線表示實驗路徑,黑點表示參考點,間隔大約為5 m,用模糊理論的方法建立指紋庫;移動端沿著實驗路徑約1 m/s的速度收集AP的RSSI值,進行WiFi定位,如圖3所示.

通過圖4和圖5的對比,可以看出加入了區間值模糊理論,定位路徑更加接近真實的實驗路徑,定位精度提高了很多.

圖3 試驗路徑圖

圖4 傳統的指紋定位圖

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

5 結束語

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

參考文獻:

[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] 付維權,孫志仁,曹奇英. 普適計算及其定位感知系統[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.