移动边缘计算中隐私感知的在线任务卸载机制.pdf

第 8 卷 第 4 期 信 息 安 全 学 报 Vol.8 No.4 2023 年 7 月 Journal of Cyber Security July 2023 通讯作者:叶阿勇,博士,教授,博士生导师 Email:。本课题得到资助国家自然科学基金(No.61972096,No.61771140,No.61872088,No.61872090),福建省科技厅高校产学合作计划项目(No.2022H6025)。收稿日期:2022-01-07;修改日期:2022-02-21;定稿日期:2023-04-18 移动边缘计算中隐私感知的在线任务卸载机制 邓慧娜邓慧娜1,2,叶阿勇叶阿勇1,2,刘燕妮1,2,孙明辉1,2 1福建师范大学计算机与网络空间安全学院 福州 中国 350117 2福建省网络安全与密码技术重点实验室 福州 中国 350117 摘要 移动边缘计算是一种新型的计算范式,它将云计算能力从集中式云分布到网络边缘,可有效解决云计算实时性低及移动终端计算能力不足等问题。但由于用户移动的不确定性以及边缘服务器的覆盖范围的有限性,使得实现高效率的任务卸载面临挑战,并且现有可用性优先的任务卸载算法容易造成用户轨迹隐私泄露。针对上述问题,本文考虑了迁移成本、轨迹隐私与可用性三者之间的矛盾关系,基于信息论提出一种高可用性的在线隐私感知任务卸载机制。首先,基于真实轨迹与发布轨迹之间的互信息量化轨迹隐私泄露程度,并将该任务卸载问题转换为多目标优化问题;然后,进一步提出一种基于马尔可夫链的任务卸载方案来求解该优化问题;最后,在多约束场景下设计了面向设备端的轻量级在线任务卸载算法,解决了在迁移成本约束下轨迹隐私与感知时延的加权平衡问题,以及迁移成本与感知时延双重约束下的轨迹隐私泄露最小化问题。实验结果表明,本文提出的隐私感知任务卸载方案在不同约束场景下的安全性均优于其他方案,能以较低的感知时延实现轨迹隐私保护,适用于资源受限的移动设备进行快速决策与卸载。关键词 移动边缘计算;轨迹隐私;迁移成本;可用性;任务卸载 中图法分类号 TP391 DOI 号 10.19363/J10-1380/tn.2023.07.09 Privacy-aware online task offloading mechanism in mobile edge computing DENG Huina1,2,YE Ayong1,2,LIU Yanni1,2,SUN Minghui1,2 1 College of computer and Cyber Security,Fujian Normal University,Fuzhou,China,350117 2 Fujian Provincial Key Laboratory of Network Security and Cryptology,Fuzhou,China,350117 Abstract Mobile edge computing is a new computing paradigm,it pushes the computing power of cloud servers from the upper-layer centralized cloud to the lower-layer network edge,which can effectively solve the problems of low real-time performance of cloud computing and insufficient computing power of mobile devices.But due to the uncer-tainty of the users movement and the limited signal coverage of the edge server,it has become a very challenging problem to get the task offload to be completed efficiently.At the same time,there are currently some usability-first task offloading algorithms,which ignore user trajectory privacy and security in order to obtain the lowest delay.In view of these challenges,we considered the contradictory relationship among the three aspects of migration cost,trajectory pri-vacy,and usability.And we propose a privacy-aware online task offloading mechanism with high availability on the basis of information theory.First of all,we quantify the degree of leakage of trajectory privacy by calculating the mu-tual information between the real trajectory and the released trajectory,and formulate this task offloading problem as a multi-objective optimization problem.Next,we further propose a task offloading scheme based on Markov chain to solve this optimization problem.At last,we designed a lightweight online task offloading algorithm for the device side in a multi-constraint scenario.We solve the weighted balance problem between trajectory privacy and perceived delay under the constraints of migration cost,and the problem of minimizing trajectory privacy leakage under the dual con-straints of migration cost and perceived delay.Our experimental results show that,the privacy-aware task offloading scheme proposed in this paper is more secure than other schemes in different constrained scenarios.It can realize tra-jectory privacy protection while ensuring low perception delay,and it is suitable for fast decision-making and offload-ing on those mobile devices with limited resources.Key words mobile edge computing;track privacy;migration cost;usability;task offloading 邓慧娜 等:移动边缘计算中隐私感知的在线任务卸载机制 127 1 引言 移动边缘计算1-2(Mobile Edge Computing,MEC)是一种随着 5G 技术发展衍生出的新技术,它通过将云计算能力和 IT 服务环境下沉到移动通信网络边缘,就近向用户提供服务,用户通过无线通信信道直接将计算任务卸载到移动设备周围的边缘服务器上,从而构建出一个具备高性能、低时延与高带宽的电信级服务环境3。目前已经在许多现实场景中得到应用,例如:智慧工厂、智能电网、智能驾驶、健康医疗、娱乐和数字媒体4-6,MEC 技术能在满足计算密集型应用的计算需求的同时保证极小的处理时延7。MEC技术提高了用户的体验质量,但MEC系统中不合理的任务卸载策略会导致服务器空闲或者过载。现有的任务卸载策略虽然考虑了计算资源、隐私、时延、能耗、成本等限制因素,但仍以下几个问题没有得到解决:(1)用户的移动轨迹易暴露。可用性优先的调度机制往往将任务卸载到最近的边缘服务器,以获得最小通信时延,但也容易暴露用户移动轨迹。如图 1 所示,攻击者根据路网信息以及用户连续接入的服务器位置,就可以知道用户的家庭住址以及去哪个医院的隐私信息。(2)轨迹隐私、迁移成本8与可用性三者之间相互制约。为了获得更低的时延,用户设备在快速移动过程中会通过频繁的迁移将任务卸载到最近的服务器,而计算任务在多个服务器之间迁移时会消耗大量网络资源与能源,造成服务提供商较大的迁移成本压力。同时攻击者根据现有卸载机制易获得用户的敏感隐私信息,而进行隐私保护则要选择距离更远的服务器,此时会牺牲一定的可用性以及负担更高的迁移成本。图 1 用户移动轨迹泄露图 Figure 1 Diagram of user trajectory privacy leak 因此,本文研究在多场景下用户移动卸载过程中受迁移成本约束的任务卸载问题,主要贡献为以下 3 个方面:1)考虑了迁移成本、轨迹隐私与可用性三者之间的矛盾关系,引入互信息量化隐私泄露度,将任务卸载问题转换为多目标优化问题,然后基于马尔可夫链提出一种高可用性的隐私感知在线任务卸载机制。2)在两种约束场景下设计了面向设备端的在线任务卸载算法:在迁移成本约束下提出一种多目标优化的在线任务卸载算法,实现轨迹隐私与感知时延之间的平衡;在迁移成本与时延的双重约束下,提出一种在线最优调度算法,实现轨迹隐私泄露的最小化。这两种算法的计算复杂度呈线性,在计算受限的移动设备上具有更高的可用性。3)搭建仿真环境,考虑任务数量、迁移成本约束、时延约束对算法性能的影响,从 G(t)值、隐私泄露度、响应时间等方面分析本文的任务卸载算法。2 相关工作 目前许多学者在计算卸载策略上展开了深入的研究,他们的工作可以分为时延优先卸载策略和隐私感知的卸载策略。2.1 时延优先的计算卸载 时延是服务器性能的体现,是评估计算卸载策略的一个关键要素,文献9-12针对 MEC 系统中计算卸载的时延问题展开研究。文献9研究基于设备到设备(Device to Device,D2D)的分布式MEC系统,提出一种联合任务分配与功率分配的优化方案以最小化任务处理时延。设计出一个基于遗传算法(GA)的进化方案来解决该混合整数非线性规划(MINLP)问题,进一步提出一种启发式的移动任务感知调度算法来获得低复杂度的有效任务分配。文献10研究在用户移动过程中长期迁移成本约束下的服务器性能优化问题,以实现用户感知时延最小化。基于 Lyapunov 优化将该长期优化问题分解为不需要先验知识的实时优化问题,然后基于 Markov 近似算法来寻求这个 NP-hard 问题的近似最优解,最后提出了一种低时间复杂度的分布式近似方案来解决大规模场景下的计算卸载问题。文献11研究边缘计算架构下的用户分配问题,通过考虑无线信号传输的复杂性与距离对于用户体验质量的影响,来实现最低延迟和最大化用户 QoE(Quality of Experience,QoE)的目标,在小规模场景下提出了最优解算法(DEUA-O)和在大规模场景下提出了次优解算法(DEUA-H)。文献12从运营商的角度来解128 Journal of Cyber Security 信息安全学报,2023 年 7 月,第 8 卷,第 4 期 决用户分配问题,认为感知时延是体现用户体验质量的决定性因素,通过为每个用户分配不同的QoS(Quality of Service,QoS)级别来实现用户体验质量的最大化,用整数线性规划技术来求解这个NP-hard 问题,在大规模场景中提出一种启发式算法来求解它的次优解。2.2 隐私保护的计算卸载 现有的大部分策略都是时延优先的计算卸载策略,但是由于分布式的 MEC 设备容易受到攻击,攻击者通过服务器窃取、推测、利用用户的私人信息来造成损失,因此一些工作加入隐私保护来制定卸载策略,文献13-16针对计算卸载过程中用户隐私保护问题展开研究。文献13研究 MEC 系统的用户隐私安全问题,考虑在MEC系统中现有的应用程序无法抵御攻击者对用户卸载进行的推断攻击,基于 Lyapunov 优化框架提出一种成本效益-隐私权衡的用户任务卸载方案,来实现在保证最佳用户体验的同时保护用户隐私。文献14研究移动边缘计算架构中隐私保护与任务卸载的联合优化问题,在保护用户隐私的同时获得最低的时延与能耗。将该优化问题表述为一个半参数 MBA(Multi-armed Bandit)问题,基于转换汤普森采样(TS)结构提出一种面向用户侧的隐私感知在线任务卸载(PAOTO)算法,来得到最佳的延迟和能耗性能以及保护用户隐私。文献15考虑在物联网中的隐私安全问题,在系统层面上提出一种基于强化学习(Reinforcement Learning)的具有隐私感知的任务卸载方案,在物联网设备上做出任务卸载决策的同时保护 MEC 系统的用户位置隐私和使用模式隐私。文献16针对用户服务信任的问题,提出一个具有信任感知的任务卸载机制。通过过滤掉用户不信任的服务器,然后根据卸载策略让用户在可信 MEC 服务器中选择服务器来提供服务,以减少延迟与能耗。上述文献从隐私保护和时延优先两个方面提出了相应的计算卸载策略,但也有一些局限的地方,他们没有考虑到:1)现实场景中用户通常是动态移动的;2)现有的卸载机制易造成轨迹隐私的泄露。因此我们提出了一种针对用户移动过程中对轨迹隐私的保护方案,主要解决用户在移动过程因为选择服务器位置泄露而造成用户轨迹隐私泄露的问题,同时提出一种具有隐私感知的实时在线决策算法来解决这个问题。3 系统模型与问题定义 考虑在单用户多 MEC 网络场景中,用户 u 在路径 L 上前进时,周围有 S=s1,s2,s边缘服务器为用户提供计算服务,每个 MEC 边缘服务器具有一定的计算资源,且用户可以通过无线接入点或者基站(5G基站)来获服务。我们定义时间tT=1,2,T,其中 T 为轨迹长度。同时定义 nN=1,2,N为用户在一次服务申请时需要向MEC服务器的卸载的任务数,具体符号含义如表 1 所示。为简化问题,本系统有以下几个假设:1)每个用户每次移动只能请求一次计算任务,且需大量计算资源以及可接受一定延迟。2)每个 MEC 服务器的计算资源与整个任务的迁移成本受限。3)接入服务器必须完成用户的每次服务请求。表 1 主要符号与含义 Table 1 Main symbols and meanings 符号 含义 u 用户 si 边缘服务器 si S 服务器集合 T 轨迹长度 n 时刻 t 中,用户卸载给服务器 si的任务数量 L 长度为 T 的真实轨迹 长度为 T 的发布轨迹 lt 时刻 t 的用户真实位置 t 在时刻 t 的接入服务器位置()uixt 在时刻t选择si服务器的决策 G(t)隐私泄露度与时延的加权函数,uj im 用户u的任务在t时刻从服务器sj迁移到服务器si所需要的成本 provideM 运营商提供的最大迁移成本 3.1 威胁模型 攻击者可分为内部攻击者和外部攻击者,假定内部攻击者为边缘服务器,它是诚实但好奇的,它会遵循整个任务卸载的过程,但是它可能利用用户上传的位置数据跟踪用户的移动轨迹,推断用户的隐私信息。外部攻击者为第三方全局攻击者,它能够通过侧信道攻击监听、推测边缘服务器上的用户信息。本文考虑存在一个攻击者,它具有以下能力:1)获得所有边缘服务器的位置;2)获得用户所有接入边缘服务器的信息,包括服务器 ID、接入时间以及服务时长;3)掌握所有路网信息;4)推测用户隐私信息。在一定的时间段 1,2,T 内,用户在移动的过程中向周围的 MEC 服务器进行任务请求,定义任务卸载过程中的接入MEC服务器位置集合=1,2,邓慧娜 等:移动边缘计算中隐私感知的在线任务卸载机制 129 T为发布轨迹(其中 T为 T 时刻的接入服务器位置),攻击者通过跟踪用户行进过程中的发布轨迹,来推测用户的真实轨迹。同时,为了减少时延与能耗,用户会选择最近的服务器进行请求和卸载,攻击者依据这个卸载机制能更精确获得用户在某一时刻的位置,继而综合路网信息、停留时间等推测出用户的私人信息(如个人职业,家庭地址,工作单位等)。因此,我们的目标是在知道这类情况下,阻止因用户任务卸载导致的个人隐私信息泄漏。3.2 轨迹隐私泄露度模型 给定一个时间段 1,2,T,用 L=l1,l2,lT来表示用户在时间段内长度为 T 的真实轨迹,lT表示用在 T 时刻的真实位置。由于服务器位置是公开的,攻击者根据发布轨迹获得用户的真实轨迹,因此定义真实轨迹与发布轨迹的相似度为轨迹隐私泄露度,通过计算发布轨迹与真实轨迹之间的互信息来度量,公式如下:1212()(;)(,;,)privacyTTtI LI l ll ()(|)H LH L (1)3.3 迁移成本模型 移动用户在行进过程中会不停对MEC服务器的服务请求,任务在不同的MEC服务器之间进行迁移,由此产生额外的操作成本,因此对迁移成本进行定义。首先,定义,uj im为用户 u 的一个单位任务在 t 时刻从服务器 j 迁移到服务器 i 所需要的成本,因此当u 经过一条长度为 T(即在 T 个服务器之间迁移)的轨迹时,需要将 n 个单位任务在不同的服务器之间迁移,其迁移成本可以表示为:,11()(1)()uuuujij iijMtxtxt mn (2)其 中,()uixt为 在 时 刻t用 户 做 的 决 策,1,()0,iuiisxts选择服务器未选择服务器,即选择服务器 si为任务卸载服务器。服务提供商希望尽可能减用户尽可能减少迁移来降低运营成本,因此给出一个迁移成本限制1()TuprovidertMtM,provideM为最大迁移成本,如果用户总的迁移成本超过这个值,运营商将停止本次服务。3.4 QoS 模型 移动边缘服务器上的计算资源是受限且有差异的,因此不同的MEC服务器提供给用户的QoS有区别,在本文的 MEC 系统结构中,服务器的 QoS 由用户感知延迟来体现5,用户感知延迟由计算延迟和通信延迟组成。(1)计算时延模型 在每个 MEC 服务器上,可能会有多个移动用户共享服务器的计算资源,但服务器的计算资源有限,当它收到多个任务请求时,有些用户的请求可能会进入服务器的排队队列中或者被提供低质量的服务。因此,为了更好的体现出服务器的 QoS,我们建立一个简化的计算时延模型来度量它。在时刻 t 用户u 将 n 个任务卸载到服务器 si上计算所需时间为:()tnitf,在时刻 t 的计算时延为:11()()()()tuuniiiiiO txt o txtf (3)其中 fi为服务器的 CPU 计算能力,tn是在 t 时刻计算 n 个任务所需要的计算资源。(2)通信时延模型 在 MEC 系统中,在数据传输的过程中移动设备与服务器之间因距离而产生通信时延,为了便于说明问题,本文系统模型中不考虑由于信号衰减、网络质量等因素出现丢包等情况。使用一个参数模型来描述任务,utuuuN,其中 u表示任务上传的数据量,u表示任务下载的数据量,u表示处理该任务所需要的 CPU 资源,是一个标识数,表示该任务是否处理成功,如果成功则为 1,否则为 0。参考文献17-18,用户与 MEC 服务器之间的上传数据速率可以表示为:,2(,)log(1)um uupmmpym uZ (4)设置输出数据下行信道的网络带宽与输入数据的上传信道的网络带宽表示为相等,在忽略设备损耗,环境等其他因素的影响下,假设同一信道的信道增益和噪声功率是不变的,因此输出数据的下载速率可以表示为:,2(,)log(1)um udownmmpym uZ (5)其中,Zm是上行信道的网络带宽,pu为信道传输功率,Bm,u为用户 u 和 MEC 节点 m 之间的信道增益,m为白噪声功率。计算移动用户 u 输入数据到 MEC 节点m之间的传输时间以及当MEC服务器完成任务计算以后,从服务器m将输出数据传输给用户u的下载时间为:130 Journal of Cyber Security 信息安全学报,2023 年 7 月,第 8 卷,第 4 期 ()(,)uupuphtym u (6)()(,)udowndownhtym u (7)因此,结合公式(6)和(7)总的通信时延为:()()()updownH ththt (8)综合任务的计算时延(3)和通信时延(8),在t时刻的用户感知时延可表示为:()()()Z tO tH t (9)3.5 问题表述 本文主要关注的是在多MEC服务器的环境中,用户在移动过程中进行任务卸载时的服务器选择问题,涉及用户敏感信息的保护。本文设计了一个迁移成本约束下的具有隐私感知的任务卸载方案,将迁移成本约束下的任务卸载问题转化为一个联合优化问题,设置权重w1,w2来表示用户对于隐私保护和时延两者不同的偏好,将轨迹隐私与感知时延(即QoS)转化成同一维度,实现轨迹隐私与感知时延的加权最小化,该问题可定义为:Object:11()min()()TuprovidetuiiMtMG t xt (10)12()()()privacyG twtw Z t (11)st:121ww (12)11()()NutiniinxttC (13)1()1uiixt (14)()0,1uixt (15)其中,目标(10)是在服务提供商给出的迁移成本约束下,实现轨迹隐私-感知时延加权函数的最小化,G(t)代表加权函数,1()TuprovidertMtM表示迁移成本限制,()uixt表示在t时刻选择服务器si的决策,()*uixt表示G(t)值最小的最佳决策。公式(11)是G(t)的组成部分,由轨迹隐私泄露度与时延加权构成。限制(12)表示总权重为1,权重数w1,w2在任务卸载前由用户决定。限制(13)表示用户卸载任务所需的计算资源总和不能超过该服务器的最大容量,限制(14)和(15)确保每个用户最多被分配给一个具有足够计算资源的边缘服务器。3.6 NP-hard 问题证明 在3.5小节已提出本文的优化问题,现证明迁移成本约束下的轨迹隐私与时延的联合优化问题是一个NP-hard问题,以下给出证明。定理1.迁移成本约束下的轨迹隐私-时延函数最小化问题是NP-hard问题。证明.首先,介绍一个经典的NP-hard问题:容量受限的设施选址问题(CFLP)。定义设施为F,设施的容量为C,任务需求为R,花费成本为Cost。此CFLP问题可以定义为以下:,min:cosi ji jiii F j Ri Ftyf x (16)st:,1i ji Fy (17),ji jiij Rr yc x (18),0,1ii jx y (19)其中yi,j表示设施i是否满足需求rj,xi表示设施i是否打开,costi,j是将需求rj分配给设施i的花费,ci表示设施i的容量,fi代表开放成本。我们将CFLP问题简化为一个具有隐私感知的任务调度问题,由于本系统中没有服务器的启动成本 问 题,因此0iii Ff x。我 们给 定 一 个实例CFLP(Cost,R,C,F)和本文实例POTO(G(t),N,provideM,S),其中|R|=|N|,|F|=|S|,M provider代表成本限制,G(t)是加权最小值。可以得到,满足目标函数(16)和约束(19)的解决方案也能满足目标函数(10)和约束(15)。每个用户对于服务器的需求不一样,所以对于成本和时延的权重不一样,所以满足约束(17)的解决方案也满足约束(12)。当服务器不满足用户的任务需求时,即不会将任务卸载给服务器,所以可以将约束(13)投影到约束(18)。如果一个解决方案能解决CFLP问题,那该方案也能解决本文的优化问题,因此证明迁移成本约束下的轨迹隐私-时延联合问题也是一个NP-hard问题。4 隐私感知的任务卸载机制设计 一般来说,用户的轨迹隐私泄露的越少、感知时延越大,则接入服务器的可用性就越小。因此,在迁移成本的约束下实现具有隐私感知的任务卸载机制时,如何达到轨迹隐私与可用性之间的动态平衡仍存在挑战,目前可采用全局最优的离线方法与局部最优的在线方法来实现两者间的动态平衡。本文的任务卸载机制设计思路如图2所示。邓慧娜 等:移动边缘计算中隐私感知的在线任务卸载机制 131 图 2 隐私感知的任务卸载机制设计思路 Figure 2 Design of privacy aware task unloading mechanism 4.1 离线/在线轨迹隐私-可用性权衡命题 命题命题1.(离线轨迹隐私离线轨迹隐私-可用性权衡可用性权衡)在一定时间段1,2,T内,给定长度为T的真实轨迹L=(l1,l2,lT)、长度为T的发布轨迹=1,2,T,在迁移成本约束下离线轨迹隐私与感知时延加权最小化函数为:112()()min()()TuprovidertofflineofflineprivacyMtMG twtw Z t(20)1212()(;)(,;,)offlineprivacyTTtI LI l ll (21)其中()offlineprivacyt为计算整条发布轨迹与真实轨迹的互信息。假设一个简化的离线场景,用户u在一条长度为T的轨迹上移动,在每个t时刻用户周围有N个服务器可选择。用户设备在移动开始前通过全局规划计算出所有发布轨迹的G(t)值,然后找出最小的G*(t)值对应的发布轨迹,将该发布轨迹中对应的服务器作为卸载服务器,从而得到全局最优的任务调度决策。但为了得到最优解,该方式必须计算出所有发布轨迹与真实轨迹可能组合(,)lL的互信息,计算量为NT,则计算复杂度将随着轨迹长度、服务器密度的增加而呈指数增加,从而使得计算受限的移动设备无法做出实时决策。因此,我们提出另一个命题,即在线轨迹隐私-可用性权衡,用于分析在线轨迹隐私泄露度-可用性的加权最小化问题。命题命题2.(在线轨迹隐私在线轨迹隐私-可用性权衡可用性权衡)在一定的时间段1,2,T内,迁移成本约束下在线轨迹隐私-感知时延的加权最小化函数为 112()()min()()TuprovidertonlineonlineprivacyMtMG twtw Z t (22)11()(;|)TonlinettprivacytttI L (23)其中()onlineprivacyt为计算在t时刻发布轨迹与真实轨迹的互信息。定理2:()()offlineonlineG tG t 证明:离线任务卸载方法可得到全局最优的任务卸载决策,在线任务卸载方法得到是局部次优任务卸载决策,线卸载决策集中包括离线卸载决策。因为Z(t)值为计算移动设备与边缘服务器之间的感知时延,离线与在线卸载方法中的Z(t)相等,因此主要证明offlineonlineprivacyprivacy。(;)offlineprivacyI L 11(;|)TtttI L 1111(;|)(,;|,)TttttttTttI LI LLL()11(;|)TattttI L 步骤(a)是因为在在线任务卸载的服务器位置选择设置中,当前的接入服务器位置t独立于由未来的真实位置1,tTLL给定的1,ttL。因此可以得到,最小化的和小于或等于单个最小化的和,因此有offlineonlineprivacyprivacy,由此证明()()offlineonlineG tG t。在在线方法中,感知时延很容易由t时刻用户发出请求与收到回复之间的时间差计算得到,因此目标函数中G(t)的值取决于对隐私泄露度的求解。对于()onlineprivacyt,只需计算时刻t内的发布轨迹与每个时刻t真实轨迹之间的互信息1(;|)tttI L,同时在时刻t计算得到的数据会作为时刻t+1互信息计算的输入数据,而不是类似于离线方式需计算整条发布轨迹与真实轨迹间的互信息。但是,在线卸载决策仍需要计算时刻t内接入服务器位置与所有时刻t真实位置之间所有可能组合(,)(,)ttlL的互信息值,即函数(23)的计算仍与轨迹长度T有关,与离线方式一样,它的计算复杂度仍为NT,呈指数增长。为了解决上述问题,我们提出一种基于马尔可夫链的在线任务卸载机制。通过引入马尔可夫链来得到隐私泄露度的上界与下界,消除轨迹长度对于隐私泄露度计算的影响,使函数(23)的计算与轨迹长度无关,从而降低计算复杂度。132 Journal of Cyber Security 信息安全学报,2023 年 7 月,第 8 卷,第 4 期 4.2 迁移成本约束下基于马尔可夫链的在线任务卸载机制 4.2.1 基于马尔可夫链的隐私泄露度算法基于马尔可夫链的隐私泄露度算法 在马尔可夫链中,当前系统的状态仅仅与之前几个时刻的状态相关,而与其他时刻状态无关,极大的简化了一些复杂问题19。因此在本文的轨迹隐私模型中,我们认为方案中的服务器发布位置只与上一时刻的位置状态有关,而与之前的位置状态无关。假设用户的移动轨迹可以由一种概率分布来生成,这种概率分布由用户的初始位置概率分布与移动模型计算得,用长度为n的向量p1作为用户的初始位置概率分布,用户的移动模型可以看作是由马尔可夫转移矩阵M表示的一阶马尔可夫链20-21。基于这种认知,本方案在时刻t选择的服务器t仅取决于当前用户真实位置lt,t1时刻的服务器位置t1和用户真实位置lt1,如图3所示。图 3 基于马尔可夫链的发布轨迹 Figure 3 Location release mechanism with Markov chain 根据文献20可知,当前接入服务器位置的选择受制于上一时刻接入服务器与用户的位置,因此基于马尔可夫链对本方案的接入服务器选择范围进行限制。针对命题2,我们通过放宽隐私泄露度函数得到在线真实隐私泄露度onlineprivacy在迁移成本约束下的上界与下界,使隐私泄露度函数的上下界位置数与轨迹长度无关。因此提出以下定义:定理3:(基于马尔可夫限制的轨迹隐私泄露度上下界)通过对接入服务器位置选择机制的马尔可夫限制,在线隐私泄露度的上下界定义如下:MarkovonlineMarkovlowerprivacyupper (24)111()(,;|)TMarkovupperttttttI l l (25)111()(;|,)TMarkovlowerttttttI ll (26)其中,()Markovuppert为在线隐私泄露度 onlineprivacyt的上限,()Markovlowert为在线隐私泄露度 onlineprivacyt的下限。证明:1)onlineMarkovprivacyupper()11121(;|)(,;|,)btttttttI LI ll 1221211(,;|,)tttttI l llll 1121(,;|,)ttttI ll 12111(|,)(|,)ttttttHHl l 111(|)(|,)ttttttHHl l 11(,;|)()MarkovttttupperI l lt 步骤(b)的第二项等于零,是因为在马尔可夫限制中当前的接入服务器位置t只取决于11,tttl l,因此onlineprivacy总是小于等于Markovupper。2)onlineMarkovprivacylower 112111(;|)(|,)(|,)tttttttttI LHHl l 121111(|,)(|,)tttttttHlHl l 1111(|,)(|,)tttttttHlHl l()11(;|,)cttttI ll 因为在马尔可夫限制中当前接入服务器位置t只取决于1,tttl l,因此对步骤(c)的第一项进行了相应的转换,因此onlineprivacy总是大于等于Markovlower。在基于马尔可夫限制计算()onlineprivacyt时,只需计算每个时刻t内N个发布位置与真实位置之间的互信息,其计算复杂度为N呈线性增长。相较于离线卸载方法与在线卸载方法,基于马尔可夫链的在线任务卸载方案具有更低的计算复杂度、更高的可用性,适用于资源受限的移动设备做出快速决策。下面给基于马尔可夫链的在线隐私泄露度算法,虽然公式(24)给出了在线隐私泄露度的上下限,但我们只考虑最大的隐私泄露度,因此只计算马尔可夫上限而不再计算下限。根据文献22可知 11111111,1(|,)(,;|)(,)log(|)ttttttttttttttttllttqllI l lpllr-(27)1(,)1111(,)1(|)(|,)(|)tttttd lttttttd lttrleqllrle (28)211111221,(,)(.,)(|)tttttttttttvp llpllp ll-(29)111111,(|)(,|)(|,)tttttttttttv vrp l lqll-(30)因此,根据Markovupper计算出onlineprivacy的最大值,以下给出其隐私泄露度算法,如算法1所示:算法 1.隐私泄露度算法 输入输入:拉格朗日乘子,t1时刻内发布服务器位邓慧娜 等:移动边缘计算中隐私感知的在线任务卸载机制 133 置与真实位置的联合分布1122(,)ttttpll,发布服务器位置的边界分布1()tp,失真矩阵(,)ttdl 输出输出:时刻t的发布服务器位置的条件分布11(|,)ttttqll,发布服务器位置的边界分布()ip,发 布 服 务 器 位 置 与 真 实 位 置 的 联 合 分 布11(,)ttttpll,最大隐私度量()Markovuppert 1:初始化01(|)ttr作为均匀分布 2:FOR,ttl in,L do 3:通过公式(28)计算011(|,)ttttqll 4:通过公式(29)计算出11(,)tttp ll 5:通过公式(30)计算出1(|)ttr 6:通过公式(27)计算出11(,;|)ttttI l l 7:通过公式(21)计算出()Markovuppert 8:END FOR 4.2.2 隐私感知的在线任务卸载算法隐私感知的在线任务卸载算法 在计算出()onlineprivacyt后,我们提出一种具有隐私感知的在线任务卸载算法(Privacy-aware of Online Task Offloading,POTO),通过计算每个决策的G(t)值来快速做出最佳服务器选择决策,如算法2所示:算法 2.隐私感知的在线任务卸载算法 POTO 输入输入:用户u,边缘服务器集合S,任务量N,迁移成本限制provideM 输出输出:用户的服务器的最佳分配策略:uS 1:初始化用户的内置服务器列表user_X 2:FOR 在时刻t 3:搜寻用户u周围的可用服务器 4:IF icapSjcapN 5:将si 服务器加入列表user_X 6:END IF 7:FOR si in user_X do 8:根据公式(2),计算出1()TutMt 9:IF 1()TuprovidertMtM 10:将si服务器加入列表user_Y 11:END IF 12:FOR si in user_Y do 13:根据公式(11),计算出选择每个当前策略()uixt 的G(t)值 14:END FOR 15:在策略集()uxt中选择出G(t)值最小的作为最佳分配策略()*uixt执行 16:END F