Sum-Networks From Incidence Structures: Construction and Capacity Analysis
Sum-Networks From Incidence Structures: Construction and Capacity Analysis
复制标题
DOI：
10.1109/tit.2017.2765661
复制
发表时间：
2016-11
影响因子：
2.5
通讯作者：
Ardhendu Shekhar Tripathy;A. Ramamoorthy
中科院分区：
文献类型：
--
作者：
Ardhendu Shekhar Tripathy;A. Ramamoorthy
总和网络是在有向的无环网络上函数计算问题的实例，在该网络中，每个终端节点都希望通过在所有源节点观察到的信息的有限字段计算总和。经过良好研究的多个单播网络通信问题的许多特征也适用于总和，这是由于两个问题之间的已知减少。在本文中，我们描述了一种使用发病率结构来构建总和实例的算法。评估了其中几个总和家族的计算能力。与多个单播问题的编码能力不同，总和网络的计算能力取决于计算总和的有限字段的特征。这种依赖非常强。我们展示了总和网络的示例，这些示例在一个特征上具有速率1解决方案，但在不同特征上接近零的速率。此外，总和可以具有不同字母的任意计算能力。
A sum-network is an instance of a function computation problem over a directed acyclic network, in which each terminal node wants to compute the sum over a finite field of the information observed at all the source nodes. Many characteristics of the well-studied multiple unicast network communication problem also hold for sum-networks, due to a known reduction between the two problems. In this paper, we describe an algorithm to construct families of sum-network instances using incidence structures. The computation capacity of several of these sum-network families is evaluated. Unlike the coding capacity of a multiple unicast problem, the computation capacity of sum-networks depends on the characteristic of the finite field over which the sum is computed. This dependence is very strong; we show examples of sum-networks that have a rate-1 solution over one characteristic but a rate close to zero over a different characteristic. In addition, a sum-network can have arbitrarily different computation capacities for different alphabets.