Authorization

 

Journal

Volume 11, №1

 
Modified Merging Clustering and Backbone Formation Algorithms for Mobile Ad Hoc Networks (pages 46-73)
Orhan Dagdeviren, Kayhan Erciyes, Deniz Cokuslu


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 and hoc networks. The clusters 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.

Keywords: Clustering, Backbone Formation, Mobile Ad Hoc Networks, Layered Architecture, Spanning Tree, Message Complexity, Time Complexity.

AMS Subject Classification: 68.



COIA 2027

7-9 July 2027
Baku, Azerbaijan

Search