Research On Compound Routing Scheme Based On Quadtree Coding For Routing Table Compression

Most existing routing schemes in wireless networks can be divided into two main groups:topology-based routing and position-based routing.Using topology-based rout-ing schemes,each network element selects optimal path which data packets are trans-ferred to various destinations.However,network elements have to hold large routing tables.The routing efficiency would be seriously impacted by the enormous size of the routing table.In position-based routing,the size of routing table can be reduced.In the greedy geographical algorithm,each node forwards the message to one of its neighbors that is geographically closest to the destination.Each node maintains small state.How-ever,it does not guarantee delivery of the message as the local minimum problem may happen.And they often choose a very long path for the traveling packets.Our HQLSR(Hierarchical Quadtree-Based Link State Routing)scheme can guar-antee delivery and bypass local minimums.HQLSR is a two-level link-state routing scheme based on quadtree addressing system,instead of using the network addresses.We first allocate addresses to nodes in different geographical locations using quadtree structure,and then converge nodes which meet the connectivity constraint into zone according to actual link relationship of nodes.We adopt different routing algorithms intrazone and interzone,and construct a two-level routing architecture.Within each zone,we employ the sibling routing technique to shrink intrazone routing table dramat-ically.Between zones,the shortest path algorithm is used to find the shortest path in terms of zone hops.Although it may leave the globally optimal path to compress the routing table,it improves path stretch in comparison with geographical routing schemes.In the cases where the distribution of nodes is not uniform and the distribution area is relatively narrow,the largest length of nodes quadtree addresses will be very long and convergence effect is not ideal.Therefore,we propose a rectangular addressing technique RGA to replace quadtree addressing technique which reduce the maximum addressing length.Since the length of the node address in the packet header and routing table is determined by the maximum addressing length,we can reduce the size of the packet and the size of the routing table by reducing the maximum addressing length.We use a flexible convergence way to improve the aggregation effect to achieve better compression.Similarly,we apply the rectangular addressing technique to the hierar-chical routing mechanism then we present the improved compound routing mechanism HRAR.The expermental results show that the HRAR routing mechanism can achieve better compression effect and lower path stretch.