邵蘇杰 吳 磊 鐘 成 郭少勇 卜憲德

①(北京郵電大學(xué)網(wǎng)絡(luò)與交換技術(shù)國家重點(diǎn)實(shí)驗(yàn)室 北京 100876)

②(國網(wǎng)河北省電力有限公司雄安新區(qū)供電公司 雄安 071600)

③(國網(wǎng)智能電網(wǎng)研究院有限公司 南京 210003)

1 引言

隨著物聯(lián)網(wǎng)的發(fā)展，邊緣設(shè)備大規(guī)模普及，其數(shù)據(jù)逐漸呈現(xiàn)海量異構(gòu)、處理復(fù)雜等特點(diǎn)，對業(yè)務(wù)的實(shí)時性和可靠性也提出了更高的要求[1]。云平臺與邊緣用戶的遠(yuǎn)距離通信產(chǎn)生過大傳輸時延，業(yè)務(wù)時響應(yīng)不及時，難以滿足業(yè)務(wù)QoS[2]。邊緣計算作為一種分布式的數(shù)據(jù)處理和存儲架構(gòu)被提出，協(xié)同云計算提供就近服務(wù)[3]，為處于邊緣的業(yè)務(wù)提供更快的響應(yīng)時間和更低的帶寬成本以及更好的數(shù)據(jù)隱私性[4,5]。然而，與云服務(wù)器相比，邊緣服務(wù)器在處理、存儲和通信等方面的資源相對有限，難以在單獨(dú)節(jié)點(diǎn)中承載復(fù)雜的物聯(lián)網(wǎng)(Internet of Things)應(yīng)用[6]。

隨著微服務(wù)架構(gòu)的提出[7]，復(fù)雜單體應(yīng)用被分解為更細(xì)粒度且松散耦合的微服務(wù)集合，每個微服務(wù)集中實(shí)現(xiàn)一種功能，多個微服務(wù)結(jié)合成為工作流形式的組合服務(wù)，以提供完整的業(yè)務(wù)請求。為高效利用邊緣側(cè)資源，容器技術(shù)作為一種輕量級的虛擬化技術(shù)，成為微服務(wù)部署的絕佳選擇[8]，它將微服務(wù)封裝在容器中并實(shí)現(xiàn)資源隔離，可在資源受限和異構(gòu)的邊緣服務(wù)器中部署多個容器實(shí)例，為完成業(yè)務(wù)的并發(fā)請求提供多種服務(wù)選擇方案。前驅(qū)微服務(wù)的選擇策略將直接影響工作流中后續(xù)所有微服務(wù)的完成時間，請求中關(guān)鍵微服務(wù)的阻塞很有可能導(dǎo)致請求的整體執(zhí)行時間超過預(yù)期，降低用戶服務(wù)質(zhì)量。此外，基于邊緣計算的分布式特性，部署在網(wǎng)絡(luò)距離較遠(yuǎn)的邊緣服務(wù)器上容器實(shí)例之間的通信，將造成通信時延和網(wǎng)絡(luò)資源消耗的增加。因此，相比線性結(jié)構(gòu)的服務(wù)選擇而言，邊緣微服務(wù)選擇問題需要考慮到微服務(wù)之間的依賴關(guān)系以及并發(fā)請求對容器實(shí)例的競爭關(guān)系，如何在邊緣環(huán)境下為基于工作流的并發(fā)請求制定最優(yōu)的服務(wù)選擇策略成為難題。

