控制与决策  2019, Vol. 34 Issue (11): 2366-2374  
0

引用本文 [复制中英文]

吕灵灵, 杨志鹏, 张磊. 基于合约设计的移动边缘计算任务卸载策略研究[J]. 控制与决策, 2019, 34(11): 2366-2374.
[复制中文]
LYU Ling-ling, YANG Zhi-peng, ZHANG Lei. Contract theory based task offloading strategy of mobile edge computin[J]. Control and Decision, 2019, 34(11): 2366-2374. DOI: 10.13195/j.kzyjc.2019.0593.
[复制英文]

基金项目

国家自然科学基金项目(U1204605, 11501200);中原千人计划项目(ZYQR201810138);河南省教育厅项目(17HASTIT023, 17B520006)

作者简介

吕灵灵(1983—), 女, 教授, 博士, 从事周期系统控制、移动边缘计算等研究, E-mail: lingling_lv@163.com;
杨志鹏(1996—), 男, 硕士生, 从事移动边缘计算的研究, E-mail: 1140875687@qq.com;
张磊(1981—), 男, 副教授, 博士, 从事网络安全、移动边缘计算等研究, E-mail: zhanglei@henu.edu.cn

通讯作者

张磊, E-mail: zhanglei@henu.edu.cn

文章历史

收稿日期:2019-05-01
修回日期:2019-07-09
基于合约设计的移动边缘计算任务卸载策略研究
吕灵灵 1, 杨志鹏 1, 张磊 2     
1. 华北水利水电大学 电力学院,郑州 450045;
2. 河南大学 计算机与信息工程学院,河南 开封 475004
摘要:移动边缘计算将边缘服务器部署到无线局域网侧, 将部分计算密集任务卸载到边缘云服务器, 从而缩短计算服务与移动设备的距离, 降低数据传输成本.考虑移动边缘计算(MEC)环境下的计算任务分配问题, 通过探索用户体验敏感度的异质性, 建立CPU运算周期数-数据量-价格的三元组合约模型, 提出基于合约理论的计算任务分配策略, 以最大化云服务商的利润为目标, 同时保证移动用户的非负效益.分别讨论完整信息场景下和统计信息场景下的最优合约设计策略.仿真结果验证了所提出方案可以有效实现计算任务的卸载.
关键词移动边缘计算    计算任务卸载    合约理论    全息    统计信息    
Contract theory based task offloading strategy of mobile edge computin
LYU Ling-ling 1, YANG Zhi-peng 1, ZHANG Lei 2     
1. School of Electric Power, North China University of Water Resources and Electric Power, Zhengzhou 450045, China;
2. School of Computer and Information Engineering, Henan University, Kaifeng 475004, China
Abstract: Mobile edge computing (MEC) deploys edge servers to the side of wireless LAN and offloads some computing-intensive tasks to edge cloud servers, which can shorten the distance between computing services and mobile devices and reduce the cost of data transmission.This paper considers the problem of computing task offloading in the mobile edge computing environment. By exploring the heterogeneity of user experience sensitivity, a ternary combination model of the number of CPU cycles, data size and price is established, and a computing task allocation strategy based on contract theory is established to maximize the profit of cloud service providers and ensure the non-negative benefit of mobile users. The optimal contract design strategies for complete information scenarios and statistical information scenarios are discussed, respectively. Simulation results show that the proposed schemes can effectively realize the offloading of computing tasks.
Keywords: mobile edge computing    task offloading    contract theory    full information    statistical information    
0 引言

近年来, 随着互联网的蓬勃发展, 用户数据量激增, 新型移动应用(如面部识别、自然语言处理、高清视频、增强现实、互动游戏等)不断涌出, 引起了人们的广泛关注.这些移动应用的执行需要较高的计算资源, 并消耗较大的电力能源.然而, 移动设备由于物理尺寸的限制, 通常只具有有限的计算能力和电量.目前, 普遍认为只依赖云计算不足以实现5G计算和通信毫秒级延迟的雄心壮志.新的网络架构需要被设计研究, 以更好地将云计算的概念集成到移动网络中[1].移动边缘计算(mobile edge computing, MEC)将密集的移动计算卸载到位于蜂窝网络边缘的云, 为该问题的解决提供了有效的途径.移动边缘计算是基于5G演进的架构, 并将移动接入网与互联网业务深度融合的一种技术, 其核心思想是将存储、计算等功能下移到网络边缘(如基站、用户等), 就近为用户提供所需求的内容或服务, 从而降低端到端时延和减少回程链路流量[2].

