The Network Packing Problem in Terrestrial Broadcasting

Carlo Mannino (manninodis.uniroma1.it)
Fabrizio Rossi (rossidi.univaq.it)
Stefano Smriglio (smrigliodi.univaq.it)

Abstract: The introduction of digital technology all over Europe requires a complete and challenging re-planning of the actual terrestrial broadcasting system. In fact, in order to implement digital networks, transmitters and frequencies must be removed from the current analog networks. On the other hand, the service level (territory coverage) of analog networks must be preserved until the new networks can guarantee a sufficient coverage. Hence, a multi-network (and multi-objective) problem arises, referred to as Network Packing Problem (NPP), in which several networks (both analog and digital) sharing a common set of resources have to be designed. In this paper we report our experience in developing solution methods to NPP at RAI Way, the major Italian broadcaster. The RAI Way problem is particularly challenging both for the instances size and for the severe service requirements imposed by Italian law. We devise a two-phase heuristic for NPP. In the first phase, a target configuration is identified for each network by solving a single network optimization problem. In the second phase all networks are packed together so as to approximate Pareto optimal solutions minimizing the coverage losses from the target levels. The resulting tool is currently used at RAI Way to evaluate high-quality alternatives for the forthcoming deployment of digital equipments.

Keywords: terrestrial broadcasting, OFDM, antenna siting, frequency assignment, local search, interval graph, mixed integer programs

Category 1: Applications -- OR and Management Sciences (Telecommunications )

Citation: Operations Research, to appear

Download:

Entry Submitted: 10/21/2003
Entry Accepted: 10/21/2003
Entry Last Modified: 11/21/2005

Modify/Update this entry