Scheduling data broadcasts on wireless channels: exact solutions and heuristics

We discuss the broadcasting problem of N data items over K wireless channels, under the assumptions of skewed data allocation to channels and flat data scheduling per channel. Both the uniform and nonuniform length cases are surveyed showing their exact and heuristic solutions, respectively. Two of the heuristic methods are greedy and the third one is based on a dynamic programming procedure developed to solve a simplified version of the problem. An experimental evaluation of our heuristics is presented and the quality of the solutions generated is compared against a lower bound, which is derived by relaxing the problem and then solving it optimally via a dynamic programming procedure developed in earlier sections.