一種結(jié)合灰狼和FM算法的云端應(yīng)用解構(gòu)方法

姜?jiǎng)P華，孫 鵬，韓 銳

(1.中國科學(xué)院聲學(xué)研究所國家網(wǎng)絡(luò)新媒體工程技術(shù)研究中心，北京 100190； 2.中國科學(xué)院大學(xué)，北京 100049)

0 引 言

隨著物聯(lián)網(wǎng)技術(shù)的飛速發(fā)展，智能終端已廣泛普及至千家萬戶，并時(shí)刻生成海量數(shù)據(jù)。如何高效、即時(shí)地處理這些實(shí)時(shí)數(shù)據(jù)，已成為當(dāng)今網(wǎng)絡(luò)技術(shù)中亟待解決的關(guān)鍵問題[1]。在現(xiàn)有云計(jì)算架構(gòu)中，產(chǎn)生自網(wǎng)絡(luò)邊緣的實(shí)時(shí)數(shù)據(jù)需通過互聯(lián)網(wǎng)傳輸至遠(yuǎn)程云端服務(wù)器集中處理。由于云端和用戶間網(wǎng)絡(luò)結(jié)構(gòu)復(fù)雜、帶寬受限，海量數(shù)據(jù)長距離傳輸會(huì)加重網(wǎng)絡(luò)負(fù)載，造成網(wǎng)絡(luò)擁塞、服務(wù)延遲等問題；同時(shí)終端設(shè)備能耗和用戶隱私安全等問題也不容忽視[2]。因此，傳統(tǒng)的集中式云計(jì)算服務(wù)模式已經(jīng)難以支撐網(wǎng)絡(luò)邊緣海量數(shù)據(jù)的實(shí)時(shí)處理。

為此，中科院提出了海服務(wù)的概念。海(SEA)服務(wù)是一種廣域環(huán)境下的現(xiàn)場(on-site)、彈性(elastic)、自治(autonomous)的網(wǎng)絡(luò)服務(wù)系統(tǒng)，通過將位于網(wǎng)絡(luò)邊緣的設(shè)備資源聚合抽象成服務(wù)平臺(tái)，為用戶提供即時(shí)高效的服務(wù)。當(dāng)用戶發(fā)出請(qǐng)求時(shí)，以接入節(jié)點(diǎn)為中心，利用節(jié)點(diǎn)的自治管理和協(xié)作，構(gòu)建鄰域響應(yīng)集群，從而動(dòng)態(tài)地為實(shí)時(shí)或準(zhǔn)實(shí)時(shí)性服務(wù)請(qǐng)求提供高效響應(yīng)[3]。

海服務(wù)利用靠近請(qǐng)求端的設(shè)備快速處理服務(wù)請(qǐng)求，為終端用戶提供高效、現(xiàn)場的服務(wù)，適合局部數(shù)據(jù)處理和實(shí)時(shí)請(qǐng)求響應(yīng)；而云計(jì)算則基于虛擬化技術(shù)，對(duì)服務(wù)請(qǐng)求實(shí)現(xiàn)時(shí)空弱約束的承載，適合全局?jǐn)?shù)據(jù)匯聚和批量處理[3]。2種服務(wù)系統(tǒng)各有側(cè)重，協(xié)同合作可將全局信息與局部信息分級(jí)處理，為用戶提供多類型、多級(jí)別的服務(wù)，滿足具有多等級(jí)用戶體驗(yàn)和服務(wù)質(zhì)量應(yīng)用的需求。

在海云協(xié)同架構(gòu)中[3]，云端應(yīng)用被解構(gòu)成有依賴關(guān)系的子任務(wù)序列，并部署到海端節(jié)點(diǎn)上，其中解構(gòu)指云端應(yīng)用被拆分成子任務(wù)序列的過程。解構(gòu)得到的子任務(wù)粒度直接決定任務(wù)部署策略的解空間大小，進(jìn)而影響部署后任務(wù)在海端節(jié)點(diǎn)上的總執(zhí)行時(shí)間；同時(shí)由于子任務(wù)間存在依賴關(guān)系，故依賴任務(wù)間的傳輸開銷也會(huì)影響其排隊(duì)等待的時(shí)間，進(jìn)而影響服務(wù)完工時(shí)間。因此需要研究適合海云協(xié)同架構(gòu)的云端應(yīng)用解構(gòu)方法，使解構(gòu)子任務(wù)序列適配海端節(jié)點(diǎn)的資源分布，并盡量減少任務(wù)間的數(shù)據(jù)傳輸量，縮短等待時(shí)延。

