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

（1.云南大學(xué) 信息學(xué)院，昆明 650500；2.云南民族大學(xué) 電氣信息工程學(xué)院，昆明 650504；3.云南民族大學(xué) 應(yīng)用技術(shù)學(xué)院，昆明 650504）

0 概述

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

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

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

1 問題描述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

定義1系統(tǒng)開銷被定義為歸一化后的平均時延和平均能耗的加權(quán)和，表示系統(tǒng)實現(xiàn)所需的時間代價和能耗代價，能夠反映系統(tǒng)性能的優(yōu)劣，值越小，系統(tǒng)性能越好，計算公式如下：

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

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

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

2.1 個體編碼

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

表1 個體編碼Table 1 Individual coding

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

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

2）Z中每一列中有且只有一個標記，對應(yīng)

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

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

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

2.3 發(fā)現(xiàn)者位置更新

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

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

2.4 加入者位置更新

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

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

2.5 警戒者位置更新

警戒者的位置是在種群中隨機產(chǎn)生的，按照式（17）的規(guī)則更新位置：

2.6 邏輯混沌映射

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

其中：μ∈(0,4]。

2.7 精英反向?qū)W習(xí)策略

反向?qū)W習(xí)（Opposition-Based Learning，OBL）策略通過構(gòu)造初始種群加快算法搜索速度。精英反向?qū)W習(xí)策略［24］是反向?qū)W習(xí)策略的改進，利用優(yōu)勢個體反向構(gòu)造初始種群，以保證種群的多樣性，加快算法的搜索速度。

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

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

2.8 CSSA 算法描述

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

步驟1初始化種群，定義相關(guān)參數(shù)，轉(zhuǎn)到步驟2。

步驟2計算所有個體的適應(yīng)度值，找出精英個體，并根據(jù)式（19）構(gòu)造新的種群，轉(zhuǎn)到步驟3。

步驟3計算所有個體的適應(yīng)度函數(shù)值并進行排序；保存適應(yīng)度值和個體位置；找出最佳適應(yīng)度函數(shù)值fg并保存其位置Xbest，轉(zhuǎn)到步驟4。

步驟4根據(jù)式（15）更新發(fā)現(xiàn)者的位置和適應(yīng)度函數(shù)值；找出目前發(fā)現(xiàn)者占據(jù)的最優(yōu)位置XP、當前全局最差個體的Xworst和fw，轉(zhuǎn)到步驟5。

步驟5根據(jù)式（16）更新加入者的位置和適應(yīng)度函數(shù)值，轉(zhuǎn)到步驟6。

步驟6根據(jù)式（17）隨機更新警戒者的位置和適應(yīng)度函數(shù)值，轉(zhuǎn)到步驟7。

步驟7得到更新后的位置和適應(yīng)度函數(shù)值，轉(zhuǎn)到步驟8。

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

步驟9根據(jù)式（18）產(chǎn)生新的個體，并與原個體比較，若新個體更優(yōu)，則更新原個體的位置和適應(yīng)度函數(shù)值，否則不更新，轉(zhuǎn)到步驟10。

步驟10比較迭代次數(shù)是否滿足itermax，若滿足，則轉(zhuǎn)到步驟11，否則轉(zhuǎn)到步驟4。

步驟11輸出最佳適應(yīng)度值和個體位置。

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

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

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

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

保持基站數(shù)量為2 753，不斷增加ES 數(shù)量，測試平均時延的變化，如圖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 數(shù)量的變化Fig.1 Variation of average time delay with the number of ES

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

保持基站數(shù)量為2 753，不斷增加ES 數(shù)量，測試平均能耗的變化，如圖2 所示。由圖2 可以看出：當ES 數(shù)量為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 數(shù)量為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數(shù)量為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 數(shù)量為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 數(shù)量的變化Fig.2 Variation of average energy consumption with the number of ES

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

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

圖3 系統(tǒng)開銷隨ES 數(shù)量的變化Fig.3 Variation of system overhead with the number of ES

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

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

圖4 當ES 數(shù)量為100 時CSSA 的適應(yīng)度曲線Fig.4 Fitness curve of CSSA when the number of ES is 100

4 結(jié)束語

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