夏穎，秦娟，王艷春，高鑫

（齊齊哈爾大學(xué) 通信與電子工程學(xué)院，黑龍江 齊齊哈爾 161006）

隨著智能手機的普遍使用及無線通信技術(shù)的發(fā)展、基于位置服務(wù)的業(yè)務(wù)需求快速增長，室內(nèi)、外定位導(dǎo)航系統(tǒng)及其應(yīng)用得到了眾多科研工作者的廣泛關(guān)注[1-4]。截止目前，已有眾多的方法應(yīng)用于室內(nèi)、外定位服務(wù)中，比如，基于紅外線、超聲波、射頻和WLAN 等信號識別的室內(nèi)定位系統(tǒng)，以及利用衛(wèi)星信號進行定位導(dǎo)航的北斗衛(wèi)星定位系統(tǒng)、GPS 衛(wèi)星定位系統(tǒng)等。基于WLAN 的室內(nèi)定位系統(tǒng)是利用廣泛覆蓋的無線局域網(wǎng)基礎(chǔ)設(shè)施來進行室內(nèi)移動目標(biāo)位置估計的，系統(tǒng)的傳輸帶寬低、定位精度較高、無需額外增加其他硬件設(shè)備等優(yōu)勢而得到廣泛的應(yīng)用?；赪LAN 的定位技術(shù)，包括離線階段的位置指紋數(shù)據(jù)庫構(gòu)建，及在線階段的RSS 信號采集與位置信息映射。離線指紋數(shù)據(jù)構(gòu)建階段，通過在目標(biāo)區(qū)域內(nèi)選擇若干參考點，通過每個參考點采集到的無線接入點信號強度與其位置坐標(biāo)對應(yīng)關(guān)系，構(gòu)建離線指紋數(shù)據(jù)庫，即Radio Map。在線階段，移動終端實時接收來自各個無線接入點的不同強度RSS 信號，通過合適的映射匹配算法，將采集到的信號解算為指紋庫中的匹配信號，實現(xiàn)用戶位置的估算。

鑒于室內(nèi)無線信號傳播復(fù)雜多變的特點，不同時刻，確定參考點上接收到的來自同一接入點的RSS 信號具有較復(fù)雜的時變特性。為了提高離線階段指紋庫的數(shù)據(jù)精度，離線階段需要對同一參考點采集多個指紋數(shù)據(jù)，進行不同時段、不同設(shè)備的數(shù)據(jù)融合。位置指紋數(shù)據(jù)精確程度直接影響著在線階段的位置估計，因此，如何實現(xiàn)離線階段構(gòu)建的指紋庫在動態(tài)環(huán)境下，能夠具有穩(wěn)定的在線定位精度，是將WLAN 廣泛應(yīng)用于室內(nèi)位置估計的關(guān)鍵。

在眾多關(guān)于提高靜態(tài)指紋數(shù)據(jù)庫在動態(tài)環(huán)境下的定位精度研究中，基于移動終端的志愿感知的構(gòu)建方法[5-6]需要對非友善用戶提交的數(shù)據(jù)進行數(shù)據(jù)剔除，給定位解算增加了額外的開銷?；诎氡O(jiān)督學(xué)習(xí)的指紋數(shù)據(jù)構(gòu)建[7-10]在部分標(biāo)記數(shù)據(jù)基礎(chǔ)上，通過半監(jiān)督學(xué)習(xí)實現(xiàn)未標(biāo)記數(shù)據(jù)的標(biāo)定，很好地利用了多個移動終端充當(dāng)志愿者隨機采集實時RSS 數(shù)據(jù)，既可以有效減少離線階段指紋庫構(gòu)建的時間與人力消耗，還可以有效克服無線信號傳播時變帶來的定位精度下降?；诙嗑S模糊映射AP 優(yōu)化的室內(nèi)定位方法[11-13]，通過多維模糊映射構(gòu)造模糊判定矩陣并計算AP 在線模糊隸屬度，同時結(jié)合KNN 算法完成對目標(biāo)的位置坐標(biāo)估算。上述方法中在使用RSS 信號完成位置估計的同時，對于其多維數(shù)據(jù)具有的流形結(jié)構(gòu)特征，通過提取非線性特征用于輔助定位，進而實現(xiàn)更精確的定位結(jié)果。上述傳統(tǒng)的基于半監(jiān)督學(xué)習(xí)的位置指紋定位方法中，僅保持RSS 數(shù)據(jù)的局部流形結(jié)構(gòu)，在局部結(jié)構(gòu)相似的數(shù)據(jù)間，會產(chǎn)生映射錯誤，直接影響指紋數(shù)據(jù)及定位結(jié)果的準(zhǔn)確性。

