異構邊緣云架構下的多任務卸載算法

尼俊紅, 臧云

(1.華北電力大學(保定) 電子與通信工程系,河北 保定 071003; 2.華北電力大學 河北省電力物聯網技術重點實驗室,河北 保定 071003)

隨著移動通信技術的發展和智能終端的普及,增強現實(augmented reality,AR)、虛擬現實(virtual reality,VR)、無人駕駛等各種應用不斷涌現,用戶對服務質量(quality of service,QoS)和體驗質量有了更高的要求。預計到2030年,移動數據流量將出現爆炸式增長,全球移動終端數將接近1 000億,中國可能達到200億[1]。在終端設備上運行這些新興的數據量較大的應用程序,需要大量的計算資源、存儲資源以及較高的能耗,而移動設備的計算能力、資源存儲和電池電量往往是有限的,無法滿足這些需求。

歐洲電信標準化協會在2014年成立了移動邊緣計算(mobile edge computing,MEC)規范工作組,促進對移動邊緣計算的研究[2]。移動邊緣計算是指在移動網絡邊緣部署計算和存儲資源,為移動網絡提供IT服務環境和云計算能力,從而為用戶提供超低時延和高帶寬的網絡服務解決方案[3-4]。MEC的關鍵技術為計算卸載,為應用制定適合的卸載決策[5]是近年來的研究熱點。

研究人員為了研究任務卸載決策的相關問題做了許多工作,通過建立車輛和無人機協助下的MEC模型,將不同的任務按需卸載到不同的邊緣節點,并設計了分布式匹配-貪婪算法[6]。Gu等[7]研究了車輛網絡移動邊緣計算系統,提出了2種獨立的啟發式匹配算法解決移動中的任務卸載問題。Du等[8]通過聯合優化卸載決策和計算資源、無線電資源的分配,解決混合云/霧系統中的計算卸載問題。Wang等[9]提出了基于智能體的任務卸載體系架構,協同無人機和邊緣服務器上的計算資源為用戶提供最優的任務卸載決策。Yu等[10]建立了深度多標簽分類模型,并將模型分為離線演示生成、離線模型訓練和在線決策3個階段,提出了基于深度模仿學習的MEC任務卸載策略。Ke等[11]考慮車輛移動場景下信道的時變性,建立了異構車載網絡任務計算卸載模型,提出了一種基于深度強化學習的自適應計算卸載方法,通過權衡能耗、帶寬分配和緩沖隊列的成本來選擇任務最佳卸載策略。

除了以上這些方法,還有一些研究者通過群體智能算法解決卸載問題,例如遺傳算法(genetic algorithm,GA)、粒子群算法(particle swarm optimization,PSO)等。王妍等[12]提出云輔助移動邊緣計算的計算卸載策略,在GA算法的基礎上,設計了一種基于改進GA算法的計算卸載算法。羅斌等[13]針對時延敏感型的應用,提出了一種基于PSO算法的計算卸載策略,在能耗約束條件下最小化時延,使用懲罰函數來平衡時延與能耗。Wu等[14]考慮延遲和能量消耗因素,提出了一種邊緣云協同多任務計算卸載模型,采用非線性指數慣性權重PSO算法進行求解。Wei等[15]通過建立異構網絡模型以及任務依賴關系模型,設計了結合貪婪策略的PSO和動態PSO 2種算法研究任務卸載策略。Adhikari等[16]研究了分布式霧設備和集中式云數據中心的協作,使用加速PSO技術為分層霧云環境設計了一種多目標卸載策略,在有效利用計算資源的同時,最小化總成本和延遲。

上述研究工作的共同特點是邊緣節點類型單一或者在構建系統模型時未考慮不同計算任務的差異性。而在實際環境中,往往是復雜異構的邊緣網絡,而用戶側無論是任務的類型還是任務的數量都不是單一的。本文考慮構建混合云/霧的異構邊緣網絡模型,將多任務卸載到車輛、無人機、路邊單元等邊緣節點或者通過邊緣節點卸載到邊緣云,滿足用戶的服務質量和體驗質量。

1 異構邊緣云系統模型

1.1 網絡模型

如圖1所示,本文考慮由N個用戶,M個邊緣節點,1個邊緣云組成的異構邊緣云系統,其中無人機、路邊單元、車輛作為邊緣節點,數量分別為I、J、K,I+J+K=M。為了滿足用戶的服務質量和體驗質量,用戶可以在本地執行任務,也可以將任務通過D2D方式卸載到車輛,或通過蜂窩無線網絡卸載到無人機、路邊單元(road side unit,RSU)等邊緣節點。由于邊緣節點的計算能力和能源有限,當其無法滿足用戶需求時,可將任務通過邊緣節點中繼到邊緣云服務器。邊緣云部署在服務小區的基站上,無人機和車輛通過無線方式連接到邊緣云,路邊單元通過有線鏈路連接到邊緣云。

圖1 異構邊緣云系統網絡模型

用戶卸載決策的約束條件為:

(1)

1.2 計算模型

為了便于分析,假定邊緣節點和邊緣云僅在接收到所有輸入數據之后,開始執行任務。

1.2.1 本地執行

(2)

(3)

1.2.2 邊緣節點執行

Bn/Rn,ei,j+Cn/fei,j+Dn/Rei,j,n

(4)

式中:ei,j的第1個下標i表示邊緣節點類型,i=1,2,3分別對應無人機、路邊單元和車輛;j表示邊緣節點的序號;Bn、Rn,ei,j分別表示用戶n上傳數據量大小以及用戶n和邊緣節點ei,j之間通信鏈路的上行傳輸速率;fei,j表示邊緣節點ei,j的計算能力;Rei,j,n表示邊緣節點ei,j與用戶n之間的下行傳輸速率。假定通信鏈路的上、下行信道條件相同,且分配帶寬相同,則上、下行傳輸速率相等,即,Rn,ei,j=Rei,j,n。

用戶n將任務卸載到邊緣節點執行的能耗為:

(5)

1.2.3 邊緣云執行

除了以上幾種任務執行方式之外,還可以將任務通過邊緣節點中繼到部署在基站的邊緣云服務器執行。

因此,任務通過邊緣節點中繼到邊緣云服務器卸載的時延為:

(6)

(7)

(8)

(9)

此外,數據在無人機和邊緣云服務器之間傳輸階段和任務執行階段,UE處于空載狀態,此時的能耗為:

(10)

1.3 問題表述

用戶n任務執行時,系統的時延Tn和能耗En可以分別表示為:

(11)

(12)

(13)

2 H-PSOGA任務卸載算法

PSO和GA算法都是經典的群體智能算法。PSO算法原理簡單、搜索速度快,但是容易陷入局部最優;GA算法具有很強的全局搜索能力,但是收斂精度不高。本文采用先串行后并行的方式,提出了一種基于PSO算法和GA算法的混合優化算法(hybrid particle swarm optimization and genetic algorithm,H-PSOGA)。

假設粒子群規模為S,整個粒子群的位置集合表示為X={x1,x2,…,xS},速度集合表示為V={v1,v2,…,vS}。

H-PSOGA算法首先進行PSO進化,計算每個個體的適應度值并進行排序,然后利用PSO融合GA進行子代的選擇、多點交叉、反向變異,形成新的子代;子代再進行PSO進化,并重復上述過程再次形成新的子代;循環往復,直至得到最優解。H-PSOGA算法優化過程如圖2所示,m為粒子群初始規模,算法實現具體步驟為:

圖2 H-PSOGA 算法優化過程

1)隨機初始化每個個體的速度、位置以及相關參數,對不滿足約束條件的個體重新初始化;

2)將個體當前位置設置為個體最優任務分配方案Gbest,并將適應度值最大的個體的位置設置為群體最優分配方案Hbest,計算每個個體的適應度值為:

(14)

式中:λt和λe為時延和能耗的權重系數;τmax q和emax q分別為q類型任務的容忍時延和容忍能耗。

3)根據式(15)、(16)更新個體每一維度的速度與位置并取整:

v(t+1)=ω·v(t)+c1·mrand·(Gbest-x(t))+

c2·mrand·(Hbest-x(t))

(15)

x(t+1)=x(t)+v(t+1)

(16)

式中:ω為慣性權重;c1、c2為學習因子;mrand為分布在區間[0,1]的隨機數。

權重ω隨著適應度值的變化而變化:

(17)

式中:F表示目前的適應度值;Favg、Fmin分別表示目前所有粒子適應度的平均值和最小值。當粒子目標值比較分散時,減小慣性權重,粒子目標值比較集中時,增加慣性權重;

4)判斷是否滿足PSO進化的迭代次數或者收斂精度,若滿足條件,則執行步驟5),否則執行步驟2),直到滿足條件為止;

5)計算每個個體的適應度值并按照從大到小的順序進行排序;

6)種群選擇,將排序后的種群Q平均分成4個子種群,淘汰適應度值最小的子種群4,如圖3所示;

圖3 選擇操作示意

7)多點交叉和反向變異:保留的3個子種群進行交叉、變異操作,對每一維度進行取整;

定義平均距離的概念,通過判斷交叉父代同一維度的距離與平均距離的大小,本文設計了一種交叉方式。假設2個個體分別為x1和x2,定義2個個體的平均距離為:

(18)

圖4 交叉操作示意

由圖4(a)的2個個體的基因序列,根據式(18)計算2個個體的平均距離為1.37,圖4(a)中第4維和第5維的距離大于平均距離,則第4維和第5維對應的基因分別交換位置,得到圖4(b)的子代。

在實數編碼時,等位基因的類型不再是簡單的布爾型,故變異不能簡單的取反。本文采用基于時變概率的反向學習方式進行均勻變異,使個體跳出局部最優。設個體目前適應度值為Fs,目前種群的平均適應度值為Favg,適應度值方差ψ2為:

(19)

(20)

(21)

8)適應度值最大的子種群直接進行PSO速度和位置更新生成子代;

9)計算所有子代的適應度值并按照從大到小的順序進行排序;

