基于k-匿名的隐私保护计算卸载方法

赵 星 彭建华 游 伟 陈 璐

(中国人民解放军战略支援部队信息工程大学 郑州 450001)

1 引言

随着智能终端和物联网的普及，各类终端应用不断涌现，为用户带来丰富娱乐体验的同时也消耗了终端更多的计算资源和能耗[1]。移动边缘计算(Mobile Edge Computing, MEC)[2]是第5代移动通信网络(5G)[3]的重要支撑技术，通过将计算资源部署在网络边缘，空间上邻近终端用户，降低服务时延的同时也可减少终端能耗。计算卸载技术[4]作为MEC的关键技术之一，通过无线链路将计算密集型终端应用传输至邻近的MEC节点处理，利用MEC服务器充足的计算资源和能源减少终端处理任务的时延和能耗，有效提高了服务质量和用户体验。计算卸载决策指终端感知无线环境并结合自身卸载任务特性，基于不同的优化目标(降低终端能耗[5]、减少任务处理时延[6]和权衡能耗与时延[7])，选择最优的任务处理方式(本地处理、卸载到MEC节点或丢弃)。

目前针对MEC安全和隐私问题的研究多是从加密、认证等数据安全和访问控制角度防护卸载的数据内容[8]，并未充分考虑卸载决策中的隐私问题，对用户卸载的行为习惯、使用模式所导致的隐私泄露研究[9]则更少。文献[10]研究现有卸载决策发现终端在信道条件较好时会尽可能上传计算任务以减少自身能耗，攻击者可据此通过监听MEC节点上的任务卸载情况，反推出用户的使用模式和所处无线环境，甚至实现对终端的定位；文献[11]进一步分析了物联网场景中卸载决策的隐私，建立隐私模型综合考虑隐私、能耗和计算时延，基于增强学习求解；文献[12]分析了物联网场景中用户的位置隐私威胁，基于越远的服务节点越能保护用户位置隐私的原理定义隐私量，并利用深度决策后状态学习算法快速求解最优的卸载决策。文献[13]基于上述研究进一步基于任务卸载概率的显著性定义计算任务的隐私量，以此建立隐私保护计算卸载模型并求出隐私约束下的最优平均能耗。然而上述研究均考虑单个用户的隐私保护，基于计算任务的卸载频率相对于统计流行度的显著性度量用户的隐私属性，没有充分考虑不同MEC区域用户群体的不同导致隐私度量偏差。此外在多用户场景中，直接采取单用户隐私保护会使整体能耗的线性增高，降低整体服务质量。

为实现多用户场景下协同隐私保护并最小化整体能耗，本文提出一种基于k-匿名的隐私保护计算卸载方法。首先，分析卸载决策中的隐私威胁和多用户场景中防护难点，提出基于卸载任务及卸载频率的隐私约束，限制k个用户的各卸载任务实际卸载频率相近；然后，提出基于k匿名的隐私保护计算卸载模型，并用基于模拟退火的隐私保护计算卸载算法(Privacy preserving Computation Offloading algorithm based on Simulated Annealing,PCOSA)快速求得最优分组。实验结果表明，PCOSA能最小化终端能耗，且每个卸载任务都有k个用户的卸载特征相似，使攻击者无法区分出目标用户。

2 模型分析

2.1 系统模型

目前比较常见的边缘系统模型如图1所示[14]，MEC节点部署于一定区域内的多个基站或无线热点之后，为接入网络的多个终端用户提供计算卸载服务。假设系统为单位时隙 Δ ms的时隙系统，在每个时隙t内，终端可随机产生一个可卸载的任务T(t)，假定每个卸载任务平均包含b Byte，终端处理每个字节的数据需要 β个CPU循环[15]，每个任务均有时延门限ξ (t)，需在规定时延门限内处理完任务，否则只能丢弃。时隙t的计算任务的卸载结果可以是本地处理、卸载到MEC节点或丢弃，分别用指示函数IL(t) , IM(t)和 ID(t)表示。

图1 系统模型

考虑本地处理情况，假设终端的CPU频率可以根据不同的卸载决策而改变(最大值为 fmax)，时隙t 内的C P U 频率为 f(t)，则可计算得时延为DL(t)=b·β/f(t) ，终端的能耗为EL(t)=κ·f3(t)·DL(t) ，其中κ 表示CPU的能耗系数[16]。

计算任务本地处理的最优CPU频率为f∗(t)=β·b/ξ(t)， 若可以本地处理(即f∗(t)≤fmax)，则本地处理的最低能耗为(t)=κ·[f∗(t)]3·ξ(t)。

考虑卸载到MEC节点情况，假定MEC控制NAP个无线接入点覆盖1个服务区域，各无线接入设备与终端的无线信道相互独立，时隙t中第i个无线接入点的参数为：上行链路带宽 Wi，信道噪声功率密度，信道增益为(t)，终端的发射功率pi(t)( 最大值为pmax)。

