作者簡介：田榮倜（1998－），男，湖南邵陽人，碩士研究生，主要研究方向為邊緣計算；胡志剛（1963－），男（通信作者），山西孝義人，教授，博導(dǎo)，博士，主要研究方向為網(wǎng)絡(luò)并行處理、高性能計算、軟件工程（zghu@csu.edu.cn）．

摘 要：針對邊緣計算中服務(wù)副本選擇過程中多用戶資源爭用導(dǎo)致的服務(wù)質(zhì)量降低的難題，提出了一種網(wǎng)絡(luò)接入點(diǎn)選擇和服務(wù)副本選擇聯(lián)合優(yōu)化方法。首先，依據(jù)用戶所在位置，貪心地為每條用戶請求選擇合適的網(wǎng)絡(luò)接入點(diǎn)，以避免大量用戶同時選擇同一個基站而造成網(wǎng)絡(luò)擁塞。其次，網(wǎng)絡(luò)中存在多個服務(wù)副本，在服務(wù)副本選擇階段，依據(jù)每個副本的負(fù)載以及用戶的移動路徑，基于改進(jìn)的免疫遺傳算法為每條用戶請求選擇合適的服務(wù)副本，以期提高整個系統(tǒng)的運(yùn)行效率。仿真實(shí)驗結(jié)果表明，相比于已有方案，該策略能有效提高用戶服務(wù)質(zhì)量。

關(guān)鍵詞：副本選擇；接入網(wǎng)絡(luò)選擇；移動性感知；擁塞感知

中圖分類號：TP393 文獻(xiàn)標(biāo)志碼：A

文章編號：1001－3695（2023）04－035－1178－06

Abstract：This paper proposed a joint optimization method of network access point selection and service replica selection to address the challenge of service quality degradation caused by multi-user resource contention in edge computing.Firstly，it greedily selected the appropriate network access point for each user request depending on the user’s location.So as to avoid network congestion caused by a large number of users selecting the same access network simultaneously.Secondly，there were multiple service replicas in the network.In the service replica selection stage，it determined the appropriate service replica for each user request according to the load of each replica and the user’s mobility path，based on an improved immune genetic algorithm.Thus，it improved the operational efficiency of the whole system.The simulation experimental results demonstrate that the method can effectively improve the user service quality compared with the existing solutions.

Key words：replica selection；access network selection；mobility aware；congestion aware

0 引言

移動設(shè)備與網(wǎng)絡(luò)流量的快速增長以及人們對于低時延應(yīng)用的需求增長，推動了移動邊緣計算（MEC）的快速發(fā)展。不同于傳統(tǒng)的云計算范式，MEC中服務(wù)在地理位置上的臨近性使得用戶請求可以快速得到處理，同時減少主干網(wǎng)的傳輸壓力，為智能制造[1]、輔助駕駛[2]、虛擬現(xiàn)實(shí)[3，4]、增強(qiáng)現(xiàn)實(shí)[5]等應(yīng)用提供了很好的低時延服務(wù)支持。一種典型的邊緣計算訪問模式中，服務(wù)提供商在靠近用戶的位置租用物理資源，并通過虛擬化技術(shù)將服務(wù)以虛擬機(jī)或者容器的形式部署在邊緣服務(wù)器，其中包含相關(guān)服務(wù)的處理邏輯和支撐數(shù)據(jù)，比如預(yù)訓(xùn)練好的機(jī)器學(xué)習(xí)模型和必需的數(shù)據(jù)庫。一般地，用戶通過附近的接入點(diǎn)（AP）發(fā)出對某種服務(wù)的調(diào)用請求，同時上傳需要處理的用戶數(shù)據(jù)，該請求和相應(yīng)數(shù)據(jù)將被轉(zhuǎn)發(fā)到附近部署有該服務(wù)的邊緣服務(wù)器上處理，并將處理后的結(jié)果返回給用戶。服務(wù)的訂閱者具有分散且不斷移動的特點(diǎn)，為了提供良好的服務(wù)質(zhì)量，服務(wù)提供商通常需要在一片區(qū)域內(nèi)部署多個服務(wù)實(shí)例，本文稱之為服務(wù)副本。所以副本選擇問題指的就是如何為每個發(fā)出請求的用戶選擇合適的服務(wù)副本處理該用戶請求。

對于熱門服務(wù)，多個終端用戶同時發(fā)出服務(wù)請求，此時不合理的接入網(wǎng)絡(luò)選擇和副本選擇策略將會造成對于網(wǎng)絡(luò)、計算、內(nèi)存等資源的爭用。一方面，在資源受限的邊緣服務(wù)器上，多個請求的資源爭用勢必顯著降低系統(tǒng)整體執(zhí)行效率，從而降低用戶服務(wù)質(zhì)量。雖然可以通過增加物理資源來緩解這種爭用，但是這同時會導(dǎo)致額外的租用開銷。另一方面，在5G環(huán)境下，基站的部署更加密集，同一個用戶可能會處于多個接入網(wǎng)絡(luò)的覆蓋范圍下。這種情況下，對接入網(wǎng)絡(luò)的選擇也會顯著影響請求響應(yīng)時延，不合理的接入網(wǎng)絡(luò)選擇策略會導(dǎo)致不必要的網(wǎng)絡(luò)擁塞，并且會使一些用戶總是連接到擁塞的網(wǎng)絡(luò)接入點(diǎn)[6，7]。因此，在密集網(wǎng)絡(luò)環(huán)境中同時存在多個服務(wù)副本的情況下，由于用戶所處位置差異、用戶移動性以及各個服務(wù)副本的異質(zhì)性，每條服務(wù)請求如何接入網(wǎng)絡(luò)以及選擇哪一個服務(wù)副本來處理請求都會顯著影響服務(wù)質(zhì)量。

當(dāng)前，邊緣計算中的副本選擇問題大多描述為請求調(diào)度問題。例如文獻(xiàn)[8，9]研究了邊緣云中數(shù)據(jù)密集型應(yīng)用的服務(wù)放置和請求調(diào)度問題，考慮在通信和計算資源的限制下，為每條請求選擇服務(wù)副本以優(yōu)化服務(wù)的用戶請求數(shù)目。文獻(xiàn)[10]以最小化操作開銷為目標(biāo)，為聯(lián)合服務(wù)放置和請求調(diào)度問題設(shè)計了在線算法。一些研究[11，12]從用戶分配的角度研究副本選擇問題，即為每個服務(wù)副本選擇處理的用戶請求集合。但是以上研究都是考慮最大化服務(wù)的用戶總數(shù)量，而沒有以提高用戶服務(wù)質(zhì)量為目標(biāo)對副本選擇問題進(jìn)行進(jìn)一步的研究，也沒有考慮到多用戶之間的干擾和用戶的移動性。

文獻(xiàn)[13]考慮到應(yīng)用的異質(zhì)性、用戶的移動性、邊緣服務(wù)器的異質(zhì)性等問題，采用深度確定性策略梯度來進(jìn)行副本選擇以優(yōu)化訪問時延。與本文最接近的研究文獻(xiàn)[14]，其正式定義了移動性感知的多用戶服務(wù)副本選擇問題，并且提出使用遺傳算法求解此問題，以獲取近似最優(yōu)的副本選擇方案。然而，以上研究都沒有考慮網(wǎng)絡(luò)密集環(huán)境下的接入網(wǎng)絡(luò)選擇。

本文從服務(wù)提供商的角度研究密集網(wǎng)絡(luò)環(huán)境下接入網(wǎng)絡(luò)選擇和副本選擇聯(lián)合優(yōu)化。 即在固定的服務(wù)副本部署環(huán)境下，當(dāng)多個用戶同時請求某種服務(wù)時，考慮用戶移動性、副本異質(zhì)性以及多個用戶之間的資源爭用，為每個用戶請求作出合理的接入網(wǎng)絡(luò)選擇和服務(wù)副本選擇決策，以提高整體服務(wù)質(zhì)量。

本文考慮并建模了密集網(wǎng)絡(luò)環(huán)境下的接入網(wǎng)絡(luò)選擇和副本選擇聯(lián)合優(yōu)化問題，

提出了基于貪心策略的擁塞感知接入網(wǎng)絡(luò)選擇方法和基于改進(jìn)免疫遺傳算法的服務(wù)副本選擇算法來求解上述問題，以期在不增加部署開銷的前提下提高用戶服務(wù)質(zhì)量。

