高晉洲，朱曉娟，張?zhí)旌?，?健，程 璐

(安徽理工大學(xué) 計算機科學(xué)與工程學(xué)院，安徽 淮南 232001)

邊緣計算是指部署在近終端，為智能終端設(shè)備提供數(shù)據(jù)處理服務(wù)的計算模型，彌補了遠程云計算在數(shù)據(jù)處理時效性上的不足[1]。近幾年，邊緣計算在智慧煤礦[2]、智慧醫(yī)療[3-4]及智能交通[5]等場景中得到了廣泛應(yīng)用。部署在特定位置的邊緣服務(wù)器有助于智能工廠進行全面自主監(jiān)測、設(shè)備故障檢測、提高預(yù)警速度，保證工廠安全高效生產(chǎn)。確定待部署邊緣服務(wù)器的數(shù)量和最佳部署位置以及確定邊緣服務(wù)器與智能終端設(shè)備之間的分配連接關(guān)系[6]是邊緣服務(wù)器部署在智能工廠中需要完成的2個關(guān)鍵步驟。其中，確定合理的待部署邊緣服務(wù)器數(shù)量及部署方式，對企業(yè)和服務(wù)商進行邊緣計算規(guī)劃具有重要作用。

目前，邊緣服務(wù)器部署的優(yōu)化目標(biāo)主要包括服務(wù)時延、服務(wù)可靠性以及服務(wù)器間的負載均衡和部署成本。翟立秋[6]采用分簇的思想，提出了一種基于WB-MP算法，通過節(jié)點權(quán)重部署邊緣服務(wù)器的方法，降低了服務(wù)時延。Chen等[7]設(shè)計了K-Clustering算法，以最少的邊緣服務(wù)器數(shù)量滿足了用戶的訪問時延要求。Zeng等[8]運用圖論中的最小支配集，在確保服務(wù)質(zhì)量要求的同時最小化邊緣服務(wù)器數(shù)量。Li等[9]提出將K-means算法與蟻群算法相結(jié)合，建立邊緣服務(wù)器放置優(yōu)化模型，使各服務(wù)器之間達到負載均衡。

當(dāng)前仍然存在的2個問題[10-12]：①缺少對邊緣服務(wù)器部署數(shù)量的研究；②不能動態(tài)考慮在基于全局計算任務(wù)總量與異構(gòu)服務(wù)器計算能力的不同的情況下邊緣服務(wù)器之間的負載均衡。因此，本文提出了一種智能工廠中邊緣服務(wù)器的部署方法，采用數(shù)量決策算法Gap-statistic++算法確定邊緣服務(wù)器數(shù)量；利用Rpack算法進行基于全局異構(gòu)服務(wù)器之間的負載均衡部署，旨在進一步提高數(shù)據(jù)處理的可靠性與實效性。

1 系統(tǒng)模型與問題定義

1.1 系統(tǒng)模型

智能工廠邊緣計算系統(tǒng)包括智能終端設(shè)備、云服務(wù)器、邊緣服務(wù)器。為了便于研究，作出如下假設(shè)：①智能終端設(shè)備和云服務(wù)器已完成部署；②每個智能終端設(shè)備的計算任務(wù)量和數(shù)據(jù)量呈周期性變化。

1)智能終端設(shè)備集合。設(shè)智能工廠中有m臺已部署完成的智能終端設(shè)備，記為集合SD，SD={sd1,sd2,…,sdm}；智能終端設(shè)備的位置記為集合TL，TL={tl1,tl2,…,tlm}；智能終端設(shè)備對其提交的計算任務(wù)能接受的最大等待時間記為集合P，P={p1,p2,…,pm}。為保證系統(tǒng)的健壯性，取集合最大值tmax=max{P}作為系統(tǒng)時間閾值。

2)潛在位置集合。在智能工廠中不是任何位置都具備部署邊緣服務(wù)器的條件，因此需要將邊緣服務(wù)器部署在通過生產(chǎn)工藝得出的潛在位置上[10]。設(shè)有n個潛在位置，記為集合PL，PL={pl1,pl2,…,pln}，n≤m。

