Minimum cost multiple multicast network coding with quantized rates
Minimum cost multiple multicast network coding with quantized rates
复制标题
DOI：
10.1016/j.comnet.2012.11.017
复制
发表时间：
2013-04
期刊：
影响因子：
--
通讯作者：
M. Raayatpanah;H. Fathabadi;B. Khalaj;S. Khodayifar
中科院分区：
文献类型：
--
作者：
M. Raayatpanah;H. Fathabadi;B. Khalaj;S. Khodayifar
在本文中，我们考虑了具有会话内网络编码的多个组播会话，其中所有链路的速率都是基本速率的整数倍。虽然在通信链路上量化速率是很常见的，但传统的最小成本网络编码问题通常不能产生量化的解决方案。在本研究中，针对多组播会话的最小传输成本问题进行了研究。假设在每个会话的每个链路上的编码包注入速率取量化值。首先将该问题表述为一个混合整数线性规划问题，然后证明了该问题在一般图上是强np困难的。为了得到该问题的精确解，提出了一种有效的基于Benders分解的方案。该方案将该问题分解为一个主整数规划问题和若干线性规划子问题。通过随机网络上的数值结果，对所提方案的有效性进行了评价。
In this paper, we consider multiple multicast sessions with intra-session network coding where rates over all links are integer multiples of a basic rate. Although having quantized rates over communication links is quite common, conventional minimum cost network coding problem cannot generally result in quantized solutions. In this research, the problem of finding minimum cost transmission for multiple multicast sessions with network coding is addressed. It is assumed that the rate of coded packet injection at every link of each session takes quantized values. First, this problem is formulated as a mixed integer linear programming problem, and then it is proved that this problem is strongly NP-hard on general graphs. In order to obtain an exact solution for the problem, an effective and efficient scheme based on Benders decomposition is developed. Using this scheme the problem is decomposed into a master integer programming problem and several linear programming sub-problems. The efficiency of the proposed scheme is subsequently evaluated by numerical results on random networks.