邊緣計算中的邊緣服務器放置策略

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

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

0 引 言

在移動邊緣計算中，將具有計算能力和數據存儲功能的邊緣服務器(edge server，ES)放置在基站上，能夠將核心網的部分功能下沉到網絡邊緣，有效降低網絡傳輸時延。這使得研究ES放置問題具有重要意義。

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

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

1 ES放置模型分析

1.1 物理網絡模型

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

圖1 ES放置場景

1.2 問題描述

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

1.3 ES放置模型

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

(1)

其中，Bh表示第h個子網；wi為ui的負載。

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

(2)

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

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

(3)

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

(4)

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

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

(5)

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

(6)

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

由以上分析可知，ES放置問題是一個多目標優化問題，傳統優化方法難以解決。定義一個新的指標(系統開銷)，通過加權將多個優化目標轉化為一個，實現目標函數降維，降低實現難度。

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

(7)

其中，μ是經驗系數。根據經驗，在優化過程中，負載均衡和平均時延同樣重要，所以μ的值為0.5。

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

(8)

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

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

2.1 傳統遺傳算法

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

2.2 算法描述

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

2.3 染色體編碼

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

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

表1 染色體基因編碼

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

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

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

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

2.4 初始化種群

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

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

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

(3)將滿足編碼規則的染色體加入種群，并判斷當前種群的數量是否為N， 若滿足，則結束；否則，轉入步驟(2)。

2.5 適應度函數

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

(9)

2.6 選擇操作

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

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

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

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

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

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

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

2.7 變異與遺傳操作

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

(10)

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

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

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

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

2.8 算法流程

步驟1 按照2.3確定編碼規則，按照2.5節確定適應度函數F(X)， 轉入步驟2；

步驟2 初始化參數(種群數量N，權重性能參數，經驗系數μ，最大遠程傳送時延T)，按照2.4節初始化種群，設定迭代次數L，轉入步驟3；

步驟3 根據式(9)計算所有染色體的適應度函數F(X)， 按照2.6節進行選擇操作，產生子代種群，轉入步驟4；

步驟4 判斷是否滿足退出循環的條件，若滿足條件，退出循環，轉入步驟5；否則，轉入步驟3；

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

3 仿真與結果分析型

3.1 數據集說明

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

表2 部分基站的信息

3.2 仿真環境及實驗設計

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

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

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

3.3 實驗結果分析

(1)實驗1結果分析

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

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

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

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

(2)實驗2結果分析

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

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

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

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

3.4 分析適應度函數的權重性能系數

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

圖4 系統開銷隨λ的變化

3.5 收斂性分析

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

圖5 系統開銷的收斂曲線

4 結束語

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