張俊娜 鮑 想 陳家偉 趙曉焱 袁培燕 王尚廣

1 （河南師范大學(xué)計算機與信息工程學(xué)院 河南新鄉(xiāng) 453007）

2 （智慧商務(wù)與物聯(lián)網(wǎng)技術(shù)河南省工程實驗室（河南師范大學(xué)） 河南新鄉(xiāng) 453007）

3 （網(wǎng)絡(luò)與交換技術(shù)國家重點實驗室（北京郵電大學(xué)） 北京 100876）（jnzhang@htu.edu.cn）

隨著物聯(lián)網(wǎng)的快速發(fā)展和萬物互聯(lián)時代的到來，智能移動設(shè)備在人們的日常生活中越來越普及.同時，諸如虛擬現(xiàn)實、人臉識別、圖像處理等[1]低時延、高能耗的應(yīng)用程序得到了廣泛應(yīng)用.但移動設(shè)備受電池容量、計算和存儲能力等諸多限制，直接運行上述應(yīng)用程序會帶來較高的延遲和能耗，用戶體驗極差[2].為了提升用戶體驗，邊緣計算（edge computing,EC）應(yīng)運而生，其在距離移動設(shè)備最近的邊緣網(wǎng)絡(luò)提供計算和存儲資源，目的是減少延遲來確保高效的網(wǎng)絡(luò)操作和服務(wù)交付[3].通過將移動設(shè)備中部分或全部計算任務(wù)卸載到邊緣服務(wù)器處理，可以解決移動設(shè)備在資源存儲、計算能力以及電池容量等方面存在的不足，并降低應(yīng)用的延遲.

近年來，許多學(xué)者針對任務(wù)卸載進行了研究[4-7]，然而這些研究也存在一些局限性：1）只考慮單一優(yōu)化目標.即只優(yōu)化卸載任務(wù)的完成時間或能耗.如文獻[8]只考慮卸載任務(wù)的完成時間，無法滿足用戶對能耗的需求.2）假定卸載的多個任務(wù)相互獨立.現(xiàn)實中很多應(yīng)用程序包含的任務(wù)往往存在依賴關(guān)系.例如，人臉識別應(yīng)用程序包含特征提取和特征分類任務(wù)，且“特征提取”任務(wù)的輸出是“特征分類”任務(wù)的輸入.因此，只有“特征提取”任務(wù)成功執(zhí)行，才能開始執(zhí)行“特征分類”任務(wù).3）默認邊緣服務(wù)器緩存有卸載任務(wù)所需的所有服務(wù).文獻[9-10]均研究依賴性任務(wù)的卸載問題，但均假設(shè)邊緣服務(wù)器緩存有卸載在其上的所有任務(wù)所需的服務(wù).現(xiàn)實生活中，任務(wù)的執(zhí)行往往需要特定執(zhí)行環(huán)境.例如，人臉識別應(yīng)用程序中“特征提取”任務(wù)，只能被卸載到配置有相應(yīng)機器學(xué)習(xí)服務(wù)的邊緣服務(wù)器才能被成功執(zhí)行.若邊緣服務(wù)器上沒有配置該服務(wù)，將導(dǎo)致卸載任務(wù)無法執(zhí)行.而邊緣服務(wù)器存儲資源有限，只能緩存有限服務(wù)，因此卸載任務(wù)時需考慮邊緣服務(wù)器緩存服務(wù)約束.4）假定邊緣服務(wù)器具有無限存儲和計算資源.文獻[11-12]均不考慮邊緣服務(wù)器的存儲和計算資源，而現(xiàn)實中邊緣服務(wù)器提供的資源是有限的，卸載任務(wù)時必須考慮資源受限問題，否則會出現(xiàn)任務(wù)卸載不成功的風(fēng)險.

綜上所述，已有任務(wù)卸載研究往往忽略任務(wù)間的依賴關(guān)系，默認邊緣服務(wù)器緩存有任務(wù)所需的所有服務(wù)和具有無限資源，且大多只優(yōu)化單一用戶需求.為了解決上述局限性，本文研究在邊緣服務(wù)器計算資源和服務(wù)緩存有限的情形下，權(quán)衡時延和能耗的依賴任務(wù)卸載問題，并提出了聯(lián)合時延和能耗的依賴性任務(wù)卸載方法（dependent task offloading method for joint time delay and energy consumption, DTO-TE）.

首先，放松優(yōu)化函數(shù)中的二進制變量為連續(xù)變量，并修改相關(guān)約束，將問題轉(zhuǎn)換成凸優(yōu)化問題進行求解.其次，將得到的小數(shù)解作為卸載概率進行迭代運算使其恢復(fù)成二進制解，作為應(yīng)用程序中每個任務(wù)的可行卸載決策，并根據(jù)該決策計算任務(wù)的卸載優(yōu)先級.最后，按照任務(wù)優(yōu)先級從高到低依次將任務(wù)卸載到成本最小的邊緣服務(wù)器.若多個依賴任務(wù)卸載到不同的邊緣服務(wù)器，則采用改進粒子群優(yōu)化方法（particle swarm optimization, PSO）求解邊緣服務(wù)器的最佳傳輸功率，從而獲得最小的傳輸時延和傳輸能耗.

本文的主要貢獻有4 點：

1）在邊緣服務(wù)器計算資源和服務(wù)緩存有限的約束下，建立了任務(wù)依賴模型、網(wǎng)絡(luò)模型、完成時間模型和能耗模型，并采用線性加權(quán)的方法將對時延和能耗的共同優(yōu)化轉(zhuǎn)化為對成本優(yōu)化的單目標優(yōu)化問題.

2）針對非凸的NP-hard 問題，通過松弛約束中的二進制變量將其轉(zhuǎn)換成凸優(yōu)化問題.采用凸優(yōu)化工具求得可行卸載決策，從而確定任務(wù)的最優(yōu)卸載順序.

3）若將多個依賴任務(wù)卸載到不同的邊緣服務(wù)器，邊緣服務(wù)器間因傳輸數(shù)據(jù)產(chǎn)生成本.為了最小化總成本，采用改進的粒子群算法求解邊緣服務(wù)器的最佳傳輸功率.

4）基于真實數(shù)據(jù)集，本文方法與已有的方法進行了充分的實驗對比.實驗結(jié)果表明，本文方法比其他對比方法在總成本上減少8%～23%.

1 相關(guān)工作

近年來，任務(wù)卸載作為EC 關(guān)鍵技術(shù)之一受到了廣泛的關(guān)注.針對任務(wù)卸載問題，許多學(xué)者提出了解決方法或研究思路，并取得了較好的研究成果.下面將對一些與本文研究密切相關(guān)的成果予以分析.

