基于改進粒子群的邊緣計算任務卸載策略

曹 靖 王朝亮 鄭國權 孫 毅

1.華北電力大學電氣與電子工程學院 北京 102206;2.國網浙江省電力有限公司營銷服務中心 浙江杭州 310000;3.中國電力科學研究院 北京 100080

第五代移動通信系統(The Fifth Generation Mobile Communications System,5G)是新一代蜂窩移動通信技術,具有高帶寬、低時延、大連接通信優勢,已列為國家“新基建”重點部署的七大領域之一[1]。隨著5G通信服務普及,大量互聯網信息技術已成為研究熱點,其中以邊緣計算(Edge computing)技術[2]為代表的分布式數據計算技術在5G通信技術支持下得到大力發展。邊緣計算技術通過將計算服務分布式從網絡中心下沉至網絡邊緣,允許為網絡用戶提供應用程序、數據資料與服務運算,從而滿足各類用戶低時延業務的運算需求。

隨著虛擬現實技術、自動駕駛等新型業務出現,網絡終端側數據呈現爆炸式增長,此類業務數據的響應時延需求進一步提高,同時大量業務數據計算依賴于相應算法框架,這給現有邊緣計算服務系統帶來巨大的通信和算力壓力。邊緣緩存技術[3]和設備直連通信(Device-to-Device,D2D)技術[4]的引入為實時高頻數據計算提供了可靠解決方案。邊緣緩存技術允許邊緣側設備緩存業務計算所需業務算法框架,從而減少邊緣服務器的數據計算壓力,同時設備直連通信技術可實現兩個設備之間的通信鏈路的建立,使數據計算更多的在邊緣設備處理,減少基站通信和計算壓力,進一步提高業務響應能力。

本文在5G通信支持的邊緣計算系統中引入服務緩存和設備間直連通信,允許終端設備緩存部分服務并為相鄰設備提供任務卸載和計算,研究依賴服務緩存的業務數據邊緣計算卸載決策的制定。首先設計考慮服務緩存和設備間直連任務卸載的系統模型,在此基礎上設計基于改進粒子群的卸載決策算法,并通過仿真分析驗證所提算法在邊緣計算場景下的可行性和優越性。

1 系統模型

如圖1所示,本文考慮由一個基站和N個終端設備組成的多接入邊緣計算場景,設所有網絡節點集合為N+={1,2,…,N,N+1},其中N={1,2,…,N}為終端設備集合,N+1表示基站。基站處配備了邊緣計算服務器,擁有所有類型的服務緩存M={1,2,…,M},同時為覆蓋范圍內的終端提供通信信道分配及邊緣計算服務;終端具有固定緩存列表,以支持對應業務類型的數據計算,各設備的服務緩存列表表示為bi=(bi,1,…,bi,M),其中bi,m=1表示設備i∈N具有業務m∈M的緩存文件。到達設備的計算任務可以通過設備間直連通信或與基站間5G通信將計算任務卸載至具有相應緩存的節點進行計算處理。

圖1 系統模型

1.1 設備任務到達模型

假設計算任務到達設備遵循離散化時間尺度T={1,2,…,T},每個時隙間隔為τ,每個時隙t∈T開始時,所有設備將有多個計算任務到達,且任務受服務類型區分,到達設備的計算任務表示為{dm,Tm,ρ},其中,dm為計算任務數據大小,Tm為數據處理的時延要求,ρ為處理器每計算單位該類型的計算任務所需的CPU周期數。

1.2 任務卸載模型

(1)

(2)

(3)

1.3 任務隊列模型

(4)

(5)

(6)

(7)

式中,κ為設備數據計算能耗系數。

在該系統所描述的邊緣計算任務卸載過程中,計算任務從產生到完成處理最多經過卸載、排隊和處理三個過程。由于計算任務的排隊模型無法給出任務的具體等待時間,可采用平均排隊時延[5]來表示:

(8)

1.4 問題建立

本文目標旨在考慮設備緩存的邊緣計算系統中構建最優任務卸載算法,故將邊緣計算系統中設備任務處理能耗與時延的加權平均和作為目標函數,定義目標函數為:

(9)

約束:

(10)

(11)

(12)

(13)

(14)

式中α和β分別為時延和能耗權重系數,本文設定其值均為0.5。約束(10)、(11)表示計算任務卸載有且僅有一個卸載目標,且該目標需要擁有相應服務緩存;約束(12)、(13)分別對設備的最大計算頻率和最大傳輸功率進行約束;約束(14)為任務處理時延約束。對于該問題的求解由于受約束及排隊時延限制,需要對任務卸載決策Y進行決策分析和制定。本文提出基于改進粒子群算法的服務緩存約束卸載決策方法對該問題進行求解。

2 基于改進粒子群的卸載決策算法

本文目標為系統所有設備的任務處理能耗與時延加權和最小優化問題,由于存在任務處理時延約束(14)和任務卸載變量Y,該問題屬于NP-hard問題[6],無法直接求解。本文設計基于改進粒子群算法設計卸載決策求解方法,對于單一變量問題的求解具有計算簡單、收斂性好的特點,具有較好性能。

(15)

(16)

其中,ω為慣性權重,c1和c2為學習因子,r1,r2∈[0,1]為0到1之間隨機數。傳統粒子群算法對于慣性權重和學習因子采用恒定賦值,其數值大小不會隨著迭代進行而改變,這使得粒子群算法所求解出的計算結果容易陷入局部最優解,采用該方法無法得出系統最優卸載決策。本文所設計的改進粒子群算法分別通過對慣性權重系數及學習因子進行改進,其值在每次迭代中自我更新,在求解中能夠以最少次數迭代得出全局最優解,且該解不落入局部最優。本文慣性權重和學習因子表示為:

(17)

(18)

(19)

其中,ω1和ω2分別為當前迭代過程開始與結束時的慣性權重,c11、c21、c12及c22分別為兩個學習因子在當前迭代過程中開始與結束時的值,k為當前迭代次數,N為迭代總次數。

本文所設計的考慮服務緩存的改進粒子群算法具體步驟如圖2所示。

圖2 算法流程

3 仿真分析

本節基于Matlab R2017b仿真平臺設計仿真算法對本文所提任務卸載問題求解,并與隨機卸載算法和傳統粒子群算法進行比較分析,從而驗證本文算法優越性。部分仿真參數設置如下表所示。

仿真參數表

圖3為本文所提算法的收斂性證明,由圖可知本文算法能夠在百次迭代內即接近收斂,具有較好的收斂性。

圖3 算法收斂性驗證

圖4和圖5分別對比了隨機卸載算法、傳統粒子群算法和本文算法受設備緩存服務數及計算任務數據規模變化的影響。其中隨機卸載算法旨在對于設備所到達的計算任務,在滿足其時延要求情況下隨機選擇一個具有相應緩存的設備進行卸載,而不考慮所選擇卸載目標設備是否為當前系統中最優目標,因此該卸載方案在三種方案中,其平均時間能耗加權和最大,性能最差;傳統粒子群算法在設備緩存數和計算任務規模較小時,其優化結果與本文算法相近,然而隨著緩存數的增加,設備能為更多類型業務提供數據計算服務,但設備的計算能力并未改變,因此任務的排隊時延增加,而傳統粒子群算法在此時所得出優化結果不及本文算法,得出的結果為局部最優解;計算任務數據規模的增大導致設備對于單一任務的計算時延增加,也相應增加了隊列中任務的等待時延,而本文算法相比于其他算法具有最優優化結果,進一步證明了本文算法的優越性。

圖4 設備緩存服務數對目標的影響

圖5 計算任務數據規模對目標的影響

結語

為推進5G通信與邊緣計算技術的普及和發展,本文針對業務數據計算對于求解算法框架依賴的場景下此類數據邊緣計算可行方案,提出了聯合服務緩存和設備直連通信的邊緣計算系統,對該系統中任務卸載和計算過程進行數學模型規定,在此基礎上設計了基于改進粒子群的卸載決策算法,通過仿真分析驗證了所提算法在邊緣計算場景下的有效性。