Dominating Sets Routing Mobile Ad Hoc Networks Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

we propose a routing methodology using a graph theory concept called Dominating sets in mobile Ad hoc networks. Efficient routing among a set of mobile hosts is one of the most important functions in mobile ad hoc wireless networks. Routing based on a Connected Dominating Set is a promising-approach, where the searching space for a route is reduced to nodes in the set. A set is dominating if all the nodes in the set are either in the set or neighbors of nodes in the set.

Our approach uses a centralized algorithm for dominating set construction. Constructing Dominating Sets (DS) creates a virtual infrastructure for the mobile ad hoc network and handles routing in an efficient manner. DS can create a virtual network backbone for packet routing . Messages can be routed from the source to a neighbor in the dominating set, along the DS to the dominating set member closest to the destination node, and then finally to the destination. This is termed Dominating set based routing or Backbone based routing or spine based routing. Restricting the routing to the DS results in a significant reduction in message overhead associated with routing updates.

Keywords-Mobile Adhoc network,Dominating set,Guha Khuller's Algorithm,AODV.

I. Introduction

Mobile Ad hoc Networks

Mobile Ad Hoc Networks (MANETs) refer to a class of wireless network that can be formed dynamically and randomly without the need for infrastructural setups. Such networks are able to adapt and reconfigure themselves on the fly according to node mobility and changing network topologies. These characteristics are particularly attractive to the military user due to the inherent unpredictability of the tactical environment.

MANET technology has its roots in defence, having been developed from military research efforts.

B. Routing in Mobile Ad hoc Networks

Each node in a Mobile ad hoc network is responsible for routing, hence each node should maintain necessary information about the next hop or the path through which the data has to be routed to the destination. A number of routing protocols (e.g. Destination Sequenced Distance Vector (DSDV) Dynamic Source Routing (DSR), Ad hoc On Demand Distance Vector (AODV)) have been proposed for mobile ad hoc networks.

C. Techniques Used

By routing, we mean process of exchanging information from one station to the other stations of the network. Routing protocols of mobile ad-hoc network tend to need different approaches from existing Internet protocols, since most of the existing Internet protocols were designed to support routing in a network with fixed structure. Proposed solutions could be classified into two types: table-driven, on-demand protocols.

(i) Table Driven Protocols

Table-driven protocols are one of the old ways of acquiring routing in mobile ad-hoc networks. These protocols maintain consistent overview of the network. Each node uses routing tables to store the location information of other nodes in the network. This information is used to transfer data among various nodes of the network. To ensure the freshness of the routing tables, these protocols adopts different sorts of mechanisms. The best known proactive protocol is Destination Sequence Distance Vector (DSDV) protocol.

(ii) On Demand Routing protocol

Another in the family of routing protocols for mobile ad-hoc network is on-demand routing protocols. With on-demand protocols, if a source node requires a route to the destination for which it does not have route information, it initiates a route discovery process which goes from one node to the other until it reaches to the destination or an intermediate node has a route to the destination. It is the responsibility of the route request receiver node to reply back to the source node about the possible route to the destination. The source node uses this route for data transmission to the destination node. Some of the better known on-demand protocols are Ad-hoc On-demand Distance Vector routing (AODV), Dynamic Source Routing (DSR) and Temporary Ordered Routing Algorithm (TORA).

D. Dominating Sets

In graph theory, a dominating set for a graph G = (V, E) is a subset V′ of V such that every vertex not in V′ is joined to at least one member of V′ by some edge. The domination number γ(G) is the number of vertices in the smallest dominating set for G







Fig.1.Graph showing Dominating Sets

In the graph above, {4,5} is an example of a dominating set of size 2.

A Connected Dominating Set (CDS) is a connected DS,that is,there is a path between any two nodes in CDS that does not use nodes that are not in CDS.

Fig.1. shows Connected Dominating Set (CDS).

The dominating set problem is an NP-complete problem in graph theory.

The famous classical Dominating set problem is Five-Queens problem where all the five queens are placed in a chessboard so that they donot attack each other.

E.Routing in Mobile Ad hoc Networks using Dominating Sets

