Testbed for Fast-Deployable Flying WiFi Networks

EPFL's Information Processing Group (IPG) and Laboratory for Intelligent Systems (LIS), in conjunction with SenseFly (a LIS spin-off) recently started a project aimed at developing a testbed to experiment with self-organized wireless networks carried by autonomous unmanned aircrafts. The idea is to use drones developed by SenseFly to carry the infrastructure of a self-organized WiFi network for easy and rapid deployment. The network can be used to connect people on the ground (e.g. rescue people in case of catastrophe) and/or to send back to a data center the information collected by sensors. The sensors might also be carried by some of the drones. The drones have a high degree of autonomy. In particular, they are capable of carrying out a missions and land without human intervention. In this work we present the state of this ongoing project that involves many challenges, including resource management, mobility management, self-organization, and scalability.

Neighbor discovery with reception status feedback to transmitters

Ramin Khalili

Neighbor discovery is essential for the process of self-organization of a wireless network, where almost all routing and medium access protocols need knowledge of one-hop neighbors. In this paper we study the problem of neighbor discovery in a static and synchronous network, where time is divided into slots, each of duration equal to the time required to transmit a hello message, and potentially, some sort of feedback message. Our main contributions lie in detailing the physical layer mechanism for how nodes in receive mode detect the channel status, describing algorithms at higher layers that exploit such a knowledge, and characterizing the significant gain obtained. In particular, we describe one possible physical layer architecture that allows receivers to detect collisions, and then introduce a feedback mechanism that makes the collision information available to the transmitters. This allows nodes to stop transmitting packets as soon as they learn about the successful reception of their discovery messages by the other nodes in the network. Hence, the number of nodes that need to transmit packets decreases over time. These nodes transmit with a probability that is inversely proportional to the number of active nodes in their neighborhood, which is estimated using the collision information available at the nodes. We show through analysis and simulations that our algorithm allows nodes to discover their neighbors in a significantly smaller amount of time compared to the case where reception status feedback is not available to the transmitters.

Ieee Service Center, 445 Hoes Lane, Po Box 1331, Piscataway, Nj 08855-1331 Usa2010

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

Network coding for efficient communication in extreme networks

Jean-Yves Le Boudec, Jörg Widmer

Some forms of ad-hoc networks need to operate in extremely performance- challenged environments where end-to-end connectivity is rare. Such environments can be found for example in very sparse mobile networks where nodes ”meet” only occasionally and are able to exchange information, or in wireless sensor networks where nodes sleep most of the time to conserve energy. Forwarding mechanisms in such networks usually resort to some form of intelligent flooding, as for example in probabilistic routing. We propose a communication algorithm that significantly reduces the overhead of probabilistic routing algorithms, making it a suitable building block for a delay-tolerant network architecture. Our forwarding scheme is based on network coding. Nodes do not simply forward packets they overhear but may send out information that is coded over the contents of several packets they received. We show by simulation that this algorithm achieves the reliability and robustness of flooding at a small fraction of the overhead.

2005

Function Computation over Networks

Chien-Yi Wang

\Theta((\log L)/L)

\Theta(1/\log L)

, where

L

EPFL2015