[發明專利]一種面向關鍵度和時效性的邊緣計算任務調度方法

有效

• 申請號: 201811208098.4
• 申請日: 2018-10-17
• 公開（公告）號: CN109582448B
• 公開（公告）日: 2021-03-16
• 發明（設計）人: 郭成昊;汪亞斌;劉祥;尚小東;于靖;張煜
• 申請（專利權）人: 中國電子科技集團公司第二十八研究所
• 主分類號: G06F9/48
• 分類號: G06F9/48;G06F9/50
• 代理公司: 江蘇圣典律師事務所 32237
• 代理人: 黃振華

1.一種面向關鍵度和時效性的邊緣計算任務調度方法，其特征在于，包括如下步驟：

步驟1，計算任務的任務關鍵度時效性值；

步驟2，根據任務關鍵度時效性值計算任務消耗值；

步驟3，根據運行時數據、任務消耗值和調度策略修改流網絡圖；

步驟4，根據關鍵度和時效性對任務獲取的資源進行合理分配；

步驟1包括如下步驟：

步驟1-1，設任務具有n個不同的關鍵度，記第i個任務的關鍵度為Xi，i取值為1～n，根據如下公式計算第i個任務的相對關鍵度pi：

步驟1-2，根據第i個任務需要完成時間Di確定第i個任務的時效性值di：

步驟1-3，根據如下公式計算第i個任務的關鍵度時效性值wi：

wi＝pi*di；

步驟1-4，通過如下公式對所有任務的關鍵度時效性值進行最小、最大規范：

其中，maxa表示所有任務的關鍵度時效性值中的最大值，mina表示所有任務的關鍵度時效性值中的最小值，new_maxa、new_mina分別表示需要映射到規范化后的最大值和最小值，即把wi值映射到[new_mina,new_maxa]區間中，如果new_mina,new_maxa分別為0和1，即映射到0到1的區間中；

步驟2包括如下步驟：

第i個任務的消耗值wcosti定義為：

其中，W1～Wn代表每一維度的權重，Wn表示第n維度的權重，公式(5)中用cpu、memory分別表示cpu占用率和內存占用率，dn表示其計算機中其余資源的占用率；每一維度的取值范圍規范化為[0,c]，c是一個常數值，對圖進行構造時任務相關消耗賦值為cost(u,v)，任務相關消耗cost(u,v)表示任務由計算節點u調度到v后執行的消耗；

步驟3包括如下步驟：

步驟3-1，把任務調度流網絡，用有向圖G＝(V,E,U,C)表示，其中V是節點集合，節點表示資源供需實體，包括任務需求方和資源供給方；E是邊的集合，表示任務調度到相應機器上進行計算；U表示邊的容量，即為了完成特定任務機器能夠最多供給的資源量；C表示任務調度到特定機器后，運行該任務需要使用的資源消耗；

步驟3-2，尋找由有向圖G中起始點sv到終點tv的所有有向鏈，依次標出每條鏈的最大容量并使用面向關鍵度和時效性的最小消耗函數計算出相應的最小消耗，如果最大容量為0時，則消耗為無窮大，將最大容量為0的邊標記為||，轉步驟3-3；否則，當所有單位費用都為0時，此時，不再存在由sv到tv的有向鏈，不能再進行增廣，此時為最小費用最大流，結束調度；

步驟3-3，對有向圖G進行初始化，使初始可行流為0，選取單位消耗最小的有向鏈，對此條有向鏈進行最大容量的增廣，不再存在由s v到t v的有向鏈時，則不能再進行增廣，結束調度，此時為最小消耗最大流。

2.如權利要求1所述的方法，其特征在于，步驟3-2中，所述面向關鍵度和時效性的最小消耗函數如下：

min∑_(w,v)∈Ewcost(w,v)f(w,v)，

其中wcost(w,v)代表任務調度流網絡中任務從計算節點w調度到計算節點v執行的消耗，f(w,v)表示w到v的任務數量。

3.如權利要求2所述的方法，其特征在于，步驟4包括：

設定任務集合為T，物理資源集合為M，任務調度問題映射為找出從集合T到集合M的邊的集合，使得邊上的消耗最小；

設定任務服務集合1,2…,n分別有資源需求rs1,rs2,…,rsn，設定rs1＝rs2＝…＝rsn，令服務器具有能力rc，任務j的資源ASj計算方法如下：

把ASj按照資源需求從小到大分配給每一個任務，如果分配結束后，有任務的分配資源超過所需資源，則把多余資源繼續按公式(6)分配。

4.如權利要求3所述的方法，其特征在于，步驟4中，為了確定T到M的邊，把任務調度約束描述為如下三元組：

調度約束＝T,R,B，

其中T表示任務，R表示表示任務約束的資源，B表示任務被調度到資源上所獲得的效益，采用效益函數描述調度約束，即：

max∑B (7)

把調度約束轉換為決定是否在圖的不同節點間建立邊的問題，在T和R之間建立一條邊T→R，每條邊會被賦予一個cost值，cost為和效益B相對的值，最大收益函數對應的最小消耗函數如下：

min∑cost (8)。