Complexity and heuristics for wireless broadcast with noncumulative layered data

Layer transmission generates multiple layers for a video program, enabling a receiver to selectively subscribe to the layers commensurate with its bandwidth. It is an effective solution to the problem of bandwidth heterogeneity in video broadcasting. However, two important issues remain to be addressed. First, how does a receiver select the subset of layers to achieve the highest bandwidth utilization? Second, how does the sender optimally allocate the layer bandwidth to match the diverse bandwidth requirements from the receivers? We formally investigate these problems in noncumulative layered broadcasting, where any subset of the layers can be used to reconstruct the video. We formulate both the optimal layer subscription problem for a receiver and the optimal layer bandwidth allocation problem for the sender. We show that the former has an effective solution, while the latter is computationally intractable. Three efficient heuristic algorithms are then proposed for the allocation problem, and simulation results show that all of them significantly outperform nonadaptive allocation algorithms.