位置服务与隐私保护课件

位置服务（LBS）中的隐私保护位位 置置 服服 务（LBS）位置位置服务服务简言之，就是简言之，就是基于地理位置数据基于地理位置数据而展开的服务。是指通过而展开的服务。是指通过移动终端和无线通讯网络（或卫星定位系统）的相互配合，移动终端和无线通讯网络（或卫星定位系统）的相互配合，以空间数据库为基础，确定移动用户的实际地理位置或坐以空间数据库为基础，确定移动用户的实际地理位置或坐标，并将其与其他信息整合起来，为用户提供所需要的与标，并将其与其他信息整合起来，为用户提供所需要的与位置相关的增值服务。位置相关的增值服务。LBSLBS：Location Based ServiceServices that intergrate a mobile devices location or position with other information so as to provide added value to a user位 置 服 务（LBS）位置简言之，就是基于地理位置数据而展GPSSENSORRFID紧急救援服务紧急救援服务信息娱乐服务信息娱乐服务分发服分发服务务交通导航交通导航跟踪服务跟踪服务定位最近的救援者位置定位最近的救援者位置查找距离我百米内最近的银行查找距离我百米内最近的银行向我餐馆向我餐馆500500米范围内的用户发送电子优惠券米范围内的用户发送电子优惠券查找到达目的地的最优路径查找到达目的地的最优路径对航空物流进行追踪对航空物流进行追踪GPSSENSORRFID紧急救援服务信息娱乐服务分发服务交位置服务前景广阔位置服务前景广阔.20072007年以来中国位置服务市场规模及增长年以来中国位置服务市场规模及增长市场规模市场规模位置服务前景广阔.2007年以来中国位置服务市场规模及位置服务前景广阔位置服务前景广阔.用户数量用户数量20072007年以来中国位置服务用户规模及增长年以来中国位置服务用户规模及增长全球及国内移动位置服务市场发展阶段对比全球及国内移动位置服务市场发展阶段对比位置服务前景广阔.用户数量2007年以来中国位置服务用 位置服务位置服务（LBS）军事产业军事产业政府事务政府事务求助服务求助服务追踪监控追踪监控定位导航定位导航休闲娱乐休闲娱乐分发服务分发服务Form oracle位置服务前景广阔位置服务前景广阔.使用领域 位置服务军事产业政府事务求助服务追踪监控定位导航休闲娱 也许某天，当你经过熟悉的星巴克，也许某天，当你经过熟悉的星巴克，打开手机记录你的位置，却惊喜地发打开手机记录你的位置，却惊喜地发现一位好友也正在这里享用咖啡。而现一位好友也正在这里享用咖啡。而在不远处的商场内，某件你关注了很在不远处的商场内，某件你关注了很久的名牌衬衫正在打折久的名牌衬衫正在打折又或者你去一个遥远的城市旅行，打又或者你去一个遥远的城市旅行，打开手机，却发现自己瞬间对这个陌生开手机，却发现自己瞬间对这个陌生的地方变得如此熟悉，想去哪儿就能的地方变得如此熟悉，想去哪儿就能随心所欲，想玩什么立马就能朝着目随心所欲，想玩什么立马就能朝着目标出发标出发此时，你肯定会为位置服此时，你肯定会为位置服务所带来的便捷生活方式而兴奋！务所带来的便捷生活方式而兴奋！可是你又是否设想过，未来，无可是你又是否设想过，未来，无论你走到哪里，上班，下班，旅论你走到哪里，上班，下班，旅行亦或是散步，都会有漫天飞舞行亦或是散步，都会有漫天飞舞的各种广告铺天盖地向你席卷而的各种广告铺天盖地向你席卷而来，你无处躲藏，只能被淹没在来，你无处躲藏，只能被淹没在信息的垃圾中烦恼叹息信息的垃圾中烦恼叹息甚至有一天，对你而言，无论是熟甚至有一天，对你而言，无论是熟悉的亲朋还是陌生人，都没有了秘悉的亲朋还是陌生人，都没有了秘密，每天无论你走到哪儿，干了什密，每天无论你走到哪儿，干了什么，将要去哪，甚至你最近喜欢什么，将要去哪，甚至你最近喜欢什么，想要计划什么，大家都能知道么，想要计划什么，大家都能知道的时候，你会不会又对这一新兴的的时候，你会不会又对这一新兴的服务产生恐惧呢。服务产生恐惧呢。1432也许某天，当你经过熟悉的星巴克，打开手机记录你如何解决位置服务如何解决位置服务中堪忧的隐私保护中堪忧的隐私保护问题呢？问题呢？如何解决位置服务中堪忧的隐私保护问题呢？内内 容容 导导 览览导引：隐私保护问题导引：隐私保护问题隐私保护的系统结构隐私保护的系统结构隐私保护模型与匿名技术隐私保护模型与匿名技术隐私保护的算法实现隐私保护的算法实现内 容 导 览导引：隐私保护问题隐私保护的系统结构隐私保护模4隐私问题举例隐私问题举例生活中这样的例子很常见：张某利用自己带有GPS的手机提出了“寻找距离我（现在所在位置）最近的肿瘤医院”的查询。这是导航系统中一个普通的最近邻查询（即NN查询）。此查询被提交给服务提供商，比如Google Maps，再由服务提供商通过查询空间数据库返回给用户查询结果。此时涉及到的隐私问题包含两个方面：一是用此时涉及到的隐私问题包含两个方面：一是用户不想让人知道他此刻所在的位置户不想让人知道他此刻所在的位置,比如银行。比如银行。二是用户不想让任何人知道自己提出了某方面二是用户不想让任何人知道自己提出了某方面的查询，如张某不想让人知道自己将去肿瘤医的查询，如张某不想让人知道自己将去肿瘤医院。院。4隐私问题举例生活中这样的例子很常见：张某利用自己带有GPS4位置服务中的隐私泄露位置服务中的隐私泄露查询隐私泄露查询隐私泄露其他人以任何方式获知对象过去或现在的位置。位置隐私泄露位置隐私泄露 查询请求的内容，可能透露用户的行为模式（如经常走的道路及经过的频率）、兴趣爱好（如喜欢去哪个商店、哪种俱乐部）、健康状况（如经常去的心理咨询诊所）以及政治倾向等个人隐私信息。4位置服务中的隐私泄露查询隐私泄露其他人以任何方式获知对象过4隐私泄露的三种途径隐私泄露的三种途径观察观察（Observation）攻击者从位置设备或者位置服务器中直接获取用户的位置信息。（如利用手机内置GPS定位导致的位置信息泄露）直接交流（直接交流（Direct Communication）攻击者通过“位置”连接外部的数据源（或者背景知识）从而确定在该位置或者发送该消息的用户。（如查询信息A是从别墅B发出的，当攻击者知道别墅B的主人是C这一背景时，那么就能确定A是由C发出的）攻击者通过观察被攻击者的行为直接获取位置信息。（如攻击者跟踪被攻击者）连接泄露（连接泄露（Link Attack）4隐私泄露的三种途径观察（Observation）攻击者从位4位置服务中的隐私保护位置服务中的隐私保护查询隐私保护查询隐私保护避免用户与某一精确位置匹配。避免用户与某一精确位置匹配。位置隐私保护位置隐私保护 避免用户与某一敏感查询匹配。避免用户与某一敏感查询匹配。4位置服务中的隐私保护查询隐私保护避免用户与某一精确位置匹配4寻找一种状态，在这种寻找一种状态，在这种状态下很多对象组成一状态下很多对象组成一个集合（匿名集），从个集合（匿名集），从集合的外面向里看，组集合的外面向里看，组成集合的各个对象无法成集合的各个对象无法被区分，使得某一个位被区分，使得某一个位置的信息无法与确切的置的信息无法与确切的个人个人/组织组织/机构相匹配。机构相匹配。位置信息经过匿名处理位置信息经过匿名处理后不再是用户的真实位后不再是用户的真实位置，可能是多个位置的置，可能是多个位置的集合或者一个模糊化的集合或者一个模糊化的位置，查询系统应该对位置，查询系统应该对应地返回包含真实查询应地返回包含真实查询信息的模糊信息集信息的模糊信息集隐私保护的工作隐私保护的工作位置匿名位置匿名查询处理查询处理4寻找一种状态，在这种状态下很多对象组成一个集合（匿名集），4位置服务位置服务VS隐私保护隐私保护鱼与熊掌可否兼得？鱼与熊掌可否兼得？位置服务位置服务隐私保护隐私保护提供精确位置提供精确位置隐藏用户位置隐藏用户位置不能兼得！只能寻找平衡点！不能兼得！只能寻找平衡点！在最少的位置暴露下获得最好的服务，使在最少的位置暴露下获得最好的服务，使隐私暴露处于隐私暴露处于“可控状态可控状态”！4位置服务VS隐私保护鱼与熊掌可否兼得？位置服务隐私保护提供隐私保护的特点隐私保护的特点保护位置隐私与享受服务是一对矛盾保护位置隐私与享受服务是一对矛盾位置信息的多维性特点位置信息的多维性特点位置匿名的即时性特点位置匿名的即时性特点基于位置匿名的查询处理基于位置匿名的查询处理位置隐私需求个性化位置隐私需求个性化隐私保护的特点保护位置隐私与享受服务是一对矛盾位置信息的多维 隐私保护的系统结构隐私保护的系统结构Non-cooperative Architecture独立结构独立结构中心服务器结构中心服务器结构Centralized Architecture分布式点对点结构分布式点对点结构Peer-to-peer Architecture仅有客户端与位置数据库服务器的仅有客户端与位置数据库服务器的C/SC/S结构。该结构需结构。该结构需要移动用户拥有具有强大定位、计算、存储能力的设备，要移动用户拥有具有强大定位、计算、存储能力的设备，自己完成位置匿名和查询结果求精。自己完成位置匿名和查询结果求精。在用户和位置数据库服务器之间加入第三方可信中间件在用户和位置数据库服务器之间加入第三方可信中间件位置匿名服务器，并由位置匿名服务器完成匿名处位置匿名服务器，并由位置匿名服务器完成匿名处理和查询结果求精。理和查询结果求精。由客户端和位置数据库服务器组成，移动客户端根据由客户端和位置数据库服务器组成，移动客户端根据匿名算法找到其他一些移动用户组成一个匿名组，以匿名算法找到其他一些移动用户组成一个匿名组，以此进行位置匿名。同时组内的客户端之间的节点具有此进行位置匿名。同时组内的客户端之间的节点具有平等性，共同协调完成查询结果求精。平等性，共同协调完成查询结果求精。隐私保护的系统结构Non-cooperative独立结独独 立立 结结 构构缺点：缺点：对客户端要求高；对客户端要求高；缺乏全局信息，隐蔽性弱缺乏全局信息，隐蔽性弱优点：优点：结构简单，易于配置结构简单，易于配置处理流程：处理流程：将匿名后的位置连带查询一起发送给将匿名后的位置连带查询一起发送给位置数据库服务器；位置服务器根据匿名的位置位置数据库服务器；位置服务器根据匿名的位置进行查询处理并将候选结果集返回给用户；用户进行查询处理并将候选结果集返回给用户；用户根据真实位置挑选出真正的结果。根据真实位置挑选出真正的结果。独立结构示意图独立结构示意图独 立 结 构缺点：对客户端要求高；优点：结构简单，易于配置优优 点点缺缺 点点中心服务器结构中心服务器结构处理过程处理过程：（：（1 1）用户发送包含精确位置的查询请求给位置匿名服务器。（用户发送包含精确位置的查询请求给位置匿名服务器。（2 2）匿）匿名服务器使用某种匿名算法完成位置匿名后，将匿名后的请求发送给位置数据库名服务器使用某种匿名算法完成位置匿名后，将匿名后的请求发送给位置数据库服务器。（服务器。（3 3）位置数据库服务器根据匿名区域进行查询处理，并将查询结果的）位置数据库服务器根据匿名区域进行查询处理，并将查询结果的候选集返回给位置匿名服务器。（候选集返回给位置匿名服务器。（4 4）位置匿名服务器从候选结果集中挑出真正）位置匿名服务器从候选结果集中挑出真正的结果返回给移动用户。的结果返回给移动用户。具有全局信息，具有全局信息，隐私保护效果好。隐私保护效果好。位置匿名服务器位置匿名服务器成为系统的瓶颈；成为系统的瓶颈；位置匿名服务器位置匿名服务器还可以成为隐私还可以成为隐私泄露的唯一攻击泄露的唯一攻击点。点。优 点缺 点中心服务器结构处理过程：（1）用户发送包含精分布式点对点结构分布式点对点结构ThemeGallery is a Design Digital Content&Contents mall developed by Guild Design Inc.优点：优点：拥有全局信息，隐私效果好；消除了系统拥有全局信息，隐私效果好；消除了系统瓶颈；消除了唯一攻击点。瓶颈；消除了唯一攻击点。缺点：缺点：网络通讯代价高。网络通讯代价高。处理过程处理过程：（：（1 1）移动客户端根移动客户端根据匿名算法建立一个匿名组，进据匿名算法建立一个匿名组，进行位置匿名。（行位置匿名。（2 2）根据实际的）根据实际的网络通讯情况选择一个合适的头网络通讯情况选择一个合适的头结点，头结点将匿名后的查询请结点，头结点将匿名后的查询请求发送给位置数据库服务器。求发送给位置数据库服务器。（3 3）位置数据库服务器根据匿）位置数据库服务器根据匿名区域进行查询处理，并将查询名区域进行查询处理，并将查询结果的候选集返回给头结点。结果的候选集返回给头结点。（4 4）头结点可以选择出真实结）头结点可以选择出真实结果发送给提出查询的用户，也可果发送给提出查询的用户，也可以将查询结果的候选集发送给用以将查询结果的候选集发送给用户，由用户自己挑选出真实的结户，由用户自己挑选出真实的结果。果。头结点平衡网络负载！头结点平衡网络负载！分布式点对点结构ThemeGallery is a Desi位置位置K-匿名模型（匿名模型（Location K-Anonymity Model）隐私保护模型隐私保护模型模型描述模型描述模型定义模型定义 把某一用户的真实位置点扩大为一个模糊的位置范围模糊的位置范围，使得该范围覆盖k个个用户的位置，此时无法将该用户与其他（k-1）个用户相区别，称此位置满足位置k-匿名。将任意用户的位置以一个三元组(x1,x2,y1,y2,t1,t2)表示，其中(x1,x2,y1,y2)描述了对象所在的二维空间区域，t1,t2表示一个时间段。(x1,x2,y1,y2,t1,t2)表示用户在这个时间段的某一个时间点出现在(x1,x2,y1,y2)所表示的二维空间中的某一点。除此用户外，还有其他至少（k-1）个用户也在此时间段内的某个时间出现在(x1,x2,y1,y2)的二维空间的某一点，这样的用户集合满足位置k-匿名。位置K-匿名模型（Location K-Anonymity 原原 始始 查查 询询匿名后查询匿名后查询K=3隐私保护需求的四个参数隐私保护需求的四个参数：k：即 k-匿名，用户要求返回的匿名集中至少包含的用户数。Amin：匿名空间的最小值，返回的匿名空间必须要超过此值，可以是面积或半径等。Amax：匿名空间的最大值，返回的匿名空间必须不能超过此值，也可以是面积或半径等。Tmax：可容忍的最长匿名延迟时间。即从用户提出请求的时刻起需要在Tmax的时间范围内完成用户的匿名。原 始 查 询匿名后查询K=3隐私保护需求的四个参数：隐私保护技术隐私保护技术假位置假位置假位置假位置空间匿名空间匿名空间匿名空间匿名时空匿名时空匿名时空匿名时空匿名DummySpatial CloakingSpatio-Temporal Cloaking隐私保护技术假位置空间匿名时空匿名DummySpatial 一、假位置一、假位置位置匿名位置匿名查询处理查询处理不公开真实服务请求的位置，而不公开真实服务请求的位置，而是公布假位置，即哑元是公布假位置，即哑元(Dummy)(Dummy)。用户发送多个不同的位置信息给用户发送多个不同的位置信息给服务器，而这些位置信息中只有服务器，而这些位置信息中只有一个是该用户的真实准确位置，一个是该用户的真实准确位置，其他的都是错误的或假的位置信其他的都是错误的或假的位置信息。这样即使恶意的攻击者获取息。这样即使恶意的攻击者获取了某个用户的位置信息，也不能了某个用户的位置信息，也不能推测出该用户的准确位置。推测出该用户的准确位置。基于假位置的匿名查询，基于假位置的匿名查询，位置数据库中的查询处位置数据库中的查询处理器无需作任何修改，理器无需作任何修改，因为发送给位置数据库因为发送给位置数据库服务器的仍是一些明确服务器的仍是一些明确的位置点，可以直接利的位置点，可以直接利用已有的数据库查询处用已有的数据库查询处理技术完成各种查询，理技术完成各种查询，。只是返回的结果不一定只是返回的结果不一定是真实结果，存在一定是真实结果，存在一定的误差。的误差。一、假位置位置匿名查询处理不公开真实服务请求的位置，而是公布二、空间匿名二、空间匿名降低对象的空间粒度，用一个空间区域来表示用户的真实精确位降低对象的空间粒度，用一个空间区域来表示用户的真实精确位置，区域的形状不限，普遍使用圆和矩形。同时结合置，区域的形状不限，普遍使用圆和矩形。同时结合 k-匿名的思匿名的思想来构造，即用户提供给服务器的位置区域不仅需要包含该用户想来构造，即用户提供给服务器的位置区域不仅需要包含该用户的准确位置，并且还需要包含其他的准确位置，并且还需要包含其他 k-1-1 个移动用户。这样用区域个移动用户。这样用区域表示位置之后，用户在此区域内每一个位置上出现的概率相同。表示位置之后，用户在此区域内每一个位置上出现的概率相同。攻击者仅能知道用户在这个空间区域内，却无法确定具体的位置。攻击者仅能知道用户在这个空间区域内，却无法确定具体的位置。二、空间匿名降低对象的空间粒度，用一个空间区域来表示用户的真三、时空匿名三、时空匿名时空匿名就是在空间匿名的基础上，增加一个时间轴。在扩大位置区域的同时，延迟响应时间，可以在这段时间中出现更多的用户、提出更多的查询，隐私匿名度更高。三、时空匿名时空匿名就是在空间匿名的基础上，增加一个时间轴。基于空间匿名与时空匿名的查询处理基于空间匿名与时空匿名的查询处理用户发送给位置服务器的不再是精确的位置点，而是一个匿名框。用户在框内的每一个位置出现的概率相同，查询处理器无法获知移动用户的确切位置。传统的查询方式不再适用。查询处理器查询处理器查询的类别查询的类别基于位置数据库服务器中的数据可以分为两种：公开数据和隐私数据。相应的，根据查询点和被查询点是否隐私，可以将查询分为四种。查查 询询 结结 果果一、在候选结果集中随机挑选一个对象作为结果返回给用户；二、返回整个候选集，用户或第三方可信件求精；三、以概率查询处理技术处理查询结果。基于空间匿名与时空匿名的查询处理用户发送给位置服务器的不再是查询类型被 查 询 点公开数据隐私数据查询点公开数据基于公开数据的公开查询基于公开数据的公开查询如：某电影院200米内所有的餐馆基于隐私数据的公开查询基于隐私数据的公开查询如：加油站500米内的所有出租车隐私数据基于公开数据的隐私查询基于公开数据的隐私查询如：距离我最近的加油站基于隐私数据的隐私查询基于隐私数据的隐私查询如：离我最近的朋友某加油站某加油站500米内的所有出租车米内的所有出租车将所有与查询范围相交的匿名区域都作为候选集。将匿名框与圆形框的重叠区域面积大小表示查询结果是真正结果的概率。查询结果查询结果：（：（B，50%）（）（C，90%）（）（D，1）（）（E，60%）示示 例例查询被 查 询 点公开数据隐私数据公开基于公开三种匿名技术的对比三种匿名技术的对比假位置假位置假位置假位置空间匿名空间匿名空间匿名空间匿名时空匿名时空匿名时空匿名时空匿名DummySpatial CloakingSpatio-Temporal Cloaking三种匿名技术的对比假位置空间匿名时空匿名DummySpati基于基于P2P的位置匿名算法实现的位置匿名算法实现 现有系统区域被划分成网格的形式，要求移动用户通过与其现有系统区域被划分成网格的形式，要求移动用户通过与其他用户的通信查找到他用户的通信查找到 k-1 个用户，将自己真实的位置点扩大为一个个用户，将自己真实的位置点扩大为一个模糊的匿名空间，使得该范围覆盖了模糊的匿名空间，使得该范围覆盖了 k 个用户的位置，同时还必须个用户的位置，同时还必须满足满足Amin。假定匿名空间是一个矩形，用一个左下。假定匿名空间是一个矩形，用一个左下-右上的二元右上的二元（xl,ybxr,yu）表示。如何实现这一过程呢？）表示。如何实现这一过程呢？基于P2P的位置匿名算法实现 现有系统区域被划算法一：算法一：Function P2P Anonymity-Requestor(k,d)1、初始化：令已找到用户的集合、初始化：令已找到用户的集合S=，已经找到用户的个数，已经找到用户的个数k=s=0，跳数的初始值，跳数的初始值h=1，d为用户的度，为用户的度，k为匿名度，为匿名度，hmax为最大跳数，为最大跳数，flag为为标志位。标志位。2、if(dk-1)then 以以单跳单跳形式广播查找请求，寻找形式广播查找请求，寻找k-1用户；用户；else hmax=最大跳数；最大跳数；flag=0；do 以以多跳多跳形式开始广播查找请求；形式开始广播查找请求；S 是经过多跳形式返回的已找到的用户集合，则是经过多跳形式返回的已找到的用户集合，则 k=s；度是指与该用户在一个通讯范围内用户的数目。度是指与该用户在一个通讯范围内用户的数目。单跳指由发站直接到收站的一次性传输；多跳指由发站到收站经过多次转发的方式。单跳指由发站直接到收站的一次性传输；多跳指由发站到收站经过多次转发的方式。移动用户移动用户 m m 如果想要获得服务，首先将已找到用户的如果想要获得服务，首先将已找到用户的集合集合SS置为空集，已找到用户的个数置为空集，已找到用户的个数kk赋为赋为 0 0。然。然后，用户后，用户 m m 通过比较隐私档案中通过比较隐私档案中k k 值和自身度值和自身度d d 的大的大小，选择相应的方式（单跳或多跳）向其周围的用户小，选择相应的方式（单跳或多跳）向其周围的用户发送一个消息序号发送一个消息序号 ID ID 来广播查找请求，用户来广播查找请求，用户 m m 监听监听网络，等待周围用户的响应。网络，等待周围用户的响应。基于基于P2P的位置匿名算法实现的位置匿名算法实现算法一：Function P2P Anonymity-Req算法算法二二:Function P2P Anonymity-Receiver(h)1、if（一个请求是重复的）then 通过一个 ACK 消息回应服务的请求者；return；2、if(h=1)then 发送一个元组(ID，xr,yr，vmax，tr，h)回应服务的请求者；else h=h-1；广播查找请求；S 是查找到的用户的集合；for SiS do Si.h=Si.h+1;S=S(ID，xr,yr，vmax，tr，h);返回S 到服务的请求者；（1 1）当请求的接收者）当请求的接收者 r r 接收到来自服接收到来自服务请求者务请求者m m（可能是请求的发起者，也可（可能是请求的发起者，也可能是请求的转发者）的查找请求后：首能是请求的转发者）的查找请求后：首先基于消息序号先基于消息序号 ID ID 请求的接收者请求的接收者 r r检检查该请求是否为一个重复的请求。若是，查该请求是否为一个重复的请求。若是，则返回一个则返回一个 ACK ACK 消息。否则，基于消息。否则，基于 h h 的大小处理请求。的大小处理请求。（2 2）当）当 h=1h=1（单跳单跳）时，时，r r 返回一个返回一个包含包含 IDID、当前位置、最大运动速度、时、当前位置、最大运动速度、时间戳和跳数的元组间戳和跳数的元组(ID(ID，xxr r,y,yr r，v vmaxmax，t tr r，h)h)给请求者；给请求者；（3 3）当）当 h1 h1（多跳多跳）时，）时，r r 递减递减 h h 的的值，再向周围用户发送原始的消息序号值，再向周围用户发送原始的消息序号 ID ID 来广播查找请求。来广播查找请求。r r 监听整个网络，监听整个网络，等待周围用户的响应，直到收集到所有等待周围用户的响应，直到收集到所有其周围用户的回复。最后，其周围用户的回复。最后，r r 分别递增分别递增收集到的元组中的收集到的元组中的 h h 值，同时将自己的值，同时将自己的元组信息一起添加到已收集的元组中构元组信息一起添加到已收集的元组中构成集合成集合 S S，返回给请求的发起者或转发，返回给请求的发起者或转发者者 r r。基于基于P2P的位置匿名算法实现的位置匿名算法实现算法二:Function P2P Anonymity-Re do 以以多跳多跳形式开始广播查找请求；形式开始广播查找请求；S 是经过多跳形式返回的已找到的用户集合，则是经过多跳形式返回的已找到的用户集合，则 k=s；if(flag=0)then 服务请求者服务请求者中心位置的调整中心位置的调整；flag=1；if(k k-1)then if(S=S|h=hmax)then 请求挂起；请求挂起；h=h+1；S =S；while(k=k-1)；当请求的发起者当请求的发起者 m 经过一次查经过一次查找请求后得到的用户数小于找请求后得到的用户数小于 k-1 时，时，它将继续递增它将继续递增 h的值，并且以一个的值，并且以一个新的消息序号新的消息序号 ID 重新广播请求，重新广播请求，重复此过程，直到找到重复此过程，直到找到 k-1 个用户。个用户。值得注意的是，如果在两次连值得注意的是，如果在两次连续的广播后得到的结果集相同，或续的广播后得到的结果集相同，或者，当跳数者，当跳数 h 的值超过规定的最大的值超过规定的最大跳数时，跳数时，m 则需要释放他的隐私档则需要释放他的隐私档案，选择一个更小的案，选择一个更小的 k 值，或是将值，或是将请求挂起一段时间，随即再次发出请求挂起一段时间，随即再次发出查找请求服务。查找请求服务。当用户只是通过单跳的形式就可以当用户只是通过单跳的形式就可以查找到满足匿名要求的用户数时，查找到满足匿名要求的用户数时，即即dk-1dk-1，这说明用户处于一个相，这说明用户处于一个相对密集的区域，用户的移动对其位对密集的区域，用户的移动对其位置匿名影响不大。但当用户采用多置匿名影响不大。但当用户采用多跳的形式查找用户时，即用户所处跳的形式查找用户时，即用户所处的区域相对稀疏时，必须考虑用户的区域相对稀疏时，必须考虑用户 位置的调整。位置的调整。基于基于P2P的位置匿名算法实现的位置匿名算法实现 do当请求的发起者 m 经过一次查找请求后得到3、for all Si Sdo 调整集合中每个用户的位置范围；4、形成一个包含这 k 个用户的最小匿名空间A；5、if(AAmin)then 扩大区域 A 到 Amin；算法结束！算法结束！如果所形成的匿名空间如果所形成的匿名空间 AAAAminmin，则扩大空间则扩大空间 A A 到到 A Aminmin。最后，服务的请求者最后，服务的请求者 m m 将将包含匿名空间包含匿名空间 A A 的查询发的查询发送到基于位置的社会性网络送到基于位置的社会性网络数据库服务器。经过处理之数据库服务器。经过处理之后，返回给用户一个查询结后，返回给用户一个查询结果的候选集，用户根据自己果的候选集，用户根据自己的精确位置对候选结果集求的精确位置对候选结果集求精。精。基于基于P2P的位置匿名算法实现的位置匿名算法实现3、for all Si Sdo如果所形成的匿名空间位置服务与隐私保护课件