3)邊緣服務(wù)器集合。設(shè)有k個待部署邊緣服務(wù)器，記為集合SN，SN={sn1,sn2,…,snk}；邊緣服務(wù)器的計算能力記為集合CP，CP={cp1,cp2,…,cpk}；邊緣服務(wù)器的位置集合記為CL，CL={cl1,cl2,…,clk}，clj∈PL，j≤k，k≤n。

智能工廠邊緣計算系統(tǒng)可以看作是一個由智能終端設(shè)備、邊緣服務(wù)器和云服務(wù)器組成的網(wǎng)絡(luò)，可以用無向圖G=(V,L)表示。其中，V=SD∪SN，表示網(wǎng)絡(luò)無向圖中的智能終端設(shè)備和邊緣服務(wù)器設(shè)備；L表示所有智能終端設(shè)備與邊緣服務(wù)器之間的分配連接[9]。每一個邊緣服務(wù)器負責(zé)其所分配連接的智能終端設(shè)備的計算任務(wù)，當(dāng)其接收的計算任務(wù)過多，而導(dǎo)致計算時間超過tmax時，后續(xù)到達的計算任務(wù)將上傳至遠程云服務(wù)器(云邊協(xié)同)。

1.1.1服務(wù)時延定義

智能工廠邊緣計算系統(tǒng)服務(wù)時延主要包括：邊緣服務(wù)器的計算時延、邊緣服務(wù)器與其所關(guān)聯(lián)終端設(shè)備之間的通信時延。

設(shè)智能工廠生產(chǎn)線的工作周期為T，將工作周期劃分為O個時段，即T={t1,t2,…,to}。智能終端設(shè)備計算量呈周期性變化，在周期T內(nèi)，智能終端設(shè)備sdi在時段j時的計算任務(wù)量記為dij，所有智能終端設(shè)備的計算任務(wù)量矩陣記為DL：

(1)

為了保證邊緣計算系統(tǒng)的健壯性，智能終端設(shè)備sdi的計算任務(wù)量取周期內(nèi)計算任務(wù)量的最大值[10]di，max，di，max=max{dio}。

邊緣服務(wù)器snj的計算負載記為slj：

(2)

式(2)中，Yji為二進制變量，表示邊緣服務(wù)器snj與智能終端設(shè)備sdi的分配關(guān)系。Yji=1表示智能終端設(shè)備sdi上的計算任務(wù)分配到邊緣服務(wù)器snj上；Yji=0則表示不分配。

邊緣服務(wù)器snj的計算時延記為ctj：

(3)

在周期T內(nèi)，智能終端設(shè)備sdi在時段j的數(shù)據(jù)量記為qij，智能終端設(shè)備的數(shù)據(jù)量矩陣記為DA：

(4)

為了保證邊緣計算系統(tǒng)的健壯性，智能終端設(shè)備sdi的數(shù)據(jù)量取周期內(nèi)數(shù)據(jù)量的最大值qi,max，qi,max=max{qio}。

邊緣服務(wù)器snj的通信時延記為ttj：

(5)

(6)

式(5)～(6)中，lji為智能終端設(shè)備sdi與邊緣服務(wù)器snj之間的距離；dave為一跳距離；e為sdi到snj所需跳數(shù)；b為中繼設(shè)備帶寬。

邊緣服務(wù)器snj的服務(wù)時延記為stj：

stj=ttj+ctj

(7)

1.1.2負載均衡定義

負載均衡是用來衡量每個邊緣服務(wù)器的負載與平均邊緣服務(wù)器負載的差異情況，但是對于異構(gòu)邊緣服務(wù)器，系統(tǒng)的負載均衡并不是指每個服務(wù)器負載的計算任務(wù)量趨于相等，而是根據(jù)每個邊緣服務(wù)器計算能力的不同，分配不同的負載，追求整體任務(wù)的完成時間最短。負載均衡標(biāo)準(zhǔn)差記為LB：

(8)

LB的值越小，則每個邊緣服務(wù)器的計算時間與平均計算時間之間的差距越小，整體邊緣服務(wù)器負載越均衡。

1.2 邊緣服務(wù)器部署問題

智能工廠系統(tǒng)中邊緣服務(wù)器的最優(yōu)部署：首先,確定待部署邊緣服務(wù)器的最佳數(shù)量；然后，在n個潛在位置中選取k個目標(biāo)位置放置異構(gòu)邊緣服務(wù)器；最后，完成m個智能終端設(shè)備與k個邊緣服務(wù)器的分配連接，同時滿足一定的約束條件，即在邊緣服務(wù)器部署過程中需要考慮服務(wù)時延、負載均衡和最長容忍時間約束。因此，建立加權(quán)目標(biāo)函數(shù)為：

