Search

It is shown that a greedy orthogonal access scheme achieves the sum degrees of freedom (DoF) of all one-dimensional (all nodes placed along a straight line) convex cellular networks (where cells are convex regions) when no channel knowledge is available at the transmitters except the knowledge of the network topology. In general, optimality of orthogonal access holds neither for two-dimensional convex cellular networks nor for one-dimensional non-convex cellular networks, thus revealing a fundamental limitation that arises when both one-dimensional and convex properties are simultaneously enforced. The result also establishes the sum capacity of the corresponding class of index coding problems. © 2013 IEEE.

We present a condition for 1/2 degree of freedom for each user in constant $K$ -user single-antenna interference channels. This condition is sufficient for all and necessary for almost all channel matrices. Moreover, it applies to all channel topologies, i.e., to fully-connected channels as well as channels that have individual links absent, reflected by corresponding zeros in the channel matrix. Moreover, it captures the essence of interference alignment by virtue of being expressed in terms of a generic injectivity condition that guarantees separability of signal and interference. Finally, we provide codebook constructions achieving 1/2 degree of freedom for each user for all channel matrices satisfying the condition we identified. [ABSTRACT FROM AUTHOR]

The robust principles of treating interference as noise (TIN) when it is sufficiently weak, and avoiding it when it is not, form the background of this work. Combining TIN with the topological interference management (TIM) framework that identifies optimal interference avoidance schemes, we formulate a TIM-TIN problem for multilevel topological interference management, wherein only a coarse knowledge of channel strengths and no knowledge of channel phases is available to transmitters. To address the TIM-TIN problem, we first propose an analytical baseline approach, which decomposes a network into TIN and TIM components, allocates the signal power levels to each user in the TIN component, allocates signal vector space dimensions to each user in the TIM component, and guarantees that the product of the two is an achievable number of signal dimensions available to each user in the original network. Next, a distributed numerical algorithm called ZEST is developed. The convergence of the algorithm is demonstrated, leading to the duality of the TIM-TIN problem in terms of generalized degrees-of-freedom (GDoF). Numerical results are also provided to demonstrate the superior sum-rate performance and fast convergence of ZEST. [ABSTRACT FROM AUTHOR]

We present sum-set inequalities specialized to the generalized degrees of freedom (GDoF) framework. These are information theoretic lower bounds on the entropy of bounded density linear combinations of discrete, power-limited dependent random variables in terms of the joint entropies of arbitrary linear combinations of new random variables that are obtained by power level partitioning of the original random variables. These bounds generalize the aligned image sets approach, and are useful instruments to obtain GDoF characterizations for wireless networks, especially with multiple antenna nodes, subject to arbitrary channel strength and channel uncertainty levels. To demonstrate the utility of these bounds, we consider various examples of interference and broadcast channels for which we obtain tight GDoF characterizations with the aid of sum-set inequalities. [ABSTRACT FROM AUTHOR]

This paper obtains the first degrees of freedom (DoFs) bound that is provably sensitive tonetworkcoherence time, i.e., coherence time in an interference network, where all channels experience the same coherence patterns. This is accomplished by a novel adaptation of the aligned image sets bound and settles various open problems noted previously by Naderi and Avestimehr and by Gouet al.For example, a necessary and sufficient condition is obtained for the optimality of 1/2 DoF per user in a partially connected interference network, where the channel state information at the receivers (CSIRs) is perfect, the channel state information at the transmitters (CSITs) is instantaneous but limited to finite precision, and the network coherence time is $T_{c}=1$. The surprising insight that emerges is that even with perfect CSIR and instantaneous finite precision CSIT, the network coherence time matters, i.e., it has a DoF impact. [ABSTRACT FROM AUTHOR]

