王 辉, 毕成玉, 申自浩, 刘沛骞

(1. 河南理工大学 软件学院, 河南 焦作 454000;2. 河南理工大学 计算机科学与技术学院, 河南 焦作 454000)

随着无线传感网络和定位技术的发展, 移动群智感知(mobile crowd sensing, MCS)[1]已成为一种新兴的分布式智能感知范式. MCS不需要预先部署静态传感网络, 工人手持配备传感器的智能设备即可快速、 高效地收集感知数据, 目前已广泛应用于环境监测、 气象预测和社交推荐等领域[2-3].

近年来关于MCS的研究已有很多结果. 在任务分配阶段, Akter等[4]提出了一种禁忌搜索TST(tabu search algorithm for task allocation)任务分配算法减少工人的移动距离, 但该算法需要工人提交真实位置数据, 存在隐私泄露风险. 随着基于位置服务中位置隐私保护研究[5]的发展, 研究者们开始关注MCS中的位置隐私保护[6]. 为保护任务分配过程中工人的位置隐私, Song等[7]基于差分隐私(differential privacy, DP)[8]将工人位置的坐标转换为极坐标, 并对极坐标的位置记录执行差分隐私转换以保护工人的位置隐私, 但同时也影响了任务分配结果的准确性, 导致任务完成率较低. 在数据上传阶段, 工人上传到第三方平台的感知数据中不可避免地包含自身真实位置数据. 为保护工人在数据上传阶段的位置隐私, 李卓等[9]基于本地差分隐私(local differential privacy, LDP)[10]设计了用户提交数据属性联合隐私保护的CS-MVP算法, 将个体位置数据随机化, 扰乱了数据整体分布以保护位置隐私, 但当敌手有足够的先验知识时就会减弱隐私保护效果. 也有使用L-多样性、K-匿名[11]等泛化方法对位置数据进行模糊处理, 使第三方无法恢复数据, 从而无法区分个体以达到位置隐私保护的目的, 但同时导致较高的服务质量损失. 考虑到传统可信第三方平台遭受恶意攻击的隐私泄露风险, 利用区块链[12]的匿名性和不可篡改性, Yang等[13]提出了一个基于区块链的分布式群智感知系统模型, 解决了依赖可信第三方的问题, 但区块链的透明机制不利于工人的位置隐私, 无法抵挡来自工人间的协作攻击和先验知识攻击.

针对上述问题, 本文设计一个结合区块链和边缘计算的移动群智感知(blockchain and edge computing-mobile crowdsensing, BE-MCS)系统模型, 避免使用第三方平台, 并针对工人需上传自身真实位置数据的两个阶段设计不同的算法. 结果表明, 该模型在保护工人位置隐私的同时取得了较高的任务完成率和较低的服务质量损失.

1 系统模型

图1为结合了区块链和边缘计算的BE-MCS系统模型. 该模型边缘节点被视为是半可信的, 其中包含4个角色:

图1 BE-MCS系统模型Fig.1 BE-MCS system model

1) 任务请求者. 任务请求者在区块链中通过P2P通信将任务信息发送给边缘节点, 等待其回传感知数据;

2) 边缘节点. 边缘节点是分布在感知区域中的边缘设备, 是区块链的链上节点, 收到任务请求者发送的任务后通过区块链的广播机制向感知区域内的工人发送任务信息, 协作完成任务分配并收集和汇总工人上传的感知数据, 处理后发送给任务请求者;

3) 工人. 工人向边缘节点提交自身关于位置的信息获取感知任务, 执行感知任务后将感知数据上传到边缘节点;

4) 区块链. 区块链取代第三方平台, 利用智能合约作为感知过程提供通信和存储等功能, 通过合法性验证将交易信息记录在分布式账本中.

2 两阶段位置隐私保护方法

2.1 隐私保护任务分配

考虑工人移动速度差异对任务完成率的影响, 使用工人到任务的行程时间作为衡量指标. 任务分配流程简述如下:

1) 任务请求者将发布一系列任务T={t1,t2,…,tm},T中的每个任务ti通过Paillier密码机制[14]分配一对公私密钥对(pki,ski), 即公钥pki和私钥ski, 然后在区块链中通过P2P通信将任务ti的公钥分发送任务所在区域中的边缘节点EN, 而将私钥发送给最接近EN的边缘节点EN′;

2) 边缘节点收到任务信息后, 将向其感知区域内的所有工人发布任务ti的公钥pki;

3) 工人用任务的公钥pki解密任务信息, 根据自身位置和移动速度计算他们到达任务ti的行程时间, 并使用公钥pki加密行程时间, 然后将加密的行程时间上传到任务ti所在的边缘节点EN;

4) 边缘节点EN接收到加密行程时间后, 与拥有任务ti私钥ski的边缘节点EN′协同,EN将通过密文差值计算选出行程时间最短的几位工人, 将任务分配给他们.

