本发明属于群智感知技术领域，涉及移动群智感知中用户轨迹的隐私保护，具体是一种移动群智感知中收集用户实时位置信息的差分隐私方法。
背景技术：
近年来，随着以智能手机、智能手表等为代表的移动智能终端的普及，相关产业呈现井喷式增长。不断发展的内置传感器提高了智能设备的感应能力，并且迅速增长的用户为移动群智感知(mcs)的发展奠定了基础。作为一种新的数据收集范例，mcs系统通常由服务器和大量参与者组成。具体而言，服务器首先将感知任务发布给移动智能设备用户，如果用户愿意参与感知任务，他会接受任务并提交数据来完成任务。然而，在数据收集的过程中，参与者的隐私信息往往会被攻击者获取，出于安全考虑，用户往往会退出感知任务，因此，在任务的发布、数据的收集以及上传过程中保护参与者的隐私极其重要。
由于大多数mcs任务与位置有关，因此服务器通常要求参与者报告其位置以及传感数据。但是，参与者位置的公开越来越多，这带来了隐私泄露的威胁。为了保护参与者的位置隐私，差分隐私由于其强大的隐私保护能力，它已经是在数据库环境中保护个人隐私的常用方法，为用户隐私的保护提供了很好的解决方案。差分隐私保护，不需要特殊的假设攻击、不关心攻击者所拥有的背景知识，甚至假设攻击者已知除一条记录之外的所有记录，仍然可以保护用户的敏感信息不会受到攻击，同时给出可证明性的量化分析。
目前，差分隐私技术通常用在服务器端对数据库的数据进行保护，但是，攻击者也可能从不可信的第三方或服务器获得用户的全部数据。
技术实现要素：
针对上述现有技术中描述的不足，本发明提供一种移动群智感知中收集用户实时位置信息的差分隐私方法，保护用户的实时位置。用户在本地端对其实时位置进行扰动并将扰动后的位置上传到服务器，在最大化用户上传数据所能够获得收益的前提下实现对其隐私的保护，同时，用户对其位置隐私保护的强度是由多个因素决定的。
为达到上述目的，本发明提供如下技术方案：
一种移动群智感知中收集用户实时位置信息的差分隐私方法，能够对用户的实时位置进行保护，包括以下步骤：
先对用户活动区域进行划分标号。
s1：计算用户当前位置点所在的滑动窗口内所剩余的隐私预算εr，判断用户当前的位置点是否为关键点并计算重要性i，然后计算用户轨迹的隐私泄漏量tplw-1；
s2：根据用户当前位置点的重要性i以及隐私泄露量tplw-1给用户当前位置点分配隐私预算εi；
s3：用户根据分配的隐私预算εi对当前位置点进行扰动获得候选位置点集a，并选择出用户对隐私泄露量和所获得的收益均满意的位置点作为扰动位置提交给服务器。
进一步，在步骤s1中，具体步骤为：
s11：计算用户当前位置点所在的滑动窗口内所剩余的隐私预算εr；
根据用户当前位置点所在的滑动窗口内前面w-1个位置点所消耗的隐私预算，计算当前位置点所剩余的隐私预算εr：
其中，εg为全局的隐私预算，εk为当前位置点前面第k个位置点所消耗的隐私预算；
s12：判断用户当前位置点是否为关键点，并计算当前位置点的重要性i；
假设前一位置点为li-1，当前位置点为li，后一位置点为li 1，且三个位置点连续；
获得向量
s13：根据用户当前位置点所在的滑动窗口，计算用户前w-1个扰动位置点所形成轨迹的隐私泄露量tplw-1；
其中，s(lk,lk')为真实位置lk与扰动位置lk′之间的相似度，参数σ为缩放函数；d⊥(lk,lk')为真实位置lk与扰动位置lk′之间的垂直距离；d||(lk,lk')为真实位置lk与扰动位置lk′之间的水平距离；de(lk,lk')为真实位置lk与扰动位置lk′之间的欧式距离。
进一步，在步骤s2中，所述隐私预算εi的计算公式为：
εi＝min(max(λεr,εmin),εmax)；
λ＝β1·i β2·tplw-1；
其中，εmin为保证扰动轨迹有效性的最小隐私预算，εmax为保证扰动轨迹有效性的最大隐私预算，λ为给用户当前位置点分配的隐私预算的比例，在确定λ时，β1为位置重要性所占的比例，β2为轨迹隐私泄漏量所占的比例。
进一步，在步骤s3中，具体步骤为：
s31：获得候选位置点集a以及候选位置点集a中各候选位置点被选中的概率；
s32：建立最优化模型，并将最优化模型划分为用户获得收益最大以及隐私泄漏量最小两个子问题，从候选集中选出既能够保证用户的隐私又能够使用户对其所能够获得的收益满意的扰动位置点。
进一步，在步骤s31中，具体步骤为：
s311：在用户整个活动区域内筛选出与当前位置点真实的曼哈顿距离dm小于设定距离值d的位置点，得到候选位置点集a；
曼哈顿距离dm的计算公式为：
dm(li,lj)＝|d||(li,lj)| |d⊥(li,lj)|；
其中，li为当前位置点，lj为整个活动区域内的真实位置点；
s312：根据所获得隐私预算εi，利用累积分布函数
进一步，在步骤s32中，具体步骤为：
s321：建立用户获得收益最大的子问题模型，即扰动轨迹有效性最大的子问题模型，子问题模型为：
其中，p(lk|lk-1)表示用户从位置点lk-1移动到位置点lk的概率，是该位置点被选中的概率；m(lk'|lk)为为差分隐私机制；dm(lk,lk')为用户真实位置lk与扰动位置lk'之间的曼哈顿距离；k表示位置点的下标。
s322：建立隐私泄露最少的子问题模型，子问题模型为：
s323：在求解的过程中固定一个子问题，求解另一个子问题，将求解的结果带入固定的子问题中，直至两个子问题得到的结果相同，则得到的结果就是扰动位置点。
本发明的有益效果在于：本发明是假设用户动态地不间断地提交位置信息到服务器。基于此假设，本发明使用了滑动窗口的概念，在整个滑动窗口内的隐私预算固定，根据扰动轨迹的隐私泄露量以及用户当前位置的重要性为用户当前位置分配适当的隐私预算，然后对用户的位置点进行扰动获得候选集并从中获得最优的扰动位置点。本发明可以有效的从本地来保护用户的实时位置隐私而不需要服务器来保护用户的隐私。
本发明的其他优点、目标和特征在某种程度上将在随后的说明书中进行阐述，并且在某种程度上，基于对下文的考察研究对本领域技术人员而言将是显而易见的，或者可以从本发明的实践中得到教导。本发明的目标和其他优点可以通过下面的说明书来实现和获得。
附图说明
为了使本发明的目的、技术方案和优点更加清楚，下面将结合附图对本发明作优选的详细描述，其中：
图1为在移动群智感知中收集用户实时位置信息的差分隐私方法的总体框架图。
图2为地理区域划分图。
图3为用户运动距离的测量。
图4为关键点和非关键点的示意。
图5为出租车分布的等高线图，其中图a1为通畅时间段原始gps数据，图a2为通畅时间段扰动gps数据，图b1为高峰时间段原始gps数据，图b2为高峰时间段扰动gps数据，图c1为平常时间段原始gps数据，图c2为平常时间段扰动gps数据。
图6为隐私预算与mae和mre之间的关系图，图6a为在不同的算法下从隐私预算0.5到5之间变化时的mae变化比较图；图6b为在不同的算法从隐私预算0.5到5之间变化时的mre变化比较图。
图7为滑动窗口与mae和mre之间的关系。
具体实施方式
以下通过特定的具体实例说明本发明的实施方式，本领域技术人员可由本说明书所揭露的内容轻易地了解本发明的其他优点与功效。本发明还可以通过另外不同的具体实施方式加以实施或应用，本说明书中的各项细节也可以基于不同观点与应用，在没有背离本发明的精神下进行各种修饰或改变。需要说明的是，以下实施例中所提供的图示仅以示意方式说明本发明的基本构想，在不冲突的情况下，以下实施例及实施例中的特征可以相互组合。
在具体说明本发明实施例之前，先解释本发明实施例所涉及的7个概念，具体如下：
(1)移动群智感知网络是指利用普通用户的移动设备作为基本感知单元，通过移动互联网进行有意识或无意识的协作，实现感知任务分发与感知数据收集，完成大规模的、复杂的社会感知活动。
(2)ε-差分隐私，对于两个相差最多为一条记录的数据集d1、d2，range(m)为随机算法m的取值范围。如果算法m在数据集d1和d2的任意输出结果为
(3)w-轨迹差分隐私，对于轨迹t的任意两个相差最多为一个位置点的两条包含w个位置点的子轨迹t1和t2，range(m)为随机算法m的取值范围。如果算法m在子轨迹t1和t2上的输出结果能够满足pr[m(t1)∈t]≤eε×pr[m(t2)∈t]，则称算法m满足w-轨迹差分隐私。
(4)地理区域模型，如图2所示，将地理区域离散化为m×n个方格并进行标号，用户任意时刻所处的位置用方格的号码ci或者是二维坐标(xi,yi)来进行表示。
(5)轨迹之间的距离，如图3所示，给定任意两个位置l1和l2，我们用α来表示两者之间的方位角，其取值范围为[0,2π)，那么l1和l2之间的水平距离和垂直距离分别为d||(l1,l2)＝de(l1,l2)cos(π/2-α)和d⊥(l1,l2)＝de(l1,l2)sin(π/2-α)，其中de(l1,l2)表示l1和l2之间的欧氏距离，那么l1和l2之间的曼哈顿距离可以表示为dm(l1,l2)＝|d||(l1,l2)| |d⊥(l1,l2)|。
(6)关键点与非关键点，如图4所示，对于任意三个连续的位置li，li 1和li 2，我们用β来表示向量
(7)轨迹隐私泄漏量，其计算方法如下：
其中，s(li,li')为表示两个位置之间的相关度的函数，在本文中，我们用高斯核函数
(8)用户获得的收益，为了量化第三方或服务器能够从用户提交的扰动轨迹所能够获得的收益，我们计算了用户提交的扰动轨迹与其真实轨迹之间的曼哈顿距离的期望值。
首先，对于给定的随机算法m，我们计算任意两个位置点之间的曼哈顿距离的期望，其计算方法如下：
其中，p(li|li-1)表示用户从li-1移动到li的概率。
接下来，我们计算两条轨迹之间的曼哈顿距离的期望值
本发明优选的一种实施例：如图1所示，一种移动群智感知中收集用户实时位置信息的差分隐私方法，用户在本地使用差分隐私机制对其实时位置进行扰动，在该过程中用户能够控制隐私保护的强度，与此同时，还能够保证用户所上传的数据的有效性。
本发明提供的差分隐私方法一共分为三部分，第一部分，计算用户当前位置所在的滑动窗口内所剩余的隐私预算，判断用户当前的位置点是否为关键点并计算其重要性，计算用户轨迹的隐私泄漏量；第二部分，根据用户当前位置的重要性以及隐私泄露量给用户当前位置分配隐私预算；第三部分，用户根据分配的隐私预算对当前位置进行扰动获得候选位置集，并选择出用户对隐私泄露量和所获得的收益均满意的位置点作为扰动位置提交给服务器，具体步骤如下：
s1：计算用户当前位置点所在的滑动窗口内所剩余的隐私预算εr，判断用户当前的位置点是否为关键点并计算重要性i，然后计算用户轨迹的隐私泄漏量tplw-1；
s11：计算用户当前位置点所在的滑动窗口内所剩余的隐私预算εr；
根据用户当前位置点所在的滑动窗口内前面w-1个位置点所消耗的隐私预算，计算当前位置点所剩余的隐私预算εr：
其中，εg为全局的隐私预算，εk为当前位置点前面第k个位置点所消耗的隐私预算。
s12：判断用户当前位置点是否为关键点，并计算当前位置点的重要性i；
假设前一位置点为li-1，当前位置点为li，后一位置点为li 1，且三个位置点连续；
获得向量
s13：根据用户当前位置点所在的滑动窗口，计算用户前w-1个扰动位置点所形成轨迹的隐私泄露量tplw-1；
其中，s(lk,lk')为真实位置lk与扰动位置lk′之间的相似度，参数σ为缩放函数；d⊥(lk,lk')为真实位置lk与扰动位置lk′之间的垂直距离；d||(lk,lk')为真实位置lk与扰动位置lk′之间的水平距离；de(lk,lk')为真实位置lk与扰动位置lk′之间的欧式距离。
s2：根据用户当前位置点的重要性i以及隐私泄露量tplw-1给用户当前位置点分配隐私预算εi；
εi＝min(max(λεr,εmin),εmax)；
λ＝β1·i β2·tplw-1；
其中，εmin为保证扰动轨迹有效性的最小隐私预算，εmax为保证扰动轨迹有效性的最大隐私预算，λ为给用户当前位置点分配的隐私预算的比例，在确定λ时，β1为位置重要性所占的比例，β2为轨迹隐私泄漏量所占的比例。
s3：用户根据分配的隐私预算εi对当前位置点进行扰动获得候选位置点集a，并选择出用户对隐私泄露量和所获得的收益均满意的位置点作为扰动位置提交给服务器。
s31：获得候选位置点集a以及候选位置点集a中各候选位置点被选中的概率；
s311：在用户整个活动区域内筛选出与当前位置点真实的曼哈顿距离dm小于10的位置点，得到候选位置点集a；
曼哈顿距离dm的计算公式为：
dm(li,lj)＝|d||(li,lj)| |d⊥(li,lj)|；
其中，li为当前位置点，lj为整个活动区域内的真实位置点。
s312：根据所获得隐私预算εi，利用累积分布函数
s32：建立最优化模型，并将最优化模型划分为用户获得收益最大以及隐私泄漏量最小两个子问题，从候选集中选出既能够保证用户的隐私又能够使用户对其所能够获得的收益满意的扰动位置点。
s321：建立用户获得收益最大的子问题模型，即扰动轨迹有效性最大的子问题模型，模型为：
其中，p(lk|lk-1)表示用户从位置点lk-1移动到位置点lk的概率，是该位置点被选中的概率；m(lk'|lk)为差分隐私机制；dm(lk,lk')为用户真实位置lk与扰动位置lk'之间的曼哈顿距离；k表示位置点的下标。
s322：建立隐私泄露最少的子问题模型，子问题模型为：
s323：在求解的过程中固定一个子问题，求解另一个子问题，将求解的结果带入固定的子问题中，直至两个子问题得到的结果相同，则得到的结果就是扰动位置点。
验证实施例：
在实验过程中，将整个有效数据集中的活动区域划分为80×60个单元格，每个单元格为边长为200米的正方形。在进行实验验证所提出的保护用户轨迹隐私的权利的有效性之前，首先从视觉效果上通过示例来展示所提出的发明的有效性。将一天中的时间分为三个时间段：
通畅时间段(00:00——7:00)；
高峰时间段(7:00——10:00&17:00——20:00)；
平常时间段(10:00——12:00&13:00——17:00)。
为了描述三个时间段内的交通流量，固定隐私预算ε的值为1并使用所提出的发明对用户的轨迹进行扰动，得到扰动后的gps数据后，绘制原始gps数据和扰动后的gps数据的等高线图，图5展示了该结果，其中图a1为通畅时间段原始gps数据、图b1为高峰时间段原始gps数据，图c1为平常时间段原始gps数据，图a2为通畅时间段扰动gps数据、图b2为高峰时间段扰动gps数据，图c2为平常时间段扰动gps数据，各个子图中颜色越深的地方表示该位置的交通流量越大。通过观察发现，原始的gps数据与扰动后的gps数据绘制的等高线图之间存在很大的差异，但是扰动后的gps数据所表示的街道信息与原始的gps数据所表示的街道信息是重合的。
为了评价该发明的性能，使用平均绝对误差(meanabsoluteerror，mae)和平均相对误差(meanrelativeerror，mre)这两个指标来评价发明的性能。假设t＝{l1,l2,...,ln}表示用户的真实轨迹序列，r＝{r2,r2,...,rn}表示用户提交给第三方或服务器的扰动轨迹序列。
mae和mre的计算方法如下，在公式中令分母为mae是为了减小一些过大或过小的数据对结果造成的偏差。
mae和mre的值取决于两个因素：隐私预算ε和发明中所定义的滑动窗口w的大小。接下来进行一系列的实验来验证发明的有效性。
首先研究隐私预算对用户收益的影响，设置滑动窗口w大小为5，轨迹长度为5。图6显示了不同的算法在隐私预算0.5到5之间变化时的用户收益的比较，其中rdctp为本发明的方法，图6a为在不同的算法下从隐私预算0.5到5之间变化时的mae变化比较图；图6b为在不同的算法从隐私预算0.5到5之间变化时的mre变化比较图。从图中可以看到，三种算法下的mae和mre都随着隐私预算的增加而减小，因为增加的噪音逐渐减少。此外，本发明的效果比gnoise和sdd要好，这是因为本发明所使用的方法可以自适应地分配隐私预算。
最后，研究了滑动窗口的大小对用户收益的影响，固定隐私预算的值为1，轨迹长度为15时，改变滑动窗口w的大小。图7显示了该发明的下的mae和mre的变化。
我们可以观察到，随着滑动窗口的增大，mae和mre都随w的增大而增加。这是因为分配给每个位置的隐私预算越来越小，这表明对位置的隐私保护增强。此外，mre略有增加，这是因为预算分配机制考虑了轨迹隐私泄漏和剩余预算，以将隐私预算自适应地分配给当前位置。因此，rdctp对滑动窗口w的变化具有鲁棒性。
通过模拟上海出租车收集的真实世界交通数据，证实了本发明相比已有的相关工作提供了更强的隐私保护级别，同时保留了轨迹的有效性和实用性。
最后说明的是，以上实施例仅用以说明本发明的技术方案而非限制，尽管参照较佳实施例对本发明进行了详细说明，本领域的普通技术人员应当理解，可以对本发明的技术方案进行修改或者等同替换，而不脱离本技术方案的宗旨和范围，其均应涵盖在本发明的权利要求范围当中。
1.一种移动群智感知中收集用户实时位置信息的差分隐私方法，其特征在于，能够对用户的实时位置进行保护，包括以下步骤：
s1：计算用户当前位置点所在的滑动窗口内所剩余的隐私预算εr，判断用户当前的位置点是否为关键点并计算重要性i，然后计算用户轨迹的隐私泄漏量tplw-1；
s2：根据用户当前位置点的重要性i以及隐私泄露量tplw-1给用户当前位置点分配隐私预算εi；
s3：用户根据分配的隐私预算εi对当前位置点进行扰动获得候选位置点集a，并选择出用户对隐私泄露量和所获得的收益均满意的位置点作为扰动位置提交给服务器。
2.根据权利要求1所述的移动群智感知中收集用户实时位置信息的差分隐私方法，其特征在于，在步骤s1中，具体步骤为：
s11：计算用户当前位置点所在的滑动窗口内所剩余的隐私预算εr；
根据用户当前位置点所在的滑动窗口内前面w-1个位置点所消耗的隐私预算，计算当前位置点所剩余的隐私预算εr：
其中，εg为全局的隐私预算，εk为当前位置点前面第k个位置点所消耗的隐私预算；
s12：判断用户当前位置点是否为关键点，并计算当前位置点的重要性i；
假设前一位置点为li-1，当前位置点为li，后一位置点为li 1，且三个位置点连续；
获得向量
s13：根据用户当前位置点所在的滑动窗口，计算用户前w-1个扰动位置点所形成轨迹的隐私泄露量tplw-1；
其中，s(lk,lk')为真实位置lk与扰动位置lk′之间的相似度，参数σ为缩放函数；d⊥(lk,lk')为真实位置lk与扰动位置lk′之间的垂直距离；d||(lk,lk')为真实位置lk与扰动位置lk′之间的水平距离；de(lk,lk')为真实位置lk与扰动位置lk′之间的欧式距离。
3.根据权利要求1所述的移动群智感知中收集用户实时位置信息的差分隐私方法，其特征在于，在步骤s2中，所述隐私预算εi的计算公式为：
εi＝min(max(λεr,εmin),εmax)；
λ＝β1·i β2·tplw-1；
其中，εmin为保证扰动轨迹有效性的最小隐私预算，εmax为保证扰动轨迹有效性的最大隐私预算，λ为给用户当前位置点分配的隐私预算的比例β1为位置重要性所占的比例，β2为轨迹隐私泄漏量所占的比例。
4.根据权利要求1所述的移动群智感知中收集用户实时位置信息的差分隐私方法，其特征在于，在步骤s3中，具体步骤为：
s31：获得候选位置点集a以及候选位置点集a中各候选位置点被选中的概率；
s32：建立最优化模型，并将最优化模型划分为用户获得收益最大以及隐私泄漏量最小两个子问题，从候选集中选出既能够保证用户的隐私又能够使用户对其所能够获得的收益满意的扰动位置点。
5.根据权利要求4所述的移动群智感知中收集用户实时位置信息的差分隐私方法，其特征在于，在步骤s31中，具体步骤为：
s311：在用户整个活动区域内筛选出与当前位置点真实的曼哈顿距离dm小于设定距离值d的位置点，得到候选位置点集a；
曼哈顿距离dm的计算公式为：
dm(li,lj)＝|d||(li,lj)| |d⊥(li,lj)|；
其中，li为当前位置点，lj为整个活动区域内的真实位置点；
s312：根据所获得隐私预算εi，利用累积分布函数cεi(dm(li,lj))获得候选位置点集a中各候选位置点被选中的概率。
6.根据权利要求4所述的移动群智感知中收集用户实时位置信息的差分隐私方法，其特征在于，在步骤s32中，具体步骤为：
s321：建立用户获得收益最大的子问题模型，即扰动轨迹有效性最大的子问题模型，子问题模型为：
其中，p(lk|lk-1)表示用户从位置点lk-1移动到位置点lk的概率，是该位置点被选中的概率；m(lk'|lk)为差分隐私机制；dm(lk,lk')为用户真实位置lk与扰动位置lk'之间的曼哈顿距离；k表示位置点的下标；
s322：建立隐私泄露最少的子问题模型，子问题模型为：
s323：在求解的过程中固定一个子问题，求解另一个子问题，将求解的结果带入固定的子问题中，直至两个子问题得到的结果相同，则得到的结果就是扰动位置点。
技术总结