1 云端應(yīng)用解構(gòu)

應(yīng)用解構(gòu)的概念最初來源于軟件工程領(lǐng)域中功能模塊“高內(nèi)聚、低耦合”的設(shè)計(jì)思想。在面向服務(wù)架構(gòu)(Service-Oriented Architecture)中，應(yīng)用解構(gòu)的定義是：將復(fù)雜軟件的組件封裝為離散、自治、自由接入的獨(dú)立服務(wù)，從而達(dá)到靈活部署和屏蔽平臺(tái)異構(gòu)的目的[4]。微服務(wù)中，解構(gòu)指將應(yīng)用拆分成不同的微服務(wù)以提高模塊性[5]。在海云協(xié)同架構(gòu)中，應(yīng)用解構(gòu)定義為將云端應(yīng)用拆分成有依賴子任務(wù)序列，以便在海端節(jié)點(diǎn)上部署和執(zhí)行[3]。

現(xiàn)有應(yīng)用解構(gòu)方法主要應(yīng)用于分布式系統(tǒng)部署場景。典型應(yīng)用包括：

1)劃分系統(tǒng)Coign利用中間件層在編譯過程中拆分二進(jìn)制代碼段，實(shí)現(xiàn)應(yīng)用解構(gòu)[6]。

2)分布式計(jì)算引擎Spark采用彈性分布式數(shù)據(jù)集(Resilient Distributed Dataset)設(shè)置各基本操作間的寬窄依賴，進(jìn)而劃分操作對(duì)應(yīng)的執(zhí)行位置[7]。

3)邊緣云計(jì)算范式Clonecloud將移動(dòng)端服務(wù)拆分后遷移至云端[8]，與海云協(xié)同場景中云端應(yīng)用下放至網(wǎng)絡(luò)邊緣有相近之處。首先，Clonecloud根據(jù)預(yù)先設(shè)置的靜態(tài)規(guī)則，從代碼中選出開始拆分和重新合并的切入點(diǎn)；隨后根據(jù)任務(wù)的執(zhí)行流程，在切入點(diǎn)間將代碼拆分成數(shù)段，建立調(diào)用關(guān)系樹；最后將拆分后的子任務(wù)建立成任務(wù)成本圖，將選擇問題轉(zhuǎn)化為圖劃分問題，并采用線性規(guī)劃求解。

上述應(yīng)用解構(gòu)方法各自存在缺陷：Coign的拆分粒度過細(xì)，且需要人工設(shè)置代碼段中斷點(diǎn)；Spark采用的RDD只能實(shí)現(xiàn)粗粒度劃分，且難以劃分異步更新并共享狀態(tài)的批處理應(yīng)用；Clonecloud將終端任務(wù)遷移至云端，沒有考慮云端的計(jì)算、存儲(chǔ)開銷和執(zhí)行時(shí)間；而海云協(xié)同場景中，應(yīng)用是從云端下放到邊緣，終端開銷、能耗和任務(wù)完成時(shí)間不可忽略。此外，現(xiàn)有應(yīng)用解構(gòu)方法主要針對(duì)簡單圖，負(fù)載均衡的定義是子劃分中任務(wù)量相等[9]；而海云協(xié)同場景中云端應(yīng)用屬于有向帶權(quán)圖，且海端節(jié)點(diǎn)異構(gòu)性強(qiáng)、負(fù)載波動(dòng)劇烈，負(fù)載均衡要求子劃分任務(wù)規(guī)模匹配海端節(jié)點(diǎn)資源分布。因此，現(xiàn)有應(yīng)用解構(gòu)方法難以應(yīng)用到海云協(xié)同系統(tǒng)中。

在海云協(xié)同場景中，云端應(yīng)用規(guī)模動(dòng)態(tài)變化，耦合程度高，其功能模塊間的調(diào)用關(guān)系樹需要用有向帶權(quán)圖表示[10]，如圖1所示。其中，頂點(diǎn)權(quán)重表示該模塊對(duì)應(yīng)任務(wù)的完工時(shí)間；有向邊權(quán)重表示模塊間傳輸?shù)臄?shù)據(jù)量。如此，可將應(yīng)用解構(gòu)轉(zhuǎn)化為圖劃分問題，其優(yōu)化目標(biāo)表述如下：

圖1 有向帶權(quán)圖示例

