孫赫勇 文 勃 鄭 丹 周 強(qiáng)

1(中車青島四方機(jī)車車輛股份有限公司大連分公司 遼寧 大連 116000)2(中車青島四方機(jī)車車輛股份有限公司青島分公司 山東 青島 266000)3(中車青島四方機(jī)車車輛股份有限公司焦作分公司 河南 焦作 454150)4(北京交通大學(xué)軟件學(xué)院 北京 100044)

0 引 言

移動(dòng)云計(jì)算可以將移動(dòng)設(shè)備上的計(jì)算任務(wù)、數(shù)據(jù)處理及存儲(chǔ)卸載至云端資源上，從而降低移動(dòng)設(shè)備對(duì)于計(jì)算資源的巨大需求，解決復(fù)雜性應(yīng)用任務(wù)的執(zhí)行[1-2]。移動(dòng)應(yīng)用中的任務(wù)模塊通常具有相互關(guān)聯(lián)性，因此通常以任務(wù)交互圖TIG進(jìn)行建模[3]。TIG中的任務(wù)需要在保持性能和能效的基礎(chǔ)上映射并調(diào)度至遠(yuǎn)程云端資源上。映射即是通過匹配任務(wù)需求和資源能力將資源分配給任務(wù)，調(diào)度即是在所分配的資源上執(zhí)行任務(wù)的過程。每個(gè)TIG擁有多個(gè)頂點(diǎn)和有向邊，頂點(diǎn)代表包含需要執(zhí)行的指令集的任務(wù)，有向邊代表任務(wù)的映射資源間的數(shù)據(jù)流，代表通信代價(jià)。由于通信代價(jià)取決于任務(wù)間的數(shù)據(jù)流大小和傳輸帶寬，不同的任務(wù)-資源映射，其通信代價(jià)也是不同的。

由于每個(gè)資源上的處理器均可通過動(dòng)態(tài)電壓/頻率調(diào)整DVFS技術(shù)運(yùn)行在不同的離散頻率下[4]，頻率越高，完成時(shí)間越短，但其能耗也越高。因此，計(jì)算代價(jià)在不同的資源頻率分配下也是不同的，這取決于映射處理器的運(yùn)行頻率。對(duì)于TIG而言，從開始節(jié)點(diǎn)至出口節(jié)點(diǎn)間的每條路徑的完成時(shí)間為計(jì)算代價(jià)與通信代價(jià)之和。擁有最大完成時(shí)間的路徑即為TIG的關(guān)鍵路徑。任務(wù)卸載至云端資源上執(zhí)行不能影響應(yīng)用執(zhí)行的性能和能耗，這表明進(jìn)行卸載應(yīng)確保任務(wù)在期限內(nèi)完成，且能耗也得到降低。應(yīng)用卸載問題的目標(biāo)即是尋找最優(yōu)的任務(wù)-資源分配(即映射)與最優(yōu)資源頻率分配(即調(diào)度)，使得整個(gè)TIG不僅可以在全局期限內(nèi)完成，還可以使能耗達(dá)到最小化。

相關(guān)工作中，文獻(xiàn)[5]提出一種基于調(diào)度的整數(shù)線性規(guī)劃ILP算法，文獻(xiàn)[6]提出一種基于固定優(yōu)先級(jí)的任務(wù)調(diào)度算法，然而，兩篇文獻(xiàn)在模型中并沒有考慮映射階段的能耗降低和通信代價(jià)的影響。文獻(xiàn)[7-8]同步考慮了映射階段和調(diào)度階段的能耗，但忽略了通信代價(jià)對(duì)能耗的影響。文獻(xiàn)[9]提出一種基于兩階段調(diào)度與映射框架的整數(shù)規(guī)劃IP算法，尋找最優(yōu)任務(wù)-資源匹配與電壓分配方案。然而，調(diào)度決策中卻忽略了考慮通信代價(jià)。不同于以上工作，文獻(xiàn)[10]提出一種CAHPC算法，將通信代價(jià)考慮到調(diào)度與映射階段中進(jìn)行能耗優(yōu)化。然而，本文的工作將移動(dòng)應(yīng)用卸載問題形式化為一個(gè)二次分派問題，以兩層遺傳算法進(jìn)行了求解，且以任務(wù)交互圖TIG對(duì)移動(dòng)應(yīng)用進(jìn)行了分割，提供了對(duì)單個(gè)任務(wù)模塊進(jìn)行卸載決策的可行性。

