基于手機收集的無線信號的自動地點學習方法

許亞倩，李建武

(中國電子信息產業發展研究院 網絡空間研究所，北京 100846)

基于手機收集的無線信號的自動地點學習方法

許亞倩，李建武

(中國電子信息產業發展研究院 網絡空間研究所，北京 100846)

大部分人的日常生活通常只集中在少數幾個特定的地點(例如家、辦公室、食堂、餐廳、咖啡店及健身房等)。這幾個地點與人們的行為和日程息息相關，被稱為有意義的地點。地點學習是一種新興技術，利用手機傳感器收集到的數據自動學習對用戶有意義的地點。所學習的地點信息可以用于大量基于地點的移動應用和互聯網服務，也可以幫助推斷用戶側寫。詳細介紹了一種自動地點學習方法——利用手機自動收集的無線信號的信號強度指示符(

Signal Strength Indicators，RSSI)，采用基于密度的聚類算法，自動學習對用戶有意義的地點，生成地點的無線指紋。此外，還討論了該自動地點學習方法在實驗室和現實場景中的工作性能，建立模型并確定最佳參數，用于提供最佳的地點正確識別率。

地點學習；無線指紋；基于密度的聚類算法

0 引言

用戶的位置為許多新興的基于位置的應用和服務提供了重要信息。一些基于位置的服務和應用[1-2]，例如導航、緊急安全與安全應用等，需要基于坐標(例如，緯度51.310 756 5，經度9.474 256 1，高度260.0)的位置信息；而另一類新興的服務和應用，諸如社交軟件、叫車服務等，則使用基于地點(例如，萬壽路地鐵站、中國電子信息產業發展研究院)的位置信息。

近年來，一種新興的技術“地點學習”越來越受到重視，該技術旨在發現與用戶相關的、且具有語義的“地點”[3-4]。這些地點往往是用戶停留超過一定時間段(例如，10 min)或頻繁訪問的地方，例如家、辦公室、會議室以及萬壽路地鐵站等等。地點學習一般利用一系列連續收集的傳感器數據(例如，GPS讀數、手機信號、無線信號及加速度計讀數等)，挖掘對用戶有意義的地點，同時挖掘其他有用的信息(例如，該地點的進入時間和離開時間等)。地點學習的原理是如果用戶在某個地點停留一段時間，手機在該地點連續收集到的傳感器數據會累積，數據密度增大[5]，這種數據密度的屬性可以被用來進行地點學習。

地點學習雖然不能自動給地點命名，但可以自動發現在用戶日常生活中的重要地方，用于基于地點的應用和服務[6-7]，例如智能家居中根據用戶地點自動控制電器開關。另外，這些地點信息可以幫助推斷用戶的其他信息，例如活動、偏好、愛好及社交角色等，支持更廣泛的移動應用和互聯網服務。

1 基于聚類算法的自動地點學習方法

本文介紹的基于聚類算法的自動地點學習方法是一種“無監督”的學習方法?！盁o監督”是指該方法使用的無線信號強度標示符是手機在用戶日常生活中自動收集的，不需要用戶的額外輸入和操作。手機自動收集并記錄無線信號強度標示符后，對該數據進行處理，自動發現用戶停留超過一段時間(例如，10 min)的地點，學習這些地點的無線指紋，存儲于本地數據庫中。當用戶重新訪問這些學習過的地點時，手機自動收集的無線信號強度標示符與本地數據庫中的無線指紋對比，識別出用戶當前所處地點。

1.1 基于密度的聚類算法

基于密度的聚類算法的基本思想是挖掘數據高密度的聚類，聚類即密度高的數據點的集合。在本文提到的自動地點學習方法中，手機自動收集的數據是信號強度表示符(RSSI)，一個RSSI即為一個數據點?；诿芏鹊木垲愃惴軌蜃詣油诰騌SSI密度較高的簇，每個簇代表一個對用戶有意義的地點。為了發現簇，基于密度的聚類算法使用鄰域和鄰域密度的概念，指定了2個參數：距離閾值(Eps)和密度閾值(MinPts)[8]。下面分別介紹基于密度的聚類算法中重要的定義和流程。

