Hop ID: A virtual coordinate-based routing for sparse mobile ad hoc networks

Routing in wireless communication systems such as ad hoc networks remains a challenging problem given the limited wireless bandwidth, users' mobility, and potentially large scale. Recently, a thrust of research has addressed these problems - the on-demand routing, geographical routing, and virtual coordinates. In this paper, we focus on geographical routing that has been shown to achieve good scalability without flooding; however, this usually requires the availability of location Information and can suffer from poor routing performance and severe dead end problems, especially in sparse networks. Specifically, we propose a new Hop ID routing scheme, which is a virtual coordinate-based routing protocol and does not require any location information. This achieves excellent routing performance comparable with that obtained by the shortest path routing schemes. 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. 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.