本文將卸載決策問題建模為一個(gè)二次分派問題，并提出一種兩層遺傳算法進(jìn)行求解，其中：內(nèi)層調(diào)度問題的目標(biāo)是通過構(gòu)建最大化的計(jì)算代價(jià)尋找最優(yōu)資源頻率分配；而外層映射問題的目標(biāo)是尋找最優(yōu)的任務(wù)-資源分配方案，以產(chǎn)生接近于全局期限的完成代價(jià)。即算法將利用不超過期限的松馳時(shí)間，得到能效更高的調(diào)度方案。

1 系統(tǒng)模型

1.1 相關(guān)定義

1) 任務(wù)交互圖(Task Interaction Graph,TIG)。TIG為工作流結(jié)構(gòu)，即有向無循環(huán)圖，其每個(gè)頂點(diǎn)代表一個(gè)任務(wù)，每條邊代表任務(wù)間的數(shù)據(jù)傳輸。

2) 運(yùn)行頻率f。f為資源上處理器在執(zhí)行任務(wù)時(shí)的運(yùn)行頻率，該頻率可利用處理器上的DVFS技術(shù)進(jìn)行調(diào)整，若處理器運(yùn)行在較高的執(zhí)行頻率，則計(jì)算代價(jià)(時(shí)間)更低，但能耗更高。

(1)

4) 通信代價(jià)Tcomm。執(zhí)行所有任務(wù)i∈N期間所有數(shù)據(jù)傳輸花費(fèi)的時(shí)間即為TIG的通信代價(jià)。對(duì)于每個(gè)任務(wù)-資源分配a∈A，假設(shè)通信代價(jià)在所有資源-頻率分配組合下為常量，而對(duì)于不同的任務(wù)-資源分配，其值不同。

(2)

式中：Cij表示任務(wù)分配后兩個(gè)資源間的通信時(shí)間；p,q∈P。

5) 完成代價(jià)Ttotal。TIG的完成代價(jià)為計(jì)算代價(jià)和通信代價(jià)之和，表示為：

Ttotal=Tcomp+Tcomm

(3)

6) 全局期限dg。執(zhí)行TIG的最大允許時(shí)間即為全局期限dg。該值為整個(gè)TIG在移動(dòng)設(shè)備上執(zhí)行的估算時(shí)間，可確保卸載環(huán)境下的TIG執(zhí)行優(yōu)先于整個(gè)TIG在移動(dòng)設(shè)備上的執(zhí)行，以此改善能效并維持性能。

(4)

7) 擴(kuò)展因子Sf。全局期限與TIG完成代價(jià)之比即為擴(kuò)展因子，且Sf≥1。擴(kuò)展因子的最優(yōu)值為1，即TIG剛好在截全局期限到達(dá)時(shí)完成。Sf<1表明TIG完成代價(jià)超過全局期限，無法滿足性能要求。

(5)

8) 松馳時(shí)間Tslack。對(duì)于每個(gè)任務(wù)-資源分配，松馳時(shí)間為全局期限dg與TIG的最遲完成代價(jià)Ttotal之差。若松馳時(shí)間較少，則表明完成代價(jià)已與期限較為接近。

Tslack=dg-Ttotal

(6)

9) 剩余松馳時(shí)間Tresidual。對(duì)于每個(gè)任務(wù)-資源分配，剩余松馳時(shí)間為全局期限與通信代價(jià)及平均計(jì)算代價(jià)之差。若Tresidual較高，TIG的執(zhí)行可通過利用DVFS放緩任務(wù)執(zhí)行而增加計(jì)算代價(jià)，進(jìn)而降低執(zhí)行能耗。

(7)

10) 局部期限dl(Ti)。完成任務(wù)Ti的最大允許時(shí)間為局部期限。初始條件下，任務(wù)Ti的平均計(jì)算代價(jià)即為其局部期限，然后剩余松馳時(shí)間Tresidual以正比于平均計(jì)算代價(jià)%Tresidual(即初始局部期限)的方式在所有任務(wù)間進(jìn)行分配，并被添加至各自的平均計(jì)算代價(jià)中，以此為任務(wù)設(shè)置新的擴(kuò)展局部期限。

(8)

式中：

(9)

1.2 執(zhí)行時(shí)間模型

TIG負(fù)載在運(yùn)行頻率為f的處理器上的執(zhí)行時(shí)間為：

(10)

為了最小化功耗，TIG中的每個(gè)任務(wù)需要執(zhí)行于不同的運(yùn)行頻率上。因此，式(10)可重寫為：

(11)

(12)

1.3 通信時(shí)間模型

執(zhí)行于兩個(gè)資源上的任務(wù)間的數(shù)據(jù)傳輸量為DMbit，傳輸帶寬為BWMbit/s，則通信時(shí)間為：

(13)

1.4 能量模型

任務(wù)的計(jì)算能耗為功耗與執(zhí)行時(shí)間的乘積，功耗取決于運(yùn)行頻率，執(zhí)行時(shí)間為式(11)，那么：

(14)

(15)

類似地，總體通信能耗Ecomm為：

(16)

式中：Pi,tx和Pi,rx分別表示發(fā)送和接收功率；Cij表示對(duì)應(yīng)的通信時(shí)間。因此，TIG執(zhí)行的總體能耗為：

E=Ecomp+Ecomm

(17)

2 問題形式化

將移動(dòng)設(shè)備上的應(yīng)用劃分為包含多個(gè)互聯(lián)部分的TIG，表示為有向圖G(V,E,dg)。令T={Tj,1≤j≤N}表示TIG中的任務(wù)集合，圖的每個(gè)頂點(diǎn)Tj∈V代表TIG中的一個(gè)任務(wù)，每個(gè)任務(wù)Tj可表示為三元組Tj，其中：Ec表示任務(wù)執(zhí)行需要的總CPU周期數(shù)，即執(zhí)行負(fù)載；F(Tj,Ti)∈E表示任務(wù)Tj與Ti間的數(shù)據(jù)流；dl(Tj)表示任務(wù)Tj的局部期限。假設(shè)每個(gè)任務(wù)Tj最多可擁有5個(gè)模塊M={Mk,1≤k≤5}，可在相同或不同的處理器頻率下執(zhí)行以降低資源能耗。任務(wù)Tj的所有模塊執(zhí)行所需的CPU周期數(shù)之和恒為Ec，dg給出TIG完成執(zhí)行的全局期限。令P={pi,1≤i≤P}表示資源集合，也可表示為有向圖結(jié)構(gòu)，每個(gè)節(jié)點(diǎn)pi代表一個(gè)資源，每個(gè)資源pi可表示為二元組pi，其中：f表示資源的運(yùn)行頻率；D(pi,pj)∈E表示資源pi與pj間的帶寬。每個(gè)資源pi上的處理器可運(yùn)行于離散的頻率下，表示為f={fk,1≤k≤F}。

N個(gè)任務(wù)在M個(gè)資源上的映射不僅取決于計(jì)算代價(jià)，還取決于通信代價(jià)。為了計(jì)算最優(yōu)代價(jià)，問題求解需要計(jì)算所有任務(wù)-資源分配下的總代價(jià)。基于以上分析，以下將該卸載決策問題定義為具有以下假設(shè)的二次分派問題(Quadratic Assignment Problem,QAP)[11]：

