Stochastic optimal control and performance analysis of wireless ad hoc networks

Abstract

In this thesis, we consider a stochastic optimal control approach for resource allocation and provisioning in wireless ad hoc networks. Specifically, we study the problem of multi-class network scheduling under a time-varying channel and topology. We formulate the problem using the decision theoretic approach known as Markov Decision Process (MDP). We present four variants of MDP formulations to highlight the results and contribution.The first model uses the theory of I?-irreducibility for controlled Markov chains, with the objective of minimizing the average congestion level. Using stability concepts of I?-irreducible chains, we present the first novel method of achieving optimization and stability conditions simultaneously for a general Markov queuing network, and for deriving performance bounds directly from the control algorithm. The second model formulates a Semi-Markov Decision Process (SMDP) where each agent performs network-level bandwidth allocation and buffer management. We then use a model-free approach known as Neuro-Dynamic Programming that uses simulation-based techniques to find near-optimal policies. The third model uses the framework known as Hierarchical Semi-Markov Decision Process (HSMDP) that decomposes the original SMDP provisioning problem into a task structure. A model-free Hierarchical Reinforcement Learning (HRL) technique is then used to achieve faster convergence and better performance by reusing subtasks solutions. Finally, we formulate the scheduling problem as a Decentralized Partially Observable Markov Decision Process (DEC-POMDP) which is a multi-agent extension of MDP for decentralized control where each agent observes different partial views of the global network condition. We also address the issue of locality of interaction among neighboring nodes and apply a model-free solution. In addition, we present the first method of analyzing the stability and optimization of a decentralized Markov network and derive performance bounds as the algorithm converges.