Academic
Publications
Random Walks on Digraphs: A Theoretical Framework for Estimating Transmission Costs in Wireless Routing

Random Walks on Digraphs: A Theoretical Framework for Estimating Transmission Costs in Wireless Routing,10.1109/INFCOM.2010.5462109,Yanhua Li,Zhi-Li Z

Random Walks on Digraphs: A Theoretical Framework for Estimating Transmission Costs in Wireless Routing   (Citations: 2)
BibTex | RIS | RefWorks Download
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.
Conference: IEEE INFOCOM - INFOCOM , pp. 2775-2783, 2010
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...Finally, we remark that [29] recently generalizes some of our results of the hitting time for irreversible Markov chains, using the notion of pseudo-inverse of Laplacian...

    Chi-Kin Chauet al. Analysis of Latency of Stateless Opportunistic Forwarding in Intermitt...

    • ...In wireless networks, due to the unstable channel characteristics, using a single “shortest” path (e.g., with link quality as link weights) for routing is often not the best choice; routing strategies that go beyond shortest path routing (see, e.g., [4], [15], [18], [25] and references therein) using multiple paths are often more effective...
    • ...Another application arises more naturally in wireless sensor networks, where deciding on the best strategies hinge on trading off different cost considerations [18], e.g., transmission latency as well as energy consumption – the latter is important, for example, to maximize the sensor network life time, where it is shown in [19] that potential-based routing using �� 2-norm maximizes the network life time...

    Yanhua Liet al. The Routing Continuum from Shortest-Path to All-Path: A Unifying Theor...

Sort by: