分層學習的邊緣計算資源調度粒子群優化算法

胡曉敏，陳鎮填，李 敏，2

1.廣東工業大學 計算機學院，廣州 510006

2.廣東工業大學 信息工程學院，廣州 510006

隨著物聯網行業的發展，智能移動設備的數量快速增長，相應的智能移動應用服務程序也越來越多，在教育、商業、游戲、安全和醫療保健等各個領域都有相關的智能移動應用程序[1]。這些應用程序要求設備提供較高的服務質量，如低延遲、數據安全和隱私保護，并且一臺智能移動設備上往往會運行多種應用程序，對設備的硬件條件，特別是設備的計算能力和電池容量提出了較高的要求。然而，智能移動設備具有便攜性和移動性的特點，其硬件條件無法滿足應用程序的服務質量需求。邊緣計算技術為解決智能移動設備在計算資源和能耗上的需求提供了手段。

邊緣計算是指在網絡邊緣執行計算的一種新型計算模型[2]，通過使用部署在網絡邊緣的設備（如工作站、通信基站等）對終端設備（如智能家居、移動設備等）產生的數據進行處理，由邊緣計算設備提供計算能力，大大降低了對終端設備的硬件要求。如何更有效地利用邊緣計算設備的資源，降低終端設備的能耗，成為了邊緣計算資源調度的核心問題。針對這一問題，越來越多的研究人員通過研究計算卸載決策（computation offloading decision）和資源分配（resource allocation）這兩個方面來減少設備的能源消耗。Yang等人[3]在一個多服務器，多用戶設備構成的計算模型中，針對移動設備能耗問題提出了改進的分支定界算法，從卸載決策和計算資源這兩方面進行優化，降低移動設備的能源消耗。Guo等人[4]則提出了一種基于計算算法的遺傳算法（genetic algo‐rithm based computation algorithm），用于多服務器和多用戶設備組成的邊緣計算模型的能耗優化問題，通過卸載決策，信道分配和資源分配這三個方面來降低用戶設備的能源消耗。Huang等人[5]提出多用戶合作的移動邊緣計算卸載系統，移動設備不僅可以將計算任務卸載給邊緣服務器完成，也可以選擇卸載給其他空閑的移動設備。為了降低移動設備計算能耗，作者提出了一種基于蟻群算法的雙層優化方法，對移動邊緣計算中的任務卸載決策和資源分配問題進行聯合優化，在滿足延遲約束下使得所有移動用戶的總消耗最小化。

在邊緣計算能耗優化問題上需要對多方面資源進行合理的調度，如網絡信道分配、數據分流比例和計算資源分配，并且還會考慮最大延遲等多方面約束。因此邊緣計算的能耗優化問題是一個復雜的非線性規劃問題[6]，傳統的數學優化算法無法在合理的時間內得到其最優解。

模擬自然界群體協作尋優的群體智能算法，憑借其強大的全局搜索能力和尋優能力，更少的計算代價和更快的收斂速度被廣泛應用。其中粒子群優化算法具有收斂速度快，設置參數少等特征，是求解一些實際工程問題的首要選擇。根據利用粒子群算法優化計算卸載問題的方式，已有的做法可以分為三類：第一類是對粒子群算法的操作進行改進。如Adhikari等人[7]提出的加速粒子群算法，使用全局最優個體來更新個體的速度和位置，目的是提高算法的收斂速度。Deng[8]和Wang[9]等人改進了粒子群算法的慣性系數計算公式，根據粒子的適應度值動態地改變慣性系數。第二類是把粒子群算法與其他進化算法相結合。如Chen等人[10]將粒子群算法與遺傳算法相結合，解決卸載深度網絡中間層的決策問題。第三種是利用粒子群算法解決任務卸載問題中的子問題。如Zhou等人[11]為解決超密集異構網絡中的計算卸載問題，先采用遺傳算法進行粗粒度搜索，再用粒子群算法進行細粒度搜索得出最優的計算卸載決策。Xue等人[12]提出粒子群和遺傳算法相結合的算法用于大型深度神經網絡的遷移決策問題，提出層合并上傳算法解決上傳問題。Liu等人[13]則將概率任務卸載問題分解成多個無約束子問題，使用粒子群算法去求解每個子問題從而得到概率任務卸載問題的最優解。

