基于用戶密度和平均訪問時間的邊緣服務(wù)器放置方法

胡春節(jié) 劉靜 鄭文祥

摘 要：為解決邊緣服務(wù)器放置過程中資源浪費和延遲增加的問題，對邊緣服務(wù)器放置方案的用戶密度和平均訪問時間進行分析建模，將其描述為多目標優(yōu)化問題。設(shè)計了一種基于用戶密度和平均訪問時間的邊緣服務(wù)器放置方案，并提出了一種多目標海馬遺傳算法（MOSGA）解決該問題。MOSGA首先使用多目標優(yōu)化算法的思想對海馬優(yōu)化（sea horse optimizer，SHO）算法進行改進，使SHO算法能夠適用于多目標優(yōu)化問題，并在此基礎(chǔ)上使用遺傳算法改進SHO算法的繁殖操作，使MOSGA能更好地跳出局部最優(yōu)解，加速問題的求解。該算法在上海電信數(shù)據(jù)集上進行了實驗驗證，仿真實驗結(jié)果表明，MOSGA明顯優(yōu)于RA、K-means、NSGA、LMM，不僅有效解決了服務(wù)器資源浪費的問題，同時大大降低終端設(shè)備訪問服務(wù)器的時間。

關(guān)鍵詞：邊緣計算；邊緣服務(wù)器放置；多目標優(yōu)化；海馬優(yōu)化；遺傳算法

中圖分類號：TP393?? 文獻標志碼：A??? 文章編號：1001-3695（2024）05-024-1448-08

doi： 10.19734/j.issn.1001-3695.2023.09.0413

Edge server placement method based on user density and average access time

Abstract：To address the issue of resource wastage and increasing latencies in the placement process of edge servers， this paper analyzed and modeled the user density and average access time of edge server placement schemes as multi-objective optimization problems. It designed an edge server placement scheme based on user density and average access time， and proposed a multi-objective sea-horse genetic algorithm （MOSGA） to solve this problem. The MOSGA algorithm firstly used the idea of multi-objective optimization algorithm to improve the SHO algorithm， so that the SHO algorithm could be applied to multi-objective optimization problems. It used the genetic algorithm to improve the propagation operation of the SHO algorithm， so that the MOSGA could better jump out of the local optimal solution and accelerate the solution of the problem. The proposed algorithm was verified on the data set of Shanghai Telecom， and the simulation experiment results show that MOSGA is obviously better than RA， K-means， NSGA and LMM， which not only effectively solves the problem of server resource waste， but also greatly reduces the time of terminal equipment to access the server.

Key words：mobile edge computing; edge server placement; multi-objective optimization; sea horse optimizer; genetic algorithm

0 引言

隨著5G網(wǎng)絡(luò)的推廣和普及，移動邊緣計算（mobile edge computing，MEC）作為一種新興的計算模式，引起人們的廣泛關(guān)注。MEC的主要特點是縮短終端用戶設(shè)備和計算、存儲資源之間的距離，提供低延遲和高帶寬的服務(wù)，從而提升用戶體驗。邊緣服務(wù)器（edge server，ES）的放置位置是影響MEC性能的一個關(guān)鍵因素。

然而，設(shè)計一個好的邊緣服務(wù)器放置（edge server placement，ESP）方案是一個艱巨的任務(wù)，存在以下困難：a）需要充分利用ES的計算和存儲資源，避免某些ES過于閑置而出現(xiàn)資源浪費；b）MEC的目標是降低網(wǎng)絡(luò)延遲和提高系統(tǒng)的響應(yīng)速度，因此在選擇ESP的位置時，必須盡量減少數(shù)據(jù)傳輸時間和平均訪問時間；c）ESP放置問題是一個NP難問題（non-deterministic polynomial-time hard，NP-hard），例如從100個基站中選擇20個放置位置，其可能的方案約為5.36×1020種，這就意味著對這個問題求解的搜索空間將是巨大的，難以在短時間內(nèi)找到最優(yōu)解，需要設(shè)計一種高效的算法進行求解。

近年來，MEC備受關(guān)注［1～5］，而ESP問題則是該領(lǐng)域亟待解決的問題。在求解ESP問題時，現(xiàn)有各項研究工作的關(guān)注點也不同。一些研究關(guān)注于降低延遲或者平衡邊緣服務(wù)器負載，例如文獻［6］基于免疫優(yōu)化算法設(shè)計了一種有效的ESP方法，旨在減少訪問延遲并優(yōu)化負載；文獻［7］針對車聯(lián)網(wǎng)出現(xiàn)額外的延遲和網(wǎng)絡(luò)擁塞現(xiàn)象，提出了一種動態(tài)邊ESP方法，以適應(yīng)車聯(lián)網(wǎng)交通動態(tài)變化；文獻［8］研究了智能城市移動邊緣計算環(huán)境中的ESP問題，以優(yōu)化移動邊緣計算網(wǎng)絡(luò)性能，提高響應(yīng)速度；文獻［9］將ESP問題建模為一個容量聚類問題進行求解，最大限度地減少回程延遲。文獻［10］設(shè)計了一種負載感知的ESP方法，以保證邊緣服務(wù)的執(zhí)行效率，降低訪問延遲；文獻［11］考慮到ES出現(xiàn)故障的不確定性，研究了用于邊緣計算的魯棒性服務(wù)器布局問題，旨在最大化預期總體工作負載。以上方法在一定程度上解決了ESP問題，但忽視了ES一旦放置將難以移動的特點，這直接影響到邊緣服務(wù)器計算和存儲資源的利用率。