基于真實(shí)的基站數(shù)據(jù)集，實(shí)施了仿真實(shí)驗來驗證本文所提出策略的性能。結(jié)果表明，與幾個基準(zhǔn)方法對比，本文策略可以有效降低用戶平均響應(yīng)時延，提高用戶服務(wù)質(zhì)量。

1 系統(tǒng)模型

對于既定的副本放置方案，接入網(wǎng)絡(luò)選擇與副本選擇聯(lián)合優(yōu)化研究旨在為每條用戶請求選擇最合適的接入基站以及服務(wù)副本。如圖1所示，考慮基站密集部署的邊緣環(huán)境，用戶分散于邊緣區(qū)域，同一個用戶可能會被多個基站所覆蓋，用戶集合記為U={u1，u2，…，uN}。一共有M個邊緣云，每個邊緣云由無線基站（接入點(diǎn)）以及其相配套的服務(wù)器組成，無線基站集合記為B={b1，b2，…，bM}?；綽j只能服務(wù)以自身為中心，以rbj為半徑的圓形區(qū)域范圍內(nèi)的用戶，將特定時隙覆蓋用戶ui的基站集合記為

Symbol TigerFCpi。邊緣云之間通過高速局域網(wǎng)互相連接。只有部分邊緣云上放置有服務(wù)副本，整個邊緣一共部署了K個副本，表示為集合Rep={r1，r2，…，rK}。每個副本都部署在不同的邊緣服務(wù)器上，并且假設(shè)在選擇期間副本放置方案不變動。

本文假設(shè)每個用戶僅發(fā)出一條請求，若單個用戶發(fā)出多條請求則視為多個用戶所發(fā)出。以虛擬現(xiàn)實(shí)圖片渲染服務(wù)為例，某用戶發(fā)出一條圖片渲染請求，同時上傳原始圖片，該請求和數(shù)據(jù)被發(fā)送到合適的服務(wù)副本上并得到處理，然后將渲染后的圖片返回給用戶。

邊緣環(huán)境下的服務(wù)副本選擇較為復(fù)雜，一方面，用戶處在移動中，可能離開當(dāng)前基站信號覆蓋范圍；另一方面，在多用戶場景下，用戶請求之間會存在資源爭用。本文主要考慮兩點(diǎn)：a）多個用戶選擇同一個無線接入點(diǎn)上傳數(shù)據(jù)會造成帶寬資源爭用；b）多個用戶請求選擇同一個服務(wù)副本會增大在該副本上的平均執(zhí)行時間，具體取決于邊緣服務(wù)器系統(tǒng)的并行調(diào)度策略。

用戶在邊緣區(qū)域不斷移動，對于特定用戶，以其移動路徑表示這種移動性，即{（x1，y1），（x2，y2），…，（xt，yt）}，其中每個元素表明在特定時間點(diǎn)該用戶的坐標(biāo)位置。本文和文獻(xiàn)[15]一樣，假設(shè)用戶的移動路徑是可以提前獲知的，這一假設(shè)得益于當(dāng)前軌跡預(yù)測等技術(shù)的進(jìn)步以及導(dǎo)航地圖等應(yīng)用的大規(guī)模使用，提前獲知用戶的移動軌跡是可行的。

GANSA的核心思想在于，優(yōu)先為接入網(wǎng)絡(luò)可選擇范圍更小的用戶選擇擁塞程度更小的接入網(wǎng)絡(luò)。如圖2所示，按照網(wǎng)絡(luò)的密集程度可以將被基站覆蓋到的地區(qū)分為A、B、C三個區(qū)域。在階段1，算法先為區(qū)域A、C內(nèi)的用戶選擇接入網(wǎng)絡(luò)，因為它們的可選擇范圍更少。在階段2，再為區(qū)域B中的用戶選擇接入網(wǎng)絡(luò)，選擇策略是在該區(qū)域可達(dá)的基站中貪心地選擇狀態(tài)最佳的基站。通過這種方式，區(qū)域B中的用戶可以選擇網(wǎng)絡(luò)狀況更佳的基站2接入網(wǎng)絡(luò)，而不是依據(jù)地理距離選擇大量用戶聚集的基站1，從而有效避免地理上聚集的用戶，同時選擇相同的鄰近接入網(wǎng)絡(luò)造成的網(wǎng)絡(luò)資源爭用。

