Two scalable location service protocols for wireless ad hoc networks

We present two location service protocols, viz., the hierarchical location service protocol and the on-demand location service protocol, to track the position of mobile nodes in a wireless ad hoc network. The hierarchical location service uses a location-based hierarchy to maintain the location of nodes in the network, whereas the on-demand location service uses a unicast-based network probing, unlike flooding, to obtain the position of a node on-demand. In the unicast-based network probing, a location query for a node is unicast to nodes that are closer to a few fixed positions in the network. For a given network size, the number of such positions remains constant. Both the location service protocols use a heuristic greedy forwarding protocol, called the angular routing protocol, to circumvent dead ends, and to route packets beyond one hop. We use a theoretical framework to show that both the location service protocols are asymptotically scalable with respect to the number of nodes in the network. Further, we present results from an extensive simulation study comparing the performance of the proposed on-demand location service protocol with LAR1 and a combination of GPSR-GLS. Simulations show that the on-demand location service along with angular routing protocol outperforms the LAR1 and GPSR-GLS protocol in terms of control overhead, percentage of packets delivered, and average hop count, for various network scenarios.