Age matters: efficient route discovery in mobile ad hoc networks using encounter ages

By H. Dubois-Ferrière, Matthias Grossglauser, Martin Vetterli. ACM Interational Symposium on Mobile Ad Hoc Networking and Computing, 2003

484 citations recorded by the source corpus.

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 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.

Subfields: Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/999e3d48cc36e49de2a700428c7b5fd16590282d

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

Citations in the corpus

PeopleRank: Social Opportunistic Forwarding (2010, background): “All these algorithms are well-known in the literature, they use a local information to decide whether to forward a message when node i meets node j. • Last Contact [8]: Node i forwards messages to node j if j has contacted any other node more recently than node i. • Destination Last contact [8]: Nod”
Intelligent fluid infrastructure for embedded networks (2004, methodology): “An algorithm for routing data among mobile users has been suggested in [4], where data is forwarded to nodes which have”
Probabilistic routing in intermittently connected networks (2003, background): “It is because of similar reasons that the approach taken by Dubois-Ferriere et al. to improve route discovery works [ 13 ].”
Efficient Routing in Intermittently Connected Mobile Networks: The Multiple-Copy Case (2008, methodology): “Further, we use a “transitivity function” for timer values (see details in [17]), in order to diffuse this indirect location information much faster than regular last encounter based schemes [27].”
Routing in intermittently connected mobile ad hoc networks and delay tolerant networks: overview and challenges (2006, methodology): “To accommodate the dynamic topology of mobile ad hoc networks, an abundance of routing protocols have recently been proposed, such as OLSR [1], AODV [2], DSR [3], LAR [4], EASE [5, 6 ], ODMRP [7], and many others [8, 9]. For all these routing protocols, it is implicitly assumed that the network is ”
A message ferrying approach for data delivery in sparse mobile ad hoc networks (2004, background): “There is also other work on exploiting mobility for security [7], location [14] and routing [10, 32].”
Multiple Controlled Mobile Elements (Data Mules) for Data Collection in Sensor Networks (2005, methodology): “An algorithm for routing data among randomly mobile users was suggested in [18] where data is forwarded to nodes which have recently encountered the intended destination node.”
Single-copy routing in intermittently connected mobile networks (2004, methodology): “In a number of other works, all nodes are assumed to be mobile and algorithms to transfer messages from any node to any other node are sought for [1], [2], [9], [10], [11], [18], [19], [20].”
Security and Cooperation in Wireless Networks (2007, background): “Another interesting approach for position-based routing that does not require a location service is called Last Encounter Routing and described in [123].”
Spray and Focus: Efficient Mobility-Assisted Routing for Heterogeneous and Correlated Mobility (2007, methodology): “However, timers also quickly become poorer indicators of proximity as their value increases (this is commonly referred to as the “distance effect” [34]).”
SECTOR: secure tracking of node encounters in multi-hop wireless networks (2003, methodology): “6.3 Security of Last Encounter Routing In [10], Dubois-Ferriere, Grossglauser and Vetterli present an approach called FRESH, for e.cient route discovery in mobile ad hoc networks using encounter ages.”
Mobility helps security in ad hoc networks (2003, unknown): “A more recent work by Dubois-Ferriere, Grossglauser and Vetterli [10] shows that if nodes keep track of their encounters, route discovery can be performed at a much lower cost than with traditional broadcast search methods.”
Social network analysis for routing in disconnected delay-tolerant MANETs (2007, background): “[6] and [13] use the so-called ‘time elapsed since last encounter’ or the ‘last encounter age’ to route messages to destinations.”
Impact of Human Mobility on Opportunistic Forwarding Algorithms (2007, background): “It also necessitates t o design a forwarding algorithm that differentiate between nodes; some schemes of that type have been only recently proposed [17], [18], [19].”
Controllably mobile infrastructure for low energy embedded networks (2006, background): “A problem with this approach, however, is that the nodes closer to the base station relay data from nodes that are farther away.”