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.