Modelling the IEEE 802.11 protocol in wireless multi-hop networks

IEEE 802.11 is probably the most widely used, medium access control protocol in current wireless networks. In the Wireless LAN (i.e., single-hop) setting, its performance is by now quite well understood. However, in the multi-hop setting where relay nodes are used to achieve end-to-end communication, there is, to date, no widely accepted model. Consequently, when confronted with experimental results, people often find it hard to interpret them. The goals of this thesis are (i) to model protocols "à la 802.11" in the context of multi-hop ad hoc networks, (ii) to derive theoretical limits for their performance, (iii) to contrast the performance of the current IEEE 802.11 protocol with these limits and (iv) to identify all the factors that prevent IEEE 802.11 from reaching these limits. Most of this thesis is dedicated to achieving the two first goals. We begin by proposing an idealized version of IEEE 802.11. We model this idealized protocol using a continuous Markov chain. We then use the properties and the stationary distribution of this Markov chain to derive the performance of the idealized 802.11 protocol. We first look at its spatial reuse or, in other words, at its ability to schedule a large number of concurrent successful transmissions. We show that the idealized 802.11 protocol organizes the transmissions in space in such a way that it leads to an optimal spatial reuse when its access intensity is large. This is encouraging, as it shows that a protocol using only local interactions can find a global optimum in a completely decentralize way. We then consider the short and long-term fairness properties of the idealized 802.11 protocol. We observe a clear trade-off between its spatial reuse and its fairness. At low access intensities, its fairness is high but its spatial reuse is low; whereas at high access intensities, the reverse is true. As a result, the access intensity of the protocol can be used to adapt its performance to fit the requirements of the applications running on top of it. The fairness performance of 802.11 also highly depends on the underlying network topology – 802.11 only amplifies the existing topological inequalities. In regular lattice topologies these inequalities arise only at the border where the nodes have fewer neighbors than the nodes inside the network. We demonstrate that, in large line networks and for all finite access-intensities, this border effect does not propagate inside the network, as a result 802.11 is fair. In contrast, we demonstrate that in large grid topologies a phase transition occurs. Under a certain access intensity, the border effect fades away; whereas above a certain access intensity, it propagates throughout the network, and the protocol is severely unfair. Finally, after extending our model to consider different node sensing and capture capabilities, we compare the performance of the ns-2 implementation of IEEE 802.11 and of the idealized protocol. We observe a large gap between the theoretical and practical performance. We identify the three problems that are responsible for this gap. We then propose a remedy to address each of these problems, and show that a 'cured' IEEE 802.11 can achieve the level of performance of the idealized 802.11 protocol.