移动Ad Hoc云中任务卸载的联合优化策略

胡 杨，韩嘉伟，张志红，李 军，刘 畅，曾祥豹，李小飞，王音心

(1.中电科技集团重庆声光电有限公司，重庆 401332；2.中国电子科技集团公司第二十六研究所，重庆 400060；3.重庆邮电大学 移动通信技术重庆市重点实验室，重庆 400065)

0 引言

随着智能手机、平板电脑等移动终端在生活中的广泛普及，人们从互联网获取信息的方式已从传统的台式电脑终端逐渐转移至移动终端。由中国互联网信息中心发布的《第41次中国互联网络发展状况统计报告》显示，截至2017年12月，我国手机网民规模达7.72亿，且使用移动手机上网的比例高达97.5%，超过了60.1%的台式电脑上网比例[l]。在互联网用户服务需求日益多样化的趋势下，移动终端还需依赖更强大的网络资源和技术平台才可提供更多、更强健的服务，因此，科研人员提出了移动云计算(MCC)[2-3]的概念，将传统云计算(CC)技术和理念融合到移动互联网的服务领域中，利用云端强大的处理和存储能力来减轻移动设备端的负载，以提升整个服务体系的处理能力与服务能力。但在实际生活中，移动终端用户往往找不到可用的云基础设施，不能保证随时随地的接入情况，而且由于服务器距离太远，任务迁移也会面临着高网络延迟和通信成本的问题。因此，科研人员基于移动云计算的思想，提出了移动Ad Hoc云计算[4-5]的概念并受到了广泛关注。

在移动Ad Hoc云中人们关注的两个重要指标是：任务卸载过程中产生的系统能量消耗[6]和任务卸载时延[7]。任务卸载过程中产生的系统能量消耗，包括在任务提交和计算结果返回阶段产生的通信能耗，以及在代理终端执行处理过程中产生的计算能耗。所述能耗大小直接影响到移动设备的电池续航能力，该问题对由资源(如内存、CPU)受限且电池容量小的移动设备所组成的移动Ad Hoc云的影响尤为明显，如果不能处理好任务卸载过程中的能耗问题，将会影响到云系统的续航能力，降低系统的服务性能。在任务卸载中存在数据传输及任务处理时延，虽然相对传统移动云计算，移动Ad Hoc云在任务时延上具有很大的优势，但由于网络中存在多个性能差异的移动设备，而且每个设备间的无线网络环境也各不相同，因此，在客户端卸载任务时，每个代理终端产生的时延也不尽相同。对于云游戏、云感知等时延敏感性的实时性任务[8]，如果时延过大，将会严重影响到移动Ad Hoc云的服务质量(QOS)，从而降低客户服务体验。对于文件压缩、图像处理等非时延敏感性任务，则可以适当放宽对时延的要求。总之，对于任何计算任务，时延总是越小越好。

本文在移动Ad Hoc云任务卸载的过程中，提出了一种降低系统能耗与任务时延的联合优化算法(JOECD)，解决了客户端计算任务恰当选择代理终端问题。

1 系统模型

图1 任务卸载系统模型

移动Ad Hoc云计算系统任务卸载模型如图1所示，客户端在网络中发现一系列合适的代理终端并向其卸载自身计算任务，代理终端利用自身的可用资源为客户端进行服务，并把执行完成后的任务返回给客户端[9]。不失一般性，假设网络中存在两种无线通信方式，即WiFi与蜂窝网络。众所周知，WiFi的通信成本普遍低于蜂窝网络，而通信速率普遍高于蜂窝网络，因此，在任务卸载的过程中优先选择使用WiFi进行通信。如果代理终端移出了WiFi的通信范围，则客户端自动切换为蜂窝网络继续通信。

假设系统中存在M个客户端(C)需要卸载任务，且每个客户端的任务量不同，第i个客户端Ci的任务量为Wi，在任务来临时卸载至代理终端，默认每个客户端仅存在一个计算任务。同时，假设系统中存在N个代理终端(A)可共享资源，第j个代理终端Aj的最大可用资源量为Qj，当用户卸载的任务处理完成后返回结果给客户端。假设系统中的所有移动设备上可用的整体资源及剩余电池能量都足以运行每个独立的计算任务，即任何计算任务都可以选择卸载至网络中任意其他代理终端进行处理。因此，当客户端在进行任务卸载时，需根据代理终端的属性决策出如何选择代理终端进行任务卸载，以达到优化系统能耗和时延的目的。当客户端Ci中的计算任务到达时，Ci会在系统中寻求足够的资源来处理自身的计算任务，在任务卸载的过程中会产生相应的能量消耗及时延。

基于上述假设，对移动Ad Hoc云在任务卸载过程中涉及到系统能耗及任务时延进行建模，并由此推导出目标函数。

1.1 计算能耗

在任务卸载过程中，系统能耗包括在移动设备上处理计算任务所产生的计算能耗，以及在数据传输过程中产生的通信能耗。其中，计算能耗与计算任务量及当前终端的处理能力有关，因此，客户端Ci在任务卸载中产生的总计算能耗ei为

(1)

1.2 通信能耗

(2)

(3)

为了便于分析，假设在Aj将任务处理后得到的结果数据大小为客户端Ci提交数据的ρ倍(0<ρ≤1)，因此，结果回传阶段在WiFi和蜂窝中传输的数据量如下：

(4)

(5)

因此，在卸载任务至代理终端的过程中产生的通信能耗为

(6)

式中：bcell为蜂窝的网络带宽；2为单位时间的通信能耗。

因此，Ci在任务卸载过程中所产生的总通信能耗为

(7)

式中上角com表示通信。

为了便于讨论，本文假设所有移动设备在能耗方面都是同性质的。对于所有设备都使用同样的单位时间能耗λ1与λ2，用于通信的能量总量一般高于用于计算处理的能量[9]，即λ1<λ2。

1.3 任务时延模型

类似于通信能耗，如果将客户端Ci的计算任务卸载至代理终端Aj，则卸载计算任务所产生的任务时延可表示为数据传输产生的传输时间及任务处理所产生的计算时间之和，即

(8)

因此，客户端Ci在任务卸载过程中所产生的任务时延为

(9)

1.4 优化问题

使下式最小

(10)

目标函数需要满足:

(11)

(12)

xij≥0j=1,…,N

(13)

值得注意的是，通常需要根据具体情况的不同对任务延迟和系统能耗进行综合权衡[11]。在上述目标函数中，我们使用权重参数γ进行灵活配置。例如，如果移动设备电池性能问题并不用严重，或者当前客户端的计算任务对延迟非常敏感，则可以将γ设置得尽可能小。在这种情况下，优化问题变为尽量使任务时延最小化以降低对能耗的关注度。然而，如果能耗是移动设备的主要关注点，而任务延迟是可以容忍的，则γ可以设置得足够大。

2 系统能耗与任务时延的联合优化算法

在移动Ad Hoc云中，客户端在卸载一些计算密集型任务过程中不仅会产生相应的传输能耗与计算能耗，而且还会产生一定的任务时延。为了降低系统能耗与减小任务时延，本节提出了一种运用在移动Ad Hoc云中，基于系统能耗与任务时延的联合优化 (JOECD)算法。

2.1 算法具体流程

当每一个客户端的计算任务来临时，都会执行JOECD算法，主要流程如图2所示。

(14)

图2 JOECD算法流程图

为更清晰地展现客户端进行任务决策并卸载的过程，在算法1)中对JOECD算法进行了详细的设计：

输入参数：客户端卸载任务量W,代理终端最大可用资源量Q,单位时间的计算能耗λ1，单位时间的通信能耗λ2,WiFi的网络带宽bwf,蜂窝的网络带宽bcell,客户端个数M，代理终端个数N。

