邊緣計算中的邊緣服務(wù)器放置策略

趙興兵，李 波，楊志軍，保利勇，丁洪偉+

(1.云南大學(xué) 信息學(xué)院，云南 昆明 650000；2.云南省教育廳 教學(xué)儀器裝備中心，云南 昆明 650000)

0 引 言

在移動邊緣計算中，將具有計算能力和數(shù)據(jù)存儲功能的邊緣服務(wù)器(edge server，ES)放置在基站上，能夠?qū)⒑诵木W(wǎng)的部分功能下沉到網(wǎng)絡(luò)邊緣，有效降低網(wǎng)絡(luò)傳輸時延。這使得研究ES放置問題具有重要意義。

目前，有關(guān)邊緣服務(wù)器放置的研究較少，微云放置[1-6]和計算卸載[7,8]等都能為ES放置[9]提供一定的參考。文獻[2]使用基于整數(shù)線性規(guī)劃的方法對WMAN中用戶和微云之間的時延進行優(yōu)化，并且試圖向遠程云分配用戶請求。文獻[5]考慮將用戶分配給最近的微云，以此最小化時延，并提出了基于密度優(yōu)先的放置方法。文獻[9，10]都對具有能量感知的ES放置進行了研究。ES放置的能耗問題包括ES的能耗和移動設(shè)備的能耗。ES的能耗主要來源于CPU，提高CPU的使用率可以優(yōu)化ES的能耗；移動設(shè)備的能耗主要取決于接入時延，即優(yōu)化移動設(shè)備能耗的問題本質(zhì)上是優(yōu)化時延的問題。文獻[11]針對5G蜂窩網(wǎng)中的ES放置問題，提出了基于最大等效帶寬的方法來最小化系統(tǒng)的時延開銷和能量開銷。文獻[12]提出了基于混合整數(shù)線性規(guī)劃的方法優(yōu)化WMAN中ES放置的時延和負載均衡。

上述文獻中，文獻[1]的方法能直接用到大規(guī)模WMAN中放置ES，因為微云的放置位置一般不是基站，而為了節(jié)約部署成本，ES必須被放置在基站位置上；文獻[9-11]都涉及了ES放置的能量問題，但由于用戶的移動性和基站能量的無線性，優(yōu)化能耗的意義較小。文獻[12]提出的混合整數(shù)線性規(guī)劃(MIP)在問題規(guī)模較大時表現(xiàn)較差。針對上述問題，本文提出一種改進遺的傳算法MGA對ES進行放置，該方法對初始化種群、選擇、交叉和遺傳變異操作進行了改進，大幅提升了ES放置的性能。

1 ES放置模型分析

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

用無向圖G={V,E} 表示W(wǎng)MAN的基礎(chǔ)設(shè)施網(wǎng)絡(luò)，其中V=B∪C∪U。B={b1,b2,…,bm} 表示基站的集合；C={c1,c2,…,ck} 表示ES的集合；U={u1,u2…,un} 是用戶的集合。E代表網(wǎng)絡(luò)中的鏈路(包括基站之間的有線連接和基站與用戶之間的無線連接)和邏輯分配關(guān)系。X和Y分為基站分配矩陣和ES部署矩陣，引入二進制變量xik={0,1} 表示分配關(guān)系，xik=1表示將bk分配給ci， 否則沒有，xik∈X；yjk={0,1} 表示部署關(guān)系，yjk=1表示將cj放置在bk， 否則沒有，yjk∈Y。 以圖1的放置場景為例，其中yij=1；xie,xij,xir=1。

圖1 ES放置場景

1.2 問題描述

基于以上分析，假設(shè)ES與某個基站共址，WMAN中的ES放置問題可定義為：在有許多基站的無向圖G中，通過劃分子網(wǎng)的思想，尋找k個合理的位置放置ES，同時考慮基站與ES之間的分配關(guān)系，使得放置后ES的平均時延最小，并且使得ES的負載均衡最優(yōu)。

1.3 ES放置模型

每個子網(wǎng)中，用戶的服務(wù)請求通過基站匯集到ES中處理，可以計算出ES的負載，如式(1)

(1)

其中，Bh表示第h個子網(wǎng)；wi為ui的負載。

定義1 負載均衡BL。負載均衡定義為網(wǎng)絡(luò)中所有ES的負載的均衡程度，值越小越好。考慮經(jīng)濟學(xué)中用來測量收入分配差異程度的基尼系數(shù)[13]與負載均衡的相似性，引入基尼系數(shù)來計算負載均衡，其數(shù)學(xué)模型如式(2)

(2)

其中，gi為將每戶收入由低到高排列后，從第1戶到第i戶的總收入。

同理，用每個ES的負載表示每戶收入； ?i表示將所有ES的負載從小到達排列后，從第1個ES到第i個ES的負載之和。將負載均衡定義為式(3)

(3)

ES的時延包括用戶請求經(jīng)基站轉(zhuǎn)發(fā)到達ES，產(chǎn)生的本地傳送時延和ES將部分負載遷移到遠程云處理產(chǎn)生的遠程傳送時延。對于每個子網(wǎng)，ES的本地傳送時延Dh表示所有用戶請求經(jīng)基站轉(zhuǎn)發(fā)到達ES的總時延(本文不考慮移動用戶請求接入基站之前的無線時延)，數(shù)學(xué)模型表示為式(4)

(4)

其中，dhj是第j個基站與其所屬的第h個ES之間的距離；η為電磁波的傳播速度。

對于每個ES，遠程傳送時延Rh是將負載中將超出W·90%的部分遷移到遠程云處理產(chǎn)生的(假設(shè)遠程云的計算能力非常強，則這部分負載產(chǎn)生的處理時延和排隊時延可以忽略不記)，數(shù)學(xué)模型如式(5)

(5)

其中，T為將負載遷移到遠程云處理所需的最大時延；W為ES負載的閾值。

(6)

其中，dh=Dh+Rh， 表示每個ES的時延。

由以上分析可知，ES放置問題是一個多目標(biāo)優(yōu)化問題，傳統(tǒng)優(yōu)化方法難以解決。定義一個新的指標(biāo)(系統(tǒng)開銷)，通過加權(quán)將多個優(yōu)化目標(biāo)轉(zhuǎn)化為一個，實現(xiàn)目標(biāo)函數(shù)降維，降低實現(xiàn)難度。

定義3 系統(tǒng)開銷S。 系統(tǒng)開銷定義為負載均衡和平均時延的加權(quán)和，其值越小，表明系統(tǒng)性能越好，如式(7)

(7)

其中，μ是經(jīng)驗系數(shù)。根據(jù)經(jīng)驗，在優(yōu)化過程中，負載均衡和平均時延同樣重要，所以μ的值為0.5。

經(jīng)過以上分析，將WMAN中的ES放置問題建模如下

(8)

其中，式(8a)是優(yōu)化的目標(biāo)函數(shù)。式(8b)～(8d)表示實現(xiàn)優(yōu)化目標(biāo)的約束條件；式(8b)表示所有子網(wǎng)能夠覆蓋全部用戶；式(8c)表示所有基站都必須被分配給ES，且一個基站只能被分配給一個ES；式(8d)表示所有ES都被放置在基站上，且一個基站只能放置一個ES。

2 基于改進遺傳算法的放置方法

2.1 傳統(tǒng)遺傳算法

GA是一種經(jīng)典的種群進化算法，它模擬生物優(yōu)勝劣汰的進化機制，最終得到問題的最優(yōu)解。問題的可行解被抽象為染色體上基因型對應(yīng)的表現(xiàn)型，求解優(yōu)化問題的最優(yōu)解等同于尋找最優(yōu)的基因型。但GA存在容易陷入局部最優(yōu)、收斂性差和在問題規(guī)模較大時尋優(yōu)精度較低等問題，為此，本文提出MGA改善相關(guān)問題并解決大規(guī)模WMAN中的ES放置問題。

