BMS 0x2 Přístup k médiu Petr Hanáček Faculty of Information Technology Technical University of Brno Božetěchova 2 612 66 Brno tel. (05) 4114 1216 e-mail:
[email protected] Petr Hanáček
BMS0x Slide 1
Motivace • TC • CC downlink (Paging Channel, PCH) • CC uplink (Random Access Channel, RACH)
CC uplink
CC downlink
Petr Hanáček
TCn downlink
TCn uplink
BMS0x Slide 2
Motivace • Můžeme aplikovat metody přístupu k médiu, které známe z pevných sítí? • Například zkusme CSMA/CD – Carrier Sense Multiple Access with Collision Detection – Vysílej, jakmile je médium volné, poslouchej co jsi vyslal, zda nedošlo ke kolizi (původní metoda u IEEE 802.3)
• Problémy v bezdrátových sítích – Síla signálu klesá proporcionálně se čtvercem vzdálenosti – Vysílač aplikuje princip CS (Carrier Sense, poslouchání média) a CD (Collision Detection, detekce kolize), ale ke kolizi dojde až u příjímače – Může se totiž stát, že vysílač „neslyší“ kolizi, tj. CD nefunguje – CS nemusí fungovat v případě „skrytého terminálu“
Petr Hanáček
BMS0x Slide 3
Motivace – skryté terminály • Skryté terminály (nedetekovaná kolize) – – – –
A vysílá pro B, C neslyší A C chce vysílat pro B, C slyší “volné” médium (CS selhává) Vzniká kolize u B, A neslyší kolizi (CD selhává) A je “skrytý” pro C
• ALE případ, kdy se blokuje zbytečně: – – – – –
A
B
C
B vysílá pro A, C chce vysílat pro jiný terminál (ani A ani B) C musí čekat, protože CS říká, že médium je obsazené ALE A je mimo dosah rádiového pokrytí C, takže čekání je zbytečné Rušení vzniká na straně příjímajícího, ne vysílajícího! Říká se, že C je “exposed” pro B
Petr Hanáček
BMS0x Slide 4
Motivace – blízké a vzdálené terminály • Terminály A a B vysílají, C přijímá – Síla signálu klesá se čtvercem vzdálenosti – Signál terminálu B překrývá signál terminálu A – C neslyší A
A
B
C
• Pokud by C byl například arbiter, který rozhoduje o přidělení pásma jednotlivým terminálům, terminál B by pro něj překryl signál terminálu A • Jde například o vážný problém u sítí CDMA – je třeba precizní řízení výkonu! Petr Hanáček
BMS0x Slide 5
Přístupové metody SDMA/FDMA/TDMA • SDMA (Space Division Multiple Access) – Rozdělení prostoru do sektorů, použití směrových (sektorových) antén – Buňková struktura
• FDMA (Frequency Division Multiple Access) – Pro přenos přiřadí konkrétní frekvenci – Permanentní (např. rozhlasové vysílání), slow hopping (např. GSM), fast hopping (FHSS, Frequency Hopping Spread Spectrum)
• TDMA (Time Division Multiple Access) – Pro přenos přiřadí konkrétní frekvenci po určitý časový interval (timeslot)
• Metody, použité v předchozí přednášce pro multiplexování jsou nyní použity pro řízení přístupu k médiu! Petr Hanáček
BMS0x Slide 6
FDMA – schéma, příklad GSM
f 960 MHz
935.2 MHz
124
200 kHz
1 20 MHz
915 MHz
890.2 MHz
124
1
t
Petr Hanáček
BMS0x Slide 7
TDMA – schéma, příklad DECT • Uplink a downlink jsou na stejné frekvenci!
417 µs 1 2 3
11 12 1 2 3
downlink
Petr Hanáček
uplink
11 12 t
BMS0x Slide 8
TDMA - Aloha/slotted aloha • Mechanismus CD – Máš-li data, vysílej (na rozdíl od CSMA/CD, který napřed poslouchá) – Došlo-li ke kolizi, zkus to později – Slotted Aloha navíc používá časové sloty, vysílání musí vždy začít na hranici slotu
• Aloha
kolize
stanice A stanice B stanice C
• Slotted Aloha
t kolize
stanice A stanice B stanice C t Petr Hanáček
BMS0x Slide 9
DAMA - Demand Assigned Multiple Access • Aloha má využití kanálu pouze 18%, Slotted Aloha 36% (pro Poissonovo rozložení okamžiku příchodu paketů a délek paketů) • Rezervace může zvýšit využití na 80% – – – –
Dojde-li ke kolizi, vysílač si rezervuje nějaký budoucí timeslot Vysílání v tomto slotu je již bezkolizní Rezervace způsobuje větší zpoždění Typické schéma pro satelitní spoje
• Příklady rezervačních algoritmů: – Explicitní rezervace (Reservation-ALOHA) – Implicitní rezervace (PRMA) – Rezervující TDMA
Petr Hanáček
BMS0x Slide 10
Metoda DAMA: Explicitní rezervace •Explicitní rezervace (Reservation Aloha): – Střídání dvou režimů: » ALOHA režim: souboj o malinké rezervační sloty, kolizní » Rezervovaný režim pro přenos dat pomocí rezervovaných datových slotů (bezkolizní) » Pokud dojde ke kolizi, odpovídající datový slot se nevyužije – Je důležité, aby si všechny stanice držely konzistentní seznam rezervovaných slotů – Přesná časová synchronizace collision
Aloha
reserved
Petr Hanáček
Aloha
reserved
Aloha
reserved
Aloha
BMS0x Slide 11
t
Metoda DAMA: PRMA • Implicitní rezervace (PRMA - Packet Reservation MA): – Určitý počet slotů tvoří rámec, rámce se opakují – Stanice bojují o prázdné (nerezervované) sloty podle algoritmu slotted Aloha – Jakmile se stanici podaří získat slot, tento slot je automaticky rezervován stanici i v následujících rámcích, dokud má stanice data k vysílání – Jakmile je slot uvolněn (nebyl využit pro data), je opět předmětem souboje rezervace ACDABA-F
1 2 3 4 5 6 7 8
ACDABA-F
rámec1 A C D A B A
AC-ABAF-
rámec2 A C
A---BAFD
frame3 A
B A F
ACEEBAFD
frame4 A
B A F D
F
A B A
frame5 A C E E B A F D Petr Hanáček
time-slot
Kolize při pokusu o rezervaci t BMS0x Slide 12
Metoda DAMA: Rezervující TDMA • Princip: – Každý rámec se skládá z N minislotů a z X datových slotů – Každá stanice má svůj vlastní minislot a pomocí něj si může rezervovat k datových slotů (typicky X = N * k). – Nerezervované datové sloty mohou být využity podle principu round-robin
N minislotů
rezervace datových slotů
Petr Hanáček
N * k datových slotů
Např. N=6, k=2
Volné datové sloty mohou být využity podle principu round-robin
BMS0x Slide 13
MACA - Collision Avoidance • MACA (Multiple Access with Collision Avoidance) využívá krátké signalizační pakety pro předcházení kolizím – RTS (request to send): vysílač požaduje od přijímače právo vysílat krátkým RTS paketem, který vyšle před vysláním datového paketu – CTS (clear to send): jakmile je přijímač schopen přijímat, dává vysílači právo vysílat paketem CTS
• Signalizační pakety obsahují – Adresu vysílače – Adresu přijímače – Velikost paketu
• Varianty této metody je možno nalézt v IEEE 802.11 jako mechanismus DFWMAC (Distributed Foundation Wireless MAC) Petr Hanáček
BMS0x Slide 14
Příklad MACA • MACA odstraňuje problém skrytého terminálu – A a C chtějí vysílat pro B – A pošle RTS jako první – C musí čekat, dokud nedostane CTS od B
RTS CTS A
CTS B
C
• MACA odstraňuje problém „exposed“ terminálu – B chce vysílat pro A, C chce vysílat pro jiný terminál – nyní C nemusí čekat, protože je mimo dosah A a to pozná tak, že neslyší CTS od terminálu A A
Petr Hanáček
RTS
RTS
CTS B
C
BMS0x Slide 15
Varianta MACA: DFWMAC v IEEE802.11 sender
receiver idle
idle packet ready to send; RTS RxBusy ACK
time-out ∨ NAK; RTS
wait for the right to send
RTS; CTS
time-out ∨ bad_data; NAK
CTS; data
wait for ACK Pakety: ACK: positive acknowledgement NAK: negative acknowledgement RxBusy: receiver busy
Petr Hanáček
time-out; RTS
data; ACK
wait for data RTS; RxBusy Notace: AAA;BBB AAA: vstupní událost/přijatý paket BBB: odeslaný paket BMS0x Slide 16
Periodické vyzývání (polling) • Pokud existuje terminál, který slyší všichni, tento „centrální terminál“ (obvykle základnová stanice) může periodicky vyzývat ostatní terminály • Příklad: Randomly Addressed Polling – Základnová stanice oznámí terminálům připravenost – Terminály, které chtějí vysílat, vyšlou náhodné číslo (bezkolizně, například pomocí CDMA) – Náhodné číslo se chápe jako dočasná adresa terminálu – Základnová stanice vybere jednu hodnotu ze seznamu přijatých náhodných čísel (může dojít ke kolizi, pokud dva terminály zvolily stejné náhodné číslo) – Základnová stanice komunikuje s terminálem a po skončení, osloví následující terminál ze seznamu – Po oslovení všech terminálů ze seznamu se celý postup periodicky opakuje
Petr Hanáček
BMS0x Slide 17
ISMA (Inhibit Sense Multiple Access) • Momentální stav média je signalizován pomocí „obsazovacího tónu“ - “busy tone” – Základnová stanice signalizuje na downlinku, jestli je médium volné nebo ne – Terminály nesmí vysílat, pokud je médium obsazené – Terminály přistupují k médiu, až umlkne obsazovací tón – Základnová stanice signalizuje kolize a úspěšné přenosy pomocí obsazovacích tónů a potvrzení – Mechanismus použitý např. pro CDPD (USA, integrované do AMPS)
Petr Hanáček
BMS0x Slide 18
CDMA
Petr Hanáček
BMS0x Slide 19
CDMA • CDMA (Code Division Multiple Access) – Všechny stanice vysílají na stejné frekvenci, ve stejnou dobu a využívají celou šířku komunikačního pásma – Každá stanice má jedinečné náhodné číslo, ze kterého si vytvoří jedinečnou pseudonáhodnou sekvenci – Pokud přijímač zná toto náhodné číslo, může se „naladit“ na odpovídající vysílač
• Nevýhody: – Značná složitost přijímače – Signály všech vysílajících stanic by na anténě přijímače měly mít stejnou úroveň (pokud ne, přicházejí velké komplikace)
• Výhody: – Žádné frekvenční plánování – K dispozici je velké množství kódů pro různé stanice (typicky více než frekvencí u FDMA) – Teoreticky úplné odstranění interferencí Petr Hanáček
BMS0x Slide 20
Rozprostřené spektrum - motivace • Přenosový kanál: – AWGN (Additive white Gaussian noise), únik (fading) – Rušivé signály (impulsní, trvalé, interference) – Úmyslné rušení (jamming) (vojenské a bezpečnostní aplikace) » Kontinuální tón » Pulzní AWGN
• Sdílení jedné frekvence více stanicemi – Všichni vysílají současně na stejné frekvenci
• Systémy s rozprostřeným spektrem – Šířka pásma > Požadovaná šířka pásma (obvykle mnohem větší) – Demodulace: pomocí korelace
Petr Hanáček
BMS0x Slide 21
Rozprostřené spektrum - realizace • Dá se realizovat pomocí – – – –
Direct sequence Frequency-hopping Time-hopping Hybridní metody
• Na přijímací straně je třeba inverzní operace – Mapování musí být deterministické a snadno implementovatelné – Jsou třeba dodatečné synchronizační mechanismy
Petr Hanáček
BMS0x Slide 22
Model komunikačního systému s rozprostřeným spektrem
Petr Hanáček
BMS0x Slide 23
Typy SS sytémů (I) • Direct Sequence Spread Spectrum (DSSS)
Petr Hanáček
BMS0x Slide 24
Typy SS sytémů (II) • Frequency Hopping Spread Spectrum (FHSS)
Petr Hanáček
BMS0x Slide 25
Typy SS sytémů (III) • Time-Hopped (TH) system
Petr Hanáček
BMS0x Slide 26
Rozprostřené spektrum - vlastnosti • Vysoká tolerance proti neúmyslnému rušení / interferenci – Rušení jinými službami, únik
• Vysoká tolerance proti úmyslnému rušení – Rušičky je obtížné realizovat
• Snížení pravděpodobnosti odposlechu – Odposlech je obtížný bez znalosti pseudonáhodné sekvence
• Současný přístup několika stanic ke stejné frekvenci – Ortogonální sekvence
Petr Hanáček
BMS0x Slide 27
Vliv kvality signálu Kvalita kanálu
1
2
5
3
6
Úzkopásmové kanály
4 frekvence Úzkopásmový signál
guard space
Kvalita kanálu
1
Signál s rozprostřeným spektrem Petr Hanáček
2
2
2
2
2
Kanál s rozprostřeným spektrem
frekvence
BMS0x Slide 28
DSSS (Direct Sequence Spread Spectrum) I • XOR signálu s pseudonáhodnou posloupností (PN sekvence, chipping sequence) – Hodně chipů na bit (např. 128) znamenají mnohem větší šířku pásma tb
• Výhody
data
– Redukuje frekvenčně 0 1 závislý únik tc – V buňkových sítích » Základnové stanice používají stejné frekvence 01101010110101 » Je možno zároveň přijímat signál několika stanic » „Soft handover“
01101011001010
• Nevýhody – Je nutný přesný management výkonu
Petr Hanáček
tb: perioda bitu tc: perioda chipu
BMS0x Slide 29
XOR chipping sequence = Výsledný signál
DS/SS systém - Spreading
Petr Hanáček
BMS0x Slide 30
DS/SS systém - Despreading
Petr Hanáček
BMS0x Slide 31
DS/SS systém - schéma Rozprostřený signál
Vysílaný signál
Data X
modulátor
Chipping sequence
Nosná Vysílač
Korelátor Filtrovaný signál
Přijatý signál demodulátor Nosná
X
Data integrátor
Rozhodovací blok
Chipping sequence Přijímač
Petr Hanáček
BMS0x Slide 32
CDMA příklad I data A
1
0
Ad
1
klíč A klíčová sekvence A
0
1
0
1
0
0
1
0
0
0
1
0
1
1
0
0
1
1
data ⊕ klíč
1
0
1
0
1
1
1
0
0
0
1
0
0
0
1
1
0
0 As
signál A
V reálu jsou použity mnohem delší klíčové sekvence
Petr Hanáček
Ak
BMS0x Slide 33
CDMA příklad II As
signál A
data B
1
0
Bd
0
klíč B Klíčová sekvence B data ⊕ klíč
0
0
0
1 1 0
1 0
1 0
0
0
0
1 0
1
1
1
1
1
1
0 0 1
1 0
1 0
0
0
0
1 0
1
1
1 Bs
signál B
As + Bs
Petr Hanáček
Bk
BMS0x Slide 34
CDMA příklad III data A
1
0
1
1
0
1
As + Bs
Ak
(As + Bs) * Ak výstup integrátoru výstup komparátoru
Petr Hanáček
BMS0x Slide 35
Ad
CDMA příklad IV data B
1
0
0
1
0
0
As + Bs
Bk
(As + Bs) * Bk výstup integrátoru výstup komparátoru
Petr Hanáček
BMS0x Slide 36
Bd
CDMA příklad V As + Bs
nesprávný klíč K
(As + Bs) *K
výstup integrátoru výstup komparátoru
Petr Hanáček
(0)
(0)
?
BMS0x Slide 37
FHSS (Frequency Hopping Spread Spectrum) I • Diskrétní změny frekvence nosné – Posloupnost změn frekvence je určována pseudonáodnou posloupností
• Dvě verze – Rychlá - Fast Hopping: během jednoho bitu je použito několik frekvencí – Pomalá - Slow Hopping: několik bitů je na stejné frekvenci
• Vhody – Omezuje vliv frekvenčně omezeného úniku a úzkopásmovéo rušení – Jednoduchá implementace – V jednom okamžiku využívá malou část spektra
• Nevýhody – Není tak robustní jako DSSS
Petr Hanáček
BMS0x Slide 38
FHSS (Frequency Hopping Spread Spectrum) II tb data 0
1
f
0
1
1
t
td
f3
slow hopping (3 bits/hop)
f2 f1 f
t
td
f3
fast hopping (3 hops/bit)
f2 f1 t
tb: bit period
Petr Hanáček
td: dwell time
BMS0x Slide 39
FHSS (Frequency Hopping Spread Spectrum) III Úzkopásmový signál
Data modulátor
Vysílaný signál
modulátor
syntetizér Vysílač
Úzkopásmový signál
Přijatý signál
Data demodulátor
Posloupnost (hopping Sequence)
Petr Hanáček
Posloupnost (hopping Sequence)
demodulátor
syntetizér Přijímač
BMS0x Slide 40
Time-Hopping (TH) SS System
Petr Hanáček
BMS0x Slide 41
PN sekvence
Petr Hanáček
BMS0x Slide 42
PN Sekvence • Používají se Pseudo-noise (PN) sekvence pro – Pro vytvoření DS/SS signálu – Pro řízení frekvence nosné u FH/SS
• Někdy se nazývají pseudonáhodné (pseudo random) • Vlastnosti: – Vyváženost (Balanced property) » Relativní četnost jedniček a nul je stejná – Run-length property » Test běhů (run-length) je počet sousedních jedniček a nul » Délky běhů mají exponenciální rozložení – Vlastnost „Delay and Add“ » Stejný počet shod a neshod mezi PN sekvencí a posunutou PN sekvencí » Ochrana před vícecestným šířením Petr Hanáček
BMS0x Slide 43
Typy PN sekvencí • M-sekvence – Sekvence s maximální délkou
• Zlaté sekvence (Gold sequences) – Používají se především tam, kde je důležitý současný přístup několika stanic k médiu
• Jiné PN sekvence – Jiné pseudonáhodné generátory
Petr Hanáček
BMS0x Slide 44
M-sekvence • Maximum-Length Shift Register • Jsou generované pomocí LFSR (linear feedback shift register) na základě generujícího polynomu • Pro LFSR s m bity je nejdelší možná perioda PN sekvence rovná n=2m-1 • Sekvence s největší periodou (bývá jich více) se nazývá Maximum-Length Sequence nebo msekvence
Petr Hanáček
BMS0x Slide 45
LFSR - Linear Feedback Shift Registers • Shift registr (binárně) R = (rn, rn-1, ..., r1) • Tap sequence (binárně) T = (tn, tn-1, ..., t1) (zpětné vazby) • Generování bitu: – r1 se dá na výstup – Ostatní bity se posunou doprava – rn = TR mod 2 = t1r1 XOR t2r2 XOR ... XOR tnrn.
rn
rn-1 tn
Petr Hanáček
... tn-1
r1
key stream
t1
BMS0x Slide 46
Maximální perioda • Maximální perioda je 2n - 1. Dosáhneme jí, je-li polynom – T(x) = tn xn + tn-1 xn-1 + ... + t1x + 1
primitivní • Existují tabulky primitivních polynomů • Příklad:
–T(x) = x4 + x + 1 je primitivní r4
r3
r2
r1
key stream
T = (1, 0, 0, 1) Petr Hanáček
BMS0x Slide 47
Některé primitivní polynomy
The right-most bit represents the coefficient of the highest degree term, e. g., 1011011 ⇒ 1+x2+x3+x5+x6
Petr Hanáček
BMS0x Slide 48
Vlastnosti m-sekvencí • Cyklicky posunutá m-sekvence je opět m-sekvence • Vlastnost Shift-and-add – Součet modulo-2 m-sekvence a posunuté té samé m-sekvence dává jiný posuv té samé m-sekvence
• Obsahuje o jednu víc jedniček než nul – Protože (0,0,…,0) není povolený stav registru – Splňuje požadavek na vyváženost
• Pro každou m-sekvenci má 1/2k běhů délku k – Splňuje požadavek na test běhů
Petr Hanáček
BMS0x Slide 49
Zlaté sekvence • Vzniká jako součet modulo-2 mezi jednou sekvencí a posunutou verzí jiné sekvence
Petr Hanáček
BMS0x Slide 50
Porovnání SDMA/TDMA/FDMA/CDMA SDMA Idea
rozdělení prostoru na buňky/sektory
Terminály
v jedné buňce/sektoru může být aktivní pouze jeden terminál
Sdílení
buňková struktura, směrové antény
Výhody
velmi jednoduché, zvyšuje kapacitu na km² není flexibilní, antény jsou pevné
Nevýhody
Poznámka
použitelná pouze v kombinaci s TDMA, FDMA nebo CDMA
Petr Hanáček
TDMA
FDMA
CDMA
rozděluje vysílací čas na timesloty (podle požadavků nebo fixně) terminály sdílí frekvenci, ale mohou být aktivní pouze část času synchronizace podle času
rozděluje vysílací pásmo na oddělené kanály
dělí spektrum pomocí ortogonálních kódů
každý terminál má trvale přidělenu svou frekvenci
všechny terminály jsou aktivní současně, trvale, na stejné frekvenci
filtrování jednotlivých frekvenčních kanálů
pomocí detekce kódu
zavedená technologie, plně digitální, flexibilní je třeba ochranný interval (multipath), obtížná synchronizace standard v pevných sítích, společně s FDMA/SDMA i v mobilních sítích
zavedená technologie, jednoduchá, robustní není flexibilní, nešetří frekvence
flexibilní, netřeba frekvenční plánování, soft handover složitý přijímač, je třeba složité řízení výkonu
typicky kombinováno s TDMA (frequency hopping) a SDMA (frequency reuse)
komplikovaná, větší složitost, kombinuje se s TDMA/FDMA
BMS0x Slide 51
