丁 宇，吳楚田

(1.太原理工大學 計算機科學與技術學院，太原 030024；2.太原旅游職業(yè)學院 現(xiàn)代教育信息中心，太原 030032)

目前，由于智能手機的迅速普及和室內(nèi)定位技術的發(fā)展，室內(nèi)基于位置服務(location based service,LBS)應用得到了較多的關注。然而發(fā)展室內(nèi)LBS的先決條件是提供廣泛覆蓋、易于解釋、可呈現(xiàn)用戶位置的室內(nèi)平面圖，但正是目前十分有限的數(shù)字化的室內(nèi)平面圖限制了室內(nèi)LBS的普及。

現(xiàn)在越來越多的研究實現(xiàn)了室內(nèi)平面圖的自動構建，這在移動計算中屬于相對較新的研究問題。其中無線信息和慣性感應數(shù)據(jù)的結合是主要研究方法。CROWDLNSIDE[1]和SMARTSLAM[2]都是利用慣性數(shù)據(jù)使用Dead Reckoning算法估計人的日常行動軌跡并加以簡單的去噪和直線校正，累計疊加以覆蓋可通行區(qū)域來實現(xiàn)室內(nèi)平面圖的構建。這些方法通過智能手機來獲取慣性數(shù)據(jù)，雖然提高了估計平面圖的可行性，但由于手機傳感器精度受限，再加上Dead Reckoning算法本身的缺陷，致使構建的平面圖精度較低。JIGSAW[3]要求使用者執(zhí)行兩個拍照任務來獲取地標圖片，通過三維重建(structure from motion，SFM)技術獲取地標信息來校正慣性數(shù)據(jù)。JIANG et al[4]在慣性數(shù)據(jù)的基礎上對RSS指紋眾包進行了復雜的分析，而CALL[5]則輔助了自行獲取的AP位置信息來進行校正。室內(nèi)導航系統(tǒng)IMOON[6]利用照片眾包(Crowdsourcing)構建初始3D模型后，使用慣性數(shù)據(jù)和RSS指紋從模型中提取障礙物，留下可通行區(qū)域來編譯導航網(wǎng)絡。以上方法對慣性數(shù)據(jù)進行了各個方面的校正，得到了更精細的平面圖的同時卻增加了整體的復雜度。因此，尋找更高效精準的平面圖構建方法具有十分重要的意義。

不同于傳統(tǒng)的室內(nèi)平面圖繪制方法，筆者拋棄了精度受限的慣性數(shù)據(jù)和復雜的校正方法，而是直接使用來自WIFI基礎設施的信道狀態(tài)信息(channel state information,CSI)來構建以路徑為基礎的平面圖。構建過程中對文獻[7]的角落形狀檢測法進行了改進，并應用于檢測拐彎路徑；在對所有的眾包數(shù)據(jù)進行標記和優(yōu)化處理后，快速學習了路徑連接關系和路徑長度，并依此分析出用戶的行走路徑形狀，獲得了結構完整的室內(nèi)路徑平面圖，最高精度可達90.1%；其中每條路徑平均只使用20條軌跡序列即可進行整合，較于目前的構建工作要簡單高效。整個構建過程不需要通過其他手段獲取額外的信息，提高了自動構建室內(nèi)平面圖的靈活性，構建結果可用性較高，可應用于導航、定位等基礎室內(nèi)LBS應用。

1 預備知識

基于OFDM技術的IEEE 802.11n標準提供了這種叫做CSI的RF信道特性。它包含了子載波上每一個收發(fā)天線間的信道信息，利用現(xiàn)成的IEEE 802.11n標準的Intel 5300網(wǎng)卡以及微調(diào)過的驅動程序，即可獲得CSI形式的采樣版信道頻率響應值(channel frequency response，CFR)，格式如下：

H=[H(f1),H(f2),…,H(fN)]T,
i∈[1,30] .

(1)

每個CSI刻畫了一個子載波的幅度和相位信息：

H(fi)=‖H(fi)‖ejsin∠H(fi).

(2)

式中：H(fi)是中心頻率為fi的子載波的CSI；∠H(fi)代表相位[8]。通過恰當?shù)男盘柼幚砑夹g，CSI可以對不同的傳播環(huán)境呈現(xiàn)不同的子載波幅度和相位特征，而且相同的傳播環(huán)境下CSI值可保持相對穩(wěn)定。

2 算法流程

