多级本地化差分隐私算法推荐框架

王瀚仪，李效光，毕文卿，陈亚虹，李凤华，牛犇

（1.中国科学院信息工程研究所，北京 100093；2.中国科学院大学网络空间安全学院，北京 100049；3.西安电子科技大学网络与信息安全学院，陕西 西安 710071）

0 引言

随着移动通信技术的发展，数据的重要性越来越突出，服务商试图通过分析用户的数据为用户提供更加个性化的优质服务。然而，随着互联网用户隐私保护意识的觉醒，以及多个国家相继出台隐私保护法案带来的双重压力，如何在保护用户隐私信息的前提下采集数据成为各大互联网服务商刻不容缓的任务。在学术界和工业界的共同推动下，本地化差分隐私（LDP,local differential privacy）技术逐渐成为保护用户隐私数据的重要技术手段之一。LDP 借助其严格的数学定义，在不需要可信第三方参与的情形下，抵御任意背景知识的攻击者，并且通过隐私预算参数，量化了算法隐私保护的强度，充分满足了被采集用户对隐私信息保护的需求；同时，LDP 还能够在用户数据量充足的条件下，保证统计分析结果的可用性。

LDP 技术的研究众多，各类统计分析任务下的LDP 技术层出不穷，然而参与统计分析任务的用户均需要采用相同的LDP 保护机制，选取相同的隐私预算参数，忽略了用户动态变化的资源环境与不同用户对资源、隐私的个性化需求。

面对现实中移动终端资源的动态变化与限制，以及用户对个性化的追求，单一的隐私保护算法不足以支撑用户的需求。例如，打车服务商想通过频繁采集用户位置打卡信息来选取合适的打车等候站点。一方面，用户不想泄露自己的位置信息，因此服务商在信息采集过程中需要为用户提供隐私保护；另一方面，服务商希望得到一个比较准确的统计结果，因此常用LDP 算法解决这类问题。尽管LDP 有很多不同的机制，但是现有方案中所有用户必须采用相同的LDP 机制，服务商才能够计算出较为准确的结果，这种方案固化带来的问题是一旦用户设备资源受限，则会使结果不准确或者无法采集该用户的信息。例如，某用户手机电量不足，若和其他用户一样选择电量消耗较大的机制，手机很可能直接由于电量耗尽而关机，无法执行任务也无法正常通信；若所有用户都选择电量消耗较小的机制，考虑到消耗小的机制往往可用性较差，因此服务商计算结果的可用性就会急剧降低。

为了权衡用户对资源、隐私的偏好以及服务商对可用性的需求，本文设计了多级LDP 算法推荐框架，考虑到服务商对统计结果可用性的要求以及用户对资源、隐私的个性化需求，通过多级管理为不同用户推荐不同的但适合当前自身资源环境的LDP 算法，实现多用户差异化隐私保护。进一步，将框架应用至位置服务中的位置兴趣点（PoI,point of interest）频数统计任务中，改进LDP 算法以保证统计结果的可用性，设计协同机制保护用户的隐私偏好。

本文主要的贡献如下。

1)设计一个多级LDP 算法推荐框架，解决LDP 技术忽略用户之间差异的问题。从隐私信息全生命周期保护的角度出发，分5 个步骤对用户信息进行保护。充分考虑用户对资源、隐私的个性化需求以及服务商对统计结果的可用性要求，通过服务商和用户对LDP 算法进行选取，既保证了服务商对用户的管理，又不限制用户的个性化需求。

2)将框架落地到PoI 频数统计场景中，并将框架具体化。选择4 种典型频数LDP 算法，考虑电量、流量2 个资源因素以及算法的可用性，为用户推荐当前环境下的最优LDP 算法。通过对LDP 机制进行改进，使不同用户即使采用不同的机制，仍能保证服务商计算出的统计结果为真实结果的无偏估计。在此基础上，设计开销较小的用户协同机制，保护用户的隐私需求。

