一种在随机网络中基于算网协同的分布式计算卸载方法

摘要

本发明属于移动通信技术领域，特别涉及一种在随机网络中基于算网协同的分布式计算卸载方法，包括基于本地计算模型和边缘云计算模型，构建设备端收益最大化问题模型和MEC服务器最大化收益问题模型；根据用户的随机移动和突发计算要求，分别建立停留时间和等待时延的复合场景集合；采用后验追索权行动来补偿博弈策略，建立设备端和MEC服务器双方基于博弈的随机规划模型；过构建场景树，将设备端和MEC服务器双方的多阶段随机规化问题转化为DEP问题，并求解获得MEC服务器卸载的最优任务策略和MEC服务器对设备端的最优报价策略；本发明基于Lyapunov优化理论的扩展博弈论方法，实现了时变环境下任务的动态卸载和自适应计算能力管理。

权利要求

1.一种在随机网络中基于算网协同的分布式计算卸载方法，其特征在于，包括以下步骤：根据UDN环境中设备类型，基于差异化服务质量要求和任务处理成本，分别建立本地计算模型和边缘云计算模型；

基于本地计算模型和边缘云计算模型，在设备端采用Lyapunov优化理论和最小化漂移减效用函数，建立设备端收益最大化问题模型；

基于本地计算模型和边缘云计算模型，在MEC服务器采用最大值理论，建立起MEC服务器最大化收益问题模型；

根据用户的随机移动和突发计算要求，分别建立停留时间和等待时延的复合场景集合；

采用后验追索权行动来补偿博弈策略，建立设备端和MEC服务器双方基于博弈的随机规划模型；

通过构建场景树，将设备端和MEC服务器双方的多阶段随机规化问题转化为DEP问题；

利用Lagrangian乘子和KKT条件求解设备端和MEC服务器双方的优化问题，计算出设备端所选择的MEC服务器卸载的最优任务策略和MEC服务器对设备端的最优报价策略；

若设备端向MEC服务器卸载的最优任务量策略，以及MEC服务器对设备端的最优动态报价策略都满足Stackelberg均衡解，那么设备按照最优任务卸载策略向MEC服务器进行任务卸载。

2.根据权利要求1所述的一种在随机网络中基于算网协同的分布式计算卸载方法，其特征在于，建立设备端收益最大化问题模型包括：约束条件：

0≤Di(t)≤Qi(t),t∈T，

其中，f表示第i个设备的CPU时钟频率集合，D表示时隙t内卸载任务集合， 表示第i个设备的长期收入，Vi为Lyapunov优化理论中非负控制参数，Di,k(t)表示第i个移动设备卸载到位置k处的卸载任务，Ai(t)表示第i个移动设备t时隙到达的任务，T为时隙的索引且T＝{0,1,…}， 表示第i个设备在时隙t的总收益；k∈{L,M,S}为当前任务类型，L表示非卸载任务，M表示卸载到宏基站的任务，S表示卸载到小基站的任务； 为本地服务器处理卸载任务的时间， 表示Di(t)的最大计算延时约束， 为第i个移动设备t时隙内分配的CPU时钟频率的最小值，fi,L(t)为第i个移动设备t时隙内分配的CPU时钟频率，为第i个移动设备t时隙内分配的CPU时钟频率的最大值，Di(t)为在时隙t开始时任务处理决策，Qi(t)为在时隙t开始时任务队列积压， 表示平均队列积压。

3.根据权利要求1所述的一种在随机网络中基于算网协同的分布式计算卸载方法，其特征在于，若将任务卸载到宏基站，则MEC服务器最大化收益问题模型表示为：约束条件：pi,M(t)≥0,t∈T,

其中，pM(t)表示t时隙宏基站的定价合集， 表示宏基站所分配的计算能力集合，表示宏基站的收益，uM[pM(t)]表示宏基站的服务效用， 表示宏基站的任务计算能耗，Di,M(t)表示宏基站处理的任务挤压， 为任务在服务器的等待时延；pi,M(t)表示在每个时隙t内的第i个设备对宏基站的支付成本，T为时隙的索引且T＝{0,

1,…}， 表示时隙t内宏基站总的计算卸载时间， 表示Di(t)的最大计算延时约束，为宏基站中每个CPU核的最小频率， 为当前宏基站中第i个CPU核的频率， 为宏基站中每个CPU核的最大频率。

