7期 周傲英等：基于位置的服务：架构与进展 1165 证其空间临近性被保存下来.Ruppel等人[s]提出 空间-社会数据[9].针对这一类型数据的分析可以 了一种位置保存映射方法，但是Liu等人[s]在随后 更深入地掌握用户的兴趣爱好，进一步地提供个 的研究中发现该方法可以被攻破.一种能够保护用 性化LBS服务.通过对具有空间信息标注的图片的 户位置隐私，又能保证检测到用户之间临近性的算 分析，WorldExplorer提供了一种新的基于地图的 法在文献[87]中提出.该方法首先将用户的坐标映 探索服务[9) 射到一个网格中，并将该网格的标识符进行加密发 用户可以对已有的空间对象加文字标注，或者 送到LBS服务提供商，服务提供商仅仅可以利用这 对其它对象进行具有空间、时间信息的标注.这产生 种加密后网格标识符进行临近性的检测，却无法反 了一种空间关键字查询服务，即结合空间信息的信 推出用户的实际位置，用户位置隐私因此得到保护. 息检索.Cong等人[提出了一种算法，综合考虑空 7.4云计算平台下的LBS 间上的相似度和标注文字的相关程度，通过倒排表 通常情况下移动终端受限于计算能力和电池资 和R-tree索引，返回最相关的k个空间对象.Zhang 源，无法完成较复杂的运算，如何利用强有力的云计 等人[s6提出了m最近关键字查询和bR'-tree索引 算平台来提供更高效的基于位置的服务富有挑战. 结构，可以找到m个空间上最近、并满足m个用户 海量历史轨迹数据管理。大量的室外空间轨迹 给定的关键字的空间对象， 数据已经堆积，最新的研究8]已经对多达1亿个室 7.6针对紧急情况的LBS 外移动对象进行了轨迹索引研究.另一方面，室内轨 不少学者最近也在关注如何在紧急情况下提供 迹数据也在快速增长，例如地铁站、飞机场等场所每 高质量的LBS服务，例如地震、火灾等.在紧急情况 天的数据量达到百万量级.对大量的历史轨迹数据 下，周围环境更为恶劣，往往也要求用户快速做出反 进行分析和查询，能够为改进LBS的服务质量提供 应，因而对LBS服务的要求更苛刻.例如，火灾现场 很好的帮助.MapReduce框架为大规模的分布式的 充满烟雾、光线黯淡且有很多障碍物[9] 轨迹处理提供了良好的基础.Yang和Ma等人[s-o] 当前，许多科研机构均对本问题进行探索，提出 利用分布式平台，提出了基于MapReduce架构的大 了不少方案.SummitSafety公司的Pathfinder系统 规模历史轨迹数据处理算法，该方法将时空系统分 利用了超声波技术，能为消防员在黑暗空间中快速 区，把轨迹数据存储在不同节点上·在处理查询时， 找到安全出口，超声波无法穿墙而过，但是能够绕过 按照同样的分区策略，把查询分布在不同的节点上 墙角或通过门缝传播.该系统在安全出口处放置若 执行，最后合并出最终结果 干超声波发射器，发送不同频率信号.消防员手持超 隐私保护.云计算平台为LBS提供了一种新 声波接收仪，分析接收到的信号即可快速制定安全 的运营模式，即LBS服务提供商并不一定拥有自己 的路径].美国国家标准和技术协会(NIST)利用 的云计算平台，而是将自己的数据和服务外包到云 RFID技术研发的flipside系统有助于消防员在黑 计算平台（由云计算平台服务提供商提供）上运行. 暗空间快速定位.与传统的RFID系统不同，在这个 这就带来了新的隐私保护问题，即如何在利用不可 系统中，RFID标签是静态的，各消防员穿戴移动的 信的云计算平台的同时，获得可信的基于位置的服 RFID阅读器.读到临近的RFID标签时，即可定 务.这类隐私保护方法需要保证两方面安全[91-9]：既 位].Klannt100]设计的LifeNet系统能够为消防员 要求保证被外包的时空数据是隐私的(privacy),即 在黑暗空间中寻找一条安全路径.该系统也采用超 云计算平台服务提供商无法破解外包的时空数据： 声波技术，在室内空间布置若干个标杆.消防员可以 同时也要求用户能对查询的结果完整性(integrity) 携带一个设备，感知临近的信标，并依赖感知到的信 进行验证，即用户能验证结果是正确并且是完整的， 标构造路径，显示到头盔上去，其它代表性的系统还 以防止云计算平台服务提供商篡改和删除某些 包括PPL[ao]、HeadSLAM1o2]等.这个方向的研究 结果 工作尚未成熟，上述提及的系统中大多处于实验室 7.5社会化LBS 环境之中，仅有Pathfinder系统已经商业化. 随着Web2.0技术的迅速普及，Flicker、Deli- cious、YouTube和Facebook等服务允许用户参与 8 未来的研究工作 并共享自己的数据.由于这些数据通常包含3种信 息一时间、空间和人物，因而也常被视为是时间- 基于位置的服务在近几年得到了广泛的研究，证其空间临近性被保存下来．Ｒｕｐｐｅｌ等人［８５］提出 了一种位置保存映射方法，但是Ｌｉｕ等人［８６］在随后 的研究中发现该方法可以被攻破．一种能够保护用 户位置隐私，又能保证检测到用户之间临近性的算 法在文献［８７］中提出．该方法首先将用户的坐标映 射到一个网格中，并将该网格的标识符进行加密发 送到ＬＢＳ服务提供商，服务提供商仅仅可以利用这 种加密后网格标识符进行临近性的检测，却无法反 推出用户的实际位置，用户位置隐私因此得到保护． ７４云计算平台下的犔犅犛 通常情况下移动终端受限于计算能力和电池资 源，无法完成较复杂的运算，如何利用强有力的云计 算平台来提供更高效的基于位置的服务富有挑战． 海量历史轨迹数据管理．大量的室外空间轨迹 数据已经堆积，最新的研究［８８］已经对多达１亿个室 外移动对象进行了轨迹索引研究．另一方面，室内轨 迹数据也在快速增长，例如地铁站、飞机场等场所每 天的数据量达到百万量级．对大量的历史轨迹数据 进行分析和查询，能够为改进ＬＢＳ的服务质量提供 很好的帮助．ＭａｐＲｅｄｕｃｅ框架为大规模的分布式的 轨迹处理提供了良好的基础．Ｙａｎｇ和Ｍａ等人［８９９０］ 利用分布式平台，提出了基于ＭａｐＲｅｄｕｃｅ架构的大 规模历史轨迹数据处理算法，该方法将时空系统分 区，把轨迹数据存储在不同节点上．在处理查询时， 按照同样的分区策略，把查询分布在不同的节点上 执行，最后合并出最终结果． 隐私保护．云计算平台为ＬＢＳ提供了一种新 的运营模式，即ＬＢＳ服务提供商并不一定拥有自己 的云计算平台，而是将自己的数据和服务外包到云 计算平台（由云计算平台服务提供商提供）上运行． 这就带来了新的隐私保护问题，即如何在利用不可 信的云计算平台的同时，获得可信的基于位置的服 务．这类隐私保护方法需要保证两方面安全［９１９２］：既 要求保证被外包的时空数据是隐私的（ｐｒｉｖａｃｙ），即 云计算平台服务提供商无法破解外包的时空数据； 同时也要求用户能对查询的结果完整性（ｉｎｔｅｇｒｉｔｙ） 进行验证，即用户能验证结果是正确并且是完整的， 以防止云计算平台服务提供商篡改和删除某些 结果．７５社会化犔犅犛 随着Ｗｅｂ２．０技术的迅速普及，Ｆｌｉｃｋｅｒ、Ｄｅｌｉ ｃｉｏｕｓ、ＹｏｕＴｕｂｅ和Ｆａｃｅｂｏｏｋ等服务允许用户参与 并共享自己的数据．由于这些数据通常包含３种信 息———时间、空间和人物，因而也常被视为是时间 空间社会数据［９３］．针对这一类型数据的分析可以 更深入地掌握用户的兴趣爱好，并进一步地提供个 性化ＬＢＳ服务．通过对具有空间信息标注的图片的 分析，ＷｏｒｌｄＥｘｐｌｏｒｅｒ提供了一种新的基于地图的 探索服务［９４］． 用户可以对已有的空间对象加文字标注，或者 对其它对象进行具有空间、时间信息的标注．这产生 了一种空间关键字查询服务，即结合空间信息的信 息检索．Ｃｏｎｇ等人［９５］提出了一种算法，综合考虑空 间上的相似度和标注文字的相关程度，通过倒排表 和Ｒｔｒｅｅ索引，返回最相关的犽个空间对象．Ｚｈａｎｇ 等人［９６］提出了犿最近关键字查询和ｂＲｔｒｅｅ索引 结构，可以找到犿个空间上最近、并满足犿个用户 给定的关键字的空间对象． ７６针对紧急情况的犔犅犛 不少学者最近也在关注如何在紧急情况下提供 高质量的ＬＢＳ服务，例如地震、火灾等．在紧急情况 下，周围环境更为恶劣，往往也要求用户快速做出反 应，因而对ＬＢＳ服务的要求更苛刻．例如，火灾现场 充满烟雾、光线黯淡且有很多障碍物［９７］． 当前，许多科研机构均对本问题进行探索，提出 了不少方案．ＳｕｍｍｉｔＳａｆｅｔｙ公司的Ｐａｔｈｆｉｎｄｅｒ系统 利用了超声波技术，能为消防员在黑暗空间中快速 找到安全出口．超声波无法穿墙而过，但是能够绕过 墙角或通过门缝传播．该系统在安全出口处放置若 干超声波发射器，发送不同频率信号．消防员手持超 声波接收仪，分析接收到的信号即可快速制定安全 的路径［９８］．美国国家标准和技术协会（ＮＩＳＴ）利用 ＲＦＩＤ技术研发的ｆｌｉｐｓｉｄｅ系统有助于消防员在黑 暗空间快速定位．与传统的ＲＦＩＤ系统不同，在这个 系统中，ＲＦＩＤ标签是静态的，各消防员穿戴移动的 ＲＦＩＤ阅读器．读到临近的ＲＦＩＤ标签时，即可定 位［９９］．Ｋｌａｎｎ［１００］设计的ＬｉｆｅＮｅｔ系统能够为消防员 在黑暗空间中寻找一条安全路径．该系统也采用超 声波技术，在室内空间布置若干个标杆．消防员可以 携带一个设备，感知临近的信标，并依赖感知到的信 标构造路径，显示到头盔上去．其它代表性的系统还 包括ＰＰＬ［１０１］、ＨｅａｄＳＬＡＭ［１０２］等．这个方向的研究 工作尚未成熟，上述提及的系统中大多处于实验室 环境之中，仅有Ｐａｔｈｆｉｎｄｅｒ系统已经商业化． ８未来的研究工作 基于位置的服务在近几年得到了广泛的研究， ７期 周傲英等：基于位置的服务：架构与进展 １１６５