基于移動邊緣計算環境下的服務緩存和任務調度聯合優化算法

杜建華，王立俊，謝寒生,趙卓寧, 王雙雙

(1.海南省氣象信息中心，海口 570203；2.成都信息工程大學，成都 610225；3.海南省南海氣象防災減災重點實驗室，海口 570203)

0 引言

物聯網以及無線通信技術的推陳出新，使得各種移動相關應用呈爆炸式發展勢頭。大量的計算密集和時間敏感型應用，在通信資源和計算資源方面對網絡基礎設施提出了更高的要求。而傳統云計算框架中，網絡帶寬因終端設備與云中心服務器之間要處理大量數據上傳、處理和結果的回傳，承受巨大的壓力。為提高資源效率和用戶體驗，移動邊緣計算(MEC,mobile edge computing)框架能夠給予移動終端以任務卸載支持，使得云計算服務從集中云擴展至網絡邊緣，在近端提供資源的同時有效降低了服務延遲。需要注意的是，邊緣設備在通信、計算、存儲資源等方面具有一定的局限性，尤其是當終端用戶的任務需求激增時。大量終端用戶向邊緣設備卸載任務，會造成邊緣設備資源緊張、負載過重和任務處理時延的增加，影響任務處理的時效和用戶體驗。此外，各邊緣設備間的負載不均衡現象會進一步加劇，部分閑置的服務資源無法被充分利用。

為了給終端用戶提供更準確、更精確粒度的服務，一些基于移動邊緣計算的服務緩存策略被提出。文獻[10]對支持MEC的密集蜂窩網絡中的動態服務緩存策略進行了研究，提出了一種高效的基于聯合優化動態服務緩存和任務卸載的在線算法。文獻[11]針對MEC系統在服務異構性、空間需求耦合和分散協調等方面存在的問題，基于MEC的密集小區網絡中的協作服務部署方法進行了分析，提出了一種高效的分布式算法。文獻[12]研究了具有多維約束的服務部署和請求路由的聯合優化問題，提出了一種使用隨機取整實現接近最優性能的算法。為實現更可行的邊緣資源分配，文獻[13]提出了齊次條件下的常數因子近似算法和一般條件下的啟發式算法來解決緩存服務放置和任務請求調度問題。文獻[14]引入卸載成本模型來捕獲用戶能耗、服務緩存成本和云使用成本，利用局部搜索技術設計了一個多項式時間迭代算法COSTA。為了充分利用邊緣節點的存儲和計算能力，文獻[15]針對邊緣節點之間的協作服務緩存和工作負載調度問題建立數學模型，并設計了迭代算法來解決上述混合整數非線性規劃問題。從上述研究工作可以看到，邊緣設備之間的協作能夠更高效地利用各設備的通信、計算和存儲資源。計算任務卸載決策需要對眾多終端用戶的服務響應進行合理的安排，同時盡可能地避免邊緣設備間的負載不均衡的情況。任務卸載和服務緩存之間相互耦合，進行聯合優化能夠在任務執行時延限制的條件下，有效保障用戶的服務質量。

1 問題描述

1.1 網絡模型

考慮如圖1所示的移動邊緣計算網絡，

K

個基站配備了具有計算和存儲功能的邊緣服務器，

N

個移動用戶產生任務后，指定服務器或遠程云數據中心來執行。考慮到邊緣服務器的密集部署以及覆蓋范圍會出現重疊，對于移動用戶

n

可能位于多個不同基站的控制區域，用

K

表示該用戶所能訪問的基站集合。由于任務的執行需要用戶的輸入及計算資源，

C

和

F

分別表示基站

k

的最大存量容量和最大周期頻率。系統能夠處理的任務種類為

S

，且任意移動用戶在一個時間段提交一個任務請求。?,表示用戶

n

的任務請求

s

，計算任務模型用三元組?,={

f

,)，

d

,,

T

,}來描述，其中，

f

,為任務所需的計算資源，

d

,為任務的輸入數據量，

T

,為任務所允許的時間延遲。

圖1 網絡模型

當移動用戶的服務請求被遷移到鄰近的基站組上，如果該基站已緩存移動用戶請求的服務并具有足夠的計算能力和帶寬資源以供移動用戶使用，則直接進行處理。如果鄰近的基站組中沒有緩存所請求的服務，則接收到服務請求的邊緣設備將請求其他緩存相應的服務的邊緣設備進行協同工作，該移動用戶的服務請求將被遷移至協助處理的邊緣設備。若所有的邊緣設備都無法進行響應，則直接將任務上傳至遠端中心云來進行處理。

1.2 服務緩存模型

