Search

We present a framework for random access that is based on three elements: physical-layer network coding (PLNC), signature codes, and tree splitting. In presence of a collision, physical-layer network coding enables the receiver to decode, i.e., compute, the sum of the packets that were transmitted by the individual users. For each user, the packet consists of the user’s signature, as well as the data that the user wants to communicate. As long as no more than $K$ users collide, their identities can be recovered from the sum of their signatures. This framework for creating and transmitting packets can be used as a fundamental building block in random access algorithms, since it helps to deal efficiently with the uncertainty of the set of contending terminals. In this paper, we show how to apply the framework in conjunction with a tree-splitting algorithm, which is required to deal with the case that more than $K$ users collide. We demonstrate that our approach achieves throughput that tends to 1 rapidly as $K$ increases. We also present results on net data-rate of the system, showing the impact of the overheads of the constituent elements of the proposed protocol. We compare the performance of our scheme with an upper bound that is obtained under the assumption that the active users are a priori known. Also, we consider an upper bound on the net data-rate for any PLNC-based strategy in which one linear equation per slot is decoded. We show that already at modest packet lengths, the net data-rate of our scheme becomes close to the second upper bound, i.e., the overhead of the contention resolution algorithm and the signature codes vanishes. [ABSTRACT FROM AUTHOR]

In this paper, we propose a new coding scheme and establish new bounds on the capacity region for the multi-sender unicast index-coding problem. We revisit existing partitioned distributed composite coding (DCC) proposed by Sadeghi et al. and identify its limitations in the implementation of multi-sender composite coding and in the strategy of sender partitioning. We then propose two new coding components to overcome these limitations and develop a multi-sender cooperative composite coding (CCC). We show that CCC can strictly improve upon partitioned DCC, and is the key to achieve optimality for a number of index-coding instances. The usefulness of CCC and its special cases is illuminated via non-trivial examples, and the capacity region is established for each example. Comparisons between CCC and other non-cooperative schemes in recent works are also provided to further demonstrate the advantage of CCC. [ABSTRACT FROM AUTHOR]

Consider two remote nodes having binary sequences $X$ and Y$ , respectively. Y$ is an edited version of , where the editing involves random deletions, insertions, and substitutions, possibly in bursts. The goal is for the node with Y$ to reconstruct X$ with minimal exchange of information over a noiseless link. The communication is measured in terms of both the total number of bits exchanged and the number of interactive rounds of communication. This paper focuses on the setting where the number of edits is , where $n$ is the length of $X$ . We first consider the case where the edits are a mixture of insertions and deletions (indels), and propose an interactive synchronization algorithm with near-optimal communication rate and average computational complexity of $O(n)$ arithmetic operations. The algorithm uses interaction to efficiently split the source sequence into substrings containing exactly one deletion or insertion. Each of these substrings is then synchronized using an optimal one-way algorithm based on the single-deletion correcting channel codes of Varshamov and Tenengolts. We then build on this synchronization algorithm in three different ways. First, it is modified to work with a single round of interaction. The reduction in the number of rounds comes at the expense of higher communication, which is quantified. Next, we present an extension to the practically important case where the insertions and deletions may occur in (potentially large) bursts. Finally, we show how to synchronize the sources to within a target Hamming distance. This feature can be used to differentiate between substitution and indel edits. In addition to theoretical performance bounds, we provide several validating simulation results for the proposed algorithms. [ABSTRACT FROM PUBLISHER]

In this paper, we study the queue-overflow probability of wireless scheduling algorithms. In wireless networks operated under queue-length-based scheduling algorithms, there often exists a tight coupling between the service-rate process, the system backlog process, the arrival process, and the stochastic process governing channel variations. Although one can use sample-path large-deviation techniques to form an estimate of the queue-overflow probability, the formulation leads to a difficult multidimensional calculus-of-variations problem. In this paper, we present a new technique to address this complexity issue. Using ideas from the Lyapunov function approach in control theory, this technique maps the complex multidimensional calculus-of-variations problem to a 1-D calculus-of-variations problem, and the latter is often much easier to solve. Further, under appropriate conditions, we show that when a scheduling algorithm minimizes the drift of a Lyapunov function at each point of every fluid sample path, the algorithm will be optimal in the sense that it maximizes the asymptotic decay rate of the probability that the Lyapunov function value exceeds a given threshold. We believe that these results can potentially be used to study the queue-overflow probability of a large class of wireless scheduling algorithms and to design new scheduling algorithms with optimal overflow probabilities. [ABSTRACT FROM AUTHOR]

This paper investigates basic trade-offs between energy and delay in wireless communication systems using finite blocklength theory. We first assume that data arrive in constant stream of bits, which are put into packets and transmitted over a communications link. Our results show that depending on exactly how energy is measured, in general energy depends on $\sqrt {d^{-1}}$ or $\sqrt {d^{-1}\log {d}}$ , where $d$ is the delay. This means that the energy decreases quite slowly with increasing delay. Furthermore, to approach the absolute minimum of −1.59 dB on energy, bandwidth has to increase very rapidly, much more than what is predicted by infinite blocklength theory. We then consider the scenario when data arrive stochastically in packets and can be queued. We devise a scheduling algorithm based on finite blocklength theory and develop bounds for the energy-delay performance. Our results again show that the energy decreases quite slowly with increasing delay. [ABSTRACT FROM AUTHOR]

This paper investigates joint power control and routing policies for general multihop wireless networks when all the transmitting nodes are subject to a long-term average power constraint. The main contribution of this paper is to propose online power and rate control algorithms and prove that these policies stabilize the entire queuing network whenever the packet arrival rates at each node are in the corresponding region of achievable rates. The online policies are time varying and based on the queue size at each node and the instantaneous channel conditions. The theoretical results are supported by simulations for the illustrative cases of both a multiple-access channel and a relay channel. [ABSTRACT FROM AUTHOR]

We consider a wireless device-to-device caching network where n nodes are placed on a regular grid of area A\left ({n}\right) . Each node caches L_{C}F$ (coded) bits from a library of size LF$ bits, where L$ is the number of files and F ). Moreover, we propose a cache-induced hierarchical cooperation scheme and associated cache content placement optimization algorithm to achieve the optimal per-node capacity scaling law. When the path loss exponent $\alpha <3$ , the optimal per-node capacity scaling law achieved by the cache-induced hierarchical cooperation can be significantly better than that achieved by the existing state-of-the-art schemes. To the best of our knowledge, this is the first work that completely characterizes the per-node capacity scaling law for wireless caching networks under the physical model and Zipf distribution with an arbitrary skewness parameter $\tau $ . While scaling law analysis yields clean results, it may not accurately reflect the throughput performance of a large network with a finite number of nodes. Therefore, we also analyze the throughput of the proposed cache-induced hierarchical cooperation for networks of practical size. The analysis and simulations verify that cache-induced hierarchical cooperation can also achieve a large throughput gain over the cache-assisted multihop scheme for networks of practical size. [ABSTRACT FROM PUBLISHER]

Cross-layer optimization is a key step in wireless network design that coordinates the resources allocated to different layers in order to achieve globally optimal network performance. Existing work on cross-layer optimization for wireless networks often adopts simplistic physical-layer models for wireless channels, such as treating interference as noise or interference avoidance. This crude modeling of physical layer often leads to inefficient utilization of resources. In this paper, we adopt a deterministic channel model proposed in refid="ref1"/, refid="ref2"/, a simple abstraction of the physical layer that effectively captures the effect of channel strength, broadcast and superposition in wireless channels. This model allows us to go beyond “treating interference as noise” and as a consequence are able to achieve higher throughput and utility. Within the network utility maximization (NUM) framework, we study the cross-layer optimization for wireless networks based on this deterministic channel model. First, we extend the well-studied conflict graph model to capture the flow interactions over the deterministic channels and characterize the feasible rate region. Then we study distributed algorithms for general wireless multi-hop networks with both link-centric formulation and node-centric formulation. The convergence of algorithms is proved by applying Lyapunov stability theorem and stochastic approximation method. Further, we show the convergence to the bounded neighborhood of optimal solutions with probability one under constant step sizes and constant update intervals. Our numerical evaluations validate the analytical results and show the advantage of deterministic channel model over simple physical layer models such as treating interference as noise. [ABSTRACT FROM AUTHOR]

A new algorithm of matrix spectral factorization is proposed which can be applied to compute an approximate spectral factor of any positive definite matrix function which satisfies the Paley-Wiener condition. ref refid="fnote1"/ id="fnote1" asterisk="no"paraThis paper includes the detailed proofs for an innovative method for matrix spectral factorization that can be used in numerous applications, including filtering, data compression, and wireless communications. A U.S. patent application has been submitted for this innovation through the Technology Commercialization Center, University of Maryland.para [ABSTRACT FROM AUTHOR]

This paper provides a solution to the question of how, when and where to perform inter-session network coding for a general network model both under wired and wireless conditions. In particular, an original queuing architecture and a dynamic routing-scheduling-coding strategy are introduced for serving multiple sessions when linear network coding is allowed across sessions. This policy provides a novel extension to the class of back-pressure policies by incorporating inter-session coding decisions via simple rules on the relevant queue-length levels. Despite the fact that the capacity region of inter-session coding is a challenging open problem, in this paper, we prove that our algorithm can support any set of rates in a nontrivial characterized region of achievable rates. In addition to its practical implications, this work also provides a theoretical framework in which the gains of inter-session network coding and pure routing can be compared. [ABSTRACT FROM AUTHOR]

The error performance of different types of receivers over an arbitrarily correlated Rician fading MIMO channel is assessed by evaluating the decision metric and the pairwise error probability. The differences are in the way channel state information at the receiver (CSIR) is recovered. We consider: i) a genie-aided receiver, based on the perfect knowledge of CSIR; ii) a mismatched receiver, based on the use of pilot-aided (imperfect) CSIR in the perfect-CSIR decision metric; iii) an optimum receiver, based on perfect channel distribution information at the receiver (CDIR), which performs jointly channel and data estimation. In this paper, the decision metric of the optimum receiver is derived, and an iterative algorithm is proposed to calculate it for sequential decoding schemes. The complexity of this iterative algorithm is analyzed and compare against the complexity of the mismatched receiver. Closed-form expressions are given for the pairwise error probabilities (PEPs) of the three receivers with arbitrarily correlated Rician fading. These expressions are further processed to obtain the asymptotic (in the SNR) PEPs, the diversity order, and the asymptotic power losses. Numerical results are presented to support the validity of this analysis and to assess the impact of power efficiency and CDIR estimation errors on the PEP versus the εb/N0 ratio. [ABSTRACT FROM AUTHOR]

This paper deals with beamforming in wireless relay networks with perfect channel information at the relays, receiver, and transmitter if there is a direct link between the transmitter and receiver. It is assumed that every node in the network has its own power constraint. A two-step amplify-and-forward protocol is used, in which the transmitter and relays not only use match filters to form a beam at the receiver but also adaptively adjust their transmit powers according to the channel strength information. For networks with no direct link, an algorithm is proposed to analytically find the exact solution with linear (in network size) complexity. It is shown that the transmitter should always use its maximal power while the optimal power of a relay can take any value between zero and its maxima. Also, this value depends on the quality of all other channels in addition to the relay's own. Despite this coupling fact, distributive strategies are proposed in which, with the aid of a low-rate receiver broadcast, a relay needs only its own channel information to implement the optimal power control. Then, beamforming in networks with a direct link is considered. When the direct link exists during the first step only, the optimal power control is the same as that of networks with no direct link. For networks with a direct link during the second step only and both steps, recursive numerical algorithms are proposed. Simulation shows that network beamforming achieves the maximal diversity order and outperforms other existing schemes. [ABSTRACT FROM AUTHOR]

This paper provides a theoretical framework for the analysis of interference-coupled multiuser systems. The fundamental behavior of such a system is modeled by interference functions, defined by axioms "nonnegativity, "scale-invariance," and "monotonicity." It is shown that every interference function has an interpretation as the optimum of a min-max problem, where the optimization is over a closed comprehensive positive coefficient set. This provides new insight into the structure of general interference functions and its elementary building blocks. Conversely, it is shown that every closed comprehensive positive set can be expressed as a level set of an interference function. This shows a close connection between the analysis of interference functions and multiuser performance regions, which are typically closed comprehensive. The generality of this framework allows for a wide range of potential applications. As an example, we analyze the problem of interference balancing. [ABSTRACT FROM AUTHOR]

Input queued (iQ) switches exploiting buffered cross- bars (CICQ switches) are widely considered very promising architectures that outperform IQ switches with bufferless switching fabrics both in terms of architectural scalability and performance. In- deed the problem of scheduling packets for transfer through the switching fabric is significantly simplified by the presence of internal buffers in the crossbar, which makes possible the adoption of efficient, simple and fully distributed scheduling algorithms. This paper studies the throughput performance of CICQ switches supporting multicast traffic, showing that, similarly to IQ architectures, also CICQ switches with arbitrarily large number of ports may suffer of significant throughput degradation under "pathological" multicast traffic patterns. Despite the asymptotic nature of these results, the authors believe that they can contribute to a deeper understanding of the behavior of CICQ architectures sup- porting multicast traffic. [ABSTRACT FROM AUTHOR]

This paper explores optimization of paging and registration policies in cellular networks. Motion is modeled as a discrete-time Markov process, and minimization of the discounted, infinite-horizon average cost is addressed. The structure of jointly optimal paging and registration policies is investigated through the use of dynamic programming for partially observed Markov processes. It is shown that there exist policies with a certain simple form that are jointly optimal. An iterative algorithm for policies with the simple form is proposed and investigated. The algorithm alternates between paging policy optimization, and registration policy optimization. It finds a pair of individually optimal policies. Majorization theory and Riesz's rearrangement inequality are used to show that jointly optimal paging and registration policies are given for symmetric or Gaussian random walk models by the nearest-location-first paging policy and distance threshold registration policies. [ABSTRACT FROM AUTHOR]