在MEC环境中, 执行计算和存储的服务器都部署在网络边缘, 用户设备(UE)可以通过将移动应用的一部分任务卸载到边缘服务器上执行的方式来提高移动应用的服务质量和减少UE的能源消耗.因此, 近年来MEC环境下的计算任务卸载问题引起了国内外学者们极大的研究兴趣[3-9].文献[3]研究了5G异构网络中MEC的节能计算卸载(EECO)机制, 结合5G异构网络的多访问特性, 设计了一种EECO方案, 该方案通过联合优化卸载和无线资源分配, 在延迟约束下获得最小的能耗.文献[4]研究了基于时分多址(TDMA)和正交频分多址(OFDMA)的多用户MECO系统的资源分配问题.对于具有无限或有限云计算能力的TDMA MECO系统, 将最优资源分配问题表示为一个凸优化问题, 在计算延迟的约束下最小化加权和移动能耗.文献[5]针对边缘云计算环境下的任务调度属于NP难度问题的特性, 根据群体智能寻优的原理, 利用博弈论方法, 提出了一个目标达到纳什均衡的分布式多用户计算任务调度算法.文献[6]针对边缘计算网络中的负载均衡需求, 提出了一种基于集中控制的调度机制.该机制首先决定在哪些网络节点部署边缘计算功能, 再针对用户的数据和请求, 在满足相关负载均衡约束的前提下通过调度尽量降低流量的平均端到端延迟.遗憾的是, 上述文献都没有考虑如何激励移动用户参与到MEC网络中来, 也没有考虑到运营商的利润.

合约理论(契约理论)是在特定交易环境下用来分析不同合同人之间的经济行为与结果, 往往需要通过假定条件在一定程度上简化交易属性, 建立模型来分析并得出理论观点.合约理论通过协调所提供的服务和差别定价来有效地设计激励机制, 特别是在不完整的信息情景下[10].因此, 合约理论在一些优化资源调度问题中得到了广泛的应用.如, 文献[11]设计了一种基于合约设计的不对称信息下的混合电动汽车的充电策略, 以电力部门利润最大化为目标, 并同时保证了电动汽车用户的非负效用; 文献[12]考虑了异构蜂窝网络中的流量卸载问题, 提出了一种感知拥塞的网络选择算法, 通过研究用户质量敏感性的异质性, 设计了最优质量价格契约, 使运营商利润最大化; 文献[13]用合约理论研究了不完全信息下的协同频谱共享问题; 文献[14]设计了一个最佳合约来应对频谱交易过程; 文献[15]提出了一个机制, 让每个用户根据其类型选择合适的质量-价格合约项, 以激励用户利用他们的延迟和价格敏感性来换取服务成本.

本文考虑局部MEC环境下用户数量多, 而执行计算和存储的边缘云服务器有限的情况下, 如何在满足约束条件的同时, 将移动用户的任务合理地卸载到边缘服务器上的问题.在本文中, 提出一种基于三元合同的任务卸载方案.由于移动用户价格敏感性的异质性, 将用户分为不同类型, 并为用户提供最佳计算任务-价格合约.通过利用合理定价, 既能保证每个用户的非负效益, 又能最大化云服务商的利润.

1 系统建模 1.1 网络模型

MEC网络结构如图 1所示, 用户侧由N={1, 2, …, N}用户组成, 用户任务通常由语音电话、传真机、AR、游戏、智能视频加速等构成; 网络侧由云服务商所拥有的若干边缘服务器组成.用户侧和网络侧通过通信链路进行数据传输.

图 1 MEC网络结构
1.2 计算模型

用户nN的任务用In=(dn, bn)的二元组来表示, dn为完成用户n的计算任务所需要的CPU循环周期数, bn为用户n的计算任务的数据量大小.关于计算任务, 有如下假设.

假设1  移动用户传输给云端的计算任务数据量bn越大, 则完成任务需要的CPU循环周期数dn越大.换句话说, 对于任意两个任务Ii=(bi, di)和Ij=(bj, dj), 若bi>bj, 则di>dj; 反之亦然.

1.2.1 本地计算模型

若用户n不使用边缘计算, 则用户n的任务在本地进行计算, 完成计算任务所使用的计算时间为tnL=dn/CnL.其中: dn是用户任务的数据量, CnL是用户n移动设备的CPU计算能力(以GHz为单位).除了要考虑计算时间, 还要考虑完成计算任务所消耗的能量, 设γnL是CPU每个时钟周期的功耗, βnL是单位数据量存储需要的功耗, 则完成计算任务In=(dn, bn)所消耗的能量为enL=γnLdn+βnLbn.因此, 用户n的本地计算总开销为

(1)

其中: λtt>0和λne>0分别代表用户n赋予时间窗口和能量窗口所占比重, 都折合成费用.用户根据特定场景下自己对电量消耗或时滞延迟的敏感度可以灵活调度两个权值, 从而动态调整系统的总开销.

1.2.2 边缘云计算模型

用户采用边缘云计算的开销主要包括两部分, 一部分是时间花费, 包括传输时间消耗和计算时间消耗; 另一部分是支付给云服务商的费用.本文假设用户的通讯费用是包月的, 对问题求解没有影响, 因此不考虑这部分成本.在这里假定所有用户传输速率相同, 用V表示用户的传输速率, 则用户n的任务卸载到边缘服务器上, 此时产生的数据上传时间为tncloud, T=bn/V; 边缘服务器计算时间为tnc=dn/C, C是边缘服务器单位时间内的计算量; 下行传输时间极短, 忽略不计.因此, 使用边缘服务器的时间开销为λnt(tcloud, T+tnc); 假设用户利用边缘云计算实现计算任务In=(dn, bn)所支付给云服务商的价格为πn, 则采用边缘云计算的总开销为

(2)
1.3 用户的效用函数

只有当移动用户将计算任务提交到边缘服务器进行计算所付出的代价小于在本地计算所付出的代价时, 用户才会参与到MEC网络中来.因此, 用户得到的效益可以建模为采用边缘云服务代替本地计算所节省的开销, 即Un=KnL-Knc.结合式(1)和(2), 有

(3)

其中

(4)

这里, 对应于计算任务In=(dn, bn), τnθn组合在一起形成一个二元组(τn, θn), 代表了用户的属性.可以根据用户属性进行分组, 将相同属性的用户分为一组, 记Γ={1, 2, …, K}为所有类型的集合, 且每个类型的移动用户数量记为Nk (kΓ), 则显然有

(5)
1.4 云服务商模型

不可避免地, 云服务商为移动用户提供边缘云计算服务将会产生一些操作成本.操作成本主要包括数据的存储成本和任务的计算成本.这里假定操作成本关于数据大小bk和计算量dk单调递增.这样, 运营商为用户类型k提供服务的操作成本可以建模为

(6)

其中prb>0和prd>0分别代表数据存储和任务计算的单位成本.令R代表云服务商的利润, 即财政收入和操作成本的差, 则有

(7)
2 问题形成和可行解分析

在介绍了云服务商和移动用户的数学模型之后, 本节首先讨论由计算任务和计算价格组成的合约设计.定义一个三元组构成的集合如下:

(8)

这样, 集合Λ唯一确定了一组(dk, bk, πk)值, 即云服务器为移动用户完成计算任务Ik=(dk, bk), 云服务商向用户收取的费用为πk.由计算模型可知, 对于任意一个计算任务二元组Ik=(dk, bk), 都存在唯一的(τk, θk)与之对应.因此, 可以将移动用户类型表示为如下集合:

(9)

此处假设τ1 < τ2 < … < τK, θ1 < θ2 < … < θK.

从移动用户的角度而言, 为了保证用户参与边缘云计算的积极性, 选择的策略必须满足如下两个约束, 这也是很多文献在激励机制设计中通常用到的.

定义1 (IR:个体理性条件)  合约的设计必须保证每个用户的自身利益, 即每个用户的效用函数都是非负的, 有

(10)

定义2 (IC:激励相容条件)  激励相容条件是指合约的设计必须使第k种类型用户选择第k个策略相对于其他策略来说是最优策略, 即

(11)

根据以上的准备工作, 云服务商利润最大化问题可以归结为如下的合约设计问题:

(12)

为了求解上述问题, 需要对IC条件和IR条件进行分析和简化.为此, 首先给出如下结论.

引理1 设合约设计问题的可行解集合为Λ={(dk, bk, πk), kΓ}, 则∀(τi, θi), (τj, θj)∈Π, 当且仅当bi < bj, di>dj时, 有πi>πj.

证明 必要性.根据类型i的IC条件, 整理可得τi(di-dj)+θj(bi-bj)≥πi-πj, 若πi>πj, 则τi(di-dj)+θi(bi-bj)>0.又因为τi>0, θi>0, 根据假设1, 必然有bi>bj, di>dj, 必要性得证.

