Implementing Abstract MAC Layer in Dynamic Networks

Dynamicity is one of the most challenging, yet, central aspects of wireless networks. Dynamicity can come in many guises, such as churn (node insertion/deletion) and node mobility. Although the study of dynamic networks has been popular in distributed computing domain, previous works considered only partial factors causing dynamicity. We here propose a dynamic model that is comprehensive to include crucial dynamic factors on nodes and links. Our model defines dynamicity in terms of localized topological changes in the vicinity of each node, rather than a global view of the whole network. Obviously, a localized dynamic model suits distributed algorithm studies better than a global one. The proposed dynamic model uses the more realistic SINR model to describe wireless interference, instead of the oversimplified graph-based models adopted in most existing works. Under the proposed dynamic model, we provide an efficient distributed algorithm accomplishing local broadcast services in the abstract MAC layer that was first presented by Kuhn et al.\ \cite{DBLP:conf/wdag/KuhnLN09}. Our solution paves the road for many new fast algorithms for solving high-level problems in dynamic networks, such as consensus, single-message broadcast, and multiple-message broadcast. Extensive simulations show that our algorithm exhibits good performance in realistic environments with dynamic behaviors.