本文提出基于標(biāo)簽信息的全局流形對齊定位算法，實現(xiàn)多域間高維數(shù)據(jù)的低維嵌入，在提取低維特征的同時，保持目標(biāo)域幾何結(jié)構(gòu)和流形間的相似性不變。該算法利用離線階段采集的少量有標(biāo)簽的指紋數(shù)據(jù)，結(jié)合眾多移動終端定位區(qū)域采集的實時無標(biāo)簽RSS 數(shù)據(jù)，通過樣本標(biāo)簽信息和局部幾何結(jié)構(gòu)重構(gòu)每個樣本點的特征，實現(xiàn)未標(biāo)記數(shù)據(jù)的位置標(biāo)定，減少離線階段對確定參考點的數(shù)據(jù)采集；在線定位階段，將移動終端采集的高維RSS 數(shù)據(jù)進行位置解算時，保持流形的全局結(jié)構(gòu)。流形對齊目標(biāo)函數(shù)在求解過程中，可以充分挖掘參考點標(biāo)簽數(shù)據(jù)與位置坐標(biāo)的對應(yīng)關(guān)系，將指紋數(shù)據(jù)及位置信息同時投影到共同的標(biāo)簽空間，在計算低維嵌入位置信息的同時獲得樣本標(biāo)簽信息，可以提高位置信息標(biāo)定的準(zhǔn)確性，提升定位性能。

1 基本理論

基于位置指紋的WLAN 室內(nèi)定位過程，在線階段的位置估算，可以歸為分類問題。即通過一定的映射匹配算法，將采集的定位信息劃分到所屬的區(qū)域，進而獲得目標(biāo)的位置信息。流形學(xué)習(xí)作為一種典型的數(shù)據(jù)特征提取方式，可以獲得很好的分類結(jié)果，流形對齊則是流形學(xué)習(xí)算法在多個流形上應(yīng)用的拓展。

1.1 流形對齊算法

流形對齊是通過挖掘不同流形原始空間的幾何結(jié)構(gòu)，將不同的流形投影到同一低維空間，并保持在投影空間的局部或全局幾何結(jié)構(gòu)一致。已知高維流形空間的樣本點x1,x2,…,xn，維數(shù)為D，其中xi?RD，流形對齊的目的就是求得每個樣本點在低維特征空間R d(d?D)中的低維嵌入y1,y2,…,yn，其中yj?Rd。算法的一般步驟為：

（1）構(gòu)建全部樣本點的鄰域點距離矩陣：計算每個樣本點與其他樣本點的歐氏距離，按距離由近及遠(yuǎn)升序排列。采用經(jīng)典k-近鄰方法，為每個樣本點選取k個樣本點組成的集合作為其鄰域。（2）高維流形空間的幾何結(jié)構(gòu)構(gòu)建：其構(gòu)建的準(zhǔn)確性直接影響降維結(jié)果，經(jīng)典的等距特征映射算法（ISOMAP）、局部線性嵌入算法（LLE）、拉普拉斯特征映射算法（LE），分別從流形全局與局部結(jié)構(gòu)角度優(yōu)化非線性降維。（3）低維嵌入：以最大化保持流形內(nèi)在幾何結(jié)構(gòu)的權(quán)值矩陣、相似性矩陣為目標(biāo)，構(gòu)造目標(biāo)函數(shù)，求解特征值、特征向量，將高維空間中的樣本點映射到共同的低維空間。

1.2 基于特征層的流形對齊

假設(shè)待對齊的l個流形X1,X2,…,Xl，其中任意Xk=?R1×D，定義目標(biāo)函數(shù)：

2 基于標(biāo)簽信息的流形全局結(jié)構(gòu)對齊定位算法

上述流形對齊算法，僅對具有線性關(guān)系的流形可以有效保持對齊后的幾何結(jié)構(gòu)?；谖恢弥讣y的室內(nèi)定位算法，在實現(xiàn)不同指紋數(shù)據(jù)更新時，需要實現(xiàn)多流形對齊，其關(guān)鍵在于將每一個數(shù)據(jù)集合找到對應(yīng)的映射。在對移動目標(biāo)采集的指紋信息進行位置匹配映射時，可以借助離線階段構(gòu)建的指紋數(shù)據(jù)庫中標(biāo)簽數(shù)據(jù)，通過標(biāo)簽信息建立待對齊未知域和目標(biāo)域之間的聯(lián)系，利用未知域中測試樣本和目標(biāo)域中參考樣本，預(yù)測未知域中測試樣本數(shù)據(jù)的目標(biāo)域映射。

