基于多目標優先級粒子群算法的資源調度策略

朱新峰，吳名位，王國海

(1.揚州大學 信息工程學院，江蘇 揚州 225100；2.中電科航空電子有限公司 航空電子事業部，四川 成都 610000)

0 引 言

近年來，隨著5G技術的應用推廣，移動邊緣計算(mobile edge computing，MEC)的研究和應用也越來越廣泛。MEC一直被公認為是一種很有發展前景的技術，尤其在觸覺互聯網、物聯網(IoT)和互聯網等下一代互聯網應用領域中，增強現實、無人駕駛等眾多新興領域對延遲提出了更高的要求。MEC將網絡控制、數據處理和相關存儲遷移到網絡邊緣，為覆蓋范圍內的移動用戶提供高可用的密集型計算服務。因此，智能移動終端上可運行對帶寬、存儲和計算高要求的應用任務，同時大大降低傳輸時延，從而提高用戶的無感體驗。但隨著移動網絡和電子信息技術的發展，移動用戶和智能移動終端數量呈爆炸式增長，這為MEC的發展帶來很大的挑戰，尤其是在邊緣基站的計算資源分配方面。邊緣基站計算資源的緊缺性要求盡可能公平地為用戶分配相關資源，如果沒有公平的資源分配，可能無法滿足部分用戶的最小資源需求，造成用戶設備性能下降、用戶體驗差等不良影響。目前，邊緣云均由若干個智能基站組成，因此要實現邊緣云的資源公平分配，就要合理調度邊緣云中每個基站的資源，使得每個基站的資源都可以得到充分利用，從而實現整個邊緣云資源的充分利用，使邊緣云既能滿足用戶使用體驗，又盡可能惠及更多的用戶。合理的資源調度在實現邊緣云充分利用的同時實現了資源的集約化，也為服務提供商帶來了更多的利潤。

1 相關工作

在邊緣云中，如何較好地滿足用戶需求,為用戶提供合理的資源需求是服務提供者需要考慮的重要問題。隨著客戶數量的變化，用戶所需資源量也在不斷變化，或大或小，邊緣云需要有效調度各基站的資源來應對這種變化，同時做到資源的集約化使用，并盡可能滿足每個用戶的資源需求。因此，如何有效調度現有的資源來滿足這些需求顯得至關重要。該文從用戶實際資源需求出發，結合邊緣基站部署結構，設計了MPPSO算法，對用戶任務進行合理分類，把用戶子任務和邊緣基站進行聯合編碼，最終尋找出最優資源調度器。文獻[4]通過在網絡外圍提供云服務減少服務延遲回程負載，并增強相關操作方面的體驗質量。文獻[5]在資源匹配算法中，從資源位置、任務優先級和網絡傳輸成本等方面構建了資源匹配的優化問題，通過添加偽容器將最優問題轉化為加權二部圖的最優匹配問題，實現了邊緣服務器上任務資源匹配的最優策略，有效降低了網絡時延，提高了服務質量。文獻[6]將數據塊的優化布置與任務的優化調度相結合，減少提交任務的計算延遲和響應時間，提高邊緣計算的用戶體驗。文獻[7]基于混合整數線性規劃的云數據中心虛擬機遷移問題，采用支持向量機實現虛擬機在系統間的分配，實現了穩定且低成本的媒體服務。文獻[8]優化了一組虛擬機的平均任務響應時間，提出并求解了有功耗約束的多核服務器處理器的最優時間劃分問題，既優化一組虛擬機的整體性能，又使虛擬機的總功耗不超過一定的可用功率。文獻[9]基于特征粒子群優化的虛擬機初始配置改進離散粒子群優化算法，基于內存利用率、帶寬利用率和虛擬機大小的虛擬機將運營成本和環境影響降到最低。文獻[10]提出的特殊任務的調度算法，使任務選擇合適的邊緣云執行，規劃邊緣云上調度執行順序，使用預測算法應對任務的移動性，在指定的時間內，使得更多的任務得到處理。文獻[11]提出的自適應梯度多目標粒子群算法(AGMOPSO)，采用stocktickerMOG方法更新文檔，提高了算法的收斂速度和邊緣云的計算性能，平衡了AGMOPSO的收斂性和多樣性。

2 問題描述

邊緣云由多個智能基站組成，每個基站具有計算、存儲和帶寬控制等功能，邊緣云向其覆蓋范圍內的移動用戶提供資源服務，每個用戶所需的資源可以有多種。以日常使用的APP為例，一個任務需要多種資源，例如CPU計算、數據存儲和必要的軟硬件。因此，根據不同用戶的需求來制定對應的資源分配策略，把虛擬化資源合理地提供給用戶是現在常用的方法，一套虛擬資源里包含各種資源類型，以滿足用戶的各種需求。

假設用戶為User,用戶群體如式(1)：

User：={User,User,…,User}

(1)

用戶需要執行

n

個任務

T

，則用戶可以定義為：User:={

T

1,

T

2,…,

T

}

(2)

每個任務需要的資源定義為：

T

:={CP,SR,SW,BW,

Co

}

(3)

邊緣云有

m

個智能基站群，如式(4)：

BT:={BT,BT,…,BT}

(4)

每個基站擁有多種虛擬資源，一般如式(5)：

BT:={CP,SR,SW,BW,Co}

(5)

其中，CP為計算資源，SR為存儲資源，SW為軟硬件資源，BW為帶寬資源，Co為單位資源功耗。假設邊緣云由

m

個智能基站組成，覆蓋范圍內有

k

個用戶，每個用戶需要執行

n

個任務，目標是找到科學合理的資源調度策略，把邊緣云內的資源分配給用戶，保證用戶的任務得到有效執行，并滿足以下條件：

邊緣云為用戶提供相應服務時，要綜合考慮各種因素，這里主要考慮以下三個：

(1)數據傳輸速率。對于基站來說，速率的不斷提高可大大降低時延，也是考察邊緣基站的主要性能之一，這對服務提供商來講可以獲得較高的利潤。因此，最好的方式就是合理優化任務分類，盡量將優先級高的任務卸載至邊緣基站，優化資源調度程序，避免信道擁擠和非必要占用，實現所有任務數據傳輸速率總和最大，從而提高基站性能。

(2)任務優先級

q

。如何滿足不同用戶的不同優先級任務的資源需求也是衡量基站性能的重要指標之一。在有限的資源內，能覆蓋的用戶數量也是一定的，如何讓現有的資源盡可能滿足任務的需求，此時參照任務優先級調用資源顯得十分重要。

(3)任務執行能耗。基站的能耗是一定的，也是影響運行商利潤的重要因素之一，在提供一定資源量的前提下，建設消耗每單位資源功耗為(Cost)，則總功耗應不小于所有任務執行結束時的總和。

3 基于多目標粒子群算法的資源分配機制

3.1 標準粒子群算法PSO

PSO算法源自自然界中鳥群覓食的靈感，當鳥在覓食的時候，除了按照自己的目標飛行，還要參照群里其他鳥的飛行軌跡，尤其是靠近食物的那只鳥。在PSO中，每只鳥都被看作是一個粒子，鳥群被看作是粒子群，每個粒子被編碼成一種任務資源調度程序。PSO的主要目標是在迭代更新多次后從種群尋找出最優的粒子，也就是最優的任務資源調度程序，粒子的更新公式如式(6)：

(6)

3.2 多目標粒子群MOPSO

在單粒子群算法中，只要一個適應度函數，在粒子的更新過程中，也在不斷計算粒子的適應度值，然后依次做比較，尋找個體歷史最優值和群體全局最優。在多目標粒子群算法中要面臨兩個主要問題，一是如何選擇pb(個體最優)。在單目標粒子群中，只要對比一下就可以選出pb，但對于多目標，有多個適應度函數,很難判斷誰優誰劣，無法嚴格說明哪個好，哪個差。二是如何選擇gb(全局最優)。在單目標粒子群算法中只有一個gb,但在多目標粒子群中，最優的個體可能有多個，而每個粒子只能選擇一個領導者，這讓很多粒子難以抉擇。針對以上問題，引進帕累托算法理論，調整相關參數，使得多個適應度函數向相同方向遞進，這樣就可以避免個體在尋找最優時背向而行。對于第二個問題，這里使用外部存檔集，將最優解存放至外部存檔集，從中選取全局最優值，以粒子擁擠度來選擇領導者，為了保證粒子的搜索能力，盡量選擇密度小的粒子。

3.3 帕累托最優理論在多目標粒子群算法中的應用

在邊緣云面臨多個目標考量的情況下，很難選擇出一個最優的資源調度程序，無法保證該資源調度程序是否在所有方面都優于其他調度程序。也就是說，假設一共有

a

個適應度函數，假設有資源調度程序A和B，A中的一部分適應度值優于B中的適應度值，但是B剩余部分的適應度值要優于A中的適應度值，此時，就很難確定A和B誰更優。帕累托最優理論可以在多個資源調度程序中對比出誰更優一些。根據這一理論，可以確定，在MPPSO中生成的所有資源調度程序中肯定至少存在一個最優的資源調度程序。假設Si為所提出MPPSO算法產生的資源調度程序，前文介紹了三個性能指標，這里使用其中兩個，即數據傳輸速率和任務執行能耗，在MPPSO產生的資源調度程序中，Si的這兩項指標要優于其他任意資源調度程序。

4 MPPSO

文中分析在資源有限的MEC中如何實現系統資源的均衡調度，包括帶寬、功率的資源的聯合分配，考慮到用戶任務的優先級和全局吞吐量，設計兩個適應度函數。

4.1 適應度函數設計

用戶屬性(user)：用戶數量

N

，用戶序號

i

=(1,2,…,

N

)，每個用戶包含

j

個任務(

T

)，

j

=(1,2,3…)，用戶

i

可表示如式(7)：

(7)

每個任務包含

k

個子任務(

t

)，

k

=(1,2,…,

K

)，則第

i

個用戶的第

j

個任務可表示為：

(8)

子任務如式(9)：

(9)

參照香農公式，任意子任務數據上行傳輸速率如式(10)：

(10)

則第

i

個用戶的第

j

個任務的任務數據上行傳輸速率如式(11)：

(11)

α

,,可篩除未卸載至邊緣基站的子任務。任意子任務卸載至邊緣云處理總能耗為數據傳輸能耗與任務處理能耗之和，如式(12)：

(12)

此時

α

,,=1，未卸載至邊緣基站的子任務功耗如式(13)：

(13)

此時

α

,,=0，則第

i

個用戶的第

j

個任務的任務總能耗如式(14)：

(14)

考慮邊緣基站資源有限和任務相關要求，式(11)和式(14)應滿足式(15)和式(16)：

(15)

(16)

綜上，適應度函數

f

=max(

R

,)，適應度函數

f

=min(

E

,)，為提高算法性能，文中修改

f

=-max(

R

,)。

4.2 粒子編碼和解碼

文中采用子任務長度和基站數量結合的方式進行編碼，單個粒子的長度為子任務個數的兩倍的一維矩陣，矩陣中從首元素至尾元素，每兩元素分別代表子任務的優先級和基站調度序號。例如{3,2,2,1,1,3}，從左至右表示優先級為3的任務在第2個基站執行，優先級為2的任務在第1個基站執行，優先級為1的任務在第3個基站執行。優先級越高，越優先卸載至邊緣云執行，同時盡量使得每個邊緣基站可以均勻調用。

在解碼時，從粒子中提取在邊緣基站執行的子任務排序，綜合考慮每個子任務執行前的子任務在邊緣基站的執行時間和其父任務相鄰的子任務的執行時間，按照優先級的高低依次為每個子任務安排執行時間，執行時間均盡可能早。

粒子的更新公式(6)適應連續變量優化問題，文中為解決非連續變量的非整數優化問題，做了一些優化。主要做法為：將粒子中的每個變量就近取整，因為每個變量的變化范圍均有一定的限制，設計一種以限制值為半徑的圓形策略，當變量超過該半徑時，用梯度下降使變量回到限制范圍內。

4.3 MPPSO算法步驟

(1)初始化粒子群，初始化參數，初始化適應度函數；

(2)初始化外部存檔集，初始化粒子擁擠度；

(3)進入迭代，利用公式(6)開始更新粒子群，根據帕累托最優理論，將符合條件的粒子存入外部存檔集；

(4)對比外部存檔集個數，如果數量小于或等于

K

，則進行步驟5，否則進行步驟6；(5)更新未進入外部存檔集的粒子，根據帕累托最優理論，繼續填充外部存檔集，直到數量等于

K

；

(6)如果達到迭代最大值，或者外部存檔集不再發生變化，停止更新，進入步驟8，否則進入步驟7；

(7)進入步驟3，直到達到迭代最大值，或者外部存檔集不再變換；

(8)結束算法，此時的粒子群為最優集，為邊緣云資源調度資源提供參考。

5 實驗結果與分析

為了驗證實驗效果，采取了對比實驗，分別選取了資源分配常用的DE算法和PSO算法。利用MATLAB2016a作為實驗平臺，PC配置為聯想啟天T5000，16G內存，酷睿i7CPU，Windows10操作系統。邊緣云的資源調度會受到很多因素的影響，比如基站的部署方式、用戶量、基站所處物理環境等，這里為了便于對比和獲得較好的實驗效果，假設三個算法條件相同。但對于多目標優化問題來說，無法通過單一指標確定誰優誰劣，因此采取兩種指標來對比實驗效果，一是在相同用戶量和任務量的條件下，邊緣云中每個邊緣基站的調用頻率，二是在數量相同的，且優先級順序相同的子任務下，觀察最優的資源調度程序按照任務優先級順序執行情況。

部分實驗參數見表1。

表1 部分實驗參數

續表1

邊緣基站的調用頻率對比如圖1～圖3所示。

圖1 基站調用次數(MPPSO算法)

圖2 基站調用次數(DE算法)

圖3 基站調用次數(PSO算法)

綜上對比，在相同的條件下，MPPSO算法可使邊緣云中的邊緣基站調用次數相對均勻，間接證明在MPPSO算法使得邊緣云資源得到了合理的調度。而DE和PSO算法中，均有一個基站調用次數過多，這容易使得某個基站運行過載，或有些任務得不到較好執行，或其他鄰居基站的資源得不到充分利用。

接下來是子任務執行情況對比，將任務優先級設定為

P

=3，

P

=2和

P

=1，即數值越大，任務優先級越高，輸入相同數量級的任務，任務執行情況對比如圖4～圖6所示。

圖4 任務執行情況(MPPSO算法)

圖5 任務執行情況(DE算法)

圖6 任務執行情況(PSO算法)

綜上對比可以看出，MPPSO算法使任務基本是按照任務優先從大至小的順序執行，且執行的大多數是優先級較高的任務，這不僅可以充分保證優先級高的任務優先執行，還可以保證邊緣基站的資源用在關鍵時刻，而其他非必須卸載至邊緣云執行的非高優先級任務則少量卸載至邊緣基站執行。DE算法也是基本優先執行高優先級的任務，但是優先級不高的任務也得到了一定量的執行，這使得一些非必須卸載至邊緣基站的任務也得到了執行，雖然可以降低本地功耗，相對充分利用邊緣云資源，但卻縮小了邊緣基站的利潤空間，增加了任務執行時延，同時還有可能使得一些高優先級任務得不到執行，給用戶帶來不好的使用體驗。PSO算法下的資源分配比較中性，其基本按照任務的數量進行判斷是否需要卸載至邊緣基站執行，實際生活中，中等優先級占大多數，且對各方面資源要求均不太高，高優先級任務和低優先級任務相對不是很多，可以理解成該算法排斥優先級較高和較低的任務，因此，PSO算法一般適用于小型基站，或用戶量不大且對資源要求不高的群體，某種程度講也是一種資源節約。

總結上述可以得出結論：對于一些大型的邊緣計算中心，在用戶活躍度較高且復雜高級任務執行數量較多的環境中，MPPSO更加適合。

6 結束語

移動邊緣計算有助于實現5G新業務超低時延、高能效和高可靠的高密度連接需求。文中主要研究了邊緣云計算中的資源調度問題，將此類問題歸類為多目標優化問題，提出了MPPSO算法，利用數據傳輸速率和任務執行能耗設計了兩個適應度函數。同時，基于邊緣云資源調度特征，聯合用戶和邊緣基站，設計了一種粒子編碼機制，并對傳統的粒子演化機制進行了改進，使其適應于非連續整數變量優化問題，并引入了帕累托最優理論，尋找最優資源調度程序。實驗和兩個在資源分配中的常用算法DE和PSO進行對比，證明MPPSO算法在用戶數量較多，且高級復雜任務較多的邊緣云中表現更好。下一步，將進一步細化任務分類機制，深入研究更復雜的資源分配問題。