然而，上述提到的研究中都只是研究如何降低智能移動設備端的能耗和網絡傳輸的能耗，很少將邊緣服務器端的能耗作為優化目標。對于提供云計算服務的企業來說，他們需要考慮如何充分利用服務器的計算資源，降低服務器的能耗，增加機器的使用時間，減少企業成本。受此啟發，針對優化資源配置，減少設備能耗問題，本文對與計算任務和計算能耗的相關參數進行建模，將降低服務器能耗作為優化目標之一，提出了與移動設備計算能耗、數據傳輸能耗和邊緣服務器計算能耗相關的總能耗公式，并且增加了對邊緣服務器相關計算資源的限制作為新的約束條件，如邊緣服務器的存儲約束，最大能耗約束和CPU周期約束。

本文采用粒子群算法對總能耗優化問題進行求解，優化每臺移動設備對于移動設備的計算速度，下載數據功耗，數據卸載百分比和剩余網絡帶寬占這四個參數的取值，更合理分配計算資源使得總能耗最小。針對粒子群存在容易陷入局部最優和種群多樣性低等問題，本文引入分層學習策略對算法進行改進，通過分層學習的方式保存種群粒子的多樣性和提高算法全局搜索能力，并將改進的算法稱為基于分層學習的粒子群算法（levelbased learning swarm optimizer，LLSO）。

1 問題建模

1.1 系統模型

考慮到智能移動設備有限的計算資源，無法按需求完成計算任務，需要將部分或者全部計算任務傳輸給邊緣服務器處理，因此提出了用于聯合優化的計算分流系統模型，如圖1所示。在圖1中，假設存在M臺智能移動設備和S個支持上行和下行功能的傳輸通道，M臺智能移動設備可以通過S個傳輸通道發送自己的計算數據和接受邊緣服務器的計算結果，并且傳輸通道之間不存在干擾。優化算法會收集智能移動設備和邊緣服務器的硬件資源信息，并且收集移動設備需要運行的計算任務和相關約束，在滿足所有約束條件的情況下，如計算延遲約束，移動設備和服務器的最大能耗約束等，決定每臺設備最優的執行方案，合理地調整計算資源和規劃計算任務卸載比例，從而能夠消耗最少的移動設備計算能耗，傳輸能耗和邊緣服務器計算能耗。

圖1 計算卸載系統模型Fig.1 Computation offloading system model

1.2 能耗優化建模

智能移動設備和邊緣服務器的總能耗是由每臺智能移動設備的本地計算能耗ELm，服務器處理每臺智能移動設備分流數據產生的計算能耗ECm以及數據傳輸過程產生的傳輸能耗ηm這三個方面構成，計算公式如下：

每臺智能移動設備的本地計算能耗ELm與設備的計算功率和工作時長有關[14]，用PLm表示單臺智能移動設備的計算功率，用tLm表示單臺智能移動設備的工作時長，因此可以得到本地計算能耗ELm的計算公式為：

以上公式中計算功率與智能移動設備的計算速度有關。用fm表示編號第m臺智能移動設備的計算速度，單位cycle/s，因此，智能移動設備的計算功率可以通過下面的公式計算得到：

其中，kL為智能移動設備芯片結構相關的一個常數，其值與移動設備的硬件條件相關。

工作時長與智能移動設備需要處理的計算數據量和數據復雜性相關，數據量越多，數據的復雜性越大，計算速度越慢，需要的工作時長就越長。根據文獻[15]，使用Im表示第m臺智能移動設備需要計算的數據量，使用一個常數α來表示所有計算數據的復雜性。由于模型中會將部分數據分流到服務器去計算，因此使用λm表示第m臺智能移動設備在本地計算的數據量占總數據量的比例，其取值范圍為[0，1]。根據以上關系，可以得到智能移動設備的工作時長計算公式如下：

單臺智能移動設備的計算能耗根據公式（2）~（4）化簡之后如下所示：

可見單臺智能移動設備的計算能耗與智能移動設備芯片結構，智能移動設備的計算速度，需要計算的數據量和數據的復雜性有關。假設每臺智能移動設備的電池容量有限，用ELmax表示每臺智能移動設備能夠用于計算的最大能耗，因此每臺移動設備在處理數據所消耗的能源需滿足：

