移动群智感知下的位置隐私保护与任务分配方案*

刘 凯，韩益亮，郭凯阳，吴日铭

（1.武警工程大学密码工程学院，西安 710086；2.武警部队密码与信息安全保密重点实验室，西安 710086）

0 引言

移动群智感知（mobile crowd sensing，MCS）作为一种新兴的互联网感知范式，融合了众包思想与移动感知技术，已经成为了一种新型的信息服务模式和信息传播方式［1］。尤其是随着配备有传感设备的智能手机的普及，使得MCS 迅速走进大众的视野，大量具备感知能力的移动智能终端通过协同合作完成某一感知任务，为用户提供个性化服务［2］。与传统的传感器网络相比，MCS 不需要专门安装传感设备，不仅节省了大量的人力物力，而且利用移动用户的动态性与时效性进行任务感知更加契合大数据的时代特点［3］。目前，MCS 已经在交通、医疗、工业、社区服务等方面有了广泛应用［4-7］。近年来，基于信息系统的体系作战发展迅速，信息化条件下的新型作战力量不断涌现［8］，MCS 平台能够帮助信息作战系统提高指挥控制效率，充分发挥信息系统互联、互通、互操作的融合功能。

目前在MCS 方面的研究主要集中在激励机制、任务分发及位置隐私保护等方面，尤其是关于位置隐私的保护问题已经成为学者关注的重点。

文献［9］在移动群智感知的基础上提出了稀疏移动群智感知的概念，并利用本地化差分隐私机制保护用户的位置隐私，稀疏MCS 平台根据用户提交的数据推理未知区域的数据。文献［10］提出并评估了一种新的基于嵌入和聚类的时空模糊机制，并引出了概率k-匿名的概念。文献［11］提出了一种位置隐私保护的任务分配框架与地理模糊机制，以保护在任务分配过程中用户的位置隐私安全。文献［12］设计了一种与参与者密度无关的聚合统计方案来保护用户的位置隐私，首先利用多假名机制来克服低密度参与者带来的脆弱性问题，而后提出了基于Paillier 密码系统的方案来应对假名机制带来的女巫攻击问题，最后通过引入一个实体的身份服务器来解决用户的问责问题。

现有的方案注重在用户上传感知数据的过程中对用户的位置信息进行保护，但对平台下发的任务信息的保护，以及引入第三方服务器可能导致的隐私泄露问题考虑还不够全面。为了解决这些问题，设计了一种基于差分隐私与属性加密的位置隐私保护与任务分配方案，不仅可以在用户上传数据时对用户的位置信息进行保护，在MCS 平台下发任务时也能防止任务点的信息泄露。本文所做主要工作如下：1）考虑人流量密度对任务点选择的影响，减小用户在位置混淆后产生的距离误差，提高了混淆位置的可用性。2）结合位置转移概率矩阵与差分隐私的性质，保证生成的混淆位置具有相似的位置转移概率，在时间序列上满足差分隐私保护。3）引入第三方服务器进行概率转移矩阵的离线生成，提高了方案的运行效率。因为第三方服务器只负责位置信息的收集与矩阵的生成工作，不参与用户的位置信息上传与MCS 平台发布任务的过程，避免了第三方服务器不可信的问题。

1 预备知识

1.1 属性加密

属性加密分为密钥策略的属性加密（KP-ABE）和基于密文策略的属性加密（CP-ABE）。KP-ABE使用属性来描述加密的数据，并将策略构建到用户密钥中；而在CP-ABE 中，属性被用来描述用户的凭证，而加密数据的一方构建解密的策略［13］。基于密文策略的属性加密方案一般包括以下4 个算法：1）Setup 输入安全参数后生成公共密钥Pk 和主密钥Msk。2）KeyGen 输入公钥Pk、主密钥Msk、属性集合S，生成私钥Sk。3）Encrypt 将公钥Pk、消息M和属性域的访问结构A 作为输入，对M 进行加密，并生成密文CT。4）Decrypt 解密算法以Pk、密文CT、包含访问策略A 和私钥Sk 作为输入。如果属性集S 满足访问结构A，则算法将解密密文并返回消息M。

1.2 差分隐私

差分隐私模型的基本思想是在原始数据集或者在数据集传输的过程中添加噪声，来达到保护数据隐私属性的目的。差分隐私可大致分为以下两大类［14］：中心化差分隐私和本地化差分隐私。中心化差分隐私是将用户数据集中在一个可信的中心服务器上，通过中心服务器对用户的数据集进行加噪处理，使其满足差分的需求，所以数据集的安全性很大程度上依赖中心服务器的可靠性；本地化差分隐私是将数据处理的过程交由移动端完成，依靠用户个人对敏感信息进行保护。

假设算法A 是运行在服务器上的算法，在数据集D 和D'上的任意输出结果O 满足式（1），则说明算法A 满足ε-差分隐私：

2 基于差分隐私与属性加密的移动群智感知模型

2.1 场景预设

在城市反恐中，作战单元需要收集自己附近的环境信息，并将收集到的信息上传给前指中心。前指中心需要根据作战单元提供的战场信息合理地分配任务，确保作战指挥的科学高效。同时，根据作战任务需求，作战单元还要将自身信息共享给其他作战单元，保证信息共享，确保任务的高效完成。每个作战单元在执行感知任务前都需向前指中心提交个人信息，前指中心拥有所有作战单元的属性信息。

如图1 所示，各作战单元作为移动群智感知任务的参与者，负责收集环境信息，将信息上传给前指中心。前指中心作为MCS 的服务平台，负责将用户提交的信息进行整合处理，同时根据用户所处的位置信息，合理地进行任务分配，并将任务信息进行加密后传输给作战单元。第三方服务器根据收集的历史信息，生成位置混淆模块，用于隐藏用户的真实位置。

图1 群智感知模型图Fig.1 Mobile swarm perception model diagram

2.2 位置隐私保护与任务分配方案流程

本文针对MCS 平台中数据上传与任务下发时存在的隐私泄露问题，提出了一种基于差分隐私与属性加密的位置隐私保护方案。在生成位置混淆模块时，本文以一阶马尔可夫链生成的位置概率转移矩阵混淆用户位置，同时以作战单元移动距离最小为限制条件构造混淆函数。既确保混淆后的位置与作战单元的真实位置之间满足差分隐私的需求，又保证了任务分配的合理性。在任务信息的下发过程中，创新性地使用属性加密的方法，以用户的属性信息构建基于CP-ABE 的任务加密与解密算法，确保任务点信息在下发过程中的安全问题。所提方案主要包括以下4 个流程：

2.2.1 离线生成位置混淆模块

MCS 平台下发的任务一般是由系统内的其他用户发布的，所以人流量密集，人员活动频繁的地区，成为任务区域的概率也更高［15］。假设某区域内一天的活动轨迹点总数为m，单个网格内的活动轨迹点数为n，该网格内一天的人流量密度，该地区被选为任务点的概率与成正比。

在服务中心分配任务时，为了保证用户的移动距离最短，所以会优先考虑距离用户位置近的任务点，而在任务区域的选择上，距离用户上传位置信息较近的区域会以较高的概率被分配给用户。那么将划分后的网格中心O 作为任务点，任务点与任务参与者之间的距离为r，设为区域l 被选为任务点的概率，则与距离函数成反比。

假设用户当前时刻所处的位置为l，经过位置混淆函数处理后，将用户的位置映射到l1，如果存在区域l'与l 具有相似的概率被映射到l1，即满足式（2），则称其满足隐私保护强度为ε 的差分隐私。其中表示从用户的真实位置区域l 混淆到l1的概率，表示区域l'混淆到l1的概率。

