1st Annual Conference on Broadband Networks

Research Article

A distributed mobile backbone formation algorithm for wireless ad hoc networks

  • @INPROCEEDINGS{10.1109/BROADNETS.2004.4,
        author={Hueijiun Ju and Izhak Rubin and Kevin Ni and Christopher Wu},
        title={A distributed mobile backbone formation algorithm for wireless ad hoc networks},
        proceedings={1st Annual Conference on Broadband Networks},
  • Hueijiun Ju
    Izhak Rubin
    Kevin Ni
    Christopher Wu
    Year: 2004
    A distributed mobile backbone formation algorithm for wireless ad hoc networks
    DOI: 10.1109/BROADNETS.2004.4
Hueijiun Ju1,*, Izhak Rubin1,*, Kevin Ni1, Christopher Wu1
  • 1: Electrical Engineering Department, University of California, Los Angeles 420 Westwood Plaza, Los Angeles, CA 90095
*Contact email: hju@ee.ucla.edu, rubin@ee.ucla.edu


In this paper, we present a novel fully distributed version of a mobile backbone network topology synthesis algorithm (MBN-TSA) for constructing and maintaining a dynamic backbone in mobile wireless ad hoc networks. The following features induce the key advantages offered by the algorithm: a) the MBN-TSA algorithm is designed to work with the unreliable natural of wireless environment; b) the backbone layout is dynamically formed and locally modified in response to communications link quality fluctuations, nodal failures and nodal mobility; c) a control mechanism employing the BN_neighbor_limit threshold as a key parameter, is introduced to control the size of the backbone network (BNet) and improve stability; d) analytical results show that the MBN-TSA has very little control overhead: time complexity in the order of O(l) and message complexity in the order of O(l) per node. In addition, we present an on-demand routing protocol that makes use of the underlying dynamically self-configured MBN network infrastructure. By carrying out extensive simulations, we demonstrate the performance advantages when compared to a non backbone oriented on-demand ad hoc routing protocol such as AODV.