Random walks and green's function on digraphs: A framework for estimating wireless transmission costs

Yanhua Li, Zhi Li Zhang

Research output: Contribution to journalArticlepeer-review

17 Scopus citations


Various applications in wireless networks, such as routing and query processing, can be formulated as random walks on graphs. Many results have been obtained for such applications by utilizing the theory of random walks (or spectral graph theory), which is mostly developed for undirected graphs. However, this formalism neglects the fact that the underlying (wireless) networks in practice contain asymmetric links, which are best characterized by directed graphs (digraphs). Therefore, random walk on digraphs is a more appropriate model to consider for such networks. In this paper, by generalizing the random walk theory (or spectral graph theory) that has been primarily developed for undirected graphs to digraphs, we show how various transmission costs in wireless networks can be formulated in terms of hitting times and cover times of random walks on digraphs. Using these results, we develop a unified theoretical framework for estimating various transmission costs in wireless networks. Our framework can be applied to random walk query processing strategy and the three routing paradigms-best path routing, opportunistic routing, and stateless routing-to which nearly all existing routing protocols belong. Extensive simulations demonstrate that the proposed digraph-based analytical model can achieve more accurate transmission cost estimation over existing methods.

Original languageEnglish (US)
Article number6179323
Pages (from-to)135-148
Number of pages14
JournalIEEE/ACM Transactions on Networking
Issue number1
StatePublished - 2013


  • Digraph
  • random walk
  • spectral graph theory
  • transmission cost
  • wireless networks

Fingerprint Dive into the research topics of 'Random walks and green's function on digraphs: A framework for estimating wireless transmission costs'. Together they form a unique fingerprint.

Cite this