Based on single-source multicast network coding, in order to explore the relationship between multicast rate and the number of minimal needed coding nodes, by employing the technique of generation and extension of linear network coding, theoretical analysis and formula derivation of the relationship were given. It is concluded that the number of the minimal needed coding nodes monotonously increases with the increasing of multicast rate. A multi-objective optimization model was constructed, which accurately described the quantitative relationship between them. For the sake of solving this model, a search strategy was derived to search all feasible coding schemes. By combining the search strategy with NSGA-II, an algorithm for solving this model was presented. In the case of being required to consider the tradeoff between them, the solution of the model is the basis of choice for determining network coding scheme. The proposed algorithm not only can search whole Pareto set, but also search part Pareto set related with certain feasible multicast rate region given by user with less search cost. The simulation results verify the conclusion of theoretical analysis, and indicate that the proposed algorithm is feasible and efficient.
蒲保兴, 赵乘麟. 基于网络编码的组播率与编码节点数的平衡[J]. 计算机应用, 2015, 35(4): 929-933.
PU Baoxing, ZHAO Chenglin. Tradeoff between multicast rate and number of coding nodes based on network coding. Journal of Computer Applications, 2015, 35(4): 929-933.
[1] AHLSWEDE R, CAI N, LI S R Y, et al. Network information flow[J]. IEEE Transactions on Information Theory,2000,46(4):1204-1216. [2] YANG L, ZHENG G, HU X. Research on network coding: a survey[J]. Journal of Computer Reasearch and Development,2008,45(3):400-407.(杨林,郑刚,胡晓惠.网络编码研究进展.计算机研究与发展,2008,45(3):400-407.) [3] LI S Y R, YEUNG R W, CAI N. Linear network coding[J]. IEEE Transactions on Information Theory,2003,49(2):371-381. [4] KOETTER R, MEDARD M. An algebraic approach to network coding[J]. IEEE/ACM Transactions on Networking, 2003,11(5):782-795. [5] WANG M, LI B. How practical is network coding? [C]// IWQoS 2006: Proceedings of the 14th IEEE International Workshop on Quality of Service. Piscataway: IEEE Press, 2006:274-278. [6] PU B, WANG W. Evaluation and analysis of the computation cost of linear network coding[J]. Journal on Communications,2011,32(5):47-55.(蒲保兴,王伟平.线性网络编码的运算代价的估算与分析[J].通信学报,2011,32(5):47-55.) [7] LANGBERG M, SPINTSON A, BRUCK J. The encoding complexity of network coding[J]. IEEE Transactions on Information Theory, 2006, 52(6): 2386-2397. [8] LANGBERG M,SPINTSON A,BRUCK J.Network coding:a computational perspective[J].IEEE Transaction Information Theory, 2009, 55(1): 147-157. [9] KIM M,AHN C W,MEDARD M, et al. On minimizing network coding resources: an evolutionary approach[C]// INFOCOM 2007: Proceedings of the 26th IEEE International Conference on Computer Communications. Piscataway: IEEE Press, 2006:1991-1999. [10] MINKYU K, MEDARD M, AGGARWAL V, et al. Evolutionary approaches to minimizing network coding resources[C]// INFOCOM 2007: Proceedings of the 26th IEEE International Conference on Computer Communications. Piscataway: IEEE Press, 2007:1991-1999. [11] DENG L, ZHAO J, WANG X. Genetic algorithm solution of network coding optimization[J]. Journal of Software,2008,19(8):2269-2279.(邓亮,赵进,王新. 基于遗传算法的网络编码优化[J].软件学报,2008,19(8):2269-2279.) [12] HAO K, JIN Z. An optimization algorithm of network coding for minimizing coding nodes[J]. Journal of Electronics and Information Technology,2011,33(2):260-265.(郝琨,金志刚.一种最少化编码节点的网络编码优化算法[J].电子与信息学报,2011,33(2):260-265.) [13] PU B, YANG L, WANG W. Generation and extension of linear network coding[J]. Journal of Software,2011,22(3):558-571.(蒲保兴,杨路明,王伟平.线性网络编码的导出与扩展[J].软件学报,2011,22(3):558-571.) [14] DEB K, PRATAB A, AGARWAL A, et al. A fast and elitist multi-objective genetic algorithm: NSGA-II[J]. IEEE Transactions on Evolutionary Computation, 2002,6(2):182-197. [15] PU B, YANG L, XIE D. Multi-objective optimization algorithm embedded by user preference region[J]. Journal of Chinese Computer Systems,2009,30(1):144-148.(蒲保兴,杨路明,谢东. 嵌入用户偏爱区域的多目标优化算法[J].小型微型计算机系统,2009,30(1):144-148.) [16] MELANCON G, PHILIPPER F. Generating connected acyclic digraphs uniformly at random[J]. Information Processing Letters,2004,90(4):209-218.
2015, Vol. 35 
