[發(fā)明專利]基于云邊端混合計算模式系統(tǒng)的任務(wù)調(diào)度方法和系統(tǒng)

有效

• 申請?zhí)枺?/td>: 202011201376.0
• 申請日: 2020-11-02
• 公開（公告）號: CN112506644B
• 公開（公告）日: 2022-09-30
• 發(fā)明（設(shè)計）人: 徐健;梁昌勇;顧東曉;趙樹平;陸文星;蔣麗;董駿峰;王彬有;馬一鳴;張馳;邵建芳;王穎
• 申請（專利權(quán)）人: 合肥工業(yè)大學(xué)
• 主分類號: G06F9/50
• 分類號: G06F9/50
• 代理公司: 北京久誠知識產(chǎn)權(quán)代理事務(wù)所(特殊普通合伙) 11542
• 代理人: 余罡

1.一種基于云邊端混合計算模式系統(tǒng)的任務(wù)調(diào)度方法，其特征在于，包括：

S1、獲取云邊端混合計算服務(wù)系統(tǒng)的參數(shù)包；

S2、獲取云邊端混合計算模式系統(tǒng)中的任務(wù)調(diào)度矩陣的約束條件和任務(wù)調(diào)度目標(biāo)，所述任務(wù)調(diào)度矩陣包括業(yè)務(wù)實時計算任務(wù)的卸載執(zhí)行計算設(shè)備調(diào)度決策矩陣和業(yè)務(wù)實時計算任務(wù)與應(yīng)用更新計算任務(wù)在場景內(nèi)中繼邊緣服務(wù)器調(diào)度決策矩陣，所述業(yè)務(wù)實時計算任務(wù)包括單體業(yè)務(wù)實時計算任務(wù)和微服務(wù)型業(yè)務(wù)實時計算任務(wù)；

S3、基于參數(shù)包、任務(wù)調(diào)度矩陣的約束條件和任務(wù)調(diào)度目標(biāo)，采用兩階段優(yōu)化算法獲取云邊端混合計算模式系統(tǒng)中的最佳任務(wù)調(diào)度方案，具體包括：

其中，所述任務(wù)調(diào)度矩陣的約束條件包括：

滿足X和Y都為01矩陣且

BST卸載執(zhí)行計算設(shè)備調(diào)度決策矩陣X應(yīng)遵循BST卸載規(guī)則；

X可以取1的元素個數(shù)對應(yīng)于每個BST依據(jù)卸載規(guī)則可以作為其候選執(zhí)行計算設(shè)備的個數(shù)，Y可以取1的元素個數(shù)對應(yīng)于每個由T發(fā)出到E或者C的BST和AST在場景中所有邊緣服務(wù)器的個數(shù)；

X和Y中取1的元素對應(yīng)的計算設(shè)備j就是BST候選執(zhí)行計算設(shè)備和候選中繼邊緣服務(wù)器；

其中：

BST表示業(yè)務(wù)實時計算任務(wù)，AST表示應(yīng)用更新計算任務(wù)；

X和Y是計算任務(wù)的調(diào)度變量，X表示BST的卸載計算設(shè)備選擇，Y表示BST和AST在計算任務(wù)發(fā)出方計算設(shè)備所在場景內(nèi)中繼邊緣服務(wù)器選擇；

X和Y中的元素和的i,j分別對應(yīng)所在的行和列，或者為1表示計算任務(wù)i選擇計算設(shè)備j來執(zhí)行計算或者進(jìn)行中繼，0表示計算任務(wù)i不在計算單元j上的執(zhí)行計算或進(jìn)行中繼；