4.根据权利要求1所述的一种在随机网络中基于算网协同的分布式计算卸载方法，其特征在于，若将任务卸载到小基站，则MEC服务器最大化收益问题模型表示为：约束条件：pi,S(t)≥0,t∈T，

其中，pS(t)表示时隙t中小基站的定价合集， 表示小基站所分配的计算能力集合，表示小基站的收益，uS[pS(t)]表示小基站的服务效用， 表示小基站的任务计算能耗，Di,S(t)表示小基站处理的任务挤压， 为任务在服务器的等待时延， 为在小基站中第i个移动设备的停留时间；pi,S(t)表示在每个时隙t内的第i个设备对小基站的支付成本，T为时隙的索引T＝{0,1,…}， 表示时隙t内小基站总的计算卸载时间， 表示Di(t)的最大计算延时约束， 为小基站中每个CPU核的最小频率，为当前小基站中第i个CPU核的频率， 为小基站中每个CPU核的最大频率。

5.根据权利要求1所述的一种在随机网络中基于算网协同的分布式计算卸载方法，其特征在于，建立停留时间和等待时延的复合场景集合包括：若已知小基站中某一移动设备的可能停留时间以及可能等待时间，根据笛卡尔积获取所有移动设备的停留时间的复合场景以及等待时延的复合场景，则所有移动设备的停留时间的复合场景集合表示为：其中，m为移动设备的个数； 为第i个移动设备的停留时间的复合场景， 为第i个移动设备的等待时延的复合场景。

说明书

一种在随机网络中基于算网协同的分布式计算卸载方法

技术领域

[0001] 本发明属于移动通信技术领域，特别涉及一种在随机网络中基于算网协同的分布式计算卸载方法。

背景技术

[0002] 随着移动互联网和物联网快速发展和融合，移动设备(MDs)(如智能手机、可穿戴设备、自动驾驶汽车等)和面向云应用(如虚拟现实(VR)、增强现实(AR)、在线游戏等)迅速增长，驱动着算力和存储资源推向网络边缘，以减少传输时延和拥塞。多接入边缘计算(MEC)技术可以通过将设备或应用的部分或全部计算任务卸载到边缘云服务器的方式增强用户的服务体验。与此同时，为了满足下一代无线通信网络的要求，超密集网络(UDN)通过在宏基站(MBS)的覆盖范围内部署低功率短距离的小基站(SBSs)，能有效地提高网络吞吐量和接入容量。如图1所示，通过将MEC与UDN融合可以使用户随时随地享受无处不在的网络计算服务，并促进任务计算卸载的连续性。

[0003] 然而，在实际的支持MEC的UDN系统中仍然存在着一些特殊的困难。其主要有：(1)随着物联网时代面向云的设备、应用和数据的快速增长，传统的集中式的优化框架需要系统状态的精确信息(例如流量特点、网络负载、信道状态信息(CSI)等)，这在有很多异构物联网应用的复杂时变的支持MEC的UDN场景下并不是有效率的。(2)由于随机移动，移动设备将在不同的无线边缘云接入点之间不断地切换，这会增加任务重卸载和资源重分配的开销，并且严重降低了计算卸载性能。现有技术的一些主要的成果有：(1)车载互联网移动感知和动态迁移服务(参考文献：I.Labriji,F.Meneghello,D.Cecchinato,S.Sesia,E.Perraud,E.C.Strinati and M.Rossi,“Mobility Aware and Dynamic Migration of MEC Services for the Internet of V ehicles,”IEEE Transactions on Network and Service Management,vol.18,no.1,pp.570‑584,March 2021)：该算法在MEC服务器下，通过预测停留时间，进行比例计算卸载。(2)物联网‑边缘云计算系统中的节能和延时保证工作负载分配算法(参考文献：M.Guo,L.Li and Q.Guan“, Energy‑Efficient and Delay‑Guaranteed Workload Allocation in IoT‑Edge‑Cloud Computing Systems,”IEEE Access,vol.7,pp.78685‑78697,2019.)：在该算法中具有不同功能特性的轻量级边缘云服务器种类繁多，不能快速、及时地响应突发性计算需求，在服务器中卸载任务有一个不确定的等待时延(包括任务队列、减压、安全分析等)，这意味着卸载和资源分配决策不应仅考虑网络边(通信因素)，还应包含服务边(实际可获得的计算能力因素)，尤其是延时敏感型的应用，但是现有技术中缺少在随机和时变的网络环境下的任务卸载需求。