(9)

(10)

clj∈{pl1,pl2,…，pln},1≤j≤k

(11)

(12)

ω1+ω2=1,0≤ω1≤1，0≤ω2≤1

(13)

式(9)～(13)中，ω1為服務(wù)時延權(quán)重；ω2為負載均衡權(quán)重。式(10)可以確保每個智能終端設(shè)備只能分配給1個邊緣服務(wù)器。式(11)可以確保每個邊緣服務(wù)器均部署在潛在位置上。式(12)可以確保任何一個智能終端設(shè)備所提交的計算任務(wù)均能在tmax時間內(nèi)完成。式(13)表示服務(wù)時延權(quán)重與負載均衡權(quán)重的約束條件。

2 部署算法

2.1最優(yōu)數(shù)量決策算法Gap-statistic++

Gap-statistic算法是一種用于確定聚類個數(shù)的機器學(xué)習(xí)算法，其基本思想是將樣本數(shù)據(jù)集的離散程度與參考數(shù)據(jù)集(等數(shù)量均勻生成)離散程度進行比較，以分類數(shù)為自變量，建立一個比較統(tǒng)計量，通過分析該統(tǒng)計量關(guān)于類數(shù)的變化情況來確定最佳聚類數(shù)量[11]。Gap-statistic算法的基本過程為：假設(shè)樣本數(shù)據(jù)通過K-means算法已經(jīng)被聚類為k(k即邊緣服務(wù)器數(shù)量)個簇類，簇類集合記為C，C={c1,c2,…,ck},nj=|cj|，|cj|表示簇cj內(nèi)節(jié)點個數(shù)。簇cj中所有數(shù)據(jù)點之間距離平方之和Dj可表示為：

(14)

將樣本數(shù)據(jù)集分為k個簇類時，所有簇離散程度的總和Wk可表示為：

(15)

由此定義Gap-statistic算法的Gap值可表示為：

Gapn(k)=En*logWk*-logWk

(16)

式(16)中，Wk*為參考數(shù)據(jù)集分為k個簇時的離散程度總和；En*為logWk*的期望；Gap(k)為參考數(shù)據(jù)集和樣本數(shù)據(jù)集被聚類為k個簇類時的總離散程度之差。

假設(shè)kb是樣本數(shù)據(jù)集的最優(yōu)聚類個數(shù)，參考數(shù)據(jù)的離散程度會隨著k增大而均勻減小，當(dāng)2個數(shù)據(jù)集的總離散程度之差最大時，樣本數(shù)據(jù)集的簇內(nèi)離散程度便達到了相對此時聚類數(shù)的最優(yōu)值，即Gap(kb)取最大值，kb則是樣本數(shù)據(jù)集的最優(yōu)簇類個數(shù)。

由于Gap-statistic是借助K-means算法對數(shù)據(jù)集進行聚類，其對初始簇類中心的選擇是隨機的。這可能會造成局部最優(yōu)現(xiàn)象，導(dǎo)致Gap值出現(xiàn)偏差。本文將原Gap-statistic算法中的K-means算法換成K-means++算法，推導(dǎo)出更加穩(wěn)定的Gap-statistic++算法。

1)K-means++算法步驟為：①在數(shù)據(jù)集中隨機選擇1個樣本點作為第1個簇類中心；②計算樣本中的每1個樣本點與第1個簇類中心點之間的距離，并將其中最遠的點定義為第2個簇類中心點；③以概率進行選擇，將與之前的簇類中心點距離之和最大的點，定義為下一個簇類中心點，重復(fù)上述過程，直到k個簇類中心都被確定；④計算所有樣本點到這k個簇類中心的距離，離哪個簇類中心近就將其歸于哪一類；⑤對每個聚類好的簇重新計算簇質(zhì)心，并將其定義為新的簇類中心，然后回到④，直到簇類中心不變。

2.2部署算法Rpack

