基于手机收集的无线信号的自动地点学习方法

许亚倩，李建武

(中国电子信息产业发展研究院 网络空间研究所，北京 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 基于聚类算法的自动地点学习方法

本文介绍的基于聚类算法的自动地点学习方法是一种“无监督”的学习方法。“无监督”是指该方法使用的无线信号强度标示符是手机在用户日常生活中自动收集的，不需要用户的额外输入和操作。手机自动收集并记录无线信号强度标示符后，对该数据进行处理，自动发现用户停留超过一段时间(例如，10 min)的地点，学习这些地点的无线指纹，存储于本地数据库中。当用户重新访问这些学习过的地点时，手机自动收集的无线信号强度标示符与本地数据库中的无线指纹对比，识别出用户当前所处地点。

1.1 基于密度的聚类算法

基于密度的聚类算法的基本思想是挖掘数据高密度的聚类，聚类即密度高的数据点的集合。在本文提到的自动地点学习方法中，手机自动收集的数据是信号强度表示符(RSSI)，一个RSSI即为一个数据点。基于密度的聚类算法能够自动挖掘RSSI密度较高的簇，每个簇代表一个对用户有意义的地点。为了发现簇，基于密度的聚类算法使用邻域和邻域密度的概念，指定了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