基于手機(jī)收集的無線信號(hào)的自動(dòng)地點(diǎn)學(xué)習(xí)方法

許亞倩，李建武

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

基于手機(jī)收集的無線信號(hào)的自動(dòng)地點(diǎn)學(xué)習(xí)方法

許亞倩，李建武

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

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

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

地點(diǎn)學(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ù)等，則使用基于地點(diǎn)(例如，萬壽路地鐵站、中國電子信息產(chǎn)業(yè)發(fā)展研究院)的位置信息。

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

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

1 基于聚類算法的自動(dòng)地點(diǎn)學(xué)習(xí)方法

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

1.1 基于密度的聚類算法

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

(1)

(2)

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

② 如果2個(gè)簇包含相同的RSSI點(diǎn)，則2個(gè)簇合并成一個(gè)簇；

③ 對(duì)于不屬于任何簇的RSSI點(diǎn)，被視為噪聲。

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

(3)

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

(4)

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

1.2 自動(dòng)地點(diǎn)學(xué)習(xí)方法

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

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

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

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

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

2 可行性驗(yàn)證

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

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

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

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

(5)

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

2.1 AP數(shù)量對(duì)自動(dòng)地點(diǎn)學(xué)習(xí)方法的影響

將AP的數(shù)量從1個(gè)增加到4個(gè)來重復(fù)測量，使用在每個(gè)地點(diǎn)前30 min收集的無線RSSI點(diǎn)作為訓(xùn)練數(shù)據(jù)集，隨后的30 min收集的無線RSSI點(diǎn)作為測試數(shù)據(jù)集?；谥暗难芯砍晒鸞9]，Eps= 2和MinPts= 120被用作學(xué)習(xí)過程中的參數(shù)。計(jì)算每個(gè)房間的CRP后求平均值。結(jié)果如圖3所示?？梢杂^察到AP的增加提高了CRP。當(dāng)只有1個(gè)AP時(shí)，CRP值為59.17%，3個(gè)和4個(gè)AP時(shí)的CRP分別增加到97.63%和99.25%，該結(jié)果顯示了AP數(shù)量的增加大幅提高了自動(dòng)地點(diǎn)學(xué)習(xí)方法的CRP。

圖3 AP從1增加到4時(shí)的平均CRP值

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

前面介紹過該地點(diǎn)學(xué)習(xí)方法使用的基于密度的聚類算法中有2個(gè)參數(shù)：距離閾值(Eps)和密度閾值(MinPts)。在本小節(jié)中，比較使用不同參數(shù)組合獲得的CRP，建立適合辦公區(qū)域的地點(diǎn)學(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時(shí)，CRP值顯著下降。這是因?yàn)楫?dāng)Eps過大時(shí)，2個(gè)相鄰房間的RSSI點(diǎn)生成的簇具有重疊的趨勢(shì)，導(dǎo)致地點(diǎn)學(xué)習(xí)方法無法區(qū)分相鄰房間?；谶@個(gè)結(jié)果，保持MinPts值為110，重復(fù)Eps值(從1～10)和AP數(shù)(從1～4)，觀察Eps和AP數(shù)量的最佳組合。圖5表明，Eps保持3～7之間，AP為3時(shí)，可以獲得最佳CRP值。

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

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

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

3 結(jié)束語

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

[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ī)收集的無線信號(hào)的自動(dòng)地點(diǎn)學(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—)，女，博士，主要研究方向：移動(dòng)通信、人機(jī)交互、情境感知等。李建武(1984—)，男，博士，主要研究方向：移動(dòng)通信、數(shù)據(jù)分析、網(wǎng)絡(luò)安全等。

TP274

A

1003-3114(2017)04-09-4