Mobile backbone synthesis for ad hoc wireless networks

In this paper, we present an extended mobile backbone network topology synthesis algorithm (ETSA) for constructing and maintaining a dynamic backbone structure for mobile ad hoc wireless networks. We present and analyze the mathematical features of the proposed scheme. Using these results, we prove that: (1) The ETSA scheme converges in constant time; (2) The length of each control packet is bounded by a constant value that is independent of the number of network nodes; (3) The size of the backbone network depends only on the size of the operational area and is independent of nodal density. We compare the performance features of this scheme with those characterizing other protocols that employ clustering operations and/or use selective forwarding on demand routing methods. In addition, we present an on-demand routing protocol (MBNR) that makes use of the underlying dynamically self-configuring backbone network infrastructure and demonstrate its performance advantages when compared with an on-demand routing protocol that is based on a flat architecture, as well as with other backbone-based routing protocols.