Mobiele communicatie: reken maar!

Mobiele Mobiele communicatie: communicatie: reken reken maar! maar! Richard J. Boucherie Stochastische Operationele Research • Toen : telefooncentrale Æ Erlang verliesmodel • Nu : GSM • Straks : Video on demand • Toen : CPU Æ Processor sharing model • Nu: Internet TCP/IP – VoIP; Wireless LAN, Wifi • Straks : UMTS, WiMax en verder • Kwaliteit Å Æ Capaciteit Wiskundige modellen nodig voor definitie en berekening! 18-19 november 2005

Richard J. Boucherie – Mobiele communicatie: reken maar!

1

19

Capaciteit Capaciteit en en kwaliteit? kwaliteit? Hoe lang wil je wachten tot jouw SMS is verstuurd?

Hoe veel masten moeten er dan geplaatst worden?

Hebben we dan wel voldoende capaciteit om deze extra informatie te verzenden? 18-19 november 2005


2

Plannen Plannen GSM GSM netwerk netwerk GSM radio interface - basis Landelijke dekking Telfort

• 2 × 25 MHz ⇒ [ FDMA ] ⇒ 2 × 125 frequenties

• elke carrier ⇒ [ TDMA ] ⇒ 8 kanalen • totaal 8 × 2 × 125 = 2000 kanalen • planning op basis van frequenties (ruwweg 2 per antenne) • hergebruik frequenties • aantal beschikbare kanalen per basis station frequency reuse

8 ...

tijd 18-19 november 2005

200 kHz

frequentie

goedkoop


duur 3

17

Basis Basis model: model: enkele enkele cel cel Capaciteit

C E(ρ, C)

- Kwaliteit

TELEPHONE MS (G)MSC PSTN/ISDN

ρ

- Belasting

BTS

BSC

Relevante vraag: Hoe definieer je kwaliteit en capaciteit?

RADIO INTERFACE

Oplossing: Erlang verlies formule

ρC C!

E(ρ, C) = 1+ ρ +

ρ

2

2!

+ ...+

ρ

C

= kans op preciesC

C!

geblokkeerd

Maar hoe vinden we deze formule? Richard J. Boucherie – Mobiele communicatie: reken maar!

C 4

6

Markov Markov keten keten Stel C=3: maximaal 3 gesprekken

3 4

Toestand n = # gesprekken, n=0,1,2,3. Alle gesprekken gelijk, lengte onzeker

0

1 4

2 4

1 4

1

Proces dat hopt van toestand naar toestand: Markov keten Evenwichtsverdeling:

1 n! π (n) = 1 1 1+1+ + 2! 3!

kans om in toestand n te zitten op willekeurig moment ρC

vloeistof

C!

E(ρ, C) = 1+ ρ +

18-19 november 2005

ρ2

ρC

= kans op preciesC

+ ...+ C! 2! Richard J. Boucherie – Mobiele communicatie: reken maar!

1 4

2 4

1 4

1 4

2

1 4

3 4

3

1 1 4 4 1 2 π (1) = π (2) 4 4 1 3 π (2) = π (3) 4 4 π (0) + π (1) + π (2) + π (3) = 1

π (0) = π (1)

0!= 1 1!= 1 2!= 2×1 = 2 3!= 3×1×1 = 6

5

5

Blokkeringskansen Blokkeringskansen Kans dat gesprek geblokkeerd is ρC

Erlang verlies formule

kans op preciesC E(ρ, C) = = 2 C ρ ρ kans op minderdan C 1+ ρ + + ...+ 2! C! C!

dimensionering van GSM cellen , C  E( ,C) kwaliteit , E( ,C)  C capaciteit C, E( ,C)   belasting (aantal abonnee’s)

Erlang calculator: http://www.erlang.com/calculator/erlb/ Richard J. Boucherie – Mobiele communicatie: reken maar!

6

4

Erlang Erlang tabellen tabellen Belasting 8

15 kanalen komt overeen met 2 frequenties

