 |
 |
 |
 |
| |
|
|
|
|
SECAN-Lab Home News Projects SECAN-LAB Mesh Sequencer U-2010 NARTUS EFIPSANS IRMA SECRICOM The Group Members Publications Theses Teaching Presentations Topics Mobile Computing Ad-Hoc Networks Ad-Hoc Protocols Mesh Computing Trust Related Stuff L-101 Laboratory Systems AS28 Systems 802.11 Network Simulator Internships Conferences Publications Standards Projects Links Partners OSTN Miscellaneous Contact About Job Opportunities Search |
Cluster Based Routing Protocol
CBRP (Cluster Based Routing Protocol) is an on-demand routing protocol, where the nodes are divided into clusters!
The algorithmThe following algorithm is used to form the clusters!When an node comes up, it has the "undecided" state! The first action of this node is to start a timer and broadcasts a HELLO message! When a cluster-head receives this HELLO message, it replies immediately with a triggered HELLO message. After that, when the node receives this answer, it will change his state into the "member" state. But when the node gets no message from any cluster-head, it makes itself as cluster-head, but only, when it has bi-directional link to one or more neighbours! Otherwise, when it has no link to any other node, it stays in the "undecided" state and repeats the procedure with sending an HELLO message again! Cluster-heads are changed as infrequently as possible. The neighbour tableEach node of an ad-hoc network maintains a neighbour table.
Example of a neighbour table In this table we find in first column the ID of the neighbour. In the second column we find the status of this node, is the node a cluster-head or only a member and then in the third column, we find the status of the link between the nodes, uni- or bi-directional. E cluster-head has not only the information’s about the members of its cluster in the table, but it maintains also a cluster adjacency table that contains information about the neighbouring clusters. In this table is the gateway through which the neighbour cluster can be reached saved, and also the ID of the cluster-head. How a source finds a way to the destinationNode S (source) has to send data to node D (destination). S sends route requests to all the neighbouring cluster-heads, and only to the cluster-heads. When a cluster-head receives the route request, it checks if the node D is in his cluster. If this is the case, the cluster-head sends the request directly to the destination. But when D isn't in the cluster, it sends the route request to all the adjacent cluster-heads. All cluster-head saves his address in the packet, so when a cluster-head receives a route request where his address is saved in the packet, it discards this packet. When the route request packet arrives at the destination, D replies back with the route that had been recorded in the request packet. When the source S doesn't receive a reply from the destination within a time period, it tries to send a route request again. In the Cluster Based Routing Protocol, routing is done using source routing. But this protocol uses also route shortening. When a node receives the reply of the destination to the source, it tries to find the farthest node in the route that is its neighbour. With this principle the route between source and destination can be reduced. On the following figure you can see an ad-hoc network, separated in the different cluster with all the components:  All the refences: Misra1999 Other references, but not used for this page: Mingliang1998 "Cluster Based Routing Protocol" is mentioned on: Ad-Hoc Protocols (Classification) | Ad-Hoc Workshop Winter 04/05 (Termine) |