发明内容

[0004] 为了满足在随机和时变的网络环境下，大规模物联网应用日益增长的需求，本发明提出一种在随机网络中基于算网协同的分布式计算卸载方法，包括以下步骤：

[0005] 根据UDN环境中设备类型，基于差异化服务质量要求和任务处理成本，分别建立本地计算模型和边缘云计算模型；

[0006] 基于本地计算模型和边缘云计算模型，在设备端采用Lyapunov优化理论和最小化漂移减效用函数，建立设备端收益最大化问题模型；

[0007] 基于本地计算模型和边缘云计算模型，在MEC服务器采用最大值理论，建立起MEC服务器最大化收益问题模型；

[0008] 根据用户的随机移动和突发计算要求，分别建立停留时间和等待时延的复合场景集合；

[0009] 采用后验追索权行动来补偿博弈策略，建立设备端和MEC服务器双方基于博弈的随机规划模型；

[0010] 过构建场景树，将设备端和MEC服务器双方的多阶段随机规化问题转化为DEP问题；

[0011] 利用Lagrangian乘子和KKT条件求解设备端和MEC服务器双方的优化问题，计算出设备端所选择的MEC服务器卸载的最优任务策略和MEC服务器对设备端的最优报价策略；

[0012] 若设备端向MEC服务器卸载的最优任务量策略，以及MEC服务器对设备端的最优动态报价策略都满足Stackelberg均衡解，那么设备按照最优任务卸载策略向MEC服务器进行任务卸载。

[0013] 本发明基于Lyapunov优化理论的扩展博弈论方法，实现了时变环境下任务的动态卸载和自适应计算能力管理；在此基础上，考虑到用户的移动性和有限的边缘资源导致的计算和网络不确定因素，提出了多目标不确定条件下的分布式两阶段和多阶段随机规划算法，并且本发明可以采取后验补救措施来补偿不准确的预测网络信息。

附图说明

[0014] 图1为一种典型的支持MEC的UDN环境；

[0015] 图2为本发明中一种基于多目标不确定性下的超密集网络的分布式计算能力与网络协作方法流程图；

[0016] 图3为本发明中任务处理和时隙模型；

[0017] 图4为本发明中第i个移动设备的停留时间情景树；

[0018] 图5为发明中追索与补偿过程示意图；

[0019] 图6为发明中价格随迭代次数的变化过程图；

[0020] 图7为发明中卸载的任务随迭代次数的变化过程图；

[0021] 图8为本发明中计算卸载性能随时间变化(V＝500，V表示漂移减效用函数中的非负控制参数)示意图；

[0022] 图9为本发明中计算卸载性能随V变化示意图。

具体实施方式

[0023] 下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

[0024] 本发明提供一种在随机网络中基于算网协同的分布式计算卸载方法，包括以下步骤：

[0025] 根据UDN环境中设备类型，基于差异化服务质量要求和任务处理成本，分别建立本地计算模型和边缘云计算模型；

[0026] 基于本地计算模型和边缘云计算模型，在设备端采用Lyapunov优化理论和最小化漂移减效用函数，建立设备端收益最大化问题模型；

[0027] 基于本地计算模型和边缘云计算模型，在MEC服务器采用最大值理论，建立起MEC服务器最大化收益问题模型；

[0028] 根据用户的随机移动和突发计算要求，分别建立停留时间和等待时延的复合场景集合；

[0029] 采用后验追索权行动来补偿博弈策略，建立设备端和MEC服务器双方基于博弈的随机规划模型；

[0030] 过构建场景树，将设备端和MEC服务器双方的多阶段随机规化问题转化为DEP问题；

[0031] 利用Lagrangian乘子和KKT条件求解设备端和MEC服务器双方的优化问题，计算出设备端所选择的MEC服务器卸载的最优任务策略和MEC服务器对设备端的最优报价策略；

[0032] 若设备端向MEC服务器卸载的最优任务量策略，以及MEC服务器对设备端的最优动态报价策略都满足Stackelberg均衡解，那么设备按照最优任务卸载策略向MEC服务器进行任务卸载。

[0033] 实施例1

[0034] 本实施例对本发明根据UDN环境中设备类型，基于差异化服务质量要求和任务处理成本，分别建立本地计算模型和边缘云计算模型的过程进行详细说明。

