多用戶MIMO-MEC網絡中基于APSO的任務卸載研究

顧 敏，徐雅男，王辛迪，花 敏，周 雯*

(1.南京林業大學 信息科學技術學院，江蘇 南京 210037；2.安徽大學 互聯網學院，安徽 合肥 230039)

0 引言

隨著5G移動通信技術的發展,計算密集型應用以及物聯網(Internet of Things, IoT)相關應用迅速增加,給智能終端設備和中心網絡的實時處理帶來了巨大挑戰[1]。傳統模式下的任務計算卸載模式如云計算、霧計算等,難以高效地執行計算密集型任務,導致用戶的體驗質量(Quality of Experience, QoE)下降。為了緩解這一困難,移動邊緣計算(Mobile Edge Computing, MEC)應運而生。MEC系統允許設備將計算任務卸載到網絡邊緣節點,如基站、無線接入點等,既滿足了終端設備計算能力的擴展需求,同時彌補了云計算時延較長的缺點[2]。

為了發揮邊緣計算技術在緩解移動終端計算資源不足和降低終端時延[3]、能耗[4-5]等方面的優勢,必須采用有效的任務決策及資源管理策略。文獻[3-9]對單天線邊緣計算系統的任務卸載問題進行了研究。文獻[7]研究了時延和能量損耗的權衡關系,提出一種基于MEC的內容感知分類卸載算法。文獻[8]提出了多小區MEC系統的能量感知任務卸載方案,在有限的能量和敏感的延遲下聯合優化了通信和計算資源的分配。文獻[9-12]對多天線邊緣計算系統的任務卸載進行研究。文獻[9]在MEC系統引入了多輸入多輸出(Multiple Input Multiple Output, MIMO)技術,對系統具備完全信道信息(Channel State Information, CSI)和不完全CSI這2種情況下的任務卸載問題分別進行了研究。文獻[11]考慮了無線、計算、回程和上下行資源分配的聯合優化,提出了一種基于連續凸逼近的迭代算法。文獻[12]研究了具有無線回程的2層海量MIMO異質網絡中的節能資源分配問題。

現有基于MEC的MIMO多用戶系統的研究通常假設基站是多天線,用戶端是單天線[9,12-13],而對于用戶端是多天線的研究較少。同時很多研究假設下行鏈路的反饋結果很小,將反饋時延予以忽略,未考慮到下行鏈路中多路數據的傳輸。另一方面,文本、視頻和圖像均可采用數據壓縮技術進行壓縮,減小傳輸的數據量。本文在MIMO-MEC系統引入該技術,以期降低系統運算成本。

基于上述,本文研究了具備數據壓縮功能的MEC系統的任務決策問題,其中基站、多用戶均配備了多根天線。該問題可以歸結為一個非凸的多約束優化問題?？紤]到粒子群算法可解決復雜的多約束目標優化問題,文獻[14-16]將其用來解決MEC系統的任務卸載及資源分配問題,本文基于改進的粒子群算法提出了一種多用戶任務分配算法,對上行鏈路的帶寬、發送功率和壓縮比例等多個方面進行了優化。仿真結果表明,提出的方法優于若干對比方案,能夠有效降低任務的執行時延。

1 系統模型

如圖1所示,MIMO-MEC網絡由K個用戶設備(User Equipment,UE)和一個基站(Base Station,BS)組成,且基站配備一個MEC服務器。用戶和BS均配備多根天線:BS配有NT根天線,用戶k配備NR,k根天線,?k∈?{1,2,…,K}。在此系統中,UE的任務可以一部分在本地執行計算,另外一部分可以卸載到MEC服務器進行計算。為了節省數據傳輸量,卸載的任務可以先進行部分壓縮再上傳至MEC服務器計算。

圖1 MEC的MIMO網絡框架Fig.1 MIMO network framework for MEC