文獻[13]研究小蜂窩網(wǎng)絡(luò)下單個邊緣服務(wù)器的任務(wù)卸載問題，并提出了一種高效的低時延云邊端協(xié)同卸載方案，該方案不僅可以降低任務(wù)的總處理時延，還可以處理大量的用戶請求.文獻[14]在多基站的EC 場景下，研究多用戶任務(wù)卸載問題，該問題以最小化所有用戶最大任務(wù)執(zhí)行時間為目標，提出了一種啟發(fā)式計算卸載方法.文獻[8]研究了兼顧邊緣服務(wù)器服務(wù)緩存的依賴任務(wù)卸載問題，以最小化卸載任務(wù)的完成時間為目標，提出基于凸優(yōu)化的依賴任務(wù)卸載方法.該方法將每個任務(wù)卸載到完成時間最小的邊緣服務(wù)器上，從而優(yōu)化整個應(yīng)用程序的完成時間.文獻[15]在超密集組網(wǎng)的EC 場景下，聯(lián)合優(yōu)化卸載決策和資源分配問題，提出了基于坐標下降法的任務(wù)卸載方案.然而，文獻[13-15]只考慮單一優(yōu)化目標，即只優(yōu)化時延或能耗，無法滿足用戶對時延和能耗的共同需求.

文獻[16]針對超密集網(wǎng)絡(luò)下獨立任務(wù)的卸載問題，提出一種基于雙深度Q 網(wǎng)絡(luò)的在線卸載方法，通過特定的神經(jīng)網(wǎng)絡(luò)估計每個動作所獲得的獎勵值，獲得最優(yōu)的任務(wù)卸載策略以及最佳的CPU 頻率和發(fā)射功率，從而最小化任務(wù)的完成時間和終端能耗.文獻[17]研究在邊緣服務(wù)器資源受限情形下的獨立任務(wù)卸載問題，為了有效利用EC 的計算資源和提高用戶體驗，以最小化所有移動設(shè)備的時延和能耗為目標，提出了一種高效的李亞普諾夫在線算法，獲得了最優(yōu)的任務(wù)卸載和數(shù)據(jù)緩存決策.文獻[18]研究在多個邊緣服務(wù)器覆蓋場景下的獨立任務(wù)卸載問題.該文獻設(shè)計了一種概率優(yōu)先的先驗卸載模型，將問題轉(zhuǎn)換成平衡時延和能耗的效用函數(shù)，提出基于遺傳算法的聯(lián)合卸載比例和傳輸功率的分布式先驗卸載機制.文獻[16-18]均假定卸載的多個任務(wù)相互獨立，然而現(xiàn)實應(yīng)用程序中任務(wù)間往往存在依賴關(guān)系.

文獻[9]研究依賴任務(wù)的調(diào)度決策問題.在應(yīng)用程序完成時間的約束下，將調(diào)度決策問題構(gòu)建成以應(yīng)用程序執(zhí)行成本最小化為目標的優(yōu)化函數(shù)，提出啟發(fā)式多用戶重分配卸載方法以獲取最優(yōu)的卸載決策，從而優(yōu)化任務(wù)的完成時間.文獻[10]提出一種面向多用戶的串行任務(wù)動態(tài)卸載策略，為所有任務(wù)做出近似最優(yōu)的卸載策略，從而使平均完成時間和移動設(shè)備的平均能耗達到近似最優(yōu).文獻[19]研究在完成時間受到預(yù)定期限的約束下依賴任務(wù)的卸載問題，以最小化移動設(shè)備的能耗為目標，提出了一種高效的自適應(yīng)卸載算法，確定哪些任務(wù)必須被卸載及卸載到哪個邊緣服務(wù)器.文獻[9-10,19]雖然考慮了任務(wù)之間的依賴關(guān)系，但均假設(shè)邊緣服務(wù)器上緩存有執(zhí)行卸載任務(wù)的服務(wù).因邊緣服務(wù)器的存儲能力有限，往往只能緩存有限的服務(wù).

文獻[20]針對邊緣服務(wù)器只能緩存有限服務(wù)的情形，研究依賴任務(wù)的卸載和調(diào)度問題.為了降低所有卸載任務(wù)的完成時間，提出一種求解最優(yōu)任務(wù)分配和高效調(diào)度的方法.文獻[11]研究具有時間約束的依賴任務(wù)卸載問題.為了最小化應(yīng)用程序完成時間，提出了基于貪婪調(diào)度的個體時間分配算法.文獻[12]研究在服務(wù)緩存受限的EC 系統(tǒng)中依賴任務(wù)的調(diào)度問題.為了解決任務(wù)對邊緣服務(wù)器資源的競爭，將任務(wù)調(diào)度定義為以最小化時延為目標的優(yōu)化問題，并在此基礎(chǔ)上，提出了上下文感知的貪婪任務(wù)調(diào)度算法以獲得最佳的調(diào)度決策.文獻[11-12, 20]均假設(shè)邊緣服務(wù)器的計算資源是無限的，可執(zhí)行任意數(shù)量的任務(wù).但現(xiàn)實中邊緣服務(wù)器往往具有有限的資源.

為了解決上述局限性，本文研究在邊緣服務(wù)器計算資源和服務(wù)緩存有限的情形下，權(quán)衡時延和能耗的依賴任務(wù)卸載問題，并提出了DTO-TE 方法.

2 系統(tǒng)建模和問題描述

本節(jié)首先介紹邊緣服務(wù)器間的網(wǎng)絡(luò)模型和任務(wù)間的依賴模型；然后詳細描述了任務(wù)卸載到邊緣服務(wù)器執(zhí)行的完成時間模型和能耗模型；最后描述了在邊緣服務(wù)器計算資源和服務(wù)緩存有限的情形下，依賴性任務(wù)的卸載問題，并將其構(gòu)建成以最小化總成本為目標的優(yōu)化函數(shù).

2.1 網(wǎng)絡(luò)模型

本文建立的網(wǎng)絡(luò)模型如圖1 所示，邊緣網(wǎng)絡(luò)由若干個基站組成，每個基站均部署1 個EC 服務(wù)器，不同EC 服務(wù)器具有不同的處理和通信能力，且通過無線方式相互通信.虛線方框中內(nèi)容表示邊緣服務(wù)器緩存的服務(wù)，不同形狀的圖形表示不同的服務(wù)；實線表示邊緣服務(wù)器之間通過局域網(wǎng)或蜂窩網(wǎng)連接.

Fig.1 Network model圖1 網(wǎng)絡(luò)模型

集合M={m1,m2,···,ml,}表示EC 網(wǎng)絡(luò)中的集，其中l(wèi)表示邊緣服務(wù)器的數(shù)量.從邊緣服務(wù)器m傳輸數(shù)據(jù)到邊緣服務(wù)器m′的 通信延遲為tmm′.當m=m′時，表示為同一服務(wù)器，此時通信時延為0.每個邊緣服務(wù)器最大限度地緩存服務(wù)，Mv表示可以處理任務(wù)v的邊緣服務(wù)器集，即任務(wù)v只能卸載到Mv中的邊緣服務(wù)器上才能被執(zhí)行.此外，每個邊緣服務(wù)器具有有限的計算資源，采用CPU 周期表示.邊緣服務(wù)器m具有的計算資源為C（m）.tvm表示任務(wù)v卸載到邊緣服務(wù)器m上的執(zhí)行時間，rvm表示邊緣服務(wù)器m執(zhí)行任務(wù)v每秒所需要的CPU 周期.

