基于能效和時延的多層次計算卸載方法研究

摘 要：計算卸載是移動邊緣計算技術（MEC）的核心技術之一。為保證任務在最大可容忍時延的前提下使能量消耗最小化，采用三級物聯網-霧-云系統架構提出考慮多用戶多邊緣節點場景的計算卸載方法。通過多級卸載對計算卸載概率和發射功率分配進行聯合優化。利用逐次凸逼近（SCA）和Dinkelbach方法，交替確定每個用戶的卸載決策和發射功率，將非凸優化問題轉化為一系列凸問題，從而得到原問題的近似最優解。通過仿真分析，模擬結果展示了不同參數如發射功率、計算卸載概率對計算卸載性能指標的影響，驗證了所提出算法的收斂性。

關鍵詞：移動邊緣計算技術；能量消耗；時延；多級卸載；聯合優化；卸載概率

中圖分類號：TP393 文獻標識碼：A 文章編號：2095-1302（2024）06-00-05

0 引 言

隨著互聯網的普及和移動智能終端的不斷發展和應用，導致計算和存儲資源有限的智能移動設備（SMD）不足以作為主要的操作平臺。本地執行應用程序不能很好地滿足用戶需求，將會導致應用程序的高能耗和高時延[1-2]。為了克服這些限制，針對以上問題，通信行業內提出了計算卸載技術，借助云服務器豐富的計算資源[3]，將計算任務放在遠程云服務器上處理，這種做法已經成為一種有效的數據處理方式。

為降低計算任務的處理時延與移動設備能耗，提出了一種應用于多用戶多邊緣節點場景的基于三層物聯網-霧-云系統架構的計算卸載方案。對系統的卸載策略和傳輸功率分配進行聯合優化，以保證在最大容忍延遲的前提下盡可能降低物聯網系統的時延和能耗[4-6]。由于霧節點計算資源受限，開發了分布式霧節點協作算法，以實現霧層的負載分擔，減少任務排隊的等待時間。建立計算卸載概率和發射功率的聯合優化算法[7-9]。由于聯合優化問題具有非凸性和NP復雜性，利用逐次凸逼近框架設計了迭代算法，通過模擬仿真分析以證明所提出的計算卸載方案的性能和收斂性[10]。

1 多層次計算卸載的架構建模

文中提出了一個考慮霧節點協作的應用于多用戶多邊緣節點場景的物聯網-霧-云系統通用模型。圖1所示為系統架構。霧層被定義為調節數據傳輸和處理負載的中間層，霧層由多個AP接入點組成。這種與數據源的短距離顯著降低了物聯網設備的數據傳輸功耗，并實現了快速響應。包含計算和存儲設備的最高層是云層，在云端，基于物聯網系統的主要處理單元是云服務器[11-12]。

本文中使用較多的基本符號見表1所列。

1.1 本地處理

令fil表示IDi的本地計算能力（單位為CPU周期/s），Ci表示完成任務ψi所需的CPU周期數，由此推導出：Ci=θi·γi。因此，在IDi上本地執行任務ψi的處理時延為：

（1）

令vi作為表示每個CPU周期消耗能量的系數，由此可知vi=α·（fil）2，α取決于處理器的結構。可以通過下式求得任務本地處理的能量消耗為：

（2）

假設IDi以Pioff的概率進行任務卸載，其中0≤Pioff≤1，以概率（1-Pioff）在本地處理任務。計算卸載決策向量表示為Poff={Pioff}，i∈n。

1.2 霧處理

（1）霧處理

假設物聯網層有n個ID，整個集合記為n={1， 2， ...， N}，霧層由M個霧節點組成，記為m={1， 2， ...， M}。IDi表示第i個請求的任務，定義為ψi=（θi， γi， τimax），i∈n。由于ID可以將其任務卸載到附近的霧節點。位于位置li的IDi可能被多個AP覆蓋。假設ID使用正交頻分多址（OFDMA）與AP進行通信，可用的AP帶寬為B Hz，由使用OFDMA的ID共享。任務從IDi傳輸APj的上行數據速率為ri， j。titransmit I→F為將任務從IDi傳輸到霧節點j所需的時間。將數據傳輸到霧節點j所需的能量消耗：

（3）