另一些研究的關(guān)注點在降低ES的能耗或成本方面。例如，文獻［12］設(shè)計一種雙因子近似算法，用于解決異構(gòu)ESP問題，從而保證有界的延遲和放置成本；文獻［13］提出了一種跨區(qū)域資源優(yōu)化模型，旨在最小化服務(wù)提供商的成本，并得到最終ESP策略；文獻［14］研究了MEC中最小化微云的放置成本和端到端延遲成本問題，并提出了基于成本意識的微云放置算法；文獻［15］研究了具有能量感知的ESP問題，并設(shè)計了一種基于粒子群優(yōu)化的能量感知ESP算法來尋找最優(yōu)解，目標是最小化ES的放置成本。但是文獻［12］的雙因子近似算法存在求解精度不高的問題，而文獻［13～15］未考慮終端用戶對延遲要求。此外，上述研究將ESP問題建模為單目標或加權(quán)單目標優(yōu)化問題，優(yōu)化單個目標通常難以適應(yīng)多樣化的應(yīng)用場景和用戶需求。而將多個目標加權(quán)成單目標優(yōu)化的方法雖然可以將多個優(yōu)化指標轉(zhuǎn)換為一個綜合指標，但會存在優(yōu)化目標權(quán)重難以確定、目標之間相互影響等問題。

元啟發(fā)式算法因為高效性、靈活性、可擴展性、魯棒性和可解釋性等諸多優(yōu)點［16，17］被用于求解ESP問題。例如文獻［18］提出一個基于改進的非支配排序遺傳算法（non-dominated sorting genetic algorithm，NSGA）來解決網(wǎng)絡(luò)分區(qū)和邊緣服務(wù)器放置問題，以優(yōu)化邊緣計算在分布式狀態(tài)估計中的應(yīng)用。

此外，半監(jiān)督學習的聚類算法也被用求解ESP問題。例如文獻［19］提出了一種基于改進的K均值聚類的方法（K-means clustering algorithm，K-means）來確定ES的理論位置和數(shù)量，以此優(yōu)化ES的網(wǎng)絡(luò)延遲、能耗和成本。

針對ES放置問題中存在的困難和上述研究方案中的不足，本文提出了一種基于用戶密度和平均訪問時間的邊緣服務(wù)器放置方法，并設(shè)計了一種元啟發(fā)式算法——多目標海馬遺傳算法（multi-objective seahorse genetic algorithm，MOSGA）求解ES放置方案。本文的貢獻如下：

a）建立了MEC的系統(tǒng)模型，相比其他研究工作，本文對用戶密度和平均訪問時間進行分析建模，并將ESP問題描述為多目標優(yōu)化問題。考慮用戶密度和平均訪問時間的影響，能夠更好地滿足用戶需求并解決ESP過程中的資源浪費問題。此外，將ESP問題描述為多目標優(yōu)化問題，可適應(yīng)更多元化的應(yīng)用場景和用戶需求，同時也能解決將多個優(yōu)化目標加權(quán)為一個目標優(yōu)化時，優(yōu)化目標權(quán)重難以確定、目標之間相互影響等問題。

b）提出了一種多目標海馬遺傳算法求解ES放置方案，旨在解決ESP問題求解規(guī)模大、復雜度高的問題。MOSGA結(jié)合多目標優(yōu)化算法（multi-objective optimization algorithm，MOP）［20］的思想改進SHO算法［21］，使得MOSGA可以用于解決多目標優(yōu)化問題，在此基礎(chǔ)上使用遺傳算法（genetic algorithm，GA）［22］改進SHO算法的繁殖階段，使得MOSGA能更好地跳出局部最優(yōu)，加快問題的求解。

c）仿真實驗結(jié)果表明，MOSGA與隨機算法（random algorithm，RA）、聚類算法K-means［19］ 、非支配遺傳算法NSGA［18］、拉格朗日乘數(shù)法（lagrange multiplier method，LMM）［23］相比，不僅在總的用戶密度和平均訪問時間方面表現(xiàn)最優(yōu)，有效減少了服務(wù)器的資源浪費，而且大大降低了終端設(shè)備訪問服務(wù)器的時間。

