On broadcast and agreement in mobile ad hoc networks

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.