假設霧節點j，j∈m的服務時間服從指數分布，平均服務時間等于1/μjF，μjF是霧節點j的計算能力。假設任務到達霧節點j的到達率服從泊松過程，平均到達率為是一個二進制變量，表示IDi是否將其任務卸載到霧節點j，若是，則χlj=1，反之χlj=0。θlγl表示完成任務ψl所需的CPU周期。將霧節點建模為M/M/1隊列，在霧節點j接受任務ψi的情況下，任務ψi的平均響應時間為：

（4）

霧節點j接受計算任務ψi的概率如下：

Pi， japprove=P（霧節點j的預計等待時間lt;最大容忍延遲）

=P（Wjlt;τimax）" " " " " " " " " " " " " " " " " " " " " " " " " " " " " " （5）

式中：Wj是j隊列中存在的所有任務的處理時間總和。使用等待時間Wj的累積分布函數（CDF）來求解等式（5）。假設隊列中有n個任務，用zrj表示霧節點j中第r個任務的處理延遲，這里可以定義。由于zrj服從服務時間為μjF的指數分布，n個獨立指數（μ）分布隨機變量之和為γ（n， μ）隨機變量，得到概率密度函數如下：

（6）

另一方面，根據運籌學隊列理論知識，處于狀態n的概率可以推導出為式（7），其中ρj=λjf/μjF，λjf是到達霧節點j的任務到達率。

（7）

（2）霧節點協作方案

為了滿足任務的延遲要求，降低霧節點中任務的排隊延遲，引入了霧節點協作方案，用于霧節點通信以相互交換信息。根據這些信息，就可以確定最合適的相鄰霧節點。任務ψi在霧層停留的總時間可以計為：

（8）

式中：k是霧節點j的最佳鄰域霧節點，rff代表兩個霧節點之間的傳輸速率。每當IDi將其任務卸載到霧節點層時，它將進入空閑狀態，直到結果返回。在IDi空閑狀態下，設Pidle表示其功耗，tifog表示其時間，則空閑狀態下IDi的能耗為：

（9）

1.3 云處理

IDi請求的任務以概率（1-Pi， japprove）（1-Pifp）傳輸到云服務器。設titransmitF→C表示任務ψi從霧節點傳輸到云服務器所需要的時間，其中rFC表示霧節點j到中心云服務器之間的傳輸速率。文中選擇M/M/∞隊列來模擬中央云服務器中的任務處理。假設服務速率為μC，沒有等待時間，任務到達云服務器立即被處理，在云服務器中處理任務ψi所需的時間可以表示如下：

（10）

IDi在云服務器處理任務時的能耗見式（11）：

（11）

ψi的延遲如下：

（12）

得到ψi的總能耗如下：

（13）

文中使用Min-Max歸一化法將延遲和能耗縮放到[0，1]。可以定義計算卸載在時延和能效方面的開銷為：

（14）

式中：ηit，ηie∈[0， 1]，i∈n分別表示IDi任務的時延和能耗的加權系數。本文設置ηit+ηie=1。這里可以針對不同的任務調整ηit，ηie，替換等式中的Ti和Ei。

ID的平均計算卸載開銷為：

（15）

該函數為成本函數，最終目標是將成本函數降到最低。

2 基于能效和時延的計算卸載優化方法

2.1 問題闡述

文中提出了一種基于霧的物聯網網絡延遲感知和節能方案，通過最小化時延以及能耗來最小化網絡中所有ID的平均計算卸載開銷。卸載策略和發射功率分配的聯合優化問題描述如下：

目標函數：

P0：min Cost（Poff， Ptrans）{Poff， Ptrans}" " " " " " " "（16）

約束條件：

0≤Pioff≤1，i∈n，" " " " " " " " " " " " " "（17）

0≤Pitrans≤Pimax，i∈n，" " " " " " " " " " " （18）

τi≤τimax，i∈n，" " " " " " " " " " " " nbsp; " （19）

（20）

約束條件（17）表示IDi以Pioff的概率卸載其任務。約束條件（18）表示IDi的發射功率不能超過給定的最大發射功率。約束條件（19）保證完成時間不會超過任務的最大可容忍延遲。約束條件（20）保持霧節點隊列的穩定性，使得到達率應該小于霧節點中的服務率[13]。

