第39卷  计  算  机  学  报  Vol. 39 2016 论文在线出版号  No.167    CHINESE JOURNAL OF COMPUTERS  Online Publishing No.167 ——————————————— 本课题得到国家自然科学基金项目(61170292, 61472212);  国家科技重大专项课题(2015ZX03003004);  国家“八六三”高技术研究发展计划基金项目(2013AA013302, 2015AA015601); 欧盟CROWN基金项目(FP7-PEOPLE-2013-IRSES-610524)资助.  王晓亮，男，1986年生，博士研究生，主要研究领域为无线网络和移动计算，E-mail: wangxiaoliang12@mails.tsinghua.edu.cn.  徐恪，男，1974年生，博士，教授，博士生导师,  主要研究领域为互联网体系架构、高性能路由器、P2P网络、物联网和网络经济学，E-mail: xuke@mail.tsinghua.edu.cn. 杨铮，男，1983年生，博士，副教授，主要研究领域为无线网络与移动计算，E-mail: yangzheng@tsinghua.edu.cn. 葛志诚，男，1992年生，硕士研究生，主要研究领域为物联网和传感器网络，E-mail: gzc15@mails.tsinghua.edu.cn. TinyLoc: 一种面向能耗受限的可穿戴设备的室内定位算法 王晓亮1)  徐恪1)  杨铮2)   葛志诚1) 1)(清华大学计算机科学与技术系,  北京  100084)  2)(清华大学软件学院,  北京  100084)  摘  要  近年来，基于Wi-Fi接收信号强度的室内定位技术一直是研究领域的热点问题。随着智能家居和可穿戴计算的高速发展，大量新型智能设备的出现进一步推动了室内定位技术的发展，同时带来了新的挑战。可穿戴设备与传统智能设备相比，有着与用户更加紧密的位置绑定关系，是一类更加适合的室内定位平台。但另一方面，类似智能手表、眼镜、手环、戒指等可穿戴设备，由于其自身资源受限的特性，迫切需要一种低功耗的新型室内定位算法。通过本文在Moto  360二代智能手表上进行的实验可以发现，基于Wi-Fi  RSS的室内定位服务会使智能手表的使用时间缩短82%以上，其中99%的定位能耗，是为了保证定位精度而大量进行射频信号采集所造成的。简单的减少信号采集量将带来显著的定位精度下降，如何在保障定位精度的前提下，尽可能减少信号采集量是低功耗定位技术面对的核心挑战。本文提出了一种面向能耗受限的可穿戴设备的室内定位技术TinyLoc。TinyLoc在实时定位阶段仅需要一次信号采集，同时运用用户运动特性弥补信号采集量减少而带来的精度缺失。实验结果表明，在90%的情况下，TinyLoc对于完整路径上的点平均误差可以达到2m以内，另一方面，在相同实验环境下，TinyLoc能耗为传统Wi-Fi定位算法的1/6，是MoLoc的64%。相比传统的基于Wi-Fi信号的定位算法，TinyLoc可以延长Moto 360二代智能手表约3倍的定位工作时间。 关键词  室内定位；节能；运动特性；可穿戴计算 中图法分类号TP391 论文引用格式 王晓亮，徐恪，  杨铮，葛志诚，TinyLoc: 一种面向能耗受限的可穿戴设备的室内定位算法，2016，Vol.39：在线出版号  No.167 WANG  Xiao-Liang，XU  Ke，YANG  Zheng，GE  Zhi-Cheng,  TinyLoc:  Indoor  Localization  for  Energy-Constrained  Wearable Devices,Chinese Journal of Computer,2016,Vol.39:Online Publishing No.167 TinyLoc: Indoor Localization for Energy-Constrained Wearable Devices WANG Xiao-Liang1)  XU Ke1)  YANG Zheng2)  GE Zhi-Cheng1) 1)(Department of Computer Science and Technology, Tsinghua University, Beijing 100084) 2)(School of Software, Tsinghua University, Beijing 100084)  Abstract  Indoor localization technology based on Wi-Fi has long been a hot research topic in the past decade. Despite  of  numerous  solutions,  new  challenges  have  been  arisen  along  with  the  trend  of  smart  home  and wearable  computing. Compared  with  the  traditional  intelligent  devices,  the  wearable  devices  have  a  tighter 网络出版时间：2016-11-06 16:49:35网络出版地址：http://www.cnki.net/kcms/detail/11.1826.TP.20161106.1649.002.html2  计  算  机  学  报  2016年   position  binding  relationship  with  users,  and  are  a  more suitable  indoor localization platform. However,  power efficiency  needs  to  be  significantly  improved  for  resource-constrained  wearable  devices,  such  as  smart  watch, wristband,  finger  ring,  etc.  According  to  our  experiments on 2nd generation MOTO  360 smart watch, indoor locating service will reduce the standby time of the device by 82%, and 99% of the system energy consumption can be attributed to real-time radio scan. However, simply reducing radio data collection will cause a serious loss of positioning precision because of unstable Wi-Fi signals. Reducing the amount of data collection with ensuring locating  accuracy  is  the  core  challenge  of  energy-constrained  indoor  localization.  In  this  paper,  we  present TinyLoc,  an  indoor  localization  approach  that  only  needs  one  real-time  radio  scan  in  the  localization  phase to achieve  energy-saving  performance  for  wearable  devices.  Meanwhile,  TinyLoc  enhances  the  localization accuracy  using  users  motion  features.  Experiment  results  demonstrate  that  location  point  error  is  less  than  2 meters  for  more  than  90%  cases  on  the  full  path,  and  energy  consumption  is  only  1/6  of  the  traditional  Wi-Fi localization  algorithm  and  64%  of  MoLoc  in  the  same  experimental  settings. Compared  to  traditional locating algorithms based on Wi-Fi signals, TinyLoc can extend about three times of the standby time for indoor locating on 2nd generation Moto 360 smart watch.    Key words  Indoor Localization; Energy Efficiency; User Motion; Wearable Computing   1  引言 由于Wi-Fi的广泛使用，自2000年以来，以Wi-Fi 信号接收强度为基础的方案便已广受关注[1,2,3]。然而，由于传统智能设备在家居环境中的，与用户的位置绑定关系并不理想，例如智能手机、笔记本电脑等，部署于该类智能设备上的Wi-Fi 定位算法，通过计算该类智能设备的位置来标记用户当前所在的位置，这一算法并不能很好的反应用户真实的实时位置，部署于传统智能设备上的室内定位技术，在新兴的智能家居场景中将面临挑战。幸运的是，迅速发展的可穿戴设备提供了另一类设备平台。相比起传统智能设备，可穿戴设备与用户具备更紧密的位置绑定关系，更加适应室内LBS的场景需求。然而，由于可穿戴设备自身各类资源的严重受限特性，同时也对当前室内定位技术提出了新的挑战。 考虑当前的可穿戴设备的电量仅仅是传统智能设备的十分之一，节能性是现有的室内定位技术应用到智能家居和可穿戴设备场景所必须考虑的首要问题。现有节能机制的思想是使用辅助传感器获取环境信息从而动态地调整数据采样率，例如使用陀螺仪、加速器传感器以及摄像头等[4,5,6,7]。由于其额外的设备依赖和能耗，现有的技术不适用于可穿戴设备。在基于一次Wi-Fi  RSS（Received Signal Strength，接收信号强度）数据采集的实时定位阶段，能耗主要包括两方面：计算能耗和实时Wi-Fi信号强度指纹采集能耗。根据我们的实验结果，实时数据采集所造成的能耗占总能耗的99%。尽管最小化实时数据采集对能耗降低有显著效果，但由于Wi-Fi信号存在自身短暂性变化以及墙、家居、人的活动造成的多径衰落的影响，简单地减少实时数据采集量会造成严重的精度缺失。 如何在保证实时数据采集最小化的同时实现合适的定位精度？我们的方案应用了用户运动特性。现有的基于用户运动的方法，如MoLoc[8]，主要使用惯性传感器直接获取运动信息。然而，通过我们的实验，尽管使用惯性传感器的能耗对传统的智能设备似乎无法造成任何负担，但对于能耗敏感的可穿戴设备，惯性传感器的能耗不能忽视。 本文提出了一种新的室内定位技术TinyLoc。与现有基于用户运动的室内定位技术不同，TinyLoc不使用惯性传感器来获取用户的实时运动数据，而是通过历史指纹信息分析用户运动特性从而调整定位结果。与传统的室内定位技术相比，TinyLoc在实时定位阶段仅需要一次RSS数据采集即可实现较高精度，具备良好的节能性。与MoLoc相比，TinyLoc在实现相同精度的同时可减少35%的能耗，设备工作时间延长3倍。平均精度达到基础Wi-Fi定位算法的10倍。本文作出的贡献如下： 论文在线出版号  No.167  王晓亮等：TinyLoc: 一种面向能耗受限的可穿戴设备的室内定位算法  3  （1）通过Moto 360上的相关实验，首次分析并指出了基于Wi-Fi RSS的室内定位技术在可穿戴设备上的能耗水平，以及定位过程中各种操作的能耗组成。 （2）首次提出了面向资源受限的可穿戴设备的室内定位技术TinyLoc，并实现了实时定位阶段仅需一个RSS数据的特性，保证了算法节能性的显著提高。 （3）在避免使用惯性传感器而导致额外能耗的前提下，提出了利用用户的运动特性修正定位结果的优化方法，进一步降低定位算法能耗。 2  动机和挑战   通常来讲，基于Wi-Fi  RSS的室内定位技术可以划分为指纹库构建和实时定位两个阶段。在指纹库构建阶段，定位区域内的背景Wi-Fi RSS值会被探测并记录下来，以此构建指纹库。在实时定位阶段，用户所在位置的Wi-Fi RSS值会被实时采集并用于与指纹库中的记录进行对比，以此来判断用户当前所在的位置。由于指纹库的构建过程频度较低，这里本文将专注于讨论实时定位阶段的能耗优化问题。   我们在Moto  360二代智能手表和HTC  One智能手机两种平台上设计并进行了相关实验，用以记录和分析实时定位阶段的设备能耗情况。本节将具体展现现有定位技术在实时定位阶段的能耗组成，以及本文是如何利用用户的室内运动特性来优化定位结果并降低系统能耗的。 2.1   系统能耗分析   我们将实时定位阶段分为信号采集和位置计算两个部分，并在Moto  360和HTC  One上进行实验，分别测量信号采集和位置计算在单次定位中的能耗情况。能耗分析实验中，设备进行Wi-Fi信号扫描时覆盖1、6、13 号信道，以每个室内位置均进行一次3信道扫描的频率进行测试，得到当前位置所有Wi-Fi热点的RSS值。能耗数据由测试前后设备系统电量差，减去同等时间跨度下系统待机能耗得到。 表1  实时定位阶段能耗组成（mA﹒h） 设备  定位算法  信号采集  位置计算  信号采集占比 HTC One MoLoc  0.3105  0.0003  99.90% Wi-Fi  0.1917  0.0003  99.84% Moto 360 MoLoc  0.01310  0.00008  99.38% Wi-Fi  0.00806  0.00008  98.98%   首先，我们记录两款智能设备在信号采集过程中的电量消耗，并计算出平均采集一组RSS信号（在一个位置通过一次13信道扫描获得若干SSID的Wi-Fi RSS值）所需的电量。第二步，我们在两款设备上，分别多次重复运行现有定位算法，记录 电量消耗并计算出平均一次位置计算需要消耗的电量。数据分析显示，信号采集所消耗的电量占到单次实时定位阶段（一次信号采集+一次位置计算）整体能耗的99%以上（如表1所示）。不难看出，  图1 实时数据量对定位精度的影响 如何降低信号采集过程的能耗，是解决整体定位算法节能性问题的关键，其中最直接的方式是减少实时阶段Wi-Fi RSS采集量。   遗憾的是，由于Wi-Fi信号的不稳定性，在室内探测到的Wi-Fi RSS值经常存在较大波动。这就要求使用Wi-Fi RSS定位技术的定位算法，在实时定位阶段保证每个位置一定量的RSS值，以重复采集的方法削弱Wi-Fi信号不稳定的影响并提升定位精度。我们通过在HTC  One智能手机上的相关实验分析了实时数据数量的变化对定位精度的影响（如图1所示），可以发现，当实时数据量由9个减少为1 个时，基于Wi-Fi 指纹匹配的传统方法，在定位误差上从2m增加到4m，定位精度降低了近50%。所以，单纯减少Wi-Fi RSS采集量，虽然能极大的降低定位算法能耗，但是同时也会带来定位精度上的严重损失。   如何在保障定位精度的前提下，尽可能的减少Wi-Fi RSS采集量，从而降低系统能耗是目前面对 的核心挑战。本文使用用户在室内的运动特性来优化定位结果，减少信号采集量同时保障定位精度。当前也有一些室内定位算法，通过设备内建4  计  算  机  学  报  2016年   传感器来直接获取用户运动信息，以此赋予RSS指纹更多的维度来增强不同位置之间的区分度，从而优化算法定位精度。例如MoLoc[8]使用陀螺仪与加速计来获取用户运动信息。   然而，通过实验我们发现，虽然这些内建传感器的能耗对传统智能设备（如智能手机、平板电脑等）来说可以接受，但是对于资源受限的可穿戴设备来讲，则显得不可忽视。如表2 所示，我们将MoLoc分别在Moto360智能手表和HTC  One智能手机上进行了实验并记录了各个部分的系统能耗，这里内建传感器包括加速计和陀螺仪，手机端采样率分别为50Hz和500Hz，智能手表端采样率分别为25Hz和200Hz。其中内建运动传感器在单次定位中的能耗，占到单次定位总能耗的近40%。 表2  MoLoc算法能耗组成（mA﹒h） 设备  类型  信号采集  内建传感器  位置计算 HTC One mA﹒h  0.1916  0.1189  0.0003 占比  61.60%  38.30%  0.10% Moto 360 mA﹒h  0.00806  0.00504  0.00008 占比  61.17%  38.21%  0.62% 2.2   室内运动特性    为了避免使用内建运动传感器带来的额外能耗，TinyLoc不直接使用传感器的数据，而是使用人在室内的运动特性及其相关规律来优化RSS指纹的匹配结果，并进一步提高定位精度。   人在室内的运动特性主要有两个方面。首先，人在室内移动时，总是倾向于尽可能少的改变移动方向，即保持运动轨迹的平滑性。我们在两种室内环境下（见第四节实验部分环境介绍），进行了人们室内运动时轨迹规律的统计和分析。通过智能手机内建传感器（加速计、陀螺仪）或室内监控视频来记录和分析行动路径，遴选并统计了1500条有效记录，得到实验结果如图2所示。   可以发现，室内路径主要由直行路径组成，占总步数中仅80%。转弯和非正常转弯（如连续变向移动）占约20%。这是因为人在室内移动时，总是带有一定的目标性，并在移动中有意识的选取尽可能短的路径。这就意味着人在室内行动时，总是倾向于走直线，如需转弯，也是尽早的改变方向，并在之后的移动中尽可能的保持当前方向，尽量避免在较短的步伐内做出大角度的转折。然而，在使用Wi-Fi RSS进行室内定位的技术中，由于Wi-Fi信号的不稳定性，基于RSS进行的位置判断则经常出现偏差而导致整体路径频繁的出现偏折（如图3a 所示）。定位算法中可以根据上述特性对偏折的路径进行修复，从而提高定位精度。另一方面，人在室内的行动轨迹是可连通的，即人的实际行动轨迹是不可能形成诸如穿透墙壁或穿越其他物理障碍的情况的。因此，根据当前室内环境各个位置之间的可达性，以及用户的当前位置，我们是可以预先判定他合理的下一个位置的集合，忽略因Wi-Fi的不稳定性而导致的明显不合理的偏差结果，从而进一步提高定位精度。例如，在如图3(b)至图3(d)所示的实验中，我们采用Wi-Fi 指纹匹配算法来进行室内定位，选取的实验场所是某楼宇中两间连通的  图2 室内路径组成分析 实验室以及一块开阔的室内区域，总面积约300m2。其中，绿色的曲线标示了真实的室内运动轨迹，蓝色的三角形和红色的叉标示了由RSS匹配得到的位置结果。如果不做任何的优化或者修正，我们得到的路径将如红色虚线所示，这是仅使用Wi-Fi指纹匹配得到的室内定位路径。然而，如果我们考虑人在室内的移动特性，我们可以将路径优化为如图3(b)中TinyLoc所示的结果。   以图3(c)和图3(d)中所示的位置点Y和X来进一步举例说明。对于点X，由于它前面一个位置与当前的X位置在物理环境上并不连通，根据第二条运动特性，我们可以确定位置X是一个误差点。对于点Y，如果将它与它之前的位置连接起来得到的瞬时的移动方向，那么可以发现，点Y的瞬时移动方向，与它之前和之后的方向均不相同，根据第一条运动特性，即人在室内的移动路径倾向于保持平滑，那么我们也可以得知位置Y是一个误差点。通过有根据的调整、优化类似X和Y的误差点，我们可以显著优化依靠Wi-Fi指纹论文在线出版号  No.167  王晓亮等：TinyLoc: 一种面向能耗受限的可穿戴设备的室内定位算法  5  进行室内定位的定位结果。   诚然，以类似误差点Y的处理方式对路径进行优化，在一些特点的场景下一定会带来定位错误，例如，用户确实在室内进行频繁的运动方向切换。然而，对于大多数情况来说，特别是对于用户相对熟悉的环境，如家庭或办公室等楼宇中，用户在室内进行频繁的变向运动的概率很小，而同时，由于Wi-Fi自身信号稳定性较差，由此引起的误认为用户在进行频繁变向运动的概率却非常高，所以，我们认为这样的取舍是值得的。   与传统的利用概率方式的室内定位系统（如Horus系统[9]）相比，TinyLoc在计算量和Wi-Fi指纹库的要求上都更加轻量级（Horus系统采用贝叶斯分类器，指纹库需要每个位置100次以上的数 图3  运动特性示意图据采样），更加符合可穿戴设备的要求。基于上述策略，我们设计了TinyLoc室内定位算法，通过第4节将详细描述的相关实验，我们得出的结论是，这两个策略对基于Wi-Fi 指纹匹配的定位结果优化，效果比较显著。 3    TinyLoc算法设计   这一节将对TinyLoc 算法的设计给出详细描述，并通过一个实例分析，进一步阐明TinyLoc算法的工作过程和设计细节。 3.1   背景数据和位置模型   TinyLoc通过使用室内路径的连续性和运动趋势来辅助定位并提升定位精度，所以，在信号采集阶段，作为每个位置RSS值的补充，TinyLoc同时还需要各个位置之间的联通关系。举例来讲，在一个N个位置的区域，首先需要在N个位置采集各个AP 的 指 纹 信 息fingerprinti=(RSS1,RSS2,…,RSSm)，m为AP的个数。除此之外，TinyLoc需要这N个节点的相对位置以及连通关系构成室内位置模型。室内位置模型可表示为一个有权值的邻接矩阵M。 1,1 1,2 1,2,1 2,2 2,,1 ,2 ,NNN N N NMj j jj j jj j jæö ç÷ ç÷ =ç÷ ç÷ èøLLM M O ML  （1） ,,             0,          ij ijijk loc locloc locjìï=íïî和 相邻和 不相邻  （2）   我们规定k为大于0的整数，φ(i,j)=k 表示位置j 在位置i 的k方向上，这一数据将用作对运动趋势的判断。邻接矩阵M标示了室内位置的相对连接关系。   TinyLoc假设位置模型可以通过建筑平面信息或者运行前由用户自行输入的方式获得。另外，关于室内地图自动构建的研究也有很多，都可以与TinyLoc配合使用，获得位置关系模型。 3.2   运用运动特性的室内定位算法 表3  算法变量描述 变量名  描述 P  基于连通性强化当前位置选择的加权因子（P>1） R  基于连通性弱化当前位置选择的加权因子（R<1） 6  计  算  机  学  报  2016年   T  基于运动趋势弱化当前位置选择的加权因子（T<1） U  基于连通性的初始概率 M  邻接矩阵 S  基于K-NN算法的定位结果，例如[1 1 2 2: , : , , :nn loc q loc q loc q L] preQ, curQ  （位置，路径，累计概率）的层序遍历队列   TinyLoc的核心思想是利用人在室内移动的特性，其中之一是利用运动连续性来修正移动路径。对于智能家庭中触发LBS服务的场景，人不可能从一个位置跳跃到另一个不相邻的位置，所以当前定位结果和上一个定位结果是有联系的，路径中上一个定位位置应该成为当前定位的参考因子。根据邻接矩阵M中的φ(i,j)是否为0，我们得知loci 和locj 的连通关系。若上一个位置loci 是当前位置locj 的相邻节点，表明从loci 移动到locj在位置关系上是可能的，这时我们对这种情况出现的概率乘以一个增强因子；若上一个位置loci 与当前位置locj 不相邻，那么一定是上次定位或者本次定位出现偏差，我们对这种情况出现概率乘以一个削弱因子，以此来对运动轨迹进行修正。TinyLoc的核心算法将在后文介绍，表3为算法的变量说明。图4  使用运动特性修正定位结果示意   TinyLoc算法本质是对包含所有可能路径和可能性的固定高度的树进行剪枝和层序遍历，找出累积概率最大的叶节点为当前定位结果。算法维护一个包含当前可能的定位结果路径的队列curQ，队列的元素为包含当前位置、当前路径、累积概率的元组。每进行一次定位，根据定位结果和队列preQ 计算每一个可能路径的累积概率Q，重新生成当前队列curQ，以便进行下一次定位。算法1展示了累积概率Qn的计算方法。 算法1.    TinyLoc. 输入：位置概率列表S，邻接矩阵M，点集V 输出：定位路径path 1．pathß[ ], preQß[ ], curQß[ ] 2. FOR ALL startLoc∈s[0] DO 3.   preQßpreQ+(startLoc, startLoc, s[0][startLoc]) 4. FOR iß1 TO length[s]-1 DO 5.   maxQß0, mapßs[i] 6.    WHILE length[preQ]≠0 DO 7.     preLocßpreQ[0], DEL(preQ[0]) 8.      FOR ALL loc∈V & loc≠preLoc[0] DO 9.        IF loc∈map & M[preLoc[0]][loc]>0 THEN 10.         QßpreLoc[2] * map[loc]×P 11.      ELSE IF loc∈map & M[preloc][loc]=0 THEN 12.         QßpreLoc[2] * map[loc]×R 13.      ELSE IF M[preLoc][loc]>0 THEN 14.         QßpreLoc[2]×U 15.      IF ChangeTendency(preLoc[1],loc,M) THEN 16.         QßQ×T   17.         curQßcurQ+(loc,preLoc[1]+loc,Q) 18.      IF Q>maxQ THEN 19.         maxQßQ 20.         pathßpreLoc[1]+loc 21.   preQßcurQ 22.   curQß[ ] 23. RETURN path   其中loci 为当前位置，qi 为本次定位结果为loci的概率。若当前位置与上一个位置相邻，则对累积概率乘以加权因子P(P>1)，对这种情况出现的可能性进行增强；若当前位置与上一个位置不相邻，则对累积概率乘以加权因子R(R<1)，对这种情况出现的可能性进行削减；对于不在本次扫描结果中但与上一个位置相邻的位置，由于测量存在偏差该位置仍有可能是真实位置，为不使这种可能在累积概率树中消失，对这种情况的累积概率乘以一预设值U. -1-1-1,                  n i in n i iniQ q P locQ Q q R locQ U loc´´ ìï= ´ ´ íï´î邻接且匹配，       不邻接， 邻接不匹配  （3） 如图4(a)所示，上一个位置是loc2，若当前扫描结果为loc4的概率是q4，loc5的概率是q5，由于loc4与loc2相邻，loc5与loc2不相邻，所以分别对论文在线出版号  No.167  王晓亮等：TinyLoc: 一种面向能耗受限的可穿戴设备的室内定位算法  7  loc4和loc5的累积概率乘以P和R的加权因子。对于loc3，它不在本次扫描结果中，但与loc2相邻，此时对其累积概率赋予预设值U。这样对于1-2-4-5和1-2-3-5两条路径，由于后者存在路径不连通的情况，前者会具有更大的累积概率从而更符合真实的路径。 人在室内的位置移动一般不会频繁的改变方向，在路径上体现出全程或者分段具有方向性和连贯性。所以，TinyLoc利用连通性保证定位路径的基本合理性后，再利用人在室内移动的趋势连贯性优化路径，平滑移动曲线，排除因测量或其它外部影响导致的大幅度定位波动（例如图4(a)）。算法2给出了一种检测运动趋势改变的算法。 算法2.  运动趋势调整. 输入：path, loc, M 输出：运动趋势是否有变化 1. IF length[path] < 2 THEN 2.      RETURN FALSE 3.  IF  M[path[-1]][loc]=0 OR M[path[-2]][path[-1]]=0 THEN 4.      RETURN FALSE 5. currntTendßM[path[-1]][loc] mod 8 6. previousTendßM[path[-2]][path[-1]] mod 8 7. IF |currentTend - previousTend| = 2 then 8.      RETURN TURE 9. ELSE 10.    RETURN FALSE  在TinyLoc中，对于运动趋势改变的情况，我们对其累积概率乘以一削弱因子T(T<1)。这一算法，可以将路径中突然出现的运动拐点（与前后运动方向均不一致，一般由于测量数据偏差导致）进行修正。如图4(b)所示，对于路径2-3-6 和路径2-4-6，对位置2而言虽然具有一致的连通性。但由于路径2-3-6中，存在2-3和3-6两次连续的方向变化，同时，它们的变向也不同于前后节点1-2以及6-7一致的方向，所以节点3很可能是一个因为测量误差导致的错误拐点，需要被修正。TinyLoc将2-3-6 路径的的累积概率乘以削弱因子T，使路径2-4-6具有较高的累积概率（如图4(c)），从而使定位结果更符合通常状况，达到平滑运动轨迹，减小整体误差的目标。 综上所述，TinyLoc算法核心思路是，维护一颗代表之前可行位置及路径的概率树，通过联合当前位置的可能解，判断新的路径在两条运动规律上的符合情况，若符合运动规律要求，则对相应位置和路径的概率树乘以增强因子，若不符合，则乘以削弱因子。在这套机制的基础上，我们适当规模的概率树剪枝，来控制算法复杂度。由于TinyLoc完全部署于可穿戴设备上，不需要与其它设备或服务器交互计算数据，无相关通信开销。这里我们仅讨论TinyLoc算法的计算和存储复杂度。 首先，我们假设算法1中的列表S长度为m，即我们在每个位置进行K-NN匹配时，选择匹配最优的m个可行解，同时保留概率树上此前k步的所有信息。再设阈值P，对于累计概率小于阈值P的路径，同样采取剪枝操作。那么，概率树的深度将始终维持在k层，且每一层m+1及之外的匹配以及累计概率已经小于阈值P的解将全部剪枝。 算法开始前，我们将m和k值确定，由于概率树深度是确定的，且当前位置对应的第k-1层叶子节点数上限也是确定（为mk个），所以通过算法1和算法2可知，TinyLoc随着路径长度L的增长，其算法的计算复杂度是常数阶的，即O(1)。说明TinyLoc算法设置合理的m和k之后，计算效率是不受路径长度影响的。 若研究算法对参数k的计算复杂度，这里我们假设另一个参数m=3。通过计算可以得知概率树中第k-1层叶子节点数量为3k个，则在最坏情况下TinyLoc的计算复杂度随参数k是指数增长的，在这个例子中是O(3k)。所以在算法实际运用中，参数k不易设置的过高。若研究参数m对算法的计算复杂度，我们假设另一个参数k=3。与上述讨论类似，可以得知最坏情况下随参数m是3次方增长的，即O(m3)。然而，在实际匹配过程中，m个可行解受限于运动规律（物理连通性和轨迹平滑性）错误解要么根据联通矩阵直接排除，要么累计概率很快缩减到阈值P以下，大量错误解将被剪枝，TinyLoc随参数k的实际计算复杂度将远优于理论最差的指数情况。 在算法的存储即空间复杂度方面，根据算法1、2所示，TinyLoc需要存储k步内每步m个可行解的累计概率树，与计算复杂度相似，TinyLoc并不会随着路径长度的增长而需要更多的存储空间，所以其空间复杂度随路径长度L依然是常数阶，及O(1)。若要在算法开始前调整参数k和m，则与计算复杂度相似，TinyLoc 的空间复杂度为O(mk)。 8  计  算  机  学  报  2016年   通过上述分析可以发现，TinyLoc算法要求参数m和k的不易设置的过大，在参数确定的情况下，TinyLoc算法并不会随着路径的增长而形成额外的计算或存储开销。其具体的算法性能分析，详见第四节实验部分。   3.3   实时性和节能性   TinyLoc定位阶段只需要采集一个数据便可达到令人满意的室内定位精度。考虑到目标是部署于穿戴设备，最小化的数据采集，是对实时性和节能性重要的保证。基于信号强度指纹的定位算法，由于定位时Wi-Fi存在测量误差，都会因此出现定位偏差，这种偶然误差会对定位算法的效果造成严重影响。如果在相同位置进行多次数据采集，使用概率分布进行匹配，则可以改善这一状况。但实时定位阶段的射频信号扫描无疑会增加算法的能耗和时耗，对算法的实时性造成影响。 1 1 2 2 { : , : , , : }ii Input loc q loc q loc q = L  （4） Loc i 在Wi-Fi指纹匹配结果集中，概率为qi。 TinyLoc则采用了另外一种思路，实时扫描的定位阶段不需要急于得到某个确定的位置结果，而是倾向于得到一个可能位置的概率分布，再通过此后的位置和移动趋势，对之前的概率进行反馈和修正。因此TinyLoc在某个位置匹配概率不高的情况下依 图5 TinyLoc示例                      图6  实验区域I                    图7 实验区域II                 图8 Moto 360二代智能手表然能以及前后路径信息将较为模糊的点修正到相对正确的位置上，对偶然误差有良好的容忍度。TinyLoc借鉴了K-NN算法思想，使用一次Wi-Fi扫描进行匹配，以匹配到距离最近的k个指纹作为总体样本，一般取k大于每个位置的背景数据量，统计该样本中的每个位置出现的频率，把它作为TinyLoc的输入。只要真实位置能够出现在该指纹匹配的前k个样本内，就可以保证算法正确运行，相比一次扫描结果给出一个定位位置的算法，TinyLoc具备在保障准确率的同时，达到更好的实时性和节能性。 3.4    TinyLoc算法示例   下面举一个例子说明TinyLoc算法执行过程。本文提出的定位算法，会记录当前位置以及前若干步中若干最优匹配（例如本文实验中设置为前2不前3个最优匹配），并以此形成一颗概率树，在用户行进的过程中，不断通过当前位置的更新，以及当前位置与之前位置的关系，利用两个运动特性，去对不符合运动特性的相关位置概率乘以削弱因子，来强化符合RSS匹配且符合运动特性的定位结果点，这样。依靠构造概率树、计算累计概率和相应的剪枝操作，对路径上可能产生精度扰动的点（例如办公室交叉路口的转弯拐点）若产生了误判，会随着路径的延伸，很快得到纠正，并保证一个良好的定位精度。本例的室内位置模型如图5所示。 表4中第一列表示真实的路径，第二列中的数据是每次Wi-Fi RSS匹配结果，包含每个可能的位置及其对应的概率，第三列为使用最近邻算法得出  的路径结果，为3-5-9-0，与真实路径2-5-7-9差别很大。数据表明此次Wi-Fi扫描具有较大测量误差，使最近邻算法无法正确匹配。在这种情况下，TinyLoc对测量误差具有较大容忍度，可以对错误路径进行修正。 论文在线出版号  No.167  王晓亮等：TinyLoc: 一种面向能耗受限的可穿戴设备的室内定位算法  9  表4  TinyLoc算法示例 真实位置  匹配结果  基于Wi-Fi的判断结果 2  {1:0.3, 3:0.4, 2:0.2}  3 5  {5:0.4, 4:0.3, 2:0.3}  5 7  {6:0.3, 7:0.2, 9:0.4}  9 9  {0:0.4, 8:0.3, 9:0.2}  0  TinyLoc维护一棵所有路径的累积概率树，树的节点包含当前位置，对应路径和累积概率，我们称之为TinyLoc算法树。本例剪枝后的TinyLoc算法树如图5所示。   算法开始时，根据Wi-Fi信号扫描的匹配结果，存在3个可能的起点：1、  2,、3，累积概率分别初始化为本次扫描各个可能位置的概率。进行第二次扫描，第二次扫描可能的位置分别与上一轮扫描结果根据连通关系和运动趋势计算累积概率，去除累积概率小的路径，剩下的可能路径为1-2, 1-5,2-4,2-5,3-2,3-5，此时累积概率最大的路径为3-2，仍不符合真实结果。进行第三次扫描，计算第三次扫描结果所有对应路径的累积概率，求得累积概率最大的路径为2-5-6，虽然仍不符合真实路径，却修正了路径第一步和第二步。进行第四次扫描，计算累积概率，得到累积概率最大的路径为2-5-7-9，修正为正确路径。在第三次扫描结果中，loc6的概率为0.3，大于loc7的概率为0.2，且路径2-5-6-9和路径2-5-7-9同样满足运动连续性，对于这种情况，TinyLoc根据运动趋势变化，将路径修   图9 实验区域I 路径定位精度CDF（HTC One）  图11 实验区域I 路径定位精度CDF（Moto 360） 正为2-5-7-9. 4  实验评估   这一节将阐述对TinyLoc进行的实验的设计、步骤、结果和相关分析。 4.1   实验设置   考虑到人们在使用可穿戴设备时，由于肢体各部分的自然活动（例如挥动手臂）可能使得可穿戴设备无法严格的代表人体的整体移动方式，进而影响对于运动轨迹的预测。为了测试TinyLoc定位算法的有效性，在实验中，我们同时在HTC One智能手机以及Moto 360二代智能手表（如图8所示）上，对TinyLoc、MoLoc以及基础的Wi-Fi指纹算法（K进行了实现，通过在传统智能设备和可穿戴设备两种不同平台上同时进行的实验，来进一步对比并研究TinyLoc的定位精度和能耗优化情况。 另外，由于室内场景的多样性，为了进一步提高实验结果的有效性，我们同时在一个144m2的室内开阔区域和一个200  m2的室内封闭办公场所分别进行了实验，如果图6、图7所示。   实验场地I是位于某大厅的室内空旷区域。实10  计  算  机  学  报  2016年      图10 实验区域II 路径定位精度CDF（HTC One）     图12 实验区域II 路径定位精度CDF（Moto 360） 验区域长24m宽6m，包含8*3个位置，相邻位置间隔3m。我们在区域的顶点和一条边的中点布置了5个AP，分别在数据构造和定位阶段在每个位置进行10次RSS抽样，用于指纹库构建和位置估计。对于MoLoc，我们记录了每两个位置间移动的陀螺仪和加速度传感器读数，其中3次用于运动数据库构建，1次用于定位。试验场地II位于某个长13.2m宽15.6m的网络实验室，该区域遍布桌、椅、机架等家具，电脑、服务器、交换机等设备，电磁环境复杂。我们随机选取了8个能覆盖整个区域的AP，选定了18个位置，每两个位置间隔2-4m。数据采集和实验方法与场地II 相同。实验数据集由所有采集到的路径信息中随机选择得到，计算所需的邻接矩阵M在算法开始前手动输入。 4.2   实验结果与分析   我们设计了实验在各个方面（精度、能耗等）对比考察TinyLoc，MoLoc和基础的Wi-Fi指纹定位算法，并在传统智能设备和可穿戴设备上分别进行了实验。同时，为了研究TinyLoc算法的可移植性，我们设计了实验对比了借助TinyLoc改进后的FreeLoc[6]和原生FreeLoc算法。实验结果和相关分析将在本节详细讨论。  图13 实验区域I 单点定位精度（HTC One）  图15 实验区域I 单点定位精度（Moto 360） 4.2.1   定位精度 我们分别从定位误差CDF、定位准确率两个方面比较TinyLoc、MoLoc和Wi-Fi的定位精度。随后对不同AP个数情况下以及不同路径长度下的定位精度进行统计分析，解释TinyLoc和MoLoc运用运动特性的区别。 1tan ( , )stepestimated realnn nlocDis ce loc locDstep==å   (5) 1,2,3 ,()( 1, 2, 3, , )step N locxstepcount loc path D xplength path N= Î Ù £== åLL(6) 我们首先做出了在两种实验环境和两种设备。平台上路径定位误差概率分布曲线，CDF的计算方法由公式(5)和公式(6)所指明。本文提出的算法与其它室内定位算法不同，需要利用当前位置之前的路径信息，再加以运动特性的判断来修正定位结果。于是，在进行定位精度实验时，难以像其它定位算法那样，直接给出单独针对某一个点或某一个位置的定位精度，因为缺乏之前路径的信息，本算法难以运论文在线出版号  No.167  王晓亮等：TinyLoc: 一种面向能耗受限的可穿戴设备的室内定位算法  11  行。于是，在算法的定位精度的误差计算部分， 图14 实验区域II 单点定位精度（HTC One）  图16 实验区域II 单点定位精度（Moto 360） 我们计算的是一条路径上所有定位点的平均点定位误差，即通过计算一条修正后的路径所有偏差点的误差求平均值得到的，如公式（5）所示。另外有一点需要说明的是，由于本算法的计算过程实是在维护一颗概率树，其树根，即路径的初始位置是按照真实位置输入系统的。两个实验场地的定位误差CDF如图9~12所示。   从图中可以发现，TinyLoc和MoLoc明显优于Wi-Fi指纹匹配方法。其中，在Moto 360二代智能手表上进行的实验，TinyLoc和MoLoc路径定位误差小于1m的概率分别为80%和60%左右，在HTC One上，路径误差小于1m的概率分别则为80%和70%左右，而误差小于2m的概率则均达到了80%以上。对比两种设备平台上的实验结果，可以发现曲线的变化趋势是相对一致的，在Moto 360二代上得到的实验结果要略低于HTC One上的实验结果，相差约3%~5%左右。由此可以看出，可穿戴设备并不能完全排除肢体相对身体移动时带来对运动趋势和定位结果的影响，例如挥动手臂或扭转肢体等，如何进一步优化仍是一个值得探索的命题。另一方面，运用运动特性的定位算法考虑了相邻位置的可达性，大幅度缩小估计位置的可能集合，可以 图17 实验区域I 定位精度随AP数量变化趋势  图19 实验区域I 定位精度随路径长度变化趋势 很大程度上减小由Wi-Fi 指纹相似性或随机变化造成的误差。 我们再从单个位置的定位准确率来比较定位精度。定位准确度即匹配正确的点的比例，可以直观表明某算法的定位效果。我们从实时数据的10个样本中选取了5个计算其位置匹配率，实验I和实验II 的结果如图13~16所示。可以看出，在Wi-Fi平均定位准确率达到50%的情况下，MoLoc可将定位准确率提高至80%以上，TinyLoc可以提高至88%以上。相比之下，TinyLoc可以明显提升基础Wi-Fi 定位算法效果，同时也可提升1%~20%MoLoc的定位精度。   以上实验结果分别是在空旷实验环境下5个AP，办公室内8个AP的情况下得到的。基于Wi-Fi指纹匹配的定位算法的效果和AP个数是相关的。我们分别统计了两种实验环境中不同AP个数情况下的定位准确度如图17、18所示。随着AP数量增多，三种定位算法的定位精度都有提升。当AP个数超过一定数量后，定位精度基本不再提高，这与文献[10]的实验结果相符。在AP数量不12  计  算  机  学  报  2016年   同的情况下，TinyLoc和MoLoc的定位效果均优于基础的Wi-Fi指纹定位算法。详细来看，在实验I中，由于 图18 实验区域II 定位精度随AP数量变化趋势  图20 实验区域I 定位精度随路径长度变化趋势 场地空旷，在AP数量为2的情况下，3种算法的的定位精度都很低，TinyLoc和MoLoc基本相当，定位精度为35%左右，Wi-Fi指纹定位算法则精度更低，为27%左右。随着AP数量的增加，当达到最大5个AP时，TinyLoc和MoLoc分别达到90%和85%左右的精确度，而Wi-Fi指纹定位算法也有明显提升，精度接近60%。在实验I 中，随着AP数量从2个增加到5个，TinyLoc、MoLoc和基础的Wi-Fi指纹定位算法精度提升分别达到257%、243%和222%。可见AP数量对定位精度影响显著。在实验II中，定位精度随AP数量增加而显著提升的趋势与实验I相符，由于其实验场所为室内环境，虽然存在Wi-Fi信号的多径效应，然而室内结构的自然分割导致各个位置的Wi-Fi指纹差别相对开阔空间更为明显，区分度更大，于是可以看出在同为3个AP的情况下，实验II中3种定位算法的精度均高于实验I中的情况，最终达到的最大精度也好于实验I中。 通过对误差概率分布和不同AP个数下的定位精度精度的比较可以得出，TinyLoc和Moloc能够明显改善Wi-Fi指纹匹配算法的定位效果。就利用了运动特性的TinyLoc和MoLoc而言，二者定位效 图21 不同算法在两款设备上的单次定位能耗  图23 不同算法单位精度提升的能耗代价 果相差不大，多数情况下TinyLoc 优于MoLoc。我们从原理分析造成这种状况的原因：MoLoc对当前位置定位时，只参考上一步的定位结果可能集合；TinyLoc维护一棵特定高度的累积概率树，当前定位估计位置可以对历史路径进行修正。随着路径长度的增长，定位效果提升将越明显。 最后，由于TinyLoc是利用运动特性的室内定位算法，关于定位精度，我们设计了实验评估路径长度对定位精度的影响。可以想见，路径长度越长，提供给算法进行运动趋势判断的信息越多，对定位精度提升应该更加有利。我们分别在两种实验环境进行了不同长度路径的定位测试，准确率如图19、20所示。当路径长度为0时，初始位置估计只依赖Wi-Fi指纹匹配结果。从第二次定位的结果可以看出，无论是TinyLoc还是Moloc，由于使用运动特性进行定位结果修正，对Wi-Fi的定位效果有了明显提升，而提升效果TinyLoc略优于MoLoc。随着路径长度的增加，TinyLoc对定位效论文在线出版号  No.167  王晓亮等：TinyLoc: 一种面向能耗受限的可穿戴设备的室内定位算法  13  果的提高幅度均优于MoLoc，在路径长度达到5步时，TinyLoc和MoLoc即可达到最优定位精度，此时相对于基础Wi-Fi指纹匹配算法，MoLoc可以提升约10%~20%的定位精度，而TinyLoc则可提升约30%     图22 不同算法在Moto 360运行时的工作时间  图24 利用TinyLoc优化FreeLoc定位精度 的定位精度。 4.2.2   算法能耗   我们分别在Moto  360二代智能手表和HTC One智能手机上实现并运行这3种定位算法，一方面通过反复运行测算出每个定位算法在计算部分的平均能耗，另一方面，通过反复扫描Wi-Fi信号强度，测算Moto 360二代和HTC One在数据采集阶段的扫描能耗。结果显示TinyLoc仅消耗约64%的MoLoc能耗，在持续定位的使用情况下，可延长智能手表约1.25倍的运行时间。同时，TinyLoc在使用最少能耗的情况下，达到了最大精度提升，这对于资源受限的可穿戴设备来说是非常重要的。 对于MoLoc，我们多次执行计步程序以统计平均运动传感器能耗。图21 显示了执行一次定位TinyLoc、MoLoc以及基础Wi-Fi定位算法的总能耗。图中的单位是1%，按照HTC的2300mAh的电量进行折算，三种定位算法的耗能分别为0.1922mAh、0.302mAh 和0.1919mAh。另外，在Moto 360上进行的测试得出TinyLoc、MoLoc和基础Wi-Fi 指纹匹配三种定位算法的能耗如表1 所示，分别为0.0084mAh ，0.0131mAh 和0.0081mAh。其中，TinyLoc和基于Wi-Fi指纹匹配的算法，其能耗包括两部分，信号采集能耗和计算能耗。而MoLoc还包括额外的内建运动传感器能耗。由于计算能耗相比信号采集能耗来讲，非常微小，几乎可以忽略不计，MoLoc相比其它两种算法能耗偏高的主要原因就是其使用的内建运动传感器带来的额外能耗。   在Moto  360上以3秒每次的频率进行Wi-Fi信号扫描，在此基础上，对三种定位算法分别测试其在Moto  360上的最长可工作时间，结果如图22所示。从图中我们可以发现，Moto  360在使用不同定位算法时，最长运行时间有显著的差异。首先，Moto  360自身的待机时间约为24小时，一直使用TinyLoc进行室内定位是可运行时间最长的，可达到约13.27小时，使用MoLoc则为10.59小时，而Wi-Fi指纹匹配则为4.25小时（要求到达一定精度，此时Wi-Fi指纹匹配算法需要每个位置采集6个数据以保证达到一个可接受的精度）。可以发现，使用TinyLoc的运行时间是MoLoc的约1.25倍，是Wi-Fi指纹匹配的3.12倍。 实际上，从某种程度上讲，定位精度和能耗是互相对立的两个方面。定位算法采取一定措施提高定位精度，势必造成定位能耗增加，这将不利于算法的可部署性。面向可穿戴设备的定位算法，应该考虑如何尽可能的减少能耗并提供精度，即如何提高单位能耗对精度优化的贡献度。 为了研究这三种算法对能源的使用效率，我们测试TinyLoc、MoLoc和Wi-Fi指纹匹配在单位精度提升的情况下，所需要的能耗代价。实验结果如图23所示。可以看出，TinyLoc以最小的能耗增长为代价，达到了最大化的定位精度提升。基于Wi-Fi指纹匹配的方法，需要通过增加采集额外的实时RSS数据来提高精度，通过图1我们可以知道，这将带来几乎900%的能耗提升（需要9倍的数据采集量来达到最优的定位精度）。TinyLoc通过使用运动特性的方式提高精度，避免了更多实时数据的采集，但是引入了额外的计算量，但额外的计算能耗仅占总能耗的5%。MoLoc通过设备内建的运动传感器来获取运动信息，以此来优化14  计  算  机  学  报  2016年   定位精度，而这带来了额外的约30%能耗增长。   由此可见，TinyLoc以最小的能耗代价获得了最大精度增益，因而适用于低电量的可穿戴设备和对精度有高要求的智能家居环境。 4.2.3   算法可移植性 与其他基于运动特性的定位算法一样，TinyLoc具有很好的兼容性，可以方便地与其他定位系统相  结合。FreeLoc[6]算法使用某一室内位置各AP热点之间相对RSS强弱排序做为指纹，来代替绝对RSS数值对位置进行定位。这一做法极大提升了指纹数据在不同设备间公用的兼容性，然而对于定位精度存在一定程度上的影响。我们实现了FreeLoc的算法原型，并在场地1中进行了实验。结果表明，FreeLoc 的定位效果确不理想。我们使用TinyLoc利用运动特性修正定位结果的思想改进FreeLoc，在FreeLoc的基础上使用运动特性提高定位精度，实现了混合TinyLoc和FreeLoc的定位方案TinyLoc-based FreeLoc。定位误差CDF如图24所示。   实验结果表明，TinyLoc 利用运动特性对定位结果进行修正的思路确实可以提高定位精度，且与其他现有的定位系统具备很好的可结合性。 5  讨论 本文提出了一种仅需采集一个实时数据进行定位的室内定位技术TinyLoc，使用人在室内的运动特性，对定位结果进行修正和优化，具备轻量级、节能、实时、高精度的特点。TinyLoc能够很好的满足智能家居场景下、个人穿戴设备上部署室内LBS的相关要求。然而，TinyLoc技术中依然有一些富于挑战性的技术性问题值得讨论，下面简要描述我们正在研究也最为关心的一个。 TinyLoc 可以在只采集一个实时数据的情况下，获得良好的定位精度，其中很重要的一个原因是背景数据和环境模型（参见2.1节）中包含了各个位置之间的相对关系，这也是TinyLoc算法中，利用人在室内运动特性来优化定位结果的基础。然而，如何获取所在环境的相对位置信息，又如何规范化定义相对位置，以更好的描述环境信息，都是值得研究的问题。 我们正在研究一种基于传统智能移动设备（如手机、平板电脑等）的自动位置信息获取技术。在背景数据采集阶段，先使用传统设备进行采集，除了自动获取位置RSS值，还可以根据设备自带的陀螺仪、加速器，通过角度偏移自动获取每个位置之间的相对位置关系，形成支持TinyLoc的背景数据和位置模型。 6  相关工作 近十年来许多室内定位技术被提出。其中基于Wi-Fi的室内定位技术由于其在室内环境下的易部署性，一直是研究热点。我们的工作着眼于设计一个低功耗的室内定位技术，通过应用用户运动特性弥补减少实时数据量带来的精度缺失。 早期的室内定位技术应用GSM信号、RFID、次声波、超声波或UWB来确定位置，它们需要依赖特殊设备[1]。无线射频信号于2000 年在RADAR中被首次用于定位[2]。近年来，许多定位技术开始重视Wi-Fi 信号强度，以此来提高精度[9,11]、减小测量区域[12]、训练系统[13]等。然而，信号强度总是波动，所以需要一定实时数据量来保证定位精度。如何减小测量误差对定位效果的影响是另一个重要研究课题。FreeLoc[14]不直接使用信号强度RSS值，而是使用AP间RSS的相对排序进行匹配，以此解决RSS不规则改变的问题。然而，对于AP个数较少的环境，或者相邻区域RSS差别不大的情况将会对定位精度造成严重问题。MoLoc[8]是一种利用运动信息来辅助提升定位精度的室内定位算法。MoLoc可以比较容易的与当前其它定位算法组会使用，通过简单的增加一个运动数据库即可。然而，MoLoc使用设备内建的传感器采集运动信息，首先这限制了MoLoc可以部署和使用的设备范围，另外，内建传感器的频繁使用也会带来额外的系统能耗，这对于传统智能设备并不是一个问题，而对于资源严重受限的可穿戴设备来讲，这一额外的能耗尚需进一步优化。 另一种方法是放弃RSS，测量Wi-Fi环境中其他相对稳定的物理量来实现更高精度，如FILA[3]和文献[15]提到的CSI(channel  state  information)。该方法引入了物理层的通信信道状态信息，周围物理空间环境的变化，将会反映在CSI中，从而使得基于CSI的定位算法识别出环境差别并用以定位。然而由于CSI的测量困难、测量成本较高，它目前并不适用于可穿戴设备。另外，作为室内定位的基础，对自动化室内地图和指纹数据库建立论文在线出版号  No.167  王晓亮等：TinyLoc: 一种面向能耗受限的可穿戴设备的室内定位算法  15  也有不少相关研究，如文献[16]采用广播信号进行指纹数据库建立和相应定位算法。 此外，节能性一直是室内定位领域的热门研究课题，也是可穿戴设备所要考虑的首要问题。通过各类辅助设备，感知环境信息来动态调整数据采集，是当前节能机制的主要思想。例如根据节点的移动速度，动态调整信号强度采集频率[4,5,17,18]，通过多重OFDM辅助波的信道应答来提高精度[19]，以及使用周围环境信息[6,7]。此外也有在系统层面降低系统整体能耗的方案，如GreenLoc[20]。GreenLoc认为人群通常具有相似的运动行为，所以可以选取人群中的一些个体作为样本，使用对他们进行定位的结果代表整个人群，从而降低了系统总能耗。但GreenLoc并不擅长对个体的定位，而这正是智能家居应用场景中所需要的。另外，Wi-Fi 信号扫描的信道覆盖也会带来更多的能耗开销，如文献[21]采用了更少的信道覆盖方法，保障精度的同时降低算法能耗。文献[22]则采用Zigbee技术在2.4G频段上扫描Wi-Fi信号的方式，降低信号采集能耗，取得了明显的能耗优化，然而因此新引入的地图机制可能会带来额外的系统复杂度和能耗开销。  另一方面，如文献[23,24,25]在移动设备的数据传输方面，通过新的传输协议和机制设计，将传输能耗进行了进一步优化，对基于移动设备的室内定位技术，提高数据处理和传输时的能源效率起到积极作用。 7  总结与展望 智能家居与可穿戴设备的快速发展，为家居环境下的LBS发展提供了良好的基础。然而，节能性是现有的定位技术在投入使用前所必须考虑的重要问题。在本文中，我们首次提出了可部署于穿戴设备上的，面向智能家居场景的低能耗的室内定位算法——TinyLoc。该算法应用运动特性来修正定位结果，优化定位精度。根据在HTC One智能手机以及Moto  360智能手表上的实验结果，使用该算法定位误差小于2m的概率达到90%以上，比同环境中的基于Wi-Fi的基础定位算法，精确度提高9倍以上。与此同时，在定位精度相似的条件下，它的平均能耗仅为MoLoc的65%。实验中，本文提出了将TinyLoc核心思想应用于其他定位技术的方案，并在实验测试中取得了良好效果，证明了TinyLoc的可移植性和良好的技术兼容性。   未来我们计划聚焦于TinyLoc所需的背景数据和环境模型的自动构建技术。除应用运动特性外，我们将着眼于为TinyLoc扩展更丰富的定位策略，以适应更加多样化的室内应用场景，并在范围更大的实际环境下测试和完善TinyLoc。 参 考 文 献 [1] Liu H, Darabi H, Banerjee P, et al. Survey of wireless indoor positioning techniques  and  systems.  IEEE  Transactions  on  Systems,  Man,  and Cybernetics,  Part  C  (Applications  and  Reviews),  2007,  37(6): 1067-1080.  [2]  Bahl  P,  Padmanabhan  V  N.  RADAR:  An  in-building  RF-based  user location  and  tracking  system//Proceedings  of  the  2000  IEEE International  Conference  on  Computer  Communications.  Tel  Aviv, Israel, 2000, 2: 775-784. [3]  Wu  K,  Xiao  J,  Yi  Y,  et  al.  Fila:  Fine-grained  indoor  localization// Proceedings  of  the  2012 IEEE  International  Conference  on  Computer Communications. Orlando, USA, 2012: 2210-2218. [4]  You  C,  Chen  Y  C,  Chiang  J  R,  et  al.  Sensor-enhanced  mobility prediction for energy-efficient localization//Proceedings of the 2006 3rd Annual  IEEE  Communications  Society  on  Sensor  and  Ad  Hoc Communications and Networks. Reston, USA, 2006, 2: 565-574. [5]  Constandache  I,  Choudhury  R  R,  Rhee  I.  Towards  mobile  phone localization  without  war-driving//Proceedings  of  the  2010  IEEE International  Conference  on  Computer  Communications.  San  Diego, USA, 2010: 1-9. [6] Liu Y, Lu S, Liu Y. COAL: Context Aware Localization for high energy efficiency  in  wireless  networks[C]//Proceedings  of  the 2011  IEEE Wireless  Communications  and  Networking  Conference.  Cancun, Mexico, 2011: 2030-2035. [7] Azizyan M, Constandache I, Roy Choudhury R. SurroundSense: mobile phone localization via ambience fingerprinting//Proceedings of the 15th annual  international  conference  on  Mobile  computing  and  networking. Beijing, China, 2009: 261-272. [8]  Sun  W,  Liu  J,  Wu  C,  et  al.  MoLoc:  On  distinguishing  fingerprint twins//Proceedings  of  2013  IEEE  33rd  International  Conference  on Distributed Computing Systems. Philadelphia, USA, 2013: 226-235. [9]  Youssef  M,  Agrawala  A.  The  Horus  WLAN  location  determination system//Proceedings  of  the  3rd  international  conference  on  Mobile systems, applications, and services. New York, USA, 2005: 205-218. [10]  Li  H,  Sun  L,  Zhu  H,  et  al.  Achieving  privacy  preservation  in  WiFi fingerprint-based  localization//Proceedings  of  the  2014  IEEE International  Conference  on  Computer  Communications.  Toronto, Canada, 2014: 2337-2345. [11] Klepal M, Beauregard S. A novel backtracking particle filter for pattern matching  indoor  localization//Proceedings  of  the  first  ACM 16  计  算  机  学  报  2016年   international  workshop  on  Mobile  entity  localization  and  tracking  in GPS-less environments. San Francisco, USA, 2008: 79-84. [12] Eleryan , Elsabagh M, Youssef M. Synthetic generation of radio maps for  device-free  passive  localization//  Proceedings  of  the  2010  IEEE Global Telecommunications Conference. Houston, USA, 2011: 1-5. [13] Wang H, Sen S, Elgohary A, et al. No need to war-drive: unsupervised indoor localization//Proceedings of the 10th international conference on Mobile systems, applications, and services. Low Wood Bay, UK, 2012: 197-210. [14]  Yang  S,  Dessai  P,  Verma  M,  et  al.  FreeLoc:  Calibration-free crowdsourced  indoor  localization//Proceedings  of  the  2013  IEEE International  Conference  on  Computer  Communications.  Turin,  Italy, 2013: 2481-2489. [15]  Yang  Z,  Zhou  Z,  Liu  Y.  From  RSSI  to  CSI:  Indoor  localization  via channel response. ACM Computing Surveys (CSUR), 2013, 46(2): 25. [16] Yoon  S,  Lee  K,  Rhee  I.  FM-based  indoor  localization  via  automatic fingerprint  DB  construction  and  matching//Proceeding  of  the  11th annual  international  conference  on  Mobile  systems,  applications,  and services. Taipei, China, 2013: 207-220. [17]  Shafer  I,  Chang  M  L.  Movement  detection  for  power-efficient smartphone  WLAN  localization//Proceedings  of  the  13th  ACM international  conference  on  Modeling,  analysis,  and  simulation  of wireless and mobile systems. Bodrum, Turkey, 2010: 81-90.  [18]  Mizell  D.  Using  gravity  to  estimate  accelerometer  orientation// Proceedings  of  the 7th  IEEE  Int.  Symposium  on  Wearable Computers. White Plains, USA, 2003: 252. [19] Sen S, Radunovic B, Choudhury R R, et al. You are facing the Mona Lisa: spot localization using PHY layer information//Proceedings of the 10th  international  conference  on  Mobile  systems,  applications,  and services. Low Wood Bay, UK, 2012: 183-196. [20]  Abdellatif  M,  Mtibaa  A,  Harras  K  A,  et  al.  GreenLoc:  An  energy efficient  architecture  for  WiFi-based  indoor localization  on  mobile phones//Proceedings  of  the 2013  IEEE  International  Conference  on Communications. Budapest, Hungary, 2013: 4425-4430. [21] Brouwers N, Zuniga M, Langendoen K. Incremental wi-fi scanning for energy-efficient  localization//Proceedings  of  the  2014  IEEE International  Conference  on  Pervasive  Computing  and Communications. Budapest, Hungary, 2014: 156-162. [22]  Gao  Y,  Niu  J,  Zhou  R,  et  al.  Zifind:  Exploiting  cross-technology interference  signatures  for  energy-efficient  indoor  localization// Proceedings  of  the  2013 IEEE  International  Conference  on  Computer Communications. Turin, Italy, 2013: 2940-2948. [23]  Liu  F,  Shu  P,  Lui  J  C  S.  Appatp:  An  energy  conserving  adaptive mobile-cloud  transmission  protocol.  IEEE  Transactions  on  Computers, 2015, 64(11): 3051-3063. [24]  Zhang  T,  Zhang  X,  Liu  F,  et  al.  eTrain:  Making  wasted  energy  useful by utilizing heartbeats for mobile data transmissions//Proceedings of the 2015  IEEE  35th  International  Conference  on Distributed  Computing Systems. Columbus, USA, 2015: 113-122. [25]  Liu  F,  Shu  P, Jin  H, et al. Gearing  resource-poor  mobile devices  with powerful  clouds:  architectures,  challenges,  and  applications.  IEEE Wireless communications, 2013, 20(3): 14-22.  WANG  Xiao-Liang,  born  in  1986, Ph.D. candidate,  His  research  interests  include wireless network and mobile computing.   XU  ke, born  in  1974,  Ph.D.,  professor,  Ph.D. supervisor. His research  interests  include  Internet  architecture,  high performance  router,  P2P  network,  Internet  of  things  and network economics.   YANG  zheng,  born  in  1983,  Ph.D.,  assistant  professor.  His research  interests  include  wireless  network  and  mobile computing.   GE  Zhi-Cheng, born  in  1993, Master  candidate. His  research interests include Internet of things and wireless sensor network.    Background The  rapid  development  of  smart  home  and  wearable devices provides a good foundation for the high availability of indoor  LBS  in  home  setting  scenario.  However,  energy efficiency  is  the  essential  issue  that  needs  to  be  significantly improved  for  the  existing  locating  technology  before  they  can be  implemented  on  energy-constrained  wearable  devices.  In 论文在线出版号  No.167  王晓亮等：TinyLoc: 一种面向能耗受限的可穿戴设备的室内定位算法  17  this  paper,  we  propose  a  novel  indoor  localization  technology called “TinyLoc” with its focus  on  energy  efficiency,  the  first one that can fit in wearable computing in smart home scenes. This  work  was  supported  by  the  National  Natural  Foundation  of  China (61170292,  61472212),  National Science and  Technology  Major  Project  of  China  (2015ZX03003004),  the  National  High  Technology  Research  and  Development  Program  of  China  (863  Program)  (2013AA013302,  2015AA015601),  EU  Marie  Curie  Actions  CROWN  (FP7-PEOPLE-2013-IRSES-610524). By  referring  user  motion  features,  TinyLoc  modifies locating  results  to  achieve  satisfying  locating  accuracy  and guarantee  excellent  energy-saving  performance.  According  to the  experiment  deployed  on  HTC  One  and  Moto  360,  the probability  of  error  within  two  meters  can  reach  more  than 90%.  Meanwhile, energy  consumption  is  35%  lower than  that of MoLoc when achieves the same accuracy.