2.2 任務(wù)依賴模型

本文研究將1 個應(yīng)用程序卸載到EC 環(huán)境中.假定應(yīng)用程序能被劃分成多個依賴任務(wù)，1 個任務(wù)僅能被卸載到1 個邊緣服務(wù)器，且任務(wù)執(zhí)行需要計算資源和相應(yīng)服務(wù)的支持.如圖2 所示，假設(shè)應(yīng)用程序由4 個任務(wù)組成.只有菱形代表的服務(wù)可為任務(wù)2 提供執(zhí)行環(huán)境，那么任務(wù)2 只能被卸載到緩存有菱形代表的服務(wù)的邊緣服務(wù)器上.此外，任務(wù)2 與任務(wù)1 存在依賴關(guān)系，即任務(wù)2 是任務(wù)1 的后繼任務(wù)，那么當且僅當任務(wù)1 執(zhí)行完畢，且執(zhí)行結(jié)果被傳輸?shù)饺蝿?wù)2卸載的邊緣服務(wù)器后，任務(wù)2 才可以執(zhí)行.

Fig.2 Task dependent model圖2 任務(wù)依賴模型

本文采用有向無環(huán)圖（directed acyclic graph,DAG），G=（V, E）表示任務(wù)之間的依賴關(guān)系，其中V表示任務(wù)集，E表示邊集.為了便于描述，為應(yīng)用程序構(gòu)建DAG 時增加2 個虛擬任務(wù)vs和ve.vs表示開始任務(wù)，沒有前驅(qū)任務(wù)；ve表示結(jié)束任務(wù)，沒有后繼任務(wù).這2 個任務(wù)無需被卸載，即在用戶設(shè)備執(zhí)行時所需時間為0，那么應(yīng)用（包含n個任務(wù)）DAG 的任務(wù)集為V={vs,v1,v2,···,vn,ve}.有向邊 (v,v′)表 示任務(wù)v和v′之間存在依賴關(guān)系，即任務(wù)v的輸出是任務(wù)v′的輸入.用dvv′表 示 任 務(wù)v到任 務(wù)v′需 傳輸 的 數(shù) 據(jù) 量.表1 總 結(jié) 了在本文中使用的關(guān)鍵符號.

Table 1 Key Symbols Meaning表1 關(guān)鍵符號意義

2.3 完成時間模型

由2.2 節(jié)可知，應(yīng)用程序的完成時間從vs開始執(zhí)行，至ve執(zhí)行完畢.vs和ve為虛擬節(jié)點，所需的執(zhí)行時間為0，那么vs執(zhí)行結(jié)束時刻即為應(yīng)用程序開始時刻，ve開始執(zhí)行時刻即為應(yīng)用程序結(jié)束時刻.當ve的所有前驅(qū)任務(wù)均執(zhí)行完畢，并把結(jié)果傳回到用戶設(shè)備時，用戶設(shè)備可開始執(zhí)行.由此可知，應(yīng)用程序的完成時間可由組成其的任務(wù)完成時間及任務(wù)間的依賴關(guān)系得出.

通過2.2 節(jié)構(gòu)造的應(yīng)用程序的DAG 可知，任務(wù)v能夠執(zhí)行時需滿足2 個條件：1）任務(wù)v所有前驅(qū)任務(wù)均執(zhí)行完畢，且把執(zhí)行結(jié)果傳輸至其被卸載的邊緣服務(wù)器；2）卸載任務(wù)v的邊緣服務(wù)器有計算資源執(zhí)行任務(wù)v.

依賴任務(wù)被卸載至相同邊緣服務(wù)器，數(shù)據(jù)傳輸時延為0；卸載至不同邊緣服務(wù)器時，需要傳輸?shù)臄?shù)據(jù)量為dv′v，則傳輸時延可表示為

其中Rm′m是邊緣服務(wù)器m′到 邊緣服務(wù)器m的傳輸速率，tm′m表示m′與m之間的傳輸時延，可通過香農(nóng)公式[10]計算得到：

其中B是信道帶寬，Pm′是邊緣服務(wù)器m′的傳輸功率，hm′m是m′和m之 間的信道增益，N0表示噪聲功率.

任務(wù)v可能由多個前驅(qū)組成，那么任務(wù)v接收到所有前驅(qū)任務(wù)執(zhí)行結(jié)果的時刻為

其中Pred(v)表 示任務(wù)v的直 接前驅(qū)任務(wù)集合，tv′表示任務(wù)v′的開始執(zhí)行時刻，tv′m′表 示任務(wù)v′在邊緣服務(wù)器m′上所需執(zhí)行時間.

此外，本文研究場景中，邊緣服務(wù)器串行執(zhí)行卸載至其上的任務(wù).當任務(wù)v卸載到邊緣服務(wù)器m時，需要等待排在其前面的所有任務(wù)執(zhí)行完才能被執(zhí)行.假如排在任務(wù)v之前的任務(wù)為k，用SLm表示任務(wù)k被卸載的邊緣服務(wù)器m執(zhí)行完畢的時刻，那么有

其中tk表示任務(wù)k真正的開始時刻，tkm表 示任務(wù)k在邊緣服務(wù)器m上的執(zhí)行時間.

因此，任務(wù)v在邊緣服務(wù)器m上的開始時刻為

通過上述分析，應(yīng)用程序的完成時間可表示為

其中二進制變量zmv表示任務(wù)v是否卸載到邊緣服務(wù)器m上 ，zmv= 1 表示是，zmv=0 表示否.tvm表 示任務(wù)v在邊緣服務(wù)器m上的執(zhí)行時間.

2.4 能耗模型

執(zhí)行應(yīng)用程序的能耗包括在用戶設(shè)備和在邊緣服務(wù)器上產(chǎn)生的能耗.本文只關(guān)注邊緣服務(wù)器上產(chǎn)生的能耗、可能產(chǎn)生執(zhí)行卸載任務(wù)的執(zhí)行能耗，以及傳輸具有依賴關(guān)系任務(wù)之間的執(zhí)行結(jié)果的傳輸能耗.

任務(wù)v在邊緣服務(wù)器m的執(zhí)行能耗evm可表示為

假設(shè)2 個依賴任務(wù) (v,v′)分別被卸載到邊緣服務(wù)器m′和 邊緣服務(wù)器m時，傳輸能耗可表示為

其中Pm′表 示邊緣服務(wù)器m′的傳輸功率.

因此，邊緣服務(wù)器的總能耗可以表示為

其中M′表 示任務(wù)v所有前驅(qū)任務(wù)所在的邊緣服務(wù)器集合.

2.5 研究問題描述

本文研究在邊緣服務(wù)器計算資源和服務(wù)緩存有限的約束下，聯(lián)合時延和能耗的依賴任務(wù)卸載問題.引入時延和能耗的偏好權(quán)重變量 ω(ω ∈[0,1])，其取值由用戶對時延和能耗的需求決定[21].如果對時延的需求超過能耗時，例如延遲敏感型應(yīng)用人臉識別，用戶更關(guān)注時延時， ω ＜0.5；反之，例如執(zhí)行應(yīng)用的設(shè)備為電池容量有限的移動設(shè)備，用戶更關(guān)注能耗時，ω ≥0.5.因此，根據(jù)式（6）（9），權(quán)衡時延和能耗的應(yīng)用程序總成本可定義為

綜合以上分析，本文研究問題可以優(yōu)化為

其中：C1表示任務(wù)的卸載決策，取zmv=1 表示任務(wù)v被卸載到邊緣服務(wù)器m上，反之取zmv=0；C2表示每個任務(wù)只能卸載到緩存有其所需服務(wù)的邊緣服務(wù)器；C3表示依賴任務(wù)之間的執(zhí)行順序；C4表示同一邊緣服務(wù)器上任務(wù)的執(zhí)行順序；C5表示任務(wù)需要卸載到滿足其計算資源的邊緣服務(wù)器；C6表示邊緣服務(wù)器傳輸功率的取值范圍.

文獻[8]研究在邊緣服務(wù)器計算資源和服務(wù)緩存有限的約束下，時延最優(yōu)的依賴性任務(wù)卸載問題，并證明了研究問題為NP-hard 問題.與文獻[8]研究問題相比，本文優(yōu)化目標增加了能耗，因此，本文研究問題也屬于NP-hard 問題.

根據(jù)化學(xué)結(jié)構(gòu)分類，腸內(nèi)營養(yǎng)制劑可分為要素型與非要素型，要素型以氨基酸或蛋白水解物（氨基酸、肽類）為氮源，不需消化或少量消化便可吸收。非要素型是以整蛋白為氮源，需經(jīng)過消化才可以吸收。對于消化和吸收功能基本正常的患者可選用非要素型腸內(nèi)營養(yǎng)制劑，如營養(yǎng)不良，中度燒傷、創(chuàng)傷，昏迷不醒等患者。而對于消化和吸收功能受到不同損傷的患者更適用要素型腸內(nèi)營養(yǎng)制劑，如重度燒傷、創(chuàng)傷，腸瘺，膽囊纖維化，急性胰腺炎，短腸綜合征等患者。

3 聯(lián)合時延和能耗的依賴性任務(wù)卸載方法

為了求解本文研究的NP-hard 問題，本節(jié)提出一種聯(lián)合時延和能耗的依賴性任務(wù)卸載方法，該方法可分3 步：1）松弛二進制變量.松弛式（11）中C1，將問題轉(zhuǎn)換為凸優(yōu)化問題，即轉(zhuǎn)化NP-hard 問題，并使用凸優(yōu)化工具進行求解，為每個卸載任務(wù)獲得多個介于[0,1]的松弛解；2）計算卸載任務(wù)的優(yōu)先級.選擇每個任務(wù)松弛解中最大值作為其可行解，通過迭代運算確定每個任務(wù)的卸載優(yōu)先級；3）完成卸載任務(wù).按照優(yōu)先級從高到低把任務(wù)卸載到邊緣服務(wù)器，若多個依賴任務(wù)可卸載到不同的邊緣服務(wù)器，則采用改進的粒子群方法求解邊緣服務(wù)器的最佳傳輸功率.

3.1 松弛變量和定義優(yōu)先級

由式（11）中約束C1可知，本文研究問題為非凸問題.將C1中二進制變量zmv松弛為[0,1]（即C7），即假設(shè)每個卸載任務(wù)可被劃分為若干個子任務(wù)，且可被卸載到不同的邊緣服務(wù)器并行執(zhí)行.因此優(yōu)化問題可轉(zhuǎn)換為

引理1.式（12）為凸優(yōu)化問題.

證明.由凸優(yōu)化問題的判定準則可知，若式（12）同時滿足3 個條件時為凸優(yōu)化問題：

1）目標函數(shù)為凸函數(shù).目標函數(shù)為多元變量相加的一次函數(shù)，因此其Hesse 矩陣為零矩陣.又因零矩陣為半正定矩陣，所以目標函數(shù)為凸函數(shù).

2）不等式約束為凸函數(shù).式（12）中有多個不等式約束，但證明方法類似.現(xiàn)以最復(fù)雜的不等式約束C3為例進行證明.令c(x)=tv′+tv′m′+tmm′-tv，可以看出c(x)為多元相加的一次函數(shù)，Hesse 矩陣為0，因此約束C3為凸函數(shù).同理，其他不等式約束也是凸函數(shù).

3）等式約束為仿射函數(shù).將式（12）中約束C2轉(zhuǎn)換成可得出g(x)為仿射函數(shù).

綜上所述，式（12）為凸優(yōu)化問題.證畢.

由于式（12）中傳輸功率是未知的，為了能求解凸優(yōu)化問題，先將傳輸功率固定為其范圍內(nèi)的隨機數(shù)（其最優(yōu)值求解見3.2 節(jié)）.借助CPLEX[22]凸優(yōu)化工具在多項式時間求得最優(yōu)解.由于為連續(xù)變量，所以求得的解 0 ≤≤1.但本文中任務(wù)是不可拆分的，需把松弛后得到的結(jié)果恢復(fù)成原始問題的二進制值.

通過求得的每個任務(wù)可行的卸載決策，將DAG每條邊的權(quán)值設(shè)為wv′v=tv′m+ev′m，與結(jié)束任務(wù)相連的邊的權(quán)值設(shè)為0.任務(wù)v到結(jié)束任務(wù)的最大權(quán)值定義為任務(wù)v的優(yōu)先級，采用L(v)表示，按照優(yōu)先級倒序存放在隊列Q中.按照隊列Q卸載任務(wù)，不僅能保留任務(wù)間的依賴關(guān)系，還將DAG 中最長路徑上的任務(wù)優(yōu)先卸載執(zhí)行.

3.2 卸載任務(wù)

為了方便描述，再定義一些變量，用R(m)表示邊緣服務(wù)器m的剩余資源，Mv(R)表 示同時滿足任務(wù)v的計算資源和服務(wù)緩存約束的邊緣服務(wù)器集合.根據(jù)3.1 節(jié)得到的隊列Q依次將任務(wù)卸載到總成本最小的邊緣服務(wù)器.每卸載一個任務(wù)v，用式（13）～（17）更新其實際的開始時間AS T(v,mv)、 完成時間ACT(v,mv)、能耗SEC(v,mv) 、 總能耗TEC(v,mv)和 剩余資源R(mv).

