Abstract:

In order to solve the problem of multi-source multi-sink multicast network coding, an algorithm for computing achievable information rate region and an approach for constructing linear network coding scheme were proposed. Based on the previous studies, the multi-source multi-sink multicast network coding problem was transformed into a specific single-source multicast network coding scenario with a constraint at the source node. By theoretical analyses and formula derivation, the constraint relationship among the multicast rate of source nodes was found out. Then a multi-objective optimization model was constructed to describe the boundary of achievable information rate region. Two methods were presented for solving this model. One was the enumeration method, the other was multi-objective optimization method based on genetic algorithm. The achievable information rate region could be derived from Pareto boundary of the multi-objective optimization model. After assigning the multicast rate of source nodes, the linear network coding scheme could be constructed by figuring out the single-source multicast network coding scenario with a constraint. The simulation results show that the proposed methods can find out the boundary of achievable information rate region including integral points and construct linear network coding scheme.

Key words: multi-source multi-sink multicast, achievable information rate region, single source multicast, network coding, multi-objective optimization

摘要：

为了解决多源多宿组播网络编码问题,提出了计算可达信息率区域的算法和构造线性网络编码的方法。在已有研究的基础上,把多源多宿组播网络编码问题转化为一个含有约束的单源组播网络编码问题,通过理论分析与推导,找出了各源点组播率之间的相互约束关系,进而构造了一个多目标优化模型来表征可达信息率区域的边界,提出了两种求解该多目标优化问题的方法:枚举法和基于遗传算法的多目标优化算法。从求出的Pareto边界可以导出可达信息率区域。选定了各源点的组播率后,通过求解含有约束的单源组播网络编码问题便可以构造出线性网络编码方案。仿真测试结果表明提出的方法可以求出可达信息率区域的整数点边界,并能构造线性网络编码方案。

关键词: 多源多宿组播, 可达信息率区域, 单源组播, 网络编码, 多目标优化