[發(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
• 代理人: 張澎

技術(shù)領(lǐng)域

本發(fā)明涉及蟻群優(yōu)化算法在網(wǎng)絡(luò)編碼環(huán)境下編碼節(jié)點(diǎn)資源優(yōu)化的方法，屬于多媒體通信與網(wǎng)絡(luò)傳輸技術(shù)領(lǐng)域。

背景技術(shù)

傳統(tǒng)的網(wǎng)絡(luò)傳輸中節(jié)點(diǎn)對(duì)接收到的數(shù)據(jù)流不會(huì)做任何操作，數(shù)據(jù)傳輸采用存儲(chǔ)/轉(zhuǎn)發(fā)的方式進(jìn)行。然而，采用這種方式并不能保證多播速率能達(dá)到最大流最小割定理確定的理論上界。2000年，Ahlswede等人首次提出了網(wǎng)絡(luò)編碼的概念，證明在多播網(wǎng)絡(luò)中，利用網(wǎng)絡(luò)編碼技術(shù)，多播速率總能夠達(dá)到最大流最小割定理確定的上限。由于網(wǎng)絡(luò)編碼能夠減少數(shù)據(jù)傳輸次數(shù)，提高網(wǎng)絡(luò)吞吐量和網(wǎng)絡(luò)數(shù)據(jù)傳輸效率，近年來(lái)成為研究領(lǐng)域的一個(gè)熱點(diǎn)。

但在引入網(wǎng)絡(luò)編碼后，節(jié)點(diǎn)需要進(jìn)行額外的編碼操作(在有限域上復(fù)雜的數(shù)學(xué)運(yùn)算)，會(huì)帶來(lái)計(jì)算、存儲(chǔ)等資源的開(kāi)銷。在最初的研究中，網(wǎng)絡(luò)中的所有節(jié)點(diǎn)都被當(dāng)作編碼節(jié)點(diǎn)進(jìn)行編碼操作。隨后有研究指出，并不是所有編碼節(jié)點(diǎn)都一定需要進(jìn)行編碼操作，只需要其中一部分節(jié)點(diǎn)進(jìn)行編碼操作就可以保證最大傳輸速率。這樣，如何在保證網(wǎng)絡(luò)傳輸速率的前提下，盡可能地減少編碼操作，從而減少網(wǎng)絡(luò)編碼帶來(lái)的開(kāi)銷，成為網(wǎng)絡(luò)編碼研究領(lǐng)域中的一個(gè)重要的研究方向，即網(wǎng)絡(luò)編碼資源優(yōu)化(Network Coding Resource Minimization，NCRM)問(wèn)題的提出。

現(xiàn)階段，網(wǎng)絡(luò)編碼資源優(yōu)化方法有如下兩類型：

1、基于貪心算法的方法

C.Fragouli et al.和M.Langberg et al.分別提出兩種基于貪心算法的方法來(lái)解決這個(gè)問(wèn)題，但是貪心算法容易陷入局部最優(yōu)，一次不當(dāng)?shù)倪x擇就可能會(huì)導(dǎo)致非常不理想的結(jié)果。整體來(lái)說(shuō)，優(yōu)化效果并不理想。

2、基于進(jìn)化算法的方法

Kim et al.證明了網(wǎng)絡(luò)編碼資源優(yōu)化問(wèn)題是一個(gè)NP-hard問(wèn)題(也就意味著上述基于貪心算法的方法很難很好地解決本問(wèn)題)，并提出了兩種基于遺傳算法來(lái)解決問(wèn)題的方法。隨后，Xing et al.分別采用量子衍生算法、基于種群的增量學(xué)習(xí)算法、緊湊型遺傳算法和基于路徑編碼的進(jìn)化算法解決網(wǎng)絡(luò)編碼資源優(yōu)化問(wèn)題。國(guó)內(nèi)的學(xué)者鄧亮等以及邵星等也分別用遺傳算法給出了自己的解決方案。這些方法都屬于進(jìn)化算法，眾所周知，進(jìn)化算法是一類基于自然進(jìn)化和選擇的隨機(jī)搜索算法，由于算法模式很少利用到或基本沒(méi)有利用到所解決問(wèn)題本身的一些特性，所以進(jìn)化算法有很強(qiáng)的魯棒性和適應(yīng)性，適用于各種優(yōu)化領(lǐng)域。然而，也正因如此，進(jìn)化算法無(wú)法有效利用到局部信息或問(wèn)題本身的信息，使搜索變得盲目，導(dǎo)致結(jié)果或效率變差。

總體而言，雖然對(duì)于網(wǎng)絡(luò)編碼資源優(yōu)化已經(jīng)出現(xiàn)了多種方法，但在優(yōu)化效果和效率上還不能完全令人滿意，特別是在網(wǎng)絡(luò)應(yīng)用上，對(duì)于時(shí)間和資源的消耗尤為看重。蟻群優(yōu)化算法提出之時(shí)就是用來(lái)解決路徑構(gòu)造問(wèn)題(貨郎擔(dān)問(wèn)題)，該算法可以很好地利用全局信息和局部信息。而網(wǎng)絡(luò)編碼資源優(yōu)化問(wèn)題也可以理解為構(gòu)造多個(gè)從起點(diǎn)到特定終點(diǎn)滿足數(shù)據(jù)速率的路徑集合，且使編碼節(jié)點(diǎn)盡可能少的問(wèn)題。因而，本發(fā)明采用蟻群優(yōu)化算法來(lái)解決該問(wèn)題，旨在從效果和效率上同時(shí)進(jìn)行優(yōu)化。

發(fā)明內(nèi)容

為了克服現(xiàn)有技術(shù)的缺點(diǎn)，本發(fā)明采用蟻群優(yōu)化算法來(lái)解決網(wǎng)絡(luò)編碼資源優(yōu)化的問(wèn)題。

1、首先說(shuō)明使用蟻群優(yōu)化算法解決本問(wèn)題的兩個(gè)基本元素，信息素τ和啟發(fā)因素η的構(gòu)造和維護(hù)：

(1)信息素用來(lái)提供對(duì)蟻群的全局性的指導(dǎo)，所以針對(duì)本問(wèn)題，信息素的值同編碼節(jié)點(diǎn)的個(gè)數(shù)相關(guān)。另外，由于本問(wèn)題的特殊性，網(wǎng)絡(luò)中的一條邊可能被蟻群中的螞蟻選擇一次，多次或者不選，如果使用傳統(tǒng)的單張信息素表，就會(huì)造成信息素的覆蓋，從而無(wú)法明確地對(duì)螞蟻進(jìn)行指導(dǎo)。本發(fā)明針對(duì)此特殊性，采用了一種分布的、多維的信息素維護(hù)方式，每只螞蟻對(duì)應(yīng)一張信息素表，只有不同迭代次數(shù)，相同位置的螞蟻才共享同一張信息素表。

(2)啟發(fā)因子的作用是提供局部指導(dǎo)信息，本發(fā)明提出了一種啟發(fā)因子供螞蟻使用，將當(dāng)前情況下網(wǎng)絡(luò)拓?fù)渲械倪叡贿x擇的次數(shù)作為啟發(fā)因子。當(dāng)之前的螞蟻小組成功構(gòu)造路徑集之后，對(duì)該路徑集中的每條邊被選次數(shù)屬性加1，之后的螞蟻小組中的螞蟻構(gòu)造路徑的時(shí)候就會(huì)參考這個(gè)屬性，由于使用圖分解之后，每個(gè)潛在編碼節(jié)點(diǎn)只有一條出邊，如果這個(gè)潛在編碼節(jié)點(diǎn)有大于1條的入邊，則說(shuō)明該節(jié)點(diǎn)需要編碼，所以螞蟻會(huì)參考這個(gè)屬性作為啟發(fā)因子，選盡量大的啟發(fā)因子，保證當(dāng)前節(jié)點(diǎn)盡量只選擇一條入邊，即保證當(dāng)前節(jié)點(diǎn)盡量不做編碼操作。

本發(fā)明實(shí)現(xiàn)其發(fā)明目的的具體手段是: