AD-HOC HÁLÓZATOK
2011. május 19., Budapest
Ad hoc hálózatok • mi az ad hoc hálózat? • más elnevezések: multihop, önszervező, infrastruktúra nélküli • A) mozgó készülékek által létrehozott hálózat • a készülékek adattovábbítást is végeznek • önszervező és átszervező • folyamatosan változó topológia • B) mobil készülékek + könnyen mozgatható, de a hálózat működése közben általában fix hozzáférési pontok • önszervező • a hozzáférési pontok végeznek adattovábbítást: -> cellás hálózathoz hasonló
Ad hoc hálózatok • csomópontok: mobilok és a hordozható hozzáférési pontok • összeköttetések: azon csomópontok között van, amelyek között a csatorna csillapítása p kisebb egy gy küszöbnél
Ad hoc hálózatok • alkalmazások • katonai kommunikáció („smart dust”), űrkutatás • készenléti szervek szervek, katasztrófaelhárítás • nagy tömeget vonzó események • otthoni hálózat (intelligens ház, szg. hálózat + telekomm.+ szórakoztató elektronika + házi automaták), ) járműbeli hálózat ((VAN), ) testen viselt hálózat (BAN) ( ) • érzékelő hálózatok, kis sebességű hálózatok • infrastruktúra elérése, utolsó néhány csomópont • stb.
Ad hoc hálózatok • főbb problémák: • fizikai réteg: teljesítmény takarékosság, változó topológia, asszimetrikus linkek • adatkapcsolati réteg: közeghozzáférés-vezérlés: nincs központi egység ami felügyeli, elosztott módszer kell • hálózati réteg: topológia felderítés, frissítés, útvonalválasztás változó topológián • minden réteg: biztonsági kérdések, QoS biztosítása
Ad hoc MAC • többszörös hozzáférés: • FDMA: nincs központi egység ami a frekvencia kiosztást felügyeli, minden frekvenciát hallgatni kellene, vagy külön vezérlő sávot kell létrehozni -> ezt is meg kell osztani • TDMA: ez OK, szervezett módon: központi egység (master) kell az időrések elosztására (Bluetooth filozófia), ezt ki kell választani, masterek közti kommunikációban meg kell egyezni, gond a hálózatban az időrés-szinkronitást elérni; vivőérzékeléses eljárások: OK, de vannak problémák • CDMA: ez OK, a kódok kiosztása a gond • duplexitás: TDD (FDD lehet, ha vannak hozzáférési pontok vagy masterok, amik a két frekvencia között „fordítják” az adatfolyamot)
Ad hoc MAC • problémák vivőérzékeléses véletlen hozzáférés alkalmazásánál • rejtett terminál: A ---- B ---- C : A ad Bnek, C nem hallja, ő is adást kezdeményezhet, ütközés B-ben • kitett (exposed) terminál: A ---- B ---- C ---- D : B ad A -nak, C hallja nem ad D nek, pedig nem lenne ütközés, kihasználtság romlik • elfogás (capture): két terminál ad egyszerre valakinek, valakinek a nagyobb teljesítménnyel vett adást az ütközés ellenére is venni tudja • nem csakk ad-hoc d h háló hálózatban tb
Ad hoc MAC • a MAC minősítése: • késleltetés: • kihasználtság, kihasználtság throughput: a csatorna kapacitásának hány százalékán megy adat • igazságos (fairness): prioritásnak megfelelő kapacitás jusson • stabilitás: forgalom f ingadozásokat elviselje • robosztusság a fading ellen • ki fogyasztás • QoS, multimédia támogatás (prioritások, scheduling)
Ad hoc MAC • CSMA alapú MAC protokollok • rejtett és kitett terminál problémája • ütközés detektálás: nem megy, megy adás közben venni sem lehet (időben duplex ált.), a vevő nem tud szólni hogy ütközés történt • adás végén csak az ack. hiánya jelezné az ütközést: kapacitás pazarlás • ütközés elkerülési/érzékelési / megoldások kellenek • foglaltságjelzés egy másik frekvenciasávban (busy tone) • „kézfogásos” eljárások
Ad hoc MAC • kézfogásos módszerek • aki küldeni akar, egy rövid RTS csomagot küld a címzett azonosítójával • mindenki, mindenki aki veszi az RTS-t RTS t, nem ad • a címzett az RTS vétele után válaszként CTS-t küld • akik ezt veszik, azok se adnak • a CTS megkapása után a küldő megkezdi az adást
Ad hoc MAC • EY-NPMA (Elimination-Yield Non-preemptive Priority Multiple Access) • Hiperlan 1 • adó 1700 bitidőig figyeli a csatornát csatornát, ha üres üres, azonnal adni kezd • ha van rajta adás, megvárja a végét, majd megkezdődik a csatornahozzáférési periódus • prioritások: minden csomagra eddigi várakozás alapján, maguk számolják, 0 H-1 prioritási szint, 0 a legnagyobb • 1. prioritizálási fázis: mindenki a saját prioritásának megfelelő időrésig (256 bitidő egyenként) ké t) hallgatja h ll tj a csatornát, t át ha h valaki l ki adott, d tt kiszáll ki áll é és megvárja á j a kö köv. versenyzési fázist; ha nem, ad egy prio börsztöt, mivel a nagyobb prioritásúak hamarabb adnak, csak a legnagyobb prioritásúak mennek tovább
Ad hoc MAC • EY-NPMA (Elimination-Yield Non-preemptive Priority Multiple Access) • 2. versenyzési fázis • 2.a: elimináció: mindenki egy geo eloszlású számú időrésnyit ad (256 bitidő hosszú rések), utána hallgatja a csatornát, aki hallja hogy még más ad, abbahagyja és a köv ciklusban próbálkozik: akik a legnagyobb számú rést sorsolta, az megy tovább (több is lehet) • 2.b: „termés” (yield): geo eloszlású véletlen számú időrést hallgatnak (64 bitidő hosszúak), ha addig más nem kezd adni, akkor küld egy csomagot
Ad hoc MAC példa
Ad hoc MAC
Ad hoc MAC •csomag gp prioritási szintek: felhasználó p prioritástól ((high, g , low)) és csomag g hátralévő élettartamától függ (NMRL = Normalized MPDU Residual Lifetime) • legnagyobb prioritású csomag (0): high user priority és kisebb mint 10 msec NMRL •legkisebb prioritású csomag (4): high user prioritás és több mint 80 msec NMRL NMRL, alacsony user prioritás és több mint 40 msec NMRL • 0 prioritású csak high user prioritású felhasználó csomagja lehet
Ad hoc MAC • FPRP (Five Phase reservation Protocol) • TDMA • szinkronizáció van (GPS) • a protokoll ciklusaihoz képest a topológia lassan változik • a csp.-k ütközést tudnak észlelni •minden csp.-nek egyedi azonosítója van
Ad hoc MAC
RS: az azonos sorszámú IS –ért lehet versenyezni itt, a következő keretek mindegyikében megkapja a győztes minden RS valahány valahány, 5 fázisból álló figlalási ciklust tartalmaz
Ad hoc MAC • RR fázis: aki foglalni szeretne, p valószínűséggel küld egy RR csomagot, t a többi h hallgat ll t • CR (Collision Report): ha egy node ütközést észlelt az RR fázisban, CR csomagot küld, ha az eredeti adó nem hall CR CR-t, t, feltételezi hogy kérése sikeresen átment és ő lesz az adó (TN), rejtett terminál megoldva itt • RC (Res (Resv. Confirmation): Confirmation) TN itt RC csomaggal megerősíti a foglalását (többi a környezetében ebből tudja, hogy övé az adott időrés) • RA ((Resv. Acknowledgement): g ) mindenki, aki RC-t hallotta, küldi. Ha TN nem vesz ilyet, akkor tudja hogy el van vágva a többitől, ill a 2 hopra levők is tudják, bejegyzik az időrés foglaltságát • P/E fázis (Packing/Elimination): minden 2 hopra levő küld akik RA t hallják, de RC –t nem, küld egy P csomagot, akik ezt hallják, de a többit nem, jobb eséllyel versenyezhetnek az időrésért, a foglalási valószínűségüket igazítják ehhez, ehhez valamint Tn adja deadlock feloldásához
Ad hoc routing • cél: az ad hoc hálózat két tetszőleges csomópontja között továbbítani csomagokat, lehetőleg valamilyen szempontból optimálisan • proaktív algoritmusok (táblázat alapú): az útvonalak az átvitel előtt ki vannak számolva, minden csp. táblázatokban tárol routing információt (milyen célcím esetén melyik a next hop, ahová küldeni kell), ezeket frissíteni kell a topológia változásakor, a frissítésnek az egész hálózatban meg kell történnie • reaktív algoritmusok (forrás által kezdeményezett, vagy igény szerinti útvonalválasztás): a forrás kezdeményez egy útvonal keresési folyamatot a hálózatban, adás előtt. ha az útvonal megvan, útvonal-fenntartási folyamat, amíg kell az útvonal • hierarchikus útvonalválasztási algoritmusok
Ad hoc routing • táblázat alapú p algoritmusok: g • DSDV (Destination-Sequenced Distance-Vector routing) • útvonal táblázatok minden csomópontban: lehetséges célhoz tartozó útvonalhoz hova kell küldeni küldeni, + ugrások száma száma, + sorszám • táblázat frissítések ha valami történik: teljes (ritkán), frissítések • a sorszám azt mutatja, hogy mennyire friss a bejegyzés • a legfrissebb útvonalat választják
Ad hoc routing • CGSW ((Clusterhead Gatewayy Switch Routing) g) • a mobilok csoportokra, klaszterekre osztva • minden csoportnak van „feje”, ezt a mobilok egy elosztott algoritmussal választják • átjáró csomópontok: amik egyszerre több csoport vezetőt is el tud érni, csomagok útja: mobil-fej-átjáró-fej stb. • kétféle táblázat minden mobilban: klaszter vezető táblázat: minden lehetséges célhoz a legjobb úton a következő klaszter fej, útvonalválasztási tábla: a következő ugrás egy bizonyos cél eléréséig • tábla változások üzenetszórva • kap egy csomagot: klaszte vezető táblázatból kikeresi hogy melyiknek küldje, utána routingból hogy ehhez melyik a next hop
Ad hoc routing • WRP ((Wireless routing gp protocol)) • minden csp-ban 4 táblázat: távolság táblázat, útv. táblázat, link költség tábla, üzenet újraküldési lista • mobilok frissítéseket küldenek egymásnak: ök ök. eltűnése eltűnése, új ök ök. megjelenése esetén; ezeket továbbküldik, illetve néhányra ACK -ot várnak • a szomszédságot az üzenetekből, ACK -okból illetve ha ezeket nem ad, néha hellot küld
Ad hoc routing • forrás által kezdeményezett útvonalválasztási módszerek • AODV (Ad hoc on-demand distance vector) • DSDV hez hasonlít, de nincs gyakran tábla frissítés, csak egy adott útvonalon található mobilok vesznek részt a frisstésben • mobil adni akar, RREQ üzenetet küld mindenkinek, ezt mindenki továbbküldi (ha van bejegyzése a célról, de régi, akkor is) • addig megy tovább míg a célhoz célhoz, vagy egy olyan közbülsőhöz ér ér, amelyiknek elég friss bejegyzése van • az RREQ továbbítása közben mindenki feljegyzi, hogy kitől kapta az első másolatát az adott üzenetnek, üzenetnek ez egy visszaút lesz • a cél vagy egy közbülső egy RREP választ küld az RREQ által kijelölt útvonalon • az RREP a forrásig megy, mindenki megjegyzi kitől kapta: útvonal
Ad hoc routing • AODV (folyt.) • látható, hogy csak szimmetrikus linkekkel működik • ha a forrás elmozdul: kezdeményezhet újra egy útvonalkeresést • ha másik mozdul el: a szomszédja küld egy link failure üzenetet üzenetet, ezt továbbküldik a forrásik, kezdeményezhet újat
Ad hoc routing • DSR (dynamic source routing) • mobilokban útvonal tárolók, a teljes útvonalat tárolják minden célig • küldeni akar és nincs útvonala: RRQ broadcast, cél címe, forrás címe, kérés azonosító • mindenki továbbítja, aki nem tud útvonalat, a csomagban beleteszi a saját címét, csak akkor továbbítja, ha ez az első • ha valakinek van jó útvonala a célig célig, vagy a cél válaszol válaszol, benne van a válszban a teljes útvonal (amin az RRQ jött), ill. közbülső node hozzáteszi a saját útvonalát • a válszt küldheti egy tárolt útvonalon, ill. szimm. esetben az RRQ útvonalán, ill küldhet RRQ -tt, amihez csatolja a választ
Ad hoc routing • ABR (Associativity based routing) • mérték: összeköttetés stabilitás foka -> mobilitással fordítottan arányos • minden mobil periodikusan jelzést küld, a szomszédai ez alapján összeköttetés táblázatot frissítenek • útvonal keresésnél: broadcast kérés, mindenki továbbítja és beleteszi címét és a szomszédaira éd i vonatkozó k ó jjellemzőt ll ő • a következő a magára vonatkozó jellemzőt hagyja csak benne majd továbbküld • a célhoz megérkezik több útvonalon, a cél azt választja, aminek a stabilitása a legnagyobb, egyenlők közül a legkevesebb ugrásból állót • ezen az útvonalon küld választ, ezt a nodek aktívnak jelölik, a többi inaktív
Ad hoc routing • SSR (Signal Stability routing) • csp. közti jel erőssége és a mobil helyztének stabilitása alapján • rreq üzenetek küldése, csak erős csatornán továbbítják, mérték: stabilitás • legstabilabb erős csatornás útvonal választása • ha nincs rreplay üzenet, a forrás új broadcastot kezdeményez, engedélyezve a gyenge csatornán való továbbítást
Ad hoc routing • TORA (temporally ordered routing algorithm) • adaptív, hurkokat nem okozó, változékony mobil környezetben alkalmazható • minden forrás-cél forrás cél párhoz több útvonal • hibrid algoritmusok • CEDAR (core extraction distributed adhoc routing) • ötlet:elosztott algoritmussal kiválasztják a hálózat magját, ezek vesznek részt csak az útvonalszámításban és frissítésben • kisebb az overhead • ZHLS (zone-based hierarchical link state) • a hálózat zónákra van osztva, GPS alapján minden mobil tudja melyik zónában van • hierarchikus a routing: zonán belül és zónák között