The main result of this paper is that an orthogonal access scheme, such as time division multiple access achieves the all-unicast degrees of freedom (DoF) region of the topological interference management problem if and only if the network topology graph is chordal bipartite, i.e., every cycle that can contain a chord, does contain a chord. The all-unicast DoF region includes the DoF region for any arbitrary choice of a unicast message set, so e.g., the results of Maleki and Jafar on the optimality of orthogonal access for the sum-DoF of one-dimensional convex networks are recovered as a special case. The result is also established for the corresponding topological representation of the index coding problem. [ABSTRACT FROM PUBLISHER]

We propose a cognitive blind interference alignment (BIA) scheme for macro-femto two-tier networks where the users are equipped with a single reconfigurable antenna. The proposed scheme fully cancels the intracell interference in both the upper and lower tiers. Moreover, it provides the optimal Degrees of Freedom (DoF) in the macro-tier while the lower tier subject to inter-tier interference achieves non-zero DoF. To do so, the proposed scheme relies on a topology management scheme where the users belong to the macro-tier if and only if they can optimally treat the interference caused by the transmission at the femto-tier as noise. The proposed scheme does not require any channel state information at the transmitter or data sharing between the macro- and femto-tiers. An outer bound of the DoF is derived for the considered macro-femto network. It is demonstrated that the proposed scheme can attain the outer bound subject to optimal sum DoF for the macro-tier. Furthermore, compared to previous approaches, cognitive BIA can achieve better sum rates for macro-femto networks for femtocells subject to different levels of inter-tier interference. [ABSTRACT FROM PUBLISHER]

A conjecture made by Lapidoth et al. at Allerton 2005 (also an open problem presented at ITA 2006) states that the degrees of freedom (DoF) of a two user broadcast channel, where the transmitter is equipped with two antennas and each user is equipped with one antenna, must collapse under finite precision channel state information at the transmitter (CSIT). That this conjecture, which predates interference alignment, has remained unresolved, is emblematic of a pervasive lack of understanding of the DoF of wireless networks—including interference and X networks—under channel uncertainty at the transmitter(s). In this paper, we prove that the conjecture is true in all non-degenerate settings (e.g., where the probability density function of unknown channel coefficients exists and is bounded). The DoF collapse even when perfect channel knowledge for one user is available to the transmitter. This also settles a related recent conjecture by Tandon et al. The key to our proof is a bound on the number of codewords that can cast the same image (within noise distortion) at the undesired receiver whose channel is subject to finite precision CSIT, while remaining resolvable at the desired receiver whose channel is precisely known by the transmitter. We are also able to generalize the result along two directions. First, if the peak of the probability density function is allowed to scale as O((\sqrt {P})^\alpha ) , representing the concentration of probability density (improving CSIT) due to, e.g., quantized feedback at rate ({\alpha }/{2})\log (P)$ , then the DoF is bounded above by $1+\alpha $ , which is also achievable under quantized feedback. Second, we generalize the result to arbitrary number of antennas at the transmitter, arbitrary number of single-antenna users, and complex channels. The generalization directly implies a collapse of DoF to unity under non-degenerate channel uncertainty for the general $K$ -user interference and $M\times N$ user $X$ networks as well. [ABSTRACT FROM AUTHOR]

It has been recently shown by Geng et al. that in a $K$ -user Gaussian interference network, if for each user, the desired signal strength is no less than the sum of the strengths of the strongest interference from this user and the strongest interference to this user (all signal strengths measured in dB scale), then power control and treating interference as noise (TIN) is sufficient to achieve the entire generalized degrees of freedom (GDoF) region. Motivated by the intuition that the deterministic model of Avestimehr et al. (Avestimehr-Diggavi-Tse deterministic model) is particularly suited for exploring the optimality of TIN, the results of Geng et al. are first re-visited under the ADT deterministic model, and are shown to directly translate between the Gaussian and deterministic settings. Next, we focus on the extension of these results to parallel interference networks, from a sum-capacity/sum-GDoF perspective. To this end, we interpret the explicit characterization of the sum capacity/sum GDoF of a TIN optimal network (without parallel channels) as a minimum weighted matching problem in combinatorial optimization, and obtain a simple characterization in terms of a partition of the interference network into vertex-disjoint cycles. Aided by insights from the cyclic partition, the sum-capacity optimality of TIN for $K$ -user parallel interference networks is characterized for the ADT deterministic model, leading ultimately to the corresponding GDoF results for the Gaussian setting. In both the cases, subject to a mild invertibility condition, the optimality of TIN is shown to extend to parallel networks in a separable fashion. [ABSTRACT FROM AUTHOR]

