PUMA
Istituto di Scienza e Tecnologie dell'Informazione     
Anticaglia S., Barsi F., Bertossi A. A., Iamele L., Pinotti M. C. Efficient heuristics for data broadcasting on multiple channels. In: Wireless Networks, vol. 14 (2) pp. 219 - 231. Springer, 2008.
 
 
Abstract
(English)
The problem of data broadcasting over multi- ple channels consists in partitioning data among channels, depending on data popularities, and then cyclically trans- mitting them over each channel so that the average wait- ing time of the clients is minimized. Such a problem is known to be polynomially time solvable for uniform length data items, while it is computationally intractable for non- uniform length data items. In this paper, two new heuris- tics are proposed which exploit a novel characterization of optimal solutions for the special case of two channels and data items of uniform lengths. Sub-optimal solutions for the most general case of an arbitrary number of channels and data items of non-uniform lengths are provided. The first heuristic, called Greedy +, combines the novel characteri- zation with the known greedy approach, while the second heuristic, called Dlinear, combines the same characteriza- tion with the dynamic programming technique. Such heuris- tics have been tested on benchmarks whose popularities are characterized by Zipf distributions, as well as on a wider set of benchmarks. The experimental tests reveal that Dlinear finds optimal solutions almost always, requiring good run- ning times. However, Greedy + is faster and scales well when changes occur on the input parameters, but provides solutions which are close to the optimum.
URL: http://www.springerlink.com/content/101756/
DOI: 10.1007/s11276-006-9146-x
Subject Wireless Communication
Data broadcasting
Multiple channels
Heuristics
Flat scheduling
Average waiting time
Dynamic programming
C.2.1 Networks Architecture and Design
G.2.2 Graph Theory


Icona documento 1) Download Document PDF


Icona documento Open access Icona documento Restricted Icona documento Private

 


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional