面向邊緣計算的服務(wù)解耦與部署策略

李麗穎 張潤澤 魏同權(quán)

1（華東師范大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院 上海 200062）

2（南京理工大學(xué)計算機(jī)科學(xué)與工程學(xué)院 南京 210094）

隨著物聯(lián)網(wǎng)和5G 無線網(wǎng)絡(luò)的快速發(fā)展，萬物互聯(lián)已經(jīng)成為一種趨勢，促進(jìn)了各個領(lǐng)域新興應(yīng)用的發(fā)展[1].與此相對應(yīng)的是邊緣設(shè)備及其產(chǎn)生的數(shù)據(jù)量迅速增長.麥肯錫全球研究報告稱，預(yù)計到2025 年，物聯(lián)網(wǎng)連接的設(shè)備將超過300 億個，相關(guān)的數(shù)據(jù)量也從2016 年的96 ZB/月增長到了2021 年的278 ZB/月[2].這些海量而多樣的設(shè)備和數(shù)據(jù)連接物與物、物與人，最終實現(xiàn)“萬物互聯(lián)”[3].

關(guān)鍵技術(shù)的蓬勃發(fā)展也使得分布式的用戶請求數(shù)量迅速增加.然而，當(dāng)前的服務(wù)模式大多是將應(yīng)用程序的功能封裝為獨立的單元并將該單元部署在云服務(wù)器上.分布式的用戶向云端服務(wù)器發(fā)送服務(wù)請求，云端服務(wù)器運行相應(yīng)的應(yīng)用程序并向用戶反饋結(jié)果.然而，這種集中式的服務(wù)往往會帶來巨大的服務(wù)響應(yīng)延遲和帶寬開銷，降低服務(wù)質(zhì)量（quality of service,QoS）[4].

解決上述問題的一種有效的方法是將這種集中式服務(wù)解耦為子服務(wù).例如，Auer 等人[5]提出了一個基于問卷調(diào)查的評估框架，他們通過問卷調(diào)查歸納出將集中式服務(wù)解耦并部署到子服務(wù)架構(gòu)上的重要指標(biāo)，并根據(jù)問卷調(diào)查的結(jié)果來推斷具體的集中式服務(wù)具體如何解耦并部署到子服務(wù)架構(gòu)中.然而，這種基于問卷調(diào)查的解耦方案受限于問卷設(shè)計，通常都比較主觀，其效果和普適性較差，并且會耗費大量的人力和時間成本.為了解決上述問題，Arisholm 等人[6]提出了動態(tài)耦合度的概念用于衡量應(yīng)用程序在實際運行時的相關(guān)程度.Poshyvanyk 等人[7]提出了一種用于衡量程序的類之間的標(biāo)識符和相關(guān)性的耦合度.然而，這些現(xiàn)有的工作忽略了服務(wù)自身的特性（如服務(wù)的字段等），因而效果不佳.

除了對集中式服務(wù)進(jìn)行解耦，將解耦后的子服務(wù)部署到邊緣計算架構(gòu)中也是一個能夠有效降低時延的解決方案.邊緣計算利用終端設(shè)備的計算能力，可以顯著減少傳輸?shù)皆品?wù)器的數(shù)據(jù)量和服務(wù)請求的響應(yīng)時間[8-9].然而，由于邊緣設(shè)備的存儲空間和計算能力有限，如何將解耦后的子服務(wù)部署在邊緣服務(wù)器上是亟待解決的問題.現(xiàn)有關(guān)于邊緣計算架構(gòu)下的服務(wù)部署的相關(guān)工作如文獻(xiàn)[10-12]，并沒有同時考慮邊緣服務(wù)器本身的異構(gòu)性和服務(wù)器之間的負(fù)載均衡，并且脆弱的邊緣設(shè)備也帶來了嚴(yán)重的安全性問題.首先，對于大多數(shù)邊緣計算相關(guān)技術(shù)（如無線網(wǎng)絡(luò)和分布式系統(tǒng)等），不僅需要保護(hù)其中的組件免受網(wǎng)絡(luò)攻擊，還需要協(xié)調(diào)不同等級的安全機(jī)制.其次，對邊緣計算而言，在異構(gòu)的系統(tǒng)下提供穩(wěn)定的連接和高可訪問性是提供高質(zhì)量服務(wù)的基礎(chǔ)[13].因此，邊緣服務(wù)器在保證網(wǎng)絡(luò)安全的條件下及時響應(yīng)用戶的服務(wù)請求就顯得尤為重要.

移動設(shè)備數(shù)量的爆炸式增長推動了傳統(tǒng)的邊緣計算向移動邊緣計算（mobile edge computing,MEC）的方向發(fā)展.移動邊緣計算[14]將云端的計算能力推向了邊緣端，即在移動設(shè)備和無線接入網(wǎng)的邊緣部署計算平臺，使得移動設(shè)備可以就近使用所需服務(wù)和云端計算功能[15].盡管移動邊緣計算可以顯著地降低端到端的延遲，但是設(shè)備移動的不可預(yù)測性給部署服務(wù)帶來了新的挑戰(zhàn)[16].Wang 等人[17]設(shè)計了一種服務(wù)遷移策略來解決順序決策服務(wù)的部署問題.Taleb 等人[18]基于馬爾可夫鏈模型提出了一種面向移動設(shè)備的邊緣計算部署策略.然而，文獻(xiàn)[14-18]所述工作都沒有考慮到移動邊緣計算服務(wù)部署的成本問題.