In many wireless networks, link strengths are affected by many topological factors, such as different distances, shadowing, and intercell interference, thus resulting in some links being generally stronger than other links. From an information theoretic point of view, accounting for such topological aspects is still a novel approach, that has been recently fueled by strong indications that such aspects can crucially affect transceiver and feedback design, as well as the overall performance. This paper here takes a step in exploring this interplay between topology, feedback, and performance. This is done for the two user broadcast channel with random fading, in the presence of a simple two-state topological setting of statistically strong versus weaker links, and in the presence of a practical ternary feedback setting of alternating channel state information at the transmitter [alternating channel state information at the transmitter (CSIT)] where for each channel realization, this CSIT can be perfect, delayed, or not available. In this setting, the work derives generalized degrees-of-freedom bounds and exact expressions, that capture performance as a function of feedback statistics and topology statistics. The results are based on novel topological signal management schemes that account for topology in order to fully utilize feedback. This is achieved for different classes of feedback mechanisms of practical importance, from which we identify specific feedback mechanisms that are best suited for different topologies. This approach offers further insight on how to split the effort—of channel learning and feeding back CSIT—for the strong versus for the weaker link. Further intuition is provided on the possible gains from topological spatio-temporal diversity, where topology changes in time and across users [ABSTRACT FROM PUBLISHER]

An interference alignment perspective is used to identify the simplest instances (minimum possible number of edges in the alignment graph, not more than 2 interfering messages at any destination) of index coding problems where non-Shannon information inequalities are necessary for capacity characterization. In particular, this includes the first known example of a multiple unicast (one destination per message) index coding problem where non-Shannon information inequalities are shown to be necessary. The simplest multiple unicast example has 7 edges in the alignment graph and 11 messages. The simplest multiple groupcast (multiple destinations per message) example has 6 edges in the alignment graph, 6 messages, and 10 receivers. For both the simplest multiple unicast and multiple groupcast instances, the best outer bound based on only Shannon inequalities is 2/5, which is tightened to 11/28 by the use of the Zhang–Yeung non-Shannon type information inequality, and the linear capacity is shown to be 5/13 using the Ingleton inequality. Conversely, identifying the minimal challenging aspects of the index coding problem allows an expansion of the class of solved index coding problems up to (but not including) these instances. [ABSTRACT FROM AUTHOR]

We consider the topological interference management problem for a downlink hexagonal cellular network, where the channel state information at the transmitters is limited to just the network topology. Recent work by Jafar showed that if interference is limited to only near the cell boundary, then, an aligned frequency reuse pattern achieves the optimal value of 6/7 degrees of freedom (DoF) per cell, as opposed to the conventional frequency reuse baseline of 1/3 DoF per cell. We generalize the setting to include interference from multiple layers of adjacent cells and characterize how the gains of the optimal solution over basic frequency reuse diminish with increasing number of interference layers. Next, we focus on single-layer interference and explore the sensitivity of the idealized assumptions behind the connectivity model of Jafar, which achieves higher DoF but only at the cost of a higher effective noise floor than the baseline, and under idealized placements of users. A modified connectivity model that operates at a comparable noise-floor to the baseline is then studied, and its DoF are shown to be bounded above by 6/11 and below by 1/2. Through numerical simulations, we compare the solutions that achieve 6/7, 1/2, and 1/3 DoF per cell and find that, while both the 6/7 and the 1/2 DoF solutions beat the baseline 1/3 figure, between them, the 1/2 DoF aligned frequency reuse pattern is more robust for small cell networks particularly for random users' distribution on the cell boundaries. [ABSTRACT FROM PUBLISHER]