在2.1 節(jié)中，為了能夠?qū)κ剑?2）求解，假設(shè)傳輸功率為隨機值.隨著傳輸功率取值的增大，時延會變短，但能耗會增加；反之隨著傳輸功率取值的減小，能耗會降低，但又會增加時延.為了能夠使應(yīng)用程序的總成本最小，應(yīng)求邊緣服務(wù)器的最佳傳輸功率.由文獻[23]可知，邊緣服務(wù)器間最佳傳輸功率問題為NP-hard 問題，因此只能采用啟發(fā)式算法進行求解.基于PSO 不依賴問題規(guī)模，設(shè)置參數(shù)少、收斂速度快的特點，本文采用改進的PSO 算法求解邊緣服務(wù)器間的最佳傳輸功率.

3.2.1 PSO 算法

PSO 是基于群體的進化方法，源于對鳥群捕食的行為研究，基本思想是通過群體中個體之間的協(xié)作和信息共享來尋找最優(yōu)解.本文采用的PSO 在1維的搜索空間隨機產(chǎn)生V個粒子構(gòu)成原始種群X={x1,x2,···,xv}.對應(yīng)于本文研究問題，搜索空間為邊緣服務(wù)器間傳輸功率的可取值范圍.每個粒子包含位置和速度2 個屬性，位置表示搜索空間中一個解，即邊緣服務(wù)器間傳輸功率一個取值；速度表示粒子在搜索空間中尋找最佳傳輸功率的方向和大小.尋優(yōu)過程中第k個粒子搜索到的最優(yōu)位置表示為pbestk,全局搜索過程中粒子群搜索到的最優(yōu)位置表示為gbest,第k個粒子的位置和速度更新的計算過程[24]分別為

其 中w表 示 慣 性 權(quán) 重，c1和c2為 學(xué) 習(xí) 因 子，rand()表 示[0,1]的隨機數(shù)，t表示迭代次數(shù).

雖然經(jīng)典PSO 算法收斂速度較快，但存在容易陷入局部最優(yōu)解等缺點[25]，究其原因是因為經(jīng)典PSO算法采用固定的慣性權(quán)重.較大的慣性權(quán)重有利于跳出局部解，便于全局搜索；而較小的慣性權(quán)重則有利于對當前的搜索區(qū)域進行精確局部搜索.當慣性權(quán)重的值恒定時，迭代前期缺少全局搜索能力或迭代后期缺少局部搜索能力，易造成PSO 方法陷入局部最優(yōu)解，或后期在全局最優(yōu)解附近產(chǎn)生振蕩現(xiàn)象.為了平衡全局和局部搜索能力，本文改進了經(jīng)典PSO算法.

3.2.2 改進的PSO 算法

本文采用如式（20）所示的慣性權(quán)重線性遞減的調(diào)整方法進行尋優(yōu)：

其中wmax，wmin分 別表示w的最大值和最小值，t表示當前迭代次數(shù)，tmax表 示最大迭代次數(shù)，通常取wmax=0.9，wmin=0.4[25].

3.2.3 適應(yīng)度函數(shù)構(gòu)造

PSO 算法采用適應(yīng)度評價優(yōu)化目標.本文將任務(wù)在邊緣服務(wù)器上執(zhí)行產(chǎn)生的時延和能耗作為優(yōu)化目標.構(gòu)造適應(yīng)度函數(shù)為

其中fitness值越小，越優(yōu)，反之亦然.

3.3 方法實現(xiàn)

通過3.2 節(jié)的分析，本節(jié)將詳細描述聯(lián)合時延和能耗的依賴性任務(wù)卸載方法，即DTO-TE 方法.該方法為應(yīng)用程序中所有卸載任務(wù)做出最優(yōu)的卸載決策，從而優(yōu)化任務(wù)卸載產(chǎn)生的總成本.

DTO-TE 的具體實現(xiàn)過程如算法1.

算法1.DTO-TE 方法.

輸入：任務(wù)集合V，邊緣服務(wù)器集合M，DAG；

輸出：任務(wù)的卸載決策和應(yīng)用程序的總成本.

①根據(jù)3.2 節(jié)計算每個任務(wù)的優(yōu)先級L(v)；

②按照任務(wù)優(yōu)先級降序排列，并保存到卸載隊列Q；

③初始化AS T(v)=ACT(v)=TEC(v)=0；

④初始化邊緣服務(wù)器的剩余資源R(m)=C(m)；

⑤ whileQ≠?

⑥v=Q.top（），將任務(wù)v產(chǎn)生的能耗SEC(v)置0；

⑦ form∈Mv(R) do

⑧ 用3.2.2 節(jié)提出的改進PSO 算法計算m和v前驅(qū)任務(wù)所在的邊緣服務(wù)器間的最佳傳輸功率；

⑨ 計算保存v在邊緣服務(wù)器m的總成本；

⑩ end for

? 將任務(wù)卸載到成本最小的邊緣服務(wù)器；

? 根據(jù)式（14）（16）（17）更新ACT，TEC，R(m)；

? 保存v的卸載決策并從隊列Q刪 除任務(wù)v；

? end while

算法1 的分析過程分為2 個部分：1）獲取任務(wù)的優(yōu)先級，按照優(yōu)先級降序保存到隊列Q，并初始化任務(wù)和邊緣服務(wù)器信息（行③④）.2）判斷Q是否為空，若非空將其中的任務(wù)按順序卸載到總成本最小的邊緣服務(wù)器上.用改進的PSO 算法求解邊緣服務(wù)器間的最佳傳輸功率（行⑤～?）.更新任務(wù)的完成時間、總能耗和最終卸載的邊緣服務(wù)器的剩余資源，并從隊列中刪除已卸載任務(wù)，繼續(xù)循環(huán)，直至循環(huán)結(jié)束（行?～?）.

算法2給出了改進的PSO 算法求得最優(yōu)傳輸功率的過程.

算法2.改進的PSO 算法.

輸入: 任務(wù)v前驅(qū)任務(wù)所在的邊緣服務(wù)器和任務(wù)v所在的邊緣服務(wù)器；

輸出: 最佳傳輸功率.

①初始化種群規(guī)模PopS ize=20 ， 加速因子c1=2，c2=2， 迭代次數(shù)為MaxIter；

② 根據(jù)式（21）,計算每個粒子的適應(yīng)度值；

③ forj=1 toPopS ize

④ 初始位置xj和初始速度vj在搜索空間范圍內(nèi)隨機產(chǎn)生；

⑤pbestj=xj；/*初始化每個粒子的歷史最優(yōu)解*/

⑥endfor

⑦gbestj=max(pbestj)； /*初始化全局最優(yōu)解*/

⑧ fori=1 toMaxIter

⑨ forj=1 toPopS ize

⑩ 根據(jù)式（20）更新權(quán)重；