本文提出了一種2 階段的服務(wù)質(zhì)量優(yōu)化方案以解決移動邊緣計算架構(gòu)下的服務(wù)部署問題.在第1 階段，本文考慮了服務(wù)的解耦和邊緣服務(wù)器的負(fù)載均衡問題，對服務(wù)部署問題進(jìn)行建模，提出了一種集中式服務(wù)的實時解耦方案，并且設(shè)計了一種靜態(tài)部署策略；在第2 階段，本文考慮了邊緣設(shè)備的移動性，設(shè)計了一種設(shè)備移動感知的服務(wù)部署策略，優(yōu)化了移動邊緣計算架構(gòu)下的服務(wù)質(zhì)量.具體來說，本文的主要貢獻(xiàn)包括3 個方面：

1）在考慮邊緣服務(wù)器負(fù)載均衡的前提下提出了一種面向集中式服務(wù)的解耦策略，并設(shè)計了一種基于分解的多目標(biāo)進(jìn)化算法的服務(wù)部署策略以優(yōu)化服務(wù)質(zhì)量.該策略能夠在保證服務(wù)器負(fù)載均衡和安全性的前提下，優(yōu)化服務(wù)請求的響應(yīng)時間.

2）進(jìn)一步考慮了邊緣設(shè)備的移動性，提出了一種動態(tài)服務(wù)部署策略.首先，為了適應(yīng)移動的服務(wù)請求，建模動態(tài)用戶的服務(wù)部署問題.然后，提出了一種設(shè)備移動感知的實時服務(wù)放置策略以進(jìn)一步優(yōu)化服務(wù)請求的響應(yīng)時間.

3）為了驗證所提方法的有效性，本文進(jìn)行了一系列的仿真實驗.實驗結(jié)果表明，與多種基準(zhǔn)方法相比，在保證系統(tǒng)安全以及服務(wù)器負(fù)載均衡的前提下，本文所提出的面向集中式服務(wù)靜態(tài)部署策略能夠服務(wù)請求的響應(yīng)時間降低36%，所提出的動態(tài)部署策略能進(jìn)一步降低13%的服務(wù)響應(yīng)時間.

1 系統(tǒng)模型

本節(jié)主要介紹本文主要用到的相關(guān)模型，包括系統(tǒng)架構(gòu)模型、服務(wù)模型、耦合度模型和傳輸成本模型.

1.1 系統(tǒng)架構(gòu)模型

不失一般性，本文采用常見的移動邊緣計算系統(tǒng)架構(gòu).假設(shè)該架構(gòu)硬件上包含1 個云服務(wù)器、Nes個邊緣服務(wù)器、Nbs個基站和Ntd個終端設(shè)備.基站之間通過有線連接，終端設(shè)備與基站之間通過無線連接，終端具有可移動性.邊緣服務(wù)器的集合用ES={ES1,ES2,…,}表示，其中ESi（1≤i≤Nes）為第i個邊緣服務(wù)器.基站的集合用Vbs表示，終端設(shè)備的集合用Vt表示.系統(tǒng)架構(gòu)圖如圖1 所示，其拓?fù)潢P(guān)系可以用無向圖G={V,E}表示，其中V=Vbs∪Vtd，E=Ewire∪Ewireless，其中Ewire為2 基站之間所有的有線連接組成的集合，Ewireless為所有基站和終端設(shè)備之間的無線連接所組成的集合.

Fig.1 System architecture圖 1 系統(tǒng)架構(gòu)

在云端服務(wù)器上維護(hù)完整的集中式服務(wù)，并且負(fù)責(zé)將集中式服務(wù)解耦為Nser個子服務(wù)并且將這些子服務(wù)部署/卸載到Nes個邊緣服務(wù)器上.每個邊緣服務(wù)器通過使用子服務(wù)來快速響應(yīng)終端設(shè)備的服務(wù)請求，這些邊緣服務(wù)器在計算能力和存儲空間上是異構(gòu)的.由于基站數(shù)量的不斷增加，在所有的基站上部署邊緣服務(wù)器會帶來巨大的成本，因此并不是所有的基站附近都會部署邊緣服務(wù)器，即Nes≤Nbs.在本文中，使用文獻(xiàn)[19]所提出的方法將Nes個邊緣服務(wù)器部署在Nbs個基站上.基站會負(fù)責(zé)接收鄰近終端設(shè)備的服務(wù)請求，這個基站被稱為這些終端設(shè)備的本地基站，對應(yīng)的邊緣服務(wù)器被稱為這些終端設(shè)備的本地邊緣服務(wù)器.如果終端設(shè)備的本地基站部署了邊緣服務(wù)器，且終端設(shè)備的服務(wù)請求可以在本地邊緣服務(wù)器上處理，則請求將直接在本地邊緣服務(wù)器上處理，否則這個服務(wù)請求將被轉(zhuǎn)發(fā)到可以處理該請求的邊緣服務(wù)器上，結(jié)果會被返回給終端設(shè)備.

1.2 服務(wù)及耦合度模型

假設(shè)云服務(wù)器維護(hù)Nser個服務(wù)，服務(wù)集合S={S1,S2,…,}，每個服務(wù)Sj（1≤j≤Nser）包含Mj個字段.定義一個Mj×Nes大小的矩陣Ij來表示服務(wù)中各個字段的被訂閱情況：

對于邊緣服務(wù)器ESi（1≤i≤Nes），定義一個對服務(wù)Sj中字段m的影響因子：

其中ωdel，ωadd，ωupd分別為刪除、增加和更新字段m對服務(wù)Sj影響的權(quán)重因子.需要注意的是，這3 種對服務(wù)中字段的操作都是原子操作.也就是說，在每次對字段的操作中，有且只有上述3 種操作的其中一種.服務(wù)的耦合度用于判定服務(wù)是否需要被解耦的依據(jù).將服務(wù)Sj在邊緣服務(wù)器ESi上的耦合度定義為

因此，服務(wù)Sj的耦合度為

從式（6）（7）的定義可以看出，一個服務(wù)的耦合度越高，其中的字段操作越頻繁.如果不對這種高耦合度的服務(wù)進(jìn)行解耦，產(chǎn)生的傳輸成本就會越高.因此，本文的方案傾向于解耦對高耦合度的服務(wù).

1.3 安全性模型

本文定義了一個包含了K種不同類型的安全服務(wù)的集合，該集合用A={A1,A2,…,AK}表示.假設(shè)seci（1≤i≤K）為服務(wù)Sj使用安全服務(wù)Ai后的安全等級.T（Ai,Sj）為服務(wù)Sj使用安全服務(wù)Ai時的開銷：

其中Ci為常數(shù)系數(shù)，取決于具體的安全服務(wù)算法.本文采用指數(shù)模型[20]計算服務(wù)Sj采用安全服務(wù)Ai失敗的概率為

整個系統(tǒng)的安全性可以被定義為各個服務(wù)的安全性的乘積：

因此，為所有服務(wù)提供安全服務(wù)的總耗時為

其中Cost(S j)為傳輸服務(wù)S j所帶來的開銷，在1.4 節(jié)詳細(xì)定義了該值.

1.4 傳輸成本模型

為了將服務(wù)從云服務(wù)器卸載到邊緣服務(wù)器，一般會將服務(wù)封裝到Internet 協(xié)議數(shù)據(jù)包中.因此，除了要考慮服務(wù)本身的大小，還需要考慮一些額外信息（如頭部信息等）所產(chǎn)生的開銷.假設(shè)這類開銷用Costhead表示，則傳輸服務(wù)S j所帶來的開銷被計算為

其中，Cost(m)為服務(wù)S j中第m個字段的大小.

在傳輸成本方面，假設(shè)設(shè)備通過無線連接與服務(wù)器進(jìn)行通信，服務(wù)器之間通過電纜或者光纖的有線連接方式傳輸信息.2 個邊緣服務(wù)器ESi和ES j(1 ≤i≤Nes,1 ≤j≤Nes)之間的傳輸時延為

其中Wi,j和Bi,j分別為邊緣服務(wù)器ESi和ES j之間需要傳輸?shù)臄?shù)據(jù)量和帶寬大小.而這2 個服務(wù)器之間的傳播時延為

其中，Di,j為ESi和ES j之間根據(jù)路由的物理鏈路距離，θ為電纜/光纜中電信號的傳播速率.因此，可以定義ESi和ES j之間的有線總時延：

設(shè)備i與服務(wù)器ES j之間的無線傳輸時延為

2 集中式服務(wù)的實時解耦方案以及部署策略

本文所提方案用于解決移動邊緣計算架構(gòu)下的服務(wù)安全部署問題.本節(jié)主要介紹所提方法的第1 階段.具體來說，在這個階段，我們考慮了服務(wù)的安全性和邊緣服務(wù)器的負(fù)載均衡問題，對服務(wù)部署問題進(jìn)行建模，提出了一種集中式服務(wù)的實時解耦方案以及部署策略.

2.1 基于K-Means 算法的服務(wù)實時解耦

根據(jù)1.2 節(jié)對服務(wù)耦合度的定義可知，如果一個服務(wù)的耦合度越高，其中的字段被進(jìn)行增加、修改和刪除的操作越頻繁.如果不對這種高耦合度的服務(wù)進(jìn)行解耦，會產(chǎn)生較高的傳輸成本.因此，本文所提方案僅對高耦合度的服務(wù)進(jìn)行解耦.具體來說，定義一個服務(wù)的耦合度閾值Fth.如果服務(wù)Sj的耦合度FSj＞Fth，則Sj被認(rèn)為是高耦合度服務(wù)，需要被解耦；反之，則認(rèn)為服務(wù)Sj為低耦合度服務(wù)，不需要被解耦.

在對服務(wù)進(jìn)行耦合度分類后，采用文獻(xiàn)[22]中所提出的算法ISODATA（iterative self-organizing data analysis techniques algorithm）,對服務(wù)進(jìn)行初始解耦.這種解耦方法原理簡單且易于實現(xiàn)，然而，該解耦方式本質(zhì)上是一種離線的解耦，不適合增加、刪除和修改操作頻繁的移動感知應(yīng)用場景，其對應(yīng)的響應(yīng)時延也較長.因此，本文提出了一種基于加權(quán)K-Means算法的服務(wù)解耦方案，該方案可以實現(xiàn)對服務(wù)的實時解耦.

K-Means 是一種迭代求解的聚類分析算法，是基于歐氏距離的聚類算法.K-Means 算法認(rèn)為2 個目標(biāo)的距離越近，相似度越大.具體來說，該算法首先會隨機(jī)選擇初始化后的K個樣本作為初始聚類中心這些聚類中心被表示為{C1,C2,…,CK}.對于每個待聚，類的樣本，首先計算該樣本和每一個聚類中心的歐氏距離，然后將樣本分類到與其距離最小的聚類中心對應(yīng)的類別，最后算出每個類別的平均值以更新聚類中心.

我們只對高耦合度的服務(wù)進(jìn)行解耦.具體來說，定義了一個耦合度閾值Fth，對于每一個服務(wù)S j，采用式（7）計算其對應(yīng)的耦合度FSj.若FSj＞Fth，則服務(wù)Sj為高耦合度服務(wù)，需要采用解耦算法進(jìn)行解耦；反之，服務(wù)Sj為低耦合度服務(wù)，不需要被解耦.提出的基于加權(quán)K-Means 算法的實時服務(wù)解耦方案將ISODATA產(chǎn)生的結(jié)果作為初始解，實時地根據(jù)對服務(wù)中字段的操作（增加、刪除和更新），不斷地實時更新每一個服務(wù)的解耦方案，在考慮邊緣服務(wù)器節(jié)點負(fù)載均衡的條件下優(yōu)化服務(wù)請求的響應(yīng)時間.