1) 所有處理器資源擁有相同的離散運(yùn)行頻率集合；

2) 對(duì)于每個(gè)任務(wù)的不同模塊，所有資源可以相同或不同的運(yùn)行頻率進(jìn)行任務(wù)執(zhí)行；

3) 每個(gè)任務(wù)至多可分配至一個(gè)資源上執(zhí)行；

4) TIG需在全局期限內(nèi)完成，而單個(gè)任務(wù)需在其局部期限內(nèi)完成。

基于此，QAP可表示為：

(18)

約束條件為：

Tcritical≤dg

(19)

(20)

(21)

aij∈{0,1}i,j=1,2,…,N

(22)

首先，基于以上優(yōu)化模型，分別分析決策變量a∈A和f∈F。

1) 分配決策a：對(duì)于每個(gè)任務(wù)-資源分配a∈A，全局松馳時(shí)間Tslack為全局期限與計(jì)算代價(jià)和通信代價(jià)之差。最優(yōu)全局松馳時(shí)間可以通過列舉所有任務(wù)-資源分配A下的全局松馳時(shí)間得到。決策變量a∈A給出了擁有最小全局松馳時(shí)間的任務(wù)-分配解，這表明TIG的完成代價(jià)Ttotal已接近于TIG的全局期限。

2) 頻率決策f：對(duì)于每個(gè)任務(wù)-資源分配a∈A，計(jì)算代價(jià)Tcomp為任務(wù)分配至資源上的執(zhí)行代價(jià)。然而，計(jì)算代價(jià)在所分配的處理器利用DVFS改變頻率時(shí)會(huì)發(fā)生變化。例如：若處理器運(yùn)行在更高頻率，則計(jì)算代價(jià)較低，但能耗更高。離解的運(yùn)行頻率結(jié)構(gòu)可以使頻率決策變量f∈F識(shí)別出最大化代價(jià)時(shí)的最優(yōu)資源運(yùn)行頻率，從而得到最小化的全局松馳時(shí)間。

其次，對(duì)于式(18)給出的目標(biāo)函數(shù)而言，第一部分dg給出全局期限，即TIG完成的最大延時(shí)；第二部分給出單個(gè)任務(wù)-資源分配下的總體計(jì)算代價(jià)，但僅在任務(wù)i分配至資源p，即aip=1時(shí)才進(jìn)行計(jì)算；第三部分給出單個(gè)任務(wù)-資源分配下的總體通信代價(jià)。

最后，對(duì)于約束條件，式(19)表明僅當(dāng)最終的執(zhí)行時(shí)間小于或等于全局期限時(shí)，才可以將當(dāng)前的任務(wù)-資源分配添加至全局松馳時(shí)間中。式(20)和式(21)表明每個(gè)任務(wù)僅能分配至一個(gè)資源上。式(22)表明分配變量aip為二進(jìn)制數(shù)，即為0或1。

3 兩階段混合整數(shù)QAP

為了計(jì)算全局松馳時(shí)間，需要同時(shí)得到計(jì)算代價(jià)和通信代價(jià)。計(jì)算代價(jià)取決于處理器資源的運(yùn)行頻率，通信代價(jià)取決于資源間的帶寬。對(duì)于單個(gè)通信代價(jià)，可能擁有較大的計(jì)算代價(jià)，由于對(duì)于每個(gè)任務(wù)-資源分配(即映射)而言，其資源頻率分配(即調(diào)度)可能較大。此時(shí)的計(jì)算代價(jià)的取值范圍為以最快處理器頻率得到的最小代價(jià)至以最慢處理器頻率得到的最大代價(jià)。為了得到最小的全局松馳時(shí)間，計(jì)算代價(jià)必須盡可能大。因此，為了找到最優(yōu)的任務(wù)-資源分配，必須找到最優(yōu)的資源頻率分配，進(jìn)而在不超過期限的同時(shí)產(chǎn)生最大化的計(jì)算代價(jià)。基于此分析可知，直接求解式(18)的目標(biāo)函數(shù)值比較困難。然而，計(jì)算代價(jià)與通信代價(jià)間的相互無關(guān)性使得可以將式(18)中的問題分解為由子問題S和上層問題T組成的兩階段混合整數(shù)QAP，以簡(jiǎn)化TIG的最優(yōu)全局松馳時(shí)間的求解過程。

