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(x<120)and extract(p):从元组空间中取出符合谓词p的 (y>150)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)是另一种处 则考虑到每个移动终端的计算和存储能力有差别， 理连续查询的索引结构，和通常的索引构建策略相 针对每个移动终端最多能处理的查询个数确定一个
狉犲犪犱（狆）：从元组空间中读取符合谓词狆的元 组，但该元组仍旧保留在元组空间中． ＬＢＳ系统可以很方便地使用元组空间模型，信 息发布者和订阅者通过元组空间进行通信． ５服务处理方法 ５１快照查询和连续查询 如前所述，从查询处理的技术角度，基于位置的 服务通常包含两类查询服务：快照查询和连续查询． 快照查询访问移动对象数据库后立即返回查询结 果．典型的快照查询如：“查询当前离我最近的快餐 店”．连续查询根据周围环境变化情况持续刷新查询 结果．例如，“监控未来一小时内某路口车流量变化” 就是一个典型的连续查询． 快照查询的处理较为简单．根据查询对象的时 效性不同，快照查询大致可分为历史查询、当前查询 和未来查询三类．历史查询用于查询过去时间内发 生的事件，例如“查找哪些车辆昨天出现在停车场”； 当前查询用于查询正在发生的事情，例如“查找哪些 车辆现在出现在停车场”；将来查询则查询将要发生 的事件，例如“查找哪些车辆将在五分钟后出现在停 车场”．为了提高快照查询的执行效率，需要创建各 种索引结构．对于历史查询，需要在时间空间维度 上对移动对象的历史运动轨迹进行索引．对于当前 查询和未来查询，则需要对移动对象的当前位置进 行索引，并维护移动对象的移动模型．这一类索引结 构需要支持较多的更新操作．这两种索引结构已经 在第３节中做详细综述． 相比而言，连续查询的处理更为复杂，常用的策 略有周期性快照查询法［３２］、增量处理法和查询感知 处理法．周期性快照查询法．该方法是最朴素的连续查 询处理方法，定期执行快照查询（通常是当前快照查 询），并刷新查询结果．缺点是难以有效地定义周期 值：过小的周期值将增加系统负荷，而过大的周期值 会降低查询结果精度． 增量处理法．根据初始结果，动态增加新数据 或者删除过期数据．ＳＩＮＡ［４２］定义了两类更新：正更 新和负更新（从当前结果集内增加或删除一个移动 对象），从而增量地更新查询结果．ＳＩＮＡ通过散列、 验证和连接３个步骤完成对连续查询的正负更新， 从而有效地执行连续查询．Ｑｉｎｄｅｘ［３２］是另一种处 理连续查询的索引结构．和通常的索引构建策略相 反，Ｑｉｎｄｅｘ为所有查询建立索引，当移动对象的位 置变化时，通过Ｑｉｎｄｅｘ可以找到受影响的查询， 并更新相应的查询结果． 查询感知处理法．该方法根据连续查询的查询 条件计算出“安全区域”［３２，４３］，只有当移动对象离开 或进入“安全区域”时，才会影响查询结果．因此，系 统可以忽略很多不影响查询结果的位置更新操作， 进而降低系统负荷．如图５所示，给定５个范围查询， 对象犃的安全区域表示为一个以犃为圆心的圆，而 对象犅的安全区域则是一个矩形．文献［３２，４３］基于 欧式空间距离计算安全区域，而在实际应用中许多 时候需要基于道路网络进行计算．针对这一特点， Ｙｉｕ等人［４４］针对道路网络上的犽ＮＮ连续查询提出 了新的方法．该方法首先通过确定能够影响当前 犽ＮＮ结果的路段，当移动对象离开该路段时则更新 连续查询结果．该方法同时支持共享查询处理． 图５安全区域［３２］ ５２分布式查询处理方法 按照移动终端是否参与查询处理，服务处理方 法可以分为集中式和分布式两种处理方式．在集中 式方式中，仅服务提供商处理连续查询，移动终端并 不参与查询处理．分布式方式中，服务提供商与移动 终端协作完成连续查询处理． Ｇｅｄｉｋ等人［４５］提出了一种分布式连续查询处理 架构ＭｏｂｉＥｙｅｓ，其核心思想是由移动终端来计算和 判断是否是一个连续查询的结果，而中心服务器负 责注册和维护连续查询的相关参数，并将参数传到 相关移动终端．移动终端维护一个注册表以记录临 近的一组连续查询，并周期性地检查自己是否属于 这些查询的结果之中．若是，则向服务器报告．为减 少服务器和移动终端之间的通信代价和移动终端的 计算开销，该文还提出了３种优化策略．Ｃａｉ等人［４６］ 则考虑到每个移动终端的计算和存储能力有差别， 针对每个移动终端最多能处理的查询个数确定一个 ７期 周傲英等：基于位置的服务：架构与进展 １１６１