We propose a blind interference alignment scheme for partially connected cellular networks. The scheme cancels both intracell and intercell interference by relying on receivers with one reconfigurable antenna and by allowing users at the cell edge to be served by all the base stations in their proximity. An outer bound for the degrees of freedom is derived for general partially connected networks with single-antenna receivers when knowledge of the channel state information at the transmitter is not available. It is demonstrated that for symmetric scenarios, this outer bound is achieved by the proposed scheme. On the other hand, for asymmetric scenarios, the achievable degrees of freedom are not always equal to the outer bound. However, the penalty is typically small, and the proposed scheme outperforms other blind interference alignment schemes. Moreover, significant reduction of the supersymbol length is achieved compared with a standard blind interference alignment strategy designed for fully connected networks. [ABSTRACT FROM PUBLISHER]

We consider the problem of network coding across three unicast sessions over a directed acyclic graph, where the sender and receiver of each unicast session are both connected to the network via a single edge of unit capacity. We consider a network model in which the middle of the network can only perform random linear network coding, and restrict our approaches to precoding-based linear schemes, where the senders use precoding matrices to encode source symbols. We adapt a precoding-based interference alignment technique, originally developed for the wireless interference channel, to construct a precoding-based linear scheme, which we refer to as precoding-based network alignment scheme (PBNA). A primary difference between this setting and the wireless interference channel is that the network topology can introduce dependencies among the elements of the transfer matrix, which we refer to as coupling relations, and can potentially affect the achievable rate of PBNA. We identify all these coupling relations and interpret them in terms of network topology. We then present polynomial-time algorithms to check the presence of these coupling relations in a particular network. Finally, we show that, depending on the coupling relations present in the network, the optimal symmetric rate achieved by precoding-based linear scheme can take only three possible values, all of which can be achieved by PBNA. [ABSTRACT FROM PUBLISHER]

The index coding problem is studied from an interference alignment perspective providing new results as well as new insights into, and generalizations of, previously known results. An equivalence is established between the capacity of multiple unicast index coding (where each message is desired by exactly one receiver), and groupcast index coding (where a message can be desired by multiple receivers), which settles the heretofore open question of insufficiency of linear codes for the multiple unicast index coding problem by equivalence with groupcast settings, where this question has previously been answered. Necessary and sufficient conditions for the achievability of rate half per message in the index coding problem are shown to be a natural consequence of interference alignment constraints, and generalizations to feasibility of rate \({1}/(L+1)\) per message when each destination desires at least \(L\) messages, are similarly obtained. Finally, capacity optimal solutions are presented to a series of symmetric index coding problems inspired by the local connectivity and local interference characteristics of wireless networks. The solutions are based on vector linear coding. [ABSTRACT FROM AUTHOR]

This paper studies linear interference networks, both wired and wireless, with no channel state information at the transmitters except a coarse knowledge of the end-to-end one-hop topology of the network that only allows a distinction between weak (zero) and significant (nonzero) channels and no further knowledge of the channel coefficients' realizations. The network capacity (wired) and degrees of freedom (DoF) (wireless) are found to be bounded above by the capacity of an index coding problem for which the antidote graph is the complement of the given interference graph. The problems are shown to be equivalent under linear solutions. An interference alignment perspective is then used to translate the existing index coding solutions into the wired network capacity and wireless network DoF solutions, as well as to find new and unified solutions to different classes of all three problems. [ABSTRACT FROM PUBLISHER]

