基于霧計算的能耗最小化公平計算遷移研究

葛欣煒，段聰穎，陳思光,2

(1.南京郵電大學 江蘇省寬帶無線通信和物聯(lián)網(wǎng)重點實驗室，江蘇 南京 210003；

2.南京郵電大學 江蘇省通信與網(wǎng)絡(luò)技術(shù)工程研究中心，江蘇 南京 210003)

1 概 述

物聯(lián)網(wǎng)(Internet of Things，IoT)和人工智能(Artificial Intelligence，AI)是實現(xiàn)智慧城市的兩大基礎(chǔ)技術(shù)[1]。隨著智慧城市概念的提出，爆發(fā)式增長的智能物聯(lián)網(wǎng)設(shè)備產(chǎn)生了巨大的數(shù)據(jù)和計算工作量[2]。尤其是，當智能物聯(lián)網(wǎng)設(shè)備在運用深度學習之類的AI算法進行大數(shù)據(jù)分析時，有可能造成過高的延遲。移動云計算(Mobile Cloud Computing，MCC)通過將計算任務(wù)遷移到遠程云數(shù)據(jù)中心來進行計算，以滿足智能IoT移動網(wǎng)絡(luò)中的計算需求[3]，是一種有效的計算模式。但是，由于一般這些遠程數(shù)據(jù)中心距離智能IoT移動設(shè)備較遠，并且它們與遠程云數(shù)據(jù)中心之間的通信主要依賴于骨干網(wǎng)，因此數(shù)據(jù)中心很難為網(wǎng)絡(luò)邊緣的智能設(shè)備中的延遲敏感型應用提供高質(zhì)量服務(wù)[4]。

移動邊緣計算(Mobile Edge Computing，MEC)是解決上述問題的新興計算模式[5]，通過在智能IoT設(shè)備附近部署邊緣云服務(wù)器來降低計算延遲。霧計算是MEC模式的一個分支，它將計算任務(wù)遷移到附近的霧節(jié)點(Fog Node，F(xiàn)N)，進一步減少傳輸延遲并降低智能IoT設(shè)備的能耗。這是因為與MCC相比，霧節(jié)點更靠近網(wǎng)絡(luò)邊緣，可以提高智能設(shè)備和霧節(jié)點之間的響應速度[6]。但與MEC不同，霧節(jié)點分布相對密集，難以與有利于遷移的智能設(shè)備區(qū)分開來[7]，且霧節(jié)點尺寸更小，資源更少，電池容量更低，這就使得對霧節(jié)點的相關(guān)資源進行合理分配以及對網(wǎng)絡(luò)整體性能的優(yōu)化變得尤為重要。

文獻[8-13]通過聯(lián)合優(yōu)化網(wǎng)絡(luò)資源分配與遷移決策，實現(xiàn)延遲與能耗的最小化，改善了整個霧計算網(wǎng)絡(luò)的性能。文獻[13]構(gòu)建了含能耗與時間延遲約束的霧節(jié)點能耗最小化模型，基于對偶分解的加速梯度算法，快速求出最優(yōu)遷移比，達到最小化霧節(jié)點能耗的目的，同時，極大地改善了傳統(tǒng)求解方法的收斂速度，降低了計算任務(wù)延遲。文獻[14]構(gòu)建了一個系統(tǒng)能效最大化問題，通過聯(lián)合優(yōu)化計算頻率、發(fā)射功率以及遷移時間，采用廣義分式規(guī)劃理論提出一種迭代算法進行求解，從而獲得更高的系統(tǒng)計算能效。

文獻[15-17]構(gòu)建了從用戶到FN的計算遷移模型，以降低能耗并減少延遲。文獻[15]構(gòu)建了一個混合整數(shù)非線性規(guī)劃問題，提出了一種低復雜度三階算法，通過平衡終端設(shè)備與霧節(jié)點的工作負載，實現(xiàn)了計算和傳輸延遲的最小化。Hu等人在文獻[16]中提出了一種基于霧計算的人臉識別機制，可以提高處理效率，有效地識別個人身份，同時減少網(wǎng)絡(luò)傳輸?shù)难舆t。文獻[17]提出了一種針對霧計算網(wǎng)絡(luò)中的所有FN、數(shù)據(jù)服務(wù)運營商和用戶的聯(lián)合優(yōu)化機制，以實現(xiàn)最優(yōu)的分布式資源分配。雖然上述文獻所做工作在一定程度上降低了能量消耗并減少了延遲，但其優(yōu)化結(jié)果并不是太理想。尤其是，霧計算網(wǎng)絡(luò)具有大量的霧節(jié)點，其中一些霧節(jié)點處于空閑狀態(tài)，而另一些霧節(jié)點幾乎一直處于滿負荷工作的狀態(tài)。因此，F(xiàn)N之間的協(xié)作在霧計算網(wǎng)絡(luò)中起著重要的作用。

