A distributed mobile backbone formation algorithm for wireless ad hoc networks

Abstract

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/spl I.bar/neighbor/spl I.bar/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.