所述BST卸載規(guī)則表示T、E、C上產(chǎn)生的BST不卸載到T，BST包括單體業(yè)務(wù)實時計算任務(wù)UBST和微服務(wù)計算任務(wù)MBST，一個在T上產(chǎn)生的微服務(wù)計算任務(wù)MBST被觸發(fā)，會激發(fā)同場景若干個E產(chǎn)生微服務(wù)子任務(wù)MBSST，一個E只產(chǎn)生一個MBSST，當(dāng)執(zhí)行完一個微服務(wù)計算任務(wù)MBST激發(fā)的所有微服務(wù)子任務(wù)MBSST后，通過對所有微服務(wù)子任務(wù)MBSST的結(jié)果耦合，完成微服務(wù)計算任務(wù)MBST；由T、E、C上產(chǎn)生的BST，包括T、E、C上產(chǎn)生的單體業(yè)務(wù)實時計算任務(wù)UBST和由T觸發(fā)的在E上產(chǎn)生的微服務(wù)子任務(wù)MBSST的候選卸載執(zhí)行計算設(shè)備為云邊端混合計算模式系統(tǒng)中所有的E和C；

所述BST的卸載規(guī)則的傳輸類型集合包括7種卸載路徑，所述7種卸載路徑包括：同場景內(nèi)T產(chǎn)生的BST到E的卸載、同場景內(nèi)E產(chǎn)生的BST在E之間的卸載、不同場景內(nèi)E產(chǎn)生的BST在E之間的卸載、E和C產(chǎn)生的BST在E和C之間的卸載、C產(chǎn)生的BST在C之間的卸載、一個場景T上產(chǎn)生的BST經(jīng)過同場景的E再卸載到另一個場景E上、T上產(chǎn)生的BST經(jīng)過同場景的E再卸載到C上；

AST任務(wù)的傳輸類型集合包括8種傳遞路徑，8種傳遞路徑包括：同場景內(nèi)T產(chǎn)生的AST在不同T之間的傳遞、同場景內(nèi)T和E產(chǎn)生的AST在T和E之間的傳遞、T和C產(chǎn)生的AST經(jīng)過與T同場景的E在T和C之間的傳遞、同場景內(nèi)E 產(chǎn)生的AST在不同E之間的傳遞、E和C產(chǎn)生的AST在E和C之間的傳遞、C產(chǎn)生的AST在C之間的傳遞；

7種BST卸載路徑和8種AST傳遞路徑組成四種場景；

S301、獲取兩階段優(yōu)化算法的輸入?yún)?shù)和執(zhí)行參數(shù)，所述輸入?yún)?shù)包括參數(shù)包中的參數(shù)，所述執(zhí)行參數(shù)包括第一階段迭代次數(shù)、第二階段迭代次數(shù)、基因種群大小，轉(zhuǎn)入S302；

S302、初始記錄空間RS為空，整理應(yīng)用更新計算任務(wù)AST傳輸類型集合，轉(zhuǎn)入S303；

S303、依據(jù)業(yè)務(wù)實時計算任務(wù)的卸載執(zhí)行計算設(shè)備調(diào)度決策矩陣X的約束條件隨機(jī)生成BSTpgn個決策矩陣X基因構(gòu)成種群BSTP，轉(zhuǎn)步驟與304；

S304、判斷第一階段X決策矩陣優(yōu)化是否達(dá)到迭代次數(shù)，若是轉(zhuǎn)S328，否則轉(zhuǎn)S305；

S305、對BSTP進(jìn)行交叉和變異操作，得到種群MCBSTP，轉(zhuǎn)S306；

S306、將交叉和變異后的種群MCBSTP加入BSTP中，構(gòu)成MergeBSTP，轉(zhuǎn)S307；

S307、取出MergeBSTP中的第一個基因作為目前計算的基因BSTgene，轉(zhuǎn)S308；

S308、判斷BSTgene是否為MergeBSTP最后一個基因且已經(jīng)獲得其任務(wù)總運行時間，若是轉(zhuǎn)步驟S326，否則轉(zhuǎn)步驟S309；

S309、判斷BSTgene是否在記錄空間RS中，若是轉(zhuǎn)S325，否則轉(zhuǎn)S310；

S310、對BSTgene對應(yīng)的X決策矩陣進(jìn)行解析獲得BST傳輸類型集合，轉(zhuǎn)步驟S311；

S311、融合BSTgene對應(yīng)的BST傳輸類型集合、S302獲得的AST傳輸類型集合以及OC-CT，計算所有計算任務(wù)的計算時間和等待時間，轉(zhuǎn)步驟S312；

