多邊緣服務器協(xié)作環(huán)境下基于時延感知的服務選擇算法

謝 娜,譚文安,2,孫 勇,趙 璐,黃 黎,4

(1.南京航空航天大學計算機科學與技術學院,江蘇 南京 211106)(2.上海第二工業(yè)大學計算機與信息工程學院,上海 201209)(3.南京師范大學地理科學學院,江蘇 南京 210023)(4.江蘇開放大學信息與機電工程學院,江蘇 南京 210017)

近年來,隨著移動設備和無線網(wǎng)絡技術的快速發(fā)展,服務不再局限于傳統(tǒng)的平臺而變得更加復雜多樣. 用戶可以不受時空約束而任意選擇所需的服務來處理自己業(yè)務. 這也進一步加劇了服務數(shù)量和種類的快速增長. 同時無人駕駛、智慧城市[1]、增強現(xiàn)實[2]等延遲敏感型和計算密集型新應用服務的出現(xiàn)和流行,使得用戶對服務質(zhì)量和聚合粒度提出更高要求[3]. 如何為用戶選擇合適的服務是服務選擇的熱點問題,并引起了學者們的密切關注.

Deng等[4]在移動云環(huán)境中分析了服務持續(xù)移動性和基于位置變化的特點,提出了移動模型和移動感知的QoS計算規(guī)則,采用基于教-學優(yōu)化可移動性的選擇算法獲得近似最優(yōu)解,實驗驗證該方法優(yōu)于當前標準的優(yōu)化算法. 文獻[5]分析了在移動環(huán)境中服務請求者和提供者均具有移動性,提出了一個移動服務共享社區(qū)的移動服務供應體系結(jié)構(gòu),采用Krill-Herd算法解決服務組合的問題. 以上在移動云環(huán)境中的服務選擇工作是針對服務的移動性展開的,而忽略服務能量的消耗問題. 文獻[6]針對移動云環(huán)境下移動設備電池容量有限的問題,以移動狀態(tài)下某用戶調(diào)用工作流的總能耗最小為目標進行服務選擇,提出了不同結(jié)構(gòu)組合服務的能耗聚合規(guī)則并采用遺傳算法求解能耗最低的高質(zhì)量服務組合. Tong等[7]提出了一種能量感知的保證QoS的工作流管理機制,設計了一個兼顧服務能量和服務質(zhì)量的高效服務選擇方案,并提出了基于平衡能量消耗的自適應機制的約束分解的服務選擇方法. 文獻[8]是在滿足延遲約束的基礎上以最小化移動設備的能量消耗為目標,選擇每個子任務在移動設備端或云端執(zhí)行的策略. 將協(xié)同任務執(zhí)行定義為延遲約束的工作流調(diào)度問題,根據(jù)不同的情況使用兩種算法調(diào)度任務. 對于無執(zhí)行限制的特殊情況采用單攀策略求解. 對于部分任務必須在移動設備或云上執(zhí)行的一般情況則采用LARAC算法求解. 通過仿真實驗表明協(xié)同任務執(zhí)行比本地執(zhí)行和遠程執(zhí)行更節(jié)能.

以上服務選擇的研究均是以服務資源在云端為前提的. 然而,隨著移動網(wǎng)絡服務資源日益增多,有限的網(wǎng)絡帶寬容易給用戶傳輸造成網(wǎng)絡阻塞,使得訪問云端服務的時延過高,不能滿足用戶低延遲服務的需求,如無人機,虛擬/增強現(xiàn)實[2]等. 云端的服務選擇方式已不適應于時延敏感型的服務. 移動邊緣計算(mobile edge computing,簡稱MEC)作為新興的一種計算模式[9-10]應運而生,它可以將服務資源下沉到靠近用戶端,并通過無線網(wǎng)將移動設備與邊緣服務器相連,為用戶提供低時延的服務[11]. 部分研究者把服務選擇的環(huán)境轉(zhuǎn)向邊緣端. 如文獻[12]針對網(wǎng)絡質(zhì)量引起的邊緣計算協(xié)同服務效率和質(zhì)量低等問題,構(gòu)建了基于盟主的邊緣計算協(xié)同服務器組織模型,并提出了協(xié)同服務池的算法解決邊緣計算服務節(jié)點過載問題. 實驗驗證該算法能有效提高邊緣計算協(xié)同服務能力和質(zhì)量. 文獻[13]研究了在移動邊緣計算系統(tǒng)中的服務選擇問題,以進一步減少服務請求的總體響應時間為目的,考慮了交付服務的邊緣服務器選擇. 提出了一種結(jié)合遺傳算法和模擬退火算法的新啟發(fā)式算法. 通過實驗仿真證明所提方法的高效性.