(1)

(2)

發現簇的方法如下：

② 如果2個簇包含相同的RSSI點，則2個簇合并成一個簇；

③ 對于不屬于任何簇的RSSI點，被視為噪聲。

在發現高密度簇之后，下一步是為每個簇提取一個RSSI范圍。

(3)

定義4——無線指紋：在基于RSSI的地點學習方法中，無線指紋是在每一地點收集到的無線信號的MAC地址和RSSI范圍對(MACk:[RSSIkl,RSSIku])的集合。圖1給出了某一地點無線指紋的范例。

(4)

圖1 基于RSSI范圍的無線指紋的范例

1.2 自動地點學習方法

本文所提出的基于聚類算法的自動地點學習方法具有自動學習、定位和更新無線指紋的機制。它自動學習和更新對用戶有意義的地點的無線指紋，并在用戶重新訪問這些地點時進行地點識別。該自動地點方法在工作中執行以下操作：

收集：手機中的嵌入式加速度計檢測手機的運動狀態。一旦手機被檢測靜止，系統激活無線感測功能，收集無線信號強度標示符RSSI。當手機處于運動狀態或收集時間達到30 min時，系統會停用無線感應功能。

學習：如果手機在某處靜止至少10 min，系統將位置視為有意義的地點。啟動基于密度的聚類算法，自動學習該地點并創建無線指紋。無線指紋與地點一一對應，存儲在數據庫中。

定位：當感測到無線信號時，系統將感知的無線信號與無線指紋數據庫中存儲的無線指紋進行比較，通過計算找出最相似無線指紋。系統可以推斷用戶位于最相似無線指紋所指示的地點。

更新：如果系統檢測到所處地點的無線指紋無效，則自動更新該地點的無線指紋。手機在該地點感測無線信號重新學習以生成新的無線指紋，并被添加到數據庫。當無線指紋在一段時間內(例如，在系統中將其設置為3個月)不被識別，系統會刪除無效的指紋。

2 可行性驗證

在擁有多間相鄰小房間的辦公區域進行上述自動地點學習方法可行性驗證。選擇小規模辦公區域的原因是，在室內環境下以通過無線指紋區分相鄰房間是一個科研難題。該辦公區位于一棟三層樓房的二樓，由5個相鄰的辦公房間組成，每個房間即一個有意義的地點。房間2408的面積為 38.32 m2，房間2410、2411、2412和2414的面積為 18.31 m2，布局如圖2所示。在第一種情況下，使用部署在已知位置的4個無線路由器(AP)來探索AP數量對該自動地點學習方法的影響。第二種情況下，撤掉上述4個AP，在無特殊部署的實際環境中進行研究。

圖2 可行性驗證研究的場所布局和數據手機位置

該實驗使用5個摩托羅拉智能手機Milestone(Android版本2.2.1)作為測量設備，收集位置如圖2所示。手機以5 s的間隔收集RSSI，允許在整個測量中有辦公人員存在。在這種情況下，人的運動會對信號穩定度產生影響，但模型建立在真實生活場景中，而非實驗場景中。

將每個房間收集數據分為訓練數據集和評估數據集，訓練數據集用于產生每個房間的無線指紋，訓練數據集用來進行房間識別，評估方法可行性。首先定義識別階段的評估度量：“正確(Correct)”指智能手機在一個房間，該方法正確識別它所在的房間；“錯誤(False)”表示手機在一個房間，但識別結果是另一房間；“正確識別率(CRP)”被定義為“正確(Correct)”的數量除以“正確(Correct)”和“錯誤(False)”的數量。

(5)

CRP度量能夠衡量該自動地點學習方法如何正確地學習且識別地點，即評估該方法的可行性。

