Power-Efficient Sensor Placement and Transmission Structure for Data Gathering under Distortion Constraints

We consider the joint optimization of sensor placement and transmission structure for data gathering, where a given number of nodes need to be placed in a field such that the sensed data can be reconstructed at a sink within specified distortion bounds while minimizing the energy consumed for communication. We assume that the nodes use either joint entropy coding based on explicit communication between sensor nodes, where coding is done when side information is available, or Slepian-Wolf coding where nodes have knowledge of network correlation statistics. We consider both maximum and average distortion bounds. We prove that this optimization is NP-complete since it involves an interplay between the spaces of possible transmission structures given radio reachability limitations, and feasible placements satisfying distortion bounds.We address this problem by first looking at the simplified problem of optimal placement in the one-dimensional case. An analytical solution is derived for the case when there is a simple aggregation scheme, and numerical results are provided for the cases when joint entropy encoding is used. We use the insight from our 1-D analysis to extend our results to the 2-D case and compare it to typical uniform random placement and shortest-path tree. Our algorithm for two-dimensional placement and transmission structure provides two to three fold reduction in total power consumption and between one to two orders of magnitude reduction in bottleneck power consumption. We perform an exhaustive performance analysis of our scheme under varying correlation models and model parameters and demonstrate that the performance improvement is typical over a range of data correlation models and parameters. We also study the impact of performing computationally-efficient data conditioning over a local scope rather than the entire network. Finally, we extend our explicit placement results to a randomized placement scheme and show that such a scheme can be effective when deployment does not permit exact node placement.

Razvan Cristescu

2004

Efficient decentralized communications in sensor networks

Razvan Cristescu

This thesis is concerned with problems in decentralized communication in large networks. Namely, we address the problems of joint rate allocation and transmission of data sources measured at nodes, and of controlling the multiple access of sources to a shared medium. In our study, we consider in particular the important case of a sensor network measuring correlated data. In the first part of this thesis, we consider the problem of correlated data gathering by a network with a sink node and a tree communication structure, where the goal is to minimize the total transmission cost of transporting the information collected by the nodes, to the sink node. Two coding strategies are analyzed: a Slepian-Wolf model where optimal coding is complex and transmission optimization is simple, and a joint entropy coding model with explicit communication where coding is simple and transmission optimization is difficult. This problem requires a joint optimization of the rate allocation at the nodes and of the transmission structure. For the Slepian-Wolf setting, we derive a closed form solution and an efficient distributed approximation algorithm with a good performance. We generalize our results to the case of multiple sinks. For the explicit communication case, we prove that building an optimal data gathering tree is NP-complete and we propose various distributed approximation algorithms. We compare asymptotically, for dense networks, the total costs associated with Slepian-Wolf coding and explicit communication, by finding their corresponding scaling laws and analyzing the ratio of their respective costs. We argue that, for large networks and under certain conditions on the correlation structure, "intelligent", but more complex Slepian-Wolf coding provides unbounded gains over the widely used straightforward approach of opportunistic aggregation and compression by explicit communication. In the second part of this thesis, we consider a queuing problem in which the service rate of a queue is a function of a partially observed Markov chain, and in which the arrivals are controlled based on those 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 based on which to make control decisions. 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 may be applied for designing efficient and stable algorithms for medium access control in multiple accessed systems, in particular for sensor networks.

EPFL2004

Razvan Cristescu, Martin Vetterli

We consider the problem of correlated data gathering by a network with a sink node and a tree based communication structure, where the goal is to minimize the total trans- mission cost of transporting the information collected by the nodes, to the sink node. For source coding of correlated data, we consider a joint entropy based coding model with explicit communication where coding is simple and the transmission structure optimiza- tion is difficult. We first formulate the optimization problem definition in the general case and then we study further a network setting where the entropy conditioning at nodes does not depend on the amount of side information, but only on its availability. We prove that even in this simple case, the optimization problem is NP-hard. We propose some efficient, scalable, and distributed heuristic approximation algorithms for solving this problem and show by numerical simulations that the total transmission cost can be significantly improved over direct transmission or the shortest path tree. We also present an approximation algorithm that provides a tree transmission structure with total cost within a constant factor from the optimal.

2006

Efficient decentralized communications in sensor networks

Razvan Cristescu

EPFL2004

Power-Efficient Sensor Placement and Transmission Structure for Data Gathering under Distortion Constraints