基于任务质量的双向隐私保护任务分配系统

1.本发明涉及移动智感知任务分配领域，具体是一种基于任务质量的双向隐私保护任务分配系统。

背景技术：

2.随着网络质量的快速提高和移动设备的普及，可以经济有效的收集现实生活中数据的移动智感知技术(mcs)得到了广泛的关注。其中，感知任务的合理分配是mcs需要重点研究的问题，只有将任务分配给合适的任务参与者，mcs应用系统才可以更准确地实现其设计目标。mcs在线感知任务分配的过程是感知平台依据在线任务请求者的要求筛选出有执行任务能力的在线参与者的过程。不同于传统的众包，mcs的任务请求者和任务参与者在感知平台上动态的出现并与执行任务的时间和位置有关。因此，在任务分配的过程中任务请求者和任务参与者的感知信息会有隐私泄露的问题，需要对感知数据进行隐私保护。此外，感知系统无法保证大量的任务参与者都提交高质量的感知数据，除了任务参与者粗心或判断错误外，从人中收集的感知结果也会存在不可靠的情况。因此，在任务分配过程中需要通过更优的系统设计提高整体感知任务的质量。
3.在mcs应用场景中，感知数据的隐私保护与任务分配密切相关。感知数据包括任务请求者和任务参与者的时间信息，位置信息等。双向隐私保护即保护任务参与者的隐私信息并保护任务请求者的信息。现有研究大都通过对感知数据的加密或扰动来实现隐私保护，但感知信息一旦被加密或扰动就很难实现任务的精确匹配与优化。
4.文献[b.zhao,s.tang,x.liu,x.zhang and w.-n.chen,"itam:bilateral privacy-preserving task assignment for mobile crowdsensing,"in ieee transactions on mobile computing,vol.20,no.12,pp.3351-3366,1dec.2021]中，通过加密实现了双向隐私保护，但它需要占用任务请求者的计算资源。
[0005]
文献[muthurajkumar s,karthikeyan c a,pradeep k,et al.privacy-preserving dynamic task scheduling for autonomous vehicles[c]//proceedings of 2nd international conference on artificial intelligence:advances and applications.springer,singapore,2022:669-684]、文献[qian y,ma y,chen j,et al.optimal location privacy preserving and service quality guaranteed task allocation in vehicle-based crowdsensing networks[j].ieee transactions on intelligent transportation systems,2021,22(7):4367-4375]中，实现任务参与者感知信息的有效保护，但没有考虑对任务请求者的隐私保护。所以如何实现任务分配的双向隐私保护仍然是一个挑战。
[0006]
在mcs应用场景中，提高任务感知质量是任务分配的一个关键问题。在机会主义感知中任务参与者通常沿着预先确定的路径移动，例如上班需要经过的路径。所以在机会主义感知中，任务分配问题即如何选出多个合格的任务参与者，在移动时执行感知任务并有效的提高感知任务质量。任务质量的主要指标有时空覆盖率，数据收集时间等。
[0007]
文献[xin miao,yanrong kang,qiang ma,kebin liu,and lei chen.2020.quality-aware online task assignment in mobile crowdsourcing.acm transactions on sensor networks,vol.16,no.3,article 30.(july 2020),21pages]中，研究了任务分配的感知质量，但它没有考虑隐私问题。文献[j.zhang,q.zhang and s.ji,"a fog-assisted privacy-preserving task allocation in crowdsourcing,"in ieee internet of things journal,vol.7,no.9,pp.8331-8342,sept.2020]中，通过轻量级加密技术实现双向隐私保护并降低计算成本，但它没有考虑任务分配的优化问题。所以如何在双向隐私保护的基础上，优化任务匹配的感知质量仍然是一个挑战。

技术实现要素：

[0008]
本发明的目的是提供一种基于任务质量的双向隐私保护任务分配系统，，在满足模型约束条件下最大化总任务质量并保护任务参与者和任务请求者的数据隐私，以解决现有技术mcs任务分配时难以兼顾隐私保护和优化任务匹配质量的问题。
[0009]
为了达到上述目的，本发明所采用的技术方案为：
[0010]
基于任务质量的双向隐私保护任务分配系统，包括密钥分发中心、感知平台a、感知平台b、任务参与者、任务请求者，任务分配过程如下：
[0011]
步骤(1)、所述密钥分发中心为感知平台a分发密钥对(pka,ska)，为感知平台b分发密钥对(pkb,skb)，并由密钥分发中心将感知平台b的公钥pkb发送给感知平台a，密钥分发中心还为任务参与者分发密钥对其中：pka为感知平台a的公钥，ska为感知平台a的私钥，pkb,为感知平台b的公钥，skb为感知平台b的私钥，为任务参与者的公钥，为任务参与者的私钥，ωi表示任务参与者执行任务分配的数据，ωi∈i，i表示任务参与者数据集合；
[0012]
步骤(2)、所述感知平台a得到感知平台b的公钥pkb，所述任务请求者从感知平台a处获得感知平台b的公钥pkb，然后任务请求者使用公钥pkb加密自己的任务要求为加密自己的任务要求为其中：tj表示在线感知任务的要求；latj表示感知任务的纬度，表示加密后的感知任务纬度；lngj表示感知任务经度，表示加密的感知任务经度；表示感知任务可以被执行的开始时间，表示加密的感知任务可以被执行的开始时间；表示感知任务可以被执行的结束时间，表示加密的感知任务可以被执行的结束时间；
[0013]
完成加密之后，任务请求者将任务要求发送给感知平台a，感知平台a在接收到任务请求后，感知平台a为感知任务招募任务参与者；
[0014]
步骤(3)、所述任务参与者从感知平台a处获得感知平台b的公钥pkb，任务参与者使用公钥pkb，将自身的感知数据ωi加密处理为加密信息
其中：表示参与者起点的纬度，表示加密的参与者起点的纬度；表示参与者起点的经度，表示加密的参与者起点的经度；表示参与者终点的纬度，表示加密的参与者终点的纬度；表示参与者终点的经度，表示加密的参与者终点的经度；表示参与者执行感知任务的开始时间，表示加密的参与者执行感知任务的开始时间；表示参与者执行感知任务的结束时间，表示加密的参与者执行感知任务的结束时间；vi表示参与者执行感知任务的行驶速度，表示加密的参与者执行感知任务的行驶速度；bi表示任务参与者i执行感知任务的预算，表示加密的任务参与者i执行感知任务的预算；
[0015]
然后，任务参与者将加密信息和自身公钥发送给感知平台a；
[0016]
步骤(4)、感知平台a根据在线的加密任务要求中最优化总任务质量要求，将表示为vi；在线的感知任务集为在线任务参与者数据集为i＝{ω1,ω2,...,ωm}；感知平台为任务参与者分配的在线感知任务集为l为位置的缩写，任务参与者起点的位置可表示为任务参与者的路径可以表示为其中为任务参与者的起点为任务参与者的起点为任务参者的目的地并且任务参与者的路径li是逐一连接的；建立任务分配问题如下所示：
[0017][0018]
s.t.
[0019][0020][0021][0022]
[0023][0024]
在任务分配模型设计中，需要满足约束条件使得任务分配更符合实际；其中第一个约束设计确保每个任务参与者执行任务的成本不超预算；第二个约束设计确保参与者执行任务的时间不超过自己参与感知的时间范围；第三个和第四个约束设计确保任务参与者能够在任务没有结束之前到达指定的位置；第五个约束设计确保任务参与者执行感知任务时，在线感知任务已到达感知平台需要被执行，即参与者到达任务指定位置时不需要等待便可以执行感知任务；为任务参与者分配的任务和规划的路径在参与者到达时立即完成并不可逆转且在模型中参与者到达任务指定位置收集感知数据的时间忽略不计；其中，v
ij
表示感知任务tj是否被参与者i执行，tj被任务参与者i执行则v
ij
＝1否则v
ij
＝0；表示两个位置的距离，表示参与者需要执行感知任务的经纬度，表示参与者需要执行感知任务的经纬度；li表示任务参与者i执行感知任务的路径；
[0025]
表示任务质量函数，有：
[0026][0027]
其中kj为任务tj被执行的次数；pj为任务属性，与任务的难度和任务参与者整体的可靠性有关；由公式可知，当kj为奇数时，值增加，即任务质量增加；当kj为偶数时，值不变；定义的辅助函数为：
[0028][0029]
任务被执行第kj次时任务质量增量为其值随着kj的增加而降低；表示当多一个任务参与者执行感知任务tj时，潜在的质量增量；任务分配总任务质量最优的主要思想是当一个新任务参与者到达时，为该任务参与者分配一组在线感知任务，在任务参与者执行任务之后，能够使得总体的感知任务质量达到最大值；然而，任务质量函数仅在奇数点处增加，因此采用作为贪婪度量，该度量包含了偶数点处任务参与者对感知任务的影响，即为任务参与者分配满足增量和最大的感知任务集；
[0030]
在满足任务分配模型的约束条件下，构建基于差旅预算影响的多项式用于
测量候选任务被执行后感知质量增加情况，公式如下所示：
[0031][0032]
其中为任务参与者执行已经确定的感知任务需要移动的总距离，表示参与者执行感知任务的经纬度，l
r+1
表示参与者执行感知任务的下一个感知任务的经纬度；为被确定的任务集ti中最后一个感知任务到任务tj位置的移动距离，lj表示候选任务的经纬度，l
ε+1
表示参与者目的地的经纬度；为候选任务tj到任务参与者目的地的距离；设计表示在选择执行任务tj后参与者剩余的参与感知任务的预算，即可体现选择当前候选任务tj对任务参与者i差旅预算的影响；为候选任务tj对应的质量增量，当时感知任务tj被执行后会使得增加进而使得整体感知质量增加；与的比值是任务质量的增量与参与者执行任务tj的成本的比值，为任务参与者选择高价值但低成本的感知任务；所以不仅有效的体现候选任务tj对任务参与者i差旅预算的影响，还体现候选任务被执行后对整体感知质量的影响情况；
[0033]
任务分配总质量最优的原理是：为任务参与者i选择尽可能大的即为参与者选择尽可能大的任务集，而与质量函数的增量成正比，会使得任务质量的增量尽可能的大，进而使得整体感知任务质量尽可能大的增加，从而使得总体感知质量最优化；
[0034]
感知平台a基于上述描述的任务请求者与任务参与者的加密信息、任务分配的模型与约束条件和在线任务分配公式在感知平台b的帮助下为任务参与者满足任务参与者执行感知任务要求并使得总体感知任务质量最优的执行任务集合，即感知平台a对收到的加密数据进行加入随机数的处理，再将加密后的数据传输给感知平台b，感知平台b使用自己的paillier私钥解密数据并将对解密数据进行判断得出结论，再使用感知平台a的paillier公钥加密结论值并传输给感知平台a，最后感知平台a使用自己的paillier私钥进行解密得出比较结果，通过多次的大小比较，感知平台a可为任务参与者ωi选出满足条件的感知任务集
[0035]
进一步的，步骤(4)中，感知平台a为每个任务参与者选择满足约束条件并尽可能大的感知任务，其中与质量函数的增量成正比，即为参与者选择尽可能大的任务集，会使得整体任务质量尽可能大的增加，从而使得总体感知质量最优化。
[0036]
进一步的，还包括：步骤(5)、完成参与者任务匹配后，感知平台a将任务参与者的公钥发送给相应的任务请求者。
[0037]
进一步的，还包括：步骤(6)任务请求者在收到参与者的公钥后，使用任务参与者的公钥逐项加密任务请求为并发送给感知平台a，随后感知平台a将收到的发送给任务参与者。
[0038]
与现有技术相比，本发明的优点为：
[0039]
1)实现基于任务质量的在线任务分配。将任务分配建模为感知质量最优问题，设计了一种基于差旅距离影响的在线任务分配系统的算法，并考虑在线任务参与者的可达性。
[0040]
2)基于paillier加密算法，实现对任务请求者和任务执行者感知数据的双向隐私保护。在任务分配算法中涉及在加密的情况下进行除法、开根号和平方计算，根据计算需求设计算法以实现基于paillier加密的相应数值计算。
附图说明
[0041]
图1是本发明实施例系统模型图。
[0042]
图2是本发明实施例系统中任务参与者模型图。
[0043]
图3是本发明实施例仿真分析时的性能分析图，其中(a)研究任务到达率对平均感知质量的影响，(b)研究参与者到达率对对平均感知质量的影响，(c)研究任务到达率对每个任务被执行的参与者人数的影响，(d)研究参与者预算对每个任务被执行的参与者人数的影响。
[0044]
图4是本发明实施例仿真分析时任务参与者的可达性图，其中(a)研究在不同的任务到达率情况下考虑参与者是否可达对模型平均感知质量的影响，(b)研究在不同的参与者到达率情况下考虑参与者是否可达对模型平均感知质量的影响。
[0045]
图5是本发明实施例仿真分析时加密计算的时间开销图。
[0046]
图6是本发明实施例仿真分析时算法3的时间开销图，其中(a)研究在线感知任务的数量对计算开销的影响，(b)研究任务参与者的预算bi对开销的影响。
具体实施方式
[0047]
下面结合附图和实施例对本发明进一步说明。
[0048]
一、系统构成：
[0049]
如图1所示，本实施例系统包含感知平台，密钥分发中心，一任务参与者和一任务请求者。其中，密钥分发中心负责为感知平台和任务参与者分发密钥；感知平台a负责接收加密的任务请求和参与者的感知数据并在感知平台b协助下以保护参与者和任务请求数据隐私的方式进行任务匹配；任务参与者提交自己的加密数据，并从感知平台a处获得需要执行的任务序列。
[0050]
本实施例系统进行任务分配的大致过程如下：
[0051]
1)密钥分发。可信的密钥分发中心为任务参与者，感知平台a和感知平台b分发公私钥并将感知平台b的公钥分别发送给感知平台a。
[0052]
2)任务要求加密。任务请求者从感知平台a上获得感知平台b的公钥，使用感知平
台b的公钥加密任务要求，并将加密的任务要求发送给感知平台a。
[0053]
3)任务参与信息加密。任务参与者使用感知平台b的公钥加密自己的参与信息并将加密后的数据发送给感知平台a。
[0054]
4)分配任务路径。接收到任务参与者的加密数据后，感知平台a在感知平台b的帮助下为任务参与者分配合适的在线感知任务路径。
[0055]
本发明所用到的符号及含义见表1。
[0056]
表1相关符号及含义
[0057][0058][0059]
二、威胁模型：
[0060]
本实施例系统的威胁模型主要包括以下三种：
[0061]
1)感知平台被认为是半诚实体，即其会遵循感知协议执行任务，但试图推断任务参与者或任务请求者的真实身份、位置等隐私信息。
[0062]
2)任务参与者和任务请求者被认为是半诚实体，他们会按照系统协议执行任务，但试图获得自身以外实体的数据。
[0063]
3)tipq系统外存在实体对任务参与者或任务请求者的隐私信息感兴趣，会造成感知数据隐私泄露。
[0064]
特别地，当感知任务中任何两个实体相互勾结时，移动体智能感知应用程序的可行性就会被破坏。因此，我们假设任务参与者，任务请求者和感知平台之间不存在共谋。事实上，任务参与者为了保护隐私也不会与感知平台或任务请求者共谋。
[0065]
三、本实施例系统设计目标：
[0066]
本实施例系统的设计目标包括隐私保护目标和优化目标:
[0067]
隐私目标：包括对任务参与者和任务请求者的双向隐私保护。具体而言，对任务参与者的隐私保护是指除任务参与者自身以外，没有其他实体可以获得他参与任务分配的感知信息；对任务请求者的隐私保护是指任务要求不会被感知平台、不执行感知任务的参与者以及其他实体获得。特别地，每个任务参与者会通过假名的方式参与感知任务，因此保护了任务参与者的身份隐私。
[0068]
优化目标：任务分配满足总任务质量最优
[0069][0070]
四、本实施例系统采用的技术：
[0071]
本实施例系统采用的技术有任务质量函数，paillier密码系统和基于paillier加密的比较协议pcp，其中：
[0072]
4.1、任务质量函数
[0073]
一个感知任务由不同的任务参与者执行多次，任务被执行次数越多，得到的感知数据质量更高更有实用价值。文献[xin miao,yanrong kang,qiang ma,kebin liu,and lei chen.2020.quality-aware online task assignment in mobile crowdsourcing.acm transactions on sensor networks,vol.16,no.3,article 30.(july 2020),21pages.]中基于任务执行的次数设计了任务质量函数：
[0074][0075]
其中kj为任务tj被执行的次数；pj为任务属性，与任务的难度和任务参与者整体的可靠性有关。由公式可知，当kj为奇数时，值增加，即任务质量增加；当kj为偶数时，值不变。定义的辅助函数为：
[0076][0077]
任务被执行第kj次时任务质量增量为其值随着kj的增加而降低。表示当多一个任务参与者执行感知任务tj时，潜在的质量增量。任务分配总任务质量最优的主要思想是当一个新任务参与者到达时，为该任务参与者分配一组在线感知任务，在任务参与者执行任务之后，能够使得总体的感知任务质量达到最大值。然而，任务质量函数仅在奇数点处增加，因此采用作为贪婪度量，该度量包含了偶数点处任务参与者对感知任务的影响，即为任务参与者分配满足增量和最大的感知任务集。
[0078]
4.2、paillier密码系统
[0079]
同态加密即对明文进行加、乘运算再使用密钥加密的结果，与分别对明文进行加密再进行相应的计算结果等价。文献[paillier p.public-key cryptosystems based on composite degree residuosity classes[c]//international conference on the theory and applications of cryptographic techniques.springer,berlin,heidelberg,1999:223-238.]中描述了paillier同态加密算法支持加性同态和标量乘同态。
[0080]
具体而言，假设m1,m2,(为整数集，m1,m2,a为整数集中的数)
[0081]
加法同态：
[0082]
标量乘同态：此外，当m＝n-1时，当gcd(m,n)＝1时，其中，n为公钥参数。
[0083]
4.3、比较协议pcp
[0084]
为解决两个paillier加密数据的比较问题，使用文献[b.zhao,s.tang,x.liu,x.zhang and w.-n.chen,"itam:bilateral privacy-preserving task assignment for mobile crowdsensing,"in ieee transactions on mobile computing,vol.20,no.12,pp.3351-3366,1dec.2021.]提出的隐私保护的比较协议pcp。假设感知平台b的公钥为pkb＝(gb,nb)，两个明文值为m1,m2≥0，其中bit_length(nb)＝α(α＞2)，)＝α(α＞2)，pcp的详细过程如下：
[0085]
1)感知平台a:感知平台a选择两个随机数并随机选择x的值，其中为小于2
τ
且和2
τ
互质的数构成的集合，为小于n且和n互质的数构成的集合，x∈{0,1}。
[0086]
当x＝1时，感知平台a计算公式(3)：
[0087][0088]
当x＝0时，感知平台a计算公式(4)：
[0089][0090]
感知平台a将mb，和自己的公钥pka＝(ga,na)发送给感知平台b。
[0091]
2)感知平台b:从感知平台a获得mb，和pka后，感知平台b用自己的私钥skb对mb进行解密，获得感知平台b接着选择一个随机数并比较b和大小。
[0092]
当时，感知平台b计算公式(5)：
[0093][0094]
当时，感知平台b计算(6)：
[0095][0096]
当时，感知平台b计算公式(7)：
[0097][0098]
感知平台b将计算出的ma发送给感知平台a。
[0099]
3)感知平台a:从感知平台b获得ma后，感知平台a用自己的私钥ska对mb进行解密，获得根据br和x的值，感知平台a可以得到m1和m2的大小关系如公式(8)所示，其中，当x＝1和br＝1、或x＝0和br＝0时，令pcp＝1表示m1＜m2；当x＝1和br＝0、或x＝0和br＝1时，令pcp＝0表示m1＞m2。公式(8)如下：
[0100][0101]
五、本实施例系统的详细设计过程如下：
[0102]
5.1、基于任务质量的在线任务分配模型
[0103]
一个在线感知任务被形式化为具体而言，在线感知任务tj需要任务参与者在物理位置(latj,lngj)处执行；为在线感知任务执行的时间范围。其中：latj表示感知任务的纬度；lngj表示感知任务经度；表示感知任务可以被
执行的开始时间；表示感知任务可以被执行的结束时间。
[0104]
一个任务参与者执行任务分配的数据可以形式化为其中：表示参与者起点的纬度；表示参与者起点的经度；表示参与者终点的纬度；表示参与者终点的经度；表示参与者执行感知任务的开始时间；表示参与者执行感知任务的结束时间；vi表示参与者执行感知任务的行驶速度；bi为任务参与者执行在线感知任务的差旅预算，限制参与者从起点到目的地的路径长度。
[0105]
在线的感知任务集为在线任务参与者数据集为i＝{ω1,ω2,...,ωm}。感知平台为任务参与者分配的在线感知任务集为则任务参与者的路径可以表示为其中为任务参与者的起点为任务参与者的起点为任务参者的目的地并且任务参与者的路径li是逐一连接的。其中，l为位置的缩写，例如任务参与者起点的位置可表示为
[0106]
在tipq中任务分配需要最大化总任务质量，并根据任务参与者的位置信息对参与者执行感知任务的路径进行合理的调度来分配感知任务。最大化总任务质量的任务分配问题形式化表述为：
[0107][0108]
s.t.
[0109][0110][0111][0112][0113][0114]
在任务分配模型中需要满足一些约束条件使得任务分配更符合实际。具体而言，约束(9)确保每个任务参与者执行任务的成本不超预算。约束(10)确保参与者执行任务的时间不超过自己参与感知的时间范围；约束(11)和约束(12)确保任务参与者能够在任务没
有结束之前到达指定的位置。约束(13)确保任务参与者执行感知任务时，在线感知任务已到达感知平台需要被执行，即参与者到达任务指定位置时不需要等待便可以执行感知任务。为任务参与者分配的任务和规划的路径在参与者到达时立即完成并不可逆转且在模型中参与者到达任务指定位置收集感知数据的时间忽略不计。在任务分配模型设计中，需要满足一些约束条件使得任务分配更符合实际。其中，v
ij
表示感知任务tj是否被参与者ωi执行，tj被任务参与者i执行则v
ij
＝1否则v
ij
＝0；表示两个位置的距离，表示参与者需要执行感知任务的经纬度，表示参与者需要执行感知任务的经纬度；li表示任务参与者ωi执行感知任务的路径；
[0115]
在本实施例系统中，任务分配问题是通过调度路径的方式为每个新任务参与者分配任务并最大化总任务质量。为了实现质量最优的任务分配，提出一种在线多项式。在满足任务参与者的差旅预算和时间约束的条件下，该算法考虑了选择的感知任务对差旅距离的影响。如图2所示，在执行感知任务后，有两个候选任务和可以考虑。这两个候选任务的质量增量相同并且参与者执行感知任务的差旅成本也近似相同，但是可以看出候选任务到参与者目的地的距离明显大于候选任务因此，如果选择候选任务则会需要更多的差旅距离预算到达目的地，从而使得执行其他感知任务的差旅预算减少。根据这种情况，需要给予任务更高的优先级。
[0116]
根据图2的观察结果，在满足任务分配模型的约束条件下，构建基于差旅预算影响的多项式，用于测量候选任务被执行后感知质量增加情况，如公式(14)所示：
[0117][0118]
其中为任务参与者执行已经确定的感知任务需要移动的总距离，表示参与者执行感知任务的经纬度，l
r+1
表示参与者执行感知任务的下一个感知任务的经纬度；为被确定的任务集ti中最后一个感知任务到任务tj位置的移动距离，lj表示候选任务的经纬度，l
ε+1
表示参与者目的地的经纬度；为候选任务tj到任务参与者目的地的距离。设计表示在选择执行任务tj后参与者剩余的参与感知任务的预算，即可体现选择当前候选任务tj对任务参与者i差旅预算的影响。为候选任务tj对应的质量增量，当时感知任务被执行后会使得增加进而使得整体感知质量增加。与的比值是任务质量的增量与参与者执行任务tj的成本的比值，为任务参与者选择高价值但低成本的感知任务。所以不仅有效的体现候选任务tj对任务参与者i差旅预算的影响，还体现候选任务被执行后对整体感知质量的影响情况。
[0119]
任务分配总质量最优的原理是：为任务参与者i选择尽可能大的即为参与者选择尽可能大的任务集，而与质量函数的增量成正比，会使得任务质量的增量尽可能的大，进而使得整体感知任务质量尽可能大的增加，从而使得总体感知质量最优化。
[0120]
5.2、隐私保护的计算构造
[0121]
paillier系统仅可以进行加法同态和标量同态的运算，但是在基于任务质量的在线任务分配模型中还包含除法运算和欧几里得距离运算。为了解决上述加密计算问题，设计divopen实现基于paillier系统的除法运算和开根号运算并设计eucdis计算欧几里得距离。
[0122]
算法1描述了paillier系统的除法运算和开根号运算，感知平台a可以通过感知平台b的协助计算出两个加密数据的商或一个加密数据的开根号值。详细过程：为了防止感知平台b推断m1，m2和m3，感知平台a为三个个加密数据分别加入随机数，并将处理过的加密数据发送给感知平台b；感知平台b在接收到加密数据后先进行解密，计算解密后明文的商或开根号值并将结果进行加密，然后将加密的结果发送给感知平台a；感知平台a对加密结果进行处理最后获得加密的商或加密的开根号值。
[0123]
算法1divopen
[0124]
输入：感知平台a拥有的加密数据和感知平台b拥有私钥skb[0125]
输出：感知平台a得到和
[0126]
1.感知平台a选择两个随机数r1,r2,且gcd(r1,r2)＝r1，gcd(r3·
r3,n2)＝1，计算并将m1和m2发送给感知平台b
[0127]
2.感知平台b计算m1←
dec(m1),m
′2←
dec(m2),m
′3←
dec(m3)，计算)，计算并将md和mk发送给感知平台a。
[0128]
3.感知平台a计算加密的商为计算加密的开根号值为
[0129]
算法2描述了paillier系统的距离运算，感知平台a可以通过感知平台b的帮助计算出两个加密数据的欧几里得距离。详细过程：感知平台a在加密数据中加入随机数，并将处理过的加密数据发送给感知平台b；感知平台b在接收到加密数据后先进行解密，对解密后的数据进行平方运算并将结果进行加密，然后将加密的结果发送给感知平台a；感知平台a对加密结果进行处理最后获得加密数据的差值平方；感知平台a计算平方和并。其中r1＜＜r2，保证r1·
(m
1-m2)+r2＞0。
[0130]
算法2eucdis
[0131]
输入：感知平台a拥有的加密数据和感知平台b拥有私钥skb[0132]
输出：感知平台a得到
[0133]
1.感知平台a选择四个随机数r1,r2,r3,且r1＜＜r2,r3＜＜r4且gcd(r1·
r1,n2)＝1,gcd(r3·
r3,n2)＝1，计算
[0134][0135]
并将m1，m2，r2和r4发送给感知平台b。
[0136]
2.感知平台b计算m
′←
dec(m1)-r2,m
″←
dec(m2)-r4，计算并将m
′d和m
″d发送给感知平台a。
[0137]
3.感知平台a计算距离为3.感知平台a计算距离为
[0138]
4.感知平台a计算平方和并执行divopen中的开根号运算得出欧几里得距离值
[0139]
六、本实施例系统的任务分配过程：
[0140]
以下说明本实施例系统如何在保护隐私的情况下，实现基于任务质量的任务分配。首先概述tipq的主要信息流，然后详细基于任务质量的在线任务分配设计。
[0141]
6.1、本实施例系统的信息处理过程：
[0142]
本实施例系统的信息处理过程如下：
[0143]
1)密钥分发：为了实现感知平台进行任务分配计算，密钥分发中心为感知平台a分发密钥对(pka,ska)，为感知平台b分发密钥对(pkb,skb)并将感知平台b的公钥pkb发送给感知平台a。此外，密钥分发中心为任务参与者分发密钥对
[0144]
2)任务要求加密：为了防止任务请求者的数据被感知平台和未被选中的任务参与者获得，任务请求者从感知平台a处获得感知平台b的公钥pkb，然后任务请求者使用公钥pkb加密自己的任务要求为加密自己的任务要求为其中：tj表示在线感知任务的要求；latj表示感知任务的纬度，表示加密后的感知任务纬度；lngj表示感知任务经度，表示加密的感知任务经度；表示感知任务可以被执行的开始时间，表示加密的感知任务可以被执行的开始时间；表示感知任务可以被执行的结束时间，表示加密的感知任务可以被执行的结束时间；
[0145]
完成加密之后，任务请求者将任务要求发送给感知平台a，感知平台a在接收到任务请求后，感知平台a为感知任务招募任务参与者；
[0146]
3)加密信息和公钥上传：为了保护任务参与者信息的隐私，任务参与者从感知平台a处获得感知平台b的公钥pkb，任务参与者使用公钥pkb，将自身的感知数据ωi详细加密
处理为加密信息处理为加密信息其中：表示参与者起点的纬度，表示加密的参与者起点的纬度；表示参与者起点的经度，表示加密的参与者起点的经度；表示参与者终点的纬度，表示加密的参与者终点的纬度；表示参与者终点的经度，表示加密的参与者终点的经度；表示参与者执行感知任务的开始时间，表示加密的参与者执行感知任务的开始时间；表示参与者执行感知任务的结束时间，表示加密的参与者执行感知任务的结束时间；vi表示参与者执行感知任务的行驶速度，表示加密的参与者执行感知任务的行驶速度；bi表示任务参与者i执行感知任务的预算，表示加密的任务参与者i执行感知任务的预算。然后，任务参与者将加密信息和自身公钥发送给感知平台a；
[0147]
4)分配任务路径：感知平台a基于上述描述的任务请求者与任务参与者的加密信息、任务分配的模型与约束条件和在线任务分配公式在感知平台b的帮助下为任务参与者满足任务参与者执行感知任务要求并使得总体感知任务质量最优的执行任务集合，即感知平台a对收到的加密数据进行加入随机数的处理，再将加密后的数据传输给感知平台b，感知平台b使用自己的paillier私钥解密数据并将对解密数据进行判断得出结论，再使用感知平台a的paillier公钥加密结论值并传输给感知平台a，最后感知平台a使用自己的paillier私钥进行解密得出比较结果，通过多次的大小比较，感知平台a可为任务参与者i选出满足条件的感知任务集
[0148]
6)假名和公钥传输：完成参与者任务匹配后，感知平台a将任务参与者的公钥发送给相应的任务请求者。
[0149]
7)加密任务要求上传：任务请求者在收到参与者的公钥后，使用任务参与者的公钥逐项加密任务请求为并发送给感知平台a，随后感知平台a将收到的发送给任务参与者。
[0150]
6.2基于任务质量的在线任务分配算法设计：
[0151]
本实施例通过算法3给出了本实施例系统基于任务质量的在线任务分配设计。其中，第1-6行是将新达的感知任务放入感知任务集中并对感知任务被执行的次数、对应的感知质量和感知质量增量进行初始化；第7-9行是判断感知任务是否到达结束时间，任务结束则从感知任务集中去除，t
now
为当下对应的时间；第10-12行是当参与者提交的加密感知数据到达时，执行算法aptp得出参与者需要执行的感知任务集；第13-19行是判断感知任务集中的哪些感知任务被执行，若被执行则执行次数加一并计算对应的与值。
[0152]
算法3基于任务质量的在线任务分配：
[0153]
输入：加密的感知任务集和所有任务参与者的数据集合
[0154]
输出：每个参与者需要执行的感知任务集
[0155][0156][0157][0158]
算法4给出了为一个任务参与者分配感知任务集的具体过程。其中，第3-7行是检测是否存在新的任务可以被任务参与者执行；第9行获取候选任务集；第12行判断新的候选任务是否满足距离和时间的约束；第13-14行检测新的候选任务能否实现更高的任务质量，如果可以则更新参与者需要执行的在线感知任务；第19行是将新的感知任务添加到参与者执行的任务集合尾部。算法4体现了使得任务分配总质量最优的感知任务分配过程即在感知任务集中选出满足约束条件并且尽可能大的感知任务。
[0159]
算法4参与者的感知任务分配(aptp)
[0160]
输入：加密的感知数据集感知任务对应的任务质量增量和任务参与者的加密感知数据
[0161]
输出：参与者需要执行的感知任务集
[0162][0163][0164]
七、双向隐私性分析：
[0165]
本实施例通过对任务请求数据的隐私性分析和对参与者数据的隐私性分析来来说明tipq系统模型的隐私保护能力。
[0166]
定理1只要paillier加密系统是安全的，则tipq保护任务请求者和任务参与者的感知数据隐私，即实现双向隐私保护。具体而言，本实施例系统中的感知平台、未被选中的任务参与者和主动攻击者attacker都不能获得任务要求，并且感知平台、任务请求者以及attacker无法获得任务参与者的感知数据。
[0167]
证明：一个在线感知任务被表示为并要求被隐私保护。任务请求者用感知平台b的公钥进行加密，即：
[0168]
由图1所示的tipq系统可知任务请求者虽然用感知平台b的公钥pkb进行数据加密，感知平台b协助感知平台a进行任务分配计算，但是感知平台a会对请求者的数据进行处理再发送给感知平台b，所以感知平台b虽然有私钥skb但是无法获得任务要求。感知平台a虽然直接处理参与者的数据但没有感知平台b的私钥skb所以任务请求者的数据无法被感知平台a获得。根据前文描述可知，任务请求者只会使用被选中的参与者的公钥加密任务要
求未被选中的参与者无法获得被选中的参与者的私钥所以未被选中的参与者无法获得任务要求。同理，攻击者attacker也无法获得感知平台b和选中的参与者的私钥所以attacker没有获得任务要求的能力。
[0169]
此外，一个任务参与者执行任务分配的数据可以形式化为并使用公钥pkb进行加密即：因为感知平台a和感知平台b不会共谋，感知平台a无法从感知平台b处获得私钥skb所以感知平台a无法通过解密获得参与者的感知数据ωi，且根据前文的运算算法可知任务参与者虽然用感知平台b的公钥进行数据加密，但是加密后的数据没有直接被感知平台b处理，所以参与者的数据无法被感知平台b获得。同理，attacker不拥有感知平台b和参与者的私钥所以attacker无法获得参与者感知数据。
[0170]
综上所述，本实施例系统实现了对请求者和参与者感知数据的双向隐私保护。
[0171]
八、数值仿真与结果分析：
[0172]
8.1、实验环境与参数设置
[0173]
实验用matlab实现tipq。实验由intel(r)core(tm)i7-1065g7 cpu@1.30ghz 1.50ghz处理器，16gb内存，操作系统为windows10的笔记本电脑完成。实验使用基于跟踪和合成的数据集来模拟任务参与者和感知任务的在线行为。其中参数设置如表格2所示，默认的任务到达率为1.0，任务参与者到达率为1.8；任务的属性pj服从高斯分布n(0.8，0.15)；任务参与者的预算bi满足bi＝d(li)*δ其中δ服从高斯分布n(1.5，0.5)。本文最终的实验结果都是基于运行1000次的平均值。
[0174]
表2参数设置
[0175][0176][0177]
8.2性能分析
[0178]
8.2.1方案的可行性
[0179]
为了验证tipq基于加密的任务分配模型的可行性，本实施例与qaota模型进行了对比，如图3所示。实验使用整体感知任务的平均质量和每个感知任务可以分配的参与者数来比较分配方法的性能。
[0180]
从如图3(a),图3(b),图3(c)和如图3(d)中可以看出本发明系统的平均感知质量和平均每个任务可以被参与者执行的次数均高于qaota模型，即在考虑隐私保护的基础上
本发明系统通过提出的多项式算法使得任务分配的性能更优。
[0181]
如图3(a)和如图3(c)所示，随着任务到达率的增加，平均感知任务质量和任务被执行的平均参与者数都会减少。因为随着感知任务总数的增加，可以为每个任务参与者分配更多的感知任务，但任务参与者的数量和预算bi值是一样的，任务参与者可以执行的感知任务数量没有显著增加，任务被执行的平均次数减少了，所以整体的感知质量会降低。如图3(b)所示，随着任务参与者到达率的增加，整体感知任务的平均质量也随之增加。因为当感知任务的数量不变时，任务参与者的总数增加，会使得预算bi总和增加，每个感知任务被执行的次数增加，所以整体的感知质量会也会增加。如图3(d)所示，随着任务参与者预算bi的增加，每个感知任务被执行的次数也会随之增加。
[0182]
8.2.2任务参与者的可达性
[0183]
本发明系统在qaota模型的目标函数基础上考虑了任务参与者的可达性，即在满足预算bi的情况下，考虑任务参与者是否可以到达指定的任务地点。因为模型为在线任务分配，不仅和位置有关与时间也有关。在模型中可以忽略任务参与者到达指定地点执行任务的收集数据时间，但在显然任务参与者到达指定地点的时间需要考虑。如图4所示，考虑任务参与者可达性与没有考虑可达性的模型在平均感知质量的结果上可以获得近似的值和相似的特性，所以考虑任务参与者的可达性可以在保证感知任务质量的基础上更加符合实际生活场景。
[0184]
8.2.3计算开销分析
[0185]
图5显示了在数据量增多的情况下，算法div、算法eucdis和算法pcp的计算开销。图5从实验的角度分析了paillier加密计算除法，距离和比较数值大小的时间开销。其中div和pcp的时间开销相似，eucdis的计算开销较大因为在算法中还设计加密情况下的开根号运算。
[0186]
为了进一步检验本发明系统的有效性，算法3的时间开销被测试。从算法3中可以看出，当一个任务参与者到达时，算法3的运行时间与很多因素有关，例如在线的感知任务，任务参与者的预算bi等。为了测试算法3的时间开销，本实施例分别考虑了在线感知任务的数量和任务参与者的预算bi对开销的影响。结果如图6所示，算法3的运行时间随着任务数量和预算bi的增加而增加。
[0187]
本发明所述的实施例仅仅是对本发明的优选实施方式进行的描述，并非对本发明构思和范围进行限定，在不脱离本发明设计思想的前提下，本领域中工程技术人员对本发明的技术方案作出的各种变型和改进，均应落入本发明的保护范围，本发明请求保护的技术内容，已经全部记载在权利要求书中。

