Distributed network organization and message dissemination in dynamic ad hoc networks

Abstract

In the past decades, dynamic ad hoc networks have played a conspicuously more important role in many real-life areas, including disaster relief, environment monitoring, public safety and so on. Meanwhile, due to the widespread implementation of sensor networks and Internet-of-Things/Vehicles, which are practically dynamic ad hoc networks, there exists an enormous demand on designing suitable models and efficient algorithms for dynamic ad hoc networks. In this thesis, I propose a set of comprehensive dynamic models to depict the dynamicity of, and a number of distributed algorithms addressing the fundamental problems of network organization and message dissemination in dynamic ad hoc networks.

The dynamic behaviors of nodes and links are firstly considered in the first part of the thesis. Different from previously proposed largely independent and somewhat fragmented dynamic models, I propose a new comprehensive dynamic model to cover most of the essential dynamic behaviors of nodes and links. Some efficient randomized and distributed algorithms are designed for the construction of both local and global network organization, which have the nearly optimal performance in terms of the time complexity. The second part of the thesis focuses on the dynamic ambient noise from the environment, which is also called channel jamming in previous works. In this part, I propose a strong adversarial jamming model which removes the budget constraint that is commonly adopted in previous works. Two randomized and distributed algorithms for global network organization and the message dissemination problem are presented, both of which have nearly optimal performance in terms of time complexity. In the third part of the thesis, a fully dynamic model is presented, which can cover both the dynamicity of nodes/links and ambient noise. An efficient randomized and distributed algorithm with worst-case guarantees for the global message dissemination problem is given, which sheds light on distributed algorithm design in real dynamic ad hoc networks.