ExOR (protokol bezdrátové sítě) - ExOR (wireless network protocol)

Extrémně příležitostné směrování (ExOR) je kombinací směrovací protokol a řízení přístupu k médiím pro bezdrátová síť ad hoc, vynalezl Sanjit Biswas a Robert Morris z Laboratoř umělé inteligence MIT a popsáno v příspěvku z roku 2005.[1] Velmi podobné oportunistické směrovací schéma také nezávisle navrhli Zhenzhen Ye a Yingbo Hua z University of California, Riverside a prezentována v příspěvku v roce 2005.[2]Dříve open source,[3] ExOR byl k dispozici v roce 2005, ale již jej nelze získat. Strategie vysílání a retransmise používané algoritmem byly již popsány v literatuře.[4][5][6][7][8][9] ExOR je cenný, protože dokáže ovládat dostupná digitální rádia a využívat některé dříve nepraktické algoritmické optimalizace.

Dějiny

Algoritmus je navržen k přenosu paketů internetový protokol, takže umožňuje maximální počet dalších služeb. V době vynálezu digitální rádia široce nahradil drátové internetové služby pro přenosná zařízení. Specializované integrované obvody byly široce dostupné za nízké náklady.

MIT v té době (2005) byl zapojen do Jeden notebook na dítě projekt, pokus o vytvoření levného počítače s nízkou spotřebou energie, který by pomohl vzdělávat zbídačené děti. Za výhody se považovaly snížené náklady na digitální kopie knih a spotřebního materiálu, jako je papír, s možnými pedagogickými vylepšeními díky interaktivitě a flexibilitě. Jednou z klíčových funkcí notebooku měla být a bezdrátová síť ad hoc to by umožnilo notebookům spolupracovat, aby poskytly více zdrojů, než by si jednotlivý počítač mohl dovolit. Praktický, ale vynikající síťový algoritmus by přímo pomohl vzdělávat více dětí snížením nákladů a energie potřebné pro notebook. Bezdrátová síť ad hoc by stála méně a spotřebovala méně energie, pokud by používala standardní rádia (tj integrované obvody pro 802.11 ) a přenesl více dat na větší vzdálenosti s menším počtem mezilehlých rádií.

Tento protokol byl prototypován RoofNet a mnoho úřadů[SZO? ] věřit, že je to protokol pro přístup k médiím nasazený Meraki zapojit San Francisco.

Algoritmus

Počáteční rádio, zdroj, vysílá dávku paketů. Jak časovače v mezilehlých rádiích vyprší, rádia dále od cíle vysílají pakety, které dosud nepřenášelo žádné bližší rádio.

Nejsložitější je podporovat toto základní schéma. Časovače v mezilehlých rádiích jsou nastaveny na odhad doby přenosu, kterou budou bližší rádia potřebovat k přenosu paketů. Odhad se počítá na základě počtu paketů v dávce a pravděpodobnosti správného přenosu z každého mezilehlého rádia.

ExOR používá ke shromažďování informací o pravděpodobnosti úspěšného přenosu mezi každou dvojicí digitálních rádií v síti konvenční směrovací protokol „RRTc“.

Autoři se obávali, že retransmisní pakety by mohly spotřebovat příliš mnoho dostupného rozhlasového času. ExOR se proto snaží snížit retransmise paketů na minimum. To odpovídá vysoké efektivitě ExOR.

Nejprve z směrovacích informací odesílající rádio vytvoří seznam rádií, které by mohly být schopny předávat data z vysílajícího rádia do cíle. Čísla rádií jsou umístěna v a seznam tříděny podle vzdálenosti k cíli, od nejbližší k nejvzdálenější. Cílové rádio je v čele seznamu. Zdrojové rádio také spustí seznam paketů v dávce, aby změřil postup paketů. Tato „dávková mapa“ je řada rádiových čísel, jedno na každý paket. Každé rádiové číslo je rádio, které přenášelo daný paket, a bylo nejblíže cílovému rádiu. Každý datový paket má seznam radiopřijímačů a pakety umístěné vpředu. Seznam šetří místo v každém paketu pomocí radiových čísel namísto IP adres. Poté vysílající rádio vysílá první dávku datových paketů. Spustí časovač. Rádia, která přijímají pakety, ale nejsou v seznamu v paketu, ignorují datové pakety. Tato rádia vyhodí pakety, jakmile jsou přijaty. Rádia, která jsou v seznamu rádií paketu, ukládají datové pakety, které přijímají. Také aktualizují svou dávkovou mapu. Když rádio vyprší, vysílá pakety, které žádné rádio blíže k cíli znovu nevyslalo. Tyto pakety obsahují nejlepší dostupné informace rádia o postupu paketů v dávce (tj. Jeho dávková mapa). Konkrétně dávková mapa každého paketu obsahuje rádiové číslo retransmiteru pro každý paket, který znovu vysílá. Když rádio přijme paket odeslaný z rádia, které je blíže k cíli, vymaže svou vlastní kopii tohoto paketu. Není nutné, aby tento paket znovu vysílal. Rovněž však aktualizuje svou dávkovou mapu o průběhu paketů v dávce. Tímto způsobem informace o postupu paketů proudí zpět směrem ke zdroji, protože rádia dále od cíle aktualizují své dávkové mapy odposloucháváním opakovaných přenosů.

Vzhledem k tomu, že k opětovným přenosům blíže ke zdrojovému rádiu dochází později, informace o postupu paketů proudí zpět do zdrojového rádia, přestože se nikdy nepřenášejí žádné potvrzovací pakety. Na konci je obvykle několik paketů, které nikam nevedly. Ty jsou odesílány nejspolehlivější cestou bez hazardu na nespolehlivých trasách.

ExOR je efektivnější s velkými bloky dat. Ty dávají dávce větší šanci najít alternativní trasy. Dávkové mapy se však také zvětší. Takže bloky dat více než 100 000 bajtů jsou rozděleny do skupin datové pakety zvané dávky. Menší zprávy jsou odesílány nejspolehlivější cestou.

Vzhledem k tomu, že hlavní internetový protokol TCP odesílá proud dat, používá ExOR k akumulaci bloků dat místní datové servery proxy.

Výhody a nevýhody

Každý paket je vysílán opakovaně a pokrývá nejdelší možnou vzdálenost při každém přenosu. Nějaký čas je promarněn tím, že přijímač vysílá informace o paketech, ale je to mnohem méně než u běžných směrovacích schémat, která se mohou znovu vyslat, když dojde ke ztrátě potvrzovací zprávy.

Nejsou k dispozici žádné potvrdit pakety a žádné kolize s nimi. To šetří čas rádia.

Autoři tvrdí, že protokol je zhruba dvakrát tak efektivní než běžné směrovací protokoly s pevným „optimálním“ směrováním. (Viz „testování“ níže, kde jsou uvedeny metody, které se k tomu používají).

Autoři tvrdí, že variace v dodacích lhůtách je 1/4 jiných sítí ad hoc, a připisují to algoritmu s využitím nejlepších dostupných dodacích lhůt.

Autoři uspořádali test tak, aby protokol hromadil velké bloky dat pro přenos. Data ukazují kompromis mezi rychlostí reakce sítě a účinností rádiového systému.

Doba odezvy v některých hrách může být ovlivněna větším množstvím ukládání do vyrovnávací paměti ve vysoce účinných sítích.

Testování

Odhady účinnosti ExOR jsou založeny na skutečné implementaci s Linux směrovací sada nástrojů zvaná kliknutí. Experimentální verze softwaru byly simulovány a nainstalovány na střešní síť zvanou „RoofNet“ v Cambridge v Massachusetts. Tato data byla porovnána s publikovanými daty pro podobnou síť.[10]

Viz také

Reference

  1. ^ ExOR: Oportunistické vícesměrové směrování pro bezdrátové sítě Sanjit Biswas, Robert Morris, představeno na SIGCOMM '05, 2005, Copyright ACM, Philadelphia, Penn. 2005, ACM č. 1-59593-009-4 / 05/0008
  2. ^ Zásady linkové vrstvy předávání dat přes bezdrátová relé Zhenzhen Ye, Yingbo Hua, představeno na IEEE MILCOM '05, 2005, Copyright IEEE, Atlantic City, NJ, říjen 2005
  3. ^ [1][trvalý mrtvý odkaz ]
  4. ^ „Využívání distribuované prostorové rozmanitosti v sítích,“ J. N. Laneman, G. Wornell; Analyzuje některá informační-teoretická kooperativní schémata rozmanitosti, ale rádia používají speciální techniky ke sdílení spektra. ExOR přizpůsobuje schéma časových úseků delší časové škále, kterou lze implementovat do softwaru pomocí komoditních rádií.
  5. ^ „Přeposílání rozmanitosti výběru v paketové rádiové síti s více kanály s únikem kanálů a zachycením,“ P. Larsson, SIGMOBIL Mob. Comm. Rev.5 (4): 47-564, 2001
  6. ^ „OAR, Opportunistic Media Access for Multirate Networks,“ B. Sadeghi, V. Kanodia, A. Sabharwal a E. Knightly; Sborník ACM Mobicom 2002, září 2002
  7. ^ „Exploiting Path Diversity in the Link Layering Wireless Ad-Hoc Networks,“ Proc. 6. sympozia IEEE WoWMoM, červen 2005
  8. ^ „MAC Layer Anycasting in Wireless Networks,“ R. Roy Chowdhury a N. Vaidya, druhý seminář o horkých tématech v sítích (HotNets II), listopad 2003
  9. ^ „Geographic Random Forwarding (GeRaf),“ M. Zorzi, R. Rao, IEEE Transactions on Mobile Computing, 2 (4), říjen 2003
  10. ^ „Link Level Measurements from a 802.11b Mesh Network,“ D. Aguayo, J. Bicket, S. Biswas, G. Judd a R. Morris; ACM SIGCOMM 2004, srpen 2004