采用安卓系统的多模室内地图自动构建系统

许 强，赵 方，尚国强，朱沿旭，左 超

(1.北京邮电大学，北京 100876；2.北京航空航天大学电子信息工程学院，北京 100191；3总装备部工程设计研究总院，北京 100028)

1 背景介绍

当今世界，电子地图在人们的生活中越来越突显出愈发重要的辅助作用，现在室外地图构建技术已经逐渐趋于成熟，能够为用户提供精确的室外地图，而相关室外位置技术也层出不穷，丰富了人们的日常生活，带来极大的便利。

然而随着移动互联网的迅猛发展，但是室外位置相关技术已经不能完全满足人们的定位需求了，人们不仅仅满足于能获得在室外的精准定位，对室内精准定位提出了迫切需求，室内位置相关技术应用研究逐渐开始流行。

室内位置相关技术的核心就是室内定位，室内定位是指利用各种手持设备基于或者不基于室内已知精确位置基础设施，推导计算出当前设备在室内所处位置。

现今室内定位大部分是基于已知地图的，但是由于建筑建成时间、建筑所有权、建筑管理等原因，并不能获取有效即时室内地图，所以没有办法保证利用地图进行室内精准定位的方案顺利进行。

为了弥补室内地图的缺失，绘制室内地图是必不可少的步骤，但是当今常见的室内地图绘制通常需要使用很大的精力，例如基于达时间差(time difference of arrival，TDOA)的ARIADNE系统[1]，要首先部署室内射频信号发射点，然后进行海量采样，才能画出较精准的可用射频指纹信息图，这个绘制过程往往要耗费大量人力物力，有时甚至条件难以满足。

当完成室内距离、兴趣点(points of interests，POI)等数据大量采集后，还需要经过繁杂的处理、运算绘出室内定位可用的矢量地图，总的来说，从数据采集到室内地图绘制整个过程都是条件要求极高并且运算量很大的，难以符合快速获取室内地图的要求。

针对以上情况，提出一个众包的解决方案，拟利用群体无意识协作，降低对人力投入的依赖，利用无关人群手持设备中安装的相关软件，调用各种内置传感器采集信号数据，在手机获得网络链接时，随机地发送给服务器，从大量数据中提取出室内拓扑图，并将其应用到室内定位中。

2 相关工作

从各种角度看来，室内定位不可能独立于室内地图而存在，离开了室内地图，室内定位就像是无根之木，定位根本无从谈起。只有结合了室内地图，室内定位才有据可依，才变得有意义。同样，室内地图也需要用于室内定位才能彰显出它的作用，并且室内地图的获取同样也需要部分依赖于室内定位技术，室内定位和室内地图两者是相辅相成的一个整体。

现在较先进的绘制室内地图和室内定位使用的的数据很多都是来源于同样类型的信号数据，这些数据不仅可以利用到室内定位中，也同样可以利用到室内地图的构建绘制中。

对于室内定位来讲，近年来定位方案层出不穷，但都离不开以下几个方向：基于红外技术、基于超声波技术、基于蓝牙技术、基于射频识别技、基于无线保真(wireless fidelity，WiFi)相关技术、基于地磁、基于加速度传感器等。这些方向总结起来可以分为两大类，一类是基于信号传播模型的，另一类是基于信号指纹的[2]。

基于信号传播模型的室内定位，主要是首先在室内部署信标点，即已知信号发射源在地图上的位置坐标，将在某地点接收到的接收信号强度值(received signal strength，RSS)代入相应的信号传播模型中，计算推断出该点位置。较早的RSS相关传播模型有基于到达时间(time of arrival，TOA)的PinPoint系统，基于到TDOA的Cricket和基于到达角度(angle of arrival，AOA)的VOR系统等。

除此之外，较常用的信号传播模型有长距离路径衰减模型(long-distance path loss，LDPL)模型，它是利用测量到的RSS值根据射频(radio frequency，RF)传播距离模型来确定当前位置距离已知锚点(anchor point，AP)长度，然后通过AP点位置和长度来确定当前所处具体位置。但是很明显这种模型牺牲了室内复杂环境下的定位精度，换取降低初期大量人工采样的代价。虽然这种模型算法免去了人工采样的过程，但是需要初期部署AP点，并设定AP点精准坐标，这样才能利用已知精确位置AP点进行定位。EZ模型是基于LDPL模型的一种变型，它利用无线信号传播测算距离并利用遗传算法解决定位问题，EZ要根据在窗户或者建筑入口处随机获得全球定位系统(global positioning system，GPS)信号来确定位置的绝对坐标。

这种测算距离位置已知信号源长度的方法不仅仅可以用在室内定位，也可以用于室内地图绘制，但是这类方法要实现知道所有的信号源坐标，所以部署过之后，绘制室内地图的意义并不大。

对于基于信号指纹的室内定位来说，最重要的就是室内多种类型的兴趣点，兴趣点是指已知位置点或者可以通过分析某种数据的变化特征得出的点，可以在室内定位中用做AP点，常见的使用这些特征点指纹的方法是通过大量采集信号数据，分析得出相应特征点指纹，并将得出的指纹存入数据库，然后利用人当时所处地理位置信息与指纹匹配，进行定位。

最早使用基于指纹匹配技术的室内定位系统是RADAR[3]，RADAR是一个利用射频指纹(radio frequency identification devices，RFID)来进行用户室内定位和室内移动轨迹记录的系统。之后的一些室内定位系统有基于RADAR改进的Horus系统，使用室内RFID[4]定位的LANDMARC系统[5]，和利用室内WiFi指纹的WILL系统[2]。

这种采集信号指纹用作室内定位的思路，也同样适用于室内地图挖掘，而且比基于信号传播模型的方法更契合实际。通常在挖掘绘制室内地图的时候，室内的POI点也是可以利用的，最常见的思路就是采集到室内的各个AP之后，根据AP之间的连通关系画出室内连通图。

最初的室内地图绘制，主要是通过人工测量室内相关数据，再由相关人员利用绘图软件绘制地图。后来的利用定位技术的绘制地图方法也主要是基于这种最原始的思路，都是需要测量各种距离数据，然后利用数据绘制出地图来，例如现在苹果(Apple)公司推出的利用iBeacon方式绘制室内地图，这些方式都要预先部署基础设施，并且知道设施的具体位置，这样很难做到大规模绘制室内地图。

后来利用室内各种信号指纹挖掘室内地图，虽然在方法上更方便，但是还是存在缺点，例如仍然无法消除对人工部署已知基础设施的依赖，仍然需要安排一些人员进行数据采集工作，并且当前的地图绘制方法很难找到一种低消耗且高质量的思路。

鉴于以往地图绘制技术通常需要有目的性的部署相关基础设施，并且需要专门人员在建筑内采集数据，导致绘制成本较高，并且有些前提条件不能很好的满足，所以为了避免这些短处，本系统主要是基于众包的方式采集数据，众包主要是指利用人群的无意识协作，即利用装在很多人手机上软件的附加功能，在平时用户手持手机活动的时候开始采集相关数据，并临时存储在手机上。当手机获取网络访问的时候，将采集到的数据传输到服务器端。这种模式大大地降低了采数据开销，能够将数据采集的任务分配给很多人共同完成。而绘制地图主要是基于WiFi基础设施，以智能手机为辅助，采集多种室内地理信息特征点，挖掘室内地图并利用得到的地图进行室内定位。

3 方法设计

当前在做室内定位方面，大部分是需要基于已知地图的，在地图未知的情况下，进行室内定位非常艰难，而本研究主旨就是利用WiFi指纹以及其他辅助AP挖掘室内拓扑结构、构建室内地图，为进一步室内定位提供基础。

本文提出一种C/S(Client+Server)架构的系统来实现室内拓扑图绘制的方案，基于安卓(Android)系统的客户端主要负责利用手机内自带的各类传感器，收集目标数据并对数据进行初步处理，将其保存在手机本地。当手机偶然获得网络访问的时候，将存储的数据发送到服务器上，在服务器上，对采集到的数据进行聚类分析等后续处理，并挖掘出室内拓扑结构，绘制室内地图。

图1 系统结构图

3.1 客户端设计

根据前人在基于信号指纹的室内定位技术的卓越研究成果，主要基于计步器[6]，采集室内WiFi指纹、用加速度传感器采集楼梯电梯以及利用陀螺仪采集转弯点等地理位置信息特征点。首先经过粗粒度处理之后临时存储在用户手机上，然后当手机获得网络访问的时候，将数据文件发送给服务器端。

以下介绍使用的室内地理信息特征点。

3.1.1 WiFi-MARK

采集WiFi数据的时候，并不需要知道WiFi信号源的具体位置，亦即不需要事先部署满足需要的WIFI设施，而是只需要利用室内已存在的基础设施即可。

图2 WiFi空间信号强度示意图

由于WiFi传播信号如图2，在三维空间中WiFi信号强度相同的空间可以构成一个球面，而对于水平的楼层来说则是一个圆，行走过程的轨迹相当于是“等WiFi强度”圆形区域的一条割线，根据几何知识可知，在这条割线的正中间是WiFi信号最强的点，如图3所示，在采集数据的时候将其记录下来，作为一个WiFi标记，称作WiFi-PEAK。WiFi-PEAK记录格式为：

WP={RSSID，RSSI，wPosition，A}；

其中RSSID指该点接收到的WIFI信号的ID，RSSI代表对应的RSSID信号强度，wPosition是指该点基于计步器的相对位置，A是指该点接收到的临近WiFi接入点集合，用来分辨当前点和RSSID的相对位置。

图3 WiFi信号强度变化

之所以要采用WiFi信号最强点而不是采集普通WiFi信号用作为WiFi指纹是因为：由于设备差异性、设备位置不同和采样时间变化，采集到的WiFi信号强度并不相同，甚至还有相对较大的误差，这些误差给生成WiFi指纹的过程带来很大麻烦，而采集信号最强点则避免了这些麻烦[8]。

使用滑动窗口的方式采集WiFi信号最强点，亦即在一条没有拐弯的路径上，使用7个窗口的滑动窗口机制，识别出信号最强点。

3.1.2 电梯楼梯

利用手机中自带的加速度传感器，能够测量记录手机的实时重力读数。根据重力读数以及在电梯、扶梯和楼梯处的重力变化特征，如图3.4所示，能识别出相应的电梯扶梯和楼梯，这些地点通过走廊连接入室内地图[9]。

图4 电梯、楼梯和正常行走时的重力读数区别

3.1.3 转弯点

在常见的室内定位中，转弯点通常是无用的，有些甚至将其视作产生噪声干扰的来源之一，但是在本系统中，通过记录手机中自带的陀螺仪读数变化，识别出转弯点(cornerpoint，CP)，并将其记录下来。识别过程也使用滑动窗口机制，转弯点记录格式如下：

CP={bDirection，aDirection，pPosition}；

其中bDirection是指在转弯前的前进方向，aDirection是转弯之后的前进方向，pPosition是指由计步器所得的转弯点的相对位置。转弯点可以用在约束两段直的走廊路径上，链接两个不同方向的走廊。

3.1.4 门

由以上的点可以画出走廊的形状，为了绘制室内地图还需要房间的形状。而房间和走廊的连接点是门，同样在绘制地图的时候，也可以通过门来将室内数据和走廊数据联系起来。

门是跟走廊直接连接的，根据采集到的数据分析，其中较大概率的情况下，在门的位置的地方会有静止并且方向不规则变化的特征，根据这个概率性特征以及判断是否与走廊紧密相连，可以确定出门所在位置。

3.1.5 室内静止点

房间在室内地图中是很重要的一部分，在绘制室内地图的过程中，不仅要绘制出房间的大致形状，并且还要将相邻房间区分出来。在大多数情况下，人们在房间内通常会有较长时间的静止(例如10 min以上的静止)，在设计的系统中，当手机长时间静止的话，将其认为是在室内，并记录该点位置及相关信息，相关信息主要是指在该点接收到的部分WiFi信号的RSSID以及其对应强度，其中部分是指仅记录RSS>-40以及RSS<-80的信号特征，由于每个房间是墙壁封闭的，所以每个房间里的点采集到的该特征是有较大差别的，通过这个特征将不同房间的点区分出来，并标示出房间[10]。

3.2 服务器端设计

将服务器设计为迭代式的，在服务器端将采集到的数据梳理分类，利用K-means算法，剔除噪声点，将采集到的室内WiFi-PEAK、楼梯电梯点和转弯点数据进行聚类，得到相对应的可用AP，通过转弯点的约束走廊方向，连接分段走廊，并且加入AP点即可拟合出较为精确的走廊地图，根据采集到的室内静止点和从门到室内静止点之间的行走轨迹，可以画出房间的形状，并且通过室内静止点的数据可以区分出房间，利用门的点将房间和走廊连接起来就可以得到房间和走廊的完整地图。

接下来可利用手机在窗口或者门口偶然获得的GPS信号，以修正室内相关地理信息点在地球坐标系中的精确位置，最终获得室内外无缝衔接的地图。

4 系统实现

针对上一节定义的需要采集的点，设计出的客户端核心代码结构如下：

Algorithm1 Anchor points recognition

Scanresult=Wifimanager.ScanWifi()；//扫描WiFi信号

Δdegree=| oldDegree - curDegree |；//陀螺仪角度变化

