趙 莉,李君茹

(信陽農(nóng)林學(xué)院 信息工程學(xué)院,河南 信陽 464000)

隨著移動(dòng)通信網(wǎng)的飛速發(fā)展和智能終端的快速普及,云計(jì)算技術(shù)在人們?nèi)粘９ぷ骱蜕钪械玫搅藦V泛的應(yīng)用。人們在云計(jì)算模式下通常會(huì)在不同設(shè)備資源、網(wǎng)絡(luò)和工作場景中變換計(jì)算模式[1]。在上述環(huán)境中,為了完成終端無法完成或未完成的任務(wù),需要在短時(shí)間內(nèi)將任務(wù)遷移到云端平臺(tái)中。任務(wù)遷移指的是在保持任務(wù)運(yùn)行的狀態(tài)下在主機(jī)節(jié)點(diǎn)中將任務(wù)轉(zhuǎn)移到另一個(gè)節(jié)點(diǎn)中,在任務(wù)遷移中任務(wù)分解是最重要的步驟,直接影響著任務(wù)遷移的效果[2]。

王晨旭等[3]對任務(wù)粒度進(jìn)行計(jì)算,在設(shè)計(jì)結(jié)構(gòu)矩陣中分析任務(wù)的分布情況,根據(jù)分析結(jié)果獲得任務(wù)的解耦水平,在動(dòng)態(tài)解耦的基礎(chǔ)上實(shí)現(xiàn)任務(wù)分解,但是該方法無法獲取云計(jì)算任務(wù)之間存在的聯(lián)系,導(dǎo)致網(wǎng)絡(luò)負(fù)載高,任務(wù)分解次數(shù)多。胡亞楠等[4]對激活權(quán)重和激活規(guī)則的不一致性進(jìn)行分析,根據(jù)分析結(jié)果構(gòu)建任務(wù)分解目標(biāo)函數(shù),采用改進(jìn)粒子群優(yōu)化(Modified particle swarm optimization,MPSO)算法對目標(biāo)函數(shù)求解,實(shí)現(xiàn)任務(wù)分解,但是該方法分解任務(wù)所用的時(shí)間較長,進(jìn)而增加了任務(wù)執(zhí)行時(shí)間。

為了解決上述方法中存在的問題,本文提出基于多Agent技術(shù)的云計(jì)算任務(wù)分解方法。首先,采用與或依賴圖分析云計(jì)算任務(wù)之間存在的聯(lián)系,依據(jù)分析結(jié)果采用模糊聚類方法對云計(jì)算任務(wù)進(jìn)行聚類處理;然后,通過多Agent技術(shù)對云計(jì)算任務(wù)進(jìn)行分解,以提高任務(wù)執(zhí)行效率,降低網(wǎng)絡(luò)負(fù)載與任務(wù)分解次數(shù),縮短分解與執(zhí)行時(shí)間;最后,與其它算法進(jìn)行云計(jì)算任務(wù)分解對比實(shí)驗(yàn),以驗(yàn)證本文方法的優(yōu)越性。

1 云計(jì)算任務(wù)分析與處理

用四元組Y=〈L,S,O,H〉表示云計(jì)算任務(wù),其中L描述的是由任務(wù)的中間結(jié)果、初始條件、目標(biāo)、局部數(shù)據(jù)和全局?jǐn)?shù)據(jù)構(gòu)成的知識(shí)集;S代表的是云計(jì)算任務(wù)對應(yīng)的操作集;O代表的是云計(jì)算任務(wù)中初始條件構(gòu)成的集合;H={l1,l2,…,ln} 描述的是目標(biāo)集,里面通常存在一些相關(guān)知識(shí),是知識(shí)集L的子集。

