Design of optimal link-layer algorithms for wireless networks

Abstract

Since the appearance of smart devices like as smart phones and table PCs, the mobile data traffic has been heavily increased. Many researchers and experts from network sectors predict that such explosive increase in the amount of mobile traffic will be lasted for a while and it will reach to ten-fold increase within the next 5 years. Due to the mobile data explosion, current wireless networks are facing to the severe traffic overloads. To cope with the serious threat, we should exhaust every means of alleviating traffic overloads. Among many ones, we particularly focus on the way to optimally utilize network resources in this dissertation. We propose several link-layer algorithms achieving optimal performances based on the learning approach. First, we study about recent throughput optimal CSMA (Carrier Sense Multiple Access) protocols. Although those algorithms are optimal in the throughput aspect, most of them are known to exhibit poor delay performance making them impractical for implementation. Thus, we focus on the recent idea of exploiting multiple channels for delay reduction in CSMA, and prove that it is per-link delay order-optimal, i.e O(1)-asymptotic-delay per link, if the number of virtual channels is logarithmic with respect to mixing time of the underlying CSMA Markov chain. The logarithmic number is typically small, i.e., at most linear with respect to the network size. Second, we develop an optimal rate adaptation protocol. We noticed that existing rate adaption schemes have been driven mainly by heuristics. In contrast, we formulate the rate adaptation problem as a kind of multi-armed bandit (MAB) problem. We derive an asymptotic upper bound for the expected reward in the corresponding MAB problem. This provides a fundamental performance limit that any rate adaptation algorithm cannot exceed. We then propose algorithms that approach this performance limit, and adapt their design to non-stationary environments where the success transmission probabilities at different rates evolve over time. We illustrate the efficiency of our algorithms (compared to the state-of-the-art algorithms) using both trace-driven simulations and implementation in a 802.11n real network test-bed. Related to the second topic, we finally study the MAB with additional observations problem, which is modeled on the rate adaptation with packet probing scenario. We investigate how much more observations help to significantly improve the performance in both stochastic and adversarial settings as done in the MAB literature. First, for the stochastic setting, we derive an asymptotic upper bound on expected reward and propose two algorithms called SIMPLE and KL-UCB-A. In particular, we have shown that KL-UCB-A is order-optimal in terms of the number of rounds T under mild conditions. Second, for the adversarial setting, we also develop an algorithm that achieves an order-optimal reward with respect to the number of arms, the number of observations and the number of rounds.