[0035] 在本实施例中，如图1，考虑一个工作在离散时间上的支持MEC的UDN系统，令T＝{0,1,…}和τ∈T，T表示时隙索引，τ表示每个时隙的持续时间。系统包含一个宏基站(MBS)和n个小基站(SBS)。令N＝{1,…,n}表示n个SBS的集合，M和S∈N分别表示MBS和第S个SBS。M＝{1,…,m}表示m个移动设备(MD)。每个基站都配备了具有计算能力的MEC服务器，该服务器可以在其覆盖范围内为MD提供计算能力，MD可以在本地处理任务，或者卸载任务到基站的MEC服务器。每个MD可以采用5G网络开发的双连接或CoMP技术，同时连接到MBS和附近的一个SBS。

[0036] 令MDi表示第i个移动设备，MDi请求处理的任务可以用四元组来表示，其中Qi(t)和Di(t)分别表示在时隙t开始时，任务队列积
压和任务处理决策， 表示Di(t)的最大计算延时约束，γi为可以通过离线测量获得的计算密度，单位为cycles/bit。

[0037] 令Ai(t)表示MD i(i∈M)到达的任务，A(t)＝{A1(t),…,Am(t)}表示时隙t内所有MD的集合。由于在一个时隙内到达的任务是有限的，可得 为最大到达的任务。假设所有MDs的任务到达率是独立同分布的；进一步，MD i的队列积压的更新+
方程可表示为Qi(t+1)＝[Qi(t)‑Di(t)] +Ai(t)，i∈M，t∈T，其中
Di,L(t)、Di,M(t)和Di,S(t)分别表示本地、MBS和SBS处理的任务
挤压。

[0038] 在每个时隙开始时，每个移动设备需要确定任务卸载策略：非卸载任务Di,L(t)和卸载任务Di,k(t)，k∈{M,S}的数量。如图3所示，卸载有三个阶段，即：

[0039] 1)MDs通过无线信道将计算任务Di,k(t)上传到BSs，并假设任务上传时延为[0040] 2)在服务器中等待一段时间后，称其为等待时延

[0041] 3)卸载的任务将会被服务器处理，处理时间为

[0042] 无论在哪里处理任务，必须在约束时间 内完成，否则，将会被视为处理失败。

[0043] 由于移动设备的电池容量是有限的，为了在有限的时间内实现节能，MD可以使用由动态电压频率调整(Dynamic Voltage and Frequency Scaling，DVFS)技术确定的合适的CPU时钟频率来处理任务。令 表示已处理的任务与本地计算资源间的关系，其中 为本地执行时间，fi,L(t) 为时隙内分配的CPU时
钟频率(周期/s)， 和 分别表示MD i的最小和最大的CPU时钟频率。

[0044] 对于每一个MD，本发明假设设备的能量消耗主要由CPU工作产生。通常，CPU工作的能量消耗为 其中ki为有效能量系数，该系数与设备的芯片结构有关，可以通过离线测量获得。

[0045] 为了不失一般性，本发明做出以下三个假设：

[0046] 1)如果MDs在MBS和SBSs的覆盖范围内，则可以在每个时隙内同时与MBS和附近的一个SBS进行通信，即，MD可以将任务同时卸载到MBS和附近的一个SBS中；

[0047] 2)由于MDs的随机移动和突发性计算需求，SBS中的停留时间 和不同BSs中的等待时延 是随机且独立同分布的；

[0048] 3)当MDs在将任务上传到SBS的同时离开SBS的无线覆盖范围时(上传任务表示为)，剩余的任务 必须首先上传到MBS，然后MBS通过有线光纤网络转发到SBS。

[0049] 对于延时敏感性应用，任务上传延迟必须小于约束时间，即 否则，任务注定执行失败。因为计算结果通常比大部分应用的输入任务小得多，所以本发明忽略从基站下载计算结果的时间开销。一旦每个MD决定卸载任务到MBS和附近的SBS，任务上传时延和通信能量开销如下：

[0050] 1)卸载任务到MBS的MEC服务器

[0051] 对于每个MD，任务的输入比特需要通过无线信道传递给MBS。需要注意的是，随着用户数量的增加，UDN的干扰环境更加复杂。因此，卸载决策应该考虑设备之间的功率干扰。根据Shannon‑Hartley公式，上传数据速率表示为：

[0052]

