Cluster-Head Gateway Switch Routing Protocol

CGSR

The Clusterhead Gateway Switch Routing (CGSR) uses DSDV as an underlying protocol.

General

Mobile nodes are partioned into clusters and a clusterhead is elected using a distributed algorithm. All nodes in the communication range of the clusterhead belong to its cluster. A node that is in the communication range of two or more clusterheads is called a gateway node.

CGSR uses a Least Cluster Change (LCC) clustering algorithm. A clusterhead change occurs only when two clusterheads come into one cluster or one of the nodes moves out of the range of all the clusterheads.

A clusterhead is able to control a group of ad-hoc hosts, this means that it is in charge of broadcasting within the cluster, forwarding messages and dynamic channel scheduling.

Each node maintains 2 tables:

• a cluster member table, containing the cluster head for each destination node
• a DV-routing table, containing the next hop to the destination.

The cluster member table is broadcasted periodically. A node will update the entries in its cluster member table on receiving a new one from its neighbors. Sequence numbers are used as in DSDV.

Routing in CGSR

If a node has to route a packet, it finds the nearest clusterhead along the route to the destination according to the cluster member table and the routing table. Then it will consult its routing table to find the next hop in order to reach the clusterhead selected above and transmits the packet to that node.

Thus, the routing principle looks as follows:

1. Lookup of the clusterhead of the destination node
2. Lookup of next hop
3. Packet send to destination
4. Destination clusterhead delivers packet

First, the source has to transmit the packet to its clusterhead. Then, this clusterhead sends the packet to the gateway node that connects this clusterhead and the next clusterhead along the route to the destination. The gateway sends the packet to the next clusterhead. This will go on until the destination clusterhead is reached. The destination clusterhead then transmits the packet to the destination node.



Routing in CSGR is more effective than DSDV because it is done through the clusterheads and gateways.

Allocate Wireless Channels

The clustering method provides an effective way to allocate wireless channels among different clusters. It´s possible to enhance spatial reuse amongst clusters by using different spreading codes CDMA

Token approach

A token approach is used within a cluster. The goal consists of giving priority to clusterheads in order to maximize channel utilization and minimize delay.

A clusterhead should get more chances to transmit as it is in charge of broadcasting within the cluster and of forwarding packets between nodes.

The channel access scheme looks as follows:

1. Initially, the clusterhead will get the permission token. It transmits any messages it has in its transmission queue.
2. The clusterhead gives the token to one of its neighbors according to a scheduling algorithm.
3. That node returns the token to its clusterhead after it has transmitted its messages, if there are any.
4. These steps will be repeated.

Priority Token Scheduling (CGSR+PTS) allows to give higher priority to neighbor nodes from which a packet was recently received.The clusterhead handles the permission token to the upstream neighbor (could be a gateway) in a way that the packets will be sent with least delay. Initially, every neighbor of a clusterhead has the same priority to receive the token. When a packet is transmitted by a node, the clusterhead increases the priority of that node. When the token returns from an empty queue at a neighbor, the clusterhead will decreases the node´s priority. PTS helps to forward high
priority traffics with least delay, in order to give more transmission opportunities for real time and multimedia sources.

The next step is gateway code scheduling (CGSR+PTS+GCS), in order to give more priority to the upstream clusterhead of a gateway. One has to note that a gateway must switch its code to hear the upstream / downstream clusterhead, thus losing time.

A final step consists of path reserving (CGSR+PTS+GCS+PR). This keeps a path more stable by reserving it until it´s disconnected (or a pseudo link appears, see CDMA)

The mentioned token approach has some known weaknesses. Only one node, which gets the permission token, can access the channel with an assigned code (CDMA) for each cluster.
In some cases the permission token may be lost:

• The node with the permission token moves outside the cluster.
• The host is a gateway (belonging to more than one cluster). It might be tuned to a different code (i.e. different cluster), thus missing the permission token.

In order to overcome the listed problems, the clusterhead reissues the permission token after a timeout. One could avoid gateway problems by using gateways that are able to simultaneously communicate over 2 interfaces.

Conclusion

Routing in CSGR is more effective than in other DV protocols, meaning that the routing table size is reduced by only keeping one entry for one whole destination cluster. This reduces the broadcast packet size aswell. The least cluster change (LCC) algorithm provides the stablest cluster structure for grouping mobile nodes and allocating radio channel codes. Clusterhead controlled token protocol is efficient for channel access within a cluster and packet forwarding. Packets are delivered efficiently in CGSR.Heuristic token scheduling, gateway code scheduling and path reservation speed up packet delivery along multihop paths, this makes CGSR capable of transmitting multimedia traffic.

But the performance is degraded by the following facts:
The selection of the clusterheads may cause complexity and overhead, as it is difficult to maintain the cluster structure in mobile environment.

Also, there are traffic bottleneck and single point failures at the clusterheads and gateways.(higher computation and communication load than other nodes, path length increases also)
CGSR is instable at high mobility when the rate of change of clusterheads is high.

All this would degrade the scalability of the network, which is highly undesirable.

References

[Chiang1997] Original paper
[Chowdavarapu2000] Pictures

"Cluster-Head Gateway Switch Routing Protocol" is mentioned on: Ad-Hoc Protocols (Classification) | Ad-Hoc Protocols (History) | Ad-Hoc Workshop Winter 04/05 (Termine)