[發明專利]一種基于Kuhn-Munkres算法的收益率時間相關服務數據包的調度算法

有效

• 申請號: 201710360198.8
• 申請日: 2017-05-22
• 公開（公告）號: CN107241813B
• 公開（公告）日: 2020-04-07
• 發明（設計）人: 高振國;孫鵬;陳丹杰;盧志茂;陳炳才;姚念民
• 申請（專利權）人: 大連理工大學
• 主分類號: H04W72/12
• 分類號: H04W72/12
• 代理公司: 大連理工大學專利中心 21200
• 代理人: 梅洪玉

1.一種基于Kuhn-Munkres算法的收益率時間相關服務數據包的調度算法，特征在于，包括如下步驟：

步驟一，建立服務請求模型；

將服務請求表示為一個五元組：

(G_s,Q_s,D_s,W_s(n),L_s(n)) (3)

其中，每個服務需要被調度的數據包數量為Q_s，其到達時間為G_s，截止時間為D_s，如果該服務的請求在時隙n∈[G_s,D_s]內被調度，那么該請求的每一個數據包將會獲得收益W_s(n)，每個請求s在時隙n內可以被調度數據包的數量上限為L_s(n)；

步驟二，將在線調度問題轉化為加權二分圖，并使用鄰接矩陣存儲；

將待調度請求數據的待分配數據包作為二分圖G(X,Y,E)的一個頂點集合X，已知信息時隙經過微時隙映射后產生的微時隙作為頂點集合Y；當時隙n滿足G_s≤n≤D_s，該請求s的每個數據包與時隙n內的L_s(n)個微時隙相連，即請求s的每個數據包與時隙n有且僅有L_s(n)條邊，且保證該請求s的所有數據包在每個時隙n內連接的微時隙是相同的；該邊的權值為該數據包在該微時隙m中分配能夠獲得收益值W_s(m)；

將轉化后的加權二分圖用鄰接矩陣存儲表示；

步驟三，基于步驟二存儲為鄰接矩陣形式的加權二分圖，利用Kuhn-Munkres算法求解，得到最優匹配。