Efficient heuristics for data broadcasting on multiple channels

The problem of data broadcasting over multiple channels consists in partitioning data among channels, depending on data popularities, and then cyclically transmitting them over each channel so that the average waiting 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 heuristics 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 characterization with the known greedy approach, while the second heuristic, called Dlinear, combines the same characterization with the dynamic programming technique. Such heuristics 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 running times. However, Greedy+ is faster and scales well when changes occur on the input parameters, but provides solutions which are close to the optimum. This work has been supported by ISTI-CNR under the BREW research grant. Stefano Anticaglia received the bachelor’s degree in Computer Science from the University of Perugia (Italy) in 2005. At present, he is a student in the master’s of Computer Science of the University of Perugia. Ferruccio Barsi received the doctor engineering degree from the University of Pisa, Italy, in 1969. From 1969 to 1992 he has been with he National Council of Research at the Istituto di Elaborazione dell’Informazione, Pisa. Since 1992, he is a Full Professor of Computer Science in the Mathematics and Computer Science Department of the University of Perugia, Italy. His main contributions are in the areas of computer architecture, error-control coding, systems diagnosis, VLSI design, digital signal processing, and computer graphics. He is currently involved in researches concerning network security and wireless communications. Alan Bertossi was born in London (England) in 1956. He got the Laurea Degree summa cum laude in Computer Science from the University of Pisa (Italy) in 1979. Afterwards, he worked as a System Programmer and Designer. From 1983 to 1994 he was with the University of Pisa as a Research Associate first, and later as an Associate Professor. From 1995 to 2002 he was with the University of Trento (Italy), as a Full Professor. Since 2002, he has been with the Department of Computer Science of the University of Bologna (Italy), as a Professor of Computer Science. His main research interests are the computational aspects of high-performance, parallel, VLSI, distributed, fault-tolerant, and real-time systems. He has published about 40 refereed papers on international journals, as well as several papers in international conferences, workshops, and encyclopedias. He has authored a book (on design and analysis of algorithms, in Italian) and he served as a guest coeditor for special issues of Algorithmica, Discrete Applied Mathematics, and Mobile Networks and Applications. He is a member of the editorial board of Information Processing Letters. His biography is included in the 1999 edition of Who’s Who in the World and in the 2000 edition of Who’s Who in Science and Engineering. Since 1999, he has been a scientific collaborator at the Institute of Information Sciences and Technologies of the Italian National Research Council (ISTI-CNR, Pisa, Italy). During 2001–2003, he was the national coordinator of an Italian research project on algorithms for wireless networks. Lucio Iamele received the bachelor’s degree in Computer Science from the University of Perugia (Italy) in 2004. At present, he is working at Noranet (Italy) as a system programmer and designer. M. Cristina Pinotti received the Dr. degree cum laude in Computer Science from the University of Pisa, Italy, in 1986. During 1987–1999 she was a Researcher with the National Council of Research at the Istituto di Elaborazione dell’Informazione, Pisa. From 2000–2003 she was an Associate Professor at the University of Trento. From 2004, she is a Full Professor at the University of Perugia. In 1994 and 1995 she was a Research Associate at the Department of Computers Sciences, University of North Texas, Denton, TX. In 1997 she visited the Department of Computer Science, Old Dominion University, Norfolk, VA (USA). Her research interests are in wireless networks, sensor networks, design and analysis of algorithms, data broadcasting, channel assignment problems, graph coloring, multiprocessor interconnection networks, design and analysis of parallel algorithms, parallel data structures, distributed computer arithmetic, residue number systems, VLSI special purpose architectures. She has published about 50 refereed papers on international journals, in international conferences and workshops. She has been a guest co-editor for special issues of Mobile Networks and Applications, Wireless Networks and Journal of Parallel and Distributed Computing. She is a member of the editorial board of International Journal of Parallel, Emergent and Distributed Systems.