3）实验结果表明，本文方案能够使资源自适应地为用户推荐个性化的LDP 算法，并且能够保证统计结果的可用性。

1 相关工作

差分隐私（DP,differential privacy）[1]是一个具有严格数学定义的隐私保护概念，即任意一条记录的增加或删除都不会影响查询结果，也就避免了让攻击者了解更多的信息。基于此，学者们提出了多种差分隐私保护技术。Dwork 等[2]提出了Laplace机制，针对连续的数值型查询结果添加服从Laplace的噪声。Mcsherry 等[3]针对非数值型数据的查询结果提出了指数机制，以一定概率从结果集合中选择一个结果输出。

标准的DP 通过可信的数据中心收集用户数据，并发布满足差分隐私的用户数据统计分析结果。然而在实际应用中，很难找到完全可信的数据中心，由此LDP 应运而生，其能够在用户端执行满足差分隐私的保护机制，同时保证统计结果的准确性。按照服务商的数据统计分析的任务类型不同，LDP 机制主要可以划分为三类[4]：频数统计任务[5-10]、均值统计任务[11-12]和复杂任务[13-14]。还有一些工作对DP概念中的隐私预算进行研究，例如在LDP 中为不同用户分配不同的隐私预算，或探讨如何为DP 算法选择合适的隐私预算。

1.1 频数统计任务下的LDP

有多种LDP 机制被设计用来求取用户的频数结果，如统计某个年龄段的用户数。这些机制或不对数据进行编码处理[5-6]，或采用二进制向量[7]、hash 函数[7,15]、矩阵转换[8]等手段对用户数据进行编码，并对编码数据或原始数据扰动后发送给服务商，服务商再对数据进行校准、聚合，得到频数估计结果。Google 团队提出了Rappor 算法[16]，应用随机应答（RR,randomized response）扰动机制，使服务商能够在隐藏用户字段的前提下，从用户处获得字段频数的统计结果。

除此之外，还扩展出许多新型频数统计任务，例如频繁项集挖掘[9]、针对key-value 类型数据的频数估计[10]等。Ye 等[10]提出PrivKV 算法，能够在满足LDP 的条件下对key-value 数据进行保护，并且保留key 和value 之间的关联关系；为了提高结果的准确度，Ye 等在此基础上改进算法，对PrivKV进行多次迭代，为了减少网络时延，进一步将多次迭代优化为虚拟迭代，减少了用户的参与。

1.2 均值统计任务下的LDP

均值统计任务是求取多个用户数据的均值，如求用户的平均年龄。针对均值统计任务，最基础的LDP 机制是利用Laplace 机制[2]分别对用户数据添加噪声。Duchi 等[11]提出了一种适用于多维数值型数据的LDP 机制，其基本思想是利用随机响应技术，根据一定的概率分布扰动每个用户的数据，同时确保均值统计结果的无偏估计。然而，Nguyên等[12]指出当数据维数为偶数时，Duchi 等的算法并不能满足LDP 的定义，并对该算法进行了修正，同时提出了Harmony 算法，满足与Duchi 等的算法相同的隐私保护强度和可用性，但大大减小了算法的通信量。

Wang 等[17]提出了针对一维数值型数据的PM算法，相对Duchi 等的算法而言，统计结果有着更小的方差，即更好的可用性，同时实现也更加简易；进一步地，Wang 等基于Harmony 算法将PM 算法扩展至高维数据，并设计HM 算法以处理分类型的数据。

1.3 复杂任务下的LDP

Yilmaz 等[13]提出利用LDP 算法来训练朴素的贝叶斯分类器，首先将每个用户的标签和取值转化成一个新的值，然后对该值执行LDP 机制下的扰动，在保留标签和取值之间关系的同时，保护用户的训练数据。Mahawage 等[14]改进已有频数统计任务下的LDP 算法，用于控制卷积神经网络中的隐私泄露，同时提出效用增强随机化机制，进一步提高随机化二进制字符串的可用性。Shin 等[15]将LDP机制应用到推荐系统中，在用于矩阵分解的梯度下降算法中给梯度添加噪声，保护用户在交互过程中的真实梯度不被服务商获取，从而保护用户的真实属性以及对应评分。进一步地，为了减少开销，Shin等[15]引入降维技术并提出基于采样的二元机制，减小算法的开销，同时在一定参数范围内也能保证较好的推荐准确性。Zhao 等[18]将联邦学习与LDP 相结合，提出多种LDP 机制，以在保护用户隐私、降低通信成本的前提下实现机器学习模型。

1.4 个性化的LDP

Chen 等[19]首次提出了个性化本地化差分隐私（PLDP,personalized local differential privacy）的概念，并进一步提出了个性化计数估计协议，利用用户组聚类算法将该协议应用于不同隐私级别的用户。Nie 等[20]提出了一个框架来优化直方图估计，其中利用个性化隐私下的数据回收方案扩大估计的样本量，并证明该框架具有最优效用。Xia 等[21]利用本地化差分隐私技术执行k-means 聚类任务，为了提高结果的可用性，给二进制数据的不同比特位分配了不同的隐私预算，并考虑到不同用户具有不同的隐私需求，因此设计不同用户参与扰动的比特位不同。Shen 等[22]提出了新的PLDP 概念，改进频数统计任务下的OUE 算法，设计了多维联合分布估计方案，为不同维度的数据分配不同的隐私预算，使其比传统LDP 具有更好的效能。

1.5 DP 隐私预算参数选择

在差分隐私中，隐私预算参数ε表示算法的隐私保护程度，ε越小，保护程度就越高。针对如何选取参数ε的问题，Naldi 等[23]提出了一种基于区间估算理论的选择方法，用置信区间和置信水平2 个参数来衡量ε。Shahani 等[24]在给定场景下通过权衡隐私保护和可用性对ε进行选择，并给出了ε的一个上界。

综上，LDP 算法可应用在多种任务场景下，种类众多，且不同LDP 算法在资源开销、可用性上各有优势，但不同用户往往采用相同的LDP 算法。并且，尽管隐私预算参数的大小决定了算法的隐私保护强度，但少有工作为不同用户选取不同的隐私预算。

2 预备知识

2.1 本地化差分隐私

定义1一个随机算法M满足ε-LDP，当且仅当对于任意2 条不同记录t，t′∈Domain(M)，以及任意y∈Range(M)，都有

因此，2 个不同的数据经过随机算法M扰动后，接收者无法通过收到的数据来分辨二者。

2.2 个性化本地化差分隐私

由于不同用户的隐私需求不同，Chen 等[19]提出PLDP 的概念。PLDP 中包含2 个参数，第一个参数是安全区域，即用户认为可以透露的最小区域τ，例如，该用户不介意别人知道其所在位置为北京，可以将安全区域设置为北京，则用户希望算法能够使真实位置与安全区域内的其他位置无法区分开；第二个参数是隐私预算ε，与LDP 中的概念相同，ε表示算法限制攻击者区分任意2 个位置的能力大小，ε越小，表示该能力越高，称(τ,ε)为某特定用户的隐私规范。基于此，(τ,ε)-PLDP 的基本概念如下。

定义 2一个随机算法M对某用户满足(τ,ε)-PLDP，当且仅当对于任意2 个位置t,t′∈τ，以及任意O⊆Range(M)，都有

2.3 问题与挑战

本文旨在解决本地化差分隐私机制各异，但不同用户往往采用相同的机制和参数，无法根据用户当前的资源环境和隐私需求灵活地为用户提供细粒度的隐私保护的问题。为了实现该目标，本文需解决以下3 个挑战。

