基于時延與能量感知的邊緣服務器放置方法

趙興兵，趙一帆，李 波，陳 春，丁洪偉

（1.云南大學 信息學院，昆明 650500；2.云南民族大學 電氣信息工程學院，昆明 650504；3.云南民族大學 應用技術學院，昆明 650504）

0 概述

隨著物聯網、人工智能、大數據、云計算等新一代信息技術的快速發展，各種基于移動互聯網的新型業務不斷出現，移動終端的數據流量呈現爆炸式增長［1］。由于移動終端具有有限的計算和存儲能力，因此可將部分負載遷移到云端進行處理［2-3］。但由于云計算部署模式［4］的限制，基于遠程數據中心的云計算模式需要通過廣域網傳輸數據和應用，因此產生的網絡時延和抖動會對實時交互性應用和用戶體驗產生不利影響。邊緣計算在靠近用戶端的網絡邊緣部署本地云資源，在很大程度上可緩解網絡帶寬、時延和抖動對移動應用的影響，有效改善傳統通信網絡結構。移動邊緣計算［5］支持用戶在無線接入網（Radio Access Network，RAN）范圍內訪問信息和云計算服務，大幅降低了傳送時延，提高了用戶體驗［1］。邊緣服務器（Edge Server，ES）是移動邊緣計算的重要組成部分［6］。在城市中，移動用戶分布密集，來自用戶的任務量大。對于運營商而言，相比于其他地區，在城市中放置ES 將有更高的收益。因此，研究無線城域網（Wireless Metropolitan Area Network，WMAN）中的ES 放置問題（簡稱為WESP問題）具有重要意義。

目前，有關ES 放置問題的研究較少，但在相關研究領域微云放置已取得了一定的研究成果，可為ES 放置提供一定的參考。文獻［7］以最小化系統時延為目標，對微云放置進行研究，提出負載最重優先和用戶密度優先的放置策略。文獻［8］研究WMAN中有限容量的微云放置問題，在問題規模較小時提出基于整數線性規劃的放置方法。文獻［9-11］討論了微云放置的成本問題，其中：文獻［9］通過拉格朗日啟發式算法對微云進行放置；文獻［10］將時延映射為成本，提出二進制差分進化布谷鳥搜索算法，解決基于軟件控制網絡的微云放置問題；文獻［11］采用改進的貪婪算法解決ES 放置問題。文獻［12］以覆蓋更多的用戶為目標，對微云放置問題進行討論。文獻［13］以優化時間開銷和能量開銷為目標，討論了5G 環境中的ES 放置問題，并提出基于等效帶寬的放置方法。文獻［14］以優化用戶接入時延和均衡ES 負載為目標，討論移動邊緣計算環境中的ES 放置問題，并提出基于混合整數規劃（Mixed Integar Planing，MIP）的放置方法。此外，學者們還對移動邊緣計算中的應用部署問題進行了大量研究［15-17］。

本文對WMAN 中ES 放置的時延和能耗問題進行研究，建立WESP 問題的時延和能耗模型，提出基于混沌麻雀搜索算法（Chaos Sparrow Search Algorithm，CSSA）的ES 放置方法，針對WESP 問題設計新的個體編碼方式，使用精英反向學習（Elite Opposition-Based Learning，EOBL）策略產生初始種群加快算法搜索速度，采用邏輯混沌映射策略對麻雀個體進行改進，增強算法收斂性。

1 問題描述

假設E=｛E1，E2，…，E|E|｝為一組ES 集合，|E|為邊緣服務器的總數；B=｛B1，B2，…，B|B|｝為一組基站集合，|B|為基站的總數；對于?i，表示基站Bi為一組移動用戶提供轉發服務，|U|為由基站Bi提供轉發服務的用戶總數。

WESP 問題描述：給定一組ES 的集合、BS 的集合以及每個基站負責的用戶集合，在給定的基站集合中尋找一種ES 放置方案，并為ES 分配基站，使得ES 放置的平均時延D［E］和平均能耗EC［E］最小。目標函數的數學模型表示如下：

其中：X為ES 放置方案，即問題的一組可行解。

單個邊緣服務器Ev的負載W[Ev]表示如下：

其中：W[?]表示將單個用戶的負載累加到ES。

邊緣服務器的平均時延是所有ES 傳輸時延的平均值，表示如下：

單個ES 的傳輸時延包含本地傳送時延和遠程傳送時延。本地傳送時延是移動用戶請求到達ES的傳輸時間，表示如下：

其中：T[?]為單個用戶請求到達ES 的傳輸時延，由基站與ES 之間的距離除以光速得到，并且本文不考慮用戶請求接入基站之前的無線傳輸時延。

假設所有ES 同構，單個ES 負載的閾值為WTH。當ES 的負載達到閾值后，ES 不再處理用戶請求，隨后到達的用戶請求將被遷移到遠程云處理，產生的遠程傳送時延如下：

其中：Tmax為ES 將負載遷移到遠程云產生的固定時延。

由式（4）和式（5）可知，單個ES 的時延表示如下：

在ES 中，CPU、內存和硬盤等都是造成能耗的器件，但主要的能耗器件為CPU［18］，并且ES 的能耗可由功率和CPU 使用率的線性關系得出［19-20］。單個ES 的能耗表示如下：

其中：Pidle為服務器的空閑功率；Pmax為服務器完全工作時的功率；UPv為服務器的使用率。UPv的計算公式如下：

由式（7）～式（9）可得，所有ES 的平均能耗表示如下：

由以上分析可知，WESP 問題是一個多目標優化問題，優化的目標是最小化ES 的平均時延和平均能耗，傳統的優化算法難以解決多目標優化問題。本文采用加權方法將平均時延和平均能耗轉化為系統開銷，其中權值為0.5，因為在優化過程中平均時延和平均能耗同樣重要。

由于時延和能耗的量綱不同，為了消除量綱不同對加權效果的影響，因此先采用式（11）對單個ES的時延和能耗進行歸一化，再使用式（3）和式（10）重新計算平均時延和平均能耗。

定義1系統開銷被定義為歸一化后的平均時延和平均能耗的加權和，表示系統實現所需的時間代價和能耗代價，能夠反映系統性能的優劣，值越小，系統性能越好，計算公式如下：

2 基于混沌麻雀搜索的放置方法

麻雀搜索算法（Sparrow Search Algorithm，SSA）［21］是一種新型群體智能優化算法，通過模擬麻雀的捕食和反捕食行為進行迭代尋優，具有調整參數少、收斂速度快、設計簡單等優點。麻雀種群可分為發現者、加入者和警戒者。發現者和加入者構成了發現者-跟隨者模型，警戒者為模型加入警戒者機制。在麻雀種群中：容易發現食物的個體（在本文中為適應度函數值較小的個體）被指定為發現者，負責為所有加入者提供覓食區域和方向；剩下的個體為加入者，負責平衡種群數量，迭代過程中發現者和跟隨者的比重是不變的；警戒者由種群中隨機選取的個體組成，占種群數量的10%～20%，負責為種群警戒，當危險發生時提醒其他成員轉移位置。

麻雀搜索算法優點眾多，但不適用于解決WESP 問題，并且存在接近全局最優時搜索能力不足和容易陷入局部最優的問題。為了克服這些問題并解決WESP 問題，本文提出基于混沌麻雀搜索算法的放置方法。

2.1 個體編碼

由以上分析可知，WESP 問題是一個離散優化問題，傳統的二進制編碼和實數編碼難以有效描述WESP 問題，并且難以與迭代過程相結合。文獻［22］提出一種放置問題編碼方式，受此啟發，本文提出一種個體編碼方式，如表1 所示，其中√表示ES的標記。

表1 個體編碼Table 1 Individual coding

在表1 中，個體編碼為k×2m的矩陣，每一行表示一個邊緣服務器，每一列表示一個基站。前m列為放置矩陣Y，后m列為分配矩陣Z。在放置矩陣中，每一行的標記位置表示第i個ES 的放置位置。在分配矩陣中，每一列的標記位置表示將此列代表的基站分配給該行代表的ES。以表1 為例：第1 行表示將第1 個ES 放置在第1 個基站上，并且為其分配第1 個和第（m-1）個基站；第k行表示將第k個ES放置在第2 個基站上，并且為其分配第2 個基站。因為WESP 問題存在約束條件，所以編碼還需滿足以下規則：

1）Y中任意兩行對應的標記不在同一列，并且每一行有且只有一個標記，對應

2）Z中每一列中有且只有一個標記，對應

3）在Z和Y中，相同列中的標記必須位于同一行，放置ES 的基站被分配給該ES。

2.2 適應度函數

適應度函數用來控制種群迭代更新，適應度函數值反映個體能量的高低。本文將適應度函數定義為式（14），表示平均時延和平均能耗的加權和。適應度函數值越小，放置性能越好，個體能量越高且越優秀。

2.3 發現者位置更新

在搜索過程中，具有良好適應度的發現者會優先獲取食物，并且發現者負責為種群尋找食物提供覓食方向，因此發現者相比加入者有更大的搜索范圍，按式（15）的規則更新位置：

其中：α∈(0,1]為隨機數；R2∈[0,1]為安全值；SST∈[0,1]為警戒值；Q為服從正態分布的隨機數；L為1×2m的矩陣，其元素全部為1；itermax為最大迭代次數；Round(?)為取整操作。當R2

2.4 加入者位置更新

在覓食過程中，一些加入者會時刻監視發現者，并與發現者搶奪食物（表現為式（15）），如果搶奪食物成功，則成為發現者，否則成為加入者，按式（16）的規則更新位置：

其中：XP為目前發現者占據的最佳位置；Xworst為當前種群的最差位置；A+=AT(AAT)-1，A是形狀為1×2m、元素為1 或-1 的矩陣。當時，個體i沒有獲得食物，處于十分饑餓的狀態，此時個體i將飛往其他地方覓食；否則，個體i將向食物更加豐富的區域移動。

2.5 警戒者位置更新

警戒者的位置是在種群中隨機產生的，按照式（17）的規則更新位置：

2.6 邏輯混沌映射

傳統SSA 與其他群體智能優化算法一樣，在迭代后期，算法搜索能力下降，導致種群多樣性降低，容易陷入局部最優。為了克服該問題，采用邏輯混沌映射［23］的方式在每次迭代結束后對種群的位置進行更新，以保持種群的多樣性，保證算法的收斂性，如式（18）所示：

其中：μ∈(0,4]。

2.7 精英反向學習策略

反向學習（Opposition-Based Learning，OBL）策略通過構造初始種群加快算法搜索速度。精英反向學習策略［24］是反向學習策略的改進，利用優勢個體反向構造初始種群，以保證種群的多樣性，加快算法的搜索速度。

設Xi=(Xij1,Xij2,…,Xij(2m)),j=1,2,…,k為一個 普通個體，其對應的極值為精英個體其對應的精英反向解定義如下：

其中：maxdj、mindj分別為Xi的第j維的最大值和最小值。

2.8 CSSA 算法描述

將求解WESP 問題的CSSA 算法步驟描述如下：

步驟1初始化種群，定義相關參數，轉到步驟2。

步驟2計算所有個體的適應度值，找出精英個體，并根據式（19）構造新的種群，轉到步驟3。

步驟3計算所有個體的適應度函數值并進行排序；保存適應度值和個體位置；找出最佳適應度函數值fg并保存其位置Xbest，轉到步驟4。

步驟4根據式（15）更新發現者的位置和適應度函數值；找出目前發現者占據的最優位置XP、當前全局最差個體的Xworst和fw，轉到步驟5。

步驟5根據式（16）更新加入者的位置和適應度函數值，轉到步驟6。