與智能移動設備本地的計算能耗類似，邊緣服務器的計算能耗也是通過邊緣服務器的功率P和計算時間tCm的乘積計算得來，經相同的推導和化簡后如公式（7）所示。在公式（7）中，用ECm表示服務器處理第m臺智能移動設備分流數據產生的計算能耗，而第m臺智能移動設備會保留λm的數據量在本地計算，所以服務器需要處理的數據量是(1-λm)·Im。具體公式如下：

其中，kC是與邊緣服務器芯片結構相關的一個常數，fC表示邊緣服務器的計算速度這兩個參數都與服務器的硬件條件相關。用ECmax表示服務器的最大能耗限制，因此，服務器在處理所有移動設備的數據產生的能耗要滿足：

同時，對于邊緣服務器接收M臺智能移動設備傳輸過來的總數據量也有一定的限制，通過服務器最大CPU周期數Amax和服務器最大內存存儲空間Gmax來表現，具體約束如下：

其中，α表示數據量的復雜性，而ζ表示每比特的數據所占用的內存空間。

對于第m臺智能移動設備在傳輸數據到服務器的過程中的數據傳輸能耗ηm計算公式如下：

這個公式求和的兩個部分分別代表數據傳輸中的上行鏈路能耗和下行鏈路能耗。其中，PIL表示智能移動設備的閑置功率，kTL表示智能移動設備傳輸數據的增強系數，PTm表示智能移動設備傳輸數據的功率，PDL表示智能移動設備下載數據的功率，下標L代表這些參數跟本地智能移動設備相關。

γm表示第m臺智能移動設備在每條傳輸通道上所占用的帶寬比例，其取值范圍為[0，1]，為確保最大限度地利用帶寬，γm需要滿足：

tU表示智能移動設備上傳數據所需要的時間，tD表示數據從服務器傳回智能移動設備的時間。tU、tD分別通過以下公式計算：

其中，RUm和RDm分別表示上行鏈路的和下行鏈路的信道傳輸速率，β1、β2分別表示在上傳和下載數據過程中的額外開銷。

數據傳輸能耗與傳輸時間有關，而數據傳輸時間跟信道傳輸速率相關。信道傳輸速率與數據占用的信道帶寬W，數據傳輸功率PT和噪聲干擾功率N0相關。在數據傳輸過程中存在干擾而導致信道衰弱現象，假設該模型的數據傳輸信道為瑞利衰落信道。根據文獻[14]，上行鏈路和下行鏈路的傳輸分別在不同的頻率上進行。數據傳輸之間的路徑損耗用(dm)-v表示，dm表示第m臺智能移動設備到服務器的距離，v則表示路徑衰減指數。h1、h2分別表示上行鏈路和下行鏈路的信道衰減系數。因此，鏈路的信道傳輸速率為通道數量S，傳輸帶寬占比γm，鏈路帶寬W，與數據傳輸功率衰減和噪聲干擾有關的對數函數的乘積。上行鏈路的速率RUm和下行鏈路的速率RDm的計算公式為：

其中，S表示通道數量。WU和WD分別表示上行鏈路和下行鏈路的帶寬。PTC表示服務器的傳輸數據的功率，N0表示高斯白噪聲的功率。以上這些參數的取值都與對應的物理網絡設備有關。

智能移動設備將部分數據分流給服務器完成計算的時間tC的計算如公式（17），該時間包括數據上傳時間tU、數據下載時間tD和服務器處理第m臺智能移動設備數據的時間tCm這三部分。

其中，上傳數據時間tU和數據傳回時間tD由公式（14）和（15）計算得到，而服務器處理數據的時間tCm與需要處理的數據量有關，具體計算公式如下：

大多數智能移動設備上的應用程序都有相應的延遲需求，最大完成時間包含兩個方面，一方面是智能移動設備本地計算的時間tLm，由公式（4）計算得到，另一方面就是智能移動設備將部分數據卸載到服務器完成計算的時間tC。由于這兩方面的計算是并行進行的，花費時間較多的那部分時間視為該計算任務的最終完成時間，因此該計算任務的最終完成時間需要滿足：

其中，Lmax表示應用程序的延遲限制，即智能移動設備處理數據的最大完成時間。

2 基于分層學習的粒子群算法

粒子群算法因為其結構簡單，收斂速度快等特點，受到國內外大量的研究，并應用到與各種實際問題中[16-17]。但是在解決復雜的約束問題時，粒子群算法存在容易陷入局部最優和缺失種群多樣性等問題。因此，本文采用了分層學習的策略來對傳統的粒子群算法進行改進，提出了利用基于分層學習的粒子群算法（levelbased learning swarm optimizer，LLSO），來提高PSO面對復雜優化問題時的全局搜索能力和種群多樣性。

2.1 優化目標函數

本文的優化目標是最小化如公式（1）所示的所有本地設備的計算能耗，數據傳輸能耗和邊緣服務器計算能耗的總和。由于同時還需要滿足各種約束，如延遲約束，服務器存儲約束，移動設備和服務器最大能耗約束以及傳輸網絡的帶寬約束，本文將所有的約束條件轉化成對應的懲罰函數，因此優化目標是最小化總能耗和懲罰函數值的和，即：

其中，Ω表示所有懲罰函數值的總和，N為正整數，表示懲罰函數的權重，x代表問題的解。

懲罰函數Ω的計算方式如下：

其中，y1、y2為指數常量，分別取值為2和1。gp(x)表示不等式約束的懲罰函數，p=1,2,…,5。hq表示等式約束的懲罰函數，具體公式如下：

公式（22）到（27）分別是由移動設備最大能耗約束（6），服務器最大能耗約束（8），服務器CPU計算周期約束（9），服務器存儲約束（10），延遲約束（19）和帶寬約束（12）轉化的各類懲罰函數。對于不等式約束，如果差值小于0，說明沒有違反約束情況，懲罰值設為0，若差值大于0，說明違反了約束條件，將差值設為懲罰值。對于等式約束，差值不等于0表明違反約束，并用差值的絕對值表示懲罰值。

2.2 個體編碼

LLSO算法的解向量x表示當前所有智能移動設備的資源分配情況，由智能移動設備相關的四個參數構成：智能移動設備的計算速度fm，智能移動設備下載數據的功耗PTm，計算數據卸載百分比λm和剩余網絡帶寬占比μm。假設智能移動設備的數量為M，向量x的長度是4M，其中第1到M的元素存放每臺智能移動設備的計算速度fm，接下來的M個元素存放智能移動設備的功耗PTm，接著存放M個分流百分比λm，最后的M個位置存放 參 數 μm，最 終 向 量x的 編 碼 方 式 如 下x=(f1,f2,…fM,PT1,PT2,…,PTM,λ1,λ2,…,λM,μ1,μ2,…,μM)。算法通過不斷迭代優化，調整設備的計算功率參數，數據卸載比例以及傳輸網絡帶寬比例，最終輸出的結果就是能耗最低的資源分配方式。同時LLSO算法中每個粒子會維護一個速度向量v。速度向量v是保存每個粒子的速度，表示資源分配變化的范圍，向量v的長度也是4M，分別存放著每臺智能移動設備不同參數對應的不同速度值。

2.3 算法流程

在算法開始運行前會先進行初始化粒子操作，在四個參數不同的取值范圍內隨機生成一個浮點數。四個優化參數對應取值范圍為fm∈[0,fmax]，PTm∈[0,Pmax]，λm∈[0,1]，μm∈[0,1]。其中fmax表示智能移動設備的最快計算速度，Pmax表示智能移動設備最大傳輸功率。在初始化完成后，會先將參數μ換算成每臺智能移動設備真實的帶寬占比γ，計算方法如下，其中γ1=μ1：

換算完成后，還會對參數λ和參數γ之間的數據關系進行一個判斷：如果當γ的值為0時，說明某個智能移動設備沒有使用帶寬通道去傳輸數據給服務器計算，表示所有數據必須在智能移動設備上計算，因此需要將對應的參數λ的值修改為1。最后更新粒子群的全局最優粒子。

在進化的過程中，不同適應度的粒子在局部尋優和全局尋優中有著不同的作用[16]，因此將它們區別開來，根據適應度的不同劃分不同的層次。分層學習策略先將種群按照適應度值的大小進行排序并進行分層操作，層數較低的粒子在進行更新操作時，學習的對象是層數較高的任意一個粒子。這種方法促使粒子向比自身更優的粒子學習，同時也保留了搜索的多樣性。

假設種群的數量為NP(number of particles)，將該種群按照適應度的大小分為NH(number of height)層，每一層用Hi(1≤i≤NH)表示，那么劃分到同一層的粒子數量為HS(height size)，并且HS=NP/NH。如圖2所示，將初始化之后的種群按照目標函數值從小到大進行排序，然后按順序每HS個粒子劃分為一層，其中前HS個粒子劃分為第一層H1，最后HS個粒子劃分到最后一層HNH。

圖2 分層學習策略Fig.2 Strategy of level-based learning

在分層操作完成后進行算法的個體更新操作，與傳統的PSO算法按下標順序更新粒子不同，LLSO算法是從層級最低，即位于HNH層的粒子開始更新，再更新層級較高的粒子。在更新操作中，假設位于第i層中的第j個粒子xi,j,1

其中，r1、r2、r3都是在[0，1]中隨機生成的隨機數，而?是控制參數，主要影響粒子xl2,k2的更新效果，其取值范圍在[0，1]。

LLSO算法的偽代碼如算法1所示。第1行初始化粒子群，在參數的取值范圍內隨機生成浮點數，第2行根據公式（20）計算每個粒子的適應度值，并初始化全局最優粒子。第4到15行是算法的迭代優化過程：第5行進行分層操作，第6到13行對每個粒子進行更新操作，對于每個待更新的粒子，首先選取層級較高的兩個粒子，再根據公式（29）、（30）更新該粒子的速度信息和位置信息，最后再更新粒子的適應度值。第14行在更新完粒子后重新比較每個粒子的適應度值，更新全局最優粒子。第16行輸出最終的優化結果。

算法1基于分層學習的粒子群算法

輸入：種群大小NP，分層數量NH，控制參數?，最大適應度評估次數MAX_FES

輸出：全局最優個體

1.初始化粒子群，計算每層劃分的個體數量，令fes=0

2.計算種群中所有粒子的適應度值，初始化全局最優粒子

3.fes+=NP；

4.while fes

5. 按照粒子適應度值大小進行分層操作；

6. For i=NH to 2 do

7. For j=1 to HS do

8. 隨機選取層級較高的粒子xl1,k1,xl2,k2作為進化榜樣；

9. 根據公式（29）、（30）更新粒子xi,j的速度信息和位置信息；

10. 計算粒子新的適應度值；

11. End For

12.fes+=HS；

13. End For

14. 更新全局最優粒子；

15.End while

16.輸出全局最優個體

3 實驗

3.1 實驗介紹和參數設計

為了驗證LLSO算法在解決邊緣計算資源調度問題上的性能，本文將使用LLSO算法用于移動設備的能耗優化問題。實驗會測試LLSO算法對于不同移動設備數量情況下的優化性能，因此本次實驗中智能移動設備的數量的取值范圍為[5，10]。而本次實驗的模型參數，即目標函數中與智能移動設備和服務器相關的常數參數，根據文獻[18-19]，做出以下設置，如表1所示。

表1 目標函數參數默認值Table 1 Default values of parameters of objective function

LLSO中引入了兩個參數，分層的數量NH和控制參數?。NH大小影響進化過程中種群的多樣性，控制參數影響著粒子xl2,k2在進化過程中的影響力，而該粒子具有更多的全局尋優潛力。因此這兩個參數會影響LLSO算法的整體表現，根據文獻[17]，將這兩個參數設置為NH=4、?=0.4。種群數量NP=100。

同時為了驗證LLSO算法在優化結果和優化速度上的優勢，本文選擇其他具有代表性的啟發式算法對同一個問題同時進行優化，并比較它們的優化結果。選取的算法如下：模擬退火算法（SA）[20]、遺傳算法（GA）[21]、粒子群算法（PSO）[22-23]，基于模擬退火的粒子群算法（SA-based PSO，SAPSO）[24]和基于遺傳模擬退火的粒子群算法（genetic simulated-annealing-based particle swarm optimization，GSP）[25]。對比算法的參數設置如下：根據文獻[25]，GSP算法中的初始溫度參數設為108，降溫速率為0.95，變異概率為0.01，慣性權重的取值范圍為[0.4，0.95]，加速因子1.496，學習因子0.5。SA算法的初始溫度為108，降溫速率為0.95。GA算法中的交叉概率為0.8，變異概率為0.01。根據文獻[26]，PSO算法中加速因子c1為1.85，加速因子c2為2，慣性權重的取值范圍為[0.38，0.99]。

3.2 實驗結果

表2的數據是六種算法在不同數量的移動設備的情況下獨立運行100次的能耗優化的結果，每種算法在目標函數評價達到200 000次時停止優化，并且用可行解概率來表示每種算法在100次獨立運行中得到可行解次數百分比，即可行解懲罰值為0的結果。從表2的結果可以看出，在100次獨立運行中，本文提出LLSO算法的能耗優化結果比其他五種算法的優化結果較好，并且在所有不同移動設備數量情況下LLSO算法的可行解概率都能達到100%。當移動設備數量較少時，如M=5和M=6時，所有算法都能求出可行解，其中GA和GSP算法的能耗平均值與LLSO算法比較接近，但LLSO算法的能耗優化結果最低。當移動設備的數量增多時，如M=9和M=10時，SA和PSO這兩種算法的可行解概率都低于20%，說明這兩種算法在移動設備數量較多的優化模型中已經無法適用，GSP、GA和SAPSO四種算法的可行解概率低于90%，而LLSO算法的可行解概率仍是100%。

表2 六種算法在不同移動設備數量的優化結果Table 2 Optimization results of six algorithms in different number mobile devices

圖3展示的是六種算法在六種不同移動設備的情況下的能耗優化收斂趨勢圖，其收斂曲線展示的是100次獨立運行的平均值收斂情況。從圖中可以看出LLSO算法在所有情況下的平均優化結果都優于其他五種算法，在20 000次評價次數的時候已經接近收斂。GSP算法與LLSO的收斂趨勢比較接近，但GSP算法的優化結果沒有LLSO算法好。GA算法的收斂速度最快，在第5 000次迭代的時候就接近收斂，收斂結果與GSP算法相同。當移動設備數量較少時，GA算法的優化結果與LLSO算法的優化結果相近，相差不到0.1，但當移動設備數量增多時，優化結果的差距逐漸增大，當M=10時，LLSO算法的優化結果比GA算法提高10%左右。SA、PSO和SAPSO算法與LLSO算法相比優化結果較差，并且在M大于7時這三種算法的收斂曲線出現波動，說明這三種算法在移動設備數量較多時無法優化出滿足約束條件的結果，導致能耗值收斂曲線出現上升的現象。

圖3 六種算法能耗值優化收斂圖Fig.3 Energy consumption optimization convergence diagram of six algorithms

圖4展示的是六種算法在不同移動設備情況下100次獨立運行的能耗優化結果的分布情況。從圖中可以看出，LLSO算法的結果最好，優化結果分布最為集中，說明LLSO算法的表現穩定，并且能耗平均值和中位數都比其他四種算法較低。GA算法和GSP算法的結果分布情況相近。而SA、PSO和SAPSO算法的優化結果分布較差，其中PSO算法在不同數量移動設備情況的優化結果的分布范圍比其他算法的大，可以看出PSO算法的優化結果不穩定。

圖4 六種算法優化結果分布對比Fig.4 Comparison of optimization results distribution of six algorithms

4 結束語

隨著物聯網行業的發展，智能移動設備越來越普及，但是移動設備因其便攜性和移動性的特點，使得移動設備無法滿足對于計算資源要求較高的應用程序。而邊緣計算技術為解決這一問題提供了解決方案，通過將部分任務分給邊緣服務器完成來滿足應用服務的計算需求。而如何制定計算卸載決策，合理分配資源，成為邊緣計算資源調度中一個挑戰。因此本文提出了一種移動設備計算卸載模型，通過調整計算卸載的比例和計算資源的分配，使得所有移動設備和邊緣服務器消耗的總能量達到最小，并使用基于分層學習的粒子群算法來優化這一問題，并通過對比實驗證明該算法比其他優化算法獲得了具有更低的能耗的解。本文的未來工作包括設計新的搜索模式用于算法求解大規模問題，提高移動設備數量較多時算法得出可行解的能力。