公式（16）中的問題是非線性的。此外，由于速率函數（公式（3））以及優化變量的乘法，它是非凸和NP復雜的，具有很高的計算復雜度。因此，求解最佳解決方案非常困難。在這種情況下，文中采用逐次凸逼近的方法來解決問題，將非凸優化問題轉化為一系列凸子問題，從而得到原問題的近似最優解。在本文中，采用SCA方法來設計一種迭代算法，分兩步交替確定每個用戶的卸載決策和發射功率，可以有效求出問題（16）的最優解[14]。

2.2 迭代算法

文中采用迭代算法來確定每個用戶的卸載決策和傳輸功率。

（1） 初始化

為求解優化問題（16），應該先通過算法找到滿足約束條件（19）和約束條件（20）的初始可行點。由于沒有任何約束，這里可以設置Ptrans=[Pimax]，i∈n，增大發射功率，以盡可能減少延遲。為了確定初始計算卸載概率向量，必須先解決以下線性優化問題。

目標函數：

（21）

由于問題（21）是線性的，因此是凸函數，該問題求得的最優解off*當作初始計算卸載向量（Poff0=off*）。

（2）計算卸載決策問題

由于已經給定了初始的發射功率向量Ptranst，因此唯一的優化變量是Poff，聯合優化問題（16）的描述變為：

目標函數：

min Cost（Poff， Ptranst）{Poff}" " " " " " " " " " " " （22）

約束條件為式（17），式（19）和式（20）。

在第t次迭代中求得的卸載概率最優解用Pofft表示，用于下一步迭代求解。

（3）發射功率分配問題

對于一個給定的計算卸載概率向量，Si1和Si2是關于Pitrans的常量，因此，發射功率分配問題可以轉化為目標函數：

（23）

約束條件為式（18）～式（20）。

為了解決非線性分式規劃問題（23），文中使用Dinkelbach方法將非凸問題轉換為等效的凸減法形式，將問題（23）轉換為如下的等價優化問題。

目標函數：

（24）

約束條件為式（18）～式（20）。

基于Dinkelbach的發射功率分配算法如下所示。

輸入：{Pioff}，i∈n，無線網絡的帶寬為B，物聯網設備和霧節點間的信道增益為g，背景噪聲功率為No，。

輸出：，。

初始化：l=0，設置初始值ε3，lmax；

do

