唐東明，盧顯良

?

用于網(wǎng)絡(luò)編碼優(yōu)化的改進(jìn)量子進(jìn)化算法

唐東明1，盧顯良2

(1. 西南科技大學(xué)信息工程學(xué)院 四川綿陽(yáng) 621010; 2. 電子科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 成都 611731)

網(wǎng)絡(luò)編碼允許網(wǎng)絡(luò)中間節(jié)點(diǎn)對(duì)輸入數(shù)據(jù)進(jìn)行處理而非簡(jiǎn)單轉(zhuǎn)發(fā)，提高了網(wǎng)絡(luò)的吞吐量和魯棒性，已經(jīng)被證明能夠達(dá)到網(wǎng)絡(luò)最大流最小割限制。但網(wǎng)絡(luò)節(jié)點(diǎn)的編碼操作引發(fā)了額外的計(jì)算及資源開銷。為此，該文提出了一種針對(duì)網(wǎng)絡(luò)編碼優(yōu)化的改進(jìn)量子進(jìn)化算法IQEA-NC，以滿足達(dá)到理論多播速率的情況下最小化網(wǎng)絡(luò)的編碼開銷目的。IQEA-NC對(duì)傳統(tǒng)量子進(jìn)化算法進(jìn)行了有效的改進(jìn)，降低了算法搜索空間，增強(qiáng)了全局搜索能力，同時(shí)避免了陷入局部最優(yōu)。仿真對(duì)比實(shí)驗(yàn)表明，同已有的量子進(jìn)化算法及其他進(jìn)化算法相比，該方法提高了優(yōu)化性能，在準(zhǔn)確性和收斂速度上都具有較大的優(yōu)勢(shì)。

多播; 網(wǎng)絡(luò)編碼; 優(yōu)化; 量子進(jìn)化算法

網(wǎng)絡(luò)編碼(network coding)[1]是一種融合編碼和路由的信息交換技術(shù)，允許網(wǎng)絡(luò)中間節(jié)點(diǎn)對(duì)傳輸?shù)男畔凑蘸线m的方式進(jìn)行編碼處理而不僅僅完成存儲(chǔ)和轉(zhuǎn)發(fā)，基于該方式的網(wǎng)絡(luò)多播能夠?qū)崿F(xiàn)最大流最小割定理確定的最大理論傳輸容量。文獻(xiàn)[2]進(jìn)一步證明只需要線性網(wǎng)絡(luò)編碼就可以達(dá)到網(wǎng)絡(luò)最大傳輸容量。線性網(wǎng)絡(luò)編碼中，編碼節(jié)點(diǎn)輸出鏈接上的信息是其輸入鏈接信息的線性組合。網(wǎng)絡(luò)編碼在提高網(wǎng)絡(luò)吞吐量、改善負(fù)載均衡、降低無(wú)線節(jié)點(diǎn)能耗等方面具有明顯的優(yōu)勢(shì)，并逐漸在內(nèi)容分發(fā)[3]、分布式存儲(chǔ)[4]、無(wú)線網(wǎng)絡(luò)[5]、P2P網(wǎng)絡(luò)[6]等領(lǐng)域得到成功應(yīng)用。

然而，網(wǎng)絡(luò)節(jié)點(diǎn)的編碼操作引入了額外的計(jì)算開銷和資源消耗，增大了系統(tǒng)的復(fù)雜性[7]。減少進(jìn)行網(wǎng)絡(luò)編碼操作的中間節(jié)點(diǎn)數(shù)量具有實(shí)際的意義。事實(shí)上，編碼操作不需要在所有的中間節(jié)點(diǎn)都實(shí)施，只要在部分節(jié)點(diǎn)上進(jìn)行網(wǎng)絡(luò)編碼就可達(dá)到網(wǎng)絡(luò)的最大理論傳輸容量[8]。然而，確定最小編碼節(jié)點(diǎn)集被證明是一個(gè)NP難問題[8-9]。

已有的研究工作都是通過減少參與編碼的中間節(jié)點(diǎn)數(shù)量，以降低網(wǎng)絡(luò)編碼開銷，優(yōu)化編碼效率。文獻(xiàn)[7]指出了針對(duì)有環(huán)和無(wú)環(huán)拓?fù)涞木W(wǎng)絡(luò)編碼節(jié)點(diǎn)的上界，并證明該界限僅決定于設(shè)計(jì)速率和接收節(jié)點(diǎn)的數(shù)量。文獻(xiàn)[10]提出子樹分解的方法，得出在雙源、個(gè)接收節(jié)點(diǎn)的無(wú)環(huán)網(wǎng)絡(luò)中，編碼節(jié)點(diǎn)數(shù)不超過個(gè)。但上述兩種方法依賴于信息傳輸?shù)倪呅蛄校缓线m的序列會(huì)導(dǎo)致算法性能下降并帶來(lái)更多的計(jì)算開銷。文獻(xiàn)[11]提出了用于網(wǎng)絡(luò)編碼的線性規(guī)劃模型，但優(yōu)化算法過于復(fù)雜，隨著接收節(jié)點(diǎn)的增加，復(fù)雜度呈指數(shù)級(jí)增長(zhǎng)。文獻(xiàn)[8-9]提出了基于遺傳算法的網(wǎng)絡(luò)編碼優(yōu)化算法，實(shí)驗(yàn)結(jié)果表明效果優(yōu)于上述非啟發(fā)式算法，但遺傳算法本身存在的缺陷，如早熟、收斂速度慢等可能導(dǎo)致該算法表現(xiàn)出較差的性能。最近，量子進(jìn)化算法[12]被引入到網(wǎng)絡(luò)編碼優(yōu)化問題的研究中，由于該算法具有種群規(guī)模小、收斂速度快和全局尋優(yōu)能力強(qiáng)等特點(diǎn)而大量應(yīng)用于各種組合優(yōu)化問題的求解中[13-15]。文獻(xiàn)[16]應(yīng)用量子進(jìn)化算法及其改進(jìn)算法解決網(wǎng)絡(luò)編碼優(yōu)化問題，得到較經(jīng)典遺傳算法更好的性能，但該算法僅僅考慮了量子進(jìn)化算法本身的性能改進(jìn)，沒有針對(duì)性地考慮網(wǎng)絡(luò)編碼優(yōu)化問題的特殊性，當(dāng)網(wǎng)絡(luò)規(guī)模擴(kuò)大時(shí)，該算法搜索能力會(huì)下降。

針對(duì)現(xiàn)有的網(wǎng)絡(luò)編碼優(yōu)化算法存在的不足，本文以量子進(jìn)化算法作為研究工具，對(duì)網(wǎng)絡(luò)編碼優(yōu)化問題進(jìn)行進(jìn)一步的研究。提出了基于改進(jìn)量子進(jìn)化算法的網(wǎng)絡(luò)編碼優(yōu)化算法IQEA-NC，該算法充分利用了量子計(jì)算的并行性和量子染色體多狀態(tài)表征能力，同時(shí)考慮了網(wǎng)絡(luò)編碼優(yōu)化的諸多約束條件，對(duì)量子進(jìn)化算法進(jìn)行了有針對(duì)性的改進(jìn)。

1 網(wǎng)絡(luò)編碼優(yōu)化問題描述

本文討論線性網(wǎng)絡(luò)編碼下的單源多接收節(jié)點(diǎn)的多播問題。多播網(wǎng)絡(luò)可以表示為一個(gè)有向無(wú)環(huán)圖，其中，表示節(jié)點(diǎn)的集合，表示鏈路的集合。每個(gè)鏈接具有單位容量，節(jié)點(diǎn)間具有較大容量的鏈接使用多個(gè)單位容量鏈接表示。單源多播場(chǎng)景可以用一個(gè)4元組表示，即在圖中，將信息從單源以速率傳輸?shù)浇邮展?jié)點(diǎn)集，如果存在一種傳輸策略使得所有個(gè)接收節(jié)點(diǎn)都接收到了源節(jié)點(diǎn)發(fā)出的數(shù)據(jù)信息，那么稱速率是可達(dá)的。

很明顯，具有多個(gè)輸入鏈接的節(jié)點(diǎn)才可能進(jìn)行編碼操作，僅一個(gè)輸入鏈接的節(jié)點(diǎn)只完成信息的存儲(chǔ)和轉(zhuǎn)發(fā)。既使是多輸入鏈接的節(jié)點(diǎn)，如果其輸出鏈接的信息僅僅依賴于一個(gè)輸入鏈接的信息，該節(jié)點(diǎn)仍無(wú)需進(jìn)行編碼操作。事實(shí)上，網(wǎng)絡(luò)中間節(jié)點(diǎn)是否需要編碼取決于其是否存在至少一條輸出邊需要傳輸編碼信息，所以編碼鏈接能夠比編碼節(jié)點(diǎn)更精確地表示當(dāng)前網(wǎng)絡(luò)的編碼計(jì)算開銷[7]。因此，本文討論的網(wǎng)絡(luò)編碼優(yōu)化問題就是在保證網(wǎng)絡(luò)多播速率可達(dá)到的情況下，最小化參與網(wǎng)絡(luò)編碼的編碼鏈接數(shù)量。

本文引用了代數(shù)方法[17]對(duì)網(wǎng)絡(luò)編碼優(yōu)化問題進(jìn)行描述。給定一個(gè)有向無(wú)環(huán)圖, 如果滿足條件，則稱邊連入邊。以圖為參照，生成一個(gè)有向標(biāo)線圖，其中，，，圖中的每一條邊被標(biāo)記上對(duì)應(yīng)的鏈路系數(shù)，在有限域上隨機(jī)選取。按文獻(xiàn)[17]的方法，為個(gè)接收節(jié)點(diǎn)中的每一個(gè)節(jié)點(diǎn)都建立一個(gè)的系統(tǒng)傳遞矩陣以描述源節(jié)點(diǎn)和每個(gè)接收節(jié)點(diǎn)間的關(guān)系。表示這個(gè)系統(tǒng)傳遞矩陣所對(duì)應(yīng)行列式的乘積，是一個(gè)關(guān)于的多項(xiàng)式，當(dāng)≠0時(shí)，網(wǎng)絡(luò)可以達(dá)到給定的多播速率[17]。

2 量子進(jìn)化算法

進(jìn)化算法是一類模擬生物進(jìn)化過程的隨機(jī)搜索及優(yōu)化方法，把量子計(jì)算的原理和特性融入到進(jìn)化計(jì)算中產(chǎn)生的量子進(jìn)化算法(QEA)[12]，可以充分利用量子計(jì)算的并行性和隨機(jī)性解決普通進(jìn)化計(jì)算在損失種群多樣性時(shí)引起的早熟收斂。

2.1 量子比特

在量子進(jìn)化算法中，最小的信息單元為一個(gè)量子比特(qutbit)，它的定義是在一個(gè)二維復(fù)向量空間中的一個(gè)單位向量。一個(gè)量子比特的狀態(tài)可取0(記為)，或者1(記為)，或者狀態(tài)0和1的不同疊加態(tài)。一個(gè)量子比特記為，可以表示為：

且滿足歸一化條件：

(2)

2.2 量子編碼

量子進(jìn)化算法采用了基于量子比特的編碼方式，即用實(shí)數(shù)定義一個(gè)量子比特位。一個(gè)具有個(gè)量子比特位的系統(tǒng)可以描述為：，其中，。該表示方法可以表征任意的線性疊加態(tài)。

3 基于量子進(jìn)化算法的網(wǎng)絡(luò)編碼優(yōu)化

本文將量子進(jìn)化算法用于網(wǎng)絡(luò)編碼優(yōu)化問題，提出了基于改進(jìn)的量子進(jìn)化算法的網(wǎng)絡(luò)編碼優(yōu)化算法(IQEA-NC)。針對(duì)網(wǎng)絡(luò)編碼優(yōu)化問題的特點(diǎn)，對(duì)量子種群的初始化、觀測(cè)算子及量子旋轉(zhuǎn)門修正等方面進(jìn)行了改進(jìn)，提高量子進(jìn)化算法的多樣性保持能力，并降低算法搜索空間、增強(qiáng)全局搜索能力，同時(shí)避免陷入局部最優(yōu)。

3.1 網(wǎng)絡(luò)編碼優(yōu)化問題的量子比特表示

在網(wǎng)絡(luò)編碼優(yōu)化問題中，本文取適應(yīng)度函數(shù)為滿足網(wǎng)絡(luò)多播速率要求的前提下，參與網(wǎng)絡(luò)編碼的鏈接數(shù)的倒數(shù)，即：

3.2 初始化種群

3.3 觀測(cè)算子的改進(jìn)

3.4 量子旋轉(zhuǎn)門修正

量子進(jìn)化算法中，采用量子旋轉(zhuǎn)門操作對(duì)量子比特進(jìn)行改變從而更新量子種群，促進(jìn)每個(gè)量子比特的概率幅值收斂到0或者1，直到搜索到最優(yōu)解。量子旋轉(zhuǎn)門的定義為：

表1 量子旋轉(zhuǎn)門的調(diào)整策略

量子旋轉(zhuǎn)門操作定義為：

(7)

3.5 IQEA-NC算法描述

IQEA-NC算法具體步驟如下：

4) 判斷終止條件是否滿足，即是否滿足預(yù)定義的結(jié)束條件或者最大進(jìn)化代數(shù)()，若滿足，則算法終止；否則，繼續(xù)向下執(zhí)行。

5) 根據(jù)表1查找量子旋轉(zhuǎn)門的旋轉(zhuǎn)角，用式(6)和式(7)對(duì)采用量子門旋轉(zhuǎn)操作并進(jìn)行修正，得到更新的量子種群。

4 仿真實(shí)驗(yàn)及結(jié)果分析

圖1 人工生成的固定拓?fù)?/p>

為了測(cè)試和比較算法的性能，將本文算法與NCQEA[16]和SGA[8]進(jìn)行性能比較，仿真在兩種類型的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)開展，第一種是在文獻(xiàn)[8]中使用人工生成的固定拓?fù)洌鐖D1所示，記為Network 1；第二種是由BRITE模擬生成的20個(gè)節(jié)點(diǎn)的隨機(jī)拓?fù)?，記為Network 2，具體參數(shù)為20 nodes, 54 links, 8 sinks, rate 3。仿真實(shí)驗(yàn)中涉及到的算法在Matlab 7.5環(huán)境下編程實(shí)現(xiàn)，軟件運(yùn)行環(huán)境為Pentium Dual- Core CPU，2.8 GHz主頻，4 GB內(nèi)存。

為便于比較，3種算法設(shè)置了相同的種群大小和最大進(jìn)化代數(shù)。對(duì)于IQEA-NC算法的其他參數(shù)，選取了經(jīng)過多次實(shí)驗(yàn)嘗試后的經(jīng)驗(yàn)值，具體設(shè)置如下：種群大小，最大進(jìn)化代數(shù)，量子比特概率幅值初始值，，量子旋轉(zhuǎn)門的旋轉(zhuǎn)角大小，門閾值，對(duì)量子種群的觀測(cè)次數(shù)。

NCQEA參數(shù)設(shè)置為：種群大小為100，最大進(jìn)化代數(shù)為300，初始量子旋轉(zhuǎn)角度為。

SGA參數(shù)設(shè)置為：種群大小為100，最大進(jìn)化代數(shù)為300，交叉概率為0.8，變異概率為0.01。

以上3種算法的終止條件為：如果連續(xù)50次相鄰兩代種群的最佳適應(yīng)度都沒有發(fā)生變化，則算法結(jié)束，否則達(dá)到最大進(jìn)化代數(shù)算法結(jié)束。每種算法都運(yùn)行60次，獲得算法的最優(yōu)值和平均值。

4.1 算法效果比較

表2給出了IQEA-NC、SGA、NCQEA在兩種拓?fù)錀l件下進(jìn)行60次試驗(yàn)后得到的編碼鏈接數(shù)的平均結(jié)果。從測(cè)試結(jié)果看，對(duì)Network 1網(wǎng)絡(luò)，IQEA-NC總能夠得到最小的編碼鏈接數(shù)量，同時(shí)具有較小的平均值；對(duì)Network 2網(wǎng)絡(luò)，IQEA-NC相對(duì)于SGA，無(wú)論是最優(yōu)值還是平均值，都表現(xiàn)出較為明顯的性能優(yōu)勢(shì)；相對(duì)于NCQEA，兩者都可以得到較小的最優(yōu)值，但在平均值上，IQEA-NC比NCQEA具有更大的優(yōu)勢(shì)。

表2 IQEA-NC、SGA、NCQEA效果比較

4.2 算法收斂性比較

為比較3種算法的收斂性，本文修改了算法的終止條件，不再判斷連續(xù)50次相鄰兩代種群的最佳適應(yīng)度的變化情況，而是讓算法運(yùn)行到最大進(jìn)化代數(shù)才結(jié)束，實(shí)驗(yàn)在Network 2網(wǎng)絡(luò)上進(jìn)行。圖2給出了3種算法的收斂性比較。從圖中可以看出，IQEA-NC的收斂速度最快，性能優(yōu)于NCQEA和SGA，能夠快速接近最優(yōu)值；SGA進(jìn)化速度緩慢，且在算法后期陷入了局部最優(yōu)。另外，相對(duì)于同樣基于量子進(jìn)化算法的QEANC，IQEA-NC初次搜索就可以得到較優(yōu)的解，這是由于采用改進(jìn)的種群初始化方法，減小了算法搜索空間。采用多觀測(cè)算子使算法在代內(nèi)實(shí)現(xiàn)了局部種群優(yōu)化，提高了解的質(zhì)量；量子旋轉(zhuǎn)門修正策略避免了算法陷入局部極值。正是這些改進(jìn)，使得IQEA-NC具有更好的性能優(yōu)勢(shì)。

圖2 算法收斂性比較

5 結(jié) 論

針對(duì)網(wǎng)絡(luò)編碼優(yōu)化應(yīng)用的實(shí)際特征，本文在初始種群選擇、觀測(cè)算子設(shè)計(jì)和量子旋轉(zhuǎn)門修正策略等方面對(duì)傳統(tǒng)量子進(jìn)化算法進(jìn)行了有效的改進(jìn)，提出了基于改進(jìn)量子進(jìn)化算法的網(wǎng)絡(luò)編碼優(yōu)化算法。相對(duì)于已有的基于進(jìn)化算法的網(wǎng)絡(luò)編碼優(yōu)化方法，本文提出的方法在滿足多播速率的情況下，算法在準(zhǔn)確性和收斂性上都有較大提高。

[1] AHLSWEDE R, CAI N, LI S Y R, et al. Network information flow[J]. IEEE Transactions on Information Theory, 2000, 46(4): 1204-1216.

[2] LI S Y R, YEUNG R W, CAI N. Linear network coding[J]. IEEE Transactions on Information Theory, 2003, 49(2): 371-381.

[3] GKANTSIDIS C, RODRIGUEZ P. Network coding for large scale content distribution[C]//Proceedings of IEEE INFOCOM. Miami: IEEE Press, 2005.

[4] DIMAKIS A G, GODFREY P B, WAINWRIGHT M, et al. Network coding for distributed storage systems[C]// Proceedings of IEEE INFOCOM. Barcelona: IEEE Press, 2007.

[5] WU Y, CHOU P A, KUNG S Y. Information exchange in wireless with network coding and physical layer broadcast[C]//Proceedings of the Conference on Information Sciences and Systems, Baltimore: IEEE Press, 2005.

