Tradeoff between multicast rate and number of coding nodes based on network coding

doi:10.11772/j.issn.1001-9081.2015.04.0929

Abstract

Abstract:

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.

Key words: single-source multicast, random linear network coding, multicast rate, minimum coding node number, multi-objective optimization

摘要：

为探究单源组播网络编码的组播率与最少编码节点数之间的关系,利用线性网络编码的导出与扩展技术,对两者间的关系进行了理论分析和推导,得出了"最少编码节点数随组播率单调递增"的结论。构造了一个多目标优化模型用于精确地描述两者间的数量关系。为求解这个多目标优化模型,设计出能搜索所有可行编码方案的策略。运用该策略,并结合NSGA-II,提出了求解该模型的算法。在需要兼顾两者平衡的情况下,模型的解为确定编码方案提供了选择依据。所提算法不仅能搜索出整个Pareto集,而且能在指定可行组播率区域的前提下,以较小的运算代价得出相应的部分Pareto集。仿真结果验证了理论分析的结论,表明了所提算法的可行性和有效性。

关键词: 单源组播, 随机线性网络编码, 组播率, 最少编码节点数, 多目标优化

CLC Number:

TP393.01

PU Baoxing, ZHAO Chenglin. Tradeoff between multicast rate and number of coding nodes based on network coding[J]. Journal of Computer Applications, 2015, 35(4): 929-933.

蒲保兴, 赵乘麟. 基于网络编码的组播率与编码节点数的平衡[J]. 计算机应用, 2015, 35(4): 929-933.

References

[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.