随着电动汽车（electric vehicle, EV）的发展，针对电动汽车用户的各种第三方位置服务（location-based services，LBS）已经日益流行. 这些LBS为电动汽车用户提供个性化的功能，如智能充电^[1-2]、天气预报^[3]、智能停车^[4]和道路辅助^[5]等.

LBS通过调用电动汽车API平台提供的实时位置API来获取电动汽车用户的位置信息，如图1所示. 一个示例平台是SmartCar^[6]，它支持包括特斯拉、大众等在内的多种电动汽车制造商. API平台直接与内置在电动汽车中的蜂窝调制解调器通信，并向第三方服务提供包括位置API在内的实时API. 该平台始终使用访问控制机制来保护用户隐私，如SmartCar基于OAuth2.0授权访问. 用户必须完全信任第三方服务才能使用个性化功能， 这带来了重要的位置隐私隐患^[7-8].

图  1  实时电动汽车位置API

Figure  1.  Real-time EV location API

下载: 全尺寸图片 幻灯片

现有的研究仅关注位置隐私和LBS效用之间的权衡. 为了防止揭示用户的真实位置，位置隐私保护机制（location privacy preserving mechanism，LPPM）生成一个随机的伪位置作为报告位置，它可以形式化为给定真实位置情况下报告位置的概率密度函数（probability density function，PDF）. 一个最佳LPPM通过解决一个最优化问题，从而实现最低可容忍的LBS效用限制下的最大化位置隐私，反之亦然.

现有的技术^[9-15]无法直接应用于电动汽车的实时位置API. 第1个问题涉及到运行时间. 在现有技术中，求解最佳LPPM需要为每对真实位置和伪位置设置一个变量，例如，在给定真实位置的情况下报告伪位置的概率，这会引起巨大的计算开销. 即使候选的报告位置数量限制在不到100个，构建最佳LPPM所需的时间也超过1 h^[9]，甚至数天^[11]. 同时由于电动汽车用户的历史位置（即用户位置分布）持续更新，最佳LPPM也需要定期重建. 第2个问题涉及到现有所谓“最佳”LPPMs的最佳性. 现有的最新技术总是基于这样一个共同假设，即感兴趣区域内的所有位置都处在离散的网格上 ^[9-13,16]. 然而，社会并没有充分了解这一假设的最佳性和实用性. 假设有一个细网格和一个粗网格，粗网格中的每个单元格可以通过合并细网格中的若干单元格获得. 文献[11]指出，一个在粗网格上最佳的LPPM不一定适用于细网格. 因此，许多方法^[11,13]便基于网格越精细，隐私和效用之间的权衡就会越好的期望，这一期望可以从整体趋势中得到证实 ^[9,12-13,16]. 然而我们发现了一些意外的隐私-效用（PU）异常现象，即在精细网格上构建的最佳LPPM实现的隐私或效用可能不如在粗网格上，这与“最佳”的含义相矛盾，我们将这种意外现象称为PU异常.

本文的目标是实时构建最佳LPPMs. 我们深入研究了PU异常，并引入了粒度独立性的概念作为有效解决方法. 基于这一概念，我们提出了一个实际而新颖的机制Divide-and-Coin. 与现有技术总是计算所有位置上的完整概率分布不同，Divide-and-Coin直接生成一个报告位置. 它将输入的位置区域递归地划分为子区域，计算出这些子区域的最佳报告概率，并根据这些概率随机选择一个子区域作为新的输入区域. 如果选择的区域符合用户设置的大小约束要求，其将作为计算出的报告位置.

我们证明了Divide-and-Coin是最佳的，即生成报告位置区域的概率等于最佳LPPM在该区域报告一个位置的累积概率. 此外，由于Divide-and-Coin不需要推导所有位置上的完整概率密度函数，与现有技术相比，它在运行时间上有了巨大的改进，复杂度从至少O(${n}^{2.055}$)减少到O($\mathrm{l}\mathrm{o}\mathrm{g}n$)，其中n是报告位置的数量. 即使用户配置文件随时间变化，我们提出的机制仍然能够即时生成报告位置. 我们的实验结果显示，Divide-and-Coin可以在1 s内从城市级区域（n=${2}^{217}$=131 072）生成建筑级别的最佳报告位置.

总结一下，本文的主要贡献有3点：

1）做到能够实时构建最佳LPPM. 与现有技术相比，Divide-and-Coin将生成最佳报告位置的运行时间从至少O(${n}^{2.055}$)缩短到O($\mathrm{l}\mathrm{o}\mathrm{g}n$).

2）揭示并研究了最佳LPPMs的PU异常. 据我们所知，所有现有旨在构建最佳LPPMs的技术都受到了这一异常的影响.

3）引入了粒度独立性的概念，并作为对PU异常的有效解决方法.

1.   系统模型

在本节中，我们描述本文考虑的系统模型，这与大多数现有的研究^[9,12-13,16]是一致的. 我们还介绍了本文中使用的符号释义，总结在表1中.

表  1  符号释义

Table  1.  Notation Interpretation

符号	释义
$r,{r'},\hat{r}$	真实位置，报告位置，估计位置
$\mathcal{R},{\mathcal{R}'}$	真实位置集合，报告位置集合
$f\left({r'},r\right)$	LPPM（给定$r$报告${r'}$的概率）
$\pi \left(r\right)$	用户位于$r$的先验概率
$P\left(f,\pi \right),{P}^{\mathrm{m}\mathrm{i}\mathrm{n}},{P}^{\mathrm{o}\mathrm{p}\mathrm{t}}$	隐私，最小可忍受隐私，最佳LPPM隐私
${Q}_{\mathrm{l}\mathrm{o}\mathrm{s}\mathrm{s}}\left(f,\pi \right),{Q}_{\mathrm{l}\mathrm{o}\mathrm{s}\mathrm{s}}^{\mathrm{m}\mathrm{a}\mathrm{x}},{Q}_{\mathrm{l}\mathrm{o}\mathrm{s}\mathrm{s}}^{\mathrm{o}\mathrm{p}\mathrm{t}}$	质量损失，最大可忍受质量损失， 最佳LPPM质量损失
$\omega ,{\omega' }$	输入给LPPM的位置粒度， 由LPPM输出的位置粒度
$\mathcal{A},{c}_{\omega }^{\mathcal{A}},{C}_{\omega }^{\mathcal{A}}$	连续区域，粒度为$\omega$的单元格， 粒度为$\omega$ 的单元格集合
${r}_{\omega },r'_{\omega '},{\hat{r}}_{\omega }$	真实位置，报告位置，估计位置（对应粒度$\omega$下）
${\mathcal{R}}_{\omega },\mathcal{R}'_{\omega' }$	真实位置集合，估计位置集合（对应粒度$\omega$下）
${f}_{\omega '_{i},{\mathrm{\omega }}_{{i}}}^{\mathrm{t}\mathrm{r}}\left(r'_{\omega'_j},{r}_{{\omega }_{j}}\right)$	由粒度$\omega '_{i},{\omega }_{i}$构建的LPPM再转换到粒度$\omega'_j,{\omega }_{j}$得到的等价LPPM

下载: 导出CSV 

| 显示表格

1.1   位置隐私保护机制

我们考虑瞬时LBSs ^[7]，用户可以零星地访问这些服务，因此同一用户的2个被揭示的位置是相互条件独立的^[16]. 在不可信LBS提供商的情况下，攻击者可以获得该提供商持有的任何信息，包括用户的报告位置.

报告位置可以是用户的真实位置，也可以是由LPPM生成的伪位置. LPPM基于用户的真实位置r∈$\mathcal{R}$计算出恰当的报告位置r′∈${\mathcal{R}'}$，从而实现用户的位置隐私和LBS效用之间的平衡. 报告位置集可以与真实位置集相同（即$\mathcal{R}={\mathcal{R}'}$），也可以不同（即$\mathcal{R}$ ≠ ${\mathcal{R}'}$）^[17]. LPPM可以形式化为在给定真实位置r的情况下报告位置$r'$的概率密度函数f (r′，r)，满足

1.2   攻击者掌握的信息

攻击者试图根据他的知识推断目标用户的真实位置r. 我们假设攻击者知道用户的报告位置r′和LPPM所计算出的概率密度函数 f. 我们还假设他对用户的历史位置有一些了解，因此攻击者可以通过统计分析用户的历史信息来获取用户位置分布. 我们使用π(r)来表示用户位置分布，其代表用户在任何给定位置r∈R处的概率密度函数，其可被视为用户在位置r的先验概率.

1.3   理论上的最佳LPPM

为了评估LPPM，我们需要定义2个重要的度量标准. 使用${Q}_{\mathrm{l}\mathrm{o}\mathrm{s}\mathrm{s}}$表示质量损失，即LPPM概率密度函数 f的效用的对立面；使用P表示位置隐私. 当确定了这2个度量标准，一个最佳的LPPM便可以通过解决一个最优化问题来构建，它可以在最大可容忍的质量损失阈值下实现最高的隐私保护${Q}_{\mathrm{l}\mathrm{o}\mathrm{s}\mathrm{s}}^{\mathrm{m}\mathrm{a}\mathrm{x}}$：

或者在最小可容忍的隐私阈值${P}^{\mathrm{m}\mathrm{i}\mathrm{n}}$内实现最低的质量损失

此优化问题在大量文献[9-13,16,18-19]中被广泛使用，这些文献提出了不同的质量损失${Q}_{\mathrm{l}\mathrm{o}\mathrm{s}\mathrm{s}}$度量标准和隐私P度量标准.

1.4   现实中的近似最佳LPPM

在现实世界中，报告位置可以是连续位置平面中的任何点（形式化为$\mathcal{R}$²）. 然而，出于计算原因，在构建最佳的LPPM时，${\mathcal{R}'}$ 必须是可数集. 为了从$\mathcal{R}$²生成可数集${\mathcal{R}'}$，现有的研究始终考虑的是一个感兴趣的区域$\mathcal{A}$，该区域的大小有限，并通过指定单元格的边长将该区域映射到一个网格，并让$\mathcal{R}$或${\mathcal{R}'}$中的任何位置都成为单元格的中心 ^{[9,11-13,16-17,20-27]}.

2.   PU异常

现有方法^[11,13]总是基于一个期望，即网格越精细，隐私与效用之间的权衡就能越好. 这一期望已经通过模拟和实验得到了确认，但仅在总体趋势中成立.

在本节中，我们揭示了现有最佳LPPMs的PU异常，即通过更精细网格实现的“最佳”LPPM的隐私（或质量损失）比通过较粗网格实现的隐私更少（或质量损失更大）. 我们将这种意外行为称为隐私-效用异常（PU异常）.

2.1   参考技术

为了揭示和研究这一异常现象，我们参考了2种已经被社区广泛接受的代表性技术：基于估计距离误差构建最佳失真隐私机制的EDE程序^[16]，以及基于地理不可区分性构建最佳机制的GEO程序^[9]. 质量损失度量定义为报告位置r′和真实位置r的平均质量损失，其在EDE和GEO程序中都定义为

其中${d}_{Q}(r',r)$是$r'$和r的欧几里得距离. 然而，这些技术中的隐私度量定义并不相同.

在EDE程序中，隐私被定义为用户的无条件期望隐私:

其中${d}_{Q}\left(\hat{r},r\right)$衡量了当真实位置为r时，攻击者猜测为$\hat{r}$的损失，并以$\hat{r}$和r之间的欧氏距离来构建.

在GEO程序中，隐私被定义为

其中${d}_{P}$也以欧氏距离构建. 式（6）中的最小可容忍隐私${P}^{\mathrm{m}\mathrm{i}\mathrm{n}}$与最大隐私预算ϵ成反比，即${P}^{\mathrm{m}\mathrm{i}\mathrm{n}}$=1/ϵ. 因此，式（6）中的约束条件等价于

2.2   构建LPPMs

对于每种技术，我们构建不同网格的最佳LPPM，并比较它们所实现的隐私和效用的度量值. 为了区分不同的网格，我们使用参数$\omega$来表示网格的粒度，一个基于粒度为${\omega' }$的报告位置集${\mathcal{R}'}$以及粒度为ω的真实位置集$\mathcal{R}$构建的LPPM可以形式化为一个概率密度函数 ${f}_{{\omega' },\omega }^{\mathrm{o}\mathrm{p}\mathrm{t}}\left(r'_{\omega' },{r}_{\omega }\right)$. 为了简化计算，我们令ω′=ω.

我们考虑一个非常简单的用户位置分布${\pi }_{0}$，如图2最右侧所示，其中${\pi }_{0}$(${r}_{i}$)=${\pi }_{0}$(${r}_{j}$)=0.5. 我们还给出了一组粒度，其中任何2个粒度都相互构成上下级关系，如图2所示. 图2展示了不同粒度下用户的位置分布，$\pi_{\omega_{1\times2}}$，$\pi_{\omega_{2\times4}}$，$\pi_{\omega_{4\times8}}$，$\pi_{\omega_{{8\times16}}}$是基于粒度$\omega_{1\times2}$，$\omega_{2\times4}$，$\omega_{4\times8}$，$\omega_{{8\times16}}$并由${\pi }_{0}$转变的. 对于每个粒度，根据${\pi }_{0}$生成一个新位置分布并将${\pi }_{0}$域中的每个位置转换为该粒度下网格中的一个单元格的中心，例如，对于${\omega }_{1\times 2}$，${r}_{i}$=(0.29, 0.29)被转换为${r}_{i}$=(0.5, 0.5). 下面给出EDE LPPMs和GEO LPPMs的定义.

图  2  不同粒度下的用户位置分布

Figure  2.  User profiles with different granularities

下载: 全尺寸图片 幻灯片

1）EDE LPPMs. 对于给定的位置分布π和特定粒度ω，以及给定的${Q}_{\mathrm{l}\mathrm{o}\mathrm{s}\mathrm{s}}^{\mathrm{m}\mathrm{a}\mathrm{x}}$上限，可以通过解决式（3）中定义的优化问题来构建一个最佳LPPM，并同时满足式（1）（2）（4）（7）（8）. 我们将${Q}_{\mathrm{l}\mathrm{o}\mathrm{s}\mathrm{s}}^{\mathrm{m}\mathrm{a}\mathrm{x}}$设置为${\omega }_{1\times 2}$粒度下单元格边长的0.5倍，以构建图2中的所有用户位置分布的最佳LPPM.

2）GEO LPPMs. 对于给定的位置分布π和特定粒度ω，以及给定的${P}^{\mathrm{m}\mathrm{i}\mathrm{n}}$下限，可以通过解决式（5）中定义的优化问题来构建一个最佳LPPM，并同时满足式（1）（2）（7）（9）（10）. 我们将${P}^{\mathrm{m}\mathrm{i}\mathrm{n}}$设置为$1$，以构建图2中的所有用户位置分布的最佳LPPM.

2.3   PU异常

确定一个最佳LPPM ${f}_{\omega'_{i},{\omega }_{i}}^{\mathrm{o}\mathrm{p}\mathrm{t}}$是否在另一对粒度（$\omega'_j$,${\omega }_{j}$）下仍然是最佳的，是一项不容易解决的任务. 一个直观的想法是再构建一个最佳LPPM ${f}_{\omega'_j,{\omega }_{j}}^{\mathrm{o}\mathrm{p}\mathrm{t}}$，并比较这2个最佳LPPM所实现的隐私和效用的度量值. 然而，这2个LPPM的隐私和效用度量值不能直接进行比较，因为这些值的物理含义是由位置集合所决定的，不同粒度下的位置集合所决定的物理含义完全不同. 因此，以不同粒度构建的LPPM应该被转换到相同的粒度下进行比较.

我们现在讨论在什么情况下以及如何将某些粒度构建的LPPM进行转换. 假设有一个细网格和一个粗网格，粗网格中的每个单元格可以通过合并细网格中固定数量的单元格来获得. 基于条件概率，任何在细网格上构建的LPPM可以转换成在粗网格上的LPPM，最终可以与直接在粗网格上构建的任何LPPM进行比较. 对于给定的区域$\mathcal{A}$，粒度$\omega$确定了如何将该区域映射到一个网格. 我们使用${C}_{\omega }^{\mathcal{A}}$来表示网格内所有单元格的集合，$\omega'_j$是相对于$\omega '_{i}$的上级粒度，而${\omega }_{j}$是相对于${\omega }_{i}$的上级粒度. 对于任何的$c'^{\mathcal{A}}_{\omega'_j}$∈$C'^{\mathcal{A}}_{\omega'_j}$和${c}_{{\omega }_{j}}^{\mathcal{A}}$∈${C}_{{\omega }_{j}}^{\mathcal{A}}$，我们总是可以找到一些单元格，$c'^{\mathcal{A}}_{\omega '_{i},\alpha }\in C'^{\mathcal{A}}_{\omega '_{i}}$和${c}_{{\omega }_{i},\;\beta }^{\mathcal{A}}\in {C}_{{\omega }_{i}}^{\mathcal{A}}$，满足：

即对于任何一个存在下级粒度的单元格集合总能由有限个其下级粒度的单元格组合而成. 此外，$o\left({r'}\right)$表示r′被报告的观察事件，而a(r)表示用户位于r的实际事件. 对于任何由下级粒度构建的原始概率密度函数 ${f}_{\omega'_i,{\mathrm{\omega }}_{i}}^{\mathrm{o}\mathrm{p}\mathrm{t}}\left(r'_{\omega'_i},{r}_{{\mathrm{\omega }}_{i}}\right)$，我们可以基于条件概率计算其在上级粒度下的转换概率密度函数 ${f}_{\omega'_i,{\mathrm{\omega }}_{i}}^{\mathrm{t}\mathrm{r}}\left(r'_{\omega' _j},{r}_{{\mathrm{\omega }}_{j}}\right)$：

其中需要注意的是，带有不同下标的$r'_{\left(\cdot \right)}$和${r}_{\left(\cdot \right)}$是单元格$c'^{\mathcal{A}}_{\left(\cdot \right)}$和${c}_{\left(\cdot \right)}^{\mathcal{A}}$的中心，并且这些单元格的下标与式（11）中相应定义的下标一致.

我们在本段落揭示EDE/GEO的LPPM在$\pi_0$上存在的PU异常现象. 使用不同粒度构建的EDE/GEO LPPM被转换成${\omega }_{1\times 2}$以及连续位置域，与最佳 LPPM实现的隐私和质量损失进行比较. P（或${Q}_{\mathrm{l}\mathrm{o}\mathrm{s}\mathrm{s}}$）表示转换后的 LPPM实现的隐私（或质量损失），${P}^{\mathrm{o}\mathrm{p}\mathrm{t}}$（或${Q}_{\mathrm{l}\mathrm{o}\mathrm{s}\mathrm{s}}^{\mathrm{o}\mathrm{p}\mathrm{t}}$）表示最佳 LPPM实现的隐私（或质量损失）， 转换后的 LPPM与最佳LPPM之间的隐私（或质量损失）差异可以计算为隐私距离$\left|P-{P}^{\mathrm{o}\mathrm{p}\mathrm{t}}\right|$（或质量损失距离$\left|{Q}_{\mathrm{l}\mathrm{o}\mathrm{s}\mathrm{s}}-{Q}_{\mathrm{l}\mathrm{o}\mathrm{s}\mathrm{s}}^{\mathrm{o}\mathrm{p}\mathrm{t}}\right|$）.

结果如图3所示. 在图3（a）中，总体趋势验证了最佳EDE LPPM在细网格上有更好的隐私表现. 然而，粒度${\omega }_{4\times 8}$处存在异常. 图3（b）则说明了最佳GEO LPPM在效用上同样存在异常. EDE的效用性能趋势与GEO的隐私性能趋势相似，粒度${\omega }_{4\times 8}$上都存在异常. 因此，对于在细粒度网格上构建的最佳LPPM，无论是EDE还是GEO，都无法确保其在应用于粗粒度网格时仍然保持最佳，也无法确保其仍然满足相关约束条件.

图  3  在不同粒度上构建的最佳EDE/GEO LPPM的性能表现

Figure  3.  Performance of optimal EDE/GEO LPPMs constructed with different granularities

下载: 全尺寸图片 幻灯片

在第6节中，我们对目前技术进行了调查. 所有构建最佳LPPM的技术都部分或完全基于EDE和/或GEO程序，因此它们都受到PU异常的影响.

3.   粒度独立作为异常解决方法

本节将介绍一种PU异常的解决办法.

3.1   粒度独立

对于一个独立于粒度的真正最佳LPPM，如果使用下级粒度生成的原始概率密度函数是最佳的，那么根据式（12）计算的上级粒度下的转换概率密度函数也应该是最佳的. 这引出了我们对粒度独立性的定义：

定义1. 粒度独立. 一个最佳LPPM ${f}_{\omega '_{i},{\omega }_{i}}^{\mathrm{o}\mathrm{p}\mathrm{t}}$满足粒度独立性，当且仅当对于任何一对粒度$( \omega'_{j},{\mathrm{\omega }}_{j} )$，其中$\omega'_j$是相对于$\omega '_{i}$的上级粒度，而${\omega }_{j}$是相对于${\omega }_{i}$的上级粒度，式（13）（14）都成立.

显然，一个满足粒度独立性（granularity independence，GI）的最佳LPPM不会受到PU异常的影响. 此外，一个最佳LPPM满足粒度独立性的一个充分条件是：$\mathcal{R}$和${\mathcal{R}'}$都不受粒度的影响. 为了满足这一条件，一个合理的设置是：

1） $\mathcal{R}$是一个有限的兴趣点集合（POIs）；

2）${\mathcal{R}'}$是一个感兴趣的位置区域（一个无限不可

数的连续位置集合）.

3.2   实现粒度独立的挑战

考虑到可计算性，将上述设置应用于实际程序并不是一件容易的事情. 如果将$\mathcal{R}$设置为有限的兴趣点（POIs）集合，将${\mathcal{R}'}$设置为感兴趣的区域$\mathcal{A}$，我们可以修改约束条件式（1）、质量损失和隐私为：

给定一个名为π的位置分布和一个名为${Q}_{\mathrm{l}\mathrm{o}\mathrm{s}\mathrm{s}}^{\mathrm{m}\mathrm{a}\mathrm{x}}$的上限，理论上可以通过解决式（3）中定义的优化问题来构建最佳的EDE+GI LPPM，并同时满足式（2）（4）（15）（16）（17）的条件. 类似地，原则上也可以构建GEO+GI LPPM.

然而，出于可计算性原因，这样的程序在实际应用中并不可行. 该程序需要为每对$r\in \mathcal{R}$和${r'}\in {\mathcal{R}'}$都引入一个变量，而当${\mathcal{R}'}$是一个无限集时，就会产生无限数量的变量. 因此，最优化问题无法在多项式时间内求解.

3.3   EDE+GI程序作为衡量标准

我们解决如下EDE+GI程序的计算性挑战. 式（16）中的质量损失和式（17）中的隐私都具有一个有趣且重要的特性，对于${\mathcal{R}'}$的任何给定划分$\mathcal{P}$，可以通过累积计算$\mathcal{P}$中每个元素的质量损失和隐私来计算质量损失和EDE隐私. 假设$\mathcal{P}=\{{\mathcal{A}}_{1},{\mathcal{A}}_{2},… ,{\mathcal{A}}_{K}\}$是${\mathcal{R}'}$的一个划分，我们总有

其中${Q}_{\mathrm{l}\mathrm{o}\mathrm{s}\mathrm{s},i}$和${P}_{i}$被定义为使用${\mathcal {A}}_{{i}}$分别获得的质量损失和隐私

这一特性意味着，尽管对于EDE+GI来说，无法解决最优化问题以获得报告任何${r'}\in {\mathcal{R}'}$的最佳概率密度函数，但我们仍然可以获得报告${\mathcal{R}'}$任何一部分的最佳概率密度函数. 这个概率密度函数可以用来生成一个位置区域${\mathcal{A}}_{{i}}\in \mathcal{P}$，而不是一个位置点${r'}\in {\mathcal{R}'}$. 在用户必须报告一个点位置的情况下，我们可以使用${\mathcal{A}}_{{i}}$的中心来代表${\mathcal{A}}_{{i}}$. 同时，由于划分$\mathcal{P}$并不唯一，$\mathcal{P}$中的位置区域${\mathcal{A}}_{{i}}$的面积也可以被限制在某个阈值内以保证使用位置区域的中心来代表位置点所导致的误差在用户的可接受范围内. 我们提出EDE+GI程序作为一个衡量标准：给定用户位置分布$\pi$、划分$\mathcal{P}$和上限${Q}_{\mathrm{l}\mathrm{o}\mathrm{s}\mathrm{s}}^{\mathrm{m}\mathrm{a}\mathrm{x}}$，一个最佳LPPM ${f}_{\mathcal{P}}^{\mathrm{o}\mathrm{p}\mathrm{t}}$可以通过解决下述最优化问题构建

该程序实现了最佳的权衡，通过该程序构建的任何LPPM ${f}_{\mathcal{P}}^{\mathrm{o}\mathrm{p}\mathrm{t}}$都是最佳的.

定理1. 对于任何划分$\mathcal{P}$，由EDE+GI程序构建的位置隐私保护机制${f}_{\mathcal{P}}^{\mathrm{o}\mathrm{p}\mathrm{t}}$都是最佳的，即始终存在一个最佳LPPM ${f}^{\mathrm{o}\mathrm{p}\mathrm{t}}$，它是EDE+GI程序的解，满足

证明. 假设${f}_{\mathcal{P}}^{\mathrm{o}\mathrm{p}\mathrm{t}}$是实际EDE+GI程序的任意解，我们可以找到${f}^{\mathrm{o}\mathrm{p}\mathrm{t}}$. 考虑一个新的程序，它使用一个新的约束条件式（27）作为EDE+GI程序的约束. 令${f}^{\mathrm{o}\mathrm{p}\mathrm{t}}$是这个新程序的解，我们现在证明${f}^{\mathrm{o}\mathrm{p}\mathrm{t}}$必定也是EDE+GI程序的解. 首先，若${f}^{\mathrm{o}\mathrm{p}\mathrm{t}}$不是EDE+GI程序的解，这意味着存在一个LPPM ${f'}$满足条件：

我们可以基于${f'}$计算LPPM $f'_{\mathcal{P}}$：

很明显，$f'_{\mathcal{P}}$满足式（25）（26）中的约束条件. 此外，根据式（4）（18）（20），$f'_{\mathcal{P}}$也满足式（23）（24）中的约束. 根据式（19）（21）（27），$f'_{\mathcal{P}}$实现的隐私大于${f}_{\mathcal{P}}^{\mathrm{o}\mathrm{p}\mathrm{t}}$，这与式（22）中的定义相矛盾. 因此，我们得出结论，${f}^{\mathrm{o}\mathrm{p}\mathrm{t}}$也是EDE+GI程序的解. 证毕.

4.   即时的最佳隐私保护机制

在本节中，我们提出一种名为Divide-and-Coin的即时最佳隐私保护机制，用于报告位置的即时生成.

4.1   基本概念

Divide-and-Coin不是一个构建LPPM的程序. 它本身就是一个LPPM，并以迭代的方式基于真实位置随机生成一个报告位置区域，如图4所示. 假设用户能够指定一个感兴趣的区域${\mathcal{R}'}$和一个报告区域大小的上限${S}^{\mathrm{m}\mathrm{a}\mathrm{x}}$. Divide-and-Coin保证生成一个大小不会超过${S}^{\mathrm{m}\mathrm{a}\mathrm{x}}$报告区域. 假设用户位于${r}_{0}$. 首先，考虑${\mathcal{R}'}$的一个划分$\mathcal{P}$，再以${f}_{\mathcal{P}}^{\mathrm{o}\mathrm{p}\mathrm{t}}\left({\mathcal{A}}_{i},{r}_{0}\right)$的概率随机选择一个元素${\mathcal{A}}_{i}\in \mathcal{P}$. 然后检查这个元素的大小（${\mathcal{A}}_{i}$同样是一个区域）. 如果${\mathcal{A}}_{i}$的大小不超过${S}^{\mathrm{m}\mathrm{a}\mathrm{x}}$，那么就报告${\mathcal{A}}_{{i}}$；否则，用户考虑区域${\mathcal{A}}_{{i}}$的新划分，并选择这个新划分中的一个元素${\mathcal{A}'_i}$. 上述步骤以迭代方式执行，生成一个最终报告区域.

图  4  Divide-and-Coin概述图

Figure  4.  Overview of Divide-and-Coin

下载: 全尺寸图片 幻灯片

4.2   最佳机制：Divide-and-Coin

Divide-and-Coin主要由3个迭代执行的操作组成：$Divide\left(\right)$操作将给定区域划分为子区域，Program()操作构建报告子区域的最佳概率密度函数，Coin()操作随机选择一个子区域.

1）Divide . 其以区域${\mathcal{R}'}\subset {R}^{2}$作为输入，输出区域${\mathcal{R}'}$的一个划分$\mathcal{P}$. 为了保证正确性，Divide操作确保对于相同的输入始终生成相同的输出. 为了降低时间复杂度，它总是将1个区域划分为2个大小相同的子区域.

2）Program . 其以Divide操作生成的划分$\mathcal{P}$、位置分布$\pi$、真实位置${r}_{0}$、当前迭代的质量损失上限${Q}_{\mathrm{l}\mathrm{o}\mathrm{s}\mathrm{s}}^{\mathrm{m}\mathrm{a}\mathrm{x}}$以及上一轮迭代的${f}_{\mathcal{P}}$作为输入（记为${f}^{\mathrm{t}\mathrm{e}\mathrm{m}\mathrm{p}}\left(r\right)$），输出为本轮迭代划分$\mathcal{P}$上的最佳分布${f}_{\mathcal{P}}$. 其通过解决式（22）中定义的最优化问题得到，同时满足式（23）（24）（25）以及

3）Coin . 它的输入是由Divide和Program操作分别生成的$\mathcal{P}$和${f}_{\mathcal{P}}$. Coin 基于${f}_{\mathcal{P}}$随机选择$\mathcal{P}$中的一个元素（区域${\mathcal{A}}_{i}\in \mathcal{P}$）进行输出，该区域${\mathcal{A}}_{i}$成为下一次迭代中Divide的输入区域.

我们使用${f}^{\mathrm{D}\&\mathrm{C}}\left({r'},r\right)$来表示Divide-and-Coin的隐式概率密度函数. 其输入包括感兴趣区域${\mathcal{R}'}\subset {R}^{2}$、用户位置分布$\pi$、真实位置${r}_{0}\in \mathcal{R}$，输出区域大小上限${S}^{\mathrm{m}\mathrm{a}\mathrm{x}}$、估计的质量损失${Q}_{0}$的上限. 其输出是一个区域${\mathcal{A}'}\subseteq {\mathcal{R}'}$.

我们的最终机制Divide-and-Coin包括7个步骤.

1）初始化.在第1次迭代中，${Q}_{\mathrm{l}\mathrm{o}\mathrm{s}\mathrm{s}}^{\mathrm{m}\mathrm{a}\mathrm{x}}$设置为${Q}_{0}$，${f}^{\mathrm{m}\mathrm{a}\mathrm{x}}\left(r\right)$对所有$r\in \mathcal{R}$都设置为1.

2）退出.当区域${\mathcal{A}'}$的大小不再大于${S}^{\mathrm{m}\mathrm{a}\mathrm{x}}$，退出并报告区域${\mathcal{A}'}$.

3）更新区域$\mathcal{A}$.构建步骤2中不满足要求的区域${\mathcal{A}'}$的新划分$\mathcal{P}$，计算划分$\mathcal{P}$上最佳分布${f}_{\mathcal{P}}$，并基于该分布随机选择该划分中的某个元素.

4）更新${f}^{\mathrm{t}\mathrm{e}\mathrm{m}\mathrm{p}}$.暂存本轮迭代的最佳分布.

5）更新${Q}_{\mathrm{l}\mathrm{o}\mathrm{s}\mathrm{s}}^{\mathrm{m}\mathrm{a}\mathrm{x}}$.${Q}_{\mathrm{l}\mathrm{o}\mathrm{s}\mathrm{s}}^{\mathrm{m}\mathrm{a}\mathrm{x}}$取决于步骤3所选择的元素.

6）计算报告区域$\mathcal{A}$的累积概率分布${f}^{\mathrm{D}\& \mathrm{C}}$并更新${\mathcal{A}'}$.

7）返回步骤2.

Divide-and-Coin本身是一个LPPM，可以形式化为一个隐式概率密度函数${f}^{\mathrm{D}\& \mathrm{C}}\left({r'},r\right)$. Divide-and-Coin基于用户的真实位置${r}_{0}$生成一个区域${\mathcal{A}'}$作为报告位置，并可以保证${\mathcal{A}'}$的大小不会超过参数${S}^{\mathrm{m}\mathrm{a}\mathrm{x}}$. Divide-and-Coin不需要计算完整的分布${f}^{\mathrm{D}\& \mathrm{C}}$. 它根据真实位置${r}_{0}$以及概率${f}^{\mathrm{D}\& \mathrm{C}}\left({\mathcal{A}'},{r}_{0}\right)$生成报告位置${\mathcal{A}'}$，概率${f}^{\mathrm{D}\& \mathrm{C}}\left({\mathcal{A}'},{r}_{0}\right)$可以通过计算每次迭代中选择一个元素的概率乘积来获得，如式（40）中所示. 概率${f}^{\mathrm{D}\& \mathrm{C}}\left({\mathcal{A}'},{r}_{0}\right)$描述了报告${\mathcal{A}'}$中每个点位置的累积概率：

4.3   Divide-and-Coin的优势

Divide-and-Coin具有3个优点：

1）实现最佳的权衡. Divide-and-Coin是最佳的，因为它等于最佳概率密度函数在所有${r'}$∈${\mathcal{A}'}$ 上的累积概率，根据定理2给出.

定理2. Divide-and-Coin是最佳的，即对于任何可能的报告区域${\mathcal{A}'}$（可能的程序输出）和任何真实位置${r}_{0}$，始终存在一个最佳LPPM${f}^{\mathrm{o}\mathrm{p}\mathrm{t}}$，它是EDE+GI程序的解，满足：

证明. 由于Divide操作只能为相同的区域生成一个划分，我们可以假设Divide-and-Coin机制迭代n次才最终输出${\mathcal{A}'}$. 进一步假设在第k次迭代中，由Coin操作生成的选定区域是$\mathcal{A}'_{k}$. 根据定理1，${f}^{\mathrm{D}\& \mathrm{C}}\left(\mathcal{A}'_{1},{r}_{0}\right)$是最佳的. 对于$1\le k < n$，如果${f}^{\mathrm{D}\& \mathrm{C}}\left(\mathcal{A}'_{k},{r}_{0}\right)$是最佳的，根据式（36）（38）（39）和命题1证明 ${f}^{\mathrm{D}\& \mathrm{C}} \left(\mathcal{A}{\mathcal{{'}}}_{k+1},{r}_{0}\right)$也是最佳的，从而${f}^{\mathrm{D}\& \mathrm{C}}\left({\mathcal{A}'},{r}_{0}\right)$是最佳的.证毕.

2）从不出现PU异常. Divide-and-Coin满足粒度独立性，（根据定理2出发）因此从不出现PU异常.

3）较低的计算开销. 我们将Divide-and-Coin的时间复杂度与传统的EDE程序和EDE+GI程序进行比较. 我们假设可能的报告位置数为n，真实位置数为$m < <n$. 我们进一步假设${S}^{\mathrm{m}\mathrm{a}\mathrm{x}}$不会超过EDE程序中的单元格大小. 根据文献[28]，EDE程序和EDE+GI程序的时间复杂度不小于$O\Big({m}^{2\tfrac{1}{18}}{n}^{2\tfrac{1}{18}}\Big)\approx O\left({m}^{2.055}{n}^{2.055}\right)= O\left({n}^{2.055}\right)$. 对于Divide-and-Coin，它迭代$\mathrm{l}\mathrm{o}\mathrm{g}\;n$次来生成最后的输出，每次迭代的时间复杂度只有$O\left({m}^{2.055}\right)$. 因此，整个程序的时间复杂度为$O\left({m}^{2.055}\mathrm{log}\;n\right)=O\left(\mathrm{log}\;n\right)$.

4.4   实现

我们将Divide-and-Coin实现为C++中的一个位置隐私工具包. 基于此工具包，我们开发了一个由位置API和Divide-and-Coin机制组成的LPPM服务器，如图5所示. 该LPPM 服务器需要用户授权来访问电动汽车API平台，因此其实际上是一个可信的位置服务提供商（LBS），可以从API平台获取实时的真实位置信息. 当用户访问其他LBS时，该LBS无需借助电动汽车API平台授权来访问用户的真实位置信息，而是实时获取由LPPM服务器提供的报告位置.

图  5  电动汽车场景中使用Divide-and-Coin框架

Figure  5.  Framework of using Divide-and-Coin in EV scenarios

下载: 全尺寸图片 幻灯片

5.   评　　估

在本节中，我们评估PU异常的影响来验证Divide-and-Coin的最佳性并评估其运行性能. 设置${Q}_{\mathrm{l}\mathrm{o}\mathrm{s}\mathrm{s}}^{\mathrm{m}\mathrm{a}\mathrm{x}}$为单元格边长的$0.869$倍^[16]来构建最佳的EDE LPPMs，并将${P}^{\mathrm{m}\mathrm{i}\mathrm{n}}$设置为$1$^[9]来构建最佳的GEO LPPMs.

5.1   实验配置

所有实验运行在操作系统为Ubuntu 16.04的台式机上，该台式机配置了7.7 GB内存和一颗i7-6700CPU@ 3.40 GHz. 比较程序基于C++实现. 实验共用到4种位置分布数据集来评估PU异常对 EDE程序^[10]和GEO程序^[9]的影响以及本文算法的最佳性：

1）3种假定的位置分布，如图6所示；

图  6  3个假定的位置分布 $\pi_{_1}$，${\pi }_{_2}$ ，${\pi }_{_3}$均匀分布在黑色单元格上

Figure  6.  Three assumed profiles $\pi_{_1}$, ${\pi }_{_2}$ and ${\pi }_{_3}$distribute uniformly over the dark cells

下载: 全尺寸图片 幻灯片

2）6个随机生成的位置分布；

3）100个随机生成的位置分布，每个大小为16×16个单元格，包含64个随机真实位置；

4）GeoLife GPS轨迹数据集^[29]，包含182个用户的17 621条轨迹.

5.2   PU异常的影响

我们通过比较最佳LPPMs和转换后的LPPMs的隐私和效用性能来评估PU异常对EDE程序^[10]和GEO程序^[9]的影响.

对于图6中3种假定的位置分布进行的评估，我们考虑2种不同的粒度，即${\omega }_{9\times 9}$和${\omega }_{3\times 3}$. 我们根据式（12）将基于粒度${\omega }_{9\times 9}$构建的最佳LPPMs转换为粒度${\omega }_{3\times 3}$的LPPMs，以便与基于粒度${\omega }_{3\times 3}$构建的最佳LPPMs进行比较. 隐私比和质量损失比如图7所示. 如果一个转换后的LPPM是最佳的，那么隐私和质量损失的比率都应该是1. 我们可以发现，最佳的EDE LPPMs和最佳的GEO LPPMs都受到PU异常的影响，而转换后的LPPMs始终在隐私方面表现更好但在效用方面表现更差，这是因为这些位置分布中的真实位置彼此相近.

图  7  由${\omega }_{9\times 9}$转换的LPPM与由${\omega }_{3\times 3}$构建的最佳LPPM在隐私比以及质量损失比

Figure  7.  Ratios of privacy and quality loss achieved by the transformed LPPMs from ${\omega }_{9\times 9}$and the optimal LPPMs with ${\omega }_{3\times 3}$

下载: 全尺寸图片 幻灯片

在使用100个随机位置分布的评估中，我们旨在评估PU异常对最佳EDE/GEO LPPMs的平均影响. 我们考虑4种粒度，即${\omega }_{16\times 16}$，${\omega }_{8\times 8}$，${\omega }_{4\times 4}$，${\omega }_{2\times 2}$. 不同粒度的最佳LPPMs都被转换为${\omega }_{2\times 2}$以进行比较. 结果如图8所示，使用更精细的网格构建的最佳LPPM不一定在较粗的网格上仍然保持最佳，并且其隐私保护和质量损失都不能保证.

图  8  使用100个随机位置分布绘制的隐私率和质量损失率的箱线图

Figure  8.  Boxplot of the privacy ratio and quality loss ratio using 100 random profiles

下载: 全尺寸图片 幻灯片

我们还使用真实用户位置分布来评估PU异常的影响. 同样，我们考虑4种粒度，即${\omega }_{16\times 16}$，${\omega }_{8\times 8}$，${\omega }_{4\times 4}$，${\omega }_{2\times 2}$. 使用${\omega }_{16\times 16}$粒度的单元格的边长约为496 m，结果如图9所示. 我们使用${P}_{\mathrm{E}\mathrm{D}\mathrm{E}}$和${P}_{\mathrm{G}\mathrm{E}\mathrm{O}}$来区分EDE隐私和GEO隐私. 可以发现，对于最佳EDE LPPMs来说，${Q}_{\mathrm{l}\mathrm{o}\mathrm{s}\mathrm{s}}$的值应等于${Q}_{\mathrm{l}\mathrm{o}\mathrm{s}\mathrm{s}}^{\mathrm{m}\mathrm{a}\mathrm{x}}$，对于最佳GEO LPPMs来说，实现的隐私应等于${P}^{\mathrm{m}\mathrm{i}\mathrm{n}}$. 所有转换LPPMs都不是最佳的，因此EDE和GEO都受到了PU异常的影响.

图  9  使用真实用户位置分布由转换后 LPPM和最佳 LPPM实现的隐私率和质量损失率

Figure  9.  Privacy ratio and quality loss ratio achieved by transformed LPPMs and optimal LPPMs using real user profile

下载: 全尺寸图片 幻灯片

5.3   Divide-and-Coin的最佳性

我们设计了实验来验证Divide-and-Coin的隐式概率密度函数是否是最佳概率密度函数. 实验方法为判断在给定真实位置的情况下生成报告位置的概率与由EDE+GI程序构建的最佳LPPM是否一致. 我们生成了6个随机位置分布，其中1个如图10所示（其余类似，不再详细描述），每个真实位置的先验概率标注在单元格上. 我们使用Divide-and-Coin为每个真实位置生成一个概率密度函数. 在Divide-and-Coin执行的每轮迭代中，我们获得2个子区域的概率. 然后，对于每个子区域，我们继续执行Divide-and-Coin以构建2个更小的子区域，并获得相应的概率. 最终报告一个子区域的概率是选择其父区域的概率和在选择其父区域的条件下选择它的条件概率的乘积. 最后，我们可以计算出报告任何位置的概率，实现了最佳隐私保护的最终概率密度函数，如图11所示.

图  10  一个随机生成的用户位置分布

Figure  10.  A random generated user profile

下载: 全尺寸图片 幻灯片

图  11  Divide-and-Coin 的最佳性评估

Figure  11.  Evaluation on the optimality of Divide-and-Coin

下载: 全尺寸图片 幻灯片

5.4   Divide-and-Coin的运行时间

EDE程序和EDE+GI程序的时间复杂度都是$O\left({\left|\mathcal{R}\right|}^{2.055}{\left|{\mathcal{R}'}\right|}^{2.055}\right)$，而Divide-and-Coin的时间复杂度仅为$O\left({\left|\mathcal{R}\right|}^{2.055}\mathrm{log}\left|{\mathcal{R}'}\right|\right)$. 我们考虑使用GeoLife数据集作为用户位置分布，并进行实验以评估Divide-and-Coin的运行时间. 这些真实位置是用户的POIs，因此$\left|\mathcal{R}\right|$不应该很大. 在这里，我们提供一个有关$\mathcal{R}$合理规模的计算. 假设可以为用户位置分布设置一个阈值${\pi }^{\mathrm{m}\mathrm{i}\mathrm{n}}$，来代表位置分布中的最小概率. 例如，${\pi }^{\mathrm{m}\mathrm{i}\mathrm{n}}$=0.001表示如果用户位于某个位置的概率小于0.001，那么我们便不将该位置视为真实位置. 然后，我们假定“80-20原则”，即80%的真实位置占据了位置分布中20%的概率. 基于这些假设，我们得出结论，如果${\pi }^{\mathrm{m}\mathrm{i}\mathrm{n}}$ = 0.001，则$\left|\mathcal{R}\right| < \left(20\%/{\pi }^{\mathrm{m}\mathrm{i}\mathrm{n}}\right)/80\%=250$. 如果${\pi }^{\mathrm{m}\mathrm{i}\mathrm{n}}$= 0.005，则$\left|\mathcal{R}\right| < 50$. 我们设置$50 \le \left|\mathcal{R}\right|\le 250$. 我们将Divide-and-Coin的平均运行时间与通过EDE+GI程序构建的最佳LPPM的运行时间进行比较，结果如图12和图13所示. Divide-and-Coin的运行时间要小得多，而且不太受$\left|{\mathcal{R}'}\right|$值的影响，这与我们前文对时间复杂度的分析一致.

图  12  在$\left|\mathcal{R}\right|$=256时不同$\left|{\mathcal{R}'}\right|$的运行时间

Figure  12.  Running time on $\left|{\mathcal{R}'}\right|$ with $\left|\mathcal{R}\right|$=256

下载: 全尺寸图片 幻灯片

图  13  在$\left|{\mathcal{R}'}\right|$=1 024时不同$\left|\mathcal{R}\right|$的运行时间

Figure  13.  Running time on $\left|{\mathcal{R}}\right|$ with $\left|\mathcal{R}'\right|$= 1 024

下载: 全尺寸图片 幻灯片

此外，我们进一步评估Divide-and-Coin是否能够实时执行. 图14展示了在不同$\left|\mathcal{R}\right|$值的情况下Divide-and-Coin的运行时间与迭代次数的关系. 我们考虑一个极端情况，即报告位置的数量$\left|{\mathcal{R}'}\right|={2}^{17}= 131\; 072$（对于现有技术几乎无法计算），以及真实位置的数量$\left|\mathcal{R}\right|=256$（这表明即使某个真实位置的概率小于0.001，也会被考虑在内）. 在这种情况下，Divide-and-Coin能够从一个${2}^{27}\;{\mathrm{m}}^{2}$（约134.22 $\mathrm{k}{\mathrm{m}}^{2}$）的城市级区域中生成一个${2}^{10}\;{\mathrm{m}}^{2}$（约0.001 km²）的建筑级位置. 实验结果表明，即使在这种极端条件下，Divide-and-Coin仍能在1 s内完成.

图  14  Divide-and-Coin 在不同$\left|\mathcal{R}\right|$的运行时间

Figure  14.  Running time of Divide-and-Coin on $\left|\mathcal{R}\right|$

下载: 全尺寸图片 幻灯片

6.   相关工作

如何保护用户的位置隐私在很大程度上取决于LBS的访问方式. 如果一个LBS被频繁且匿名地访问，位置隐私就是避免被跟踪的能力^[30-34]；如果一个LBS被偶尔且不匿名地访问，位置隐私就是避免暴露用户真实位置的能力^{[9,11-13,16-17,20-27]}. 我们专注于后一种情况.

6.1   隐私概念和LPPMs

考虑到用户的位置分布可以获得的情况，一个传统的位置隐私概念是位置熵^[20-22]，其描述了攻击者的不确定性. Shokri等人^[16]引入了攻击者不正确性作为不确定性和不准确性的结合，并提出了估计距离误差（EDE）作为隐私的概念，这已经成为该领域的标准. 在另一方面的研究中，考虑用户个人资料是否未知（或不准确^[35]），Andrés等人^[17]基于2维空间下差分隐私（DP）^[36]的一般化^[37]引入了地理不可区分性（GEO），它定义了位置隐私为攻击者在任何2个位置上的条件后验概率之间的最大差异. 尽管GEO不完美，因为它使用参数ϵ量化隐私，而这可能会对隐私级别^[27,38]产生误导，但它已经成为位置隐私的另一个正式概念，并被许多研究^[23-25]采用. EDE和GEO的结合将同时保护位置免受贝叶斯推断攻击和侧信道推断攻击^[26].

6.2   最佳LPPMs

Shokri等人^[16]通过考虑攻击者的贝叶斯建模，提出了一个线性程序来构建最佳的EDE LPPM，并随后使用Stackelberg贝叶斯博弈框架提出了一个改进的程序^[10]. Chatzikokolakis等人^[9,11]提出了一个用于构建最佳GEO LPPM的程序. 文献[12]构建的LPPM在满足GEO约束的同时实现了最佳的EDE，而文献[13]构建的LPPM则在保持EDE最佳的同时实现了最大化条件熵（CE）. 根据不可区分性、DP和互信息之间的关系^[39]，基于熵的隐私概念还可以与GEO或DP相结合. 一些研究也考虑报告位置在连续平面上的情况^[11,13,17]. 然而，它们要么无法构建最佳的LPPM^[11,17]，要么仍然需要将输出限制为离散的字母表^[11,13].

6.3   电动汽车用户的位置隐私

Campolo等人^[40]提出了一个综合的基于智能手机的平台，该平台检索车辆数据并提供实时API. 通过使用基于身份的访问控制机制，该平台保护了包括位置在内的所有敏感数据. Gao等人^[41]提出了一种使用区块链来保护位置隐私的安全支付方案. Pazos-Revilla等人^[42]提出了一种使用物理层辅助来保护位置隐私的安全充电方案. Zhang等人^[8]提出了一个保护位置隐私的认证方案.

7.   总　　结

在这项工作中，我们的目标是为电动汽车场景中的实时位置API构建最佳的位置隐私保护机制（LPPM）. 我们揭示了现有最佳LPPM的PU异常现象，并将其称为PU异常. 为了解决这种异常现象，我们将粒度独立性的概念正式转化为一种最佳性的属性. 最后，我们提出了一种可以实时构建的最佳机制Divide-and-Coin.

作者贡献声明：董恺提出了算法思路和实验方案并负责撰写论文；王立夫负责完成实验并参与撰写论文；凌振参与算法思路设计与修改论文.