Online Ski Rental for ON/OFF Scheduling of Energy Harvesting Base Stations

Gilsoo Lee, Walid Saad, Mehdi Bennis, Abolfazl Mehbodniya, Fumiyuki Adachi

TL;DR

This paper tackles the challenge of optimizing energy consumption in cellular networks by intelligently managing the ON/OFF schedules of self-powered small cell base stations (SBSs) that rely on energy harvesting. They introduce a novel approach inspired by the "ski rental problem" to make these decisions autonomously and efficiently, even with unpredictable energy availability, leading to significant reductions in total cost and network delay.

What Problem Does This Paper Address?

Modern cellular networks are increasingly deploying small cell base stations (SBSs) to boost capacity and coverage. However, this densification leads to a substantial increase in overall energy consumption. To combat this, there's a growing interest in self-powered SBSs that utilize energy harvesting (e.g., solar power). The core challenge lies in managing these SBSs effectively: energy harvesting is inherently uncertain and intermittent, and SBSs have finite energy storage. This uncertainty makes it difficult for SBSs to decide when to be ON (consuming energy to serve users) and when to be OFF (conserving energy and relying on storage or a macrocell base station). Without intelligent scheduling, networks face either excessive energy waste or degraded performance due to insufficient capacity. This paper addresses the problem of optimizing the ON/OFF schedule of these self-powered SBSs to minimize operational costs, which include both energy consumption and user-perceived delay, under conditions of unknown future energy arrivals.

Methods

The authors propose a two-pronged approach:

  1. Problem Formulation: They first formulate the problem of minimizing the total operational cost (combining SBS ON-time costs and MBS fallback costs) as an optimization problem. This initial formulation is complex due to the dynamic nature of energy harvesting and user association.
  2. Approximation and Online Optimization: To manage complexity, they propose an approximation that decomposes the problem into individual subproblems for each SBS. This allows for a distributed, self-organizing approach. The core innovation is framing each SBS's decision-making as an online ski rental problem.
  3. Ski Rental Analogy: In the classic ski rental problem, an individual faces uncertainty about how many days they'll ski and must decide whether to rent skis daily (lower cost per day, but accumulates) or buy them upfront (higher initial cost, but cheaper for long-term use). Similarly, an SBS must decide whether to "rent" its resources by staying ON (incurring per-unit time costs) or "buy" the more expensive but reliable macrocell base station (MBS) resources by turning OFF.
  4. Deterministic Online Algorithm (DOA): A baseline online algorithm that turns an SBS OFF at a predetermined time.
  5. Randomized Online Algorithm (ROA): The key contribution. This algorithm uses a probability distribution to decide when to turn OFF, inspired by the ski rental problem's optimal strategy. This allows SBSs to make decisions autonomously without knowing future energy arrivals, aiming to minimize the expected cost.

Datasets

Not discussed in the paper. The authors use simulated data for evaluation.

Key Insights and Ideas

  • The "Ski Rental" Analogy is Powerful: Framing the ON/OFF scheduling problem as a ski rental problem provides a robust theoretical framework for handling uncertainty in energy harvesting. It elegantly captures the trade-off between immediate operational costs and the potential cost of relying on a more expensive alternative.
  • Autonomous Decision-Making is Crucial: In dense networks, centralized control is impractical. The proposed online algorithms enable each SBS to make its own ON/OFF decisions locally, reducing signaling overhead and improving scalability.
  • Randomization Offers Optimal Competitive Ratio: While a deterministic approach (DOA) provides a baseline, the randomized online algorithm (ROA) achieves a theoretically optimal competitive ratio for the approximated problem, meaning it performs as close to the ideal offline solution as possible given the online constraints.
  • Energy Storage and Cost Trade-offs Drive ON Time: The simulations reveal that higher energy storage capacity, lower operational costs (due to transmission power or efficiency), and higher costs for using the MBS all contribute to longer ON times for SBSs. Conversely, higher MBS operational power or lower SBS costs can lead to shorter ON times.

Key Results

  • The proposed Randomized Online Algorithm (ROA) significantly reduces the total operational cost of the network compared to baseline approaches, with reductions of up to 69.9%.
  • ROA also leads to substantial improvements in network performance, reducing per-SBS network delay by up to 20.6% and total energy consumption by up to 15.6% compared to a baseline.
  • The ROA achieves an empirical competitive ratio of 1.86, demonstrating its effectiveness in approximating the optimal offline solution.
  • The number of ON/OFF switchings is significantly reduced by ROA, leading to more stable network operation and fewer handovers.
  • The study highlights how factors like transmit power, energy storage levels, and the relative costs of SBS operation versus MBS fallback influence the optimal ON time for SBSs.

Limitations and Future Work

  • Approximation for Complexity: The paper relies on an approximation of the original problem to make it tractable. While this approximation is effective, it means the proposed algorithms are optimal for the approximated problem, not necessarily the original, more complex one.
  • Theoretical Analysis of Original Problem: The authors note that the theoretical analysis of the original, non-approximated problem is challenging due to the dynamic nature of costs and user associations.
  • Future Work: The paper suggests exploring more dynamic cost functions and investigating the impact of different energy harvesting models. Further research could also focus on extending these algorithms to more complex network topologies and considering other performance metrics.

Summary updated

Abstract

The co-existence of small cell base stations (SBSs) with conventional macrocell base station is a promising approach to boost the capacity and coverage of cellular networks. However, densifying the network with a viral deployment of SBSs can significantly increase energy consumption. To reduce the reliance on unsustainable energy sources, one can adopt self-powered SBSs that rely solely on energy harvesting. Due to the uncertainty of energy arrival and the finite capacity of energy storage systems, self-powered SBSs must smartly optimize their ON and OFF schedule. In this paper, the problem of ON/OFF scheduling of self-powered SBSs is studied, in the presence of energy harvesting uncertainty with the goal of minimizing the operational costs consisting of energy consumption and transmission delay of a network. For the original problem, we show that an algorithm can solve the problem in the illustrative case. Then, to reduce the complexity of the original problem, an approximation is proposed. To solve the approximated problem, a novel approach based on the ski rental framework, a powerful online optimization tool, is proposed. Using this approach, each SBS can effectively decide on its ON/OFF schedule autonomously, without any prior information on future energy arrivals. By using competitive analysis, a deterministic online algorithm and a randomized online algorithm (ROA) are developed. The ROA is then shown to achieve the optimal competitive ratio in the approximation problem. Simulation results show that, compared with a baseline approach, the ROA can yield performance gains reaching up to 15.6% in terms of reduced total energy consumption of SBSs and up to 20.6% in terms of per-SBS network delay reduction. The results also shed light on the fundamental aspects that impact the ON time of SBSs while demonstrating that the proposed ROA can reduce up to 69.9% the total cost compared with a baseline approach.
BibTeX
@article{lee2017online,
  author = {Gilsoo Lee and Walid Saad and Mehdi Bennis and Abolfazl Mehbodniya and Fumiyuki Adachi},
  title = {{Online Ski Rental for ON/OFF Scheduling of Energy Harvesting Base Stations}},
  journal = {IEEE Trans. Wireless Communications},
  year = {2017},
  url = {https://openreview.net/forum?id=4EabsaWLhwK},
}
Figure