[發(fā)明專利]面向大規(guī)模時(shí)間敏感網(wǎng)絡(luò)的調(diào)度方法、裝置及電子設(shè)備

有效

• 申請(qǐng)?zhí)枺?/td>: 202010917727.1
• 申請(qǐng)日: 2020-09-03
• 公開（公告）號(hào): CN112054968B
• 公開（公告）日: 2022-04-12
• 發(fā)明（設(shè)計(jì)）人: 郭少勇;金翼;邱雪松;陸繼釗;熊翱;李文萃;亓峰;李永杰;邵蘇杰;舒新建;孟慧平
• 申請(qǐng)（專利權(quán)）人: 北京郵電大學(xué);國網(wǎng)河南省電力公司信息通信公司;國網(wǎng)河南省電力公司;國家電網(wǎng)有限公司
• 主分類號(hào): H04L47/50
• 分類號(hào): H04L47/50;H04L47/6275
• 代理公司: 北京柏杉松知識(shí)產(chǎn)權(quán)代理事務(wù)所(普通合伙) 11413
• 代理人: 丁蕓;馬敬

1.一種面向大規(guī)模時(shí)間敏感網(wǎng)絡(luò)的調(diào)度方法，其特征在于，所述方法包括：

步驟A，針對(duì)每一個(gè)待調(diào)度的時(shí)間觸發(fā)流量，獲取該時(shí)間觸發(fā)流量的傳輸路徑集合；其中，一所述傳輸路徑集合包括至少一條傳輸路徑，每條所述傳輸路徑各自對(duì)應(yīng)有鏈路信息；

步驟B，根據(jù)各所述傳輸路徑集合，將各個(gè)所述時(shí)間觸發(fā)流量進(jìn)行分組，得到觸發(fā)流量組；

步驟C，在各所述觸發(fā)流量組中，選取一個(gè)未調(diào)度的觸發(fā)流量組；

步驟D，針對(duì)當(dāng)前選取的觸發(fā)流量組，根據(jù)時(shí)隙、已獲得的各ILP目標(biāo)函數(shù)，以及當(dāng)前選取的觸發(fā)流量組中各個(gè)時(shí)間觸發(fā)流量的傳輸路徑，建立當(dāng)前選取的觸發(fā)流量組的整數(shù)線性規(guī)劃ILP目標(biāo)函數(shù)，其中，所述時(shí)隙是根據(jù)各所述時(shí)間觸發(fā)流量的傳輸周期確定的；

步驟E，針對(duì)當(dāng)前選取的觸發(fā)流量組，求解該觸發(fā)流量組的ILP目標(biāo)函數(shù)，得到該觸發(fā)流量組中的各個(gè)時(shí)間觸發(fā)流量的目標(biāo)傳輸路徑和目標(biāo)傳輸時(shí)隙；

步驟F，針對(duì)每一時(shí)間觸發(fā)流量，按照該時(shí)間觸發(fā)流量的目標(biāo)傳輸時(shí)隙和該時(shí)間觸發(fā)流量的目標(biāo)傳輸路徑，在目標(biāo)傳輸時(shí)隙將該時(shí)間觸發(fā)流量由源主機(jī)傳輸?shù)侥康闹鳈C(jī)；

步驟G，判斷各所述觸發(fā)流量組是否均調(diào)度完成，若否，則返回上述步驟C繼續(xù)執(zhí)行；

所述根據(jù)各所述傳輸路徑集合，將各個(gè)所述時(shí)間觸發(fā)流量進(jìn)行分組，得到觸發(fā)流量組，包括：

將各個(gè)所述時(shí)間觸發(fā)流量進(jìn)行預(yù)分組，得到多個(gè)預(yù)觸發(fā)流量組方案，其中，一個(gè)所述預(yù)觸發(fā)流量組方案用于將所有的時(shí)間觸發(fā)流量進(jìn)行分組，得到多個(gè)預(yù)觸發(fā)流量組；一個(gè)所述預(yù)觸發(fā)流量組中包括至少一個(gè)所述時(shí)間觸發(fā)流量；