2.2 算法描述

算法主要思想：考慮大規(guī)模離散優(yōu)化問題編碼變量較多的問題，提出了實數(shù)編碼的方式，降低了算法的實現(xiàn)難度與計算量；由于初始種群對于智能進化算法有較大影響，在算法開始時，采用多輪隨機不重復(fù)解策略維持初始種群的多樣性，擴大了全局搜索范圍；在進行選擇操作時，采用部分優(yōu)秀父代和子代共同競爭的策略產(chǎn)生新的子代，保證了種群多樣性，增強了算法的尋優(yōu)能力；進行交叉操作時，提出了優(yōu)秀父代非線性交叉節(jié)點選擇算法，該算法使得MGA在早期擁有較強的全局搜索能力，在后期擁有較快的收斂速度；變異操作時，結(jié)合提出的編碼方式，采用隨機打亂整條染色體上基因排列的策略，能提供全新的解，進一步擴大了算法的全局搜索范圍。

2.3 染色體編碼

大規(guī)模WMAN中的ES放置問題本質(zhì)是尋找ES到基站的映射關(guān)系，這是一個離散多目標(biāo)優(yōu)化問題，傳統(tǒng)的二進制編碼方法難以解決。為了減少編碼變量，進而降低算法運算時間，并且易于進行交叉和變異操作，本文使用一個二維實數(shù)矩陣對染色體進行編碼。

如表1所示，矩陣的形狀為m×3，每一行表示一個ES的部署關(guān)系和一個基站的分配關(guān)系。每行中,第一個數(shù)據(jù)表示基站編號；第二個數(shù)據(jù)代表在此基站上放置的ES的編號，若為0，表示不放置；第3個數(shù)據(jù)是ES的編號，表示將此基站分配給ES。以表1為例，第一行表示在第一個基站上放置第一個ES；第二行表示第二個基站不放置ES并將第二個基站分配給第二個ES；第m行表示在第m個基站上放置第二個ES。

表1 染色體基因編碼

因為WMAN中的ES放置問題存在約束條件，所以矩陣元素的取值必須滿足以下規(guī)則：

(1)第二列元素的取值是一個整數(shù)，來自 [0,k+1]；

(2)第三列元素的取值是一個整數(shù)，來自 [1,k+1]；

(3)在每行中，如果第二列的數(shù)據(jù)不為0，則第三列的數(shù)據(jù)和第二列相同。

2.4 初始化種群

種群由一組染色體組成，每一條染色體都是問題的一組可行解；初始種群對于問題求解有重要影響。為了保證初始種群的多樣性并提高搜索效率，采用多輪隨機不重復(fù)解策略產(chǎn)生初始種群，過程如下：

(1)產(chǎn)生形狀為N×m×3的零數(shù)組保存種群，轉(zhuǎn)入步驟(2)；

(2)隨機產(chǎn)生一個形狀為m×3的數(shù)組，作為問題的一組解，與編碼規(guī)則比較，若滿足編碼規(guī)則，轉(zhuǎn)入步驟(3)；否則，重復(fù)步驟(2)；

(3)將滿足編碼規(guī)則的染色體加入種群，并判斷當(dāng)前種群的數(shù)量是否為N， 若滿足，則結(jié)束；否則，轉(zhuǎn)入步驟(2)。

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

適應(yīng)度函數(shù)應(yīng)該反映染色體的優(yōu)劣程度，以便為種群進化方向提供指導(dǎo)。染色體的優(yōu)劣程度與負載均衡和平均時延有關(guān)。將適應(yīng)度函數(shù)定義為式(9)，適應(yīng)度函數(shù)值越小，染色體越優(yōu)秀；否則，染色體的性能越差

(9)

2.6 選擇操作

對于大規(guī)模放置問題，選擇操作主要考慮避免陷入局部最優(yōu)與保證種群的多樣性，本文使用部分父代和子代共同競爭的方式選擇進入下一代的個體，過程如下：

