移動邊緣計算分布式保護業(yè)務(wù)部署算法

李泳成，宗紅梅，林玠珉，孟二帥，符小東，房洪蓮，沈一春

(1.蘇州大學(xué) 電子信息學(xué)院，江蘇 蘇州 215006； 2. 中天通信技術(shù)有限公司，江蘇 南通 226000；3. 中天寬帶技術(shù)有限公司，江蘇 南通 226463； 4. 中天科技精密材料有限公司，江蘇 南通 226009)

0 引 言

隨著第五代移動通信技術(shù)(5th Generation Mobile Communication Technology,5G)的成熟，諸如物聯(lián)網(wǎng)、車聯(lián)網(wǎng)等資源密集、時延敏感型業(yè)務(wù)快速增長。移動邊緣計算(Mobile Edge Computing, MEC)通過在網(wǎng)絡(luò)邊緣部署邊緣數(shù)據(jù)中心，就近為用戶提供計算和存儲資源，被認(rèn)為是承載這些新興業(yè)務(wù)的重要技術(shù)之一[1]。同時，MEC也存在單個邊緣數(shù)據(jù)中心內(nèi)計算和存儲資源有限，缺乏為大量并發(fā)業(yè)務(wù)提供服務(wù)的能力。因此，MEC中存在一類業(yè)務(wù)可以通過切分成多個子業(yè)務(wù)，以分布式的形式在不同數(shù)據(jù)中心中執(zhí)行，稱為MEC分布式業(yè)務(wù)[2]。目前，針對MEC分布式業(yè)務(wù)的研究主要集中在業(yè)務(wù)切分和計算卸載[3-5]，而缺乏對該類業(yè)務(wù)保護問題的研究。本文針對MEC分布式業(yè)務(wù)保護問題展開了深入研究。通過結(jié)合專用保護技術(shù)[6]，本文以最小化總業(yè)務(wù)時延為目標(biāo)，構(gòu)建了整數(shù)線性規(guī)劃(Integer Linear Programing，ILP)模型，并提出了基于輪詢的MEC分布式專用保護業(yè)務(wù)部署算法。仿真結(jié)果表明，本文所提啟發(fā)式算法能有效降低業(yè)務(wù)總時延和均衡MEC服務(wù)器間的負(fù)載，且與ILP模型獲得的最優(yōu)結(jié)果十分接近。

1 MEC分布式專用保護業(yè)務(wù)部署

1.1 問題定義

在MEC網(wǎng)絡(luò)中，服務(wù)器、無線接入點和光纖鏈路故障都可能導(dǎo)致MEC分布式業(yè)務(wù)無法完成。為此，需要為MEC分布式業(yè)務(wù)提供保護以提高其生存性。本文結(jié)合專用保護技術(shù)，為每一個子業(yè)務(wù)都部署專屬保護子業(yè)務(wù)，即MEC分布式專用保護業(yè)務(wù)。首先，對MEC網(wǎng)絡(luò)做如下假設(shè)：(1) 網(wǎng)絡(luò)中每個節(jié)點上存在一個MEC服務(wù)器，其單位時間t內(nèi)可用計算資源為N個單位；(2) 完成所有業(yè)務(wù)可用的總時隙為T；(3) 每個MEC分布式專用保護業(yè)務(wù)選擇最近的m個MEC服務(wù)器部署；(4) 本文中采用最短路由算法選出最近的m個MEC服務(wù)器；(5) 單個業(yè)務(wù)的時延為所有子業(yè)務(wù)和保護子業(yè)務(wù)完成的最大時延。

圖1所示為一個MEC分布式專用保護業(yè)務(wù)部署的實例。假設(shè)每個時隙下，每個MEC服務(wù)器可用計算資源為3個單位。業(yè)務(wù)u的子業(yè)務(wù)S1(3個單位)、S2(5個單位)、S3(4個單位)和S4(4個單位)已分別部署到4個MEC服務(wù)器上(N0、N1、N2和N3)?，F(xiàn)給出兩種方案部署業(yè)務(wù)u的保護子業(yè)務(wù)。方案1為S1在N3上部署了保護子業(yè)務(wù)P1(3個單位)、為S2在N2上部署保護子業(yè)務(wù)P2(5個單位)、為S3在N1上部署保護子業(yè)務(wù)P3(4個單位)，為S4在N2上部署保護子業(yè)務(wù)P4(4個單位)。而方案2則為S1在N2上部署了保護子業(yè)務(wù)P1(3個單位)、為S2在N3上部署保護子業(yè)務(wù)P2(5個單位)、為S3在N0上部署保護子業(yè)務(wù)P3(4個單位)，為S4在N1上部署保護子業(yè)務(wù)P4(4個單位)。顯然，第2種部署方案所需的總業(yè)務(wù)時延為3個時隙，而方案1則為5個時隙，且方案2各個MEC服務(wù)器之間的負(fù)載更加均衡。為此，需要為MEC分布式保護業(yè)務(wù)提出高效的優(yōu)化部署方案，以降低總業(yè)務(wù)時延，均衡各個MEC服務(wù)器之間的負(fù)載。