針對(duì)每兩個(gè)時(shí)間觸發(fā)流量，計(jì)算該兩個(gè)時(shí)間觸發(fā)流量的傳輸路徑集合的相似度；

針對(duì)每一預(yù)觸發(fā)流量組方案中的每兩個(gè)預(yù)觸發(fā)流量組，根據(jù)該兩個(gè)預(yù)觸發(fā)流量組中的特定兩個(gè)時(shí)間觸發(fā)流量的傳輸路徑集合的相似度，計(jì)算該兩個(gè)預(yù)觸發(fā)流量組的第一相似度；所述特定兩個(gè)時(shí)間觸發(fā)流量分別屬于不同的預(yù)觸發(fā)流量組；

針對(duì)每一預(yù)觸發(fā)流量組方案，根據(jù)所述第一相似度計(jì)算該預(yù)觸發(fā)流量組方案的相似度；所述預(yù)觸發(fā)流量組方案的相似度與各個(gè)所述第一相似度成正比，在所述預(yù)觸發(fā)流量組方案的相似度的最小時(shí)，該預(yù)觸發(fā)流量組方案中的預(yù)觸發(fā)流量組為觸發(fā)流量組；

根據(jù)以下公式計(jì)算每兩個(gè)時(shí)間觸發(fā)流量的傳輸路徑集合的相似度；

其中，f_i和f_j表示時(shí)間觸發(fā)流量；表示f_i的傳輸路徑集合，表示f_j的傳輸路徑集合；p_m為f_i的傳輸路徑集合中的一條路徑；p_n為f_j的傳輸路徑集合中的一條路徑；w(f_i,f_j)表征時(shí)間觸發(fā)流量f_i和時(shí)間觸發(fā)流量f_j的傳輸路徑集的相似度；

根據(jù)以下公式計(jì)算預(yù)觸發(fā)流量組方案的相似度：

w(G¹,G²...G^max-1,G^max)表征預(yù)觸發(fā)流量組方案的相似度，其中G¹,G²…G^max-1,G^max表征一個(gè)預(yù)觸發(fā)流量組方案中的各個(gè)預(yù)觸發(fā)流量組；當(dāng)w(G¹,G²...G^max-1,G^max)最小時(shí)，G¹,G²…G^max-1,G^max為最終的觸發(fā)流量組；fo是預(yù)觸發(fā)流量組Gⁱ中的任意一個(gè)時(shí)間觸發(fā)流量，f_p是預(yù)觸發(fā)流量組G^j中的任意一個(gè)時(shí)間觸發(fā)流量；

所述ILP目標(biāo)函數(shù)表示為：

其中，G^m表示觸發(fā)流量組；f_i表示觸發(fā)流量組G^m中的時(shí)間觸發(fā)流量，f_i∈G^m；表示時(shí)間觸發(fā)流量f_i從源主機(jī)到目的主機(jī)的傳輸路徑集合；p表示傳輸路徑集合中的路徑，t_i表示時(shí)隙，T為時(shí)隙集合；l表示鏈路，L為鏈路集合；

表示傳輸路徑p與時(shí)隙t_i的映射關(guān)系，當(dāng)在時(shí)隙t_i，存在時(shí)間觸發(fā)流量按照傳輸路徑p進(jìn)行傳輸時(shí)，為1，否則為0；

表示傳輸路徑p與時(shí)間觸發(fā)流量f_i的映射關(guān)系，其中，若存在時(shí)間觸發(fā)流量f_j的傳輸路徑為p，則為1，否則為0；

Y_(p,l)表示傳輸路徑p與鏈路l的映射關(guān)系，其中，若傳輸路徑p包括鏈路l，則Y_(p,l)為1，否則Y_(p,l)為0；

表示鏈路l與時(shí)隙的映射關(guān)系，其中，在時(shí)隙t_i，若已有任一時(shí)間觸發(fā)流量調(diào)度到鏈路l，則為1，否則為0。