基于机会性位置校正的低功耗城市众包导航

穆运峰，王 林，刘文远

（燕山大学 信息科学与工程学院，河北 秦皇岛066004）

0 引 言

众包导航是将获取位置和规划移动路径的计算由移动互联［1］用户分布式完成的一类导航服务，可应用于城市楼群密集区域人员移动引导、文化博览园内观光导游、园林公园内寻人服务等［2］。目前最常用的室外导航技术是全球卫星定位 系 统 （global positioning system，GPS）。GPS 获取位置精度可满足户外导航需求，但其能耗是不可接收的。对此，文献 ［3］采用GPS、WiFi、全球移动通信系统（global system of mobile communication，GSM）等 多 种 传感器组合定位，延长续航时间；文献 ［4］通过降低GPS的采样频率延长电池的生命周期；文献 ［5］提出在高楼林立城区和植被茂密的林区，使用WiFi在GPS失效的位置辅助定位；文献 ［6］提出A－GPS方法，结合网络基站信息和GPS信息对移动台进行定位，基站辅助定位。基于位置的服务 （LBS）在精度和能耗上的权衡，使得陆基无线电导航 （例如WiFi、GSM）得到日益重视。文献 ［7］采用连接室外无线接入点，通过旋转寻找RSSI信号最强的方向；文献 ［8］利用GSM 进行初定位，并通过物理环境确定用户的逻辑位置；文献 ［9］提出机会性的社交网络，利用机会性的遇见信标进行重新定位。然而，为了满足用户精度的要求，用户需要在室外大规模地部署信标。针对现有工作存在的问题，本文设计一种基于机会性位置校正的低功耗城市众包导航系iWALK。与传统导航技术需要专业设备或大规模锚节点部署不同，该系统利用手机自带的加速度计和电子罗盘测量移动用户行走的位移和方向，用户可以在起点和终点分别开启GPS，获得位置标记，来确定轨迹长度。与GPS全球定位系统相比，iWALK 在降低能耗的同时能实现众包导航服务。

1 iWALK 系统架构

图1是基于机会性校正众包导航系统iWALK 的体系结构。服务开启时，用户通过GPS全球定位系统获得初始位置的经、纬度坐标，并根据用户的体重和身高获得步长，实时采集加速度计传感器的读数，对Z 方向的加速度数值进行步态检测，如检测到是有效步，则计步，通过步长乘以步数获得用户的行走位移；同时读取电子罗盘的读数，电子罗盘读数提供行走的方向。其中，距离用米表示，方向用顺时针偏离磁北的角度表示。（RSSI＿i，SHI＿i，ORI＿i）三元组捕获用户的运动模式，称为用户的 “运动指纹”，其中RSSI＿i，SHI＿i，ORI＿i分别表示i时刻的GSM 信号接收强度、位移长度、移动方向。运动指纹被定期的传送给服务器。

图1 众包导航系统的体系结构

服务器使用航迹推算方法生成行走轨迹，对行走轨迹置反后得到用户的返回导航路径。航迹推算方法依赖自包含的惯导传感器主动定位，能够随时提供连续的行人位置信息。由于行人行走的行为具有随机性和多变性，在步数、步长以及航向3个因素中都存在误差，使用户的行走轨迹严重偏离用户的实际轨迹，本文中利用音频信号检测相遇，机会性的获取开启GPS 设备的用户位置信息进行位置校正，最后采用漂移消除，进一步减小轨迹映射的误差。

2 机会性位置校正

目前智能手机大多数都已经包含了多种传感器，借助它们自带的传感器进行开发，不仅拓展了行人导航定位的使用范围，也使得室外定位更加灵活。但在实际运用中仍然存在许多问题，例如加速度计噪声导致计算用户运动位移产生错误［6］、电子罗盘噪声导致记录用户运动方向存在偏差等。为了解决此类问题，本文利用机会性的相遇事件来纠正这些错误。

2.1 相遇检测

对于检测相遇，系统应该能够准确的捕捉到相遇事件的发生，检测机制必须十分敏锐。现有的工作是基于蓝牙机制来发现邻近的用户［10］，但蓝牙机制对于发现短暂的相遇反应太慢，实验结果表明50%的相遇事件蓝牙是检测不到的，所以该方法不适用。文献 ［9］中作者提出了采用音频信号检测相遇，并在不同的噪声情况下进行了音频检测实验，证明利用音频信号处理实际的相遇是可行的。利用自组织网络机制GSM 全球移动通信系统，采用文献 ［9］中的检测方法，我们在喧闹的步行街上进行了音频实验，其中手机距离为1 m。实验结果如图2 所示，该音调频带（虚线表示）在2500 Hz～3000 Hz之间，而语音信号在1000Hz左右，所以能够很好的区分开来。

图2 音频检测

2.2 用户位置校正

用户位置校正［11］建立在音频检测的基础之上。当手机检测到两个用户相遇时，根据用户接收到的GSM 基站指纹来判断两个用户位置的相似度，这里采用Tanimoto 系数法，用来测量两个指纹之间的相似。和余弦相似度相比，它需要更少的共享信标，定义如下

式中：F1——用户扫描到的GSM 指纹数据，F2——检测到遇见的用户扫描到的GSM 指纹数据，相似值T（F1，F2）越大说明两个用户间相似程度越大，距离越近。另外，用户同一时间可能会检测到遇见多个用户，此时选取其中相似值最大的且已知GPS 的用户的位置作为该用户的地理位置。

2.3 用户轨迹漂移消除

用户位置纠正是用户轨迹的漂移消除的前提。用户在初始时刻tr1获得自己的经、纬度坐标，当下一个时刻tr2用户遇见已知经、纬度坐标的用户时，进行位置校正，此时能够计算出从估计位置到校正位置需要纠正的向量大小，标记纠正向量为。由于tr2时刻用户的位置是正确的，所以整个过程的漂移累计只有在时间tr1－tr2内，基于这一观察，可以纠正两个连续校正位置间的轨迹，称之为 “漂移消除”。

式中：L（t）——用户在时间t时刻的位置。漂移消除路径如图3所示。

图3 漂移消除：实线表示用户真实路径；点虚线表示用户被计算的路径；虚线表示漂移消除后被纠正的路径

与文献 ［9］类似，我们都在两次重新定位之间采用分段纠正方法进行漂移消除，不同之处在于两次重新定位的方式不同，文献 ［9］中需在导航场景中部署信标节点为原点生成坐标系，并基于用户与信标节点的相对位置，用距离信标较近的节点校正离信标较远节点的位置信息；而本文基于运动指纹匹配，利用机会性GPS 信息进行位置校正，从而大大降低了对导航基础设施的依赖程度。图4给出用户在燕山大学校园内步行100 m 时的路径，其中点虚线表示通过加速度计和电子罗盘数据计算得到的路径，这里称为惯性；点线表示相遇、纠正用户位置和漂移消除共同作用的结果；实线为用户真实行走路径。从图4可以看出采用漂移消除可以更好地纠正用户的行走轨迹，能指导用户回到距离初始位置更近的地方。

3 仿真实验及分析

为了评估iWALK 系统的性能，测试整个系统范围内用户的运动和相遇模式，我们使用HTC G1智能手机收集传感器数据，在燕山大学采集实验数据，同时使用GPS准确记录用户真实走过路径，生成回程导航轨迹，并将用户终点位置作为回程的起点进行回程导航实验。

3.1 实验数据及仿真环境

使用HTC G1手机采集传感器数据，该手机内置GPS、加速度计和电子罗盘。7 名志愿者被要求在燕山大学校园内以水平手持智能手机分别以不同的速度、不同的传感器采样频率和不同的路径移动，累计数据采集时间12小时。通过收集用户在移动过程中的GPS、加速度和磁偏北方向数据，获取到实验所需的真实数据。实验过程中建立笛卡尔坐标系，标记坐标系的纵轴的正向为地理方向的北，负向为地理方向的南，横轴正向为地理方向的东，负向为地理方向的西，例如 （－5，0）处表示在原点位置向西行5 m。在实验过程中默认起始点位置为坐标原点 （0，0）处。电子罗盘读数为偏离北的角度，东方向即为偏离北90°，因此，在实验中顺时针旋转为正角，旋转一圈为360°。

图4 用户在燕山大学校园内的行走路径

3.2 移动轨迹映射精度

3.2.1 瞬时错误对轨迹映射精度的影响

图5 用户的瞬时错误随时间的变化情况

在燕山大学校园内进行实验，以测试iWALK 的实用性。利用一部HTC G1智能手机收集传感器数据，同时用另一部HTC G1手机获得GPS坐标作为纠正用户瞬时位置的数据。图5显示了用户的瞬时错误在不同方案下随时间的变化情况。实验结果表明，iWALK 可以使误差减小到10m 左右，能够满足用户室外的精度要求。只使用加速度计和电子罗盘记录轨迹是不可行的，因为这些传感器的噪声会导致瞬时错误迅速增长，严重偏离用户的实际轨迹；当检测到相遇，并进行重新定位后，瞬时错误明显下降；漂移消除进一步纠正用户的轨迹，误差继续减小。

3.2.2 行走速度、采样频率和路径对轨迹映射精度的影响由于不同人群的行走速度是不同的，即使是同一个人在不同时间、不同环境下的行走速度也会不一样。因此步行速度是评价iWALK 系统的一个重要标准。图6 （a）是在相同的起点和沿直线行走40m 的情况下，不同步行速度的实验结果比较，其中点线表示在较快的步行速度下的实验结果，虚线表示正常走路下的实验结果。由图6 （a）知，行走速度较快时计算出的路径为37m，比正常走路时准确2 m。可见速度越快震动越大，计步方法计算位移越准确。因此，用户的行走模式对iWALK 有重要影响。另外从实验结果可以看出，即使在相同的地点，由于传感器噪音，实验也会存在一定的误差，图6 （a）中两次实验存在2°的误差。

图6 用户不同行走速度、采样频率和路径对轨迹映射精度的影响

iWALK 利用手机自带的惯导传感器采集数据，不同手机所配置的传感器型号可能不同，采样频率也就会随之不同。为了检测轨迹记录是否与传感器的采样频率有关，本文在相同的起点、沿直线正常行走40m 的情况下，使用不同的采样频率收集数据进行实验，实验结果如图6 （b）所示，其中点线的采样频率为1.5 Hz，实线的采样频率为0.75Hz。由图6 （b）可以看出，采样频率减小一倍，实验得到的位移几乎也减小一倍。原因是当传感器采集数据的频率较低时，一部分数据会丢失，使实验计算得到的用户行走步数远远小于其实际步数，从而得到错误的位移。因此对于iWALK 系统，手机配置的传感器的采样频率越高回程效果越好。

iWALK 要求在陌生复杂路况的环境下能够提供回程导航服务，因此本文方法能否满足用户的精度要求，能否准确识别路况是非常重要的。在不同的路径下进行实验，图6（c）分别是在直线行走、一次转弯、多次转弯的情况下步行40m 的实验结果，其中保持正常行走、采样频率一致。由图6 （c）可以看出，在3条路径下实验分别得到37m、34m 和23m 的位移，可见iWALK 受路径的影响很大，尤其在转弯时会严重影响加速度计和电子罗盘的读数，导致位移计算产生较大误差。因此，路况越复杂，转弯次数越多，位移计算误差越大，回程导航服务越不准确。另外，从实验结果中可以看出iWALK 能够准确检测到转弯，即使是小角度的偏转。

3.3 系统运行能耗

最后测试整个回程导航服务过程中的能量消耗情况。为了评估能量消耗，使用平均能量消耗来估计手机电池的生命周期，图7 （a）为实验获得的HTC G1智能手机在不同GPS环境下的平均能量消耗和传感器在不同采样频率下的平均能量消耗生命周期。从图7 （a）可以看出，使用传感器代替GPS将大大提高电池的生命周期，实现了低功耗的目的。

图7 系统能量消耗情况