经过位置混淆模块混淆后的位置并不是用户的真实位置，如图2 所示，MCS 服务平台是用户上传的位置为依据，将距离用户最近的任务点分配给移动用户。因此，为了减小用户移动距离对任务分配的影响，在构建位置混淆函数时，需要考虑位置混淆后带来的距离误差。因为用户事先并不知道任务点的位置，所以对用户来说，区域L 内的所有位置都有可能成为任务点，设l*为服务器给用户分配的任务地点，为用户的真实位置与任务点的距离，为混淆后的位置与任务点之间的距离。则混淆位置后引起的误差距离为：

图2 任务分配示意图Fig.2 Schematic diagram of task allocation

2.2.2 移动端的位置混淆

用户在移动端下载位置混淆模块，用户需输入自身的位置信息，并选择适当的隐私保护强度ε，通过位置混淆函数将自己的真实位置映射到一个虚假的位置，而后上传给MCS 服务中心。因为第三方服务器只负责生成位置混淆模块，并且位置混淆的过程在移动端完成，所以真实的位置信息只有参与者自身知道，避免了由于第三方服务器不可信而产生的隐私泄露问题。

2.2.3 前指服务器进行任务分配与加密处理

MCS 服务器接收到用户提交的位置信息后，按照距离最近的原则给用户分配任务。在确定用户的任务点后，为了保护任务点的隐私安全，利用属性加密的方法对分配的任务位置进行加密，并将其传输给移动用户。

采用分层级的树形结构实现任务信息的加密，可有效抵抗合谋攻击。服务器需要首先确定访问树T 的结构，每个子节点和阈值描述的阈门由非叶子节点表示［16］，若numx为节点x 的子节点数且节点阈值为kx，kx的取值范围为（0，numx］。设Tx为根节点为x 的子树，如果用户的一组属性集合Sx满足访问树Tx，则表示为Tx（Sx）=1。

1）选取一个素数阶P 的双线性群G，并选取发生器g，则双线性映射为：

2）密钥生成算法以一组属性集合S 作为输入，生成由属性集合标识的密钥Sk，属性集合S 为用户的属性子集。随机选择，任取，计算Dy和Dj，则密钥生成为：

3）使用密钥对任务点的位置信息进行加密，服务器通过访问树结构指定私钥必须满足的策略。加密时首先为访问树的每个节点x 选择一个多项式qx，且多项式的次数m 与节点的阈值k 之间应满足mx=kx-1。在算法开始时，选择一个随机数，且从根节点R 开始，有，而后选择多项式的其他点来进行完整定义。

假设Y 是T 的叶子节点集合，则对于叶子节点y∊Y 有：

因此，密文的组成结构为

2.2.4 客户端解密任务点

用户端接收到服务器发来的加密信息后，将自己的属性信息输入得到私钥进行解密，如果用户的属性符合访问结构，那么用户就可以解密密文得到任务点的具体信息，如果用户的属性不符合访问结构，用户就无法解密得到任务点的位置，任务点的隐私信息就得到了保护。具体的解密过程如下：

如果S 满足访问树的整体或者部分结构，那：

客户端根据自身属性信息解密后得到任务点的信息，即可前往任务点完成平台发布的任务。

3 实验仿真

本文采用Geolife 数据集进行仿真实验，该GPS轨迹数据集收集了182 名用户从2007 年4 月至2012 年8 月的活动路线，记录了用户广泛的户外活动，如购物、观光、徒步旅行等，一共包含17 621 条轨迹信息，这些轨迹都按时间序列进行存储。

实验环境如下：Intel i7-7700K 3.6 GHz，8 GB 内存，Microsoft Windows 10 操作系统，模型算法均在Pycharm2019 下实现。

Geolife 数据集中的用户活动范围以时间进行分类，选取用户在2008 年11 月21 日至11 月24日内活动的轨迹点，将用户每天的活动轨迹划分为一组数据，共生成4 组数据集。下页图3 是使用ARCMAP 软件生成的用户历史移动轨迹路线。将用户所在区域划分为边长为1 km 的正方形网格，并进行标号，统计用户在各个网格内的活动轨迹点，即可计算出各网格内人员流动密度。图4 与图5 分别为不同时间内同一地区的人员流动数量与统计的人员流动密度图，可以看出，即使在相同的地区，不同时间内的人流量与人员流动密度差别也较大。