充分性.根据类型j的IC条件有πj-πiτj(dj-di)+θj(bj-bi), 如果bi>bj, di>dj, 且因为τj>0, θj>0, 则有πj-πi < 0, 即πi>πj, 充分性得证.

推论1 设合约设计问题的可行解集合为Λ={(dk, bk, πk), kΓ}, 则∀(τi, θi), (τj, θj)∈Π, 当且仅当bi=bj, di=dj时, 有πi=πj.

注1  以上结论表明, 用户的计算任务越大, 支付给云服务商的价钱也越多, 反之亦然.支付和计算任务是单调递增关系, 这个条件对于一个健康的市场具有最基本的重要性, 同时也是由合约设计的激励相容性条件保证的.

引理2  设合约设计问题的可行解集合为Λ={(dk, bk, πk), kΓ}, 则∀(τi, θi), (τj, θj)∈Π, 如果τi>τj, θi>θj, 则一定有bibj, didj.

证明 根据IC条件, 对类型ij, 分别有

将上边两式不等号两侧分别相加, 可以得到

整理可得

由假设1可知, di-djbi-bj同号, 若τi>τj, θi>θj, 则有bibj, didj.

注2  引理2表明了类型值与计算任务之间的关系, 即较高类型的移动用户应该分配到更多的计算资源.因为越高的类型值(τ, θ), 单位计算资源能给云服务商带来越多的利润.

定理1  设τ1 < τ2 < … < τK, θ1 < θ2 < … < θK, 当且仅当下列3个条件同时满足, 则集合Λ={(dk, bk, πk), kΓ}为合约设计问题的可行解集:

1) 0≤ d1d2≤…≤ dKdmax, 0≤ b1b2≤…≤ bKbmax;

2) 0≤π1τ1d1+θ1b1;

3) πk-1+τk-1(dk-dk-1)+θk-1(bk-bk-1)≤πk, πkπk-1+τk(dk-dk-1)+θk(bk-bk-1), ∀k≠1.

证明 充分性.定义集合Λ:={(d1, b1, π1), (d2, b2, π2), …, (dk, bk, πk)}, 即Λk是由Λ中前k种类型的三元组构成.设任意(dk, bk, πk)∈Λ都满足条件1) ~条件3), 采用数学归纳法证明Λ是可行集.

K=1时, Λ={(d1, b1, π1)}, 因为只有一个合约项, IC条件自动满足, 而条件2)正是IR条件, 因此当K=1时, Λ是可行集.

假设当K=m时命题成立, 也就是说, Λ={(d1, b1, π1), (d2, b2, π2), …, (dm, bm, πm}是可行解集, 接下来只需要证明当K=m+1时, 解集Λ={(d1, b1, π1), (d2, b2, π2), …, (dm+1, bm+1, πm+1)}仍然是可行集.

下面证明该集合分别满足IR和IC条件.根据以上假设, 只需证明合约项(dm+1, bm+1, …, πm+1)满足IC条件和IR条件, 已知可行性解集Λ={(d1, b1, π1), (d2, b2, π2), …, (dm+1, bm+1, πm+1)}中所有合约项都满足IC条件.

首先证明合约项(dm+1, bm+1, πm+1)满足IC条件和IR条件.

根据类型(τm, θm)的IC条件可以得到

因此下式成立:

(13)

进一步由条件3)的右侧不等式

可得

(14)

结合式(13)和(14)可得, ∀i∈ {1, 2, …, m}, 有

成立, 即合约项(dm+1, bm+1, πm+1)满足IC条件.根据上面不等式, 由于0 < τi < τm+1, 0 < θi < θm+1, 可得

即合约项(dm+1, bm+1, πm+1)满足IR条件.

接下来, 还需要进一步证明Λ={(d1, b1, π1), (d2, b2, π2), …, (dm+1, bm+1, πm+1)}中所有合约项都满足IC条件.

根据类型(τi, θi)的IC条件, 有τidi+θibi-πiτidm+θibm-πm, ∀i∈ {1, 2, …, m}.由条件3)的左侧不等式πm+1πm+τm(dm+1-dm)+θm(bm+1-bm)可得, ∀i∈{1, 2, …, m}, 有

又有dm+1>dm, bm+1>bm, 并且τmτi, θmθi, 可以得到

即在加入新的合约项(dm+1, bm+1, πm+1)之后, 原来的合约项仍满足IC条件.综上可得, 满足条件1) ~条件3)的集合是一个可行集, 即充分性得证.

