【笔记】雾计算中移动应用的优先级约束任务调度
目錄
前置
摘要
介紹
模型
應(yīng)用模型
計算和通信模型
能耗模型
問題定義
NP難
預(yù)功率分配算法
能量約束調(diào)度
算法1：具有啟發(fā)式H的能量約束列表調(diào)度（ECLS-H）
時間約束調(diào)度
算法2：具有啟發(fā)式H的時間約束列表調(diào)度（TCLS-H）
后功率分配算法
能量約束調(diào)度
算法3：具有啟發(fā)式H的能量約束逐級調(diào)度（ECLL-H）
時間約束調(diào)度
算法4：具有啟發(fā)式H的時間約束逐層調(diào)度（TCLL-H）
前置
什么是霧計算【來自百度】
霧計算是一種對云計算概念的延伸，它主要使用的是邊緣網(wǎng)絡(luò)中的設(shè)備，數(shù)據(jù)傳遞具有極低時延。霧計算具有遼闊的地理分布，帶有大量網(wǎng)絡(luò)節(jié)點的大規(guī)模傳感器網(wǎng)絡(luò)。霧計算移動性好，手機和其他移動設(shè)備可以互相之間直接通信，信號不必到云端甚至基站去繞一圈，支持很高的移動性和更多的邊緣節(jié)點。
| 云計算 | 霧計算 |
| 以IT運營商服務(wù)，社會公有云為主的 | 以量制勝，強調(diào)數(shù)量，不管單個計算節(jié)點能力多么弱都要發(fā)揮作用 |
| 強調(diào)整體計算能力，一般由一堆集中的高性能計算設(shè)備完成計算 | 將網(wǎng)絡(luò)計算從網(wǎng)絡(luò)中心擴展到了網(wǎng)絡(luò)邊緣，從而更加廣泛地應(yīng)用于各種服務(wù) |
| 幾乎全部保存在云中 | 將數(shù)據(jù)、數(shù)據(jù)處理和應(yīng)用程序集中在網(wǎng)絡(luò)邊緣的設(shè)備中，數(shù)據(jù)的存儲及處理更依賴本地設(shè)備，而非服務(wù)器 |
摘要
霧計算環(huán)境面臨優(yōu)先級約束、功率分配和性能成本權(quán)衡的多重挑戰(zhàn)。我們應(yīng)對這三個挑戰(zhàn)的策略描述如下。首先，在功率分配前算法和后功率分配算法中，優(yōu)先級約束分別由經(jīng)典列表調(diào)度算法和逐級調(diào)度方法處理。其次，在功率分配前算法（后功率分配算法）中，在確定計算卸載策略之前（后）確定功率分配策略。第三，通過定義能量約束調(diào)度問題和時間約束調(diào)度問題來處理性能-成本權(quán)衡。
我們開發(fā)了一類基于經(jīng)典列表調(diào)度算法和等能量方法的預(yù)功率分配算法，用于能量約束和時間約束調(diào)度。我們開發(fā)了一類用于能量約束和時間限制調(diào)度的后功率分配算法，這些算法基于逐級調(diào)度方法和我們先前提出的獨立任務(wù)算法。我們通過對隨機生成的有向無環(huán)圖的移動應(yīng)用進行廣泛實驗，對所提出的算法進行了評估，并確定了最有效和最高效的啟發(fā)式算法。目前沒有相關(guān)的研究。
介紹
在用戶設(shè)備（user equipment, UE）上生成的移動應(yīng)用程序可以分解為具有優(yōu)先級約束的多個任務(wù)，這些任務(wù)可以任意復(fù)雜。此外，這些任務(wù)可能具有非常不同的計算和通信要求。這種復(fù)雜的移動應(yīng)用超出了移動設(shè)備用于及時處理的計算能力。
在移動邊緣云（mobile edge cloud, MEC）中的服務(wù)器的幫助下，可以將移動應(yīng)用程序的任務(wù)卸載到MEC服務(wù)器。計算卸載(Computation offloading)提供了增強UE的計算能力并延長UE的電池壽命的有效手段。通過MEC， UE可以在更短的時間內(nèi)完成應(yīng)用，而代價是額外的通信時間。UE可以節(jié)省用于計算的能量消耗，延長電池使用時間，而代價是用于通信的額外能量。
具有優(yōu)先約束任務(wù)的移動應(yīng)用的計算卸載成為在霧計算環(huán)境中調(diào)度移動應(yīng)用的優(yōu)先約束任務(wù)。霧計算引入了一些與傳統(tǒng)節(jié)能任務(wù)調(diào)度系統(tǒng)截然不同的新的獨特功能，并且霧計算環(huán)境是一個復(fù)雜且難以管理的計算平臺。首先，UE不將其所有任務(wù)卸載到MEC。第二，UE不能改變和控制MEC的計算速度，而只能改變和控制其自身的計算速度和與MEC的通信速度。第三，在處理能量延遲權(quán)衡時，僅考慮UE中計算和通信的能量消耗（MECs中的能量消耗不考慮在內(nèi)）。第四，霧計算表現(xiàn)出強烈的異構(gòu)性。
在異構(gòu)霧計算環(huán)境中調(diào)度移動應(yīng)用程序的優(yōu)先級受限任務(wù)存在多個挑戰(zhàn)。首先，需要確定計算卸載策略，以滿足任務(wù)之間的所有優(yōu)先約束。其次，需要確定功率分配策略，對于每個任務(wù)，該策略給出本地執(zhí)行的計算速度或遠程執(zhí)行的通信速度。第三，在定義優(yōu)化問題時，應(yīng)考慮性能（即總執(zhí)行時間）和成本（即總能耗）。
模型
應(yīng)用模型
假設(shè)UE具有移動應(yīng)用A = (L, ?)。存在任務(wù)列表。每個任務(wù)被指定為，其中是的計算需求（計算量），是的通信要求（UE和MEC之間要通信的數(shù)據(jù)量）。
任務(wù)之間存在優(yōu)先級約束，這些約束由偏序?指定。如果，則是的前身，并且任務(wù)在任務(wù)完成之前不能開始其執(zhí)行。
具有優(yōu)先約束任務(wù)的移動應(yīng)用程序可以用有向無環(huán)圖（dag）G來描述。G中的頂點是L中的m個任務(wù)。G中弧的給定方式是，當(dāng)且僅當(dāng)時，存在從到的弧。
計算和通信模型
假設(shè)存在n個異構(gòu)MEC，即。每個具有計算速度（處理器執(zhí)行速度，不能被UE改變）。
每個任務(wù)可以在UE或MEC上執(zhí)行，任務(wù)執(zhí)行時間包括計算時間和通信時間。
①如果沒有卸載并在UE上以計算速度(可由UE決定)本地執(zhí)行，則UE上的計算時間為。沒有用于本地執(zhí)行的通信時間。
在UE上本地執(zhí)行的的執(zhí)行時間為.
?②如果被卸載到并在上遠程執(zhí)行，則上的計算時間為。UE與之間的的通信速度為（數(shù)據(jù)傳輸速率，可由UE決定）。對于，UE和之間的通信時間（以秒為單位）為。
在上遠程執(zhí)行的的執(zhí)行時間為
能耗模型
UE的功耗P中有兩個分量用于計算，即動態(tài)功耗和靜態(tài)功耗。
動態(tài)分量，其中ξ和α是由該技術(shù)確定的一些常數(shù)。
靜態(tài)分量通常是常數(shù)
因此，我們得到。
若未卸載并在計算速度為的UE上本地執(zhí)行，則功耗為，并且UE上的計算能耗為。
注意，UE除了消耗用于計算的功率之外，還消耗用于通信的功率。
設(shè)為任務(wù)的UE到的傳輸功率，， 其中，是信道帶寬，是各種因素的組合量，如背景噪聲功率、其他設(shè)備對同一MEC的數(shù)據(jù)傳輸對通信信道造成的干擾以及UE和之間的信道增益。
從UE到的ti通信能耗為
注意，對于UE上的本地執(zhí)行，僅考慮計算能耗，而對于MEC上的遠程執(zhí)行，只考慮通信能耗。移動應(yīng)用程序的總能耗為，這是移動應(yīng)用程序主要的成本度量。
問題定義
移動應(yīng)用程序A的計算卸載策略（也稱為調(diào)度）是為每個任務(wù)決定何時（執(zhí)行的開始時間）和何處（執(zhí)行的位置，UE或MEC），合法的計劃必須確保所有任務(wù)遵循優(yōu)先約束。
若，則有（前一個任務(wù)的開始時間+執(zhí)行時間 ≤ 下一個任務(wù)的開始時間）。功率分配策略是為每個任務(wù)ti決定如何執(zhí)行ti，我們使用T表示完成L中所有任務(wù)的總執(zhí)行時間（即完成時間），這是移動應(yīng)用程序的主要性能度量。
給定移動應(yīng)用A＝(L,?) 其中，在具有n個MEC的霧計算環(huán)境中（具有計算速度和能量約束）：
能量約束調(diào)度問題是為UE和MEC上的L中的所有任務(wù)找到計算卸載策略和功率分配策略，使得E不超過，并且最小化T。?
時間約束調(diào)度問題是為UE和MEC上的L中的所有任務(wù)找到計算卸載策略和功率分配策略，使得T不超過，并且最小化E。
NP難
證明過程暫且忽略
定理1 即使對于獨立任務(wù)和只有一個MEC，能量約束調(diào)度問題也是NP困難的。
定理2?即使對于獨立任務(wù)和只有一個MEC，時間約束調(diào)度問題也是NP困難的。
預(yù)功率分配算法
能量約束調(diào)度
預(yù)功率分配有幾種方法。在等速方法中，所有任務(wù)具有相同的計算速度。這在霧計算中是不可能的，因為UE不能改變MEC的計算速度。在等時間方法中，所有任務(wù)的執(zhí)行時間相同。這在霧計算中也是不可能的，因為UE只能控制通信時間。
在本文中，我們采用了等能量方法，其中所有任務(wù)消耗相同的能量，即。
其優(yōu)點在于，當(dāng)在UE或MEC上調(diào)度任務(wù)時，可以立即確定其計算或通信速度。
①如果沒有以計算速度卸載并在UE上本地執(zhí)行，則有:
?當(dāng)α = 2時，有
(即)?。因此，等式（18）可以通過使用標(biāo)準(zhǔn)二分法進行數(shù)值求解，在區(qū)間之前搜索最佳.
后續(xù)推理如下述（20）~（22）式所示：【公式（20）暫時沒理解如何推出來】
②如果被卸載到并在上遠程執(zhí)行，則有：
根據(jù)泰勒級數(shù)（25）我們可推出不等式（26），再根據(jù)公式（24）替換即可得出不等式（27），如下所示：
?
則可以由下述式子表示：
?因此，等式（24）可以通過使用標(biāo)準(zhǔn)二分法進行數(shù)值求解，在區(qū)間之前搜索最佳，滿足公式（29）（30）.
算法1：具有啟發(fā)式H的能量約束列表調(diào)度（ECLS-H）
算法1中介紹了我們的具有預(yù)功率分配的能量約束調(diào)度算法，稱為具有啟發(fā)式H的能量約束列表調(diào)度（ECLS-H）（H參見第5.1節(jié)）。
輸入：A=（L，?)， 其中，，， 和。
輸出：計算卸載策略和功率分配策略，以使E不超過，并使T最小化。
我們將定義為索引j，使得；
我們將定義為索引j，使得
該算法本質(zhì)上是適用于霧計算環(huán)境的經(jīng)典列表調(diào)度算法[3]。通過預(yù)功率分配，當(dāng)任務(wù)計劃執(zhí)行時，任務(wù)的執(zhí)行時間可用。
第1行 ?用啟發(fā)式H初始化列表L；
第2行 ?變量T動態(tài)地記錄當(dāng)前時間作為時間表的移動；
第3-9行 ?for循環(huán)在時間0（第（5）行）調(diào)度第一批就緒任務(wù)（第（3）行）。
? 第6行 ?設(shè)表示當(dāng)前在上運行的任務(wù)的剩余執(zhí)行時間， 為了方便，我們將UE設(shè)置為。
第10-25行 ?while循環(huán)調(diào)度剩余任務(wù)。在每次重復(fù)中，執(zhí)行以下操作。
? 第11行 ?首先，識別最早完成其當(dāng)前任務(wù)的MECj。
? 第12行 ?其次，時鐘移動到完成當(dāng)前任務(wù)的時刻。
? 第13-17行 ?第三，每個繁忙MEC的剩余執(zhí)行時間(14)由第13-17行中的for循環(huán)更新(15)。
? 第18-24行 ?第四，下一批就緒任務(wù)(18)由第18-24行中的for循環(huán)在時間T(20)調(diào)度。如果j=0，則(第6和21行)的執(zhí)行時間為，其中通過求解等式（18）找到；如果j>0，則，其中通過等式（24）找到。該算法告訴何時何地(第5和20行)以及如何（第6和21行）執(zhí)行
當(dāng)?shù)仁?#xff08;18）或等式（24）由于能量分配不足而無法求解時，UE或被認為不可用并被跳過。
算法1的總體時間復(fù)雜度為
時間約束調(diào)度
算法2：具有啟發(fā)式H的時間約束列表調(diào)度（TCLS-H）
算法2中提出了一種具有預(yù)功率分配的時間約束調(diào)度算法，稱為具有啟發(fā)式H的時間約束列表調(diào)度（TCLS-H）。
輸入：A=（L，?)， 其中，，?，和。
輸出：計算卸載策略和功率分配策略，以使T不超過，E最小化
當(dāng)在時間約束調(diào)度中調(diào)度任務(wù)以保證時間約束時，很難確定計算或通信速度。我們的戰(zhàn)略是采用兩個階段的過程。
在第一階段（第1-5行），我們發(fā)現(xiàn)使得通過ECLS-H算法獲得的T（第3行）不長于（第5行）。這可以通過將設(shè)置為某個合理值（第1行）并逐漸增加（第4行）直到。
在第二階段（第6-13行），每個任務(wù)（第7行）的執(zhí)行時間按因子（第6行）縮放，通過如下降低計算或通信速度。
如果在UE上（第8行）調(diào)度任務(wù)，則被改變?yōu)?#xff0c;使得，使得（第9行）。
如果在（第10行）上調(diào)度任務(wù)，則將更改為，使得，從而得到（第11行）。注意，這種執(zhí)行時間縮放不影響任務(wù)之間的優(yōu)先級約束和執(zhí)行任務(wù)的位置，只影響任務(wù)執(zhí)行的開始時間。
在計算和通信速度降低之后，任務(wù)不再消耗相同量的能量。然而，這根本不是問題，因為我們最初的目的是產(chǎn)生計算卸載策略和功率分配策略，以滿足時間約束。如果在第一階段調(diào)用ECLS-H算法K次，則算法2的總體時間復(fù)雜度為，K值取決于E的初始值和增量?E。
后功率分配算法
能量約束調(diào)度
有向無環(huán)圖可以分解為v個級別，其中級別定義如下。
1級由初始任務(wù)組成，即沒有前導(dǎo)任務(wù)的任務(wù)。如果從某個初始任務(wù)到任務(wù)的最長路徑上的節(jié)點數(shù)為，則l級包含任務(wù)；
?設(shè)表示級別中的一組任務(wù)， 因此，我們有。
我們采用逐級調(diào)度方法，即L中的任務(wù)是逐級調(diào)度的。這意味著只有當(dāng)所有在中的任務(wù)都完成后，中的任務(wù)才可以開始執(zhí)行。每個級別的進度表都是單獨、獨立和分別生成的。整個移動應(yīng)用程序的調(diào)度只是的v個調(diào)度的級聯(lián)。
算法3：具有啟發(fā)式H的能量約束逐級調(diào)度（ECLL-H）
由于同一級別中的所有任務(wù)彼此獨立，我們可以通過使用任何啟發(fā)式能量約束調(diào)度算法H對獨立任務(wù)進行調(diào)度。所有這些算法都具有獨特的特征，即，在確定計算卸載策略之后確定功率分配策略。算法3中提出了一種具有后功率分配的能量約束調(diào)度算法，稱為具有啟發(fā)式H的能量約束逐級調(diào)度（ECLL-H）。
逐級能量約束調(diào)度的關(guān)鍵問題是確定如何將給定能量預(yù)算E~分配給v級。
輸入：A =（L, ?)， 其中，，， 和。
輸出：計算卸載策略和功率分配策略，以使E不超過，并使T最小化
設(shè)為算法H應(yīng)用于具有能量約束的時的總執(zhí)行時間。
第1-3行 ?最初，通過使用具有一些初始能量分配El的算法H來調(diào)度每個級別Ll。
第4-5行 ?然后，剩余能量（第4行）除以K得到（第5行）；
第6-16行 ?while循環(huán)重復(fù)了略多于K次。在每次重復(fù)中，執(zhí)行以下操作：
第一，確定?E，它是一個隨機數(shù)γ乘以E'，其中γ均勻分布在[0.5,1.0]（第10行）。
第二，在以下情況下，選擇導(dǎo)致其總執(zhí)行時間減少最多,提供額外能量?E(即)的級（第12行）。
第三，分配級額外能量?E（第13行）。在分配了所有剩余能量之后，while循環(huán)終止（第6行）。
移動應(yīng)用程序的總執(zhí)行時間T為（第17行）。
Ll的初始能量約束El確定如下。定義，根據(jù)下式，我們可以將設(shè)置為
【注】對于同一級別的獨立任務(wù)，我們的啟發(fā)式能量約束調(diào)度算法H將相同的計算速度分配給在UE上本地執(zhí)行的所有任務(wù)，并將相同的通信速度分配給上遠程執(zhí)行的所有工作。然而，來自不同級別的任務(wù)具有不同的計算速度，即使它們都在UE上本地執(zhí)行，而來自不同級別任務(wù)具有不同通信速度，即使他們都在同一MEC上遠程執(zhí)行.
算法3的時間復(fù)雜度為
時間約束調(diào)度
算法4：具有啟發(fā)式H的時間約束逐層調(diào)度（TCLL-H）
算法4中提出了我們的具有后功率分配的時間約束調(diào)度算法，稱為具有啟發(fā)式H的時間約束逐層調(diào)度（TCLL-H）。
輸入：A=（L，?)， 其中，，?，和。
輸出：計算卸載策略和功率分配策略，以使T不超過，E最小化
逐級時間約束調(diào)度中的關(guān)鍵問題是確定如何將給定的時間預(yù)算T分配給v級。
設(shè)為算法H應(yīng)用于具有時間約束的時的總能耗。
第1-3行 ?最初，通過使用算法H和一些初始時間分配Tl來調(diào)度每個級別Ll。
第4-5行 ?然后，附加時間（第4行）除以K得到（第5行）；
第6-16行 ?while循環(huán)重復(fù)略多于K次。在每次重復(fù)中，執(zhí)行以下操作：
第一，確定?T，它是一個隨機數(shù)γ乘以，其中γ均勻分布在[0.5,1.0]（第10行）
第二，選擇導(dǎo)致其總能耗增量最小，時間量?T減少(即)的級（第12行）
第三，級的執(zhí)行時間減少了?T（第13行）。
while循環(huán)在所有附加時間減少后終止（第6行）。移動應(yīng)用程序的總能耗E為（第17行）。
的初始時間約束確定如下:
?
算法4的總時間復(fù)雜度為
總結(jié)
以上是生活随笔為你收集整理的【笔记】雾计算中移动应用的优先级约束任务调度的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 【PHM】PHM算法与智能分析技术——数
- 下一篇： bat倒计时