基于能效和時(shí)延的多層次計(jì)算卸載方法研究

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

關(guān)鍵詞：移動(dòng)邊緣計(jì)算技術(shù)；能量消耗；時(shí)延；多級(jí)卸載；聯(lián)合優(yōu)化；卸載概率

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2095-1302（2024）06-00-05

0 引 言

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

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

1 多層次計(jì)算卸載的架構(gòu)建模

文中提出了一個(gè)考慮霧節(jié)點(diǎn)協(xié)作的應(yīng)用于多用戶多邊緣節(jié)點(diǎn)場景的物聯(lián)網(wǎng)-霧-云系統(tǒng)通用模型。圖1所示為系統(tǒng)架構(gòu)。霧層被定義為調(diào)節(jié)數(shù)據(jù)傳輸和處理負(fù)載的中間層，霧層由多個(gè)AP接入點(diǎn)組成。這種與數(shù)據(jù)源的短距離顯著降低了物聯(lián)網(wǎng)設(shè)備的數(shù)據(jù)傳輸功耗，并實(shí)現(xiàn)了快速響應(yīng)。包含計(jì)算和存儲(chǔ)設(shè)備的最高層是云層，在云端，基于物聯(lián)網(wǎng)系統(tǒng)的主要處理單元是云服務(wù)器[11-12]。

本文中使用較多的基本符號(hào)見表1所列。

1.1 本地處理

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

（1）

令vi作為表示每個(gè)CPU周期消耗能量的系數(shù)，由此可知vi=α·（fil）2，α取決于處理器的結(jié)構(gòu)?？梢酝ㄟ^下式求得任務(wù)本地處理的能量消耗為：

（2）

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

1.2 霧處理

（1）霧處理

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

（3）

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

（4）

霧節(jié)點(diǎn)j接受計(jì)算任務(wù)ψi的概率如下：

Pi， japprove=P（霧節(jié)點(diǎn)j的預(yù)計(jì)等待時(shí)間lt;最大容忍延遲）

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

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

（6）

另一方面，根據(jù)運(yùn)籌學(xué)隊(duì)列理論知識(shí)，處于狀態(tài)n的概率可以推導(dǎo)出為式（7），其中ρj=λjf/μjF，λjf是到達(dá)霧節(jié)點(diǎn)j的任務(wù)到達(dá)率。

（7）

（2）霧節(jié)點(diǎn)協(xié)作方案

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

（8）

式中：k是霧節(jié)點(diǎn)j的最佳鄰域霧節(jié)點(diǎn)，rff代表兩個(gè)霧節(jié)點(diǎn)之間的傳輸速率。每當(dāng)IDi將其任務(wù)卸載到霧節(jié)點(diǎn)層時(shí)，它將進(jìn)入空閑狀態(tài)，直到結(jié)果返回。在IDi空閑狀態(tài)下，設(shè)Pidle表示其功耗，tifog表示其時(shí)間，則空閑狀態(tài)下IDi的能耗為：

（9）

1.3 云處理

IDi請(qǐng)求的任務(wù)以概率（1-Pi， japprove）（1-Pifp）傳輸?shù)皆品?wù)器。設(shè)titransmitF→C表示任務(wù)ψi從霧節(jié)點(diǎn)傳輸?shù)皆品?wù)器所需要的時(shí)間，其中rFC表示霧節(jié)點(diǎn)j到中心云服務(wù)器之間的傳輸速率。文中選擇M/M/∞隊(duì)列來模擬中央云服務(wù)器中的任務(wù)處理。假設(shè)服務(wù)速率為μC，沒有等待時(shí)間，任務(wù)到達(dá)云服務(wù)器立即被處理，在云服務(wù)器中處理任務(wù)ψi所需的時(shí)間可以表示如下：

（10）

IDi在云服務(wù)器處理任務(wù)時(shí)的能耗見式（11）：

（11）

ψi的延遲如下：

（12）

得到ψi的總能耗如下：

（13）

文中使用Min-Max歸一化法將延遲和能耗縮放到[0，1]?？梢远x計(jì)算卸載在時(shí)延和能效方面的開銷為：

（14）

式中：ηit，ηie∈[0， 1]，i∈n分別表示IDi任務(wù)的時(shí)延和能耗的加權(quán)系數(shù)。本文設(shè)置ηit+ηie=1。這里可以針對(duì)不同的任務(wù)調(diào)整ηit，ηie，替換等式中的Ti和Ei。

ID的平均計(jì)算卸載開銷為：

（15）

該函數(shù)為成本函數(shù)，最終目標(biāo)是將成本函數(shù)降到最低。

2 基于能效和時(shí)延的計(jì)算卸載優(yōu)化方法

2.1 問題闡述

文中提出了一種基于霧的物聯(lián)網(wǎng)網(wǎng)絡(luò)延遲感知和節(jié)能方案，通過最小化時(shí)延以及能耗來最小化網(wǎng)絡(luò)中所有ID的平均計(jì)算卸載開銷。卸載策略和發(fā)射功率分配的聯(lián)合優(yōu)化問題描述如下：

目標(biāo)函數(shù)：

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的概率卸載其任務(wù)。約束條件（18）表示IDi的發(fā)射功率不能超過給定的最大發(fā)射功率。約束條件（19）保證完成時(shí)間不會(huì)超過任務(wù)的最大可容忍延遲。約束條件（20）保持霧節(jié)點(diǎn)隊(duì)列的穩(wěn)定性，使得到達(dá)率應(yīng)該小于霧節(jié)點(diǎn)中的服務(wù)率[13]。

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

2.2 迭代算法

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

（1） 初始化

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

目標(biāo)函數(shù)：

（21）

由于問題（21）是線性的，因此是凸函數(shù)，該問題求得的最優(yōu)解off*當(dāng)作初始計(jì)算卸載向量（Poff0=off*）。

（2）計(jì)算卸載決策問題

由于已經(jīng)給定了初始的發(fā)射功率向量Ptranst，因此唯一的優(yōu)化變量是Poff，聯(lián)合優(yōu)化問題（16）的描述變?yōu)椋?/p>

目標(biāo)函數(shù)：

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

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

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

（3）發(fā)射功率分配問題

對(duì)于一個(gè)給定的計(jì)算卸載概率向量，Si1和Si2是關(guān)于Pitrans的常量，因此，發(fā)射功率分配問題可以轉(zhuǎn)化為目標(biāo)函數(shù)：

（23）

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

為了解決非線性分式規(guī)劃問題（23），文中使用Dinkelbach方法將非凸問題轉(zhuǎn)換為等效的凸減法形式，將問題（23）轉(zhuǎn)換為如下的等價(jià)優(yōu)化問題。

目標(biāo)函數(shù)：

（24）

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

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

輸入：{Pioff}，i∈n，無線網(wǎng)絡(luò)的帶寬為B，物聯(lián)網(wǎng)設(shè)備和霧節(jié)點(diǎn)間的信道增益為g，背景噪聲功率為No，。

輸出：，。

初始化：l=0，設(shè)置初始值ε3，lmax；

do