圖1 MEC分布式專用保護業(yè)務(wù)實例Figure 1 Case of MEC distributed dedicated protection service

1.2 ILP模型

結(jié)合以上關(guān)于MEC分布式專用保護業(yè)務(wù)部署的問題描述，本文通過將問題進行數(shù)學(xué)抽象，以最小化業(yè)務(wù)總時延為目標(biāo)，構(gòu)建了一個ILP優(yōu)化模型。該模型將問題涉及的限制條件和目標(biāo)用數(shù)學(xué)公式表達，能夠為該問題在求解域內(nèi)搜尋到滿足所有限制條件的理論最優(yōu)解。所構(gòu)建模型的具體推導(dǎo)過程如下：

首先，將該問題涉及到的集合，進行數(shù)學(xué)抽象，包括MEC網(wǎng)絡(luò)中的節(jié)點集合，業(yè)務(wù)集合，每個業(yè)務(wù)所包含的子業(yè)務(wù)集合，每個業(yè)務(wù)可用的MEC節(jié)點集合，以及所有可用時隙的集合。其次，將該問題涉及到的參數(shù)進行數(shù)學(xué)抽象，包括每個MEC節(jié)點單位時間內(nèi)允許提供的計算資源，每個子業(yè)務(wù)需要MEC節(jié)點提供的計算資源。最后，對該問題需要設(shè)立的變量進行整理，包括總業(yè)務(wù)時延以及為求解該目標(biāo)值所依賴的其他變量?；谝陨纤悸?，定義本文ILP模型的集合、參數(shù)和變量如下：

(1) 集合

U: MEC網(wǎng)絡(luò)中分布式業(yè)務(wù)集合。

E: MEC網(wǎng)絡(luò)中節(jié)點集合。

Ku: MEC分布式業(yè)務(wù)u的子業(yè)務(wù)集合。

Eu: MEC分布式業(yè)務(wù)u可用的MEC節(jié)點集合。

T: 可用時隙集合。

(2) 參數(shù)

Ru: MEC分布式業(yè)務(wù)u所需的MEC計算資源，u∈U。

Ve: MEC節(jié)點e上單個時隙內(nèi)提供的MEC計算資源。

Δ: 一個極大值。

(3) 變量

Γ: 整型變量，總業(yè)務(wù)時延。

優(yōu)化目標(biāo)：最小化Γ。

接下來，需要進一步明確該模型所需滿足的限制條件。為此，本文考慮4個主要內(nèi)容：每個業(yè)務(wù)的子業(yè)務(wù)都被成功在MEC節(jié)點上部署；每個子業(yè)務(wù)的保護業(yè)務(wù)被成功在MEC節(jié)點上部署；單個時隙內(nèi)，每個MEC節(jié)點提供的計算資源不能超過其最大計算資源；總業(yè)務(wù)時延的計算方法。基于以上思路，本文將限制條件表示如下：

(1) 子業(yè)務(wù)約束

(2) 保護子業(yè)務(wù)約束

(3) MEC服務(wù)容量約束

(4) 業(yè)務(wù)總時延

式(1～2)表示任意業(yè)務(wù)的一個子業(yè)務(wù)只能使用一個MEC服務(wù)器。式(3)表示任意業(yè)務(wù)的所有子業(yè)務(wù)必須部署到不同MEC服務(wù)器上，其中，e1和e2為集合Eu中任意兩個MEC節(jié)點，t1和t2為集合T中任意兩個時隙。式(4)確認(rèn)業(yè)務(wù)的子業(yè)務(wù)在每個時隙內(nèi)占用的MEC服務(wù)器的計算資源。式(5)表示MEC服務(wù)器子業(yè)務(wù)提供的計算資源。式(6)表示任意業(yè)務(wù)所有子業(yè)務(wù)占用計算資源量總和等于該業(yè)務(wù)計算資源需求。式(7)表示任意子業(yè)務(wù)與其保護子業(yè)務(wù)不能部署到同一MEC服務(wù)器上。式(8)表示任意業(yè)務(wù)的一個子業(yè)務(wù)的保護子業(yè)務(wù)只能使用一個MEC服務(wù)器。式(9～11)表示任意業(yè)務(wù)的某個子業(yè)務(wù)占用的計算資源與其保護子業(yè)務(wù)占用的計算資源相同。式(12)表示在某個時隙，MEC服務(wù)器被占用的計算資源之和不能超過其可提供最大計算資源。式(13～14)表示業(yè)務(wù)總時延不小于任意業(yè)務(wù)的子業(yè)務(wù)及其保護子業(yè)務(wù)的完成時間。