1)现有LDP 算法为了便于服务商对扰动后的用户数据进行无偏估计，所有用户均采用相同的机制和参数。然而不同LDP 算法在资源开销、统计分析结果可用性上各有优劣，因此能否结合不同机制的不同特性，为资源开销、隐私需求各异且动态变化的用户推荐个性化的LDP 算法，并且仍能保证结果的无偏，是本文面临的第一个挑战。2)如何在有限且动态变化的资源环境下，为用户选择适配当前资源环境的LDP 机制，是本文面临的第二个挑战。3)不同用户对隐私的需求不同，用户选取的隐私预算参数能够反映用户对隐私的个性化偏好，若某个用户对隐私的需求较低，攻击者可以集中针对该用户进行攻击，因此，如何在不泄露该偏好的情况下执行方案，是本文面临的第三个挑战。

2.4 攻击模型

本文设定服务商和用户是诚实而好奇的（HBC,honest-but-curious），他们诚实地遵守设计的方案，但是会试图根据已知信息推测其他用户的更多信息。本文涉及的系统参数如表1 所示。

表1 系统参数

3 多级LDP 算法推荐

3.1 算法推荐框架

Li 等[25]提出隐私计算及其框架，该框架从隐私信息全生命周期保护的角度出发，分为隐私信息提取、场景抽象、隐私操作选取、隐私保护方案设计或选取、隐私保护效果评估5 个步骤。本文基于该框架，设计了多级LDP 算法推荐框架，分为5 个步骤，图1 简要描述了所提框架。

图1 多级LDP 算法推荐框架

1)隐私信息提取。用户对服务商想要采集的信息进行评估，并根据信息的敏感程度，设定自己的隐私预算大小。

2)场景抽象。服务商通过自身需求确定LDP算法的计算场景，例如，是求取用户信息的平均值，还是执行更复杂的任务。

3)隐私操作选取。确定场景后，服务商确定满足场景的算法集合ALG；然后，服务商会根据用户的级别，依照策略从所有算法集合ALG 中为每个用户i选择一个算法集合 algi⊆ALG，方便服务商管控。策略机制可以根据需求自定义，例如，作为普通用户 A，服务商为用户开放部分算法，即algA⊂ALG，对资源灵活性要求不高的用户提供更简洁的选择；相反，若用户B 对资源灵活性要求较高，成为服务商的会员，那么服务商会为用户B 开放所有的算法供用户选择，即algB=ALG。

4)隐私保护方案设计或选取。具体细分为如下4 个步骤。

①服务商预处理。为了方便用户对算法进行选取，服务商需要先进行预处理，得到各项资源开销与影响因素之间的关系；同时从服务商自身考虑，也需要将算法的可用性纳入影响用户选取LDP算法的因素中，以便增加统计结果的可用性。考虑o类资源开销r1,r2,…,ro，设定影响LDP 算法资源开销因素有h个，分别为a1,a2,…,ah。利用实验拟合集合ALG 中每个算法alg 的各类资源开销与影响因素之间的关系,1≤j≤o,alg∈ALG；同时，利用LDP 算法结果的方差来衡量其可用性，因此可以通过理论推导得到算法alg的可用性rvar与相应的影响因素之间的关系,alg∈ALG。

② 用户具体算法选取。用户i定义自身对o类资源开销的权重0≤w1,w2,…,wo≤1，权重越高表示对该类资源的消耗越重视。服务商统一定义对算法可用性的权重0≤wvar≤1，同时根据用户在当前状态下影响因素与权重的取值，利用多目标决策方法选择最优算法 algopt∈algi。

③LDP 算法扰动。用户选取本地化差分隐私个性化隐私预算εi，利用所选算法对用户的隐私数据datai进行扰动得到 resulti=，再将结果 resulti在隐藏自身隐私预算εi的前提下进行校准，并发给服务商，其中，用户对隐私保护强度要求越高，选择的隐私预算值就越小，具体选取方法可以参考1.5 节中的相关工作。

④服务商结果整合。服务商收到用户的数据后对数据进行聚合，得到目标结果R。

5)隐私保护效果评估。由于本文对LDP 算法进行推荐，因此可以用实验的形式来量化分析方案的偏差性和复杂性[25]。

3.2 基于位置PoI 频数统计的LDP 算法推荐

本节具体考虑位置PoI 频数统计场景下对LDP算法的推荐，由于本文侧重点在于如何推荐LDP算法，因此图1 中的步骤1)、步骤5)在此部分不作研究。本文框架不仅可以用于频数统计任务的LDP算法，还可以用于其他LDP 算法中，但是，一是由于均值统计算法一般不需要校准，不涉及泄露用户隐私偏好的情况；二是复杂类型的LDP 算法一般由均值或频数统计任务演化而来，因此本文以频数统计的场景为例进行讨论。

3.2.1 方案设置

根据PLDP 的定义，用户i根据自己的需求选定PoI 集合Di⊆D，则用户扰动后的结果均在集合Di内。为方便起见，本文给定Di供用户选择，即Di∈，其中⊆D，因此在传输Di时，用户只需要传输一个下标即可；同时，用户根据隐私偏好选择隐私预算εi。

本节选取了4 种单值频数统计的LDP 算法作为算法集合，分别是DE（direct encoding）、OUE（optimized unary encoding）、OLH（optimized local hashing）和THE（thresholding with histogram encoding ）[7]，即ALG={DE,OUE,OLH,THE}。单值频数统计[26]是指每个用户只发送一个变量取值给数据收集者，数据收集者根据所有用户上传的取值统计每一个候选值的频数结果，并进行发布。本节选取的4 种算法代表了最典型的LDP 频数统计算法，4 种算法分别采用了不同的编码机制，故产生了有差别的资源消耗。下面，简单介绍这4 种算法，其中假设用户选择的数据扰动范围集合为D，本地化差分隐私预算为ε。

本文方案具体分为5 个步骤，分别为服务商算法集管控、服务商预处理、用户具体算法选取、LDP算法扰动、服务商结果整合，具体步骤在3.2.2～3.2.6节中分别详细介绍。

3.2.2 服务商算法集管控

服务商根据用户的级别为用户推荐不同的算法，在本节中设置策略如下：为普通用户推荐算法DE 和OLH，为会员用户推荐4 种算法。这里选择DE 和OLH 是因为DE 在较小时，开销很小，可用性也不大；OLH 开销较大，可用性却相对稳定，所以服务商为用户提供的算法集可供对灵活性要求不高的用户使用。记服务商给用户i推荐算法集合为algi。

3.2.3 服务商预处理

3.2.4 用户具体算法选取

首先建立用户对各项资源的权重，可以根据用户偏好主观地进行设置，也可以由服务商建立指导设置，后期可以根据用户需求进行调整。本节给出了一种客观判断权重的方案，为用户提供指导：根据用户当前的剩余电量br（满电量是100），使用的流量套餐中的剩余流量fr（MB），以及每超出套餐1 MB 需要的价格fp（元），建立用户本身对电量和流量重视程度的权重值w1和w2。其中，，当手机充电时，用户不会担心电量消耗，因此w1=0；当手机连接Wi-Fi 或者剩余流量充足时，用户不会担心流量消耗，因此w2=0；当使用流量且剩余流量不足时，令w2=3.33fp（现有流量套餐超出的最高单价为0.3 元/MB）。因此，权重设置为

服务商对可用性的权重设置为w3=1。

The Establishment and Structure of the Oirats Karuns of the Upper Three Banners

4)推荐算法。评分最高的算法 algopt将作为用户的推荐结果。

3.2.5 LDP 算法扰动