2.2 隐私威胁

基于加密及认证等防护措施，假定系统中终端、基站或热点、MEC服务器均可信，攻击者直接截获卸载任务并分析其所述用户身份信息难度很大。由于MEC系统应用层的相对开放性，攻击者可利用侧信道攻击[17]的方式推测、监听MEC服务器上卸载的计算任务及卸载频率。由于用户使用终端的习惯不同，每个用户常用的终端应用及其卸载频率也一般不同，若攻击者通过其他手段掌握了目标用户的部分先验信息(如用户经常性卸载的计算任务及其大致卸载概率)，则可通过监听MEC节点上任务卸载情况并推测目标用户所在MEC节点。

用户所有可卸载的计算任务集合记为 T，用户卸载概率较高的计算任务集合记为TU,TU∈T(频率太低的卸载任务随机性较大，攻击验证难度较大，因此不作考虑，θp为考虑保护卸载任务的隐私保护门限)， TU中 各任务的卸载概率为PU，任务数量记为 NT。若攻击者已掌握某一用户u的卸载情况Tu,Pu，且能入侵MEC系统监听各用户的任务卸载情况(由于身份加密，攻击者无法直接判断出用户的真实身份)，则攻击者可统计MEC节点上一段时间内各用户的实际卸载频率，若存在一个用户的与Pu接近，则可判断该用户大概率为目标用户u，进一步进行后续的攻击和分析。参与判定的卸载任务越多(即NT越大)，卸载频率越接近，则攻击 者锁定目标用户u成功的概率越大。

3 基于k-匿名的隐私保护计算卸载方法

本节针对2.2节中分析的用户隐私威胁和多用户场景隐私保护的挑战，提出基于k-匿名的协同隐私保护计算卸载模型，然后基于模拟退火算法求解最优分组，并给出隐私约束下平均能耗最低的卸载流程。

3.1 问题建模

利用多用户场景下用户间的相似性，可不独立保护每个用户的隐私，而是基于k-匿名原理[18]，使MEC节点覆盖范围内存在k个用户的实际卸载频率相似，从而使攻击者无法从k个卸载行为相近的用户中区分出所攻击的目标用户u，整体保护k个用户的隐私。

为满足k-匿名，各用户计算卸载的隐私约束由式(1)所示，对于任意时隙t和任务用户i都存在k-1个用户j满足

其中优化目标为N个用户的平均能耗最低，式(2a)为用户i在时隙t时任务处理时间约束，式(2b)、式(2c)给出了指示函数的限制。

3.2 基于模拟退火的隐私保护计算卸载算法

为求解上述模型，本节提出基于模拟退火的隐私保护计算卸载算法(Privacy preserving Computation Offloading algorithm based on Simulated Annealing, PCOSA)， PCOSA算法分为两步，PCOSA I完成MEC节点下现有用户的分组及确定每组内防护任务数及各卸载任务的隐私约束频率, PCOSA II中各用户根据的约束完成实时的计算卸载过程。

为满足式(1)，k个用户的分组中，每个用户都需改变卸载任务(如任务m)的卸载频率至区间范围内，定义改变原始卸载频率而导致的偏离代价为

其中，pj,i表示第j个用户第i个计算任务的卸载频率。

将N个用户每k个分为一组，共有N !/k!种不同的分组方案，当N较大时常规算法无法在多项式时间内求得最优分组的解，即为NP难问题。本文基于模拟退火算法快速求解分组结果，PCOSA I先计算所有k个用户分组的代价，然后随机初始化一种分组情况并计算其总代价，最后基于SA求解总代价最小的最优分组，其流程如表1所示。PCOSA I基于SA算法求出用户的最优分组，其时间复杂度和模拟退火的参数相关，迭代次数 NSA满足T×λNSA→Tmin，在表1循环体中求偏离代价须执行次数为和N/k的二重循环，因此PCOSA I的时间复杂度为O (NSA××N/k)，为尽量求得最优分组解，迭代次数 NSA一般较大，且用户较多时N/k的值也较大，算法整体时间复杂度较高。但用户分组一般发生在用户接入网络或重新分组时，时延较不敏感，且MEC服务器也有较强的计算处理能力。

PCOSA II基于上述k-匿名分组结果及各分组中卸载任务的隐私约束频率，使每个用户在每个时隙中根据感知的无线环境、卸载任务特性，做出满足时延和隐私限制下能耗最优的卸载决策。

用NO表示截止时隙t时用户已经卸载的总次数，变量 Nm,Nm∈N表示其中任务m 的卸载次数，为用户n中任务m的隐私约束频率，则×(1+·θ)表示其隐私上界。用户n的任务m满足隐私约束下剩余的可卸载次数为

表1 PCOSA I 算法流程

