1162 计算 学 报 2011年 存在区域，仅当移动对象离开存在区域时，才向中心 位置，请求 位置，请求 服务器发送位置更新，并获取新的存在区域.移动终 LBS TTP 提供商 端在存在区域移动时，需要自己计算并检查是否是 结果 结果 与该存在区域相关的连续查询的结果， 基于TTP的隐私保护方法 与集中式方式相比，分布式方式通常需要在服 用户1 位置'，请求 务器与移动终端之间传递更多的消息，这带来两个 结果 LBS 问题：一是大量移动终端可能造成网络拥塞；二是网 提供商 络通信会消耗移动终端的能量，缩短充电周期.另 用户 外，该方法无法适用于无计算能力的移动终端，如仅 基于合作策略的非TTP隐私保护方法 携带RFID标签的移动对象. 图6隐私保护方法 6 隐私保护 区分开来.Gedik等人提出了整合时间和空间区 域的k-匿名方法CliqueCloak,在一个时空立方体内 隐私保护是LBS的重要内容.用户并不期望由 部至少仍然存在其它k一1个对象.林欣等人[]发 于接受了服务而向外界泄露了位置信息，这既包括 现k-匿名方法对连续攻击保护效果较弱，提出了一 当前的具体位置，也包括对象的移动习惯等.最常用 种能够有效保护连续查询时用户隐私的基于嫡理论 的位置隐私解决方案是空间伪装(spatial cloa- 的度量方式AD(anonymity degree).Mokbel等 king)),即用户将位置伪装成为一个区域之后再 人[s]提出了Casper方法，利用金字塔数据结构将 发送给服务提供商，服务提供商则根据用户所提供 整个空间划分成大小不等的单元，若移动对象较为 的区域信息为用户提供服务.在这种方式下，服务提 密集，则单元面积较小；反之，则单元面积较大 供商无法准确得知用户的位置.事实上，用户隐私和 Kalnis等人s]提出了Hilbert Cloak方法，利用 服务质量是一对矛盾关系，需根据具体情况进行权 Hilbert曲线将二维空间映射成一维空间，再利用 衡.Tan等人[4]提出了量化分析隐私保护和服务质 B+-tree对移动对象建立索引.通过选取具有连续 量比例的方法.本节回顾两大类隐私保护技术[4町， Hilbert值的k个对象进行隐私保护.Privacy- 即依赖于可信赖的第三方机构的技术（简称TTP- Gids]使用网格进行k-匿名，并在此基础上增加了 based)和不依赖于可信赖的第三方机构的技术（简 -多样性，进而又提高了隐私的保护程度. 称非TTP-based). 依赖于可信赖第三方的隐私保护技术的有效性 6.1依赖可信赖第三方机构的隐私保护方法 在很大程度上取决于第三方机构是否可信.近年来， 在TTP-based技术中，用户将位置信息发送给 陆续出现了一些有关第三方机构的丑闻事件，使得 TTP(Trusted Third Party),由TTP对位置信息做 第三方机构的独立性与权威性大打折扣.该技术的 变换，之后再连同服务请求一起发送给服务提供商； 另一个缺点是集中式处理方式，即所有用户请求均 服务提供商基于不精确的位置信息进行处理，并将 发送到TTP,使得TTP成为系统性能瓶颈.因此， 服务结果返回给TTP.TTP经过过滤、取精后返回 当前的发展趋势越来越倾向于不依赖可信第三方的 给用户，如图6所示.在此过程中，TTP的主要任务 隐私保护方法， 是将原始的、准确的位置信息转化为不准确的位置 6.2不依赖可信赖第三方机构的隐私保护方法 信息，以保护用户的隐私 目前，有一些隐私保护技术并不依赖于TTP, 一种简单的方法是TTP直接用虚假标识符表 其基本思想是用户和其它用户之间交互位置信息， 示真实的用户标识符，再发送给服务提供商[4们.但 进而构造伪装的位置，如图6所示.主要步骤如 是，服务提供商仍可借助其它辅助信息进行破解，比 下[56]：(1)请求服务的用户A首先将自身位置模糊 如通过电话号码或家庭住址来推测真实用户信息， 化，并向周围的邻居广播：(2)邻居对象将模糊化之 k-匿名方法是另外一种使用较广泛的方法[50，其核 后的位置信息发送给用户A,直到A至少搜集到 心思想是以一个覆盖移动对象的矩形来描述该对象 一1个移动用户的位置信息：(3)用户A随机选取 的真实位置，该矩形同时还包含另外k一1个对象， 及一1个对象，与自身构成一个含k个对象的集合，并 使得服务提供商无法将该对象与其余k一1个对象 将包含这些对象的MBR或任意一个非用户A对象存在区域，仅当移动对象离开存在区域时，才向中心 服务器发送位置更新，并获取新的存在区域．移动终 端在存在区域移动时，需要自己计算并检查是否是 与该存在区域相关的连续查询的结果． 与集中式方式相比，分布式方式通常需要在服 务器与移动终端之间传递更多的消息，这带来两个 问题：一是大量移动终端可能造成网络拥塞；二是网 络通信会消耗移动终端的能量，缩短充电周期．另 外，该方法无法适用于无计算能力的移动终端，如仅 携带ＲＦＩＤ标签的移动对象． ６隐私保护 隐私保护是ＬＢＳ的重要内容．用户并不期望由 于接受了服务而向外界泄露了位置信息，这既包括 当前的具体位置，也包括对象的移动习惯等．最常用 的位置隐私解决方案是空间伪装（ｓｐａｔｉａｌｃｌｏａ ｋｉｎｇ）［４７］，即用户将位置伪装成为一个区域之后再 发送给服务提供商，服务提供商则根据用户所提供 的区域信息为用户提供服务．在这种方式下，服务提 供商无法准确得知用户的位置．事实上，用户隐私和 服务质量是一对矛盾关系，需根据具体情况进行权 衡．Ｔａｎ等人［４８］提出了量化分析隐私保护和服务质 量比例的方法．本节回顾两大类隐私保护技术［４９］， 即依赖于可信赖的第三方机构的技术（简称ＴＴＰ ｂａｓｅｄ）和不依赖于可信赖的第三方机构的技术（简 称非ＴＴＰｂａｓｅｄ）． ６１依赖可信赖第三方机构的隐私保护方法 在ＴＴＰｂａｓｅｄ技术中，用户将位置信息发送给 ＴＴＰ（ＴｒｕｓｔｅｄＴｈｉｒｄＰａｒｔｙ），由ＴＴＰ对位置信息做 变换，之后再连同服务请求一起发送给服务提供商； 服务提供商基于不精确的位置信息进行处理，并将 服务结果返回给ＴＴＰ．ＴＴＰ经过过滤、取精后返回 给用户，如图６所示．在此过程中，ＴＴＰ的主要任务 是将原始的、准确的位置信息转化为不准确的位置 信息，以保护用户的隐私． 一种简单的方法是ＴＴＰ直接用虚假标识符表 示真实的用户标识符，再发送给服务提供商［４４］．但 是，服务提供商仍可借助其它辅助信息进行破解，比 如通过电话号码或家庭住址来推测真实用户信息． 犽匿名方法是另外一种使用较广泛的方法［５０］，其核 心思想是以一个覆盖移动对象的矩形来描述该对象 的真实位置，该矩形同时还包含另外犽－１个对象， 使得服务提供商无法将该对象与其余犽－１个对象 图６隐私保护方法 区分开来．Ｇｅｄｉｋ等人［５１］提出了整合时间和空间区 域的犽匿名方法ＣｌｉｑｕｅＣｌｏａｋ，在一个时空立方体内 部至少仍然存在其它犽－１个对象．林欣等人［５２］发 现犽匿名方法对连续攻击保护效果较弱，提出了一 种能够有效保护连续查询时用户隐私的基于熵理论 的度量方式ＡＤ（ａｎｏｎｙｍｉｔｙｄｅｇｒｅｅ）．Ｍｏｋｂｅｌ等 人［５３］提出了Ｃａｓｐｅｒ方法，利用金字塔数据结构将 整个空间划分成大小不等的单元，若移动对象较为 密集，则单元面积较小；反之，则单元面积较大． Ｋａｌｎｉｓ等人［５４］提出了ＨｉｌｂｅｒｔＣｌｏａｋ方法，利用 Ｈｉｌｂｅｒｔ曲线将二维空间映射成一维空间，再利用 Ｂ＋ｔｒｅｅ对移动对象建立索引．通过选取具有连续 Ｈｉｌｂｅｒｔ值的犽个对象进行隐私保护．Ｐｒｉｖａｃｙ Ｇｒｉｄ［５５］使用网格进行犽匿名，并在此基础上增加了 犾多样性，进而又提高了隐私的保护程度． 依赖于可信赖第三方的隐私保护技术的有效性 在很大程度上取决于第三方机构是否可信．近年来， 陆续出现了一些有关第三方机构的丑闻事件，使得 第三方机构的独立性与权威性大打折扣．该技术的 另一个缺点是集中式处理方式，即所有用户请求均 发送到ＴＴＰ，使得ＴＴＰ成为系统性能瓶颈．因此， 当前的发展趋势越来越倾向于不依赖可信第三方的 隐私保护方法． ６２不依赖可信赖第三方机构的隐私保护方法 目前，有一些隐私保护技术并不依赖于ＴＴＰ， 其基本思想是用户和其它用户之间交互位置信息， 进而构造伪装的位置，如图６所示．主要步骤如 下［５６］：（１）请求服务的用户犃首先将自身位置模糊 化，并向周围的邻居广播；（２）邻居对象将模糊化之 后的位置信息发送给用户犃，直到犃至少搜集到 犽－１个移动用户的位置信息；（３）用户犃随机选取 犽－１个对象，与自身构成一个含犽个对象的集合，并 将包含这些对象的ＭＢＲ或任意一个非用户犃对象 １１６２ 计 算 机 学 报 ２０１１年