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

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

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

2.南京郵電大學 江蘇省通信與網絡技術工程研究中心，江蘇 南京 210003)

1 概 述

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

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

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

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

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

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

針對上述挑戰，面向霧計算網絡，該文提出一種能耗最小化公平計算遷移機制，主要貢獻如下：

·在霧計算網絡場景下，構建了一個最小化所有任務完成總能耗的優化問題，通過對任務遷移比、傳輸功率和霧節點選擇的聯合優化，在一定延遲約束條件下，實現總能耗的最小化。

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

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

2 系統模型

2.1 網絡模型

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

圖1 計算任務遷移模型

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

2.2 計算模型

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

(1)計算延遲。

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

子任務遷移到霧節點i的傳輸延遲可以表示為：

(1)

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

(2)

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

霧節點i的計算延遲可以表示為：

(3)

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

(4)

終端節點只有在接收到所有子任務的處理結果后才能做出下一步決策，因此，總任務延遲定義為所有子任務延遲的最大值，即總延遲表示為：

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

(5)

(2)能量消耗。

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

(6)

霧節點i的能耗可以表示為：

(7)

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

(8)

其中，κ表示有效電容系數。

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

E=etra+ei+eloc

(9)

3 優化問題描述

任務延遲和能耗由任務遷移比ai和傳輸功率Pi決定。在滿足延遲約束的條件下，恰當地分配ai和Pi，進而使總能耗最小，從而將優化問題表述為：

(10)

s.t. C1 0≤ai≤1

C2 0≤Pi≤Pmax

C3T≤Tmax

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

4 聯合任務遷移比、傳輸功率與目的節點選擇的公平計算遷移算法

4.1 任務遷移候選目的節點集生成算法

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

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

(11)

則有：

(12)

為了保證優化問題P1可解，必須滿足tloc≤Tmax的條件，結合公式(12)，可知當且僅當滿足以下兩個條件時，總任務時延T可以小于上界Tmax，即：

(13)

(14)

其中，

(15)

由于P1的非凸性，原問題P1轉化為：

(16)

其中，

(17)

現在，針對ai和Pi的優化問題P1被轉換為針對TN傳輸功率Pi的能量最小化問題P2。

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

(18)

總能耗E是關于傳輸功率Pi的嚴格單調遞增函數。因此，Pi最優值等于Pi取值范圍內的最小值，即:

(19)

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

(20)

(21)

所以,

(22)

算法1：任務遷移候選目的節點集生成算法。

1.輸入：任務大小w，霧節點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 目的節點公平性選擇

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

首先，為每個霧節點定義公平調度指標，如下:

(23)

歷史平均功耗更新如下：

(24)

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

引入Jain’s公平指數：

(25)

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

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

算法2：目的節點公平選擇算法。

2.輸出：最優目的節點i*

3.BEGIN

5.i*is null；

6.else

7.for eachi∈do

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

9.end for

10. 選擇公平性指數最高的霧節點進行遷移，

11.returni*

12.end if

13.END

5 仿真結果

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

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

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

圖2 總能耗與霧節點的任務處理速率關系圖

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

圖3 霧節點分布半徑與Jain’s指數關系圖

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

圖4 任務遷移概率與最大傳輸功率關系圖

圖5 任務遷移概率與最大容忍延遲關系圖

圖6 霧節點存活率與生成任務數關系圖

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

6 結束語

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