本文假設(shè)選擇同一個接入網(wǎng)絡(luò)的所有用戶平等分配上行帶寬資源[16]。而無線下行帶寬相對來說較為充足，所以本文不考慮無線下行帶寬爭用，即假設(shè)用戶通過無線基站獲取處理結(jié)果時能夠分配到固定大小的帶寬資源。

3.2 基于改進(jìn)免疫遺傳的副本選擇算法

在獲取了每個用戶的接入網(wǎng)絡(luò)選擇決策之后，第二步就是在選定的接入網(wǎng)絡(luò)選擇決策下為每條用戶請求選擇服務(wù)副本。依據(jù)文獻(xiàn)[14]，在特定接入網(wǎng)絡(luò)選擇策略下的副本選擇問題可以由設(shè)施選址問題歸約而來，所以是NP難問題。

遺傳算法是一個被廣泛使用的元啟發(fā)式算法，具有較強(qiáng)的全局搜索能力，對于許多問題都能夠快速取得比較好的求解效果，是一個較為通用的求解NP難問題的方法。但是，遺傳算法的局部搜索能力較弱，容易陷入早熟和局部最優(yōu)，并且針對具體的問題，往往需要依據(jù)問題的性質(zhì)作出改進(jìn)才能取得更優(yōu)良的近似解。本文采用改進(jìn)的遺傳算法來求解服務(wù)副本選擇子問題，但不同于文獻(xiàn)[14]，本文引入疫苗注射算子[17]和單位時延感知的變異算子以提高算法在此問題中的尋優(yōu)能力。

一個可行的副本選擇方案被編碼為一條染色體，其上每個基因位點(diǎn)代表一個用戶的服務(wù)副本選擇決策，則染色體長度就是用戶請求數(shù)N。例如，若染色體的1號基因位點(diǎn)上的值為3，則表示用戶1選擇了服務(wù)副本3處理其請求。記種群規(guī)模為NPOP，進(jìn)行Numit輪迭代。本文的目標(biāo)是最小化平均響應(yīng)時延，所以將個體的適應(yīng)度函數(shù)定義為此個體對應(yīng)的副本選擇方案X下平均響應(yīng)時延的倒數(shù)，即

在傳統(tǒng)的遺傳算法中，最重要的操作是交叉和變異，對于遺傳算法的收斂至關(guān)重要。交叉就是父種群中個體以一定概率兩兩交換染色體片段形成子代，旨在組合父種群的優(yōu)質(zhì)基因片段產(chǎn)生優(yōu)質(zhì)個體，本文采用最常使用的兩點(diǎn)交叉算子。而變異算子是指對父種群中的個體以一定概率進(jìn)行突變，以期獲得適應(yīng)度更高的個體。文獻(xiàn)[14]為了以更大的可能變異得到適應(yīng)度更高的個體，提出了響應(yīng)時間感知的變異策略，即認(rèn)為響應(yīng)時間更大的請求有更大的優(yōu)化空間。然而，僅僅是響應(yīng)時間并不能準(zhǔn)確反映該基因位點(diǎn)的可優(yōu)化空間，因為響應(yīng)時間受到請求本身需要處理的數(shù)據(jù)量的影響。考慮這樣一種情況，用戶A和B分別要求渲染一張10 MB和5 MB的圖片，而假設(shè)在某種副本選擇方案下，兩個用戶請求的響應(yīng)時延均為10 s，則顯然用戶B的響應(yīng)時間的優(yōu)化空間更大。因此本文提出單位數(shù)據(jù)響應(yīng)時間感知的變異策略，不僅考慮響應(yīng)時間，而且將請求本身需要處理的數(shù)據(jù)量考慮在內(nèi)。

另外，為了進(jìn)一步提高算法的局部搜索能力，同時避免種群退化，本文引入疫苗注射算子來進(jìn)行副本選擇。即通過對種群染色體注射疫苗，以期提高染色體的適應(yīng)度，并通過免疫測試防止種群退化。

如圖3所示，對于自適應(yīng)疫苗注射算子，需要保留當(dāng)前最優(yōu)的染色體個體作為疫苗，然后以一定概率對種群中的染色體進(jìn)行免疫接種操作。疫苗注射與免疫測試具體步驟如算法2所示。

上述算法中，對一個種群POP做疫苗注射與免疫選擇時，先初始化一個空的新種群，然后以一定概率probvacc從舊種群中選擇染色體進(jìn)行免疫操作，在選中的染色體上隨機(jī)選擇一個位點(diǎn)，將此位點(diǎn)的值替換為疫苗對應(yīng)位點(diǎn)的值。然后對替換后的染色體進(jìn)行免疫測試，即如果注射疫苗后的染色體適應(yīng)度增強(qiáng)，則以免疫后的染色體加入種群，否則直接以原始染色體加入種群。

上述優(yōu)化方法中，由于變異位點(diǎn)的數(shù)目固定，引入單位時延感知的變異算子意味著讓優(yōu)化空間更大的位點(diǎn)以更大的概率變異，從而增大搜索到更優(yōu)解的概率。而疫苗注射與免疫選擇算子中，由于疫苗本身是當(dāng)前的優(yōu)質(zhì)個體，具有更高的適應(yīng)度，所以疫苗注射過程能夠以較大概率使得當(dāng)前染色體的適應(yīng)度提高，而免疫測試過程則保證了注射疫苗后種群不會退化。所以本文提出的基于改進(jìn)免疫遺傳的副本選擇算法具有更強(qiáng)的優(yōu)化能力和更高的搜索效率。

3.3 接入網(wǎng)絡(luò)與副本聯(lián)合選擇算法

基于上述討論，本文所提出的接入網(wǎng)絡(luò)與副本聯(lián)合選擇算法細(xì)節(jié)如算法3所示。

算法3 基于免疫遺傳算法的單位時延感知聯(lián)合網(wǎng)絡(luò)與副本選擇（IGa-UL-JNRS）

算法3通過依次求解兩個子問題來求解聯(lián)合優(yōu)化問題。算法開始時，通過調(diào)用GANSA避免用戶聚集選擇同一個接入網(wǎng)絡(luò)，從而獲得較低的網(wǎng)絡(luò)接入時延，后續(xù)的副本選擇決策基于此進(jìn)行。在進(jìn)行副本選擇時，首先初始化一個種群并記錄當(dāng)前最優(yōu)個體，然后進(jìn)行Numit輪迭代。每輪迭代中，先復(fù)制父代種群，然后分別通過Crossover、Mutation、Vaccinate算子依次對父代種群進(jìn)行交叉、變異、疫苗注射與免疫測試操作，通過sortByFitness將得到的新種群與原始父種群混合后按照適應(yīng)度排序，通過Select算子選擇適應(yīng)度最高的NPOP個體組成新一代種群。

在一個無線上行帶寬爭用較嚴(yán)重的環(huán)境下，接入網(wǎng)絡(luò)選擇決策會顯著影響數(shù)據(jù)上傳時間，進(jìn)而影響總體響應(yīng)時延。而后續(xù)的副本選擇決策過程依據(jù)總體響應(yīng)時延進(jìn)行，所以接入網(wǎng)絡(luò)選擇會進(jìn)而影響后續(xù)的副本選擇決策。高效的接入網(wǎng)絡(luò)選擇策略不僅有利于降低接入時延，而且降低了網(wǎng)絡(luò)接入時延成為服務(wù)質(zhì)量提升的瓶頸的可能性，從而有利于后續(xù)作出更優(yōu)的副本選擇決策，提高服務(wù)質(zhì)量。

GANSA中，只需要遍歷所有用戶一次就可以得到接入網(wǎng)絡(luò)選擇方案。而在基于遺傳算法的副本選擇算法中，計算復(fù)雜度主要來自于交叉、變異、免疫算子，其均為多項式時間復(fù)雜度。所以算法3整體是多項式時間復(fù)雜度的。

4 實(shí)驗與算法評估

4.1 實(shí)驗設(shè)置

