Abstract
This paper presents the first online algorithm designed to minimize the dual objectives of energy consumption and flow time within a broadcast scheduling framework. In this model, a single transmission can satisfy multiple overlapping requests for the same data, a scenario common in wireless and ad-hoc networks. Given the inherent theoretical lower bounds of broadcast scheduling, the study employs resource augmentation to demonstrate that the proposed algorithm is scalable and $O(1/\epsilon^3)$-competitive under arbitrary convex power functions. Furthermore, the research extends these findings to provide a novel non-clairvoyant algorithm for standard scheduling models.
Introduction
In modern wireless communication, particularly in battery-operated ad-hoc networks, energy efficiency is a critical design constraint. A common technique for managing energy is "speed scaling," where a transmitter adjusts its processing speed to balance power consumption against user latency. In scheduling theory, this latency is typically measured as "flow time"—the duration between a request's arrival and its completion.
While speed scaling is well-documented in standard scheduling (where each request is unique), its application to broadcast scheduling remains relatively unexplored. In a broadcast environment, multiple clients may request the same information (e.g., a specific data page). A single broadcast of that page satisfies all pending requests for it simultaneously. This overlap introduces significant complexity, as traditional scheduling metrics and algorithms do not directly translate.
Problem Formulation and Challenges
The primary challenge in broadcast scheduling is its inherent difficulty; even without energy considerations, the problem possesses an $\Omega(n)$ lower bound on the competitive ratio. This implies that no standard online algorithm can perform competitively against an optimal offline adversary without additional advantages.
Furthermore, real-world systems often exhibit complex power consumption patterns. While many models assume a simple polynomial relationship (e.g., $P(s) = s^\alpha$), this paper addresses the more general case of an arbitrary convex power function. To circumvent the theoretical lower bounds, the author utilizes resource augmentation, providing the online algorithm with a speed advantage of $(1+\epsilon)$ over the offline optimal scheduler.
Methodology
The proposed solution relies on a multi-stage theoretical framework:
1. Fractional to Integral Reduction
The author develops a technique to convert "fractional" broadcast schedules—where data is treated as a continuous fluid—into "integral" schedules. This reduction is specifically designed to handle variable transmission speeds, ensuring that the mathematical insights gained from the simpler fractional model remain valid in realistic, discrete scheduling scenarios.
2. The BLAPS-Based Algorithm
The core algorithm is a variation of Broadcast Latest Arrival Processor Sharing (BLAPS). The algorithm dynamically adjusts its transmission speed such that the power consumed at any moment is proportional to the number of currently unsatisfied requests. This ensures that the system works harder when the backlog is high, effectively balancing energy use against flow time.
3. Job Selection and Power Distribution
Processing power is not distributed uniformly. Instead, the algorithm focuses on a subset of the most recently arrived requests, determined by a parameter $\beta$. By prioritizing recent arrivals within this subset, the algorithm maintains responsiveness while managing the total flow time.
4. Potential Function Analysis
The $O(1/\epsilon^3)$-competitive ratio is established through a sophisticated potential function argument. This analysis bridges the gap between broadcast scheduling techniques and standard speed-scaling theory, proving that the algorithm remains stable and efficient under the $(1+\epsilon)$ speed augmentation.
Key Results and Contributions
The research yields two primary contributions to the field of scheduling theory:
- Scalable Broadcast Scheduling: The algorithm is proven to be $O(1/\epsilon^3)$-competitive for minimizing the sum of total flow time and energy in the broadcast model. This represents the first scalable result for this specific problem combination.
- Non-Clairvoyant Standard Scheduling: Because broadcast scheduling is a generalization of standard scheduling, the algorithm naturally applies to the latter. It provides a new, scalable, non-clairvoyant algorithm for minimizing weighted flow time plus energy. Notably, this algorithm does not require knowledge of job sizes upon arrival, filling a significant gap in the literature for arbitrary power functions.
Conclusion and Future Directions
This work demonstrates that scalable online algorithms are achievable in the complex environment of broadcast scheduling with speed scaling. By handling arbitrary convex power functions, the model moves closer to real-world applicability.
However, a limitation remains: the algorithm's internal parameters (specifically $\beta$) are dependent on the resource augmentation factor $\epsilon$. Future research may focus on developing "$\epsilon$-oblivious" algorithms that do not require prior knowledge of the speed advantage. Additionally, exploring alternative objective functions within the broadcast framework continues to be a promising area for algorithmic development.
Summary updated