Search

We consider medium access control (MAC) in multihop sensor networks, where only partial information about the shared medium is available to the transmitter. We model our setting as a queuing problem in which the service rate of a queue is a function of a partially observed Markov chain representing the available bandwidth, and in which the arrivals are controlled based on the partial observations so as to keep the system in a desirable mildly unstable regime. The optimal controller for this problem satisfies a separation property: we first compute a probability measure on the state space of the chain, namely the information state, then use this measure as the new state on which the control decisions are based. We give a formal description of the system considered and of its dynamics, we formalize and solve an optimal control problem, and we show numerical simulations to illustrate with concrete examples properties of the optimal control law. We show how the ergodic behavior of our queuing model is characterized by an invariant measure over all possible information states, and we construct that measure. Our results can be specifically applied for designing efficient and stable algorithms for medium access control in multiple-accessed systems, in particular for sensor networks.

In this paper, we focus on the general relay channel. We investigate the application of the estimate-and-forward (EAF) relaying scheme to different scenarios. Specifically, we study assignments of the auxiliary random variable that always satisfy the feasibility constraints. We then consider the Gaussian relay channel with coded modulation, where we show that a three-level quantization outperforms the Gaussian quantization commonly used to evaluate the achievable EAF rates in this scenario. Last, we consider the cooperative general broadcast scenario with a multistep conference between the receivers. We first apply EAF to obtain a general achievable rate region with a multistep conference. We then use an explicit assignment for the auxiliary random variables to obtain an explicit rate expression for the single common message case with a two-step conference. Index Terms--Channel capacity, cooperative broadcast, estimate-and-forward (EAF), network information theory, relay channels.

In this paper, we consider the problem of rate/distortion with side information available only at the decoder. For the case of jointly Gaussian source X and side information Y, and mean-squared error distortion, Wyner proved in 1976 that the rate/distortion function for this problem is identical to the conditional rate/distortion function [R.sub.X/Y], assuming the side information Y is available at the encoder. In this paper we construct a structured class of asymptotically optimal quantizers for this problem: under the assumption of high correlation between source X and side information Y, we show there exist quantizers within our class whose performance comes arbitrarily close to Wyner's bound. As an application illustrating the relevance of the high-correlation asymptotics, we also explore the use of these quantizers in the context of a problem of data compression for sensor networks, in a setup involving a large number of devices collecting highly correlated measurements within a confined area. An important feature of our formulation is that, although the per-node throughput of the network tends to zero as network size increases, so does the amount of information generated by each transmitter. This is a situation likely to be encountered often in practice, which allows us to cast under new--and more "optimistic"--light some negative results on the transport capacity of large-scale wireless networks. Index Terms--Ad hoc networks, capacity, hexagonal lattice, lattice codes, lattice quantization, multihop radio networks, network information theory, quantization, rate/distortion, rate/distortion with side information, sensor networks, source coding, throughput, vector quantization, wireless networks.

We consider the problem of communicating over the general discrete memoryless broadcast channel (DMBC) with partially cooperating receivers. In our setup, receivers are able to exchange messages over noiseless conference links of finite capacities, prior to decoding the messages sent from the transmitter. In this paper, we formulate the general problem of broadcast with cooperation. We first find the capacity region for the case where the BC is physically degraded. Then, we give achievability results for the general broadcast channel, for both the two independent messages case and the single common message case. Index Terms--Broadcast channels, channel capacity, cooperative broadcast, network information theory, relay channels.

The problem of time synchronization in dense wireless networks is considered. Well-established synchronization techniques suffer from an inherent scalability problem in that synchronization errors grow with an increasing number of hops across the network. In this work, a model for communication in wireless networks is first developed, and then the model is used to define a new time synchronization mechanism. A salient feature of the proposed method is that, in the regime of asymptotically dense networks, it can average out all random errors and maintain global synchronization in the sense that all nodes in the multihop network can see identical timing signals. This is irrespective of the distance separating any two nodes. Index Terms--Cooperation in networks, large network asymptotics, relay networks, scalability, sensor networks, time synchronization, wireless communications.

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 = {[v.sub.0][v.sub.1] ... [v.sub.n]} and E [subset or equal to] V x V. If ([v.sub.i], [v.sub.j]) [member of] E, then node i can send messages to node j over a discrete memoryless channel (DMC) ([X.sub.ij], [p.sub.ij](y|[??]), [Y.sub.ij]), of capacity [C.sub.ij]. The channels are independent. Each node [v.sub.i] gets to observe a source of information [U.sub.i](i = 0 ... M), with joint distribution p([U.sub.0][U.sub.1] ... [U.sub.M]). 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 ([v.sub.0] by convention) must have received enough information to reproduce the entire field of observations ([U.sub.0] [U.sub.1] ... [U.sub.M]), with arbitrarily small probability of error. In this paper, we prove that such perfect reconstruction is possible if and only if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] for all S [subset or equal to] {0 ... M}, S [not equal to] [empty set], 0 [member of] [S.sup.c]. 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. Index Terms--Communication networks, correlated sources, directed graphs, multiterminal source coding, network algorithhms, network analysis, network architecture, network capacity, network coding, network design, network flow, network protocols, networks, routing, sensor networks.

