Abstract
This chapter presents three algorithms to determine stable connected dominating sets (CDS) for wireless mobile ad hoc networks (MANETs) whose topology changes dynamically with time. The three stability-based CDS algorithms are (1) Minimum Velocity (MinV)-based algorithm, which prefers to include a slow moving node as part of the CDS as long as it covers one uncovered neighbor node; (2) Node Stability Index (NSI)-based algorithm, which characterizes the stability of a node as the sum of the predicted expiration times of the links (LET) with its uncovered neighbor nodes, the nodes preferred for inclusion to the CDS in the decreasing order of their NSI values; (3) Strong Neighborhood (SN)-based algorithm, which prefers to include nodes that cover the maximum number of uncovered neighbors within its strong neighborhood (region identified by the Threshold Neighborhood Ratio and the fixed transmission range of the nodes). The three CDS algorithms have been designed to capture the node size—lifetime tradeoff at various levels. In addition to presenting a detailed description of the three stability-based CDS algorithms with illustrative examples, the authors present an exhaustive simulation study of these algorithms and compare their performance with respect to several metrics vis-à-vis an unstable maximum density-based MaxD-CDS algorithm that serves as the benchmark for the minimum CDS Node Size.
TopIntroduction
A mobile ad hoc network (MANET) is a dynamically changing distributed system of arbitrarily moving wireless nodes that operate under resource constraints such as limited battery charge, memory and processing capacity. In addition, the network operates under limited bandwidth, necessitating limited transmission range for the nodes to prevent collisions when packets are transmitted over long-distance. A node within the transmission range of another node is said to be a ‘neighbor’ of the latter, and the set of nodes within the transmission range of a node are said to constitute the ‘neighborhood’ of the node. Due to the limited transmission range of the nodes, MANET routes are generally multi-hop in nature, and these routes are discovered through an expensive broadcast query-reply cycle involving all the nodes in the network. Due to the dynamically changing topology, the routes fail over time, leading to the frequent route discoveries.
A connected dominating set (CDS) is considered as an energy-efficient communication topology for network-wide broadcasting vis-à-vis flooding in mobile ad hoc networks (MANETs). Though flooding guarantees delivery of the broadcast message to all the nodes in the network, the number of retransmissions is significantly high as a node receives a copy of the message from each of its neighbors (each node would have to broadcast a message exactly once). A Connected Dominating Set (CDS) of a network graph comprises of a subset of the nodes such that every node in the network is either in the CDS or is a neighbor of a node in the CDS. With a CDS-based broadcast, a message is broadcast only by the CDS nodes (nodes constituting the CDS) and the non-CDS nodes (who are neighbors of the CDS nodes) merely receive the message, once from each of their neighbor CDS nodes. The efficiency of broadcasting depends on the CDS Node Size that directly influences the number of redundant retransmissions.
In a unit-disk graph modeling a MANET, all the nodes in the network are represented as vertices; there exists an edge between any two nodes in the graph only if the two nodes corresponding to the end vertices of the edge are neighbors in the MANET (Kuhn et. al., 2004). We say a network is covered if every node in the network is either in the CDS or is a neighbor of a node in the CDS. As nodes operate with a limited transmission range, a CDS is often not fully connected (i.e., a CDS node is not connected to every other CDS node) and a non-CDS node may not be in the neighborhood of every CDS node. A CDS is considered to be broken if either a CDS node is not reachable to any of the other CDS nodes (directly or through multi-hop paths) or a non-CDS node is not in the neighborhood of at least one CDS node. Due to the dynamically changing topology of MANETs, a CDS may not exist for the entire communication session. In prior research, Meghanathan (2006) as well as Velummylum and Meghanathan (2010) have observed the commonly used minimum node-size based connected dominating set (MCDS) to be quite unstable for MANETs, requiring frequent transitions from one CDS to another. A MCDS is preferred because of its tendency to contain as few nodes as possible to be part of the connected dominating set, minimizing the number of unnecessary retransmissions in network-wide broadcasts.
This book chapter will present three different algorithms to determine stable connected dominating sets (CDS) for MANETs and an exhaustive simulation-based performance comparison study of these algorithms in comparison with the classical MCDS algorithm. The algorithms will be based on the idea of iteratively including nodes into CDS (one node per iteration) until all nodes in the network are covered by at least one node in the CDS. To maintain CDS connectivity, only covered nodes (i.e., a node that is in the neighborhood of a node already in the CDS) will be considered as candidate nodes for inclusion into the CDS. We now describe the underlying principle behind the three algorithms proposed to determine stable connected dominating sets and the associated tradeoffs.
Key Terms in this Chapter
Connected Dominating Set (CDS): A subset of nodes in the network (that are reachable from one another either directly or through one or more nodes in the CDS) such that every node in the network is either in the subset or is a neighbor of a node in the subset.
Topology: An arrangement of the nodes in the network that can be used for communication between any two nodes in the network.
CDS Node Size: The number of nodes constituting the CDS.
Edge Distance Ratio (EDR): The EDR for an edge is the ratio of the physical Euclidean distance between the two constituent end nodes of the edge to that of the fixed transmission range.
Threshold Neighbor Distance Ratio (TNDR): The TNDR is the maximum value of the EDR for an edge i — j , in order for node i to be considered a “strong” neighbor of node j and vice-versa.
Mobile Ad Hoc Network (MANET): A network whose topology changes dynamically with time due to the mobility of the nodes.
Hop Count per s-d Path: The number of edges on a path, between any two nodes s and d, whose intermediate nodes, if any such exists, are those that are part of the CDS.
Strong Neighborhood: Node j belongs to the strong neighborhood of node i (denoted SN i ) and vice-versa if the EDR of the edge i — j is = TNDR . Note that the strong neighborhood of a node is a subset of the nodes in its open neighborhood .
Open Neighborhood: Node j belongs to the open neighborhood of node i (denoted ON i ) if the physical Euclidean distance between node i and j is = R , the transmission range of the nodes in the network. Every node j ON i is simply referred to as a “neighbor” of node i .
Stability: A characteristic of communication topologies related to the duration of existence of the topology; the longer the topology exists, the more stable it is.
Algorithm: A sequence of steps to perform a particular task.
CDS Edge Size: The number of edges connecting any two nodes in the CDS.
Transmission range: The maximum distance between any two nodes such that the signal emanating from one node could directly reach the other node with strength appreciable enough to correctly extract the encoded information.
CDS Lifetime: The duration of existence of a CDS.
Node Stability Index (NSI): The NSI value of a node is the sum of the predicted expiration times of the links with its neighbors.