A Linear Network Code Construction for General Integer Connections Based on the Constraint Satisfaction Problem
A Linear Network Code Construction for General Integer Connections Based on the Constraint Satisfaction Problem
复制标题
DOI：
10.1109/tnet.2017.2746755
复制
发表时间：
2017-10
期刊：
影响因子：
--
通讯作者：
Ying Cui;M. Médard;Edmund M. Yeh;Douglas Leith;Fan Lai;K. Duffy
中科院分区：
文献类型：
--
作者：
Ying Cui;M. Médard;Edmund M. Yeh;Douglas Leith;Fan Lai;K. Duffy
在容量受限的网络中，寻找一般连接的网络代码是一个固有的困难问题。利用网络编码的一般连接的资源最小化进一步复杂化。现有的解决方案识别方法主要依赖于高度受限的网络代码类，并且几乎都是集中式的。在本文中，我们引入线性网络混合系数的代码建设的一般连接，推广随机线性网络编码的组播连接。对于这样的代码建设，我们提出的问题，成本最小化的子图中涉及的编码解决方案，并将此最小化的基于路径的约束满足问题（CSP）和基于边的CSP。在CSP一般是NP完全问题的情况下，利用通信自由学习方法，提出了一种基于路径的概率分布式算法和一种基于边的概率分布式算法，该算法在有限时间内几乎必然收敛.我们的方法允许相当一般的编码流，保证不超过路由的成本，并显示了一个可能的分布式实现。数值结果表明，我们的方法比现有的方法的性能改善。
The problem of finding network codes for general connections is inherently difficult in capacity constrained networks. Resource minimization for general connections with network coding is further complicated. Existing methods for identifying solutions mainly rely on highly restricted classes of network codes, and are almost all centralized. In this paper, we introduce linear network mixing coefficients for code constructions of general connections that generalize random linear network coding for multicast connections. For such code constructions, we pose the problem of cost minimization for the subgraph involved in the coding solution and relate this minimization to a path-based constraint satisfaction problem (CSP) and an edge-based CSP. While CSPs are NP-complete in general, we present a path-based probabilistic distributed algorithm and an edge-based probabilistic distributed algorithm with almost sure convergence in finite time by applying communication free learning. Our approach allows fairly general coding across flows, guarantees no greater cost than routing, and shows a possible distributed implementation. Numerical results illustrate the performance improvement of our approach over existing methods.