一種面向邊緣計算QoE的服務組合及調度方法

簡琤峰,裘科意,張美玉

(浙江工業大學 計算機學院 數字媒體技術研究所,杭州 310023)

1 引 言

全球物聯網和無線網絡的快速發展推動了移動終端和“邊緣計算”的發展,使得網絡邊緣設備的數量迅速增加,從而產生了海量的實時數據.以云計算模型為核心的集中式大數據處理方式,通過將大量的資源集中統一進行管理,并根據用戶的請求動態分配,由于其良好的商業模式得到蓬勃發展.但完全集中化的模式由于在數據傳輸過程中網絡延遲,處理過程中的計算能力限制,能量消耗等缺點,其關鍵技術無法滿足強實時性要求以及大數據量的交互與處理[1-3].在這樣的大環境下,邊緣計算應運而生,它是云計算之后回歸的新興的計算范例.通過將應用、數據和服務從集中式節點推向網絡邊緣,在網絡邊緣處理數據,邊緣計算能夠有效縮短響應時間,提高處理效率并降低網絡壓力,從而滿足實時性要求.傳統的云計算調度往往只從技術角度——服務質量(QoS)來體現性能指標,而在邊緣計算中,我們同樣需要重視用戶的體驗質量(QoE)[4-8].如何在確保網絡邊緣服務質量的(QoS)、提高用戶的體驗質量(QoE)的前提下對資源進行合理的調度是一個值得研究的課題[9-11].

在邊緣計算資源協同與調度問題上,已有一些新興的算法與研究.Yu等人[12]提出了一種聯合調度算法,協調地分配無線和計算資源,能接納更多請求,節能效果顯著.Sardellitti等人[13]將MIMO多單元系統中的多個移動用戶(MU)計算卸載到通用云服務器的問題轉化為無線電資源和計算資源的聯合優化問題,將總體用戶的能耗降至最低,同時滿足延遲約束,并提出了一種基于新穎的連續凸近似技術的迭代算法,收斂到原始非凸問題的局部最優解.Lin等人[14]提出了一種用于MCC任務調度問題的新算法,以在應用完成時間的硬約束下最小化移動設備中的應用的總能量消耗.Kiani等人[15]提出了兩種時間尺度機制來將計算和通信資源分配給MU,制定了二元線性規劃(BLP),旨在最大化服務提供商的利潤和帶寬分配的凸優化問題,設計了啟發式算法來解決BLP問題,并針對帶寬分配問題提出了集中式解決方案.但他們均未考慮在滿足用戶體驗QoE的前提下對網絡邊緣資源進行合理的調度.

針對上述問題,本文采用了一種兩階段的調度模型[16],此模型在保證QoS約束的前提下,根據用戶請求的QoE,篩選有效資源,并進行調度,使得整個服務執行的時間開銷達到最小,從而滿足實時性要求,本質上可規約成一個多目標優化問題.模型的第一階段將用戶QoE映射到QoS參數指標,并為每個服務請求選擇滿足其QoS的最優服務組合;第二階段為調度階段,利用提出的改進的天牛須粒子群算法(BAPSO)求解此問題.此算法將單個個體的天牛須搜索算法拓展至群體,在天牛開始覓食時加入天牛個體對自身歷史最優位置的記憶以及群體歷史最優位置記憶,并在覓食過程中引入動態因子和二階振蕩機制,豐富了天牛群體在移動過程中的搜尋信息,較好地避免了群體陷入局部極值問題.通過matlab仿真證明將該算法應用于此能夠高效地解決大規模的邊緣服務資源的調度和分配問題.

2 兩階段模型描述

2.1 服務組合結構

以用戶的服務請求為驅動的資源調度優化問題可以理解為:如何在滿足用戶QoE的前提下最好地將任務分配給邊緣節點.我們將流處理系統抽象為一個主從結構,邊緣服務器是接收用戶請求和分配任務的主節點,邊緣節點是執行任務的從節點.在了解邊緣節點可提供的資源及用戶的服務請求信息后,將其做最優化最有效的“請求-服務”匹配,并且完成總時間最短這一高效性的要求.

