第34卷第7期 计 算机学报 Vol.34 No.7 2011年7月 CHINESE JOURNAL OF COMPUTERS July 2011 基于位置的服务：架构与进展 周傲英””杨 彬”金澈清”马强” 1”(华东师范大学上海市高可信计算重点实验室上海200062) 2)(复旦大学上海市智能信息处理重点实验室上海200433) 摘要随着无线通信技术和智能移动终端的快速发展，基于位置的服务(Location-based Services,LBS)在军事、 交通、物流等诸多领域得到了广泛应用，它能够根据移动对象的位置信息提供个性化服务，目前，主流的定位技术 大致可分为卫星定位，基于网络基础设施的定位和感知定位三类.LBS使用有效的移动对象时空索引技术来高效 处理服务查询请求，并且采用不同隐私保护策略以有效保护用户的位置隐私.近年来，由于应用场景趋于复杂、多 定位技术协同、数据规模迅速扩大等因素影响，室内LBS、不确定位置信息管理，新型隐私保护技术、云计算平台下 的LBS、社会化LBS等也越来越重要.文中介绍了LBS系统的架构及其各个组成部分的关键技术，回顾了近几年 来LBS技术的研究进展，探讨了未来的研究方向 关键词基于位置的服务：定位技术：移动对象：隐私保护 中图法分类号TP311 D0I号：10.3724/SP.J.1016.2011.01155 Location-Based Services:Architecture and Progress ZHOU Ao-Ying).2)YANG Bin2)JIN Che-Qing)MA Qiang? (Shanghai Key Laboratory of Trustworthy Computing.East China Normal University.Shanghai 200062) 2(Shanghai Key Laboratory of Intelligent In formation Processing.Fudan University.Shanghai 200433) Abstract With the advances in wireless communication technologies and smart mobile devices, Location-based Services (LBS),which provide personalized services based on users'location in- formation,have been widely applied in military,transportation,logistics etc.Currently,main- stream positioning techniques are mainly divided into three categories,including satellite-based positioning,network infrastructure-based positioning and presence sensing positioning.With the help of effective spatio-temporal indexes,LBS are capable of processing the service requests effi- ciently.LBS usually employ different location privacy preservation methods to protect the user privacy.Recently,because of the complexity of applications,the cooperation of multiple positio- ning techniques and the huge data volume,new challenges emerge.Indoor LBS,management of uncertain data,novel location privacy protection method,LBS on cloud infrastructure and social LBS are becoming critical issues.This paper introduces the architecture of an LBS system and the key techniques of its components.Second,After reviewing the main progresses in recent years, we discuss the future work briefly. Keywords location-based services;positioning technologies;moving objects;privacy preservation 收稿日期：2009-12-04：最终修改稿收到日期：2011-03-28.本课题得到国家自然科学基金创新研究群体科学基金(61021004)、国家杰出青 年基金(60925008)、国家自然科学基金面上基金(61070052)和上海市重点学科建设项目(B412)资助.周傲英，男，1965年生，教授，博士 生导师，主要研究兴趣为数据管理与信息系统，包括Wb数据管理、中文Wb基础设施、Web搜索与挖掘、数据流与数据挖掘，复杂事件 处理与实时商务智能、不确定数据管理及其应用、数据密集的计算、分布存储与计算、对等计算及其数据管理，Wb服务计算等.E-mail: ayzhou(@sei.ccnu.edu.cn.杨彬，男，l982年生，博士，主要研究方向为移动数据管理.金澈清（通信作者），男，1977年生，博士，副教授， 主要研究方向为数据流管理，不确定数据管理、基于位置的服务等.E-mail:cqjin@sei.ecnu.edu.cn.马强，男，1984年生，硕士，主要研 究方向为海量数据管理
书 第３４卷第７期 ２０１１年７月 计 算 机 学 报 ＣＨＩＮＥＳＥＪＯＵＲＮＡＬＯＦＣＯＭＰＵＴＥＲＳ Ｖｏｌ．３４Ｎｏ．７ Ｊｕｌｙ２０１１ 收稿日期：２００９１２０４；最终修改稿收到日期：２０１１０３２８．本课题得到国家自然科学基金创新研究群体科学基金（６１０２１００４）、国家杰出青 年基金（６０９２５００８）、国家自然科学基金面上基金（６１０７００５２）和上海市重点学科建设项目（Ｂ４１２）资助．周傲英，男，１９６５年生，教授，博士 生导师，主要研究兴趣为数据管理与信息系统，包括Ｗｅｂ数据管理、中文Ｗｅｂ基础设施、Ｗｅｂ搜索与挖掘、数据流与数据挖掘、复杂事件 处理与实时商务智能、不确定数据管理及其应用、数据密集的计算、分布存储与计算、对等计算及其数据管理、Ｗｅｂ服务计算等．Ｅｍａｉｌ： ａｙｚｈｏｕ＠ｓｅｉ．ｅｃｎｕ．ｅｄｕ．ｃｎ．杨彬，男，１９８２年生，博士，主要研究方向为移动数据管理．金澈清（通信作者），男，１９７７年生，博士，副教授， 主要研究方向为数据流管理、不确定数据管理、基于位置的服务等．Ｅｍａｉｌ：ｃｑｊｉｎ＠ｓｅｉ．ｅｃｎｕ．ｅｄｕ．ｃｎ．马强，男，１９８４年生，硕士，主要研 究方向为海量数据管理． 基于位置的服务：架构与进展 周傲英１），２） 杨彬２） 金澈清１） 马强２） １）（华东师范大学上海市高可信计算重点实验室上海２０００６２） ２）（复旦大学上海市智能信息处理重点实验室上海２００４３３） 摘要随着无线通信技术和智能移动终端的快速发展，基于位置的服务（ＬｏｃａｔｉｏｎｂａｓｅｄＳｅｒｖｉｃｅｓ，ＬＢＳ）在军事、 交通、物流等诸多领域得到了广泛应用，它能够根据移动对象的位置信息提供个性化服务．目前，主流的定位技术 大致可分为卫星定位、基于网络基础设施的定位和感知定位三类．ＬＢＳ使用有效的移动对象时空索引技术来高效 处理服务查询请求，并且采用不同隐私保护策略以有效保护用户的位置隐私．近年来，由于应用场景趋于复杂、多 定位技术协同、数据规模迅速扩大等因素影响，室内ＬＢＳ、不确定位置信息管理、新型隐私保护技术、云计算平台下 的ＬＢＳ、社会化ＬＢＳ等也越来越重要．文中介绍了ＬＢＳ系统的架构及其各个组成部分的关键技术，回顾了近几年 来ＬＢＳ技术的研究进展，探讨了未来的研究方向． 关键词基于位置的服务；定位技术；移动对象；隐私保护 中图法分类号ＴＰ３１１ 犇犗犐号：１０．３７２４／ＳＰ．Ｊ．１０１６．２０１１．０１１５５ 犔狅犮犪狋犻狅狀犅犪狊犲犱犛犲狉狏犻犮犲狊：犃狉犮犺犻狋犲犮狋狌狉犲犪狀犱犘狉狅犵狉犲狊狊 ＺＨＯＵＡｏＹｉｎｇ１），２） ＹＡＮＧＢｉｎ２）ＪＩＮＣｈｅＱｉｎｇ１） ＭＡＱｉａｎｇ２） １）（犛犺犪狀犵犺犪犻犓犲狔犔犪犫狅狉犪狋狅狉狔狅犳犜狉狌狊狋狑狅狉狋犺狔犆狅犿狆狌狋犻狀犵，犈犪狊狋犆犺犻狀犪犖狅狉犿犪犾犝狀犻狏犲狉狊犻狋狔，犛犺犪狀犵犺犪犻２０００６２） ２）（犛犺犪狀犵犺犪犻犓犲狔犔犪犫狅狉犪狋狅狉狔狅犳犐狀狋犲犾犾犻犵犲狀狋犐狀犳狅狉犿犪狋犻狅狀犘狉狅犮犲狊狊犻狀犵，犉狌犱犪狀犝狀犻狏犲狉狊犻狋狔，犛犺犪狀犵犺犪犻２００４３３） 犃犫狊狋狉犪犮狋Ｗｉｔｈｔｈｅａｄｖａｎｃｅｓｉｎｗｉｒｅｌｅｓｓｃｏｍｍｕｎｉｃａｔｉｏｎｔｅｃｈｎｏｌｏｇｉｅｓａｎｄｓｍａｒｔｍｏｂｉｌｅｄｅｖｉｃｅｓ， ＬｏｃａｔｉｏｎｂａｓｅｄＳｅｒｖｉｃｅｓ（ＬＢＳ），ｗｈｉｃｈｐｒｏｖｉｄｅｐｅｒｓｏｎａｌｉｚｅｄｓｅｒｖｉｃｅｓｂａｓｅｄｏｎｕｓｅｒｓ’ｌｏｃａｔｉｏｎｉｎ ｆｏｒｍａｔｉｏｎ，ｈａｖｅｂｅｅｎｗｉｄｅｌｙａｐｐｌｉｅｄｉｎｍｉｌｉｔａｒｙ，ｔｒａｎｓｐｏｒｔａｔｉｏｎ，ｌｏｇｉｓｔｉｃｓｅｔｃ．Ｃｕｒｒｅｎｔｌｙ，ｍａｉｎ ｓｔｒｅａｍｐｏｓｉｔｉｏｎｉｎｇｔｅｃｈｎｉｑｕｅｓａｒｅｍａｉｎｌｙｄｉｖｉｄｅｄｉｎｔｏｔｈｒｅｅｃａｔｅｇｏｒｉｅｓ，ｉｎｃｌｕｄｉｎｇｓａｔｅｌｌｉｔｅｂａｓｅｄ ｐｏｓｉｔｉｏｎｉｎｇ，ｎｅｔｗｏｒｋｉｎｆｒａｓｔｒｕｃｔｕｒｅｂａｓｅｄｐｏｓｉｔｉｏｎｉｎｇａｎｄｐｒｅｓｅｎｃｅｓｅｎｓｉｎｇｐｏｓｉｔｉｏｎｉｎｇ．Ｗｉｔｈｔｈｅ ｈｅｌｐｏｆｅｆｆｅｃｔｉｖｅｓｐａｔｉｏｔｅｍｐｏｒａｌｉｎｄｅｘｅｓ，ＬＢＳａｒｅｃａｐａｂｌｅｏｆｐｒｏｃｅｓｓｉｎｇｔｈｅｓｅｒｖｉｃｅｒｅｑｕｅｓｔｓｅｆｆｉ ｃｉｅｎｔｌｙ．ＬＢＳｕｓｕａｌｌｙｅｍｐｌｏｙｄｉｆｆｅｒｅｎｔｌｏｃａｔｉｏｎｐｒｉｖａｃｙｐｒｅｓｅｒｖａｔｉｏｎｍｅｔｈｏｄｓｔｏｐｒｏｔｅｃｔｔｈｅｕｓｅｒ ｐｒｉｖａｃｙ．Ｒｅｃｅｎｔｌｙ，ｂｅｃａｕｓｅｏｆｔｈｅｃｏｍｐｌｅｘｉｔｙｏｆａｐｐｌｉｃａｔｉｏｎｓ，ｔｈｅｃｏｏｐｅｒａｔｉｏｎｏｆｍｕｌｔｉｐｌｅｐｏｓｉｔｉｏ ｎｉｎｇｔｅｃｈｎｉｑｕｅｓａｎｄｔｈｅｈｕｇｅｄａｔａｖｏｌｕｍｅ，ｎｅｗｃｈａｌｌｅｎｇｅｓｅｍｅｒｇｅ．ＩｎｄｏｏｒＬＢＳ，ｍａｎａｇｅｍｅｎｔｏｆ ｕｎｃｅｒｔａｉｎｄａｔａ，ｎｏｖｅｌｌｏｃａｔｉｏｎｐｒｉｖａｃｙｐｒｏｔｅｃｔｉｏｎｍｅｔｈｏｄ，ＬＢＳｏｎｃｌｏｕｄｉｎｆｒａｓｔｒｕｃｔｕｒｅａｎｄｓｏｃｉａｌ ＬＢＳａｒｅｂｅｃｏｍｉｎｇｃｒｉｔｉｃａｌｉｓｓｕｅｓ．ＴｈｉｓｐａｐｅｒｉｎｔｒｏｄｕｃｅｓｔｈｅａｒｃｈｉｔｅｃｔｕｒｅｏｆａｎＬＢＳｓｙｓｔｅｍａｎｄｔｈｅ ｋｅｙｔｅｃｈｎｉｑｕｅｓｏｆｉｔｓｃｏｍｐｏｎｅｎｔｓ．Ｓｅｃｏｎｄ，Ａｆｔｅｒｒｅｖｉｅｗｉｎｇｔｈｅｍａｉｎｐｒｏｇｒｅｓｓｅｓｉｎｒｅｃｅｎｔｙｅａｒｓ， ｗｅｄｉｓｃｕｓｓｔｈｅｆｕｔｕｒｅｗｏｒｋｂｒｉｅｆｌｙ． 犓犲狔狑狅狉犱狊ｌｏｃａｔｉｏｎｂａｓｅｄｓｅｒｖｉｃｅｓ；ｐｏｓｉｔｉｏｎｉｎｇｔｅｃｈｎｏｌｏｇｉｅｓ；ｍｏｖｉｎｇｏｂｊｅｃｔｓ；ｐｒｉｖａｃｙｐｒｅｓｅｒｖａｔｉｏｎ
1156 计算 机学 报 2011年 户的隐私，LBS系统一般还有位置隐私保护模块， 1 引言 从而不会在向用户提供服务的过程中泄露用户的隐 私.位置隐私保护模块有时也涉及到与第三方可信 随着无线通信技术和智能移动终端的广泛应 机构之间的交互. 用，基于位置的服务(Location-based Service,LBS) 得到飞速发展与普及.基于位置的服务是指移动终 查询处 位置隐 理引擎 私保护 移动 静态 端利用各种定位技术获得当前位置信息，再通过无 数据库 数据南 线网络得到某项服务.早期的LBS系统主要用于在 查询执行模块 存储模块 紧急情况下快速定位求助者的位置，以实施救援，比 中间件模块 定位模块 如美国的E911系统和欧洲的E112系统).当前， LBS已经广泛应用在军事、交通、物流、医疗、民生 6 等领域中.例如，司机可以利用内置GPS功能的智 图1LBS系统的架构 能手机查找最近的加油站，也可制定行车线路.在大 型博物馆（例如故宫博物馆）内，游客可以借助一个 虽然LBS中的许多功能和传统的GIS(Geo 能感知位置的语音导游器来欣赏对各个藏品的 graphic Information Systems)系统相似，但是LBS 讲解 和GIS有许多本质的区别).GIS系统通常可以利 LBS区别于其它传统网络服务的一大特点就 用较多的计算资源，为少数专业技术人员提供专业 是上下文感知性(context aware)以及应对上下文变 的地理数据的分析和处理.而LBS则是为大量普通 化的适应性(adaption).上下文是指描述某个实体 用户提供有限的地理数据服务，并且这些服务要在 状态的任何信息.Nivala等人对基于地图的移动服 资源有限的移动终端上运行，因此，一个LBS服务 务提出了9种上下文信息]：移动地图用户、位置、 提供商通常具备如下几方面特点： 时间、运动方向、导航历史、使用目的、社会和文化状 高性能.快速处理用户的查询请求，以避免长 况、物理环境和系统属性.根据上下文的状况和变 时间等待： 化，需要动态适应LBS的服务内容和表达形式. 可扩展性.能够支持大规模用户和数据； Reichenbacher将适应性划分为4个级别：信息级 高可靠性。保证系统长时间稳定运行； 别、技术级别、用户界面级别和显示级别]」 实时性，支持实时查询动态信息： 1.1LBS的系统架构 移动性，无论移动终端在任何地点都可以为其 图1描述了LBS系统的一般性架构.先进的定 提供服务； 位技术可以实时获取用户/移动对象的位置信息，并 开放性.支持多种公告协议和标准； 发送到LBS系统中去，当前应用最广泛的定位技术 安全性.保护服务提供商的数据和用户的隐私： 无疑就是GPS了，此外也不乏其它定位技术，例如 互操作性.LBS通常需要和其它电子商务服务 GSM,Wi-Fi,RFID Radio Frequency IDentifica- 集成在一起，因此需要有良好的互操作性 tion)等.LBS系统将这些位置信息保存在移动对象 1.2LBS的分类 数据库(Moving()bject Database,MOD)之中，通 根据服务信息的投递是否需要用户的直接交 过构建特定的索引来提高访问效率.此外，LBS系 互，LBS可以分为拉动服务(pull services)和推送服 统还需要保留一些静态GIS信息.用户向LBS系统 务(push services)[.拉动服务是指由用户主动发 发出服务请求，并获取服务.LBS中间件是用户与 送明确的服务请求，服务提供商把所需信息返回给 LBS系统之间的通信媒介，它具有多种模型，包括 用户，就如同用户把所需要的信息从服务提供商那 基于内容的模型(content--based model)、基于主题 里“拉”到用户自己这里.比如，用户发送一个请求 空间的模型(subject space--based model)和元组空 “离我最近的饭店在哪里？”给服务提供商，服务提供 间模型(tuple space model)等，前两个模型又被称 商根据用户当前位置，找到最近的饭店返回给用户 为发布/订阅模型(publish/subscribe model)[). 推送服务则和拉动服务相反，用户没有明确发送服 LBS系统的查询处理引擎访问移动对象数据库和 务请求，而是当某一条件满足时，服务提供商自动将 静态数据库，从而提供用户所需的服务，为了保护用 相关信息返回给用户，推送服务可以分为用户事先
１引言 随着无线通信技术和智能移动终端的广泛应 用，基于位置的服务（ＬｏｃａｔｉｏｎｂａｓｅｄＳｅｒｖｉｃｅ，ＬＢＳ） 得到飞速发展与普及．基于位置的服务是指移动终 端利用各种定位技术获得当前位置信息，再通过无 线网络得到某项服务．早期的ＬＢＳ系统主要用于在 紧急情况下快速定位求助者的位置，以实施救援，比 如美国的Ｅ９１１系统和欧洲的Ｅ１１２系统［１］．当前， ＬＢＳ已经广泛应用在军事、交通、物流、医疗、民生 等领域中．例如，司机可以利用内置ＧＰＳ功能的智 能手机查找最近的加油站，也可制定行车线路．在大 型博物馆（例如故宫博物馆）内，游客可以借助一个 能感知位置的语音导游器来欣赏对各个藏品的 讲解． ＬＢＳ区别于其它传统网络服务的一大特点就 是上下文感知性（ｃｏｎｔｅｘｔａｗａｒｅ）以及应对上下文变 化的适应性（ａｄａｐｔｉｏｎ）．上下文是指描述某个实体 状态的任何信息．Ｎｉｖａｌａ等人对基于地图的移动服 务提出了９种上下文信息［２］：移动地图用户、位置、 时间、运动方向、导航历史、使用目的、社会和文化状 况、物理环境和系统属性．根据上下文的状况和变 化，需要动态适应ＬＢＳ的服务内容和表达形式． Ｒｅｉｃｈｅｎｂａｃｈｅｒ将适应性划分为４个级别：信息级 别、技术级别、用户界面级别和显示级别［３］． １１犔犅犛的系统架构 图１描述了ＬＢＳ系统的一般性架构．先进的定 位技术可以实时获取用户／移动对象的位置信息，并 发送到ＬＢＳ系统中去．当前应用最广泛的定位技术 无疑就是ＧＰＳ了，此外也不乏其它定位技术，例如 ＧＳＭ、ＷｉＦｉ、ＲＦＩＤ（ＲａｄｉｏＦｒｅｑｕｅｎｃｙＩＤｅｎｔｉｆｉｃａ ｔｉｏｎ）等．ＬＢＳ系统将这些位置信息保存在移动对象 数据库（ＭｏｖｉｎｇＯｂｊｅｃｔＤａｔａｂａｓｅ，ＭＯＤ）之中，通 过构建特定的索引来提高访问效率．此外，ＬＢＳ系 统还需要保留一些静态ＧＩＳ信息．用户向ＬＢＳ系统 发出服务请求，并获取服务．ＬＢＳ中间件是用户与 ＬＢＳ系统之间的通信媒介，它具有多种模型，包括 基于内容的模型（ｃｏｎｔｅｎｔｂａｓｅｄｍｏｄｅｌ）、基于主题 空间的模型（ｓｕｂｊｅｃｔｓｐａｃｅｂａｓｅｄｍｏｄｅｌ）和元组空 间模型（ｔｕｐｌｅｓｐａｃｅｍｏｄｅｌ）等，前两个模型又被称 为发布／订阅模型（ｐｕｂｌｉｓｈ／ｓｕｂｓｃｒｉｂｅｍｏｄｅｌ）［４］． ＬＢＳ系统的查询处理引擎访问移动对象数据库和 静态数据库，从而提供用户所需的服务．为了保护用 户的隐私，ＬＢＳ系统一般还有位置隐私保护模块， 从而不会在向用户提供服务的过程中泄露用户的隐 私．位置隐私保护模块有时也涉及到与第三方可信 机构之间的交互． 图１ＬＢＳ系统的架构 虽然ＬＢＳ中的许多功能和传统的ＧＩＳ（Ｇｅｏ ｇｒａｐｈｉｃＩｎｆｏｒｍａｔｉｏｎＳｙｓｔｅｍｓ）系统相似，但是ＬＢＳ 和ＧＩＳ有许多本质的区别［１］．ＧＩＳ系统通常可以利 用较多的计算资源，为少数专业技术人员提供专业 的地理数据的分析和处理．而ＬＢＳ则是为大量普通 用户提供有限的地理数据服务，并且这些服务要在 资源有限的移动终端上运行．因此，一个ＬＢＳ服务 提供商通常具备如下几方面特点： 高性能．快速处理用户的查询请求，以避免长 时间等待； 可扩展性．能够支持大规模用户和数据； 高可靠性．保证系统长时间稳定运行； 实时性．支持实时查询动态信息； 移动性．无论移动终端在任何地点都可以为其 提供服务； 开放性．支持多种公告协议和标准； 安全性．保护服务提供商的数据和用户的隐私； 互操作性．ＬＢＳ通常需要和其它电子商务服务 集成在一起，因此需要有良好的互操作性． １２犔犅犛的分类 根据服务信息的投递是否需要用户的直接交 互，ＬＢＳ可以分为拉动服务（ｐｕｌｌｓｅｒｖｉｃｅｓ）和推送服 务（ｐｕｓｈｓｅｒｖｉｃｅｓ）［４］．拉动服务是指由用户主动发 送明确的服务请求，服务提供商把所需信息返回给 用户，就如同用户把所需要的信息从服务提供商那 里“拉”到用户自己这里．比如，用户发送一个请求 “离我最近的饭店在哪里？”给服务提供商，服务提供 商根据用户当前位置，找到最近的饭店返回给用户． 推送服务则和拉动服务相反，用户没有明确发送服 务请求，而是当某一条件满足时，服务提供商自动将 相关信息返回给用户．推送服务可以分为用户事先 １１５６ 计 算 机 学 报 ２０１１年
7期 周傲英等：基于位置的服务：架构与进展 1157 同意和用户事先未同意两个子类.用户事先同意的 服务通常是通过向服务提供商订阅(subscription) 2 定位技术 实现，比如：用户订阅根据当前位置提供天气预报信 息的服务，当用户从上海到达北京时，服务提供商就 基于位置的服务的基础是高质量地获取位置信 将北京的天气资料发给该用户，用户未事先同意的 息.定位技术主要有3类：卫星定位技术、基于网络 服务一般指的是广告投递服务，比如：服务提供商将 的定位技术和感知定位技术，卫星定位技术是指利 某商场的促销信息发送给周边的用户. 用太空中的人造卫星对移动对象进行定位，典型代 根据服务对象的不同，LBS又可以分为特定服 表是GPS.基于网络的定位技术是指利用网络基站 务和通用服务.特定服务是指为特定人群或特定地 (或者接入点)等基础设施对移动对象进行定位，当 区提供的服务，例如医院的残疾人跟踪服务、景点的 移动终端被某一网络覆盖区域感知时，由网络基站 自助导游服务等.特定服务需要服务提供商维护特 或控制点计算出该移动终端的位置，典型代表是移 定数据集合，比如旅游景点的相关信息.通用服务是 动通信网络（如GSM,CDMA等）.感知定位技术指 指通信提供商对其所有用户提供的通用服务，OGC 在指定空间内部署传感器，当移动对象进入传感器 (Open Geospatial Consortium)OpenLS(Open 的检测区域时，则能判定该对象的位置，典型代表是 Location Services)标准规定了6种基本的通用服 无线射频识别技术(RFID). 务：目录服务、网关服务、位置工具（地理编码和反地 卫星定位技术.目前在室外空间最为广泛使用的 理编码)服务、显示服务、路径服务和导航服务 卫星定位技术是GPS(Global Positioning System). 根据服务处理技术的不同，LBS又可以分为快 GPS全球定位系统是由美国国防部于1978年设计 照查询服务(snapshot queries)和连续查询服务 研制的，起初只用于军事用途[).美国于2000年全 (continuous queries).快照查询服务根据查询条件， 面放开GPS对普通民众的使用权限，使得GPS广 一次执行，返回结果；连续查询根据移动对象的位置 泛应用于民用交通导航.类似定位系统有欧洲的伽 变换信息持续更新查询结果，通常情况下，推送服务 利略系统、俄罗斯的GLONASS系统.我国也已经 通过连续查询来实现」 实验开发了北斗1定位系统，北斗2定位系统正在 目前已经有一些LBS相关技术的综述文献. 研究中.GPS能将终端的位置限制在经度、纬度、 D'Roza和Bilchevl)总结了LBS中常见的室外定位 高度组成的三维坐标系统内，其它改进型技术还 包括差分GPS技术和辅助GPS技术等.差分GPS 技术，综述了LBS中数据传递的格式和协议.Liu等 (Differential GPS)系统可以纠正卫星信号在电离 人[描述了主流的室内定位技术.Jiang和Yao)分 层和对流层传输时的时间误差，进而提高精度.辅助 析了LBS的常见应用情景和特点，指出了LBS与 GPS(Assistant-GPS)系统是指使用一些辅助数据 GIS系统之间的差异.Mokbel等人[)对如何提高 (例如地面的移动网络基站)来提高GPS在弱信号 LBS查询的可扩展性进行了综述，提出了共享执行 下的定位精度.当外部条件良好时，GPS能够获得 策略.Lee等人[s]初步探讨了室内、室外空间不同的 较佳的定位效果.但是GPS的精度较易受到周围环 位置系统模型和相应的查询.潘晓等人[)则对LBS 境的影响，例如高大建筑、室内空间等。 中的隐私保护方法进行了综述.Schiller和Voisard] 基于网络的定位技术.这种定位技术往往依赖 编辑的书较为全面地介绍了LBS系统，该书出版于 于移动通信网络设施.移动通信网络通常通过CO) 2004年，无法收录之后的LBS研究进展.本文围绕 (Cell Of Origin)s)进行定位，将移动终端定位在其 LBS的架构，介绍关键技术，特别是新近的研究 注册的基站的覆盖范围内.因此，移动通信网络 进展. COO定位的精度和基站覆盖范围紧密相关.尽管使 本文第2节回顾主流定位技术；第3节介绍针 用一些辅助手段有助于提升精度，但总体来说这类 对移动对象的索引技术；第4节描述3个主要的中 定位技术的精度较低.此外，还可以依赖无线局域网 间件模型：第5、6节分别介绍LBS系统的查询处理 进行定位，如Wi-Fi等.基于Wi-Fi的定位通常根据 技术和位置隐私保护技术；第7节着重叙述近期 Wi-Fi访问点(Access Point or Hotspot)的已知部 LBS的研究进展：第8节探讨未来的研究方向；最 署位置和信号强弱进行定位，主要有基于三边测量 后，在第9节总结全文 的方法[1和基于信号强度指纹的方法[].基于三边
同意和用户事先未同意两个子类．用户事先同意的 服务通常是通过向服务提供商订阅（ｓｕｂｓｃｒｉｐｔｉｏｎ） 实现，比如：用户订阅根据当前位置提供天气预报信 息的服务．当用户从上海到达北京时，服务提供商就 将北京的天气资料发给该用户．用户未事先同意的 服务一般指的是广告投递服务，比如：服务提供商将 某商场的促销信息发送给周边的用户． 根据服务对象的不同，ＬＢＳ又可以分为特定服 务和通用服务．特定服务是指为特定人群或特定地 区提供的服务，例如医院的残疾人跟踪服务、景点的 自助导游服务等．特定服务需要服务提供商维护特 定数据集合，比如旅游景点的相关信息．通用服务是 指通信提供商对其所有用户提供的通用服务．ＯＧＣ （ＯｐｅｎＧｅｏｓｐａｔｉａｌＣｏｎｓｏｒｔｉｕｍ）的ＯｐｅｎＬＳ（Ｏｐｅｎ ＬｏｃａｔｉｏｎＳｅｒｖｉｃｅｓ）标准规定了６种基本的通用服 务：目录服务、网关服务、位置工具（地理编码和反地 理编码）服务、显示服务、路径服务和导航服务． 根据服务处理技术的不同，ＬＢＳ又可以分为快 照查询服务（ｓｎａｐｓｈｏｔｑｕｅｒｉｅｓ）和连续查询服务 （ｃｏｎｔｉｎｕｏｕｓｑｕｅｒｉｅｓ）．快照查询服务根据查询条件， 一次执行，返回结果；连续查询根据移动对象的位置 变换信息持续更新查询结果．通常情况下，推送服务 通过连续查询来实现． 目前已经有一些ＬＢＳ相关技术的综述文献． Ｄ’Ｒｏｚａ和Ｂｉｌｃｈｅｖ［５］总结了ＬＢＳ中常见的室外定位 技术，综述了ＬＢＳ中数据传递的格式和协议．Ｌｉｕ等 人［６］描述了主流的室内定位技术．Ｊｉａｎｇ和Ｙａｏ［１］分 析了ＬＢＳ的常见应用情景和特点，指出了ＬＢＳ与 ＧＩＳ系统之间的差异．Ｍｏｋｂｅｌ等人［７］对如何提高 ＬＢＳ查询的可扩展性进行了综述，提出了共享执行 策略．Ｌｅｅ等人［８］初步探讨了室内、室外空间不同的 位置系统模型和相应的查询．潘晓等人［９］则对ＬＢＳ 中的隐私保护方法进行了综述．Ｓｃｈｉｌｌｅｒ和Ｖｏｉｓａｒｄ［４］ 编辑的书较为全面地介绍了ＬＢＳ系统，该书出版于 ２００４年，无法收录之后的ＬＢＳ研究进展．本文围绕 ＬＢＳ的架构，介绍关键技术，特别是新近的研究 进展．本文第２节回顾主流定位技术；第３节介绍针 对移动对象的索引技术；第４节描述３个主要的中 间件模型；第５、６节分别介绍ＬＢＳ系统的查询处理 技术和位置隐私保护技术；第７节着重叙述近期 ＬＢＳ的研究进展；第８节探讨未来的研究方向；最 后，在第９节总结全文． ２定位技术 基于位置的服务的基础是高质量地获取位置信 息．定位技术主要有３类：卫星定位技术、基于网络 的定位技术和感知定位技术．卫星定位技术是指利 用太空中的人造卫星对移动对象进行定位，典型代 表是ＧＰＳ．基于网络的定位技术是指利用网络基站 （或者接入点）等基础设施对移动对象进行定位．当 移动终端被某一网络覆盖区域感知时，由网络基站 或控制点计算出该移动终端的位置，典型代表是移 动通信网络（如ＧＳＭ，ＣＤＭＡ等）．感知定位技术指 在指定空间内部署传感器，当移动对象进入传感器 的检测区域时，则能判定该对象的位置，典型代表是 无线射频识别技术（ＲＦＩＤ）． 卫星定位技术．目前在室外空间最为广泛使用的 卫星定位技术是ＧＰＳ（ＧｌｏｂａｌＰｏｓｉｔｉｏｎｉｎｇＳｙｓｔｅｍ）． ＧＰＳ全球定位系统是由美国国防部于１９７８年设计 研制的，起初只用于军事用途［５］．美国于２０００年全 面放开ＧＰＳ对普通民众的使用权限，使得ＧＰＳ广 泛应用于民用交通导航．类似定位系统有欧洲的伽 利略系统、俄罗斯的ＧＬＯＮＡＳＳ系统．我国也已经 实验开发了北斗１定位系统，北斗２定位系统正在 研究中．ＧＰＳ能将终端的位置限制在经度、纬度、 高度组成的三维坐标系统内．其它改进型技术还 包括差分ＧＰＳ技术和辅助ＧＰＳ技术等．差分ＧＰＳ （ＤｉｆｆｅｒｅｎｔｉａｌＧＰＳ）系统可以纠正卫星信号在电离 层和对流层传输时的时间误差，进而提高精度．辅助 ＧＰＳ（ＡｓｓｉｓｔａｎｔＧＰＳ）系统是指使用一些辅助数据 （例如地面的移动网络基站）来提高ＧＰＳ在弱信号 下的定位精度．当外部条件良好时，ＧＰＳ能够获得 较佳的定位效果．但是ＧＰＳ的精度较易受到周围环 境的影响，例如高大建筑、室内空间等． 基于网络的定位技术．这种定位技术往往依赖 于移动通信网络设施．移动通信网络通常通过ＣＯＯ （ＣｅｌｌＯｆＯｒｉｇｉｎ）［５］进行定位，将移动终端定位在其 注册的基站的覆盖范围内．因此，移动通信网络 ＣＯＯ定位的精度和基站覆盖范围紧密相关．尽管使 用一些辅助手段有助于提升精度，但总体来说这类 定位技术的精度较低．此外，还可以依赖无线局域网 进行定位，如ＷｉＦｉ等．基于ＷｉＦｉ的定位通常根据 ＷｉＦｉ访问点（ＡｃｃｅｓｓＰｏｉｎｔｏｒＨｏｔｓｐｏｔ）的已知部 署位置和信号强弱进行定位，主要有基于三边测量 的方法［１０］和基于信号强度指纹的方法［１１］．基于三边 ７期 周傲英等：基于位置的服务：架构与进展 １１５７
1158 计算 机 学 报 2011年 测量的方法通过信号传递模型，将接收到的信号强 术.RFID系统通常包括两个组成部分：RFID阅读 度转换为到访问点的距离，进而利用三边测量法定 器和RFID标签.RFID阅读器能感知其覆盖区域内 位.但是由于室内影响信号强度的因素很多，这使 出现的RFID标签.当携带RFID标签的对象被某 得建立一个通用的信号传播模型并不简单，而模 一RFD阅读器感知时，即可对该对象定位.该方法 型的好坏直接影响到定位的效果.基于信号强度指 与移动通信网络的C(O)方法类似，但是RFID的覆 纹的方法首先将事先选择的室内空间每个参考点到 盖区域要小很多，主要用于室内空间.这使得RFID 所有Wi-Fi访问点的信号强度（即指纹）记录到数 定位的位置通常被限制在符号系统中，符号系统比 据库，终端根据当前自身到所有访问点的信号强 几何坐标系统更适合描述室内空间，比如人们通常 度信息在指纹数据库中查找与其最接近的参考 用房间号码来指示一个室内位置，而不是通过经纬 点，并用该参考点的位置定位移动终端.这种方法 度.另一方面，通过RFD读卡器的部署信息，可以 的精度在很大程度上取决于参考点选取的数量和 将符号系统的坐标转化为几何坐标系统.因此，为了 位置. 更好地利用RFID进行室内定位，需要综合考虑室 感知定位技术，感知定位技术适用于短距离识 内空间的平面规划和RFD阅读器的部署.此外，蓝 别.一般而言，需要一个信号发送端和一个信号接收 牙、红外等也是比较典型的感知定位技术。 端.当信号发送端和信号接收端相互间距离很小时， 表1总结了各类定位技术的特点。 则能够被识别.RFID就是一种典型的感知定位技 表1定位技术对比 类别 代表性技术 精度 覆盖范固 应用场景 定位坐标 卫星定位技术 GPS,北斗，你利略 中高 广 室外 几何坐标 基于网铬的定位技术 GSM.3G.CDMA.Wi-Fi 中低 较广 室外/室内 几何坐标 感知定位技术 RFID,蓝牙，红外 小 室内 符号坐标 由于室内、室外的环境不同，定位技术的工作原 出现了一批有针对性的移动对象历史轨迹索引技术 理不同，使得很难有一种定位技术能同时广泛地支 和移动对象当前/将来位置索引技术，历史轨迹索引 持室内和室外定位.为了给服务提供商进行统一的 技术不仅考虑对象的空间位置，也考虑时间维度：当 室内外定位信息，需要在室内室外定位技术之间进 前-将来位置索引技术则对于移动对象位置的更新 行切换.Hansen等人]对这一问题进行了研究，提 操作具有良好的适应性。 出了针对室外GPS定位和室内Wi-Fi定位之间的 3.1历史轨迹索引技术 4种切换策略.相对于室外空间的成熟定位技术，近 首先我们来讨论索引移动对象历史轨迹的方 年来对室内空间的各类定位技术的研究比较集中， 法.历史轨迹的索引方法可以分为两类：基于R-tree 但大部分研究集中在如何提高某一个特定技术的定 的索引和基于Hash的索引.基于R-tree的历史轨 位精度.如何通过多种室内定位技术获得更精确的 迹索引方法将时间维视为一个普通维，将移动对象 位置信息也有较高的研究价值，即提供一种通用的 的轨迹表示成多维空间内的一组线段，再用R-tree 室内定位模型. 进行索引.如图2所示，一个移动对象的轨迹被表现 在二维几何空间范围(x,y)和一个时间维(t)的三维 3索引技术 空间内. 索引技术是移动对象数据库的核心技术，决定 了LBS的查询性能.对空间数据的索引技术的研究 工作已经开展了20余年的时间，出现了R-tree家 族1s1们、KD-tree家族s-1和Quard--tree家族]等 代表性的索引技术.这类空间索引技术能够有效实 现对静态空间对象的索引.然而，当移动对象频繁移 动时，上述索引技术的性能显著下降.因此，近年来 图？室外移动对象在几何坐标下的移动轨迹四]
测量的方法通过信号传递模型，将接收到的信号强 度转换为到访问点的距离，进而利用三边测量法定 位．但是由于室内影响信号强度的因素很多，这使 得建立一个通用的信号传播模型并不简单，而模 型的好坏直接影响到定位的效果．基于信号强度指 纹的方法首先将事先选择的室内空间每个参考点到 所有ＷｉＦｉ访问点的信号强度（即指纹）记录到数 据库，终端根据当前自身到所有访问点的信号强 度信息在指纹数据库中查找与其最接近的参考 点，并用该参考点的位置定位移动终端．这种方法 的精度在很大程度上取决于参考点选取的数量和 位置．感知定位技术．感知定位技术适用于短距离识 别．一般而言，需要一个信号发送端和一个信号接收 端．当信号发送端和信号接收端相互间距离很小时， 则能够被识别．ＲＦＩＤ就是一种典型的感知定位技 术．ＲＦＩＤ系统通常包括两个组成部分：ＲＦＩＤ阅读 器和ＲＦＩＤ标签．ＲＦＩＤ阅读器能感知其覆盖区域内 出现的ＲＦＩＤ标签．当携带ＲＦＩＤ标签的对象被某 一ＲＦＩＤ阅读器感知时，即可对该对象定位．该方法 与移动通信网络的ＣＯＯ方法类似，但是ＲＦＩＤ的覆 盖区域要小很多，主要用于室内空间．这使得ＲＦＩＤ 定位的位置通常被限制在符号系统中．符号系统比 几何坐标系统更适合描述室内空间，比如人们通常 用房间号码来指示一个室内位置，而不是通过经纬 度．另一方面，通过ＲＦＩＤ读卡器的部署信息，可以 将符号系统的坐标转化为几何坐标系统．因此，为了 更好地利用ＲＦＩＤ进行室内定位，需要综合考虑室 内空间的平面规划和ＲＦＩＤ阅读器的部署．此外，蓝 牙、红外等也是比较典型的感知定位技术． 表１总结了各类定位技术的特点． 表１定位技术对比 类别 代表性技术 精度 覆盖范围 应用场景 定位坐标 卫星定位技术 ＧＰＳ，北斗，伽利略 中高 广 室外 几何坐标 基于网络的定位技术 ＧＳＭ，３Ｇ，ＣＤＭＡ，ＷｉＦｉ 中低 较广 室外／室内 几何坐标 感知定位技术 ＲＦＩＤ，蓝牙，红外 高 小 室内 符号坐标 由于室内、室外的环境不同，定位技术的工作原 理不同，使得很难有一种定位技术能同时广泛地支 持室内和室外定位．为了给服务提供商进行统一的 室内外定位信息，需要在室内室外定位技术之间进 行切换．Ｈａｎｓｅｎ等人［１２］对这一问题进行了研究，提 出了针对室外ＧＰＳ定位和室内ＷｉＦｉ定位之间的 ４种切换策略．相对于室外空间的成熟定位技术，近 年来对室内空间的各类定位技术的研究比较集中． 但大部分研究集中在如何提高某一个特定技术的定 位精度．如何通过多种室内定位技术获得更精确的 位置信息也有较高的研究价值，即提供一种通用的 室内定位模型． ３索引技术 索引技术是移动对象数据库的核心技术，决定 了ＬＢＳ的查询性能．对空间数据的索引技术的研究 工作已经开展了２０余年的时间，出现了Ｒｔｒｅｅ家 族［１３１４］、ＫＤｔｒｅｅ家族［１５１６］和Ｑｕａｒｄｔｒｅｅ家族［１７］等 代表性的索引技术．这类空间索引技术能够有效实 现对静态空间对象的索引．然而，当移动对象频繁移 动时，上述索引技术的性能显著下降．因此，近年来 出现了一批有针对性的移动对象历史轨迹索引技术 和移动对象当前／将来位置索引技术．历史轨迹索引 技术不仅考虑对象的空间位置，也考虑时间维度；当 前将来位置索引技术则对于移动对象位置的更新 操作具有良好的适应性． ３１历史轨迹索引技术 首先我们来讨论索引移动对象历史轨迹的方 法．历史轨迹的索引方法可以分为两类：基于Ｒｔｒｅｅ 的索引和基于Ｈａｓｈ的索引．基于Ｒｔｒｅｅ的历史轨 迹索引方法将时间维视为一个普通维，将移动对象 的轨迹表示成多维空间内的一组线段，再用Ｒｔｒｅｅ 进行索引．如图２所示，一个移动对象的轨迹被表现 在二维几何空间范围（狓，狔）和一个时间维（狋）的三维 空间内． 图２室外移动对象在几何坐标下的移动轨迹［２２］ １１５８ 计 算 机 学 报 ２０１１年
7期 周做英等：基于位置的服务：架构与进展 1159 3DR-tree1町把时间维当作一个额外的空间维， 的目录删除后再插入，或者是将该节点的MBR进 不区分空间维和时间维，用一个3DR-tree统一对 行扩展以包含该对象的新位置，为了应对移动对象 在这个三维空间内的轨迹进行索引，使得空间查询、 频繁的更新操作，RUM-tree2]利用保存在内存的 时间查询、时空查询在3DR-tree上统一实现.MR- 特定信息，在更新时能避免访问磁盘来实现删除旧 tree)和HR-tree2o]对每一个时刻的移动对象的位 条目.而过期的旧条目将以批处理方式移除，从而提 置建立一个R-tree.为了节省索引的空间，对连续时 高了更新操作的效率. 刻内位置未发生改变的移动对象不再进行保存，而 3.3将来位置索引技术 是通过指针指向前一个节点.MV3R-tree2)同时维 为了索引未来时刻的移动对象位置，通常情况 护两棵树：MVR-tree和3DR-tree,其中MVR-tree 下需要根据移动对象的速度V对移动对象的未来 用于处理时间参数为时刻的时空查询，3DR-tree用 位置建模，即locationnew=locationo十VX(tnew一 于处理时间参数为时间间隔的时空查询.为了处理 t).对移动对象将来位置的索引技术分为两类：基 针对轨迹的查询，TB-tree2利用类似R-tree的结 于R-tree的索引结构和基于B+-tree的索引结构. 构，但是它要求每个节点只保存来自于同一移动对 TPR-tree2]和TPR'-tree[so]使用时间参数的MBR 象轨迹的时空数据.这样，在时空上临近但不属于一 来组织移动对象，在组织节点时不仅考虑移动对象 个移动对象轨迹的数据将被分别保存在不同的节 当前的位置，也考虑移动对象的速度，因而MBR能 点内 随时间的变化而扩展.当移动对象的位置更新时，则 基于Hash的索引结构通常将空间维和时间维 重新计算包含该对象的MBR.由于这类索引结构保 分开处理.SET2]把空间维和时间维区分开：使用 存了速度信息，因而能预测移动对象的将来位置 静态、无重叠的网格划分空间维度（如图3所示）：使 REr-tree)是TPR-tree的一种扩展，它针对部分 用一维R-tree索引各空间网格内的时间维度.Song 移动对象长时间不更新位置信息导致MBR不断扩 在其相关研究中也是先按照空间维度使用静态的网 大的缺点，设定一个失效时间以删除失效的移动对 格划分[2)，而对每个空间网格内的对象的时间属性 象或重新计算.VCIR--tree]额外保持每个R-tree 进行转化，用SEB-tree2进行素引. 节点的所有对象的最大速度，在查询处理时，根据查 询时间和最大速度对MBR或查询本身进行扩展， 如图4所示. 扩展的MBR MBR.V 图3SETI中基于空间的网格划分[2] 3.2当前位置索引技术 Query 移动对象的位置随时间不停变化，这就要求索 引结构能够应对大量更新操作.2十3R-tree[ze)是一 种既能索引历史轨迹，又能索引当前位置的方法，它 MBR2,V 扩展的Query 维护了两个R-tree,一个2DR-tree用于索引移动对 R △XVm 象当前位置，另一个3DR-tree用于索引移动对象 R 的历史轨迹.当移动对象的位置改变时，一条新的轨 Query: 迹线段被构造出来并插入至3DR-tree中，与此同 时，新位置插人到2DR-tree中，且旧位置从2D R-tree中移除.LUR-treel2)通过R-tree索引移动对 象的当前位置，以满足移动对象频繁的位置更新操 图4VCIR-tree处理范围查询时的MBR扩展和查询扩展[町 作.一旦移动对象的位置改变，新的位置将及时更新 利用B+-tree对移动对象建立索引也是一种重 到R-tree中.如果新位置仍然在其原先节点的 要的方法.B-tree]是第一个基于B+-tree索引移 MBR内，只需更改该目录的位置；如果新的位置超 动对象的方法.整个空间被划分为若干个单元格，借 出其节点的MBR,则根据不同策略选择是将该对象 助于空间填充曲线(space filling curve),每个单元
３ＤＲｔｒｅｅ［１８］把时间维当作一个额外的空间维， 不区分空间维和时间维，用一个３ＤＲｔｒｅｅ统一对 在这个三维空间内的轨迹进行索引，使得空间查询、 时间查询、时空查询在３ＤＲｔｒｅｅ上统一实现．ＭＲ ｔｒｅｅ［１９］和ＨＲｔｒｅｅ［２０］对每一个时刻的移动对象的位 置建立一个Ｒｔｒｅｅ．为了节省索引的空间，对连续时 刻内位置未发生改变的移动对象不再进行保存，而 是通过指针指向前一个节点．ＭＶ３Ｒｔｒｅｅ［２１］同时维 护两棵树：ＭＶＲｔｒｅｅ和３ＤＲｔｒｅｅ，其中ＭＶＲｔｒｅｅ 用于处理时间参数为时刻的时空查询，３ＤＲｔｒｅｅ用 于处理时间参数为时间间隔的时空查询．为了处理 针对轨迹的查询，ＴＢｔｒｅｅ［２２］利用类似Ｒｔｒｅｅ的结 构，但是它要求每个节点只保存来自于同一移动对 象轨迹的时空数据．这样，在时空上临近但不属于一 个移动对象轨迹的数据将被分别保存在不同的节 点内．基于Ｈａｓｈ的索引结构通常将空间维和时间维 分开处理．ＳＥＴＩ［２３］把空间维和时间维区分开：使用 静态、无重叠的网格划分空间维度（如图３所示）；使 用一维Ｒｔｒｅｅ索引各空间网格内的时间维度．Ｓｏｎｇ 在其相关研究中也是先按照空间维度使用静态的网 格划分［２４］，而对每个空间网格内的对象的时间属性 进行转化，用ＳＥＢｔｒｅｅ［２５］进行索引． 图３ＳＥＴＩ中基于空间的网格划分［２３］ ３２当前位置索引技术 移动对象的位置随时间不停变化，这就要求索 引结构能够应对大量更新操作．２＋３Ｒｔｒｅｅ［２６］是一 种既能索引历史轨迹，又能索引当前位置的方法，它 维护了两个Ｒｔｒｅｅ，一个２ＤＲｔｒｅｅ用于索引移动对 象当前位置，另一个３ＤＲｔｒｅｅ用于索引移动对象 的历史轨迹．当移动对象的位置改变时，一条新的轨 迹线段被构造出来并插入至３ＤＲｔｒｅｅ中，与此同 时，新位置插入到２ＤＲｔｒｅｅ中，且旧位置从２Ｄ Ｒｔｒｅｅ中移除．ＬＵＲｔｒｅｅ［２７］通过Ｒｔｒｅｅ索引移动对 象的当前位置，以满足移动对象频繁的位置更新操 作．一旦移动对象的位置改变，新的位置将及时更新 到Ｒｔｒｅｅ中．如果新位置仍然在其原先节点的 ＭＢＲ内，只需更改该目录的位置；如果新的位置超 出其节点的ＭＢＲ，则根据不同策略选择是将该对象 的目录删除后再插入，或者是将该节点的ＭＢＲ进 行扩展以包含该对象的新位置．为了应对移动对象 频繁的更新操作，ＲＵＭｔｒｅｅ［２８］利用保存在内存的 特定信息，在更新时能避免访问磁盘来实现删除旧 条目．而过期的旧条目将以批处理方式移除，从而提 高了更新操作的效率． ３３将来位置索引技术 为了索引未来时刻的移动对象位置，通常情况 下需要根据移动对象的速度犞对移动对象的未来 位置建模，即犾狅犮犪狋犻狅狀ｎｅｗ＝犾狅犮犪狋犻狅狀ｏｌｄ＋犞×（狋ｎｅｗ－ 狋ｏｌｄ）．对移动对象将来位置的索引技术分为两类：基 于Ｒｔｒｅｅ的索引结构和基于Ｂ＋ｔｒｅｅ的索引结构． ＴＰＲｔｒｅｅ［２９］和ＴＰＲｔｒｅｅ［３０］使用时间参数的ＭＢＲ 来组织移动对象，在组织节点时不仅考虑移动对象 当前的位置，也考虑移动对象的速度，因而ＭＢＲ能 随时间的变化而扩展．当移动对象的位置更新时，则 重新计算包含该对象的ＭＢＲ．由于这类索引结构保 存了速度信息，因而能预测移动对象的将来位置． ＲＥＸＰｔｒｅｅ［３１］是ＴＰＲｔｒｅｅ的一种扩展，它针对部分 移动对象长时间不更新位置信息导致ＭＢＲ不断扩 大的缺点，设定一个失效时间以删除失效的移动对 象或重新计算．ＶＣＩＲｔｒｅｅ［３２］额外保持每个Ｒｔｒｅｅ 节点的所有对象的最大速度，在查询处理时，根据查 询时间和最大速度对ＭＢＲ或查询本身进行扩展， 如图４所示． 图４ＶＣＩＲｔｒｅｅ处理范围查询时的ＭＢＲ扩展和查询扩展［３２］ 利用Ｂ＋ｔｒｅｅ对移动对象建立索引也是一种重 要的方法．Ｂｘｔｒｅｅ［３３］是第一个基于Ｂ＋ｔｒｅｅ索引移 动对象的方法．整个空间被划分为若干个单元格，借 助于空间填充曲线（ｓｐａｃｅｆｉｌｌｉｎｇｃｕｒｖｅ），每个单元 ７期 周傲英等：基于位置的服务：架构与进展 １１５９
1160 计 算 机 学报 2011年 格被赋予一个标识符.移动对象所在的单元格的标 矩形框（左下角坐标(100,150），右上角坐标(120， 识符值被B+-tree进行索引.当处理范围查询时，需 180)内的移动对象感兴趣.因此，这个事件不会发 要通过移动对象的速度和相对时间对范围进行扩 送到订阅者， 展.Jensen等人[a)提出了支持更精确的范围查询的 基于内容的模型比较简单，但是无法记录发布 扩展算法.Yiu等人a]提出了B-tree,将一个二维 者或者订阅者的状态.例如，假设某用户（订阅者）不 的移动对象映射到四维的对偶空间进行索引.Chen 愿一天之内接连看两场电影，则最好不要在一天内 等人[3]针对移动对象经常在时空范围内发生变化 多次向他发送电影放映通知.由于基于内容的模型 的特点，提出了一种可自适应调节的STB-tree索 并不记录历史事件，无法满足这个需求，因此可以应 结构」 用基于主题空间的模型. 此外，STRIPESCs)是一个对位置和速度进行索 4.2基于主题空间的模型 引的对偶索引，它将在二维空间移动的移动对象映 基于主题空间的模型的核心概念是主题空间. 射到四维的对偶空间，并对四维空间进行PR Quad 一个主题空间实际上是一个多维空间，空间中的每 tree)索引.这样的结构提高了更新效率，但是却对 个维度分别被定义为一个元组d={name,type}, 查询效率有所影响.针对不同的当前/将来位置索引 其中ame是维度的唯一标识符，type表示数据类 技术，Chen等人[a]提出了一个测试基准，并对主要 型.例如，关于位置的主题空间可以被描述为 的当前/将来位置索引方法的特性进行了详细的比较. {(x,double),(y,double)}.此外，兴趣区域(interest region)表示订阅者感兴趣的一个子域，在某个主题 4 LBS中间件模型 空间中；对象区域(object region)表示一个对象的状 态或者属性.订阅者的订阅请求指定一组兴趣区域 中间件技术广泛地用于移动计算环境之中. 和一个过滤函数，以查看对象区域是否符合订阅标 LBS系统将LBS中间件作为服务处理引擎与终端用 准；发布者的发布准则指定了一组对象区域和一个 户之间的软件载体，隐藏了具体技术细节，便于向客 过滤函数，以查看兴趣区域是否与本次发布匹配.可 户端提供服务.主要的LBS中间件模型有三种，包括 基于内容的模型(content-based model)、基于主题 以通过订阅请求和发布准则来判定是否匹配0 在基于主题空间的模型中，信息在发布之后仍 空间的模型(subject space--based model)和元组空 旧会保留在系统之中，而不是直接被移除，因此该模 间模型(tuple space model),前两个模型又可被归 为发布/订阅模型(publish,/subscribe model).发布/ 型支持有状态的发布/订阅.此外，也有助于实现对 订阅模型是移动计算中应用最为广泛的中间件模型 称的发布/订阅系统.换句话说，仅当发布准则与订 之一.该模型中有两个角色：发布者和订阅者（也称 阅请求匹配时才会向订阅者发送信息.这个特性能 消费者)，二者之间通过事件交换信息，发布者产生 有效降低信息发布量，避免了冗余信息的传播， 事件，订阅者向发布者发送订阅请求.当特定事件发 4.3元组空间模型 生时，即可将该事件通知订阅者.发布者与订阅者之 元组空间模型最早被用于并行编程领域，以协 间的联系并不紧密，是松耦合的：换言之，当订阅者 调并发执行的任务，一个元组是一个包含多项值的 暂时无法工作时，发布者仍可发布事件4]」 矢量，元组空间是一个包含许多元组的集合.多个任 4.1基于内容的模型 务共享一个元组空间，可以通过改变元组空间中的 在本模型中，一个事件被描述为一组（属性，值） 各个元组值（或插入新元组）来实现任务间通信.因 对子，而订阅请求则被描述为一个事件相关的谓词. 此，一般情况下任务间通信是松耦合、匿名化的.如 对于任一事件，检查所有订阅请求的谓词：当谓词为 果想实现同步化通信的目的，则在任务向元组空间发 真时，则将该事件发布给订阅者 送信息之后，必须等待目标任务产生响应元组们 例如，假设某个LBS系统中某个移动对象产生 一般来说，元组空间模型需要支持3个原子 的事件为{(id,"救护车")，(location,(100,200))}, 操作。 表明某一辆救护车的当前坐标是(100,200).订阅者 rite(t):向元组空间插入一个元组t; 的请求是：(location,(x>100)and(x150)and(y<180)),表示订阅者对于空间上 元组：
格被赋予一个标识符．移动对象所在的单元格的标 识符值被Ｂ＋ｔｒｅｅ进行索引．当处理范围查询时，需 要通过移动对象的速度和相对时间对范围进行扩 展．Ｊｅｎｓｅｎ等人［３４］提出了支持更精确的范围查询的 扩展算法．Ｙｉｕ等人［３５］提出了Ｂｄｕａｌｔｒｅｅ，将一个二维 的移动对象映射到四维的对偶空间进行索引．Ｃｈｅｎ 等人［３６］针对移动对象经常在时空范围内发生变化 的特点，提出了一种可自适应调节的ＳＴ２Ｂｔｒｅｅ索 引结构．此外，ＳＴＲＩＰＥＳ［３７］是一个对位置和速度进行索 引的对偶索引，它将在二维空间移动的移动对象映 射到四维的对偶空间，并对四维空间进行ＰＲＱｕａｄ ｔｒｅｅ［１７］索引．这样的结构提高了更新效率，但是却对 查询效率有所影响．针对不同的当前／将来位置索引 技术，Ｃｈｅｎ等人［３８］提出了一个测试基准，并对主要 的当前／将来位置索引方法的特性进行了详细的比较． ４犔犅犛中间件模型 中间件技术广泛地用于移动计算环境之中． ＬＢＳ系统将ＬＢＳ中间件作为服务处理引擎与终端用 户之间的软件载体，隐藏了具体技术细节，便于向客 户端提供服务．主要的ＬＢＳ中间件模型有三种，包括 基于内容的模型（ｃｏｎｔｅｎｔｂａｓｅｄｍｏｄｅｌ）、基于主题 空间的模型（ｓｕｂｊｅｃｔｓｐａｃｅｂａｓｅｄｍｏｄｅｌ）和元组空 间模型（ｔｕｐｌｅｓｐａｃｅｍｏｄｅｌ）．前两个模型又可被归 为发布／订阅模型（ｐｕｂｌｉｓｈ／ｓｕｂｓｃｒｉｂｅｍｏｄｅｌ）．发布／ 订阅模型是移动计算中应用最为广泛的中间件模型 之一．该模型中有两个角色：发布者和订阅者（也称 消费者），二者之间通过事件交换信息．发布者产生 事件，订阅者向发布者发送订阅请求．当特定事件发 生时，即可将该事件通知订阅者．发布者与订阅者之 间的联系并不紧密，是松耦合的；换言之，当订阅者 暂时无法工作时，发布者仍可发布事件［４，３９］． ４１基于内容的模型 在本模型中，一个事件被描述为一组（属性，值） 对子，而订阅请求则被描述为一个事件相关的谓词． 对于任一事件，检查所有订阅请求的谓词；当谓词为 真时，则将该事件发布给订阅者［４］． 例如，假设某个ＬＢＳ系统中某个移动对象产生 的事件为｛（犻犱，＂救护车＂），（犾狅犮犪狋犻狅狀，（１００，２００））｝， 表明某一辆救护车的当前坐标是（１００，２００）．订阅者 的请求是：（犾狅犮犪狋犻狅狀，（狓＞１００）ａｎｄ（狓＜１２０）ａｎｄ （狔＞１５０）ａｎｄ（狔＜１８０）），表示订阅者对于空间上 矩形框（左下角坐标（１００，１５０），右上角坐标（１２０， １８０））内的移动对象感兴趣．因此，这个事件不会发 送到订阅者． 基于内容的模型比较简单，但是无法记录发布 者或者订阅者的状态．例如，假设某用户（订阅者）不 愿一天之内接连看两场电影，则最好不要在一天内 多次向他发送电影放映通知．由于基于内容的模型 并不记录历史事件，无法满足这个需求，因此可以应 用基于主题空间的模型． ４２基于主题空间的模型 基于主题空间的模型的核心概念是主题空间． 一个主题空间实际上是一个多维空间，空间中的每 个维度分别被定义为一个元组犱＝｛狀犪犿犲，狋狔狆犲｝， 其中狀犪犿犲是维度的唯一标识符，狋狔狆犲表示数据类 型．例如，关于位置的主题空间可以被描述为 ｛（狓，犱狅狌犫犾犲），（狔，犱狅狌犫犾犲）｝．此外，兴趣区域（ｉｎｔｅｒｅｓｔ ｒｅｇｉｏｎ）表示订阅者感兴趣的一个子域，在某个主题 空间中；对象区域（ｏｂｊｅｃｔｒｅｇｉｏｎ）表示一个对象的状 态或者属性．订阅者的订阅请求指定一组兴趣区域 和一个过滤函数，以查看对象区域是否符合订阅标 准；发布者的发布准则指定了一组对象区域和一个 过滤函数，以查看兴趣区域是否与本次发布匹配．可 以通过订阅请求和发布准则来判定是否匹配［４０］． 在基于主题空间的模型中，信息在发布之后仍 旧会保留在系统之中，而不是直接被移除，因此该模 型支持有状态的发布／订阅．此外，也有助于实现对 称的发布／订阅系统．换句话说，仅当发布准则与订 阅请求匹配时才会向订阅者发送信息．这个特性能 有效降低信息发布量，避免了冗余信息的传播． ４３元组空间模型 元组空间模型最早被用于并行编程领域，以协 调并发执行的任务．一个元组是一个包含多项值的 矢量，元组空间是一个包含许多元组的集合．多个任 务共享一个元组空间，可以通过改变元组空间中的 各个元组值（或插入新元组）来实现任务间通信．因 此，一般情况下任务间通信是松耦合、匿名化的．如 果想实现同步化通信的目的，则在任务向元组空间发 送信息之后，必须等待目标任务产生响应元组［４１］． 一般来说，元组空间模型需要支持３个原子 操作． 狑狉犻狋犲（狋）：向元组空间插入一个元组狋； 犲狓狋狉犪犮狋（狆）：从元组空间中取出符合谓词狆的 元组； １１６０ 计 算 机 学 报 ２０１１年
7期 周做英等：基于位置的服务：架构与进展 1161 read(p):从元组空间中读取符合谓词p的元 反，Q-index为所有查询建立索引，当移动对象的位 组，但该元组仍旧保留在元组空间中， 置变化时，通过Q-index可以找到受影响的查询， LBS系统可以很方便地使用元组空间模型，信 并更新相应的查询结果 息发布者和订阅者通过元组空间进行通信， 查询感知处理法.该方法根据连续查询的查询 条件计算出“安全区域”2]，只有当移动对象离开 5 服务处理方法 或进入“安全区域”时，才会影响查询结果.因此，系 统可以忽略很多不影响查询结果的位置更新操作， 5.1快照查询和连续查询 进而降低系统负荷.如图5所示，给定5个范围查询， 如前所述，从查询处理的技术角度，基于位置的 对象A的安全区域表示为一个以A为圆心的圆，而 服务通常包含两类查询服务：快照查询和连续查询. 对象B的安全区域则是一个矩形.文献[32,43]基于 快照查询访问移动对象数据库后立即返回查询结 欧式空间距离计算安全区域，而在实际应用中许多 果.典型的快照查询如：“查询当前离我最近的快餐 时候需要基于道路网络进行计算.针对这一特点， 店”.连续查询根据周围环境变化情况持续刷新查询 Yiu等人[针对道路网络上的kNN连续查询提出 结果.例如，“监控未来一小时内某路口车流量变化” 了新的方法.该方法首先通过确定能够影响当前 就是一个典型的连续查询. kNN结果的路段，当移动对象离开该路段时则更新 快照查询的处理较为简单.根据查询对象的时 连续查询结果.该方法同时支持共享查询处理。 效性不同，快照查询大致可分为历史查询、当前查询 查询 和未来查询三类，历史查询用于查询过去时间内发 安全区域 生的事件，例如“查找哪些车辆昨天出现在停车场”； 当前查询用于查询正在发生的事情，例如“查找哪些 Q 车辆现在出现在停车场”；将来查询则查询将要发生 Q A 的事件，例如“查找哪些车辆将在五分钟后出现在停 车场”.为了提高快照查询的执行效率，需要创建各 Q 种索引结构.对于历史查询，需要在时间-空间维度 Q ●B 上对移动对象的历史运动轨迹进行索引.对于当前 查询和未来查询，则需要对移动对象的当前位置进 行索引，并维护移动对象的移动模型.这一类索引结 图5安全区域3町 构需要支持较多的更新操作.这两种索引结构已经 5.2分布式查询处理方法 在第3节中做详细综述。 按照移动终端是否参与查询处理，服务处理方 相比而言，连续查询的处理更为复杂，常用的策 法可以分为集中式和分布式两种处理方式，在集中 略有周期性快照查询法[3)、增量处理法和查询感知 式方式中，仅服务提供商处理连续查询，移动终端并 处理法。 不参与查询处理.分布式方式中，服务提供商与移动 周期性快照查询法，该方法是最朴素的连续查 终端协作完成连续查询处理， 询处理方法，定期执行快照查询（通常是当前快照查 Gedik等人[4)提出了一种分布式连续查询处理 询)，并刷新查询结果.缺点是难以有效地定义周期 架构MobiEyes,其核心思想是由移动终端来计算和 值：过小的周期值将增加系统负荷，而过大的周期值 判断是否是一个连续查询的结果，而中心服务器负 会降低查询结果精度， 责注册和维护连续查询的相关参数，并将参数传到 增量处理法.根据初始结果，动态增加新数据 相关移动终端.移动终端维护一个注册表以记录临 或者删除过期数据.SINA[a]定义了两类更新：正更 近的一组连续查询，并周期性地检查自己是否属于 新和负更新（从当前结果集内增加或删除一个移动 这些查询的结果之中.若是，则向服务器报告.为减 对象)，从而增量地更新查询结果.SINA通过散列、 少服务器和移动终端之间的通信代价和移动终端的 验证和连接3个步骤完成对连续查询的正负更新， 计算开销，该文还提出了3种优化策略.Cai等人) 从而有效地执行连续查询.Q-index3)是另一种处 则考虑到每个移动终端的计算和存储能力有差别， 理连续查询的索引结构，和通常的索引构建策略相 针对每个移动终端最多能处理的查询个数确定一个
狉犲犪犱（狆）：从元组空间中读取符合谓词狆的元 组，但该元组仍旧保留在元组空间中． ＬＢＳ系统可以很方便地使用元组空间模型，信 息发布者和订阅者通过元组空间进行通信． ５服务处理方法 ５１快照查询和连续查询 如前所述，从查询处理的技术角度，基于位置的 服务通常包含两类查询服务：快照查询和连续查询． 快照查询访问移动对象数据库后立即返回查询结 果．典型的快照查询如：“查询当前离我最近的快餐 店”．连续查询根据周围环境变化情况持续刷新查询 结果．例如，“监控未来一小时内某路口车流量变化” 就是一个典型的连续查询． 快照查询的处理较为简单．根据查询对象的时 效性不同，快照查询大致可分为历史查询、当前查询 和未来查询三类．历史查询用于查询过去时间内发 生的事件，例如“查找哪些车辆昨天出现在停车场”； 当前查询用于查询正在发生的事情，例如“查找哪些 车辆现在出现在停车场”；将来查询则查询将要发生 的事件，例如“查找哪些车辆将在五分钟后出现在停 车场”．为了提高快照查询的执行效率，需要创建各 种索引结构．对于历史查询，需要在时间空间维度 上对移动对象的历史运动轨迹进行索引．对于当前 查询和未来查询，则需要对移动对象的当前位置进 行索引，并维护移动对象的移动模型．这一类索引结 构需要支持较多的更新操作．这两种索引结构已经 在第３节中做详细综述． 相比而言，连续查询的处理更为复杂，常用的策 略有周期性快照查询法［３２］、增量处理法和查询感知 处理法．周期性快照查询法．该方法是最朴素的连续查 询处理方法，定期执行快照查询（通常是当前快照查 询），并刷新查询结果．缺点是难以有效地定义周期 值：过小的周期值将增加系统负荷，而过大的周期值 会降低查询结果精度． 增量处理法．根据初始结果，动态增加新数据 或者删除过期数据．ＳＩＮＡ［４２］定义了两类更新：正更 新和负更新（从当前结果集内增加或删除一个移动 对象），从而增量地更新查询结果．ＳＩＮＡ通过散列、 验证和连接３个步骤完成对连续查询的正负更新， 从而有效地执行连续查询．Ｑｉｎｄｅｘ［３２］是另一种处 理连续查询的索引结构．和通常的索引构建策略相 反，Ｑｉｎｄｅｘ为所有查询建立索引，当移动对象的位 置变化时，通过Ｑｉｎｄｅｘ可以找到受影响的查询， 并更新相应的查询结果． 查询感知处理法．该方法根据连续查询的查询 条件计算出“安全区域”［３２，４３］，只有当移动对象离开 或进入“安全区域”时，才会影响查询结果．因此，系 统可以忽略很多不影响查询结果的位置更新操作， 进而降低系统负荷．如图５所示，给定５个范围查询， 对象犃的安全区域表示为一个以犃为圆心的圆，而 对象犅的安全区域则是一个矩形．文献［３２，４３］基于 欧式空间距离计算安全区域，而在实际应用中许多 时候需要基于道路网络进行计算．针对这一特点， Ｙｉｕ等人［４４］针对道路网络上的犽ＮＮ连续查询提出 了新的方法．该方法首先通过确定能够影响当前 犽ＮＮ结果的路段，当移动对象离开该路段时则更新 连续查询结果．该方法同时支持共享查询处理． 图５安全区域［３２］ ５２分布式查询处理方法 按照移动终端是否参与查询处理，服务处理方 法可以分为集中式和分布式两种处理方式．在集中 式方式中，仅服务提供商处理连续查询，移动终端并 不参与查询处理．分布式方式中，服务提供商与移动 终端协作完成连续查询处理． Ｇｅｄｉｋ等人［４５］提出了一种分布式连续查询处理 架构ＭｏｂｉＥｙｅｓ，其核心思想是由移动终端来计算和 判断是否是一个连续查询的结果，而中心服务器负 责注册和维护连续查询的相关参数，并将参数传到 相关移动终端．移动终端维护一个注册表以记录临 近的一组连续查询，并周期性地检查自己是否属于 这些查询的结果之中．若是，则向服务器报告．为减 少服务器和移动终端之间的通信代价和移动终端的 计算开销，该文还提出了３种优化策略．Ｃａｉ等人［４６］ 则考虑到每个移动终端的计算和存储能力有差别， 针对每个移动终端最多能处理的查询个数确定一个 ７期 周傲英等：基于位置的服务：架构与进展 １１６１
1162 计算 学 报 2011年 存在区域，仅当移动对象离开存在区域时，才向中心 位置，请求 位置，请求 服务器发送位置更新，并获取新的存在区域.移动终 LBS TTP 提供商 端在存在区域移动时，需要自己计算并检查是否是 结果 结果 与该存在区域相关的连续查询的结果， 基于TTP的隐私保护方法 与集中式方式相比，分布式方式通常需要在服 用户1 位置'，请求 务器与移动终端之间传递更多的消息，这带来两个 结果 LBS 问题：一是大量移动终端可能造成网络拥塞；二是网 提供商 络通信会消耗移动终端的能量，缩短充电周期.另 用户 外，该方法无法适用于无计算能力的移动终端，如仅 基于合作策略的非TTP隐私保护方法 携带RFID标签的移动对象. 图6隐私保护方法 6 隐私保护 区分开来.Gedik等人提出了整合时间和空间区 域的k-匿名方法CliqueCloak,在一个时空立方体内 隐私保护是LBS的重要内容.用户并不期望由 部至少仍然存在其它k一1个对象.林欣等人[]发 于接受了服务而向外界泄露了位置信息，这既包括 现k-匿名方法对连续攻击保护效果较弱，提出了一 当前的具体位置，也包括对象的移动习惯等.最常用 种能够有效保护连续查询时用户隐私的基于嫡理论 的位置隐私解决方案是空间伪装(spatial cloa- 的度量方式AD(anonymity degree).Mokbel等 king)),即用户将位置伪装成为一个区域之后再 人[s]提出了Casper方法，利用金字塔数据结构将 发送给服务提供商，服务提供商则根据用户所提供 整个空间划分成大小不等的单元，若移动对象较为 的区域信息为用户提供服务.在这种方式下，服务提 密集，则单元面积较小；反之，则单元面积较大 供商无法准确得知用户的位置.事实上，用户隐私和 Kalnis等人s]提出了Hilbert Cloak方法，利用 服务质量是一对矛盾关系，需根据具体情况进行权 Hilbert曲线将二维空间映射成一维空间，再利用 衡.Tan等人[4]提出了量化分析隐私保护和服务质 B+-tree对移动对象建立索引.通过选取具有连续 量比例的方法.本节回顾两大类隐私保护技术[4町， Hilbert值的k个对象进行隐私保护.Privacy- 即依赖于可信赖的第三方机构的技术（简称TTP- Gids]使用网格进行k-匿名，并在此基础上增加了 based)和不依赖于可信赖的第三方机构的技术（简 -多样性，进而又提高了隐私的保护程度. 称非TTP-based). 依赖于可信赖第三方的隐私保护技术的有效性 6.1依赖可信赖第三方机构的隐私保护方法 在很大程度上取决于第三方机构是否可信.近年来， 在TTP-based技术中，用户将位置信息发送给 陆续出现了一些有关第三方机构的丑闻事件，使得 TTP(Trusted Third Party),由TTP对位置信息做 第三方机构的独立性与权威性大打折扣.该技术的 变换，之后再连同服务请求一起发送给服务提供商； 另一个缺点是集中式处理方式，即所有用户请求均 服务提供商基于不精确的位置信息进行处理，并将 发送到TTP,使得TTP成为系统性能瓶颈.因此， 服务结果返回给TTP.TTP经过过滤、取精后返回 当前的发展趋势越来越倾向于不依赖可信第三方的 给用户，如图6所示.在此过程中，TTP的主要任务 隐私保护方法， 是将原始的、准确的位置信息转化为不准确的位置 6.2不依赖可信赖第三方机构的隐私保护方法 信息，以保护用户的隐私 目前，有一些隐私保护技术并不依赖于TTP, 一种简单的方法是TTP直接用虚假标识符表 其基本思想是用户和其它用户之间交互位置信息， 示真实的用户标识符，再发送给服务提供商[4们.但 进而构造伪装的位置，如图6所示.主要步骤如 是，服务提供商仍可借助其它辅助信息进行破解，比 下[56]：(1)请求服务的用户A首先将自身位置模糊 如通过电话号码或家庭住址来推测真实用户信息， 化，并向周围的邻居广播：(2)邻居对象将模糊化之 k-匿名方法是另外一种使用较广泛的方法[50，其核 后的位置信息发送给用户A,直到A至少搜集到 心思想是以一个覆盖移动对象的矩形来描述该对象 一1个移动用户的位置信息：(3)用户A随机选取 的真实位置，该矩形同时还包含另外k一1个对象， 及一1个对象，与自身构成一个含k个对象的集合，并 使得服务提供商无法将该对象与其余k一1个对象 将包含这些对象的MBR或任意一个非用户A对象
存在区域，仅当移动对象离开存在区域时，才向中心 服务器发送位置更新，并获取新的存在区域．移动终 端在存在区域移动时，需要自己计算并检查是否是 与该存在区域相关的连续查询的结果． 与集中式方式相比，分布式方式通常需要在服 务器与移动终端之间传递更多的消息，这带来两个 问题：一是大量移动终端可能造成网络拥塞；二是网 络通信会消耗移动终端的能量，缩短充电周期．另 外，该方法无法适用于无计算能力的移动终端，如仅 携带ＲＦＩＤ标签的移动对象． ６隐私保护 隐私保护是ＬＢＳ的重要内容．用户并不期望由 于接受了服务而向外界泄露了位置信息，这既包括 当前的具体位置，也包括对象的移动习惯等．最常用 的位置隐私解决方案是空间伪装（ｓｐａｔｉａｌｃｌｏａ ｋｉｎｇ）［４７］，即用户将位置伪装成为一个区域之后再 发送给服务提供商，服务提供商则根据用户所提供 的区域信息为用户提供服务．在这种方式下，服务提 供商无法准确得知用户的位置．事实上，用户隐私和 服务质量是一对矛盾关系，需根据具体情况进行权 衡．Ｔａｎ等人［４８］提出了量化分析隐私保护和服务质 量比例的方法．本节回顾两大类隐私保护技术［４９］， 即依赖于可信赖的第三方机构的技术（简称ＴＴＰ ｂａｓｅｄ）和不依赖于可信赖的第三方机构的技术（简 称非ＴＴＰｂａｓｅｄ）． ６１依赖可信赖第三方机构的隐私保护方法 在ＴＴＰｂａｓｅｄ技术中，用户将位置信息发送给 ＴＴＰ（ＴｒｕｓｔｅｄＴｈｉｒｄＰａｒｔｙ），由ＴＴＰ对位置信息做 变换，之后再连同服务请求一起发送给服务提供商； 服务提供商基于不精确的位置信息进行处理，并将 服务结果返回给ＴＴＰ．ＴＴＰ经过过滤、取精后返回 给用户，如图６所示．在此过程中，ＴＴＰ的主要任务 是将原始的、准确的位置信息转化为不准确的位置 信息，以保护用户的隐私． 一种简单的方法是ＴＴＰ直接用虚假标识符表 示真实的用户标识符，再发送给服务提供商［４４］．但 是，服务提供商仍可借助其它辅助信息进行破解，比 如通过电话号码或家庭住址来推测真实用户信息． 犽匿名方法是另外一种使用较广泛的方法［５０］，其核 心思想是以一个覆盖移动对象的矩形来描述该对象 的真实位置，该矩形同时还包含另外犽－１个对象， 使得服务提供商无法将该对象与其余犽－１个对象 图６隐私保护方法 区分开来．Ｇｅｄｉｋ等人［５１］提出了整合时间和空间区 域的犽匿名方法ＣｌｉｑｕｅＣｌｏａｋ，在一个时空立方体内 部至少仍然存在其它犽－１个对象．林欣等人［５２］发 现犽匿名方法对连续攻击保护效果较弱，提出了一 种能够有效保护连续查询时用户隐私的基于熵理论 的度量方式ＡＤ（ａｎｏｎｙｍｉｔｙｄｅｇｒｅｅ）．Ｍｏｋｂｅｌ等 人［５３］提出了Ｃａｓｐｅｒ方法，利用金字塔数据结构将 整个空间划分成大小不等的单元，若移动对象较为 密集，则单元面积较小；反之，则单元面积较大． Ｋａｌｎｉｓ等人［５４］提出了ＨｉｌｂｅｒｔＣｌｏａｋ方法，利用 Ｈｉｌｂｅｒｔ曲线将二维空间映射成一维空间，再利用 Ｂ＋ｔｒｅｅ对移动对象建立索引．通过选取具有连续 Ｈｉｌｂｅｒｔ值的犽个对象进行隐私保护．Ｐｒｉｖａｃｙ Ｇｒｉｄ［５５］使用网格进行犽匿名，并在此基础上增加了 犾多样性，进而又提高了隐私的保护程度． 依赖于可信赖第三方的隐私保护技术的有效性 在很大程度上取决于第三方机构是否可信．近年来， 陆续出现了一些有关第三方机构的丑闻事件，使得 第三方机构的独立性与权威性大打折扣．该技术的 另一个缺点是集中式处理方式，即所有用户请求均 发送到ＴＴＰ，使得ＴＴＰ成为系统性能瓶颈．因此， 当前的发展趋势越来越倾向于不依赖可信第三方的 隐私保护方法． ６２不依赖可信赖第三方机构的隐私保护方法 目前，有一些隐私保护技术并不依赖于ＴＴＰ， 其基本思想是用户和其它用户之间交互位置信息， 进而构造伪装的位置，如图６所示．主要步骤如 下［５６］：（１）请求服务的用户犃首先将自身位置模糊 化，并向周围的邻居广播；（２）邻居对象将模糊化之 后的位置信息发送给用户犃，直到犃至少搜集到 犽－１个移动用户的位置信息；（３）用户犃随机选取 犽－１个对象，与自身构成一个含犽个对象的集合，并 将包含这些对象的ＭＢＲ或任意一个非用户犃对象 １１６２ 计 算 机 学 报 ２０１１年
7期 周做英等：基于位置的服务：架构与进展 1163 的位置发送给服务提供商：(4)服务提供商根据接 Yang[s)提出了一种基于图的室内移动对象的跟踪算 收到的位置提供服务.Chow等人[]在此基础上提 法，用于确定室内移动对象的轨迹，并且提出了两种 出了一种基于点对点(P2P)架构的基于合作的隐私 基于R-tree的索引结构RTR-tree和Tp2R-treel]. 保护技术.MobiHide[s]方法也利用点对点构架，把 RTR-tree将室内移动对象的轨迹表示为若干水平 用户的二维空间信息通过Hilbert曲线映射到一维 的线段，TPR-tree则把轨迹表示为一个带时间参 空间，通过在映射后的一维空间内选取连续的k个 数的点.这两种索引结构均可有效支持室内空间的 对象以保护用户的隐私.Solanas等人[s]也提出了 范围查询和室内轨迹查找. 一个无需借助TTP的网络传输协议. 阅读器编号◆ 尽管上述方法不再依赖TTP,但是仍然需要和 至少k一1个可信用户交互[]，增加了整个方法的 通信复杂度，并且在实际应用中无法有效保证参与 R 隐私保护的其它k一1个用户是可信的.最近，一些 R 学者提出了新的解决方案，并不借助与临近节点的 R 交互.我们将在下一节中详细叙述。 :时间 (a)RTR-tree 7近期研究进展 阅读署编号本 7.1室内LBS技术 R.2T. 随着大型建筑物的内部空间趋于大型化和复杂 r 化，室内LBS(例如室内导航等)得到了越来越多的 R.2T.L 关注s61),例如，博物馆的自动导游指引服务、基于 乘客移动模式分析的机场商铺规划等.为了支持此 类服务，亟需发展室内空间建模技术、索引技术和连 时间 续查询处理技术. (b)TPR-tree 室内空间模型.一般来说，室内空间的拓扑关 图7室内移动对象在符号空间下的轨迹以及 系比室外空间复杂得多，因而更适合用符号化的坐 对应的RTR-tree和TPR-treels) 标系统[6]对室内空间结构建模.三维几何网络模 连续查询处理.针对室内移动对象的连续查询 型[6]区分对待室内实体（房间）之间水平和垂直的 处理，Yang等人[s]提出了一种查询感知的、增量的 连通关系.3 D Poincare Dualitytst通过对偶转换，把 方法.该方法适用于基于符号化存在感应器的室内 三维空间内的实体的连通关系转换为对偶空间，可 定位技术（如RFID).针对每个连续范围查询，作者 以应用于室内空间紧急疏散线路的计算，为了支持 提出了关键设备的概念，即在符号空间中的安全区 室内导航，一种三维可测量拓扑模型[6]被提出，该 域[3]，仅当关键设备有新的读数产生时，会对查询 模型同时考虑空间实体的形状和连通关系.Li等人 结果进行增加或删除操作，这样，非关键设备的新读 提出基于栅格的语义模型[6]，可以维持不同室内位 数将不会被用于增量更新查询结果。 置间的最短路径.Jensen等人[s町提出了一种基于图 7.2不确定的位置服务 模型的方法，不仅维持室内实体间的拓扑结构，还能 位置信息的不确定性源于多种因素.首先，非连 有效管理基于感知定位的室内定位数据。 续的定位采样会带来不确定性.一般来说，定位技术 室内轨迹索引技术，由于室内空间表示为符号 会定期汇报位置信息，因而移动对象的位置在相邻 化系统，因此室内轨迹表达方式也和室外轨迹不同. 两次采样之间存在不确定性[6s0].其次，定位技术自 室内移动对象的轨迹可以表示在一个包含空间维和 身具有精度限制.再次，当以物体的历史运动轨 时间维的多维空间.空间维用符号化的地理位置编 迹和附加信息来预测其未来行为时也存在不确定 号表示，例如房间号、RFD阅读器编号等.这样，移 性].最后，出于隐私保护目的，需将数据模糊 动对象的轨迹可以表示为若干水平线段，进而利用 化]，人为地引入不确定性. R-tree索引这些线段，如图7所示.Jensen、Lu和 不确定位置信息管理技术大致可分为如下几种
的位置发送给服务提供商；（４）服务提供商根据接 收到的位置提供服务．Ｃｈｏｗ等人［５７］在此基础上提 出了一种基于点对点（Ｐ２Ｐ）架构的基于合作的隐私 保护技术．ＭｏｂｉＨｉｄｅ［５８］方法也利用点对点构架，把 用户的二维空间信息通过Ｈｉｌｂｅｒｔ曲线映射到一维 空间，通过在映射后的一维空间内选取连续的犽个 对象以保护用户的隐私．Ｓｏｌａｎａｓ等人［５９］也提出了 一个无需借助ＴＴＰ的网络传输协议． 尽管上述方法不再依赖ＴＴＰ，但是仍然需要和 至少犽－１个可信用户交互［６０］，增加了整个方法的 通信复杂度，并且在实际应用中无法有效保证参与 隐私保护的其它犽－１个用户是可信的．最近，一些 学者提出了新的解决方案，并不借助与临近节点的 交互．我们将在下一节中详细叙述． ７近期研究进展 ７１室内犔犅犛技术 随着大型建筑物的内部空间趋于大型化和复杂 化，室内ＬＢＳ（例如室内导航等）得到了越来越多的 关注［８，６１］．例如，博物馆的自动导游指引服务、基于 乘客移动模式分析的机场商铺规划等．为了支持此 类服务，亟需发展室内空间建模技术、索引技术和连 续查询处理技术． 室内空间模型．一般来说，室内空间的拓扑关 系比室外空间复杂得多，因而更适合用符号化的坐 标系统［６２］对室内空间结构建模．三维几何网络模 型［６３］区分对待室内实体（房间）之间水平和垂直的 连通关系．３ＤＰｏｉｎｃａｒｅＤｕａｌｉｔｙ［６４］通过对偶转换，把 三维空间内的实体的连通关系转换为对偶空间，可 以应用于室内空间紧急疏散线路的计算．为了支持 室内导航，一种三维可测量拓扑模型［６５］被提出，该 模型同时考虑空间实体的形状和连通关系．Ｌｉ等人 提出基于栅格的语义模型［６６］，可以维持不同室内位 置间的最短路径．Ｊｅｎｓｅｎ等人［６１］提出了一种基于图 模型的方法，不仅维持室内实体间的拓扑结构，还能 有效管理基于感知定位的室内定位数据． 室内轨迹索引技术．由于室内空间表示为符号 化系统，因此室内轨迹表达方式也和室外轨迹不同． 室内移动对象的轨迹可以表示在一个包含空间维和 时间维的多维空间．空间维用符号化的地理位置编 号表示，例如房间号、ＲＦＩＤ阅读器编号等．这样，移 动对象的轨迹可以表示为若干水平线段，进而利用 Ｒｔｒｅｅ索引这些线段，如图７所示．Ｊｅｎｓｅｎ、Ｌｕ和 Ｙａｎｇ［６１］提出了一种基于图的室内移动对象的跟踪算 法，用于确定室内移动对象的轨迹，并且提出了两种 基于Ｒｔｒｅｅ的索引结构ＲＴＲｔｒｅｅ和ＴＰ２Ｒｔｒｅｅ［６７］． ＲＴＲｔｒｅｅ将室内移动对象的轨迹表示为若干水平 的线段，ＴＰ２Ｒｔｒｅｅ则把轨迹表示为一个带时间参 数的点．这两种索引结构均可有效支持室内空间的 范围查询和室内轨迹查找． 图７室内移动对象在符号空间下的轨迹以及 对应的ＲＴＲｔｒｅｅ和ＴＰ２Ｒｔｒｅｅ［６７］ 连续查询处理．针对室内移动对象的连续查询 处理，Ｙａｎｇ等人［６８］提出了一种查询感知的、增量的 方法．该方法适用于基于符号化存在感应器的室内 定位技术（如ＲＦＩＤ）．针对每个连续范围查询，作者 提出了关键设备的概念，即在符号空间中的安全区 域［３２］．仅当关键设备有新的读数产生时，会对查询 结果进行增加或删除操作．这样，非关键设备的新读 数将不会被用于增量更新查询结果． ７２不确定的位置服务 位置信息的不确定性源于多种因素．首先，非连 续的定位采样会带来不确定性．一般来说，定位技术 会定期汇报位置信息，因而移动对象的位置在相邻 两次采样之间存在不确定性［６９７０］．其次，定位技术自 身具有精度限制［７１］．再次，当以物体的历史运动轨 迹和附加信息来预测其未来行为时也存在不确定 性［７２］．最后，出于隐私保护目的，需将数据模糊 化［４７］，人为地引入不确定性． 不确定位置信息管理技术大致可分为如下几种 ７期 周傲英等：基于位置的服务：架构与进展 １１６３
1164 计算 机学 报 2011年 情况. 设该机器人的位置服从正态分布，针对这一特殊的 (1)查询发出点精确，被查询的数据点是不确 分布，提出了3种优化的策略.此问题的定义虽然是 定的移动对象。 在室内的机器人应用，但是其使用的模型仍然是室 这类不确定查询在LBS中最常见.Cheng等 外空间常用的几何模型，并未考虑室内符号空间 人[]提出了一套针对室外移动对象的查询处理框 Hu等人[8]则针对最近邻查询进行了研究，并提出 架.首先，根据定位的精度，将移动对象可能出现的 了EXO-tree提高查询效率， 区域限制在一个不确定区域内.在此基础上定义了 (3)查询发出点和被查询数据点都是不确定的. 概率范围查询和概率NN查询.并对直线运动模型 Kriegel等人[9-so]研究了查询出发点和被查询 和自由移动模型的移动对象的不确定性进行了总结 数据点都存在不确定性的查询处理技术，定义了概 与分析，进而有效地处理概率范围查找和概率NN 率kNN查询和概率连接查询，并对Monte Carlo抽 查询.在此基础上，Cheng等人[s]又提出了概率阈 样点建R-tree索引以提高查找效率.Chen等人z) 值kNN查询，根据提出的k-bound概念进行过滤 提出的p-bound则可以用于提高范围查询效率. (k-bound为查询发出点到不确定对象的第k个最 (4)不确定的移动速度. 大距离，如图8所示)，并且提出了3种优化处理 Huang等人[s]考虑移动对象速度变化的不确 该查询的方法.基于树的U-Tree和基于网格的 定性，提出了一种支持连续kNN查询的方法.Lian U-Gid)等索引方法可以索引多维不确定数据. 等人[s)定义了概率RNN查询，并提出了基于双曲 Yang等人[s]提出了针对室内移动对象的查询处理 线的启发式查询处理算法.给定移动对象当前位置和 技术，将范围查询的结果划分为两类：确定结果和不 速度的分布，移动对象不确定性的模型[)可以被确 确定结果.给定移动对象的最大移动速度和室内空 定.根据该模型，可以用于预测未来移动对象的位置。 间的拓扑结构，对不确定结果集上的概率分析也做 7.3非合作策略的不基于TTP的隐私保护方法 了基本讨论.Yang等人在其最新的研究中，针对定 非合作策略的不基于TTP的隐私保护方法是 位系统的精度不确定性，提出了室内移动对象的不 近几年出现的一种新型隐私保护方法，该方法无需 确定区域的定义，并在此基础上提出了基于精确查 用户与其它用户之间的交互，而仅由用户自己完成 询发出点的概率阈值kNN查询处理方法. 整个操作.SpaceTwist[s]使用一个锚点来代替移动 对象的真实位置，通过对服务商不断查找锚点的 0 最近邻的感兴趣点(POI),进而最终确定离真实位 置最近的POL.在这一过程中，服务提供商只获得锚 0.2 点的位置，而不能获得移动对象的真实位置.Ghinita 等人[s提出的基于私人信息恢复(PIR-based)的技 0 术也是非合作策略的方法.如图9所示，它通过把隐 私信息使用加密技术处理再发出查询请求，得到查 询结果后再在客户端解密，保证了用户信息的私密 k-bound (=3) 性，这一方法不仅保护了单次查询的隐私，同时还可 图8查询发出点精确的不确定移动对象NN查询，k=3) 以很好地保护多次关联查询的隐私，以防止对手分 析多次查询之间的关联性来窃取用户隐私. (2)查询发出点是不确定的移动对象，被查询 的数据点是精确的 加密位置请求 LBS Chen等人[)针对范围查询提出了3种优化方 用户 提供商 法：首先通过查询扩展，过滤掉一些不可能成为查询 加密结果 结果的数据点；接着通过互换查询发出点和数据点 对加密结果 的角色，提高查询效率：最后针对阈值概率查询，提 进行解密 出了p-bound以限制查找空间，进而提高查询效 图9基于PIR的隐私保护策略[] 率.Ishikawa等人[)则考虑了室内机器人这一应用 在找朋友应用中需要检测朋友之间的空间临近 场景，范围查询从不确定的机器人位置发出，并且假 性，这就要求用户隐私数据被保护的同时，还需要保
情况．（１）查询发出点精确，被查询的数据点是不确 定的移动对象． 这类不确定查询在ＬＢＳ中最常见．Ｃｈｅｎｇ等 人［７１］提出了一套针对室外移动对象的查询处理框 架．首先，根据定位的精度，将移动对象可能出现的 区域限制在一个不确定区域内．在此基础上定义了 概率范围查询和概率ＮＮ查询．并对直线运动模型 和自由移动模型的移动对象的不确定性进行了总结 与分析，进而有效地处理概率范围查找和概率ＮＮ 查询．在此基础上，Ｃｈｅｎｇ等人［７３］又提出了概率阈 值犽ＮＮ查询，根据提出的犽ｂｏｕｎｄ概念进行过滤 （犽ｂｏｕｎｄ为查询发出点到不确定对象的第犽个最 大距离，如图８所示），并且提出了３种优化处理 该查询的方法．基于树的ＵＴｒｅｅ［７４］和基于网格的 ＵＧｒｉｄ［７５］等索引方法可以索引多维不确定数据． Ｙａｎｇ等人［６８］提出了针对室内移动对象的查询处理 技术，将范围查询的结果划分为两类：确定结果和不 确定结果．给定移动对象的最大移动速度和室内空 间的拓扑结构，对不确定结果集上的概率分析也做 了基本讨论．Ｙａｎｇ等人在其最新的研究中，针对定 位系统的精度不确定性，提出了室内移动对象的不 确定区域的定义，并在此基础上提出了基于精确查 询发出点的概率阈值犽ＮＮ查询处理方法． 图８查询发出点精确的不确定移动对象犽ＮＮ查询，犽＝３［７３］ （２）查询发出点是不确定的移动对象，被查询 的数据点是精确的． Ｃｈｅｎ等人［７６］针对范围查询提出了３种优化方 法：首先通过查询扩展，过滤掉一些不可能成为查询 结果的数据点；接着通过互换查询发出点和数据点 的角色，提高查询效率；最后针对阈值概率查询，提 出了狆ｂｏｕｎｄ以限制查找空间，进而提高查询效 率．Ｉｓｈｉｋａｗａ等人［７７］则考虑了室内机器人这一应用 场景，范围查询从不确定的机器人位置发出，并且假 设该机器人的位置服从正态分布．针对这一特殊的 分布，提出了３种优化的策略．此问题的定义虽然是 在室内的机器人应用，但是其使用的模型仍然是室 外空间常用的几何模型，并未考虑室内符号空间． Ｈｕ等人［７８］则针对最近邻查询进行了研究，并提出 了ＥＸＯｔｒｅｅ提高查询效率． （３）查询发出点和被查询数据点都是不确定的． Ｋｒｉｅｇｅｌ等人［７９８０］研究了查询出发点和被查询 数据点都存在不确定性的查询处理技术，定义了概 率犽ＮＮ查询和概率连接查询，并对ＭｏｎｔｅＣａｒｌｏ抽 样点建Ｒｔｒｅｅ索引以提高查找效率．Ｃｈｅｎ等人［７６］ 提出的狆ｂｏｕｎｄ则可以用于提高范围查询效率． （４）不确定的移动速度． Ｈｕａｎｇ等人［８１］考虑移动对象速度变化的不确 定性，提出了一种支持连续犽ＮＮ查询的方法．Ｌｉａｎ 等人［８２］定义了概率犚ＮＮ查询，并提出了基于双曲 线的启发式查询处理算法．给定移动对象当前位置和 速度的分布，移动对象不确定性的模型［７２］可以被确 定．根据该模型，可以用于预测未来移动对象的位置． ７３非合作策略的不基于犜犜犘的隐私保护方法 非合作策略的不基于ＴＴＰ的隐私保护方法是 近几年出现的一种新型隐私保护方法，该方法无需 用户与其它用户之间的交互，而仅由用户自己完成 整个操作．ＳｐａｃｅＴｗｉｓｔ［８３］使用一个锚点来代替移动 对象的真实位置，通过对服务商不断查找锚点的犽 最近邻的感兴趣点（ＰＯＩ），进而最终确定离真实位 置最近的ＰＯＩ．在这一过程中，服务提供商只获得锚 点的位置，而不能获得移动对象的真实位置．Ｇｈｉｎｉｔａ 等人［８４］提出的基于私人信息恢复（ＰＩＲｂａｓｅｄ）的技 术也是非合作策略的方法．如图９所示，它通过把隐 私信息使用加密技术处理再发出查询请求，得到查 询结果后再在客户端解密，保证了用户信息的私密 性．这一方法不仅保护了单次查询的隐私，同时还可 以很好地保护多次关联查询的隐私，以防止对手分 析多次查询之间的关联性来窃取用户隐私． 图９基于ＰＩＲ的隐私保护策略［８１］ 在找朋友应用中需要检测朋友之间的空间临近 性，这就要求用户隐私数据被保护的同时，还需要保 １１６４ 计 算 机 学 报 ２０１１年