1 系統(tǒng)模型和問題定義

1.1 系統(tǒng)模型

MEC的體系結(jié)構(gòu)有云數(shù)據(jù)中心層、邊緣層和用戶設(shè)備層三個層次。本文的研究集中在邊緣層，該層由N個基站組成，本文的目標是在這些基站中選擇M個合適的位置放置ES，使得用戶設(shè)備的請求可以在離用戶更近的ES上被處理，用戶設(shè)備請求中部分數(shù)據(jù)處理和存儲任務(wù)可以轉(zhuǎn)移到ES上處理，降低延遲的同時減少對網(wǎng)絡(luò)傳輸帶寬的需求，節(jié)約資源，為用戶提供更好的體驗。

1.2 城市基站訪問記錄

在城市中的基站每時每刻都會接收來自用戶設(shè)備的請求，產(chǎn)生源源不斷的訪問記錄，假定在一段時間內(nèi)共產(chǎn)生K條訪問記錄，每條接入記錄中包含訪問開始時間tstri、訪問結(jié)束時間tendi、基站編號bidi以及用戶設(shè)備編號uidi四個屬性。

1.3 用戶密度模型

在一段時間內(nèi)基站i接入的用戶設(shè)備數(shù)量Euclid Math OneNApi計算方式為

對于任意一個基站i，其覆蓋面積Ai計算如下：

Ai=πr2i（3）

其中：ri為基站i的覆蓋半徑。那么對于任意一個基站i，其用戶密度Ui計算如下：

1.4 平均訪問時間模型

在一段時間內(nèi)，基站i被訪問的總時間Ti計算方式如下：

其中：［bidj=i］表示當?shù)趈條訪問記錄的基站編號bidj等于i時為1，否則為0；tendj表示第j條訪問記錄的結(jié)束訪問時間；tstrj表示第j條訪問記錄的開始訪問時間。

對于任意一個基站i，其被訪問的總次數(shù)Ci計算如下：

其中：［bidj=i］表示當?shù)趈條訪問記錄的基站編號bidj等于i時為1，否則為0。那么，對于任意一個基站的i平均訪問時間Tavei計算為

1.5 服務(wù)質(zhì)量模型

在MEC中，在基站上放置ES的目的是為了盡可能縮短計算和存儲資源與用戶之間的距離，降低延遲，為用戶提供更好的體驗。換句話說，ES放置位置選址應(yīng)當滿足以下兩點：

a）ES的放置位置盡可能選擇用戶密集的基站。用戶密集的基站往往承載著較多的用戶請求。這可能會占用大量的網(wǎng)絡(luò)傳輸帶寬資源，在這些基站上放置ES可以將部分請求分流到ES上進行處理，減輕基站的壓力，提高基站的處理能力和穩(wěn)定性，節(jié)約資源。同時在這些基站上放置ES也能縮短用戶設(shè)備與服務(wù)器之間的距離，降低網(wǎng)絡(luò)延遲，提高用戶體驗。

b）ES的放置位置盡可能選擇用戶設(shè)備平均訪問時間長的基站。用戶設(shè)備在訪問基站時，由于基站的負載較大和被訪問時間較長，可能會面臨較長的等待時間和較高的訪問延遲。通過在這些基站上放置ES，可以將用戶的請求分配到離用戶更近的服務(wù)器上進行處理，減少訪問延遲和等待時間，提高服務(wù)的質(zhì)量和可用性，從而提高用戶體驗。

因此，給定M個ES，從N個基站中選擇出M個位置放置ES，其總的用戶密度F1和總的被訪問時長F2分別計算如下：

根據(jù)以上描述，該問題用數(shù)學語言描述如下：

其中：式（11）表示i和j的取值均為正整數(shù)且滿足1≤i≤N，1≤j≤K；式（12）表示一個基站上最多只能放置一個ES；式（13）表示被選中放置ES的基站數(shù)量要等于ES數(shù)量M；式（14）是用戶設(shè)備訪問時間限制，即每條訪問記錄的訪問開始時間tstrj不超過訪問結(jié)束時間tendj。

2 邊緣服務(wù)器放置

基于用戶密度和平均訪問時間的ES放置方法可以再表述如下：

a）找到一個最優(yōu)的邊緣服務(wù)器放置問題解決方案X。

b）使其滿足式（11）～（14）的約束并且最大化式（10）。

2.1 NP-hard問題證明

定理1 基于用戶密度和平均訪問時間的邊緣服務(wù)器放置問題Q是一個NP-hard問題。

證明 通過對0-1背包問題［23］的簡化，本文可以將問題Q歸約到一個已知的NP-Hard問題。具體地，本文將每個基站i看作一個物品Bi，每個物品Bi有一個價值Wi（F1，F(xiàn)2），Ui為

由于0-1背包問題是已知的NP-hard問題，所以問題Q也是NP-hard問題，即沒有已知的多項式時間算法可以解決。這意味著在一般情況下，本文無法在多項式時間內(nèi)找到問題Q的最優(yōu)解，而只能通過啟發(fā)式算法或近似算法來求解。

根據(jù)以上證明可以得出結(jié)論：基于用戶密度和平均訪問時間的邊緣服務(wù)器放置問題Q是NP-hard問題。

2.2 問題編碼和算法設(shè)計

為了有效地解決ESP問題，本文提出了一種基于用戶密度和平均訪問時間的邊緣服務(wù)器放置方法，并設(shè)計了一種MOSGA算法求解該問題。

SHO算法最早由Zhao等人［21］提出，其靈感來自于海馬的移動、捕捉和繁殖行為，具有速度快、收斂精度高等優(yōu)點。由于SHO算法提出之初是用于解決單目標優(yōu)化問題，而本文要解決的問題是一個多目標優(yōu)化問題，所以不能直接應(yīng)用。為了解決這一問題，本文將SHO算法與MOP算法結(jié)合，使其能夠用于解決多目標優(yōu)化問題，同時為使SHO算法能夠更好地跳出局部最優(yōu)，加快問題的求解，本文使用GA算法改進SHO算法的繁殖行為。下面將詳細介紹MOSGA。

1）海馬個體和適應(yīng)度函數(shù)的構(gòu)造

在MOSGA中，每個海馬實際上代表一種解決方案。整個海馬種群被定義為

其中：np為海馬的種群大小；d為變量的維數(shù)。對于所有的海馬，其適應(yīng)度值存儲如下：

2）海馬的移動

海馬的移動行為用于實現(xiàn)解空間的探索和開發(fā)，其有兩種模式：

a）海馬伴隨著海洋中的旋渦螺旋運動，這時新海馬的位置如下：

X1new（t+1）=Xi（t）+Lévy（λ）（（Xelite（t）－Xi（t））×x×y×z+Xelite（t））（17）

其中：Xelite（t）為當前迭代次數(shù)下最優(yōu)海馬時，并由算法4得出，Xi（t）為第i個海馬；x、y、z分別表示在螺旋運動下坐標（x，y，z）的三維分量，x=ρ×cos（θ），y=ρ×sin（θ），z=ρ×θ，這里ρ=u×eθv；u、v的取值均為0.05、λ取值為1.5［21］，θ為［0，2π］的隨機數(shù)；Lévy（z）為萊維飛行函數(shù)，其計算方式如下：

其中：s為一個常數(shù)；w、k為 ［0，1］的隨機數(shù)，由式（19）得出。σ的計算方式如下：

b）海馬隨著海浪做布朗運動，新海馬的位置如下：

X1new（t+1）=Xi（t）+rand×l×βt×（Xi（t）－βt×Xelite）（20）

其中：Xelite為全局最優(yōu)海馬的位置；l為一個常數(shù)；βt為布朗游走系數(shù)，計算方式為

由于海馬的移動服從正態(tài)0-1分布，為了權(quán)衡搜索和開發(fā)的性能，當rand（0，1）>0，海馬隨著海洋中的旋渦螺旋運動，否則海馬隨著海浪做布朗運動。

算法1 海馬移動時位置的更新過程

3）海馬的捕食

海馬以捕食浮游動物和小型甲殼動物為生，捕食有成功和失敗兩種結(jié)果。當海馬捕食成功時，海馬的位置更新如下：

X2new（t+1）=α×（Xelite－rand×X1new（t））+（1－α）×Xelite（22）

當海馬捕食失敗時，海馬的位置更新如下：

X2new（t+1）=（1－α）×（X1new（t）－rand×Xelite）+α×X1new（t）（23）

其中：X1new（t）表示海馬在第t次運動后的新位置；α表示海馬捕食的步長，計算方式如下：

其中：T表示最大迭代次數(shù)。

海馬進行捕食時，有90%的概率捕食成功，當海馬捕食成功時，按照式（22）更新位置；否則，按照式（21）更新位置。

算法2 海馬捕食時位置的更新過程

4）海馬的繁殖

與其他動物的繁殖不同，雄性海馬負責繁殖。首先，根據(jù)適應(yīng)度函數(shù)進行非支配排序，將適應(yīng)度好的一半海馬個體作為雄性海馬，另一半作為雌性海馬。海馬角色分配過程計算如下：

fa=X2sort（1：np/2）（25）

mo=X2sort（np/2+1：np）（26）

其中：X2sort是按適應(yīng)度降序排列的種群； fa和mo分別表示雄性和雌性海馬群。當雌性個體交配產(chǎn)生后代時，為了使得算法能夠更好地跳出局部最優(yōu)解，本文使用GA為海馬的繁殖行為添加變異操作，交配后的個體有一定的概率突變。海馬進行繁殖時：

