用于網絡編碼優化的改進量子進化算法

唐東明，盧顯良

?

用于網絡編碼優化的改進量子進化算法

唐東明1，盧顯良2

(1. 西南科技大學信息工程學院 四川綿陽 621010; 2. 電子科技大學計算機科學與工程學院 成都 611731)

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

多播; 網絡編碼; 優化; 量子進化算法

網絡編碼(network coding)[1]是一種融合編碼和路由的信息交換技術，允許網絡中間節點對傳輸的信息按照合適的方式進行編碼處理而不僅僅完成存儲和轉發，基于該方式的網絡多播能夠實現最大流最小割定理確定的最大理論傳輸容量。文獻[2]進一步證明只需要線性網絡編碼就可以達到網絡最大傳輸容量。線性網絡編碼中，編碼節點輸出鏈接上的信息是其輸入鏈接信息的線性組合。網絡編碼在提高網絡吞吐量、改善負載均衡、降低無線節點能耗等方面具有明顯的優勢，并逐漸在內容分發[3]、分布式存儲[4]、無線網絡[5]、P2P網絡[6]等領域得到成功應用。

然而，網絡節點的編碼操作引入了額外的計算開銷和資源消耗，增大了系統的復雜性[7]。減少進行網絡編碼操作的中間節點數量具有實際的意義。事實上，編碼操作不需要在所有的中間節點都實施，只要在部分節點上進行網絡編碼就可達到網絡的最大理論傳輸容量[8]。然而，確定最小編碼節點集被證明是一個NP難問題[8-9]。

已有的研究工作都是通過減少參與編碼的中間節點數量，以降低網絡編碼開銷，優化編碼效率。文獻[7]指出了針對有環和無環拓撲的網絡編碼節點的上界，并證明該界限僅決定于設計速率和接收節點的數量。文獻[10]提出子樹分解的方法，得出在雙源、個接收節點的無環網絡中，編碼節點數不超過個。但上述兩種方法依賴于信息傳輸的邊序列，不合適的序列會導致算法性能下降并帶來更多的計算開銷。文獻[11]提出了用于網絡編碼的線性規劃模型，但優化算法過于復雜，隨著接收節點的增加，復雜度呈指數級增長。文獻[8-9]提出了基于遺傳算法的網絡編碼優化算法，實驗結果表明效果優于上述非啟發式算法，但遺傳算法本身存在的缺陷，如早熟、收斂速度慢等可能導致該算法表現出較差的性能。最近，量子進化算法[12]被引入到網絡編碼優化問題的研究中，由于該算法具有種群規模小、收斂速度快和全局尋優能力強等特點而大量應用于各種組合優化問題的求解中[13-15]。文獻[16]應用量子進化算法及其改進算法解決網絡編碼優化問題，得到較經典遺傳算法更好的性能，但該算法僅僅考慮了量子進化算法本身的性能改進，沒有針對性地考慮網絡編碼優化問題的特殊性，當網絡規模擴大時，該算法搜索能力會下降。

針對現有的網絡編碼優化算法存在的不足，本文以量子進化算法作為研究工具，對網絡編碼優化問題進行進一步的研究。提出了基于改進量子進化算法的網絡編碼優化算法IQEA-NC，該算法充分利用了量子計算的并行性和量子染色體多狀態表征能力，同時考慮了網絡編碼優化的諸多約束條件，對量子進化算法進行了有針對性的改進。

1 網絡編碼優化問題描述

本文討論線性網絡編碼下的單源多接收節點的多播問題。多播網絡可以表示為一個有向無環圖，其中，表示節點的集合，表示鏈路的集合。每個鏈接具有單位容量，節點間具有較大容量的鏈接使用多個單位容量鏈接表示。單源多播場景可以用一個4元組表示，即在圖中，將信息從單源以速率傳輸到接收節點集，如果存在一種傳輸策略使得所有個接收節點都接收到了源節點發出的數據信息，那么稱速率是可達的。

很明顯，具有多個輸入鏈接的節點才可能進行編碼操作，僅一個輸入鏈接的節點只完成信息的存儲和轉發。既使是多輸入鏈接的節點，如果其輸出鏈接的信息僅僅依賴于一個輸入鏈接的信息，該節點仍無需進行編碼操作。事實上，網絡中間節點是否需要編碼取決于其是否存在至少一條輸出邊需要傳輸編碼信息，所以編碼鏈接能夠比編碼節點更精確地表示當前網絡的編碼計算開銷[7]。因此，本文討論的網絡編碼優化問題就是在保證網絡多播速率可達到的情況下，最小化參與網絡編碼的編碼鏈接數量。

本文引用了代數方法[17]對網絡編碼優化問題進行描述。給定一個有向無環圖, 如果滿足條件，則稱邊連入邊。以圖為參照，生成一個有向標線圖，其中，，，圖中的每一條邊被標記上對應的鏈路系數，在有限域上隨機選取。按文獻[17]的方法，為個接收節點中的每一個節點都建立一個的系統傳遞矩陣以描述源節點和每個接收節點間的關系。表示這個系統傳遞矩陣所對應行列式的乘積，是一個關于的多項式，當≠0時，網絡可以達到給定的多播速率[17]。

2 量子進化算法

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

2.1 量子比特

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

且滿足歸一化條件：

(2)

2.2 量子編碼

量子進化算法采用了基于量子比特的編碼方式，即用實數定義一個量子比特位。一個具有個量子比特位的系統可以描述為：，其中，。該表示方法可以表征任意的線性疊加態。

3 基于量子進化算法的網絡編碼優化

本文將量子進化算法用于網絡編碼優化問題，提出了基于改進的量子進化算法的網絡編碼優化算法(IQEA-NC)。針對網絡編碼優化問題的特點，對量子種群的初始化、觀測算子及量子旋轉門修正等方面進行了改進，提高量子進化算法的多樣性保持能力，并降低算法搜索空間、增強全局搜索能力，同時避免陷入局部最優。

3.1 網絡編碼優化問題的量子比特表示

在網絡編碼優化問題中，本文取適應度函數為滿足網絡多播速率要求的前提下，參與網絡編碼的鏈接數的倒數，即：

3.2 初始化種群

3.3 觀測算子的改進

3.4 量子旋轉門修正

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

表1 量子旋轉門的調整策略

量子旋轉門操作定義為：

(7)

3.5 IQEA-NC算法描述

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

4) 判斷終止條件是否滿足，即是否滿足預定義的結束條件或者最大進化代數()，若滿足，則算法終止；否則，繼續向下執行。

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

4 仿真實驗及結果分析

圖1 人工生成的固定拓撲

為了測試和比較算法的性能，將本文算法與NCQEA[16]和SGA[8]進行性能比較，仿真在兩種類型的網絡拓撲結構開展，第一種是在文獻[8]中使用人工生成的固定拓撲，如圖1所示，記為Network 1；第二種是由BRITE模擬生成的20個節點的隨機拓撲，記為Network 2，具體參數為20 nodes, 54 links, 8 sinks, rate 3。仿真實驗中涉及到的算法在Matlab 7.5環境下編程實現，軟件運行環境為Pentium Dual- Core CPU，2.8 GHz主頻，4 GB內存。

為便于比較，3種算法設置了相同的種群大小和最大進化代數。對于IQEA-NC算法的其他參數，選取了經過多次實驗嘗試后的經驗值，具體設置如下：種群大小，最大進化代數，量子比特概率幅值初始值，，量子旋轉門的旋轉角大小，門閾值，對量子種群的觀測次數。

NCQEA參數設置為：種群大小為100，最大進化代數為300，初始量子旋轉角度為。

SGA參數設置為：種群大小為100，最大進化代數為300，交叉概率為0.8，變異概率為0.01。

以上3種算法的終止條件為：如果連續50次相鄰兩代種群的最佳適應度都沒有發生變化，則算法結束，否則達到最大進化代數算法結束。每種算法都運行60次，獲得算法的最優值和平均值。

4.1 算法效果比較

表2給出了IQEA-NC、SGA、NCQEA在兩種拓撲條件下進行60次試驗后得到的編碼鏈接數的平均結果。從測試結果看，對Network 1網絡，IQEA-NC總能夠得到最小的編碼鏈接數量，同時具有較小的平均值；對Network 2網絡，IQEA-NC相對于SGA，無論是最優值還是平均值，都表現出較為明顯的性能優勢；相對于NCQEA，兩者都可以得到較小的最優值，但在平均值上，IQEA-NC比NCQEA具有更大的優勢。

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

4.2 算法收斂性比較

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

圖2 算法收斂性比較

5 結 論

針對網絡編碼優化應用的實際特征，本文在初始種群選擇、觀測算子設計和量子旋轉門修正策略等方面對傳統量子進化算法進行了有效的改進，提出了基于改進量子進化算法的網絡編碼優化算法。相對于已有的基于進化算法的網絡編碼優化方法，本文提出的方法在滿足多播速率的情況下，算法在準確性和收斂性上都有較大提高。

[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-)，男，博士生，主要從事網絡信息處理、網絡編碼方面的研究.