近年來，國內(nèi)外學(xué)者針對邊緣環(huán)境中的服務(wù)選擇問題做了研究，文獻(xiàn)[9]提出一種感知延遲的微服務(wù)混搭方法，在移動邊緣計算中為應(yīng)用程序提供微服務(wù)的最佳配置，有效保證了時延并顯著降低網(wǎng)絡(luò)資源消耗，但只考慮了簡單串行結(jié)構(gòu)，未考慮復(fù)雜工作流形式的應(yīng)用架構(gòu)。 文獻(xiàn)[10]采取工作流形式描述復(fù)合服務(wù)，結(jié)合實(shí)例處理速度和任務(wù)并發(fā)度，提出一種基于列表的微服務(wù)選擇算法，能有效保障業(yè)務(wù)服務(wù)質(zhì)量，但沒有考慮邊緣環(huán)境的特性。文獻(xiàn)[11]提出一種基于最短路徑的性能感知服務(wù)路徑選擇方法，綜合了微服務(wù)實(shí)例的計算能力和微服務(wù)實(shí)例之間的傳輸條件以及任務(wù)特性，提高了整體效率，但無法滿足并發(fā)場景。文獻(xiàn)[12]基于帶約束的多服務(wù)選擇的基本模型，將問題轉(zhuǎn)化為一系列等價線性規(guī)劃子問題，提出一種公平感知的并發(fā)服務(wù)選擇算法，通過有限次的線性規(guī)劃迭代，為并發(fā)請求提供目標(biāo)服務(wù)，并獲得更高QoS，但同樣只考慮了簡單結(jié)構(gòu)的服務(wù)請求。文獻(xiàn)[13]基于李雅普諾夫優(yōu)化以及馬爾可夫近似提出一種CSS(Composite Service Selection)框架，在移動環(huán)境下優(yōu)化網(wǎng)絡(luò)服務(wù)的組合，最小化整體組合服務(wù)請求的總體響應(yīng)時間，但沒考慮單個服務(wù)實(shí)例的請求隊列調(diào)度，難以實(shí)現(xiàn)全局優(yōu)化。

基于此，本文提出一種基于優(yōu)先級機(jī)制和改進(jìn)蟻群算法的邊緣微服務(wù)選擇方案，本文的主要貢獻(xiàn)如下：

(1)根據(jù)邊緣計算場景特點(diǎn)，本文結(jié)合微服務(wù)依賴關(guān)系，構(gòu)建基于容器的邊緣微服務(wù)選擇3層架構(gòu)，并基于此建立了時延模型和網(wǎng)絡(luò)資源消耗模型，以求最大化滿足約束時延的請求數(shù)量，并減少網(wǎng)絡(luò)資源消耗。

(2)考慮并發(fā)請求對容器實(shí)例的競爭性，引入優(yōu)先級機(jī)制，利用工作流拓?fù)鋬?yōu)化任務(wù)調(diào)度順序，并采用改進(jìn)蟻群算法的全局優(yōu)化形成最優(yōu)決策。利用真實(shí)的工作流對算法進(jìn)行了評估，與基準(zhǔn)方案相比，本文方案能有效滿足并發(fā)請求QoS。

2 系統(tǒng)模型與問題表述

2.1 系統(tǒng)架構(gòu)

基于容器的微服務(wù)選擇架構(gòu)如圖1所示，該架構(gòu)被劃分為應(yīng)用層、容器實(shí)例層及邊緣節(jié)點(diǎn)層。

應(yīng)用層包含一系列開發(fā)人員以微服務(wù)架構(gòu)開發(fā)的邊緣業(yè)務(wù)，這些業(yè)務(wù)被分解為一組互相依賴的輕量級獨(dú)立微服務(wù)，并遵循工作流的執(zhí)行邏輯，即后驅(qū)微服務(wù)必須等待其所有前驅(qū)微服務(wù)完成并傳遞數(shù)據(jù)才可開始執(zhí)行[14]。依次執(zhí)行該業(yè)務(wù)包含的所有微服務(wù)才視為一次請求的完成。

為避免單個節(jié)點(diǎn)宕機(jī)無法提供可靠服務(wù)，容器實(shí)例層抽象底層物理資源創(chuàng)建容器實(shí)例承載用戶請求。同一業(yè)務(wù)的并發(fā)請求爭用容器實(shí)例，容器實(shí)例同一時刻只能執(zhí)行一個請求，選擇該實(shí)例的其他請求將在該實(shí)例上排隊[15]。當(dāng)現(xiàn)有容器實(shí)例隊列過長無法滿足當(dāng)前并發(fā)請求時延約束時，也可從云中鏡像倉庫下載微服務(wù)基礎(chǔ)鏡像，打包所需編譯器、開發(fā)庫和配置文件等組件創(chuàng)建新的容器實(shí)例擴(kuò)展服務(wù)能力[16]。