Xoffi=rXfai+（1－r）Xmoi（27）

xoffi，q=lb+r1（ub－lb）（28）

其中，式（27）表示海馬交配產(chǎn)生后代Xoffi；式（28）表示后代Xoffi，q發(fā)生變異；r和r1為（0，1）的隨機數(shù)；Xoffi，q表示后代i在第q維發(fā)生變異；q為 ［0，d］的隨機整數(shù)；ub、lb問題變量的上界和下界。

算法3 海馬繁殖行為

5）最佳海馬個體

由于SHO算法提出之初是用于解決單目標優(yōu)化問題，而本文的問題是一個多目標優(yōu)化問題，為了使SHO算法能夠解決多目標問題，受MOP算法的啟發(fā)，本文使用MOP算法的非支配排序策略來比較個體的優(yōu)劣，并計算最高等級種群的質(zhì)心，選擇離質(zhì)心最近的個體作為最佳海馬：a）將海馬種群分為多個層；b）計算最高等級層中海馬適應(yīng)值的質(zhì)心；c）計算該層所有海馬個體與質(zhì)心歐氏距離；d）選擇離質(zhì)心最近的海馬的位置作為最佳海馬的位置。

算法4 最佳海馬位置尋找過程

6）MOSGA整體設(shè)計

在MOSGA中，海馬有移動、捕食和繁殖三種行為。MOSGA的完整流程為：a）初始化海馬種群的位置X、當前迭代次數(shù)t、最佳白鯨位置Xelite；b）開始種群迭代過程，計算當前迭代次數(shù)下所有海馬個體適應(yīng)值f1（Xi（t））、f2（Xi（t）），運行算法4計算當前迭代次數(shù)下最佳海馬位置Xelite（t），并更新全局最佳海馬位置Xelite；c）運行算法1和2更新海馬位置，運行算法3產(chǎn)生子代海馬，并將父子代海馬合并；d）檢查海馬位置并修復，再次計算海馬群的適應(yīng)值，根據(jù)適應(yīng)值對X（t）非支配排序，選擇排名前np的海馬個體進入X（t+1），更新迭代次數(shù)；e）檢查終止條件，當t≥T，MOSGA終止；否則返回b）；f）計算最佳海馬位置Xelite及其適應(yīng)值f1（Xelite（t））、f2（Xelite（t））。

算法5 MOSGA

2.3 MOSGA時間復雜度分析

時間復雜度是判斷算法性能的一個重要指標。本節(jié)將對MOSGA的時間復雜度進行分析。假設(shè)種群數(shù)量為np，最大迭代次數(shù)為T。MOSGA的時間復雜度來自以下五部分：

a）海馬群的初始化，其時間復雜度為O（np）；

b）根據(jù)算法4尋找最佳海馬個體的時間復雜度為O（2×np2×T）；

c）海馬移動執(zhí)行算法1的時間復雜度為O（np×T）；

d）海馬捕食執(zhí)行算法2的時間復雜度為O（np×T）；

e）海馬繁殖執(zhí)行算法3的時間復雜度O（2×np2×T）。

因此，MOBGA總的時間復雜度可以計算如下：

O（np）+2×O（2×np2×T）+2×O（np×T）=O（4np2×T+np×T）≈O（np2×T）（29）

即MOSGA的時間復雜度可近似為O（np2×T）。

3 仿真和評估

3.1 實驗環(huán)境

硬件環(huán)境：CPU為Intel Core i7 3.20 GHz，RAM為32 GB。

軟件環(huán)境：操作系統(tǒng)為64位Windows 11；開發(fā)軟件為PyCharm；編程語言為Python；編程工具為Python 3.9.7；數(shù)據(jù)庫為MySQL 5.7.23。

3.2 數(shù)據(jù)集說明

本文使用上海電信真實數(shù)據(jù)集對算法性能進行驗證，由于原始數(shù)據(jù)集中部分數(shù)據(jù)字段值缺失，所以需要對原始數(shù)據(jù)集進行處理后才能使用。經(jīng)過處理后得到的數(shù)據(jù)集合包含6 270個移動用戶在2 770個基站上共計558 737條訪問記錄，每條記錄包括基站經(jīng)緯度、用戶標識號、訪問開始時間和訪問結(jié)束時間。為了便于處理分析這些數(shù)據(jù)，本文將這些數(shù)據(jù)寫入MySQL數(shù)據(jù)庫中。

3.3 對比算法

為了驗證MOSGA的性能。本文將與RA、K-means［19］、NSGA［18］、LMM［23］進行對比。此外，為了保持公平性，MOSGA與對比算法中NSGA的最大迭代次數(shù)保持相同的設(shè)置。