Blokkeringskans 1%


7

3

Erlang Erlang verlies verlies formule formule ρC C!

E(ρ, C) = 1+ ρ +

ρ2 2!

+ ...+

ρC

=

kans op preciesC kans op minderdan C

C!

A.K. Erlang (1917) Erlang verlies formule fundamenteel voor dimensionering van telecommunicatiesystemen algemeen toepasbaar en in aangepaste vorm voor groter netwerk (meerdere masten) en voor andere diensten (Video on Demand)

Hoeveel capaciteit nodig?

video servers huishoudens met VoD

netwerk

18-19 november 2005


8

Model Model voor voor een een CPU CPU • CPU centrale processor in computer voert meerdere taken tegelijk uit • Iedere taak wordt geaccepteerd: meer taken = tragere afhandeling Taken delen processing kracht van CPU, en blijven actief tot ze zijn afgerond. CPU

18-19 november 2005


9

Processor Processor sharing sharing model model System karakteristiek Belasting

ρ Server

Belangrijkste eigenschap PS: alle taken delen enkele server Belangrijkste prestatie maat: vertraging

ET ( x) =

x 1− ρ

Processor sharing systeem is eerlijk

18-19 november 2005


10

6

Markov Markov keten keten Toestand n = # gesprekken, n=0,1,2,… Alle gesprekken gelijk, lengte onzeker, maar enkele server

λ

μ

λ

λ+μ

λ+μ

0

μ

λ+μ

1

λ+μ

Proces dat hopt van toestand naar toestand: Markov keten Evenwichtsverdeling:

⎛λ⎞ π (n) = ⎜⎜ ⎟⎟ ⎝μ⎠

⎛ λ⎞ ⎜⎜1− ⎟⎟ ⎝ μ⎠

kans om in toestand n te zitten op willekeurig moment vloeistof

18-19 november 2005

λ/μ EN = 1− λ / μ

μ

1/ μ ET = EN / λ = 1− λ / μ


λ+μ

2

λ+μ

π (0)

n

λ

μ λ+μ

λ

= π (1)

μ

λ+μ λ+μ μ λ π (1) = π (2) λ+μ λ+μ λ μ π (2) = π (3) λ+μ λ+μ π (0) + π (1) + π (2) + ....= 1 ⎛λ⎞ ρ = ⎜⎜ ⎟⎟ ⎝μ⎠ 11

Invloed Invloed van van onzekerheid onzekerheid •

aankomst en bedieningsproces deterministisch dan 100% belasting mogelijk

•

kleine fluctuaties in aankomsten, dan geheel ander gedrag

•

doorlooptijd groeit snel in belasting systeem

hier 100 maal ET ( x) =

x (1 − ρ )

vertraging is 10 maal bedieningstijd

ρ 18-19 november 2005

0.9

0.99


12

Twee Twee basis basis modellen modellen Processor sharing model

Erlang loss model Blocked call

Single server

C servers

Alle taken geaccepteerd

geen vertraging

sleutel eigenschappen: alle taken delen enkele server elke taak heeft eigen server sleutel prestatiematen: vertraging

fractie geblokkeerde taken eerlijk delen van de resources

18-19 november 2005


13

Voorbeelden Voorbeelden S1

Ack

S2 X ms

X ms R1

R2 L1

S0

240 ms

R3

L2 10 ms

Internet D1

time

D0

10 ms

5 MHz

D2

5 MHz

frequency 18-19 november 2005


14

UMTS UMTS UMTS Radio interferentie • frequency division duplex ⇒ [ FDMA ] ⇒ 2 × 12 frequencies

• 2 × 60 MHz

• each frequency ⇒ [ CDMA ] ⇒ ??? channels Vodafone UMTS dekking November 2005

• Processor sharing model: Frequenctie = processor gesprek/data file = taak • Vertraging data en gesprekskwaliteit voor spraak time

5 MHz

5 MHz

frequency

18-19 november 2005


15

