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和 不确定位置信息管理技术大致可分为如下几种的位置发送给服务提供商；（４）服务提供商根据接 收到的位置提供服务．Ｃｈｏｗ等人［５７］在此基础上提 出了一种基于点对点（Ｐ２Ｐ）架构的基于合作的隐私 保护技术．ＭｏｂｉＨｉｄｅ［５８］方法也利用点对点构架，把 用户的二维空间信息通过Ｈｉｌｂｅｒｔ曲线映射到一维 空间，通过在映射后的一维空间内选取连续的犽个 对象以保护用户的隐私．Ｓｏｌａｎａｓ等人［５９］也提出了 一个无需借助ＴＴＰ的网络传输协议． 尽管上述方法不再依赖ＴＴＰ，但是仍然需要和 至少犽－１个可信用户交互［６０］，增加了整个方法的 通信复杂度，并且在实际应用中无法有效保证参与 隐私保护的其它犽－１个用户是可信的．最近，一些 学者提出了新的解决方案，并不借助与临近节点的 交互．我们将在下一节中详细叙述． ７近期研究进展 ７１室内犔犅犛技术 随着大型建筑物的内部空间趋于大型化和复杂 化，室内ＬＢＳ（例如室内导航等）得到了越来越多的 关注［８，６１］．例如，博物馆的自动导游指引服务、基于 乘客移动模式分析的机场商铺规划等．为了支持此 类服务，亟需发展室内空间建模技术、索引技术和连 续查询处理技术． 室内空间模型．一般来说，室内空间的拓扑关 系比室外空间复杂得多，因而更适合用符号化的坐 标系统［６２］对室内空间结构建模．三维几何网络模 型［６３］区分对待室内实体（房间）之间水平和垂直的 连通关系．３ＤＰｏｉｎｃａｒｅＤｕａｌｉｔｙ［６４］通过对偶转换，把 三维空间内的实体的连通关系转换为对偶空间，可 以应用于室内空间紧急疏散线路的计算．为了支持 室内导航，一种三维可测量拓扑模型［６５］被提出，该 模型同时考虑空间实体的形状和连通关系．Ｌｉ等人 提出基于栅格的语义模型［６６］，可以维持不同室内位 置间的最短路径．Ｊｅｎｓｅｎ等人［６１］提出了一种基于图 模型的方法，不仅维持室内实体间的拓扑结构，还能 有效管理基于感知定位的室内定位数据． 室内轨迹索引技术．由于室内空间表示为符号 化系统，因此室内轨迹表达方式也和室外轨迹不同． 室内移动对象的轨迹可以表示在一个包含空间维和 时间维的多维空间．空间维用符号化的地理位置编 号表示，例如房间号、ＲＦＩＤ阅读器编号等．这样，移 动对象的轨迹可以表示为若干水平线段，进而利用 Ｒｔｒｅｅ索引这些线段，如图７所示．Ｊｅｎｓｅｎ、Ｌｕ和 Ｙａｎｇ［６１］提出了一种基于图的室内移动对象的跟踪算 法，用于确定室内移动对象的轨迹，并且提出了两种 基于Ｒｔｒｅｅ的索引结构ＲＴＲｔｒｅｅ和ＴＰ２Ｒｔｒｅｅ［６７］． ＲＴＲｔｒｅｅ将室内移动对象的轨迹表示为若干水平 的线段，ＴＰ２Ｒｔｒｅｅ则把轨迹表示为一个带时间参 数的点．这两种索引结构均可有效支持室内空间的 范围查询和室内轨迹查找． 图７室内移动对象在符号空间下的轨迹以及 对应的ＲＴＲｔｒｅｅ和ＴＰ２Ｒｔｒｅｅ［６７］ 连续查询处理．针对室内移动对象的连续查询 处理，Ｙａｎｇ等人［６８］提出了一种查询感知的、增量的 方法．该方法适用于基于符号化存在感应器的室内 定位技术（如ＲＦＩＤ）．针对每个连续范围查询，作者 提出了关键设备的概念，即在符号空间中的安全区 域［３２］．仅当关键设备有新的读数产生时，会对查询 结果进行增加或删除操作．这样，非关键设备的新读 数将不会被用于增量更新查询结果． ７２不确定的位置服务 位置信息的不确定性源于多种因素．首先，非连 续的定位采样会带来不确定性．一般来说，定位技术 会定期汇报位置信息，因而移动对象的位置在相邻 两次采样之间存在不确定性［６９７０］．其次，定位技术自 身具有精度限制［７１］．再次，当以物体的历史运动轨 迹和附加信息来预测其未来行为时也存在不确定 性［７２］．最后，出于隐私保护目的，需将数据模糊 化［４７］，人为地引入不确定性． 不确定位置信息管理技术大致可分为如下几种 ７期 周傲英等：基于位置的服务：架构与进展 １１６３