摘要：为了解决多源多宿组播网络编码问题，提出了计算可达信息率区域的算法和构造线性网络编码的方法。在已有研究的基础上，把多源多宿组播网络编码问题转化为一个含有约束的单源组播网络编码问题，通过理论分析与推导，找出了各源点组播率之间的相互约束关系，进而构造了一个多目标优化模型来表征可达信息率区域的边界，提出了两种求解该多目标优化问题的方法：枚举法和基于遗传算法的多目标优化算法。从求出的Pareto边界可以导出可达信息率区域。选定了各源点的组播率后，通过求解含有约束的单源组播网络编码问题便可以构造出线性网络编码方案。仿真测试结果表明提出的方法可以求出可达信息率区域的整数点边界，并能构造线性网络编码方案。
关键词：多源多宿组播；可达信息率区域；单源组播；网络编码；多目标优化
中图分类号： TN919.03；TP393.01 文献标志码：A
英文摘要
Abstract：In order to solve the problem of multisource multisink 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 multisource multisink multicast network coding problem was transformed into a specific singlesource 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 multiobjective 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 multiobjective optimization method based on genetic algorithm. The achievable information rate region could be derived from Pareto boundary of the multiobjective optimization model. After assigning the multicast rate of source nodes， the linear network coding scheme could be constructed by figuring out the singlesource 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：multisource multisink multicast； achievable information rate region； single source multicast； network coding； multiobjective optimization
0 引言
组播情形，本文把在这种情形下如何运用网络编码进行数据传输的问题称为多源多宿组播网络编码问题。针对这个问题，文献[11]首次提出了能使网络吞吐率达到最大的网络编码构造方法，但只能得到使吞吐率达到最大的编码方案，而不能求可达信息率区域。而求出可达信息率区域是完整地解决这个问题的必要条件，因为只有求出了可达信息率区域，才能根据具体的要求对各源点的组播率进行选择。
1 相关研究
单源组播网络用一个有向无环多重图G=（V，E）表示，其中：V为节点集，E为有向边集， TV为宿点集，s为源点。
网络中的一条有向边也称为一条链路，假设链路的容量为整数，表示链路的最大数据传输速率，当链路的容量大于1时，可以拆分成多条单位容量的链路，每条单位容量的链路称为信道。
定义1 单源组播网络线性网络编码的组播率是指源点的数据传输速率，即源点在单位时间内发送数据的速率；组播容量是指满足所有宿点均能解码条件下的最大组播率，它等于源点与所有宿点之间的最小割值[1]。
定义2 单源组播网络按指定组播率采用线性网络编码
进行数据传输，若能找到某个编码方案，使所有宿点均能解码并恢复出源点的信息，则称该编码方案是可行编码方案。
对于网络中的任一节点v，其输出信道的集合记为Out（v），其输出信道数记为|Out（v）|。
定义4 在多源多宿组播网络中，若T为宿点集，r∈T，S是源点集，对于S中的一个子集B，记mincut（B，r）是分离集合B与宿点r的最小割的值，记mf（B，T）是分离集合B与所有宿点的最小割的最小值，即：
mf（B，T）=minr∈T{mincut（B，r）}（1）
2 问题的提出
式（3）描述了多源多宿组播情形下各源点组播率的容量区域，可以证明，容量区域是可达的，即可达信息率区域与容量区域相等。但在实际应用中，运用式（3）来计算可达信息率区域不太直观，同时限于篇幅，本文在此不给出证明，并寻找另外的方法来计算可达信息率区域。
提出如下问题：在多源多宿组播网络G1=（V，E）中，如何确定各源点的组播率，并构造线性网络编码方案，使各宿点能正确地解码，恢复出各源点播出的信息。
3 解决方法
3.1 问题的分析
定义6 在添加了虚拟成员的单源组播网络G2中，需要从虚拟源点s组播数据至所有宿点，要求采用线性网络编码技术实现数据传输，并且满足约束条件：在虚拟源点处不能进行编码（采用路由传输方式），这一问题称之为原问题的派生问题。
定理1 求解原问题与求解派生问题是等价的，即原问题的可行线性网络编码方案与派生问题的可行线性网络编码方案一一对应[11]。
定理2 对于任意的单源组播网络，s是源点，T为宿点集，若组播容量与源点的输出信道数相等，即满足以下条件：
mf（s，T）=|Out（s）|（5）
则一定可以找到一个可行的、且组播率为mf（s，T）的线性网络编码方案，该编码方案在源点处不需要进行网络编码。
证明 利用文献[2]构造线性网络编码的LIF算法的思想来证明：一定存在一个可行线性网络编码方案，其组播率为mf（s，T），且该编码方案在原点处不需要进行网络编码。
由于组播容量为mf（s，T），则从源点s至每一宿点存在h条边不重叠的路径，又由于式（5）成立，则源点的输出信道数为h，从而源点至每一宿点的h条路径均分别从源点的输出信道流出。源点的组播率为h，则源点的全局编码向量为h个单位向量，经过源点后，把这h个单位向量分别传输至每一条输出信道后，则能保证源点至每一宿点上的h条路径上的全局编码向量是线性无关的。接下来可按LIF算法继续确定其他节点输出信道的局部编码向量，可以得出组播率为h的可行编码方案。该编码方案在源点处不用编码，采用路由传输方式。证毕。
另一方面，以上两个定理为原问题提供了一个构造可行线性网络编码方案的方法：只要在单源组播网络G2中合适地选定各虚拟链路的容量，同时使式（5）成立，则可以运用LIF算法构造一个可行的、且组播率达到组播容量的线性网络编码方案，在这个编码方案中，把虚拟源点经虚拟链路ssi（1≤i≤n）传输的消息当成是由源点si产生，而其他节点的编码方式保持不变，则形成了一个原问题的线性网络编码方案，且每一宿点均能恢复出所有源点播出的消息。
3.3 模型求解
式（9）给出了一典型的多目标优化问题，它欲使多个目标最大化，同时满足一定的约束条件。本文提供两种求解方法：第一种是枚举法，在源点数量较少且各个分量xi（1≤i≤n）变化范围较小的情况下比较适用；第二种是基于NSGAⅡ的多目标优化算法，它适合于一般的情形。
3.3.1 枚举法
当求出了边界C后，可以很容易地求出可达信息率区域R，由性质2，对于c∈C所有满足0xc的x均是可达信息率区域中的点，它们构成了一个超立方体，该超立方体在“第一卦限指什么？”这是一个数学术语，属空间解析几何的一个概念。 卦限，是数学中的一个基本概念，指的是在空间立体几何中，由相互垂直的坐标轴X轴、Y轴、Z轴，把空整个间分成八 个部分，其中每一部分就是一个卦限。三个坐标面把空间分成八个部分，每个部分叫作一个卦限。含有x轴正半轴、y轴正半轴、z轴正半轴的卦限称为第一卦限，其他第二、三、四卦限，在xoy面的上方，按逆时针方向确定。在第一、二、三、四卦限下面的部分分别称为第五、六、七、八卦限。第一卦限内，原点及点c是该超立方体的两个顶点。R就是这些超立方体的并集。
4 仿真测试
两个边界点确定的部分可达信息率区域x3轴为何刻度不均匀？当时画时考虑到不要把文字被盖住，特意而为之。
现重画了该图，在附件中，请选择使用。
5 结果分析
本文提出的算法是以最小割为基础，采用了FordFulkerson算法进行计算，只能针对网络链路容量为整数的情形，求出的结果也是整数，从而求出的可达信息率区域中的边界点均为整数，事实上可达信息率区域是连续的，其边界点的坐标是实数。因此本文求出的边界点是比较粗略的，导致导出的可达信息率区域在边界处不是很精确，但在R的内部是精确的，既可以是整数，也可以是实数。尽管如此，在实际应用中，由于组播率是一个整数，从而求出的可达信息率区域能满足要求：当多个源点发送数据具有某一优先级顺序时，可以根据这一优先级顺序在R中选取各源点的组播率，并使网络的吞吐率达到最大。
6 结语
针对多个源点传输信息至同一宿点集的多源多宿组播网络，给出了采用网络编码实现数据传输的可达信息率区域的计算方法，并给出了构造线性网络编码方案的策略。通过理论分析与推导，把求解多源多宿组播网络编码的可达信息率区域的问题转化成一个多目标优化问题，其多目标优化问题的解就是可达信息率区域的边界。提出了两种求解多目标优化问题的方法：枚举法和基于遗传算法的多目标优化算法。在求出的可达信息率域内选定各源点的组播率向量后，可以利用单源组播网络的线性网络编码构造方法来构造出多源多宿组播网络的线性网络编码方案。本文提出的方法依赖于求网络的最大流，从而只能求出坐标为整数的边界点，即得出的可达信息率区域在边界处较为粗略，如何得到更为精确的可达信息率区域边界，则是下一步的研究内容。
参考文献：
[3]HO T， MEDARD M， KOETTER R， et al. A random linear network coding approach to multicast [J]. IEEE Transactions on Information Theory， 2006， 52（10）： 4413-4430.
[4]RAYMOND W Y. Information theory and network coding [M]. Berlin： Springer， 2010： 505-545.
[7]ROMANMOORTHY A， JAIN K， CHOU P A. Separating distributed source coding from network coding [J]. IEEE Transactions on Information Theory， 2006， 52（6）： 2785-2795.
[8]YOUAIL R S， CHRNG W， TAO S G. Achieving the information rate region for two sources two sinks network coding： An extended work [C]// ICIEA 2009： Proceedings of the 4th IEEE Conference on Industrial Electronics and Applications. Piscataway： IEEE， 2009： 768-722.
[9]HUANG S R. Network coding for multiple unicast over directed acyclic networks [D]. Ames： Iowa State University， 2013.
