基于成本感知的邊緣服務器部署方法

史振飛，胡 朋，李 波，楊志軍，丁洪偉+

(1.云南大學 信息學院，云南 昆明 650500；2.優備科技股份有限公司 研發部，云南 昆明 650000)

0 引 言

由于移動終端設備物理資源的限制，其有限的資源(如電池壽命、計算能力、網絡帶寬等)與移動設備對計算以及儲存等資源的需求，這兩者之間的矛盾給未來移動終端平臺帶來了巨大的挑戰[1-3]。

為了提高移動終端應用的性能，可以將移動用戶產生的計算任務轉移到資源豐富的遠程云上，實現遠程云計算(MCC)[4]。然而，云數據中心通常位于距離用戶較遠的區域，因此移動應用程序會遭受較高的端到端(D2D)延遲。對于時延敏感型應用，如增強現實(AR)、虛擬現實(VR)、在線游戲和自動駕駛等，這些延遲是難以容忍的。為了彌補云計算的不足，引入了邊緣計算來減少傳輸延遲，并通過更接近移動設備的邊緣服務器實現實時控制[5]。而移動邊緣計算[6](MEC)能夠在靠近用戶端的地方提供計算和儲存服務。

現有的大多數研究都假設其所需的邊緣服務器已經部署在相應的位置，僅僅關注卸載和資源分配策略[7，8]。然而，沒有最佳的邊緣服務器的放置策略，這些工作都是不現實的。因此，研究邊緣服務器的部署問題，為移動邊緣計算的其它工作奠定基礎，具有重要意義[9，10]。雖然有一些關于邊緣服務器放置的研究旨在最大限度地減少移動用戶和邊緣服務器之間的平均訪問延遲和能耗，但他們大多都忽視了如何在保證延遲約束的情況下最小化邊緣服務器數量的問題，這對終端用戶和邊緣服務提供商來說是非常重要的。部署的服務器數量越多，用戶的體驗質量就越好，理想的情況是在每個基站(base station，BS)上都部署邊緣服務器，但這是不現實的，因為服務提供商的預算總是有限的。因此，研究如何在滿足用戶需求(如時延)的同時，如何為邊緣服務器提供商節約部署成本具有重要意義。

1 相關工作

近年來，有關云放置的研究已經取得了一定的成果，可為邊緣服務器的放置提供一定的參考。文獻[2]針對AP的重復排序過程過多，從而導致算法的效率底下，提出了一種NHA和粒子群(PSO)優化算法來解決延遲問題。文獻[11]研究了無線城域網(WMAN)中基于工作流應用(WAs)的云放置問題，提出了一種基于粒子群算法的云放置策略，并且該算法具有編碼庫更新模式(PGEL)的遺傳算法算子。文獻[12]研究了邊緣云放置問題，將其表述為一個多目標優化問題，提出了一種基于k中值和混合整數二次規劃的近似方法，目標是使云之間的負載均衡且通信時延最小。文獻[13]研究了在物聯網(IOT)網絡中的大量無線接入點(AP)上部署云服務器，以優化部署成本和網絡延遲。并且提出了一種容錯的云部署方案，當網絡中部署的云出現故障時，通過軟件定義網絡技術及時啟動容錯的云服務器，來保證網絡延遲的穩定性。

在現有的邊緣服務器部署研究中，文獻[14]研究了移動邊緣計算中的邊緣服務器部署問題，并驗證了邊緣服務器部署問題是NP-hard問題。提出了一種基于整數線性規劃(MIP)的系統部署方法，當問題規模較小時，MIP方法給出的優化結果更精確，但當問題規模較大時，優化結果的精度降低。文獻[15]研究了關于ES能耗的邊緣服務器布局問題，設計了一種基于粒子群(PSO)算法來優化ES的能耗。文獻[16]研究了WMAN環境下的ES部署問題，將其描述為一個多目標約束優化問題，提出了一種基于混合整數規劃的部署方法。文獻[17]設計了一種MNSGA-Ⅱ算法來平衡ES之間的負載和通信延遲。文獻[18]研究了在異構網絡中ES的放置，把響應時間和能耗作為任務開銷，提出了一種基于AP適應性評價的自適應聚類算法(MTO)來優化計算任務的任務開銷。文獻[19]研究了在無線城域網(WMAN)中ES的放置問題，他們將貪婪算法和遺傳算法(GA)相結合，有效地解決了邊緣服務器之間的負載均衡和移動用戶的服務質量(QoS)的需求，同時最小化邊緣服務器的數量。文獻[20]研究了在超密集網絡(UDN)中部署ES，提出了一種基于排隊理論和矢量量化(VQ)技術，在給定的UDN環境下優化ES的數量、位置和移動用戶分配。