文獻[18]提出了一種眾籌算法來整合網(wǎng)絡(luò)中閑置資源的機制，并對資源提供者進行監(jiān)督，有效提高了任務(wù)完成效率。文獻[19]進一步擴展了上述工作，提出了更有效的激勵措施來鼓勵設(shè)備資源共享。文獻[20]構(gòu)建了一種與傳統(tǒng)霧模型不同的霧計算模型，提出的基于博弈論的資源共享機制，提高了計算效率，但其并未考慮霧節(jié)點本身資源的有限性。文獻[21]在多用戶邊緣計算場景下，考慮了云邊資源的協(xié)同優(yōu)化，提出一種基于次模理論的貪心算法，在用戶資源受限的情況下仍能夠穩(wěn)定有效的降低系統(tǒng)能耗與時延。文獻[22]將協(xié)同霧計算與資源分配優(yōu)化問題結(jié)合，提出了一種基于變量拆分的交替方向乘子法的分布式計算遷移優(yōu)化算法，以實現(xiàn)給定功率下的最優(yōu)遷移機制。文獻[23]構(gòu)建了一個任務(wù)完成時延與能耗加權(quán)和的最小化問題，提出了一個基于深度強化學習的遷移算法，以較低的計算成本實現(xiàn)最優(yōu)遷移策略的快速求解。

從上述分析可以發(fā)現(xiàn)，現(xiàn)有文獻大都未考慮計算遷移過程中霧節(jié)點選擇的公平性，而是側(cè)重于最大程度地減少處理延遲與能耗，這可能會給終端節(jié)點(Terminal Node，TN)或FN帶來極大的計算負擔，導致FN過早失效。這是因為，部分霧節(jié)點可能具有強大處理能力和充足電源，而其他的則可能是電源有限甚至是電池供電的節(jié)點，顯然，電池壽命對于這些FN至關(guān)重要。考慮到FN的不同處理效率和可持續(xù)性，在追求低能耗任務(wù)遷移的同時，可以通過在FN之間公平地進行計算任務(wù)遷移，從而防止FN由于任務(wù)過載而過早失效。

針對上述挑戰(zhàn)，面向霧計算網(wǎng)絡(luò)，該文提出一種能耗最小化公平計算遷移機制，主要貢獻如下：

·在霧計算網(wǎng)絡(luò)場景下，構(gòu)建了一個最小化所有任務(wù)完成總能耗的優(yōu)化問題，通過對任務(wù)遷移比、傳輸功率和霧節(jié)點選擇的聯(lián)合優(yōu)化，在一定延遲約束條件下，實現(xiàn)總能耗的最小化。

·基于上述優(yōu)化問題，提出一個任務(wù)遷移候選目的節(jié)點集生成算法，該算法通過二分法，以較低的復雜度獲得各個霧節(jié)點在相應延遲約束下的最低能耗及其對應的遷移比和傳輸功率，生成任務(wù)遷移候選目的節(jié)點集。進一步，為了在低能耗與目的節(jié)點選擇的公平性之間取得平衡，基于公平調(diào)度指標，提出一個目的節(jié)點公平選擇算法，以公平、節(jié)能的方式實現(xiàn)計算任務(wù)分配，防止霧節(jié)點過早失效。

·仿真結(jié)果表明，該機制可以在低能耗的情況下保證各霧節(jié)點之間的公平性，較最大等效處理速率機制，平均霧節(jié)點存活率提升了10.9%。

2 系統(tǒng)模型

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