目前室內(nèi)無線網(wǎng)絡普及程度較高，幾乎每個房間都有一個無線接入點(access point，AP)，因此利用Wi-Fi基礎設施進行室內(nèi)環(huán)境感應是十分可行的。只需要用戶在室內(nèi)行走時使用移動設備連接到網(wǎng)絡，并記錄用戶進入室內(nèi)之前到走出室內(nèi)之后的GPS信號來標記一段軌跡的開始和結束，最后通過分析眾多包含不同源的CSI序列的行走軌跡來構建平面圖。從用戶走進室內(nèi)之前到走出室內(nèi)后獲得GPS信號標記開始和結束，獲取來自不同AP的CSI序列來構建平面圖。圖1為算法的流程圖，其構建過程主要分為4部分。

圖1 室內(nèi)路徑生成算法流程圖Fig.1 Flowchart of Indoor path plan generation algorithm

1) 拐點識別算法：通過匹配在不同走廊形狀上行走測得的CSI變化率的變化特征來識別拐點，區(qū)分直線行走和拐彎序列并對拐點進行標記；

2) 峰值檢測方法：在單個軌跡的序列中尋找每一段AP序列的峰值，并對峰值出現(xiàn)時間進行標記；

3) 軌跡序列拼接算法：利用AP序列和拐點序列的相似性進行分組和拼接，分析出眾包數(shù)據(jù)中各路徑之間的連接關系得到鄰接圖G；

4) 分段長度估計算法：將標記點的時間差序列段進行K-means聚類，取簇中心作為行走的時間間隔來估計路徑長度。

3 算法實現(xiàn)

該平面圖構建方法主要分為對眾包CSI序列的逐個標記處理和學習路徑關系兩個階段。以下將詳細闡述算法的實現(xiàn)過程。

3.1 CSI序列處理

3.1.1 拐點識別分析

根據(jù)FILA中的CSI的路徑損耗模型[11]可知：

(3)

式中：c，f0是波速和中心頻率；n是路徑損耗指數(shù)，在室內(nèi)環(huán)境中一般是2～4；σ是環(huán)境因子，這些均為常數(shù)，因此行走過程中會改變CSI值的因素只有距離和阻礙物的變化。而阻礙物如墻、家居一般分布在墻角，后續(xù)識別拐角和峰值等方法都可以抵抗這種衰減。因此導致CSI產(chǎn)生變化的主要因素是d，且它們互成反比。所以用戶以不同形狀的軌跡勻速經(jīng)過AP時，收發(fā)距離的變化為：

(4)

式中：d0是初始位置的收發(fā)距離。在本文中，不同于文獻[7]中的三種角落形狀，要識別的形狀有直角、直線、相反直角的特征，將直角和反直角判斷拐彎。

首先，參照文獻[7]中CSI變化率的提取得到如圖2(a)的3種路徑形狀的變化率R1.

通過比較3個R1隨時間的變化，發(fā)現(xiàn)反直角的R1變化與直線相似，均為逐漸遞減但遞減速度不同。因此想要區(qū)分反直角和直線兩種情況[7]的方法并不適用。通過二次提取CSI變化率的變化速率R2，變化曲線如圖2(b)，發(fā)現(xiàn)R2在拐彎情況下會有一個陡峭的波動，而直線的變化則十分緩慢，因此可利用波動幅度來區(qū)分直線和直角軌跡。通過訓練多組拐彎數(shù)據(jù)得到適當?shù)姆乳撝郸?，波動幅度超過(-τ,τ)則視為拐彎序列。通過判斷波動幅度的正負還可以確定直角還是相反直角。最后將波動的峰值點標記為拐點T.

由于理論模型中的函數(shù)是連續(xù)的，而實驗采集的數(shù)據(jù)是離散值，并且室內(nèi)環(huán)境下噪音干擾較多。因此我們用中值濾波對CSI數(shù)據(jù)進行去噪，然后擬合實驗數(shù)據(jù)并用擬合表達式來直接估計其變化率。

3.1.2 峰值檢測

無線信號的傳播與傳輸距離有關。當用戶手持移動設備在走廊行走時，會路過一個收發(fā)距離最短的地方，在這里走廊與AP會有一個的垂直距離，此點叫做AP在走廊上的對應位置。理論上講在這一位置上接收到該AP的信號強度應當是最強的，因此我們計劃使用高斯平滑后CSI序列，尋找到曲線的峰值并進行標記，以此確定AP對應位置出現(xiàn)的時刻。