本文對無線城域網(WMAN)中ES放置的時延和成本進行研究，建立了基于部署成本和時延的邊緣服務器部署模型，并利用權重系數將多個目標連接起來。提出了基于縱橫交叉策略的鯨魚優化算法(crosswise strategy whale optimization algorithm，CSWOA)的ES部署方法，首先通過精英反向學習策略構造新種群，提高種群的多樣性和全局收斂速度，其次，利用改進的非線性收斂因子能更好地權衡全局探索和局部搜索能力，最后，利用縱橫交叉策略提高算法跳出局部最優的能力。

2 系統模型

2.1 網絡模型

本文考慮WMAN環境下的ES部署問題，可以將ES部署問題看作是一個連通的無向圖G=(B∪S，E) 由移動終端設備、基站和邊緣服務器可能部署的位置組成。其中B={b1，…，bj，…，bn} 代表基站的合集，|B|=n，S={s1，…，si，…，sk} 表示ES部署位置的集合，|S|=k，E表示基站與ES之間的關系。當k個ES被放置后，將基站集合劃分為k個子集，用集合C={c1，…，ci，…，ck} 表示，|C|=|S|=k， 且各個子集之間的基站互不相交。每個子集中的某一個基站上放置一個邊緣服務器，用來負責處理這個子集中所有基站上的任務。在WMAN中邊緣服務器放置模型如圖1所示。

圖1 邊緣服務器放置系統模型

對于基站集合 {b1，…，bj，…，bn} 中的每一個基站bj(j=1，2，…，n)， 用l(bj)、w(bj) 來分別表示它的位置和工作負載，對于邊緣服務器集合 {s1，…，si，…，sk} 中的每一個服務器si(i=1，2，…，k)， 用l(bi)、w(bi) 來分別表示它的部署位置和工作負載，用ci表示分配給ESsi的基站集合，則ESsi上的工作負載w(si)=w(b1)+w(b2)+…+w(bi)。 本文使用歐式距離來表示基站bj和邊緣服務器si之間的距離如式(1)所示

(1)

為了能夠準確描述ES部署問題，本文引入了一個矩陣X表示ES的放置位置和矩陣Y表示基站與ES的分配關系。二進制決策變量xij和yij分別表示矩陣X和矩陣Y的元素。xij，yij∈[0，1]， 當時xij=1， 代表將ESsi部署在基站bj上，否則，xij=0； 當yij=1時，代表將基站bj分配給ESsi，否則，yij=1。其中i=1，2，…，k，j=1，2，…，n。

2.2 時延模型

本文不考慮移動用戶請求接入基站之前的無線傳輸延遲，因為改變ES的位置并不影響用戶請求接入基站的時延，它只取決于用戶的服務計劃和帶寬分配策略[21]。因此，本文只考慮基站與ES之間的端到端延遲，并且根據香農公式，將基站bj上的任務上傳到邊緣服務器si的傳輸速率rij如式(2)所示

(2)

其中，w表示信道帶寬，pj表示基站bj的發射功率(本文假設所有基站的發射功率相同)，hij表示基站bj與ESsi之間的信道增益，N0表示噪聲功率。則基站與ES之間的傳輸時間Tij如式(3)所示

(3)

其中，d(si，bj) 和rij分別表示bj和si之間的距離和傳輸速率。

當邊緣服務器si上的負載w(si)大于其上的闕值wmax時，ES不再處理基站所轉發的任務請求，然后將基站上的剩余任務轉移到云計算中心進行處理，則傳輸時延Ti，cloud如式(4)所示

(4)

