1164 计算 机学 报 2011年 情况. 设该机器人的位置服从正态分布，针对这一特殊的 (1)查询发出点精确，被查询的数据点是不确 分布，提出了3种优化的策略.此问题的定义虽然是 定的移动对象。 在室内的机器人应用，但是其使用的模型仍然是室 这类不确定查询在LBS中最常见.Cheng等 外空间常用的几何模型，并未考虑室内符号空间 人[]提出了一套针对室外移动对象的查询处理框 Hu等人[8]则针对最近邻查询进行了研究，并提出 架.首先，根据定位的精度，将移动对象可能出现的 了EXO-tree提高查询效率， 区域限制在一个不确定区域内.在此基础上定义了 (3)查询发出点和被查询数据点都是不确定的. 概率范围查询和概率NN查询.并对直线运动模型 Kriegel等人[9-so]研究了查询出发点和被查询 和自由移动模型的移动对象的不确定性进行了总结 数据点都存在不确定性的查询处理技术，定义了概 与分析，进而有效地处理概率范围查找和概率NN 率kNN查询和概率连接查询，并对Monte Carlo抽 查询.在此基础上，Cheng等人[s]又提出了概率阈 样点建R-tree索引以提高查找效率.Chen等人z) 值kNN查询，根据提出的k-bound概念进行过滤 提出的p-bound则可以用于提高范围查询效率. (k-bound为查询发出点到不确定对象的第k个最 (4)不确定的移动速度. 大距离，如图8所示)，并且提出了3种优化处理 Huang等人[s]考虑移动对象速度变化的不确 该查询的方法.基于树的U-Tree和基于网格的 定性，提出了一种支持连续kNN查询的方法.Lian U-Gid)等索引方法可以索引多维不确定数据. 等人[s)定义了概率RNN查询，并提出了基于双曲 Yang等人[s]提出了针对室内移动对象的查询处理 线的启发式查询处理算法.给定移动对象当前位置和 技术，将范围查询的结果划分为两类：确定结果和不 速度的分布，移动对象不确定性的模型[)可以被确 确定结果.给定移动对象的最大移动速度和室内空 定.根据该模型，可以用于预测未来移动对象的位置。 间的拓扑结构，对不确定结果集上的概率分析也做 7.3非合作策略的不基于TTP的隐私保护方法 了基本讨论.Yang等人在其最新的研究中，针对定 非合作策略的不基于TTP的隐私保护方法是 位系统的精度不确定性，提出了室内移动对象的不 近几年出现的一种新型隐私保护方法，该方法无需 确定区域的定义，并在此基础上提出了基于精确查 用户与其它用户之间的交互，而仅由用户自己完成 询发出点的概率阈值kNN查询处理方法. 整个操作.SpaceTwist[s]使用一个锚点来代替移动 对象的真实位置，通过对服务商不断查找锚点的 0 最近邻的感兴趣点(POI),进而最终确定离真实位 置最近的POL.在这一过程中，服务提供商只获得锚 0.2 点的位置，而不能获得移动对象的真实位置.Ghinita 等人[s提出的基于私人信息恢复(PIR-based)的技 0 术也是非合作策略的方法.如图9所示，它通过把隐 私信息使用加密技术处理再发出查询请求，得到查 询结果后再在客户端解密，保证了用户信息的私密 k-bound (=3) 性，这一方法不仅保护了单次查询的隐私，同时还可 图8查询发出点精确的不确定移动对象NN查询，k=3) 以很好地保护多次关联查询的隐私，以防止对手分 析多次查询之间的关联性来窃取用户隐私. (2)查询发出点是不确定的移动对象，被查询 的数据点是精确的 加密位置请求 LBS Chen等人[)针对范围查询提出了3种优化方 用户 提供商 法：首先通过查询扩展，过滤掉一些不可能成为查询 加密结果 结果的数据点；接着通过互换查询发出点和数据点 对加密结果 的角色，提高查询效率：最后针对阈值概率查询，提 进行解密 出了p-bound以限制查找空间，进而提高查询效 图9基于PIR的隐私保护策略[] 率.Ishikawa等人[)则考虑了室内机器人这一应用 在找朋友应用中需要检测朋友之间的空间临近 场景，范围查询从不确定的机器人位置发出，并且假 性，这就要求用户隐私数据被保护的同时，还需要保情况．（１）查询发出点精确，被查询的数据点是不确 定的移动对象． 这类不确定查询在ＬＢＳ中最常见．Ｃｈｅｎｇ等 人［７１］提出了一套针对室外移动对象的查询处理框 架．首先，根据定位的精度，将移动对象可能出现的 区域限制在一个不确定区域内．在此基础上定义了 概率范围查询和概率ＮＮ查询．并对直线运动模型 和自由移动模型的移动对象的不确定性进行了总结 与分析，进而有效地处理概率范围查找和概率ＮＮ 查询．在此基础上，Ｃｈｅｎｇ等人［７３］又提出了概率阈 值犽ＮＮ查询，根据提出的犽ｂｏｕｎｄ概念进行过滤 （犽ｂｏｕｎｄ为查询发出点到不确定对象的第犽个最 大距离，如图８所示），并且提出了３种优化处理 该查询的方法．基于树的ＵＴｒｅｅ［７４］和基于网格的 ＵＧｒｉｄ［７５］等索引方法可以索引多维不确定数据． Ｙａｎｇ等人［６８］提出了针对室内移动对象的查询处理 技术，将范围查询的结果划分为两类：确定结果和不 确定结果．给定移动对象的最大移动速度和室内空 间的拓扑结构，对不确定结果集上的概率分析也做 了基本讨论．Ｙａｎｇ等人在其最新的研究中，针对定 位系统的精度不确定性，提出了室内移动对象的不 确定区域的定义，并在此基础上提出了基于精确查 询发出点的概率阈值犽ＮＮ查询处理方法． 图８查询发出点精确的不确定移动对象犽ＮＮ查询，犽＝３［７３］ （２）查询发出点是不确定的移动对象，被查询 的数据点是精确的． Ｃｈｅｎ等人［７６］针对范围查询提出了３种优化方 法：首先通过查询扩展，过滤掉一些不可能成为查询 结果的数据点；接着通过互换查询发出点和数据点 的角色，提高查询效率；最后针对阈值概率查询，提 出了狆ｂｏｕｎｄ以限制查找空间，进而提高查询效 率．Ｉｓｈｉｋａｗａ等人［７７］则考虑了室内机器人这一应用 场景，范围查询从不确定的机器人位置发出，并且假 设该机器人的位置服从正态分布．针对这一特殊的 分布，提出了３种优化的策略．此问题的定义虽然是 在室内的机器人应用，但是其使用的模型仍然是室 外空间常用的几何模型，并未考虑室内符号空间． Ｈｕ等人［７８］则针对最近邻查询进行了研究，并提出 了ＥＸＯｔｒｅｅ提高查询效率． （３）查询发出点和被查询数据点都是不确定的． Ｋｒｉｅｇｅｌ等人［７９８０］研究了查询出发点和被查询 数据点都存在不确定性的查询处理技术，定义了概 率犽ＮＮ查询和概率连接查询，并对ＭｏｎｔｅＣａｒｌｏ抽 样点建Ｒｔｒｅｅ索引以提高查找效率．Ｃｈｅｎ等人［７６］ 提出的狆ｂｏｕｎｄ则可以用于提高范围查询效率． （４）不确定的移动速度． Ｈｕａｎｇ等人［８１］考虑移动对象速度变化的不确 定性，提出了一种支持连续犽ＮＮ查询的方法．Ｌｉａｎ 等人［８２］定义了概率犚ＮＮ查询，并提出了基于双曲 线的启发式查询处理算法．给定移动对象当前位置和 速度的分布，移动对象不确定性的模型［７２］可以被确 定．根据该模型，可以用于预测未来移动对象的位置． ７３非合作策略的不基于犜犜犘的隐私保护方法 非合作策略的不基于ＴＴＰ的隐私保护方法是 近几年出现的一种新型隐私保护方法，该方法无需 用户与其它用户之间的交互，而仅由用户自己完成 整个操作．ＳｐａｃｅＴｗｉｓｔ［８３］使用一个锚点来代替移动 对象的真实位置，通过对服务商不断查找锚点的犽 最近邻的感兴趣点（ＰＯＩ），进而最终确定离真实位 置最近的ＰＯＩ．在这一过程中，服务提供商只获得锚 点的位置，而不能获得移动对象的真实位置．Ｇｈｉｎｉｔａ 等人［８４］提出的基于私人信息恢复（ＰＩＲｂａｓｅｄ）的技 术也是非合作策略的方法．如图９所示，它通过把隐 私信息使用加密技术处理再发出查询请求，得到查 询结果后再在客户端解密，保证了用户信息的私密 性．这一方法不仅保护了单次查询的隐私，同时还可 以很好地保护多次关联查询的隐私，以防止对手分 析多次查询之间的关联性来窃取用户隐私． 图９基于ＰＩＲ的隐私保护策略［８１］ 在找朋友应用中需要检测朋友之间的空间临近 性，这就要求用户隐私数据被保护的同时，还需要保 １１６４ 计 算 机 学 报 ２０１１年