基于改進粒子群算法的邊云協同計算卸載策略

劉向舉,李金賀,蔣社想

(安徽理工大學 計算機科學與工程學院,安徽 淮南 232001)

為了彌補移動云計算(Mobile Cloud Computing,MCC)的不足,移動邊緣計算(Mobile Edge Computing,MEC)作為一種有效的計算范例出現。MEC將計算和存儲資源從云數據中心地理分布部署到網絡的邊緣,可以在物理上接近用戶設備對數據進行分析和處理,從而大大降低任務執行的延遲和能耗,有效減輕核心網的流量負荷,延長移動設備的使用壽命。雖然與MCC相比,MEC具有更短的延遲和更強的可靠性,但它所能提供的資源量仍然遠遠小于MCC。因此,將移動設備生成的所有任務都卸載到MEC服務器上是不合理的,將云資源與邊緣資源相結合,利用云資源作為邊緣資源的輔助,形成云邊協作的卸載場景,可以充分利用網絡中的現有資源,為不同需求的任務提供更多的卸載選擇。

計算卸載一直是一個熱門的研究焦點。He W等人[1]研究了一個多用戶全雙工通信的MEC系統,考慮了功率控制、時間調度、卸載決策和用戶配對策略,提出的最優算法有效的解決了系統延遲最小化問題。羅馨玥等人[2]針對多個移動設備的MEC系統,考慮了在系統時延的約束下,提高系統的能量效率。然而,這些工作只考慮了如何利用邊緣服務器的資源,沒有考慮到結合云服務器的資源。因此,現有的工作研究了云邊緣協作環境中與計算卸載相關的問題,張帆等人[3]針對云邊協同的計算卸載模型,以最小化時延為目標,設計了一種多任務計算卸載方法。楊君等人[4]提出了一種邊云協同計算的能耗感知資源調度方法,能夠在實時性的前提下有效降低能耗。于濱等人[5]考慮了多移動設備組成的邊云協同系統,為了降低移動設備的時延,提出了基于深度強化學習的任務卸載算法。

上述工作只針對單一目標進行優化,沒有考慮到時延和能耗的聯合優化。因此,本文研究以時延和能耗的加權和為目標,提出了一種基于改進的粒子群算法的卸載方法,能夠為邊云協同場景范圍內的所有移動設備制定計算卸載策略。

1 系統模型和問題描述

1.1 網絡模型

本文考慮了一個具有1個云服務器、多個MEC服務器和多個用戶的云-邊緣協作網絡框架,如圖1所示。其中在基站上配置了可以執行計算密集型和數據敏感性任務的邊緣服務器,每個移動用戶通過無線信道關聯到相應基站,可以在唯一的MEC服務器上執行計算卸載,或者邊緣節點通過回程鏈路將任務卸載到遠程云服務器。

基站或MEC服務器集合可以表示為N={1,2,…,n,…,N},用戶移動設備任務集合為U={1,2,…,u,…,U}。每個移動用戶u每次都有一個不可分割任務需要執行,任務屬性采用二元組表示為Qu={su,wu},其中su表示上傳計算的任務數據大小,wu表示處理任務所需的計算量。

1.2 通信模型

假設系統內的所有移動設備采用正交方式接入,移動設備之間不存在干擾。系統中每個用戶在一定時間間隔內位置不變,根據香農信道容量公式,移動用戶u與邊緣服務器n之間的上行傳輸速率可表示為

(1)

1.3 計算模型

(1) 本地計算:假設每個用戶設備具有固定且不同的CPU頻率,則用戶任務Qu在本地計算的執行時間和能耗分別為

(2)

(3)

(2) 移動邊緣計算:用戶將任務卸載至MEC服務器的處理主要包括3個階段:上傳數據、在MEC服務器上執行任務和結果返回。由于任務結果數據量相對較小,任務結果在下行傳輸中的能耗和延遲可以忽略不計,所以本文主要關注前2個階段。

根據式(1),移動用戶u卸載任務Qu上行傳輸到基站n時的傳輸時延和能耗分別為

(4)

(5)

(6)

(7)

式中:pedge為與MEC服務器n相聯的基站平均功率。則任務Qu卸載至邊緣計算的時延和能耗分別為

(8)

(9)

(3) 云服務器計算:當任務卸載至云計算時,任務需要先卸載至MEC服務器,再傳輸至云服務器進行云計算和結果返回。由于云距離邊緣節點較遠,本文將不同的邊緣節點和云服務器之間的距離視為相等,同樣忽略了結果返回的延遲。假設邊緣節點上傳任務到云服務器的傳輸速率為常量Rc。任務Qu的傳輸延遲和能耗分別為