Dominating-set-based routing is based on the concept of Dominating Set in graph theory. In mobile ad hoc networks (MANETs), the routing of messages is performed by ordinary nodes. In fact, a MANET typically has no network infrastructure, therefore all routing and network management functions must be performed by ordinary nodes. The key to scalability and efficiency in traditional computer networks is the organization of the network infrastructure into a hierarchical structure. However, due to the lack of a network infrastructure, MANETs are inherently flat. In order to achieve scalability and efficiency, new algorithms have emerged that rely on a virtual network infrastructure, which organizes ordinary nodes into a hierarchy. The construction of this infrastructure is the primary application of Dominating Sets (DS) in wireless networks.

The main idea of this approach is to reduce the routing and searching process to a sub graph induced from the dominating set. Moreover, the dominating set should be connected for the ease of the routing process within the induced graph consisting of dominating nodes only. Vertices in a dominating set are called gateway hosts while vertices that are outside a dominating set are called non-gateway hosts. The main advantage of connected dominating-set-based routing is that it simplifies the routing process to the one in a smaller sub network generated from the connected dominating set. This means that only gateway hosts need to keep routing information. As long as changes in network topology do not affect this sub network there is no need to re-calculate routing tables.



Routing in MANETs is difficult since mobility causes frequent network topology changes and requires more robust and flexible mechanisms to search for and maintain routes.

B. Ad hoc On Demand Distance Vector Routing Protocol

Ad-hoc On-demand Distance Vector (AODV) routing is a routing protocol for Mobile Ad-hoc Networks (MANETs) and other wireless ad-hoc networks. AODV is capable of both unicast and multicast routing. It is a reactive routing protocol, meaning that it establishes a route to a destination only on demand. In contrast, the most common routing protocols of the Internet are proactive, meaning they find routing paths independently of the usage of the paths. AODV is, as the name indicates, a distance-vector routing protocol. AODV avoids the counting-to-infinity problem of other distance-vector protocols by using sequence numbers on route updates, a technique pioneered by DSDV.In AODV, the network is silent until a connection is needed. At that point the network node that needs a connection broadcasts a request for connection. Other AODV nodes forward this message, and record the node that they heard it from, creating an explosion of temporary routes back to the needy node. When a node receives such a message and already has a route to the desired node, it sends a message backwards through a temporary route to the requesting node. The needy node then begins using the route that has the least number of hops through other nodes. Unused entries in the routing tables are recycled after a time.When a link fails, a routing error is passed back to a transmitting node, and the process repeats.



Connected Dominating Set (CDS) based routing has a significant advantage for Mobile ad hoc wireless network when comparing with other routing protocol. It simplifies the routing process to the smaller sub-network generated from the connected dominating set. Thus if a proactive approach is used, only the hosts in the CDS need to keep routing information. If a reactive approach is applied, the dynamic search process for a route is restricted to the dominating set only, so the search space is reduced to the sub-network (backbone network) generated from the CDS. In general, by introducing CDS the searching space for routing is limited to the backbone network formed by members of CDS. In Mobile ad hoc wireless network, the topology is continuously changed due to node mobility, changes in links between nodes may invalidate the current backbone, thus the price paid to recalculate CDS should not be high.


Many optimization problems on graphs are NP-Complete. This means that we cannot solve these problems in polynomial time. A number of algorithms for Connected Dominating set construction have been proposed for the past few years. Algorithms for Connected Dominating Set construction in Mobile ad hoc networks can be divided into two categories: 1) Centralized algorithms that depend on global topology information (network-wide) 2) Decentralized algorithms that depend on local topology information only.

(a) Centralized Algorithms

Guha and Khuller's Algorithm

Ruan's Algorithm

Cheng's Greedy Algorithm

Min's Algorithm

Butenko's Algorithm

(b) Distributed Algorithms

WCDS Construction

Greedy CDS Construction

MIS Based CDS Construction

Alzoubi and Wan's Single Leader Algorithm

Cheng's Single Leader Algorithm

Alzoubi's Multiple Leader algorithm

Cheng's Multiple Leader Algorithm

Single Leader vs. Multiple Leader

