6.6 Strict Hierarchical Routing

Similar to quasihierarchical routing, strict hierarchical routing helps routing objectives, and provides communications connectivity in mobile wireless networks at the expense of increased processing cost. The forwarding tables help to identify the clusters and boundaries enclosing both source and destination nodes. As illustrated in Figure 6.14, where the number of cluster levels is k = 3, the data packets are forwarded from s₀ to the boundary of s_l, then to level 1 clusters until they reach the boundary of s₂, then to the boundary of s_k-₁. The packets hop then on k - 1 level clusters until they reach the boundary of d_k-₁. The packets then hop to cluster levels k - 2, then k - 1, around the destination node until they reach the destination node d₀.

Building the clustering and routing tables at the cluster head of cluster c at level j (0 ≤ j < m) involves the following steps:

Calculation of the average cost of cluster c.
Determination if cluster c is at the boundary of a higher level cluster j + 1.
If 2 is true, determination of which clusters at level i, i = j + 1 are neighbors of c, these clusters at level j + 1 are directly linked to c and together with c lie within parent level j + 2 cluster. However, i can be larger than j + 1 if c happens to lie on the boundary of a higher level parent cluster.
Each cluster head within clustering level j relays the cost and neighbor information in 1 to 3 to cluster heads of neighboring clusters of level j, by which each cluster head would be able to compute its cluster minimum route cost to any level j cluster and the identity of the next cluster to take to reach another level j cluster (all within the next parent level j + 1).
In the sequel and once these pieces of information in 1 to 4 are exchanged, all cluster heads would know also the identity of level j clusters lying on the boundary of level j + 1, and the clusters these boundary clusters are linked to, as well as least cost routing information.

Strict clustering is not as accurate in calculating minimum routing cost as quasi clustering, because the strict clustering table contains mainly costs between clusters of various levels rather than between actual nodes. The details of the costs of various links of a certain cluster are averaged out.

This coarse granularity of strict clustering is a mixed blessing in the sense of providing less-frequent cost advertisement and hence savings in the precious radio channel capacity (cost is averaged over many links before being relayed to neighbors), while yielding higher routing cost by the same mechanism.

Clustering and routing tables in strict hierarchical routing may have the same number of entries as in quasihierarchical routing. However, the processing time to find the route to a certain node in strict clustering costs 2m - 1⁸ investigations of table entries, while in quasi clustering only one table entry may be consulted.

Routes computed based on strict routing are generally longer than their quasi routing counterparts, which are longer than routes based on nonhierarchical routing techniques. ^[22]

^[22]Lauer, G.S., Hierarchical routing design for SURAN, IEEE International Communications Conference (ICC), June 1986, pp. 93–102.