Antonio Sassano (Università di Roma “La Sapienza”)

Progetto di reti digitali terrestri e cammini minimi

Seminario 1 – Il Problema

The technology: OFDM

• Decomposes a bitstream into slower parallel bitstreams

1 Megabit/s T streams of 1/T Megabit/s

• Modulates T orthogonal carriers

• One Symbol q bits (64QAM 6 bits)

Stream 1

Stream 2

Stream 3

Stream T

….

Symbols

“Frequency hopping”

Symbols

Features of OFDM• Orthogonal carriers overlap Spectral Efficiency = More bits per hertz

• “Frequency hopping” reduces the “fading” effect• But … orthogonality needs care

Multi-path effect

Same stream…Same symbol …… but delayed

Time

Inter Symbol Interference

• Delays destroy orthogonality• “Longer” symbols (low rate) help• .. But OFDM does even better

The Guard Interval

And here comes …. the magic

• OFDM adds a prefix to every symbol• If the guard interval is “longer” than delays Orthogonality can be restored

Inter Symbol Interference is avoided Service is improved

GUARD INTERVAL SYMBOL

GUARD INTERVAL SYMBOL

GUARD INTERVAL SYMBOL

GUARD INTERVAL SYMBOL

The Magic … of OFDM

• Two transmitters located in different sites• … using the same frequency (same carrier)• … transmitting the same content (same symbols)

ANALOG THECNOLOGY Interference No service

DIGITAL TECHNOLOGY Delayed symbols

If delays are smaller than Guard Interval ….. ….. OFDM guarantees a better service

“artificial multipath”GUARD INTERVAL SYMBOL

GUARD INTERVAL SYMBOL

6

Coverage of service area

C1

C5

C1C3

C7

C9

C11

C1

C9

C5

C3

C3

Border of service area

C3

Border of coverage

area for an

individual

transmitter

Classical Re-use Schema of the Analog Era Each transmitter uses a different frequency channel (Cx), acting

independently and having its own coverage area Re-use of channels is possible given sufficient geographical separation

Multi Frequency Networks (MFNs)

Source ITU: Nigel Laflin 2003

7

Coverage of service area

Border of service area

C1

C1

C1

C1

C1

C1

C1

C1

C1

C1

Border of coverage area

All transmitters of the network use the same frequency channel

The transmitters provide a common coverage area and can’t be operated independently – they must carry identical multiplex content

Single Frequency Network (SFN)

Source ITU: Nigel Laflin 2003

OFDM: Conclusions • Better spectral efficiency (more bits per Hz)• Better use of spectrum (SFN)• Resilience to “selective frequency fading”• Turns Multipath from “bad” to “good”

And in fact …. It will be the basic technology for:

• Digital Broadcasting• Wimax (WiBro)• LTE (Long Term Evolution of 3G)• … 4th generation (Anytime, Anywhere … )• Short Range (UltraWideBand)

…. No Jokes (I)

…. No Jokes (II)

Il Problema da Risolvere

Progetto di una (semplice) Rete OFDM(rete digitale terrestre SFN)

Si vuole servire in tecnologia digitale terrestre una specifica area geografica

L’area geografica viene rappresentata come una griglia di rettangoli di lato 96 secondi (di grado)

Ogni rettangolo della griglia è rappresentato dal suo baricentro: il testpoint

I siti di trasmissione sono anch’essi posizionati sulla “griglia”: ad esempio Roma Monte Mario

Ogni rettangolo della griglia è rappresentato dal suo baricentro: il testpoint

Sito candidato di Roma Monte Mario

Problema: Progetto di rete OFDMINPUT• Digital Terrain Model (milioni di testpoint in Europa)• Informazioni su posizione, quota e tipo di vegetazione• Siti Candidati (35.000 in Italia e Paesi confinanti)

Siti di trasmissione nel sud della Francia

SRTM DTM (Nasa)• 1 tp = 6x6 secondi• 1 tp ≈ 180x180 mt

• In ciascun testpoint la qualità del servizio è una funzione della:– Potenza ricevuta dai segnali serventi– Potenza ricevuta dai segnali interferenti

• La potenza ricevuta in un testpoint è una funzione dei seguenti fattori:– distanza– terreno (orografia, palazzi, vegetazione…)– guadagno dell’antenna del settore “visto” dall’antenna ricevente

Come verificare se un tespoint è “servito”

La propagazione elettromagnetica

• In ogni testpoint possiamo calcolare la potenza del segnale ricevutoda uno specifico trasmettitore (Monte Mario nell’esempio)

• Il calcolo viene effettuato utilizzando modelli di simulazione certificati dalla International Telecommunication Union (ITU)

• Il modello di simulazione tiene conto della distanza e dell’orografia• La potenza ricevuta dipende alla potenza emessa

15.024, ig

• Guadagno nominale

– per ogni trasmettitore i

