許亞倩，李建武

(中國電子信息產(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è)寫。詳細(xì)介紹了一種自動地點學(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)用等，需要基于坐標(biāo)(例如，緯度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í)方法?！盁o監(jiān)督”是指該方法使用的無線信號強度標(biāo)示符是手機在用戶日常生活中自動收集的，不需要用戶的額外輸入和操作。手機自動收集并記錄無線信號強度標(biāo)示符后，對該數(shù)據(jù)進行處理，自動發(fā)現(xiàn)用戶停留超過一段時間(例如，10 min)的地點，學(xué)習(xí)這些地點的無線指紋，存儲于本地數(shù)據(jù)庫中。當(dāng)用戶重新訪問這些學(xué)習(xí)過的地點時，手機自動收集的無線信號強度標(biāo)示符與本地數(shù)據(jù)庫中的無線指紋對比，識別出用戶當(dāng)前所處地點。

1.1 基于密度的聚類算法

基于密度的聚類算法的基本思想是挖掘數(shù)據(jù)高密度的聚類，聚類即密度高的數(shù)據(jù)點的集合。在本文提到的自動地點學(xué)習(xí)方法中，手機自動收集的數(shù)據(jù)是信號強度表示符(RSSI)，一個RSSI即為一個數(shù)據(jù)點?；诿芏鹊木垲愃惴軌蜃詣油诰騌SSI密度較高的簇，每個簇代表一個對用戶有意義的地點。為了發(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)激活無線感測功能，收集無線信號強度標(biāo)示符RSSI。當(dāng)手機處于運動狀態(tài)或收集時間達(dá)到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í)方法的介紹及實驗探索請參考文獻(xiàn)[7,9,15]。

3 結(jié)束語

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