所提出的基于K-Means 的服務(wù)解耦算法對應(yīng)的偽代碼如算法1 所示.

算法1.基于K-Means 的服務(wù)解耦算法.

算法1 以耦合度閾值Fth和 服務(wù)集合S={S1,S2,…,SNser}作為輸入，并輸出對每一個服務(wù)的解耦方案.算法1 首先初始化需要被解耦的服務(wù)的集合為空集，該集合用Ω表示；然后將聚類中心的個數(shù)K設(shè)為預(yù)計解耦得到的子服務(wù)的個數(shù)Nsub（算法1 的行①）.對于每一個服務(wù)Sj，首先將其耦合度FSj初始化為0，然后采用式（7）計算服務(wù)Sj的耦合度（算法1 的行③④）.如果服務(wù)Sj的耦合度大于耦合度閾值，則認(rèn)為Sj為高耦合度服務(wù)，此時需要對服務(wù)進(jìn)行解耦，因此將Sj加入集合Ω，并采用ISODATA 算法[22]得到初始解耦方案和K個聚類中心的初始取值；否則認(rèn)為Sj為低耦合度服務(wù)，不需要對其進(jìn)行解耦（算法1 的行②～?）.對集合Ω中每一個服務(wù)Sj，如果此時需要增加其中的字段，則算法1 首先計算增加的字段與此時每一個聚類中心之間的歐氏距離，然后將增加的字段加入與之最近的對應(yīng)的子服務(wù)，并根據(jù)式（20）更新（算法1 的行?～?）.如果此時需要刪除/更新服務(wù)Sj中的字段，則從對應(yīng)的子服務(wù)中刪除/更新相應(yīng)字段，并根據(jù)式（20）更新（算法1 的行?～?）.需要注意的是，如果相應(yīng)的操作是更新，則式（20）中＝0.也就是說，此時相應(yīng)子服務(wù)中的字段數(shù)量不會改變.迭代結(jié)束后，算法1 會返回對每一個服務(wù)的解耦方案.

2.2 基于MOEA/D 的服務(wù)靜態(tài)放置策略

在對服務(wù)進(jìn)行解耦之后，我們設(shè)計了一種靜態(tài)的服務(wù)部署策略將解耦后的子服務(wù)部署到邊緣服務(wù)器上以優(yōu)化服務(wù)質(zhì)量.具體來說，首先將子服務(wù)的部署問題建模為一個多目標(biāo)優(yōu)化問題（multi-objective optimization problem,MOP），然后采用基于分解的多目標(biāo)進(jìn)化算法（multi-objective evolutionary algorithm based on decomposition,MOEA/D）去解決該問題，以保證在服務(wù)器負(fù)載均衡和安全性的前提下，優(yōu)化服務(wù)請求的響應(yīng)時間.

結(jié)合第1 節(jié)的建模，可以將本文所關(guān)注的問題建模為一個多目標(biāo)優(yōu)化問題，該多目標(biāo)優(yōu)化問題表示為

其中FM:Y→RM由M個實值函數(shù)組成，Y為決策空間，RM為目標(biāo)空間.為了便于表述，給出2 個定義.

定義1.如果存在2 個向量u,v∈RM，任意i=1,2,…,M，都滿足ui＜vi，則稱u支配v.

MOEA/D 算法將式（22）中的目標(biāo)函數(shù)分解為M個實值函數(shù)的優(yōu)化問題，然后通過解決這M個實值函數(shù)的優(yōu)化問題得到式（22）中的帕累托集合.使用基于切比雪夫的分解算法來解決多目標(biāo)優(yōu)化問題，具體來說，首先定義目標(biāo)優(yōu)化問題：

基于切比雪夫的MOEA/D 算法，在每一輪迭代中更新4 個內(nèi)容：

1）分解成的子問題數(shù)量M以及子問題i的當(dāng)前解xi∈Y；

《關(guān)于推動傳統(tǒng)出版和新興出版融合發(fā)展的指導(dǎo)意見》（新廣發(fā)〔2015〕32號）的發(fā)布，標(biāo)志著國家開始重視出版融合發(fā)展，支持力度逐年加大，積極鼓勵傳統(tǒng)期刊企業(yè)試水，探索出版媒體融合新模式。2017年，隨著國家政策的大力倡導(dǎo)，以及出版單位的積極努力，開拓融合出版發(fā)展的主體應(yīng)運而生，無論是國家認(rèn)證的融合發(fā)展實驗室，還是各主體自身的融合發(fā)展研發(fā)部門，甚至是企業(yè)的單個融合發(fā)展項目，都紛紛涌現(xiàn)出來。互聯(lián)網(wǎng)數(shù)字出版模式已基本形成，并培養(yǎng)出大量極具粘性的用戶群（具備互聯(lián)網(wǎng)使用習(xí)慣）。

2）定義FVi=FM(xi)，?i=1,2,…,M；

3）z={z1,z2,…,zM}，其中zi是到目前函數(shù)fi(x)的最優(yōu)值；

4）在搜索過程中存儲的非支配解的集合，該集合被表示為EP.

本文提出了基于MOEA/D 的集中式服務(wù)放置算法來探索集中式服務(wù)配置到邊緣服務(wù)器的解決策略.具體來說，隨機(jī)選擇交叉算子和變異算子作為本文的遺傳算子：