圖1 邊緣服務組合結構Fig.1 Edge service composition structure

2.2 QoE與QoS的映射

相比傳統云計算側重于服務質量(QoS),邊緣計算衡量業務品質的標準更側重于用戶的體驗質量(Quality of Experience,QoE).相對于QoS關心以性能為中心的技術層面,QoE則更加關注用戶使用業務的感受,實現以用戶為中心的管理,它強調從終端用戶的角度來反映QoS.因此需要解決QoE與QoS之間的映射方法.本文采用IQoE2QoS算法[17],使用多指標模糊判定理論,實現用戶體驗質量(QoE)到服務質量(QoS)的映射.

本文采用MOS(Mean Opinion Score)來評價用戶的感知質量[18].在IQoE2QoS算法,首先利用指標統計圖劃分指標的范圍,并離散化指標得到學習集,借助此學習集計算各指標間的權重關系.設指標集為I={I1,I2,…,In},每個指標離散化后得,Ii={ai1,ai2,…,ain}.平均互信息量計算如下:

I(S,Ii)=H(S)-S(S|Ii)

(1)

歸一化后得到指標權重:

(2)

計算當前所有模式應屬于的服務等級,若包含在已有集合中,則判定;若不存在,則對未知模式進行提前模糊歸類.完成上述步驟后更新現有知識表.

IQoE2QoS算法采用機器學習的方法實現從QoS到QoE的映射,采用多指標模糊評價理論,得到QoE到QoS的反映射,并結合信息熵得到各指標同分類信息的互信息量,從而確定各個指標的權重比值.

根據上述方法得到的權重比值,子任務Ti使用對應服務資源Vi的各個QoS屬性度量值的總和如下所示:

(3)

(4)

此外,我們需要將不同的QoS屬性進行規約,即將不同的QoS屬性轉化至相同的度量單位,并解決正向和逆向QoS問題.本文中都轉換為度量[1,50]的數值,考慮的逆向QoS屬性是時間和成本,正向QoS屬性是可靠性與可用性.QoS的計算公式如下,其中max和min是相應QoS屬性的最大值和最小值.

(5)

2.3 調度時間開銷

針對批量服務請求的調度策略主要的優化目標是在滿足使用最優服務組合的條件下減少服務請求任務流執行的總時間.此外,本文還考慮服務切換的時間開銷.將節點提供的服務之間的切換時間記為矩陣logn×n,則logij代表虛擬服務點i到虛擬服務點j的服務切換時間開銷.

數組TimeTablem×n表示m個服務請求和n個服務點的最優邊緣服務組合,記錄了每個服務請求的各個子請求在每個服務點上的時間開銷.其中,TimeTableij表示第j個服務節點對應的邊緣服務sj完成第i號服務請求對應的子請求所花費的時間開銷.

在服務切換時間上,我們需要考慮以下兩種情況:

(6)

(7)

綜上可知,面向批量服務請求的邊緣服務調度問題可以描述為:在邊緣服務資源有限的情況下,確定調度邊緣服務執行服務請求的順序,使得服務請求整體執行時間最少.將為各個服務請求選擇出的最優服務組合的響應時間屬性的度量值存儲在TimeTableij中,并將其采用作為輸入源進行整個過程的最優化調度.

3 改進的天牛須粒子群算法

3.1 算法簡介

天牛須搜索(beetle antennae search,BAS)算法[19]和傳統的啟發式算法相比具有調節參數少、運算量小等優點,但其在高維情況下表現較差,且也容易陷入局部最優.因此,本文以粒子群算法原理為基礎,在算法中加入天牛覓食的特性,將單個個體的天牛須算法拓展成群體算法,并使每個個體擁有對自身歷史位置的最優記憶,使群體擁有群體歷史最優位置記憶.在此基礎上,引入動態因子和二階振蕩機制來調整粒子對兩個最優記憶的學習因子,優化群體覓食時的參數機制.

與單個體的天牛須算法相比,新算法的群體性豐富了天牛移動時位置的多樣性,彌補了單個體容易陷入局部最優的缺陷,提高了算法的全局搜索能力.天牛在迭代的每一步自身都有一個指向最優位置的“速度”,并根據對自身最優位置的記憶及對群體最優位置的記憶進行下一步位置的判斷.與普通粒子群算法的位置更新方式相比,本文算法更容易找到最優解,求解能力更強,所求解質量更高.

3.2 天牛須粒子設計

基于以上特性,本文的天牛須粒子設計如下:

1)粒子擁有左右兩須,且位于質心兩側.假設粒子在第t次迭代時質心的坐標為xt,則其左右兩須的坐標分別為:

(8)

判斷左右兩須的氣味強度大小,并據此計算下一步粒子的質心位置:

(9)

其中,δt表示第t次迭代時的步長,sign()為符號函數.

(10)

其中,rands()表示隨機函數,k表示維度.

3)每個粒子擁有自身歷史最優記憶Pbesti={Pbi_1,Pbi_2…Pbi_m},群體擁有全局最優記憶gbest={gb1,gb2,…,gbm}.

在調度過程中,將一個服務請求進行邏輯劃分后得到m個子請求.此時,服務請求執行的順序即對應天牛須粒子群算法中一個m維的粒子.每個粒子的位置由一個m維向量xi={xi_1,xi_2…xi_m}來表示,xi_j表示個體Pi第j維方向的位置,在服務調度過程中對應于執行邊緣服務請求Tj的順序編號.粒子與服務請求的映射關系如圖2所示.

粒子621435?請求執行次序T1T2T3T4T5T6執行次序編號6rd2st1nd4th3th5th

圖2 粒子個體與服務請求的映射關系
Fig.2 Mapping of particles to service requests

3.3 適應度函數

適應度函數在解決具體問題時具有極其重要的作用,它是具體問題的數學模型在算法中的體現.不同的粒子可以看做是不同的解,而將不同的解代入適應度函數得出對應的適應度函數值,將其與之前的全局最優值對比或者更新.本文處理批量服務請求的模型中,StartTimem×n與EndTimem×n分別表示開始時間矩陣和結束時間矩陣,m和n表示提供的邊緣服務數目以及邊緣服務請求的數目.矩陣PT表示各個服務請求對應的最優邊緣服務的具體執行時間.PTij表示第j個服務點對應的邊緣服務sj完成第i號服務請求對應的子請求所花費的時間.

適應度函數的輸入包括:1)邊緣服務資源的數目；2)邊緣服務請求的數目；3)基于QoS的邊緣服務組合選擇得出的各個服務請求對應的最優服務組合的執行時間矩陣；4)代表解的群體Pi.綜上,一個m維粒子Pi={Pi_1,Pi_2…Pi_m}對應的適應度函數運算過程如下:

fitness(Pi,n,m,pt)

fork=1:n

forl=1:m

ifpt(l,Pi_k)！=0

indexLast1=findlastProNotZero(pt,l,Pi_k);%上一個執行時間不為0的子請求.

StartTime(l,k)=max(EndTime(l-1,k)+log(indexLast1,l),EndTime(l,k-1));

EndTime(l,k)=StartTime(l,k)+pt(l,Pi_k);

else

EndTime(l,k)=EndTime(l-1,k);

EndTime(l,k)=EndTime(l,k);

end

end

fitness(Pi,n,m,pt)=EndTime(k,l)

3.4 天牛須粒子群算法迭代過程

首先,將單個個體拓展為群體,改進后群體的位置更新公式如下:

(11)

如果令：

(12)

則公式(11)可變型為:

(13)

針對天牛須算法和粒子群算法容易陷入局部最優等問題,為加快收斂速度并加強算法的全局搜索能力,在前期研究的基礎上[20],利用二階振蕩方法對公式(12)進行改進,優化群體覓食時的參數機制,改進后的速度更新公式為:

(14)

其中β1=c1r1,β2=c2r2.

(15)

(16)

