Distributed routing algorithms for sensor networks

Recent advances in wireless communications and computing technology are enabling the emergence of low-cost devices that incorporate sensing, processing, and communication functionalities. A large number of these devices are deployed in the field to create a sensor network for both monitoring and control purposes. Sensor networks are currently an active research area mainly due to the potential of their applications. However, the deployment of a working large scale sensor network still requires solutions to a number of technical challenges that stem primarily from the constraints imposed by simple sensor devices: limited power, limited communication bandwidth, and small storage capacity. In view of all these particular constraints, we require a new paradigm for communication, which consists of new algorithms specifically conceived for sensor networks. This thesis concentrates on the routing problem, that is, moving data among different network locations, and on the interactions between routing and coding, that is, how sensors code the observations. We start by designing efficient and computationally simple decentralized algorithms to transmit data from one single source to one single destination. We formalize the corresponding routing problem as a problem of constructing suitably constrained random walks on random graphs and derive distributed algorithms to compute the local parameters of the random walk that induces a uniform load distribution in the network. The main feature of this routing formulation is that it is possible to route messages along all possible routes between the source and the destination node, without performing explicit route discovery/repair computations and without maintaining explicit state information about available routes at the nodes. A natural extension to the single-source/single-destination scenario is to consider multiple sources and/or multiple destinations. Depending on the structure and goal of the network, nodes exhibit different communication patterns. We analyze the problem of routing under three different communication models, namely uniform communication, central data gathering, and border data gathering. For each of these models, we derive capacity limits and propose constructive routing strategies that achieve this capacity. An important constraint of sensor networks is the limited storage capacity available at the nodes. We analyze the problem of routing in networks with small buffers. We develop new approximation models to compute the distribution on the queue size at the nodes which provide a more accurate distribution than the usual Jackson's Theorem. Using these models, we design routing algorithms that minimize buffer overflow losses. Routing in large and unreliable networks, such as sensor networks, becomes prohibitively complex in terms of both computation and communication: due to temporary node failures, the set of available routes between any two nodes changes randomly. We demonstrate that achieving robust communications and maximizing the achievable rate per node are incompatible goals: while robust communications require the use of as many paths as possible between the source and the destination, maximizing the rate per node requires using only a few of the available paths. We propose a family of routing algorithms that explores this trade-off, depending on the degree of reliability of the network. The performance of routing algorithms in sensor networks can be significantly improved by considering the interaction of the source coding mechanism with the transport mechanism. We jointly optimize both the source coding and the routing algorithm in a common scenario encountered in sensor network, namely, real-time data transmission. We demonstrate that the combination of specially designed coding techniques, such as multiple description coding, and multipath routing algorithms, performs significantly better that the usual routing and coding schemes. In summary, this thesis revisits the classic routing problem in the light of distributed schemes for networks with resource-limited nodes.

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

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

Function Computation over Networks

Chien-Yi Wang

This thesis looks at efficient information processing for two network applications: content delivery with caching and collecting summary statistics in wireless sensor networks. Both applications are studied under the same paradigm: function computation over networks, where distributed source nodes cooperatively communicate some functions of individual observations to one or multiple destinations. One approach that always works is to convey all observations and then let the destinations compute the desired functions by themselves. However, if the available communication resources are limited, then revealing less unwanted information becomes critical. Centered on this goal, this thesis develops new coding schemes using information-theoretic tools. The first part of this thesis focuses on content delivery with caching. Caching is a technique that facilitates reallocation of communication resources in order to avoid network congestion during peak-traffic times. An information-theoretic model, termed sequential coding for computing, is proposed to analyze the potential gains offered by the caching technique. For the single-user case, the proposed framework succeeds in verifying the optimality of some simple caching strategies and in providing guidance towards optimal caching strategies. For the two-user case, five representative subproblems are considered, which draw connections with classic source coding problems including the Gray-Wyner system, successive refinement, and the Kaspi/Heegard-Berger problem. Afterwards, the problem of distributed computing with successive refinement is considered. It is shown that if full data recovery is required in the second stage of successive refinement, then any information acquired in the first stage will be useful later in the second stage. The second part of this thesis looks at the collection of summary statistics in wireless sensor networks. Summary statistics include arithmetic mean, median, standard deviation, etc, and they belong to the class of symmetric functions. This thesis develops arithmetic computation coding in order to efficiently perform in-network computation for weighted arithmetic sums and symmetric functions. The developed arithmetic computation coding increases the achievable computation rate from

\Theta((\log L)/L)

\Theta(1/\log L)

, where

L

is the number of sensors. Finally, this thesis demonstrates that interaction among sensors is beneficial for computation of type-threshold functions, e.g., the maximum and the indicator function, and that a non-vanishing computation rate is achievable.

EPFL2015

Function Computation over Networks

Chien-Yi Wang

\Theta((\log L)/L)

\Theta(1/\log L)

, where

L

EPFL2015

Low Complexity Scheduling and Coding for Wireless Networks

Siddhartha Brahma

n

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

EPFL2015

Efficient decentralized communications in sensor networks

Razvan Cristescu

EPFL2004