基于時(shí)延與能量感知的邊緣服務(wù)器放置方法

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

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

0 概述

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

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

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

1 問(wèn)題描述

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

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

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

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

其中：W[?]表示將單個(gè)用戶的負(fù)載累加到ES。

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

單個(gè)ES 的傳輸時(shí)延包含本地傳送時(shí)延和遠(yuǎn)程傳送時(shí)延。本地傳送時(shí)延是移動(dòng)用戶請(qǐng)求到達(dá)ES的傳輸時(shí)間，表示如下：

其中：T[?]為單個(gè)用戶請(qǐng)求到達(dá)ES 的傳輸時(shí)延，由基站與ES 之間的距離除以光速得到，并且本文不考慮用戶請(qǐng)求接入基站之前的無(wú)線傳輸時(shí)延。

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

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

由式（4）和式（5）可知，單個(gè)ES 的時(shí)延表示如下：

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

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

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

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

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

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

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

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

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

2.1 個(gè)體編碼

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

表1 個(gè)體編碼Table 1 Individual coding

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

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

2）Z中每一列中有且只有一個(gè)標(biāo)記，對(duì)應(yīng)

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

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

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

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

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

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

2.4 加入者位置更新

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

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

2.5 警戒者位置更新

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

2.6 邏輯混沌映射

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

其中：μ∈(0,4]。

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

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

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

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

2.8 CSSA 算法描述

將求解WESP 問(wèn)題的CSSA 算法步驟描述如下：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

實(shí)驗(yàn)軟硬件環(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 將負(fù)載遷移到遠(yuǎn)程云產(chǎn)生的固定時(shí)延Tmax為0.5 s，最大接入時(shí)延Ad為0.7 s。選取MIP［14］、K-Means［14］、Random［22］、Top-K［22］等4 個(gè)主流放置算法作為對(duì)比算法。算法的性能測(cè)試指標(biāo)為平均時(shí)延和平均能耗。

保持基站數(shù)量為2 753，不斷增加ES 數(shù)量，測(cè)試平均時(shí)延的變化，如圖1 所示。由圖1 可以看出：當(dāng)ES 為100 時(shí)，Random、K-Means、Top-K、CSSA、MIP的平均時(shí)延分別為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%；當(dāng)ES 為200 時(shí)，Random、K-Means、Top-K、CSSA、MIP 的平均時(shí)延分別為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%；當(dāng)ES 為300 時(shí)，K-Means 的平均 時(shí)延為0.085 s，其他算法的平均時(shí)延接近相等，約為0.005 8 s；當(dāng)ES 為400 時(shí)，Random、K-Means、Top-K、CSSA、MIP 的平均 時(shí)延分別為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 平均時(shí)延隨ES 數(shù)量的變化Fig.1 Variation of average time delay with the number of ES

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

保持基站數(shù)量為2 753，不斷增加ES 數(shù)量，測(cè)試平均能耗的變化，如圖2 所示。由圖2 可以看出：當(dāng)ES 數(shù)量為100 時(shí)，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%；當(dāng)ES 數(shù)量為200 時(shí)，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%；當(dāng)ES數(shù)量為300 時(shí)，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%；當(dāng)ES 數(shù)量為400 時(shí)，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ù)量的增加，不同算法的平均能耗都有下降的趨勢(shì)。CSSA 的平均能耗最少，之后是Top-K，其他算法的平均能耗均很高，分析其原因是CSSA 和Top-K 放置時(shí)考慮了負(fù)載因素，而其他算法放置的依據(jù)是距離，忽略了對(duì)能耗影響較大的負(fù)載因素，所以平均能耗表現(xiàn)很差。

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

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

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

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

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

4 結(jié)束語(yǔ)

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