必要性.设集合Λ={(dk, bk, πk), kΓ}为合约设计问题的可行解集, 证明条件1) ~条件3)分别满足即可.根据引理2和假设τ1 < τ2 < … < τK, θ1 < θ2 < … < θK, 条件1)显然成立.根据合约项(d1, b1, π1)的IR条件, 可知0≤ π1τ1d1+θ1b1, 即条件2)成立.根据类型(τk, θk)和(τk-1, θk-1)的IC条件有

对以上两式整理可得

即条件3)成立.必要性得证.

3 两种场景下的最优合约设计 3.1 完整信息场景

在该场景下, 云服务商可以获知所有移动用户的类型(τk, θk)的值, 并得到属于某个类型(τk, θk)的用户数量Nk.此外, 云服务商可以针对每个移动用户的类型值, 只提供该类型的合约项, 而不是合约集合中的所有合约项, 这样就能保证移动用户的类型和云服务商提供的合约项对应起来, 也即IC条件在这种场景下自然满足.但是, 在这种完全信息情况下, 需要移动用户在一开始使用移动边缘计算服务时, 向云服务商通报其类型值(τk, θk).云服务商在获知所有移动用户的有效信息后作出最佳的决策.

下面, 讨论最优解所要满足的条件.

引理3 设合约设计问题的最优解为Λ*={(dk*, bk*, πk*), kΓ}, 则一定有

(15)

证明 反证法.假设kΓ使得τkdk*+θkbk*-πk*≠0, 根据IR条件一定有τkdk*+θkbk*-πk*>0, 所以存在πk, 使得τkdk*+θkbk*-πk=0, 即πk=τkdk*+θkbk*.代入IR条件, 可以得到πk>πk*.由合约设计问题的目标函数可知, 云服务商的利润随πk递增, 所以有R(πk)>R(πk*), 这与最优解Λ*={(dk*, bk*, πk*), kΓ}的假设相矛盾, 因此一定有τkdk*+θkbk*-πk*=0, ∀kΛ.命题得证.

上述引理表明, 如果云服务商能够获知所有移动用户的类型信息, 则云服务商作出的合约设计一定会使每个参与合约的移动用户的效益为零.也即, 对于移动用户而言, 使用本地运算和使用边缘云服务所花费的代价是完全相同的.但是, 由于用户外出或者本地没有相关软件等原因, 认为用户仍然会选择边缘云计算方式.因此, 即使用户效益为零, 用户仍然愿意参与到云服务商制定的合约中去.

接下来考虑实际操作过程中的一些约束条件, 主要包括合约项中数据量bk和CPU运算循环周期数量dk的总和限制以及它们各自的单项限制.

根据引理3的结论, 合约设计问题P1可以转化为如下问题:

事实上, 根据问题P2的目标函数和约束条件, 可以看到两组决策变量是相对独立的, 因此可以分解为两个独立的子优化问题如下:

另外, 需要考虑每个类型移动用户所需要的计算任务{dk, bk}的限制, 即最大需求.设存在{bk}和{dk}, 使单项合约数据量{bk}和CPU运算循环周期数{dk}必须满足

(16)
(17)

为了讨论单项数据量约束和CPU运算能力约束对问题带来的影响, 分两种情形来讨论.首先考虑最简单的情形, 给出如下假设.

假设2 假设问题P2的最优解满足dk*dk, bk*bk.

在这个假设下, 有如下结论.

定理2 设问题P2的最优解为合约集合Λ*={(dk*, bk*, πk*), kΓ}, 其中Γ={1, 2, …, K}, 且τ1 < τ2 < … < τK, θ1 < θ2 < … < θK.则:

1) 如果τK>prd, θK>prb, 则dK*=D/Nk, bK*=B/Nk, 且di*=0, bi*=0, ∀i∈{1, 2, …, K-1};

2) 如果τK>prd, θK < prb, 则dK*=D/NK, di*=0, ∀i∈{1, 2, …, K}, 且bk*=0, ∀kΓ;

3) 如果τK < prd, θK>prb, 则bK*=B/Nk, bi*=0, ∀i∈{1, 2, …, K-1}, 且dk*=0, ∀kΓ;

4) 如果τK < prd, θK < prb, 则dk*=0, bk*=0, ∀kΓ.