[0053] 其中，ωM和gi,M(t)分别为无线带宽和MBS的信道增益；σ2(t)是平均背景噪声功率，Pi(t)是时隙t中MD i的通信功率，1(·)是指示函数。

[0054] 因 此 ，M B S的 任 务上 传 时 延为 通 信能 耗 为

[0055] 2)卸载任务到SBS的MEC服务器

[0056] MD i卸载任务Di,S(t)到SBS的MEC服务器，上传数据速率表示为：

[0057]

[0058] 其中，ωS和gi,S(t)分别表示无线带宽和SBS的信道增益。

[0059] 通常，SBS的无线覆盖范围小于MBS。根据先前提到的假设，如果MDs在上传任务期间离开SBS的无线覆盖范围，剩余的任务将首先上传到MBS，然后转发到SBS。因此，SBS的上传时延表示为：

[0060]

[0061] 其中 ， 是 SB S中M D  i的 停留 时间 ， 和分别表示剩余任务的上传时延和转发时间；c是光纤链路的数据速
率。

[0062] 因此，MD i上传Di,S(t)到SBS的通信能耗表示为：

[0063]

[0064] MD i在时隙t内的总能耗为：

[0065]

[0066] MBS/SBS的总的计算卸载时间为：

[0067]

[0068] 为了确保卸载的任务能被及时处理，在每个时隙，总的计算卸载时间 (包括上传时间，等待时延，处理时间)不超过约束时间

[0069] 假设MEC服务器配备有一个Lk核的CPU，CPU核的集合为MEC服务器的任务Di,k(t)处理能耗 其中 和
分别表示MEC服务器中有效交换电容和第lk个CPU核的CPU时
钟频率； 和 分别是每个CPU核的最小和最大CPU时钟频率。

[0070] 实施例2

[0071] 本实施例通过实施例1的构建的本地计算模型和边缘云计算模型，计算其处理任务需要消耗的资源成本。

[0072] 通过实施例1构建的本地计算模型和边缘云计算模型，可知计算卸载时延强烈地依靠于任务的通信时延、等待时延和处理时延。为了确保卸载的任务在约束时间 内处理，必须考虑计算因素(计算等待时间 计算能力fi,L和 )和网络因素(停留时间通信时间 )。

[0073] 为了评价任务处理性能，本发明首先定义了任务处理效用函数和任务处理成本函数。对于每个MD，为了评估每个时隙中处理任务的收益，本发明采用对数效用函数，该函数被广泛的使用在无线通信和移动计算领域，MD i的效用其中，ρi是MD i的效用权重参数。

[0074] 若MBS上的传输任务为：

[0075]

[0076] SBS上的传输任务为：

[0077]

[0078] 则MD i的通信成本表示为：

[0079]

[0080] 其中，θi和ηi分别表示MBS和SBS中MD i的单位比特的通信成本。

[0081] 为了简化分析，本实施例假设单位能耗成本为 因此，能耗成本

[0082] 为了改善用户的计算卸载服务体验，云服务器提供商需要消耗自己的成本。很明显，卸载服务不是免费的，边缘云服务器通常需要补偿才能分享他们的资源。令pi,k(t),k∈{M,S}($/bit)表示每个时隙t内，对于BS k的MD i的单位支付成本，则MD i的计算服务成本BS k的服务效用其中， 表示MBS或者SBS的定价策略集合。

[0083] 实施例3

[0084] 基于实施例1构建的本地计算模型和边缘云计算模型以及实施例2计算得到卸载任务需要消耗的资源成本，本实施例基于Lyapunov优化理论和最小化漂移减效用函数，建立设备端收益最大化问题模型以及MEC服务器最大化收益问题模型。

[0085] 本发明首先将任务卸载和计算资源分配问题描述为确定性优化问题，其中，假设停留时间 S∈N和计算等待时间 k∈{M,S}是事前已知的。

[0086] 本发明假设移动设备永远是理性的，并且会寻求一个最优的卸载决策去最大化其长期收入。MDs/买方的最优决策应该将已卸载的任务、通信成本、能量成本和支付成本考虑在内。通过上述分析，MD/买方i在时隙t的目标函数表示为：

[0087]

[0088] 为了保证长期演进中的计算性能，对于MD/买方i，设备端收益最大化问题模型表示为：

[0089]

[0090]

[0091]

[0092] 0≤Di(t)≤Qi(t),t∈T，

[0093]