Multiple description (MD) coding is a source coding technique for information transmission over unreliable networks. In MD coding, the coder generates several different descriptions of the same signal and the decoder can produce a useful reconstruction of the source with any received subset of these descriptions. In this paper, we study the problem of MD coding of stationary Gaussian sources with memory. First, we compute an approximate MD rate distortion region for these sources, which we prove to be asymptotically tight at high rates. This region generalizes the MD rate distortion region of El Gamal, Cover, and Ozarow for memoryless Gaussian sources. Then, we develop an algorithm for the design of optimal two-channel biorthogonal filter banks for MD coding of Gaussian sources. We show that optimal filters are obtained by allocating the redundancy over frequency with a reverse "water-filling" strategy. Finally, we present experimental results which show the effectiveness of our filter banks in the low complexity, low rate regime. Index Terms--Filter bank design, integer-to-integer transforms, multiple description (MD) coding, rate distortion functions, robust source coding.

We consider medium access control (MAC) in multihop sensor networks, where only partial information about the shared medium is available to the transmitter. We model our setting as a queuing problem in which the service rate of a queue is a function of a partially observed Markov chain representing the available bandwidth, and in which the arrivals are controlled based on the partial observations so as to keep the system in a desirable mildly unstable regime. The optimal controller for this problem satisfies a separation property: we first compute a probability measure on the state space of the chain, namely the information state, then use this measure as the new state on which the control decisions are based. We give a formal description of the system considered and of its dynamics, we formalize and solve an optimal control problem, and we show numerical simulations to illustrate with concrete examples properties of the optimal control law. We show how the ergodic behavior of our queuing model is characterized by an invariant measure over all possible information states, and we construct that measure. Our results can be specifically applied for designing efficient and stable algorithms for medium access control in multiple-accessed systems, in particular for sensor networks.

The problem of designing a multiple-description vector quantizer with lattice codebook [Lambda] is considered. A general solution is given to a labeling problem which plays a crucial role in the design of such quantizers. Numerical performance results are obtained for quantizers based on the lattices [A.sub.2] and [Z.sup.i], i = 1, 2, 4, 8, that make use of this labeling algorithm. The high-rate squared-error distortions for this family of L-dimensional vector quantizers are then analyzed for a memoryless source with probability density function (pdf) p and differential entropy h(p) [is less than] [infinity]. For any a [element of] (0, 1) and rate pair (R, R), it is shown that the two-channel distortion [[bar]d.sub.0] and the channel 1 (or channel 2) distortion [[bar]d.sub.s] satisfy [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] where G([Lambda]) is the normalized second moment of a Voronoi cell of the lattice [Lambda] and G ([S.sub.L]) is the normalized second moment of a sphere in L dimensions. Index Terms--Cubic lattice, hexagonal lattice, lattice quantization, multiple descriptions, quantization, source coding, vector quantization.

A statistical model for understanding the excellent performance achieved by several image coding algorithms was developed to construct two novel coding algorithms. The proposed coding algorithms exhibit rate/distortion performance competitive with that of the best methods. It was also found that the algorithms have fairly low complexity because of their ability to avoid difficult quantizer optimizations and have enhanced perceptual quality.

The problem of time synchronization in dense wireless networks is considered. Well-established synchronization techniques suffer from an inherent scalability problem in that synchronization errors grow with an increasing number of hops across the network. In this work, a model for communication in wireless networks is first developed, and then the model is used to define a new time synchronization mechanism. A salient feature of the proposed method is that, in the regime of asymptotically dense networks, it can average out all random errors and maintain global synchronization in the sense that all nodes in the multihop network can see identical timing signals. This is irrespective of the distance separating any two nodes. [ABSTRACT FROM AUTHOR]

Presents an overview of articles related to communications and signal processing communities in wireless sensor networks.

Presents information on a study which considered the problem of coding images for transmission over error-prone channels. Need for error resilient data compression algorithms; Design of a multiple description image coder; Image coding into any number of mutually refinable packets; Conclusions.