本文使用Python搭建實(shí)驗環(huán)境。為了評估本文策略的性能，采用與文獻(xiàn)[14]相似的實(shí)驗環(huán)境和數(shù)據(jù)集。即基于Shanghai-Telecom和EUA數(shù)據(jù)集開展實(shí)驗，分別包含上海地區(qū)和澳大利亞墨爾本地區(qū)城市中心地區(qū)的基站分布數(shù)據(jù)，在兩個數(shù)據(jù)集范圍內(nèi)分別選取600 m×600 m的區(qū)域為實(shí)驗對象。對于兩個數(shù)據(jù)集，簡單假設(shè)所有基站具有相同的覆蓋半徑，用戶在選定范圍內(nèi)均勻隨機(jī)分布，并且用戶遵循隨機(jī)路徑點(diǎn)模型[18]在區(qū)域內(nèi)移動。其他一些參數(shù)設(shè)置如表1所示。

免疫遺傳算法的一些執(zhí)行參數(shù)如表2所示。在所有實(shí)驗參數(shù)設(shè)置下，均重復(fù)20次實(shí)驗，對結(jié)果取平均值。

4.2 比較方法

為了檢驗所提出的IGa-UL-JNRS的性能，將IGa-UL-JNRS與以下幾種基準(zhǔn)方法進(jìn)行比較。

a）GAMEC[15]。決策時不考慮用戶之間的干擾，也不考慮接入網(wǎng)絡(luò)選擇和副本選擇的聯(lián)合優(yōu)化，選擇距離用戶最近的基站作為上傳接入點(diǎn)，然后基于模擬退火改進(jìn)的遺傳算法進(jìn)行副本選擇。

b）Ga-L-RS。即文獻(xiàn)[14]提出的MEC系統(tǒng)中基于遺傳算法的服務(wù)實(shí)例選擇方法（GASISMEC）。該方法考慮了用戶之間的干擾，但沒有考慮接入網(wǎng)絡(luò)選擇和副本選擇的聯(lián)合優(yōu)化，在進(jìn)行接入網(wǎng)絡(luò)選擇時，選擇距離用戶最近的基站作為上傳接入點(diǎn)，然后基于總體時延感知的遺傳算法進(jìn)行副本選擇。

c）Ga-UL-RS。不考慮接入網(wǎng)絡(luò)選擇和副本選擇的聯(lián)合優(yōu)化，簡單選擇距離最近的基站作為網(wǎng)絡(luò)接入點(diǎn)，然后基于單位時延感知的遺傳算法進(jìn)行副本選擇。

d）Ga-UL-JNRS。使用GANSA為用戶選擇接入網(wǎng)絡(luò)，然后使用單位響應(yīng)時延感知遺傳算法進(jìn)行副本選擇。

4.3 評價指標(biāo)

本文最終目標(biāo)是提高用戶服務(wù)質(zhì)量，本文以所有用戶請求的平均響應(yīng)時延來衡量用戶服務(wù)質(zhì)量，平均響應(yīng)時延越低則用戶服務(wù)質(zhì)量越高。另外，對所提算法的執(zhí)行效率做了評估。

4.4 實(shí)驗結(jié)果

圖4為EUA和Shanghai-Telecom數(shù)據(jù)集上，幾種算法的平均響應(yīng)時延隨用戶數(shù)目的變化對比。其中，從Ga-UL-RS與Ga-UL-JNRS的對比可以看出，相比在進(jìn)行接入網(wǎng)絡(luò)選擇時簡單選擇最近的基站策略，聯(lián)合接入網(wǎng)絡(luò)選擇與副本選擇策略通過盡量均勻地分配無線上行帶寬，緩解了當(dāng)用戶在地理空間大量聚集時造成的嚴(yán)重的上行帶寬爭用，從而獲取了更低的響應(yīng)延遲。并且隨著用戶數(shù)目的增加，網(wǎng)絡(luò)資源爭用的加劇，雖然所有算法的用戶平均響應(yīng)時延均增大，但是聯(lián)合接入網(wǎng)絡(luò)與副本選擇對服務(wù)質(zhì)量的增益越發(fā)明顯。而GAMEC由于在決策時既沒有考慮多用戶之間的計算資源爭用，又沒有考慮鄰近用戶對無線上行帶寬的爭用，實(shí)際執(zhí)行時的計算和帶寬資源爭用降低了邊緣云系統(tǒng)整體執(zhí)行效率，所以平均響應(yīng)時延最高。