2.1 算法模型

設(shè)高維流形樣本集X=[x1,x2,… ,xm]?RD×m和Y?Rd×n，兩樣本集可以視為各自流形中的采樣點。假設(shè)X中的樣本點信息全部已知，包括布設(shè)參考點的位置坐標(biāo)及接收的來自各個無線AP 的RRS 信息，坐標(biāo)信息簡記為。Y中只有部分樣本點的位置信息是已知的，將已知位置坐標(biāo)信息的樣本點集作為目標(biāo)域訓(xùn)練樣本集，其位置坐標(biāo)信息記為，其余的樣本即為沒有位置信息的待定位目標(biāo)。

基于標(biāo)簽信息的流形全局結(jié)構(gòu)對齊定位算法（Label Information Manifold Structure Alignment of Location Algorithm, LIMSALA），通過離線階段采集的參考點信息，作為標(biāo)簽建立未知域和目標(biāo)域之間的聯(lián)系，利用未知域中測試樣本和目標(biāo)域中參考樣本估計未知域中的待測樣本的位置信息。LIMSALA 對齊算法首先計算每個測試點到各個參考點的歐式距離，利用多維矩陣表示各個測試點，然后通過距離位置相似性計算樣本點間的相似性。保持其目標(biāo)域局部幾何結(jié)構(gòu)和流形間的相似性不變，獲取未知域測試樣本的標(biāo)簽信息。算法流程如圖1 所示。離線階段，通過在定位區(qū)域合理布設(shè)若干參考點，采集來自各個無線接入點的RSS 信號，構(gòu)建位置指紋數(shù)據(jù)庫及其對應(yīng)位置間的對齊映射特征向量，獲取信號的低維本征空間與物理空間位置的對應(yīng)關(guān)系，得出相應(yīng)的流形對齊向量，構(gòu)成在線定位映射數(shù)據(jù)庫，用于在線階段的映射定位過程。

圖1 基于標(biāo)簽信息的流形全局結(jié)構(gòu)對齊定位算法流程

2.2 LIMSALA算法步驟

步驟1. 離線階段參考點布設(shè)及指紋庫構(gòu)建。

①在目標(biāo)區(qū)域合理劃分不同區(qū)域及布設(shè)參考點，對每個參考點x i,X?RD×m構(gòu)建體現(xiàn)RSS 信息矩陣R與位置坐標(biāo)信息矩陣P，構(gòu)成位置指紋數(shù)據(jù)庫Radio Map；

②建立數(shù)據(jù)集樣本點特征層相似度矩陣W，通過最小化L(h)的特征值分解來求解。

步驟2. 建立源域X同目標(biāo)域測試樣本ty之間的聯(lián)系。

①在源域中計算參考點到每個樣本點歐式距離，在目標(biāo)域中計算測試點yt到每個特征層的歐式距離；

②根據(jù)映射目標(biāo)函數(shù)，構(gòu)造x i,yt的特征表示v xi,vyt；

步驟3. 計算待定位點的低維嵌入。

①依據(jù)在線接收到的RSS 信息，利用已采集樣本點X的部分標(biāo)簽信息，構(gòu)造樣本點低維坐標(biāo)U；

②根據(jù)目標(biāo)函數(shù)L(f,g)的求解結(jié)果，計算Y的低維嵌入，獲取目標(biāo)域中每個待測樣本點的位置信息，實現(xiàn)室內(nèi)定位。

3 實驗結(jié)果與分析

為評估基于標(biāo)簽信息的流形全局結(jié)構(gòu)對齊定位算法的性能，本文采集圖2 所示典型的WLAN 多墻環(huán)境下的RSS 數(shù)據(jù)，進行定位效果的測試與分析，并與3 種MDFM-AP、LLEMA 及k-means定位算法進行了性能比較。

3.1 實驗環(huán)境和數(shù)據(jù)采集

圖2 所示為典型的室內(nèi)辦公場景，位于某大學(xué)實驗辦公樓的中間層，樓層主體結(jié)構(gòu)包括走廊和若干房間，定位實驗選擇在走廊完成。整個實驗區(qū)域使用面積為49 m ×14 m，走廊寬度3m，長度約為128m，均勻劃分為247 m 個網(wǎng)格，中心作為參考點的物理位置。

