移动边缘计算中分布式的设备发射功率优化算法

周文晨,方维维,李阳阳,薛峰,王子岳

(1.北京交通大学计算机与信息技术学院,100044,北京;2.中国电子科学研究院创新中心,100041,北京)

近年来,移动互联网快速发展,移动用户设备数量呈指数爆炸式增长[1],移动计算需求不断升级。根据思科公司最新预测报告显示,2021年全球移动数据流量将比2016年增长7倍,全球移动设备数量将增加到116亿[2],但目前以长距离数据传输和集中式大数据处理为特点的移动云计算不仅占用大量网络带宽,而且传输时延较大,已无法满足时延敏感型业务,例如无人驾驶汽车、医疗大数据和智慧城市等的需求[3]。

欧洲电信标准化研究所(ETSI)在2014年首次提出移动边缘计算(MEC),移动设备可将高复杂度、高能耗计算任务卸载到MEC系统的接入网边缘节点,例如基站、无线接入点等,从而获得低时延、近距离的本地化云服务[4]。MEC系统结合了移动通信[5]和云计算[6]两种技术,通过协同优化通信和计算资源实现低能耗、低时延的计算卸载服务。目前,最新的MEC系统研究将关注点放在单服务器多用户条件下的通信、计算资源分配控制,以实现总体能耗最优。Mao等基于随机优化模型的优化方法,联合本地计算功率、最优发射功率和无线带宽资源等约束对移动设备能耗进行优化,但是却无法有效约束时延,且计算复杂度较大,没有考虑某个区域内MEC系统的整体部署优化[7];Liu等通过采用马尔可夫决策过程理论对任务队列的排队属性进行分析,提出了发射功率约束条件下的最小化处理时延的问题,但忽略了设备的能耗[8];You等针对TDMA、OFDMA两种网络工作模式,通过确定卸载量和时间槽,解决卸载通信和本地计算总体能耗最小化的凸优化问题,但是所提算法需要依赖于本机计算能量和信道增益的先验知识做出资源分配策略,降低了实际场景的可用性[9]。

综上所述,本文以MEC系统的多服务器、多用户的大规模场景下的计算卸载的时延和能耗的平衡为研究目标,基于边缘计算的通信和计算资源的耦合约束,设计一种基于马尔可夫近似的分布式发射功率优化算法(TPO)。该算法基于马尔可夫状态概率跳转规则设计,移动用户设备自主决策计算卸载的服务器对象,从而有效降低系统级用户功耗。理论证明,分布式TPO算法具有稳态概率分布的马尔可夫链,所设计的转移速率满足马尔可夫链的状态相互转换条件;实验仿真结果表明,所提算法显著优于基准算法,并在有效时间内逼近最优解决方案。

1 MEC系统建模

本文研究的MEC系统场景示例如图1所示。根据已有的相关研究,本文基于以下5种假设:①每个边缘服务器时间和频率完全同步;②每个边缘服务器上的每个载波的信道增益在特定时间内保持恒定;③由于每个边缘服务器的载波频率不同,假设MEC系统中边缘服务器间不存在信号干扰;④设备同一时刻只能与一个边缘服务器进行连通;⑤卸载所需要执行的指令都可以利用边缘服务器进行处理[10-13]。

图1 多MEC服务器多用户设备场景示例

假设当前区域内有M个边缘服务器X={1,2,…,M}和N个移动用户设备Y={1,2,…,N}。每个移动用户设备n的计算任务卸载到边缘服务器m,设备n必须传送所有信息到服务器m。设定执行程序的参数:①每秒输入比特数;②需要被MEC服务器执行计算的指令集;③每秒输出比特数。对于移动用户设备n所需要卸载到服务器m的计算任务的输入数据大小为Cmn,执行的指令数为Dmn=Dmn(Cmn)。设备n是否卸载计算任务到服务器m主要取决于如下因素:需要被处理的指令数、设备n与对应服务器m之间的无线信道状况和服务器m的并行多个进程的能力大小,同时每个进程为了用户的满意体验都规定了不应超过的最大时延[14],因此移动用户设备n决定卸载计算任务到服务器m之前必须考虑时延约束。在没有解码错误的前提下,用户设备n的时延应该包含将输入信息传输到对应服务器m的时间、服务器m执行指令所需的时间和将结果返回给设备n的时间。

根据香农定理,在加性白高斯噪声(AWGN)、信道带宽为B的信道上传送Cmn数据所需的最小时间为

(1)

式中:Pn是设备n计算任务卸载的发射功率;|Hmn|2是信道衰落系数(归一化距离);Gmn是信噪比裕度;dmn是设备n和相连MEC服务器m的物理距离;γ是路径损耗指数;N0是噪声功率。Pn是可调功率,Pn∈S,S是有限离散集合。

(2)

服务器m执行指令所需的时间与其资源分配方式有直接关联。系统内用户设备与服务器的连接方式表示为