1）交叉算子.本文所關(guān)注的多目標(biāo)優(yōu)化問題為，在保證服務(wù)器負(fù)載均衡和安全性的前提下，將云服務(wù)器維護(hù)Nser個服務(wù)中每一個服務(wù)對應(yīng)的Nsub個子服務(wù)部署至Nes個邊緣服務(wù)器上，以優(yōu)化服務(wù)請求的響應(yīng)時間.因此，該問題的解空間為[0,Nes-1]Nsub，并在這個解空間內(nèi)隨機(jī)生成一個整數(shù)作為交叉算子.為了便于理解，以子服務(wù)個數(shù)Nsub=7、邊緣服務(wù)器個數(shù)Nes=3 的情況為例.假設(shè)隨機(jī)生成的交叉算子為3，即從位置3 開始進(jìn)行交叉（子服務(wù)編號從0 開始），則交叉情況如圖2 所示.

2）變異算子.本文使用基于正態(tài)分布的隨機(jī)數(shù)生成方式進(jìn)行變異操作.具體來說，對于染色體i的每個位置，先以Pmutation的概率判斷是否會發(fā)生變異，若發(fā)生變異，則在該位置加上一個正態(tài)分布的隨機(jī)數(shù) τ，并將結(jié)果調(diào)整到限定范圍內(nèi)，即

Fig.2 An example of chromosome crossover process圖 2 染色體交叉過程示例

所提出的基于MOEA/D 的子服務(wù)放置算法的偽代碼如算法2 所示.

3 設(shè)備移動感知的動態(tài)服務(wù)部署策略

現(xiàn)實生活中，越來越多的終端設(shè)備會隨著用戶一邊移動一邊進(jìn)行服務(wù)請求.為了進(jìn)一步考慮邊緣設(shè)備的移動性，本文提出了一種設(shè)備移動感知的動態(tài)服務(wù)部署策略.首先，為了適應(yīng)移動的服務(wù)請求，建模了服務(wù)遷移成本隊列解耦動態(tài)用戶的服務(wù)部署問題；然后，提出了一種基于響應(yīng)時間優(yōu)先的實時服務(wù)放置策略.

圖3 展示了用戶移動情況下，在移動邊緣計算架構(gòu)下一個用戶移動軌跡的示例[23].在該架構(gòu)下，考慮網(wǎng)絡(luò)運營商設(shè)置了Nmes個MEC 節(jié)點來服務(wù)Nuser個移動用戶.每個MEC 節(jié)點都通過高速局域網(wǎng)與鄰近的基站或是無線接入點相連接.每個用戶攜帶一個移動設(shè)備，在移動設(shè)備上運行的應(yīng)用程序的服務(wù)配置文件將分配到給定的邊緣服務(wù)器的專用虛擬機(jī)[24]或容器[25].將系統(tǒng)的運行均分成若干時隙，其時間線被離散成若干時間幀t∈{0,1,…,T}.在每個離散時隙，每個移動用戶向本地MEC 節(jié)點發(fā)送服務(wù)請求，由軟件定義網(wǎng)絡(luò)控制器（SDN 控制器）收集所有用戶的服務(wù)請求信息并根據(jù)當(dāng)前全局系統(tǒng)確定最佳MEC 節(jié)點為相應(yīng)用戶提供服務(wù).

Fig.3 An example of a user's movement trajectory under the mobile edge computing architecture圖 3 在移動邊緣計算架構(gòu)下用戶的移動軌跡示例

用戶的移動通常是不規(guī)律的，為了使用戶可以獲得高質(zhì)量的QoS 服務(wù)，每個用戶的服務(wù)配置文件應(yīng)該隨著用戶移動性動態(tài)遷移.定義xi,j(t) 表示在時隙t用戶j的服務(wù)配置文件是否部署在MEC 節(jié)點i上，如果是，則xi,j(t)=1，否則xi,j(t)=0.

其中，Mi,j為用戶i在MEC 節(jié)點j上的服務(wù)配置文件的大小，Pj為節(jié)點j的計算能力.

因此，在時隙t時所有用戶的服務(wù)遷移成本Costtotal(t)計算為

定義隊列QL(t)表示從零時隙到時隙t時累計超出給定的長期平均期望預(yù)算的度量.由式（26）（29）可得，QL(t+1)可由時隙t時的QL(t)、時隙t時的服務(wù)遷移成本以及長期平均期望預(yù)算推導(dǎo)得出：

為了保證遷移成本的平均值不超過長期平均期望預(yù)算，則QL(t)的長期平均值應(yīng)趨向于0.因此，QL(t+1)≥QL(t)+Costtotal(t)-Costavg(t)成立.定義二次李雅普諾夫函數(shù)為

其中 α 和 β為常數(shù).

本文所提出的設(shè)備移動感知的動態(tài)服務(wù)部署策略的偽代碼如算法3 所示.

算法3.設(shè)備移動感知的動態(tài)服務(wù)部署策略.

算法3 以狀態(tài)空間d(t)和最大迭代輪次Tmax作為輸入，并輸出最優(yōu)服務(wù)放置策略d*.算法3 首先初始化迭代輪次為0，并隨機(jī)生成一個服務(wù)部署策略d，該部署策略d將每個服務(wù)配置文件隨機(jī)分配到Nmes個MEC 節(jié)點上（算法3 的行①）.對于每一次迭代，首先隨機(jī)選擇一個用戶的服務(wù)配置文件，對于在此時服務(wù)放置策略的狀態(tài)空間d(t)中除了d以外的每一個部署策略d′，使用式（26）計算成本函數(shù)（算法3 的行⑤～⑦）.接著算法3 根據(jù)式（29）計算得到的概率選擇一種放置策略并通過將服務(wù)放置到新的MEC 節(jié)點來更新現(xiàn)有的服務(wù)放置策略（算法3 的行⑧～⑩）.設(shè)使得Costtotal(t)最小的服務(wù)放置策略為d*，該策略d*即為最佳放置策略，d*會在每一輪迭代中被更新（算法3 的行⑩）.最后，算法3 會返回迭代結(jié)束后得到的最佳服務(wù)放置策略（算法3 的行?）.