? 根據(jù)式（18）（19）更新粒子速度vi和 位置xi；

? 計算適應(yīng)度函數(shù)得出適應(yīng)度值fitness(xi)；

? 更新粒子的歷史最優(yōu)解；

? 更新全局最優(yōu)解；

? end for

? end for

? 最佳傳輸功率=gbesti.

算法2 可分為5 個部分.1）定義了種群規(guī)模、加速因子、迭代次數(shù)和適應(yīng)度函數(shù)（行①②）并隨機生成每個粒子的初始位置（傳輸功率的初始值）、初始速度、每個粒子的極值和全局最優(yōu)解（行③～⑦）.2）進行迭代（行⑧～?），迭代部分可分為3 個階段： 更新權(quán)重；更新每個粒子的位置、速度；計算當前位置的適應(yīng)度值（當前傳輸功率對應(yīng)的成本）（行⑩～?）.3）比較當前粒子位置所得適應(yīng)度值是否小于當前粒子歷史最優(yōu)解的適應(yīng)度值，若是，則更新粒子的歷史最優(yōu)解；否則，當前粒子歷史最優(yōu)解不變（行?）.4）比較當前粒子歷史最優(yōu)解的適應(yīng)度值是否小于全局最優(yōu)解的適應(yīng)度值，若是，則更新全局最優(yōu)解（行?）.5）迭代結(jié)束后，將全局最優(yōu)解作為最佳傳輸功率（行?）.

3.4 算法1 的時間復(fù)雜度分析

假設(shè)應(yīng)用程序中的任務(wù)數(shù)量為n，邊緣服務(wù)器數(shù)量為l，每個任務(wù)的前驅(qū)任務(wù)數(shù)量為P，粒子種群規(guī)模為PopS ize，最大迭代次數(shù)為MaxIter.算法1 中，行①～④求解任務(wù)的卸載順序，并初始化信息，其時間復(fù)雜度為O(n2)；行⑤～?，按照隊列中任務(wù)順序進行卸載，但卸載過程中需用改進的PSO 算法求解邊緣服務(wù)器間的傳輸功率.由于本文采用的PSO 算法是一維的，故時間復(fù)雜度為O(MaxIter×PopS ize+PopS ize).所以算法1 中行⑤～?的時間復(fù)雜度為O(n×l×P×PopS ize×(MaxIter+1)).

綜上所述，算法1 總的時間復(fù)雜度為O(n2+n×l×P×PopS ize×(MaxIter+1)).

4 實驗驗證

4.1 實驗設(shè)置

本文實驗配置為：華碩靈耀S4000UA, IntelRCoreTMi5-7200U CPU@ 2.5～2.7 GHz， RAM 8192 MB,Windows 10 中文版 64 b，實驗環(huán)境為Python3.9.0.

在EC 網(wǎng)絡(luò)場景中[26]，假設(shè)網(wǎng)絡(luò)中有1 個應(yīng)用程序需要卸載.該應(yīng)用程序可分為若干個任務(wù)，根據(jù)任務(wù)之間的依賴關(guān)系，使用拓撲排序算法生成DAG.使用谷歌數(shù)據(jù)集[27]模擬每個任務(wù)在邊緣服務(wù)器上的處理時間和所需的處理資源.為了便于實驗，本文采用文獻[8]中的做法，將數(shù)據(jù)集中的任務(wù)執(zhí)行時間和所需的處理資源統(tǒng)一映射至區(qū)間（1,10）.緩存某一服務(wù)的邊緣服務(wù)器數(shù)量并設(shè)置為邊緣服務(wù)器總數(shù)量的50%.邊緣服務(wù)器間信道帶寬和背景噪聲功率設(shè)置參考文獻[28]，邊緣服務(wù)器的能量系數(shù)、最大傳輸功率和信道增益參考文獻[18]，具體數(shù)值如表2 所示.

Table 2 Experimental Parameters表2 實驗參數(shù)

4.2 對比方法

由于沒有和本文方法完全一致的方法，故修改與本文類似的3 種已有方法作為對比方法.

對比方法1：文獻[8]提出的方法CP，其在邊緣服務(wù)器具有服務(wù)緩存和有限資源的約束下，優(yōu)化應(yīng)用程序的完成時間.根據(jù)本文的研究問題，在CP 方法的優(yōu)化目標中加入能耗.

對比方法2：文獻[11]提出的基于貪婪卸載的個體時間分配方法ITAGS，其目標是在滿足完成時間約束的同時最小化通信和計算成本.為了能使ITAGS與本文所提方法進行比較，將 ITAGS 的約束條件修改為本文所提方法的約束條件.

對比方法3：文獻[12]提出的一種上下文感知的貪婪任務(wù)調(diào)度方法CaGTS，其目標是最小化任務(wù)的響應(yīng)時間.將CaGTS 的優(yōu)化目標和約束條件修改為本文方法的優(yōu)化目標和約束條件.

4.3 數(shù)值歸一化

相較于時延，能耗的值較大，兩者不在同一數(shù)量級，導(dǎo)致時延在實驗結(jié)果中的占比小，對任務(wù)的卸載決策影響較小.為了使時延和能耗在同一數(shù)量級上，需要對時延和能耗進行歸一化.由于時延和能耗中存在未知變量，如傳輸功率作為一種常用的歸一化方法不適用于本文.

本文采用文獻[29]的方法，將時延擴大到與能耗同一數(shù)量級，即E/(α×T)≈1， 歸一化因子 α為正數(shù).對應(yīng)用程序包含的任務(wù)數(shù)量取不同值，并設(shè)定DAG邊數(shù)是任務(wù)數(shù)量的2 倍，邊緣服務(wù)器的數(shù)量為10.采用不同的 α值分別進行實驗，實驗結(jié)果如圖3 所示.隨著 α的增加不同任務(wù)數(shù)量下的E/(α×T)呈 下降趨勢.當α=10時 ，不同任務(wù)數(shù)量下的E/(α×T)≈1.因此，在下面實驗中，均將時延擴大10 倍后再計算應(yīng)用程序的總成本.

Fig.3 Effect of α onE/(α×T)圖3 α 對E /(α×T)的影響

4.4 參數(shù)分析

為了降低參數(shù)對實驗結(jié)果的影響，本節(jié)對權(quán)重因子、邊緣服務(wù)器數(shù)量和迭代次數(shù)設(shè)置不同的值進行實驗，并觀察這些參數(shù)對實驗結(jié)果的影響.為了保證實驗結(jié)果的公正性，本文每類實驗結(jié)果均取運行100 次實驗后的平均值.

4.4.1 權(quán)重因子 ω的影響