用三元組〈M,E1,E2〉表示操作集對應(yīng)的與或依賴圖。其中,集合M由云計(jì)算任務(wù)的操作構(gòu)成,即節(jié)點(diǎn)集;E1?s×s、E2?s×s均代表的是邊集,其主要作用是描述操作之間存在的依賴關(guān)系;用〈s1|s2〉?E1表示在網(wǎng)絡(luò)中節(jié)點(diǎn)s1與節(jié)點(diǎn)s2之間為或依賴關(guān)系,用〈s1&s2〉?E2表示在網(wǎng)絡(luò)中節(jié)點(diǎn)s1與節(jié)點(diǎn)s2之間為與依賴關(guān)系。

用{si|〈s,si〉E1}表示操作s在網(wǎng)絡(luò)中對應(yīng)的或依賴集,其中E1為或連接邊集,存在于與或依賴圖〈S,E1,E2〉中,其中節(jié)點(diǎn)s、si均存在于集合S中。

用{si|〈s,si〉E2}表示操作s在網(wǎng)絡(luò)中對應(yīng)的與依賴集,其中E2為與連接邊集,存在于與或依賴圖〈S,E1,E2〉中。

針對云計(jì)算任務(wù)Y1=〈L,S,O,H〉進(jìn)行考慮,其中L={l0,l1,l2,…,l11},O={o0,o1,o2,o3,o4},S={s0,s1,s2,s3,s4,s5},不同操作下存在的輸入與輸出信息如下:

(1)s1為輸入信息{l1,l2,l3,l4},輸出信息{l11};

(2)s2為輸入信息{l0,l2,l3,l8,l11},輸出信息{l6};

(3)s3為輸入信息{l0,l1,l3,l8},輸出信息{l7};

(4)s4為輸入信息{l1,l11},輸出信息{l8};

(5)s5為輸入信息{l0,l11},輸出信息{l8}。

根據(jù)上述信息,獲得不同操作在任務(wù)Y1中的與或依賴圖,如圖1所示。

圖1 操作的與或依賴圖

圖1中s0表示整個(gè)任務(wù),與依賴關(guān)系用小段圓弧表示。通過圖1獲得云計(jì)算任務(wù)之間存在的關(guān)系,在此基礎(chǔ)上基于多Agent技術(shù)的云計(jì)算任務(wù)分解方法采用模糊聚類方法[5]對云計(jì)算任務(wù)進(jìn)行聚類處理,具體步驟如下:

(1)根據(jù)云計(jì)算任務(wù)在云環(huán)境中的依賴關(guān)系Wi建立初始化樣本矩陣;

(2)為了消除初始化樣本矩陣中存在的量綱,標(biāo)準(zhǔn)化處理初始化樣本矩陣[6]

(1)

(2)

通過標(biāo)準(zhǔn)化處理壓縮數(shù)據(jù),將其控制在區(qū)間[0,1]內(nèi)。

(3)用tij表示不同云計(jì)算任務(wù)的相似度,其計(jì)算公式如下

(3)

(4)

(5)設(shè)置閾值β,當(dāng)閾值在區(qū)間[0,1]內(nèi)取值時(shí),表示云計(jì)算任務(wù)完成聚類。

2 任務(wù)分解方法

采用多Agent技術(shù)[7,8]對云計(jì)算任務(wù)進(jìn)行分解,分析Agent能力特征,獲取云計(jì)算任務(wù)分解過程中的主要任務(wù),在層次規(guī)范分解法的基礎(chǔ)上完成云計(jì)算任務(wù)的分解。

用Dij表示用戶j對云計(jì)算任務(wù)的滿意度,采用模糊表示法對用戶滿意度進(jìn)行量化處理,將其轉(zhuǎn)變?yōu)閧0,0.25,0.5,0.75,1},其中1表示用戶對云計(jì)算任務(wù)非常滿意,0表示用戶對云計(jì)算任務(wù)非常不滿意[9]。

(5)