移動用戶卸載的計算任務與邊緣設備緩存的服務相關聯，任務能否得以執行取決于邊緣設備上是否緩存了對應的服務。由于邊緣設備上的緩存容量有限，無法緩存全部的服務。因此，邊緣設備需要定期地與覆蓋范圍內的移動用戶進行交互，以確定將哪些服務置于其緩存中。對于時隙

t

，用

Θ

={

Θ

,|

k

∈

K

}表示時所有邊緣設備的服務緩存策略，其中：

Θ

,={

Θ

,(

s

)|

s

∈

S

}為為時隙

t

邊緣設備

k

中所緩存的服務集合。

Θ

,(

s

)是一個二元變量，取值為1表示邊緣設備

k

在時隙

t

時緩存了服務

s

，取值為0則表示未緩存服務

s

。邊緣設備所緩存的服務集合不能超過其緩存容量上限，因此，服務緩存約束條件可以表示為：∑∈

θ

(

s

)≤

C

,?

k

∈

K

(1)

1.3 任務卸載策略

相比于移動用戶，邊緣設備的計算、緩存等資源比較充足，移動用戶將任務卸載至相關聯的邊緣設備進行處理，能有效彌補移動終端資源不足、能耗受限等問題。任務卸載處理的前提條件是邊緣設備是否對相應的服務事先予以緩存。由于邊緣設備資源有限，若因緩存不足沒有對用戶請求的服務進行緩存，它會先尋求其他緩存相關服務的邊緣設備進行協作處理。如果其他邊緣設備也無法處理，則再將計算任務卸載至遠端云服務中心處。因此，移動用戶產生的計算任務的卸載優先順序依次為：關聯的邊緣設備、協作的邊緣設備以及遠端云服務中心。邊緣設備間通過核心網互聯，邊緣設備間的傳輸速率可以看成是定值，用

R

表示。若移動用戶的任務請求無法通過邊緣設備處理，而需要在遠端云服務中心處執行時，將由關聯的邊緣設備通過核心網和回程鏈路傳輸至遠端，用恒定值

t

來表示這部分的傳輸時延。另外，由于處理后的數據量一般遠小于任務的輸入，且移動用戶端的下載速率遠高于其上傳速率，本文不考慮邊緣設備或云數據中心處理后的數據下載延時。假設移動用戶上傳任務數據為恒定功率

P

，時隙

t

內的信道狀態為

H

(

t

)={

h

,(

t

)|

k

∈

K

,

n

∈

N

}，其中

h

,(

t

)表示移動用戶

n

到邊緣服務器

k

之間的信道增益。

B

(

t

)={

b

,(

t

)|

s

∈

S

,

n

∈

N

}表示該時隙帶寬資源分配，

b

,(

t

)∈[0,1]表示接入邊緣設備為卸載移動用戶

n

的

s

類任務所分配的帶寬資源比例。考慮到邊緣設備帶寬資源限制，

b

,(

t

)需滿足約束條件：∑∈∑∈

δ

,(

t

,

k

)

b

,≤1,?

k

∈

K

(2)

其中：

δ

,(

t

,

k

)為二元變量，取值1表示在時隙

t

中移動用戶

n

的任務類型

s

將被卸載到邊緣服務器

k

進行處理，反之取值為0。根據接入控制和帶寬資源分配決策，移動用戶

n

在時隙

t

用于任務卸載時的數據傳輸速率可表示為：

R

,(

t

)=

(3)

其中:

N

為噪聲功率譜密度，

B

表示邊緣設備

k

的信道帶寬，|

M

|表示邊緣設備

k

關聯的移動用戶個數。

1.3.1 關聯的邊緣設備執行任務

若移動設備產生的任務卸載到自身關聯的邊緣設備處執行，則執行時延包括：移動用戶

n

上傳數據到邊緣設備所需的傳輸時延以及邊緣設備執行任務所需的計算時延。

(4)

其中:

F

,表示邊緣設備

k

分配給任務?,的計算量。

1.3.2 協作的邊緣設備執行任務

若移動設備相關聯的邊緣設備處沒有緩存任務相應的服務，邊緣設備會尋求其他能夠予以協作的邊緣設備。這種情況下，時間延遲包括：移動用戶上傳數據到相鄰邊緣設備所需的傳輸時延，邊緣設備之間傳輸數據所需的傳輸時延以及進行協作的邊緣設備執行任務所需的計算時延。

t

,(

k

,

l

)=

(5)

其中:

dis

(

k

,

l

)表示邊緣設備

k

和

l

之間的鏈路長度，

F

,表示邊緣設備

l

分配給任務?,的計算量。

1.3.3 遠端云執行任務