4 實 驗

本文在2 個數(shù)據(jù)集上進(jìn)行實驗以驗證所提方案的有效性.具體來說，首先介紹了相關(guān)的實驗設(shè)置；然后以傳輸開銷為評價標(biāo)準(zhǔn)來衡量所提的基于KMeans 的服務(wù)解耦算法的有效性；接著，在多個方面將所提的基于MOEA/D 的服務(wù)靜態(tài)放置策略與3 種基準(zhǔn)算法相比較，以驗證所提的靜態(tài)放置策略的有效性；最后，在多個方面將所提的設(shè)備移動感知的動態(tài)服務(wù)部署策略與3 種基準(zhǔn)方法相比較，以驗證所提的動態(tài)服務(wù)部署策略的有效性.

4.1 實驗設(shè)置

本文的實驗環(huán)境使用Windows 10 操作系統(tǒng)，8GB 內(nèi) 存，AMD Ryzen 5 4500U @ 2.38GHz 處理器，并使用Python3.7 的運行環(huán)境.

在數(shù)據(jù)集方面，本文采用2 個數(shù)據(jù)集進(jìn)行實驗.第1 個數(shù)據(jù)集是1990 年美國人口普查公開數(shù)據(jù)集（以下簡稱數(shù)據(jù)集1）[28]，該數(shù)據(jù)集包含了大約20 萬條1990 年美國人口的普查結(jié)果，其包含年齡等68 種基本特征.我們將該數(shù)據(jù)集分為10 個服務(wù)，并由68個邊緣設(shè)備對這些服務(wù)中的字段進(jìn)行訂閱.第2 個數(shù)據(jù)集是由上海交易中心信息技術(shù)有限公司提供的真實數(shù)據(jù)集（以下簡稱數(shù)據(jù)集2）.該數(shù)據(jù)集提供了上海交易中心信息技術(shù)有限公司真實的20 個設(shè)備對15個服務(wù)對應(yīng)的所有字段的訂閱情況.我們對每一個服務(wù)的耦合度進(jìn)行計算，并采用所提出的實時解耦策略對這2 個數(shù)據(jù)集中的服務(wù)進(jìn)行解耦.刪除、增加和更新這3 個指示變量，均設(shè)為1.為了比較離線算法與在線算法節(jié)省的帶寬，將頭部信息的大小設(shè)置為10b，并假設(shè)每條數(shù)據(jù)為200b.

在開銷方面，本文所提出的策略所帶來的開銷分為2 個部分：算法的運行時間和因傳輸解耦后的服務(wù)所帶來的傳輸開銷.因此，本文在4.2～4.4 節(jié)對這2 個方面的開銷進(jìn)行了詳細(xì)的分析和對比.

4.2 基于K-Means 的服務(wù)實時解耦策略驗證

為了驗證基于K-Means 的服務(wù)實時解耦策略，本文對比了解耦前后的傳輸開銷.數(shù)據(jù)集1 和數(shù)據(jù)集2的解耦前后傳輸開銷分別如圖4 和圖5 所示.從圖4可以看出，編號1 在解耦后的所有服務(wù)的通信開銷平均減少了29.04%；對編號3 的服務(wù)解耦效果最為明顯，其通信開銷減少了44.20%.從圖5 可以看出，與解耦前相比，所有服務(wù)在解耦后的傳輸開銷平均減少了24.71%，其中傳輸開銷減少可高達(dá)29.92%.這是因為解耦后，邊緣服務(wù)器減少了大量無關(guān)子服務(wù)的訂閱數(shù)，因此減少了大量不必要的通信開銷.只有少數(shù)服務(wù)（如編號8 的服務(wù)）在解耦前后通信開銷變化不大.這是因為這些服務(wù)解耦后邊緣服務(wù)器仍然訂閱了大量的子服務(wù).如果某服務(wù)訂閱了解耦后服務(wù)集合的所有子服務(wù)，會由于解耦增加的額外成本導(dǎo)致解耦后的字段開銷大于解耦前的字段開銷.在實際應(yīng)用中，可以考慮不對該服務(wù)進(jìn)行解耦.圖6 對比了在數(shù)據(jù)集2 上增加字段時ISODATA[22]和所提出的基于K-Means 的實時解耦策略的運行時間.在不改變劃分結(jié)果的條件下，在線算法的運行時間遠(yuǎn)小于離線算法的運行時間.在數(shù)據(jù)集2 的10 組數(shù)據(jù)中，在線算法的算法運行時間平均減少了78.14%，最多減少高達(dá)80.35%.這是因為在線算法只需要遍歷1 遍數(shù)據(jù)即可完成對整個服務(wù)的劃分，而離線算法通常要迭代很多輪才能收斂得到最終的劃分結(jié)果.

Fig.4 Comparison of the transmission overhead for dataset 1 before and after decoupling圖 4 對比數(shù)據(jù)集1 解耦前后的傳輸開銷

Fig.5 Comparison of transmission overhead for dataset 2 before and after decoupling圖 5 對比數(shù)據(jù)集2 解耦前后的傳輸開銷

Fig.6 Computation time of ISODATA and the proposed strategy when conducting add operation on dataset 2圖 6 對比在數(shù)據(jù)集2 上增加字段時ISODATA 和所提策略的運行時間