{

使用內點法求解得到：

目標函數（24）為凸函數。因此，通過內點法等傳統凸優化算法可以很快得到其最優解。

3 仿真分析

3.1 參數設置

文中模擬的環境是1 km×1 km含三層分層物聯網系統，其中包含500個物聯網設備，25個接入點AP。物聯網設備ID可以通過150 m的半徑與接入點AP連接。設置云服務器的CPU頻率固定是8 GHz。IDi和霧節點j之間的無線信道增益定義為gi， j=χdi， j-β，χ表示一個服從瑞利分布的隨機變量。

3.2 仿真結果

（1）發射功率對計算卸載性能指標的影響

發射功率對不同卸載概率值下所有ID的平均處理延遲及能耗影響如圖2所示。處理延遲會隨著發射功率的增加而減小。增加卸載概率會使處理時延增大，由于增大卸載概率導致更多的任務被卸載到霧層或云服務器。因此，所有任務的平均處理延遲將增加。隨著卸載任務數量的增加，需要更多的能量，幾條不同卸載概率的曲線幾乎相交于同一個點，對于低于該點（大約1.7 W）的最大發射功率值，在較低卸載概率下的能量消耗較高。相反，對于大于該指定點的最大發射功率值，較高卸載概率的能量消耗變得更大[15]。

（2）計算卸載概率對計算卸載性能指標的影響

圖3為卸載概率對處理延遲及能耗的影響，隨著計算卸載概率的增加，平均處理時延也呈上升趨勢。另外，通過增加卸載概率，在較低發射功率下的平均處理延遲比在較高發射功率下的平均處理延遲增加得更多。同時隨著卸載概率的增加，平均能源消耗減少。可以發現，在發射功率相同的情況下，隨著計算卸載概率的增加，平均處理延遲增加而平均能耗降低。

（3）霧節點數量對計算卸載性能指標的影響

圖4為霧節點數量對平均處理延遲的影響。將所有物聯網設備ID的計算卸載概率設置為0.2、0.4和0.8。在霧節點數量固定的情況下，平均處理延遲會隨著卸載概率的增加而增加。從圖中還可以看出，當霧節點達到一定數量時，進一步增加其數量對降低延遲效果不明顯。通過增加霧節點的數量來提供足夠的計算資源，減少了任務的等待時間和執行延遲，但是對傳輸延遲沒有影響，這意味著傳輸延遲不變，使得處理延遲最終趨于穩定。

多次運行結果如圖5所示，平均有49%的任務在本地處理，31%在霧層處理，剩下的20%在中央云服務器中完成。

圖6描述了所提出算法在具有不同霧節點數的所有ID任務的平均卸載開銷方面的收斂行為。可見，每次迭代后卸載開銷都會減少。此外，可以看出，霧節點數量越多，收斂時間越短。對于所有考慮的霧節點數量，所提算法在少于30次迭代后收斂。

4 結 語

文中提出了由多用戶和多霧服務器組成的物聯網-霧-云系統架構，將計算卸載問題轉化為發射功率和計算卸載決策目標的聯合優化，以最小化延遲約束下的物聯網設備的能耗。由于霧服務器的計算資源有限，開發了分布式算法，以減少霧節點之間的負載分擔和任務等待時間。由于公式化的問題是非凸的，提出了一種基于SCA技術的兩步迭代算法，利用Dinkelbach算法來逼近一個接近最優的解決方案。最后通過仿真結果驗證了所提算法的有效性和收斂性。

參考文獻

[1] RAY P P. A survey on Internet of Things architectures [J]. Journal of king saud university-computer and information sciences，2018，30（3）：291-319.

[2] CHIANG M，ZHANG T. Fog and IoT：An overview of research opportunities [J]. IEEE internet of things journal，2016，3（6）：854-864.

[3]孟憲令. 移動邊緣網絡中的低時延計算卸載技術[D]. 杭州：浙江大學，2020.

[4]葛東玉. ad hoc 云環境下任務卸載策略研究[D]. 重慶：重慶郵電大學，2019.

[5] CHEN M H，LIANG B，DONG M. Multi-user multi-task offloading and resource allocation in mobile cloud systems [J]. IEEE transactions on wireless communications，2018，17（10）：6790-6805.

[6] CHEN X，ZHOU Y，YANG L，et al. Hybrid fog/cloud computing resource allocation：Joint consideration of limited communication resources and user credibility [J]. Computer communications，2021，169：48-58.

[7]田賢忠，姚超，趙晨，等. 一種面向 5G 網絡的移動邊緣計算卸載策略[J]. 計算機科學，2020，47（11A）：286-290.

[8] ALAM M G R，HASSAN M M，UDDIN M Z I，et al. Autonomic computation offloading in mobile edge for IoT applications [J]. Future generation computer systems，2019，90：149-157.

[9] LI S，XU L D，ZHAO S. The internet of things：a survey [J]. Information systems frontiers，2015，17（2）：243-259.

[10] ASGHARI P，RAHMANI A M，JAVADI H H S. Internet of things applications：A systematic review [J]. Computer networks，2019，148：241-261.

[11]張海波，欒秋季，朱江，等. 車輛異構網中基于移動邊緣計算的任務卸載與資源分配[J]. 物聯網學報，2018，2（3）：36-43.

[12]董思岐，李海龍，屈毓錛，等. 移動邊緣計算中的計算卸載策略研究綜述[J]. 計算機科學，2019，46（11）：32-40.

[13]李振江，張幸林. 減少核心網擁塞的邊緣計算資源分配和卸載決策[J]. 計算機科學，2021，48（3）：281-288.

[14] LI L，GUAN Q，JIN L，et al. Resource allocation and task offloading for heterogeneous real-time tasks with uncertain duration time in a fog queueing system [J]. IEEE access，2019，7：9912-9925.

[15]高寒，李學俊，周博文，等. 移動邊緣計算環境中基于能耗優化的深度神經網絡計算任務卸載策略[J]. 計算機集成制造系統，2020，26（6）：1607-1615.

基金項目：國家自然科學基金（62137001）；國家自然科學基金（U1811261）

作者簡介：楊一桐（1990—），女，遼寧沈陽人，碩士，實驗師，主要研究方向為智能控制、無線網絡、實驗室管理等。

吳菁晶（1981—），女，副教授，主要研究方向為通信網、網絡生存性和可靠性等。