在上述邊緣環(huán)境下的服務選擇研究中,雖然能滿足用戶低延時的服務需求,但由于邊緣服務器端的計算能力、存儲容量和通信資源相對有限[14],故在其上部署的服務數(shù)量有限. 而用戶需求復雜多變,需要多個服務相互協(xié)作共同完成其復雜業(yè)務[15],單個邊緣服務器已不能提供用戶所需的所有服務. 如何在移動邊緣環(huán)境下為用戶提供復雜低延遲的服務是當前需要解決的問題. 針對該問題,本文從多個邊緣服務器相互協(xié)作共同為用戶提供服務的思想出發(fā),將邊緣協(xié)作的服務選擇(Edge Cooperation Service Selection,ECSS)問題建模成一個帶約束的最優(yōu)化問題,在邊緣服務器網(wǎng)絡中根據(jù)Dijkstra算法求解當前用戶的本地服務器到其他邊緣服務器的最短距離,基于服務器的路由閾值選擇本地服務器的鄰居節(jié)點作為候選服務器集合;并提出了一種基于低時延多有效服務的貪心選擇策略(Low-latency Much-effective service,簡稱為LLMES)的新啟發(fā)式算法,用于從候選服務器集合中選擇一組延遲最小且相互協(xié)作共同為用戶提供服務的邊緣服務器,即選中了一組滿足用戶需求的近似最優(yōu)服務. 通過實驗仿真驗證了本文提出的LLMES算法性能明顯優(yōu)于其他3種具有代表性的方法.

1 問題定義及模型

假設在某個區(qū)域內(nèi)放置n個邊緣服務器ES={es1,es2,…,esn},每個邊緣服務器esi上已部署若干服務,記作SEi={…sj…}(1≤j≤m).其中覆蓋用戶的邊緣服務器集合為ESC(ESC?ES),邊緣服務器之間可通過高速鏈路與鄰近邊緣服務器相互連接并共享信息資源[16-17],從而構(gòu)成一個邊緣服務器網(wǎng)絡,用二元組G=表示.其中E={……}(esi,esj∈ES)表示服務器之間通過高速鏈路直接連接邊的集合.假設用戶需要一組服務R={s1,s2,…,sm},為了簡化模型,進一步假設R中的服務之間沒有邏輯關系,可以并行處理,且這些服務分布在不同服務器上.如果想要滿足用戶服務需求則要從覆蓋用戶的某個服務器出發(fā),尋找其鄰近一組邊緣服務器組成一個服務器集合相互協(xié)作共同為用戶提供所有服務.且保證用戶訪問服務的總時延最小.所以,選擇服務的過程就轉(zhuǎn)換成選擇邊緣服務器的過程.如何選擇一組邊緣服務器能夠提供用戶所需的服務并保證服務的總時延最小是本文要解決的問題.

如圖1所示,用戶需要的服務是{s1,s2,s3,s4,s5,s6},而邊緣服務器中有一個本地服務器節(jié)點es1覆蓋用戶,用戶從es1出發(fā)選擇es2和es6組成的服務器集合{es1,es2,es6}相互協(xié)作共同為用戶提供一組服務,且這組服務器提供的服務時延最小.在現(xiàn)實ECSS問題場景中,服務器數(shù)量和服務數(shù)量較大,因此在ECSS中發(fā)現(xiàn)最優(yōu)解有一定的難度. 所以邊緣環(huán)境服務提供商急需一種有效的方法來解決ECSS問題.

1.1 邊緣服務器訪問模型

定義1本地服務器 當一個邊緣服務器esi能夠被用戶u直接訪問時,我們稱該邊緣服務器esi是用戶u的本地服務器,或者說u被esi覆蓋.將本地服務器組成的集合記為ESC(ESC?ES),為了描述方便,我們采用一維向量C來描述服務器集合ES中包含的本地服務器,即:C={c1,c2,…,cn},ci∈{0,1}.其中ci是二進制變量,表示esi是否為本地服務器,若ci=1表示esi是本地服務器,用戶u可直接訪問;反之則不是本地服務器,用戶u不能直接訪問.

在邊緣服務器網(wǎng)絡中,服務器之間可以直接相互通信,也可通過其他服務器進行間接路由通信.如圖2 所示,在邊緣服務器相互協(xié)作的拓撲結(jié)構(gòu)中,es1與es2直接通信,而es1與es4則需要通過es2或es6進行路由間接通信.本文為了構(gòu)建一個簡潔且通用的模型,用路由跳數(shù)hpij來衡量邊緣服務器esi到esj之間的路由距離[16-17].當用戶必須通過本地邊緣服務器esi的高速鏈路才能間接訪問邊緣服務器esj時,我們稱用戶間接訪問esj,且滿足hpij≤hplimit.其中hplimit是服務器之間能夠路由的最大跳數(shù),也稱路由閾值,圖2中本地服務器為es1.

圖1 一個邊緣服務器協(xié)作的場景Fig.1 A scene of edge server collaboration

圖2 邊緣服務器協(xié)作的拓撲結(jié)構(gòu)Fig.2 A topology of edge server collaboration

定義2鄰居服務器 給定任意一個邊緣服務器esi,存在其他服務器esj和esi在路由閾值范圍內(nèi)(0≤hpij≤hplimit)進行數(shù)據(jù)信息資源共享和傳輸,則稱esj是esi的鄰居服務器.把esi的所有鄰居服務器節(jié)點組合起來的集合稱為esi的鄰居服務器集合,記作NEi,且NEi?ES.

當用戶可以訪問(直接訪問或者間接訪問)邊緣服務器esi時,才能充分利用其資源.我們采用了一維向量A表示用戶對邊緣服務器集合ES的訪問情況,即A={a1,a2,…,an},?ai∈{0,1},i∈[1,n].其中ai是一個二進制變量,表示用戶u是否可以訪問esi.若ai=1表示用戶u可訪問esi;反之,則不可訪問.ai具體的定義如下所示:

(1)

式中,NEi表示邊緣服務器esi的鄰居節(jié)點集合,hpik表示邊緣服務器esi和esk之間的路由距離.當用戶u被esi覆蓋時,即ci=1,用戶u可直接訪問本地服務器esi上的應用服務資源,即ai=1;當用戶沒有被esi覆蓋而被esi的鄰居節(jié)點esk(esk∈NEi)覆蓋時,即ck=1,用戶可通過esk到esi之間的通信路徑(esk…esi)間接訪問esi,即ai=1;當esi沒有覆蓋用戶且其鄰居節(jié)點均無覆蓋用戶u,則用戶u不可訪問esi,即ai=0.如圖2 中,假設服務器的路由閾值hplimit是1,則邊緣服務器es5不能被訪問,而其他服務器可以被訪問,對應的訪問向量為A={1,1,1,1,0,1}.

1.2 服務時延感知的計算模型

管理移動設備用戶的上行/下行通信的無線基站一般是3G/4G宏蜂窩或小蜂窩基站[18].當多個用戶同時訪問邊緣服務器時,傳輸?shù)臄?shù)據(jù)速率公式可以參考文獻[18]和[19],這里我們不做詳細描述.用戶調(diào)用服務的時延和很多因素有關,如上行和下行傳輸?shù)臄?shù)據(jù)量,上行和下行的傳輸速率,服務的運行時間.參考文獻[19]和[20],當一個用戶向邊緣服務器發(fā)送服務請求sk時,服務請求的生命周期主要分為 4個部分,首先通過移動網(wǎng)絡將服務sk請求由用戶上傳至最近的邊緣服務器esi(這里為本地服務器)上;如果esi不能滿足用戶所有服務需求時,則會向鄰近的服務器發(fā)送服務請求,路由選擇合適邊緣服務器esj來處理請求并將請求數(shù)據(jù)傳輸?shù)皆摲掌魃?接著服務器esj接到請求后運行服務sk并返還運行結(jié)果;最后再把服務的執(zhí)行結(jié)果傳送給本地邊緣服務器esi并由esi返還給用戶.由于服務上行的數(shù)據(jù)量遠大于下行數(shù)據(jù)量的傳輸,所以上行數(shù)據(jù)傳輸時延遠大于下行數(shù)據(jù)時延,這里我們只考慮上行數(shù)據(jù)傳輸時延.為了簡化模型,我們進一步假設服務執(zhí)行時延遠小于數(shù)據(jù)傳輸時延.所以用戶訪問服務的時延只和用戶訪問本地服務器的傳輸速率,服務器之間的路由傳輸速率,以及服務上行數(shù)據(jù)量的大小有關.