2.1 AP數量對自動地點學習方法的影響

將AP的數量從1個增加到4個來重復測量，使用在每個地點前30 min收集的無線RSSI點作為訓練數據集，隨后的30 min收集的無線RSSI點作為測試數據集。基于之前的研究成果[9]，Eps= 2和MinPts= 120被用作學習過程中的參數。計算每個房間的CRP后求平均值。結果如圖3所示?？梢杂^察到AP的增加提高了CRP。當只有1個AP時，CRP值為59.17%，3個和4個AP時的CRP分別增加到97.63%和99.25%，該結果顯示了AP數量的增加大幅提高了自動地點學習方法的CRP。

圖3 AP從1增加到4時的平均CRP值

2.2 基于密度的聚類算法的參數影響

前面介紹過該地點學習方法使用的基于密度的聚類算法中有2個參數：距離閾值(Eps)和密度閾值(MinPts)。在本小節中，比較使用不同參數組合獲得的CRP，建立適合辦公區域的地點學習模型。

在學習階段的每次重復改變Eps和MinPts的值。所選擇的Eps值是1～10，增量為1。選擇的MinPts值范圍為10～240，增量為10。比較的結果如圖4所示，結果顯示Eps= 3和MinPts= 110是最佳的基于密度的聚類算法的參數。當Eps>4時，CRP值顯著下降。這是因為當Eps過大時，2個相鄰房間的RSSI點生成的簇具有重疊的趨勢，導致地點學習方法無法區分相鄰房間?；谶@個結果，保持MinPts值為110，重復Eps值(從1～10)和AP數(從1～4)，觀察Eps和AP數量的最佳組合。圖5表明，Eps保持3～7之間，AP為3時，可以獲得最佳CRP值。

圖4 使用不同參數組合(Eps，MinPts)時的CRP值

圖5 使用不同參數組合(Eps，APs)時的CRP值

通過上面改變參數組合的評估結果可以看到，當AP的數量保持為3，基于密度的聚類算法中有參數距離閾值(Eps)設定在3～7之間，密度閾值(MinPts)設定為110時，所建的地點學習模型最適合室內辦公室區域的地點學習和識別。更多關于此自動地點學習方法的介紹及實驗探索請參考文獻[7,9,15]。

3 結束語

本文詳細介紹了一種新型的自動地點學習方法——基于密度的聚類算法。該方法利用手機收集的無線信號，根據信號強度標示符的密度分布生成無線指紋，自動學習地點，無需任何用戶輸入和控制。分別在實驗室和現實場景中進行探索，研究該方法的可行性，根據實驗結果確定了適合于小規模辦公區域的理想模型和參數。結果顯示即使在小規模的辦公區域，相鄰房間正確識別概率可以達到97%，即，該方法可以有效地進行房間級別精度的地點學習，精確識別用戶所處的房間。

[1] Kim D H,Hightower J,Govindan R，et al.Discovering Semantically Meaningful Places from Pervasive RF-beacons[C]∥in Proc. 11th International Conference on Ubiquitous Computing (UbiComp),Orlando,FL,2009:21-30.

[2] Marmasse N，Schmandt C.A User-centered Location Model[C]∥in Personal and Ubiquitous Computing,USA:2002:318-321.

[3] Ashbrook D,Starner T.Learning Signicant Locations and Predicting User Movement with GPS[C]∥in the 6th International Symposium on Wearable Computers,Atlanta,GA,2002:101-108.

[4] Hightower J,Consolvo S,Lamarca A,et al.Learning and Recognizing the Places We Go[C]∥in 7th International Conference on Ubiquitous Computing,Venice,Italy,2005:159-176.

[5] Dousse O,Eberle J,Mertens M. Place Learning Via Direct WiFi Fingerprint Clustering[C]∥in IEEE 13th International Conference on Mobile Data Management,Bengaluru,2012:282-287.

