基于手機收集的無線信號的自動地點學(xué)習(xí)方法

許亞倩，李建武

(中國電子信息產(chǎn)業(yè)發(fā)展研究院 網(wǎng)絡(luò)空間研究所，北京 100846)

基于手機收集的無線信號的自動地點學(xué)習(xí)方法

許亞倩，李建武

(中國電子信息產(chǎn)業(yè)發(fā)展研究院 網(wǎng)絡(luò)空間研究所，北京 100846)

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

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

地點學(xué)習(xí)；無線指紋；基于密度的聚類算法

0 引言

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

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

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

1 基于聚類算法的自動地點學(xué)習(xí)方法

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

1.1 基于密度的聚類算法

基于密度的聚類算法的基本思想是挖掘數(shù)據(jù)高密度的聚類，聚類即密度高的數(shù)據(jù)點的集合。在本文提到的自動地點學(xué)習(xí)方法中，手機自動收集的數(shù)據(jù)是信號強度表示符(RSSI)，一個RSSI即為一個數(shù)據(jù)點。基于密度的聚類算法能夠自動挖掘RSSI密度較高的簇，每個簇代表一個對用戶有意義的地點。為了發(fā)現(xiàn)簇，基于密度的聚類算法使用鄰域和鄰域密度的概念，指定了2個參數(shù)：距離閾值(Eps)和密度閾值(MinPts)[8]。下面分別介紹基于密度的聚類算法中重要的定義和流程。

(1)

(2)

發(fā)現(xiàn)簇的方法如下：

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

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

在發(fā)現(xiàn)高密度簇之后，下一步是為每個簇提取一個RSSI范圍。

(3)

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

(4)

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

1.2 自動地點學(xué)習(xí)方法

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

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

學(xué)習(xí)：如果手機在某處靜止至少10 min，系統(tǒng)將位置視為有意義的地點。啟動基于密度的聚類算法，自動學(xué)習(xí)該地點并創(chuàng)建無線指紋。無線指紋與地點一一對應(yīng)，存儲在數(shù)據(jù)庫中。

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

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

2 可行性驗證

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

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

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

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

(5)

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

2.1 AP數(shù)量對自動地點學(xué)習(xí)方法的影響

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

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

2.2 基于密度的聚類算法的參數(shù)影響

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

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

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

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

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

3 結(jié)束語

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

[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

許亞倩，李建武. 基于手機收集的無線信號的自動地點學(xué)習(xí)方法[J].無線電通信技術(shù),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—)，男，博士，主要研究方向：移動通信、數(shù)據(jù)分析、網(wǎng)絡(luò)安全等。

TP274

A

1003-3114(2017)04-09-4