Vi presenterar den första algoritmen som implementerar ett abstrakt MAC-skikt (absMAC) i den trådlösa nätverksmodellen Signal-to-interference-plus-NoiseRatio (SINR). Vi bevisar först att effektiva SINR-implementeringar inte är möjliga för standard absMAC-specifikationen. Vi ändrar den specifikationen till en "ungefärlig" version som bättre passar SINR-modellen. Vi ger en effektiv algoritm för att genomföra den ändrade specifikationen, och använder den för att härleda effektiva algoritmer för problem på högre nivå med global sändning och konsensus. I synnerhet visar vi att absMAC framsteg egenskapen har ingen effektiv implementering i termer av SINR stark konnektivitet graf G1−ε, som innehåller kanter mellan noder av avstånd som högst (1−ε) gånger överföringsområdet, där ε > 0 är en liten konstant som kan väljas av användaren. Denna förlopp egendom begränsar tiden tills en nod är garanterad att ta emot något meddelande när åtminstone en av dess grannar sänder. För att övervinna denna begränsning inför vi det något svagare begreppet ungefärliga framsteg i absMAC-specifikationen. Vi tillhandahåller ett snabbt genomförande av den ändrade specifikationen, baserat på att dela upp algoritmen [10] i lokala och globala delar. Vi analyserar vår algoritm i termer av lokala parametrar såsom nod grader, snarare än globala parametrar såsom det totala antalet noder. Ett viktigt bidrag är vår demonstration att en sådan lokal analys är möjlig även i närvaro av global inblandning. Vår absMAC-algoritm leder till flera nya, effektiva algoritmer för att lösa problem på högre nivå i SINR-modellen. Nämligen, genom att kombinera vår algoritm med högnivåalgoritmer från [26] får vi en förbättrad (jämfört med [10] Tillstånd att göra digitala eller hårda kopior av hela eller delar av detta arbete för personligt eller klassrum användning beviljas utan avgift, förutsatt att kopior inte görs eller distribueras för vinst eller kommersiella fördelar och att kopior bär detta meddelande och den fullständiga hänvisning på första sidan. Upphovsrätt till delar av detta verk som ägs av andra än ACM måste hedras. Abstraktering med kredit är tillåten. För att kopiera på annat sätt, eller återpublicera, för att posta på servrar eller för att omfördela till listor, krävs tidigare specifik behörighet och/eller avgift. Algoritm för global enmeddelandeutsändning i SINR-modellen och den första effektiva algoritmen för flermeddelandeutsändning i den modellen. Vi härleder också den första effektiva algoritmen för nätverksomfattande konsensus, med hjälp av ett resultat av [32]. Detta arbete visar att man kan utveckla effektiva algoritmer för att lösa problem på hög nivå i SINR-modellen, med hjälp av grafbaserade algoritmer över ett lokalt abstractionlager som döljer teknikaliteterna i SINR-plattformen såsom global störning. Våra algoritmer kräver inga gränser på nätverksstorleken, eller förmågan att mäta signalstyrka, eller bäraravkänning, eller synkron vakna upp.
Vi ger mer information om bidrag i den fullständiga versionen av detta dokument REF.
A Local Broadcast Layer for the SINR Network Model
{'venue': "PODC '15", 'journal': None, 'mag_field_of_study': ['Computer Science']}