邊緣節(jié)點(diǎn)層旨在為用戶提供分布廣泛、快速高效的計算資源。節(jié)點(diǎn)分布在不同的地理區(qū)域，由各類異構(gòu)設(shè)備組成，如無線接入點(diǎn)、網(wǎng)關(guān)或高性能服務(wù)器[17]，擁有不同容量的CPU、內(nèi)存等資源。邊緣節(jié)點(diǎn)內(nèi)嵌容器管理平臺，如docker和LXC，以管理本地容器實(shí)例[18]。

以圖1為例，業(yè)務(wù)1包含的6個微服務(wù)[A,B,C,D,E,F]分別在不同邊緣節(jié)點(diǎn)創(chuàng)建多個容器，當(dāng)用戶對業(yè)務(wù)1發(fā)起請求，經(jīng)過決策為該請求包含的6個微服務(wù)分別選擇[A2,B1,C3,D2,E1,F1]形成完整執(zhí)行路徑。

2.2 系統(tǒng)模型

2.2.1 應(yīng)用模型

2.2.2 邊緣節(jié)點(diǎn)模型

邊緣集群定義為一組PM(Physics Machine)組成的物理網(wǎng)絡(luò)，網(wǎng)絡(luò)中的異構(gòu)服務(wù)器可以抽象為具有不同資源容量的邊緣節(jié)點(diǎn)EN ={EN1,EN2,...,ENN}，E Nn的 資源向量表示為={,,...,}，其中表示E Nn中第r類資源的容量。創(chuàng)建實(shí)例需要保證該節(jié)點(diǎn)的可用資源容量超過實(shí)例的各類資源需求，定義微服務(wù)的資源需求向量為=

2.2.3 時延模型

(1)傳輸時延。對于邊緣環(huán)境中的服務(wù)請求，傳輸時延主要考慮用戶上傳數(shù)據(jù)的時間、選中容器實(shí)例之間的數(shù)據(jù)傳輸時間和返回結(jié)果的時間，用戶上傳數(shù)據(jù)的時延包括端口速率引起的傳輸時延和傳播時延。假設(shè)請求上傳的平均數(shù)據(jù)大小為din，用戶與邊緣節(jié)點(diǎn)的平均帶寬為W，則用戶將輸入數(shù)據(jù)全部上傳到邊緣節(jié)點(diǎn)上的時延表示為

其中，TP代表用戶設(shè)備的傳輸功率，H代表用戶設(shè)備與邊緣節(jié)點(diǎn)的信道增益，δ2代表噪聲功率；D代表用戶設(shè)備與邊緣節(jié)點(diǎn)的物理距離，t ran(EN,U)代表無線信道的傳播速度。而由于邊緣節(jié)點(diǎn)的下行鏈路帶寬通常遠(yuǎn)遠(yuǎn)大于上行鏈路帶寬，且業(yè)務(wù)結(jié)果數(shù)據(jù)量較小，因此忽略返回結(jié)果的時間。

網(wǎng)絡(luò)中的每對邊緣節(jié)點(diǎn)彼此之間通過路由聯(lián)通，很明顯部署在不同節(jié)點(diǎn)上且具有依賴關(guān)系的容器實(shí)例之間數(shù)據(jù)傳輸時間由數(shù)據(jù)傳輸量和傳輸速率決定。

定義二元變量xikn

(2)執(zhí)行時延。本文假設(shè)微服務(wù)處理的數(shù)據(jù)是其所有前驅(qū)微服務(wù)傳輸給它的數(shù)據(jù)之和。一般來說，相同微服務(wù)的不同容器實(shí)例在異構(gòu)服務(wù)器上的執(zhí)行時間與該服務(wù)器的CPU處理速度有關(guān)。假設(shè)容器實(shí)例I(a,i,k)所 在節(jié)點(diǎn)CPU處理速度為，則該實(shí)例上任務(wù)的執(zhí)行時間定義為

(3)排隊時延。容器實(shí)例同時只能執(zhí)行一個請求，容器實(shí)例有一個請求隊列來緩存選擇實(shí)例的任務(wù)，隊列中的這些任務(wù)按順序執(zhí)行。因此，在選擇容器實(shí)例時，需要考慮實(shí)例的請求隊列，如果選擇實(shí)例I(a,i,k)，則必須等待隊列中其他任務(wù)的執(zhí)行，如果隊列中沒有其他任務(wù)，則無需等待，排隊時間=0，否則隊列中所有任務(wù)的排隊時間可以迭代計算為

(4)總時延。每個任務(wù)都必須等到其所有前驅(qū)任務(wù)完成后才能執(zhí)行，任務(wù)本身就緒時間是其所有前驅(qū)任務(wù)的完成時間和前驅(qū)任務(wù)之間的通信時間，計算如下

假設(shè)不消耗其他加載時間，則可以在獲得實(shí)際開始時間后計算實(shí)際完成時間

由于業(yè)務(wù)由具有復(fù)雜拓?fù)浣Y(jié)構(gòu)的微服務(wù)組成，請求的完成時間不是每個任務(wù)的執(zhí)行時間和傳輸時間的簡單累積，而是取決于出口任務(wù)的完成時間，即F Tq=FT()。

2.2.4 網(wǎng)絡(luò)消耗模型

用Dis(ENn1,ENn2)表示兩個節(jié)點(diǎn)之間的最短跳數(shù)，源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間跳數(shù)越多，數(shù)據(jù)將通過更多中間路由傳輸，從而消耗更多的網(wǎng)絡(luò)資源。若是的前驅(qū)任務(wù)，則進(jìn)行數(shù)據(jù)傳輸?shù)木W(wǎng)絡(luò)消耗計算為

此外，創(chuàng)建新容器時從云端下載微服務(wù)鏡像也會造成較大的網(wǎng)絡(luò)資源消耗，假設(shè)選定邊緣節(jié)點(diǎn)與云之間的距離為D is(ENn,cloud) ，為的鏡像數(shù)據(jù)量大小，則創(chuàng)建新容器實(shí)例所消耗的網(wǎng)絡(luò)資源為

綜上，完成一個請求所消耗的網(wǎng)絡(luò)資源為請求的所有任務(wù)之間的數(shù)據(jù)傳輸和新建容器的網(wǎng)絡(luò)消耗之和

其中，c ta,i代 表是否創(chuàng)建新的容器實(shí)例。

2.3 問題描述

基于上述系統(tǒng)模型，本文希望找到一種合理的微服務(wù)容器實(shí)例選擇策略，在考慮任務(wù)依賴性和高度并發(fā)的情況下，最大限度地保證用戶QoS，提高在延遲約束下完成的請求數(shù)量，并減少網(wǎng)絡(luò)資源的消耗。因此，邊緣微服務(wù)選擇問題可以定義為目標(biāo)

約束條件C1和C2表示容器實(shí)例是任務(wù)分配的最小單元，每個任務(wù)只能由一個實(shí)例執(zhí)行；C3表示所選邊緣節(jié)點(diǎn)必須有足夠的資源部署微服務(wù)實(shí)例，如果任一類資源不足，則無法放置容器實(shí)例；C4限制了每個任務(wù)的開始執(zhí)行時間，任務(wù)必須等到其每個前驅(qū)任務(wù)都執(zhí)行完畢，并將所需數(shù)據(jù)傳輸給它，才可開始執(zhí)行。

3 本文算法

本文提出了一種基于優(yōu)先級機(jī)制和改進(jìn)蟻群的微服務(wù)路徑選擇算法(Microservice Selection algorithm based on Priority mechanism and improved Ant Colony, MS-PAC)。傳統(tǒng)蟻群算法的收斂速度較慢，當(dāng)搜索空間較大時，需要很大計算時間?？紤]任務(wù)的緊迫性和容器實(shí)例的競爭性，本文添加任務(wù)優(yōu)先級機(jī)制優(yōu)化任務(wù)調(diào)度隊列，再利用蟻群算法的正反饋機(jī)制尋找全局最優(yōu)解。