用户使用算法 algopt对原始数据dl进行处理。在前述介绍的4 种频数统计的LDP 算法中，分别经过了在用户端编码、扰动和在服务商端校准的过程。然而为了保护用户的隐私预算εi，需要对原算法进行改进，避免在服务商端进行校准，为此，本文将校准过程迁移至用户端，并设计后处理算法，防止扰动结果泄露用户的隐私偏好。具体操作如下。

图2 协同机制

3.2.6 服务商结果整合

3.3 方案证明

定理1本文方案为每个用户提供了(Di,εi)的个性化本地化差分隐私。

证明由于本地化差分隐私具有后处理的性质，因此只需证明在3.2.5 节步骤2)的扰动后，对于∀j1,j2∈Di，有Pr(M(j1)=xi)≤eεPr(M(j2)=xi)。

综上，有 Pr(M(j1)=xi)≤eεPr(M(j2)=xi)不等式成立。证毕。

定理2服务商对PoIdl的访问频数的统计结果是真实频数统计结果的无偏估计。

证明真实频数统计结果为

根据本文算法定义，有

定理3本文方案得到的频数估计的方差约为。

证明的方差为

根据本文算法定义，有

因此有

根据方差公式可以看到，在每个用户选择的LDP算法固定的情况下，扰动范围Di和隐私预算εi影响了本文方案的可用性。

4 实验分析

4.1 实验设置

本节参考文献[25]提出的隐私保护效果评估，从可用性、复杂度分析的角度对所设计方案进行衡量。首先，利用实验拟合出4 种LDP 算法的资源开销与影响因素的关系式，并利用LDP 算法理论上的方差来衡量可用性；其次，将表达式代入方案，并观察用户处于不同资源场景时的最优算法结果，证明本文方案的可行性；再次，通过调节参数，比较本文方案与常见LDP 算法可用性的差异；最后，从理论和实验上分析本文方案的复杂度。

为了简便起见，假设服务商给所有用户都推荐了LDP 的算法全集ALG，且所有用户扰动范围集合Di与隐私预算εi均相同，简记为D与ε，令集合D的大小为。固定参与统计的用户人数为n=10 000，固定THE 中的参数θ=1。本文执行多次实验，并对实验结果求取平均值。

4.2 LDP 算法的资源拟合关系

本节中的测试环境为：硬件设备为小米MIX 终端，软件系统为MIUI 10 9.3.28，运行内存为6 GB。

为了拟合电量、流量与影响因子之间的关系，本节以ε=4 的情况为例，测试L变化时，执行1 000 次改进后的DE、OUE、OLH、THE 在电量和流量上的开销。

从图3 和图4 中可以发现，4 种算法的流量和电量均随着L的增大而增大，趋近于一条直线，利用最小二乘法拟合出4 种算法的流量和电量与L的关系式，得到

图3 不同算法电量消耗情况随L 的变化

图4 不同算法流量开销情况随L 的变化

对于各种算法的可用性，类似定理3 的证明，当ε=4 时，可以得到DE、THE、OUE 和OLH 算法的方差与影响因素的关系式分别为

类似地，能得到ε在其他取值下的关系式，再利用关系式代入3.2.4 节的算法选取方案，并观察用户在不同状态时推荐的最优算法，具体结果如表2所示。

表2 用户在不同状态下的算法推荐

需要说明的是，改进后的THE 算法尽管其可用性比DE 好，但是与其他算法相比开销较大，不足以成为最优算法。因此本文实验对改进后的THE 算法采用了更高效的传输方式，增大其流量开销，以换取电量开销的减小，具体传输方式为在3.2.5 节的步骤4)中，用户要将Mi发送给服务商，其他3 种算法会将Mi集合中的多个元素整合成一个字符发出，而THE 的Mi会以list 的形式发出，因此THE 的传输开销会更高，但是同时少了整合步骤，因此计算量的消耗会降低，即电量消耗会减小。更新后的THE算法可以视作另一种新型的LDP 算法。由此可以看到，当用户的状态发生变化时，本文方案可以为用户提供自适应的、个性化的算法推荐服务。

