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