[6] Jiang Y,Pan X,Li K,et al.ARIEL:Automatic Wi-Fi based Room Fingerprinting for Indoor Localization[C]∥in Proc.14th International Conference on Ubiquitous Computing,Pittsburgh,PA,USA,2012:441-450.

[7] Kim D,Kim Y,Estrin D,et al. SensLoc:Sensing Everyday Places and Paths Using Less Energy[C]∥in Proceedings of the 8th ACM Conference on Embedded Networked Sensor Systems,2010:43-56.

[8] Ester E,Kriegel H,Sander J,et al.A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise[C]∥in 2nd International Conference on Knowledge Discovery and Data Mining,Portland,OR,USA,1996:226-231.

[9] Xu Y, Lau S L,Kusber R,et al.An Experimental Investigation of Indoor Localization by Unsupervised Wi-Fi Signal Clustering[C]∥in Future Network and Mobile Summit,Treto,Italy,2012:1-10.

[10]Xu Y,Lau S L,Kusber R,et al. DCCLA:Autonomous Indoor Localization Using Unsupervised Wi-Fi Fingerprinting[C]∥in Modeling and Using Context,Lectures Notes in Computer Science,Kassel,Germany,2013:73-86.

[11]Xu Y, Kusber R,David K.An Enhanced Density-Based Clustering Algorithm for the Autonomous Indoor Localization[C]∥in 2013 International Conference on Mobile Wireless Middleware,Operating Systems and Applications (Mobilware),Bologna,2013:39-44.

[12]Lau S L,Xu Y,David K. Novel Indoor Localisation Using an Unsupervised Wi-Fi Signal Clustering Method[C]∥in 2011 Future Network and Mobile Summit,Warsaw,2011:1-8.

[13]Xu Y,David K.How Near is Near:A Case Study of the Minimum Distance to Distinguish Neighbouring Places in Place Learning Using Wi-Fi Signals[C]∥ in IEEE VTC,Nanjing,China,2016:1-5.

[14]Xu Y, David K.WHERE:An Autonomous Localization System with Optimized Size of the Fingerprint Database[C]∥in Modeling and Using Context,Lectures Notes in Computer Science,France,2015:544-550.

[15]Xu Y,Meng L,David K.Unsupervised Learning with Motion Detection[C]∥in Modeling and Using Context,Lectures Notes in Computer Science,Kassel,Germany,2015:132-143.

Autonomous Place Learning Using Wi-Fi Signals Collected by Smartphones

XU Ya-qian，LI Jian-wu

(Institute of Cyber Space of CCID,Beijing 100846,China)

People spend most of their time in a few significant places,often indoors in a small number of select rooms and locations. Indoor localization in terms of a user’s current place,related to a user’s daily life,routines or activities,is an important context. We implemented an automatic approach DCCLA (Density-based Clustering Combined Localization Algorithm) to learn automatically the Wi-Fi fingerprints of the significant places based on density-based clustering. In order to accommodate the influence of the signal variation,clustering procedure separately works on a list of RSSIs (Received Signal Strength Indicators) from each AP (Access Point). In this paper,the approach is experimentally investigated in a laboratory setup and a real-world scenario in an office area with adjacent rooms,which is a key challenge to distinguish for place learning and recognition approaches.

place learning;Wi-Fi fingerprinting;density-based clustering

10. 3969/j.issn. 1003-3114. 2017.04.03

許亞倩，李建武. 基于手機收集的無線信號的自動地點學習方法[J].無線電通信技術,2017,43(4):09-12,29.

[XU Yaqian,LI Jianwu. Autonomous Place Learning Using Wi-Fi Signals Collected by Smartphones[J].Radio Communications Technology,2017,43(4):09-12,29.]

2017-03-07

許亞倩(1985—)，女，博士，主要研究方向：移動通信、人機交互、情境感知等。李建武(1984—)，男，博士，主要研究方向：移動通信、數據分析、網絡安全等。

TP274

A

1003-3114(2017)04-09-4