计算机应用 ›› 2015, Vol. 35 ›› Issue (4): 929-933.DOI: 10.11772/j.issn.1001-9081.2015.04.0929

• 网络与通信 • 上一篇    下一篇

基于网络编码的组播率与编码节点数的平衡

蒲保兴, 赵乘麟   

  1. 邵阳学院 激光技术与信息研究所, 湖南 邵阳 422001
  • 收稿日期:2014-11-16 修回日期:2014-12-27 出版日期:2015-04-10 发布日期:2015-04-08
  • 通讯作者: 蒲保兴
  • 作者简介:蒲保兴(1965-),男,湖南邵阳人,教授,博士,主要研究方向:网络编码、进化计算; 赵乘麟(1965-),男,湖南邵阳人,教授,主要研究方向:图像编码。
  • 基金资助:

    湖南省教育厅重点科研项目(11A111, 12A068); 湖南省科技计划项目(2012FJ3108)。

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

PU Baoxing, ZHAO Chenglin   

  1. Institute of Laser Technology and Information, Shaoyang University, Shaoyang Hunan 422001, China
  • Received:2014-11-16 Revised:2014-12-27 Online:2015-04-10 Published:2015-04-08

摘要:

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

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

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

中图分类号: