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

(1.海南省氣象信息中心，海口 570203；2.成都信息工程大學(xué)，成都 610225；3.海南省南海氣象防災(zāi)減災(zāi)重點(diǎn)實(shí)驗(yàn)室，?？?570203)

0 引言

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

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

1 問題描述

1.1 網(wǎng)絡(luò)模型

考慮如圖1所示的移動(dòng)邊緣計(jì)算網(wǎng)絡(luò)，

K

個(gè)基站配備了具有計(jì)算和存儲功能的邊緣服務(wù)器，

N

個(gè)移動(dòng)用戶產(chǎn)生任務(wù)后，指定服務(wù)器或遠(yuǎn)程云數(shù)據(jù)中心來執(zhí)行?？紤]到邊緣服務(wù)器的密集部署以及覆蓋范圍會(huì)出現(xiàn)重疊，對于移動(dòng)用戶

n

可能位于多個(gè)不同基站的控制區(qū)域，用

K

表示該用戶所能訪問的基站集合。由于任務(wù)的執(zhí)行需要用戶的輸入及計(jì)算資源，

C

和

F

分別表示基站

k

的最大存量容量和最大周期頻率。系統(tǒng)能夠處理的任務(wù)種類為

S

，且任意移動(dòng)用戶在一個(gè)時(shí)間段提交一個(gè)任務(wù)請求。?,表示用戶

n

的任務(wù)請求

s

，計(jì)算任務(wù)模型用三元組?,={

f

,)，

d

,,

T

,}來描述，其中，

f

,為任務(wù)所需的計(jì)算資源，

d

,為任務(wù)的輸入數(shù)據(jù)量，

T

,為任務(wù)所允許的時(shí)間延遲。

圖1 網(wǎng)絡(luò)模型

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

1.2 服務(wù)緩存模型

移動(dòng)用戶卸載的計(jì)算任務(wù)與邊緣設(shè)備緩存的服務(wù)相關(guān)聯(lián)，任務(wù)能否得以執(zhí)行取決于邊緣設(shè)備上是否緩存了對應(yīng)的服務(wù)。由于邊緣設(shè)備上的緩存容量有限，無法緩存全部的服務(wù)。因此，邊緣設(shè)備需要定期地與覆蓋范圍內(nèi)的移動(dòng)用戶進(jìn)行交互，以確定將哪些服務(wù)置于其緩存中。對于時(shí)隙

t

，用

Θ

={

Θ

,|

k

∈

K

}表示時(shí)所有邊緣設(shè)備的服務(wù)緩存策略，其中：

Θ

,={

Θ

,(

s

)|

s

∈

S

}為為時(shí)隙

t

邊緣設(shè)備

k

中所緩存的服務(wù)集合。

Θ

,(

s

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

k

在時(shí)隙

t

時(shí)緩存了服務(wù)

s

，取值為0則表示未緩存服務(wù)

s

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

θ

(

s

)≤

C

,?

k

∈

K

(1)

1.3 任務(wù)卸載策略

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

R

表示。若移動(dòng)用戶的任務(wù)請求無法通過邊緣設(shè)備處理，而需要在遠(yuǎn)端云服務(wù)中心處執(zhí)行時(shí)，將由關(guān)聯(lián)的邊緣設(shè)備通過核心網(wǎng)和回程鏈路傳輸至遠(yuǎn)端，用恒定值

t

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

P

，時(shí)隙

t

內(nèi)的信道狀態(tài)為

H

(

t

)={

h

,(

t

)|

k

∈

K

,

n

∈

N

}，其中

h

,(

t

)表示移動(dòng)用戶

n

到邊緣服務(wù)器

k

之間的信道增益。

B

(

t

)={

b

,(

t

)|

s

∈

S

,

n

∈

N

}表示該時(shí)隙帶寬資源分配，

b

,(

t

)∈[0,1]表示接入邊緣設(shè)備為卸載移動(dòng)用戶

n

的

s

類任務(wù)所分配的帶寬資源比例?？紤]到邊緣設(shè)備帶寬資源限制，

b

,(

t

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

δ

,(

t

,

k

)

b

,≤1,?

k

∈

K

(2)

其中：

δ

,(

t

,

k

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

t

中移動(dòng)用戶

n

的任務(wù)類型

s

將被卸載到邊緣服務(wù)器

k

進(jìn)行處理，反之取值為0。根據(jù)接入控制和帶寬資源分配決策，移動(dòng)用戶

n

在時(shí)隙

t

用于任務(wù)卸載時(shí)的數(shù)據(jù)傳輸速率可表示為：

R

,(

t

)=

(3)

其中:

N

為噪聲功率譜密度，

B

表示邊緣設(shè)備

k

的信道帶寬，|

M

|表示邊緣設(shè)備

k

關(guān)聯(lián)的移動(dòng)用戶個(gè)數(shù)。

1.3.1 關(guān)聯(lián)的邊緣設(shè)備執(zhí)行任務(wù)

若移動(dòng)設(shè)備產(chǎn)生的任務(wù)卸載到自身關(guān)聯(lián)的邊緣設(shè)備處執(zhí)行，則執(zhí)行時(shí)延包括：移動(dòng)用戶

n

上傳數(shù)據(jù)到邊緣設(shè)備所需的傳輸時(shí)延以及邊緣設(shè)備執(zhí)行任務(wù)所需的計(jì)算時(shí)延。

(4)

其中:

F

,表示邊緣設(shè)備

k

分配給任務(wù)?,的計(jì)算量。

1.3.2 協(xié)作的邊緣設(shè)備執(zhí)行任務(wù)

若移動(dòng)設(shè)備相關(guān)聯(lián)的邊緣設(shè)備處沒有緩存任務(wù)相應(yīng)的服務(wù)，邊緣設(shè)備會(huì)尋求其他能夠予以協(xié)作的邊緣設(shè)備。這種情況下，時(shí)間延遲包括：移動(dòng)用戶上傳數(shù)據(jù)到相鄰邊緣設(shè)備所需的傳輸時(shí)延，邊緣設(shè)備之間傳輸數(shù)據(jù)所需的傳輸時(shí)延以及進(jìn)行協(xié)作的邊緣設(shè)備執(zhí)行任務(wù)所需的計(jì)算時(shí)延。

t

,(

k

,

l

)=

(5)

其中:

dis

(

k

,

l

)表示邊緣設(shè)備

k

和

l

之間的鏈路長度，

F

,表示邊緣設(shè)備

l

分配給任務(wù)?,的計(jì)算量。

1.3.3 遠(yuǎn)端云執(zhí)行任務(wù)

若關(guān)聯(lián)的邊緣設(shè)備和其他邊緣設(shè)備都沒有緩存移動(dòng)用戶卸載的計(jì)算任務(wù)所對應(yīng)的服務(wù)，關(guān)聯(lián)的邊緣設(shè)備需要將任務(wù)發(fā)送至遠(yuǎn)端云服務(wù)中心處執(zhí)行。考慮到遠(yuǎn)端云計(jì)算和存儲資源豐富，故不考慮其計(jì)算所需時(shí)間開銷。此時(shí)所需的時(shí)延包括：移動(dòng)用戶至邊緣設(shè)備間的數(shù)據(jù)傳輸時(shí)延以及邊緣設(shè)備至遠(yuǎn)端云服務(wù)中心間的數(shù)據(jù)傳輸時(shí)延。因此，任務(wù)被處理所需要的時(shí)間開銷為：

(6)

1.4 目標(biāo)函數(shù)

每個(gè)移動(dòng)用戶的計(jì)算任務(wù)選擇合適的關(guān)聯(lián)邊緣設(shè)備作為任務(wù)卸載目標(biāo)，關(guān)聯(lián)的邊緣設(shè)備若提前緩存了該任務(wù)執(zhí)行所需的服務(wù)則分配計(jì)算資源予以執(zhí)行，否則將向其他邊緣設(shè)備提出協(xié)作請求或發(fā)送至遠(yuǎn)端云服務(wù)中心進(jìn)行處理。本文目標(biāo)為通過對任務(wù)卸載與緩存決策進(jìn)行合理調(diào)度，優(yōu)化通信和計(jì)算資源分配，實(shí)現(xiàn)所有移動(dòng)用戶的任務(wù)的平均處理時(shí)間延遲的最小化。因此，優(yōu)化目標(biāo)表示為：

(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)的約束條件為邊緣設(shè)備緩存的服務(wù)不能超過其緩存容量。式(9)的約束條件為移動(dòng)用戶的計(jì)算任務(wù)的可以為關(guān)聯(lián)的邊緣設(shè)備、協(xié)作的邊緣設(shè)備或遠(yuǎn)端云服務(wù)中心。式(10)表示邊緣設(shè)備為移動(dòng)用戶的計(jì)算任務(wù)分配的計(jì)算量為正。式(11)表示邊緣設(shè)備為用戶任務(wù)分配的計(jì)算資源不能超過其計(jì)算資源總量。式(12)表示協(xié)作的邊緣設(shè)備同樣為用戶分配的計(jì)算資源不能超過其資源總量限制。式(13)約束條件為所有任務(wù)的處理時(shí)間需滿足其時(shí)延限制。

2 算法設(shè)計(jì)

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

2.1 粒子編碼

假設(shè)粒子群規(guī)模為U，所有移動(dòng)用戶的任務(wù)集合。

Φ

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

K

]，其中0表示移動(dòng)用戶的任務(wù)在遠(yuǎn)端云服務(wù)中心被處理，1～

K

則表示某移動(dòng)用戶的任務(wù)卸載至相應(yīng)編號的邊緣設(shè)備進(jìn)行處理。每個(gè)粒子的卸載決策向量

X

={

x

,

x

,…,

x

}表示所有任務(wù)最優(yōu)的執(zhí)行位置。初始化時(shí)，

xi

在0到

K

之間隨機(jī)取值，且需要保證其對應(yīng)的服務(wù)請求和需要的計(jì)算能力滿足對應(yīng)的邊緣設(shè)備的資源限制條件。粒子的速度為調(diào)整當(dāng)前任務(wù)分配至其他邊緣設(shè)備的趨勢快慢，用

V

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

pBest

={

p

1,

p

2,…,

p

N

}為第

i

個(gè)粒子的個(gè)體極值，

pBest

={

p

1,

p

2,…,

p

}為全局最優(yōu)粒子。

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

算法的優(yōu)化目標(biāo)為最優(yōu)的適應(yīng)度。本文建立的模型優(yōu)化目標(biāo)是在滿足邊緣設(shè)備的緩存容量、計(jì)算資源分配的約束條件下，將移動(dòng)用戶的任務(wù)請求分配至關(guān)聯(lián)的邊緣設(shè)備，使得任務(wù)處理的耗費(fèi)時(shí)間最少。因此，可以將適應(yīng)度函數(shù)定義為:

(14)

可見，所有移動(dòng)用戶的任務(wù)的平均處理時(shí)間延遲值越大，優(yōu)化性能越差；反之則優(yōu)化性能越強(qiáng)。

2.3 反向粒子的選擇

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

(15)

2.4 速度更新

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

(16)

c

=1.3+1.2cos(π

u/u

)，

c

=2.0-1.2cos(π

u/u

)，

c

、

c

為學(xué)習(xí)因子，

ψ

(·)為高斯分布函數(shù)，

δ

取搜索空間長度的0

.

2倍，

u

max為最大迭代次數(shù)。

3 實(shí)驗(yàn)結(jié)果與分析

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

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

圖2 算法的收斂性對比

圖3 緩存空間利用率對比

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

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

圖4 負(fù)載均衡情況對比

圖5 執(zhí)行時(shí)間對比

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

4 結(jié)束語

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