A Hierarchical Quadtree-Based Link State Routing Scheme for Routing Table Compression

There are two main families of routing schemes: topology-based routing and position-based routing. Topology-based routing can always transmit packets along the shortest path, but the overhead of storage and computation is too high due to huge routing tables. In contrast, position-based routing (also called geographic routing) makes forwarding decisions using geographical location information, thus only maintains a small routing state. But geographic routing might be very inefficient in route selection. Moreover, it may encounter local minimum problem which affects message delivery. In this paper, combining the advantages of topology-based and position-based routing schemes, we propose a novel hierarchical quadtree-based link state routing scheme, called HQLSR. It allocates addresses to all participating nodes based on the structure of quadtree. It makes good use of the convergence of address space to reduce the routing table size. Simulation results show that our scheme compresses routing tables effectively while stretches the path slightly.