[0094] MD i的计算任务队列的Lyapunov函数为 其中Li(Qi(t))≥0。则条件Lyapunov漂移为Δ(Qi(t))＝E{Li(Qi,t+1)‑Li(Qi(t))|Qi(t)}。

[0095] 线上最优决策的基本目标是最小化漂移减效用函数的上界，其定义为Δ(Qi(t))‑ViE{Ui[Di(t)]|Qi(t)}，其中，Vi≥0是非负控制参数。为了得到漂移减效用函数的上界，则对于在任何可能决策下任意给定的控制参数Vi≥0和 有：

[0096] Δ(Qi(t))‑ViE{Ui[Di(t)]|Qi(t)}

[0097] ≤Bi+Qi(t)Ai(t)‑E{Qi(t)Di(t)|Qi(t)}‑ViE{Ui[Di(t)]|Qi(t)}[0098] 其中，

[0099] 最小化漂移减效用函数的上界等于最小化上述不等式的右端(RHS)。因此，可将最优化问题P1‑buyer转换为：

[0100]

[0101]

[0102]

[0103] 0≤Di(t)≤Qi(t),t∈T，

[0104]

[0105] 对于BSs(基站)/卖方，根据和 MBS/SBS的收益 定义分别如下：

[0106]

[0107] s.t.pi,M(t)≥0,t∈T,

[0108]

[0109]

[0110]

[0111] s.t.pi,S(t)≥0,t∈T，

[0112]

[0113]

[0114] MBS和SBS的收益都与时隙t中的定价集合pi,k(t)、分配的计算能力 和计算等待时延 有关。为了确保卸载的任务在约束时间内被处理，SBSS需要考虑MD i的等待时间 此外，基于最大值理论，可将问题P1‑seller转化为问题：

[0115]

[0116]

[0117]

[0118]

[0119]

[0120]

[0121]

[0122]

[0123] 根据P2‑seller，每个卖方将通过每个时隙内的用户需求Di,k(t)和当前网络状态(如计算等待时间 和停留时间 )定期公布最新一轮的市场价格pk(t)。随着需求和网络状态的改变，卖方将动态地改变定价策略直到达到市场均衡。与此同时，所分配的计算能力 将进行自适应调整。

[0124] 实施例4

[0125] 在实施例3中，本认为停留时间 和等待时延 是完全已知的。然而，由于用户的随机移动和突发计算要求，在每个时隙开始时，停留时间和等待时延都是不确定的。可以通过使用平均历史值或预测它们来做出决策，但是，在现实的时变环境里，高精度的预测是很困难的。这些不精确的结果将不可避免地影响计算性能和卸载成功率。例如，如果预测的结果比实际的停留时间和等待时延更大，这将导致计算卸载成本增加，甚至是卸载失败。在这一点上，本发明采用两阶段随机规划的方法来采取后验补救措施，补偿先前不精确的预测。

[0126] 为了处理不确定的停留时间 和等待时延 本发明首先考虑一个场景的集合，该场景有一系列不确定的参数。令 表示SBS中MD i的可能的停留时间的场景集合，令 表示BS k,k∈{M,S}中MD i的可能等待时延的场景集合。根据笛卡尔积，可得所有MDs的停留时间的复合场景 和等待时延的复合场景 可以分别表示为：

[0127]

[0128]

[0129] 注意到，根据 MDs的收益与停留时间场景 有关。因此，MBS和SBSs的收益分别与 和
的复合场景有关，其中ΩS(t)是复合时间(SBS中停留时间和等待时
延)的复合场景。接下来，本发明分析基于博弈的分布式两阶段随机规划模型。

[0130] 为了简化分析过程，本发明接下来主要分析SBS，根据SBS可以很容易地推导出MBS的分析过程。

[0131] 在不确定和时变的网络环境中，随机变量的实际值只有在实现后才知道，即，停留时间 和等待时延 只有在博弈结束后并将卸载的任务上传到云端后才知道。但是，在观察实际情况后，仍可以采用后验追索权行动来补偿博弈策略。根据随机规划理论，本发明将决策集分为两组：

[0132] 第一阶段(博弈阶段)决策：任务卸载Di(t)和公布价格pi,S(t)的策略必须在通过博弈知道 和 之前采取，这个阶段称为第一阶段或博弈阶段。

[0133] 第二阶段(追索阶段)决策：计算能力分配 可以在观察 和 的实现情况后进行。称之为第二阶段决策，相应的阶段被称为第二阶段或追索阶段。

[0134] 令 和 分别表示时隙t中停留时间的实现和复合实现。令 p[ωS(t)]∈[0,1]为概率。根据随机规划理论，P2‑buyer的最优问题可表示为一个两阶段随机规划问题，即：

[0135]

[0136]

[0137]

[0138] 0≤Di(t)≤Qi(t),t∈T，

[0139]

[0140] 同样地，P2‑seller(SBS)的最优问题可表示为如下，

[0141]

[0142] s.t.pi,S(t)≥0,t∈T，

[0143]

[0144]

[0145] 其中 为追索权函数。

[0146] 宏基站的最优问题表达式本领域可以根据上述小基站表达式推导得出，本实施例不再赘述。

[0147] 实施例5

[0148] 如图1所示，每个MD可以在两个或者多个SBSs间随机移动。然而，基于两阶段随机规划的博弈策略在每个时隙中只需决定一次，这可能会得到次优解。基于这一点，更精确地捕捉 和 统计特征，从而更好地依此制定卸载、定价和计算能力分配策略，利用多阶段随机规划进一步地发展博弈策略。在多阶段随机规划中，计算卸载过程被划分为H个子切片 在子切片τh中，通过多阶段随机规划，任务卸载Di(τh),τh∈H、价格pi,S(τH)和计算能力分配 是最优的。令 和ξS(τh)表示在子切片τh内，可能的停留时间和复合时间。在所有子时隙中 ，所有合成 场景的 停留时间 为
复合时间为

[0149] 讲一个卸载任务的任务时间t划分为H个子时隙之后，一个具有2H个阶段的分布式随机规划模型如下：

[0150] MD/买方i的任务卸载最优问题可以改写为P3‑buyer(multi‑stage)优化问题：

[0151]

[0152]

[0153]

[0154]

[0155] 其中，Di(τh)和fi,L(τh)为子时隙τh中，MD i的已处理的任务和本地计算频率。

[0156] 同样地，SBSs/卖方优化问题重写为：

[0157]

[0158] s.t pi,S(τh)≥0,τh∈H，

[0159]

[0160]

[0161] 是为了确保所有子切片的计算卸载时间之和不超过约束时间

[0162] 同理，本领域技术人员可以通过以上小基站多阶段随机模型构建思路构建宏基站多阶段随机模型，本发明不再赘述。

[0163] 实施例6

[0164] 本实施例使用场景树来解决P3‑buyer(multi‑stage)和P3‑seller(multi‑stage)中的优化问题，将随机规划问题转化为确定性等式规划(DEP)。

[0165] 定义 和πS∈ξS分别是 和ξS的实现。场景树根据 和ξS(τh),τh∈H的实现进行分支。图4是MD/买方i的停留时间的一棵典型的场景树，其中有两个实现来描述τh∈H的演变。在停留时间场景树中，根节点与第一决策阶段相关联，该决策阶段没有观察到停留时间。根节点与子节点相连，子节点与进一步的阶段相关联，每一个节点都与下一阶段相关联的子节点相连，直到叶节点位置，各子节点有两个实现是关联两个随机停留时间的

[0166] 通过构建场景树，本发明将P3‑buyer(multi‑stage)和P3‑seller(multi‑stage)的买卖双方随机规划问题转化为DEP问题，即：

[0167] 令 表示停留时间场景树中，从根节点到叶子节点的路径。一旦给出一个场景将会确定。令Di(τ1)和Di(τh)分别表示根节点的任务卸载决策和路径中第2h个阶段的节点的卸载决策。然后，MD/买方i的多阶段随机规划能转化成如下的DEP问题：

[0168]

[0169]

[0170]

[0171]

[0172]

[0173]

[0174] 其中 是场景 的概率，约束 为非预期性约束，这表示卸载决策在不同路径中应该是等价的。

[0175] 同样地，令 表示复合场景树中从根节点到叶子节点的路径。对于一个给定的场景πS∈ξS(τh)，SBSs/卖方的DEP模型如下：

[0176]

[0177] s.t.pi,S(τh)≥0,τh∈H，

[0178]

[0179]

[0180]

[0181]

[0182] 其中，p(πS)是场景πS的概率， 是路径 中在第h阶段处理的任务。

