Random walks on digraphs: A theoretical framework for estimating transmission costs in wireless routing

Yanhua Li, Zhi-Li Zhang

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

25 Scopus citations


In this paper we develop a unified theoretical framework for estimating various transmission costs of packet forwarding in wireless networks. Our framework can be applied to the three routing paradigms - best path routing, opportunistic routing, and stateless routing - to which nearly all existing routing protocols belong.We illustrate how packet forwarding under each paradigm can be modeled as random walks on directed graphs (digraphs). By generalizing the theory of random walks that has primarily been developed for undirected graphs to digraphs, we show how various transmission costs can be formulated in terms of hitting times and hitting costs of random walks on digraphs. As representative examples, we apply the theory to three specific routing protocols, one under each paradigm. Extensive simulations demonstrate that the proposed digraph based analytical model can achieve more accurate transmission cost estimation over existing methods.

Original languageEnglish (US)
Title of host publication2010 Proceedings IEEE INFOCOM
StatePublished - 2010
EventIEEE INFOCOM 2010 - San Diego, CA, United States
Duration: Mar 14 2010Mar 19 2010

Publication series

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


Country/TerritoryUnited States
CitySan Diego, CA


  • Digraph
  • Random walk
  • Spectral graph theory
  • Transmission cost
  • Wireless routing


Dive into the research topics of 'Random walks on digraphs: A theoretical framework for estimating transmission costs in wireless routing'. Together they form a unique fingerprint.

Cite this