若關聯的邊緣設備和其他邊緣設備都沒有緩存移動用戶卸載的計算任務所對應的服務，關聯的邊緣設備需要將任務發送至遠端云服務中心處執行。考慮到遠端云計算和存儲資源豐富，故不考慮其計算所需時間開銷。此時所需的時延包括：移動用戶至邊緣設備間的數據傳輸時延以及邊緣設備至遠端云服務中心間的數據傳輸時延。因此，任務被處理所需要的時間開銷為：

(6)

1.4 目標函數

每個移動用戶的計算任務選擇合適的關聯邊緣設備作為任務卸載目標，關聯的邊緣設備若提前緩存了該任務執行所需的服務則分配計算資源予以執行，否則將向其他邊緣設備提出協作請求或發送至遠端云服務中心進行處理。本文目標為通過對任務卸載與緩存決策進行合理調度，優化通信和計算資源分配，實現所有移動用戶的任務的平均處理時間延遲的最小化。因此，優化目標表示為：

(7)

∑∈

θ

,(

s

)≤

C

,?

k

∈

K

(8)

w

+

w

+

w

=1,?

w

,

w

,

w

∈{0,1}

(9)

F

,>0,?

n

∈

N

,?

k

∈

K

(10)

∑∈

F

,≤

F

,?

w

=1,?

k

∈

K

(11)

∑∈

F

l

,

n

)≤

F

,?

w

=1,?

l

∈

K

(12)

[

t

,(

k

)

t

,(

k

,

l

)

t

,(

k

,

z

) ]·[

w

w

w

]≤

t

,,?

k

∈

K

(13)

式(8)的約束條件為邊緣設備緩存的服務不能超過其緩存容量。式(9)的約束條件為移動用戶的計算任務的可以為關聯的邊緣設備、協作的邊緣設備或遠端云服務中心。式(10)表示邊緣設備為移動用戶的計算任務分配的計算量為正。式(11)表示邊緣設備為用戶任務分配的計算資源不能超過其計算資源總量。式(12)表示協作的邊緣設備同樣為用戶分配的計算資源不能超過其資源總量限制。式(13)約束條件為所有任務的處理時間需滿足其時延限制。

2 算法設計

上述任務卸載與緩存決策調度問題本質上為多目標組合優化問題。算法目標是在滿足邊緣設備的緩存容量、計算資源分配的約束條件下，將移動用戶的任務請求分配至關聯的邊緣設備，使得任務處理的耗費時間最少，實現對用戶的及時響應。對于此類問題，啟發式算法能夠在一定的范圍內求解次優解或以一定的概率求其最優解，其中，粒子群優化(PSO,particle swarm optimization)算法具有參數設置少、全局搜索能力強的優點，其并行性和分布式的特點適合用來求解上述任務卸載與緩存決策調度問題。首先，需要對粒子進行編碼，使緩存策略、任務卸載與粒子的位置、速度等聯系起來。

2.1 粒子編碼

假設粒子群規模為U，所有移動用戶的任務集合。

Φ

={?,?,…,?}。粒子個體的編碼維度與任務集合元素數量一致，并采用整數編碼。每個粒子元素的取值范圍為[0,

K

]，其中0表示移動用戶的任務在遠端云服務中心被處理，1～

K

則表示某移動用戶的任務卸載至相應編號的邊緣設備進行處理。每個粒子的卸載決策向量

X

={

x

,

x

,…,

x

}表示所有任務最優的執行位置。初始化時，

xi

在0到

K

之間隨機取值，且需要保證其對應的服務請求和需要的計算能力滿足對應的邊緣設備的資源限制條件。粒子的速度為調整當前任務分配至其他邊緣設備的趨勢快慢，用

V

={?,?,…,?}來表示。

pBest

={

p

1,

p

2,…,

p

N

}為第

i

個粒子的個體極值，

pBest

={

p

1,

p

2,…,

p

}為全局最優粒子。

2.2 適應度函數

算法的優化目標為最優的適應度。本文建立的模型優化目標是在滿足邊緣設備的緩存容量、計算資源分配的約束條件下，將移動用戶的任務請求分配至關聯的邊緣設備，使得任務處理的耗費時間最少。因此，可以將適應度函數定義為:

(14)

可見，所有移動用戶的任務的平均處理時間延遲值越大，優化性能越差；反之則優化性能越強。

2.3 反向粒子的選擇

粒子群優化在算法迭代到一定程度后，會因為種群多樣性的逐漸收窄而可能陷入局部最優。為了提高求解精度和獲得比較好的穩定性，本文將反向學習(OBL,oposition-based learning)的理論引入對算法進行改進。其主要思想為：在求解過程中，根據每個粒子個體對應的反向粒子，將其假定為可能得到更接近最優解的粒子個體，通過粒子個體以及其反向個體來提高種群的多樣性，再從中擇優選擇作為后續迭代的條件。