10)選擇適應度值較大且數量與初始種群相同的子代重新組成新的種群;

11)判斷總的迭代次數或者收斂精度是否滿足條件,若滿足條件,則輸出最優解,即最優卸載方案,否則執行步驟2)。

3 H-PSOGA算法仿真與結果分析

3.1 仿真參數設置

本文使用Matlab 2020a軟件對H-PSOGA算法性能進行仿真驗證。首先用6種標準測試函數對H-PSOGA算法的性能進行測試,為了便于觀察,采用測試函數值的相反數進行繪圖。然后將H-PSOGA算法應用到系統模型中,通過與基線算法的對比,驗證本文算法在解決異構邊緣云架構下的多任務卸載中的適用性。表1為仿真模型參數。

表1 仿真參數

表2為6種標準測試函數。算法控制參數:粒子群規模S=40,粒子維度N=100,迭代次數D=1 000,學習因子c1=1.5,c2=2.5,慣性權重的最大值和最小值為ωmax=0.8,ωmin=0.4,標準測試函數最優解為0。因為是n維粒子空間,(0)n為每個維度的粒子的最優位置都是0。

表2 標準測試函數

3.2 仿真結果分析

慣性權重ω可以控制粒子的搜索范圍,增大ω的值可以提高算法的全局搜索能力,減小ω的值可以提高算法的局部搜索能力。對多種PSO改進方案進行對比實驗,如圖5所示,隨著迭代次數的增加,幾種改進PSO的方案以收斂速度為代價提高了收斂精度,非線性遞減改進權重方案的收斂精度最高,故采用該方案與本文H-PSOGA算法進行對比實驗。

圖5 不同慣性權重適應度值曲線

為了更加清晰直觀地說明H-PSOGA算法的性能,通過6種標準測試函數比較標準PSO、非線性改進權重方案、PSOGA算法以及本文H-PSOGA算法的收斂情況,如圖6所示。

圖6 6種標準函數測試結果對比

從圖6可以看出,6種算法的適應度值均隨著迭代次數的增加而逐漸增加。對于任意標準測試函數,標準PSO、非線性改進權重方案以及PSOGA算法的適應度值增加到定值達到穩定,即收斂狀態。而對于H-PSOGA算法來說,對于不同的標準測試函數,H-PSOGA算法的適應度值表現出不同的收斂效果。

圖6(a)和(b)中H-PSOGA算法適應度值整體呈現增加的趨勢,還未達到收斂的狀態;圖6(c)和(e)中H-PSOGA算法的適應度值收斂到定值,且收斂精度高于其他算法。圖6(d)和(f)中H-PSOGA算法在迭代到一定次數時停止迭代,此時得到最優解。

總體來說,H-PSOGA算法的收斂精度更高,用多種測試函數也證明了H-PSOGA算法的普適性。將H-PSOGA算法應用到系統網絡模型,進行對比實驗,如圖7所示,收斂后的適應度值比標準PSO和PSOGA算法分別提升36.5%和16%。

圖7 適應度函數收斂曲線

從圖7可以看出,隨著迭代次數的增加,標準PSO算法、非線性改進權重PSO算法、PSOGA算法的適應度值都會增加,最后收斂到相對穩定的狀態。相對于基線方案,H-PSOGA算法的適應度值較大,隨著迭代次數的增加收斂速度較快,收斂精度也較高,證明了H-PSOGA算法適用于本文提出的異構網絡模型,同時也驗證了H-PSOGA算法的性能。

圖8所示為不同類型業務的卸載決策。圖中數字1～5為5種具有不同任務復雜度、容忍時延、容忍能耗的計算任務,任務類型序號越大,任務復雜度越高。任務的復雜度越大,本地執行任務的概率越小,卸載到無人機、路邊單元、車輛以及邊緣云的概率越大,這是因為本地無法滿足用戶業務的需求,需要將任務卸載到計算能力更大的邊緣節點或邊緣云服務器。

圖8 不同類型任務卸載方案概率分布

圖9為系統平均開銷與用戶數量的關系曲線。從圖9中可以看出,隨著用戶數量的增加,系統的平均開銷逐漸增大。

圖9 系統平均開銷與用戶數量關系

在用戶數量相同的情況下,與對照方案相比,H-PSOGA算法的系統平均開銷最小。在用戶數較少時,幾種方案的性能較為接近,H-PSOGA算法的性能優勢不是很明顯;當用戶數超過 150時,系統性能提升較為明顯,例如在用戶數為200時,相比標準PSO、非線性改進算法和PSOGA算法的性能提升分別為43.06%、42.98%和31.52%;在用戶數為300時,相對上述3種對照方案的性能提升分別為31.08%、30.38%和29.4%。

4 結論

1)提出混合優化算法H-PSOGA實現異構邊緣云架構下的多任務卸載,有效提高了收斂精度,降低了系統總開銷。

2)本文在研究任務卸載時將通信資源和計算資源設為固定值,而在實際情況中,需要聯合任務卸載和資源分配進行優化,將是后續研究重點解決的問題。