Hierarchical geographic routing for wireless ad-hoc networks

Geographic routing is a well established solution for scaling in large wireless ad-hoc networks. A fundamental issue is forwarding packets around voids to reach destinations in networks with sparse topologies. All general known solutions need first to get into a dead end, at link level, to be able afterwards to apply a recovery algorithm. These techniques can lead to very inefficient forwarding paths. We propose a novel general approach, based on light weight connectivity maps, C-Maps, distributed among all the nodes in the network to obtain more efficient and robust paths. The main contribution of our method is the distributed Mercator protocol that builds these maps. Each node in this protocol builds and maintains its own C-Map that summarizes connectivity information of all the network around itself using hierarchical regions. This information is more precise from regions closer to the node. Nodes apply greedy forwarding and fare routing to the different hierarchical levels of connectivity information. Better paths are obtained with this behavior. Robustness is guaranteed by every node containing its C-Map. Our analytical and simulation work shows that the map state and the communication overhead grows logarithmically with the size of the network.