基于蟻群算法的移動邊緣服務(wù)器收益優(yōu)化策略

黃冬艷 付中衛(wèi) 李 浪

(桂林電子科技大學(xué)廣西無線寬帶通信與信號處理重點實驗室 廣西 桂林 541004)

0 引 言

隨著5G網(wǎng)絡(luò)的普及，依靠其衍生出來的新型應(yīng)用，如車聯(lián)網(wǎng)、遠程醫(yī)療、虛擬現(xiàn)實、增強現(xiàn)實等得到快速發(fā)展。但由于移動設(shè)備和物聯(lián)網(wǎng)設(shè)備計算能力和電池容量受限，這些新型應(yīng)用和服務(wù)難以部署。為了解決這個問題，近年來研究人員提出了移動邊緣計算[1]。

在移動邊緣計算的架構(gòu)中，邊緣計算服務(wù)提供商在無線接入網(wǎng)邊緣為移動設(shè)備提供云計算能力[2]，從而創(chuàng)造出一個具備高性能、低延遲與高帶寬的電信級服務(wù)環(huán)境。用戶通過將應(yīng)用程序的計算任務(wù)卸載到邊緣服務(wù)器端進行計算，可實現(xiàn)超低計算延遲。

在移動終端進行計算任務(wù)卸載時，為實現(xiàn)如能耗、延遲等性能的優(yōu)化，需要判斷是否將計算任務(wù)全部或部分卸載至邊緣服務(wù)器執(zhí)行，這被稱為計算分區(qū)問題[3]。很多文獻以移動設(shè)備的能耗[4]、應(yīng)用延遲[5-7]和網(wǎng)絡(luò)上的數(shù)據(jù)傳輸量等因素中的一個或多個的組合作為優(yōu)化目標，提出了不同的計算分區(qū)問題模型。

在文獻[4]中，為使設(shè)備能耗或任務(wù)延遲達到最小，作者分別提出了能耗最小、延遲最小的卸載算法，對移動設(shè)備的計算資源、傳輸功率和任務(wù)卸載比例進行聯(lián)合優(yōu)化。文獻[5]在雙時間尺度的情況下，采用馬爾可夫決策過程方法，提出一個一維搜索算法，搜索出最優(yōu)調(diào)度策略，實現(xiàn)了在設(shè)備能耗約束下的計算延遲最小化。文獻[8]以用戶的QoE作為優(yōu)化目標，提出一個近似動態(tài)規(guī)劃算法，找出任務(wù)最佳卸載策略。

然而，文獻[4-5，8]主要研究用戶獨立模型下的計算分區(qū)問題，只針對單個用戶進行計算分區(qū)，而不考慮其他用戶的分區(qū)結(jié)果。在實際過程中，通常會出現(xiàn)多個用戶共同占用邊緣服務(wù)器計算資源的現(xiàn)象。由于移動邊緣服務(wù)器計算資源受限，不能同時接受多個用戶的卸載請求，因此多用戶分區(qū)問題也是移動邊緣計算的研究熱點。

文獻[3]考慮了如SIFT算法這類子任務(wù)執(zhí)行關(guān)聯(lián)性的情況下，多用戶計算任務(wù)的劃分以及云計算資源的調(diào)度，根據(jù)云服務(wù)器的資源占用情況，提出了SearchAdjust算法來解決多用戶分區(qū)問題，使得用戶的平均完成時間最小化。文獻[6]考慮了如何對延遲敏感型應(yīng)用計算分區(qū)和對移動邊緣服務(wù)器資源分配，使得用戶整體延遲達到最小。為解決該問題，設(shè)計了一種多維搜索和調(diào)整算法(MDSA)。文獻[7]研究了多用戶的網(wǎng)絡(luò)感知環(huán)境下，通過對用戶任務(wù)的計算分區(qū)和邊緣服務(wù)器的帶寬資源分配，使用戶的平均吞吐量(應(yīng)用程序每秒處理的數(shù)據(jù)單元數(shù))最大化。

以上文獻主要考慮通過計算分區(qū)技術(shù)使得用戶獲得最大的收益(如最小化計算延遲或能耗)。事實上，為了收回設(shè)備的部署和維護成本并盈利，MEC服務(wù)提供商如何利用有限的計算資源來最大化其利潤，也是一個亟待解決的問題，但是以MEC服務(wù)器收益為優(yōu)化目標的研究較為少見。

本文研究多個用戶對邊緣服務(wù)器端計算資源存在競爭且每個用戶會在本地做出最小化自身成本(計算延遲和花費加權(quán)和)的卸載決策的情況下，MEC服務(wù)器提供商通過采用合適的資源分配策略實現(xiàn)其收益(利潤)的最大化。本文的主要貢獻如下：1) 在用戶子任務(wù)具有順序執(zhí)行的關(guān)聯(lián)性及用戶之間對金錢和延遲的偏好程度不同的場景下，建立以服務(wù)器端任務(wù)執(zhí)行次序為變量的服務(wù)器收益最大化模型；2) 提出基于蟻群算法求解任務(wù)最佳分區(qū)及服務(wù)器端任務(wù)最佳執(zhí)行次序的算法。

