Přístupové metody bezdrátových sítí

Norma 802.11b a 802.11g definuje jako jednu ze základních přístupových metod k bezdrátovému médiu tzv. Distribuovanou koordinační funkci. Cílem tohoto článku je popsat přístupové metody tak, aby se mohl stát podkladem pro analýzu bezdrátových sítí 802.11e, u kterých je podporováno řízení kvality služeb.

---

Access Methods of Wireless networks

Abstract

Standards 802.11b and 802.11g defines Distributed Coordination function as one of the basic access method to the wireless media. Target of this paper is to mathematically analyze this access function in order that it can be taken as basis to further analysis of 802.11e access functions which supports Quality of Service systems.

---

Úvod

V dnešní době se v řadě případů využívá Wi-Fi sítí za zcela jiným účelem, než na jaký byly navrženy. Velmi často se totiž používají pro připojení domácností nebo i firem k síti Internet. S tím souvisí nasazování Wi-Fi při budování venkovních spojů, přičemž pro tento způsob využití nebyla tato technologie nikdy určena. Primární důvody jsou důvody cenové, protože díky velkému rozšíření se běžné ceny hardware pohybují řádově níže, než u sofistikovanějších řešení jako je například standard 802.16, WiMAX. S tím jde ruku v ruce také nižší kontrola datového toku. U sítí 802.11b a 802.11g je využito tzv. Distribuované koordinační funkce, která zajišťuje spravedlivý přístup k bezdrátovému médiu, ale nedokáže upřednostnit provoz s vyšší prioritou [1]. Norma 802.11e obsahuje vylepšení, která takové upřednostnění služeb může zajistit. Pro zefektivnění použitých metod je velmi důležitý jejich důkladný popis, díky kterému je možno vytvořit matematický model jako základ pro budoucí optimalizace.

Způsoby přístupu k bezdrátovému médiu

V případě, že je již bezdrátový klient asociován s přístupovým bodem, je připraven na vysílání a přijímání dat z konkrétní bezdrátové sítě. Jelikož bezdrátové sítě pracují se sdíleným médiem a v jedné bezdrátové síti mohou být až desítky stanic, je bezpodmínečně nutné zajistit řízení přístupu k tomuto médiu.

Norma 802.11 [2] definuje několik způsobů přístupu k bezdrátovému médiu. První metody neobsahovaly téměř žádné algoritmy, které by zajistily upřednostnění služeb, které to vyžadují. Metody přístupu k médiu se ale postupně vyvíjely a největších změn se dostalo při uzavření specifikace ve verzi 802.11e, která přidává ke stávajícím metodám další tak, aby co nejlépe vyhověly moderním požadavkům na řízení kvality služeb. Složení přístupových mechanizmů je zobrazeno na Obr. 1.

Obr. 1: Mechanismy přístupu k médiu na MAC vrstvě [2]

Tuto koordinační funkci musí povinně podporovat všechny stanice. Používá řízení přístupu založené na metodě mnohonásobého přístupu s detekcí nosné a detekcí kolizí, Carrier Sense Multiple Access with Collision Detection (CSMA / CD) nebo mnohonásobého přístupu s detekcí nosné a vyhýbáním se kolizím, Carrier Sense Multiple Access with Collision Avoidance (CSMA / CA). Pro vylepšení řízení přístupu mohou zprávy obsahovat informaci, která udává, po jakou dobu bude ještě stanice obsazovat přenosové médium [1][2][3].

Distribuovaná koordinační funkce pracuje při přístupu k médiu s tzv. oknem soutěžení, Contention Window. Jeho velikost je pro každou stanici a třídu provozu dáno intervalem CW_min a CW_max. Jedná se tedy o minimální a maximální hodnoty, kterých může velikost okna dosáhnout. Pokud má stanice data k odeslání, detekuje, zda je médium volné. Pokud ano, vygeneruje náhodné číslo v intervalu <0, w – 1>, kdy w je rovno CW_min. Poté začne od tohoto čísla odpočítávat. Během celého odpočtu neustále kontroluje, zda je médium volné. Pokud není, odpočítávání je zastaveno [2].

