移動邊緣計算分布式保護業務部署算法

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

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

0 引 言

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

1 MEC分布式專用保護業務部署

1.1 問題定義

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

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

圖1 MEC分布式專用保護業務實例Figure 1 Case of MEC distributed dedicated protection service

1.2 ILP模型

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

首先，將該問題涉及到的集合，進行數學抽象，包括MEC網絡中的節點集合，業務集合，每個業務所包含的子業務集合，每個業務可用的MEC節點集合，以及所有可用時隙的集合。其次，將該問題涉及到的參數進行數學抽象，包括每個MEC節點單位時間內允許提供的計算資源，每個子業務需要MEC節點提供的計算資源。最后，對該問題需要設立的變量進行整理，包括總業務時延以及為求解該目標值所依賴的其他變量。基于以上思路，定義本文ILP模型的集合、參數和變量如下：

(1) 集合

U: MEC網絡中分布式業務集合。

E: MEC網絡中節點集合。

Ku: MEC分布式業務u的子業務集合。

Eu: MEC分布式業務u可用的MEC節點集合。

T: 可用時隙集合。

(2) 參數

Ru: MEC分布式業務u所需的MEC計算資源，u∈U。

Ve: MEC節點e上單個時隙內提供的MEC計算資源。

Δ: 一個極大值。

(3) 變量

Γ: 整型變量，總業務時延。

優化目標：最小化Γ。

接下來，需要進一步明確該模型所需滿足的限制條件。為此，本文考慮4個主要內容：每個業務的子業務都被成功在MEC節點上部署；每個子業務的保護業務被成功在MEC節點上部署；單個時隙內，每個MEC節點提供的計算資源不能超過其最大計算資源；總業務時延的計算方法?；谝陨纤悸?，本文將限制條件表示如下：

(1) 子業務約束

(2) 保護子業務約束

(3) MEC服務容量約束

(4) 業務總時延

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

2 基于輪詢的啟發式算法

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

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

遍歷網絡中所有業務集合U，對于每一個業務u執行如下操作：

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

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

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

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

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

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

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

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

3 結果與性能分析

3.1 測試條件

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

3.2 結果分析

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

圖2 網絡中業務總時延Figure 2 Total service delay in the network

3.3 負載均衡

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

圖3 網絡中MEC服務器上的負載Figure 3 Load on MEC servers in the network

4 結束語

本文研究了MEC中分布式專用保護業務的部署問題，以最小化業務總時延為目標，構建了相應的ILP模型，并提出了高效的啟發式算法，包括隨機、環和雙輪詢部署算法。仿真結果表明，本文提出的雙輪詢部署算法既能有效降低總業務時延，也能均衡MEC服務器間的負載。