4.3 方案的可用性

本节采用改进后的DE、OUE、OLH 和THE这4 种算法作为对比方案。考虑在用户所选扰动范围集合大小L和隐私预算ε发生变化时本文方案与对比方案的可用性。本文利用每个dl的真实频数与估计频数之间的均方根误差（RMSE,root mean square error）来衡量方案的可用性。具体计算式为

从式(14)可以看到，可用性越高，RMSE 的值就越小。

实验假设4种算法被用户选择作为最终方案的概率是相等的，在该前提下，首先固定ε=4，研究L对方案可用性的影响。图5 展示了本文方案与其他4 种方案可用性区别与变化趋势。为了表现L在不同数量级下方案的可用性，参考文献[10]，采取指数型的横坐标进行实验。从图5 可以看到，当L<26时，DE的可用性优势明显，但当L继续增大时，DE 可用性变差。而其他3个对比方案的可用性受L的影响不大，OLH 和OUE 的可用性很接近，维持在30 左右，THE的可用性略微差一些，维持在50 左右。本文方案由于受到DE 的影响，可用性随着L的增大有所减小，但是好于DE 本身，并且在L<210时可用性甚至优于THE。这说明本文方案的可用性中和了LDP 算法集中不同算法的可用性，这是因为独立的多个随机变量的和的方差等于变量的方差和。

图5 不同方案在固定ε 下RMSE 的变化

固定L=210，观察ε对方案可用性的影响，如图6 所示。从图6 可以看到，所有方案的可用性都随着ε的增大而增加。当ε较小时，本文方案的可用性要优于DE 和OLH 这2 个方案，且随着ε的增大，本文方案与OLH 和OUE 的可用性逐渐接近，甚至优于THE。另外，尽管理论上OUE 与OLH 的可用性是一致的，但是由于在ε较小时，OLH 中参数很小，即哈希函数会将1 024 个数字映射到个数上，使碰撞较大，从而影响了OLH 的可用性；而当ε增大时，这二者的可用性又恢复了一致。

图6 不同方案在固定L 下RMSE 的变化

综上所述，本文方案与其他方案相比，在L和ε的变动下，其可用性始终能够保持较好的状态。

4.4 方案的复杂度

本文在3.2 节中提出的方案的算法复杂度与所选择的算法集合大小有关，当算法集合大小固定时，算法复杂度与用户所选扰动范围=L有关。

具体而言，设服务为用户i推荐了个算法，并且算法的拟合关系式在用户资源充足时已由服务商更新，权重也已预计算。因此在本文方案中，每个用户均执行了次加法运算、次乘法运算、次除法运算、次开根运算和2 次随机运算。用户选择不同的扰动算法会有不同的计算开销：采用DE 算法会进行一次随机；采用OUE 算法会进行L次随机；采用OLH 算法会进行L+1 次哈希和一次随机；采用THE 算法会进行L次随机和L次加法运算。

图7 本文方案的时间开销随L 的变化

本文方案共传输数据Mi、、Di、Si至服务商，通过实验测试得出的本文算法每次通信量大小与L的关系如图8 所示。从图8 可以发现，随着L增大，本文方案的通信量也随之增加。

图8 本文方案的通信量随L 的变化

5 结束语

本文设计了基于LDP 的多级资源自适应的算法推荐框架，能够灵活地为用户提供资源、隐私个性化的算法推荐。同时，将框架应用在位置PoI 频数统计任务的场景下，并在此基础上对LDP 算法进行改进，使不同用户能够选取不同的LDP 机制，且可以设定不同的隐私需求；考虑到用户的隐私偏好包含了用户的敏感信息，因此设计了后处理机制，防止服务商推测出用户的隐私偏好。最后，通过实验证明了本文方案的可行性、可用性和效率。