{

使用內(nèi)點(diǎn)法求解得到：

目標(biāo)函數(shù)（24）為凸函數(shù)。因此，通過內(nèi)點(diǎn)法等傳統(tǒng)凸優(yōu)化算法可以很快得到其最優(yōu)解。

3 仿真分析

3.1 參數(shù)設(shè)置

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

3.2 仿真結(jié)果

（1）發(fā)射功率對(duì)計(jì)算卸載性能指標(biāo)的影響

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

（2）計(jì)算卸載概率對(duì)計(jì)算卸載性能指標(biāo)的影響

圖3為卸載概率對(duì)處理延遲及能耗的影響，隨著計(jì)算卸載概率的增加，平均處理時(shí)延也呈上升趨勢。另外，通過增加卸載概率，在較低發(fā)射功率下的平均處理延遲比在較高發(fā)射功率下的平均處理延遲增加得更多。同時(shí)隨著卸載概率的增加，平均能源消耗減少?？梢园l(fā)現(xiàn)，在發(fā)射功率相同的情況下，隨著計(jì)算卸載概率的增加，平均處理延遲增加而平均能耗降低。

（3）霧節(jié)點(diǎn)數(shù)量對(duì)計(jì)算卸載性能指標(biāo)的影響

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

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

圖6描述了所提出算法在具有不同霧節(jié)點(diǎn)數(shù)的所有ID任務(wù)的平均卸載開銷方面的收斂行為?？梢姡看蔚笮遁d開銷都會(huì)減少。此外，可以看出，霧節(jié)點(diǎn)數(shù)量越多，收斂時(shí)間越短。對(duì)于所有考慮的霧節(jié)點(diǎn)數(shù)量，所提算法在少于30次迭代后收斂。

4 結(jié) 語

文中提出了由多用戶和多霧服務(wù)器組成的物聯(lián)網(wǎng)-霧-云系統(tǒng)架構(gòu)，將計(jì)算卸載問題轉(zhuǎn)化為發(fā)射功率和計(jì)算卸載決策目標(biāo)的聯(lián)合優(yōu)化，以最小化延遲約束下的物聯(lián)網(wǎng)設(shè)備的能耗。由于霧服務(wù)器的計(jì)算資源有限，開發(fā)了分布式算法，以減少霧節(jié)點(diǎn)之間的負(fù)載分擔(dān)和任務(wù)等待時(shí)間。由于公式化的問題是非凸的，提出了一種基于SCA技術(shù)的兩步迭代算法，利用Dinkelbach算法來逼近一個(gè)接近最優(yōu)的解決方案。最后通過仿真結(jié)果驗(yàn)證了所提算法的有效性和收斂性。

參考文獻(xiàn)

[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òng)邊緣網(wǎng)絡(luò)中的低時(shí)延計(jì)算卸載技術(shù)[D]. 杭州：浙江大學(xué)，2020.

[4]葛東玉. ad hoc 云環(huán)境下任務(wù)卸載策略研究[D]. 重慶：重慶郵電大學(xué)，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 網(wǎng)絡(luò)的移動(dòng)邊緣計(jì)算卸載策略[J]. 計(jì)算機(jī)科學(xué)，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]張海波，欒秋季，朱江，等. 車輛異構(gòu)網(wǎng)中基于移動(dòng)邊緣計(jì)算的任務(wù)卸載與資源分配[J]. 物聯(lián)網(wǎng)學(xué)報(bào)，2018，2（3）：36-43.

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

[13]李振江，張幸林. 減少核心網(wǎng)擁塞的邊緣計(jì)算資源分配和卸載決策[J]. 計(jì)算機(jī)科學(xué)，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]高寒，李學(xué)俊，周博文，等. 移動(dòng)邊緣計(jì)算環(huán)境中基于能耗優(yōu)化的深度神經(jīng)網(wǎng)絡(luò)計(jì)算任務(wù)卸載策略[J]. 計(jì)算機(jī)集成制造系統(tǒng)，2020，26（6）：1607-1615.

基金項(xiàng)目：國家自然科學(xué)基金（62137001）；國家自然科學(xué)基金（U1811261）

作者簡介：楊一桐（1990—），女，遼寧沈陽人，碩士，實(shí)驗(yàn)師，主要研究方向?yàn)橹悄芸刂?、無線網(wǎng)絡(luò)、實(shí)驗(yàn)室管理等。

吳菁晶（1981—），女，副教授，主要研究方向?yàn)橥ㄐ啪W(wǎng)、網(wǎng)絡(luò)生存性和可靠性等。