如圖2所示,用戶i的任務卸載過程分為3個環節:本地處理、上行鏈路傳輸計算和下行鏈路反饋。首先,將任務拆分,其中一部分用于本地計算,剩余任務按比例壓縮處理并在任務結束后上傳至MEC服務器,此時未壓縮任務卸載到MEC服務器中計算;其次,當壓縮任務傳輸完成并且未壓縮任務也計算完畢,MEC服務器開始處理壓縮任務,即解壓任務并計算;最后,MEC服務器將計算數據反饋到用戶,并與本地計算的結果進行組合,此時用戶i的計算任務處理完畢。

圖2 任務卸載過程Fig.2 Task offloading process

多用戶在上下行鏈路的通信采用頻分復用(Frequency Division Multiple Access,FDMA)的方式并行處理,各個用戶互不干擾。

本文對任務的卸載比例、壓縮比例和用戶發送功率等多個參數進行聯合優化,目標是最小化多用戶任務的總時延。接下來,分別對通信模型和任務卸載模型做進一步解釋,最后將問題歸結為多約束的優化問題。

1.1 通信模型

(1)

(2)

(3)

(4)

式中:Bmax和B′max分別是上行鏈路和下行鏈路的總帶寬。本文對用戶的上行鏈路帶寬進行優化,對下行鏈路帶寬采用平均分配方式。

(5)

1.2 計算模型

本節詳細描述用戶i的任務卸載過程。如前所述,用戶i的計算任務表示為i={Di,Ci,Ji,Li,ρi},假設計算任務可按比例任意切割,任務卸載比例αi∈[0,1],0代表用戶任務完全由本地執行,1代表用戶任務完全卸載到MEC服務器執行。卸載的任務αiDi進行部分壓縮,壓縮比例βi∈[0,1],0代表卸載任務不壓縮執行,1代表任務全部壓縮卸載到MEC服務器執行。進一步假設,任務壓縮前后數據量的比率為γi∈[0,1],則卸載任務中未壓縮的數壓縮的數據量為αiDiβiγi。

(6)

(7)

式中:Fi為用戶設備UEi的計算頻率。由于壓縮和任務執行是并行的,所以本地計算的總時延為:

(8)

(9)

(10)

因此總能耗為:

(11)

(12)

(13)

(14)

(15)

根據圖2不難發現,用戶i的任務卸載總時延(不包括結果反饋時延)為:

(16)

(17)

(18)

因此,用戶的總能耗為:

(19)

注意,在計算能耗時,本文僅考慮用戶的能耗,不考慮MEC的能耗。

(20)

(21)

式中:ηi∈(0,1]表示MEC計算結果與卸載任務數據量的比率。

根據上述分析,用戶i卸載計算的總時延Ti可以表示為:

(22)

用戶i的總能耗為:

(23)

1.3 問題模型

本文的目標是最小化所有用戶的任務執行時延之和,優化變量包括:①任務的卸載比例;②卸載任務的壓縮比例;③用戶發送功率;④任務的計算頻率;⑤上行信道的用戶帶寬。

將當前問題聯合表達為:

(24)

在P1中,約束條件C1表示UE的能耗不超過最大能耗閾值;C2表示MEC給UE的計算資源不超過自身最大計算資源;C3表示MEC分配給UE集合的計算資源不超過自身最大計算資源;C4表示UE的信道帶寬不超過小區設置的通信帶寬最大值;C5表示UE的信道帶寬集合不超過小區設置的通信帶寬最大值; C6、C7和C8分別表示了UE任務卸載比例、卸載任務中選取壓縮部分的比例以及傳輸功率的取值范圍。

此外,本文涉及變量較多,為了方便閱讀,系統模型涉及的主要變量如表1所示。

表1 系統模型中的符號含義Tab.1 Notations’ meanings in the system model

2 算法設計

