A Non-Stochastic Learning Approach to Energy Efficient Mobility Management

Cong Shen, Cem Tekin, Mihaela van der Schaar

This paper, published in 2016, tackles the growing complexity of mobility management in ultra-dense networks (UDN). As we move toward 5G and beyond, the sheer density of small base stations (SBS) makes traditional handover protocols inefficient. The authors propose a shift from myopic optimization to long-term online learning.

TL;DR

The authors introduce BREW (Batched Randomization with Exponential Weighting), a non-stochastic online learning algorithm that minimizes long-term energy consumption in wireless networks. By explicitly accounting for handover costs and avoiding rigid statistical assumptions, BREW achieves significantly better energy efficiency and robustness than standard 3GPP protocols.

What Problem Does This Paper Address?

In traditional cellular networks, "mobility management" (deciding which base station a phone should connect to) is relatively straightforward. However, in Ultra-Dense Networks (UDN), a user might be surrounded by dozens of small cells with similar signal strengths.

This leads to two major issues:

  1. The Ping-Pong Effect: Frequent, unnecessary handovers (FHO) between base stations that waste massive amounts of energy.
  2. Unpredictable Dynamics: Real-world network conditions (traffic load, interference, SBSs turning on/off) are too "messy" for standard statistical models.

Existing 3GPP protocols are "myopic"—they optimize for the best signal right now. The authors argue that mobility management should instead focus on long-term energy consumption, treating the unpredictable network environment as a "non-stochastic" (potentially adversarial) system.

Methods

The paper moves away from optimization theory and toward Multi-Armed Bandit (MAB) theory. Specifically, they use a non-stochastic framework where the "loss" (energy consumption) of each SBS can vary arbitrarily over time.

Key Algorithms:

  • BREW (Batched Randomization with Exponential Weighting):
    • Batching: Instead of re-evaluating the connection every millisecond, BREW groups time into batches ($\tau$). It stays with one SBS for the duration of the batch. This "exploring in bulk" naturally suppresses the energy cost of frequent handovers.
  • Exponential Weighting: Based on the celebrated EXP3 algorithm, it maintains a probability distribution over all available SBSs, updating them based on observed energy performance.
  • Ranking Expert (RE) & Contextual Ranking Expert (CRE):
    • To handle SBSs that dynamically turn on and off (the "sleeping bandit" problem), the authors use an "expert" framework.
  • CRE is particularly clever: it uses the user's current SBS as a "context" to decide the next best move, drastically reducing the computational complexity of the learning process.

Datasets

The authors evaluate their approach using a system-level simulator built on industry-standard models rather than a static dataset.

  • Environment: A simulated urban deployment following 3GPP TR 36.814 specifications.
  • Pathloss Model: 3GPP "in-to-out" model with log-normal shadowing.
  • Mobility: A random waypoint model with low speed to simulate typical indoor/pedestrian UDN users.
  • Scale: Scenarios with $N=6$ and $N=12$ small base stations.

Key Insights and Ideas

  • The "Handover Cost" is Central: Most learning models ignore the energy spike caused by the act of switching. By adding a switching penalty ($E_s$) to the utility function, the algorithm learns to be "sticky" to good base stations rather than chasing every minor signal fluctuation.
  • Non-Stochastic is More Realistic: Most research assumes network rewards follow a nice Gaussian or Markov distribution. By assuming the environment is "non-stochastic," the authors create a solution that is robust against worst-case scenarios and unpredictable user behavior.
  • Batching as a Regularizer: In BREW, the batch size $\tau$ acts as a control knob. A larger $\tau$ reduces handover costs but slows down learning. The authors prove that an optimal $\tau$ exists to achieve "sublinear regret," meaning the algorithm is guaranteed to eventually perform as well as a "genie" who knew the best SBS from the start.

Key Results

  • Energy Savings: In simulations, BREW achieved 20%–30% less energy consumption than standard 3GPP-macro and 3GPP-FHO (handover-aware) protocols over moderate timeframes.
  • Asymptotic Performance: As time progresses, the gain over 3GPP protocols grows to over 60%, as BREW successfully converges to the optimal SBS while the 3GPP protocols remain stuck in sub-optimal switching loops.
  • Robustness: The authors proved (and simulated) that BREW maintains its performance even when feedback from the network is delayed or missing, a common occurrence in real-world wireless hardware.
  • Regret Bounds: The paper provides rigorous mathematical proofs that BREW's regret grows at a rate of $O(T^{2/3})$, ensuring long-term convergence.

Limitations and Future Work

  • Parameter Tuning: The optimal batch size $\tau$ and learning rate $\gamma$ depend on the time horizon $T$. In a real deployment where $T$ is unknown, the algorithm would need an "anytime" version that adjusts these parameters on the fly.
  • Missing Feedback Regret: While the authors proposed a version of BREW for missing feedback, they noted that proving a sublinear regret bound for the non-stochastic case with missing feedback remains an open theoretical challenge.
  • Computational Complexity: While CRE reduces the number of experts, the "Ranking Expert" approach still requires maintaining state for many possibilities. Further optimization would be needed for low-power IoT devices.

Summary updated

Abstract

Energy efficient mobility management is an important problem in modern wireless networks with heterogeneous cell sizes and increased nodes densities. We show that optimization-based mobility protocols cannot achieve long-term optimal energy consumption, particularly for ultra-dense networks (UDN). To address the complex dynamics of UDN, we propose a non-stochastic online-learning approach which does not make any assumption on the statistical behavior of the small base station (SBS) activities. In addition, we introduce handover cost to the overall energy consumption, which forces the resulting solution to explicitly minimize frequent handovers. The proposed Batched Randomization with Exponential Weighting (BREW) algorithm relies on batching to explore in bulk, and hence reduces unnecessary handovers. We prove that the regret of BREW is sublinear in time, thus guaranteeing its convergence to the optimal SBS selection. We further study the robustness of the BREW algorithm to delayed or missing feedback. Moreover, we study the setting where SBSs can be dynamically turned on and off. We prove that sublinear regret is impossible with respect to arbitrary SBS on/off, and then develop a novel learning strategy, called ranking expert (RE), that simultaneously takes into account the handover cost and the availability of SBS. To address the high complexity of RE, we propose a contextual ranking expert (CRE) algorithm that only assigns experts in a given context. Rigorous regret bounds are proved for both RE and CRE with respect to the best expert. Simulations show that not only do the proposed mobility algorithms greatly reduce the system energy consumption, but they are also robust to various dynamics which are common in practical ultra-dense wireless networks.
BibTeX
@article{shen2016non,
  author = {Cong Shen and Cem Tekin and Mihaela van der Schaar},
  title = {{A Non-Stochastic Learning Approach to Energy Efficient Mobility Management}},
  journal = {IEEE J. Sel. Areas Commun.},
  year = {2016},
  doi = {10.1109/jsac.2016.2612038},
}

Loading related content...

Figure