[6] WANG M, LI B. Network coding in live peer-to-peer streaming[J]. IEEE Transactions on Multimedia, Special Issue on Content Storage and Delivery in Peer-to-Peer Networks, 2007, 9(8): 1554-1567.

[7] LANGBERG M, SPRINTSON A, BRUCK J. The encoding complexity of network coding[C]//Proceedings of IEEE ISIT. Adelaide: IEEE Press, 2005.

[8] KIM M, AHN C W, MEDARD M. On minimizing network coding resources: An evolutionary approach[C]// Proceedings of Second Workshop on Network Coding, Theory, and Applications (NetCod2006). Boston: IEEE Press, 2006.

[9] KIM M, MEDARD M, AGGARWAL V. Evolutionary approaches to minimizing network coding resources[C]// Proceedings of IEEE INFOCOM. Baltimore: IEEE Press, 2007.

[10] FRAGOULI C, PARKER R. Information flow decomposition for network coding[J]. IEEE Transactions on Information Theory, 2006, 52(3): 829-848.

[11] BHATTAD K, RATNAKAR N, KOETTER R. Minimal network coding for multicast[C]//Proceedings of IEEE ISIT. Adelaide: IEEE Press, 2005.

[12] HAN K H, KIM J H. Quantum-inspired evolutionary algorithm for a class of combinatorial optimization[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(6): 580-593.

[13] SILVEIRA L R, TANSCHEIT R, VELLASCO M. Quantum-inspired genetic algorithms applied to ordering combinatorial optimization problems[C]//Proceedings of IEEE World Congress on Computational Intelligence. Brisbane: IEEE Press, 2012.

[14] KIM J H, HAN J H, KIM Y H, et al. Preference-based solution selection algorithm for evolutionary multiobjective optimization[J]. IEEE Transactions on Evolutionary Computation, 2012,16(1): 20-34.

[15] HO S L, YANG Shi-you, NI Pei-hong, et al. A quantum- inspired evolutionary algorithm for multi-objective design[J]. IEEE Transactions on Magnetics, 2013, 49(5): 1609-1612.

[16] XING Huan-lai, JIN Xing, BAI Lin, et al. A quantum- inspired evolutional algorithm for coding resource optimization based network coding multicasting [C]//Proceedings of International Conference on Semantics, Knowledge and Grid. Beijing: IEEE Press, 2008.

[17] KOETTER R, MEDARD M, An algebraic approach to network coding[J]. IEEE/ACM Transactions on Networking, 2003, 11(5): 782-795.

[18] HAN K H, KIM J H. Quantum-inspired evolutionary algorithms with a new termination criterion, H gate, and two-phase scheme[J]. IEEE Transactions on Evolutionary Computation, 2004, 8(2): 156-169.

編 輯 稅 紅

Improved Quantum-Inspired Evolutionary Algorithm for Network Coding Optimization

TANG Dong-ming1and LU Xian-liang2

(1. School of Information Engineering, Southwest University of Science and Technology Mianyang Sichuan 621010;2. School of Computer Science and Engineering, University of Electronic Science and Technology of China Chengdu 611731)

It has been proved that network coding, which allows network intermediate nodes to perform processing operations on the incoming packets instead of simply forwarding them, can approach the max-flow min-cut limit of the network graph. But such coding operations in network nodes incur additional computational overhead and consume public resources. Under condition of achieving the desired throughput in multicast scenario, this paper presents an improved quantum-inspired evolutionary algorithm (IQEA-NC) to minimize network coding resources. Compared with normal quantum-inspired evolutionary algorithm, IQEA-NC can achieve some effective improvements, such as decreasing the search space, increasing global search capacity, and jumping out of local optimum. The simulation experiment results show that IQEA-NC runs faster and more efficiently, improves the optimization performance compared with the existing algorithm.

multicast; network coding; optimization; quantum-inspired evolutionary algorithm

TP393

A

10.3969/j.issn.1001-0548.2015.02.010

2013-01-11；

2014-11-04

唐東明(1974-)，男，博士生，主要從事網(wǎng)絡(luò)信息處理、網(wǎng)絡(luò)編碼方面的研究.