3.1 子問題S

子問題S的目標(biāo)是在所有可能的頻率f∈F下找到一個(gè)頻率分配，使得該頻率在每個(gè)任務(wù)-資源分配中可以得到最大的計(jì)算代價(jià)。對(duì)于給定的任務(wù)-資源分配aip∈A和運(yùn)行頻率f∈F，子問題S試圖尋找處理器運(yùn)行頻率組合，得到最優(yōu)的計(jì)算代價(jià)，可表示為：

(23)

約束條件為：

Tip

(24)

3.2 上層問題T

(25)

式(25)的約束條件為式(19)-式(22)。因此，求解上層問題T即求解式(18)。子問題S和上層問題T聯(lián)立考慮為一個(gè)兩階段混合整數(shù)二次分派問題QAP，而T即為映射階段的優(yōu)化問題。

4 基于松馳時(shí)間的TIG調(diào)度

本節(jié)提出一種基于松馳時(shí)間TIG調(diào)度算法，實(shí)現(xiàn)TIG中任務(wù)的映射與調(diào)度。QAP為NP聯(lián)合優(yōu)化問題，利用兩層遺傳算法GA求解兩階段QAP，分別定義：getOptimalTaskResource(G(V,E,dg))(算法1)為求解映射最優(yōu)化，即外層GA；getOptimalResourceFrequency((G,f),a∈A,f∈F)(算法2)為求解調(diào)度最優(yōu)化，即內(nèi)層GA。

圖1 兩層映射與調(diào)度GA算法

兩種GA算法的過程如算法1和算法2所示。

算法1映射階段GA算法

Input:workflowG(V,E,dg),Task-Resource Assignmenta∈A,Resource-Frequency assignmentf∈F

Output:Optimal Task-Resource Assignment,Optimal Resource-Frequency assignment

[2]foreacha∈Ado

[3] calculate theTcritical

[5] calculate the Communication costTcomm

[6] calculate residual slack timeTresidual

[7] assign the local deadlinedlto all the tasks inG(V,E)

[9] calculate the global slack timeTslack

算法2調(diào)度階段GA算法

Input: workflowG(V,E,dg), Task-Resource Assignmenta∈A,Resource-Frequency assignmentf∈F

Output: Optimal Resource-Frequency assignment getOptimalResourceFrequency((G,f),a∈A,f∈F)

[1]foreachTaskjdo

[2]foreachProcessorido

[3]foreachFrequencykdo

[4] calculateTcomp

[7]endforeach

[8]endforeach

[9]endforeach

具體步驟如下：

步驟S1通過調(diào)用映射GA算法getOptimalTaskResource(G(V,E,dg))開始優(yōu)化過程，即算法1步驟1。

步驟S3對(duì)于每個(gè)任務(wù)-資源分配，利用式(7)計(jì)算Tresidual，即算法1步驟6。

步驟S4利用式(8)和式(9)，將剩余松馳時(shí)間Tresidual分配至每個(gè)任務(wù)作為其局部期限dl(Ti)，即算法1步驟8；并調(diào)用調(diào)度階段GA算法，即算法1步驟8。

步驟S5對(duì)于每個(gè)資源頻率分配，利用式(1)計(jì)算Tcomp，即算法2步驟4。

5 仿真實(shí)驗(yàn)

實(shí)驗(yàn)測(cè)試了不同的TIG結(jié)構(gòu)下的算法性能，TIG以隨機(jī)方式生成，包括隨機(jī)生成任務(wù)的執(zhí)行指令周期數(shù)、任務(wù)間的數(shù)據(jù)流以及全局期限等，資源參數(shù)包括運(yùn)行頻率和資源間的帶寬也以隨機(jī)方式生成。算法以枚舉法產(chǎn)生任務(wù)-資源分配和FF種資源頻率分配組合。利用MABLAB R2012b作為實(shí)驗(yàn)環(huán)境。實(shí)驗(yàn)結(jié)構(gòu)數(shù)據(jù)如表1所示。

表1 實(shí)驗(yàn)結(jié)果

5.1 映射階段指標(biāo)分析

映射階段指標(biāo)包括能耗節(jié)省、擴(kuò)展因子和全局松馳時(shí)間。為了測(cè)試能效，隨機(jī)生成的TIG被映射與調(diào)度至資源上。實(shí)驗(yàn)中，以Eoffload表示任務(wù)卸載后得到的能耗，Emobile表示任務(wù)完全在移動(dòng)設(shè)備上執(zhí)行得到的能耗，能耗節(jié)省比例計(jì)算為：

(26)

表1中:對(duì)于擁有3個(gè)任務(wù)的TIG，Emobile=154 mJ，Eoffload=93 mJ，根據(jù)式(26)，能量節(jié)省為40%。平均來說，任務(wù)卸載可以節(jié)省約35%的能耗，這表明調(diào)度階段算法計(jì)算最優(yōu)的運(yùn)行頻率是有效可行的。擴(kuò)展因子描述的是卸載應(yīng)用任務(wù)的完成時(shí)間的可擴(kuò)展性，應(yīng)用擴(kuò)展性越好，其值越接近于1。對(duì)于擁有3個(gè)任務(wù)的TIG，dg=1.02 s，Ttotal=0.85 s，根據(jù)式(5)，擴(kuò)展因子為1.2，而表中結(jié)果顯示TIG的平均擴(kuò)展因子為1.4。類似地，全局松馳時(shí)間給出的是任務(wù)可擴(kuò)展其運(yùn)行的剩余時(shí)間。對(duì)于擁有3個(gè)任務(wù)的TIG，dg=1.02 s，Ttotal=0.85 s時(shí)，根據(jù)式(6)，全局松馳時(shí)間為0.17 s，而平均全局松馳時(shí)間為0.56 s。

5.2 調(diào)度階段指標(biāo)分析

(27)

(28)

表1中，對(duì)于擁有3個(gè)任務(wù)的TIG，其總卸載期限為0.94 s，而總初始期限為0.58 s，根據(jù)式(28)，其緩慢值為62%?？梢?，TIG的平均緩慢值在初始值的基礎(chǔ)上增加了37%。改進(jìn)緩慢值的主要障礙在于TIG的通信代價(jià)，它會(huì)降低剩余松馳時(shí)間。

成功率SR是度量任務(wù)成功執(zhí)行次數(shù)的指標(biāo)。若移動(dòng)設(shè)備上的能耗小于卸載的能耗或本文設(shè)計(jì)的調(diào)度算法無法在所有資源頻率組合下提供最優(yōu)的計(jì)算代價(jià)(無法滿足其局部期限)，則應(yīng)用無法執(zhí)行完成，即為一次失敗的調(diào)度過程。從表1的結(jié)果可以看到，算法具有78%的平均調(diào)度成功率。

圖2給出了在不同TIG中算法得到的最優(yōu)資源頻率分配結(jié)果，圖3給出了在不同TIG中算法得到的最優(yōu)任務(wù)-資源分配結(jié)果。圖2中，對(duì)于擁有3個(gè)任務(wù)的TIG，任務(wù)模塊#1、#2、#3、#4和#5分別運(yùn)行在頻率600、600、600、600和1 400 MHz下。圖3中，對(duì)于擁有3個(gè)任務(wù)的TIG，任務(wù)#1、#2和#3分別分配至資源#3、#2和#1上運(yùn)行。

