Optimal tradeoffs for location-based routing in large-scale ad hoc networks

Existing location-based routing protocols are not versatile enough for a large-scale ad hoc environment to simultaneously meet all of the requirements of scalability, bandwidth efficiency, energy efficiency, and quality-of-service routing. To remedy this deficiency, we propose an optimal tradeoff approach that: 1) constructs a hybrid routing protocol by combining well-known location-update schemes (i.e., proactive location updates within nodes' local regions and a distributed location service), and 2) derives its optimal configuration, in terms of location-update thresholds (both distance- and time-based), to minimize the overall routing overhead. We also build a route-discovery scheme based on an Internet-like architecture, i.e., first querying the location of a destination, then applying a series of local-region routing until finding a complete route by aggregating the thus-found partial routes. To find the optimal thresholds for the hybrid protocol, we derive the costs associated with both location updates and route discovery as a function of location-update thresholds, assuming a random mobility model and a general distribution for route request arrivals. The problem of minimizing the total cost is then cast into a distributed optimization problem. We first prove that the total cost is a convex function of the thresholds, and then derive the optimal thresholds. Finally, we show, via simulation, that our analysis results indeed capture the real behavior.