將任務(wù)根據(jù)結(jié)構(gòu)和功能進(jìn)行分解,獲得多個(gè)子任務(wù),當(dāng)子任務(wù)無法繼續(xù)分解時(shí),獲得云計(jì)算的最小任務(wù),此時(shí)停止分解任務(wù);如果子任務(wù)還能夠繼續(xù)分解,測評(píng)用戶對云計(jì)算子任務(wù)的滿意度[11],設(shè)置閾值μ,當(dāng)用戶滿意度達(dá)到閾值μ時(shí),停止任務(wù)分解。

在任務(wù)分解過程中,設(shè)置的閾值μ需要滿足下述條件:

(1)當(dāng)sj屬于最小的任務(wù)時(shí),停止對任務(wù)的分解操作,當(dāng)sj不屬于最小的任務(wù)時(shí),測評(píng)用戶對任務(wù)sj的滿意度[12];

(2)當(dāng)si大于閾值μ時(shí),停止對任務(wù)的分解操作,當(dāng)si小于閾值μ時(shí),繼續(xù)分解任務(wù)sj。

采用多Agent技術(shù)對任務(wù)分解時(shí),需要確定任務(wù)的主要內(nèi)容和主要活動(dòng)。根據(jù)活動(dòng)和內(nèi)容的特點(diǎn),對任務(wù)進(jìn)行分解,用Y表示初始任務(wù),存在于網(wǎng)絡(luò)的任務(wù)系統(tǒng)中,即根節(jié)點(diǎn);用Q、A表示中層任務(wù),即分支節(jié)點(diǎn),上層任務(wù)通常由中層任務(wù)構(gòu)成,因利用單一的Agent無法實(shí)現(xiàn)中層任務(wù),因此要繼續(xù)分解中層任務(wù),用Qi、Aj表示簡單任務(wù),該任務(wù)可通過Agent單獨(dú)執(zhí)行,即子節(jié)點(diǎn)。

根據(jù)時(shí)間對任務(wù)中存在的主要活動(dòng)進(jìn)行劃分。如果任務(wù)對時(shí)間順序的要求較高,可以先分析任務(wù)的流程,獲取子任務(wù)。在任務(wù)的任務(wù)樹中包含了較多分支,每個(gè)子節(jié)點(diǎn)在任務(wù)數(shù)中都可以描述1個(gè)簡單的任務(wù),即具體的分解步驟,任務(wù)主要活動(dòng)對應(yīng)的順序可通過分解樹得以體現(xiàn),滿足任務(wù)在分解過程中的時(shí)間要求[13,14]。

根據(jù)任務(wù)功能對任務(wù)的主要內(nèi)容進(jìn)行分解。任務(wù)數(shù)可以體現(xiàn)任務(wù)的主要內(nèi)容,根據(jù)并行的規(guī)則對任務(wù)進(jìn)行執(zhí)行。根據(jù)Agent之間的交互和通信完成任務(wù)的分解,具體步驟如下:

(1)在主要活動(dòng)和主要內(nèi)容的基礎(chǔ)上,根據(jù)任務(wù)自身的特點(diǎn),獲得n個(gè)任務(wù)的子任務(wù)s1,s2,…,sn。

(2)對上述過程獲得的子任務(wù)的完整度進(jìn)行檢查,即子任務(wù)s1,s2,…,sn是否可以表達(dá)原始的任務(wù)。如果可以則運(yùn)行步驟(3),如果不可以則返回步驟(1)。

(3)檢查子任務(wù)s1,s2,…,sn之間是否存在聯(lián)系,即子任務(wù)是否獨(dú)立,執(zhí)行子任務(wù)對其它子任務(wù)的執(zhí)行會(huì)不會(huì)產(chǎn)生影響。如果子任務(wù)之間不存在聯(lián)系,判定任務(wù)獨(dú)立,則運(yùn)行步驟(4),如果子任務(wù)之間存在聯(lián)系,返回步驟(2)。

(4)在執(zhí)行任務(wù)中,對任務(wù)的可行性進(jìn)行檢查,即是否能夠通過單獨(dú)的Agent完成子任務(wù)si。子任務(wù)的可行性對其分解過程的合理性產(chǎn)生直接影響,是子任務(wù)分解過程中的重要步驟[15]。當(dāng)子任務(wù)si中i>0時(shí),則判定子任務(wù)具有可行性,運(yùn)行步驟(5),反之不可行,返回步驟(3)。

(5)確保所有子任務(wù)在分解過程中都有對應(yīng)的Agent執(zhí)行,即對任務(wù)分解的完整性進(jìn)行檢查,如果子任務(wù)完成分解,運(yùn)行步驟(6),如果任務(wù)沒有完全分解,返回步驟(4)。

(6)每個(gè)子任務(wù)通過上述處理后,獲得對應(yīng)的輸出和輸入,并有對應(yīng)的Agent執(zhí)行任務(wù),完成任務(wù)的分解。

基于多Agent技術(shù)的任務(wù)分解方法對任務(wù)分解的具體流程如圖2所示。

圖2 云計(jì)算任務(wù)的分解流程圖

3 實(shí)驗(yàn)與分析

為了驗(yàn)證基于多Agent技術(shù)的云計(jì)算任務(wù)分解方法的整體有效性,本文以云計(jì)算平臺(tái)為實(shí)驗(yàn)對象,環(huán)境為網(wǎng)絡(luò)仿真器2.0(Network simulator 2.0,NS2.0)仿真軟件、Microsoft Windows XP操作系統(tǒng)、Intel(R)Celeron(R)2.6 GHz處理器、16 GB內(nèi)存,進(jìn)行1次仿真實(shí)驗(yàn)測試。設(shè)定實(shí)驗(yàn)參數(shù)為Windows10操作系統(tǒng)、20 min操作時(shí)間、150 Hz工作頻率、JAVA編程語言。

將網(wǎng)絡(luò)負(fù)載、任務(wù)分解次數(shù)、任務(wù)分解時(shí)間和任務(wù)執(zhí)行時(shí)間作為指標(biāo),采用基于多Agent技術(shù)的云計(jì)算任務(wù)分解方法,與文獻(xiàn)[3]和文獻(xiàn)[4]方法進(jìn)行對比測試。

(1)網(wǎng)絡(luò)負(fù)載。

網(wǎng)絡(luò)負(fù)載受任務(wù)分解情況的影響,任務(wù)分解效果越好網(wǎng)絡(luò)負(fù)載越低,本文方法、文獻(xiàn)[3]方法和文獻(xiàn)[4]方法的網(wǎng)絡(luò)負(fù)載情況如圖3所示。

分析圖3可知,在多次云計(jì)算任務(wù)分解測試中,本文方法的網(wǎng)絡(luò)負(fù)載均在104byte以下,文獻(xiàn)[3]方法和文獻(xiàn)[4]方法的網(wǎng)絡(luò)負(fù)載均高于1.5×104byte。對比上述方法的測試結(jié)果可知,本文方法在云計(jì)算任務(wù)分解后的網(wǎng)絡(luò)負(fù)載較低,表明本文方法可高質(zhì)量地完成云計(jì)算任務(wù)的分解。因?yàn)楸疚姆椒▽υ朴?jì)算任務(wù)分解之前,分析了云計(jì)算任務(wù)之間存在的關(guān)系,在分析結(jié)果的基礎(chǔ)上對云計(jì)算任務(wù)進(jìn)行分解,降低了網(wǎng)絡(luò)負(fù)載。

圖3 網(wǎng)絡(luò)負(fù)載情況圖

(2)任務(wù)分解次數(shù)。

采用本文方法、文獻(xiàn)[3]方法和文獻(xiàn)[4]方法對5個(gè)云計(jì)算任務(wù)進(jìn)行分析,對比不同方法所用的分解次數(shù),測試結(jié)果如圖4所示。

圖4 不同方法的任務(wù)分解次數(shù)棒圖

分析圖4可知,對5個(gè)云計(jì)算任務(wù)進(jìn)行分解時(shí),本文方法所用的分解次數(shù)均控制在5次以內(nèi),與文獻(xiàn)[3]方法和文獻(xiàn)[4]方法相比,本文方法對同一個(gè)云計(jì)算任務(wù)進(jìn)行分解時(shí),所用的分解次數(shù)較少,驗(yàn)證了本文方法的有效性。

(3)任務(wù)分解時(shí)間。

采用本文方法、文獻(xiàn)[3]方法和文獻(xiàn)[4]方法對云計(jì)算任務(wù)進(jìn)行分解,對比不同方法分解云計(jì)算任務(wù)所用的時(shí)間,測試結(jié)果如表1所示。

由表1可知,任務(wù)分解時(shí)間與任務(wù)數(shù)量之間呈正比關(guān)系。隨著任務(wù)數(shù)量的增加,本文方法、文獻(xiàn)[3]方法和文獻(xiàn)[4]方法分解任務(wù)所用的時(shí)間不斷增加,但在任務(wù)數(shù)量相同時(shí),本文方法所用的分解時(shí)間均低于文獻(xiàn)[3]方法和文獻(xiàn)[4]方法,表明本文方法可在較短的時(shí)間內(nèi)完成云計(jì)算任務(wù)的分解,具有較高的任務(wù)分解效率。

表1 云計(jì)算任務(wù)分解時(shí)間表

(4)任務(wù)執(zhí)行時(shí)間。

將任務(wù)執(zhí)行時(shí)間作為指標(biāo),采用本文方法、文獻(xiàn)[3]方法和文獻(xiàn)[4]方法對2 000個(gè)以下和2 000個(gè)以上的云計(jì)算任務(wù)量進(jìn)行分解,對比分解后任務(wù)的執(zhí)行時(shí)間,執(zhí)行時(shí)間越短,表明方法越有效,測試結(jié)果如圖5所示。

圖5 任務(wù)執(zhí)行時(shí)間棒圖

通過圖5可知,采用本文方法對2 000個(gè)以下和2 000個(gè)以上的云計(jì)算任務(wù)量進(jìn)行分解后,任務(wù)的執(zhí)行時(shí)間均控制在1 s以內(nèi),遠(yuǎn)遠(yuǎn)低于其他2種方法,因?yàn)楸疚姆椒稍诙虝r(shí)間內(nèi)完成云計(jì)算任務(wù)的分解,進(jìn)而降低了任務(wù)執(zhí)行所用的時(shí)間,驗(yàn)證了本文方法的有效性。

4 結(jié)束語

任務(wù)分解是管理系統(tǒng)研究的重要內(nèi)容,通過任務(wù)分解可以有效減少任務(wù)執(zhí)行時(shí)間、優(yōu)化網(wǎng)絡(luò)資源、提高網(wǎng)絡(luò)工作效率。由于進(jìn)行云計(jì)算任務(wù)分解時(shí),傳統(tǒng)方法分解次數(shù)過高,任務(wù)執(zhí)行時(shí)間較長,且網(wǎng)絡(luò)負(fù)載量較大,故本文采用多Agent技術(shù)對云計(jì)算任務(wù)分解方法展開研究。本文方法根據(jù)云計(jì)算任務(wù)之間存在的聯(lián)系,采用多Agent技術(shù)實(shí)現(xiàn)云計(jì)算任務(wù)的分解,不僅解決了目前方法中存在的問題,還能更快速、精準(zhǔn)地分解云計(jì)算任務(wù)。在后續(xù)研究中,將對本文算法進(jìn)行改進(jìn),縮短運(yùn)算時(shí)間,旨在進(jìn)一步提高云計(jì)算任務(wù)分解效率。