從Ga-UL-RS與Ga-L-RS的對比可以看出，單位時延感知的變異策略能夠讓算法在有限的迭代次數(shù)內(nèi)搜索到更優(yōu)的解，即獲得更高的服務(wù)質(zhì)量。而Ga-UL-JNRS與IGa-UL-JNRS之間的對比則體現(xiàn)了簡單遺傳算法與免疫遺傳算法之間的尋優(yōu)能力差距，疫苗注射與免疫測試算子增強(qiáng)了算法的尋優(yōu)能力，獲得了更高的服務(wù)質(zhì)量。

圖5為在EUA和Shanghai-Telecom數(shù)據(jù)集上，幾種算法的平均時延隨著服務(wù)副本數(shù)目的變化對比。從圖中可以看出，隨著服務(wù)副本數(shù)目的增加，響應(yīng)時延顯著降低。這是因為更多的副本意味著更多的可分配資源，增加副本數(shù)目意味著減少資源爭用。不難推斷出，如果每個邊緣云都部署了服務(wù)副本，那么所有用戶都能獲取到較高的服務(wù)質(zhì)量，然而這也意味著更大的資源租賃與維護(hù)開銷。在服務(wù)部署時，可以依據(jù)服務(wù)水平協(xié)議進(jìn)行權(quán)衡，比如為時延敏感型應(yīng)用部署更多服務(wù)副本。相比其他基準(zhǔn)方法，提出的IGa-UL-JNRS算法始終能夠獲得最高的服務(wù)質(zhì)量。

圖6為在EUA數(shù)據(jù)集上，用戶數(shù)為50，副本數(shù)為3，采用GANSA進(jìn)行接入網(wǎng)絡(luò)選擇時，幾種副本選擇算法的最優(yōu)個體適應(yīng)度隨迭代次數(shù)的變化情況?？梢钥闯觯谇?0輪迭代中，四種方法的適應(yīng)度均隨著迭代次數(shù)快速上升。但是20輪迭代之后，沒有引入疫苗注射與免疫測試算子的Ga-UL-JNRS與Ga-L-JNRS算法均進(jìn)入較長的平臺期，而IGa-UL-JNRS與IGa-L-JNRS算法的適應(yīng)度則在120代左右再次持續(xù)上升。Ga-L-JNRS在850代達(dá)到最高適應(yīng)度0.067 52，而其余三種算法達(dá)到同樣適應(yīng)度值的迭代次數(shù)分別是449、157、16。圖7展示了EUA數(shù)據(jù)集上幾種接入網(wǎng)絡(luò)與副本聯(lián)合選擇算法求解時間消耗隨著用戶數(shù)量的變化情況。對比可見，雖然疫苗注射和免疫測試算子的加入會帶來一定的計算開銷，但是能夠顯著增強(qiáng)尋優(yōu)能力，從而以更少的迭代次數(shù)搜索到更優(yōu)的解，所以仍然具有更高的搜索效率。而IGa-UL-JNRS和IGa-L-JNRS的時間開銷非常接近，但前者具有更高的適應(yīng)度和更快的收斂速度，這表明單位時延感知的變異算子的引入能夠在不顯著增加計算開銷的前提下提高算法的效率。

5 結(jié)束語

本文研究了移動邊緣計算中，密集網(wǎng)絡(luò)環(huán)境下多用戶同時請求同種服務(wù)時的接入網(wǎng)絡(luò)選擇和服務(wù)副本選擇聯(lián)合優(yōu)化問題。為了求解此問題，對于接入網(wǎng)絡(luò)選擇子問題和服務(wù)副本選擇子問題分別提出了對應(yīng)的求解算法，提出使用一種基于貪心的接入網(wǎng)絡(luò)選擇算法求解接入網(wǎng)絡(luò)選擇子問題，使用一種改進(jìn)的疫苗遺傳算法求解服務(wù)副本選擇子問題。仿真實(shí)驗結(jié)果表明，在密集網(wǎng)絡(luò)環(huán)境下，本文方法能夠在不增加部署開銷的前提下有效提高服務(wù)質(zhì)量。

在未來的工作中，將進(jìn)一步研究密集網(wǎng)絡(luò)環(huán)境下移動性感知的副本選擇問題，主要包括與副本放置問題進(jìn)行聯(lián)合優(yōu)化。

參考文獻(xiàn)：

［1］Wang Yimeng，Zhao Cong，Yang Shusen，et al.MPCSM：microservice placement for edge-cloud collaborative smart manufacturing[J].IEEE Trans on Industrial Informatics，2020，17（9）：5898－5908.

[2]Vázquez-Gallego F，Vilalta R，García A，et al.Demo：a mobile edge computing-based collision avoidance system for future vehicular networks[C]//Proc of IEEE Conference on Computer Communications Workshops.Piscataway，NJ：IEEE Press，2019：904－905.

[3]Lai Zeqi，Hu Y C，Cui Yong，et al.Furion：engineering high-quality immersive virtual reality on today’s mobile devices[J].IEEE Trans on Mobile Computing，2019，19（7）：1586-1602.

[4]Zhang Yuan，Jiao Lei，Yan Jinyao，et al.Dynamic service placement for virtual reality group gaming on mobile edge cloudlets[J].IEEE Journal on Selected Areas in Communications，2019，37（8）：1881-1897.

[5]Ren Jinke，He Yinghui，Huang Guan，et al.An edge-computing based architecture for mobile augmented reality[J].IEEE Network，2019，33（4）：162-169.

[6]Gao Bin，Zhou Zhi，Liu Fangming，et al.Winning at the starting line：joint network selection and service placement for mobile edge computing[C]//Proc of IEEE Conference on Computer Communications Workshops.Piscataway，NJ：IEEE Press，2019：1459-1467.

[7]Gao Bin，Zhou Zhi，Liu Fangming，et al.An online framework for joint network selection and service placement in mobile edge computing[J].IEEE Trans on Mobile Computing，2021，21（11）：3836－3851.

[8]Farhadi V，Mehmeti F，He Ting，et al.Service placement and request scheduling for data-intensive applications in edge clouds[J].IEEE/ACM Trans on Networking，2021，29（2）：779-792.

[9]He Ting，Khamfroush H，Wang Shiqiang，et al.It’s hard to share：joint service placement and request scheduling in edge clouds with sharable and non-sharable resources[C]//Proc of the 38th International Conference on Distributed Computing Systems.Piscataway，NJ：IEEE Press，2018：365－375.

[10]Su Lina，Wang Ne，Zhou Ruiting，et al.Dynamic service placement and request scheduling for edge networks[J].Computer Networks，2022，213：article ID 108997.

[11]Lai P，He Qiang，Cui Guangming，et al.Edge user allocation with dynamic quality of service[C]//Proc of the 17th International Conference on Service-Oriented Computing.Berlin：Springer，2019：86-101.

[12]He Qiang，Cui Guangming，Zhang Xuyun，et al.A game-theoretical approach for user allocation in edge computing environment[J].IEEE Trans on Parallel and Distributed Systems，2019，31（3）：515－529.

[13]Guo Feiyan，Tang Bing，Tang Mingdong，et al.Microservice selection in edge-cloud collaborative environment：a deep reinforcement learning approach[C]//Proc of the 8th IEEE International Conference on Cyber Security and Cloud Computing/the 7th IEEE International Confe-rence on Edge Computing and Scalable Cloud.Piscataway，NJ：IEEE Press，2021：24－29.

[14]Zou Guobing，Qin Zhen，Deng Shuiguang，et al.Towards the optimality of service instance selection in mobile edge computing[J].Know-ledge-Based Systems，2021，217：article ID 106831.

[15]Wu Hongyue，Deng Shuiguang，Li Wei，et al.Mobility-aware service selection in mobile edge computing systems[C]//Proc of IEEE International Conference on Web Services.Piscataway，NJ：IEEE Press，2019：201－208.

[16]Zhao Jiaming，Wu Wenjun，Guo Xiao，et al.Access selection conside-ring mobile edge computing in ultra dense network[C]//Proc of the 3rd IEEE International Conference on Computer and Communications.Piscataway，NJ：IEEE Press，2017：433－437.

[17]Jiao Licheng，Wang Lei.A novel genetic algorithm based on immunity[J].IEEE Trans on Systems，Man，and Cybernetics-part A：Systems and Humans，2000，30（5）：552－561.

[18]Bettstetter C，Hartenstein H，Pérez-Costa X.Stochastic properties of the random waypoint mobility model[J].Wireless Networks，2004，10（5）：555－567.