Capacity Results for Multicasting Nested Message Sets Over Combination Networks
Capacity Results for Multicasting Nested Message Sets Over Combination Networks
复制标题
通过组合网络多播嵌套消息集的容量结果
DOI：
--
复制
发表时间：
2014
影响因子：
2.5
通讯作者：
S. Diggavi
中科院分区：
文献类型：
--
作者：
S. S. Bidokhti;V. Prabhakaran;S. Diggavi
研究了在一类称为组合网络的网络上多播两个嵌套消息的问题。一个源向多个接收者多播两个消息，一个公共消息和一个私有消息。一个子集的接收者（称为公共接收者）只需要公共消息，其余的接收者（称为私有接收者）需要公共和私有消息。讨论了三种采用线性叠加编码的编码方案，并在特殊情况下证明了它们的最优性。标准的线性叠加方案被证明是最佳的网络与两个公共接收器和任何数量的私人接收器。当公共接收器的数量增加时，该方案不再是最优的。讨论了两种改进：一种是在源处使用预编码，另一种是使用块马尔可夫编码方案。这两个方案所实现的速率区域的特点是在可行性问题。这两个内界被证明是三个（或更少）的公共和任何数量的私人接收器的网络的容量区域。虽然内边界一般不可比，但通过示例示出，通过块马尔可夫编码方案实现的区域可以严格地包括通过预编码/线性叠加方案实现的区域。最优性结果建立在Balister和Bolloba（2007）关于熵函数的子模块性的一般框架上。一个等价的图形表示，并证明了一个引理，可能是独立的利益。基于组合网络与广播信道之间的联系，提出了一种新的分组马尔可夫编码方案。所获得的速率区域包括先前已知的速率区域。这一列入是否严格仍有待确定。
The problem of multicasting two nested messages is studied over a class of networks known as combination networks. A source multicasts two messages, a common and a private message, to several receivers. A subset of the receivers (called the public receivers) only demand the common message, and the rest of the receivers (called the private receivers) demand both the common and the private message. Three encoding schemes are discussed that employ linear superposition coding, and their optimality is proved in special cases. The standard linear superposition scheme is shown to be optimal for networks with two public receivers and any number of private receivers. When the number of public receivers increases, this scheme stops being optimal. Two improvements are discussed: one using pre-encoding at the source, and one using a block Markov encoding scheme. The rate-regions that are achieved by the two schemes are characterized in terms of feasibility problems. Both inner bounds are shown to be the capacity region for networks with three (or fewer) public and any number of private receivers. Although the inner bounds are not comparable in general, it is shown through an example that the region achieved by the block Markov encoding scheme may strictly include the region achieved by the pre-encoding/linear superposition scheme. Optimality results are founded on the general framework of Balister and Bollobás (2007) for sub-modularity of the entropy function. An equivalent graphical representation is introduced and a lemma is proved that might be of independent interest. Motivated by the connections between combination networks and broadcast channels, a new block Markov encoding scheme is proposed for broadcast channels with two nested messages. The rate-region that is obtained includes the previously known rate-regions. It remains open whether this inclusion is strict.