(3)

(4)

忽略服务器m把计算结果返回给设备n的极短时间[11],则设备n的平均计算卸载的时延为

(5)

(6)

Pn∈S,n∈Y

xmn∈{0,1},m∈X,n∈Y

基于香农定理和链路传输特性将用户功率最小化策略建模成问题(6),作为典型的组合网络优化问题,其求解复杂度是NP难的,一般只能通过集中式的穷举搜索获得最优解[15],可行解空间随着网络规模的增大而呈指数级增加,而随机法又不能获得稳定而较优的解,因此有必要寻求一种有效和稳定的求解方法。

2 TPO算法设计

针对问题(6),设计了一种分布式并发的优化算法,利用Log-Sum-Exp函数[15]将问题转化为最小权重配置的近似问题,然后使用马尔可夫近似[15]求解问题,即通过求解转化后的问题从而趋近问题(6)的最优解,并证明算法可进行有效求解。

2.1 Log-Sum-Exp原则

设定配置f={xmn,m∈X,n∈Y},即问题(6)所表示的系统中移动用户设备n和边缘服务器m相连的可行配置状态,所有可行的状态f组成F,即f∈F,则问题(6)的等效问题模型是

(7)

问题(7)是NP难的网络组合优化问题,对实际系统来说可行集合F非常大,因此通过Log-Sum-Exp函数,将问题(7)近似转化为

(8)

式中β是正的常数。因为问题(8)的目标函数对于所有的ρf是二次可微、单调递增和严格的凹函数,其所有的约束都是线性的,所以Karush-Kuhn-Tucker(KKT)条件对于最优解是必要和充分的,故问题(8)的最优解是

(9)

与原问题(6)相比,近似问题(8)存在一个额外的熵项,即为优化差距,通过对比两问题的表达式可知优化差距的上限是

(10)

从式(10)可知,优化差距上限的大小取决于β,当β增加时,优化差距上限会减小,这意味着近似求解结果更加准确,优化差距上限r*=lb|F|/β,此时ρf=1/|F|,f∈F,同时由文献[16]可知,当β增加时,收敛时间将增加。

综上可知,当β增加时,近似求解获得的系统移动用户设备发射总功率更加准确,因此选择相对较大的β来获得稳态分布。通过马尔可夫近似获得的近似系统功率可表示为

(11)

2.2 TPO算法设计

根据文献[15]可知,状态转移速率有很多设计选择,将其设计为

(12)

马尔可夫链通常具有分布式的结构,因此可以设计分布式算法以实现符合马尔可夫链的移动用户设备的决策算法[17]。算法设计的关键是建立不同配置f之间的链接,实现最小化转换配置的系统级功率,通过每次只执行一个用户设备切换服务器的选择来连接系统两个配置的链接。本文将算法命名为发射功率优化(TPO)算法,TPO算法分为以下4个步骤。

步骤1每个移动用户设备随机选择MEC服务器,初始化计算资源和设备时延约束等信息。

步骤2当前状态定义为配置f,每个用户设备计算自己的发射功率并广播,同时生成均值为ζ的指数分布随机数,根据随机数进行倒计时,最先到期的用户设备n将随机切换到新MEC服务器,并通知其他所有用户设备终止倒计时。

步骤3进入新配置f′,每个用户设备重新计算自己的发射功率并广播。用户设备n根据配置f和f′的系统移动用户设备发射总功率的改变做出决策,以概率ρf,f′停留在新的MEC服务器或者以概率(1-ρf,f′)切换到原先的MEC服务器,其中

(13)

步骤4重复步骤2～步骤4,直至收敛。

2.3 TPO算法可行性证明

定理1TPO算法实现了一个时间可逆的马尔可夫链,其稳态分布如式(9)所示。

证明通过算法步骤2的移动用户设备的转换条件可知,所有配置可以在有限转换次数内相互可达,因此构造的马尔可夫链是不可约的。此外,它是具有唯一稳态分布的有限状态遍历马尔可夫链。现在证明稳态分布表达式是式(9)。

基于式(12)设定的系统状态转移速率可得

(14)

它满足细致平衡等式,证毕。

定理2通过上述完备的马尔可夫链设计,对于任意两个满足相互转换条件的配置f,f′∈F,转移速率是式(12)。

证明从系统的角度来看,状态f转移到状态f′是由于配置f下的设备n切换服务器所致,设备n从已连接的MEC服务器断开,随机切换到新的服务器,可切换的服务器有M-1个。故对于设备n离开状态f转移概率为

其中配置f∈F是马尔可夫链的状态之一,因为设备根据均值为ζ的指数分布随机数进行倒计时,倒计时结束后进行服务器切换,因此状态f转移到状态f′的转移速率为

因此,转移速率与式(12)相等,证毕。

本文算法满足近似最优解,是可行设计。

3 仿真与结果分析

3.1 实验设置

