Article Preview
TopIntroduction
A Mobile Ad hoc Network (MANET) is a dynamic distributed system of arbitrarily moving wireless nodes that operate under limited battery charge and bandwidth. The transmission range of the nodes is limited to conserve energy as well as to avoid collisions and interference that may result from long-distance transmissions. By virtue of all these resource constraints, MANET routes are often multi-hop in nature and change with time depending on node mobility and availability. To minimize resource usage, MANET routing protocols predominantly adopt an on-demand approach to discover the appropriate communication topologies (paths, trees, mesh, etc.) only when needed rather than using a proactive approach of determining them irrespective of the need (Broch et al., 1998; Johansson et al., 1999).
The MANET on-demand routing protocols typically employ a global broadcast request-reply cycle, called flooding, to discover the paths for unicasting as well as trees and meshes for multicasting (Siva Ram Murthy, 2004). With flooding, a source node (or the starting node) initiates the broadcast of the Route Request (RREQ) packets and these packets are forwarded exactly once by every other node to their neighbor nodes. The targeted nodes of the route discovery (referred to as destination nodes for unicasting and receiver member nodes for multicasting) choose the best path traversed by these RREQ packets, depending on their route selection principles, and send a Route Reply (RREP) packet on the chosen path. Flooding increases the chances of discovering the optimal communication topology as the RREQ packets traverse through several routes and the destination can choose the best path among several choices. However, with flooding, the network incurs lot of control overhead in requiring each node to broadcast (even though it is done only once) the RREQ message to the neighborhood. The level of redundancy of retransmissions is such that every node in the network gets a copy of the broadcast message from each of its neighbors.
Recent studies in the literature (e.g., Sinha et al., 2001; Wang et al., 2005; Sakai et al., 2008; Sheu et al., 2009; Bao & Garcia-Luna-Aceves, 2010) have demonstrated that a connected dominating set (CDS) of the underlying network can be used as a backbone to broadcast a message from one node to all the other nodes in the network. A CDS of a network graph is defined as the subset of the nodes in the network such that every node in the network is either in the CDS or is a neighbor of a node in the CDS. The message to be broadcast (such as a RREQ message) is forwarded only by the nodes that are part of the CDS and the nodes that are not in the CDS (referred to as the non-CDS nodes) merely receive the message from one or more neighboring CDS nodes that cover their non-CDS neighbors. The efficiency of broadcasting using a CDS lies in minimizing the number of redundant retransmissions and this depends on the number of nodes that are part of the CDS (referred to as CDS Node Size). By definition, all the nodes in the network could be considered as part of the CDS, in that case broadcasting through the CDS nodes is nothing but flooding. Hence, minimizing the CDS Node Size has been the primary objective of the algorithms proposed in this category so that we will have minimum number of redundant retransmissions. The CDS with the minimum number of nodes is referred to as a Minimum Connected Dominating Set (MCDS). Determining the MCDS for a network graph is an NP-complete problem (Cormen et al., 2001). Several heuristics have been proposed to closely approximate the optimal solution in polynomial time. The Maximum Density-based CDS (MaxD-CDS) algorithm (Meghanathan, 2006) studied in this paper is one such heuristic to minimize the CDS Node Size and is based on the strategy of preferring to include nodes that have the maximum number of uncovered neighbors as part of the CDS.