圖2 資源頻率最優(yōu)分配

圖3 任務(wù)-資源最優(yōu)分配

5.3 與同類調(diào)度算法對(duì)比分析

利用SPECJVM實(shí)驗(yàn)床中的開源移動(dòng)應(yīng)用DBAP進(jìn)行大規(guī)模實(shí)驗(yàn)仿真對(duì)比，該移動(dòng)應(yīng)用是一種數(shù)據(jù)庫訪問程序應(yīng)用，其TIG結(jié)構(gòu)上總體由33個(gè)任務(wù)節(jié)點(diǎn)、82條有向邊構(gòu)成。同時(shí)，選取文獻(xiàn)[9]的IP算法、文獻(xiàn)[10]的CAHPC算法和同為遺傳算法的DPGA算法[12]進(jìn)行性能比較。DPGA算法在遺傳操作上不同于傳統(tǒng)的遺傳算法，利用了初始種群和預(yù)留種群進(jìn)行解的進(jìn)化，以此豐富種群個(gè)體，為單層次的遺傳調(diào)度。圖4和圖5是算法隨著迭代次數(shù)的改變而得到的執(zhí)行時(shí)間和執(zhí)行能耗的實(shí)驗(yàn)結(jié)果。可以看出，除了IP算法，其他所有迭代式算法的執(zhí)行時(shí)間和執(zhí)行能耗均是隨著迭代次數(shù)的增加而下降的，這是由于IP算法在尋找最優(yōu)任務(wù)-資源匹配與電壓分配方案時(shí)是一次性計(jì)算結(jié)果，而沒有采用啟發(fā)式算法的迭代尋優(yōu)，因此其執(zhí)行時(shí)間和執(zhí)行能耗是恒定值。本文算法比對(duì)比算法在兩項(xiàng)指標(biāo)上更加有效，可以以更少的迭代次數(shù)和更快的速度收斂到最優(yōu)解上，這表明本文算法能有效利用松馳時(shí)間，其決策時(shí)間也更短。比較而言，DPGA算法比CAHPC算法的性能更好，DPGA采用了更好的初始種群配置方法，可以有效豐富種群個(gè)體，增加遺傳尋優(yōu)概率。而本文算法采用了兩層遺傳算法對(duì)卸載決策問題進(jìn)行求解，通過建模為一個(gè)二次分派問題尋找最優(yōu)資源頻率分配方案，這種內(nèi)層調(diào)度和外層映射的兩階段求解方法，可以產(chǎn)生接近于全局期限的完成代價(jià)，進(jìn)而使得算法在執(zhí)行時(shí)間和執(zhí)行能耗上具有更好的優(yōu)勢(shì)，較其他算法可以節(jié)省更多的能量。

圖4 執(zhí)行時(shí)間

圖5 執(zhí)行能耗

6 結(jié) 語

本文將卸載決策問題建模為一個(gè)二次分派問題，并提出一種兩層遺傳算法進(jìn)行求解，其中：內(nèi)層調(diào)度問題的目標(biāo)是通過構(gòu)建最大化的計(jì)算代價(jià)尋找最優(yōu)資源頻率分配；而外層映射問題的目標(biāo)是尋找最優(yōu)的任務(wù)-資源分配方案，以產(chǎn)生接近于全局期限的完成代價(jià)。

本文算法利用不超過期限的松馳時(shí)間，得到能效更高的調(diào)度方案。實(shí)驗(yàn)結(jié)果表明，在本文算法下進(jìn)行的任務(wù)卸載，平均可以為移動(dòng)設(shè)備節(jié)省約35%的能耗。