[發(fā)明專利]一種基于蟻群優(yōu)化算法的網(wǎng)絡(luò)編碼環(huán)境下資源優(yōu)化方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201410486183.2
• 申請(qǐng)日: 2014-09-22
• 公開(kāi)（公告）號(hào): CN104219154B
• 公開(kāi)（公告）日: 2017-06-13
• 發(fā)明（設(shè)計(jì)）人: 邢煥來(lái);王詔遠(yuǎn);李天瑞;葉佳;李可
• 申請(qǐng)（專利權(quán)）人: 西南交通大學(xué)
• 主分類號(hào): H04L12/751
• 分類號(hào): H04L12/751;H04L12/757;H04W40/02;H04W40/24
• 代理公司: 成都信博專利代理有限責(zé)任公司51200
• 代理人: 張澎

1.一種基于蟻群優(yōu)化算法的網(wǎng)絡(luò)編碼環(huán)境下資源優(yōu)化方法，構(gòu)造多個(gè)從起點(diǎn)到特定終點(diǎn)滿足數(shù)據(jù)速率的路徑集合，且使編碼節(jié)點(diǎn)盡可能少，以在保證傳輸速率不變的情況下，盡量?jī)?yōu)化網(wǎng)絡(luò)編碼資源，包括如下處理步驟：

步驟1、輸入初始拓?fù)浣Y(jié)構(gòu)G(V,E)，其中包含一個(gè)源節(jié)點(diǎn)S，d個(gè)接收節(jié)點(diǎn)，通過(guò)最大流最小割定理計(jì)算該拓?fù)涞淖畲笏俾蔙；

步驟2、使用圖分解的方法，將輸入網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)上潛在的編碼節(jié)點(diǎn)進(jìn)行分解，使便于判斷數(shù)據(jù)在潛在編碼節(jié)點(diǎn)中的傳輸方式，從而判斷該潛在編碼節(jié)點(diǎn)是否為實(shí)際意義上的編碼節(jié)點(diǎn)；分解后新的拓?fù)浣Y(jié)構(gòu)作為輸入，使蟻群在該拓?fù)浣Y(jié)構(gòu)之上尋找路徑；

步驟3、初始化蟻群信息素矩陣，蟻群其他參數(shù)及迭代次數(shù)I；

步驟4、根據(jù)接收節(jié)點(diǎn)的個(gè)數(shù)d生成d個(gè)螞蟻小組，為每個(gè)小組指定一個(gè)接收節(jié)點(diǎn)，每個(gè)螞蟻小組有R只螞蟻：令螞蟻小組序號(hào)為k，k:＝1；

步驟5、第k個(gè)螞蟻小組構(gòu)建路徑集，令螞蟻的序號(hào)為n，n:＝1；

步驟6、第n只螞蟻構(gòu)建路徑，如果路徑構(gòu)建成功，跳轉(zhuǎn)至步驟7，否則跳轉(zhuǎn)至步驟8；

步驟7、將構(gòu)建好的路徑加入到禁忌表中，以防止同組的螞蟻再選擇該路徑，n＝n+1；如果n<＝R，跳轉(zhuǎn)至步驟6，否則跳轉(zhuǎn)至步驟9；

步驟8、將禁忌表清空，執(zhí)行信息素局部懲罰更新機(jī)制，對(duì)當(dāng)前路徑集中的路徑執(zhí)行起懲罰作用的信息素局部更新策略，以防止不適合的路徑重新被螞蟻選擇；信息素更新后跳轉(zhuǎn)至步驟5，本組螞蟻重新構(gòu)建路徑集；

步驟9、使用本組螞蟻成功構(gòu)建的路徑集進(jìn)行信息素局部更新獎(jiǎng)勵(lì)機(jī)制；使用本組路徑集對(duì)啟發(fā)因子進(jìn)行更新；k＝k+1，如果k<＝d，跳轉(zhuǎn)至步驟5，否則，跳轉(zhuǎn)至步驟10；

步驟10、所有路徑集合并為一個(gè)解決方案；計(jì)算該方案的編碼節(jié)點(diǎn)個(gè)數(shù)，同全局最優(yōu)解比較，優(yōu)于全局最優(yōu)則用當(dāng)前解更新全局最優(yōu)解，并執(zhí)行全局信息素更新操作；I＝I-1，如果I>0，跳轉(zhuǎn)至步驟4，否則，算法結(jié)束，輸出全局最優(yōu)解。

2.根據(jù)權(quán)利要求1所述的基于蟻群優(yōu)化算法的網(wǎng)絡(luò)編碼環(huán)境下資源優(yōu)化方法，其特征在于，在步驟3、步驟6、步驟8、步驟9和步驟10的處理中，每只螞蟻對(duì)應(yīng)一張信息素表，只有不同迭代次數(shù)，相同位置的螞蟻才共享同一張信息素表。

3.根據(jù)權(quán)利要求1所述的基于蟻群優(yōu)化算法的網(wǎng)絡(luò)編碼環(huán)境下資源優(yōu)化方法，其特征在于，在步驟6和步驟9中，將當(dāng)前情況下網(wǎng)絡(luò)拓?fù)渲械倪叡贿x擇的次數(shù)作為啟發(fā)因子；當(dāng)之前的螞蟻小組成功構(gòu)造路徑集之后，對(duì)該路徑集中的每條邊被選次數(shù)屬性加1；每個(gè)潛在編碼節(jié)點(diǎn)只有一條出邊，如果這個(gè)潛在編碼節(jié)點(diǎn)有大于1條的入邊，代表該潛在編碼節(jié)點(diǎn)為實(shí)際編碼節(jié)點(diǎn)；即采用該屬性作為啟發(fā)因子；選盡量大的啟發(fā)因子。

4.根據(jù)權(quán)利要求1所述的基于蟻群優(yōu)化算法的網(wǎng)絡(luò)編碼環(huán)境下資源優(yōu)化的方法，其特征在于，在步驟8與步驟9信息素的局部更新方式中：

信息素局部懲罰更新機(jī)制為防止不適合的路徑重新被螞蟻選擇，更新方式見(jiàn)以下公式：

τ(t_k,n,(i,j))＝τ(t_k,n,(i,j))-Δτ_l

信息素局部獎(jiǎng)勵(lì)更新機(jī)制，該策略對(duì)于被成功構(gòu)建的路徑集起獎(jiǎng)勵(lì)作用；更新方式見(jiàn)以下公式：

τ(t_k,n,(i,j))＝τ(t_k,n,(i,j))+Δτ_l

其中，參數(shù)τ(t_k,n,(i,j))代表路徑(i,j)的信息素，t_k表示接收節(jié)點(diǎn)；Δτ_l取值為1/|V’|，其中|V’|為圖分解后的節(jié)點(diǎn)個(gè)數(shù)。