Hierarchical grid location management for large wireless Ad hoc networks

Abstract

Recently, a new family of protocols has been introduced for large scale ad hoc networks that make use of the approximate location of nodes in the network for geographic routing. Location management plays an important role in such protocols, and in this paper, we propose a deterministic hierachical scheme for managing the location information of nodes, and analyze the cost of such a scheme via probabilistic means and simulations. We find that the cost of hierarchical location management has an asymptotic overhead cost of O(ν N log 2 N) for location registration, which is asymptotically lower than the location management overhead in protocols described in literature, and thus scales well with the increase in the number of nodes in the network.