1 系統(tǒng)模型及問題建模

1.1 系統(tǒng)模型

為了獲得更好的用戶體驗，當(dāng)執(zhí)行某些延遲敏感型應(yīng)用時，如無人駕駛、增強現(xiàn)實、人臉識別等，用戶會將程序中的某些進程卸載至云端執(zhí)行以獲得更小的計算延遲。

如圖1所示，考慮多個計算密集型任務(wù)占用單個MEC服務(wù)器的重業(yè)務(wù)場景，然后建立多用戶MEC系統(tǒng)模型。該MEC系統(tǒng)由兩部分組成：移動邊緣服務(wù)器和移動客戶端。任務(wù)卸載具體流程如圖2所示。在移動客戶端處，客戶端中間件的監(jiān)視代理程序收集設(shè)備的計算能力、任務(wù)大小等信息，當(dāng)用戶向邊緣服務(wù)器發(fā)送卸載請求時，這些信息隨請求一起發(fā)送到邊緣服務(wù)器端，服務(wù)器端在接收到用戶的請求后，將空閑計算資源分配給請求用戶并為請求卸載任務(wù)進行執(zhí)行排序，然后將資源分配信息反饋至終端設(shè)備，終端設(shè)備在本地做出最小化自身成本的卸載決策。本文中的符號和含義如表1所示。

圖1 多用戶MEC系統(tǒng)

圖2 MEC系統(tǒng)任務(wù)卸載流程

表1 符號及其含義

(1)

本地計算花費為：

(2)

令xi,j=1表示任務(wù)(i,j)在服務(wù)器端計算，其計算時間為：

(3)

(4)

任務(wù)(i,j)在服務(wù)器端計算花費為：

(5)

為保證任務(wù)之間的執(zhí)行順序，令z(i,j),(i′,j′)=1表示任務(wù)(i,j)在任務(wù)(i′,j′)前執(zhí)行，z(i,j),(i′,j′)=0表示任務(wù)(i′,j′)在(i,j)前執(zhí)行。

1.2 問題建模

(6)

IN×(2-xs(o)-xs(k)),k≠o,1≤o≤K；

式中：約束條件C1保證單個用戶各個子任務(wù)間執(zhí)行順序；約束條件C2保證兩個不同用戶子任務(wù)的服務(wù)器端執(zhí)行次序；IN表示正無窮大的數(shù)；約束條件C3保證卸載任務(wù)在服務(wù)器端執(zhí)行時開銷小于在本地執(zhí)行開銷；約束條件C4限制卸載變量xs(k)取值0或1，保證子任務(wù)的本地計算時間、服務(wù)器端等待時間、服務(wù)器端計算時間大于0；約束條件C5保證在邊緣服務(wù)器端閑置的時候，卸載至邊緣服務(wù)器端的計算花費要小于本地計算花費。

2 算法設(shè)計

為求解問題P1，需要在K個任務(wù)的K!個排列集合中，找出令邊緣服務(wù)器端獲得最大收益的一個排列，因此問題P1為組合優(yōu)化問題[10]。解決該類問題可以使用啟發(fā)式算法、近似算法和枚舉法。當(dāng)問題規(guī)模較大時，枚舉法求解時間過長，近似算法難以找出精確解，因此本文采用啟發(fā)式算法中具有較強的全局尋優(yōu)能力和較強的魯棒性的蟻群算法[11]尋找多個請求卸載任務(wù)的最佳執(zhí)行次序。本文算法流程如圖3所示。

圖3 本文算法流程

本文算法具體步驟：

1) 計算在服務(wù)器端資源未被占用時，各個任務(wù)的子任務(wù)最佳分區(qū)決策。

2) 計算服務(wù)器資源占用列表Lcro。

3) 從Lcro中搜索服務(wù)器端的沖突的任務(wù)集合Lcon，其搜索步驟為：

(1) 搜索在Lcro中，最先在服務(wù)器端完成任務(wù)。

(2) 搜素出與此任務(wù)在服務(wù)器端執(zhí)行時間相互沖突的任務(wù)。

(3) 將此任務(wù)與其沖突的任務(wù)放在集合Lcon中。

4) 應(yīng)用蟻群算法搜索出Lcon中沖突任務(wù)執(zhí)行的最佳次序，其執(zhí)行步驟為：

(1) 對相關(guān)參數(shù)進行初始化，信息啟發(fā)式因子α=1、期望啟發(fā)因子β=5、信息素揮發(fā)系數(shù)ρ=0.1、信息素強度Q=100、最大迭代次數(shù)N=500、螞蟻個數(shù)為Lcon中沖突任務(wù)個數(shù)m。

(4) 當(dāng)所有螞蟻經(jīng)過一輪路徑選擇后，對路徑上的信息素濃度進行更新。

(5) 判斷是否達到最大迭代次數(shù)N，若否，返回步驟(3)繼續(xù)循環(huán)；若是，結(jié)束蟻群算法程序循環(huán)，輸出沖突任務(wù)Lcon最終執(zhí)行次序Scon及其收益。