一方面，子劃分中的任務(wù)規(guī)模應(yīng)匹配海端節(jié)點(diǎn)資源分布，即劃分子圖中頂點(diǎn)權(quán)和與資源狀況滿足相同分布，才能保證任務(wù)部署時(shí)有充裕的解空間進(jìn)行尋優(yōu)。其數(shù)學(xué)表述如式(1)所示：

(1)

以子任務(wù)隊(duì)列與分布曲線的相關(guān)系數(shù)表示其匹配程度，數(shù)學(xué)表述如式(2)所示：

min (ρC,R|C:{Vj|vj∈Ci},R:{rk|nk∈Nsea})

(2)

其中，C表示子任務(wù)序列，R表示海端節(jié)點(diǎn)資源序列；相關(guān)系數(shù)ρC,R越大，說明匹配程度越高，越有利于部署過程尋優(yōu)。

另一方面，部署后節(jié)點(diǎn)間通信開銷應(yīng)盡量小，則劃分后子圖間邊割權(quán)和與圖的總邊權(quán)之比、即割權(quán)比最小。其數(shù)學(xué)表述如式(3)所示：

(3)

2 結(jié)合灰狼和FM算法的解構(gòu)方法

作為經(jīng)典的NP-hard問題[11]，圖劃分問題廣泛存在于各種領(lǐng)域，目前業(yè)界的主流算法分別如下：

1)KL/FM算法。KL算法于1970年由Kernighan和Lin提出[12]。其原理是，在初始劃分方案的基礎(chǔ)上，在2個(gè)分區(qū)內(nèi)找出一對(duì)可使劃分邊割減少節(jié)點(diǎn)進(jìn)行交換，并標(biāo)記已互換的節(jié)點(diǎn)，接著從分區(qū)內(nèi)繼續(xù)尋找未被標(biāo)記的節(jié)點(diǎn)對(duì)互換，直至圖內(nèi)所有節(jié)點(diǎn)都被標(biāo)記；隨后以此次迭代得到的劃分作為初始劃分，進(jìn)入下次迭代；重復(fù)迭代直至邊割數(shù)目不再減少。在KL算法基礎(chǔ)上，F(xiàn)iduccia和Mattheyses提出FM算法[13]。每次迭代前，先計(jì)算節(jié)點(diǎn)移動(dòng)后的移動(dòng)收益并排出優(yōu)先級(jí)隊(duì)列；迭代中選擇收益最大的一個(gè)節(jié)點(diǎn)移動(dòng)，并將其從隊(duì)列中刪除。重復(fù)上述過程直至沒有節(jié)點(diǎn)可以移動(dòng)。由于每次只需要移動(dòng)一個(gè)節(jié)點(diǎn)，F(xiàn)M算法的計(jì)算量遠(yuǎn)小于KL算法。

2)多層K路均分算法。該算法分粗化、初始劃分和逆粗化3個(gè)步驟[14]：粗化根據(jù)圖的最大邊覆蓋原則，將圖中相近的點(diǎn)合并為單點(diǎn)。粗化重復(fù)迭代多次，直至粗化圖粒度足夠大。隨后使用其他劃分方法對(duì)最終粗化圖進(jìn)行劃分。最后逆粗化將初始劃分后的粗化圖逐層映射回上層粗化圖，并在各層粗化圖上使用KL/FM等算法對(duì)已形成的劃分進(jìn)行局部優(yōu)化，最終完成對(duì)整個(gè)圖的劃分。

3)啟發(fā)式算法。啟發(fā)式算法參照仿生學(xué)原理設(shè)計(jì)劃分規(guī)則，收斂較快，全局性強(qiáng)，適用于大規(guī)模圖的劃分。Tao等人[15]采用模擬退火算法處理多路圖劃分問題；Farshbaf等人[16]引入遺傳算法，在圖劃分過程中實(shí)現(xiàn)多目標(biāo)優(yōu)化。

然而，上述算法各自存在缺陷：KL/FM算法需要較好的初始劃分、多層K路均分無法處理異構(gòu)邊緣設(shè)備、啟發(fā)式算法不適應(yīng)網(wǎng)絡(luò)邊緣規(guī)模的動(dòng)態(tài)性。因此，需要研究適合海云協(xié)同場景的劃分算法。在諸多啟發(fā)式算法中，灰狼算法(Grey Wolf Optimizer, GWO)以其參數(shù)簡單、快速收斂等優(yōu)點(diǎn)受到廣泛關(guān)注?；依撬惴M狼群的社會(huì)階層和捕獵機(jī)制，將狼群分為α、β、δ和ω這4個(gè)等級(jí)，每頭狼都代表一個(gè)可行解[17]。其中，α狼作為種群頭狼，代表當(dāng)前迭代中種群內(nèi)最優(yōu)解；β狼和δ狼分別代表次優(yōu)解和第3最優(yōu)解。其余可行解用ω狼表示。每次迭代中，ω狼根據(jù)頭狼的引領(lǐng)更新位置，包圍獵物，其數(shù)學(xué)模型表述如式(4)、式(5)所示：

