Optimal regional consecutive leader election in mobile ad-hoc networks Conference Paper uri icon

abstract

  • The regional consecutive leader election (RCLE) problem requires mobile nodes to elect a leader within bounded time upon entering a specific region. We prove that any algorithm requires (Dn) rounds for leader election, where D is the diameter of the network and n is the total number of nodes. We then present a fault-tolerant distributed algorithm that solves the RCLE problem and works even in settings where nodes do not have access to synchronized clocks. Since nodes set their leader variable within O(Dn) rounds, our algorithm is asymptotically optimal with respect to time complexity. Due to its low message bit complexity, we believe that our algorithm is of practical interest for mobile wireless ad-hoc networks. Finally, we present a novel and intuitive constraint on mobility that guarantees a bounded communication diameter among nodes within the region of interest. 2011 ACM.

name of conference

  • Proceedings of the 7th ACM ACM SIGACT/SIGMOBILE International Workshop on Foundations of Mobile Computing

published proceedings

  • Proceedings of the 7th ACM ACM SIGACT/SIGMOBILE International Workshop on Foundations of Mobile Computing

author list (cited authors)

  • Chung, H. C., Robinson, P., & Welch, J. L.

citation count

  • 13

complete list of authors

  • Chung, Hyun Chul||Robinson, Peter||Welch, Jennifer L

publication date

  • January 2011