步驟6根據式（17）隨機更新警戒者的位置和適應度函數值，轉到步驟7。

步驟7得到更新后的位置和適應度函數值，轉到步驟8。

步驟8將更新后的適應度函數值與步驟2 中保存的適應度函數值進行比較，若小于步驟2 中保存的適應度函數值，則更新適應度函數值和位置，否則不更新；更新fg和Xbest，轉到步驟9。

步驟9根據式（18）產生新的個體，并與原個體比較，若新個體更優，則更新原個體的位置和適應度函數值，否則不更新，轉到步驟10。

步驟10比較迭代次數是否滿足itermax，若滿足，則轉到步驟11，否則轉到步驟4。

步驟11輸出最佳適應度值和個體位置。

3 仿真與結果分析

使用上海市電信局的真實網絡數據集對算法進行仿真實驗。經過處理后的數據集包含2 753 個基站信息，包括編號、用戶數量、緯度、經度和連續15 天的接入時長（記為負載）。經過處理后，部分基站信息如表2 所示。

表2 部分基站信息Table 2 Information of some base stations

實驗軟硬件環境為Intel?CoreTMi7-9750H CPU 2.60 GHz 處理器、Windows 10 操作系統、Python 3.7版本。核心參數設置如下：最大迭代次數itermax∈[60～100]，種群數 量N∈[60～80]，Pidle=0.3w，Pmax=0.5w，WTH為3×108min，ES 將負載遷移到遠程云產生的固定時延Tmax為0.5 s，最大接入時延Ad為0.7 s。選取MIP［14］、K-Means［14］、Random［22］、Top-K［22］等4 個主流放置算法作為對比算法。算法的性能測試指標為平均時延和平均能耗。

保持基站數量為2 753，不斷增加ES 數量，測試平均時延的變化，如圖1 所示。由圖1 可以看出：當ES 為100 時，Random、K-Means、Top-K、CSSA、MIP的平均時延分別為0.028 s、0.21 s、0.036 s、0.022 s、0.028 s，CSSA 相比其他4 種算法分別約降低了21.4%、86.6%、38.8% 和21.4%；當ES 為200 時，Random、K-Means、Top-K、CSSA、MIP 的平均時延分別為0.017 s、0.14 s、0.021 s、0.015 s、0.018 s，CSSA 相比其他4 種算法分別約降低了11.7%、92.1%、28.5%和16.6%；當ES 為300 時，K-Means 的平均 時延為0.085 s，其他算法的平均時延接近相等，約為0.005 8 s；當ES 為400 時，Random、K-Means、Top-K、CSSA、MIP 的平均 時延分別為0.008 7 s、0.23 s、0.032 s、0.003 2 s、0.006 1 s，CSSA 相比其他4 種算法分別約降低了51.7%、91.3%、28.5%和47.5%。

圖1 平均時延隨ES 數量的變化Fig.1 Variation of average time delay with the number of ES

由圖1 分析可知，隨著ES 數量的增加，不同算法的平均時延均呈現下降的趨勢，主要原因為當基站總數不變時，隨著ES 數量的增加，基站趨向于被分配給更近的ES，所以平均時延下降。CSSA 平均時延最小，其次為MIP、Top-K、Random 和K-Means。除CSSA 之外，其他算法均在ES 數量為300 時表現最好，當ES 數量為400 時，性能反而有所下降，分析其原因為陷入了局部最優，而CSSA 未陷入局部最優，性能繼續優化。因為CSSA 使用精英反向學習策略初始化種群，加快了算法的搜索速度，利用邏輯混沌映射對個體進行改進，保證了算法的收斂速度。

保持基站數量為2 753，不斷增加ES 數量，測試平均能耗的變化，如圖2 所示。由圖2 可以看出：當ES 數量為100 時，Random、K-Means、Top-K、CSSA、MIP 的平均 能耗分別為0.264 kWh、0.193 kWh、0.032 kWh、0.02 kWh、0.291 kWh，CSSA 相比其 他4 種算法約分別降低了96.1%、94.7%、41.3%和96.5%；當ES 數量為200 時，Random、K-Means、MIP 的平均能耗分別為0.21 kWh、0.266 kWh、0.285 kWh，CSSA 和Top-K 的平均能耗約 為0.012 kWh，CSSA 相比其 他3 種算法約分別降低了93.8%、91.3%和91.2%；當ES數量為300 時，Random、K-Means、Top-K、CSSA、MIP的平均能耗分別為0.264 kWh、0.193 kWh、0.011 kWh、0.01 kWh、0.271 kWh，CSSA 相比其他4 種算法約分別降低了96.2%、94.3%、9% 和95.3%；當ES 數量為400 時，Random、K-Means、MIP 的平均能耗分別為0.173 kWh、0.232 kWh、0.269 kWh，Top-K 和CSSA為0.007 kWh，CSSA 相比Random、K-Means 和MIP平均能耗約分別降低了95.5%、93.3%、18.1% 和97.3%。

圖2 平均能耗隨ES 數量的變化Fig.2 Variation of average energy consumption with the number of ES

由圖2 分析可知，隨著ES 數量的增加，不同算法的平均能耗都有下降的趨勢。CSSA 的平均能耗最少，之后是Top-K，其他算法的平均能耗均很高，分析其原因是CSSA 和Top-K 放置時考慮了負載因素，而其他算法放置的依據是距離，忽略了對能耗影響較大的負載因素，所以平均能耗表現很差。

不同算法的系統開銷隨ES 數量的變化如圖3 所示，可以看出CSSA 的系統開銷最優，其次是Top-K、Random、MIP 和K-Means。

圖3 系統開銷隨ES 數量的變化Fig.3 Variation of system overhead with the number of ES

由圖3 分析可知：CSSA 在迭代尋優時，以系統開銷為適應度函數指導種群個體進化，同時兼顧平均時延和平均能耗，所以系統開銷是最優的；對于Top-K，因為在真實的WMAN 中，用戶總是集中在特定的區域（商場、學校等），所以將ES 放置在這些位置將有更小的用戶接入時延，同時這些位置的基站負載較大，意味著放置在此地的ES 使用率較高，ES使用率越高，處于空閑狀態的時間越少，系統能耗越小，系統開銷越小；Random 和MIP 的平均時延較小，但平均能耗較大，系統開銷也較大；K-Means 中的ES由于必須被放置在基站上，因此選取與聚類質心最近的基站作為ES 的放置位置，導致平均時延較大，此外，由于K-Means 是非均勻的聚類算法，因此ES負載差異很大，導致平均能耗較大，K-Means 系統開銷也較大［18］。

圖4 給出了放置100 個ES 時CSSA 的適應度曲線，可以看出CSSA 的適應度函數值呈現單調遞減的趨勢，在前10 次迭代內適應度函數值下降較快，迭代12 次后適應度函數值完全收斂，算法找到全局最優解。在該情況下，CSSA 系統開銷最初為0.033，經過迭代后最終下降到0.027，減少了18.1%。

圖4 當ES 數量為100 時CSSA 的適應度曲線Fig.4 Fitness curve of CSSA when the number of ES is 100

4 結束語

本文提出一種基于混沌麻雀搜索算法的WMAN邊緣服務器放置方法。通過設計新的編碼方式有效描述WESP 問題，并解決離散優化問題。采用精英反向學習策略初始化種群，提高算法搜索速度。利用邏輯混沌映射改進麻雀個體，保證迭代后期的種群多樣性，避免陷入局部最優解。實驗結果表明，CSSA 在優化平均時延和平均能耗方面表現突出。但由于在實際WMAN中用戶請求可能通過多次轉發到達邊緣服務器，因此后續將分析并建立包含多跳的時延模型。此外，在新一代信息技術的支持下，邊緣服務器的作用和功能趨于多元化，異構的邊緣服務器放置問題也是下一步研究的重點方向。