基于多目標(biāo)優(yōu)先級粒子群算法的資源調(diào)度策略

朱新峰，吳名位，王國海

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

0 引 言

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

1 相關(guān)工作

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

2 問題描述

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

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

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

(1)

用戶需要執(zhí)行

n

個任務(wù)

T

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

T

1,

T

2,…,

T

}

(2)

每個任務(wù)需要的資源定義為：

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為單位資源功耗。假設(shè)邊緣云由

m

個智能基站組成，覆蓋范圍內(nèi)有

k

個用戶，每個用戶需要執(zhí)行

n

個任務(wù)，目標(biāo)是找到科學(xué)合理的資源調(diào)度策略，把邊緣云內(nèi)的資源分配給用戶，保證用戶的任務(wù)得到有效執(zhí)行，并滿足以下條件：

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

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

(2)任務(wù)優(yōu)先級

q

。如何滿足不同用戶的不同優(yōu)先級任務(wù)的資源需求也是衡量基站性能的重要指標(biāo)之一。在有限的資源內(nèi)，能覆蓋的用戶數(shù)量也是一定的，如何讓現(xiàn)有的資源盡可能滿足任務(wù)的需求，此時參照任務(wù)優(yōu)先級調(diào)用資源顯得十分重要。

(3)任務(wù)執(zhí)行能耗?；镜哪芎氖且欢ǖ?，也是影響運(yùn)行商利潤的重要因素之一，在提供一定資源量的前提下，建設(shè)消耗每單位資源功耗為(Cost)，則總功耗應(yīng)不小于所有任務(wù)執(zhí)行結(jié)束時的總和。

3 基于多目標(biāo)粒子群算法的資源分配機(jī)制

3.1 標(biāo)準(zhǔn)粒子群算法PSO

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

(6)

3.2 多目標(biāo)粒子群MOPSO

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

3.3 帕累托最優(yōu)理論在多目標(biāo)粒子群算法中的應(yīng)用

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

a

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

4 MPPSO

文中分析在資源有限的MEC中如何實現(xiàn)系統(tǒng)資源的均衡調(diào)度，包括帶寬、功率的資源的聯(lián)合分配，考慮到用戶任務(wù)的優(yōu)先級和全局吞吐量，設(shè)計兩個適應(yīng)度函數(shù)。

4.1 適應(yīng)度函數(shù)設(shè)計

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

N

，用戶序號

i

=(1,2,…,

N

)，每個用戶包含

j

個任務(wù)(

T

)，

j

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

i

可表示如式(7)：

(7)

每個任務(wù)包含

k

個子任務(wù)(

t

)，

k

=(1,2,…,

K

)，則第

i

個用戶的第

j

個任務(wù)可表示為：

(8)

子任務(wù)如式(9)：

(9)

參照香農(nóng)公式，任意子任務(wù)數(shù)據(jù)上行傳輸速率如式(10)：

(10)

則第

i

個用戶的第

j

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

(11)

α

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

(12)

此時

α

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

(13)

此時

α

,,=0，則第

i

個用戶的第

j

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

(14)

考慮邊緣基站資源有限和任務(wù)相關(guān)要求，式(11)和式(14)應(yīng)滿足式(15)和式(16)：

(15)

(16)

綜上，適應(yīng)度函數(shù)

f

=max(

R

,)，適應(yīng)度函數(shù)

f

=min(

E

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

f

=-max(

R

,)。

4.2 粒子編碼和解碼

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

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

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

4.3 MPPSO算法步驟

(1)初始化粒子群，初始化參數(shù)，初始化適應(yīng)度函數(shù)；

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

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

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

K

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

K

；

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

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

(8)結(jié)束算法，此時的粒子群為最優(yōu)集，為邊緣云資源調(diào)度資源提供參考。

5 實驗結(jié)果與分析

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

部分實驗參數(shù)見表1。

表1 部分實驗參數(shù)

續(xù)表1

邊緣基站的調(diào)用頻率對比如圖1～圖3所示。

圖1 基站調(diào)用次數(shù)(MPPSO算法)

圖2 基站調(diào)用次數(shù)(DE算法)

圖3 基站調(diào)用次數(shù)(PSO算法)

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

接下來是子任務(wù)執(zhí)行情況對比，將任務(wù)優(yōu)先級設(shè)定為

P

=3，

P

=2和

P

=1，即數(shù)值越大，任務(wù)優(yōu)先級越高，輸入相同數(shù)量級的任務(wù)，任務(wù)執(zhí)行情況對比如圖4～圖6所示。

圖4 任務(wù)執(zhí)行情況(MPPSO算法)

圖5 任務(wù)執(zhí)行情況(DE算法)

圖6 任務(wù)執(zhí)行情況(PSO算法)

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

總結(jié)上述可以得出結(jié)論：對于一些大型的邊緣計算中心，在用戶活躍度較高且復(fù)雜高級任務(wù)執(zhí)行數(shù)量較多的環(huán)境中，MPPSO更加適合。

6 結(jié)束語

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