Pro lepší využití přenosového pásma a zmenšení pravděpodobnosti kolizí je veškerý čas rozdělen na diskrétní úseky. Ať již se jedná o mezirámcové mezery nebo časové úseky (timesloty) využité pro zasílání dat. Jak již bylo řečeno, při prvním pokusu o vysílání je voleno náhodné číslo z intervalu <0, w – 1>, kdy w = CW_min. V případě, že je dvěma nebo více stanicemi zvolena stejná hodnota, díky rozdělení úseku na sloty dojde ke shodnému odpočtu a následně ke kolizi. Kolize je detekována a řešena algoritmem, který přeruší vysílání a následně generuje tzv. backoff interval. Opět je zvoleno nové náhodné číslo, tentokrát však z většího intervalu, kdy w = 2ⁿ CW_min a n udává počet předchozích neúspěšných pokusů. Hodnota w může růst až k hodnotě CW_max. Odpočítávání poté pokračuje stejným způsobem.

Další problém, se kterým se lze u využití této přístupové metody setkat, je problém skrytého uzlu. Pokud je vyžadována komunikace bezdrátové stanice s centrálním přístupovým bodem, je nutno zaručit dostatečnou kvalitu signálu. Při komunikaci s ostatními bezdrátovými klienty, připojenými ke stejnému přístupovému bodu, jsou data vedena také přes něj. Z uvedeného vyplývá, že pro zcela dostupnou síť není nutné, aby existovalo dostatečně kvalitní spojení i mezi jednotlivými klienty. Původní filozofie standardu 802.11 počítala s využitím převážně v místnostech a budovách, kde je velmi vysoká pravděpodobnost, že bezdrátové stanice budou schopny detekovat případné obsazení média jednou z nich. V situacích, kdy je technologie standardu 802.11 použita také pro venkovní bezdrátové spoje, často za využití směrových antén, nelze zaručit, že stanice bude detekovat obsazené médium ve chvíli, kdy vysílá stanice jiná. Tento problém tedy nastává ve chvíli, kdy jsou od sebe klientské stanice natolik vzdáleny, že pro vysoký útlum nebo silnou směrovost vysílaného signálu, nejsou ostatní stanice schopny detekovat, že je médium obsazené a zahájí vysílání, což pochopitelně vede ke kolizím.

Distribuovaná koordinační funkce neobsahuje žádný mechanizmus pro prioritizaci přístupu k médiu. Všechny stanice, které jsou do bezdrátové sítě připojeny, soutěží o médium se stejnými vstupními podmínkami. Jedinou možností řízení kvality služeb je upřednostnění některých datových jednotek na úrovni jednotlivých klientských zařízení, to však nemůže zajistit jejich prioritizaci při přístupu k bezdrátovému médiu.

Další přístupové funkce nemohou být z prostorových důvodů v tomto článku popsány.

Distribuovaná koordinační funkce a její matematický popis

Základní popis distribuované koordinační funkce

Zřejmě největším problémem distribuované koordinační funkce jsou kolize. Stanice má sice snahu detekovat kolize i v průběhu vysílání, avšak tato detekce není vždy stoprocentní. Proto je každý odeslaný rámec potvrzen přístupovým bodem rámcem ACK. Celý proces je přehledně zobrazen na Obr. 2.

Obr. 2: Model soutěžení Distribuované koordinační funkce

Jelikož je pro soutěžení o médium, a při odpočítávání v zájmu synchronizace, využit model, který počítá s rozdělením na přesně určené časové úseky, timesloty, je pravděpodobnost kolize, zvláště při větším počtu stanic, poměrně vysoká. Například pro technologii 802.11b je CW_min rovno 31 a CW_max 1023. U technologií 802.11a a 802.11g je hodnota CW_min dokonce jen 15. Není sice příliš pravděpodobné, že by všechny stanice počaly vysílání ve stejném časovém úseku, ale i tak je tato pravděpodobnost poměrně vysoká. Zvláště proto, že vysílání rámců jiných stanic může pokrýt poměrně dlouhý časový úsek. Poté již postačí, aby každá ze stanic, které doposud nevysílaly, započaly proces vysílání datového rámce právě v tomto okamžiku. Obě stanice po skončení vysílání vygenerují backoff z poměrně malého intervalu a obě jej započnou odpočítávat naráz.

Základní model pravděpodobnosti kolize pro DCF

Nejprve je nutno zavést pravděpodobnostní model pro jednu stanici a poté jej rozšířit. Každá stanice se může nacházet v jednom ze tří stavů:

• Stanice je v klidu, nemá data k odvysílání.
• Stanice má data k odvysílání a čeká na uvolnění média.
• Stanice má data k odvysílání a vysílá.

Pokud vyloučíme problém skrytého uzlu, ke kolizi může dojít jen přesně při přechodu stanice do stavu třetího.

Mějme nenulovou pravděpodobnost p_v, která udává, že na vstup bezdrátové stanice přijde datový rámec. Předpokládejme, že se tato pravděpodobnost nemění v čase a že je tedy v každém okamžiku stejná.

Nyní se zabývejme případem, kdy již datový rámec na vstup bezdrátové stanice přišel. V tomto případě čeká bezdrátová stanice, až bude médium volné a poté zvolí velikost intervalu odpočítávání (backoff interval) z rozmezí <0; W₀>, kdy W₀ = CW_min. Tento případ uvádíme za předpokladu, že na vstup bezdrátové stanice již přišel datový rámec k odvysílání. V takovém případě je pravděpodobnost vygenerování rovna 1. Pokud nedojde ke kolizi, je rámec odvysílán, pokud ano, je vygenerováno w z nového intervalu.

Analytické modely [5][6] distribuované koordinační funkce většinou vycházejí z předpokladu, že pravděpodobnost kolize p_k je nezávislá na počtu předchozích neúspěšných pokusů o odvysílání. Poté pravděpodobnost, že ke kolizi nedojde, je logicky, rovna 1 – p_k. Podle těchto předpokladů lze vytvořit jednoduchý pravděpodobnostní model distribuované koordinační funkce, který je zobrazen na Obr. 3.

Obr. 3: Základní pravděpodobnostní model distribuované koordinační funkce

Pravděpodobnost kolize je pravděpodobnost, že si dvě a více na sobě nezávislých bezdrátových stanic zvolí ve stejnou chvíli stejnou velikost okna odpočítávání, případně že stanice, která si volí velikost okna, zvolí hodnotu, na které se nachází jiná stanice během odpočítávání.

Bianchiho model

Bianchi ve svém díle [5] uvádí následující:

Při každém pokusu o vysílání, bez ohledu na počet předchozích pokusů, pravděpodobnost kolize každého z paketů je konstantní a nezávislá.

Bianchi dále zavádí několik proměnných. Proměnnou W určující aktuální maximální možnou velikost intervalu odpočítávání a m, která udává tzv. maximum backoff stage, tedy maximální stupeň velikosti okna intervalu odpočítávání. Jak již bylo řečeno výše, velikost intervalu odpočítávání je shora omezena hodnotou CW_max. Z výše uvedeného vyplývá vztah

(1)

Na základě tohoto předpokladu konstruuje Bianchi Markovský model vycházející ze soustavy rovnic

(2)

První rovnice určuje pravděpodobnost, že v každém časovém úseku bude interval odpočítávání snížen o jedna. Pokud vycházíme z úvahy, že model odpovídá pouze situaci, kdy je médium volné, je pravděpodobnost tohoto jevu rovna jedné. Druhá rovnice vychází z předpokladu, že stanice právě ukončila úspěšné vysílání a volí velikost intervalu odpočítávání z rozmezí <0; W₀ - 1>, kdy W₀ odpovídá hodnotě CW_min. Třetí a čtvrtá rovnice popisují případ, kdy dojde ke kolizi, přičemž čtvrtá rovnice zajišťuje speciální případ, kdy již nelze interval odpočítávání zvětšovat, protože došlo k dosažení maximální hodnoty m.

Na základě těchto rovnic poté Bianchi vytváří Markovský řetězec, který je zobrazen na Obr. 4.

Obr. 4: Bianchiho Markovský řetězec popisující interval odpočítávání [5]

Model, který navrhl Bianchi, velmi usnadňuje a zjednodušuje popis celého systému distribuované koordinační funkce a dovoluje vytvoření poměrně přesného analytického modelu, který distribuovanou koordinační funkci popisuje a pomocí kterého lze s poměrně velkou přesností simulovat chování systému, který ji používá. Jak již bylo řečeno, model vychází z předpokladu, že pravděpodobnost kolize je v každé fázi a bez ohledu na počet předchozích kolizí stejná.

Tento předpoklad ovšem není zcela přesný. Velikost okna je při prvním pokusu o vysílání volena z poměrně malého intervalu. Vycházejme z předpokladu, že se příležitosti k vysílání chtějí uchopit dvě stanice naráz a jedná se o první pokus, tedy o stav, kdy ještě při vysílání konkrétních datových jednotek ke kolizi nedošlo. Pravděpodobnost kolize v takovém případě prudce stoupá.