– per ciascun settore j1,…,36

ijN

-50

-40

-30

-20

-10

01

2 34

56

7

8

9

10

11

12

1314

1516

171819

202122

2324

25

26

27

28

29

30

3132

3334

35 36

Serie1

124, iN

-50

-40

-30

-20

-10

01

2 34

56

7

8

9

10

11

12

13

1415

161718

192021

2223

24

25

26

27

28

29

30

31

3233

3435 36

15.024,24, ii gN

Potenza di emissione e diagramma di antenna

Massimizzare l’estensione del servizio ottenibile daisiti candidati sagomando opportunamente i diagrammi (modificando il guadagno)

La funzione obiettivo

Come verificare se un tespoint è “servito”

La Qualità del Servizio dipende dal rapporto tra:1. potenza del segnale utile 2. potenza del segnale interferente

Calcolo della qualità del servizio OFDM

Condizione di Copertura

QoSss

sPsPErf

IW

IW

)()(

)()(22

Detection window 224msec

0

10

20

30

40

50

60

70

80

90

100

Time (microsec)

Power

(dBW/m2)

PI(s), I2(s)

PW(s), W2(s)

• log-normal power-sum di segnali utili e interferenti

GUARD INTERVAL SYMBOL

GUARD INTERVAL SYMBOL

GUARD INTERVAL SYMBOL

47 113 155 203 333 393 450 515

Intervallo di guardia

PREDIZIONE DEL CAMPOELETTROMAGNETICO

• Potenza nominale Fit ricevuta– in ciascun testpoint t– da ciascun trasmettitore i

ALGORITMO DI PREDIZIONE DEL SERVIZIO OFDM

MODELLO DIGITALETERRITORIO

DATI NOMINALIDEI TRASMETTITORI

OTTIMIZZA IL GUADAGNO

• Potenza Pit ricevuta (effettiva)– in ciascun testpoint t– da ciascun trasmettitore i

git

Simulazione del Servizio

d(i,t)=7

Testpoint t

Come ottimizzare il guadagno? Definizioni …

,,, 3621 iiiid gggg Modifica del guadagno trasmettitore i

,,, 3621 iiiid NNNN Guadagno nominale (costante ) per il trasmettitore i (nelle 36 direzioni)

idid Ng Guadagno effettivo

itF Potenza nominale ricevuta nel testpoint t (costante)

),( tiiditit gFP Potenza nel testpoint t

Condizione di copertura

QoSss

sPsPErf

IW

IW

)()(

)()(22

Settore “visto” da t),( tid

tit

tsIi

ijit

tsWi

it gsbgsa ),(),(

)()(

Linearizzazione della condizione di copertura

Segnali utili e frequenze utili

• Ciascun segnale utile definisce una “finestra utile”• Ciascuna finestra definisce i segnali utili e interferenti (trasmettitori)• Due differenti finestre (segnali) possono coprire lo stesso testpoint

100

0102030405060708090

47 113 155 203 333 393 450 515 msec

Power

(dBW/m2)

S(t) = segnali utili ricevuti nel tespoint t

tit

tsIi

ijit

tsWi

it gsbgsa ),(

1

),(

1

11

)()(

1s 2s

tit

tsIi

ijit

tsWi

it gsbgsa ),(

2

),(

2

22

)()(

• IPOTESI SEMPLIFICATIVA #1 |S(t)|=1

“In ogni testpoint consideriamo un solo segnale utile (ad esempio: il più potente)”

Il modello combinatorio

TPt

TPtMgsbgsa

pp

t

ttit

tsIi

ijit

tsWi

it

TPt

tt

T

1,0

)1()()(

max

),(),(

• Evento elementare : testpoint coperto oppure no

• Vantaggio: popolazione del testpoint TPp

S = vetttori di incidenza degli insiemi di testpoint coperti

1,0 TP

S Formulazione Naturale

TRg 36,,1• Nota : il vettore è una variabile di decisione

• Il problema è di PL01 mista

0° 1

30° 4

60° 7

90° 10

120° 13

150°

14180° 19

210° 22

240° 25

270° 26

300° 31

330° 34

-10dB

-20dB

-40dB

0° 1

30° 4

60° 7

90° 10

120° 13

150°

14180° 19

210° 22

240° 25

270° 26

300° 31

330° 34

-10dB

-20dB

-40dB

NON AMMISSIBILE AMMISSIBILE

ANTENNE AMMISSIBILI VINCOLI sul GUADAGNO

Tutte le g sono ammissibili? NO!!

Discretizzazione in 36 setori d = {1, …, 36}

Limiti sul guadagno

Vincoli da settore adiacente

Il rapporto tra due settori adiacenti

non può superare un valore specificato

Vincoli di attenuazione globale

Il rapporto tra ogni coppia di settori

non può superare un valore (più grande)

UB

t

LB

ttd ggg ,

0)1( idadi gg

0° 1

30° 4

60° 7

90° 10

120° 13

150°

14180° 19

210° 22

240° 25

270° 26

300° 31

330° 34

-10dB

-20dB

-40dB

Diagrammi di antenna realistici (vincoli)

0' idbid gg

Il modello “nazionale” (di PL01 Mista)

Modello nazionale

TPt

dTRiggg

ddTRigg

dTRigg

TPtMgsbgsa

p

t

UB

idid

LB

id

idbid

diaid

ttit

tsIi

itit

tsWi

it

TPt

tt

1,0

36,,1,

36,,1',, 0

36,,1, 0

)1()()(

max

1'

)1(

),(),(

Perchè Nazionale?

Perchè non consideriamo l’effetto sui paesi confinanti

99.9% in Sardegna ma forte interferenza in Tunisia e Francia

A European Plan must be implemented!

90’s - DVB-T (Digital Video Broadcasting – Terrestrial) …. a new Technology for a European Standard OFDM-based

o 6817 carriers - 8k system [1705 carriers - 2k system]o 24 Megabit/s “payload” in 8MHz channelo 5 HQ TV programs use the band of 1 analog program

Chester Conference (1995) … Stockholm ‘61 last update Geneva Conference (June 2006) THE NEW PLAN (!) 2015 Analog TV “Switch off” (All Digital Scenario) “Switch off 2012” - European Common Proposal

NEED TO UPDATE THE OLD ANALOG PLAN - STOCKHOLM 1961

GE06: Digital (SFN) changes the rules

36

Two types of planning objects: Assignments and Allotments

Assignment is a “fully specified transmitter”

Allotment is a geographic area where:

• Site• Frequency• Antenna Diagram• ……

• A SFN using frequency f can be designed• The actual structure of the SFN is left open

• STOCKHOLM ‘61 had only assignments• Allotments ease a “flexible” approach to digital coverage

21

21

ITALIA

FRANCIA

Eint≤ Thrt

Allotment e Assignment definiscono aree protette(somma in potenza degli interferenti minore di una soglia )

Assignment alzano la soglia (nelle nazioni vicine)

Un canale può essere usato dalle due amministrazioni-Le reti digitali sono protette da allotment e assignment nazionali

- … e sono limitate da allotments/assignment stranieri

L’ “approccio a soglia”

Soglie per il Canale 8

38

Modello completo di OFDM Network Design

TPt

dtTRiggg

ddtTRigg

dtTRigg

TPtMgsbgsa

p

t

UB

idid

LB

id

idbid

diaid

ttit

tsIi

itit

tsWi

it

TPt

tt

1,0

36,,1),(

36,,1',),( 0

36,,1),( 0

)1()()(

max

1'

)1(

),(),(

ExTPtThrga t

tTRi

idit

)(

+

TP National testpoint set

Foreign testpoint setExTPExTPTPttsItsWtTR ),,(),()( Transmitters received in a testpoint

Maximize National Coverage

Power Sum below GE06 threshold

(Coordinated) Network Design Model

+

)(, 1,0

1,0

)(,

36,,1),(

36,,1',),( 0

36,,1),( 0

)(, )1()()(

max

1'

)1(

),(),(

tSsTPtw

TPt

tSsTPtw

dtTRiggg

ddtTRigg

dtTRigg

tSsTPtwMgsbgsa

p

st

t

stt

LB

idid

LB

id

idbid

diaid

tstit

tsIi

itit

tsWi

it

TPt

tt

ExTPtThrga t

tTRi

idit

)(

Large Scale (0,1) ProblemExample: Channel 8 VHF

a critical channel for Italy

145 Candidate Sites

5220 Variables

154.114 Coverage Constraints

41.034 Testpoints

14.007Active Foreign Testpoints

10.440 Feasibility Constraints

CPLEX does not even find a solution for the linear relaxation! Numerically instable (coefficients ait and bit have a huge range)

We find the optimal solution by massive pre-processingand …. row generation

Is the national Solution: (“ .. let’s forget about neighbors”)

Remove the power-sum constraints: a non-solution

But we do care about neighbors ….

and we use Optimization ….

Italy (total power sum) must arrive below 30 dB microvolt/m in the yellow areas

Step 1: Preprocessing and First Relaxation

ExTPtThrga t

tTRi

idit

)(

ExTPtThrg tid

Replace Power-Sum constraints by individual upper bounds

909 (out of 14.007) Power-sum constraints are violated

Step i: Generic “Row Generation”

Add the most violated power-sum constraints and solve …

Down to 540 violations

0

1

2

3

4

5

6

7

8

9

10

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

0

100

200

300

400

500

600

700

800

900

1000

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Algorithm Progression

# of violated Power-Sum Costraints

Maximum Power-Sum Violation

Final Step: Optimal Solution

81% of national population served … GE06 constraints met!