近年來,群智能算法如遺傳算法[18-20]、蟻群算法[21]等受到了研究者的關注,已經應用到了圖像處理、網絡資源分配等方面。粒子群優化 (Particle Swarm Optimization,PSO) 算法屬于群智能算法的一種,是通過模擬鳥群捕食行為設計的。算法采用“群體”與“進化”的概念,從隨機解出發,依據個體的適應度通過迭代尋找最優解。傳統PSO算法采用固定的慣性權重,存在早熟收斂、易陷入局部最優等缺點;而自適應粒子群優化(Adaptive Particle Swarm Optimization,APSO)算法通過自適應地調整慣性權重來提高尋優能力和收斂能力?；贏PSO算法框架,本節提出了多用戶多任務的卸載算法。

2.1 自適應權重粒子群算法[21]

慣性權重是PSO算法中調節局部搜索和全局搜索的關鍵參數。慣性權重值越大,收斂速度越快,全局搜索能力強而局部搜索能力弱。APSO對傳統PSO算法的慣性權重進行了改進,使粒子群的運動速度隨系統環境的變化而變化,可以部分克服傳統粒子群算法容易陷入局部最優解的缺點。粒子群能對全局進行充分探測[22],從而提高粒子的全局搜索能力。慣性權重ω的設置如下:

(25)

式中:fj為粒子j的當前適度值,favg和fmax分別為種群粒子的平均適應度值和最大適應度值。適應度越小,說明距離最優解越近,此時更需要局部搜索;適應度越大,說明距離最優解越遠,此時需要全局搜索。與傳統PSO算法相比,APSO的慣性權重與迭代次數及每個粒子的適應度均相關[21]。

2.2 提出的多用戶多任務卸載算法

本節首先構造適應度函數,然后基于APSO提出多用戶多任務的MEC卸載算法。

①適應度函數:觀察P1可知約束條件C1過于復雜,為了簡化求解,將C1并入目標函數中。采用罰函數法,構造粒子的適應度函數如下:

(26)

式中:x代表某粒子。

Penl是懲罰函數,定義為:

(27)

式中:λ>0是懲罰因子。

基于上述適應度函數,構造問題P2:

(28)

根據文獻[23],P2與P1是等價的。

②MEC卸載算法:為了求解P2,基于APSO算法提出多用戶任務卸載算法。算法的每個粒子表示問題的一種潛在解。在5K維解空間中,第j個粒子在第k次迭代中的位置和速度可以表示為:

⑤迭代指數k?k+1;

⑥判斷問題的解是否收斂,若收斂則結束循環,輸出結果,否則轉到②。

上述提出的卸載算法可以優化卸載比例、壓縮比例及帶寬等參數,通過不斷迭代最終獲得最優或者次優解。

2.3 算法復雜度分析

假設一次乘法或者除法的運算量為O(1)。首先,應根據式(1)和式(2)計算上、下行傳輸速率?？紤]到n維矩陣行列式運算的復雜度為O(n3)以及m×n維矩陣SVD分解的復雜度為O(mn2),這一環節的運算量為:

(33)

3 仿真結果與分析

為了檢驗MEC-MIMO網絡中提出的APSO卸載策略的性能,本節首先對算法的收斂性進行分析,其次從用戶設備、任務強度和任務數據大小3個方面對5種計算卸載策略的資源分配算法進行系統任務執行時延的對比,所有策略包括:基于標準的PSO算法的MEC計算卸載(記為PSO)、基于APSO算法的MEC計算卸載(記為APSO)、基于APSO算法數據不壓縮的MEC計算卸載(記為無壓縮APSO)、蒙特卡洛法(記為MCMC)、全部MEC卸載執行策略(記為All MEC)以及全部本地卸載執行策略(記為All local)。這里,蒙特卡洛法是從可行解中隨機選取1 000個樣本,求最優值。

3.1 仿真環境及參數設置

K個用戶隨機分布在以基站為中心、半徑為d的圓形覆蓋區域內。信道建模綜合考慮了大尺度及小尺度2種衰落特征。信道的大尺度衰耗表示為:

Loss(di)=A0+nlgdi,

(34)

式中:di為用戶i到基站的距離,n為衰減指數,A0為固定常數。令Hw,i∈NT×NR,i代表上行鏈路中用戶i與基站的小尺度衰落信道矩陣,其中Hw,i的元素是獨立同分布的、均值為0,方差為1的復高斯隨機變量。則上行鏈路的信道矩陣表示為:

(35)

同理,下行鏈路的信道矩陣可表示為:

(36)

根據用戶數、卸載任務量和計算強度等指標進行仿真分析,仿真中主要用到的參數取值如表2所示。

表2 系統設置Tab.2 System configuration

3.2 結果分析

圖3對APSO算法卸載策略的收斂性進行評估,其中迭代次數設置為100,粒子數N=200?？紤]了用戶設備數K為5和10這2種情況?？梢钥闯?系統時延都隨著迭代次數的增加而降低,2種情況下該算法均具有較好的收斂性。相比于10個用戶,5個用戶下的收斂速度更快、系統時延更低。

圖3 收斂性分析Fig.3 Convergence analysis

圖4展示了設備數對系統總時延的影響?？梢园l現,隨著用戶設備數的增多,任務處理能耗與時延也隨之增加,系統的計算成本逐漸增加,5種卸載策略下的系統總時延均增長。當用戶數K≤15時APSO、PSO、無壓縮APSO和All MEC這4種方案下性能幾乎重合;當用戶數K>15時,APSO明顯優于其他5種方案,但是APSO與PSO整體僅有微小差距。除此以外,當用戶數K>30時,選擇不壓縮數據進行任務執行會耗費更多時間,原因是數據中存在一些多余成分即冗余度,通過對數據進行壓縮處理,可以降低數據大小,從而在較短時間內傳輸數據。

圖4 系統總時延vs.設備數Fig.4 Total system delay vs. number of devices

圖5展示了不同方案下任務計算強度對系統總時延的影響,其中設置UE數K=10,BS天線數及所有用戶的天線數相等設置為4。由圖可知,隨著任務計算強度增大,PSO卸載方案、MEC卸載、無壓縮APSO卸載方案、MCMC卸載方案與APSO卸載方案之間的系統時延差距逐漸拉大,全部本地卸載策略的系統時延遠遠高于其他策略,APSO算法的優化方案相比較于其他優化方案取得了較大的系統性能的提高。這說明,UE傾向于向MEC服務器卸載較多數據量(不是本地計算方式),從而降低任務執行時延。

圖5 系統總時延vs.任務計算強度Fig.5 Total system delay vs. task calculation intensity

圖6描述了不同卸載方案下任務數據量大小與總時延的關系。隨著任務數據的增加,無壓縮APSO、APSO、PSO、All MEC、MCMC卸載方案與All local卸載策略的系統總時延均呈上升趨勢,原因是任務計算量的增加會導致任務在計算過程中消耗更多的能量與時間,但APSO卸載方案產生的時延始終保持最小。在任務強度一定的情況下,PSO與APSO卸載方案效果接近,因此在考慮實踐成本的投入時,可以優先考慮該方案,PSO策略也可做備選方案。

圖6 系統總時延vs.任務數據量大小Fig.6 Total system delay vs. task data volume

4 結束語

針對具備數據壓縮功能的多用戶MIMO-MEC網絡,研究了多用戶任務卸載問題,通過聯合優化任務卸載比例、數據壓縮比例等參數來最小化系統總時延。在能耗、功率和帶寬等約束條件下,將任務卸載歸納為非凸優化問題,并通過構造罰函數將其轉化為一個相對簡單的等價問題。為了求解該問題,基于APSO框架提出了多用戶任務卸載方法。提出的方法根據粒子適應度自適應地調整權重,提高了尋優能力,得到了較好的局部最優解。通過仿真實驗評估所提卸載方法的性能,分析用戶數、任務計算強度等參數對系統性能的影響。結果表明,壓縮因子的優化可以顯著提升系統的性能;提出的方法優于本地計算、傳統粒子群等對比方案,能夠有效降低系統的任務執行時延。