Routing over multi-hop wireless networks with non-ergodic mobility

Chris Milling*, Sundar Subramanian, Sanjay Shakkottai, Randall Berry

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations


Routing to mobile nodes in a wireless network is conventionally performed by associating a static IP address (or a geographic location) to each node, and routing to that address using routing tables at intermediate nodes that are updated periodically to reflect mobility-induced network topology changes. This mode of routing works when the mobiles' speeds as well as the number of mobiles are small. However, in the presence of large number of fast-moving mobiles, such approaches are infeasible and can lead to excessive overheads, routing failures and hence, throughput loss. In this paper, we consider a wireless network over a domain with a collection of static nodes (that form a connected cover of the domain) and mobile nodes, where the mobile nodes can move in an arbitrary (non-ergodic) manner over sub-domains of the network. For such a system, we develop new routing algorithms (based on a spatial multi-resolution search) that we show are efficient both in terms of routing overheads and throughput. In particular, we show that the achievable rate region of the proposed algorithm is within a poly-logarithmic constant of the optimal rate region with non-ergodic mobility.

Original languageEnglish (US)
Title of host publicationIEEE INFOCOM 2009 - The 28th Conference on Computer Communications
Number of pages9
StatePublished - 2009
Event28th Conference on Computer Communications, IEEE INFOCOM 2009 - Rio de Janeiro, Brazil
Duration: Apr 19 2009Apr 25 2009

Publication series

NameProceedings - IEEE INFOCOM
ISSN (Print)0743-166X


Other28th Conference on Computer Communications, IEEE INFOCOM 2009
CityRio de Janeiro

ASJC Scopus subject areas

  • Computer Science(all)
  • Electrical and Electronic Engineering

Cite this