(15)

2.4 速度更新

考慮到粒子一旦陷入局部極值，則其速度無法進行更新，且過低的速度會造成粒子不易從局部極值范圍內脫離。本文采取極值擾動的方法拓展粒子的搜索區間，對學習因子采用非線性變化的策略來調整粒子的社會學習和自我學習能力。粒子的速度更新公式修改為：

(16)

c

=1.3+1.2cos(π

u/u

)，

c

=2.0-1.2cos(π

u/u

)，

c

、

c

為學習因子，

ψ

(·)為高斯分布函數，

δ

取搜索空間長度的0

.

2倍，

u

max為最大迭代次數。

3 實驗結果與分析

為了驗證本文提出的移動邊緣計算環境下的數據緩存和任務調度聯合優化模型的性能，采用CloudSim進行了仿真實驗。實驗參數設置為：終端用戶的傳輸功率為0.5 W，每個邊緣服務器的信道帶寬、存儲容量和計算容量分別被設置為 10 MHz、200 GB和 25 GHz，噪聲功率100 dBm，服務類型總數為10。任務的輸入數據大小為0.5～2 Mbits，所需的計算周期為100～1 000 CPU cycles。邊緣設備的覆蓋范圍為200 m，邊緣設備之間的直線距離為350 m。

首先，對算法的收斂性進行評估。圖2為本文提出的算法與傳統粒子群算法對上述服務緩存和任務調度聯合優化問題的求解情況對比。從實驗結果可以看到，在前15次迭代過程中收斂較快，迭代30次后得到的效用函數值趨于平穩并找到最優解。這說明本文算法在全局優化能力方面具有優勢，相比傳統的粒子群優化算法，能夠得到更小的效用函數值。

圖2 算法的收斂性對比

圖3 緩存空間利用率對比

對比實驗選取了遠程云處理策略、隨機策略、貪心算法、以及本文提出的算法在服務緩存和任務調度聯合優化問題的應用效果進行了比較。本文算法中的參數初始化為：種群規模初始化為100，最大迭代次數為50。圖3為邊緣設備緩存空間利用率對比。所利用的服務器緩存空間越大，移動用戶任務的響應時間越短。由于遠程云處理策略中所有移動用戶的任務都是直接由邊緣設備轉發至云數據中心進行處理，因此對應的MEC服務器不緩存任何任務，會造成較大的傳輸延遲。隨著移動用戶數量的增加，任務數量越來越多，貪心算法和本文算法在緩存空間利用率上提升更快，這有利于實現卸載到邊緣設備的任務能直接進行處理，減少任務的響應時間。

圖4為邊緣設備的負載均衡情況對比。從圖4可以看出，在不同的用戶規模條件下，本文算法和貪心算法能獲得更好的負載均衡度。在遠程云處理策略中，邊緣設備負責將用戶請求轉發至遠端云數據中心，其負載均衡度取決于覆蓋范圍內的用戶數量。隨機策略有時會獲得較好的負載均衡度，但整體上不穩定。貪心算法在用戶數量較大時負載均衡度偏大，說明其對邊緣設備的利用不夠均衡。

圖4 負載均衡情況對比

圖5 執行時間對比

圖5為執行時間的對比。可以看到使用隨機策略，邊緣設備的緩存任務和對移動用戶的任務請求處理都是隨機選擇的，獲得的目標值不穩定，且隨機卸載策略的總延遲增長速度越快，相比貪心算法和本文算法在執行時間上的優化差距較大。在任務規模比較小的情況下，本文算法相比貪心算法的最優調度方案所需的總執行時間相差不明顯。但是隨著任務規模的增加，可以看到本文算法能夠明顯表現出在執行時間上的優勢，當移動用戶數在400～800時，本文提出的算法的總執行時間比貪心策略少14.5%～32.1%。上述結果表明本文調度方案能夠適應大規模任務調度，在較短的時間內完成用戶任務。

4 結束語

針對任務卸載與服務緩存決策問題，本文建立數學模型并提出一種聯合優化算法來求解任務執行時延約束條件下的服務緩存決策最優解。通過仿真實驗，分析了邊緣設備的緩存空間利用率、負載均衡、執行時間等指標下的效果。實驗結果驗證了本文提出的算法的有效性，與其他策略相比在提高卸載效率、減少任務完成時間和大規模任務調度的條件下都獲得較好的性能。下一步工作，我們將繼續探索和對服務緩存算法和卸載策略進行優化、完善。