Building Wireless Network Coding Protocols

Lorenzo Keller
EPFL, 2012
EPFL thesis

Abstract

This work studies how to build wireless network protocols that achieve better reliability, lower delay and higher throughput than existing alternatives by using network coding and by exploiting the broadcast nature of the wireless channel. In the first part collection protocols, protocols used to gather information from a set of sources in a central location, are studied. Three scenaria where network coding helps data collection are discussed. First, network coding is used to reduce the overhead associated with end-to-end headers employed in traditional collection protocols. The main idea is to jointly code messages and identity of their sources using subspace codes. The benefits of the proposed protocol are assessed on a simulated testbed of wireless sensor nodes. Second, network coding is used to implement in-network function computation without requiring specialized operation of the routers. Finally, a complete protocol, SenseCode, is presented. This protocol uses network coding and overhearing as a lightweight alternative to multipath for improved reliability. The protocol performance is tested in a wide range of conditions using a simulated testbed of wireless nodes. The second part of the thesis shows how network coding can be used in broadcast protocols, protocols that are used to distribute information from a set of sources to all the network participants. First, flooding protocols for multi-hop networks are analyzed: the main objective is to improve reliability and reduce delay of this class of protocols. Existing codes and a novel scheme are tested using simulations and on a testbed made of mobile phones. Second, a complete system, MicroCast, that enables a group of mobile devices to receive high rate video content is presented. The system uses collaboratively the long range wireless links that connect each mobile device to the infrastructure and the short range local links that connect the devices among themselves. The system uses network coding and overhearing on the local links to improve the efficiency of utilization of the local radio resources.

Official source

https://infoscience.epfl.ch/record/180649?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

Lorenzo Keller
EPFL, 2012
EPFL thesis

Abstract

Official source

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

About this result

Related concepts (25)

Related concepts

Related publications (23)

Related publications

SenseCode: Network Coding for Reliable Sensor Networks

Emre Atsan, Christina Fragouli, Lorenzo Keller

Designing a communication protocol for sensor networks often involves obtaining the "right" trade-off between energy efficiency and reliability. In this paper, we show that network coding provides a means to elegantly balance these two goals. We present the design and implementation of SenseCode, a collection protocol for sensor networks---and, to the best of our knowledge, the first such protocol to employ network coding. SenseCode provides a way to gracefully introduce a configurable amount of redundant information in the network, thereby increasing reliability in the face of packet loss. We compare SenseCode to the best (to our knowledge) existing alternative and show that it improves reliability (in our experiments typically by 15%-20%), while consuming a comparable amount of network resources. We have implemented SenseCode as a TinyOs module, and evaluate it through extensive TOSSIM simulations.

2009

Bringing physical layer cooperation closer to practical wireless systems

Emre Atsan

Nowadays the demand for communication over the wireless medium is significantly increasing, while the available wireless spectrum is already limited. In this thesis, we introduce new practical physical layer designs that employ node cooperation for more efficient wireless spectrum utilization. First, a cooperative scheme is introduced that takes advantage of the existence of simultaneous multiple frequency band operation in modern wireless devices. The main idea of this scheme is to use one frequency band for sharing data among collaborating nodes, and another one for cooperatively transmitting to a common destination. The benefits of such a cooperative design across frequency bands are evaluated on a testbed of software-defined radios, where we investigate and identify the possible network conditions under which our scheme enables better throughput compared to the traditional operation. Second, we present a practical design that facilitates physical layer cooperation in Long Term Evolution (LTE) networks. The main idea here is to adapt the inherent Hybrid Automatic Repeat-reQuest (H-ARQ) in standard LTE operation, so that multiple relays can cooperate over the transmission of one encoded block. Performance evaluation of the design reveals significant throughout gains under asymmetric channel conditions for parallel relay networks in LTE framework. Finally, we look at the node cooperation from a privacy perspective in wireless sensor networks. To this end, we design and evaluate a low-overhead message encryption protocol based on network coding. The main idea of the protocol is to employ node cooperation to increase the inherent weak security that network coding offers. Results show up to 60% increase in terms of extra security added on top of the inherent one.

EPFL2015

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