(1)產(chǎn)生形狀為N×m×3的零數(shù)組保存種群；轉(zhuǎn)入步驟(2)；

(2)對所有染色體按照適應(yīng)度函數(shù)值進行從小到大排序，保存前20%的染色體作為優(yōu)秀父代染色體，轉(zhuǎn)入步驟(3)；

(3)隨機選擇一條步驟(2)中的剩余染色體作為母親染色體；隨機在步驟(2)的優(yōu)秀父代染色體中選擇一條作為父親染色體；將父親、母親染色體進行交叉、變異操作，產(chǎn)生子代染色體；轉(zhuǎn)入步驟(4)；

(4)根據(jù)式(9)計算子代染色體的適應(yīng)度函數(shù)值，并與步驟(2)中的所有優(yōu)秀父代染色體的適應(yīng)度函數(shù)值比較，若子代染色體的適應(yīng)度函數(shù)值更小，則將子代染色體加入種群，轉(zhuǎn)入步驟(5)；否則，重復(fù)步驟(4)；

(5)判斷子代種群的數(shù)量，若為N，退出選擇過程；否則，轉(zhuǎn)入步驟(3)；

通過部分父代和子代共同競爭的選擇策略，有效避免了陷入局部最優(yōu)并保證了子代種群的多樣性。

2.7 變異與遺傳操作

(1)交叉操作對于算法的全局搜索能力有重要影響，結(jié)合大規(guī)模放置問題變量較多的特點，提出非線性優(yōu)秀父代交叉點選擇算法進行交叉操作，如下

(10)

2)根據(jù)2.6節(jié)的步驟(3)確定父親染色體和母親染色體，并將父親、母親染色體上位于交點之后的所有基因交換，交換后的父親染色體作為子代染色體，轉(zhuǎn)入步驟(3)；

3)對子代染色體按2.3節(jié)的編碼規(guī)則進行檢查，并進行規(guī)則化；

采用該策略，在算法前期，交叉節(jié)點的位置靠前且變化緩慢，算法有較強的全局搜索能力；隨著算法進行，交叉節(jié)點的位置以更快的速度向染色體的末端移動，算法的收斂速度越來越快；并且始終與優(yōu)秀父代染色體發(fā)生交叉也在一定程度上保證了收斂性。

(2)采用的變異策略為隨機打亂整條染色體上的基因排列。變異操作對于算法的全局搜索能力重要意義。對于2.3節(jié)的實數(shù)編碼，隨機打亂染色體的基因排列將導(dǎo)致：①ES的位置改變；②基站與ES間的分配關(guān)系改變。所以，隨機打亂整條染色體上的基因排列可以為算法提供前所未有的解。

2.8 算法流程

步驟1 按照2.3確定編碼規(guī)則，按照2.5節(jié)確定適應(yīng)度函數(shù)F(X)， 轉(zhuǎn)入步驟2；

步驟2 初始化參數(shù)(種群數(shù)量N，權(quán)重性能參數(shù)，經(jīng)驗系數(shù)μ，最大遠程傳送時延T)，按照2.4節(jié)初始化種群，設(shè)定迭代次數(shù)L，轉(zhuǎn)入步驟3；

步驟3 根據(jù)式(9)計算所有染色體的適應(yīng)度函數(shù)F(X)， 按照2.6節(jié)進行選擇操作，產(chǎn)生子代種群，轉(zhuǎn)入步驟4；

步驟4 判斷是否滿足退出循環(huán)的條件，若滿足條件，退出循環(huán)，轉(zhuǎn)入步驟5；否則，轉(zhuǎn)入步驟3；

步驟5 根據(jù)式(8a)計算種群中所有染色體的系統(tǒng)總開銷，找出系統(tǒng)總開銷最小的染色體的基因型(對應(yīng)矩陣X和Y)，根據(jù)X和Y以及式(3)～式(6)計算負載均衡和平均時延。

3 仿真與結(jié)果分析型

3.1 數(shù)據(jù)集說明