为了验证TPO算法的有效性和稳定性,采用C++编程进行仿真实验,与随机法和穷举法的实验结果进行对比,得到关键参数对系统的影响。参数设置见表1[11,18]。移动用户设备n的输入数据大小Cmn设定为(0.2+0.02n)MB,为简化起见,设定MEC服务器执行的指令数Dmn与输入数据大小Cmn成线性相关,即Dmn=σCmn。集合S={0w,10-2w,2×10-2w,…,10w}。

表1 TPO算法仿真参数

3.2 实验结果分析

因采用穷举搜索获得系统N个移动用户设备与M个MEC服务器的连接方式的最优解共需计算MN次,复杂度过高,因此我们将TPO算法与随机法实验结果进行对比。图2分别给出了TPO算法与随机法得到的系统用户设备发射总功率。从图2可知,虽然TPO算法实现的系统用户设备发射总功率平均值在算法执行初期比随机法平均值大,但是在50次迭代后小于随机法平均值。TPO算法实现的总功率均值随着算法迭代次数逐步下降,可收敛至4.6 W,而多次随机法的均值为21.4 W,由此可推算出TPO算法性能比随机法的效果提升了78.5%,因此TPO算法不仅可行,并且得到的收敛解比随机法结果更趋近最优解,更加有效。

图2 TPO算法与随机法对比

为了进一步验证TPO算法的准确性,建立4个MEC服务器服务10个用户设备的小型MEC系统场景,在此场景下对比分析TPO算法多次实验平均值和穷举搜索最优结果。图3给出了TPO算法与穷举搜索实现的系统用户设备发射总功率。实验数据显示,TPO算法实现的系统用户设备发射总功率均值仅在第130次迭代后逼近最优解,远小于理论优化差距,与穷举法的410计算次数相比,TPO算法复杂度大大降低,更具有实际应用价值。

图3 TPO算法与穷举搜索结果对比

以上实验结果验证了TPO算法的有效性和实用性,下面将分析系统关键参数对TPO算法结果的影响。图4显示了TPO算法的参数β对算法收敛时间和系统用户设备发射总功率的影响。从图4中可知,当β=20时,系统总功率接近最优解,收敛时间较长;当β=5时,系统总功率远离最优解,收敛时间较短。因此伴随β的增加,TPO算法获得的近似系统总功率越接近最优值,同时收敛时间增加,符合式(10)理论结果。

图4 系统用户设备发射总功率与β的关系

图5是将所有移动用户设备的输入数据大小Cmn设定为相同值并统一调整,观察系统用户设备总功率与设备所需计算卸载的输入数据量大小Cmn的关系。从图5可以看出,当Cmn越大,TPO算法实现的系统用户设备的总发射功率会增大,这是因为设备需要更多的能耗传输更多的数据,但是总发射功率的收敛时间并没有伴随Cmn增加发生显著变化,说明当设备的输入比特量增加时,TPO算法的收敛速度会更快,这对实际系统中用户设备计算卸载高峰期的处理具有很大的优势。

图5 系统用户设备发射总功率与Cmn的关系

为了显示TPO算法对用户设备资源分配的调节效果,建立了用户设备高度聚集的特殊场景,将TPO算法与其他常用算法的处理效果进行对比。通过观察可知,图6b中传统的依赖接收信号强度指示(RSSI)进行连接的方式会导致MEC服务器资源分配不合理,进而无法满足用户需求,图6c中随机法实现的系统设备发射总功率为48.3 W,图6d中TPO算法实现的系统设备发射总功率仅为8.7 W,因此随机法的实验结果不满足最小化目标,而本文提出的TPO算法能够合理有效地建立移动用户设备和MEC服务器的连接,达到系统设备发射总功率优化的最优效果。

(a)用户与基站位置 (b)RSSI连接方式

(c)随机法连接方式 (d)TPO算法连接方式

4 结 论

传统的云计算模型已无法有效解决海量的边缘数据计算卸载问题,如何提升移动边缘计算的大规模网络架构的计算卸载的效率和用户体验受到越来越多的关注。本文在传输带宽和计算资源参数化的基础上,使用马尔可夫近似框架将系统用户设备的发射功率最小化问题转化,设计分布式的发射功率优化算法求得原目标的近似最优解。对比基准算法测试结果,TPO算法的系统用户设备发射总功率优化效果比随机法提升了78.5%,同时执行效果更加稳定;与穷举搜索的指数阶O(2n)计算复杂度相比,该算法的复杂度为线性阶O(n),故该算法在有限迭代轮次后即可逼近穷举搜索的最优解;与传统的RSSI连接方式相比,TPO算法能够避免在用户量小范围高度集中时争抢计算资源的现象,减少网络拥塞和资源分配不均衡的情况发生,满足用户计算卸载需求。TPO算法能够在保证用户设备的时延约束下有效降低系统用户功耗成本,确保时延敏感型业务的时延约束下的用户体验。