证明 首先采用反证法证明∀i∈{1, 2, …, K-1}, 有di*=0, bi*=0.假设存在i < K, 使得di*>0, bi*=0.由引理3.3可知, πi*=τidi*+θibi*.令πi=τKdi*+θKbi*, 构造一个新的合约项(di*, bi*, πi), 即任务(di*, bi*)对应于类型值(τK, θK).根据假设τi<τK, θi<θK, 结合问题P2的目标函数可知, 用新构造的合约项(di*, bi*, πi)代替合约项(di*, bi*, πi*)可以得到更多的利润, 这与(di*, bi*, πi)是最优合约项相矛盾.因此di*=0, bi*=0, ∀i∈{1, 2, …, K-1}.

根据问题P4的目标函数, 为了使得利润最大化, 如果τK>prd, 显然有dK*=D/Nk.若τK < prd, 则有dK*=0, 否则利润为负值.

同理, 由问题P3的目标函数可知, 如果θK>prb, 则bK*=B/Nk; 如果θK < prb, 则bK*=0.

综上, 定理2得证.

上述定理的实际意义非常明显, 如果计算成本prd和存储成本prb都足够高, 即τK < prd, θK < prb, 则云服务商不会接受任何计算任务.由于任何一个计算任务In={dn, bn}都由dnbn同时构成, 若需要的计算量dn不为零, 则其必然需要一定的存储空间, 即bn也不为零, 反之亦然.因此, 上述定理中的第2种和第3种情形在实际操作中也不可能出现, 不妨假设只有第1种情况存在, 即τK>prd, θK>prb.

接下来讨论假设2不成立的情形, 即分配给类型K的计算任务{dK*, bK*}可能超过该类型用户的需求最大值{dk, bk}.这时, 可以依次向类型集合中最高的类型分配数据存储量和计算资源, 确保分配给用户的资源不超过上限, 然后在类型集合中去掉该类型, 并重复上述操作, 直到τk-prdθk-prb中有一项变成负数, 或者可用的存储空间或计算量分配完毕为止.

根据上述理论, 将MEC网络计算任务分配策略总结成如下算法.

算法1 MEC任务分配最优合约设计算法.

输入:初始化参数类型值τ1, …, τK, θ1, …, θK, 以及各类型的用户数N1, …, NK, 单位计算成本prd, 单位存储成本prb, 数据量总量限制B和单个合约项限制bk, CPU运算周期数总量限制D和单个合约项限制dk.

输出:

while θK>prb & τK>prd & K>1 do

   dK*=D/NK;

   bK*=B/NK;

   πK*=τKdK*+θKbK*

   if dK*>dK & bK*>bK then

      dK*:=dK;

      bK*:=bK;

      πK*=τKdK*+θKbK*;

      D:=D-NKdk*;

      B:=B-NKdk*

   else

      dK*=min(dK*-dK);

      bK*=min(bK*-bK);

      πK*=τKdK*+θKbK*;

      D:=D-NKdK*;

      B:=B-NKbK*

      for i=1:K-1

         di*=0;bi*=0;πi*=0

   end for

   end if

   K:=K-1

end while

3.2 统计信息场景

一般来说, 完全掌握用户的类型信息比较困难, 且类型信息也会动态变化, 因此考虑统计信息场景.假设云服务商只能获知类型为(τk, θk)的用户数量服从的概率分布, 以及参与边缘云计算的用户总数N.此时, IC条件不会自动满足, 算法1不再适用.设每个用户属于类型(τk, θk)的概率是ϕk的用户数量{Nk}应满足的概率密度函数为

其中, 满足.

云服务商的目标为最大化期望效益, 并设满足的集合是Ω, 令

根据定理1中可行解的充要条件, 问题P1变成

定理3  假设问题P1的唯一最优解为πk*, 且0≤ d1d2≤…≤ dk, 0≤ b1b2≤ …≤ bk, 0≤τ1τ2≤…≤ θk, 0≤θ1θ2≤…≤θk, 则{πk*}一定满足

(18)

证明 可行性.通过式(18)得到的解明显满足引理1提出的充要条件, 因此一定是可行解.

最优性.这里采用反证法, 假设{π'k}, 使得运营商能够获得更高的效益.由于合约存储量、计算量是固定的, 目标函数仅与合约价格总和成正比, 所以根据假设一定存在某个用户类型(不妨设为类型(τk, θk))对应的合约满足π'k>πk*.如果k=1, 则有π'1>π1*.又因为πk*=τ1× d1+θ1× b1, 所以π'1τ1× d1+θ1× b1显然不满足IR条件, 故k>1.

k>1时, 根据假设, {π'k}满足定理1的第3个条件, 即满足

代入

得到

π'k-1>πk-1*.同理可得π'k-2>πk-2*, …, π'1>π1*, 与之前的论述矛盾, 所以不成立, 即可行解{πk*}是最优解.

唯一性.反证法, 假设{πk~}, πk~πk*, ∀kΓ, 使得E{Upro}({πk~})=E{Upro}({πk*}), 则存在至少一对类型组((τi, θi), (τj, θj)), 对应的合同价格同时满足πi~ < πi*πj~ < πj*.注意到利用πj~>πj*和最优性中的讨论, 可以得到π1~>π1*, 此时违背了类型(τ1, θ1)的IR条件.因此, 假设不成立, 即最优解{πk*}是唯一的.

若令b0=b1, d0=d1, 则式(18)可以表示为

(19)

利用式(18)和(19), 问题P5可以化简为

(20)

其中

μk=τk-τk-1, vk=θk-θk-1.

考虑实际情况, 必须添加单项计算任务的边界约束条件(16)和(17), 并计算和存储资源总和约束条件

在不考虑约束条件(20)时, 问题P6可以归结为如下的线性规划问题:

由于该问题是一个简单的线性规划, 很容易得到求解.如果问题P7的求解结果刚好满足问题P6的约束条件(20), 则该线性规划问题的解即为最优解, 否则需要对解进行修正, 修正原则如下.

设根据问题P7得到的最优合约计算任务约为{(dk, bk)}, 且不满足条件0≤ d1d2≤…≤ dk或0≤ b1b2≤…≤ bk, 则该集合中至少存在一个子集{(di, bi)…(dj, bj)}, 其中i < j, 满足di>…>djbi>…>dj, 那么对{(dk, bk)}中每一个这样的子集, 令di=…=dj, bi=…=bj, 直到满足0≤ d1d2≤…≤ dk, 0≤ b1b2≤…≤ bk为止, 则可以得到问题P6的最优解.

4 数值仿真 4.1 实验参数与数据

本节在全信息情况下和统计信息的情况下进行仿真实验.给定用户设备的计算能力以及MEC边缘服务器的计算能力等数据如表 1所示.

表 1 用户设备和边缘服务器的各类参数
4.2 完整信息下的最优合同

在这个情境下, 云服务商知道用户的类型, 可以根据用户类型提供合约, 因此自然地满足IC条件.云服务商也知道各个类型用户的数量, 在这里假设用户类型分别为

且每个类型用户数量为100.云服务商给出总的存储量为4 400 MB, 总的CPU循环周期数为580 000 MCycle, 各类型的单项存储上限分别为10、11、12、13、14、15, 单位为MB, 单项的CPU循环周期数上限为1 300、1 400、1 500、1 600、1 700、1 800, 单位为MCycle.

按照算法1得出每个类型分配的存储量和CPU循环周期数如图 2所示.可以看到类型1和类型2没有分配到任何计算任务, 这是因为他们的类型值小于单位存储成本或计算成本, 不会给云运营商带来效益.由算法1得出合约价格以及各个类型用户给云服务商带来的利润如图 3所示.可以看到, 合约价格随用户类型单调递增, 这是因为高类型用户为了得到更快的计算速度和更大的存储空间, 需要对云服务器支付更高的价格; 同时也可以看到, 在各类型用户数相同的情况下, 高类型用户能够给云服务商带来更高的利润, 这也符合实际情况.

图 2 不同用户类型的数据量和CPU循环周期数
图 3 用户的价格和运营商利润
4.3 统计信息下的最优合约设计

在统计信息的情况下, 设置如下8种用户类型:

进一步假设用户属于某个类型的概率服从以(0.000 32, 0.006)为期望, 方差为0.000 1的正态分布.设参与到边缘云服务的用户总数量为8 000, 则各类型用户的分布情况如图 4所示.此外, 假设云服务商给出总的存储量为98 000 MB, 总的CPU循环周期数为6 400 000 MCycle, 各类型的单项存储上限分别为9、10、11、12、13、14、15、16, 单位为MB, 单项的CPU循环周期数上限为1 200、1 300、1 400、1 500、1 600、1 700、1 800、1 900, 单位为MCycle.

图 4 各类型的用户数量

在以上的条件下, 通过求解线性规划问题P7得到的最优合同如图 5图 6所示.由仿真结果可以看到, 运营商的利润没有出现完全信息情景递增的情况, 这是因为用户类型服从正态分布, 高类型单个用户虽然能带来较高的利润, 但是由于用户人数较少, 整体利润就偏低, 而用户较多的中间类型反而带来较高的利润.

图 5 不同用户类型的存储量和CPU循环周期数
图 6 不同用户类型的价格和利润
5 结论

本文考虑了移动边缘计算场景下的计算任务分配问题, 提出了基于合约设计的分配决策方案.分别针对完整信息场景和统计信息场景, 设计了最优的CPU运算周期数-数据量-价格三元组构成的合约项, 使得用户选择合适的策略, 从而实现了云服务商利润最大化, 并保证了移动用户参与边缘计算的积极性.

本文的工作仅假设移动用户在当前时刻只有一个固定的计算任务, 属于静态最优合同设计问题.当所有的移动用户都不只有一个计算任务, 而是有源源不断的计算任务流到达边缘服务器时, 如何在保证网络不拥堵的情形下进行计算任务分派, 并最大化云服务商利润是下一步需要开展的工作.

参考文献
[1]
刘国强.基于移动边缘计算的任务卸载策略研究[D].哈尔滨: 哈尔滨工业大学计算机科学与技术学院, 2018.
(Liu G Q. Research on offloading strategy based on mobile edge computing[D]. Harbin: School of Computer Science and Technology, Harbin Institute of Technology, 2018.)
[2]
蒯向春.云网融合应用关键技术研究与设计[D].南京: 南京邮电大学通信与信息工程学院, 2017.
(Kuai X C. Research and design of key technology for cloud-network integration application[D]. Nanjing: College of Telecommunications & Information Engineering, Nanjing University of Posts and Telecommunications, 2017.)
[3]
Zhang K, Mao Y, Leng S, et al. Energy-efficient offloading for mobile edge computing in 5G heterogeneous networks[J]. IEEE Access, 2016, 4: 5896-5907. DOI:10.1109/ACCESS.2016.2597169
[4]
Chen X, Jiao L, Li W, et al. Efficient multi-user Computation offloading for mobile-edge cloud computing[J]. IEEE / ACM Transactions on Networking, 2016, 24(5): 2795-2808. DOI:10.1109/TNET.2015.2487344
[5]
Lin T, Qin D Y, Ma T K, et al. Research on task scheduling based on game theory in mobile edge computing[J]. Computer Simulation, 2018, 35(11): 387-391.
[6]
Dong Q, Ma Y X, Li J. Load balancing oriented scheduling scheme in edge computing network[J]. Applacation Research of Computers, 2018. DOI:10.19734/j.issn.1001-3695.2018.10.0673
[7]
Han K K, Xie Z P, Lv X. Fog computing task scheduling strategy based on improved genetic algorithm[J]. Computer Science, 2018, 45(4): 137-142.
[8]
Ho C K, Yuan D, Sun S. Data offloading in load coupled networks: A utility maximization framework[J]. IEEE Transactions Wireless Communications, 2014, 13(4): 1921-1931. DOI:10.1109/TWC.2014.021214.130809
[9]
Mao Y, Zhang J, Letaief K B. Dynamic computation offloading for mobile-edge computing with energy harvesting devices[J]. IEEE Journal on Selected Areas in Communications, 2016, 34(12): 3590-3605. DOI:10.1109/JSAC.2016.2611964
[10]
Bolton P, Dewatripont M. Contract theory[M]. Cambridge: MIT Press, 2005: 489-551.
[11]
Cao W, Yang B, Chen C, et al. PHEV charging strategy with asymmetric information based on contract design[J]. IFAC Proceedings Volumes, 2013, 46(13): 520-525. DOI:10.3182/20130708-3-CN-2036.00114
[12]
Li Y, Shen B, Zhang J, et al. Offloading in HCNs: Congestion-aware network selection and user incentive design[J]. IEEE Transactions on Wireless Communications, 2017, 16(10): 6479-6492. DOI:10.1109/TWC.2017.2724027
[13]
Duan L, Gao L, Huang J. Cooperative spectrum sharing: A contract-based approach[J]. IEEE Transactions on Mobile Computing, 2014, 13(1): 174-187. DOI:10.1109/TMC.2012.231
[14]
Gao L, Wang X, Xu Y, et al. Spectrum trading in cognitive radio networks: A contract-theoretic modeling approach[J]. IEEE Journal on Selected Areas in Communications, 2011, 29(4): 843-855. DOI:10.1109/JSAC.2011.110415
[15]
Li Y, Zhang J, Gan X, et al. A contract based incentive mechanism for delayed traffic offloading in cellular networks[J]. IEEE Transactions Wireless Communications, 2016, 15(8): 5314-5327. DOI:10.1109/TWC.2016.2555918