由于LMM是基于的凸優(yōu)化理論來求解優(yōu)化問題的，而凸優(yōu)化理論要求目標優(yōu)化函數(shù)和解空間是凸的，適用于凸問題、單目標問題、光滑問題。本文所建模的問題是多目標優(yōu)化問題，且優(yōu)化函數(shù)非凸。為了使LMM可用于求解本文的問題，本文將多目標優(yōu)化問題近似分解成P1和P2兩個單目標優(yōu)化問題，分解如下：

其中：問題P1為最大化基站的平均訪問時間；問題P2為最大化基站的用戶密度；C1為放松約束后所有基站上ES總數(shù)最大值的不等式約束；C2為選中放置ES的基站數(shù)量要等于ES數(shù)目的等式約束。問題P1、P2的拉格朗日函數(shù)形式如下：

L1（X，β1，φ1）=－f1（X）+β1h（X）+φ1g（X）（34）

L2（X，β2，φ2）=－f2（X）+β2h（X）+φ2g（X）（35）

其中：β1、β2、φ1、φ2均為拉格朗日乘子。約束條件為

通過求解滿足式（36）約束的多組候選ESP方案X，過濾掉不滿足式（14）訪問時間約束的方案，并使用算法4中的尋找最佳海馬的策略選擇出使用了LMM求解出的最優(yōu)ESP方案。

3.4 實驗參數(shù)設(shè)置

本文實驗參數(shù)設(shè)置表1所示。

為了測試算法在不同任務(wù)數(shù)目和任務(wù)最大完成時間約束下的性能。本文設(shè)置了四組對比實驗，每組實驗重復20次取平均值。

a）第一組實驗：基站數(shù)量為2 770，邊緣服務(wù)器數(shù)量從50增加到450，間隔為50，測試在不同邊緣服務(wù)器數(shù)量下算法的性能；

b）第二組實驗：邊緣服務(wù)器數(shù)量為50，基站數(shù)量從500增加到1 400，間隔為100，測試在不同基站數(shù)量下算法的性能；

c）第三組實驗：邊緣服務(wù)器數(shù)量為50，基站數(shù)量為2 770，根據(jù)3.5節(jié)網(wǎng)絡(luò)延遲的測試數(shù)據(jù)，將每跳路由平均往返延遲設(shè)置為2 ms，以此測試不同算法在降低延遲方面的性能。

d）第四組實驗：邊緣服務(wù)器數(shù)量為50，基站數(shù)量為2 770。測試NSGA和MOSGA在不同迭代次數(shù)下算法的收斂性。并以此設(shè)置表1中的最大迭代次數(shù)。

3.5 實驗結(jié)果分析

1）不同邊緣服務(wù)器數(shù)量下算法的性能

表2、3記錄了在不同邊緣服務(wù)器數(shù)量下算法的性能數(shù)據(jù)，圖2、3展示了在不同邊緣服務(wù)器數(shù)量下算法的性能變化情況。隨著邊緣服務(wù)器數(shù)目增多，五種算法在總用戶密度和總平均訪問時間方面都有增加。其中，MOSGA取得了最優(yōu)的結(jié)果，并且隨著邊緣服務(wù)器數(shù)量的增加，其優(yōu)勢表現(xiàn)得尤為明顯。這是因為隨著邊緣服務(wù)器數(shù)量的增加，有更多的用戶密度高且平均訪問時間長的基站可供選擇，在這種情況下，MOSGA因為求解速度快、收斂精度高和較強的跳出局部最優(yōu)的能力，可在給定迭代次數(shù)下探索到更優(yōu)秀的放置方案。相比之下，RA的性能取決于隨機生成解；K-means的性能在很大程度上依賴于初始聚類中心點；NSGA在探索全局最優(yōu)點的能力稍顯不足；LMM在處理非凸函數(shù)時會陷入局部最優(yōu)解而無法得到全局最優(yōu)解，因為非凸函數(shù)存在多個局部極小值點，同時全局最優(yōu)解也可能不滿足或者部分滿足式（36）中的約束，這使得LMM的性能進一步下降。綜上所述，MOSGA表現(xiàn)最優(yōu)。在用戶密度方面，RA、K-means、NSGA、LMM與MOSGA的平均性能差距分別為40.37%、23.80%、11.33%、24.37%；在總的平均訪問時間方面，RA、K-means、NSGA、LMM與MOSGA的平均性能差距分別為29.94%、15.17%、6.25、20.80%。

2）不同的基站數(shù)目下算法的性能