由式(3)和式(4)可知，邊緣服務器si上的總時延Ti如式(5)所示

(5)

因此邊緣服務器上的平均時延如式(6)所示

(6)

2.3 成本模型

部署ES的成本主要包括兩個部分：固定成本和動態成本。當ES被放置在某個基站上時，我們需要去租用場地和安裝ES所涉及的基本設備，這部分成本是由ES的位置決定的，被稱為固定成本。此外，邊緣服務提供商還需要在部署位置安裝提供計算資源的處理器，這部分成本由處理器的數量組成，稱為動態成本。故部署單個ES的成本可以如式(7)所示

(7)

其中，fi表示邊緣服務器si的安裝成本(工人費用，每個ES的安裝成本相同)，γi表示邊緣服務器si放置在基站bj時需要支付額外的費用(也就是租用場地的費用，這部分費用由基站bj上的負載決定)，c表示一個處理器的價格，mi表示邊緣服務器si上處理器的數量，η表示每單位距離輸電線的價格。

因此，邊緣服務器的平均部署成本可以表示為式(8)

(8)

為了便于比較，消除時延和成本之間的差別，本文采用max-min歸一化方法將單個ES的時延和成本數據映射到[0，1]區間上，如式(9)和式(10)所示，然后，再使用式(6)和式(8)重新計算平均時延和平均部署成本

(9)

(10)

定義1 系統成本被定義為通過式(9)和式(10)重新計算后的式(6)和式(8)的線性加權和，用來表示系統的時延和成本代價，算法性能越好，系統成本越小，公式如式(11)所示

(11)

經過以上分析，ES部署問題的數學模型可以表述如式(12)所示

MinC

(12)

(13)

(14)

ci∩cj=?i，j=(1，2，…，k)

(15)

(16)

w(si)

(17)

其中，約束(13)表示ES只能放置在基站上；約束(14)表示一個基站只能分配給一個邊緣服務器；約束(15)表示任何兩個子集中的基站之間互不交叉；約束(16)表示ES覆蓋所有的基站，并且每個ES負責處理其所覆蓋范圍內全部基站上的任務；約束(17)表示每個ES的工作負載小于ES能夠處理的最大負載，其中wmax為ES的負載闕值。

3 基于改進鯨魚優化算法的部署方法

ES部署問題已被驗證是一個NP-hard問題[14]，傳統的數學方法(如窮舉法、梯度下降法等)難以解決這類問題，而群體智能優化算法能夠以較小的計算代價得出近似最優解。作為一種新的群體智能優化算法，鯨魚優化算法(whale optimization algorithm，WOA)是模仿座頭鯨的狩獵行為演化而來[22，23]，與粒子群(particle swarm optimization，PSO)、人工蜂群算法(artificial bee colony algorithm，ABCA)等傳統智能優化算法相比，WOA具有較強的全局尋優能力和穩定性，且收斂速度較快[24]。因此本文選擇WOA算法來解決ES部署問題。但基本WOA易陷入局部最優。為了彌補基本WOA的不足，本文提出了一種基于縱橫交叉策略的WOA算法，并使用改進的WOA算法解決ES部署問題，以期獲得更好的部署方案。

3.1 個體編碼

一種ES放置方案，包括ES放置和基站分配。因此，編碼方案應該同時包含這兩種關系。且將基站分配給ES是一種一對多的映射關系，如上所述，所有基站都是潛在的ES放置位置。本文參考文獻[25]的編碼方法，采用二維矩陣作為編碼方案。利用這種編碼方案可以帶來以下好處。首先，邊緣服務器的位置很容易找到。其次，清晰地展示了基站分配。三是簡化約束違反判斷。編碼方式見表1，用’1’表示ES的放置位置和與基站之間的分配關系，個體編碼方式見表1。

表1 個體編碼方式

在表1中，個體編碼方式為k×2n的矩陣，每一行都表示一個邊緣服務器，且每一列都代表一個基站。前n列表示部署矩陣X，后n列表示分配矩陣Y。在矩陣X中，每一行的標記為1的位置表示邊緣服務器的部署位置，在矩陣Y中，每一列的標記為1的位置表示將此列所表示的基站分配給該行所代表的邊緣服務器。以表1中為例：第1行表示將編號為1的邊緣服務器部署在編號為1的基站上，并把編號為1的基站分配給它；第k行表示將編號為k的邊緣服務器部署在編號為n的基站上，并把編號為2、n的站分配給它。由于約束(13)和約束(14)，在矩陣中被標記的位置應遵守以下規則：

