Publication

On broadcast and agreement in mobile ad hoc networks

Yoav Sasson
2007
EPFL thesis
Abstract

This thesis studies communication and agreement protocols in wireless ad hoc networks from both theoretical and practical perspectives. The last decade has given rise to the rapid growth of wireless telecommunications such as cellular mobile phone networks and wireless LANs. The diversity of network-aware appliances and devices is ever-increasing. Ultimately, these wireless technologies will seemingly inter-operate, offering a new range of services. This ubiquity of wireless devices will introduce a paradigm shift in the way we conceive distributed applications. Wireless ad hoc networks are self-organizing radio networks that do not rely on a preexisting infrastructure to communicate. Nodes of such networks have limited transmission range, and data packets may need to traverse multiple other nodes before reaching their destination. Research in wireless multi-hop networks was initiated 1970s by the Defense Advanced Research Projects Agency (DARPA) and has regained popularity nowadays due to the widespread availability of wireless devices. Examples of wireless ad hoc networks are i) sensor networks, which are distributed sensors that monitor environmental conditions for civil or military purposes, ii) vehicular ad hoc networks, which offer inter/intra-vehicle and infrastructure-to-vehicle communication to improve the safety, security and efficiency of transportation systems and iii) mesh networks, which provide an instantaneous, reliable and inexpensive network infrastructure to local communities. The multi-hop nature of wireless ad hoc networks, along with possible node mobility and limited energy supplies lead to highly dynamic network topology and significantly different network characteristics and behavior than their wired counterparts. Algorithms that have proved successful for traditional networks such as LANs and WANs are generally not directly transposable to such dynamic environments. This thesis is divided into two parts. In the first part we focus on basic communication primitives such as broadcast and multicast. We first study the impact of mobility on the time complexity of deterministic broadcast algorithms. We then explore the phase transition phenomenon observed in percolation theory and random graphs as a basis for reducing the overhead of broadcast through probabilistic flooding, while maintaining satisfactory message delivery reliability. Finally, we propose a novel location service solution for handling geographically scattered and mobile multicast group members, by dynamically adjusting the number and density of nodes responsible for managing multicast group membership information. The second part of the thesis studies agreement problems. Agreement-related solutions can contribute to enhance the structure and reliability to the highly disorganized and dynamic environment of self-organized networks. We first investigate the consensus problem in the context of self-organized networks. Consensus is a cornerstone of many agreement problems. We define a variant of the traditional consensus problem, by relaxing the requirement for the set of participating processes to be known by all at the beginning of the computation. We then identify the necessary and sufficient conditions under which consensus can be solved. We finally address the problem of resource allocation in mobile ad hoc networks, by designing a novel broadcast mechanism that achieves reliable and total-order delivery of messages with high probability. These properties provide the basis of a mutual exclusion algorithm.

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 (38)
Wireless mesh network
A wireless mesh network (WMN) is a communications network made up of radio nodes organized in a mesh topology. It can also be a form of wireless ad hoc network. A mesh refers to rich interconnection among devices or nodes. Wireless mesh networks often consist of mesh clients, mesh routers and gateways. Mobility of nodes is less frequent. If nodes constantly or frequently move, the mesh spends more time updating routes than delivering data.
Wireless ad hoc network
A wireless ad hoc network (WANET) or mobile ad hoc network (MANET) is a decentralized type of wireless network. The network is ad hoc because it does not rely on a pre-existing infrastructure, such as routers or wireless access points. Instead, each node participates in routing by forwarding data for other nodes. The determination of which nodes forward data is made dynamically on the basis of network connectivity and the routing algorithm in use.
Wireless network
A wireless network is a computer network that uses wireless data connections between network nodes. Wireless networking allows homes, telecommunications networks and business installations to avoid the costly process of introducing cables into a building, or as a connection between various equipment locations. Admin telecommunications networks are generally implemented and administered using radio communication. This implementation takes place at the physical level (layer) of the OSI model network structure.
Show more
Related publications (241)

A Tutorial-Cum-Survey on Percolation Theory With Applications in Large-Scale Wireless Networks

Ainur Zhaikhan

Connectivity is an important key performance indicator and a focal point of research in large-scale wireless networks. Due to path-loss attenuation of electromagnetic waves, direct wireless connectivity is limited to proximate devices. Nevertheless, connec ...
Ieee-Inst Electrical Electronics Engineers Inc2024

Self-powered transformer intelligent wireless temperature monitoring system based on an ultra-low acceleration piezoelectric vibration energy harvester

Xin Chen

The wireless sensor nodes used for monitoring the condition of grid equipment always be powered by disposable batteries. However, it introduces disadvantages, such as inconvenient replacement, short lifespan, and envi-ronmental pollution, significantly imp ...
ELSEVIER2023

Beam Selection and Tracking for Amplify-and-Forward Repeaters

Andreas Peter Burg, Adrian Schumacher, Ruben Merz

Mobile network operators constantly have to upgrade their cellular network to satisfy the public's hunger for increasing data capacity. However, regulatory limits regarding allowed electromagnetic field strength on existing cell sites often limit or preven ...
IEEE2022
Show more
Related MOOCs (12)
Digital Signal Processing I
Basic signal processing concepts, Fourier analysis and filters. This module can be used as a starting point or a basic refresher in elementary DSP
Digital Signal Processing II
Adaptive signal processing, A/D and D/A. This module provides the basic tools for adaptive filtering and a solid mathematical framework for sampling and quantization
Digital Signal Processing III
Advanced topics: this module covers real-time audio processing (with examples on a hardware board), image processing and communication system design.
Show more

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.