The cooperative data exchange problem is studied for the fully connected network. In this problem, each node initially only possesses a subset of the @math packets making up the file. Nodes make broadcast transmissions that are received by all other nodes. The goal is for each node to recover the full file. In this paper, we present a polynomial-time deterministic algorithm to compute the optimal (i.e., minimal) number of required broadcast transmissions and to determine the precise transmissions to be made by the nodes. A particular feature of our approach is that each of the @math transmissions is a linear combination of exactly @math packets, and we show how to optimally choose the value of @math We also show how the coefficients of these linear combinations can be chosen by leveraging a connection to Maximum Distance Separable (MDS) codes. Moreover, we show that our method can be used to solve cooperative data exchange problems with weighted cost as well as the so-called successive local omniscience problem.
For solving the CCDE problem, only knowing the minimal number of required transmissions is not enough. It is also necessary to design the coding scheme. Given the total number of transmissions, designing the coding scheme is a multicast network code construction problem and can be solved by the polynomial time algorithm proposed by Jaggi in @cite_8 .
@cite_8
2156567124 1975409994 2147198176 2963364234
This paper deals with the problem of multicasting a set of discrete memoryless correlated sources (DMCS) over a cooperative relay network. Necessary conditions with cut-set interpretation are presented. A Joint source-Wyner-Ziv encoding sliding window decoding scheme is proposed, in which decoding at each receiver is done with respect to an ordered partition of other nodes. For each ordered partition a set of feasibility constraints is derived. Then, utilizing the submodular property of the entropy function and a novel geometrical approach, the results of different ordered partitions are consolidated, which lead to sufficient conditions for our problem. The proposed scheme achieves operational separation between source coding and channel coding. It is shown that sufficient conditions are indeed necessary conditions in two special cooperative networks, namely, Aref network and finite-field deterministic network. Also, in Gaussian cooperative networks, it is shown that reliable transmission of all DMCS whose Slepian-Wolf region intersects the cut-set bound region within a constant number of bits, is feasible. In particular, all results of the paper are specialized to obtain an achievable rate region for cooperative relay networks which includes relay networks and two-way relay networks. In this paper, we consider the problem of minimizing the completion delay for instantly decodable network coding (IDNC) in wireless multicast and broadcast scenarios. We are interested in this class of network coding due to its numerous benefits, such as low decoding delay, low coding and decoding complexities, and simple receiver requirements. We first extend the IDNC graph, which represents all feasible IDNC coding opportunities, to efficiently operate in both multicast and broadcast scenarios. We then formulate the minimum completion delay problem for IDNC as a stochastic shortest path (SSP) problem. Although finding the optimal policy using SSP is intractable, we use this formulation to draw the theoretical guidelines for the policies that can minimize the completion delay in IDNC. Based on these guidelines, we design a maximum weight clique selection algorithm, which can efficiently reduce the IDNC completion delay in polynomial time. We also design a quadratic-time heuristic clique selection algorithm, which can operate in real-time applications. Simulation results show that our proposed algorithms significantly reduce the IDNC completion delay compared to the random and maximum-rate algorithms, and almost achieve the global optimal completion delay performance over all network codes in broadcast scenarios. We first consider a topology consisting of one source, two destinations and one relay. For such a topology, it is shown that a network coding based cooperative (NCBC) multicast scheme can achieve a diversity order of two. In this paper, we discuss and analyze NCBC in a systematic way as well as compare its performance with two other multicast protocols. The throughput, delay and queue length for each protocol are evaluated. In addition, we present an optimal scheme to maximize throughput subject to delay and queue length constraints. Numerical results will demonstrate that network coding can bring significant gains in terms of throughput. For a network with one sender, n receivers (users) and m possible messages (files), caching side information at the users allows to satisfy arbitrary simultaneous demands by sending a common (multicast) coded message. In the worst-case demand setting, explicit deterministic and random caching strategies and explicit linear coding schemes have been shown to be order optimal. In this work, we consider the same scenario where the user demands are random i.i.d., according to a Zipf popularity distribution. In this case, we pose the problem in terms of the minimum average number of equivalent message transmissions. We present a novel decentralized random caching placement and a coded delivery scheme which are shown to achieve order-optimal performance. As a matter of fact, this is the first order-optimal result for the caching and coded multicasting problem in the case of random demands.