We show that an M\times N user MIMO X network with A antennas at each node has A\left(MN\overM+N-1\right) degrees of freedom (DoF), thus resolving in this case a discrepancy between the spatial scale invariance conjecture (scaling the number of antennas at each node by a constant factor will scale the total DoF by the same factor) and a decomposability property of overconstrained wireless networks. While the best previously known general DoF outer bound is consistent with the spatial invariance conjecture, the best previously known general DoF inner bound, inspired by the K user MIMO interference channel, was based on the decomposition of every transmitter and receiver into multiple single antenna nodes, transforming the network into an AM\times AN user SISO X network. While such a decomposition is DoF optimal for the K user MIMO interference channel, a gap remained between the best inner and outer bounds for the MIMO X channel. Here we close this gap with the new insight that the MIMO X network is only one-sided decomposable, i.e., either all the transmitters or all the receivers (but not both) can be decomposed by splitting multiple antenna nodes into multiple single antenna nodes without loss of DoF. The result is extended to SIMO and MISO X networks as well and in each case the DoF results satisfy the spatial scale invariance property. [ABSTRACT FROM PUBLISHER]

The high repair bandwidth cost of (n,k) maximum distance separable (MDS) erasure codes has motivated a new class of codes that can reduce repair bandwidth over that of conventional MDS codes. In this paper, we address (n,k,d) exact repair MDS codes, which allow for any single failed node to be repaired exactly with access to any arbitrary set of d survivor nodes. We show the existence of exact repair MDS codes that achieve minimum repair bandwidth (matching the cut-set lower bound) for arbitrary admissible (n,k,d), i.e., k \leq d \leq n-1. Moreover, we extend our results to show the optimality of our codes for multiple-node failure scenarios in which an arbitrary set of r \leq n-k failed nodes needs to repaired. Our approach is based on asymptotic interference alignment proposed by Cadambe and Jafar. As a byproduct, we also characterize the capacity of a class of multisource nonmulticast networks. [ABSTRACT FROM PUBLISHER]

The main contribution of this paper is the insight that the transmitters' knowledge of channel coherence intervals alone (without any knowledge of the values of channel coefficients) can be surprisingly useful in a multiuser setting, illustrated by the idea of blind interference alignment that is introduced in this work. Specifically, we explore five network communication problems where the possibility of interference alignment, and consequently the total number of degrees of freedom (DoF) with channel uncertainty at the transmitters, are unknown. These problems share the common property that in each case the best known outer bounds are essentially robust to channel uncertainty and represent the outcome with interference alignment, but the best inner bounds—in some cases conjectured to be optimal—predict a total collapse of DoF, thus indicating the infeasibility of interference alignment under channel uncertainty at transmitters. For each of these settings we show that even with no knowledge of channel coefficient values at the transmitters, under certain heterogeneous block fading models, i.e., when certain users experience smaller coherence time/bandwidth than others, blind interference alignment can be achieved. In each case we also establish the DoF optimality of the blind interference alignment scheme. [ABSTRACT FROM PUBLISHER]

We propose a blind interference alignment scheme for the vector broadcast channel where the transmitter is equipped with M antennas and there are K receivers, each equipped with a reconfigurable antenna capable of switching among M preset modes. Without any knowledge of the channel coefficient values at the transmitters and with only mild assumptions on the channel coherence structure we show that MK\over M+K-1 degrees of freedom are achievable. The key to the blind interference alignment scheme is the ability of the receivers to switch between reconfigurable antenna modes to create short term channel fluctuation patterns that are exploited by the transmitter. The achievable scheme does not require cooperation between transmit antennas and is therefore applicable to the M\times K~X network as well. Only finite symbol extensions are used, and no channel knowledge at the receivers is required to null the interference. [ABSTRACT FROM PUBLISHER]

It is known that the capacity of parallel (multicarrier) Gaussian point-to-point, multiple access and broadcast channels can be achieved by separate encoding for each subchannel (carrier) subject to a power allocation across carriers. In this paper we show that such a separation does not apply to parallel Gaussian interference channels in general. A counter example is provided in the form of a 3 user interference channel where separate encoding can only achieve a sum capacity of 2 log(1 + 3 SNR) while the actual capacity, achieved only by joint encoding across carriers, is 3 log(1 + 2 SNR). As a byproduct of our analysis, we propose a class of multiple-access-outer bounds on the capacity of the 3 user interference channel. [ABSTRACT FROM AUTHOR]

