Modıfıed mergıng clusterıng and backbone formatıon algorıthms for mobıle ad hoc networks

Abstract

Clustering and backbone formation are widely used techniques to manage the routing operation in mobile ad hoc networks (MANET)s. In this work, we provide algorithms to form a backbone that is highly resilient to mobility and topology variations in mobile ad hoc networks. The first algorithm forms clusters of nodes in the mobile network each with a leader. The clusters are constructed in a balanced way to distribute the network load evenly. The second algorithm builds a ring network among the leaders of the clusters. The ring backbone is constructed in a fault tolerant and energy efficient way. These two algorithms are integrated in a communication architecture. To the best of our knowledge, our algorithms are the first attempts that construct balanced clusters with a ring backbone. We show the operation of the algorithms, analyze their proof of correctness, time and message complexities and provide the simulation results in ns2 environment against the density, number of clusters, and mobility of the network. We compare our proposed algorithms with the existing algorithms, and show that our algorithms create a controllable number of balanced clusters and robust ring backbone infrastructures while, providing low message count and run-time.