Time offset optimization in digital broadcasting
- 作者：Carlo Mannino ; Fabrizio Rossi ; Antonio Sassano ; Stefano Smriglio
- 关键词：Digital terrestrial broadcasting ; Set covering ; Shortest paths ; Maximum feasible subsystem ; Irreducible inconsistent system
- 刊名：Discrete Applied Mathematics
- 出版年：2008
- 期刊代码：46_0166218x
- 类别：cp
- 出版时间：1 February 2008
- 卷：156
- 期：3
- 页码：339-351
- 文件大小：622 K
摘要
We investigate a planning problem arising in the forthcoming digital video broadcasting (DVB-T) system. Unlike current analog systems, the DVB-T standard allows a mitigation of the interference by means of a suitable synchronization of the received signals. The problem we describe in this paper is that of finding a time offset to impose to the signal emitted by each transmitter of the network, so as to maximize the network (territory) coverage (TOP, time offset problem). We show that, unlike related problems in which other transmitter parameters are taken as decision variables (e.g., emission powers or frequencies), TOP has a nice and algorithmically exploitable combinatorial structure. Namely, we introduce an exponentially sized set covering formulation of TOP, in which constraints are dynamically generated by a polynomial time oracle. We show the effectiveness of the approach through extensive experiments on the reference test bed of the Italian DVB-T Frequency Plan.