In this paper, we study the problem of joint permutor analysis and design for J-dimensional multiple turbo codes with J constituent encoders, J > 2. The concept of summary distance is extended to multiple permutors of size N and used as the design metric. Using the sphere-packing concept, we prove that the minimum length-2 summary distance (spread) Dmin, 2 is asymptoticly upper-bounded by O(NJ-1/Jr). We also show that the asymptotic minimum length-2L summary distance Dmin, 2L for the class of random permutors is lower-bounded by O (NJ-2/J-ϵ ), where ϵ > 0 can be arbitrarily small. Then, using the technique of expurgating "bad" symbols, we show that the spread of random permutors can achieve the optimum growth rate, i.e., O (NJ-1/J ), and that the asymptotic growth rate of Dmin, 2L can also be improved. The minimum length-2 and length-4 summary distances are studied for an important practical class of permutors-linear permutors. We prove that there exist J-dimensional multiple linear permutors with optimal spread Dmin, 2 = O(NJ-1/J ). Finally, we present several joint permutor construction algorithms applicable to multiple turbo codes of short and medium lengths. [ABSTRACT FROM AUTHOR]

Consider the following network communication setup, originating in a sensor networking application we refer to as the "sensor reachback" problem. We have a directed graph G = (V,E),where V = {v0v1…vn} and E ⊆ V × V. If (vi, vj) ∈ E, then node i can send messages to node j over a discrete memoryless channel (DMC) (χij, pij(y ∣ x), Yij), of capacity Cij. The channels are independent Each node vi gets to observe a source of information Ui(i = 0 … M), with joint distribution p( U0U1 … UM). Our goal is to solve an incast problem in G: nodes exchange messages with their neighbors, and after a finite number of communication rounds, one of the M + 1 nodes (v0 by convention) must have received enough information to reproduce the entire field of observations (U0U1 … UM), with arbitrarily small probability of error. In this paper, we prove that such perfect reconstruction is possible if and only if H(Us∣Usc) < Σ/i∈Sij∈Sc Cij for all S ⊆ {0 … M},S ≠ θ,0 ∈ Sc. Our main finding is that in this setup, a general source/channel separation theorem holds, and that Shannon information behaves as a classical network flow, identical in nature to the flow of water in pipes. At first glance, it might seem surprising that separation holds in a fairly general network situation like the one we study. A closer look, however, reveals that the reason for this is that our model allows only for independent point-to-point channels between pairs of nodes, and not multiple-access and/or broadcast channels, for which separation is well known not to hold. This "information as flow" view provides an algorithmic interpretation for our results, among which perhaps the most important one is the optimality of implementing codes using a layered protocol stack. [ABSTRACT FROM AUTHOR]

In an energy-efficient wireless communication ( system, transmit powers are minimized subject to predetermined signal-to-interference ratio (SIR) requirements. In this paper, a general framework for distributed stochastic power control (PC) algorithms is proposed, where the transmit powers are updated based on stochastic approximations. The proposed algorithms are distributed in the sense that no global information is needed in the power updates. Interference to each user is estimated locally via noisy observations. Two types of stochastic PC algorithms are studied: standard stochastic PC algorithms where the interference estimator is unbiased, and quasi-standard stochastic PC algorithms where the interference estimator is biased. The conditions under which the stochastic PC algorithms converge to the unique optimal solution are identified. Corresponding to two classes of iteration step-size sequences, two types of convergence, the probability one convergence and convergence in probability, are shown for both algorithms based on recent results in the stochastic approximation literature. Based on the theoretical results, some well-known stochastic PC algorithms, such as stochastic PC with matched filter receivers, and joint stochastic PC with blind minimum mean-squared error (MMSE) interference suppression, are revisited; several new stochastic PC algorithms, such as stochastic PC with minimum-power base-station assignment, and stochastic PC with limited diversity, are proposed. It is shown that these algorithms fall into either the standard or the quasi-standard stochastic PC framework. Simulation results are given to illustrate the performance of the proposed algorithms in practical systems. [ABSTRACT FROM AUTHOR]

In this paper, we establish the connection between the Orthogonal Optical Codes (OOC) and binary compressed sensing matrices. We also introduce deterministic bipolar m\times n RIP fulfilling \pm 1 matrices of order k such that m\leq \cal O\big (k (\log 2 n)^{{ \log 2 k}\over { \ln \log 2 k}}\big ). The columns of these matrices are binary BCH code vectors where the zeros are replaced by -1. Since the RIP is established by means of coherence, the simple greedy algorithms such as Matching Pursuit are able to recover the sparse solution from the noiseless samples. Due to the cyclic property of the BCH codes, we show that the FFT algorithm can be employed in the reconstruction methods to considerably reduce the computational complexity. In addition, we combine the binary and bipolar matrices to form ternary sensing matrices (\0,1,-1\ elements) that satisfy the RIP condition. [ABSTRACT FROM AUTHOR]

Existing works on distributed consensus explore linear iterations based on reversible Markov chains, which contribute to the slow convergence of the algorithms. It has been observed that by overcoming the diffusive behavior of reversible chains, certain nonreversible chains lifted from reversible ones mix substantially faster than the original chains. In this paper, the idea of Markov chain lifting is studied to accelerate the convergence of distributed consensus, and two general pseudoalgorithms are presented. These pseudoalgorithms are then instantiated through a class of location-aided distributed averaging (LADA) algorithms for wireless networks, where nodes' coarse location information is used to construct nonreversible chains that facilitate distributed computing and cooperative processing. Our first LADA algorithm is designed for grid networks; for a k\times k grid network, it achieves an \epsilon -averaging time of O(k\log (\epsilon ^-1)). Based on this algorithm, in a wireless network with transmission range r, an \epsilon -averaging time of O(r^-1\log (\epsilon ^-1)) can be attained through a centralized algorithm. Subsequently, a distributed LADA algorithm is presented, achieving the same scaling law in averaging time as the centralized scheme in wireless networks for all r satisfying the connectivity requirement; the constructed chain also attains the optimal scaling law in terms of an important mixing metric, the fill time, in its class. Finally, a cluster-based LADA algorithm is proposed, which, requiring no central coordination, provides the additional benefit of reduced message complexity compared with the distributed LADA algorithm. [ABSTRACT FROM PUBLISHER]

The nonlinear complexity of binary sequences and its connections with Lempel-Ziv complexity is studied in this paper. A new recursive algorithm is presented, which produces the minimal nonlinear feedback shift register of a given binary sequence. Moreover, it is shown that the eigenvalue profile of a sequence uniquely determines its nonlinear complexity profile, thus establishing a connection between Lempel-Ziv complexity and nonlinear complexity. Furthermore, a lower bound for the Lempel-Ziv compression ratio of a given sequence is proved that depends on its nonlinear complexity. [ABSTRACT FROM AUTHOR]

In multiple-input multiple-output (MIMO) systems, maximum-likelihood (ML) decoding is equivalent to finding the closest lattice point in an N-dimensional complex space. In general, this problem is known to be NP-hard. In this paper, a quasi-ML algorithm based on semi-definite programming (SDP) is proposed. We introduce several SDP relaxation models for MIMO systems, with increasing complexity. We use interior-point methods for solving the models and obtain a near-ML performance with polynomial computational complexity. Lattice basis reduction is applied to further reduce the computational complexity of solving these models. The proposed relaxation models are also used for soft output decoding in MIMO systems. [ABSTRACT FROM AUTHOR]

In this paper, we present a multidimensional trellis coded modulation scheme for a high rate 2 x 2 multiple-input multiple-output (MIMO) system over slow fading channels. Set partitioning of the Golden code is designed specifically to increase the minimum determinant. The branches of the outer trellis code are labeled with these partitions and Viterbi algorithm is applied for trellis decoding. In order to compute the branch metrics, a sphere decoder is used. The general framework for code design and optimization is given. Performance of the proposed scheme is evaluated by simulation and it is shown that it achieves significant performance gains over the uncoded Golden code. [ABSTRACT FROM AUTHOR]

Given an m × n array of k single random error correction (or erasure) codewords, each having length l such that mn = kl, we construct optimal interleaving schemes that provide the maximum burst error correction power such that an arbitrarily shaped error burst of size can be corrected for the largest possible value of t. We show that for all such m × n arrays, the maximum possible interleaving distance, or equivalently, the largest value oft such that an arbitrary error burst of size up tot can be corrected, is bounded by └√2k┘ if k ≤, ┌(min{m, n})²/2┐, and by min{m, n} + └(k - ┌(min{m, n})²/2┐)/min{m, n}┘ if k ≥ ┌(min{m, n} )²/2]. We generalize the cyclic shifting algorithm developed by the authors in a previous paper and construct, in several special cases, optimal interleaving arrays achieving these upper bounds. Additionally, for codewords of variable lengths, we solve a related array coloring problem for which the same upper bounds hold and can be achieved. [ABSTRACT FROM AUTHOR]

