Optimal distributed algorithms for scheduling and load balancing in wireless networks

2015-07-06With the proliferation of billions of smart devices including wearables, multimedia capable handheld devices like tablets and smartphones, and the deluge of HD video content streaming on them, the existing wireless networking technologies (cellular + WiFi) need a significant overhaul in terms of system architecture design and efficient resource allocation algorithms. This poses several challenges across the entire spectrum of the wireless network system architecture. These range from the unpredictable wireless medium and interference at the lower layers, to limited throughput and unfair resource sharing at the network layer, and to complex media content characteristics at the application layer. Typical approaches to these problems have been isolated and independent across network layers, leading to partial heuristic solutions at different layers which when put together do not perform well and often introduce more complexity. ❧ In this dissertation, taking a holistic view of the entire system, we have designed network architectures and algorithms for scheduling, load balancing and congestion control spanning different layers of the network. The primary focus is on developing low complexity algorithms which work in a self‐adaptive and online fashion in response to unpredictably changing network conditions, and which can be implemented in a distributed manner across the various nodes in the network. In particular, the key underlying theme of this dissertation is to show that the designed algorithms, albeit distributed in nature, are actually optimal in the sense of maximizing a global network‐wide performance metric. ❧ In the first part of this dissertation, we consider the user‐cell association problem for a massive MIMO heterogeneous network. We focus on the design and analysis of self‐organizing, user‐centric distributed algorithms for load balancing in a wireless network with the advanced physical layer feature of Massive MIMO which is likely to play a key role in future cellular standards like 5G and WiFi standards like 802.11 ac/ax. We formulate the user‐cell association problem as a network utility maximization, where the network utility is a function of the users' long‐term average rates (per‐user throughputs). Under a massive‐MIMO specific system model, we show that optimizing the activity fractions between user‐BS pairs problem is a convex problem that can be solved efficiently by centralized sub‐gradient algorithms. Furthermore, we show that such a solution is physically realizable, in the sense that there exists a scheduling sequence approaching arbitrarily closely the optimal activity fractions. We then consider a decentralized user‐centric scheme, where each user has a positive probability to switch cell association if the utility expected from a different base station is higher than the utility achieved from the currently associated one. We formulate a non‐cooperative association game and show that its pure-strategy Nash equilibria must be close to the global optimum of the centralized problem. We also show that, under certain technical conditions that we refer to as heavy‐loaded network, if the centralized global optimum consists of a unique association (i.e., no user has positive activity fraction to more than one base station), then this association is a pure-strategy Nash equilibrium of the corresponding user‐centric association game. Based on previously known results, we also have that the proposed user‐centric decentralized probabilistic scheme converges to a pure‐strategy Nash equilibrium with probability 1, for the practically relevant cases of proportional fairness and max-min fairness utility functions. Hence, our user‐centric algorithm is attractive not only for its simplicity and fully decentralized implementation, but also because it operates near the system social optimum. ❧ In the second part of the dissertation, we focus on the design and analysis of low complexity, self‐adaptive and distributed algorithms for user scheduling and congestion control for efficient delivery of video content over wireless networks. In particular, we consider the problem of optimizing delivery of stored video to users in a multicell wireless network formed by many users and helpers, deployed over a localized geographic area and sharing the same channel bandwidth. We focus on the wireless segment of the network, assuming that the video files are already present at the helper nodes. This condition holds when the backhaul connecting the helper nodes to some video server in the core network is fast enough, such that we can neglect the delays introduced by the backhaul. In the case where such fast backhaul is not present, we assume that the helpers can cache the relevant files by exploiting the inherent asynchronous content reuse of Video on Demand (VoD) in order to predict and proactively store the popular video files such that, with high probability, the demanded files are effectively already present in the helpers caches. This justifies our assumption of neglecting the effects of the wired backhaul and focusing only on the wireless segment of the system. For the network at hand, we consider the problem of simultaneous on‐demand video streaming to multiple users, where multiple unicast streaming sessions run in parallel and compete for the same network resources. We formulate the problem as a Network Utility Maximization (NUM) where the objective is to fairly maximize users' video streaming Quality of Experience (QoE) and then derive an iterative scheme using Lyapunov Optimization, which can solve the NUM problem up to any level of accuracy. Moreover, it can be used directly as an online protocol by interpreting the iterations as control actions in successive transmission slots. The proposed scheme decomposes into interconnected layers: an adaptive video streaming layer that is reminiscent of DASH (Dynamic Adaptive Streaming over HTTP), implemented at each user node, and involves video chunk requests, playback buffer monitoring and adaptive selection of the coded video, and a max‐weight transmission scheduler implemented at each helper. These two layers are interconnected by the appropriate queues maintained at the nodes of the network, which form the weights for the max‐weight scheduler. We then extend the design of the max‐weight transmission scheduler to the case where the helpers are equipped with multi‐user MIMO (MU-MIMO) capabilities. We exploit the channel hardening effect of high dimensional MIMO channels and devise a low complexity user selection scheme to solve the underlying combinatorial problem of selecting user subsets for linear zero‐forcing beamforming (LZFBF), which can be easily implemented and run independently at each helper. Through simulations, we show that deploying MU-MIMO significantly improves the average video quality and reduces the percentage of time spent in buffering mode. In addition, we demonstrate that the proposed cross layer approach is able to serve users more fairly than a baseline scheme representative of current systems running independently designed protocol layers, where the video quality adaptation (e.g., based on DASH) runs on top of a classical MAC/PHY transmission scheduler (e.g., based on Proportional Fairness), without exploiting cross‐layer joint optimization