3.1 微服務(wù)優(yōu)先級機(jī)制

前驅(qū)任務(wù)的延遲會累計起來影響后續(xù)任務(wù)的開始時間，應(yīng)使任務(wù)都盡可能在其子截止時間內(nèi)完成，然而同一業(yè)務(wù)的并發(fā)請求彼此爭用容器實(shí)例，無法確保任務(wù)始終能分配到最快的容器實(shí)例上執(zhí)行。因此，添加并發(fā)系數(shù)conf代表并發(fā)程度，優(yōu)化傳統(tǒng)工作流任務(wù)截止時間計算公式為

由前文可得任務(wù)的最早開始時間取決于其自身就緒時間和所有容器實(shí)例的最早可用時間，則任務(wù)的最早完成時間(EFT)可以計算為

利用上述任務(wù)的截止時間和最早開始時間來定義任務(wù)的優(yōu)先級hop()

其中， 指從當(dāng)前任務(wù)到退出任務(wù)的路徑上的任務(wù)數(shù)，其值越大，則表示該任務(wù)被延遲后影響的任務(wù)越多，其后續(xù)任務(wù)的執(zhí)行受各種因素影響的風(fēng)險也會越高，有必要盡快為當(dāng)前任務(wù)分配容器實(shí)例，以減少排隊時間。任務(wù)的優(yōu)先級并非一直不變，每有一個任務(wù)被分配，則它的后續(xù)任務(wù)的最早開始時間必然會根據(jù)該任務(wù)的分配結(jié)果動態(tài)變化，并發(fā)系數(shù)也會隨著容器實(shí)例數(shù)量改變而改變，因此優(yōu)先級會隨著任務(wù)分配的過程不斷更新，保證越緊急的任務(wù)優(yōu)先級越高。

3.2 容器部署策略

當(dāng)已部署容器實(shí)例的等待隊列太長，導(dǎo)致任務(wù)最早完成時間超過任務(wù)的截止時間時，需部署新的容器實(shí)例來執(zhí)行任務(wù)。首先考慮邊緣節(jié)點(diǎn)的資源容量，資源不足的節(jié)點(diǎn)無法部署實(shí)例，即需要滿足以下約束

該約束保證了節(jié)點(diǎn)的各類資源滿足創(chuàng)建實(shí)例的需求，滿足約束的邊緣節(jié)點(diǎn)將成為候選節(jié)點(diǎn)。網(wǎng)絡(luò)資源消耗為選取節(jié)點(diǎn)的主要因素，計算候選節(jié)點(diǎn)與部署了的前驅(qū)及后驅(qū)容器實(shí)例的節(jié)點(diǎn)之間的平均網(wǎng)絡(luò)距離

其中，K1表 示的每個前驅(qū)微服務(wù)的實(shí)例數(shù)，K2表示的每個后續(xù)微服務(wù)的實(shí)例數(shù)，選擇平均網(wǎng)絡(luò)距離最小的候選邊緣節(jié)點(diǎn)作為部署新實(shí)例的節(jié)點(diǎn)。

3.3 基于優(yōu)先級機(jī)制和改進(jìn)蟻群的微服務(wù)選擇算法

本文提出一種基于改進(jìn)蟻群算法的微服務(wù)選擇算法MS-PAC，以獲得全局最優(yōu)的微服務(wù)執(zhí)行路徑策略。除了保留基本蟻群算法的隨機(jī)和并行搜索特性之外，為提高搜索過程的收斂性，利用前一節(jié)所述優(yōu)先級機(jī)制優(yōu)化任務(wù)調(diào)度順序。與遺傳算法[19]、粒子群算法[20]等元啟發(fā)式算法相比，改進(jìn)后的蟻群算法采用信息素策略，實(shí)現(xiàn)了不同群體之間的經(jīng)驗(yàn)信息共享。

MS-PAC算法模擬螞蟻的進(jìn)食過程，各個螞蟻通過啟發(fā)式信息和信息素的指導(dǎo)為并發(fā)請求中的任務(wù)選擇容器實(shí)例，保留它們走過的路徑，并選取螞蟻中的最優(yōu)解以保留經(jīng)驗(yàn)，從而在迭代過程中逐漸趨于全局最優(yōu)解。其具體流程如下：