判斷序列為直線行走時，需要尋找每一段AP序列的全局波峰，即峰值必須大于前后2個相鄰時間窗的CSI值。如A點到B點距離48 m，AP1，AP2，AP3的對應位置分別在8，24，38 m處；用戶經(jīng)過兩點后獲取了長達50 s的CSI序列如圖3所示，通過計算分別在8.2，26，43.4 s時到達峰值，依次記錄為3個AP的到達時間t1，t2，t3，標記誤差不超過1 m.不同于原始數(shù)據(jù)的隨機出現(xiàn)的峰值，使用高斯平滑后的CSI曲線獲取的峰值更接近真實的AP對應位置。判斷某AP的序列為拐角后，拐彎軌跡可能會因為測量時間較長，在拐彎之前和之后會經(jīng)過兩條交叉路徑上的對應位置，因此會出現(xiàn)兩個波峰max1，max2，都需要標記。標記APi在走廊上的對應點出現(xiàn)的時間t的同時，我們還要記錄下APi的峰值Pks，將兩者作為APi的屬性來標記序列中的AP.

圖3 一段CSI序列樣本Fig.3 A sample of CSI sequence

3.2 路徑關系學習

通過上一節(jié)對軌跡序列的拐點和峰值的時間戳節(jié)點進行標記后，將一個人的行走軌跡用一個二元組表示：Pi={BAPx,BAPy,T1,…BAPz,…,Tj,…}.其中，BAPx=(Pks,ti)是對不同接入點的標記，Tj=(BAPi,Pks,tj)是拐點的標記，識別出Ti的CSI值來源于BAPi，ti是順序到達時間。T將路徑分割為多個單元段。

本節(jié)將介紹通過序列拼接算法和長度估計法將眾包數(shù)據(jù)進行整合，學習到路徑關系的詳細過程。

3.2.1 序列拼接

同一室內(nèi)環(huán)境下，眾包軌跡之間必定會有部分重合，利用這些重合段可以在拐點識別率有限的情況下，來補償同拐點的不同路徑的識別結果，而且重點是要利用這些部分重復序列實現(xiàn)序列拼接。

1) 分段軌跡序列Pi：用Pi經(jīng)過的所有標記拐點T來將其劃分為格式為(h1,T,h2)的三元組Path;h1,h2為經(jīng)過拐點T的前后兩段AP序列，序列中的AP按經(jīng)過順序排列。h1是入序列，h2是出序列。一次方法對所有的中報數(shù)據(jù)進行處理，得到數(shù)個Path數(shù)組。

2) 對Path進行分組，比較T的屬性BAPi是否相同，且Pks值相似度是否大于60%，滿足條件則歸為同一Turn組，一組中的h代表從同一個拐點可達的路徑。

3) 將同組Path進行歸類組合，目標是為以環(huán)形鏈表的形式Turn(h1,h2,h3,h4)表示的拐點路徑組賦值，其中相鄰h是拐彎關系，相隔一位是直走關系。Path數(shù)組中入序列和出序列是拐彎關系，因此對同一組中每個Path的hi進行KMP匹配，當入序列匹配成功、出序列失敗，則說明兩個出序列是直走關系，需相隔放置，而拐彎關系相鄰放置，所以先放置入序列為h1，其他兩個分別為h4,h2；依此類推直到不再有新的賦值。

4) 對Turn的賦值結果進行驗證：如果4個h非空且無重復，則確認為四叉路口；一個h為空，為三叉路；兩個為空則為二叉路；有重復則賦值出錯。

5) 將所有Turn中的h序列進行兩兩比較，如果以相反序列匹配成功，則判斷兩Turn代表的T節(jié)點相鄰接，用鄰接矩陣A來表示拐點T之間的鄰接關系；如果h沒有匹配到拐點，那么該h序列的末端節(jié)點APi也作為鄰接矩陣A的一個節(jié)點，并與自己歸屬的T相鄰接。將A表示為無向圖G=(E,U)，拐點T和沒有連接T的h序列末位AP的ti均定義為圖G的頂點U，h為連接邊。

3.2.2 長度估計

由于先前標記了軌跡序列中各節(jié)點的到達時間ti，因此最直接的長度估計方法是知道走速v和達時間差|ti-ti-1|來獲得。然而，人與人的走路速度和行為習慣各不相同，直接平均會影響精度。為解決這個問題，使用K-means聚類來避免離群數(shù)據(jù)對長度估計的干擾。

通過上一節(jié)的走廊拼接，將每一個拐點之間的AP序列視為單元段，以所有眾包軌跡數(shù)據(jù)在每個單元段的時間序列差(|tN-tN-1|,…,|t1-t2|)作為輸入來執(zhí)行K-means聚類。若有m條軌跡經(jīng)過同一單元段，進行m(n-1)的K-means聚類，k=1，最后以輸出簇的中心點作為穿過單元段的時間差序列。聚類后的數(shù)據(jù)剔除了離群點，保證了每一段時間差都適用于大部分情況。提前測量一段已知距離來估計人在該模型下的平均速度為v，然后與聚類后的時間間隔相乘得到節(jié)點間的穿越距離S.將單元段的長度作為h的屬性，賦值給圖G，既可用于接下來的平面路徑圖繪制。

3.2.3 生成平面圖

平面圖構造旨在以對人類觀察者視覺上更直觀的方式將圖G在平面上顯示。本文繪圖時參考LUO et al[12]采用的平面圖可視化算法，并加以長度信息進行優(yōu)化。第一步用深度優(yōu)先搜索(DFS)遍歷圖G，遍歷過程中會生成一個生成樹。第二步用Tarjan算法求出每一個頂點的DFN和LOW值，記錄深度優(yōu)先遍歷過程中的每個頂點的父節(jié)點，遍歷所有點的LOW,DFN來尋找橋，并將其用于路徑尋找算法搜索環(huán)路。最后用平面嵌入算法畫出平面路徑圖。該算法有兩個主要限制：每個邊必須是直線，夾角角度必須是直角。我們首先畫出具有四個邊緣的環(huán)路，其次非環(huán)路的路徑。最終得到一幅路徑關系草圖，簡單的將頂點和邊緣的邏輯關系呈現(xiàn)到了平面上的。根據(jù)上一節(jié)得出的單元路徑的長度，來對各節(jié)點之間的距離進行調(diào)整，使得平面圖整體達到更好的精度。

4 實驗評估

4.1 試驗部署

為了評估系統(tǒng)的性能，課題組招募了10名學生在某高校的教學樓和計算機學院樓內(nèi)采集了一個月的無線數(shù)據(jù)，總共包含了來自42個AP的251條CSI序列。以路由器的Mac地址來唯一標記一個AP，并用配有Intel 5300 NIC的3.6 GHz Intel(R)Pentium 4 CPU 4GB RAM筆記本作為接收器。所有的路由器以IEEE 802.11n AP模式工作。接收機具有3個工作天線，在實驗過程中，接收機以每秒100個數(shù)據(jù)包的速率從AP連續(xù)ping數(shù)據(jù)包。所有的數(shù)據(jù)處理是在3.60 GHz Intel(R)Core(TM)i7-4790 CPU 4G RAM桌面上的Matlab R2012a.選擇FILA的CSI傳播模型來模擬富含多路徑效應的室內(nèi)環(huán)境下的信號傳播來提取拐點特征。

4.2 結果分析

評估了拐點識別方法的準確性、聚類方法對距離估計準確性的影響以及平面圖的精度。

4.2.1 拐點估計結果

分析了為CSI變化率變化幅度設定的閾值τ對識別結果的影響，圖4的(a)、(b)分別顯示了不同τ的誤判率(FPR)和漏報率(FNR)。從圖中可以看出：τ設置過高，直線檢測的FPR較高，直角和反直角兩種情況容易被識別成直線；τ設置過低，直線檢測的FNR過高，輕微浮動的直行序列被排除，識別成了直角或反直角。因此τ為0.4是最理想情況。

圖4 對拐角檢測識別率的評估Fig.4 Evaluation of corner detection recognition rate

為了與文獻[7]的角落形狀檢測法進行比較，將兩種方法時應用于我們的試驗數(shù)據(jù)中，得出3種路徑形狀的識別率結果如圖4(c)所示。圖中，左邊是角落形狀檢測方法的識別率，右邊是拐角檢測方法的識別率，可以看出我們的方法明顯降低了直線和相反直角的混淆率，3種形狀識別率達到了94%，89%，92%.

4.2.2 距離估計誤差

整個算法中，距離精度至關重要，而峰值檢測標記AP和聚類時間段兩部分起到了精度的主要決定作用。首先我們記錄了穿越兩個節(jié)點的真實時間差來分析峰值檢測算法的效果。將CALL[5]的峰值檢測方法與本文相比較，畫出CDF圖如圖5(a)所示。CALL設置時間窗求CSI平均值來劃分CSI序列，將最大值標記為AP位置，灰線效果明顯差于使用高斯平滑標記峰值的黑線，筆者的方法80%的誤差在1.5 s內(nèi)，要比CALL準確兩倍。時間窗會而影響時間分辨率，使得記錄時間與現(xiàn)實有一定的偏差，而高斯平滑曲線則能更好的描述CSI的變化。

圖5 距離估計誤差的累積分布圖Fig.5 The cumulative distribution of the distance estimated error