(1)在矩陣X中，每一行必須有一個被標記且最多一個被標記，并且任意兩行之間的標記不在同一列。

(2)在矩陣Y中，每一列有且只有一個被標記。

(3)在矩陣X和Y中，相同列的標記一定要處于相同行，因為部署了邊緣服務器的基站一定要劃分給該邊緣服務器。

3.2 適應度函數

適應度函數用于種群的更新迭代，適應度函數值的大小能夠反映種群中個體的好壞程度。本文將適應度函數定義為式(18)，即用平均傳輸時延和平均部署成本的線性加權和作為適應度函數。適應度值越小，部署位置越好，個體越優

(18)

3.3 包圍獵物

假設某一個獵物個體目前處于一個相對較優的位置，而鯨魚群體則向該獵物移動。位置更新公式如式(19)所示

xi(t+1)=xbest(t)-A|Cxbest(t)-xi(t)|

(19)

A=2ar1-a

(20)

C=2r2

(21)

式中：xi(t) 表示第i個鯨魚個體的位置，t為當前迭代次數；xbest(t) 表示當前最優鯨魚個體的位置；A和C為系數變量；r1，r2為[0，1]上的隨機數；a為收斂因子。

3.4 泡網攻擊

發泡網攻擊是座頭鯨特殊的捕食方式，通過螺旋上升游動的方式縮小范圍的過程，來逐漸靠近目標獵物。當 |A|<1時，假設鯨魚個體按照50%的概率來確定更新方式，則位置更新公式如下

(22)

其中，p為[0，1]區間的值；b=1；l為[0，1]區間的值。

3.5 隨機搜索獵物

當 |A|≥1時，隨機在種群中選擇一個個體作為目標獵物，能在一定程度上提高算法的整體搜索能力。則位置更新公式如下

xi(t+1)=xrand(t)-A|Cxrand(t)-xi(t)|

(23)

其中，xrand(t) 表示當前種群中隨機選擇的鯨魚個體。

3.6 改進的非線性收斂因子

WOA算法中的參數A用于調整算法的全局探索和局部開發能力。在迭代過程中，收斂因子a線性遞減，使得算法收斂速度慢。為了使算法在迭代優化過程中具有較強的整體搜索能力和局部發掘能力，并保持較快的收斂速度和收斂精度。本文使用一種新的非線性收斂因子，計算公式如下

(24)

其中，t表示當前迭代次數；Max_iter為最大迭代次數；amax和amin表示控制參數a的最大值和最小值。本文取amax=0.8，amin=0.4。

3.7 縱橫交叉策略

為了提高算法的全局收斂速度，本文引入了縱橫交叉策略[22，26]，利用水平交叉提高算法的搜索范圍，通過垂直交叉對最優個體進行交叉運算，不僅能夠提高種群的多樣性又能減小算法陷入局部最優解的可能。縱橫交叉策略產生的個體與父代個體進行競爭產生最優個體，從而能夠提高算法的求解精度和收斂速度。

(1)橫向交叉

橫向交叉是對種群中的兩個不同個體在相同維度下進行交叉運算，從而提高算法的全局搜索能力。假設在第d維對父代個體Fi，d和Fj，d進行橫向交叉，則后代個體由下式產生

xi，d=r1·Fi，d+(1-r1)·Fj，d+c1·(Fi，d-Fj，d)

(25)

xj，d=r2·Fj，d+(1-r2)·Fi，d+c2·(Fj，d-Fi，d)

(26)

其中，r1，r2為[0，1]之間均勻分布的常數；c1，c2為[-1，1]之間上的值；xi，d和xj，d是父代個體Fi，d和Fj，d在第d維產生的后代個體。

(2)縱向交叉

縱向交叉是依據概率pc對最優個體Fbest在兩個不同維度進行交叉運算，且每次交叉操作只產生一個子代個體。假設對Fbest個體在第d1和d2維進行交叉，產生子代個體公式如下

