基于CSI众包数据的室内路径生成算法

丁 宇，吴楚田

(1.太原理工大学 计算机科学与技术学院，太原 030024；2.太原旅游职业学院 现代教育信息中心，太原 030032)

目前，由于智能手机的迅速普及和室内定位技术的发展，室内基于位置服务(location based service,LBS)应用得到了较多的关注。然而发展室内LBS的先决条件是提供广泛覆盖、易于解释、可呈现用户位置的室内平面图，但正是目前十分有限的数字化的室内平面图限制了室内LBS的普及。

现在越来越多的研究实现了室内平面图的自动构建，这在移动计算中属于相对较新的研究问题。其中无线信息和惯性感应数据的结合是主要研究方法。CROWDLNSIDE[1]和SMARTSLAM[2]都是利用惯性数据使用Dead Reckoning算法估计人的日常行动轨迹并加以简单的去噪和直线校正，累计叠加以覆盖可通行区域来实现室内平面图的构建。这些方法通过智能手机来获取惯性数据，虽然提高了估计平面图的可行性，但由于手机传感器精度受限，再加上Dead Reckoning算法本身的缺陷，致使构建的平面图精度较低。JIGSAW[3]要求使用者执行两个拍照任务来获取地标图片，通过三维重建(structure from motion，SFM)技术获取地标信息来校正惯性数据。JIANG et al[4]在惯性数据的基础上对RSS指纹众包进行了复杂的分析，而CALL[5]则辅助了自行获取的AP位置信息来进行校正。室内导航系统IMOON[6]利用照片众包(Crowdsourcing)构建初始3D模型后，使用惯性数据和RSS指纹从模型中提取障碍物，留下可通行区域来编译导航网络。以上方法对惯性数据进行了各个方面的校正，得到了更精细的平面图的同时却增加了整体的复杂度。因此，寻找更高效精准的平面图构建方法具有十分重要的意义。

不同于传统的室内平面图绘制方法，笔者抛弃了精度受限的惯性数据和复杂的校正方法，而是直接使用来自WIFI基础设施的信道状态信息(channel state information,CSI)来构建以路径为基础的平面图。构建过程中对文献[7]的角落形状检测法进行了改进，并应用于检测拐弯路径；在对所有的众包数据进行标记和优化处理后，快速学习了路径连接关系和路径长度，并依此分析出用户的行走路径形状，获得了结构完整的室内路径平面图，最高精度可达90.1%；其中每条路径平均只使用20条轨迹序列即可进行整合，较于目前的构建工作要简单高效。整个构建过程不需要通过其他手段获取额外的信息，提高了自动构建室内平面图的灵活性，构建结果可用性较高，可应用于导航、定位等基础室内LBS应用。

1 预备知识

基于OFDM技术的IEEE 802.11n标准提供了这种叫做CSI的RF信道特性。它包含了子载波上每一个收发天线间的信道信息，利用现成的IEEE 802.11n标准的Intel 5300网卡以及微调过的驱动程序，即可获得CSI形式的采样版信道频率响应值(channel frequency response，CFR)，格式如下：

H=[H(f1),H(f2),…,H(fN)]T,
i∈[1,30] .

(1)

每个CSI刻画了一个子载波的幅度和相位信息：

H(fi)=‖H(fi)‖ejsin∠H(fi).

(2)

式中：H(fi)是中心频率为fi的子载波的CSI；∠H(fi)代表相位[8]。通过恰当的信号处理技术，CSI可以对不同的传播环境呈现不同的子载波幅度和相位特征，而且相同的传播环境下CSI值可保持相对稳定。

2 算法流程

目前室内无线网络普及程度较高，几乎每个房间都有一个无线接入点(access point，AP)，因此利用Wi-Fi基础设施进行室内环境感应是十分可行的。只需要用户在室内行走时使用移动设备连接到网络，并记录用户进入室内之前到走出室内之后的GPS信号来标记一段轨迹的开始和结束，最后通过分析众多包含不同源的CSI序列的行走轨迹来构建平面图。从用户走进室内之前到走出室内后获得GPS信号标记开始和结束，获取来自不同AP的CSI序列来构建平面图。图1为算法的流程图，其构建过程主要分为4部分。

图1 室内路径生成算法流程图Fig.1 Flowchart of Indoor path plan generation algorithm

1) 拐点识别算法：通过匹配在不同走廊形状上行走测得的CSI变化率的变化特征来识别拐点，区分直线行走和拐弯序列并对拐点进行标记；

2) 峰值检测方法：在单个轨迹的序列中寻找每一段AP序列的峰值，并对峰值出现时间进行标记；

3) 轨迹序列拼接算法：利用AP序列和拐点序列的相似性进行分组和拼接，分析出众包数据中各路径之间的连接关系得到邻接图G；

4) 分段长度估计算法：将标记点的时间差序列段进行K-means聚类，取簇中心作为行走的时间间隔来估计路径长度。

3 算法实现

该平面图构建方法主要分为对众包CSI序列的逐个标记处理和学习路径关系两个阶段。以下将详细阐述算法的实现过程。

3.1 CSI序列处理

3.1.1 拐点识别分析

根据FILA中的CSI的路径损耗模型[11]可知：

(3)

式中：c，f0是波速和中心频率；n是路径损耗指数，在室内环境中一般是2～4；σ是环境因子，这些均为常数，因此行走过程中会改变CSI值的因素只有距离和阻碍物的变化。而阻碍物如墙、家居一般分布在墙角，后续识别拐角和峰值等方法都可以抵抗这种衰减。因此导致CSI产生变化的主要因素是d，且它们互成反比。所以用户以不同形状的轨迹匀速经过AP时，收发距离的变化为：

(4)

式中：d0是初始位置的收发距离。在本文中，不同于文献[7]中的三种角落形状，要识别的形状有直角、直线、相反直角的特征，将直角和反直角判断拐弯。

首先，参照文献[7]中CSI变化率的提取得到如图2(a)的3种路径形状的变化率R1.

通过比较3个R1随时间的变化，发现反直角的R1变化与直线相似，均为逐渐递减但递减速度不同。因此想要区分反直角和直线两种情况[7]的方法并不适用。通过二次提取CSI变化率的变化速率R2，变化曲线如图2(b)，发现R2在拐弯情况下会有一个陡峭的波动，而直线的变化则十分缓慢，因此可利用波动幅度来区分直线和直角轨迹。通过训练多组拐弯数据得到适当的幅度阈值τ，波动幅度超过(-τ,τ)则视为拐弯序列。通过判断波动幅度的正负还可以确定直角还是相反直角。最后将波动的峰值点标记为拐点T.

由于理论模型中的函数是连续的，而实验采集的数据是离散值，并且室内环境下噪音干扰较多。因此我们用中值滤波对CSI数据进行去噪，然后拟合实验数据并用拟合表达式来直接估计其变化率。

3.1.2 峰值检测

无线信号的传播与传输距离有关。当用户手持移动设备在走廊行走时，会路过一个收发距离最短的地方，在这里走廊与AP会有一个的垂直距离，此点叫做AP在走廊上的对应位置。理论上讲在这一位置上接收到该AP的信号强度应当是最强的，因此我们计划使用高斯平滑后CSI序列，寻找到曲线的峰值并进行标记，以此确定AP对应位置出现的时刻。

判断序列为直线行走时，需要寻找每一段AP序列的全局波峰，即峰值必须大于前后2个相邻时间窗的CSI值。如A点到B点距离48 m，AP1，AP2，AP3的对应位置分别在8，24，38 m处；用户经过两点后获取了长达50 s的CSI序列如图3所示，通过计算分别在8.2，26，43.4 s时到达峰值，依次记录为3个AP的到达时间t1，t2，t3，标记误差不超过1 m.不同于原始数据的随机出现的峰值，使用高斯平滑后的CSI曲线获取的峰值更接近真实的AP对应位置。判断某AP的序列为拐角后，拐弯轨迹可能会因为测量时间较长，在拐弯之前和之后会经过两条交叉路径上的对应位置，因此会出现两个波峰max1，max2，都需要标记。标记APi在走廊上的对应点出现的时间t的同时，我们还要记录下APi的峰值Pks，将两者作为APi的属性来标记序列中的AP.