S312、取出BSTgene和AST對應(yīng)的四種場景內(nèi)中繼邊緣服務(wù)器選擇的傳輸路徑任務(wù)，分場景依據(jù)業(yè)務(wù)實時計算任務(wù)與應(yīng)用更新計算任務(wù)在場景內(nèi)中繼邊緣服務(wù)器調(diào)度決策矩陣Y的約束條件隨機(jī)生成Linkpgn個決策矩陣Y基因構(gòu)成種群LinkEP，轉(zhuǎn)步驟S313；

S313、判斷第二階段LinkEP進(jìn)化是否達(dá)到迭代次數(shù)且已獲得LinkEP對應(yīng)任務(wù)總運行時間，若是轉(zhuǎn)步驟S323，否則轉(zhuǎn)步驟S314；

S314、對每個場景的LinkEP進(jìn)行交叉和變異操作，得到種群MCLinkEP，轉(zhuǎn)步驟S315；

S315、將交叉和變異后的種群加入對應(yīng)場景的LinkEP中來構(gòu)成相應(yīng)的MergeLinkEP，轉(zhuǎn)步驟S316；

S316、取出MergeLinkEP中的第一個基因作為目前計算的基因BSTgene對應(yīng)下的第二階段場景內(nèi)中繼邊緣服務(wù)器選擇的目標(biāo)基因LinkEgene，轉(zhuǎn)步驟S317；

S317、判斷LinkEgene是否為MergeLinkEP的最后一個基因，并且這個基因?qū)?yīng)的總?cè)蝿?wù)時間已經(jīng)得到計算，那么轉(zhuǎn)步驟S322，否則轉(zhuǎn)步驟S318；

S318、結(jié)合步驟S307得到的BSTgene和步驟S301輸入的AST信息對LinkEgene進(jìn)行解析對LinkEgene進(jìn)行解析獲得四種場景內(nèi)需要選擇中繼E的傳輸路徑，轉(zhuǎn)步驟S319；

S319、結(jié)合參數(shù)包中的OT-CT計算LinkEgene對應(yīng)下的所有計算任務(wù)的傳輸時間，轉(zhuǎn)步驟S320；

S320、綜合BSTgene對應(yīng)的計算時間、等待時間，和BSTgene時LinkEgene對應(yīng)的傳輸時間，獲得在BSTgene和LinkEgene對應(yīng)下的任務(wù)總運行時間和MBST 總運行時間，轉(zhuǎn)步驟S321；

S321、取出MergeLinkEP中的下一個基因賦給LinkEgene，轉(zhuǎn)步驟S317；

S322、依據(jù)任務(wù)總運行時間為適應(yīng)值，采用競標(biāo)賽法對MergeLinkEP進(jìn)行精英保留，留取找那個運行時間最小的LinKEP種群個數(shù)個基因存入LinkEP中，轉(zhuǎn)步驟S313；

S323、將BSTgene的第二階段完成迭代后的對應(yīng)種群LinkEP和總?cè)蝿?wù)運行時間最小對應(yīng)的基因，以及這個基因?qū)?yīng)的總?cè)蝿?wù)運行時間和總MBST運行時間都記入記錄空間RS，轉(zhuǎn)步驟S324；

S324、取出第一階段的迭代種群MergeBSTP中的下一個基因賦給BSTgene，轉(zhuǎn)步驟S308；

S325、將上一次迭代記錄在RS中的BSTgene對應(yīng)的第二階段完成迭代后的對應(yīng)種群LinkEP和對應(yīng)的每個基因的總?cè)蝿?wù)運行時間和總MBST運行時間重新賦給這個基因，轉(zhuǎn)步驟S324；

S326、對MergeBSTP中每個基因?qū)?yīng)的LinkEP種群中最小總?cè)蝿?wù)運行時間和對應(yīng)的MBST任務(wù)時間進(jìn)行快速非支配排序,轉(zhuǎn)步驟S327；

S327、結(jié)合非支配序和擁擠度對MergeBSTP中基因進(jìn)行帕累托選優(yōu)的精英選擇，獲得保留種群賦給BSTP，轉(zhuǎn)步驟S304；

S328、輸出BSTP中非支配序最優(yōu)的帕累托最優(yōu)解。