In this correspondence, we show that the exact number of spatial degrees of freedom (DOF) for a two user nondegenerate (full rank channel matrices) multiple-input-multiple-output (MIMO) Gaussian interference channel with M1, M2 antennas at transmitters 1, 2 and N1, N2 antennas at the corresponding receivers, and perfect channel knowledge at all transmitters and receivers, is min {M1 + M2, N1 + N2, max( M1, N2 )max ( M2, N1 ) }. A constructive achievability proof shows that zero forcing is sufficient to achieve all the available DOF on the two user MIMO interference channel. We also show through an example of a share-and-transmit scheme how the gains of transmitter cooperation may be entirely offset by the cost of enabling that cooperation so that the available DOF are not increased. [ABSTRACT FROM AUTHOR]

We consider a multiple-input-single-output (MISO) broadcast channel with mixed channel state information at the transmitter (CSIT) that consists of imperfect current CSIT and perfect outdated CSIT. Recent work by Kobayashi et al. presented a scheme that exploits both imperfect current CSIT and perfect outdated CSIT and achieves higher degrees of freedom (DoF) than possible with only imperfect current CSIT or only outdated CSIT individually. In this work, we further improve the achievable DoF in this setting by incorporating additional private messages, and provide a tight information theoretic DoF outer bound, thereby identifying the DoF optimal use of mixed CSIT. The new result is stronger even in the original setting of only delayed CSIT, because it allows us to remove the restricting assumption of statistically equivalent fading for all users. [ABSTRACT FROM PUBLISHER]

Most multiuser precoding techniques require accurate channel state information at the transmitter (CSIT) to maintain orthogonality between the users. Such techniques have proven quite fragile in time-varying channels because the CSIT is inherently imperfect due to quantization error and feedback delay. An alternative approach recently proposed by Maddah-Ali and Tse (MAT) allows for significant multiplexing gain in the multi-input single-output (MISO) broadcast channel (BC) even with CSIT that is "completely stale", i.e., uncorrelated with the current channel state. With K users, their scheme claims to lose only a log(K) factor relative to the full K degrees of freedom (DoF) attainable in the MISO BC with perfect CSIT for large K. However, their result does not consider the cost of the feedback, which is potentially very large in high mobility (short channel coherence time). In this paper, we more closely examine the MAT scheme and compare its maximum net DoF gain to single user transmission (which always achieves 1 DoF) and partial CSIT linear precoding (which achieves up to K). In particular, assuming the channel coherence time is N symbol periods and the feedback delay is Nfd, we show that when N < (1+o(1)) K\log K (short coherence time), single user transmission performs best, whereas for N> (1+o(1)) (Nfd+ K / log K)(1-log^{-1}K)^{-1} (long coherence time), zero-forcing precoding outperforms the other two. The MAT scheme is optimal for intermediate coherence times, which for practical parameter choices is indeed quite a large and significant range, even accounting for the feedback cost. [ABSTRACT FROM PUBLISHER]

We consider a cognitive radio system where the secondary transmitter varies its transmit power based on the information available from the spectrum sensor. The operation of the secondary user is governed by its peak transmit power constraint and an average interference constraint at the primary receiver. Without restricting the sensing scheme (total received energy, or correlation etc), we characterize the power adaptation strategies that maximize the secondary user's SNR and capacity. We show that, in general, the capacity optimal power adaptation requires decreasing the secondary transmit power from the peak power to zero in a continuous fashion as the probability of the primary user being present increases. In contrast, we find that that power control that maximizes the SNR is binary, i.e., if there is any transmission, it takes place only at the peak power level. Numerical results for common spectrum sensing schemes show that the SNR and capacity maximizing schemes can be very different. With an average transmit power constraint at the secondary radio, both the SNR and capacity optimal power control schemes are observed to be non-binary. Further, we find that with secondary channel knowledge at the cognitive transmitter, the optimal SNR with an average transmit power constraint is unbounded. [ABSTRACT FROM PUBLISHER]