Cluster based routing protocol 1

Guided By :
Ms. Nibedita Jagadev
Assistant Professor
Dept. of CSE

Introduction
• What are MANETs ?
• Features of MANETs
Routing Protocols
Cluster Based Routing Protocol
• Concept of Clustering
• Cluster Formation
Mechanisms in CBRP
• Routing Process
• Route Discovery
• Route Reply
• Route Error Detection
• Local Route Repair
Features Of CBRP
Conclusion
References

Routing
Protocols in
MANETs
Proactive
Routing
Reactive
Routing
Hybrid
Routing
 Presence of
Updated Routes in
the Routing Table.
 Ex : DSDV
 On-demand
Discovery of
Routes.
 Ex : AODV
 Uses the features
of both proactive
& reactive routing
 Ex : ZRP

 Clustering is a process that divides the network into
interconnected sub-structures called clusters.
 Each cluster has a cluster-head as a coordinator within the
sub-structure, which acts as a medium for data transfer
between the nodes.
 Cluster heads communicate with each other by using
gateway nodes.
 The Gateway node has two or more cluster heads as its
neighbors or— when the clusters are disjoint—at least one
cluster head and another gateway node.
Cluster Based Routing Protocol

Figure 1 : Different States in which a Node can Exist

• A node elects itself as the cluster head if
it has the lowest/highest ID in its
neighborhood. (Lowest-Id Heuristic)
Identifier-
based
Clustering
• The node, which has the most neighbor
nodes, is elected as the cluster head.
(Highest Degree Heuristic)
Connectivity
-based
Clustering
Cluster formation takes place using two mechanisms :

 CBRP uses two data structures to support the routing
process:
1) The Cluster Adjacency Table (CAT) - The CAT stores
information about neighboring clusters, i.e. whether the
links are bi-directional or unidirectional.
2) The Two-Hop Topology Database - The two-hop
topology database contains all nodes that are at most two
hops away.
 The routing process works in two steps:
1) Discovery of a route from a source node ‘S’ to a
destination node ‘D’.
2) Actual transmission of the data packets.

• In CBRP only cluster heads are ﬂooded with route request
package (RREQ). Gateway nodes receive the RREQs and
forward them to the next cluster head.
• Initially, the source node ‘S’ broadcasts a RREQ with unique
ID containing the address of the destination node ‘D’.
• When a node ‘N’ receives a RREQ it does the following:
a) If ‘N’ is Gateway Node -> Forwards the RREQ to the
next Cluster head ‘C’.
b) If ‘N’ is Cluster Head -> Checks whether ‘D’ is a
neighbor or is two-hops away from it. It then sends the
RREQ to ‘D’. Else broadcasts it to the neighboring
Cluster head.

[3]
[3,1,8,11]
1
2
4
5
6 7
8
9
10
11
3 (S)
11 (D)
[3,1]
[3,1,6]
[3,1,8]
Example :
Source Node-[3]
Destination Node-[11]
Route Discovered- [3,1,8,11]

C. Route Reply
If the RREQ reaches the destination node ‘D’, it contains
the path called as “loose source route”, [S,C1,C2,...,Ck,D].
‘D’ sends a Route Reply message (RREP) back to S using
the reversed loose source route [D, Ck,...,C1,S], i.e. RREP
is sent back to source along reversed loose source route of
cluster heads.
Every time a cluster head receives this RREP it computes
a strict source route, which then consists only of nodes that
form the shortest path within each cluster.

Example :
Source Node-[3]
Loose Source Route of
RREP- [11,8,1,3]
Strict Source Route of
RREP- [11,9,4,3]
1
2
4
5 6
7
8
9
10
3
11
3 (S)
11 (D)
[11][11,9]
[11,9,4]
[11,9,4,3]

Example :
Source Node-[3]
Loose Source Route of
RREP- [11,8,1,3]
Strict Source Route of
RREP- [11,9,4,3]
1
2
4
5 6
7
8
9
10
3
11
3 (S)
11 (D)

D. Route Error Detection
After determining the route, source routing is used for actual
packet transmission.
A forwarding node sends a Route Error Message (ERR) to
packet source if the next hop in source route is unreachable.
1
2
4
5 6
7
8
9
10
3
11
3 (S)
11 (D)
Example:
Source route header of data
packet: [3,4,9,11]
Route error (ERR)
down link: [9->11]

E. Local Route Repair
 Objective
 Increase Packet Delivery Ratio.
 Save Route Rediscovery flooding traffic.
 Reduce overall route acquisition delay.
 A forwarding node repairs a broken route using its 2-
hop-topology information and then modifies the source
route header accordingly.
 Destination node sends a Gratuitous Route Reply to
inform source of the modified route.

1
2
4
5 6
7
8
9
10
3
11
3 (S)
11 (D)
Example :
Source route header of Data
Packet : [3,4,9,11]
Route error (ERR)
down link : [9->11]

1
2
4
5 6
7
8
9
10
3
11
3 (S)
11 (D)
Example :
Packet : [3,4,9,11]
Modified source route:
[3,4,9,8,11]

1
2
4
5 6
7
8
9
10
3
11
3 (S)
11 (D)
Example :
Packet : [3,4,9,11]
Gratuitous route reply :
[3,4,9,8,11]

Cluster based routing protocol 1

Recommended

More Related Content

What's hot (20)

Similar to Cluster based routing protocol 1 (20)

Recently uploaded (20)

Cluster based routing protocol 1