本節(jié)使用來自上海市電信局的真實數(shù)據(jù)集對算法進行仿真。原始的數(shù)據(jù)集中包含大量無用信息，必須經(jīng)過處理才能使用。經(jīng)過處理后得到包括563 902個用戶和2753個基站的有用信息，包括基站的編號、經(jīng)度、緯度、15天的累計接入時長(作為負載)和用戶數(shù)量等信息，部分基站信息見表2。

表2 部分基站的信息

3.2 仿真環(huán)境及實驗設(shè)計

仿真環(huán)境配置為Intel(R) Core(TM) i7-9750H CPU 2.60 GHz處理器，Windows 10操作系統(tǒng)，Python 3.7版本。設(shè)置λ為0.6；N為60；T為0.5 s。為了評估本文算法的性能，選取兩種比較典型的放置算法(Random[12]和K-means[14])以及文獻[12]的混合整數(shù)線性規(guī)劃(MIP)方法與MGA進行對比，并設(shè)計了以下兩組實驗：

實驗1：保持ES和基站的數(shù)量之比為ρ=0.1， 不斷增加基站的數(shù)量，測試各種方案的放置性能。這一組實驗旨在研究各種復(fù)雜環(huán)境對放置效果的影響。盡管保持了ρ=0.1， 但是少量的基站不能完全反映WMAN中復(fù)雜的基站分布情況，所以需要對不同基站數(shù)量下的放置情況進行研究。

實驗2：保持基站的數(shù)量為2753，不斷增加ES的數(shù)量，測試各類方法的性能。這一組實驗旨在研究基站數(shù)量一定時，不同數(shù)量的ES對放置結(jié)果的影響，能夠找出最佳的ES放置比例。

3.3 實驗結(jié)果分析

(1)實驗1結(jié)果分析

實驗1的結(jié)果如圖2所示，橫坐標(biāo)為基站的數(shù)量。圖2(a)中，當(dāng)基站數(shù)量為1280時，MGA的平均時延最小，為0.13 s，相比K-Means、Random和MIP分別減少了0.16 s、0.11 s和0.08 s；可以發(fā)現(xiàn)，隨著基站數(shù)量增加，4種算法的平均時延均基本保持不變，但MGA的平均時延是最小的，其次是MIP、Random和K-Means；在基站數(shù)量為1820時，K-Means、MIP和MGA的平均時延均有減少的趨勢，分析其原因是：此時數(shù)據(jù)集中出現(xiàn)了一個基站分布較為密集的區(qū)域，這3種方案都在這個區(qū)域找出了較為合理的ES布局，而Random沒有。

圖2 ρ=0.1時放置性能隨基站數(shù)量的變化

圖2(b)中，隨著基站數(shù)量的增加，MIP、Random和K-Means的負載均衡均有下降的趨勢，這是由于ρ保持不變，隨著基站數(shù)量增加，ES的數(shù)量也增加，每個基站可以分配的潛在ES的數(shù)量也增加，基站會被分配給更加合理的ES；對于MGA，隨著基站數(shù)量增加，算法計算迅速增大，在一定的計算能力下，尋優(yōu)精度有所下降，所以負載均衡有輕微的上升，但始終優(yōu)于其余3種方案。

圖2(c)中，MGA的系統(tǒng)開銷小于MIP、Random和K-Means，相比以上各種方案，系統(tǒng)開銷平均下降了約35.3%、45.2%和52.7%；MGA的系統(tǒng)開銷保持在0.17左右，說明其足以應(yīng)對大規(guī)模WMAN中復(fù)雜的基站分布情況。

(2)實驗2結(jié)果分析

實驗2的結(jié)果如圖3所示，橫坐標(biāo)為ES的數(shù)量。圖3(a)中，MGA的平均時延相比MIP、Random和K-Means平均分別減少了0.05 s、0.09 s和0.12 s；當(dāng)ES的數(shù)量為280時，4種方案的平均時延都表現(xiàn)為上升，分析其原因為此時所有方案都將ES放置在了某些用戶較為稀疏的地方，導(dǎo)致了這些ES的時延增加，進而影響了平均時延；放置其余數(shù)量的ES時，所有方案的平均時延均有下降的趨勢，因為隨著ES數(shù)量增加，ρ持續(xù)增大，每個ES都趨向于負責(zé)更近、數(shù)量更少的基站，所以平均時延下降。

圖3 基站數(shù)量一定時放置性能隨ES數(shù)量的變化

圖3(b)中，K-Means的負載均衡隨ρ增加而下降，分析其原因是：K-Means是基于距離的聚類方法，當(dāng)基站數(shù)量固定時，聚類數(shù)量越多，每個聚類中的基站數(shù)量越少；而單個基站的負載相差不大；所以聚類中基站數(shù)量越少，ES的負載相差越?。黄溆?種方案的負載均衡都隨ρ增加而上升，Random上升的原因是方法本身存在隨機性，MGA和MIP上升是因為隨著ρ增加，解空間迅速增大，受計算能力的限制，尋優(yōu)精度下降；但是MGA的負載均衡始終優(yōu)于其它方案，相比MIP、Random和K-Means平均分別下降了19.1%、18.9%和18.6%。

圖3(c)中，MGA相比MIP、Random和K-Means系統(tǒng)開銷平均下降了約54.1%、42.9%和20.6%；4種方案的性能曲線的變化都在ES的數(shù)量為280時開始變得緩和，說明此后再增加ES的數(shù)量帶來的回報開始減少。所以，對于數(shù)據(jù)集對應(yīng)的真實WMAN，保持ES與基站的數(shù)量之比ρ=280/2753=0.1017時，ES放置有最大的回報率。

3.4 分析適應(yīng)度函數(shù)的權(quán)重性能系數(shù)

適應(yīng)度函數(shù)F(X)的權(quán)重性能系數(shù)λ不同于計算系統(tǒng)開銷時的經(jīng)驗系數(shù)μ。λ對MGA的尋優(yōu)精度有重要影響。采用實驗的方法對λ的最佳取值進行研究，設(shè)置基站數(shù)量為500，ES的數(shù)量為50,運行20次程序，然后取平均值，得到圖4。由圖4可知，λ=0.6時，MGA的尋優(yōu)效果最好。(注：本文其它實驗的λ均為0.6)

圖4 系統(tǒng)開銷隨λ的變化

3.5 收斂性分析

設(shè)置基站數(shù)量為500，ES的數(shù)量為50，λ=0.6，運行程序20次，然后取平均值得到圖5。由圖5可知，MGA在前600次迭代過程中收斂速度較快，迭代1400次后算法的系統(tǒng)開銷保持不變，找到全局最優(yōu)解。使用MGA使系統(tǒng)開銷從0.208下降到0.172，下降了約17.3%，并在后期保持不變。

圖5 系統(tǒng)開銷的收斂曲線

4 結(jié)束語

針對移動邊緣計算中WMAN環(huán)境下的ES放置問題進行了研究。對ES的放置場景進行了介紹，通過劃分子網(wǎng)的思想將其建模為優(yōu)化負載均衡和平均時延的多目標(biāo)優(yōu)化問題。提出一種改進的遺傳算法解決該優(yōu)化問題。MGA在編碼、初始化種群、選擇、交叉和變異等操作方面均做了較大改進，增強了算法的全局搜索能力，保證了算法的收斂性?；谡鎸崝?shù)據(jù)集的仿真結(jié)果表明，相比于其它算法，當(dāng)ρ在0.036到0.167內(nèi)變化時，MGA能夠很好解決復(fù)雜WMAN中的ES放置問題，對于解決其它大規(guī)模離散優(yōu)化問題也有一定的幫助。ES放置問題是一個NP難的多目標(biāo)優(yōu)化問題，隨著基站數(shù)量增加，解空間急劇增大。傳統(tǒng)優(yōu)化算法難以解決，未來會將考慮使用多目標(biāo)優(yōu)化算法，其能夠快速找到Pareto最優(yōu)解，有效解決問題。