解決ECSS問題的關鍵就是選擇一組部署在不同邊緣服務器上的服務,且保證用戶訪問所有服務R的總時延最低.首先從當前本地服務器集合中選擇一個本地邊緣服務器esi,然后選擇esi中能夠提供的服務,接著從esi出發(fā)路由周邊的鄰居服務器節(jié)點,根據(jù)低時延多有效服務的貪心選擇策略選擇合適的服務器節(jié)點,直到選中一組服務器中包含的服務能夠滿足用戶的所有需求.所以總時延的計算分為兩部分,一部分是用戶將服務需求數(shù)據(jù)傳輸?shù)奖贿x的本地服務器esi上的訪問時延,另一部分是將服務從本地服務器esi傳輸?shù)狡渌贿x中服務器之間的路由時延.接下來我們給出這兩部分計算時延的方法.

(1)用戶訪問本地邊緣服務器的時延

假設用戶選擇的本地服務器是esi,所需要的服務集合是R={s1,s2,…,sm},則用戶訪問本地服務器esi的時延為:

(2)

式中,Uk表示服務sk需要輸入的數(shù)據(jù)量大小,αi是用戶到本地服務器esi的上行傳輸速率,可通過文獻中的香農(nóng)公式獲得[18,20],這里不做詳細描述.TC2E(i)表示用戶的服務需求R上傳到本地服務器esi的訪問時延,ci用來控制邊緣服務器esi為本地服務器,由定義1可知,ci=1表示esi為本地服務器,否則為非本地服務器.

(2)本地服務器到其他服務器之間的路由時延

(3)

式中,Ul表示服務sl需要傳輸?shù)臄?shù)據(jù)量大小,SEj表示服務器esj能夠提供的服務集合.由文獻[18]和[21]可知服務器之間的傳輸速率和路由的帶寬及拓撲結(jié)構(gòu)相關.而服務器之間的路由距離可通過Dijkstra算法求解兩點之間的最小路徑來獲取.為了簡化模型,我們采用βi,j表示從本地服務器esi到鄰居節(jié)點服務器esj的路由路徑上的平均傳輸速率.由定義2中可知,aj為二進制變量,用來控制選擇的鄰居節(jié)點服務器是否能被用戶訪問.假設用戶所需服務不存在邏輯先后順序,可以并行運行,則從本地服務器esi到所有選中的其他服務器路由的總時延是esi到所選的其他服務器之間時延的最大值,計算公式如下所示:

MAXesj∈NEiTE2E(i,j),

(4)

式中,NEi為本地服務器esi的鄰居服務器節(jié)點集合.用戶以esi為本地服務器,選擇NEi中的部分服務器相互協(xié)作共同提供服務需求.用戶訪問所有服務R的總時延為:

T=TC2E(i)+MAXesj∈NEiTE2E(i,j),

(5)

式中,T表示用戶到被選中的一組服務器的總時延.

1.3 邊緣協(xié)作服務選擇問題

基于以上描述,我們對ECSS問題進行建模,模型描述如下.

定義3ECSS問題 假設給定一組邊緣服務器ES={es1,es2,…,esn},任意一個邊緣服務器esi(esi∈ES)上已部署的服務集合為SEi,用戶的本地服務器集合為ESC(ESC?ES).用戶服務需求的集合為R={s1,s2,…,sm}.ECSS問題就是要發(fā)現(xiàn)一組最優(yōu)的邊緣服務器ES*,使得ES*中所有服務器能夠相互協(xié)作共同為用戶提供服務R,且保證用戶訪問這些服務的總時延最小.即:

minT.

(6)

約束為:

(7)

?ci,aj∈{0,1},esi∈ESC.

(8)

目標函數(shù)(公式6)表示用戶選擇一組邊緣服務器集合ES*的訪問時延總和,值越小越好.約束(7)保證所選的一組邊緣服務器ES*中所有服務器提供的服務集合包含了用戶所需要的服務需求R.而集合ES*中的任何一個服務器esw都是從本地服務器節(jié)點esi及其鄰居節(jié)點NEi所構(gòu)成的集合{esi}∪NEi中選擇的.約束(8)是兩個二進制變量,ci表示邊緣服務器esi是否為本地服務器節(jié)點,如果是本地服務器,則ci=1,否則為非本地服務器;而aj用來控制所選的鄰居節(jié)點esj是否可以訪問;如果aj=1,表示esj可以訪問,否則不可訪問;esi∈ESC用來控制本地服務器節(jié)點的選擇必須從本地服務器集合ESC中選擇.

由ECSS問題定義可知,該問題的任何解都可以在多項式時間內(nèi)搜索到并驗證所求的解是否滿足約束條件(7)和(8),因此該問題是P問題也是NP問題. 此外,ECSS問題可通過經(jīng)典的加權(quán)集合覆蓋問題(Weighted Set covering,WSC)約簡獲得(由于篇幅原因,在這里不做詳細的證明). 所以ECSS問題是一個NP-hard問題.

在前期研究基礎上[21-23]，本研究以天然菱鎂礦為原料制備重鎂水溶液，并以此為前驅(qū)溶液，利用熱分解法制備晶須，主要考察熱分解時間、重鎂水溶液濃度和攪拌速率對晶體組成和形貌的影響，并分析了結(jié)晶動力學過程。

2 方法設計

解決ECSS問題的方法就是在滿足用戶服務約束的情況下選擇一組服務器集合保證提供服務的總時延最小. 因為ECSS問題是NP-hard問題,所以本文提出了一個解決ECSS問題的一般性框架,設計了一種基于低時延多有效服務的貪心選擇策略的新啟發(fā)式算法,即LLMES算法. 通過該算法求解ECSS問題的最優(yōu)解.

2.1 LLMES算法思想

LLMES算法的主要思想是從當前本地服務器ESC中的1個元素esi(esi∈ESC,i∈[1,n])出發(fā),計算esi的鄰居節(jié)點集合NEi.從NEi中選擇1組邊緣服務器和esi組成集合ES*,使得ES*集合中的所有邊緣服務器相互協(xié)作共同提供的服務組成集合S*能夠滿足用戶需求,即S*?R.在NEi中選擇當前最優(yōu)的邊緣服務器要滿足兩個條件,一是esi到該服務器的路由時延最短,二是能夠提供有效服務的數(shù)量最多.我們用排序指標(Ranking Criterion)作為選擇當前最優(yōu)服務器策略的衡量標準.排序指標的計算公式如下所示:

(9)

式中,crj表示邊緣服務器esj的排序指標值,Tij表示邊緣服務器esi與esj的最短路由時延,可以根據(jù)公式(3)計算.R表示用戶所需的服務集合,S*表示當前已經(jīng)選中的服務集合,SEj表示邊緣服務器esj上包含的服務集合.邊緣服務器esj上包含有效服務(即用戶所需的且未被選中的服務)數(shù)量越多,則公式(9)的分母就越大,對應的crj的值就越小.當分子Tij的值越小,服務器之間的路由時延越小,對應的crj值越小.根據(jù)當前服務器的cr值來選擇當前最優(yōu)的服務器,值越小越好.按照低時延多有效服務的選擇策略計算鄰居集合中每個服務器的crj值,選擇cr值最小的服務器并入ES*中,并將該服務器上能夠提供的服務放入服務集合S*中,直到選中所有服務R為止.

2.2 LLMES算法描述

整個求解過程分成兩個部分,第一部分先求解本地服務器esi的鄰居節(jié)點NEi.第二部分在NEi中選擇最優(yōu)服務器組合,使得用戶到這些服務器上的時延最小,并且組合的服務器能夠包含用戶需要的所有服務R.詳細算法描述如下.

步驟1:初始化邊緣服務器集合ES,用戶需求服務為R,服務需要傳輸?shù)臄?shù)據(jù)向量為UC,邊緣服務器網(wǎng)絡G中邊集為E,用戶到本地服務器之間的傳輸速率向量為CV,服務器之間的傳輸速率V,服務器部署服務矩陣D,本地服務器向量ESC,服務器路由閾值為hplimit.

步驟2:先從ESC中選擇一個本地服務器esi放入ES*中,根據(jù)公式(2)計算用戶到esi的時延TC2E.在G中采用Dijkstra算法求esi到其他服務器的路由路徑距離hpij.

步驟3:選擇滿足hpij∈[0,hplimit]的邊緣服務器節(jié)點作為本地服務器esi的鄰居節(jié)點集合NEi.

步驟4:根據(jù)公式(9)計算每個邊緣服務器節(jié)點的排序指標cr,選擇最小值對應的邊緣服務器放入ES*,根據(jù)公式(3)計算esi到該服務器的路由時延Tij.

步驟5:重復步驟4,直到ES*集合中所有服務器提供的服務包含R,選擇esi到ES*-{esi}中服務器時延最大值作為服務器的路由時延TE2E,計算總時延T.

步驟6:重復步驟2到步驟5,選擇總時延T最小的一組邊緣服務器ES*.

步驟7:輸出ES*和對應的時延T.

在LLMES算法運行過程中,采用Dijkstra算法求解圖中的一個頂點到其他頂點的最短路徑的時間復雜度是O(n2),故求解本地服務器的鄰居節(jié)點NEi的時間復雜度為O(n2).而每一次從本地服務器esi及NEi中尋找最優(yōu)解時,都要遍歷NEi判斷是否存在解.最壞情況下,需要選擇NEi中所有的服務器來提供服務,這個過程的時間復雜度為O(n2).所以從一個本地服務器esi開始選擇一組服務的時間復雜度為O(n2)+O(n2).在實際應用中對于用戶來說本地服務器個數(shù)一般為常量k.因此我們提出的LLMES算法的時間復雜度為O(n2).

3 實驗分析

本文仿真實驗的環(huán)境是Intel(R)Core(TM)i7-7500U CPU筆記本,主頻為2.70～2.9 GHz,內(nèi)存為8.00 GB. 仿真軟件為MATLAB R2016a. 實驗數(shù)據(jù)來自于EUA真實數(shù)據(jù)集[21],該數(shù)據(jù)集中包含墨爾本1 464個真實世界基站的地理位置. 我們從EUA中隨機選擇某個更小區(qū)域內(nèi)n個基站作為邊緣服務器. 此外,我們參考文獻[18]設置用戶到邊緣服務器上行速率αi為(1,3)MB/s,服務器之間的路由速率為βi,j為(80,100)MB/s.

為了驗證本文提出LLMES方法的性能和效率,我們選擇 Random方法,GES方法和GMT方法與其進行比較. 這3種方法詳細描述如下:

Random:該方法是在esi的鄰居節(jié)點NEi中隨機選擇一個邊緣服務器esj,為用戶提供所需服務,如果不能滿足需求R,則繼續(xù)隨機選擇其他服務器,直到選中的服務器集合能夠提供用戶所需的服務R為止.

GES[22]:給定一組邊緣服務器ES和若干個本地服務器ESC,選擇ESC中某個節(jié)點esi及其鄰居NEi構(gòu)成候選服務器集合,選擇服務器所提供的有效服務最多作為當前最優(yōu)邊緣服務器.重復這個選擇步驟,直到選中的服務器能夠提供所有的服務R為止. 最后在所有候選解中選擇總延遲最小的解作為最終解.

GMT:給定一組邊緣服務器ES和若干個本地服務器ESC,選擇ESC中某個節(jié)點esi及其鄰居NEi構(gòu)成候選服務器集合.選擇從本地服務器esi到該服務器的路由延遲最小的那個服務器作為當前最優(yōu)邊緣服務器.重復這個選擇步驟,直到選中的邊緣服務器能夠提供所有的服務R為止. 最后在所有候選解中選擇總延遲最小的解作為最終解.

3.1 評價指標和參數(shù)

為了更直觀體現(xiàn)本文提出的LLMES方法的有效性,我們選擇訪問時延和運行時間兩個評價指標. 并深入分析與ECSS問題場景相關的5個參數(shù)對運行結(jié)果的影響. 這5個參數(shù)分別是:

(1)邊緣服務器數(shù)量(n=|ES|):該參數(shù)表示邊緣服務器網(wǎng)絡圖的規(guī)模大小.

(2)服務數(shù)量(m=|R|):該參數(shù)用來表示當前用戶所需的服務數(shù)量.

(3)圖密度(gd=|E|/n):圖的邊數(shù)和頂點個數(shù)的比值稱為圖密度.gd越大,圖邊數(shù)越多,對應服務器之間相互協(xié)作的效果越好.

(4)路由閾值hplimit:允許服務器之間能夠路由的最大跳數(shù),兩個服務器的路由距離不能大于hplimit,否則它們不能相互通信.

(5)服務部署規(guī)模ss:每個服務器能夠部署的服務數(shù)量.

對每個參數(shù)進行不同取值范圍的設置.每次設置時選擇一個參數(shù)在一定范圍內(nèi)變化,而其他參數(shù)不變.參數(shù)詳細的設置情況如表1所示,分別是#1,#2,#3,#4和#5.例如#1設置中只有參數(shù)n是變化的,從初值10開始以步長為5的方式增加到30.其他參數(shù)值固定不變,分別是:m=7,gd=1.4,hplimit=3,ss取值為[3,4]. 每一組實驗都是在參數(shù)設置相同的環(huán)境下運行100次取平均值作為最后結(jié)果.

表1 實驗參數(shù)設置Table 1 Experimental parameter setting

比較LLMES,Random,GES和GMT 4種方法在不同參數(shù)設置情況下選擇服務的總時延和運行時間. 分析每個參數(shù)對運行結(jié)果的影響如圖3-圖12所示.

