Abstract:

Mobile

Ad hoc network is a collection of mobile hosts which is self organized, self

maintained network. It dynamically forms a wireless network without any

backbone infrastructure and centralized administration. Due to the lack of fixed

infrastructure the control overhead increases in the network. The aim of the

paper is to reduce the control overhead by using the domination set based

routing. The nodes which use to connect all the other nodes in the network are

called dominating nodes, and the set of dominating nodes creates domination

set. This paper proposes a new approach for finding the route and reducing the

reroute establishment delay and increasing the packet delivery ratio. The

efficiency of the method is demonstrated through simulation study using NS2.

1.

Introduction

The evolution of mobile ad hoc networks

(MANET) is growing rapidly. The nodes in the MANET are self sufficient and each

node is act as either router or source. There is no central controller in MANET

and the control is distributed among the nodes. Topology of the network is

dynamic and the topology change is more frequent. Conventional routing

algorithms are not suitable for MANET. There are many routing algorithms

proposed for MANET timely. Mainly the routing algorithms are categorized into

two i.e. proactive and reactive 7. Proactive algorithms are the extension of

wired routing protocols. In proactive routing algorithm all the nodes keep the

routing information in the routing table at the time of network initialization.

All nodes exchange this information periodically with neighbors, which causes very

high routing overhead. In the reactive routing protocol, the route is decided

only when a node wants to send some data. In this case, there is some delay

occurs for route establishment since the routing information is not readily

available; many control packets are used for finding the route. The control packet

also brings routing overhead in the network. As per study, it has been reported

that the reactive algorithms are more efficient than proactive ones 7. The

main constraints in MANET include high mobility, low bandwidth and low energy.

Due to the high mobility, frequent disconnections are more in MANET. In all

reactive algorithms, when the route is broken then the route re-establishment

process reduce the performance of the network by inducing more overhead.

This paper proposes a method to reduce

the reroute establishment delay and routing overhead by using the dominating

nodes in the network. Based on the study of Domination Based Routing, compared

the performance with all other well known algorithms, This clearly justifies

that the proposed work is more efficient in terms of packet delivery ratio,

control overhead and packet drop. In this method, initially all the dominating

nodes in the networks are identified. From this a domination set is created. A

set is a dominating set, if all the nodes in the network are either in the set

or the neighbors of the nodes in the set 2. The route is established through

the nodes in the domination set only. All nodes in the network can be reached

through the dominating nodes. When the route fails, it is easy to find the new

route by using the domination nodes. This ensures the re-route establishment

without any delay and overhead, thereby enhancing the routing performance, even

when the route breaks occurs.

The paper is structured as follows.

Section 2 gives the brief idea about how the domination set is calculated.

Section 3 describes the proposed domination based routing. Simulation study and

results is presented in Section 4 and the conclusion is given in section 5.

2.

calculation of Domination Set

Let G = (V;E) be a connected,

undirected, simple graph here V is the vertex set and E is the edge set. A set of vertices S in a graph

G is a dominating set if every vertex not in S is adjacent to at least

one vertex in S. The minimum number of vertices which dominates the graph G is

called minimum dominating set. A set

of vertices S is independent if

no two vertices in S are adjacent. A

connected dominating set (CDS) is a subset S of a graph G

such that S forms a dominating set and S is connected 1, 2.

Every node (vertex) in the network can

be reached through the domination nodes. An example of mobile ad hoc network is

shown in Fig. 1 and Fig. 2. with domination nodes N4, N7 and N9. There are

multiple minimum dominating set but the number of nodes in the set must be the

same in domination set. For same network Fig.1 and Fig. 2 shows two different

domination set.

Fig. 1 A typical Mobile Ad hoc Network with

domination node {N4,N7,N9}

Fig. 2 A typical Mobile Ad hoc Network with

domination node {N4,N7,N10}

Algorithm

for finding domination set

The algorithm given below creates the

domination set by calculating the adjacency matrix and collecting the nodes

corresponding to the maximum connected node, from the row sum.

Node

(a);

If

(b is a neighbour)

{

Add

to neighbour list

Send

this list to its neighbours

}

If

(a is a neighbour of b) //Find

adjacency matrix

{

Set

adjab=1

else

Set

adjab=0

}

For

each row in adjacency matrix //calculate

the domination matrix

{

Calculate

the row sum in adjacency matrix

Find

the node with maximum degree

Append

this to ” d set”

If

any node is not connected to the nodes in the d set then add this also to the d

set

}

Fig.3

Route discovery through dominating nodes

3.

Domination Set Based Routing

The given algorithm first finds the

domination set. Then the path is established to the destination only through

the domination nodes. The nodes in the domination set connect all the nodes in

the network quickly. So it is easy to get the destination within a very short interval. Whenever

the route failure occurs then the corresponding domination node identifies the

problem and fixes it locally. It can reach the destination through other nodes

if possible. Otherwise it will flood the route failure report to the other

domination nodes. In the initial phase, the domination nodes are determined

form the adjacency matrix. For that each node determines its neighbour node by

sending the HELLO packet. After determining the neighbours, the neighbouring

list is sent to the adjacent nodes and each node prepares the adjacency matrix.

From this matrix, it is easy to find out the dominating nodes and finally

domination set by using the above mentioned algorithm.

In Fig. 3. the domination set is {N4, N7,

N9}. N1 is the source and N11 is the destination nodes. N11 can be reached from

N1 through N4, N7 and N9. In the initial route discovery process each node

tries to connect the domination node from the source node. The route to

destination is always through the dominating nodes even if the shortest link

exists. In the initial stage, the cost of establishing the route is higher than

the other routing algorithms; but this is very useful in the dynamic networks,

because mobile ad hoc network is highly dynamic in nature. So this is helpful

for finding the alternate route easily. In the given example if link N10-N11 is

broken, then need not to worry about the link because still we reach all the

nodes easily. Suppose we have domination set {N4,N7,N11} In fig. 3 if the link N10-N11

is broken in fig. 2 then the node N9 can easily set up the connection N9-N11 to the destination.

4.

Results

The performance evaluation of

the proposed algorithm has been done

by using simulation tool NS2.The performance of DBR is

compared with the existing algorithms AODV and DSR. The metrics used for performance analysis

were packet delivery ratio, number of packets dropped and the routing

overhead It has been observed that DBR perform better than AODV and DSR. The

simulation parameters are listed in the Table. 1