下面给出边缘节点之间如何协作计算工人的密文行程时间差.首先基于同态加密利用Paillier加密算法的加法同态性, 设计一种密文差值计算实现工人之间加密时间的比较.假设加密函数是E(x), 解密函数是D(x),c1和c2分别是明文p1,p2的密文, 则根据加法同态, 对于明文p1,p2, 有

D(c1×c2)=D(E(p1)×E(p2)) modn2=(p1+p2) modn.

(1)

D(c1⊖c2)=D(E(p1)×E(p2)-1) modn2=(p1-p2) modn,

(2)

式(2)可通过计算密文差值计算实际明文的差值, 而无需解密明文.

对于明文p1,p2, 由E(p,r)=gp·rnmodn2可得

(3)

则密文下的行程时间差为

最后c1⊖c2用私钥解密, 得到明文下的差值为

D(c1⊖c2)=D(E(p1,r1)×E(p2,r2)-1)=p1-p2.

(5)

(6)

算法1CTWS算法.

输出: 选择出的工人集Wi;

步骤1)Wi←Ø;

步骤2) ifk>0 then

步骤3)k←n;

步骤4) end if

步骤5) whilep=1 tokdo

步骤6)wmin←null

步骤7) forq=pton-1 do

步骤10) else

步骤12) end if

步骤13) end for

步骤14)Wi←Wi∪wmin;

步骤16) end while

步骤17) returnWi.

2.2 隐私保护数据上传

在数据上传阶段, 由于感知数据中不可避免地包含真实位置数据, 因此本文通过采用双扰动的差分隐私算法(two disturbance local differential privacy, TDLDP)对感知数据中的位置数据进行扰动以保护工人的位置隐私. 即使敌手获取了工人的隐私信息, 这些数据也是不真实的.

定义1(ε-LDP) 给定n个用户, 每个用户对应一条记录, 给定一个隐私保护算法M及其定义域Dom(M)和值域Ran(M), 如果算法M在任意两条记录t和t′(t,t′∈Dom(M))上得到相同的输出结果t*(t*∈Ran(M)), 且满足

Pr[M(t)=t*]≤eε×Pr[M(t′)=t*],

(7)

则称M满足ε-LDP.

由定义1可见, LDP通过控制任意两条记录输出结果的相似度确保算法M满足ε-LDP. 隐私预算参数ε表示隐私的保护程度,ε越小, 隐私保护程度越高.即根据隐私算法M的某个输出结果, 敌手很难推断出输入数据是哪条记录.对于LDP, 每个用户都可以自己处理数据, 即隐私数据的处理过程从第三方转移到每个用户.因此, 无需考虑第三方的可信度.

性质2给定一个数据集C, 将其划分为n个不相交的子集,C={C1,C2,…,Cn}, 设M为满足ε-LDP的任意隐私预算, 则算法M满足C={C1,C2,…,Cn}上的ε-LDP.

虽然LDP机制在一定程度上限制了敌手窃取工人的位置数据, 但工人仍无法确定他们的位置数据是否已经被泄露. 因此, 通过在LDP机制中添加干扰因子ω, 可进一步保护工人的位置数据. LDP的隐私保护原理就是使敌手很难分辨出工人的真实位置, 但如果敌手有足够的先验知识推测工人的位置数据, 则LDP保护机制效果就会减弱, 但添加扰动因子ω使敌手始终无法正确预估工人的位置数据, 从而保护工作者的位置隐私.

(8)

(9)

定义2(ω-干扰因子) 概率混淆矩阵P满足ω-干扰因子表示为

(10)

结合定义1和定义2, 本文位置数据扰动算法如下.

算法2TDLDP算法.

输入:ε,ω,W,Lt;

输出: 位置集合L←{Lt,Lf};

步骤1) for eachwiinWdo

步骤2)wi加载其真实位置数据li

步骤6) end for

步骤9) end for

步骤10) returnL←{Lt,Lf}.

3 隐私安全分析

本文方案中, 唯一与工人交互位置数据的是边缘节点.下面通过证明在两个阶段边缘节点始终无法获得工人的真实数据以证明该方案的安全性.

3.1 任务分配阶段

命题1任务分配阶段, 由于任务分配是在密文下进行的, 所以边缘节点无法获得工人的真实位置信息.

证明: 在任务分配阶段, 当边缘节点对加密行程时间进行比较和排序时, 上述定义的密文计算的差值基于Paillier加密机制的加法同态, 该机制已经被证明在语义上是安全的, 并可以抵抗选择明文攻击. 这种基于密文的计算不允许边缘节点获取任何有效信息. 对于密文c1和c2, 计算差值:

D(c1⊖c2)=D(E(p1,r1)×E(p2,r2)-1)=p1-p2,

(11)

(12)

边缘节点EN通过EN′返回的查询结果1或0判断两个用户之间的行程时间差值, 但无法知道明文p1,p2的真实值.密钥管理边缘节点EN′每次只是根据请求解密密文差值, 也无法从中获取任何真实的位置信息.此外, 假设两个边缘节点相互勾结也只能获得工人到任务位置的行程时间值, 由于工人的速度未知, 还是无法推测出工人的真实位置.

3.2 数据上传阶段