設(shè)定實驗環(huán)境中邊緣服務(wù)器的數(shù)量為10，應(yīng)用程序的任務(wù)數(shù)量為500，DAG 邊的條數(shù)為1 000.變化ω的取值，采用本文方法和3 種對比方法進行實驗.時延隨 ω變化結(jié)果如圖4（a）所示，可以看出 ω取值與時延成正比關(guān)系；能耗隨 ω變化結(jié)果如圖4（b）所示，ω取值與能耗成反比關(guān)系.也就是說，當 ω ＜0.5時，意味著用戶更偏好時延，此時，可增大用戶設(shè)備到邊緣服務(wù)器的傳輸功率，降低任務(wù)的傳輸時間；相反，當ω ≥0.5時，意味著用戶對能耗的需求較高，此時，邊緣服務(wù)器可以適當增大應(yīng)用程序的完成時間，以降低邊緣服務(wù)器的能耗.為了驗證本文方法既能滿足用戶時延偏好又能滿足能耗偏好，下面每類時延對 ω分別取值為0.2 和0.8.

Fig.4 Effect of weights on time and energy consumption圖4 權(quán)重對時間和能耗的影響

此外，從圖4 還可以看出，無論 ω怎么取值，本文方法實驗結(jié)果均優(yōu)于3 個對比方法.

4.4.2 邊緣服務(wù)器數(shù)量對總成本的影響

邊緣環(huán)境中邊緣服務(wù)器的數(shù)量對實驗結(jié)果也會產(chǎn)生影響.數(shù)量較少時，每個邊緣服務(wù)器需要處理的任務(wù)會較多.又因為邊緣服務(wù)器串行處理卸載在其上的任務(wù)，所以會增加任務(wù)的等待時延，從而增加應(yīng)用程序的總時延.真實場景中因為成本問題，網(wǎng)絡(luò)提供商也不可能部署特別多的邊緣服務(wù)器.所以本節(jié)通過實驗，試圖找到一種合適的服務(wù)器數(shù)量設(shè)置，既不會增加過多的等待時延，又較符合真實場景中邊緣服務(wù)器的數(shù)量部署.

設(shè)定應(yīng)用程序包含的任務(wù)數(shù)量為500，DAG 邊的條數(shù)為1 000， ω分別取值為0.2 和0.8，變化邊緣服務(wù)器的數(shù)量，采用4 種方法分別進行實驗，實驗結(jié)果如圖5 所示.隨著邊緣服務(wù)器數(shù)量的增加，4 種方法的總成本都明顯下降.主要因為當邊緣服務(wù)器數(shù)量為2 時，所有任務(wù)只能卸載到2 個邊緣服務(wù)器上，且卸載到同一邊緣服務(wù)器的概率變大，因此，任務(wù)在邊緣服務(wù)器上的等待時間變長，從而增加了總成本.而隨著邊緣服務(wù)器數(shù)量的增加，任務(wù)可選擇卸載的邊緣服務(wù)器數(shù)量也隨之增加，對邊緣服務(wù)器資源的競爭也在降低，因此，降低了任務(wù)在邊緣服務(wù)器的等待時間，從而降低了總成本.但當邊緣服務(wù)器數(shù)量不斷增加時，總成本降低幅度變得很小且趨于平穩(wěn)，這是因為當邊緣服務(wù)器增加到一定數(shù)量時，在固定任務(wù)數(shù)下，系統(tǒng)資源變得充足且可以滿足所有任務(wù).本文方法考慮從最長路徑卸載任務(wù)，可以減少任務(wù)在邊緣服務(wù)器的等待時間；此外，考慮待卸載任務(wù)的前驅(qū)任務(wù)卸載決策和邊緣服務(wù)器間的最佳傳輸功率.因此，與其他3 種方法相比，本文方法總成本最小.從圖5可以看出，邊緣服務(wù)器數(shù)量小于10 時，4 種方法的總成本降低速度較快；當邊緣服務(wù)器數(shù)量大于10 時，4種方法的總成本降低速度放緩.因此，服務(wù)器數(shù)量較佳設(shè)置應(yīng)為10.

Fig.5 Effect of the number of edge servers on the total costs圖5 邊緣服務(wù)器數(shù)量對總成本的影響

4.4.3 PSO 迭代次數(shù)的影響

對應(yīng)用程序包含的任務(wù)數(shù)量取不同的值，并設(shè)定DAG 邊數(shù)是任務(wù)數(shù)量的2 倍，采用不同的迭代次數(shù)分別進行實驗，實驗結(jié)果如圖6 所示.隨著迭代次數(shù)的增加，不同任務(wù)數(shù)量下的應(yīng)用程序總成本均呈下降趨勢.而當?shù)螖?shù)大于20 時，總成本下降的趨勢很小.繼續(xù)迭代可能會求得更優(yōu)的傳輸功率，但對總成本的影響很小.而多余的迭代次數(shù)會增加算法的運行時間.因此，為了盡可能降低總成本，在接下來的實驗中，設(shè)置PSO 的迭代次數(shù)為20.

Fig.6 Effect of PSO iteration numbers on total costs圖6 PSO 迭代次數(shù)對總成本的影響

4.5 實驗對比

本節(jié)通過改變應(yīng)用程序中任務(wù)數(shù)量、應(yīng)用程序大小和任務(wù)間依賴關(guān)系，并設(shè)定邊緣服務(wù)器數(shù)量為10， ω分別取值為0.2 和0.8，PSO 迭代次數(shù)為20.采用本文方法與3 種對比方法進行實驗對比.

4.5.1 任務(wù)數(shù)量對總成本的影響

對應(yīng)用程序包含的任務(wù)數(shù)量取值，并設(shè)定DAG的邊的數(shù)量是任務(wù)數(shù)量的2 倍，分別采用4 種方法進行實驗，實驗結(jié)果如圖7 所示.隨著任務(wù)數(shù)量的增加，4 種方法的總成本隨之增加，且CaGTS 增加得最多.究其原因為CaGTS 總將任務(wù)卸載到執(zhí)行時間最小的邊緣服務(wù)器，不考慮前驅(qū)任務(wù)的卸載位置，導(dǎo)致產(chǎn)生大量傳輸能耗，從而增加總成本.ITAGS 和CaGTS 在任務(wù)數(shù)量較少時，總成本很接近，但隨著任務(wù)數(shù)量增加，ITAGS 的總成本小于CaGTS，主要因為ITAGS 每次貪婪卸載任務(wù)時，會兼顧前驅(qū)任務(wù)的卸載位置，從而減少了邊緣服務(wù)器間的通信成本.CP 和ITAGS 相比，在任務(wù)數(shù)量較少的時候，兩者的總成本很接近，但隨著任務(wù)數(shù)量的逐漸增大，CP 明顯優(yōu)于ITAGS，究其原因是CP 優(yōu)先卸載執(zhí)行時間長且距離結(jié)束任務(wù)遠的任務(wù)，因此進一步降低了總成本.本文方法不僅先卸載距離結(jié)束任務(wù)遠的任務(wù)，還兼顧前驅(qū)任務(wù)的卸載位置.此外，本文方法在進行依賴性任務(wù)的數(shù)據(jù)傳輸時，采用最佳的傳輸功率降低了總成本.因此，此類實驗本文方法結(jié)果最佳.

