第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),每个单元
３ＤＲｔｒｅｅ［１８］把时间维当作一个额外的空间维， 不区分空间维和时间维，用一个３ＤＲｔｒｅｅ统一对 在这个三维空间内的轨迹进行索引，使得空间查询、 时间查询、时空查询在３ＤＲｔｒｅｅ上统一实现．ＭＲ ｔｒｅｅ［１９］和ＨＲｔｒｅｅ［２０］对每一个时刻的移动对象的位 置建立一个Ｒｔｒｅｅ．为了节省索引的空间，对连续时 刻内位置未发生改变的移动对象不再进行保存，而 是通过指针指向前一个节点．ＭＶ３Ｒｔｒｅｅ［２１］同时维 护两棵树：ＭＶＲｔｒｅｅ和３ＤＲｔｒｅｅ，其中ＭＶＲｔｒｅｅ 用于处理时间参数为时刻的时空查询，３ＤＲｔｒｅｅ用 于处理时间参数为时间间隔的时空查询．为了处理 针对轨迹的查询，ＴＢｔｒｅｅ［２２］利用类似Ｒｔｒｅｅ的结 构，但是它要求每个节点只保存来自于同一移动对 象轨迹的时空数据．这样，在时空上临近但不属于一 个移动对象轨迹的数据将被分别保存在不同的节 点内．基于Ｈａｓｈ的索引结构通常将空间维和时间维 分开处理．ＳＥＴＩ［２３］把空间维和时间维区分开：使用 静态、无重叠的网格划分空间维度（如图３所示）；使 用一维Ｒｔｒｅｅ索引各空间网格内的时间维度．Ｓｏｎｇ 在其相关研究中也是先按照空间维度使用静态的网 格划分［２４］，而对每个空间网格内的对象的时间属性 进行转化，用ＳＥＢｔｒｅｅ［２５］进行索引． 图３ＳＥＴＩ中基于空间的网格划分［２３］ ３２当前位置索引技术 移动对象的位置随时间不停变化，这就要求索 引结构能够应对大量更新操作．２＋３Ｒｔｒｅｅ［２６］是一 种既能索引历史轨迹，又能索引当前位置的方法，它 维护了两个Ｒｔｒｅｅ，一个２ＤＲｔｒｅｅ用于索引移动对 象当前位置，另一个３ＤＲｔｒｅｅ用于索引移动对象 的历史轨迹．当移动对象的位置改变时，一条新的轨 迹线段被构造出来并插入至３ＤＲｔｒｅｅ中，与此同 时，新位置插入到２ＤＲｔｒｅｅ中，且旧位置从２Ｄ Ｒｔｒｅｅ中移除．ＬＵＲｔｒｅｅ［２７］通过Ｒｔｒｅｅ索引移动对 象的当前位置，以满足移动对象频繁的位置更新操 作．一旦移动对象的位置改变，新的位置将及时更新 到Ｒｔｒｅｅ中．如果新位置仍然在其原先节点的 ＭＢＲ内，只需更改该目录的位置；如果新的位置超 出其节点的ＭＢＲ，则根据不同策略选择是将该对象 的目录删除后再插入，或者是将该节点的ＭＢＲ进 行扩展以包含该对象的新位置．为了应对移动对象 频繁的更新操作，ＲＵＭｔｒｅｅ［２８］利用保存在内存的 特定信息，在更新时能避免访问磁盘来实现删除旧 条目．而过期的旧条目将以批处理方式移除，从而提 高了更新操作的效率． ３３将来位置索引技术 为了索引未来时刻的移动对象位置，通常情况 下需要根据移动对象的速度犞对移动对象的未来 位置建模，即犾狅犮犪狋犻狅狀ｎｅｗ＝犾狅犮犪狋犻狅狀ｏｌｄ＋犞×（狋ｎｅｗ－ 狋ｏｌｄ）．对移动对象将来位置的索引技术分为两类：基 于Ｒｔｒｅｅ的索引结构和基于Ｂ＋ｔｒｅｅ的索引结构． ＴＰＲｔｒｅｅ［２９］和ＴＰＲｔｒｅｅ［３０］使用时间参数的ＭＢＲ 来组织移动对象，在组织节点时不仅考虑移动对象 当前的位置，也考虑移动对象的速度，因而ＭＢＲ能 随时间的变化而扩展．当移动对象的位置更新时，则 重新计算包含该对象的ＭＢＲ．由于这类索引结构保 存了速度信息，因而能预测移动对象的将来位置． ＲＥＸＰｔｒｅｅ［３１］是ＴＰＲｔｒｅｅ的一种扩展，它针对部分 移动对象长时间不更新位置信息导致ＭＢＲ不断扩 大的缺点，设定一个失效时间以删除失效的移动对 象或重新计算．ＶＣＩＲｔｒｅｅ［３２］额外保持每个Ｒｔｒｅｅ 节点的所有对象的最大速度，在查询处理时，根据查 询时间和最大速度对ＭＢＲ或查询本身进行扩展， 如图４所示． 图４ＶＣＩＲｔｒｅｅ处理范围查询时的ＭＢＲ扩展和查询扩展［３２］ 利用Ｂ＋ｔｒｅｅ对移动对象建立索引也是一种重 要的方法．Ｂｘｔｒｅｅ［３３］是第一个基于Ｂ＋ｔｒｅｅ索引移 动对象的方法．整个空间被划分为若干个单元格，借 助于空间填充曲线（ｓｐａｃｅｆｉｌｌｉｎｇｃｕｒｖｅ），每个单元 ７期 周傲英等：基于位置的服务：架构与进展 １１５９