[發(fā)明專利]一種基于非現(xiàn)場勘測的無線室內(nèi)定位方法

有效

• 申請?zhí)枺?/td>: 201210181296.2
• 申請日: 2012-06-04
• 公開（公告）號: CN102724751A
• 公開（公告）日: 2012-10-10
• 發(fā)明（設(shè)計）人: 吳陳沭;趙弋洋;楊錚;劉云浩
• 申請（專利權(quán)）人: 清華大學
• 主分類號: H04W64/00
• 分類號: H04W64/00
• 代理公司: 北京清亦華知識產(chǎn)權(quán)代理事務所(普通合伙) 11201
• 代理人: 羅文群

1.一種基于非現(xiàn)場勘測的無線室內(nèi)定位方法，其特征在于該方法包括以下各步驟：

（1）通過手機采集無線網(wǎng)絡的信號以及手機中的加速度傳感器和方向傳感器的讀數(shù)，組成一個指紋數(shù)據(jù)集：D＝{F，S}，其中F為采集的無線信號，F(xiàn)＝[f₁，f₂，f₃，......，f_n]，f_i表示無線網(wǎng)絡中第i個無線接入點的信號強度值，S為手機中的加速度傳感器和方向傳感器的讀數(shù)，i＝1,2,3，......，n，n為無線網(wǎng)絡中無線接入點的個數(shù)；

（2）設(shè)指紋數(shù)據(jù)集中的任意兩條無線信號分別為：F＝[f₁，f₂，f₃，......，f_n]和F’＝[f’₁，f’2，f’3，...，f’n]，兩個無線信號之間的區(qū)分度用無線信號強度的二階差分值表示為：

φ(F,F′)=Σi=1n(ω(fi)-ω(f′i))2]]>

ω(fi)=Σj=1nI(fi-fj>0)(fi-fj)]]>

其中，I為指示型函數(shù)；

（3）根據(jù)步驟（2）中的二階差分值，采用K平均聚類方法將指紋數(shù)據(jù)集中的無線信號劃分為N類，即N個虛擬房間從K平均聚類結(jié)果中得到每個虛擬房間R的平均指紋F[R]和指紋閾值ξ，其中平均指紋F[R]為虛擬房間R所包含的所有無線信號指紋的平均值，指紋閾值ξ為該虛擬房間R所包含的所有無線信號中與平均指紋F[R]的最大的二階差分值，

（4）構(gòu)建一個邏輯平面圖G＝(V，E)，使邏輯平面圖G＝(V，E)中的每一個頂點R₁∈V代表一個虛擬房間，每一條邊e＝(R₁，R₂)∈E表示虛擬房間R₁與R₂相連通，構(gòu)建過程包括如下步驟：

（4-1）根據(jù)步驟（1）中的連續(xù)采集的傳感器讀數(shù)A，形成手機在移動過程中的連續(xù)移動軌跡，移動軌跡上的無線信號強度依次記為與該連續(xù)無線信號強度相對應的步驟（3）的多個相連續(xù)的虛擬房間記為

（4-2）根據(jù)步驟(4-1)中的連續(xù)虛擬房間序列將每個虛擬房間簡化為一個點，在任意兩個相鄰的虛擬房間R_i、R_i+1之間連接出一條邊；

（4-3）遍歷步驟（1）的指紋數(shù)據(jù)集中的所有連續(xù)采集的傳感器讀數(shù)，重復步驟（4-1）和（4-2），得到邏輯平面圖G＝(V，E)；

（5）將上述邏輯平面圖映射到需無線室內(nèi)定位區(qū)域的實際平面圖，得到邏輯平面圖中每一個頂點與實際平面圖的對應關(guān)系，即指紋-位置關(guān)系數(shù)據(jù)庫，包括如下步驟：

（5-1）將需無線室內(nèi)定位區(qū)域的實際平面圖簡化為一個無向圖G′＝(V′，E′)，其中每個頂點A₁∈V′代表需無線室內(nèi)定位區(qū)域的實際平面圖中的一個功能區(qū)域，每條邊e＝(A₁，A₂)∈E′表示兩個功能區(qū)域A₁和A₂相連通；

（5-2）根據(jù)介數(shù)中心性，建立上述邏輯平面圖G＝(V，E)和實際平面圖G′＝(V′，E′)中居于中心的頂點的相互映射關(guān)系，邏輯平面圖G＝(V，E)中頂點R的介數(shù)中心性C_b(R)為：

Cb(R)=Σs≠t≠R∈Vσst(R)σst]]>