Stále však musí být splněna podmínka, že stanice vygenerují hodnotu intervalu odpočítávání současně. Ani pravděpodobnost tohoto jevu ovšem není malá, zvláště v situaci, kdy je přenosové médium více vytíženo. Předpokládejme, že první pokus o vysílání bude proveden v době, kdy je médium obsazeno rámec jinou stanicí. Vše názorně demonstruje Obr. 5.

Obr. 5: Generování intervalu odpočítávání pro dvě stanice ve stejné chvíli v případě, že datová jednotky dorazí na linkovou vrstvu v rozdílných časových úsecích

V takovém případě stanice vyčkají na uvolnění média a po uplynutí intervalu DIFS vygenerují interval odpočítávání a začnou odpočítávat. Jelikož se jedná o první pokus o vysílání a interval odpočítávání je volen z malého intervalu, již při dvou stanicích, které jej vygenerují současně, je pravděpodobnost kolize relativně vysoká.

Analýza pravděpodobnosti kolize

Předpokládejme, že stanice již zahájily proces vedoucí k vysílání, tedy vygenerovaly paket. Ve chvíli, kdy dojde k uvolnění média, obě vygenerují interval odpočítávání w, od kterého budou odpočítávat. Toto číslo volí náhodně z intervalu <0, CW_min>, jehož velikost je udána proměnnou W. Pravděpodobnost vygenerování konkrétního čísla w je rovna

(3)

Pravděpodobnost, že druhá stanice zvolí náhodné číslo m shodné s n a dojde ke kolizi, je vyjádřena vztahem

(4)

Za předpokladu, že se jedná o nezávislé jevy, můžeme konstatovat, že pravděpodobnost jevů p_u a p_u je shodná. Proto lze celý vztah zjednodušit na podobu stejnou jako ve (3).

(5)

V reálném provozu ovšem nelze počítat jen se dvěma stanicemi. V bezdrátové síti mohou být těchto stanic až desítky. Pravděpodobnosti kolize v případě, že každá ze stanic v síti bude chtít vysílat, lze odvodit následujícím způsobem:

Jelikož je rychlost odpočítávání vždy shodná, kolize nastane v případě, že minimálně dvě, tedy dvě a více stanice zvolí ve stejný okamžik stejnou hodnotu w, od které budou odpočítávat před započetím vysílání. Nejprve je nutné stanovit množinu všech jevů. Pokud je počet stanic roven n, vybíráme n-tice hodnot z intervalu W. Množina všech jevů tedy bude odpovídat

(6)

Dalším logickým krokem je výběr množiny jevů, při kterých dojde ke kolizi. To je ovšem dosti problematické, protože najednou může více stanic, než jen dvě, zvolit stejnou hodnotu intervalu W. V případě počtu stanic rovného čtyřem a větším, může být dokonce kolize vícenásobná, protože lze vytvořit větší počet dvojic se stejnou hodnotou w. Proto je v tomto případě mnohem jednodušší zjistit množinu všech případů, při kterých ke kolizi nedojde. To lze poměrně snadno určit pomocí následujícího vztahu

(7)

V tomto případě již jsou k dispozici všechny podklady, aby bylo možno určit pravděpodobnost, že nedojde ke kolizi p_nk. Vztah pro p_nk lze získat pomocí podílu počtu prvků těchto množin, tedy

(8)

Pravděpodobnost kolize je jev opačný, pro p_k tedy platí, že

(9)

Ještě jednou je třeba pro úplnost dodat, že n určuje počet stanic, které začínají odpočítávat ve stejný okamžik a w udává velikost intervalu <0, CW_min>. To vše platí pro případ, že se jedná o první pokus o vysílání.

Z výše uvedeného lze vyvodit, že ač je v již zveřejněných modelech [5][6] počítáno se stejnou pravděpodobností kolize, bez ohledu na počet předchozích neúspěšných pokusů o vysílání, není tento postup zcela přesný. Pokud se pokusíme pravděpodobnost kolize vyjádřit číselně, dojdeme například u normy 802.11g, kde je velikost CW_min rovna 15, již pro 5 stanic k 50% pravděpodobnosti, že dojde ke kolizi. Oproti tomu, pokud by se u všech těchto stanic jednalo o pátý pokus o vysílání, a interval odpočítávání by byl volen z intervalu <0; 480>, byla by pravděpodobnost kolize jen pouhá 2%.

