Managing a Dynamic Broadcast Infrastructure in Mobile Ad Hoc Networks through Distributed and Asynchronous Update of a Virtual Backbone
Siomina,Iana
Dept of Science and Technology, Linkoping University
Yuan,Di
Dept of Science and Technology, Linkoping University
Broadcast communication in wireless ad hoc networks can be implemented by means of a virtual backbone. Backbone nodes forward broadcast messages for others. A classical way of constructing such a backbone is to find a connected dominating set in the underlying
graph. Based on this concept, a great amount of research has been devoted to backbone formation in static networks. In contrast, distributed backbone management in the presence of node mobility has
been explored to a less extent. We present a distributed algorithm for managing a dynamic broadcast infrastructure in mobile ad hoc networks. The algorithm relies on neither location information nor any kind of global knowledge of the network. What's more, the algorithm does not require time synchronization between nodes. Decisions of joining and leaving the backbone are made locally at nodes. A node joins the backbone if connectivity between some neighbors is seemingly broken. To keep the size of the backbone small, a backbone node applies randomized pruning if its neighbors are connected through other backbone nodes. In our simulation experiments we examine backbone size and connectivity with respect to node mobility. The results demonstrate the effectiveness of the algorithm.
Iana Siomina has received her M.Sc. degree in numerical analysis and scientific computing from the Royal Institute of Technology, Sweden and M.Sc in Computer and System Sciences from Stockholm University in 2002 and 2004, respectively. Currently, she is working towards her Ph.D. degree in Infrainformatics at the Department of Science and Technology, Linkoping Institute of Technology, Sweden. Her main research interests include radio resource management in wireless networks, efficient communication protocols in ad hoc networks, and network planning and optimization for UMTS and Wireless LANs.