Data broadcast on multiple wireless channels – Exact and time-optimal solutions for uniform data and heuristics for non-uniform data

The present chapter reviews the work on 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. For the case of data items with uniform lengths, four exact polynomial time algorithms are presented, all based on dynamic programming. The first algorithm, called DP, takes O(K N^2) time, whereas the second algorithm, called Dichotomic is faster as it runs in O(K N log N) time. The third algorithm is designed for the specific case of K = 2. Although it requires O(N log N) time, and hence it is asymptotically not faster than Dichotomic, it exploits a specific characterization of the optimal solution that we also use in developing the heuristics for the nonuniform case. Finally, the fourth algorithm, called Smawk-AED has been very recently presented and it takes O(NK) time. This algorithm matches the trivial lower bound for the time complexity of any dynamic programming algorithm for the K-uniform allocation problem that solves all the NK subproblems of allocating a prefix of the items {1, . . . , n} to k channels, 1 ≤ n ≤ N, 1 ≤ k ≤ K. For the case of data items with nonuniform lengths, the problem is NP-hard when K = 2, and strong NP-hard for arbitrary K. In this latter case, the Optimal algorithm is reviewed. It requires O(z K N^2) time, where z is the maximum data length, and reduces to the DP algorithm when z = 1. As algorithm Optimal can solve only small instances in a reasonable time, three heuristics are described, all having an O(N(K + log N)) time complexity. All the three heuristics are then tested on benchmarks whose popularities are characterized by Zipf distributions. The experimental tests reveal that one heuristic, called Dlinear, finds optimal solutions almost always, requiring reasonable running times.