Topology Control for Mobile Ad Hoc Networks: a Dominating Set Based Approach

In this book, we aim to design and implement algorithms in a distributed environment in order to solve clustering, backbone formation and efficient routing problems for mobile ad hoc networks(MANET)s. Our first goal is to find a connected dominating set (CDS), then construct clusters using the clusterhead information and extend this approach to multi-level clusters. We propose a new connected dominating set based clustering algorithm for clustering in MANETs. In our algorithm we propose a heuristic based approach by considering degrees of the nodes during node selection. We also extend our algorithm in order to generate a hierarchy of clusters. Then, we implement a flooding based routing mechanism on top of CDS based clusters. We propose a two-level flooding mechanism by using CDS members as the gateways of the clusters. We describe the algorithms, analyze their time and message complexities and measure their performance in the simulation environment ns2.