k-DLCA:基于位置服务的位置隐私保护的有效方法
1，Dan Liao 2,Xunhui,Huang
摘要：基于位置的服务（LBS）是移动社交网络的基础和核心功能之一。由于用户在使用服务时通常不得不向LBS服务提供商报告自己的位置，因此保护用户的位置隐私是一个关键的挑战。尽管许多现有的方法可以有效地保护用户的位置隐私，但大多数方法必须包含和使用用户的真实位置。在本文中，我们首先提出一种有效的基于k-匿名的虚拟位置和分割圆形区域（k-DLCA）方法来保护用户的位置隐私。与现有的研究不同，k-DLCA算法采用贪心策略选择虚拟位置，并考虑位置的语义位置信息。此外，用户的真实位置可能不包含在所选的虚拟位置中。然后我们展示了k-DLCA算法能够抵抗来自对手的攻击，并且很低的可能性暴露用户的真实位置。我们进行了广泛的模拟，以评估方案的效率。仿真结果表明，该方案具有良好的应用前景。
关键字：隐私保护；位置隐私；基于位置的服务；k匿名算法。
1.介绍
由于移动通信技术和移动设备的高速发展，LBS在移动网络中变得越来越普遍。当一个用户需要LBS，这个用户向他们的LBS提供者发送一个查询或请求，其中可能包括身份、位置、兴趣点(POI)和用户感兴趣的区域(ROI)。然而，一个不受信任的LBS服务提供商拥有所有用户信息可以使用这些信息来跟踪用户或显示他们的个人数据给第三方，用于商业或其他的的利益。因此，如何在使用LBS时保护用户的位置隐私是一个必须解决的重要问题。
几种保护用户位置隐私的方法已经被提出。他们中的大多数都是基于第一次提出的k匿名的隐身技术。k-匿名隐身技术使用一个可信的第三方从用户的邻居中选择其他k-1个LBS查询，并将除了用户自己的查询以外所有的查询发送给LBS服务提供商，而不是只发送用户的请求。然而，对第三方的严重依赖导致了单点故障，并造成了严重的性能瓶颈。为了在没有第三方的情况下保护用户的位置隐私，提出了虚拟定位技术。现有的方法可以有效地生成无法被LBS提供者区分的虚拟位置。然而，这些方法都没有考虑到语义位置信息(例如，用户在特定位置类型上发送LBS查询的可能性)。如果选择的虚拟位置是用户发送带有小概率查询的位置，那么这些位置很容易被攻击者过滤掉。虽然使用虚拟位置可以保护用户的位置隐私，但用户的真实位置必须是虚拟的位置之一。为了防止用户的真实位置丢失，15个作者提出了一种几何方法，称为n隐藏磁盘（n-CD），以保护用户的位置隐私。这种方法首先将每个用户的ROI划分为n个相等的扇区，然后在用户的ROI中随机地生成n个位置。最后，它生成了n个隐藏的磁盘，以完全覆盖用户的真正的ROI，并向LBS服务器发送n个位置和n个磁盘。通过这样做，从LBS提供程序获得的查询结果必须包括用户的真实POI。尽管这样的查询不包含用户的真实位置，但攻击者仍然能够推断出用户的真实位置必须在一个特定的重叠区域内。
在本文中，我们提出了一种有效的基于k-匿名的虚拟位置和分割圆形区域(k-dlca)方法来保护用户的位置隐私。与现有的算法不同，为了有效地保护用户的位置隐私，k-DLCA算法以贪婪的方式，考虑了可能被攻击者利用的语义位置信息，以贪婪的方式选择了基于熵的虚拟位置。另外，k-dlca算法可能不需要用户的真实位置将被包含在所选的虚拟位置中，这样就可以降低攻击者成功猜测用户真实位置的平均概率。此外，k-DLCA算法可以在较大的匿名区域隐藏用户的真实位置。
本文的其余部分按如下方式组织。第二部分给出了问题描述。第III部分描述了所提议的k-DLCA算法。第四章对k-DLCA算法进行分析。第五节提供模拟结果，第VI部分结束论文。
2.问题描述
2.1系统模型
考虑了一个由许多移动用户组成的LBS系统。对用户的初始LBS查询可以表示为q=(uid,{(x,y),R,P},其中uid和(x,y)分别是用户的身份和位置坐标；R是用户的ROI半径，P是用户的POI，例如一个餐厅，一家加油站等。为了保护用户的位置隐私,在提交一个请求到基于位置的服务提供者之前,用户第一次使用一个虚拟位置生成算法生成k虚拟位置（从(x1,y1)到(xk,yk)），k的值将取决于用户的隐私需求。如果用户想要在某些敏感的地方保护他们的POI，例如，医院，该算法还可以生成一些其他虚拟的POIs。原始的查询q被转换成一个新的查询q*=（uid,{(x1,y1)到(xk,yk)},R1,{p1,hellip;,ph}）,其中R1可能不同于R，集合{p1,hellip;,ph}是一个包括p的假的POI集合，最后，查询q*被发送到LBS服务器。在接收到查询*q时，LBS提供商将在所有虚拟位置的ROI中搜索所有POIs，并将它们返回给用户
2.2基本概念
在本文中，语义位置信息指的是用户在特定位置类型上发送LBS查询的概率。用户为每个位置类型分配一个语义参数。语义参数越大，在该位置类型上发送LBS查询的可能性就越高。在本文中，由于LBS提供商知道其服务区域中的位置，服务器负责根据位置属性对所有位置进行分类，比如道路、商店、住宅等。
在这项工作中，我们采用熵来测量隐私的程度，这可以被看作是识别用户真实位置的不确定因素。因此，我们需要对每个虚拟位置有一个当前的查询概率，这样我们就可以计算用户的熵。我们使用qi(1lt;ilt;k)去表示位置i的当前查找概率，可以通过关于i的语义位置的位置信息和历史查询概率得到。类似于[13], 历史查询概率相关的位置我可以定义在方程(1)。
qi=在位置i处的所以用户查询数目/在所有位置的用户数目查询 (1)
当前的查询概率qi*可以按如下方式计算。如果与位置i相关的历史查询概率是qi以及位置的语义参数i是bi，那么在位置i的当前查询概率是qi和bi的乘积即qi*=qi*bi. 在虚拟的位置设置中，每个虚拟位置的标准化概率用pi表示。每个用户的熵H被定义为:
H=-,pi=pi*/.(2)
当所有k个虚拟位置都有相同的概率时，可以达到最大熵值。是log2k。
3.算法设计
在本节中，我们首先介绍k-DLCA算法的攻击模型，然后给出k-DLCA算法的详细描述。
3.1攻击模型
虚拟位置生成算法可用于有效地生成虚拟位置，以保护用户在LBS中的位置隐私。LBS服务器能够获得与所有位置相关的历史查询概率，并监控从用户发出的当前查询。此外，LBS服务器还可以获取特定用户的历史信息，以及用户当前的情况和信息。另外，LBS服务器知道位置隐私保护机制是如何工作的，服务器负责传播和更新历史查询的概率，这样用户就可以从一个众所周知的地方获取这些信息（例如，LBS应用的本地数据库）。对手的目标是根据用户的位置信息确定用户的真实位置。由于对手可能会破坏LBS服务器并获取服务器所知道和持有的所有信息，我们假定LBS服务器是这项工作的对手。
3.2算法描述
k-DLCA算法的主要思想是通过考虑语义位置信息和可能被对手利用的历史查询概率来生成一组虚拟位置，以便所有虚拟位置都具有相似的当前查询概率。考虑到匿名程度k，k-DLCA算法以贪婪的方式连续选择k个虚拟位置，这样当前的熵值最大。例如，如果k匿名算法已经选择了第一个i位置（ilt;k）,当k匿名算法选择第i 1个位置时，必须保证Hi 1的值是最大的在所以存在的位置中，Hi 1是被定义在方程3：
Hi 1= (3)
P表示用户在位置j的当前查询概率，由于所选的虚拟位置可能不包括用户在此工作中的真实位置，k-DLCA算法采用不同的策略来选择虚拟位置。如果所选的虚拟位置包括用户的真实位置，k-DLCA算法会根据熵直接选择虚拟位置。如果选择的虚拟位置不包含用户的真实位置，k-DLCA算法将用户的ROI划分为n个相等的扇区，其中n小于 k。划分用户ROI的主要想法是，k-DLCA算法采用其他ROIs来完全覆盖用户的ROI，这样即使所选的虚拟位置不包含用户的真实位置，用户仍然可以从搜索结果中获得他/她感兴趣的内容。在本文中，根据用户的隐私要求，设置了k和n的值。如果nlt;k，k-DLCA算法需要根据熵选择其他k-n虚拟位置。最后，如果用户想要保护自己的真实POI，k-DLCA算法必须根据所选的虚拟位置为用户生成其他合适的虚拟POIs。关于k-DLCA算法的详细描述如下。
算法1：k匿名算法
输入：q=(uid,{(x,y),R,P}),历史查询概率集合p*，每个位置类型的语义参数;
输出：新查询q*.
1:计算基于语义参数的当前查询概率集Q和p*；
2:基于位置类型对集合Q中的元素进行分类；
3: if (strategy = =1) then
4: 调用步骤1
5: else
6:调用步骤2
7: end if
8:if一个用户需要保护隐私 then
9:选择l/2上下取余-1个虚拟的pols基于k虚拟位置
10：return q*=(uid,{(x1,y1),..,(xk,yk)},R,{P1,..,Pl/2向下取余})
11：end if
12:return q*=(uid,{(x1,y1),..,(xk,yk)},R,P)
步骤1:虚拟位置的生成，包括用户的真实位置
输入：用户位置（x,y）, 每个位置类型的语义参数、每个位置类型的当前查询概率集;
输出:k的虚拟位置{(x1,y1),..,(xk,yk)}.
1: 选择其他l-1位置类型，基于语义参数与用户实际位置的最小差异;
2: 遍历每一个被选择的位置类型（for循环）
3：根据当前查询概率与用户的真实位置的最小差异，以贪婪的方式选择k-l候选位置;
4：End for
5：选择其他k-1位置，基于选定的候选位置的熵，并确保位置类型的数量不小于l/2向下取余
6:return{(x1,y1),..,(xk,yk)}.
步骤2:排除用户真实位置的虚拟位置的生成
输入:用户位置(x,y), 位置类型的语义参数，每个位置类型的当前查询概率
输出：k个虚拟位置和新的半径。
1: 将用户的ROI划分成n个扇形区域
2: 从用户的ROI中随机选择一个位置，这属于第一个扇区;从其他n-1个区域中以贪婪的方式选择其他n-1个位置;根据当前查询概率与用户的真实位置的最小差异，以贪婪的方式选择k-l候选位置;
3:生成n个循环区域，以完全覆盖每个用户的ROI;将R作为n个圆形区域的最大半径;
4：if(nlt;k) then
5:l*表示n个位置的位置类型
6:if(l*lt;l)then
7:选择除了l和l*以外的其他位置类型，其语义参数与第一个l*位置类型的差异最小。
8:end if
9:for每一个被选的l位置类型
10：选择k-n候选位置，其当前查询概率与用户的实际位置差异最小;
11：end for
12: 在选定的候选位置以贪婪的方式选择其他k-1位置，并确保其位置类型的数量不低于l/2;
13:end if
14:return{(x1,y1),..,(xk,yk)}，R
4.算法分析
在本节中，我们首先展示了我们的方案是如何抵制串通攻击和推理攻击的。然后我们分析我们的方案是如何降低被攻击者识别用户的真实位置的可能性。
4.1抵抗共谋攻击
为了获得用户的位置隐私，被动攻击者可能与其他用户或与LBS提供商合作，以达到不同目的。
定义1:如果在用户的位置信息中成功猜测用户的真实位置的概率不会随着串通组的规模的增长而增加，那么这个方案就可以抵御串通攻击。
定理1:k-DLCA算法可以抵抗合谋攻击。
证据：在一组用户之间发生了合谋攻击。我们的方案通过选择其他虚拟位置来保护用户的位置隐私。当攻击者首先破坏用户的UA时，攻击者将获得用户的位置信息，包括k个位置。由于k个位置有类似的“查询”查询概率，所以攻击者不知道用户的真实位置，只能猜测用户的真实位置，而不是被截获的k个位置。由于k位置
全文共8490字，剩余内容已隐藏，支付完成后下载完整资料
英语原文共 6 页，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[15399]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