在部署邊緣服務(wù)器時Rpack算法分為2部分。第1部分是運用K-means++得出初始部署，具體過程為：①隨機選擇一個智能終端設(shè)備位置作為第1個邊緣服務(wù)器預(yù)定位置，將距離第1個預(yù)定位置最遠的智能終端設(shè)備位置作為第2個邊緣服務(wù)器預(yù)定位置，第3個邊緣服務(wù)器預(yù)定位置為距離前2個預(yù)定點距離和最大，依次迭代k次得出k個邊緣服務(wù)器預(yù)定位置；②計算所有剩余未被定義為邊緣服務(wù)器預(yù)定位置的智能終端設(shè)備到k個預(yù)定位置的歐式距離，將所有智能終端設(shè)備歸類到距離其最近的邊緣服務(wù)器預(yù)定位置所在的簇內(nèi)；③計算每個簇的質(zhì)心，并將其定義為新的邊緣服務(wù)器預(yù)定位置；④循環(huán)執(zhí)行②和③，直到預(yù)定位置不變，得到k個簇類。

第2部分是對上一部分所得初始部署結(jié)果進行簇與邊緣服務(wù)器的匹配,基于最小化目標(biāo)函數(shù)進行最終部署。具體過程為：①以計算時延為權(quán)重，將初始部署所得簇集合C與邊緣服務(wù)器集合SN構(gòu)建有權(quán)二分圖，運用匈牙利算法求得基于計算時延最小化的簇與邊緣服務(wù)器之間的最小匹配；②對第1部分所得的智能終端設(shè)備sdi與邊緣服務(wù)器snj的分配連接關(guān)系Yji進行基于目標(biāo)函數(shù)最小化的重新賦值；③對第1部分所得邊緣服務(wù)器預(yù)定位置集合CL基于最小化目標(biāo)函數(shù)進行重新定位；④根據(jù)分配連接關(guān)系Yji和邊緣服務(wù)器位置集合CL值計算目標(biāo)函數(shù)值，并與初始部署得到的目標(biāo)函數(shù)值進行比較，如果所得目標(biāo)函數(shù)值小于初始部署的目標(biāo)函數(shù)值，則結(jié)束計算。

3 實驗與性能評估

3.1 參數(shù)設(shè)置

仿真平臺配置為Intel i7，CPU為3.3 GHz，內(nèi)存為16 G。利用MATLAB R2016a軟件對本文所提出的Rpack算法進行測試。仿真參數(shù)見表1。

表1 仿真參數(shù)

3.2 實驗對比分析

為評估Rpack算法在邊緣服務(wù)器部署中的性能，分別從負載均衡和服務(wù)時延2個方面與KMP策略[12]和pack算法進行對比實驗[13]。每組進行50次，取均值作為最終值。

KMP策略：將終端節(jié)點聚類為k類，取其質(zhì)心作為邊緣服務(wù)器部署位置，每個終端節(jié)點分配連接到離其最近的邊緣服務(wù)器上。

pack算法：將邊緣服務(wù)器放置作為一個容量受限的位置分配問題，以最小化邊緣服務(wù)器與其關(guān)聯(lián)的終端節(jié)點之間的距離和邊緣服務(wù)器之間的負載均衡為目標(biāo),部署邊緣服務(wù)器。

3.2.1負載均衡

實驗生成60個隨機分布的智能終端設(shè)備節(jié)點，通過Gap-statistic++算法得出邊緣服務(wù)器數(shù)量。Gap函數(shù)值如圖1所示。從圖1可以看出，k=5時，Gap值最大，說明需要部署5個位緣服務(wù)器。測試不同部署算法在智能終端設(shè)備計算任務(wù)量增加過程中系統(tǒng)平均負載標(biāo)準(zhǔn)差變化情況。不同算法的負載變化情況如圖2所示。從圖2可以看出，隨著智能終端設(shè)備計算任務(wù)量增加，本算法的負載標(biāo)準(zhǔn)差相較于KMP策略和pack算法更加穩(wěn)定，差值最小。這是因為在邊緣服務(wù)器的部署過程中，KMP策略僅依靠距離進行部署，存在局部最優(yōu)現(xiàn)象。pack算法未考慮異構(gòu)服務(wù)器部署問題和系統(tǒng)中整體邊緣服務(wù)器的負載均衡。而本算法將具備不同計算能力的邊緣服務(wù)器，以最小化所有邊緣服務(wù)器的計算時延標(biāo)準(zhǔn)差為目標(biāo)，與具有不同計算任務(wù)量的簇進行合理配對，使系統(tǒng)達到整體的負載均衡。

圖1 Gap函數(shù)值

圖2 不同算法的負載變化情況

3.2.2服務(wù)時延

服務(wù)時延分別從以下2個方面進行對比。

1)智能終端設(shè)備數(shù)量固定，計算任務(wù)量增加[6]。通過逐步增加智能終端設(shè)備計算任務(wù)量，分別對3種部署算法下系統(tǒng)總服務(wù)時延進行仿真計算。不同計算任務(wù)量下的服務(wù)總時延如圖3所示。從圖3可以看出，隨著智能終端設(shè)備發(fā)送計算任務(wù)量的增加，3種算法的系統(tǒng)總服務(wù)時延都隨之增加。其中，本算法的總服務(wù)時延小于KMP策略和pack算法，這是因為KMP策略負載均衡性差，且缺乏時間閾值tmax限制，當(dāng)計算任務(wù)量增加時，邊緣服務(wù)器的服務(wù)時間會過早達到時間閾值tmax，從而導(dǎo)致大量計算任務(wù)上傳至云中心，增大了系統(tǒng)服務(wù)時間。pack算法未考慮異構(gòu)服務(wù)器的部署策略，僅對單個邊緣服務(wù)器的負載進行負載約束。當(dāng)某個邊緣服務(wù)器負載達到上限后，離它較近的智能終端設(shè)備不得不分配連接到相對較遠的未過載邊緣服務(wù)器上，增加了通信時延。同時,pack算法未設(shè)定時間閾值約束，隨著智能設(shè)備終端設(shè)備計算任務(wù)量增大，邊緣服務(wù)器的服務(wù)時間達到tmax，增大了系統(tǒng)服務(wù)時間。本算法具備更優(yōu)的負載均衡，同時設(shè)定了最長容忍時間約束tmax，避免了智能終端設(shè)備計算任務(wù)上傳到云中心。

圖3 不同計算任務(wù)量下的服務(wù)總時延

2)計算任務(wù)量固定，智能終端設(shè)備數(shù)量增加[6]。運用仿真工具隨機生成不同數(shù)量的智能終端設(shè)備節(jié)點，再運用Gap-statistic++算法得出對應(yīng)所需邊緣服務(wù)器數(shù)量。終端設(shè)備數(shù)與邊緣服務(wù)器數(shù)對應(yīng)情況見表2。逐步增加智能終端設(shè)備數(shù)量，分別對3種部署算法下的系統(tǒng)服務(wù)時延進行仿真計算，得到不同終端數(shù)量下的服務(wù)總時延如圖4所示。從圖4可以看出，隨著智能終端設(shè)備數(shù)量增加，3種算法的服務(wù)時延都在增加，而本算法在數(shù)值波動幅度和數(shù)值大小方面均優(yōu)于KMP策略和pack算法。這是因為KMP策略和pack算法均未進行時間閾值限制，導(dǎo)致系統(tǒng)服務(wù)時延出現(xiàn)不穩(wěn)定的突增。而本算法具備更優(yōu)的負載均衡和時延閾值約束，在智能終端設(shè)備數(shù)量增長的過程中保持服務(wù)時間增長的穩(wěn)定和數(shù)值最小。

表2 終端設(shè)備數(shù)與邊緣服務(wù)器數(shù)對應(yīng)情況 臺

圖4 不同終端數(shù)量下的服務(wù)總時延

4 結(jié)束語

邊緣計算是一種將數(shù)據(jù)處理服務(wù)下沉到網(wǎng)絡(luò)邊緣的一種技術(shù)模式。通過邊緣服務(wù)器的合理部署可以提高智能終端設(shè)備的服務(wù)質(zhì)量。本文把邊緣服務(wù)器的部署問題作為一個多目標(biāo)、多約束的優(yōu)化問題，通過Gap-statistic++算法得出最佳邊緣服務(wù)器數(shù)量，再采用Rpack算法得出邊緣服務(wù)器部署結(jié)果。結(jié)果表明，本算法負載均衡和服務(wù)時延性能指標(biāo)均優(yōu)于KMP部署策略和pack部署算法，具有較高的參考價值。