if(0<Δdegree<40){

if(Scanresult.slidewindow.hasMidPeak)

Write(scanresult.peak)；//滑动窗口得出WIFI-PEAK

}else if(Δdegree>40 &&Δdegree<320){

if(preSteps>3 && postSteps>3)

Write(turning)；//得到转弯点

if(threshold0

Write(door)；//得到门的位置

}

if(statictime>threshold3)

write(roompoint)；//得到室内静止点

if(accellorator.patten==ELEVATOR){//根据加速度传感器的变化得到相应的电梯和楼梯的位置

write(elevator)；

}else if(accellorator.patten==STAIR){

Write(stair)；

}

将采集到的点存储在移动终端本地，当获得网络的时候随机将数据文件发送到服务器端，服务器接收到数据之后，将接收到的数据进行聚类，并多次迭代。聚类的相关伪码如下：

Algorithm2 Anchor points clustering

//数据读取

read(wifidata)；

read(turningdata)；

read(stepdata)；

read(elevatordata)；

read(stairdata)；

//聚类处理

line[1]=kmeans(firststep，'sqEuclidean')；//起点

for i=1：wifidata.length //WIFI-PEAK

record[wifidata[i].mac].insert(wifidata[i].position)；

for i=1：record.length

line[i+1]=kmeans(record[i]，'sqEuclidean')；

line[i]=kmeans(turndata，'sqEuclidean')；//转弯点

line[i+1]=kmeans(stairdata，'sqEuclidean')；

line[i]=kmeans(elevatordata，'sqEuclidean')；//电梯

//拟合处理

polyfit(line.x，line.y)；

根据以上系统实现，将客户端安装在不同型号的手机上(MEIZU MX，MEIZU MX3，SAMSUNG NOTE2，htc one)并在北京邮电大学明光楼内采集数据，得到结果如下图：

图5 数据分类聚类以及拟合直线

与明光楼的室内实际图对比如下：

以上数据是总共行走了50次之后得到的路径，可以看出已经与实际情况相差无几。

图6 走廊图放在实际地图内

5 结束语

从实验结果来看，本系统在精确度上是值得认可的，在不需要事先布置任何先验基础设施的情况下，可以无障碍的获取室内可用的地理信息特征点，并将其转化为AP点，并用来绘制室内地图。

在数据采集的过程中，如果采集数据的程序一直运行的话，陀螺仪读数——即角度变化读数累积误差将会变得大到不能接受，所以必须要对陀螺仪读数过一段时间内进行重置校正。

门的识别在当前研究领域都是一个比较困难的问题，在本文中采取的方法也只是利用一定概率出现某种特征的方法判别门的位置，这是一个可以继续研究的方向。

[1] JI Yi-ming，BIAZ S，PANDEY S，et al.ARIADNE：A Dynamic Indoor Signal Map Construction and Localization System[C]//Proceedings of the 4th International Conference on Mobile Systems，Applications and Services.NY：ACM，2006：151-164.

[2] WU Chen-shu，YANG Zheng，LIU Yun-hao，et al.WILL：Wireless Indoor Localization without Site Survey[C]//Proceedings of INFOCOM 2012.Orlando：IEEE，2013：839-848.

[3] BAHL P，PADMANABHAN V N .RADAR：An In-building RF-based User Location and Tracking System[EB/OL].[2014-08-15].http：//research.microsoft.com/en-us/people/padmanab/infocom2000.pdf.

[4] 王小辉，汪云甲，张伟.基于RFID的室内定位技术评述[J].传感器与微系统，2009，28(2)：1-3+7.

[5] NI L M，LIU Yun-hao，LAU Y C，et al.LANDMARC：Indoor Location Sensing Using Active RFID[EB/OL].[2014-08-15].http：//www.cs.ust.hk/～liu/Landmarc.pdf.

[6] ALZANTOT M，YOUSSEF M.UPTIME：Ubiquitous Pedestrian Tracking Using Mobile Phones[C]//Proceedings of Wireless Communications and Networking Conference(WCNC)，Shanghai：IEEE，2012：3204-3209.

[7] CHINTALAPUDI K，IYER A P，PADMANABHAN V N.PADMANABHAN.Indoor Localization without the Pain[EB/OL].[2014-08-15].http：//research.microsoft.com/pubs/135721/ez-mobicom.pdf.

[8] SHEN Guo-bin，CHENG Zhuo，ZHANG Pei-chao，et al.Walkie-markie：Indoor Pathway Mapping Made Easy[C]//Proceedings of the 10th USENIX Conference on Networked Systems Design and Implementation.CA：USENIX Association，2013：85-98.

[9] WANG Feng，LUO Hai-yong，LI Zhao-hui，et al.Activity-based Smartphone-oriented Landmark Identification for Localization[C]//Proceedings of Principle and Application Progress in Location-based Services.Switzerland：Springer International Publishing，2014：59-71.

[10] ERIC T，ZAKHOR A.Floor Plan Generation and Room Labeling of Indoor Environments from Laser Range Data[C]//Proceedings of the 10th International Joint Conference on Computer Vision，Imaging and Computer Graphics Theory and Applications.Lisbon：GRAPP，2014：22-33.