Efficient Hop ID based routing for sparse ad hoc networks

Routing in mobile ad hoc networks remains as a challenging problem given the limited wireless bandwidth, users' mobility and potentially large scale. Recently, there has been a thrust of research to address these problems, including on-demand routing [1-2], geographical routing [6-8], virtual coordinates [15], etc. In this paper, we focus on geographical routing, which was shown to achieve good scalability without flooding, but it usually requires location information and can suffer from the severe dead end problem especially in sparse networks. Specifically, we propose a new Hop ID based routing protocol, which does not require any location information, yet achieves comparable performance with the shortest path routing. In addition, we design efficient algorithms for setting up the system and adapt to the node mobility quickly, and can effectively route out of dead ends. The extensive analysis and simulation show that the Hop ID based routing achieves efficient routing for mobile ad hoc networks with various density, irregular topologies and obstacles. © 2005 IEEE