Routing in Mobile Networks through Encounter Histories

In this project, we explore efficient algorithms to route in large mobile wireless networks. The challenge in desinging such algorithms is twofold. First, algorithms have to compute efficient routes, close to the shortest (or most energy-efficient) path. Second, the algorithm should not incur excessive control overhead.

Last Encounter Routing (LER)

The fundamental observation underlying our work is that under most realistic mobility processes, the history of past encounters between nodes contains noisy, but nevertheless valuable information about the current network topology. This is important because encounter information can be collected very cheaply by nodes, and because, as our work shows, this information can be exploited to significantly reduce or eliminate control traffic in routing protocols.

We develop routing protocols that exploit this effect. The key idea is that each node maintains a table of encounters to other nodes. The precise form of this table depends on the context. For example, if nodes possess positioning information (e.g., through GPS or virtual embeddings), then this last encounter table records the time and location of encounter with other nodes.

A packet being routed towards a destination then carries some control information with it, and consults the encounter table in each node to "zero in" on the destination. We have explored several variants of this idea, under different mobility processes, and with different side-information (positions available or not).

Papers:

  • Locating Mobile Nodes with EASE: Learning Efficient Routes from Encounter Histories Alone,
    M. Grossglauser and M. Vetterli, IEEE/ACM Trans. on Networking, vol 14, no 3, June 2006. [pdf] [ps]
  • Island Hopping: Efficient Mobility-Assisted Forwarding in Partitioned Networks,
    N. Sarafijanovic-Djukic, M. Piorkowski, and M. Grossglauser, IEEE SECON 2006, Reston, VA, September 2006. [pdf]
  • Last Encounter Routing under Random Waypoint Mobility,
    N. Sarafijanovic-Djukic and M. Grossglauser, NETWORKING 2004, Athens, Greece, May 2004. [pdf] [ps]
  • Age Matters: Efficient Route Discovery in Mobile Ad Hoc Networks Using Encounter Ages,
    H. Dubois-Ferrière, M.Grossglauser, M. Vetterli, ACM MOBIHOC 03, Maryland, June 2003. [pdf] [ps]
  • Space-Time Routing in Ad Hoc Networks,
    H. Dubois-Ferrière, M. Grossglauser, M. Vetterli, Ad Hoc Now 03, Montréal, Canada, October 2003. [pdf] [ps]

Student Projects:

  • Please check the LCA Projects page to find more information about semester and master projects in this area.