Efficient Media Access Control and Distributed Channel-aware Scheduling for Wireless Ad-Hoc Networks

Thumbnail Image


Publication or External Link






We address the problem of channel-aware scheduling for wireless ad-hoc networks, where the channel state information (CSI) are utilized to improve the overall system performance instead of the individual link performance. In our framework, multiple links cooperate to schedule data transmission in a decentralized and opportunistic manner, where channel probing is adopted to resolve collisions in the wireless medium.

In the first part of the dissertation, we study this problem under the assumption that we know the channel statistics but not the instant CSI. In this problem, channel probing is followed by a transmission scheduling procedure executed independently within each link in the network. We study this problem for the popular block-fading channel model, where channel dependencies are inevitable between different time instances during the channel probing phase. We use optimal stopping theory to formulate this problem, but at carefully chosen time instances at which effective decisions are made. The problem can then be solved by a new stopping rule problem where the observations are independent between different time instances. We first characterize the system performance assuming the stopping rule problem has infinite stages. We then develop a measure to check how well the problem can be analyzed as an infinite horizon problem, and characterize the achievable system performance if we ignore the finite horizon constraint and design stopping rules based on the infinite horizon analysis. We then analyze the problem using backward induction when the finite horizon constraint cannot be ignored. We develop one recursive approach to solve the problem and show that the computational complexity is linear with respect to network size. We present an improved protocol to reduce the probing costs which requires no additional cost.

Based on our analysis on single-channel networks, we extend the problem to ad-hoc networks where the wireless spectrum can be divided into multiple independent sub-channels for better efficiency. We start with a naive multi-channel protocol where the scheduling scheme is working independently within each sub-channel. We show that the naive protocol can only marginally improve the system performance. We then develop a protocol to jointly consider the opportunistic scheduling behavior across multiple sub-channels. We characterize the optimal stopping rule and present several bounds for the network throughputs of the multi-channel protocol. We show that by joint optimization of the scheduling scheme across multiple sub-channels, the proposed protocol improves the system performance considerably in contrast to that of single-channel systems.

In the second part of the dissertation, we study this problem under the assumption that neither the instant CSI nor the channel statistics are known. We formulate the channel-aware scheduling problem using multi-armed bandit (MAB). We first present a semi-distributed MAB protocol which serves as the baseline for performance comparison. We then propose two forms of distributed MAB protocols, where each link keeps a local copy of the observations and plays the MAB game independently. In Protocol I the MAB game is only played once within each block, while in Protocol II it can be played multiple times. We show that the proposed distributed protocols can be considered as a generalized MAB procedure and each link is able to update its local copy of the observations for infinitely many times. We analyze the evolution of the local observations and the regrets of the system. For Protocol I, we show by simulation results that the local observations that are held independently at each link converge to the true parameters and the regret is comparable to that of the semi-distributed protocol. For Protocol II, we prove the convergence of the local observations and show an upper bound of the regret.