(10)

(11)

任務Qu在云服務器的執行時間和能耗分別為

(12)

(13)

(14)

(15)

1.4 問題優化模型

根據上述模型,處理任務Qu的總延遲和總能耗分別為

(16)

(17)

式中:αu,βu,γu取值為0,1整數的二元變量卸載決策,當取1時分別表示任務Qu在移動設備本地、MEC服務器或云服務器進行計算,由于任務只能在一個地方執行,需滿足約束條件αu+βu+γu=1。

在MEC系統中,執行計算任務的時延和能耗決定了QoS,由于不能同時最小化平衡2個因素,本文將系統總成本定義為執行任務時延和能耗的加權和,則有

(18)

式中:λ為時間成本和能量消耗的加權系數,可以根據實際需求進行調整。

本文優化目標是通過優化卸載決策來最小化所有任務在邊緣云之間執行總成本C,優化問題表述如下

s.t.C1:αu,βu,γu∈{0,1}

C2:αu+βu+γu=1

C4:0≤λ≤1

(19)

式中:約束C1、C2表示任務只能在一個地方被處理,約束C3為給移動設備任務分配的計算資源約束;約束C4限制時延和能耗的權重和為1。當用戶數和基站數目較大時,問題(19)為大規?；旌险麛捣蔷€性規劃問題,窮舉搜索方法雖然能夠得到最優解,但是不實際和不可行,因此本文使用改進粒子群算法解決該問題。

2 基于改進粒子群算法的移動邊緣計算卸載方法

粒子群優化算法(Particle Swarm Optimization Algorithm,PSO)是一種廣泛使用的啟發式優化算法[7],不需目標函數的連續性和凸性,但容易出現早熟,導致局部收斂。模擬退火算法(Simulated Annealing Algorithm,SA)收斂效率較低,但其收斂到全局最優解的概率為1[8]。結合2種算法的優點,可以提高算法的靈活性和粒子多樣性,獲得較強的全局優化能力,從而提高參數優化的精度。因此,本文將SA與PSO結合,使用改進粒子群算法(Improve Particle Swarm Optimization Algorithm,IPSO)的方法解決問題P1。

2.1 編碼和初始化

本文采用整數編碼,粒子收斂的位置表示最終的卸載決定。用戶任務可以在本地、N個MEC服務器、1個云服務器的場景中執行,因此位置范圍定義為N={0,1,…,N,N+1},其中0表示在本地計算,1～N表示在邊緣服務器1～N中計算,N+1為云計算。PSO在每次迭代中,使用式(22)和式(23)更新粒子的位置和速度,但每個粒子的位置值由式(20)轉換為離散數值。

(20)

2.2 適應度函數

在PSO中每個粒子都通過一個適應度函數來評估,本文適應度值由式(21)計算,表示為

(21)

2.3 粒子更新策略

(22)

(23)

式中:k表示迭代次數;c1和c2為學習因子;ω為速度慣性權重;rand()表示在[0,1]之間的均勻分布的隨機數。

為了更好的平衡算法的全局搜索能力和局部改進能力,慣性權重ω應合理設置,一些研究者提出了改進的慣性權值的PSO算法[9-10]。但是,這些方法并沒有充分限制動態求解過程中慣性權值的取值范圍,并且與每一代粒子的適應度的相關性還有改進的空間。本文采用基于適應度值和迭代次數的慣性權重策略。

(24)

(25)

式中:當f(Xi)≥favg時,如果ω>0.99,則ω=0.99。當f(Xi)

IPSO算法優化卸載決策的主要過程如下:

步驟1:設置PSO算法的迭代次數kmax、種群大小Num、加速度因子c1和c2,設置SA算法的初始溫度T、退火系數h和馬爾可夫鏈長度s,初始化每個粒子的速度和位置。

步驟2:選擇式(21)作為適應度函數,計算所有粒子的適應度值,確定初始最優種群位置。

步驟3:根據式(25)更新慣性權值ω,式(22)和(23)更新速度和位置,根據適應度函數找到新的最優個體位置pbesti和最優群體位置gbesti。如果PSO算法收斂,找到當前最優位置pbesti,則繼續執行步驟4,否則重復步驟3,直到算法收斂。

步驟4:引入SA算法,將步驟3中得到的當前最優位置pbesti作為SA算法的初始位置z,即z(t)=pbesti(t),并在其鄰域內隨機選取一個新的位置z′。分別計算2個適應度J(z)和J(z′),并用Metropolis準則來判斷是否接受替換新的最優種群位置。

更新溫度T(t+1)=hT(t),迭代至s后,繼續執行步驟5。

步驟5:如果SA算法搜索的最終位置z的適應度小于PSO算法搜索的當前最優種群位置Pg(t),則z作為PSO算法新的最優種群位置。

步驟6:判斷適應度值是否滿足條件,如果滿足,輸出種群的最優位置;否則,返回步驟3,直到PSO算法完成kmax次迭代。

3 試驗結果與分析

3.1 試驗環境配置

為了評估提出算法的有效性,本文試驗使用MATLAB R2022b。仿真環境為30個用戶和5個MEC服務器在1 000×1 000 m2的區域中隨機分布,其中云服務器位于中心。其他仿真參數如表1～2所示。

表1 IPSO算法參數設置

表2 仿真環境參數設置

3.2 對比方法

將本文提出的基于IPSO的邊云協同算法與以下算法性能進行對比:

(1) 本地計算(Local Offloading,LO):計算任務由本地設備計算,不進行任務卸載。

(2) 邊緣卸載(Edge Offloading,EO):所有任務由邊緣服務器完成。

(3) 隨機卸載:(Random Offloading,RO):所有任務進行隨機卸載。

3.3 試驗結果及分析

首先評估提出的算法的收斂性,然后驗證提出的算法與其他基線算法的性能比較。

3.3.1 算法收斂性

圖2為30個移動用戶數下的算法收斂性。從收斂曲線可知,PSO需要約50次迭代才能收斂,IPSO只需20次左右迭代即可收斂,能夠快速求解到最小系統成本,比PSO降低了8.7%的系統成本,這表明IPSO具有良好的收斂性,能夠克服PSO算法容易陷入局部極值點的缺點。

圖2 算法收斂性

3.3.2 移動用戶數的影響

對IPSO算法及對比算法在不同移動用戶數量下的性能進行了評估,如圖3所示。在此試驗中所有用戶卸載同一個任務,即su=700 kB。結果表明,相對于其他方案,IPSO算法一直是最優策略,實現了最低的總計算成本。這是因為本文所提出的算法是一種邊云協同卸載方案,用戶可以在本地、邊緣服務器和云服務器處理任務,可以充分利用計算能力較強的邊緣節點的計算資源,同時分配更多的云計算資源來輔助計算能力較弱的邊緣節點,使得卸載決策更合理的分配任務,減小任務執行成本。當用戶數為30時,與EO、RO、LO算法相比,IPSO算法的系統總成本平均分別降低了24.1%、53.9%、72.3%。

圖3 用戶數量對系統成本的影響

3.3.3 任務數據大小的影響

將每個任務的數據大小從500 kB到2 500 kB遞增,給出的不同算法下任務數據大小對系統總成本的影響如圖4所示。結果表明,增加數據大小不會改變LO算法總計算成本。其余算法成本隨著任務數據大小的增加而增加,這是因為系統中通信資源是固定的,輸入數據量的增加會直接影響到卸載任務的上行傳輸延遲和能耗。這說明,計算少量數據的卸載任務可以獲得更好的結果。

圖4 任務數據大小對系統成本的影響

3.3.4 用戶偏好的影響

用戶時延偏好λ從0.1變化到0.9對IPSO的任務平均時延和能耗的影響如圖5所示。結果表明,隨著λ的增加,平均時間消耗降低,能量消耗增加,表明IPSO能夠根據用戶需求進行動態調整卸載決策,求解最小的系統成本。

圖5 用戶偏好的影響

4 結語

為了充分利用云服務器、用戶移動設備和MEC服務器的異構計算能力,本文提出了一種基于改進粒子群算法的邊云協同任務卸載策略。該策略實現了網絡資源的協同和管理,能夠滿足在多種約束下處理用戶任務的系統成本最小化的需求。試驗結果表明,該算法有效且能夠在有限迭代次數內收斂。與基準算法相比,本文算法具有最低的系統成本、能量消耗和延遲,并且隨著任務數量的增加,優勢更加明顯。然而,本文研究的MEC場景為準靜態系統,在未來的研究中,將考慮到用戶移動性、環境參數的時變性等問題,為動態多變的場景提供更好的卸載策略。