Intensive Intensive Care Care capaciteit capaciteit Intensive Care Eenheid • Patiënten arriveren op willekeurige momenten • Patiënten hebben beschikbaar IC bed nodig • Patiënt blijft in IC bed tot voldoende hertsteld • Alle bedden bezet: patiënt naar ander ziekenhuis

• Erlang loss model: bed = server patient = taak • Blokkering • Wiskundig zelfde type probleem • Typisch voor wiskunde : vergelijkbare modellen in verschillende context • Essentie van systeem is van belang 18-19 november 2005


16

Internet: Internet: TCP/IP TCP/IP • Meerdere bronnen sturen data over Internet • Bron verhoogt zendsnelheid bij Ack verlaagt snelheid wanneer Ack niet (op tijd) • Alle bronnen gebruiken zelfde protocol • Processor sharing model:

S1 X ms

Internet = processor source file = taak • Vertraging

Ack

S2 X ms R1

R2 L1

S0

240 ms

R3

L2 10 ms

D0

10 ms

Internet D1

D2

• VoIP, een uitdaging voor de toekomst! 18-19 november 2005


17

Station Station Station • Treinen arriveren op willekeurige tijdstippen • Trein heeft perron nodig • Alle perrons bezet: trein wacht

• Erlang model: perron = server trein = taak capaciteit = aantal perrons fractie vertraagde treinen

18-19 november 2005


18

Wireless Wireless LAN LAN DCF: Distributed Coordination Function DIFS

DIFS

DATA SOURCE STATION

MEDIUM BUSY

6 5 4 3 2 1 0

26 25 24

MEDIUM BUSY

SIFS

ACK DESTINATION STATION

MEDIUM BUSY

MEDIUM BUSY

DIFS

DIFS

DATA OTHER STATION

MEDIUM BUSY

9 8 7 6 5 4

MEDIUM BUSY

3 2 1 0

•

CSMA/CA Carrier Sense Multiple Access met Collision Avoidance

•

collision: verdubbel contention window, herhaal maximaal 4 maal

•

DIFS Distributed InterFrame Space

•

SIFS Short InterFrame Space

•

Medium eerlijk gedeeld tussen gebruikers:

18-19 november 2005

Processor sharing model


19

Wireless Wireless LAN LAN BASIC ACCESS MODE 2.0 2.0 Simulation Simulation (CM-2:15 (CM-2:15 dB,0) dB,0)

expected flow flow transfer transfer time time expected

Vertraging 1.6 1.6

Simulation Simulation (CM-2:15 (CM-2:15 dB,1) dB,1)

1.2 1.2 Simulation Simulation (CM-2:15 (CM-2:15 dB,2) dB,2)

0.8 0.8 Simulation Simulation (CM-2:15 (CM-2:15 dB,4) dB,4)

0.4 0.4 Analysis Analysis (CM-2:15 (CM-2:15 dB) dB)

0.0 0.0 0.0 0.0

18-19 november 2005

0.2 0.2

0.4 0.4

0.6 0.6

0.8 0.8

0.2 offered 0.4data traffic 0.6 load0.8 offered data traffic load Belasting

1.0 1.0


20

Wiskunde Wiskunde of of Wiskunst Wiskunst “Terugbrengen tot de essentie van het probleem is de kunst van wiskundig modelleren” Wiskundige modellen maken het mogelijk om - in hanteerbare vorm sleuteleigenschappen van systeem te karakteriseren - te spelen met vereiste systeemeigenschappen - fundamenteel inzicht te verkrijgen in gedrag van het systeem Ook in jullie omgeving is wiskundig modelleren inzetbaar voor verbetering of optimalisatie Uitdagingen voor de toekomst: wiskunde leuk, nuttig en nog lang niet af!

18-19 november 2005


21

www.schoolsite.utwente.nl/masterclass 18-19 november 2005


22

www.schoolsite.utwente.nl/masterclass 18-19 november 2005


23

Mobiele communicatie: reken maar!

Recommend Documents