Generalizing the Square Root Rule for Optimal Periodic Scheduling in Push-Based Wireless Environments

The present paper proposes a generalization of the square root rule for optimal periodic scheduling. The rule defines a ratio of item occurrences in a schedule, which minimizes the mean serving time. However, the actual number of each item's occurrences must be an integer. Therefore, the square root rule assumes large schedules, in order for the ratio to hold with acceptable precision. The present paper introduces an analysis-derived formula which connects the mean serving time and the size of the schedule. The relation shows that small schedules can also achieve near-optimal serving times. The analysis is validated through comparison with simulation and brute force-derived results. Finally, it is shown that minimizing the size of the schedule is also an efficient way of optimizing the aggregate scheduling cost.