联合优化时延与能效的移动终端计算迁移方法

张文柱，曹琲琲，孔维鹏

(1. 西安建筑科技大学 信息与控制工程学院，陕西 西安 710055；2. 西安电子科技大学 通信工程学院，陕西 西安 710071)

随着互联网技术和无线网络技术的迅速发展，移动应用快速增长．当前的移动终端配备了丰富的传感器和更高的屏幕分辨率，并能以更快的速率传输数据．移动应用程序的成熟度从执行基本计算的应用程序发展到3D游戏、高清视频流服务、图像处理、语音识别和增强现实应用程序等．然而，移动终端的计算能力、存储能力、电池容量均属受限资源，难以支持计算密集型应用，因此，移动计算领域迫切需要能够有效扩展移动终端资源、支持计算密集型应用的技术．

为了提升移动终端的续航能力、保证实时应用低延迟的要求，计算迁移技术日益引人关注[1-2]．计算迁移是指移动终端针对特定的工作任务，受当前计算系统资源的限制，需要将计算任务通过无线信道分配到远程服务器，利用远程服务器突出资源优势辅助移动终端完成复杂计算任务，为移动终端提供高性能的计算迁移服务[3-5]．移动终端的计算迁移首先要通过上行信道上传迁移数据，然后等待远程计算结果，最后在下行信道接收远程服务器返回的计算结果．这要求终端必须保持与远程服务器通信的数据连接，因此会消耗宝贵的电量．为了实现计算迁移的整体收益，应在确保减小应用程序计算时延的同时，必须考虑利用无线信道迁移数据所带来的附加能耗．在无线可变信道条件下，如何在任务的计算量、时延敏感性、能源消耗、无线信道带宽等诸多条件下决策计算实施迁移，以及具体迁移哪些数据，这无疑具有很大挑战性[6-7]．

近年来，有关学者提出了几种用于解决移动终端的资源可用性和可持续性问题的迁移机制．例如，基于离散时间马尔可夫链(Discrete-Time Markov Chain，DTMC)设计无线移动信道模型的衰落模型，在移动终端侧区分应用程序的普通数据和计算密集型组件，执行在多点远程服务器计算迁移，减小终端能耗[8]; 设计无线局域网环境下的计算迁移排队迁移模型，并分析传输延迟和迁移效率，目标是减小计算时延、改善用户体验[9]; 基于位置决策的移动计算迁移方法[10]，等等．尽管在当前已有的方法已经在克服移动终端的能耗、提升移动终端的处理能力方面取得进展，但是毫无疑问，目前的研究方案在灵活控制实施计算迁移组件、综合考虑移动终端的能效与应用程序的时延敏感性以及无线信道带宽的可变性等方面还需要进一步探索．

笔者设计了一种能够联合优化时延与能效的移动终端的计算迁移方法．该方法以LTE应用为背景，设计了移动计算迁移模型; 在此基础上，分析计算迁移相关参数，包括应用程序对计算资源的需求、移动终端的工作指标参数以及无线信道的传输速率等参数，构造迁移代价函数; 最后，分析应用程序对计算资源的需求、移动终端的计算能力和无线信道的传输速度，以减小时延与降低能耗为约束条件、以联合优化处理时延和能耗为目标，合理规划应用程序的计算迁移．

1 移动计算迁移模型

图1 计算迁移模型

设计的计算迁移模型如图1所示．在移动终端侧，迁移模型包括计组件分解模块、组件迁移代价评估模块、远程服务器系统信息收集模块、迁移决策模块以及结果合成模块等．为了实现计算迁移，计算组件分解模块将应用程序代码分解成计算组件，每个组件包含3个特征参数:原始代码规模、发送代码规模、接收代码规模;运行该组件所需的指令集;本地中央处理器(Central Processing Unit，CPU)执行指令的速率．组件迁移代价评估模块依据信道带宽、接收速率和发送速率、远程服务器的系统信息与状态信息，计算各个模块的迁移代价; 迁移决策模块依据迁移代价评估模块发送过来的迁移代价以及服务器状态收集模块发送过来的服务器资源状态信息，执行文中设计的算法，合理规划计算组件的迁移;最后，当服务器将计算结果返回时，结果合成模块将本地计算结果与远程服务器返回的迁移计算结果合成，作为应用程序的最终输出．

2 联合优化时延与能效的计算迁移方法

2.1 设计计算迁移的目标函数

⨁xi) ．

(1)

代价函数表示为远程执行服务的迁移代价，包括为执行远程服务而必须迁移所有关联组件模块的代价; 不同计算组件之间存在一定的关联，式(1)的后半部分反映这种关联．据此构造计算迁移的目标函数为

(2)

2.2 最小化时延条件

为了实现时延最小化的目标，必须保证执行计算迁移需要的时间小于本地运行所需的时间，即

T1=tlocal-tremote>0 ,

(3)

其中，tlocal表示计算组件在本地执行所需时间，tlocal可以由在本地执行的指令数Ilocal与本地执行指令速率Rlocal的比值求出，tlocal= (Ilocal/Rlocal)xi．tremote表示执行计算迁移所需要的总时间，tremote由3部分组成:远程服务器执行运算所需要的时间;发送迁移数据Dsend及附加数据Dadd的所需要的时间;移动终端接收远程服务器的计算结果所需要的时间．于是服务迁移所需的总时间可由下式计算:

(4)

其中，Dsend和Drec分别是发送计算组件的数据规模大小和接收远程服务器返回计算结果的数据大小(单位为字节);Dadd是发送关联计算组件的数据规模大小;Bsend和Brec分别是发送和接收数据时的信道带宽;Rremote是云服务器执行指令的速率．且有

2.3 最小化能耗条件

为了实现能效优先的目标，必须保证迁移服务执行计算迁移需要的能耗小于本地运行所需的能耗，即

T2=Elocal-Eremote>0 ,

(5)

其中，Elocal表示本地执行能耗，可以表示为在本地执行的指令数Ilocal、本地执行指令速率Rlocal以及移动终端执行指令所需的功率Plocal的函数，即Elocal= (PlocalIlocal)/Rlocal．Eremote表示执行计算迁移所需要的总能耗，Eremote包括:等待迁移结果返回的等待能耗Ewait；传输迁移数据(计算组件)需要的能耗，包括发送迁移数据所需能耗Esend和接收服务器返回计算结果所需能耗Erec；传输附加数据(关联计算组件)所需的附加能耗Eadd．于是Eremote可由下式计算:

Eremote=Esend+Ewait+Erec+Eadd=Psend(tsend+tadd)+Pidletwait+Prectrec,

(6)

其中，Psend、Prec和Pidle分别是移动终端标称的发射功率、接收功率以及处于空闲状态的功率;tsend和tadd分别是移动终端发送迁移数据所需时间和发送附加数据所需时间;twait和trec分别等待远程服务器返回结果所需时间和接收远程服务器返回结果数据所需时间．

2.4 联合优化时延与能效

依据前面分析，减小移动终端的运行时延、提高能效可以转化为最优化问题，即以式(3)和式(5)为约束条件的式(2)的优化问题，即

(7)

式(7)可通过执行整数线性规划(Integer Linear Programming，ILP)算法来求解[11]．为了获得问题P的最优解，首先找到问题P对应的松弛问题P0:

(8)

图2 采用隐形枚举法求解P的最优解流程图

问题P和P0的关系:P的可行区域是P0的可行区域的子集;如果P0无可行解，则P无可行解;P0的最优值是P的最优值的一个下界;求得P0的最优解之后，对这个最优解进行进一步的检验: 如果这个最优解是一个整数向量，则可以确定这个最优解也是问题P的最优解．文中采用隐形枚举法求解P，算法流程如图2所示，向量(x1，x2， …，xn)表示移动终端以最小化时延为目标的最优计算迁移策略，系统依据xi的值确定是否迁移组件Mi．如果P无可行解，则所有组件均不执行计算迁移．

3 仿真与性能评估结果

文中基于NS-3网络软件评估所设计的计算迁移方法在减小处理时延和降低能耗方面的性能．计算迁移的系统模型如图1所示．远程服务器有采用Intel i7-4770k CPU，处理能力为 1.2× 105DMIPS@ 3.5 GHz，8 GB 随机存取存储器(Random Access Memory，RAM)，运行Windows Server 2008操作系统; 长期演进(Long Term Evolution，LTE)移动终端采用三星Galaxy s5，配置高通Snapdragon-801 CPU，处理能力为 3.3× 104DMIPS@ 2.5 GHz，2 GB RAM，操作系统Android 4.4．移动终端通过LTE eNB(Evolved Node B)接入网络，无线信道速率分别设置为 5 Mbit/s、10 Mbit/s，误码率为10-3;移动终端执行的应用程序源码规模最小为 0.2 MB，最大为 2.0 MB，递增步长取 0.2 MB; 按照每4字节组成1条指令，可由程序源码规模计算指令数．详细仿真参数如表1所示．

表1 仿真参数

当信道传输速率为5 Mbit/s时，移动终端执行文中设计的计算迁移方法与仅执行本地计算时的处理时延、功耗对比分别如图3和图4所示．图3表明文中设计的计算迁移方法能否获得更短的处理延迟与任务需要处理的数据量密切相关．当任务的数据量小于 800 KB 时，执行时间的差异极小，本地处理时延略小; 当任务的数据量大于 800 KB 时，采用计算迁移算法总能取得更小的处理时延; 当任务的数据量为 2 000 KB 时，执行计算迁移算法能够将处理时延减小28%．

图4表明文中设计的计算迁移方法能够获得明显的能效收益．具体来说，当任务的数据量小于 400 KB 时，应用计算迁移与本地执行的时延几乎没有差别; 当任务的数据量大于 400 KB 时，与本地执行相比，执行计算迁移总能获取是更高的能效; 当应用程序的源码规模最后达到 2 000 KB 时，执行计算迁移算法能够比仅执行本地计算减少36%能耗，这说明文中设计的计算迁移算法在降低能耗方面也具有明显的效果．

图5和图6分别表明信道速率对计算迁移算法的时延、能耗的影响．图5表明更快的信道速率能够减小时延，当应用程序源码规模在 200～ 2 000 KB 范围内变化时，10 Mbit/s 信道速率比 5 Mbit/s 信道速率平均减小时延23%．图6表明更快的信道速率始终能够减小终端能耗，当应用程序源码规模在 200～ 2 000 KB 范围内变化时，10 Mbit/s 的信道速率比 5 Mbit/s 信道速率平均节省能耗26%．可见，更快的信道速率有助于计算迁移算法获得更短的时延以及更低的能耗．

4 结 束 语

面向LTE应用背景，笔者设计了一种能够联合优化时延与能效的移动终端的计算迁移方法．该方法首先设计了移动计算迁移模型;在此基础上，分析计算迁移相关参数，包括应用程序对计算资源的需求、移动终端的工作指标参数以及无线信道的传输速率等参数，构造迁移代价函数;最后，以减小时延与降低能耗为约束条件、以联合优化处理时延和能耗为目标，合理规划应用程序的计算迁移．研究结果表明，文中设计的计算迁移方法能够有效减小移动终端的处理时延，同时可以获得更高的能效．