图3 一段CSI序列样本Fig.3 A sample of CSI sequence

3.2 路径关系学习

通过上一节对轨迹序列的拐点和峰值的时间戳节点进行标记后，将一个人的行走轨迹用一个二元组表示：Pi={BAPx,BAPy,T1,…BAPz,…,Tj,…}.其中，BAPx=(Pks,ti)是对不同接入点的标记，Tj=(BAPi,Pks,tj)是拐点的标记，识别出Ti的CSI值来源于BAPi，ti是顺序到达时间。T将路径分割为多个单元段。

本节将介绍通过序列拼接算法和长度估计法将众包数据进行整合，学习到路径关系的详细过程。

3.2.1 序列拼接

同一室内环境下，众包轨迹之间必定会有部分重合，利用这些重合段可以在拐点识别率有限的情况下，来补偿同拐点的不同路径的识别结果，而且重点是要利用这些部分重复序列实现序列拼接。

1) 分段轨迹序列Pi：用Pi经过的所有标记拐点T来将其划分为格式为(h1,T,h2)的三元组Path;h1,h2为经过拐点T的前后两段AP序列，序列中的AP按经过顺序排列。h1是入序列，h2是出序列。一次方法对所有的中报数据进行处理，得到数个Path数组。

2) 对Path进行分组，比较T的属性BAPi是否相同，且Pks值相似度是否大于60%，满足条件则归为同一Turn组，一组中的h代表从同一个拐点可达的路径。

3) 将同组Path进行归类组合，目标是为以环形链表的形式Turn(h1,h2,h3,h4)表示的拐点路径组赋值，其中相邻h是拐弯关系，相隔一位是直走关系。Path数组中入序列和出序列是拐弯关系，因此对同一组中每个Path的hi进行KMP匹配，当入序列匹配成功、出序列失败，则说明两个出序列是直走关系，需相隔放置，而拐弯关系相邻放置，所以先放置入序列为h1，其他两个分别为h4,h2；依此类推直到不再有新的赋值。

4) 对Turn的赋值结果进行验证：如果4个h非空且无重复，则确认为四叉路口；一个h为空，为三叉路；两个为空则为二叉路；有重复则赋值出错。

5) 将所有Turn中的h序列进行两两比较，如果以相反序列匹配成功，则判断两Turn代表的T节点相邻接，用邻接矩阵A来表示拐点T之间的邻接关系；如果h没有匹配到拐点，那么该h序列的末端节点APi也作为邻接矩阵A的一个节点，并与自己归属的T相邻接。将A表示为无向图G=(E,U)，拐点T和没有连接T的h序列末位AP的ti均定义为图G的顶点U，h为连接边。

3.2.2 长度估计

由于先前标记了轨迹序列中各节点的到达时间ti，因此最直接的长度估计方法是知道走速v和达时间差|ti-ti-1|来获得。然而，人与人的走路速度和行为习惯各不相同，直接平均会影响精度。为解决这个问题，使用K-means聚类来避免离群数据对长度估计的干扰。

通过上一节的走廊拼接，将每一个拐点之间的AP序列视为单元段，以所有众包轨迹数据在每个单元段的时间序列差(|tN-tN-1|,…,|t1-t2|)作为输入来执行K-means聚类。若有m条轨迹经过同一单元段，进行m(n-1)的K-means聚类，k=1，最后以输出簇的中心点作为穿过单元段的时间差序列。聚类后的数据剔除了离群点，保证了每一段时间差都适用于大部分情况。提前测量一段已知距离来估计人在该模型下的平均速度为v，然后与聚类后的时间间隔相乘得到节点间的穿越距离S.将单元段的长度作为h的属性，赋值给图G，既可用于接下来的平面路径图绘制。

3.2.3 生成平面图

平面图构造旨在以对人类观察者视觉上更直观的方式将图G在平面上显示。本文绘图时参考LUO et al[12]采用的平面图可视化算法，并加以长度信息进行优化。第一步用深度优先搜索(DFS)遍历图G，遍历过程中会生成一个生成树。第二步用Tarjan算法求出每一个顶点的DFN和LOW值，记录深度优先遍历过程中的每个顶点的父节点，遍历所有点的LOW,DFN来寻找桥，并将其用于路径寻找算法搜索环路。最后用平面嵌入算法画出平面路径图。该算法有两个主要限制：每个边必须是直线，夹角角度必须是直角。我们首先画出具有四个边缘的环路，其次非环路的路径。最终得到一幅路径关系草图，简单的将顶点和边缘的逻辑关系呈现到了平面上的。根据上一节得出的单元路径的长度，来对各节点之间的距离进行调整，使得平面图整体达到更好的精度。

4 实验评估

4.1 试验部署

为了评估系统的性能，课题组招募了10名学生在某高校的教学楼和计算机学院楼内采集了一个月的无线数据，总共包含了来自42个AP的251条CSI序列。以路由器的Mac地址来唯一标记一个AP，并用配有Intel 5300 NIC的3.6 GHz Intel(R)Pentium 4 CPU 4GB RAM笔记本作为接收器。所有的路由器以IEEE 802.11n AP模式工作。接收机具有3个工作天线，在实验过程中，接收机以每秒100个数据包的速率从AP连续ping数据包。所有的数据处理是在3.60 GHz Intel(R)Core(TM)i7-4790 CPU 4G RAM桌面上的Matlab R2012a.选择FILA的CSI传播模型来模拟富含多路径效应的室内环境下的信号传播来提取拐点特征。

4.2 结果分析

评估了拐点识别方法的准确性、聚类方法对距离估计准确性的影响以及平面图的精度。

4.2.1 拐点估计结果

分析了为CSI变化率变化幅度设定的阈值τ对识别结果的影响，图4的(a)、(b)分别显示了不同τ的误判率(FPR)和漏报率(FNR)。从图中可以看出：τ设置过高，直线检测的FPR较高，直角和反直角两种情况容易被识别成直线；τ设置过低，直线检测的FNR过高，轻微浮动的直行序列被排除，识别成了直角或反直角。因此τ为0.4是最理想情况。

图4 对拐角检测识别率的评估Fig.4 Evaluation of corner detection recognition rate

为了与文献[7]的角落形状检测法进行比较，将两种方法时应用于我们的试验数据中，得出3种路径形状的识别率结果如图4(c)所示。图中，左边是角落形状检测方法的识别率，右边是拐角检测方法的识别率，可以看出我们的方法明显降低了直线和相反直角的混淆率，3种形状识别率达到了94%，89%，92%.

4.2.2 距离估计误差

整个算法中，距离精度至关重要，而峰值检测标记AP和聚类时间段两部分起到了精度的主要决定作用。首先我们记录了穿越两个节点的真实时间差来分析峰值检测算法的效果。将CALL[5]的峰值检测方法与本文相比较，画出CDF图如图5(a)所示。CALL设置时间窗求CSI平均值来划分CSI序列，将最大值标记为AP位置，灰线效果明显差于使用高斯平滑标记峰值的黑线，笔者的方法80%的误差在1.5 s内，要比CALL准确两倍。时间窗会而影响时间分辨率，使得记录时间与现实有一定的偏差，而高斯平滑曲线则能更好的描述CSI的变化。

图5 距离估计误差的累积分布图Fig.5 The cumulative distribution of the distance estimated error

通过测量AP对应位置以及拐点位置之间的距离来评估聚类时间段后的距离估计误差。如图5(b)描述了K-means聚类与平均时间段后估计的距离误差CDF。显而易见，聚类后80%的距离误差在1.6 m以内，要远好于直接平均，这样的结果足以准确的估计平面图中的路径长度了。

4.2.3 生成平面图

该系统构建的平面图是一个路径逻辑关系图，将输出的路径结构图覆盖到真实的平面图上进行对比。如图6所示，绝大部分通行路径都构建了出来，连接关系也基本无误。

图6 学院楼2楼的路径平面图构建结果Fig.6 A constructed path plan sample of CS building's 2 floor

通过对准两幅图的中心点和方向来实现最大程度的重叠，估计了它与地面真实情况的接近程度。计算结果呈现在表1中，其中Hn是精确度和找召回率的调和平均数。该方法在实验环境中达到了最高86.3%的精度，94.2%的查全率以及90.1%的Hn，这在一定程度上体现了仅利用来自于无线路由的CSI信息同样可以得到精度有保障的室内平面图。

表1 平面图精度估计参数Table 1 Accuracy evaluate about floor paln %

5 总结

自动构建数字化室内平面图是当前基于位置服务的发展必须要解决的关键技术之一。本文提出的构建方法仅通过利用来自Wi-Fi基础设施的信道状态，就绘制出一条结构完整、可应用于室内LBS的室内平面图，大幅度提高了构建效率和灵活性。该算法对于Wi-Fi噪声和遮蔽效应变化是鲁棒的，实验结果也验证了其设计的优势。通过动作识别和特征提取，进而分析房间性质，是下一步的研究方向。

[1] ALZANTOT M,YOUSSEF M.CrowdInside:automatic construction of indoor floorplans[J].Eprint Arxiv,2012:99-108.

[2] SHIN H,CHON Y,CHA H.Unsupervised construction of an indoor floor plan using a smartphone[J].IEEE Trans Systems,Man,and Cybernetics,2012:889-898.

[3] GAO R,ZHAO M,YE T,et al.Jigsaw:indoor floor plan reconstruction via mobile crowdsensing[C]∥ACM.International Conference on Mobile Computing and NETWORKING.2014:249-260.

[4] JIANG Y,XIANG Y,PAN X,et al.Hallway based automatic indoor floorplan construction using room fingerprints[C]∥ACM.International Joint Conference on Pervasive and Ubiquitous Computing.ACM,2013:315-324.

[5] ABADLEH A,HAN S,HYUN S J,et al.Construction of indoor floor plan and localization[J].Wireless Networks,2016,22(1):175-191.

[6] DONG J,XIAO Y,NOREIKIS M,et al.IMoon:using smartphones for image-based indoor navigation[C]∥The,ACM Conference on Embedded Networked Sensor Systems.ACM,2015:85-97.

[7] WANG Y,ZHOU Z,WU K.Sensor-free corner shape detection by wireless networks[C]∥IEEE.International Conference on Parallel and Distributed Systems.IEEE,2015:306-312.

[8] 朱海,肖甫,孙力娟,等.基于信道状态信息的WiFi环境感知技术[J].南京邮电大学学报(自然科学版),2016,36(1):94-103.

ZHU H,XIAO F,SUN L J,et al.CSI-based wifi environment sensing[J].Journal of Nanjing University of Posts and Telecommunications(Natural Science),2016,36(1):94-103.

[9] ZHOU Z,WU C,YANG Z,et al.Sensorless sensing with WiFi[J].Tsinghua Science & Technology,2015,20(1):1-6.

[10] ZHANG C,LI F,LUO J,et al.iLocScan:harnessing multipath for simultaneous indoor source localization and space scanning[C]∥ACM.Conference on Embedded Networked Sensor Systems.ACM,2014:91-104.

[11] XIAO J,YI Y,et al.FILA:Fine-grained indoor localization[J].Proceedings-IEEE INFOCOM,2012,131(5):2210-2218.

[12] LUO X,WONG A,ZHOU M,et al.Automatic floor plan construction for indoor localization[C]∥10th Advanced International Conference on Telecommunications.Paris：2014.