構(gòu)建的計算任務(wù)遷移模型如圖1所示，考慮一個由1個終端節(jié)點TN和N個霧節(jié)點FN組成的霧簇，該霧簇中的終端節(jié)點可以是手機、電腦等智能設(shè)備，N個霧節(jié)點(路由設(shè)備、運營商提供的各種服務(wù)器等)隨機分布在終端節(jié)點周圍。該霧簇中的霧節(jié)點分為主動霧節(jié)點和被動霧節(jié)點，主動霧節(jié)點由電網(wǎng)供電，對能量消耗不太敏感，而被動霧節(jié)點由電池供電，電池壽命有限，對能耗敏感。

圖1 計算任務(wù)遷移模型

當終端生成計算任務(wù)時，可以在終端設(shè)備本地進行處理，也可以分為多個子任務(wù)，將一部分或全部任務(wù)遷移到霧節(jié)點，再將結(jié)果發(fā)送回終端節(jié)點。

2.2 計算模型

定義處理1 bit數(shù)據(jù)所需的CPU周期為c，霧節(jié)點i的CPU頻率fi和終端節(jié)點的CPU頻率floc。一旦在TN上生成了具有延遲約束Tmax的計算任務(wù)，除了在本地處理任務(wù)之外，TN會根據(jù)已知的FN信息和任務(wù)的約束條件，要求控制器為此任務(wù)的遷移服務(wù)分配一個選定的目的節(jié)點FNi。然后，根據(jù)遷移比ai將任務(wù)分為兩個子任務(wù)，分別在本地和FNi上處理。最后，結(jié)果從FNi返回TN。

(1)計算延遲。

根據(jù)上述遷移過程，任務(wù)延遲包括三個部分，即計算任務(wù)遷移到霧節(jié)點i的傳輸延遲ttra，霧節(jié)點i的計算延遲ti，以及終端節(jié)點本地的計算延遲tloc。

子任務(wù)遷移到霧節(jié)點i的傳輸延遲可以表示為：

(1)

其中，w是總需要處理的任務(wù)大小，Ri是終端節(jié)點到霧節(jié)點i的數(shù)據(jù)傳輸速率，可以用香農(nóng)公式表示為：

(2)

其中，B是上行鏈路帶寬，Pi是終端到霧節(jié)點i的數(shù)據(jù)傳輸速率，G是上行鏈路的無線信道增益，n是上行鏈路的噪聲功率譜密度。

霧節(jié)點i的計算延遲可以表示為：

(3)

在終端節(jié)點本地計算的延遲可以表示為：

(4)

終端節(jié)點只有在接收到所有子任務(wù)的處理結(jié)果后才能做出下一步?jīng)Q策，因此，總?cè)蝿?wù)延遲定義為所有子任務(wù)延遲的最大值，即總延遲表示為：

T=max[(ttra+ti),tloc]

(5)

(2)能量消耗。

根據(jù)前面所描述的計算任務(wù)遷移到霧節(jié)點i的子任務(wù)的傳輸延遲ttra，終端節(jié)點的傳輸能耗表示為：

(6)

霧節(jié)點i的能耗可以表示為：

(7)

本地處理的能耗可以表示為：

(8)

其中，κ表示有效電容系數(shù)。

一般地，霧節(jié)點處理完成后的數(shù)據(jù)大小遠小于源數(shù)據(jù)，所以結(jié)果返回給終端節(jié)點的傳輸能耗可以忽略不計。因此，整個模型處理任務(wù)的總能耗為：

E=etra+ei+eloc

(9)

3 優(yōu)化問題描述

任務(wù)延遲和能耗由任務(wù)遷移比ai和傳輸功率Pi決定。在滿足延遲約束的條件下，恰當?shù)胤峙鋋i和Pi，進而使總能耗最小，從而將優(yōu)化問題表述為：

(10)

s.t. C1 0≤ai≤1

C2 0≤Pi≤Pmax

C3T≤Tmax

C1是任務(wù)遷移比約束，ai=0表示終端生成的任務(wù)將全部在本地計算，ai=1表示任務(wù)將全部遷移到霧節(jié)點i上進行計算。C2是傳輸功率約束，確保終端設(shè)備到霧節(jié)點i的傳輸功率不超過Pmax。C3是延遲約束，確保總?cè)蝿?wù)延遲不超過Tmax。

4 聯(lián)合任務(wù)遷移比、傳輸功率與目的節(jié)點選擇的公平計算遷移算法

4.1 任務(wù)遷移候選目的節(jié)點集生成算法

由于P1是非凸優(yōu)化問題，所以將其轉(zhuǎn)換成關(guān)于終端傳輸功率Pi的單變量問題。通過二分法，以較低的復雜度獲得各個霧節(jié)點在相應延遲約束下的最低能耗及其對應的遷移比和傳輸功率，生成任務(wù)遷移候選目的節(jié)點集。

首先，在滿足T≤Tmax的條件下，總能耗E最小時，遷移總時延滿足ttra+ti=Tmax，即：

(11)

則有：

(12)

為了保證優(yōu)化問題P1可解，必須滿足tloc≤Tmax的條件，結(jié)合公式(12)，可知當且僅當滿足以下兩個條件時，總?cè)蝿?wù)時延T可以小于上界Tmax，即：

(13)

(14)

其中，

(15)

由于P1的非凸性，原問題P1轉(zhuǎn)化為：

(16)

其中，

(17)

現(xiàn)在，針對ai和Pi的優(yōu)化問題P1被轉(zhuǎn)換為針對TN傳輸功率Pi的能量最小化問題P2。

通過對傳輸功率Pi求二階導數(shù)可知，總能耗E隨傳輸功率Pi單調(diào)遞增，則最優(yōu)的傳輸功率Pi*將直接由Pi定義域中的最小值給出，那么，在問題P2的取值范圍中，若滿足如下條件:

(18)

總能耗E是關(guān)于傳輸功率Pi的嚴格單調(diào)遞增函數(shù)。因此，Pi最優(yōu)值等于Pi取值范圍內(nèi)的最小值，即:

(19)

對于系統(tǒng)參數(shù)不滿足上述條件的情況,當Pi∈[0,+∞)時，若滿足如下條件：

(20)

(21)

所以,

(22)

算法1：任務(wù)遷移候選目的節(jié)點集生成算法。

1.輸入：任務(wù)大小w，霧節(jié)點i的CPU頻率fi

3.BEGIN

5.for eachi

9.else

10.if 條件 (18) 滿足,then

12.else

14. end if

17. end if

18.end for

20.END

4.2 目的節(jié)點公平性選擇

各個霧節(jié)點FN之間的能耗均衡對于霧計算網(wǎng)絡(luò)的可持續(xù)性和穩(wěn)定性至關(guān)重要。在這一部分，基于上述任務(wù)遷移候選目的節(jié)點集生成算法，提出一種目的節(jié)點的公平性選擇算法。因此，在延遲約束下，總能耗和計算任務(wù)公平分配之間實現(xiàn)了平衡。

首先，為每個霧節(jié)點定義公平調(diào)度指標，如下:

(23)

歷史平均功耗更新如下：

(24)

其中，μ是遺忘因子，0<μ<1。

引入Jain’s公平指數(shù)：

(25)

其中,Jain’s公平指數(shù)F在1/N到1之間，F(xiàn)越大，表示計算任務(wù)遷移機制的公平性越高。

基于算法1得到的候選目的節(jié)點集和公平性調(diào)度指標，提出如下算法2。

算法2：目的節(jié)點公平選擇算法。

2.輸出：最優(yōu)目的節(jié)點i*

3.BEGIN

5.i*is null；

6.else

7.for eachi∈do

8. 基于公式(23)，計算公平調(diào)度指標Mi；

9.end for

10. 選擇公平性指數(shù)最高的霧節(jié)點進行遷移，

11.returni*

12.end if

13.END

5 仿真結(jié)果

在本節(jié)中，將進行仿真以驗證提出的能耗最小化公平遷移算法的性能。在多種網(wǎng)絡(luò)場景下，對最小化的遷移能耗、遷移服務(wù)的可行性以及霧節(jié)點選擇的公平性進行了驗證分析。

在本仿真環(huán)境中，設(shè)定每個霧節(jié)點的帶寬B=10 Mb/s，上行鏈路的噪聲功率譜密度n=-100 dBm/Hz，總的霧節(jié)點個數(shù)為10個，任務(wù)總數(shù)為20個，終端節(jié)點的計算速率floc=2 Mbps。

圖2是總能耗與霧節(jié)點的任務(wù)處理速率關(guān)系圖。可以看出，隨著fi的增加，霧節(jié)點的處理速率上升，霧節(jié)點處理的能效比本地處理的能效高，通過將計算任務(wù)遷移到霧節(jié)點進行處理，減少了總能量消耗。隨著FNi的CPU頻率的進一步提高，該任務(wù)將完全遷移到FNi上進行處理，這導致恒定的總能耗。因此，當fi足夠大時，總能量消耗趨于收斂。從圖中還可以看出，當生成的計算任務(wù)量越大，進行計算遷移需要任務(wù)處理速率越快。

圖2 總能耗與霧節(jié)點的任務(wù)處理速率關(guān)系圖

圖3是不同霧節(jié)點分布半徑下三種任務(wù)遷移機制的Jain’s公平性指標圖。可以看出，隨著霧節(jié)點分布半徑增大，最大等效處理速率機制和完全相等任務(wù)遷移機制的公平性指標均大幅下降，遠低于該文所提機制的公平性指標。這是因為半徑越大霧節(jié)點分布越稀疏，選擇遠程霧節(jié)點進行任務(wù)遷移的概率越小。該文提出的公平遷移機制在霧節(jié)點半徑變化時始終保持較高的公平性指數(shù)，這是由于它在所有備選霧節(jié)點之間采取公平的遷移策略。

圖3 霧節(jié)點分布半徑與Jain’s指數(shù)關(guān)系圖

圖4是任務(wù)遷移概率與最大傳輸功率的關(guān)系圖。可以看出，隨著終端發(fā)射功率上限的增大，任務(wù)遷移的概率從0增加到1，并且增加的幅度近似線性。圖5是任務(wù)遷移概率與最大容忍延遲的關(guān)系圖。可以看出，隨著延遲上限的增加，計算任務(wù)遷移概率從0增加到1。當最大容忍延遲為2 s時，4 MB大小的任務(wù)可以全部在本地處理以滿足延遲上限，因此該情況下任務(wù)遷移概率始終為0。結(jié)果表明，更嚴格的延遲和傳輸功率約束導致能夠為TN提供可行的任務(wù)遷移服務(wù)的FN減少。

圖4 任務(wù)遷移概率與最大傳輸功率關(guān)系圖

圖5 任務(wù)遷移概率與最大容忍延遲關(guān)系圖

圖6 霧節(jié)點存活率與生成任務(wù)數(shù)關(guān)系圖

圖6是霧節(jié)點存活率與生成任務(wù)數(shù)的關(guān)系圖，可以看出，隨著生成任務(wù)數(shù)的不斷增加，三種機制的霧節(jié)點存活率都呈下降趨勢，這是因為隨著任務(wù)數(shù)的不斷增加，能量有限的霧節(jié)點能量不斷消耗殆盡，最終當能量耗盡時霧節(jié)點也就隨之死亡。而該文的公平遷移機制霧節(jié)點的存活率始終更高，比完全相等任務(wù)遷移機制和最大等效處理速率機制的平均霧節(jié)點存活率分別高31.9%和10.9%。這是因為該文考慮了霧節(jié)點之間遷移的公平性，終端節(jié)點始終傾向于將任務(wù)遷移給剩余能量較高且歷史平均能耗較低的霧節(jié)點，保證了霧節(jié)點之間的公平性，從而保證了霧節(jié)點不會過早耗盡能量而失效。

6 結(jié)束語

該文提出了一個基于霧計算的能耗最小化公平計算遷移機制，通過聯(lián)合優(yōu)化遷移比、傳輸功率和霧節(jié)點選擇達到公平且低能耗的計算遷移。提出任務(wù)遷移候選目的節(jié)點集生成算法, 通過二分法獲得霧節(jié)點在相應延遲約束下的最低能耗及其對應的遷移比和傳輸功率；基于公平調(diào)度指標，通過目的節(jié)點公平選擇算法，以低能耗且公平的方式進行計算任務(wù)分配，實現(xiàn)低能耗與目的節(jié)點選擇公平性之間的平衡。仿真結(jié)果表明，該機制可以在總能耗較低的情況下保證各個霧節(jié)點之間的公平性。