4 Clustering/hierarchical routing protocols

A large network can be clustered so that it contains multiple sections or zones. Traffic between clusters is routed by clusterheads. This has as advantage that the routing protocol does not have to deal with all nodes, just the clusterheads. In large networks, superclusters can be made.

Packets travel from cluster to supercluster and down again, as in a tree. Therefore, the routing protocol used is commonly named hierarchical routing.

When clusters are in place, routing is efficient and scalable because routing information is only spread within the cluster, reducing overhead. However, creating clusters with the right properties is a problem of its own.

Selecting a clusterhead within a cluster is usually done by making the nodes with the lowest MAC address a clusterhead. This algorithm does not take into account properties which may affect the quality of the clusterhead, such as speed, uptime and battery power remaining.

Another proposed method for selecting a clusterhead is selecting the node which has the most connections, but this proved to create a bottleneck at the clusterhead.

Because there is not a clear way to cluster nodes or select a clusterhead, these protocols are not ready for use in a large network.

4.1 Hierarchical State Routing

HSR, proposed in [Iwa99], is a typical example of a hierarchical routing protocol. HSR maintains a hierarchical topology, where elected clusterheads at the lowest level become members of the next higher level. On the higher level, superclusters are formed, and so on. Nodes which want to communicate to a node outside of their cluster ask their clusterhead to forward their packet to the next level, until a clusterhead of the other node is in the same cluster. The packet then travels down to the destination node.

Furthermore, HSR proposes to cluster nodes in a logical way instead of in a geological way: members of the same company or in the same battlegroup are clustered together, assuming they will communicate much within the logical cluster.

HSR does not specify how a cluster is to be formed.

4.2 Cluster Based Routing Protocol

CBRP, which is described in [Jia02], uses source routing in a clustered network. Nodes periodically broadcast HELLO messages. When a node enters the network, it waits until it receives a HELLO message from a clusterhead. When it does not receive such a message in a specified time, it becomes a clusterhead itself.

Members of a cluster are always within reach of exactly one clusterhead. When two clusterhead can connect to each other, one of them becomes a member of the other cluster.

When a member of cluster A receives an HELLO message from a member in cluster B, it reports to its clusterhead that cluster A neighbours cluster B, and that this member can be used as a gateway to cluster B.

When a node wants to know the route to another node, it broadcasts a route request message. Although this message is flooded over the entire network, only the clusterheads will handle route requests. When a member receives a route request, it directly forwards it to its clusterhead. The clusterhead appends its own address to the route request message and forwards it to the neighbouring clusters. When the route request message ends up at the destination, it contains a list of clusterheads and gateways which form a route from the source to the destination, much like in DSR.

CBRP is based on simple flooding. However, because only the clusterheads have to handle messages, overall overhead is reduced. CBRP will particularly perform well in small, highly connected networks: when a cluster has many members, the clusterhead does the work for all these members. In big, sparse networks, flooding the route requests may be a bad approach. Another disadvantage is that that the load is poorly balanced: the clusterhead has to do most of the work.