其中，σ_st為邏輯平面圖G＝(V，E)中頂點s到頂點t的最短路徑數(shù)，σ_st(R)為穿過頂點R的頂點s到頂點t的最短路徑數(shù)，按介數(shù)中心性從大到小排列得到邏輯平面圖G＝(V，E)的中心頂點序列{r₁，r₂，......，r_k}；

實際平面圖G′＝(V′，E′)中頂點A的介數(shù)中心性C_b(A)為：

Cb(A)=Σs≠t≠A∈V′σuv(A)σuv]]>

其中，σ_uv為實際平面圖G′＝(V′，E′)中頂點u到頂點v的最短路徑數(shù)，σ_uv(A)為穿過頂點A的頂點u到頂點v的最短路徑數(shù)，按介數(shù)中心性從大到小排列得到實際平面圖G′＝(V′，E′)的中心頂點序列{a₁，a₂，......，a_k}；

將上述中心頂點序列{r₁，r₂，......，r_k}與中心頂點序列{a₁，a₂，......，a_k}按照序號一一對應，得到邏輯平面圖G＝(V，E)和實際平面圖G′＝(V′，E′)的中心頂點的映射關(guān)系；

（5-3）設(shè)邏輯平面圖G＝(V，E)中非中心頂點v到所有其他頂點的最短路徑長度的和為該頂點v的權(quán)值，即：

w(v)＝∑_{u∈V，u≠v}d(v，u)

其中，d(v，u)為頂點v到u的最短路徑長度，重復本步驟，得到邏輯平面圖G＝(V，E)中所有非中心頂點的權(quán)值；

實際平面圖G′＝(V′，E′)中非中心頂點v′到所有其他頂點的最短路徑長度的和為該頂點v′的權(quán)值，即：

w(v′)＝∑_{u′∈V，u′≠v′}d(v′，u′)

其中，d(v′，u′)為頂點v′到u′的最短路徑長度，重復本步驟，得到實際平面圖G′＝(V′，E′)中所有非中心頂點的權(quán)值；

根據(jù)上述得到的所有非中心頂點的權(quán)值，利用KM算法求解帶權(quán)最小二分圖匹配模型，使得所有匹配頂點之間的權(quán)值之差最小，即使得W＝∑_v∈V|w(v)-w(v′)|最小，其中v′為v的映射，得到邏輯平面圖和實際平面圖中的非中心頂點的映射關(guān)系；

（5-4）根據(jù)步驟（5-2）和（5-3）中得到的映射關(guān)系，實施以下步驟加以糾正：

設(shè)邏輯平面圖G＝(V，E)中頂點p被映射到實際平面圖G′＝(V′，E′)中的頂點p′，定義頂點v的鄰居集合N_G(p)為邏輯平面圖G＝(V，E)中與頂點p直接相連的頂點集合，定義頂點p′的鄰居集合N_G′(p′)為實際平面圖G′＝(V′，E′)中與頂點p′直接相連的頂點集合，設(shè)N′_G(p)為與頂點p的鄰居集合N_G(p)中的所有節(jié)點相映射的實際平面圖G′＝(V′，E′)中的節(jié)點集合，若N′_G(p)與N_G′(p′)中的相同節(jié)點數(shù)少于N_G(p)所包含節(jié)點數(shù)的一半，則判定p到p′的映射不正確；遍歷實際平面圖G′＝(V′，E′)除p′以外的所有頂點，尋找新頂點q，使得N′_G(p)與q的鄰居集合N_G′(q)的相同頂點數(shù)最多，并確定頂點q與頂點p的映射關(guān)系；

（5-5）重復步驟（5-4），得到邏輯平面圖G＝(V，E)與實際平面圖G′＝(V′，E′)之間的映射關(guān)系；

（6）根據(jù)步驟（5）得到的指紋-位置關(guān)系數(shù)據(jù)庫，實現(xiàn)對用戶的定位，包括以下步驟：

（6-1）根據(jù)用戶提交的無線信號為F，若存在滿足以下條件的虛擬房間R：

與

φ(F,F[R])<ξ]]>

其中為步驟（2）中定義的二階差分值，R_i為任意一個虛擬房間，為步驟（3）中的虛擬房間集合，F(xiàn)[R]為虛擬房間R的平均信號強度，ξ為步驟（2）中的與虛擬房間R對應的信號強度閾值，則判定用戶所在虛擬房間為R；

（6-2）根據(jù)上述判定的用戶所在虛擬房間R，檢索步驟（5）中指紋位置數(shù)據(jù)庫，得到與上述虛擬房間R所對應的實際平面圖中的功能區(qū)域，即為用戶所在的位置。