[0183] 在每个子时隙中，包含两个阶段。如图5所示，偶数阶段将对奇数阶段采取计算能力追索行为βi,S(τh)，以补偿子时隙中不确定的停留时间和计算等待时延。后一子时隙对前一子时隙采取卸载任务追索行为Di,S(τh)，使补偿更准确，并确保卸载任务能在约束时间内被处理。一般情况下，多阶段随机规划求解的最优策略与阶段数有关，阶段划分越多，求解策略越优化，但求解过程越复杂。

[0184] 实施例7

[0185] 本实施例对本发明前述的资源分配策略进行分析。为了分析简化，本发明分析一个阶段的最优博弈策略，它可以很容易地以同样的方式扩展到多个阶段。

[0186] 1.最优博弈分析

[0187] 1)MDs最优策略分析

[0188]

[0189]

[0190]

[0191] 根据P2‑buyer，可得如上所示的一阶偏导 和 此外，可得二阶偏导 和 因为
0≤Di(t)≤Qi(t),t∈T和 是仿射函数， 在Di(t)上是
凸的。买方/MDs的优化问题可通过Lagrangian乘子和Karush‑Kuhn‑Tucker(KKT)条件求解，最优策略如下所示，

[0192]

[0193]

[0194] 其中：

[0195]

[0196]

[0197]

[0198] 2)BSs的最优策略分析

[0199] 根据P2‑seller(SBS)，可得 对pi,k(t)的一阶偏导，

[0200]

[0201] 如果市场的交易价格满足pi,k(t)≥0，可得

[0202] 此外，因为pi,M(t)≥0,t∈T、 pi,S(t)≥0,t∈T、 都是仿射函数， 对于pi,k(t)
是凸函数。BSs/卖方的最优问题可以通过Lagrangian乘子和KKT来求解，最优策略为：

[0203]

[0204] 其中

[0205] 定 义 1 ：如 果 卖 家 k 的 定 价 p i , k ( t ) 是 确 定 的 ， 满 足如果买方i的卸载任务Di,k(t)是确定的，满足

[0206] 现在，本发明将通过以下三个引理证明最优解 是

[0207] 引理1：如果BS/卖方k的价格pi,k(t)固定，MD/买方的收益函数Ybi(Di,k(t))在处取得最大值。

[0208] 证明：根据上述分析，可知对于Di,k(t)， 是凸的。因此，收益函数 在处取得最大值，根据定义1， 是SE解

[0209] 引理2：对于买方，最优卸载任务 随着卖方的价格pi,k(t)的增加而减少。

[0210] 证明：根据 可得：

[0211]

[0212] 因此，可得 是pi,k(t)的单调递减函数。这意味着，如果交易价格上涨，买方卸载的任务将会减少，这会导致卖方的收入很少，甚至没有。因此，卖方应该采取合适的价格去最大化收益。通过解 可得卖方的最优价格。

[0213] 引理3：如果MD/买方i的最优卸载任务 固定， 在 处取得最大值。

[0214] 证明：本发明已证明，卖方的收益 对pi,k(t)是凸的。因此根据定义1，在 处取得最大值， 是SE解

[0215] 简言之， 是最优任务卸载和定价决策，它同时也是SE解

[0216] 从图6～7可以看出，价格更新的迭代是不减的，随着迭代次数的增加，价格逐渐收敛到最优定价策略，图6以迭代次数等于50处为准从上到下四条曲线分别是MBS博弈第二阶段、MBS博弈第一阶段、SBS博弈第一阶段以及SBS博弈第二阶段，图7以迭代次数等于50处为准从上到下四条曲线分别是SBS博弈第二阶段、SBS博弈第一阶段、MBS博弈第一阶段以及MBS博弈第二阶段；与此同时，卸载任务的数量随着价格的增加而逐渐减少，当价格不再增加时卸载策略也达到稳定，验证了该方法的有效性。从图8～9可以看到，市场上的交易价格随着买家的任务队列积压而逐渐增加，而买家的收益随着卸载成本的增加的逐渐减少，从图9可知，在平均队列积压和收入之间存在[O(1/V),O(V)]的折中，验证了该方法的合理性。

[0217] 在本发明实施例中，下标S表示与小基站相关的参数，下标M表示与宏基站相关的参数，下标i表示某一移动设备的相关参数。

[0218] 尽管已经示出和描述了本发明的实施例，对于本领域的普通技术人员而言，可以理解在不脱离本发明的原理和精神的情况下可以对这些实施例进行多种变化、修改、替换和变型，本发明的范围由所附权利要求及其等同物限定。