Centrality-based Connected Dominating Sets for Mobile Ad hoc Networks

Abstract

We investigate the use of centrality measures to determine connected dominating sets (CDSs) for mobile ad hoc networks (MANETs) whose topology changes dynamically with time. A CDS is typically considered the graph theory equivalent for the backbone of a network and has been commonly used as the underlying topology for network-wide broadcasts with minimal retransmissions (accomplished by including fewer nodes in the CDS). In the case of MANETs, the degree centrality has been so far the most commonly used measure to determine a CDS with minimum node size (number of constituent nodes in the CDS). But, degree centrality-based CDS has been observed to be quite unstable in the presence of node mobility. In the rapidly emerging area of Network Science, centrality measures such as Eigenvector centrality, Betweenness centrality and Closeness centrality are used for complex network analysis. In this paper, we explore the use of these three centrality measures as the underlying criterion for inclusion of nodes in a CDS for MANETs and evaluate the lifetime and node size of such CDSs in comparison to that incurred for the degree centrality-based CDS and the maximum stable CDS determined using a benchmarking algorithm. We observe the Eigenvector centrality-based CDS to be the most stable (but the CDS node size is also the largest); the Betweenness centrality-based CDS is the least stable (but incurs the smallest CDS node size). The Betweenness centrality-based CDS incurs the lowest values for the CDS Node Size / CDS Lifetime tradeoff ratios when most of the nodes, if not all of them, are mobile.