其中,r3,r4為(0,1)范圍內的隨機數.此外,添加權重因子α1與α2控制三角變換對學習因子c1和c2的影響.

(17)

(18)

綜上所述本文的天牛須粒子群算法流程如下:

Input:Gmax,c1,c2,N;

Output:gbest;

t=0.initialise the population;

initialise related parameters;

for i=1:N

pbesti=xi

end for

gbest=argmaxxifitness(xi)

while(t

update c1,c2 as(17)and(18)

for i=1:N

update viand xias(12)-(14)

if fitness(xi)>fitness(pbseti)

pbesti=xi

end if

end for

gbest=argmaxfitness(pbest)

end while

首次迭代時隨機生成代表一組解的個體Pi,將其位置作為個體的歷史最優并初始化全局最優.隨著迭代的進行,根據適應度函數計算每個個體的適應度值并實時更新兩個最優值.當達到最大迭代次數后,結束算法,最后一個服務請求執行的結束時間就是服務請求執行的總時間.

4 實驗仿真和結果分析

為了驗證本文提出的改進的天牛須粒子群算法(BAPSO)在邊緣計算資源協同與調度模型中的有效性,在matlab上進行仿真實驗.主要運用本文提出的未加入二階振蕩的天牛須粒子群算法(MBAS)和二階振蕩天牛須粒子群算法(BAPSO)以及二階振蕩粒子群算法(MPSO)分別進行對比,為了減少偶然情況對實驗結果的影響,本文在不同問題規模下對相應的算法進行對比,并對每種情況重復進行100次模擬實驗,取平均值和最小值,以此來減小實驗誤差.

實驗中,假設每個子服務的執行時間和服務切換時間范圍是[1,60],單位分鐘.設二階振蕩粒子群算法的慣性因子的值為0.8,天牛須算法的初始步長為3.0,兩須間距離為0.8.為了對比不同的服務請求數目和服務總數情況下的服務請求執行的總時間,我們將實驗分成三個對照組,每組的邊緣服務總數分別是10,20和30.表1-表3是三個對比組的模擬仿真結果, 分別展示了三種算法仿真得到的總時間開銷的平均值和最小值.其中,n代表邊緣服務請求數目,m代表邊緣服務總數.

表1 m=10時不同服務請求數目下3種算法的對比
Table 1 Comparison of three algorithms for different edge service requests when m=10

MPSOMBASBAPSOnmminavgminavgminavg3010158116151542157815371575401018861909186419441853190550102233225521872233215722116010246224942484249924432493701027652811273927712718276180103089311330753094300430729010340934623385344233563436

表2 m=20時不同服務請求數目下3種算法的對比
Table 2 Comparison of three algorithms for different edge service requests when m=20

MPSOMBASBAPSOnmminavgminavgminavg50202914293628422918283028736020313131533085314830373091702034843512346735183458349280204006403939514001389939779020435143844254436742524336100204636469446174691460246881102049464998492550064863494912020535754055281537052535338

表1-表3是二階振蕩粒子群算法和本文提出的兩個新算法解決面向批量服務請求的調度問題得到的總時間開銷情況,是不同服務請求數目和不同邊緣服務總數情況下的實驗仿真結果.從表中可以看出,將天牛須算法拓展成群體算法(MBAS)后,求得的總時間開銷明顯小于粒子群算法,算法效率得到提升,求解質量得到提高.再對算法加入二階振蕩機制,可以看出,相對于前兩種算法,BAPSO在不同規模的服務請求數和邊緣服務總數情況下求得的時間開銷均小于前兩種算法,邊緣服務請求隊列總的執行效率得到進一步提升,且由于采用最優服務組合作為服務調度的輸入源,服務請求執行的質量也得到了提升.

表3 m=30時不同服務請求數目下3種算法的對比
Table 3 Comparison of three algorithms for different edge
service requests when m=30

MPSOMBASBAPSOnmminavgminavgminavg503035683591349035453472353160303813382237713802370837437030442244444374440243384378803046564682459946624559468390305084511050635101504450681003054025425535753795265535111030583658925772584457475822

此外,本文的模型還加入了服務切換時間,隨著服務請求數的增加,問題規模也在逐漸增加.本文提出改進天牛須粒子群調度算法能夠在保持收斂速度的情況下,保持解的質量和穩定性,并具有較強的避免陷入局部最優的能力,說明其能適應大規模的多目標優化問題的求解.篇幅限制,此處隨機選取在邊緣服務請求總數分別為50,70,100三種情況下,三種算法分別求得的總生產時間隨迭代次數的變化趨勢如圖3-圖5所示.

圖3 請求數為50時三種算法的對比Fig.3 Comparison of three algorithms when the number of requests is 50

在圖3中,BAPSO展現出較好的全局探索能力,在快速收斂的前提下較大地提高了解的質量,縮短了調度時的總時間開銷.分析圖4可知,BAPSO在迭代后期陷入局部最優的情況下及時作出調整,跳出了局部最優.在圖5中,在問題規模較大的情況下,粒子群算法較早陷入了局部最優,改進后的MBAS在經過一段時間的停滯后雖及時跳出了局部最優,但進一步改進后的BAPSO算法展現出了更強的求解能力,不斷搜尋更優解,并快速收斂.

圖4 請求數為70時三種算法的的對比Fig.4 Comparison of three algorithms when the number of requests is 70

此外,進行多次實驗,模擬了不同規模下執行BAPSO算法求解邊緣服務中多目標問題所需運算時間,重復多次得出平均值,實驗結果如表4所示.

由表4可知,隨著問題規模的增大,BAPSO的運算時間基本呈線性增加,這保證了算法在求解過程中不會由于問題規模的增大而出現運算時間驟然增大的現象, 而是一個平穩的增加過程.當子任務數在250以內時,BAPSO算法基本能在8秒內找到最優解.子任務數量在500以內時,BAPSO算法的運算時間基本在16秒以內.由實驗結果可知,從算法的計算時間開銷來看,隨著問題規模的增加,BAPSO算法也適用于求解邊緣計算下大規模的資源協同與調度問題.

圖5 請求數為100時三種算法的的對比Fig.5 Comparison of three algorithms when the number of requests is 100

表4 不同問題規模下的算法的運算時間開銷
Table 4 Operation time overhead under different problem scales

服務請求數邊緣服務總數運算時間(/s)150157.0728250257.96743003010.52733503511.34004004012.59374504513.84535005015.15075505516.45986006017.8206

對比粒子群等算法,本文算法不僅保持了個體的獨立性和種群的多樣性,提升了最優解的質量.BAPSO算法在單個體的天牛須搜索算法的基礎上拓展個體數量,引入了二階振蕩環節及對歷史最優位置的記憶,不僅能增強全局搜索能力,豐富種群的多樣性,在迭代過程中出現停滯時,BAPSO可以通過調整自身方向及速度來及時調整整個群體的移動,擴展種群位置的多樣性和優良性,跳出局部最優.通過實驗可以證明,該算法能夠在保證用戶感知的前提下高效地解決大規模的邊緣調度問題,具有較好的應用價值.此外,隨著問題規模的增加,算法的執行時間基本呈線性增長,實驗結果表明算法是高效且可應用的.

5 結 論

在保證用戶體驗質量(QoE)的前提下求解邊緣環境下資源協同及調度問題本質上是一個多目標優化問題,本文采用一種改進天牛須粒子群算法解決該問題.算法將單個個體的天牛須算法拓展至群體,并引入動態因子和二階振蕩機制等改進群體覓食的位置更新時的動態參數機制,豐富了群體移動時的位置多樣性,提升了算法的效率和算法的全局搜索能力.實驗在不同問題規模下運用本文最初改進的天牛須粒子群算法(MBAS)及加入二階振蕩后的BAPSO算法與二階振蕩粒子群算法(MPSO)分別進行對比,說明了BAPSO算法在保證用戶體驗質量(QoE)的前提下能一定程度上提高求解效率及解的質量,并適應較大規模的問題求解,具有一定的實際應用價值.