技术特征：

1.基于任务质量的双向隐私保护任务分配系统，其特征在于，包括密钥分发中心、感知平台a、感知平台b、任务参与者、任务请求者，任务分配过程如下：步骤(1)、所述密钥分发中心为感知平台a分发密钥对(pk
a
，sk
a
)，为感知平台b分发密钥对(pk
b
，sk
b
)，并由密钥分发中心将感知平台b的公钥发送给感知平台a，密钥分发中心还为任务参与者分发密钥对其中：pk
a
为感知平台a的公钥，sk
a
为感知平台a的私钥，pk
b
为感知平台b的公钥，sk
b
为感知平台b的私钥，为任务参与者的公钥，为任务参与者的私钥，ω
i
表示任务参与者执行任务分配的数据，ω
i
∈i，i表示任务参与者数据集合；步骤(2)、所述感知平台a得到感知平台b的公钥pk
b
，所述任务请求者从感知平台a处获得感知平台b的公钥，然后任务请求者使用公钥pk
b
加密自己的任务要求为加密自己的任务要求为其中：t
j
表示在线感知任务的要求；lat
j
表示感知任务的纬度，表示加密后的感知任务纬度；ln g
j
表示感知任务经度，表示加密的感知任务经度；表示感知任务可以被执行的开始时间，表示加密的感知任务可以被执行的开始时间；表示感知任务可以被执行的结束时间，表示加密的感知任务可以被执行的结束时间；完成加密之后，任务请求者将任务要求发送给感知平台a，感知平台a在接收到任务请求后，感知平台a为感知任务招募任务参与者；步骤(3)、所述任务参与者从感知平台a处获得感知平台b的公钥pk
b
，任务参与者使用公钥pk
b
，将自身的感知数据ω
i
加密处理为加密信息加密处理为加密信息其中：表示参与者起点的纬度，表示加密的参与者起点的纬度；表示参与者起点的经度，表示加密的参与者起点的经度；表示参与者终点的纬度，表示加密的参与者终点的纬度；表示参与者终点的经度，表示加密的参与者终点的经度；表示参与者执行感知任务的开始时间，表示加密的参与者执行感知任务的开始时间；表示参与者执行感知任务的结束时间，表示加密的参与者执行感知任务的结束时间；v
i
表示参与者执行感知任务的行驶速度，表示加密的参与者执行感知任务的行驶速度；b
i
表示任务参与者i执行感知任务的预算，表示加密的任务参与者i执行感知任务的预算；然后，任务参与者将加密信息和自身公钥发送给感知平台a；步骤(4)、感知平台a根据在线的加密任务要求中最优化总任务质量要求，将表示
为v
i
；在线的感知任务集为在线任务参与者数据集为i＝{ω1，ω2，...，ω
m
}；感知平台为任务参与者分配的在线感知任务集为l为位置的缩写，任务参与者起点的位置可表示为任务参与者的路径可以表示为其中为任务参与者的起点为任务参者的目的地并且任务参与者的路径l
i
是逐一连接的；建立任务分配间题如下所示：s.t.s.t.s.t.s.t.s.t.在任务分配模型设计中，需要满足约束条件使得任务分配更符合实际；其中第一个约束设计确保每个任务参与者执行任务的成本不超预算；第二个约束设计确保参与者执行任务的时间不超过自己参与感知的时间范围；第三个和第四个约束设计确保任务参与者能够在任务没有结束之前到达指定的位置；第五个约束设计确保任务参与者执行感知任务时，在线感知任务已到达感知平台需要被执行，即参与者到达任务指定位置时不需要等待便可以执行感知任务；为任务参与者分配的任务和规划的路径在参与者到达时立即完成并不可逆转且在模型中参与者到达任务指定位置收集感知数据的时间忽略不计；其中，v
ij
表示感知任务t
j
是否被参与者i执行，t
j
被任务参与者i执行则v
ij
＝1否则v
ij
＝0；表示两个位置的距离，表示参与者需要执行感知任务的经纬度，表示参与者需要执行感知任务的经纬度；l
i
表示任务参与者i执行感知任务的路径；表示任务质量函数，有：
其中k
j
为任务t
j
被执行的次数；p
j
为任务属性，与任务的难度和任务参与者整体的可靠性有关；由公式可知，当k
j
为奇数时，值增加，即任务质量增加；当k
j
为偶数时，值不变；定义的辅助函数为：任务被执行第k
j
次时任务质量增量为其值随着k
j
的增加而降低；表示当多一个任务参与者执行感知任务t
j
时，潜在的质量增量；任务分配总任务质量最优的主要思想是当一个新任务参与者到达时，为该任务参与者分配一组在线感知任务，在任务参与者执行任务之后，能够使得总体的感知任务质量达到最大值；然而，任务质量函数仅在奇数点处增加，因此采用作为贪婪度量，该度量包含了偶数点处任务参与者对感知任务的影响，即为任务参与者分配满足增量和最大的感知任务集；在满足任务分配模型的约束条件下，构建基于差旅预算影响的多项式用于测量候选任务被执行后感知质量增加情况，公式如下所示：其中为任务参与者执行已经确定的感知任务需要移动的总距离，表示参与者执行感知任务的经纬度，l
r+1
表示参与者执行感知任务的下一个感知任务的经纬度；为被确定的任务集t
i
中最后一个感知任务到任务t
j
位置的移动距离，l
j
表示候选任务的经纬度，l
ε+1
表示参与者目的地的经纬度；为候选任务t
j
到任务参与者目的地的距离；设计表示在选择执行任务t
j
后参与者剩余的参与感知任务的预算，即可体现选择当前候选任务t
j
对任务参与者i差旅预算的影响；为候选任务t
j
对应的质量增量，当时感知任务t
j
被执行后会使得增加进而使得整体感知质量增加；与的比值是任务质量的增量与参与者执行任务t
j
的成本的比值，为任务参与者选择高价值但低成本的感知任务；所以不仅有效
的体现候选任务t
j
对任务参与者i差旅预算的影响，还体现候选任务被执行后对整体感知质量的影响情况；任务分配总质量最优的原理是：为任务参与者i选择尽可能大的即为参与者选择尽可能大的任务集，而与质量函数的增量成正比，会使得任务质量的增量尽可能的大，进而使得整体感知任务质量尽可能大的增加，从而使得总体感知质量最优化；感知平台a基于上述描述的任务请求者与任务参与者的加密信息、任务分配的模型与约束条件和在线任务分配公式在感知平台b的帮助下为任务参与者满足任务参与者执行感知任务要求并使得总体感知任务质量最优的执行任务集合，即感知平台a对收到的加密数据进行加入随机数的处理，再将加密后的数据传输给感知平台b，感知平台b使用自己的paillier私钥解密数据并将对解密数据进行判断得出结论，再使用感知平台a的paillier公钥加密结论值并传输给感知平台a，最后感知平台a使用自己的paillier私钥进行解密得出比较结果，通过多次的大小比较，感知平台a可为任务参与者ω
i
选出满足条件的感知任务集2.根据权利要求1所述的基于任务质量的双向隐私保护任务分配系统，其特征在于，步骤(4)中，感知平台a为每个任务参与者选择满足约束条件并尽可能大的感知任务，其中与质量函数的增量成正比，即为参与者选择尽可能大的任务集，会使得整体任务质量尽可能大的增加，从而使得总体感知质量最优化。3.根据权利要求1或2所述的基于任务质量的双向隐私保护任务分配系统，其特征在于，还包括：步骤(5)、完成参与者任务匹配后，感知平台a将任务参与者的公钥发送给相应的任务请求者。4.根据权利要求3所述的基于任务质量的双向隐私保护任务分配系统，其特征在于，还包括：步骤(6)任务请求者在收到参与者的公钥后，使用任务参与者的公钥逐项加密任务请求为并发送给感知平台a，随后感知平台a将收到的发送给任务参与者。

技术总结

本发明公开了一种基于任务质量的双向隐私保护任务分配系统，解决了移动智感知中如何进行隐私保护、以及如何收集可靠感知数据的问题。本发明使用paillier加密方法实现任务参与者和任务请求者的感知数据隐私保护，使用基于任务质量的任务分配算法来提高系统整体感知数据的可靠性。最后本发明通过仿真证明了系统的可行性，并在平均感知质量上优于对比模型。本发明系统在任务分配的隐私保护和整体感知任务质量上进行了有益的探索。知任务质量上进行了有益的探索。知任务质量上进行了有益的探索。