圖2 實驗環(huán)境樓層平面圖

整個樓層布設(shè)多個同型號Linkksys WRT54G 無線接入點，用以整個區(qū)域的無線信號全覆蓋，在室內(nèi)多墻環(huán)境中，無線射頻信號經(jīng)過室內(nèi)墻體、桌椅等障礙物的時候，信號強度都會受到衰減，終端設(shè)備接收的實時RSS 具有復(fù)雜的時變統(tǒng)計特性。因而，利用終端驅(qū)動和RSS 信號采集軟件，在每個參考點從4 個方向、每個方向100 次，以2樣本/s采樣頻率分別采集400 個RSS 向量樣本，經(jīng)時間分集后作為訓(xùn)練樣本的離線階段指紋數(shù)據(jù)庫。實驗一共選取測試點514 個，其中124 個參考點的指紋數(shù)據(jù)，作為標(biāo)簽數(shù)據(jù)用于流形對齊映射輸入值，同時采集隨機路徑上390 個待定位目標(biāo)點的RSS 作為未標(biāo)記數(shù)據(jù)。

3.2 定位結(jié)果比較分析

圖3 所示為參考點依據(jù)物理位置均勻分布時，選取部分參考點的信息作為標(biāo)簽數(shù)據(jù)，采用基于標(biāo)簽信息的全局流形對齊定位算法LIMSALA，與基于多維模糊映射AP 優(yōu)化的MDFM-AP 定位算法、局部線性嵌入的流形對齊算法LLEMA、及傳統(tǒng)k-means算法的定位結(jié)果比較分析。當(dāng)定位誤差小于或等于3 m 時，本文算法的誤差累積概率分布為84.1%，另外3 種算法的誤差累積概率分布分別為69.7%,62.1%, 52.3%。由此可見，本文算法具有較好的定位性能，僅需較少的標(biāo)簽信息，即可實現(xiàn)與傳統(tǒng)的k-means 算法相似的定位精度。該算法利用標(biāo)簽信息建立流形間的聯(lián)系，可以實現(xiàn)在復(fù)雜定位環(huán)境下通過全局特征的保持，將參考點樣本和待測位置點樣本投影到共同的標(biāo)簽空間，因而可以獲得較好的定位結(jié)果。

圖3 不同算法的定位性能比較

表1 給出了在線測試樣本數(shù)相同的條件下，不同算法的定位性能比較：從定位計算復(fù)雜度來看，LIMSALA 算法穩(wěn)定，所需定位時間較少，僅需0.174 s，相比其它兩種算法分別減少了11.3%,87.3%，而且該算法具有最小的平均定位誤差。由此可得，在復(fù)雜的室內(nèi)環(huán)境下，基于標(biāo)簽信息的全局流形對齊定位算法可以準(zhǔn)確地得出信號的低維本征空間與物理空間位置的對齊向量，使在線定位更準(zhǔn)確，從而能更精確地估計位置。

表1 不同算法定位時間與定位性能的比較

4 結(jié)束語

本文提出了基于標(biāo)簽信息的全局流形對齊定位算法，僅需利用少量的標(biāo)簽信息構(gòu)建室內(nèi)指紋定位系統(tǒng)Radio Map，通過歐氏距離獲得位置坐標(biāo)與高維射頻信號RSS 的重構(gòu)向量表示，映射兩者間全局結(jié)構(gòu)對齊向量。該對齊映射能夠確保流形對齊過程的正確性，反映高維指紋數(shù)據(jù)與其位置空間二維坐標(biāo)的映射關(guān)系，準(zhǔn)確完成了對定位區(qū)域目標(biāo)點RSS 信號的位置估計。通過學(xué)習(xí)算法提取該數(shù)據(jù)所隱含的位置信息，用于對離線采集的已標(biāo)記數(shù)據(jù)進行更新，可以避免因指紋庫重建而帶來的人力和物力的消耗，便于室內(nèi)定位系統(tǒng)的大規(guī)模推廣和應(yīng)用。實驗結(jié)果表明，該算法可有效減少流形對齊過程中的錯誤映射，提取的全局特征結(jié)構(gòu)完整，同時無需更多的標(biāo)記數(shù)據(jù)即可實現(xiàn)待測目標(biāo)的位置估計，在提高系統(tǒng)定位性能的前提下，能夠有效地減少校準(zhǔn)工作。