3.2 實驗結(jié)果分析

(1)邊緣服務器數(shù)量的影響

圖3和圖4分別是在#1設置情況下4種方法獲得的時延和運行時間. 由圖3可知,LLMES算法選擇服務的時延相比其他3種方法最低,Random方法最高. 在EUA數(shù)據(jù)集上,LLMES算法計算的平均時延比Random,GES和GMT方法分別降低了79.3%,69%和52.3%. 且隨著邊緣服務器數(shù)量的增加,4種方法的時延略有變化. LLMES方法變化幅度最小,其他3種方法略大. 這是因為服務數(shù)量固定不變,服務器數(shù)量雖然增多,但被選中的服務器數(shù)量變化不大,所以對時延沒有太大影響. 由于4種方法選擇的策略不同,所以表現(xiàn)出不同的變化幅度. 圖4中,LLMES方法的運行時間相比其他3種方法最長. 但是和時延節(jié)省的時間相比,可忽略不計. 其平均運行時間和平均時延分別為12.61 ms和50.47 ms;Random方法的運行時間最短,但時延最高,分別為3.85 ms和243.78 ms;GES為9.17 ms和163.62 ms;GMT為6.29 ms和105.89 ms. 所以本文提出的方法的性能優(yōu)于其他3種方法. 此外,隨著邊緣服務器數(shù)量增多,4種方法的運行時間整體是增加趨勢. 這是因為隨著服務器數(shù)量增加,需要比較的候選服務器數(shù)量也隨之增加,所以運行時間呈現(xiàn)增加趨勢. 服務器數(shù)量對時延的影響較小,對運行時間的影響較大.

圖3 不同邊緣服務器數(shù)量的時延Fig.3 Latency for different number of edge servers

圖4 不同邊緣服務器數(shù)量的運行時間Fig.4 Execution time for different number of edge servers

(2)服務數(shù)量的影響

圖5和圖6分別是在#2設置情況下的運行結(jié)果. 由圖5可知,LLMES算法選擇服務的時延最低,比Random,GES和GMT方法分別降低了75.5%,66.51%和54.4%. 隨著服務數(shù)量增加,4種方法獲得的時延均隨之增加. LLMES方法增速較慢,其他3種方法增速較快. 這是因為隨著用戶所需服務數(shù)量的增加,服務要傳輸?shù)臄?shù)據(jù)量也隨之增加,且需要更多的邊緣服務器來提供服務. 所以用戶調(diào)用服務的時延表現(xiàn)出增加趨勢. 由于選擇的策略不同,因此表現(xiàn)出增速不同. 由圖6可知,LLMES方法運行的時間最長,但時延最小,其平均運行時間和平均時延分別為11.53 ms和63.27 ms;Random運行時間最短,但總時延最長,平均值分別為3.84 ms和250.87 ms;GES為182.83 ms和9.82 ms;GMT為136.76 ms和6.36 ms. 所以本文提出的方法性能優(yōu)于其他3種方法. 隨著服務數(shù)量的增多,需要選擇更多的服務器提供服務,整個搜索過程增加,所以4種方法的運行時間整體上都在增加. 服務數(shù)量的變化對4種方法的運行結(jié)果影響較大.

圖5 不同服務數(shù)量的時延Fig.5 Latency for different number of services

圖6 不同服務數(shù)量的運行時間Fig.6 Execution time for different number of services

(3)圖密度的影響

圖7和圖8分別是在#3設置情況下獲得的運行結(jié)果. 由圖7可知,LLMES算法的時延最低,比Random,GER和GMT方法分別降低了78%,68.4%和52.05%. 圖密度的增加使得時延有所降低但幅度較小. 這是因為隨著圖密度增加,與本地服務器相連且跳數(shù)小的服務器數(shù)量也隨之增加,所以時延降低. 圖密度增加使得邊緣網(wǎng)絡中的邊數(shù)增加,但與服務器數(shù)量相比可忽略不計. 所以圖密度對時延影響較小.

圖7 不同圖密度的時延Fig.7 Latency for different graph densities

圖8 不同圖密度的運行時間Fig.8 Execution time for different graph densities

由圖8可知,LLMES方法運行時間最長,Random最短. LLMES方法的平均運行時間和平均時延分別是10.42 ms和49.75 ms;Random方法分別是2.95 ms和226.72 ms;GES為8.65 ms 和157.46 ms;GMT為5.83 ms和103.82 ms. 所以本文提出的方法的性能優(yōu)于其他方法. 隨著圖密度的增多,4種方法因為選擇的策略不同而使得運行時間變化趨勢不同,但整體上呈現(xiàn)增加趨勢. 這是因為隨著圖密度的增加對應候選服務器的數(shù)量增加,所以需要更多時間去選擇服務. 圖密度對服務選擇的時延影響較小,但對運行時間的影響較大.

