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 ...
详细信息
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.
The index coding problem has recently attracted a significant attention from the research community due to its theoretical significance and applications in wireless ad hoc networks. An instance of the index coding pro...
详细信息
The index coding problem has recently attracted a significant attention from the research community due to its theoretical significance and applications in wireless ad hoc networks. An instance of the index coding problem includes a sender that holds a set of information messages X = {x(1),...,x(k)} and a set of receivers R. Each receiver rho = (x,H) in R needs to obtain a message x is an element of X and has prior side information consisting of a subset H of X. The sender uses a noiseless communication channel to broadcast encoding of messages in X to all clients. The objective is to find an encoding scheme that minimizes the number of transmissions required to satisfy the demands of all the receivers. In this paper, we analyze the relation between the index coding problem, the more general network coding problem, and the problem of finding a linear representation of a matroid. In particular, we show that any instance of the network coding and matroid representation problems can be efficiently reduced to an instance of the index coding problem. Our reduction implies that many important properties of the network coding and matroid representation problems carry over to the index coding problem. Specifically, we show that vector linear codes outperform scalar linear index codes and that vector linear codes are insufficient for achieving the optimum number of transmissions.
We study upper bounds on the sum-rate of multiple-unicasts. We approximate the Generalized Network Sharing Bound (GNS cut) of the multiple-unicasts network coding problem with k independent sources. Our approximation ...
详细信息
ISBN:
(纸本)9781467377041
We study upper bounds on the sum-rate of multiple-unicasts. We approximate the Generalized Network Sharing Bound (GNS cut) of the multiple-unicasts network coding problem with k independent sources. Our approximation algorithm runs in polynomial time and yields an upper bound on the joint source entropy rate, which is within an O (log(2) k) factor from the GNS cut. It further yields a vector-linear network code that achieves joint source entropy rate within an O (log(2) k) factor from the GNS cut, but not with independent sources: the code induces a correlation pattern among the sources. Our second contribution is establishing a separation result for vector-linear network codes: for any given field F there exist networks for which the optimum sum-rate supported by vector-linear codes over F for independent sources can be multiplicatively separated by a factor of k(1-delta), for any constant delta > 0, from the optimum joint entropy rate supported by a code that allows correlation between sources. Finally, we establish a similar separation result for the asymmetric optimum vector-linear sum-rates achieved over two distinct fields F-p and F-q for independent sources, revealing that the choice of field can heavily impact the performance of a linear network code.
In this work, we formulate and study a data dissemination problem, which can be viewed as a generalization of the index coding problem and of the data exchange problem to networks with an arbitrary topology. We define...
详细信息
ISBN:
(纸本)9781509018246
In this work, we formulate and study a data dissemination problem, which can be viewed as a generalization of the index coding problem and of the data exchange problem to networks with an arbitrary topology. We define r-solvable networks, in which data dissemination can be achieved in r > 0 communications rounds. We show that the optimum number of transmissions for any one-round communications scheme is given by the minimum rank of a certain constrained family of matrices. For a special case of this problem, called bipartite data dissemination problem, we present lower and upper graph-theoretic bounds on the optimum number of transmissions. For general r-solvable networks, we derive an upper bound on the minimum number of transmissions in any scheme with >= r rounds. We experimentally compare the obtained upper bound to a simple lower bound.
Broadcasting K independent messages to multiple users where each user has a subset of the K messages as side information is studied. This problem can be regarded as a natural generalization of the well-known index cod...
详细信息
ISBN:
(纸本)9781467377041
Broadcasting K independent messages to multiple users where each user has a subset of the K messages as side information is studied. This problem can be regarded as a natural generalization of the well-known index coding problem to the physical-layer additive white Gaussian noise channel due to the analogy between these two problems. Recently, Natarajan, Hong, and Viterbo proposed a novel broadcasting strategy called lattice index coding which uses lattices constructed over principal ideal domains (PIDs) as a transmission scheme and showed that such a scheme provides uniform side information gains. In this paper, we generalize this strategy to rings of algebraic integers of number fields which may not be PIDs and show upper and lower bounds on the achievable side information gains. This generalization substantially enlarges the design space and includes some interesting examples in which all the messages are from the same field.
In this work, we formulate and study a data dissemination problem, which can be viewed as a generalization of the index coding problem and of the data exchange problem to networks with an arbitrary topology. We define...
详细信息
ISBN:
(纸本)9781509018253
In this work, we formulate and study a data dissemination problem, which can be viewed as a generalization of the index coding problem and of the data exchange problem to networks with an arbitrary topology. We define r-solvable networks, in which data dissemination can be achieved in r> 0 communications rounds. We show that the optimum number of transmissions for any one-round communications scheme is given by the minimum rank of a certain constrained family of matrices. For a special case of this problem, called bipartite data dissemination problem, we present lower and upper graph-theoretic bounds on the optimum number of transmissions. For general r-solvable networks, we derive an upper bound on the minimum number of transmissions in any scheme with> r rounds. We experimentally compare the obtained upper bound to a simple lower bound.
The min-rank of a digraph was shown to represent the length of an optimal scalar linear solution of the corresponding instance of the index coding with Side Information (ICSI) problem. In this paper, the graphs and di...
详细信息
The min-rank of a digraph was shown to represent the length of an optimal scalar linear solution of the corresponding instance of the index coding with Side Information (ICSI) problem. In this paper, the graphs and digraphs of near-extreme min-ranks are studied. Those graphs and digraphs correspond to the ICSI instances having near-extreme transmission rates when using optimal scalar linear index codes. In particular, it is shown that the decision problem whether a digraph has min-rank two is NP-complete. By contrast, the same question for graphs can be answered in polynomial time. In addition, a circuit-packing bound is revisited, and several families of digraphs, optimal with respect to this bound, whose min-ranks can be found in polynomial time, are presented.
index coding (IC), which can be regarded as a special class of network coding, deals with the problem of sending a number of packets to a group of receivers, each of which requests one packet and may have some other p...
详细信息
index coding (IC), which can be regarded as a special class of network coding, deals with the problem of sending a number of packets to a group of receivers, each of which requests one packet and may have some other packets in its cache. This paper generalizes the IC problem in that both the packet requested by a receiver and the packets in its cache can be linear combinations of the packets. To minimize the number of transmissions required, a heuristic algorithm based on the idea of partitioning the users into coding groups is designed. To realize this idea, a polynomial time algorithm to determine whether a set of users form a coding group over the binary field or a field with a size larger than the number of users is constructed. For users that form a coding group, the corresponding encoding vector can be also found. A lower bound is derived in order to evaluate the performance of the heuristic algorithm. Numerical results show that the number of transmissions required by the heuristic algorithm and the lower bound both grow roughly linearly with the number of users, and the heuristic algorithm outperforms some benchmark algorithms.
Information Centric Network (ICN) is a content-based information dissemination approach that improves the content delivery and latency. We introduce a modified architecture for ICN which can reduce the traffic by comb...
详细信息
ISBN:
(纸本)9781479930012
Information Centric Network (ICN) is a content-based information dissemination approach that improves the content delivery and latency. We introduce a modified architecture for ICN which can reduce the traffic by combining multiple messages and facilitate the data distribution in the network. By observing the similarities between index coding and ICN architectures, we propose to combine these two techniques to arrive at a new architecture that enhances data delivery in networks beyond original ICN scheme. By taking advantage of some concepts such as linear network coding, caching and index coding, we demonstrate that we can reduce the traffic and increase the capacity of ICN architecture by combining (network encoding) multiple messages requested by different nodes and sending them in one transmission. We demonstrate that each node will be able to extract its desired message from the combined encoded messages. To achieve this goal, we first define a modified version of index coding in order to apply index coding for both wired and wireless networks. Further, we introduce a hybrid caching scheme that includes both central and distributed caching to support two different goals. Our hybrid caching approach is a combination of conventional caching in ICN that caches the content in various network locations in order to make the content readily available to nodes and a new distributed caching scheme across nodes in the network to improve the performance of the entire system. The purpose of the second caching scheme is to allow central cache system to combine multiple contents in order to serve several client nodes simultaneously with a single transmission of encoded messages. The focus of this paper is to describe the new ICN architecture and demonstrate the advantages of the new architecture.
The following source coding problem was introduced by Birk and Kol: a sender holds a word x is an element of {0, 1}(n), and wishes to broadcast a codeword to n receivers, R-1, ... , R-n. The receiver R-i is interested...
详细信息
The following source coding problem was introduced by Birk and Kol: a sender holds a word x is an element of {0, 1}(n), and wishes to broadcast a codeword to n receivers, R-1, ... , R-n. The receiver R-i is interested in x(i), and has prior side information comprising some subset of the n bits. This corresponds to a directed graph G on n vertices, where i(j) is an edge iff R-i knows the bit x(j). An index code for G is an encoding scheme which enables each R-i to always reconstruct x(i), given his side information. The minimal word length of an index code was studied by Bar-Yossef, Birk, Jayram, and Kol (FOCS'06). They introduced a graph parameter, minrk(2) (G), which completely characterizes the length of an optimal linear index code for G. They showed that in various cases linear codes attain the optimal word length, and conjectured that linear index coding is in fact always optimal. In this work, we disprove the main conjecture of Bar-Yossef, Birk, Jayram, and Kol in the following strong sense: for any epsilon > 0 and sufficiently large n, there is an n-vertex graph G so that every linear index code for G requires codewords of length at least n(1-epsilon), and yet a nonlinear index code for G has a word length of n(epsilon). This is achieved by an explicit construction, which extends Alon's variant of the celebrated Ramsey construction of Frankl and Wilson. In addition, we study optimal index codes in various, less restricted, natural models, and prove several related properties of the graph parameter minrk(G).
暂无评论