Pruning Based CDS Construction

Wu and Li's Algorithm

Butenko's algorithm

Multipoint Relaying Based CDS Construction

Steiner Tree Based CDS Construction

C.Application in MANETs

Dominating sets improves spatial reuse, collision avoidance & QOS

Dominating sets can create a virtual network backbone for packet routing and Control. Restricting the routing to the CDS results in a significant reduction in message overhead associated with routing updates.

The dominating set can be organized into a hierarchy to further reduce control message overhead

Dominating Set is useful for location-based routing

The efficiency of multicast/broadcast routing can also be improved through the utilization of Dominating Sets.

Nodes in a wireless network often have a limited energy supply. Dominating set plays an important role in power management.

In this paper we investigate the problem of minimizing the message overhead in routing the packets of data. Our key idea here is searching space for a route is reduced to nodes in the set and to reduce the message overhead by taking advantage of the dominating sets that facilitates the construction of virtual backbone network. By the effective use of dominating sets, a packet can be routed only by a minimal set of mobile nodes, thereby reducing routing message overhead

Our contribution in this paper is to analyze the centralized algorithm called Guha Khuller's to construct a virtual backbone network for the MANETs. The performance analysis shows that routing using dominating sets with the help of AODV protocol significantly increases the routing performance, compared to normal routing with AODV.


A. Routing and Dominating sets in Mobile Ad Hoc Networks

Ivan Stojmenovic1,Mark Russell and Bosko Vukojevic in their paper [6] propose to use depth first search (DFS) method for routing decisions. It is the first localized algorithm that guarantees delivery for (connected) wireless networks modeled by arbitrary graphs, including inaccurate location information.

Jie Wu and Hailan Li in their work [ 7] propose that routing based on a connected dominating set is a frequently used approach, where the searching space for a route is reduced to nodes in the set.. In this paper, they propose a simple and efficient distributed algorithm for calculating connected dominating set in ad-hoc wireless networks, where connections of nodes are determined by their geographical distances.

Jie Wu , Mihaela Cardei , Fei Dai , Shuhui Yang in their paper [8] proposed a notion of an extended dominating set where each node in an ad hoc network is covered by either a dominating neighbor or several 2-hop dominating neighbors. This work is motivated by cooperative communication in ad hoc networks ,whereby transmitting independent copies of a packet generates diversity and combats the effects of fading.

Bo Han and Weijia Jia in their work [3] proposed a novel distributed algorithm for connected dominating set (CDS) formation in wireless ad hoc networks with time and message complexity O(n). This Area algorithm partitions the nodes into different areas and selectively connects two dominators that are two or three hops away.

Anand Prakash RuhiI, D.K. Lobiya and Ivan Stojmenovic in their work [1] applied dominant pruning dominating set in VD-GEDIR, CH-MFR, K-DIR, LAK, and DREAM algorithms in mobile ad hoc environment. The results show that the flooding ratio has been significantly reduced without influencing the success rate and hop counts after applying the dominating set.

Ankur Jain Arobinda Gupta in their work [2] present a distributed self-stabilizing algorithm for finding a connected dominating set of a graph. Starting from an arbitrary initial state, the algorithm finds a connected dominating set in O (N) time, where N is the number of nodes. They also show detailed simulation results to indicate that in practice, the algorithm finds small-sized connected dominating sets in a short time.

Bonam Kim, Junmo Yang, Dong Zhou, and Min-Te Sun in their work [5] present two Timer-based Energy aware Connected Dominating Set Protocols. Their protocols extend the Mac-layer Timer-based Connected Dominating Set protocol (MTCDS) so that the energy level at each node is taken into account when constructing the CDS.

Bo Han, HaoHuan Fu, Lidong Lin and Weijia Jia in their work [3] propose a simple and efficient distributed algorithm for constructing a connected dominating set in wireless ad hoc networks with time complexity O(n) and message complexity O(nlog n) respectively.

Jie Wu in his work [9] extend dominating-set-based routing to networks with unidirectional links. Specifically, an efficient localized algorithm for determining a dominating and absorbant set of vertices (mobile hosts) is given and this set can be easily updated when the network topology changes dynamically.

Jie Wu , Ming Gaol, and Ivan Stojmen vic in their work [10] propose that efficient routing among a set of mobile hosts (also called nodes) is one of the most important functions in ad hoc wireless networks. Wu and Li proposed a simple and efficient distributed algorithm for calculating connected dominating set in ad hoc wireless networks, where connections of nodes are determined by geographical distances of nodes.


A .Sample Network









Fig 2 shows a sample network

B. Formation of Connected Dominating Sets for the sample network

Guha Khuller proposed a simple centralized algorithm for the formation of connected Dominating set in a given Mobile Ad hoc wireless network.


Algorithm : Guha Khuller's Algorithm

Step 1:

The algorithm begins by marking all vertices white

Step 2:

Algorithm selects the node with the maximal number of white neighbors

Step 3:

The selected vertex is marked black and its neighbors are marked gray.

Step 4:

The algorithm then iteratively scans the gray nodes and their white neighbors, and selects the gray node or the pair of nodes (a gray node and one of its white neighbors), whichever has the maximal number of white neighbors.

Step 5:

The selected node or the selected pair of nodes are marked black, with their white neighbors marked gray

Step 6:

Once all of the vertices are marked gray or black, the algorithm terminates. All the black nodes form a connected dominating set

























Fig.3. shows Dominating Set selection at each iteration

Initially, either node 2, or 4, or 6 could be marked since they have maximal degree. Node 6 is arbitrarily picked from these candidates and marked black. All its neighbors are then marked gray. We now consider the gray nodes 4, 5, 7 and the pair of gray and white nodes (3, 4). Of all these, the pair (3, 4) covers the most number of white neighbors. So we mark both 3 and 4 black. Finally, we consider the gray node 2 and the pairs (2, 0) and (2, 1). All these candidates have the same number of white neighbors. Therefore the single node 2 is selected. Now all the nodes are either black or gray, and the set of nodes in black {2, 4, 6} forms a CDS.

C.Simulation setup

The network simulator ns2 is used for the experiments

Parameters used during simulations



Simulation Time


Number of nodes


Environment size

700*700 m

Traffic type

Constant Bit Rate

Routing Protocol


D .Performance Metrics

The performance is evaluated based on the following metrics.

(i) Throughput - Throughput measures the rate at which a packet is received at its destination

(ii) Mobility- To move around within a broad coverage area and still be connected to the network.

(ii) Overhead- Additional information sent to aid in delivery of the actual data


(i) Screenshot : 50 Nodes topology with Dominating sets

Fig. 4 shows a 50 node topology with Dominating Sets

(ii) Performance Evaluation

We have shown through experimental results our proposals fit our objective which was to improve the performance of routing with dominating sets.

(a) Mobility:

Fig 5.shows comparison of routing overhead with and without Dominating sets considering mobility of nodes

Fig 6.shows comparison of Throughput with and without Dominating sets considering mobility of nodes

(b) No mobility:

Fig 7.shows comparison of routing overhead with and without Dominating sets without considering mobility of nodes

Fig 8.shows comparison of throughput with and without Dominating sets without considering mobility of nodes

The results show that the routing overhead is considerably reduced and throughput is improved by using Dominating sets for routing in Mobile Ad hoc networks. Thus the performance of routing is improved with the help of Dominating sets in Mobile Ad hoc Networks.


In this paper we proposed a routing methodology for mobile Ad hoc networks using dominating set. We have chosen a centralized algorithm called Guha Khuller's algorithm to find dominating set in a Mobile Ad Hoc Network. Routing based on a Connected Dominating Set is a promising-approach, where the searching space for a route is reduced to nodes in the set. We performed routing with the help of dominating sets using AODV protocol. We measured the routing performance with that of normal routing with AODV protocol. The simulation results show that with dominating sets the mobile routers are limited to dominating sets and routing performance is increased. We also analyzed many parameters such as latency, packet delivery ratio, throughput, overhead, mobility.

In the future we would also like to investigate the performance of a distributed algorithm and comparing it with its centralized counterpart .Our future work will focus on more in-depth simulation under different settings.