基于混合粒子群算法的計算卸載成本優化

周天清 曾新亮 胡海琴

(華東交通大學信息工程學院 南昌 330013)

1 引言

近年來，隨著移動終端(Mobile Terminal,MT)的爆發式增加，以及自動駕駛、人工智能、虛擬現實/增強現實(VR/AR)等急需計算資源且對時延有極高要求的計算密集型業務的不斷增長，給資源受限的移動計算系統和無線通信網絡帶來了前所未有的挑戰[1,2]。

移動邊緣計算(Mobile Edge Computing,MEC)通過將計算和存儲資源部署在網絡邊緣，允許MT將計算任務卸載到邊緣服務器，為用戶提供了超低時延、高帶寬的網絡服務[3]。但是，由于無線和計算資源有限，如果太多的MT將其計算任務卸載到MEC服務器，會導致嚴重的網絡計算擁塞和干擾[4]。超密集異構網絡[5]通過在宏小區中部署更為密集的小基站(Small Base Station, SBS)并與MEC相結合，能進一步縮短MT與MEC服務器間的距離以降低傳輸時延及支持海量鏈接。

時延和能耗作為計算卸載性能評估的重要指標，近年來得到了深入的研究。文獻[6]提出了一種延遲感知計算卸載算法，聯合優化保密配置、計算卸載和無線資源分配，以最大限度地減少整體執行延遲。文獻[7]在超密集網絡場景下對卸載策略、信道資源和傳輸功率進行聯合優化，以最小化系統能耗。文獻[8]建立SBS和宏基站(Macro Base Station,MBS)之間的無線回程鏈路以實現共享頻譜的目的，并最終最小化能耗和執行時間的加權和。但是上述研究或是利用單個MEC服務器來滿足傳入的卸載請求，或是未實現MEC服務器計算資源的合理利用。而對于多MT的場景，MEC服務器很容易擁塞，這將直接影響用戶體驗。

鑒于此，越來越多的研究傾向于多MEC服務器的場景。文獻[9]在多用戶和多MEC服務器場景下，聯合優化計算卸載和資源分配策略以最小化MT能耗。文獻[10]在能量約束下，通過優化卸載決策和計算資源分配以最大限度地降低超密集網絡中MT的計算延遲。進一步，為更合理分配網絡及計算資源，研究者開始關注卸載成本問題。文獻[11]針對非正交多址接入的車載邊緣計算網絡，聯合任務卸載、用戶分簇和計算資源塊聯合優化以最小化任務處理成本問題。文獻[12]研究了基于邊緣計算的車聯網，通過優化任務的卸載時間、無線帶寬分配和計算資源分配來最小化系統的計算與通信成本。文獻[13]為了最小化系統的計算和通信成本，提出了一種具有垂直和水平卸載的4層云邊緣計算系統。雖然文獻[11-13]考慮了任務卸載時所需支付的計算和通信費用，但未連同任務在本地計算時產生的開銷一起考慮。

不同于上述研究，本文研究了融合MEC的超密集異構網絡下多小區多用戶的計算卸載問題，將聯合執行計算卸載和計算資源管理，并在相同的帶寬利用率下最小化用戶的任務處理成本。其中，任務處理成本由本地能耗開銷、無線頻譜占用開銷和邊緣計算資源租用開銷3部分組成。本文的主要貢獻總結如下：

(1)在融合MEC的超密集異構網絡中，將用戶任務處理所需支付的費用作為計算卸載成本，聯合無線資源、計算資源管理，滿足時延約束的同時，使所有用戶的任務處理成本最小化，并建立相應的問題模型。

(2)設計了混合粒子群優化(Hybrid Particle Swarm Optimization, HPSO)算法來解決上述非凸問題，該算法先后執行多樣性增強(Diversity Enhancement, DE)的自適應遺傳算法和自適應粒子群算法。但不同于文獻[14]中的分層自適應搜索(Hierarchical Adaptive Search, HAS)算法，HPSO算法引入了部分參量的規范化處理，且改變了粒子群算法的權重更新規則以提升粒子群算法的收斂速度。此外，與[4,14]不同的是，為更合理地分配MEC服務器的計算資源，HPSO算法改進了遺傳算法中的資源塊初始化操作，并由此引進了計算資源塊按需分配策略。最后，通過仿真驗證了本文所提算法優越性。

2 系統模型

2.1 網絡模型

超密集異構邊緣計算網絡的系統模型如圖1所示，每個六邊形的蜂窩網格包含1個宏基站(MBS)、N個微基站(SBS)和K個MT，并且每個基站配有一個MEC服務器。不失一般性的情況下，本文考慮一個MBS的場景。假設基站的索引集合為N={1,2,...,n,...,N,N+1}，其中MBS的索引為N+1，MT集合表示為K={1,2,...,k,...,K}。

考慮到SBS的小范圍覆蓋和超密集部署，為降低控制開銷，SBS的控制信令可由MBS負責處理。類似文獻[14]，本文亦將頻帶分割為控制面和用戶面，其中控制面用于傳輸控制信令，用戶面用于傳輸數據。由于計算卸載發生在用戶面，因此計算卸載機制研究時僅需關注此平面。在圖1中，MT可以選擇將自己的數據任務上傳至SBS或者MBS上進行處理，亦可自身完成計算任務。值得注意的是，MBS不僅需要處理網格中的所有控制信令，還需處理由MT上傳的數據，而SBS僅需完成數據處理任務。在計算卸載過程中，對于任何任務，如果其本地計算時延小于任務截止時間，MT會選擇本地計算以降低額外開銷，否則MT將任務上傳至基站進行計算以減少時延，保證滿足時延約束。

圖1 系統模型

一般來說，計算卸載包括以下3個階段。首先，MT的計算任務通過無線信道上傳到BS上；然后，BS執行計算任務；最后，BS反饋計算結果給MT。考慮到計算結果的數據量相對較小，反饋過程可忽略不計。

2.2 資源模型

如圖1所示，每個宏小區內所有小基站形成一個簇。為消除層間和層內的干擾，用戶面所用頻帶F被劃分為F1和F2兩部分以分別供宏基站和小基站使用，其帶寬分別為μW和( 1-μ)W，其中μ表示頻帶劃分因子。為了消除宏基站間的干擾，頻帶F1被 再次劃分成3個子帶F11,F12和F13，即相鄰宏小區中的宏基站的頻帶帶寬為μW/3。為了消除小基站簇之間的干擾，頻帶F2同樣被再次劃分成3個子帶F21,F22和F23。進一步，為消除簇內小基站間的干擾，任意簇所用子帶被平分給簇內小基站，即每個小基站可利用的頻帶帶寬為 (1-μ)W/3N。最后，為了再次提升用戶上行傳輸性能，宏小區及小小區內MT間的干擾需要被消除。為此，假設任意基站可利用的頻帶被平分給其所關聯的MT。此外，假設每個MEC服務器提供U個具有相同處理能力的計算資源塊，其索引集合記為U={1,2,...,U}，其中每個計算資源塊的處理能力記為funit。

2.3 通信模型

2.4 計算模型

3 問題建模

顯然，問題P2是非凸優化問題，其目標函數和約束表現為混合整數及非線性的形式。

4 算法設計

遺傳算法有很強的全局搜索能力，但是局部搜索能力較差[15]；而粒子群算法比較簡單，收斂速度很快[16]，但容易陷入局部最優值出現早熟。鑒于兩種算法有著互補的優勢，因此，類似于文獻[4,14]，聯合遺傳算法和粒子群算法來開發HPSO算法以解決問題P2。為了避免過早收斂，提高收斂速度，糅合了基于DE的自適應遺傳算法和自適應粒子群算法，前者用于粗粒度搜索，后者則用于細粒度搜索，算法流程如圖2所示。

圖2 算法流程圖

4.1 遺傳算法

作為一種隨機搜索算法，遺傳算法從一組初始可行解集開始，其關鍵因素及相應步驟如下：

(1)染色體。在問題P2中，優化參量X被編碼成染色體S={sik,?i ∈I,?k ∈K}， 參量λ被編碼成染色體Q={qik,?i ∈I,?k ∈K}， 其中I={1,2,...,I}為個體集群。在任意個體i中，sik和qik分別表示MTk所選擇的基站索引號及所獲取的計算資源塊數，sik=0表示個體i中的MTk不選擇基站，在本地完成計算任務。

(2)適應度函數。考慮到約束C1具備混合整數非線性的形式，在遺傳算法的初始化和基因操作中難以滿足，它被作為一個懲罰項引入適應度函數中。鑒于此，為解決問題P2，個體i的適應度函數被定義為

結合上述遺傳算法因素，基于DE的自適應遺傳算法的完整過程可概述表1。

表1 基于DE的自適應遺傳算法(算法1)

4.2 粒子群算法

在粒子群算法中，粒子(個體)的位置代表問題P2的解，速度則展示解的演化情況。粒子群算法中粒子的初始位置取值為算法1的輸出值。具體而言，粒子群算法的關鍵要素及步驟如下。

結合上述要素，自適應粒子群算法的完整過程可被概述表2。

表3 計算資源塊按需分配策略(算法3)

5 仿真及對比分析

5.1 參數設置

在仿真中，本文主要研究了計算資源塊和無線信道資源的單位價格對不同卸載算法的任務平均處理時延及任務平均處理成本的影響。通過對比任務的平均處理時延和成本及算法的收斂性來論證所設計算法的有效性。為此，引入如下其他算法作為對照組。

全本地算法：所有MT的計算任務都在本地執行；全關聯算法：所有MT的計算任務都卸載到MEC服務器上執行，其中計算資源塊分配方式為隨機分配。此外，在全關聯算法中，本文考慮的是將MT的計算任務卸載到與其對應的信道增益最好的基站上；HGP算法：此算法為文獻[4]中分層的遺傳和粒子群優化 (Hierarchical Genetic and Particle swarm optimization, HGP)算法，其中計算資源塊分配方式為隨機分配；HAS算法：此算法為文獻[14]中的分層自適應搜索算法，其中計算資源塊分配方式為隨機分配。

5.2 結果分析

圖3給出了兩種資源單價的變化對任務平均處理時延的影響。在圖3(a)中，無線資源單價ω2固定為1 元/(MHz·s)，在圖3(b)中，計算資源塊的單價ω3固定為0.1元。可以看到，幾種算法下的任務平均處理時延并不會隨著計算資源塊或無線資源單價的變動而受到影響。這是因為對于在本地計算的任務而言，其處理時延主要取決于任務的數據量和MT的計算能力，而對于要上傳到基站進行計算的任務，其處理時延主要取決于傳輸時的信道狀態和分到的計算資源塊個數。

此外，在圖3中，全本地算法的任務平均處理時延最長，全關聯算法最短，其他3種算法則介于兩者之間。這是由于其他3種算法考慮了任務截止時延的約束，對于無法在截止時延內完成計算任務的MT，這3種算法才會選擇關聯基站，而全本地算法中實際存在著不滿足時延約束的MT。在全關聯算法中，雖然所有任務的時延約束都滿足了，但該算法的任務平均處理成本也是最高的。相比于全本地算法，引入資源塊按需分配策略的HPSO算法的任務平均處理時延縮短了約25%，資源塊隨機分配策略下的HAS算法則更低。這是因為這兩種算法都滿足了時延約束(由圖5(b)可驗證)，但在隨機分配策略下，計算資源塊可能存在額外分配的情況。因此，HAS算法下任務平均處理時間會更短，這也意味著HAS算法的開銷會更高。

圖3 單價變化對任務平均處理時延的影響

圖4為兩種資源單價的變化對任務平均處理成本的影響。在圖4(a)中，隨著計算資源塊單價的增加，除全本地算法外，其他算法的任務平均處理成本都相應地增加了。雖然全本地算法的任務平均處理成本最低，但是它不能保證所有任務都滿足時延約束。隨機分配策略下的全關聯算法的任務平均處理成本最高，這是因為所有MT都選擇將任務上傳至基站進行計算，甚至是一些滿足時延約束，可以在本地完成計算的任務。另外，可以發現，引入資源塊按需分配策略的HPSO算法是使得任務平均處理成本最低的算法。

表4 實驗參數

在圖4(b)中，引入資源塊按需分配策略的HPSO算法依舊是任務處理成本最小的算法。此外，會發現隨著無線資源單價的不斷提高，HGP算法的任務平均處理成本逐漸逼近甚至高于全關聯算法。這是因為隨著無線資源單價的提高，傳輸費用會成為任務處理的主要開銷。結合式(10)也不難理解，雖然在全關聯算法中或許將一部分可以在本地進行計算的任務上傳到了基站，但每次選擇的都是對應信道增益最好的基站，而HGP算法由于無法找到一個合適的解(由圖5(b)可驗證)，最后得到的卸載決策可能并不理想。因此，最終會導致HGP算法下的任務平均處理成本逐漸逼近甚至高于全關聯算法。

圖4 單價變化對任務平均處理成本的影響

圖5給出了適應度值在遺傳和粒子群算法部分的收斂變化情況。從圖5(a)可以發現，在有限的迭代次數內，HGP算法中傳統的遺傳算法難以求解P2這一混合整數非線性規劃問題。而相較于HAS算法中改進的遺傳算法，HPSO算法中的自適應遺傳算法由于一開始引入計算資源塊按需分配策略，使得資源約束條件變得更為苛刻。因此，初始化時最優個體的適應度值較高，但在迭代過程中會快速收斂。

在圖5(b)中，HGP算法中傳統的粒子群算法在迭代求解過程中依舊沒有找到合適的可行解。相比于會對全局最佳粒子的速度和位置進行更新的自適應粒子群算法，HAS算法和HPSO算法中的自適應粒子群算法最終都能收斂。此外，容易發現，采用非線性慣性權重的HPSO算法相比采用線性慣性權重的HAS算法收斂速度明顯更快，并且最終的收斂結果更好。

圖5 適應度值的搜索情況

6 結束語

本文研究了超密集異構邊緣計算網絡中任務處理成本最小優化問題。具體而言，在延遲和計算資源約束條件下，聯合優化了計算卸載和MEC服務器的計算資源塊分配以使用戶的任務處理成本降最小。在此之前，一個有效的頻帶劃分方案被引入以用于消除平面間、層間和層內的干擾。考慮到最終所規劃的問題具備非線性且混合整數形式，同時為滿足問題約束條件及提升算法收斂速度，本文改進HAS以獲取HPSO算法。仿真結果表明，同其他卸載算法相比，HPSO算法在減少任務處理成本方面具有顯著的優勢。