表4和5記錄了在不同基站數(shù)量下算法的性能數(shù)據(jù)，圖4和5展示了在不同基站數(shù)量下算法的性能變化情況。隨著基站數(shù)量增加，除RA外，其他四種算法在總用戶密度和總的平均訪問時間方面都有增加。值得注意的是，隨著基站數(shù)量的增多，這四種算法在總用戶密度和總的平均訪問時間方面增長較為緩慢，這是因為雖然可選基站的數(shù)量在不斷增多，但新增的基站并沒有更多被選中的潛力，進而導致總的用戶密度和總的平均訪問時間增長緩慢，但MOSGA的變異操作為其搜索增加了多樣性，避免陷入局部最優(yōu)解，有更大的可能性找到全局最優(yōu)解。而RA由于其隨機性，其效果取決于每一次生成的解。綜上所述，MOSGA表現(xiàn)最優(yōu)。在用戶密度方面，RA、K-means、NSGA、LMM與MOSGA的平均性能差距分別為59.42%、27.46%、6.85%、29.21%；在總的平均訪問時間方面，RA、K-means、NSGA、LMM與MOSGA的平均性能差距分別為39.58%、22.35%、12.01%、23.08%。

3）不同算法在降低延遲方面的性能

如圖6所示，基站接受其覆蓋范圍內(nèi)終端設(shè)備的計算請求，并通過漫長的路由將計算任務(wù)發(fā)送到服務(wù)器上進行處理。為了評估不同邊緣服務(wù)器放置算法在降低延遲方面的性能，本文在同一個基站下向7個不同的服務(wù)器發(fā)送500次大小300 KB的數(shù)據(jù)包，并以此計算每跳路由之間的網(wǎng)絡(luò)延遲。表6記錄了通過同一基站向不同服務(wù)器發(fā)送數(shù)據(jù)的往返延遲。

由表6可知，每跳路由的平均延遲在［1.5，3.5］ms，當邊緣服務(wù)器放置到基站上時，可減少終端設(shè)備到服務(wù)器之間的路由跳數(shù)，降低延遲（降低的延遲=用戶設(shè)備的訪問頻率×路由跳數(shù)×平均每跳延遲）。為了便于比較，本文將路由跳數(shù)統(tǒng)一設(shè)置為1跳，平均每跳延遲設(shè)置為2 ms。表7記錄了不同邊緣服務(wù)器放置算法在降低延遲方面的性能?？梢钥闯?，MOSGA在降低延遲方面表現(xiàn)最優(yōu)，RA、K-means、NSGA、LMM與MOSGA的平均性能差距分別為57.65%、9.08%、3.30%、11.99%。

4）不同迭代次數(shù)下算法的穩(wěn)定性

如圖7所示當?shù)螖?shù)大于400時，NSGA、MOSGA已經(jīng)收斂。根據(jù)實驗結(jié)果，在3.4節(jié)將最大迭代次數(shù)設(shè)置為400。

4 結(jié)束語

本文研究了基于用戶密度和平均訪問時間的ESP問題，并設(shè)計了一種高效的算法MOSGA進行求解。MOSGA使用MOP算法的思想改進SHO算法，使其可以用于解決多目標優(yōu)化問題，同時使用GA改進SHO算法的繁殖階段，使MOSGA具有更好的全局搜索能力和收斂性，仿真實驗結(jié)果表明，MOSGA能夠有效地優(yōu)化邊緣服務(wù)器的放置方案，減少服務(wù)器的資源浪費現(xiàn)象，并降低終端設(shè)備訪問服務(wù)器的時間，此項研究可為研究ESP問題提供借鑒。此外，本文未考慮終端設(shè)備請求的異構(gòu)性，若用于新環(huán)境，該方法的準確性和效率會有一定的下降，未來本文將探索在終端設(shè)備異構(gòu)情況下的ESP問題，并進一步結(jié)合其他領(lǐng)域解決方案的優(yōu)點進一步改進MOSGA的性能，例如，使用凸優(yōu)化理論指導MOSGA種群的生成。同時本文也將結(jié)合更多的因素進行邊緣服務(wù)器的放置位置選擇，以進一步提升ES放置方案的性能。

參考文獻：

［1］Mansouri Y，Babar M A. A review of edge computing： features and resource virtualization ［J］. Journal of Parallel and Distributed Computing，2021，150（1）： 155-183.

［2］Kong Xiangjie，Wu Yuhan，Wang Hui，et al. Edge computing for Internet of Everything： a survey ［J］. IEEE Internet of Things Journal，2022，9（23）： 23472-23485.

［3］谷曉會，章國安. 移動邊緣計算在車載網(wǎng)中的應(yīng)用綜述 ［J］. 計算機應(yīng)用研究，2020，37（6）： 1615-1621. （Guo Xiaohui，Zhang Guoan. Survey of mobile edge computing applications in vehicular network ［J］. Application Research of Computers，2020，37（6）： 1615-1621.）

［4］Jiang Qinting，Zhou Xuanhong，Wang Ruili，et al. Intelligent monitoring for infectious diseases with fuzzy systems and edge computing： a survey ［J］. Applied Soft Computing，2022（123）： 108835-108850.

［5］施巍松，張星洲，王一帆，等. 邊緣計算： 現(xiàn)狀與展望 ［J］. 計算機研究與發(fā)展，2019，56（1）： 69-89. （Shi Weisong，Zhang Xingzhou，Wang Yifan，et al. Edge computing： state-of-the-art and future directions ［J］. Journal of Computer Research and Development，2019，56（1）： 69-89.）