为了更好的证明iWALK 系统可以实现低功耗的效果。我们在校园、公园、景区和市中心4 个地点分别使用iWALK 和SensLoc［11］、GPS在10分钟的时间内使用回程导航下的电量消耗情况进行比较，结果如图7 （b）所示，可以看出市中心由于被高大建筑物环绕，GPS导航需要较长时间的延迟，因此消耗电量较大；相反公园周围高大建筑物较少，信号较强，消耗电量最少。而使用加速度计和电子罗盘消耗的能量与使用GPS 消耗的能量相比不到10%。由于iWALK 使用音频检测是在手机正常使用的情况下已经开启，不需要在服务时专门的开启，因此iWALK与手机闲置时的能量消耗是非常接近的。另外，在室外环境下，SensLoc使用降低GPS采样频率的方法降低能量消耗。而iWALK 只有在起点和终点开启GPS，和SensLoc方法相比，进一步节约了能量消耗的60%。

4 结束语

本文提出一种陆基众包无线电导航模式，大幅减少了开启GPS的时间，有效降低了导航服务过程中的能耗。基于音频信号检测相遇，根据GSM 指纹的相似性来寻找更准确的已知GPS坐标的用户，采取轨迹校正，消除了用户行走的轨迹漂移，有效提高了回程导航路线的精度。基于Google Android系统智能手机获取了大量真实惯导数据，仿真实验及分析结果表明，在能耗较低的条件下，用户能够获得较高的众包导航精度。后续工作在校正行人移动方向时将考虑移动终端放置的随机性等因素。

［1］LUO Junzhou，WU Wenjia，YANG Ming.Mobile Internet：Terminal devices，network and services ［J］.Chinese Journal of Computers，2011，34 （11）：2029－2051 （in Chinese）.［罗军舟，吴文甲，杨明.移动互联网：终端、网络与服务 ［J］.计算机学报，2011，34 （11）：2029－2051.］

［2］ZHOU Aoying，YANG Bin，JIN Cheqing，et al.Locationbased services：Architecture and progress ［J］.Chinese Journal of Computers，2011，34 （7）：1156－1171 （in Chinese）.［周傲英，杨彬，金澈清，等.基于位置的服务：架构与发展［J］.计算机学报，2011，34 （7）：1156－1171.］

［3］Constandache I，Gaonkar S，Sayler M，et al.EnLoc：Energy－efficient localization for mobile phones［C］／／Proceedings of the 28th IEEE International Conference on Computer Communications，2009：2716－2720.

［4］Ra M－R，Paek J，Sharma A B，et al.Energy－delay tradeoffs in smartphone applications［C］／／Proceedings of the 7th International Conference on Mobile Systems，Applications，and Services，2010：255－270.

［5］Kjaergaard M B，Langdal J，Godsk T，et al.Entracked：Energy－efficient robust position tracking for mobile devices［C］／／Proceedings of the 7th International Conference on Mobile Systems，Applications，and Services，2009：22－25.

［6］Constandache I，Choudhury R R，Rhee I.Towards mobile phone localization without war－driving ［C］／／Proceedings of the 29th IEEE International Conference on Computer Communi－cations，2010：1－9.

［7］Zhang Z.I am the antenna：Accurate outdoor AP location using smartphones［C］／／Proceedings of the 17th Annual International Conference on Mobile Computing and Networking，2011：19－23.

［8］Azizyan M，Constandache I，Choudhury R R.Surroundsense：Localizing mobile phones via ambience fingerprinting ［C］／／Proceedings of the 15th Annual International Conference on Mobile Computing and Networking，2009：261－272.

［9］Constandache I，Bao X，Azizyan M，et al.Did you see Bob？：Human localization using mobile phones［C］／／Proceedings of the 16th Annual International Conference on Mobile Computing and Networking，2010：149－160.

［10］Smith T J，Saroiu S，Wolman A.Bluemonarch：A system for evaluating Bluetooth applications in the wild ［C］／／Proceedings of the 7th International Conference on Mobile Systems，Applications，and Services，2009：41－54.

［11］Kim D H，Kim Y，Estrin D，et al.Sensloc：Sensing everyday places and paths using less energy ［C］／／Proceedings of the 8th ACM Conference on Embedded Networked Sensor Systems，2010：43－56.