(4)

(5)

(6)

(7)

各頭ω狼的位置更新公式如式(8)所示：

(8)

雖然灰狼算法計(jì)算簡單、求解快速，但仍存在著探索和開發(fā)過程轉(zhuǎn)化不明顯、易陷入局部最優(yōu)的缺陷，不適用于求解圖劃分問題[19]。

灰狼算法全局性好、收斂快，但局部開發(fā)能力弱，易陷入局部最優(yōu)；而FM算法的局部開發(fā)能力強(qiáng)，但性能受初始劃分限制。因此，本文將灰狼算法與FM算法結(jié)合，揚(yáng)長避短，優(yōu)勢互補(bǔ)，提出一種混合算法，其工作流程如圖2所示。

(9)

其中，amax、amin分別表示非線性收斂因子的極大值和極小值，tmax表示最大迭代次數(shù)。相比線性收斂因子，cos 函數(shù)可保證前期的快速收斂，并在算法停滯時(shí)，快速提高隨機(jī)因素權(quán)重，加快初始劃分的生成。

圖2 灰狼-FM混合算法工作流程圖

另一方面，在位置更新公式中，灰狼算法中α狼、β狼、δ狼對(duì)ω狼位置的影響程度均等，限制了算法向當(dāng)前最優(yōu)解收斂的速度[21]。故本文提出一種變權(quán)重位置更新策略，如式(10)所示：

(10)

其中，距離當(dāng)前搜索個(gè)體距離最遠(yuǎn)的頭狼權(quán)重最高。變權(quán)重的位置更新策略，能有效提高算法的收斂速度，并加強(qiáng)算法早期的全局性[22]。

3 仿真實(shí)驗(yàn)

為測試本文提出的灰狼與FM算法結(jié)合的混合算法的性能，本文將混合算法與灰狼算法、FM算法以及基于權(quán)重的軟件模塊劃分方法(Weighted Clustering Algorithm, WCA)進(jìn)行對(duì)比。其中，應(yīng)用的調(diào)用關(guān)系利用源代碼分析工具Doxywizard得到；節(jié)點(diǎn)資源分布方面，由于海端節(jié)點(diǎn)的異構(gòu)性和動(dòng)態(tài)性，在長尾分布、雙峰分布等多種分布模式中隨機(jī)選擇，特征參數(shù)依據(jù)工程經(jīng)驗(yàn)設(shè)置[23]；優(yōu)化指標(biāo)采用相關(guān)系數(shù)和割權(quán)比之差，數(shù)學(xué)表述如式(11)所示：

(11)

圖3表示各算法在500次迭代中適應(yīng)度值的變化對(duì)比。其中，混合算法和灰狼算法明顯優(yōu)于另外2種算法?；旌纤惴ㄔ诔跏茧A段收斂快于灰狼算法，說明改進(jìn)的有效性；混合算法陷入停滯后，將解傳遞給FM算法繼續(xù)開發(fā)，局部跳出能力有所提高，而灰狼算法則陷入停滯；圖4表示各算法的割權(quán)比的對(duì)比。其中，混合算法的割權(quán)比持續(xù)下降，顯著低于另外3種算法，大大降低了通信開銷。

圖3 各算法適應(yīng)度值對(duì)比圖

圖4 各算法割權(quán)比對(duì)比圖

4 結(jié)束語

海云協(xié)同系統(tǒng)中，應(yīng)用解構(gòu)方法嚴(yán)重影響服務(wù)質(zhì)量。對(duì)此，本文提出了一種結(jié)合灰狼和FM算法的混合算法，利用灰狼算法快速收斂的特點(diǎn)和FM算法的局部開發(fā)能力，將灰狼算法的解作為初始劃分輸入到FM算法中。實(shí)驗(yàn)結(jié)果表明，混合算法的效果優(yōu)于現(xiàn)有方法。劃分后子圖中頂點(diǎn)權(quán)和與海端節(jié)點(diǎn)資源分布相匹配，且割權(quán)比明顯降低。說明解構(gòu)子任務(wù)序列適配海端資源，且通信開銷大大減少。