(27)

3.8 精英反向學習策略

(28)

其中，maxxi，d和minxi，d表示第i個個體xi在第d維的最大值和最小值。

3.9 CSWOA算法描述

CSWOA算法步驟見表2。

表2 CSWOA算法步驟

4 仿真與結果分析

4.1 數據集說明

本文使用一個包含上海電信局城市移動用戶接入信息和基站位置信息的真實網絡數據集進行仿真。通過統計和過濾去除沒有用的信息后，最終得到了2753個基站的所有信息，包括基站位置(經緯度)、覆蓋的用戶數量以及每個基站連續15天的累積接入小時數(作為基站的工作負載)。部分基站信息見表3。

表3 部分基站信息

4.2 實驗設置

實驗軟硬件環境為IntelRCoreTMi7-7700 CPU 3.60 GHz處理器、Windows10操作系統、Python 3.7版本、Pycharm編程軟件，Pycharm Community Edition 2020版本。主要參數設置見表4。

表4 參數設置

其中，基站bj與邊緣服務器si之間的信道增益hij=d(si，bj)-β，β為路徑損失常數，且β=4；γi表示邊緣服務器si放置在某個基站上的價格，γi=邊緣服務器放置基站上的負載×0.01，時延權重系數α=0.5。

4.3 對比算法

為了驗證本文算法的性能，提出了以下4種算法與本文算法進行比較。

(1)K-Means：該方案首先根據基站的位置，采用k-均值方法將所有基站聚類成k個子簇，獲得k個聚類素數，然后將ES放置在距離聚類素數最近的基站上，最后將每個簇中的基站分配給ES。

(2)Top-K：該方案將k個ES放置在k個負載最大的基站上，然后迭代所有剩余的基站并將其分配給最近的ES。

(3)MIP：整數線性規劃。

(4)文獻[24]：改進的麻雀搜索算法。

4.4 實驗分析

基站數量不變，增加ES的數量，觀察平均時延的變化，當ES的數量為100時，K-Means、Top-K、MIP、CSSA和CSWOA的平均時延分別是0.3374、0.021 89、0.017 74、0.018 16、0.0106，CSWOA相比于其它4種算法分別降低了約96.8%、51.6%、40.2%和41.6%；當ES的數量為300時，K-Means、Top-K、MIP、CSSA和CSWOA的平均時延分別是0.0765、0.0094、0.0062、0.0035、0.0054，CSWOA相比于前3種算法分別約降低了92.9%、42.6%、12.9%，與CSSA的平均時延接近，當ES的數量為500時，K-Means、Top-K、MIP、CSSA和CSWOA的平均時延分別是0.024 17、0.0052、0.0060、0.0021、0.0020，CSWOA相比于其它3種算法分別降低了約91.7%、61.5%、66.7%，與CSSA的平均時延接近。平均時延隨ES數量的變化如圖2所示。

圖2 平均時延隨ES數量的變化

由圖2分析可知，隨著ES數量的增加，不同算法的平均時延均有所降低，主要原因為當基站數量不變，隨著ES數量的增加，分配給每個ES的基站數量變少，基站與ES之間的距離也變得更近，所以平均時延均會降低。而CSWOA在平均時延方面優于對比算法的原因為：本文使用縱橫交叉策略對基本WOA算法進行改進，幫助提高了算法跳出局部最優的能力，使得算法在迭代前期能夠充分搜索解空間，確定最優解所在的大致位置；在迭代后期進行充分挖掘，改善解的精度。并且通過改進的收斂因子，能夠在迭代優化目標函數的過程中，算法在迭代前期以較大步長移動，能夠充分勘探搜索空間；在迭代后期以較小步長移動，能夠對目標區域進行精細勘探。因此CSWOA算法始終保持最小的平均時延，極大地提升了用戶體驗質量。

基站數量不變，增加ES的數量，觀察平均部署成本的變化，當ES的數量為100時，K-Means、Top-K、MIP、CSSA和CSWOA的平均部署成本分別是0.3848、0.1898、0.3359、0.039 12、0.019 17，CSWOA相比于其它4種算法平均部署成本分別降低了約95%、89.9%、94.3%、50.9%；當ES的數量為300時，K-Means、Top-K、MIP、CSSA和CSWOA的平均部署成本分別是0.3615、0.3501、0.4228、0.0575、0.0479，CSWOA相比于其它4種算法平均部署成本分別降低了約86.7%、86.3%、88.7%、16.7%；當ES的數量為500時，K-Means、Top-K、MIP、CSSA和CSWOA的平均部署成本分別是0.4369、0.4605、0.4242、0.0921、0.0710，CSWOA相比于其它4種算法平均部署成本分別降低了約83.7%、84.5%、83.3%、22.9%。平均部署成本隨ES數量的變化如圖3所示。

圖3 平均部署成本隨ES數量的變化

由圖3分析可知，隨著ES數量的增加，不同算法的部署成本均有所升高，主要原因為基站數量不變，隨著ES數量增加，需要購買更多的ES，而且需要更多的放置位置，使得放置的成本和安裝費用增加，所以部署成本隨著ES數量的增加而增加。但CSWOA與對比算法相比部署成本最低，這是因為通過對基本WOA算法的改進能夠使目標函數很容易跳出局部最優的情況找到全局最優解，即在基站數量不變和不犧牲用戶體驗質量(Qos)(時延)的情況下，盡可能地把ES放置在負載較小的基站位置上，從而減少租用場地的花費和鋪設線路的花費。從圖中可以看出，Top-K算法隨著ES數量增加，成本增加最快，這是因為該算法是在負載最大的基站上放置ES，使得放置成本急劇增加，當ES=500時，該算法放置成本最高。

不同算法的系統成本隨ES數量的變化如圖4所示，可以看出CSWOA的系統成本最小，其次為CSSA、MIP、Top-K和K-Means。

圖4 系統成本隨ES數量的變化

由圖4分析可知：CSWOA算法的系統成本是最低的，因為本文所優化的目標函數是平均時延和平均部署成本的線性加權和，即系統成本。而從圖2、圖3中可以看到CSWOA的平均時延和平均部署成本均優于對比算法，所以CSWOA的系統成本也均優于對比算法。而且與K-Means、Top-K、MIP和CSAA相比，CSWOA的系統成本在ES=400時分別降低了91.8%、87.6%、86.9%和30.9%；對于Top-K，由于放置在較大負載的基站上，導致部署成本增加，從而使系統成本增幅較大；MIP的平均時延較小，但平均部署成本較大，故系統成本也較大；CSSA的平均時延和平均部署成本都較小，故系統成本也比其它3種傳統算法較小。

從圖5中可以看出CSWOA算法在迭代第4次時陷入了局部最優，但由于CSWOA算法采用了縱橫交叉策略使得該算法很快跳出了局部最優；并且通過改進的非線性收斂因子提高了算法的收斂速度，使得該算法在迭代第10次左右找到了全局最優解且完全收斂。雖然兩種算法都在第10次迭代左右完全收斂，且都找到了全局最優解，但是本文算法適應度值小于CSSA算法的適應度值，且系統成本從0.032 52下降到了0.018 829，減少了42.1%；而CSSA算法的系統成本從0.031 261下降到了0.022 075，減少了29.4%；故本文算法相較于CSSA算法減少了約12.7%。ES=200時的適應度曲線如圖5所示。

圖5 當ES的數量為200時的適應度值曲線

5 結束語

針對MEC環境下WMAN中ES的部署問題，本文建立了時延和部署成本優化模型，并提出了一種縱橫交叉策略的鯨魚優化算法的ES部署方法，首先，采用精英反向學習策略構造新種群，提高種群的多樣性和全局收斂速度；然后，采用改進的非線性收斂因子平衡算法的整體開發能力和局部探索能力；最后，利用縱橫交叉策略提高算法跳出局部最優的能力。實驗結果表明，CSWOA在優化平均時延和平均部署成本方面優于其它算法，驗證了該算法的高效性。由于在現實場景中移動用戶對位置和計算需求往往是動態變化的，不同的移動用戶的業務是多樣的，因此，我們下一步研究工作的重點是考慮用戶移動性問題。