2 基于輪詢的啟發(fā)式算法

由于ILP模型難以有效求解大規(guī)模問題，為此，本文也提出了部署MEC分布式專用保護業(yè)務(wù)的啟發(fā)式算法，包括隨機部署、環(huán)部署和雙輪詢部署。這3種算法都采用了輪詢策略進行子業(yè)務(wù)的切分和部署。具體地，為業(yè)務(wù)每一個計算需求(單位：unit)在單個時隙內(nèi)輪詢所有可用MEC服務(wù)器，一旦某個MEC服務(wù)器上存在空閑計算資源，則將該計算需求部署在該MEC服務(wù)器上。如果當(dāng)前時隙下沒有可用計算資源，則進入下一個時隙重復(fù)以上過程。當(dāng)業(yè)務(wù)的所有計算需求單元都完成部署，則查看每一個MEC服務(wù)器上部署的總計算需求單元，即為切分的子業(yè)務(wù)。

不同的是，隨機算法為每一個子業(yè)務(wù)隨機選擇MEC服務(wù)器部署專屬保護子業(yè)務(wù)。環(huán)部署算法則順序?qū)?dāng)前子業(yè)務(wù)的專屬保護子業(yè)務(wù)部署到下一個MEC服務(wù)器上。雙輪詢部署算法也采用了輪詢的方式部署子業(yè)務(wù)的保護子業(yè)務(wù)。該算法的核心思想是通過盡可能均勻地在各個MEC服務(wù)器上部署工作和保護子業(yè)務(wù)，從而實現(xiàn)最小化總業(yè)務(wù)時延。接下來，詳細介紹雙輪詢MEC分布式專用保護業(yè)務(wù)部署算法。

遍歷網(wǎng)絡(luò)中所有業(yè)務(wù)集合U，對于每一個業(yè)務(wù)u執(zhí)行如下操作：

(1) 采用最短路由算法獲取與業(yè)務(wù)u所在本地節(jié)點最近的n個MEC服務(wù)器加入業(yè)務(wù)u的可用MEC服務(wù)器集合Eu。

(2) 遍歷業(yè)務(wù)u計算資源請求集合Su，對于每一個計算資源s(1個單元)執(zhí)行如下操作：

(a) 令時隙索引t=0，計算資源索引v=0。

(c) 若所有MEC服務(wù)器都無法部署s，則令v=v+1，若v

(d) 否則，s被成功部署到MEC服務(wù)器m*，為其部署對應(yīng)的保護計算資源s'。

令時隙索引t=0，計算資源索引r=0，遍歷集合Eu/m*，對于每一個m執(zhí)行如下操作：

若所有MEC服務(wù)器都無法部署s'，則令v=v+1，若r

對比以上3種算法，隨機算法隨機性較強，容易導(dǎo)致部分子業(yè)務(wù)集中到某一個MEC服務(wù)器上。環(huán)部署算法雖然更加側(cè)重均衡，但因為沒有考慮不同子業(yè)務(wù)的時延，仍然會導(dǎo)致為部分MEC服務(wù)器提供更多的計算資源，從而增加總業(yè)務(wù)時延。雙輪詢部署算法將子業(yè)務(wù)和保護子業(yè)務(wù)分別通過輪詢的方式部署到MEC服務(wù)器上，能有效均衡各個MEC服務(wù)器承載的業(yè)務(wù)，從而降低總的業(yè)務(wù)時延。

3 結(jié)果與性能分析

3.1 測試條件

本文評估了MEC分布式專用保護業(yè)務(wù)部署算法在業(yè)務(wù)總時延和負(fù)載均衡方面的性能。采用6個節(jié)點、9條鏈路的n6s9和14個節(jié)點、23條鏈路的NSFNET兩個測試網(wǎng)絡(luò)[7]進行了仿真。仿真條件如下：網(wǎng)絡(luò)中每個節(jié)點上都部署一個MEC服務(wù)器，每個MEC服務(wù)器上單個時隙內(nèi)最大可用計算資源為1 000；總的時隙數(shù)設(shè)為200；n6s9網(wǎng)絡(luò)中每個MEC節(jié)點業(yè)務(wù)數(shù)在[X-5,X]范圍內(nèi)隨機產(chǎn)生，NSFNET中每個MEC節(jié)點業(yè)務(wù)數(shù)在[X-20,X]范圍內(nèi)隨機產(chǎn)生，X為每個MEC節(jié)點上的平均業(yè)務(wù)數(shù)。每個業(yè)務(wù)所需的計算資源為400；業(yè)務(wù)最大切分?jǐn)?shù)量為4。每個業(yè)務(wù)可選擇的MEC服務(wù)器通過最短路由算法(Dijkstra's)獲得。本文利用AMPL/Gurobi[8]軟件求解ILP優(yōu)化模型，并采用Java語言實現(xiàn)啟發(fā)式算法。

3.2 結(jié)果分析

圖2所示為不同部署算法的業(yè)務(wù)總時延。圖中，“ILP”表示ILP優(yōu)化模型的結(jié)果；“RS”、“CS”和“DS”分別對應(yīng)隨機部署算法、環(huán)部署算法和雙輪詢部署算法的結(jié)果。由圖2(a)可知，隨著每個MEC節(jié)點上平均業(yè)務(wù)數(shù)量的增加，ILP優(yōu)化模型和3種調(diào)度策略的網(wǎng)絡(luò)業(yè)務(wù)總時延逐漸增大。這是因為大量的業(yè)務(wù)意味著需要占用服務(wù)器更多的計算資源，從而增加了業(yè)務(wù)完成的時延。比較不同部署算法，發(fā)現(xiàn)雙輪詢算法與ILP模型結(jié)果十分接近，遠遠小于RS和CS算法的業(yè)務(wù)總時延。當(dāng)每個節(jié)點上的平均業(yè)務(wù)數(shù)為30時，與RS和CS算法相比，雙輪詢算法減少了20%和14%的業(yè)務(wù)總時延。本文在NSFNET中也做了類似仿真。如圖2(b)所示，雙輪詢算法的業(yè)務(wù)總時延總是低于隨機和環(huán)部署算法。當(dāng)每個節(jié)點上平均業(yè)務(wù)數(shù)為100時，雙輪詢算法的業(yè)務(wù)總時延比RS和CS算法分別少了50%和29%。以上結(jié)果證明了雙輪詢部署算法在減少業(yè)務(wù)總時延方面的高效性。

圖2 網(wǎng)絡(luò)中業(yè)務(wù)總時延Figure 2 Total service delay in the network

3.3 負(fù)載均衡

本文也比較了不同部署算法的MEC服務(wù)器負(fù)載均衡性能。圖3所示為n6s9和NSFNET中MEC服務(wù)器負(fù)載的方差。其中n6s9節(jié)點上業(yè)務(wù)數(shù)在[10，50]范圍內(nèi)隨機產(chǎn)生，NSFNET節(jié)點上的業(yè)務(wù)數(shù)在[20，100]范圍內(nèi)隨機產(chǎn)生?？v軸是服務(wù)器上承載的總的計算需求(負(fù)載)。發(fā)現(xiàn)雙輪詢算法的MEC服務(wù)器負(fù)載方差最小(1.48)，遠低于使用RS和CS算法的MEC服務(wù)器負(fù)載方差(6.28和4.47)。類似地，如圖3(b)所示，雙輪詢算法在NSFNET中實施后，MEC服務(wù)器負(fù)載方差僅為5.9，遠低于RS和CS算法的19.4和13.2。這是因為雙輪詢算法在為子業(yè)務(wù)和保護子業(yè)務(wù)選擇MEC服務(wù)器時，都充分考慮了每個MEC服務(wù)器的負(fù)載情況，因此能更好地均衡各個MEC服務(wù)器間的負(fù)載。

圖3 網(wǎng)絡(luò)中MEC服務(wù)器上的負(fù)載Figure 3 Load on MEC servers in the network

4 結(jié)束語

本文研究了MEC中分布式專用保護業(yè)務(wù)的部署問題，以最小化業(yè)務(wù)總時延為目標(biāo)，構(gòu)建了相應(yīng)的ILP模型，并提出了高效的啟發(fā)式算法，包括隨機、環(huán)和雙輪詢部署算法。仿真結(jié)果表明，本文提出的雙輪詢部署算法既能有效降低總業(yè)務(wù)時延，也能均衡MEC服務(wù)器間的負(fù)載。