Paper Info
Title
Scalable ε-Optimal Decision-Making and Stochastic Routing in Large Networks via Distributed Supervision of Probabilistic Automata.
Abstract
A scalable distributed stochastic routing algorithm (GODDeS) is developed to effectively exploit high quality paths in lossy ad-hoc wireless environments, typically with a large number of nodes. The routing problem is modeled as an optimal control problem for a decentralized Markov decision process via a probabilistic local broadcast model, with links characterized by locally known or estimated drop probabilities that either remain constant on average or change slowly. Equivalence of this optimization problem to that of performance maximization of probabilistic automata allows us to effectively apply the theory of quantitative measures of probabilistic regular languages, and design a distributed, highly efficient, scalable, and stationary routing policy that very nearly minimizes source-to-sink drop probabilities across the network. Theoretical results provide rigorous guarantees on global performance, showing that the algorithm achieves near-global optimality in polynomial time, and worst case asymptotic convergence time is shown to scale linearly with network size. Furthermore, the theoretical results establish that it is possible to trade off deviation from global optimality against convergence time. It is also argued that GODDeS is significantly congestion-aware and exploits multipath routes optimally. Theoretical development is supported by detailed network simulations.
Year
DOI
Venue
2014
10.1137/110857507
SIAM JOURNAL ON CONTROL AND OPTIMIZATION
Keywords
DocType
Volume
scalable decision-making,stochastic routing,probabilistic automata,ad-hoc networks
Journal
52
Issue
ISSN
Citations 
4
0363-0129
0
PageRank 
References 
Authors
0.34
0
1
Name
Order
Citations
PageRank
Ishanu Chattopadhyay1286.91