北京郵電大學理學院,北京100876
摘要：網絡編碼技術在改變了傳統的路由網絡只進行存儲和轉發的功能的基礎上，有效地提升了網絡的傳輸性能。但編碼的引入帶來了CPU計算負擔加重、緩存消耗增大等問題，為了減少或克服額外開銷。本文提出了在代數網絡編碼基礎上的網絡編碼鏈路優化模型。在此模型上，給出了一種基于改進的遺傳算法的最小化編碼節點的算法（Multi-Population Genetic Algorithm）。MPGA在標準遺傳算法SGA的基礎上進行了一定修改，有效的降低了算法尋優時間，避免了遺傳算法的局部收斂問題。通過仿真模擬，MPGA算法較SGA算法找到的需要編碼的網絡節點的數目更少，且找到最優解的運行時間也更少，速度更快。
關鍵詞：網絡編碼  多種群遺傳算法  標準遺傳算法
中圖分類號：TP393     文獻標識碼：A
　　　　Genetic Algorithm Solution of Network Coding Optimization
　　　Jia Shi-wei   Lin Jing
　　Beijing University of Posts and Telecommunications, Postcode 10087
　　E-mail:1142172138@qq.com
Abstract: Network coding technology to change the traditional route network which is only on the basis of the store and forward function, effectively enhances the transmission performance of the network. But the introduction of the coding brought burden of the calculation of the CPU, increases of cache consumption and other issues. In order to reduce or overcome the overhead. We build network coding link optimization model based on the algebraic network coding in this paper. And an algorithm called the MPGA (Multi-Population Genetic Algorithm) is proposed, which is based on the improved genetic algorithm.The MPGA makes some modifications on the basis of the standard genetic algorithm SGA, It effectively reduces optimization time and avoids the locality problem of the genetic algorithm. Simulation results show that MPGA runs faster and the output network coding scheme requires less coding nodes.
Key words: Network Coding; Multi-Population Genetic Algorithm; Standard Genetic Algorithm.

參考文獻（References）
[1]R.Ahlswede,N.Cai, S.-Y. R.Li, and R.W.Yeung, “Network information flow,” IEEE Trans. Inf. Theory, vol. 46, no. 4, pp. 1204–1216,2000.
[2]孫惠全. 圖論及其應用[M]. 北京:科學出版社，2004.
[3]黃政，王新. 網絡編碼中的優化問題研究[J]. 軟件學報，2009,20（5）：1349-1361.
[4]Fragouli C and Soljanin E.Information flow decomposition for network coding.IEEE Transactions on Information Theory,2006,52(3):829-848.
[5]Langberg M,Sprintson A,and Bruck J.The encoding complexity of network coding.IEEE Transactions on Information Theory,2006,52(6):2386-2397.
[6]Bhattad K,Ratnakar N,and Koetter R.Minimal network coding for multicast[c].IEEE International Symposium on Information Theory.Melbourne Australia: IEEE Communication Society,2005:1730-1734.
[7]Kim M,Medard M,and O’Reilly V.Evolutionary approaches to minimizing network coding resources[c].Proc.of the IEEE INFOCOM 2007:1991-1999.
[8]M  Kim,Medard M,and O’Reilly U-M.An evolutionary approach to inter-session network coding[c].Proc. of the IEEE INFOCOM 2009.Rio de Janeiro,2009:450-458.
[9]鄧亮，趙進，王新. 基于遺傳算法的網絡編碼優化[J].軟件學報，2009,20（8）：2269-2279.
[10]Richey, M.B. and R.G. Parker, “On multiple steinersubgraph problems”,Networks, vol.16, no.4, pp. 423-438, 1986.
[11]Fragouli, C. and R.G. Parker, “Information flow decomposition for network coding”, IEEE Trans, Inform. Theory, vol.52, no.3, pp.829-848, 2006
[12]M.Langberg,A.Sprintson,andJ.Bruck,“The encoding complexity of network coding,” IEEE Trans. Inf. Theory, vol. 52, no. 6, pp. 2386–2397,2006
[13]K. Bhattad, N. Ratnakar, R. Koetter, and K. R. Narayanan, “Minimalnetwork coding for multicast,” in Proc. IEEE ISIT, 2005, pp. 1730–1734.
[14]Eiben, A.E. and J. E. Smith, Introduction to Evolutionary Computing,Berlin, Germany: Springer-Verlag, 2003.
[15] Kim M, Médard M, Aggarwal V, O’Reilly UM, Kim W, Ahn CW, Effros M. Evolutionary approaches to minimizing network coding resources. In: Proc. of the IEEE INFOCOM 2007. Anchorage: IEEE Computer Society, 2007. pp. 1991−1999.
[16]樊平毅. 網絡信息論[M]. 第一版，北京:清華大學出版社，2009，2:122-123.
[17]Koetter R, Médard M (2003) An algebraic approach to network coding. IEEE/ACM Trans Netw 11(5):782–795
[18]王晶. 遺傳算法的改進[J]. 中國科技論文.

個人簡介：賈詩煒（1990-），女，本科生，主要研究領域為網絡編碼，信息安全。

個人簡介：林靜（1992-），  女，本科生，主要研究領域為網絡編碼，信息安全。