6) 服務(wù)器端任務(wù)執(zhí)行次序S中所包含的任務(wù)為卸載計算任務(wù)，剩余任務(wù)為本地計算任務(wù)，得到各用戶的分區(qū)策略。

算法步驟2)中所述的云端資源占用列表Lcro為包含每個用戶子任務(wù)在云端的開始時刻和完成時刻。

算法步驟4)中螞蟻k隨機選擇下一任務(wù)的概率：

(7)

式中：τi1j1,i2j2(t)為邊(i1j1,i2j2)上的信息素；ηi1j1,i2j2(t)為啟發(fā)式函數(shù)，alloweCk為螞蟻k待訪問的任務(wù)集合。

啟發(fā)式函數(shù)ηi1j1,i2j2(t)的更新規(guī)則為：

ηi1j1,i2j2(t)=revenuei1j1,i2j2/max(revenue)

(8)

式中：revenue為各個子任務(wù)需交付費用集合；

步驟4)中，m只螞蟻完成一次循環(huán)后，各個任務(wù)連接路徑上的信息濃度更新為：

τi1j1,i2j2(t+1)=(1-ρ)×τi1j1,i2j2(t)+Δτi1j1,i2j2(t)

(9)

式中：Δτi1j1,i2j2(t)為所有螞蟻在子任務(wù)(i1,j1)與子任務(wù)(i2,j2)連接路徑上釋放信息素而增加的信息素濃度。Δτi1j1,i2j2(t)的計算為：

(10)

(11)

3 仿真結(jié)果及分析

假設(shè)每個用戶有5個待卸載子任務(wù)，子任務(wù)之間存在順序執(zhí)行的關(guān)聯(lián)性；服務(wù)器端有兩個收費標準可供用戶選擇，每個用戶從兩個收費標準中隨機選擇一個。參照文獻[12-13]，具體參數(shù)設(shè)置如下：向服務(wù)器端發(fā)送請求的用戶總數(shù)在[5，90]范圍內(nèi)；兩收費標準分別為(CPU的單個時鐘周期內(nèi))u0=1×10-9元,u1=0.5×10-9元，每個子任務(wù)所需要的CPU周期在0.1～1 GHz隨機取值，每個設(shè)備的計算能力在1～2 GHz隨機取值。然后，對SearchAdjust算法改進，使得其優(yōu)化目標函數(shù)為邊緣服務(wù)器收益，在相同參數(shù)下對改進的SearchAdjus[3]算法與本文算法進行仿真對比。

仿真時，設(shè)置蟻群的數(shù)量為沖突任務(wù)的個數(shù)大小、迭代的最大次數(shù)為500，信息啟發(fā)式因子為1，期望啟發(fā)因子為5，信息素揮發(fā)系數(shù)為0.1，信息素強度為100，使用MATLAB R2012a版進行仿真。

圖4比較了在邊緣服務(wù)器計算能力為fc=4 GHz和fc=12 GHz的條件下，本文算法與基準算法的邊緣服務(wù)器收益。從仿真圖可得，兩種算法所獲得的收益都隨著用戶的增多而增多，但本文算法的收益增速要大于基準算法。當(dāng)用戶數(shù)目為90、fc=4 GHz時，本文算法的收益相比基準算法提高了33.6%；當(dāng)用戶數(shù)目為90、fc=12 GHz時，本文算法的收益相比基準算法提高了49.9%。這是因為隨著計算能力的提高，相比較SearchAdjust算法，本文算法在各任務(wù)可容忍執(zhí)行期限內(nèi)可以處理更多的任務(wù)。

圖4 不同算法的MEC服務(wù)器收益對比

圖5比較了在邊緣服務(wù)器計算能力fc=4 GHz和fc=12 GHz的條件下，本文算法與基準算法在用戶數(shù)目不同的情況下的每用戶平均延遲。從仿真圖中可得，兩種算法中每用戶平均延遲都隨著用戶增多而增多。當(dāng)用戶數(shù)目為90、fc=4 GHz時，本文算法的每用戶平均延遲相比基準算法增加1.6%；當(dāng)用戶數(shù)目為90、fc=12 GHz時，本文算法的每用戶平均延遲相比基準算法增加了6%。結(jié)合圖4，可以得出本文算法是以犧牲較低的用戶的平均延遲為代價，極大提高了MEC服務(wù)器的收益。

圖5 兩種算法每用戶平均計算延遲

4 結(jié) 語

本文研究了5G網(wǎng)絡(luò)中移動邊緣計算的多用戶分區(qū)問題，以最大化MEC服務(wù)器收益為優(yōu)化目標，提出基于蟻群算法求解服務(wù)器端任務(wù)最佳執(zhí)行次序的算法，以獲得最優(yōu)的任務(wù)分區(qū)策略和最佳任務(wù)執(zhí)行次序。仿真結(jié)果表明，在用戶子任務(wù)具有順序執(zhí)行的關(guān)聯(lián)性及用戶之間對金錢和延遲的偏好程度不同的場景下，本文算法能夠明顯提高MEC服務(wù)器的平均收益。下一步工作將在多個邊緣服務(wù)器相互協(xié)作的場景下，研究用戶QoE約束下的多個邊緣服務(wù)器的收益最大化策略。