［6］Chen Xiao，Liu Wei，Chen Jing，et al. An edge server placement algorithm in edge computing environment ［C］// Proc of the 12th International Conference on Advanced INFOCOM Technology. Piscataway，NJ： IEEE Press，2020： 85-89.

［7］Shen Bowen，Xu Xiaolong，Qi Lianyong，et al. Dynamic server placement in edge computing toward Internet of Vehicles ［J］. Computer Communications，2021，178（6）： 114-123.

［8］Cao Kun，Li Liying，Cui Yangguang，et al. Exploring placement of heterogeneous edge servers for response time minimization in mobile edge-cloud computing ［J］. IEEE Trans on Industrial Informatics，2020，17（1）： 494-503.

［9］Agac G，Baki B，Ar I M，et al. A supply chain network design for blood and its products using genetic algorithm： a case study of Turkey ［J］. Journal of Industrial and Management Optimization，2023，19（7）： 5407-5446.

［10］Xu Xiaolong，Xue Yuan，Qi Lianyong，et al. Load-aware edge server placement for mobile edge computing in 5G networks ［C］// Proc of the 17th International Conference on Service-Oriented Computing. Cham： Springer，2019： 494-507.

［11］Lu Dongyu，Qu Yuben，Wu Fan，et al. Robust server placement for edge computing ［C］// Proc of IEEE International Parallel and Distributed Processing Symposium. Piscataway，NJ： IEEE Press，2020： 285-294.

［12］Bhatta D，Mashayekhy L. A bifactor approximation algorithm for cloudlet placement in edge computing ［J］. IEEE Trans on Parallel and Distributed Systems，2022，33（8）： 1787-1798.

［13］Xiao Kaile，Gao Zhipeng，Wang Qian，et al. A heuristic algorithm based on resource requirements forecasting for server placement in edge computing ［C］// Proc of Symposium on Edge Computing. Piscataway，NJ： IEEE Press，2018： 354-355.

［14］Fan Qiang，Ansari N. On cost aware cloudlet placement for mobile edge computing ［J］. IEEE/CAA Journal of Automatica Sinica，2019，6（4）： 926-937.

［15］Li Yuanzhe，Wang Shangguang. An energy-aware edge server placement algorithm in mobile edge computing ［C］// Proc of International Conference on Edge Computing. Piscataway，NJ： IEEE Press，2018： 66-73.

［16］趙暢，劉允剛，陳琳，等. 面向元啟發(fā)式算法的多無人機路徑規(guī)劃現(xiàn)狀與展望 ［J］. 控制與決策，2022，37（5）： 1102-1115. （Zhao Chang，Liu Yungang，Chen Lin，et al. Research and development trend of multi-UAV path planning based on metaheuristic algorithm ［J］. Control and Decision，2022，37（5）： 1102-1115.）

［17］Bhol S，Sahu N C. Decarbonizing the grid by optimal scheduling of solar PV-wind turbine-pumped hydro storage considering application on heuristic algorithms： a comprehensive review ［J］. International Journal of Energy Research，2021，45（13）： 18473-18497.

［18］Yuan L，Gu Jie，Ma Jinghuan，et al. Optimal network partition and edge server placement for distributed state estimation ［J］. Journal of Modern Power Systems and Clean Energy，2022，10（6）： 1637-1647.

［19］Li Wenzao，Chen Jiali，Li Yiqian，et al. Mobile edge server deployment towards task offloading in mobile edge computing： a clustering approach ［J］. Mobile Networks and Applications，2022，27（4）： 1476-1489.

［20］Tan K C，Lee T H，Khor E F. Evolutionary algorithms for multi-objective optimization： performance assessments and comparisons ［J］. Artificial Intelligence Review，2002，17（4）： 251-290.

［21］Zhao Shijie，Zhang Tianran，Ma Shilin，et al. Sea-horse optimizer： a novel nature-inspired meta-heuristic for global optimization problems ［J］. Applied Intelligence，2023，53（10）： 11833-11860.

［22］Srinivas M，Patnaik L M. Genetic algorithms： a survey ［J］. Computer，1994，27（6）： 17-26.

［23］Li Mengmou. Generalized Lagrange multiplier method and KKT conditions with an application to distributed optimization ［J］. IEEE Trans on Circuits and Systems Ⅱ： Express Briefs，2018，66（2）： 252-256.

［24］Karp R M. Reducibility among combinatorial problems ［M］. Berlin： Springer，2010： 219-241.

［25］Fei Weilin，Liu Cong，Hu Sheng. Research on swarm intelligence optimization algorithm ［J］. The Journal of China Universities of Posts and Telecommunications，2020，27（3）： 1-20.