(4)路由閾值的影響

圖9和圖10分別是在#4設置情況下的運行結(jié)果. 在圖9中,LLMES算法的時延比Random、GES和GMT方法分別降低了74.4%、63.6%和50.3%. 隨著路由閾值的增加,LLMES算法和GMT方法的時延基本上沒有什么變化,而Random方法和GES方法的時延卻隨之增加. 這是因為前兩者的方法是根據(jù)服務器所提供服務的時延最小進行選擇,而跳數(shù)小的服務器數(shù)量固定,所以獲得時延基本不變. Random方法是隨機選擇服務器,隨著路由閾值的增加,候選服務器之間最大的路由距離增加,時延也隨之增加. GES方法是依據(jù)能夠供有效服務數(shù)量最多來選擇有效服務器的,所以時延也隨之增加.

在圖10中,4種方法的運行時間性能對比與圖8相同. 隨著hplimit值的增加,LLMES和GES方法的運行時間均增加,而Random和GMT方法運行時間雖然有所減少,但變化不大. 這是因為隨著路由閾值的增加,能夠相互路由的服務器數(shù)量增加. 所以候選服務器的數(shù)量隨之增加. LLMES和GMT方法在選擇能夠提供最多有效服務的服務器時間也隨之增加,所以總體運行時間增加. 而Random和GMT方法由于服務器節(jié)點的增多,可以選擇的服務器數(shù)量增加,而遇到不能提供有效服務的服務器概率變小,所以運行時間減少. 參數(shù)hplimit對4種方法的時延和運行時間的影響不同.

圖9 不同路由閾值的時延Fig.9 Latency for different routing thresholds

圖10 不同路由閾值的運行時間Fig.10 Execution time for different routing thresholds

(5)服務部署規(guī)模的影響

圖11和圖12是在#5設置情況下的運行結(jié)果. 由圖11可知,LLMES算法獲得的時延最低,比Random、GES和GMT方法分別降低了78.87%、67.54%和53.50%. 隨著參數(shù)ss的增加,4種方法的時延均隨之降低. 這是因為參數(shù)ss的增加,與本地服務器路由距離較近的服務器上部署的服務數(shù)量也隨之增加,所以服務的時延降低.

圖11 不同服務規(guī)模的時延Fig.11 Latency for different scale of services

圖12 不同服務規(guī)模的運行時間Fig.12 Execution time for different scale of services

在圖12中,LLMES方法運行時間最長但時延最低,Random運行時間最少但時延最高. LLMES方法的平均運行時間和平均時延分別是10.32 ms和49.47 ms;Random分別是3.61 ms和234.28 ms;GES為8.66 ms和152.46 ms;GMT為6.05 ms和106.42 ms. 所以LLMES方法的性能優(yōu)于其他方法. 隨著邊緣服務上部署的服務數(shù)量的增加,4種方法的運行時間均減少. 這是因為隨著參數(shù)ss的增加,只需選擇較少的服務器就能為用戶提供所有服務,所以運行時間也隨之減少. 參數(shù)ss的增加能夠降低服務時延和運行時間.

通過上述5組實驗的對比分析,本文提出的LLMES算法選擇服務的總時延最低. 雖然在運行時間上比其他3種方法略高,但是和時延節(jié)省的時間相比可忽略不計. 所以本文提出的LLMES算法的性能優(yōu)于其他3種算法.

4 結(jié)論

本文針對邊緣計算環(huán)境下用戶業(yè)務需求復雜多樣和時延敏感的問題,提出了多個邊緣服務器相互協(xié)作的思想. 將ECSS問題建模成帶約束的最優(yōu)化問題并給出一種新的啟發(fā)式算法LLMES來解決該問題. 該算法采用低時延多有效服務的貪心選擇策略選擇當前能夠提供最小時延服務集的最優(yōu)服務器集合. 通過在EUA數(shù)據(jù)集上仿真實驗分析,LLMES算法比Random、GES和GMT方法的運行時間平均增加了7.35 ms,1.69 ms和4.57 ms;而時延平均減少了179.29 ms,107.11 ms和58.53 ms. 本文提出的LLMES算法在邊緣協(xié)作環(huán)境下選擇服務的總時延更低,整體性能更好.