[發(fā)明專利]一種基于分布估計(jì)算法的組播虛擬網(wǎng)絡(luò)功能部署方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201810174179.0
• 申請(qǐng)日: 2018-02-27
• 公開（公告）號(hào): CN108400940B
• 公開（公告）日: 2019-11-05
• 發(fā)明（設(shè)計(jì)）人: 邢煥來;王心漢;戴朋林;羅壽西;趙路偉
• 申請(qǐng)（專利權(quán)）人: 西南交通大學(xué)
• 主分類號(hào): H04L12/761
• 分類號(hào): H04L12/761;H04L12/753;H04L12/727;H04L12/24
• 代理公司: 成都盈信專利代理事務(wù)所(普通合伙) 51245
• 代理人: 崔建中

1.一種基于分布估計(jì)算法的組播虛擬網(wǎng)絡(luò)功能部署方法，其特征在于，包括

步驟1：輸入網(wǎng)絡(luò)拓?fù)洌瑯?gòu)建組播樹；

步驟2：初始化分布估計(jì)算法相關(guān)參數(shù)，包括

設(shè)置種群規(guī)模為種群中第i個(gè)個(gè)體為

其中，

D＝{d_j}表示目的節(jié)點(diǎn)集，d_j表示目的節(jié)點(diǎn)，j＝1,2,...,|D|，|D|表示目的節(jié)點(diǎn)個(gè)數(shù)；

VNF＝{f_k}表示數(shù)據(jù)流從源節(jié)點(diǎn)s到達(dá)D中任一個(gè)目的節(jié)點(diǎn)之前必須流經(jīng)的一組虛擬網(wǎng)絡(luò)服務(wù)功能鏈，f_k表示具有某種特定功能的虛擬網(wǎng)絡(luò)功能，k＝1,2,...,|VNF|，|VNF|表示VNF中虛擬網(wǎng)絡(luò)功能的個(gè)數(shù)；

Y_i的元素為個(gè)體編碼，其中，編碼表示在路徑Path_j中部署f_k的節(jié)點(diǎn)位置；

Y_i中第j行稱為第j區(qū)域，第k列稱為第k位置；

設(shè)置最大迭代次數(shù)為迭代次數(shù)τ_EDA＝0；

初始化全局最優(yōu)解集GB與當(dāng)代最優(yōu)解集CB，令|GB|與|CB|分別表示GB與CB中的個(gè)體數(shù)，且1<|GB|,

步驟3：初始化個(gè)體編碼中第1區(qū)域的第1位置的編碼概率矩陣P^ff，其它區(qū)域的第1位置的編碼概率矩陣P^lf，其它位置的編碼概率矩陣Pⁱⁿ；

步驟4：生成分布估計(jì)算法種群，種群中包含個(gè)個(gè)體，其中每個(gè)個(gè)體的生成方法為：由P^ff指導(dǎo)生成第1區(qū)域中的第1位置的編碼，然后根據(jù)此編碼，由P^lf指導(dǎo)生成其它區(qū)域的第1位置的編碼，最后根據(jù)各個(gè)區(qū)域的第1位置的編碼，由Pⁱⁿ指導(dǎo)生成其它位置的編碼；

步驟5：計(jì)算種群中每個(gè)個(gè)體的適應(yīng)度，將適應(yīng)度最優(yōu)的前|CB|個(gè)個(gè)體保留為當(dāng)代最優(yōu)解集CB；合并CB與GB，并按個(gè)體的適應(yīng)度從優(yōu)到劣排序，選取排序后的前|GB|個(gè)最優(yōu)個(gè)體組成GB；所述適應(yīng)度為：采用所述組播樹部署VNF后，從組播源節(jié)點(diǎn)依次經(jīng)過各個(gè)的VNF并最終到達(dá)目的節(jié)點(diǎn)的傳輸時(shí)延總和與傳輸路徑中各VNF的處理時(shí)延總和，取二者之和的平均值作為適應(yīng)度；

步驟6：統(tǒng)計(jì)GB中每個(gè)個(gè)體的第1區(qū)域的第1位置的編碼中各值出現(xiàn)的次數(shù)，更新P^ff；其它區(qū)域的第1位置的編碼中各值出現(xiàn)的次數(shù)，更新P^lf；其它位置的編碼中各值出現(xiàn)的次數(shù)，更新Pⁱⁿ；令τ_EDA＝τ_EDA+1；

