Computer Science – Networking and Internet Architecture
Scientific paper
2010-08-10
Computer Science
Networking and Internet Architecture
14 pages 6 figures : This is a preliminary pre-print. Full version has been submitted for review elsewhere
Scientific paper
This paper introduces GODDeS: a fully distributed self-organizing decision-theoretic routing algorithm designed 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, with links characterized by locally known packet drop probabilities that either remain constant on average or change slowly. The equivalence of this optimization problem to that of performance maximization of an explicitly constructed probabilistic automata allows us to effectively apply the theory of quantitative measures of probabilistic regular languages, and design a distributed highly efficient solution approach that attempts to minimize 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. It is also argued that GODDeS is significantly congestion-aware, and exploits multi-path routes optimally. Theoretical development is supported by high-fidelity network simulations.
No associations
LandOfFree
GODDeS: Globally ε-Optimal Routing Via Distributed Decision-theoretic Self-organization does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with GODDeS: Globally ε-Optimal Routing Via Distributed Decision-theoretic Self-organization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and GODDeS: Globally ε-Optimal Routing Via Distributed Decision-theoretic Self-organization will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-582818