Suppose Alice and Bob try to transform an entangled state shared between them into another one by local operations and classical communications. Then in general a certain amount of entanglement contained in the initial state will decrease in the process of transformation. However, an interesting phenomenon called partial entanglement recovery shows that it is possible to recover some amount of entanglement by adding another entangled state and transforming the two entangled states collectively. In this paper, we are mainly concerned with the feasibility of partial entanglement recovery. The basic problem we address is whether a given state is useful in recovering entanglement lost in a specified transformation. In the case where the source and target states of the original transformation satisfy the strict majorization relation, a necessary and sufficient condition for partial entanglement recovery is obtained. For the general case we give two sufficient conditions. We also give an efficient algorithm for the feasibility of partial entanglement recovery in polynomial time. As applications, we establish some interesting connections between partial entanglement recovery and the generation of maximally entangled states, quantum catalysis, mutual catalysis, and multiple-copy entanglement transformation. [ABSTRACT FROM AUTHOR]

We develop a dynamic control strategy for minimizing energy expenditure in a time-varying wireless network with adaptive transmission rates. The algorithm operates without knowledge of traffic rates or channel statistics, and yields average power that is arbitrarily close to the minimum possible value achieved by an algorithm optimized with complete knowledge of future events. Proximity to this optimal solution is shown to be inversely proportional to network delay. We then present a similar algorithm that solves the related problem of maximizing network throughput subject to peak and average power constraints. The techniques used in this paper are novel and establish a foundation for stochastic network optimization. [ABSTRACT FROM AUTHOR]

In this paper, we consider packet scheduling for the downlink in a wireless network, where each packet's service preferences are captured by a utility function that depends on the total delay incurred. The goal is to schedule packet transmissions maximize the total utility. In this setting, we examine a simple gradient-based scheduling algorithm called the U̇R-rule, which is a type of generalized cμ-rule (Gcμ) that takes into account both a user's channel condition and derived utility when making scheduling decisions. We study the performance of this scheduling rule for a draining problem, where there is a given set of initial packets and no further arrivals. We formulate a ‘large system’ fluid model for this draining problem where the number of packets becomes large while the packet-size decreases to zero, and give a complete characterization of the behavior of the UR scheduling rule in this limiting regime. Comparison with simulation results show that the fluid limit accurately predicts the corresponding behavior of finite systems of interest. We then give an optimal control formulation for finding the optimal scheduling policy for the fluid draining model Using Pontryagin's minimum principle, we show that, when the user rates are chosen from a TDM-type of capacity region, the UR rule is in fact optimal in many cases. Sufficient conditions for optimality are also given. Finally, we consider a general capacity region and show that the UR rule is optimal only in special cases. [ABSTRACT FROM AUTHOR]

The paper develops a systematic framework for designing a stochastic location detection system with associated performance guarantees using a wireless sensor network. To detect the location of a mobile sensor, the system relies on RF-characteristics of the signal transmitted by the mobile sensor, as it is received by stationary sensors (clusterheads). Location detection is posed as a hypothesis testing problem over a discretized space. Large deviations results enable the characterization of the probability of error leading to a placement problem that maximizes an information-theoretic distance (Chernoff distance) among all pairs of probability distributions of observations conditional on the sensor locations. The placement problem is shown to be NP-hard and is formulated as a linear integer programming problem; yet, large instances can be solved efficiently by leveraging special-purpose algorithms from the theory of discrete facility location. The resultant optimal placement is shown to provide asymptotic guarantees on the probability of error in location detection under quite general conditions by minimizing an upper bound of the error-exponent. Numerical results show that the proposed framework is computationally feasible and the resultant clusterhead placement performs near-optimal even with a small number of observation samples in a simulation environment. [ABSTRACT FROM AUTHOR]

In this paper, we propose a new design criterion and a new class of unitary signal constellations for differential space-time modulation for multiple-antenna systems over Rayleigh flat-fading channels with unknown fading coefficients. Extensive simulations show that the new codes have significantly better performance than existing codes. We have compared the performance of our codes with differential detection schemes using orthogonal design, Cayley differential codes, fixed-point-free group codes, and product of groups and for the same bit-error rate, our codes allow smaller signal-to-noise ratio (SNR) by as much as 10 dB. The design of the new codes is accomplished in a systematic way through the optimization of a performance index that closely describes the bit-error rate as a function of the SNR The new performance index is computationally simple and we have derived analytical expressions for its gradient with respect to constellation parameters. Decoding of the proposed constellations is reduced to a set of one-dimensional closest point problems that we solve using parallel sphere decoder algorithms. This decoding strategy can also improve efficiency of existing codes. [ABSTRACT FROM AUTHOR]

We study the problem of private key generation in a cooperative pairwise independent network (PIN), with $M+2$ terminals (Alice, Bob, and $M$ relays), $M\geq 2$ . In the PIN, the correlated source observed by every pair of terminals is independent of the sources observed by any other pairs of terminals. Moreover, all terminals can communicate with each other over a public channel, which is also observed by Eve, noiselessly. The objective is to generate a private key between Alice and Bob with the help of the $M$ relays; such a private key needs to be protected not only from Eve but also from all relays. A single-letter expression for the private key capacity of this PIN model is obtained, where the achievability part is established by proposing a random binning (RB)-based key generation algorithm, and the converse part is established by deriving upper bounds of $M$ enhanced source models. Next, we consider a cooperative wireless network and use the estimates of fading channels to generate private keys. It has been shown that the proposed RB key generation algorithm can achieve a multiplexing gain of $M-1$ , which is an improvement compared with the existing XOR algorithm, whose achievable multiplexing gain is $\lfloor M /2\rfloor $ . [ABSTRACT FROM PUBLISHER]

Recent results establish the optimality of interference alignment to approach the Shannon capacity of interference networks at high SNR. However, the extent to which interference can be aligned over a finite number of signalling dimensions remains unknown. Another important concern for interference alignment schemes is the requirement of global channel knowledge. In this work, we provide examples of iterative algorithms that utilize the reciprocity of wireless networks to achieve interference alignment with only local channel knowledge at each node. These algorithms also provide numerical insights into the feasibility of interference alignment that are not yet available in theory. [ABSTRACT FROM AUTHOR]

A general wireless networking problem is formulated whereby end-to-end user rates, routes, link capacities, transmit-power, frequency, and power resources are jointly optimized across fading states. Even though the resultant optimization problem is generally nonconvex, it is proved that the gap with its Lagrange dual problem is zero, so long as the underlying fading distribution function is continuous. The major implication is that separating the design of wireless networks in layers and per-fading state subproblems can be optimal. Subgradient descent algorithms are further developed to effect an optimal separation in layers and layer interfaces. [ABSTRACT FROM AUTHOR]

We study the use of low-density generator matrix (LDGM) codes for lossy compression of the Bernoulli symmetric source. First, we establish rigorous upper bounds on the average distortion achieved by check-regular ensemble of LDGM codes under optimal minimum distance source encoding. These bounds establish that the average distortion using such bounded degree families rapidly approaches the Shannon limit as the degrees are increased. Second, we propose a family of message-passing algorithms, ranging from the standard belief propagation algorithm at one extreme to a variant of survey propagation algorithm at the other. When combined with a decimation subroutine and applied to LDGM codes with suitably irregular degree distributions, we show that such a message-passing/decimation algorithm yields distortion very close to the Shannon rate-distortion bound for the binary symmetric source. [ABSTRACT FROM AUTHOR]

An interference alignment (IA) scheme is presented that allows multiple opportunistic transmitters (secondary users) to use the same frequency band of a pre-existing primary link without generating any interference. The primary and secondary transmit-receive pairs are equipped with multiple antennas. Under power constraints on the primary transmitter, the rate of the primary user is maximized by water-filling on the singular values of its channel matrix leaving some eigen modes unused, and hence, the secondary users can align their transmitted signals to produce a number of interference-free dimensions at each secondary receiver without causing any interference to the primary user. An outer bound is developed on the degrees of freedom (DoF) of the secondary users. In the case of a symmetric secondary network with time-varying channel coefficients having M antennas at each node and operating in the presence of a primary link with d_0 active eigen modes, a precoding scheme is presented for the secondary transmitters that can asymptotically achieve the available (M-d_0)^+/2 DoF per secondary user. An iterative algorithm is also presented that utilizes channel reciprocity to achieve the proposed cognitive IA scheme. For a cognitive 3-user secondary network with constant channel coefficients, a novel closed-form solution is derived for the precoding matrices of the secondary users. [ABSTRACT FROM PUBLISHER]

We formally define the gradual removal problem in wireless networks, where the smallest number of users should be removed due to infeasibility of the target-SIR requirements for all users, and present a distributed power-control algorithm with temporary removal and feasibility check (DFC) to address it. The basic idea is that any transmitting user whose required transmit power for reaching its target-SIR exceeds its maximum power is temporarily removed, but resumes its transmission if its required transmit power goes below a given threshold obtained in a distributed manner. This enables users to check the feasibility of system in a distributed manner. The existence of at least one fixed-point in DFC is guaranteed, and at each equilibrium, all transmitting users reach their target-SIRs consuming the minimum aggregate transmit power. Furthermore, in contrast to the existing algorithms, no user is unnecessarily removed by DFC, i.e., DFC is Pareto and energy-efficient. We also show that when target-SIRs are the same for all users, DFC minimizes the outage probability. Simulation results confirm our analytical developments and show that DFC significantly outperforms the existing schemes in addressing the gradual removal problem in terms of convergence, outage probability, and power consumption. [ABSTRACT FROM AUTHOR]

We consider a wireless communication system formed by a single cell with one base station and K user terminals. User channels are characterized by frequency-selective fading due to small-scale effects, modeled as a set of M parallel block-fading channels, and a frequency-flat distance-dependent path loss. We compare delay-limited systems with variable-rate systems under fairness constraints, in terms of the achieved system spectral efficiency C (bills/Hz) versus Eb/N0. The considered delay-limited systems impose "hard-fairness": every user transmits at its desired rate on all blocks, independently of its fading conditions. The variable-rate system imposes "proportional fairness" via the popular Proportional Fair Scheduling (PFS) algorithm, currently implemented in 3G wireless for data (delay-tolerant) applications. We find simple iterative resource allocation algorithms that converge to the optimal delay-limited throughput for orthogonal (frequency-division multiple access (FDMA)/time-division multiple access (TDMA)) and optimal (superposition/interference cancellation) signaling. In the limit of large K and finite Al we find closed-form expressions for C as a function of Eb/N0. We show that in this limit, the optimal allocation policy consists of letting each user transmit on its best subchannel only. Also, we find a simple closed-form expression for the throughput of PFS in a cellular environment, that holds for any K and M. Finally, we obtain closed-form expressions for C versus Eb/N0 in the low and high spectral efficiency regimes. The conclusions of our analysis in terms of system design guidelines are as follows: a) if hard fairness is a requirement, orthogonal access incurs a large throughput penalty with respect to the optimal (superposition coding) strategy, especially in the regime of high spectral efficiency; b) for high spectral efficiency, PFS does not provide any significant gain and may even perform worse than the optimal delay-limited system, despite the fact that the imposed fairness constraint is laxer; c) for low to moderate spectral efficiency, the stricter hard-fariness constraint incurs in a large throughput penalty with respect to PFS. [ABSTRACT FROM AUTHOR]

Multiple-input multiple-output (MIMO) flat-fading channels with channel state information available at the receiver and channel state distribution available at the transmitter are considered. The ergodic capacity-achieving covariance matrix (ECACM) under an average input power constraint is shown to be not unique in general, and three sufficient conditions for the uniqueness are derived. Then, the structure of ECACM is characterized for certain classes of MIMO channels including the following classes of MIMO channels: 1) right-permutationally invariant channels including independent and identically distributed (i.i.d.) channels; 2) right-symmetrically distributed channels; and 3) right-permutationally invariant and right-symmetrically distributed channels. Finally, part of the single-user results are extended to the multiple-access channel. [ABSTRACT FROM AUTHOR]

We consider the problem of establishing minimum-cost multicast connections over coded packet networks, i.e., packet networks where the contents of outgoing packets are arbitrary, causal functions of the contents of received packets. We consider both wireline and wireless packet networks as well as both static multicast (where membership of the multicast group remains constant for the duration of the connection) and dynamic multicast (where membership of the multicast group changes in time, with nodes joining and leaving the group). For static multicast, we reduce the problem to a polynomial-time solvable optimization problem, and we present decentralized algorithms for solving it. These algorithms, when coupled with existing decentralized schemes for constructing network codes, yield a fully decentralized approach for achieving minimum-cost multicast. By contrast, establishing minimum-cost static multicast connections over routed packet networks is a very difficult problem even using centralized computation, except in the special cases of unicast and broadcast connections. For dynamic multicast, we reduce the problem to a dynamic programming problem and apply the theory of dynamic programming to suggest how it may be solved. [ABSTRACT FROM AUTHOR]

A description of optimal sequences for direct-spread code-division multiple access (S-CDMA) is a byproduct of recent characterization of the sum capacity. This correspondence restates the sequence design problem as an inverse singular value problem and shows that the problem can be solved with finite-step algorithms from matrix theory. It proposes a new one-sided algorithm that is numerically stable and faster than previous methods. [ABSTRACT FROM AUTHOR]

Fully diverse constellations, i.e., sets of unitary matrices whose pairwise differences are nosingular, are useful in multiple-antenna communications, especially in multiple-antenna differential modulation, since they have good pairwise error properties. Recently, group theoretic ideas, especially fixed-point-free (fpf) groups, have been used to design fully diverse constellations of unitary matrices. Here we construct four-transmit-antenna constellations appropriate for differential modulation based on the symplectic group Sp(2). They can be regarded as extensions of Alamouti's celebrated two-transmit-antenna orthogonal design which can be constructed from the group Sp(1). We further show that the structure of Sp(2) codes lends itself to efficient maximum-likelihood (ML) decoding via the sphere decoding algorithm. Finally, the performance of Sp(2) codes is compared with that of other existing codes including Almouti's orthogonal design, a 4 × 4 complex orthogonal design, Cayley differential unitary space-time codes and group-based codes. [ABSTRACT FROM AUTHOR]

Develops adaptive algorithms for multichannel blind identification with statistic and deterministic models. Application of the algorithm to wireless communications; Convergence properties of the algorithms; Demonstration of the algorithm's performance using simulation examples.