Client Control of HetNets
Heterogeneity of wireless network architectures is increasingly becoming an important part of current and next-generation wireless networks. Simultaneously, mobile devices are increasingly equipped with multiple radio access technologies (RATs) that can connect to and switch between different access networks. In such heterogeneous wireless environments, an important question that arises is "How should a user select the best access network to connect to at any given time?" To envision the difficulty of this task, imagine mobile users as cars on a busy multilane highway. These cars autonomously switch lanes in order to achieve a better speed, which (as we have all experienced during rush hour) may result in oscillations, chaos, and a reduction in everyone's overall speed--from this, we see that fully distributed user-side control of access network selection may be more difficult than it seems.
In many cases, although centralized control schemes for HetNets may be attractive due to guarantees on pareto-optimality, it is not practical to implement in real networks. Centralized control of HetNet RAT Selection requires a great amount of overhead due to message passing between UEs and the centralized controller, all of which induces delay in decision-making. Many local variables (such as remaining battery power, perceived SNR on the accessible RATs, and user personal preferences) are more readily visible at the user-side, which lend themselves better to UE-based decision-making. Furthermore, in many cases it is unclear how a centralized control scheme should be implemented between different operators: questions such as who should manage the centralized controller? and how should load balancing between different networks be done? and how should the benefits of centralized control be allocated? all exist to hinder any practical implementation of centralized control.
Here in EDGE Lab at Princeton University, we are have developed a fully-distributed, user-based algorithm to control how users select RATs to connect to. As a part of our work, we have identified the two major classes of throughput sharing formulae, and proven convergence for both classes as well as a mixture of the two. We also have shown that the algorithm converges to a Nash Equilibrium state, and have shown bounds on efficiency for the convergent states for both classes. The impact of this work is that we now have a fully distributed algorithm that does not require any explicit message passing from the base station, which achieves close to optimal performance for certain classes of throughput formula.
Instead of limiting HetNet control to fully centralized or fully distributed, we are currently exploring the benefits of a hybrid HetNet control scheme where a centralized controller collaborates with UEs in the network to best determine which RAT the UE should associate with. The advantage in this approach is that we may leverage the inherent advantages of centralized and distributed control to improve the state of the system in a faster manner, while potentially obviating many of the disadvantages of each individual approach.
In practical HetNets, there is an absence of perfect information regarding the state of the network: at any time, a UE can potentially know only the bare minimum of information regarding the RATs that it sees, the observed SNR on each RAT, and its own UE statistics. In the absence of a perfect centralized controller instructing UEs how to associate with RATs, this decision must be made at the UE—and to make this decision, there must be a way for UEs to compare RATs to determine preferences. Here in EDGE Lab, we have developed several heuristics based on the release details of LTE and 802.11k to estimate throughput based on passively-observed characteristics.
When making passive measurements regarding throughput inference, erroneous throughput values may be obtained. Errors in throughput measurements can result in extremely bad system behavior—inducing oscillations and generally preventing the system from efficiently optimizing itself. To handle this, we at EDGE Lab have developed an improvement on our fully-distributed RAT selection algorithm that adapts to the ambient noise level on each perceived RAT to prevent oscillations from erroneous inferences.
The theory for HetNet RAT Selection is not limited to only 3G, LTE and 802.11 networks. In collaboration with teams under Dr. Caire and Molisch at USC, we at the EDGE Lab are investigating what makes millimeter-wave radio unique from other types of RATs, and how mmWave RATs can be characterized in terms of HetNet RAT Selection.
We have developed a distributed, client-centric approach to RAT Selection in a HetNet environment with mmWave RATs using Multi-Armed Bandits. We model the stochastic nature of the physical channel in mmWave as a Markov chain, where the state of the channel changes when it is accessed by the user. In the Line of Sight (LOS) state, the client device has an unobstructed path for signal propagation between it and the base station; in the non-Line of Sight (non-LOS), the mmWave channel degrades severely and affords the user a much lower data rate due to obstructions on the signal path; finally, the outage state degrades the channel quality to the point that the base station and client cannot communicate.
In the HetNets scenario, there are multiple unique BSs choices for a user but the user can only associate with a single BS in any given time interval. At each time interval, the user is able to download data (obtain a reward) from the BS that it associates with—but this reward is unknown a priori to the user, and can differ between different BSs. The goal from the user perspective, therefore, is to maximize the expected sum data obtained over a period of time–in other words, how should the user select which BSs to download data from at any given time by learning the statistics of each BS from its past actions. Furthermore, this objective is complicated by the existence of fixed RAT- and BS-specific penalty costs incurred by the user when it switches.
This is a perfect example of the tradeoff between exploration and exploitation, where the client wishes to explore its options to accurately determine which BS provides the maximal average throughput and to update its knowledge periodically, yet the client also wishes to exploit the best BS to ensure the most time spent on the best BS it believes to be best to maximize the total data downloaded.
We develop an online learning algorithm based on rested Multi-armed Bandit Problems to minimize our metric of total regret, defined as the sum of sampling regret (the throughput inefficiency due to imperfect knowledge, between the total throughput obtained by our algorithm and an offline-optimal oracle algorithm) and switching regret (the cost due to handoff between one RAT and another). Our algorithm allows clients to switch frequently early on, in order to develop a good working knowledge of each RAT’s sample mean throughput, but slows the rate of switching over time as we develop better and better knowledge of each RAT. Furthermore, our algorithm indexes each RAT with an index value representing the sample mean throughput of that RAT (exploitation) and the timeliness of that sample mean throughput (exploration). We show that our algorithm is able to achieve and upper bound of O(ln(t)) total regret by minimizing switching costs by switching at pre-determined logarithmic time-intervals, which improves upon the 1985 work of Lai and Robbins, which showed that O(ln(t)) regret is the best we can do for sampling regret.
We compare the performance of our technique with a baseline Markovian MABP solution, as well as a Naïve max-instantaneous throughput algorithm, and our simulations show that we are able to obtain not only asymptotically-optimal regret, but our regret coefficients are less than that of existing solutions (due to a tighter Chernoff bound used) even with the additional concern of minimizing switches included in our formulation.
E. Aryafar, A. Keshavarz-Haddad, M. Wang, M. Chiang. HetNets Selection by Clients: Convergence, Efficiency and Practicality, submitted to IEEE Transactions on Networking
E. Aryafar, A. Keshavarz-Haddad, M. Wang, M. Chiang. RAT Selection Games in HetNetsh, IEEE INFOCOM , 2013