(1)首先必然存在多個沒有前驅(qū)任務(wù)的起點(diǎn)任務(wù)，將這些任務(wù)添加進(jìn)候選列表中，并將螞蟻A ntl隨機(jī)放置在候選列表中的一個任務(wù)上作為起點(diǎn)。

(2) Antl以 概率選擇公式為當(dāng)前任務(wù)選擇一個映射元組,I(a,i,j)> ，即根據(jù)信息素τi,j和啟發(fā)式信息ηi,j，將分配給容器實(shí)例I(a,i,j)或?yàn)槿蝿?wù)創(chuàng)建一個新的容器實(shí)例，之后該任務(wù)將被放入螞蟻禁忌列表T abul中，不再進(jìn)行調(diào)度。

(3)對某個任務(wù)做出調(diào)度后，若該任務(wù)的后驅(qū)任務(wù)中存在所有前驅(qū)任務(wù)都已完成調(diào)度的任務(wù)，則將該任務(wù)將添加到候選列表中。

(4) 更新候選列表中任務(wù)的優(yōu)先級，從優(yōu)先級最高的前Top N任務(wù)中隨機(jī)選擇一個任務(wù)作為Antl下一個任務(wù)，重復(fù)上述過程，直到完成所有任務(wù)的容器實(shí)例分配。

(5)所有螞蟻均完成全部任務(wù)的分配可以視作一次迭代，算法在達(dá)到最大迭代次數(shù)后終止。

蟻群算法的核心為概率選擇和信息素更新，Antl傾向于選擇期望值更高、信息素更多的容器實(shí)例，Antl選 擇p athi,j的概率計算公式表達(dá)為

其中，α和β分別是信息素和啟發(fā)信息的影響因子，反映了它們的相對重要性。α越大，信息素對螞蟻的影響越大，蟻群搜索的隨機(jī)性越小，β越大，螞蟻陷入局部優(yōu)化的可能性越大。

啟發(fā)式信息ηi,j代表螞蟻將任務(wù)分配給容器實(shí)例的期望，根據(jù)本文目標(biāo)，提出了兩類啟發(fā)式信息，第1個目標(biāo)是確保業(yè)務(wù)請求盡可能在約束時延內(nèi)完成。因此，將候選實(shí)例上任務(wù)的實(shí)際完成時間作為衡量容器是否合適的標(biāo)準(zhǔn)之一，定義完成時間的啟發(fā)式信息公式為

第2個目標(biāo)是減少網(wǎng)絡(luò)資源的消耗，定義為代表網(wǎng)絡(luò)資源消耗的啟發(fā)式信息

對于信息素的更新，本文提出一種結(jié)合局部和全局的信息素更新規(guī)則，局部更新通過蒸發(fā)螞蟻?zhàn)哌^的路徑上的信息素，防止螞蟻選擇相同路徑，增加算法的探索能力，防止陷入局部最優(yōu)。全局更新則在所有螞蟻完成微服務(wù)選擇方案后，會根據(jù)目標(biāo)函數(shù)評估當(dāng)前所有方案的質(zhì)量，并選擇其中質(zhì)量最高的方案增加該路徑上的信息素，這可以促進(jìn)螞蟻保留全局最優(yōu)解的經(jīng)驗(yàn)，在下一次迭代中找到更好的路徑。

在選擇一個新的映射元組,I(a,i,j)>后，螞蟻按如下方式進(jìn)行局部信息素更新

其中，ρl為局部信息素蒸發(fā)參數(shù)，且ρl ∈[0,1]，ρl越大，則路徑上剩余的信息素越少。

信息素初始化為任務(wù)數(shù)Q，則全局信息素的更新公式為

其中，ρg為 全局信息素更新參數(shù)，?τij為一次迭代后信息素的增量，Lbest為 迭代中全局最優(yōu)路徑的目標(biāo)函數(shù)值。

4 仿真實(shí)驗(yàn)與對比分析

4.1 仿真參數(shù)設(shè)置

文獻(xiàn)[21]提供了4個基準(zhǔn)工作流：Montage, LIGO,CyberShake和SIPHT，如圖2所示。每個工作流都由DAX文件描述，代表一類業(yè)務(wù)，該文件提供了工作流的詳細(xì)信息，包括任務(wù)名稱、工作負(fù)載、數(shù)據(jù)傳輸量和任務(wù)之間的依賴關(guān)系。微服務(wù)之間的數(shù)據(jù)傳輸量定義為10～15 MB，鏡像大小定義為30～50 MB，任務(wù)的工作量定義為文獻(xiàn)[22]中標(biāo)準(zhǔn)計算服務(wù)的執(zhí)行時間。在本文中業(yè)務(wù)的截止時間設(shè)置為工作流拓?fù)涞年P(guān)鍵路徑中任務(wù)執(zhí)行時間的ψ倍，以確?？梢匀萑桃欢ǖ呐抨爼r間。本文采用批處理請求策略，即假設(shè)在一個調(diào)度周期中所有請求都將同時啟動，并且所有請求都將被調(diào)度，每個調(diào)度周期彼此獨(dú)立。邊緣節(jié)點(diǎn)的CPU內(nèi)核從[8, 16, 32]中隨機(jī)選擇，內(nèi)存從[8, 16, 32] GB中隨機(jī)選擇，磁盤容量從[100, 200, 300, 400] GB中隨機(jī)選擇。邊緣節(jié)點(diǎn)之間的數(shù)據(jù)傳輸速率服從N(3×103, 102)(kB/s)，微服務(wù)CPU需求從[0.1–0.4]選擇，內(nèi)存需求從0.1～0.4 GB選擇，磁盤需求從0.3～0.6 GB選擇。用戶與邊緣節(jié)點(diǎn)平均帶寬W為20 MHz，用戶傳輸功率TP為20 dBm，噪聲功率δ2為2×10–13W，信道增益H=127+30lgd。算法的迭代次數(shù)和螞蟻數(shù)量通過多次實(shí)驗(yàn)選取300和30。實(shí)驗(yàn)中的相關(guān)參數(shù)參照表1，除非另有規(guī)定，否則適用于模擬。

圖2 基準(zhǔn)工作流

表1 仿真參數(shù)設(shè)置

本文使用時延和網(wǎng)絡(luò)資源消耗作為指標(biāo)來衡量本文的方法與其他方法相比的性能。為了驗(yàn)證本文算法的性能優(yōu)越性，選擇貪婪算法和文獻(xiàn)[10]中的MSS(Microservice Service Selection algorithm)算法進(jìn)行比較。貪婪算法由延遲和網(wǎng)絡(luò)資源消耗兩個方面組成，前者會優(yōu)先考慮隊列時間最少的容器，或者創(chuàng)建一個新的容器；后者只在初始容器上分配任務(wù)，從不創(chuàng)建新容器。MSS算法考慮了實(shí)例的共享和競爭，根據(jù)任務(wù)子期限不斷更新任務(wù)的緊迫性，調(diào)整任務(wù)執(zhí)行順序或放棄特定任務(wù)的執(zhí)行，并尋求按時完成更多任務(wù)。

4.2 實(shí)驗(yàn)結(jié)果

(1)對比不同的截止期限。為了驗(yàn)證不同方法在不同的截止日期內(nèi)完成請求的能力，本文將ψ的值從1.0變?yōu)?.0，步長為0.5。向每種應(yīng)用發(fā)起相同次數(shù)的請求，總請求數(shù)量為80。圖3顯示相較于其他策略，本文所提策略能在不同截止期限內(nèi)按時完成較多請求。尤其當(dāng)ψ=3時，4種算法之間存在最明顯的差距。這是因?yàn)楸疚牟呗酝ㄟ^優(yōu)先級機(jī)制優(yōu)先調(diào)度緊急任務(wù)，減少關(guān)鍵任務(wù)的阻塞。圖4顯示隨著ψ的增加，所有策略都降低了創(chuàng)建容器的網(wǎng)絡(luò)資源消耗，與其他算法相比，本文算法在創(chuàng)建新容器時選取網(wǎng)絡(luò)距離較小的邊緣節(jié)點(diǎn)，并且將網(wǎng)絡(luò)資源消耗作為改進(jìn)蟻群的啟發(fā)式信息之一，引導(dǎo)螞蟻向網(wǎng)絡(luò)資源消耗更小的微服務(wù)選擇結(jié)果收斂。