命题2在数据上传阶段, 由于工人在上传感知数据前对位置数据进行了扰动, 所以边缘节点无法获得工人的真实位置信息.

证明: 由于在隐私保护方面满足ε-LDP的算法已经证明了其隐私保护能力, 所以只需证明算法2满足ε-LDP. 目前, LDP的主流扰动机制是随机响应机制, 根据随机响应机制给出的LDP的隐私参数ε, 每个工人发送自己真实位置或(n-1)个虚假位置的概率表示为

(13)

根据定义1, 如果

(14)

为真, 则算法2满足性质1和性质2以及ε-LDP, 其中N表示所有移动工人的总数.如果N包含x个位置, 则只有一个位置是工作人员的真实位置, 干扰位置为(x-1)个.根据生成规则, 工人发送真实位置的概率表示为

(15)

发送干扰位置的概率为

(16)

则

(17)

成立.因此, 算法2满足性质1和性质2以及ε-LDP.

4 仿真实验分析

4.1 实验设置

在仿真实验中, 设置一个50 km×50 km的感知区域, 在整个感知区域内设置10个边缘节点, 并将其划分为10个较小的感知区域. 在整个感知区域内随机生成任务和工人的位置, 区域内任务数量为50～100, 用户数量为150～300. 同时考虑到工人移动速度的不同, 结合实际应用中的真实速度值, 按照比例随机给工人速度赋值, 即步行速度5 km/h, 骑行速度10 km/h, 驾车速度30 km/h, 赋值比例为3∶5∶2. 本文所有实验程序均在MATLAB R2020a平台上使用MATLAB语言进行仿真. 所有实验的硬件环境为Windows10 64位操作系统, Intel(R) Core(TM) i7-12700F CPU @ 2.1 GHz, 16 GB RAM.

4.2 仿真结果分析

4.2.1 任务分配阶段性能评估

任务完成率(task completion rate, TCR)是指在任务规定行程时间前完成任务占所有任务的比例, 是评价任务分配方法的一个重要指标. 将CTWS与未保护工人位置隐私的任务分配算法TST[4]、 用加噪方式的任务分配方法(DPTA)[8]进行对比, 结果如图2所示.

图2 不同算法任务完成率对比Fig.2 Comparison of task completion rates of different algorithms

由图2(A)可见, 工人数量固定为200, 所有算法的TCR随着任务数的增加均有所下降. 因为每个工人只能执行一项任务时, 任务越多, 在规定行程时间内完成一项任务的概率就越小. DPTA的任务完成率始终最低, 因为DPTA在任务分配时根据上传加噪的行程距离, 导致任务完成率较低. CTWS算法略优于TST, 因为它是基于行程时间的任务分配算法, 同时也表明本文方案可以在不泄露工人真实位置的情况下实现最优的任务分配. 由图2(B)可见, 任务数固定为80, 随着工人数量的增加, 3种方案的TCR都在增加, 但增速逐渐放缓. CTWS算法总体优于另外两种算法, 这是因为CTWS算法在进行任务分配时的衡量指标即为行程时间, 可以使任务总用时最少, 所以在不同的比较实验中能够保持更高的任务完成率, 而另外两种算法用行程距离作为主要指标进行任务分配.

4.2.2 数据上传阶段性能评估

(18)

在K-匿名机制[11]中, 工人的QL被视为工人的真实位置li与其公布的中心位置之间的误差距离.假设有N个工人, 则K-匿名机制的QL表示为

(19)

其中lic表示工人wi发布的中心位置.

图3(A)为在相同隐私保护强度不同工人数量下的质量损失比较结果. 由图3(A)可见, 随着工人数量的不断增加, 每种隐私保护机制的QL都会增加,K-匿名机制的QL最严重. 虽然CS-MVP的QL很少, 但TDLDP算法的QL更少. 因此TDLDP算法的性能优于其他算法. 图3(B)为在相同工人数量不同隐私保护强度下QL的比较结果, 其中随机生成150名工人的位置信息作为实验的真实位置. 由图3(B)可见, 随着隐私级别的不断提高, 3种算法的QL都在逐渐增加. 但TDLDP中加入了干扰因子使得QL最小, 因此在服务质量损失方面的性能优于其他算法.

图3 不同算法服务质量损失对比Fig.3 Comparison of service quality loss of different algorithms

综上所述, 本文基于群智感知中工人两次需要提交自身真实位置的两个阶段, 给出了结合区块链和边缘计算的系统模型, 避免使用中心化第三方平台, 并且有针对性地对两阶段提出了不同的位置隐私保护方法. 在任务分配阶段, 考虑到工人移动速度的差异, 用工人到任务位置的行程时间作为任务分配指标. 基于同态加密在密文下通过边缘节点的协作完成任务分配, 并针对多任务分配场景进行优化使任务总行程时间最短, 在保护工人位置隐私的同时保证了较高的任务完成率. 在数据上传阶段, 差分隐私和干扰因子的结合使得工人可以在上传感知数据前在本地对位置数据进行干扰, 在保护工人位置隐私的同时保证了较低的服务质量损失.