圖7 展示了字段個數(shù)分別為2 萬、4 萬、8 萬以及12 萬時ISODATA[22]和所提出的基于K-Means 的實時解耦策略的運行時間.相比于ISODATA 算法，4種不同字段個數(shù)的在線算法的算法運行時間分別減少了78.95%，85.37%，86.06%，85.35%.由于算法的時間復(fù)雜度與字段個數(shù)呈正相關(guān)，字段個數(shù)越大，在線算法節(jié)省的時間也就越多.因此，我們認(rèn)為，所提出的基于K-Means 的實時解耦策略比較適合服務(wù)體量較大也就是字段個數(shù)較大的情況.在這種情況下，所提算法能夠節(jié)約的處理時間較多，效果更好.但是當(dāng)服務(wù)較小或子服務(wù)耦合度較低時，所提方法反而可能會導(dǎo)致較大的開銷.這是因為所提方法需要傳輸解耦后的服務(wù)，而這會帶來較大的傳輸延遲.

圖8 展示了數(shù)據(jù)集2 在刪除字段的場景ISODATA算法和所提的基于K-Means 的實時解耦策略的運行時間比較.在解耦結(jié)果一致的條件下，所提實時解耦算法的運行時間遠(yuǎn)小于ISODATA 算法的運行時間.具體來說，在數(shù)據(jù)集2 上所提出的實時解耦算法的運行時間平均減少了73.02%，最多減少高達(dá)75.80%.

4.3 基于MOEA/D 的服務(wù)靜態(tài)放置策略驗證

Fig.7 Computation time of ISODATA and the proposed strategy under different numbers of adding segments圖 7 當(dāng)增加字段量不同時ISODATA 和所提策略的運行時間

Fig.8 Computation time of ISODATA and the proposed strategy when conducting delete operation on dataset 2圖 8 對比在數(shù)據(jù)集2 上刪除字段時，ISODATA 和所提策略的運行時間

為了驗證所提的基于MOEA/D 的集中式服務(wù)靜態(tài)放置算法的有效性，本實驗比較并分析了基于MOEA/D 策略（本文算法）和3 種基準(zhǔn)算法的集中式服務(wù)靜態(tài)放置結(jié)果，其中3 種基準(zhǔn)算法分別是基于隨機(jī)的算法（RAND）、遺傳算法（GA）[29]和粒子群算法（PSO）[30].這3 種基準(zhǔn)算法的原理為：

1）RAND.隨機(jī)選取每個服務(wù)部署的邊緣節(jié)點放置服務(wù).

2）GA.遺傳算法基于染色體自然進(jìn)化，對染色體編碼后，使用交叉和變異生成新的染色體，并基于適應(yīng)度函數(shù)評估染色體的質(zhì)量，最后根據(jù)最優(yōu)染色體得到最優(yōu)解以放置服務(wù).

3）PSO.粒子群優(yōu)化是一種使用粒子模擬一群尋找食物的鳥的算法.具有“速度”和“位置”的粒子是目標(biāo)函數(shù)空間中的搜索個體，算法會基于所有粒子的歷史最優(yōu)位置調(diào)整速度.最后將所有粒子當(dāng)前位置的最優(yōu)解視為全局最優(yōu)解.

圖9 對比了當(dāng)設(shè)備數(shù)量分別為3，5，10 時，使用本文算法、PSO、GA、RAND 得到的平均服務(wù)響應(yīng)時間.服務(wù)響應(yīng)時間是由本文算法運行時間和終端設(shè)備請求服務(wù)的響應(yīng)時間組成，終端設(shè)備的響應(yīng)時間由服務(wù)請求的通信時延、服務(wù)加密消耗的時間以及服務(wù)在邊緣服務(wù)器運行所需的時間組成.由圖9 可以看出，與PSO,GA，RAND 這3 種基準(zhǔn)算法相比，本文算法分別平均優(yōu)化了9.23%，10.33%，15.07%，最高優(yōu)化分別為24.89%，25.94%，35.55%.這是因為本文算法的運行時間以及服務(wù)放置策略均優(yōu)于這3 種基準(zhǔn)算法.

Fig.9 Average service response time of the 4 algorithms under different numbers of devices圖 9 不同設(shè)備數(shù)量下對比4 種算法的平均服務(wù)響應(yīng)時間

圖10 展示了當(dāng)設(shè)備數(shù)量分別為3，5，10 時，使用本文算法、PSO、GA、RAND 算法得到的負(fù)載均衡平均優(yōu)化率.將本文算法的負(fù)載均衡平均優(yōu)化率設(shè)置為1，與PSO,GA，RAND 這3 種基準(zhǔn)算法相比，本文算法分別平均優(yōu)化了3.28%，29.15%，66.97%，最高優(yōu)化分別為89.67%，87.91%，96.10%.雖然當(dāng)邊緣服務(wù)器數(shù)量為5 時，PSO 算法的負(fù)載均衡平均優(yōu)化率小于1，然而此時其響應(yīng)時間比本文算法高10.18%.由于PSO 和GA 難以找到優(yōu)化問題的全局最優(yōu)解，因此使用PSO 和GA 算法得到的負(fù)載均衡平均優(yōu)化率不如本文算法.因此，由圖10 可以看出，本文所提的基于MOEA/D 的服務(wù)靜態(tài)放置策略適合被應(yīng)用于設(shè)備數(shù)量較多、需要進(jìn)行負(fù)載均衡的場景中.此時，本文算法相較于基準(zhǔn)算法，能夠取得更好的優(yōu)化效果.

Fig.10 Load balancing average optimization rate of the 4 algorithms under different numbers of devices圖 10 不同設(shè)備數(shù)量下對比4 種算法的負(fù)載均衡平均優(yōu)化率

4.4 設(shè)備移動感知的動態(tài)服務(wù)部署策略驗證

為了驗證所提設(shè)備移動感知的動態(tài)服務(wù)部署策略的有效性，本文所提方案與“總是遷移”（always migration,AM）、“從不遷移”（no migration,NM）以及“隨機(jī)遷 移K個服務(wù)”（randomK-service migration,RKM）三種基準(zhǔn)方法進(jìn)行了對比.這3 種方法的原理簡介如下：

1）AM.在每個時隙中，用戶的服務(wù)配置文件總是遷移到距離用戶最近的MEC 節(jié)點上.

2）NM.在每個時隙中，用戶的服務(wù)配置文件總保持在初始的MEC 節(jié)點不遷移.

3）RKM.在每個時隙中，隨機(jī)選取K個服務(wù)配置文件遷移到當(dāng)前最優(yōu)的MEC 節(jié)點上.

本節(jié)使用2007 年由芬蘭國家土地調(diào)查局提供的赫爾辛基市區(qū)的街道進(jìn)行仿真[31].假設(shè)終端設(shè)備在該市區(qū)街道上進(jìn)行移動，我們將該市區(qū)街道劃分成64個正方形區(qū)域，每塊大小500 m×500 m，在每塊區(qū)域的中心位置部署MEC 服務(wù)器提供移動服務(wù)，其中每臺MEC 服務(wù)器具有多個CPU 核，其計算頻率為25 GHz，存儲空間為100～160 GB，2 個MEC 節(jié)點的距離使用曼哈頓距離.假設(shè)街道上有2 種類型的移動用戶：一種是行人，速度在0.5～1.5 m/s；一種是車載用戶，速度在5.56～11.11 m/s，假設(shè)行人的數(shù)量占總?cè)藬?shù)的比率是7/8.本實驗仿真100 個時隙，每個時隙是5 min，在每個時隙t內(nèi)，假設(shè)用戶的服務(wù)配置文件所在的MEC 節(jié)點保持不變，響應(yīng)用戶所需要的服務(wù)大小均勻分布在0.8～1 GB.

圖11 展示了AM，NM，RKM 和響應(yīng)時間優(yōu)先的算法（本文算法）得到的總時延，該總時延為服務(wù)的通信時延、加密時延以及計算時延之和.RKM 算法中選取的配置文件個數(shù)K取總?cè)藬?shù)的10%.與AM，NM，RKM 這3 種基準(zhǔn)算法相比，本文算法的總時延分別平均減少了8.52%，10.64%，2.78%，最多減少可分別達(dá)10.78%，12.70%，3.74%.這是由于NM 算法從不遷移服務(wù)配置文件，因此其服務(wù)總時延基本與初始化服務(wù)配置文件放置結(jié)果有關(guān)；而AM 算法雖然一直將服務(wù)配置文件遷移到距離用戶最近的位置，然而當(dāng)一個局部地區(qū)的人數(shù)過多時，遷移到同一MEC 服務(wù)器上會給服務(wù)器的計算帶來較大的壓力，每個服務(wù)分得的資源也會減少，甚至?xí)霈F(xiàn)資源不夠的情況；RKM 算法每輪隨機(jī)選取K個服務(wù)配置文件進(jìn)行遷移，然而當(dāng)K過小時，其性能會接近NM 算法，且可能會導(dǎo)致無法優(yōu)化部分服務(wù)配置文件的放置，而當(dāng)K過大時會接近AM 算法，同樣可能出現(xiàn)資源分配不當(dāng)?shù)膯栴}.

Fig.11 Comparison of the total latency of four deployment methods圖 11 對比4 種部署方案的總時延

圖12 展示了AM，NM，RKM 和響應(yīng)時間優(yōu)先的算法（本文算法）的服務(wù)遷移成本，其中平均期望預(yù)算被設(shè)定為200.從圖12 中可以看出，AM 算法由于頻繁地進(jìn)行服務(wù)配置文件的遷移，其服務(wù)遷移成本遠(yuǎn)超過長期平均期望預(yù)算；雖然NM 算法不進(jìn)行服務(wù)配置文件的遷移，但其服務(wù)的總時延過高，且與初始化的結(jié)果有很大的關(guān)系，通常會導(dǎo)致服務(wù)質(zhì)量不高；而RKM 算法沒有充分利用服務(wù)遷移預(yù)算，使其服務(wù)遷移成本一直保持在較低的水平；而本文算法其服務(wù)遷移成本保持在長期平均期望預(yù)算的遷移成本之內(nèi)的條件下，能夠取得最優(yōu)的服務(wù)總時延.

Fig.12 Comparison of the migration costs of four deployment methods圖 12 對比4 種部署方案的遷移成本

5 結(jié) 論

本文提出了一種2 階段的服務(wù)質(zhì)量優(yōu)化方案以解決移動邊緣計算架構(gòu)下的服務(wù)安全部署問題.在第1 階段，本文考慮了服務(wù)的安全性和邊緣服務(wù)器的負(fù)載均衡問題，對服務(wù)部署問題進(jìn)行建模，提出了一種基于K-Means 的服務(wù)實時解耦方案，并設(shè)計了一種基于MOEA/D 的服務(wù)部署策略；在第2 階段，本文考慮了邊緣設(shè)備的移動性，設(shè)計了一種設(shè)備移動感知的服務(wù)部署策略，優(yōu)化了移動邊緣計算架構(gòu)下的服務(wù)質(zhì)量.實驗結(jié)果表明，與多種基準(zhǔn)方法相比，在保證系統(tǒng)安全以及服務(wù)器負(fù)載均衡的前提下，本文所提出的面向集中式服務(wù)部署策略能夠使服務(wù)請求的響應(yīng)時間降低36%，所提出的動態(tài)部署策略能進(jìn)一步降低13%的服務(wù)響應(yīng)時間.

作者貢獻(xiàn)聲明：李麗穎提出了算法思路并撰寫論文；張潤澤負(fù)責(zé)完成實驗；魏同權(quán)提出指導(dǎo)意見并修改論文.