圖3 按時完成請求數(shù)量比較(ψ∈[1.0, 5.0])

圖4 總體網(wǎng)絡(luò)消耗比較(ψ∈[1.0, 5.0])

(2)對比不同請求數(shù)量。為了驗(yàn)證每個方法在不同并發(fā)度下滿足截止期限約束的能力，本文將請求數(shù)量設(shè)置為20到100，步長為20。圖5顯示了不同請求數(shù)量下MS-PAC算法能有效降低時延。其能有效平衡時延和網(wǎng)絡(luò)資源消耗，采用優(yōu)先級機(jī)制優(yōu)化任務(wù)調(diào)度順序，并通過蟻群的自學(xué)習(xí)和正反饋機(jī)制，遏制非關(guān)鍵任務(wù)無限制創(chuàng)建新容器，從而避免擠占后續(xù)任務(wù)創(chuàng)建新容器資源，因此能更合理地實(shí)現(xiàn)任務(wù)到容器的映射以及節(jié)點(diǎn)資源的管理。

圖5 不同請求數(shù)量下平均時延比較

圖6展示了不同請求數(shù)量下網(wǎng)絡(luò)資源的消耗，可以看出，除網(wǎng)絡(luò)資源消耗貪婪算法外，其他3種算法中，MS-PAC在所有情況下均表現(xiàn)最好，通過容器部署策略，盡可能選擇與該容器有最少網(wǎng)絡(luò)資源消耗的邊緣節(jié)點(diǎn)新建容器，同時在為任務(wù)選擇容器實(shí)例時，會將網(wǎng)絡(luò)資源消耗作為啟發(fā)式信息，能在保證時延的基礎(chǔ)上，最大限度地降低網(wǎng)絡(luò)資源消耗。而時延貪婪算法和MSS算法沒有考慮到選擇實(shí)例時的網(wǎng)絡(luò)消耗。

圖6 不同請求數(shù)量下總體網(wǎng)絡(luò)資源消耗

圖7顯示了不同算法在約束期限內(nèi)完成請求的數(shù)量，MS-PAC在所有情況下均表現(xiàn)出良好的性能，尤其是在并發(fā)量高時也能保證較高的按時完成率，這是因?yàn)槠渫ㄟ^優(yōu)先級機(jī)制優(yōu)先安排即將到截止期限的任務(wù)，保證這些任務(wù)盡快執(zhí)行。MSS算法也會計算任務(wù)的緊急度，以安排任務(wù)的執(zhí)行順序，但是它會根據(jù)任務(wù)的子截止日期放棄超時任務(wù)。當(dāng)請求數(shù)量為100時，與貪婪時延和MSS算法相比，本文按時完成的請求數(shù)量分別提高23.1%和8.9%。

圖7 不同請求數(shù)量下按時完成請求數(shù)比較

5 結(jié)束語

復(fù)雜的物聯(lián)網(wǎng)應(yīng)用在資源有限的邊緣節(jié)點(diǎn)以微服務(wù)的形式組合提供服務(wù)，針對高并發(fā)情況下難以選擇合適服務(wù)實(shí)例的問題，本文提出了一種基于微服務(wù)優(yōu)先級和改進(jìn)蟻群的微服務(wù)選擇策略，結(jié)合工作流機(jī)制，提高緊迫任務(wù)優(yōu)先級，利用時延和網(wǎng)絡(luò)成本指引蟻群收斂。通過在基準(zhǔn)工作流上的實(shí)驗(yàn)，本文算法能有效降低時延，在提高按時完成請求率的同時降低網(wǎng)絡(luò)成本。未來的研究將從云端協(xié)同、端端協(xié)同的角度探究如何高效執(zhí)行復(fù)雜的微服務(wù)應(yīng)用。