通過測量AP對應位置以及拐點位置之間的距離來評估聚類時間段后的距離估計誤差。如圖5(b)描述了K-means聚類與平均時間段后估計的距離誤差CDF。顯而易見，聚類后80%的距離誤差在1.6 m以內(nèi)，要遠好于直接平均，這樣的結果足以準確的估計平面圖中的路徑長度了。

4.2.3 生成平面圖

該系統(tǒng)構建的平面圖是一個路徑邏輯關系圖，將輸出的路徑結構圖覆蓋到真實的平面圖上進行對比。如圖6所示，絕大部分通行路徑都構建了出來，連接關系也基本無誤。

圖6 學院樓2樓的路徑平面圖構建結果Fig.6 A constructed path plan sample of CS building's 2 floor

通過對準兩幅圖的中心點和方向來實現(xiàn)最大程度的重疊，估計了它與地面真實情況的接近程度。計算結果呈現(xiàn)在表1中，其中Hn是精確度和找召回率的調(diào)和平均數(shù)。該方法在實驗環(huán)境中達到了最高86.3%的精度，94.2%的查全率以及90.1%的Hn，這在一定程度上體現(xiàn)了僅利用來自于無線路由的CSI信息同樣可以得到精度有保障的室內(nèi)平面圖。

表1 平面圖精度估計參數(shù)Table 1 Accuracy evaluate about floor paln %

5 總結

自動構建數(shù)字化室內(nèi)平面圖是當前基于位置服務的發(fā)展必須要解決的關鍵技術之一。本文提出的構建方法僅通過利用來自Wi-Fi基礎設施的信道狀態(tài)，就繪制出一條結構完整、可應用于室內(nèi)LBS的室內(nèi)平面圖，大幅度提高了構建效率和靈活性。該算法對于Wi-Fi噪聲和遮蔽效應變化是魯棒的，實驗結果也驗證了其設計的優(yōu)勢。通過動作識別和特征提取，進而分析房間性質(zhì)，是下一步的研究方向。

[1] ALZANTOT M,YOUSSEF M.CrowdInside:automatic construction of indoor floorplans[J].Eprint Arxiv,2012:99-108.

[2] SHIN H,CHON Y,CHA H.Unsupervised construction of an indoor floor plan using a smartphone[J].IEEE Trans Systems,Man,and Cybernetics,2012:889-898.

[3] GAO R,ZHAO M,YE T,et al.Jigsaw:indoor floor plan reconstruction via mobile crowdsensing[C]∥ACM.International Conference on Mobile Computing and NETWORKING.2014:249-260.

[4] JIANG Y,XIANG Y,PAN X,et al.Hallway based automatic indoor floorplan construction using room fingerprints[C]∥ACM.International Joint Conference on Pervasive and Ubiquitous Computing.ACM,2013:315-324.

[5] ABADLEH A,HAN S,HYUN S J,et al.Construction of indoor floor plan and localization[J].Wireless Networks,2016,22(1):175-191.

[6] DONG J,XIAO Y,NOREIKIS M,et al.IMoon:using smartphones for image-based indoor navigation[C]∥The,ACM Conference on Embedded Networked Sensor Systems.ACM,2015:85-97.

[7] WANG Y,ZHOU Z,WU K.Sensor-free corner shape detection by wireless networks[C]∥IEEE.International Conference on Parallel and Distributed Systems.IEEE,2015:306-312.

[8] 朱海,肖甫,孫力娟,等.基于信道狀態(tài)信息的WiFi環(huán)境感知技術[J].南京郵電大學學報(自然科學版),2016,36(1):94-103.

ZHU H,XIAO F,SUN L J,et al.CSI-based wifi environment sensing[J].Journal of Nanjing University of Posts and Telecommunications(Natural Science),2016,36(1):94-103.

[9] ZHOU Z,WU C,YANG Z,et al.Sensorless sensing with WiFi[J].Tsinghua Science & Technology,2015,20(1):1-6.

[10] ZHANG C,LI F,LUO J,et al.iLocScan:harnessing multipath for simultaneous indoor source localization and space scanning[C]∥ACM.Conference on Embedded Networked Sensor Systems.ACM,2014:91-104.

[11] XIAO J,YI Y,et al.FILA:Fine-grained indoor localization[J].Proceedings-IEEE INFOCOM,2012,131(5):2210-2218.

[12] LUO X,WONG A,ZHOU M,et al.Automatic floor plan construction for indoor localization[C]∥10th Advanced International Conference on Telecommunications.Paris：2014.