Adaptive Distributed Algorithms for Power-Efficient Data Gathering in Sensor Networks

Jugoslava Acimovic, Razvan Cristescu
2005
Conference paper

Abstract

In this work, we consider the problem of designing adaptive distributed processing algorithms in large sensor networks that are efficient in terms of minimizing the total power spent for gathering the spatially correlated data from the sensor nodes to a sink node. We take into account both the power spent for purposes of communication as well as the power spent for local computation. Our distributed algorithms are also matched to the nature of the correlated field, namely, for piecewise smooth signals, we provide two distributed multiresolution wavelet-based algorithms, while for correlated Gaussian fields, we use distributed prediction based processing. In both cases, we provide distributed algorithms that perform network division into groups of different sizes. The distribution of the group sizes within the network is the result of an optimal trade-off between the local communication inside each group needed to perform decorrelation, the communication needed to bring the processed data (coefficients) to the sink and the local computation cost, which grows as the network becomes larger. Our experimental results show clearly that important gains in power consumption can be obtained with respect to the case of not performing any distributed decorrelating processing.

Official source

https://infoscience.epfl.ch/record/112309?ln=en

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts

Related publications

Related publications (102)

Low Complexity Scheduling and Coding for Wireless Networks

Siddhartha Brahma

The advent of wireless communication technologies has created a paradigm shift in the accessibility of communication. With it has come an increased demand for throughput, a trend that is likely to increase further in the future. A key aspect of these challenges is to develop low complexity algorithms and architectures that can take advantage of the nature of the wireless medium like broadcasting and physical layer cooperation. In this thesis, we consider several problems in the domain of low complexity coding, relaying and scheduling for wireless networks. We formulate the Pliable Index Coding problem that models a server trying to send one or more new messages over a noiseless broadcast channel to a set of clients that already have a subset of messages as side information. We show through theoretical bounds and algorithms, that it is possible to design short length codes, poly-logarithmic in the number of clients, to solve this problem. The length of the codes are exponentially better than those possible in a traditional index coding setup. Next, we consider several aspects of low complexity relaying in half-duplex diamond networks. In such networks, the source transmits information to the destination through

n

half-duplex intermediate relays arranged in a single layer. The half-duplex nature of the relays implies that they can either be in a listening or transmitting state at any point of time. To achieve high rates, there is an additional complexity of optimizing the schedule (i.e. the relative time fractions) of the relaying states, which can be

2^n

in number. Using approximate capacity expressions derived from the quantize-map-forward scheme for physical layer cooperation, we show that for networks with

n\leq 6

relays, the optimal schedule has atmost

n+1

active states. This is an exponential improvement over the possible

2^n

active states in a schedule. We also show that it is possible to achieve at least half the capacity of such networks (approximately) by employing simple routing strategies that use only two relays and two scheduling states. These results imply that the complexity of relaying in half-duplex diamond networks can be significantly reduced by using fewer scheduling states or fewer relays without adversely affecting throughput. Both these results assume centralized processing of the channel state information of all the relays. We take the first steps in analyzing the performance of relaying schemes where each relay switches between listening and transmitting states randomly and optimizes their relative fractions using only local channel state information. We show that even with such simple scheduling, we can achieve a significant fraction of the capacity of the network. Next, we look at the dual problem of selecting the subset of relays of a given size that has the highest capacity for a general layered full-duplex relay network. We formulate this as an optimization problem and derive efficient approximation algorithms to solve them. We end the thesis with the design and implementation of a practical relaying scheme called QUILT. In it the relay opportunistically decodes or quantizes its received signal and transmits the resulting sequence in cooperation with the source. To keep the complexity of the system low, we use LDPC codes at the source, interleaving at the relays and belief propagation decoding at the destination. We evaluate our system through testbed experiments over WiFi.

EPFL2015

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

Efficient Distributed Multiresolution Processing for Data Gathering in Sensor Networks

Jugoslava Acimovic, Razvan Cristescu

We consider large sensor networks where the cost of collecting data from the network nodes to the data gathering sink is critical.~We propose several algorithms that use limited local communication and distributed signal processing to make communication more efficient in terms of transmission cost.~We consider a model that uses distributed wavelets-based signal processing.~We first propose an algorithm that performs processing at nodes as data is forwarded to the sink.~Then, we analyze algorithms that perform network division into groups of adaptive size and for which signal processing is applied separately to each group.~We show by numerical simulations that such multiresolution approaches result in significant improvements for data gathering in terms of total communication costs.

2005