Age Matters: Efficient Route Discovery in Mobile Ad Hoc Networks Using Encounter Ages

We propose FResher Encounter SearcH (FRESH), a simple algorithm for efficient route discovery in mobile ad hoc networks. Nodes keep a record of their most recent encounter times with all other nodes. Instead of searching for the destination, the source node searches for any intermediate node that encountered the destination {\em more recently than did the source node itself}. The intermediate node then searches for a node that encountered the destination yet more recently, and the procedure iterates until the destination is reached. Therefore, FRESH replaces the single network-wide search of current proposals with a succession of smaller searches, resulting in a cheaper route discovery. Routes obtained are loop-free. The performance of such a scheme will depend on the nodes' mobility processes. Under standard mobility processes our simulations show that route discovery cost can be decreased by an order of magnitude, a significant gain given that route discovery is a major source of routing overhead in ad hoc networks.

Published in:
Proc ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHOC), 257-266
Presented at:
The ACM International Symposium on Mobile Ad Hoc Networking and Computing, Annapolis, Maryland, USA, 1-3 June 2003

Note: The status of this file is: Anyone

 Record created 2005-04-18, last modified 2020-10-28

mobihoc03 - Download fulltextPDF
GrossglauserV03 - Download fulltextPS
Rate this document:

Rate this document:
(Not yet reviewed)