V obou případech se jedná o extrémní příklady, které by v praxi nastaly zajisté jen velmi zřídka. Díky odvozenému vztahu pro pravděpodobnost kolize (9) lze ale konstatovat, že předpoklad, který udává pravděpodobnost kolize nezávislou na počtu předchozích pokusů o vysílání, není zcela přesný. Celý problém je názorně ilustrován hodnotami zobrazenými v Tab. 1 a zobrazen graficky na Obr. 6.

Pomocí výše uvedené metody lze snadno zjistit pravděpodobnost kolize v případě, že všechny stanice, připojené k bezdrátovému přístupovému bodu, volí ze stejné velikosti intervalu odpočítávání. S přihlédnutím k modelu, který je zobrazen na Obr. 3 v kapitole je ale nutné pro popis celého systému vyhodnotit i další vlivy, které mají na pravděpodobnost kolize vliv. Je to zajisté pravděpodobnost, s jakou přicházejí datové jednotky na linkovou vrstvu za účelem jejich odvysílání.

Tab. 1: Pravděpodobnost kolize v závislosti na počtu stanic v systému a velikosti okna soutěžení

Obr. 6: Závislost pravděpodobnosti kolize na velikosti okna soutěžení pro různé počty stanic

Závěr

V době, kdy byla k dispozici jen Distribuovaná koordinační funkce a Centralizovaná koordinační funkce, nebylo možné u sítí 802.11 jakékoliv řízení datového toku na linkové vrstvě. Centralizovaná koordinační funkce garantovala spravedlivý přístup k médiu, ale velmi nehospodárně. Distribuovaná koordinační funkce také v podstatě zajišťuje statisticky spravedlivý přístup s tím, že dokáže s přenosovým pásmem hospodařit mnohem hospodárněji. Již ale neexistoval způsob, jak upřednostnit provoz, který by to svým charakterem vyžadoval.

S příchodem normy 802.11e doznaly přístupové mechanismy k bezdrátovému médiu řady změn. Hybridní koordinační funkce umožňuje přístup k médiu řízený přístupovým bodem, vylepšená funkce přístupu k distribuovanému kanálu rozšiřuje distribuovanou koordinační funkci o možnost zavést kategorie přístupu a soutěžení o médium nejen na úrovni sítě, ale i každé bezdrátové stanice jako takové.

Po zmapování těchto mechanizmů spočívala další práce v analýze existujících metod popisu distribuované koordinační funkce. Byla analyzována pravděpodobnost kolize v systému a vytvořeny vztahy, které by měly tuto pravděpodobnost predikovat. Bylo ukázáno, že již při malém počtu stanic, které v jeden okamžik volí velikost intervalu odpočítávání, je pravděpodobnost kolize velmi vysoká.

Další prací, která naváže na již získané poznatky je ověření dosažených vztahů simulací, navržení modelu pro simulaci vstupního datového toku a také analýza pravděpodobnosti kolize v případě, že stanice generují interval odpočítávání v různých časových úsecích.

Poděkování

Tento článek vznikl za podpory projektu GAČR 102/06/1569.

Literatura

[1] GEIER, J., 802.11 Medium Access Methods, Wi-Fi Planet, JupiterOnlineMedia, 2002, http://www.wi-fiplanet.com/tutorials/article.php/1548381
[2] IEEE: Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications, 2007, [approved standard]
[3] IEEE: Part 3: Carrier Sense Multiple Access with Collision Detection (CSMA/CD) Access Method and Physical Layer Specifications, 2002 (R2005), [online standard], http://standards.ieee.org/getieee802/802.3.html
[4] PUŽMANOVÁ R.: Schválena specifikace pro hlas do WiFi, 2005, Lupa.cz, ISSN 1213-0702, [online], http://www.lupa.cz/clanky/schvalena-specifikace-pro-hlas-do-wifi/
[5] BIANCHI, G., Performance Analysis of the IEEE 802.11 Distributed Coordination Function, IEEE Journal on Selected Areas in Communications, 2000, ISSN 0733-8716
[6] ZHANG, L.T., ZHANG, J., HUANG, B., A New Modeling and Delay Analysis of IEEE 802.11 Distributed Coordination Function, Ubiquitous Intelligence and Computing, 4th International Conference, UIC 2007, Hong Kong, China, July 11-13, 2007. Proceedings. ISBN: 978-3-540-73548-9, ISSN 1611-3349. Dostupné také online http://www.springerlink.com/content/m8nt562391423qxl/