步驟7：若則轉(zhuǎn)步驟4；否則，GB中的第1個(gè)個(gè)體即為最優(yōu)解。

2.如權(quán)利要求1所述的基于分布估計(jì)算法的組播虛擬網(wǎng)絡(luò)功能部署方法，其特征在于，所述輸入網(wǎng)絡(luò)拓?fù)洌瑯?gòu)建組播樹，包括以下步驟：

步驟1：輸入網(wǎng)絡(luò)拓?fù)銰＝(V,E)，V和E分別表示節(jié)點(diǎn)集和鏈路集，令G中的鏈路數(shù)為|E|；

步驟2：根據(jù)網(wǎng)絡(luò)組播服務(wù)請(qǐng)求，確定組播源節(jié)點(diǎn)s與目的節(jié)點(diǎn)集D在整個(gè)網(wǎng)絡(luò)中的位置；

步驟3：初始化構(gòu)建組播樹的遺傳算法的相關(guān)參數(shù)，包括

設(shè)置種群規(guī)模種群中每個(gè)個(gè)體是長(zhǎng)度為|E|的二進(jìn)制串；

設(shè)置最大迭代次數(shù)當(dāng)前迭代次數(shù)τ_GA＝0；

設(shè)置交叉概率P_c，變異概率P_m；

初始化歷史最優(yōu)解X_SFB與當(dāng)代最優(yōu)解X_CB；

步驟4：隨機(jī)生成個(gè)長(zhǎng)度為|E|的二進(jìn)制串，每個(gè)二進(jìn)制串為種群中的一個(gè)個(gè)體；其中，第i個(gè)個(gè)體表示一種組播樹方案，為X_i的第j個(gè)位置上的值，j＝1,2,…,|E|；當(dāng)時(shí)，表示X_i中的第j條鏈路被選中，當(dāng)時(shí)，表示X_i中沒有第j條鏈路；

步驟5：計(jì)算種群中每個(gè)個(gè)體的適應(yīng)度，將適應(yīng)度最優(yōu)的個(gè)體作為當(dāng)代最優(yōu)解X_CB保留；所述個(gè)體的適應(yīng)度為該個(gè)體所表示的組播樹方案中從組播源節(jié)點(diǎn)到目的節(jié)點(diǎn)所經(jīng)過的鏈路產(chǎn)生的鏈路時(shí)延的總和的平均值；

步驟6：將種群中每個(gè)個(gè)體的適應(yīng)度依次加入到輪盤中，按其適應(yīng)度優(yōu)劣確定其在輪盤中所占面積的大小，適應(yīng)度優(yōu)的個(gè)體在輪盤中所占的面積大于適應(yīng)度差的個(gè)體，即適應(yīng)度優(yōu)的個(gè)體被選擇的概率高于適應(yīng)度差的個(gè)體；基于輪盤賭方式，隨機(jī)選出個(gè)個(gè)體并放入交配池中；

步驟7：將交配池中的所有個(gè)體以隨機(jī)配對(duì)方式兩兩配對(duì)；對(duì)任意一對(duì)個(gè)體，以交叉概率P_c進(jìn)行兩點(diǎn)交叉，并保存交叉后的新個(gè)體；重復(fù)上述方式，直到生成個(gè)新個(gè)體；以生成的個(gè)新個(gè)體作為當(dāng)前種群替換原種群；

步驟8：以變異概率P_m對(duì)當(dāng)前種群中每個(gè)個(gè)體X_i中的每一位進(jìn)行變異操作；令τ_GA＝τ_GA+1；

步驟9：比較歷史最優(yōu)解X_SFB與當(dāng)代最優(yōu)解X_CB的適應(yīng)度，若X_CB優(yōu)于X_SFB，則使用X_CB替換X_SFB；否則，使用X_SFB替換當(dāng)前種群中適應(yīng)度最差的個(gè)體；

步驟10：若迭代次數(shù)則轉(zhuǎn)到步驟5；否則，以歷史最優(yōu)解X_SFB作為構(gòu)建的組播樹。