上述步骤解决了隐私约束上界和能耗最优的问题，对于任务自身频率小于分组隐私均值的情况，需整体上降低用户的卸载频次 NO，使得本来出现概率较低的任务的卸载频率变高，而卸载次数越少则用户总卸载能耗越大。为此，利用假任务机制，在任务本可以卸载((t)＜(t))却因隐私约束而无法卸载时，根据式(6)选择实际卸载频率最小于隐私约束下界任务 TF，在MEC节点上产生该任务的假任务，提高其卸载频率。

综上，PCOSA II的整体流程如表2所示。具体实现中，可在用户接入网络时的认证消息中加入其计算任务及平均卸载频率的信息，不增加额外的信令开销，也保证了安全性(若认证流程已经被攻击者攻破，则再防护卸载隐私毫无意义)。MEC根据接入用户及其任务卸载频率，完成k-匿名分组，再将分组结果通过认证应答信令发送给用户。

4 仿真分析

本节利用MATLAB数值仿真方法验证上述模型和算法的有效性，模型设置如表3所示。

为模拟用户使用终端习惯的特殊性，仿真实验中为每个用户不断随机生成卸载频率为[0,0.3]之间的卸载任务，直至所有任务卸载频率之和为1，因此各用户的防护任务集合 TU、 卸载频率PU及任务数量NT均 不一样，隐私保护门限θp=0.05。

表2 PCOSA II 算法流程

实验的对比算法包括：(1)Basic算法，不考虑隐私约束式(1)，追求能耗最优的卸载决策，作为其他算法能耗表现的基准；(2)单用户隐私保护算法(Single User Privacy-preservation Algorithm,SUPA)，独立保护每个用户的隐私，使集合 TU的实际卸载频率都低于用户的原始频率 PU，隐私偏离度也设置为 θ；(3)基于贪心思想的k-匿名算法(Greedy-based K-Anonymity Algorithm,GKAA)，基于贪心思想，每次分组选择偏移量最小的分组作为最优解的子集，对剩余用户执行同样操作，直至所有用户都分完组，其余步骤同P COSA II。

4.1 算法对比

首先分析PCOSA的隐私保护效果和能耗，随机选取一用户分析其各任务的卸载结果如图2所示，参数设置为N =60,k =3,θ =0.2,T =105。PCOSA I算法所得分组结果的均值卸载频率为组内各用户的隐私约束频率，PCOSA II算法改变了各计算任务的原始卸载频率，使其实际卸载频率均在隐私保护阈值 θ的范围内，满足了k-匿名的隐私保护效果。原始频率高于隐私约束频率的任务，为最优化用户能耗，实际频率一般只略低于隐私约束上界；而原始频率低于隐私约束频率的任务，由于实际频率的提高受假任务机制影响，最终效果会有不同，原始频率越低的任务实际频率越靠近隐私约束频率。

表3 模型参数设置

图2 各任务卸载频率对比

图3 不同时隙T最小平均能耗对比

图4 各算法卸载结果对比

4.2 参数分析

本小节进一步分析各算法参数对其效果的影响，图5分析了隐私保护阈值 θ的影响，随着θ 的增大，隐私限制变小，因此如图5(a)所示GKAA和PCOSA的最小平均能耗均不断降低；同时更小的隐私限制使分组结果中用户的卸载频率有更大的变化范围，使最小偏离代价降低。从图5(b)也可看出，当θ 增大到一定程度时，最小偏离代价也可能不再降低，导致图5(a)中最小平均能耗降低变缓。

图6描述了用户数N的影响，理论分析知更多的用户意味着分组时能找到卸载表现更接近的用户，形成更好的隐私保护效果同时平均能耗也更低。图6(b)表明随着用户数N的增加，平均每个分组的最小偏离代价不断降低。由于数据源中用户各任务卸载频率的随机性，由图6(a)可知用户数对最小平均能耗影响并不大，只随着用户数增加而略微下降。

图7反映了分组大小k的影响，更多的组内用户数导致了用户间更大的差异性，使图7(b)中的平均最小偏离代价相应增大，从而导致图7(a)中的平均能耗变大。但更多的组内用户使卸载特征相似的用户更多，实现了更好的隐私保护效果，即牺牲了一定的终端能耗而换取更好用户隐私保护效果。

图5 隐私保护阈值θ 的影响

图6 用户数N的影响

图7 分组大小k的影响

5 结束语

本文针对MEC计算卸载中用户不同任务卸载频率可能暴露其隐私的问题，提出一种基于k-匿名的隐私防护方法，利用多个用户形成卸载行为相近的群组，共同防护组内用户的隐私。提出基于模拟退火的PCOSA I算法高效求出最优的分组结果及其隐私约束频率，并根据PCOSA II算法步骤实现每个时隙内具体的卸载过程。仿真结果表明，采用k-匿名原理的多用户隐私防护机制可有效防止单个用户卸载特征被攻击者锁定攻击，且保持较低的平均卸载能耗。后续可继续深入研究MEC计算卸载中的其他隐私威胁和隐私量化方式，并结合5G具体应用场景进行分析和验证。