输出参数:系统能耗E，任务时延D。

2)l=l+1；

3)for 每一个代理终端j=1∶N；

4)根据式(10)计算Sij；

5)end for；

9)根据式(1)，(7)，(9)计算Ei与Di；

10)更新可用资源量Q(l)；

11)将Ci从集合C中移除；

12)else；

13)任务卸载失败，Ei=0，Di=0；

14)end if；

16)返回步骤2)；

17)end if；

18)返回E，D。

2.2 复杂度分析

算法复杂度是衡量算法优劣的一个指标[12]，本文提出的任务卸载决策算法的复杂度为O(MN2)。

如上所述，该算法是根据客户端的数量一轮一轮进行的，首先分析算法中第l轮决策中的复杂度，如算法1)所示，它主要包括以下步骤：

a.计算Si。对于客户端Ci，需对网络中所有的代理终端，即A中所有元素通过式(14)都计算一次Sij以得到Si，这个步骤的复杂度为O(N)。

根据上述分析，第l轮决策中的复杂度为平方阶，即O(N2)。由于系统中存在M个客户端，因此，在算法中这个决策步骤会执行M次，因此，本文提出的任务卸载决策算法的复杂度可表示为O(MN2)。

3 仿真与性能分析

为了对本文提出的系统能耗与任务时延的联合优化算法进行性能评估，将JOECD与文献[2]中提出的移动云计算(MCC)方案在系统能耗与任务时延上进行对比。在MCC方案中，客户端通过宣布一个总的回报以激励代理卸载资源，并将回报与资源卸载量进行迭代至双方收益最大化。由此可知，MCC方案中并没有对系统能耗与任务时延进行控制。

3.1 参数设置

3.2 性能分析

图3 系统能耗与客户端数量之间关系

由图3可知，当客户端数量从1增加到10时，两种方案的系统能耗都随着客户端数量的增加而增加，这是因为当云系统中计算资源充足时，卸载更多的任务会导致更多的计算能耗和通信能耗。在到达的任务量较少时，由于系统内资源充足，JOECD算法通过任务卸载决策算法可选择当前系统中能耗与任务时延最低的代理终端进行任务卸载，而移动云计算(MCC)方案则更关注系统收益以及资源利用方面，从而尽可能选择任务卸载过程中系统收益最高及通信成本最低的代理终端。因此，JOECD算法在能耗方面的表现优于MCC方案。但当客户端增多时，由于系统中的总计算资源有限，导致了在JOECD算法中无更多的代理终端进行选择，从而不得不选择能耗与时延较高的代理进行任务卸载。因此，在客户端数量较多时，JOECD算法在系统能耗上的表现会与MCC方案趋于接近。

图4给出JOECD算法与MCC方案在任务时延上的差异。由图可看出，任务时延随着云系统内客户端的数量增加而增加，这是由于任务数量越多且每个任务的分配过程都会产生时延，故而造成的总时延升高。当云系统内的任务数量增加时，云系统内的可用计算资源逐渐变得不再充足，此时JOECD算法中新的客户端已无机会选择时延表现更优的代理终端，只能选择时延较高的代理满足任务需求；而在MCC方案中，即使存在代理间的资源动态调整，但因为云系统内总的资源量受限，剩余资源不能满足到达的任务总量要求。因此，在客户端数量较高时，两种方案在任务时延趋于接近。

图4 任务时延与客户端数量之间关系

4 结束语

本文综合考虑了移动Ad Hoc云任务分配过程中系统能耗与任务时延问题，提出了任务卸载过程中基于系统能耗与任务时延的联合优化算法。该算法对任务卸载过程中会产生的计算能耗、通信能耗及卸载时延进行建模并提出了优化目标问题。通过预估处理对每个客户端的需要卸载任务进行卸载决策，以达到减小系统能耗和任务时延的目的。