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家族]等 代表性的索引技术.这类空间索引技术能够有效实 现对静态空间对象的索引.然而，当移动对象频繁移 动时，上述索引技术的性能显著下降.因此，近年来 图？室外移动对象在几何坐标下的移动轨迹四]测量的方法通过信号传递模型，将接收到的信号强 度转换为到访问点的距离，进而利用三边测量法定 位．但是由于室内影响信号强度的因素很多，这使 得建立一个通用的信号传播模型并不简单，而模 型的好坏直接影响到定位的效果．基于信号强度指 纹的方法首先将事先选择的室内空间每个参考点到 所有ＷｉＦｉ访问点的信号强度（即指纹）记录到数 据库，终端根据当前自身到所有访问点的信号强 度信息在指纹数据库中查找与其最接近的参考 点，并用该参考点的位置定位移动终端．这种方法 的精度在很大程度上取决于参考点选取的数量和 位置．感知定位技术．感知定位技术适用于短距离识 别．一般而言，需要一个信号发送端和一个信号接收 端．当信号发送端和信号接收端相互间距离很小时， 则能够被识别．ＲＦＩＤ就是一种典型的感知定位技 术．ＲＦＩＤ系统通常包括两个组成部分：ＲＦＩＤ阅读 器和ＲＦＩＤ标签．ＲＦＩＤ阅读器能感知其覆盖区域内 出现的ＲＦＩＤ标签．当携带ＲＦＩＤ标签的对象被某 一ＲＦＩＤ阅读器感知时，即可对该对象定位．该方法 与移动通信网络的ＣＯＯ方法类似，但是ＲＦＩＤ的覆 盖区域要小很多，主要用于室内空间．这使得ＲＦＩＤ 定位的位置通常被限制在符号系统中．符号系统比 几何坐标系统更适合描述室内空间，比如人们通常 用房间号码来指示一个室内位置，而不是通过经纬 度．另一方面，通过ＲＦＩＤ读卡器的部署信息，可以 将符号系统的坐标转化为几何坐标系统．因此，为了 更好地利用ＲＦＩＤ进行室内定位，需要综合考虑室 内空间的平面规划和ＲＦＩＤ阅读器的部署．此外，蓝 牙、红外等也是比较典型的感知定位技术． 表１总结了各类定位技术的特点． 表１定位技术对比 类别 代表性技术 精度 覆盖范围 应用场景 定位坐标 卫星定位技术 ＧＰＳ，北斗，伽利略 中高 广 室外 几何坐标 基于网络的定位技术 ＧＳＭ，３Ｇ，ＣＤＭＡ，ＷｉＦｉ 中低 较广 室外／室内 几何坐标 感知定位技术 ＲＦＩＤ，蓝牙，红外 高 小 室内 符号坐标 由于室内、室外的环境不同，定位技术的工作原 理不同，使得很难有一种定位技术能同时广泛地支 持室内和室外定位．为了给服务提供商进行统一的 室内外定位信息，需要在室内室外定位技术之间进 行切换．Ｈａｎｓｅｎ等人［１２］对这一问题进行了研究，提 出了针对室外ＧＰＳ定位和室内ＷｉＦｉ定位之间的 ４种切换策略．相对于室外空间的成熟定位技术，近 年来对室内空间的各类定位技术的研究比较集中． 但大部分研究集中在如何提高某一个特定技术的定 位精度．如何通过多种室内定位技术获得更精确的 位置信息也有较高的研究价值，即提供一种通用的 室内定位模型． ３索引技术 索引技术是移动对象数据库的核心技术，决定 了ＬＢＳ的查询性能．对空间数据的索引技术的研究 工作已经开展了２０余年的时间，出现了Ｒｔｒｅｅ家 族［１３１４］、ＫＤｔｒｅｅ家族［１５１６］和Ｑｕａｒｄｔｒｅｅ家族［１７］等 代表性的索引技术．这类空间索引技术能够有效实 现对静态空间对象的索引．然而，当移动对象频繁移 动时，上述索引技术的性能显著下降．因此，近年来 出现了一批有针对性的移动对象历史轨迹索引技术 和移动对象当前／将来位置索引技术．历史轨迹索引 技术不仅考虑对象的空间位置，也考虑时间维度；当 前将来位置索引技术则对于移动对象位置的更新 操作具有良好的适应性． ３１历史轨迹索引技术 首先我们来讨论索引移动对象历史轨迹的方 法．历史轨迹的索引方法可以分为两类：基于Ｒｔｒｅｅ 的索引和基于Ｈａｓｈ的索引．基于Ｒｔｒｅｅ的历史轨 迹索引方法将时间维视为一个普通维，将移动对象 的轨迹表示成多维空间内的一组线段，再用Ｒｔｒｅｅ 进行索引．如图２所示，一个移动对象的轨迹被表现 在二维几何空间范围（狓，狔）和一个时间维（狋）的三维 空间内． 图２室外移动对象在几何坐标下的移动轨迹［２２］ １１５８ 计 算 机 学 报 ２０１１年