Network coding for efficient communication in extreme networks

Jean-Yves Le Boudec, Jörg Widmer
2005
Article de conférence

Résumé

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.

Official source

https://infoscience.epfl.ch/record/85829?ln=fr

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Concepts associés

Chargement

Publications associées

Chargement

A new relaying scheme for cheap wireless relay nodes

Ramin Khalili

In this paper we will propose a relaying scheme for wireless multi-hop networks. It is based on collaboration of intermediate relays at network layer to forward useful side information in place of dumbly forwarding packets. In our scheme we assume that the nodes are not able to benefit from any interference cancellation mechanism. The channels from sender to relay nodes and from sender to receiver are logically separated through a temporal scheduling. This model is realistic for many practical scenarios in the context of wireless networks. We will show in this paper the information theoretic bounds and show that they are achievable using practical codes. The proposed coding scheme is simulated in realistic scenarios. The obtained results show a remarkable improvement in throughput, relay load and reliability compared to network using classical routing approach.

2005

Chargement

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

Chargement

Embedded sensors and actuators are revolutionizing the way we perceive and interact with the physical world. Current research on such Cyber-Physical Systems (CPSs) has focused mostly on distributed sensing and data gathering. The next step is to move from passive information extraction from the physical world towards an active framework where information is retrieved, processed, and acted upon in situ. As an example of such sensor-actuator systems that provide large-scale, distributed coordination, we consider Intelligent Transportation Systems (ITSs), with the goal of increasing travel safety and efficiency. The proliferation of wireless technologies enables different actors (e.g., pedestrians, motorists, traffic operators) to communicate with each other cheaply, efficiently, and securely. By embedding computational intelligence, communication and control into such ITSs, it will be possible to build collaborative transportation applications that help solve, for example, congestion and parking problems. This thesis explores the following question: To what extent is it possible to build distributed ITS systems that rely exclusively on local communication between nodes? The potential benefits of building such systems without infrastructure are numerous, including lower fixed and variable costs, avoiding regulatory hurdles, lower entry barriers for new players, and more control over privacy. On the other hand, self-organized ITSs without infrastructure have to operate under challenging conditions: large scale, high mobility, lack of end-to-end connectivity, ephemeral contacts between wireless nodes, and heterogeneous node capabilities. Although the networking research community has invested a significant effort in designing service abstractions that mimic traditional IP connectivity on top of wireless ad hoc networks, the ITS scenarios considered in this work are too challenging to implement such a service model. The main goal of this thesis is to design communication service models and their underlying protocols that can operate in collaborative transportation applications, and to demonstrate their effectiveness through analysis of traffic data and through realistic simulations. A key point is that the ITS applications we consider can rely on more limited service primitives, because they do not require a general any-to-any delivery service with strict performance guarantees. We first define the collaborative transportation applications of interest. Then we quantify their potential benefits and discuss their functional requirements. Next, we focus on the problem of the collection of large-scale mobility data. We propose a new method for collecting such data and introduce a novel mobility data mining framework, which is necessary to study collective mobility patterns in the context of wireless ad hoc networking. Relying on the analysis of real-life mobility traces, we find that despite the high node mobility, clusters of time-stable connectivity emerge and last at specific locations. Outside such clusters the connectivity between nodes remains sparse. This leads us to the proposal of a new mobility model that captures in an elegant way two phenomena observed in reality, i.e., emergence of stable clusters and network partitioning. This mobility model, called Heterogeneous Random Walk (HRW), appears to be the worst-case mobility model for many mobility-assisted protocols. Moreover, we show that the HRW mobility model predicts the performance of an epidemic dissemination protocol more accurately than other, similarly parsimonious models. Based on the lessons learned from the mobility data analysis, we propose a new abstraction that allows us to capture collective mobility patterns. This abstraction, called a Mobility Map, can be shared globally among mobile nodes and it can be used to improve communication in mobile partitioned networks (MPNs). Notably, we present a new geocasting protocol called GeoMobCast, which uses Mobility Maps to minimize message delay. This protocol is designed to provide the users of the collective transportation applications with the required communication service. Finally, we turn our attention on the real-life implementation of the distributed ITS that leverage short-range wireless communication. To this extent, we present the results of our experimental work with wireless sensor network technologies. We also present the necessary simulation toolbox designed to implement and evaluate collaborative transportation applications.

EPFL2009

Chargement

Function Computation over Networks

Chien-Yi Wang

\Theta((\log L)/L)

\Theta(1/\log L)

, where

L

EPFL2015

EPFL2009