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

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