Publication

Bringing Stability to Wireless Mesh Networks

Adel Aziz
2011
EPFL thesis
Abstract

Wireless mesh networks were designed as a mean to rapidly deliver large-scale communication capabilities without the support of any prior infrastructure. Among the different properties of mesh networks, the self-organizing feature is particularly interesting for developing countries or for emergency situations. However, these benefits also bring new challenges. For example, the scheduling decision needs to be performed in a distributed manner at each node of the network. Toward this goal, most of the current mesh deployments are based on the IEEE 802.11 protocol, even if it was not designed for multi-hop communications. The main goals of this thesis are (i) to understand and model the behavior of IEEE 802.11-based mesh networks and more specifically the root causes that lead to congestion and network instability; (ii) to develop an experimental infrastructure in order to validate with measurements both the problems and the solutions discussed in this thesis; (iii) to build efficient hop-by-hop scheduling schemes that provide congestion control and inter-flow fairness in a practical way and that are backward-compatible with the current protocol; and (iv) to explain the non-monotonic relation between the end-to-end throughput and the source rate and to introduce a model to derive the rationale behind this artifact. First, we propose a Markovian model and we introduce the notion of stealing effect to explain the root causes behind the 3-hop stability boundary, where linear networks up to 3 hops are stable, and larger topologies are intrinsically unstable. We validate our analytical results both through simulations and through measurements on a small testbed deployment. Second, to support the experimental research presented in this thesis, we design and deploy a large-scale mesh network testbed on the EPFL campus. We plan our architecture to be as flexible as possible in order to support a wide range of other research areas such as IEEE 802.11 indoor localization and opportunistic routing. Third, we introduce EZ-flow, a novel hop-by-hop congestion-control mechanism that operates at the Medium Access Control layer. EZ-flow is fully backward-compatible with the existing IEEE 802.11 deployments and it works without any form of message passing. To perform its task EZ-flow takes advantage of the broadcast nature of the wireless medium in order to passively derive the queue size at the next-hop node. This information is then used by each node to adapt accordingly its channel access probability, through the contention window parameter of IEEE 802.11. After detailing the different components of EZ-flow, we analyze its performance analytically, through simulations and real measurements. Fourth, we show that hop-by-hop congestion-control can be efficiently performed at the network layer in order to not abuse the contention mechanism of IEEE 802.11. Additionally, we introduce a complete framework that jointly achieves congestion-control and fairness without requiring a prior knowledge of the network capacity region. To achieve the fairness part, we propose the Explore & Enhance algorithm that finds a fair and achievable rate allocation vector that maximizes a desired function of utility. We show experimentally that this algorithm reaches its objective by alternating between exploration phases (to discover the capacity region) and enhancement phases (to improve the utility through a gradient ascent). Finally, we note that, as opposed to wired networks, the multi-hop wireless capacity is usually unknown and time-varying. Therefore, we study how the end-to-end throughput evolves as a function of the source rate when operating both below and above the network capacity. We note that this evolution follows a non-monotonic curve and we explain, through an analytical model and simulations, the rationale behind the different transition points of this curve. Following our analysis, we show that no end-to-end congestion control can be throughput-optimal if it operates directly over IEEE 802.11. Hence, this supports the methodology of performing congestion control in a hop-by-hop manner. After validating experimentally the non-monotonicity, we compare through simulations different state-of-the-art scheduling schemes and we highlight the important tradeoff that exists in congestion-control schemes between efficiency (i.e., throughput-optimality) and robustness (i.e., no throughput collapse when the sources attempt to operate at a rate above the network capacity).

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 (36)
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 (252)

Localizing Traffic Differentiation

Pavlos Nikolopoulos, Muhammad Abdullah, Zeinab Shmeis

Network neutrality is important for users, content providers, policymakers, and regulators interested in understanding how network providers differentiate performance. When determining whether a network differentiates against certain traffic, it is importa ...
2023

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

HolA: Holistic and Autonomous Attestation for IoT Networks

Flavio Toffalini, Eleonora Losiouk

Collective Remote Attestation (CRA) is a well-established approach where a single Verifier attests the integrity of multiple devices in a single execution of the challenge-response protocol. Current CRA solutions are well-suited for Internet of Things (IoT ...
SPRINGER INTERNATIONAL PUBLISHING AG2022
Show more
Related MOOCs (14)
Smart Cities, Management of Smart Urban Infrastructures
Learn about the principles of management of urban infrastructures in the era of Smart Cities. The introduction of Smart urban technologies into legacy infrastructures has already resulted and will con
Smart Cities, Management of Smart Urban Infrastructures
Learn about the principles of management of urban infrastructures in the era of Smart Cities. The introduction of Smart urban technologies into legacy infrastructures has already resulted and will con
Smart Cities, Management of Smart Urban Infrastructures
Learn about the principles of management of urban infrastructures in the era of Smart Cities. The introduction of Smart urban technologies into legacy infrastructures has already resulted and will con
Show more