图3 用户历史轨迹图Fig.3 User’s history track diagram

图4 人员流动数量图Fig.4 The personnel flow quantity diagram

图5 各网格区域内人员流动密度Fig.5 Human flow density in each grid area

3.1 任务选取方式

本文与文献［9］中基于Spare MCS 概念生成混淆函数的算法进行对比，二者都采用了差分隐私的技术来实现用户位置信息的混淆，但在混淆区域的选择上，该算法考虑到人流密度以及用户移动距离对任务点选取的影响，而稀疏MCS 算法则赋予各网格相同的概率来确定任务区域。

从图6 可以看出，在不同的数据集中，用户与任务点之间的距离虽然有所浮动，但总体变化趋势相同。随着f（r）中k的增大，考虑人流量密度影响下的距离也随之接近SpareMCS 算法下的距离，并且当k取值大于4 后，前者的距离小于后者，变化速率也随之减小。

图6 用户位置与任务点之间的距离Fig.6 Distance between user’s location and task point

3.2 误差分析

设置差分隐私保护中的拉普拉斯（Laplace）机制作为对照组，对比了不同隐私强度下，混淆位置与任务点之间的距离，以及混淆位置与真实位置之间的距离，下页图7、图8 分别比较了混淆位置与真实位置以及混淆位置与任务点之间的距离，从实验结果可以看出，在不同的数据集上，本文算法生成的混淆位置在空间距离方面都更加接近用户的真实位置和任务区域，表明与Laplace 机制相比，本文算法不仅能够保护用户的位置隐私信息，同时也能够降低混淆用户位置后带来的误差距离，提高了方案的可用性。

图7 混淆位置与任务点的距离Fig.7 The distance between the confusion location and the task point

图8 混淆位置与真实位置之间的距离Fig.8 The distance between the confusion location and the real location

3.3 运行时间开销

实验对比了本文方案、Laplace 机制以及无隐私保护（NP）情况下任务分配的时间开销，从实验结果可以看出，随着轨迹点数量的增加，3 种方案的运行时间都呈上升趋势。图9 为在线生成概率转移矩阵时，各方案的运行时间对比，因为本文方案需要统计用户的历史运动信息，所以需要的时间开销更大，整体运行时间最长，其次是Laplace 机制下的位置混淆方法，二者都满足差分隐私的要求，比NP 情况下的任务分配所需时间更长。本文方案中生成概率转移矩阵的过程可以在第三方服务器上离线完成，如图10 所示，在任务分配之前进行信息收集与矩阵生成，那么任务分配所需的时间开销就可以大大减小，任务分配的时间就与Laplace 机制下的时间接近。

图9 在线生成概率转移矩阵Fig.9 On-line generation of probabilistic transition matrix

图10 离线生成概率转移矩阵Fig.10 Off-line generation of probability transition matrix

4 结论

随着移动通讯技术的迅速发展，移动群智感知这种新颖的互联网感知也逐渐走进大众的视野，成为一种新型的信息传播与交互模式。在参与感知任务过程中，感知用户的个人身份、位置访问模式等诸多隐私信息面临着泄露的风险。本文针对移动感知任务中感知用户的位置信息和任务信息的安全问题，提出了一种基于差分隐私与属性加密的隐私保护方案，利用差分隐私技术对感知用户上传的位置信息进行混淆，在MCS 平台下发任务信息时进行属性加密，只有满足条件的用户才能对任务信息解密。同时引入第三方服务器负责位置混淆模块的生成，既提高了方案的整体效率，也不会因为第三方服务器的可信性问题产生隐私泄露的风险。实验结果证明，本文方案在隐私保护强度与控制误差方面有较大优势，同时运行效率也比较高。