Fig.7 Effect of task quantity on total costs圖7 任務(wù)數(shù)量對總成本的影響

4.5.2 應(yīng)用程序大小對總成本的影響

設(shè)定應(yīng)用程序包含的任務(wù)數(shù)量為100，任務(wù)大小隨機生成，執(zhí)行時間根據(jù)谷歌數(shù)據(jù)集中任務(wù)大小和執(zhí)行時間的比值求得，DAG 邊數(shù)為200，采用4 種方法分別進行實驗，實驗結(jié)果如圖8 所示.因為本文實驗中應(yīng)用程序任務(wù)數(shù)量固定不變，所以隨著應(yīng)用程序大小的增加，任務(wù)的平均大小也會增加，邊緣服務(wù)器處理任務(wù)的時延和能耗會隨之變大，且邊緣服務(wù)器處理任務(wù)所需的資源也在增加.因此，4 種方法的總成本也隨之增加.

Fig.8 Effect of App sizes on total costs圖8 應(yīng)用程序大小對總成本的影響

由于CaGTS 和ITAGS 都不考慮任務(wù)卸載的優(yōu)先級，導(dǎo)致距離結(jié)束任務(wù)較遠的任務(wù)可能后執(zhí)行，會產(chǎn)生較長的等待時間.與CaGTS 和ITAGS 不同，CP 考慮了前驅(qū)任務(wù)的卸載位置，且優(yōu)先卸載距離結(jié)束任務(wù)遠的任務(wù)，這將大大降低任務(wù)在邊緣服務(wù)器的等待時間.但由于CP 的傳輸功率是固定的，當任務(wù)大小增加時，任務(wù)間傳輸數(shù)據(jù)的成本就會增加，進而增加總成本.本文方法和CP 相比，在應(yīng)用程序較小時，總成本非常相近.因為這2 種方法的邊緣服務(wù)器處理任務(wù)的時間相同.CP 是根據(jù)任務(wù)的執(zhí)行時間對傳輸時間進行調(diào)整，因此在應(yīng)用程序較小時，傳輸時間也相對較小.但隨著應(yīng)用程序增大，邊緣服務(wù)器執(zhí)行任務(wù)的時間也增大，因此CP 的傳輸時間也會增大，從而對總成本影響較大.本文方法無論在應(yīng)用程序多大時，均能求得邊緣服務(wù)器的最佳傳輸功率，從而降低總成本.

4.5.3 任務(wù)依賴關(guān)系對總成本的影響

設(shè)定應(yīng)用程序的任務(wù)數(shù)量為300，依賴關(guān)系，也就是DAG 邊數(shù)從100 遞增至1 000，實驗結(jié)果如圖9所示.DAG 邊數(shù)越多，任務(wù)間依賴關(guān)系越復(fù)雜，致使邊緣服務(wù)器間的傳輸次數(shù)的增加，從而導(dǎo)致這4 種方法總成本增加.當DAG 邊較少時，4 種方法的總成本都很相近.這是因為任務(wù)之間依賴較少時，邊緣服務(wù)器間的傳輸次數(shù)也較少，此時本文方法通過獲取最佳傳輸功率從而降低總成本的優(yōu)勢不明顯.此外，本文方法為得到最佳傳輸功率，還需額外增加計算時延，從而導(dǎo)致在 ω =0.2（用戶更偏好時延），邊數(shù)為100～200 時，本文方法性能略差于對比方法.然而，隨著DAG 邊數(shù)的增加，邊緣服務(wù)器間的通信成本隨之增大，此時本文方法明顯優(yōu)于其他3 種方法.

Fig.9 Effect of task dependency relationship on total costs圖9 任務(wù)的依賴關(guān)系對總成本的影響

相比于ITAGS 和CaGTS，本文方法優(yōu)先卸載到結(jié)束任務(wù)路徑最長的任務(wù)，可以減少任務(wù)在邊緣服務(wù)器的等待時延；并且卸載任務(wù)時考慮到當前任務(wù)的前驅(qū)任務(wù)，通信成本也會降低.本文方法和CP 的總成本總體上接近，特別是在DAG 邊數(shù)在100～500之間，這是因為這2 種方法都優(yōu)先卸載最長路徑上的任務(wù)且考慮前驅(qū)任務(wù)的卸載決策，但隨著邊數(shù)不斷的增多，本文方法明顯優(yōu)于CP.這是因為任務(wù)之間的依賴關(guān)系變得越來越復(fù)雜，且任務(wù)的前驅(qū)任務(wù)也變多了，邊緣服務(wù)器之間傳輸數(shù)據(jù)的次數(shù)也變得頻繁，由于本文方法考慮邊緣服務(wù)器間傳輸數(shù)據(jù)時的最佳傳輸功率，可以獲得最小的傳輸時延和能耗，從而降低總成本.因此，本文方法取得的實驗結(jié)果最佳.由此可知，本文方法更適合應(yīng)用依賴任務(wù)較多的情形.

5 總結(jié)與展望

本文研究了在邊緣服務(wù)器計算資源和服務(wù)緩存有限的約束下，權(quán)衡時延和能耗的依賴性任務(wù)卸載問題，并提出了DTO-TE 方法.DTO-TE 通過松弛研究問題的約束將其轉(zhuǎn)換成凸優(yōu)化問題，并求得松弛解；根據(jù)松弛解求得滿足約束的可行解，從而確定任務(wù)的卸載優(yōu)先級；按照優(yōu)先級依次將任務(wù)卸載到成本最小的邊緣服務(wù)器上.實驗結(jié)果充分表明，本文方法在本文設(shè)置的各類實驗中均獲得了最優(yōu)的結(jié)果.

雖然本文方法較對比方法有一定的優(yōu)勢，但是仍存在一些不足：1）本文方法只進行了基于真實數(shù)據(jù)的仿真實驗，因?qū)嶒炘O(shè)備的限制并沒有在真實場景下進行實驗驗證；2）本文方法只建立了邊—端卸載模型，只適合較小規(guī)模應(yīng)用程序，對于大規(guī)模應(yīng)用程序，可以考慮建立云—邊—端協(xié)同卸載模型；3）本文方法只研究1 個應(yīng)用程序卸載，實際應(yīng)用中存在協(xié)同卸載多個應(yīng)用程序的場景.因此，下一步工作擬研究云—邊—端模型中的多個應(yīng)用程序的協(xié)同卸載，并在真實場景下對研究問題進行實驗驗證.

作者貢獻聲明：張俊娜提出論文思路，并全程指導(dǎo)實驗設(shè)計、結(jié)果分析和論文撰寫；鮑想負責實驗的實現(xiàn)和論文的撰寫；陳家偉和趙曉焱參與實驗設(shè)計和論文撰寫；袁培燕和王尚廣修改論文.