Abstract-Vi föreslår en allmän familj av MAC schemaläggning algoritmer som uppnår någon hastighet-punkt på en enhetlig diskret lattice inom genomströmning-regionen (dvs. lattice-throughputoptimal) under en fysisk interferens modell. Enligt den fysiska interferensmodellen, kräver en centraliserad algoritm information om nod platser (och avstånd mellan noder) för att bestämma ett schema som är bevisligen genomströmning-optimal. I detta dokument föreslår vi en distribuerad, synkron strid baserad schemaläggningsalgoritm som (i) är lattice-throughput-optimal, (ii) inte kräver nod platsinformation, och (iii) har en signalerande komplexitet som inte beror på nätverksstorlek. Således är det möjligt att enkelt implementera, och är robust för att nätverk dynamik såsom topologi och belastning förändringar. Vi anser att en MAC-länk schemaläggning algoritm för en timesloted trådlös ad-hoc-nätverk under en fysisk interferens modell. MAC-schemaläggningsproblemet för sådana nätverk har varit ett aktivt forskningsämne under de senaste decennierna, med en stor del av forskningen inriktad på en grafbaserad interferensmodell, där primära (dvs. en-hop) och sekundära (dvs tvåhop) konfliktmodeller beaktas. Den grafbaserade interferensmodellen är dock en enorm förenkling av trådlös kommunikation främst därför att den är omedveten om en realistisk aggregerad störning [1], [2], dvs. den störning som orsakas av olika sändare kan ackumuleras för att så småningom hindra mottagningen. MAC-algoritmer för schemaläggning enligt grafbaserade interferensmodeller kan i stort klassificeras i: (i) distribuerade suboptimala algoritmer med partiella genomströmningsgarantier (t.ex. [3]–[6]), där distribuerade, snabba algoritmer som uppnår bevisbara lägre gränser på genomströmningsregionen har föreslagits baserat på suboptimala val för ett schema för varje tidsparti (t.ex. maximal schemaläggning som används vid schemaläggning av byte [7] ), och (ii) graffärger baserade algoritmer (se [8] och referenser där), där färgproblem (som är NP-komplett) formuleras genom att omvandla den ursprungliga grafen till en länkinnehållsgraf, och suboptimala polynomiska centraliserade eller distribuerade heuristikalgoritmer har föreslagits. I detta dokument, under den fysiska interferensmodellen, föreslår vi en familj av dynamiska, randomiserade, distribuerade MAC schemaläggningsalgoritmer och tillhörande generaliserade villkor, som, om de är uppfyllda, säkerställer lattice-genomströmning-optimalitet, dvs. att uppnå någon prispunkt på en enhetlig diskret-lattice inom Y. Yi är med Institutionen för elektroteknik, Princeton University (e-post: yyi@princeton.edu). G. de Veciana och S. Shakkottai är vid institutionen för el- och datateknik, Texas universitet i Austin (e-post: {gustavo, shakott}@ece.utexas.edu). Denna forskning stöddes av NSF-stipendier CNS-043507, CNS-0347400, CCF-0634898, och DARPA ITMANET-programmet. Genomströmningsregionen. Observera att även en centraliserad schemaläggningsalgoritm under den fysiska interferensmodellen kräver exakt topologikunskap (dvs. nodplatser och nätverksanslutning) för att uppnå genomströmningsoptimalitet, vilket behövs för att beräkna mängden störningar som genereras av samtidigt aktiverade noder. Men något överraskande föreslår vi en distribuerad algoritm som uppnår lattice-throughput-optimalitet utan centraliserad geografisk information. Såvitt vi vet är detta dokument det första försöket att föreslå en distribuerad, genomströmningsoptimal schemaläggningsalgoritm under den fysiska interferensmodellen. Som ett exempel på den föreslagna familjen av lattice-throughputoptimal algoritmer, utvecklar vi en synkroniserad tvistebaserad algoritm, RCAMA (Randomized Contention Aware Multiple Access), som kräver endast en enkel strid signalering på varje time-slot, vilket leder till betydande förenkling av genomförandet. Förutom att RCAMA bevisligen är latticethroughput-optimal, fungerar RCAMA på ett "dynamiskt" sätt, dvs. bestämda scheman är inte nödvändigtvis konfliktfria, men de förbättras gradvis för att närma sig ett optimalt schema (se figur 1). Dessutom gör enkel stridssignalering det möjligt för RCAMA att anpassa sig till förändringar i trafikbelastning och nätverk topologi genom att lära sig ett områdes stridsmönster på ett autonomt sätt. RCAMA:s huvudsakliga motivering är att även om enskilda (end-to-end) trafikbelastningar kan förändras snabbt, kan aggregaten på vissa överbelastade länkar, i många relevanta tillämpningar, förändras långsammare och mer lokalt. På samma sätt kan nodrörlighet (som leder till förändringar i topologi och belastning) vara tillräckligt långsam för att tillåta en MAC schemaläggare att lära sig och utnyttja de erbjudna trafikegenskaperna för att snabbt förverkliga "bra" scheman. Det har varit mycket nyligen arbete i samband med algoritmer med bevisbara (partiella) genomströmningsgarantier under den graf-baserade interferensmodellen. Exempel är distribuerade suboptimala system [3]- [6], som ger lägre gränser på genomströmningsregionen utan någon uttrycklig kunskap om den erbjudna belastningen (dvs. statistik/kunskap om lasten över någon länk i nätet). Dessa algoritmer kräver antingen styrmeddelande overheads som växer med nätverksstorlek [3]- [5] eller konstant overhead men kan bara realisera begränsade genomströmningsgarantier [6]. Det är uppenbart att deras budskapskomplexitet kommer att öka betydligt under den fysiska interferensmodellen på grund av de mer komplexa interferensförhållandena mellan länkarna. Nyligen har författarna i [9], [10] föreslagit schemaläggning algoritmer med en 100% genomströmning garanti under grafbaserade interferens modeller, men de kräver fortfarande hög kontroll meddelande komplexitet. I motsats till ovanstående suboptimala, distribuerade tillvägagångssätt, antar vi att en nod endast har explicit kunskap- Denna fulltext dokument var peer review i riktning mot IEEE Communications Society ämne experter för publicering i IEEE INFOCOM 2007 förfaranden. kant av den lokala (långsiktig) erbjudna belastningen (dvs. erbjuden belastning på var och en av dess utgående länkar). Men vi kan bevisa att denna extra lokal-information vid noder leder till en distribuerad, lattice-genomströmning-optimal algoritm som kräver endast tre steg av enkel strid signalering (som leder till sex signalerande meddelanden över en-hop) på varje time-slot, oavsett nätverksstorlek. I vårt förberedande arbete [11] föreslogs en familj av lattice-genomströmning-optimala schemaläggningsalgoritmer baserat på en grafbaserad interferensmodell. Som tidigare diskuterats verkar det dock, enligt den fysiska interferensmodellen, vara en mycket svårare uppgift att hitta en genomströmningsoptimal algoritm, eftersom det maximala antalet humle som behöver beaktas är högst två för den grafbaserade interferensmodellen, medan interferens enligt den fysiska interferensmodellen är aggregerad, vilket leder till att ett godtyckligt antal humle måste övervägas vid beslut om ett "bra" schema. I praktiken, beroende på vilken tjänst som stöds av nätverket, kan information om den erbjudna belastningen antingen uttryckligen ges till noderna eller mätas av noderna. Om vi har ett garanterat servicenätverk baserat på en resursreservation signalerar (t.ex., RSVP [12] ), kan mängden belastning vara känd a priori av noder i vägen för ett reserverat flöde. I ett typiskt servicenätverk för bästa ansträngning tillhandahålls dock inte mängden last uttryckligen till noderna, men noderna kan mäta/uppskatta erbjuden belastning under en lämplig tidsperiod. Eftersom lasterna kan uppvisa viss variation, eller mätningar kan vara bullriga, kan en nod använda en övre uppskattning för det (dvs. overbook). Nyligen har det gjorts flera insatser för analys och design av trådlösa multihop-nätverk under mer allmänna interferensmodeller än den grafbaserade interferensmodellen. Arbetet med [13] utvecklar en matematisk programmeringsformulering för att minimera ramstorleken över ett trådlöst TDMA multi-hop nätverk, baserat på den optimala gemensamma MAC schemaläggning och effektstyrning under den fysiska interferensmodellen. Detta arbete skiljer sig från vårt genom att den föreslagna distribuerade, heuristiska algoritmen i [13] är suboptimal, och den fungerar under en "avslappnad fysisk interferens modell", där den interferens som genereras av endast en enda interfererande sändare närmast den avsedda mottagaren beaktas. Författarna i [14], [15] antar också denna avslappnade fysiska interferens modell för att designa och studera prestandan hos ett MAC-protokoll. Författarna i [15] överväga en matematisk optimering formulering för MAC schemaläggning under den fysiska interferensmodellen, och föreslå en heuristisk centraliserad system med målet att använda den centraliserade heuristiska som ett riktmärke för andra distribuerade on-line algoritmer. I [16], författarna införa en ny klass av interferens modeller som kännetecknas av parametern K, där en framgångsrik mottagning av ett meddelande vid en mottagare kräver ingen överföring från noder som är K-hopar bort från mottagaren. I arbetet med [17] definieras "schemaläggningskomplexiteten", som motsvarar den minsta tid som krävs tills en ansluten grafstruktur kan schemaläggas. De tar dock inte direkt itu med schemaläggningsproblemet och fokuserar endast på asymptotiska analyser av schemaläggningens komplexitet. I [18], [19], författarna har fokuserat endast på att beräkna maximal genomströmning under den fysiska interferensmodellen genom att gemensamt överväga routing, MAC schemaläggning och effektstyrning i ett optimeringsramverk. Men i [18], [19], MAC schemaläggning delen fångas med hjälp av en abstrakt vätskemodell, och ingen praktisk, genomströmning-optimal, distribuerad algoritm presenteras. De viktigaste bidragen i detta dokument är följande: i) Enligt den fysiska interferensmodellen föreslår vi först en familj av schemaläggningsalgoritmer (DRS: Dynamic Randomized Scheduling) som uppnår någon hastighetspunkt på en enhetlig diskret lattice inom genomströmningsregionen (dvs. lattice-throughputoptimal). I detta syfte ger vi två allmänna villkor, som, om de uppfylls, säkerställer att en algoritm i DRS-familjen är lattice-throughput-optimal, och vi ytterligare studerar deras konvergenshastighet. (ii) Nästa, som ett exempel på DRS-familjen, föreslår vi en synkron strid-baserad algoritm, RCAMA (Randomized Contention-Aware Multiple Access), där flera steg strid signalerar i samband med randomiserade tidslott val. Vi bevisar lattice-throughput-optimality av RCAMA, genom att visa att RCAMA uppfyller de två villkoren i (i). Vidare föreslår vi en adaptiv variation av RCAMA, ARCAMA (Adaptive RCAMA), som återigen uppfyller de två villkoren i (i) och adaptively biasures slot selection sannolikheter baserat på tidigare tvistehistoria. Vi visar via simulering att endast en kort minnestid räcker för att öka prestandan, vilket resulterar i god anpassning till belastnings-/topologiförändringar. Papperet är organiserat enligt följande: Vi börjar med en beskrivning av systemmodellen, notationer, och definitioner i avsnitt II. Därefter, i Avsnitt III, definierar vi DRS-algoritmfamiljen, och presenterar två allmänna villkor för att en DRS-algoritm ska vara lattice-throughput-optimal. I Avsnitt IV, som ett exempel på en sådan lattice-genomströmning-optimal familj, föreslår vi RCAMA, och diskutera dess variationer för bättre anpassning till belastning/topologi förändringar. Slutligen, i avsnitt VI, validerar vi våra resultat med hjälp av simuleringar. Andra stycket ska ersättas med följande: Vi antar att tiden är slut. En tidsrymd väljs på lämpligt sätt för överföring av ett paket med fast storlek och innehåller en skyddstid som motsvarar den maximala differentialförökningsfördröjningen mellan par av noder i nätverket. Vi modellerar det trådlösa multi-hop nätverket med en graf G(L, V), där L och V betecknar en uppsättning riktningslänkar, respektive en uppsättning noder. Vi antar att för varje länk mellan två noder finns det en motdel i motsatt riktning. Vi betecknar en riktad länk från node i till node j av i→ j. Det trådlösa systemet har en enda frekvens/kod, som är tillgänglig för både dataöverföring och överföring av styrmeddelanden, och det finns ingen separat fysisk kanal för styrmeddelanden (dvs. signalering i band). Varje nod i systemet är utrustad med en allsidig antenn, och synkroniserad. Vi antar 295 att varje sändning är avsedd för endast en mottagare 1, och varje nod har bara en enda transceiver (dvs halv-duplex radio). Vi betecknar den (fasta) effektnivå som en sändare använder för dataöverföring med P, och den fysiska interferensmodellen baserad på SINR (Signal-to-Interference-Noise Radio) beaktas. I denna interferensmodell är en länk i→ j, i, j  och V ansluten, om G i j P/η j ≥ γ, där G i j är förökningsförlusten från i till j, och η j är den termiska bruseffekten vid j. SINR-tröskeln γ beror på önskad bithastighet, bitfelsfrekvens och konstruktionsparametrar som modulering, kodning och så vidare. Ett meddelande (t.ex. data, ack eller styrmeddelanden) från i till j är decodable, om där V I är uppsättningen noder, som sänder samtidigt med i på en given time-slot. I praktiken, förutom störningar, är trådlösa länkar benägna att fel på grund av många andra faktorer (t.ex. blekning). Detta leder till hög förlusthastighet i paket som är skadlig för prestanda i övre lager. I många MAC-protokoll tillhandahålls därför tillförlitlighet genom att erkänna sändningar och eventuellt sända vidare. Därför definierar vi följande: Definition 2.1: Vi säger att en överföring över i→ j är framgångsrik, om både datameddelandet från i till j och motsvarande ack meddelande från j till i är decodable på j respektive i, där ack meddelande från j kommer att startas endast när datameddelandet är decodable vid i. I det här dokumentet fokuserar vi bara på flöden på länknivå, och vi överväger inte routing- och transportlagerflöden från end-to-end. En länk schema A = (A l : l = 1,..,  en), A l ( 0, 1} är en binär vektor som representerar den uppsättning länkar som planeras för överföring försök på en time-slot, där A l = 1 om länken l är planerad, och 0 annars. Vi definierar en omvänd av en länk schema A, R( A) = (B l ) att vara: B ( j, i) = 1, om A (i, j) = 1, och 0 annars. Definition 2.3: Ett länkschema A sägs vara framgångsrikt om de sändningar som planeras av A respektive R( A) är framgångsrika. Vi betecknar insamlingen av alla framgångsrika länkar scheman av A. Definition 2.4: Vi definierar genomströmningsregionen ι genom: Definition 2.5: För varje fast positivt heltal F definierar vi genomströmningsregionen F genom: Intuitivt, Α F är lattice-ampling av π med intilliggande punkter med ett avstånd på 1/F. Observera att ρ = CL( ska F=1,..., Δ F ), där CL(Z) är stängningen av en uppsättning Z. Definition 2.6: En schemaläggningsalgoritm Π väljer en sekvens av länkscheman (som inte nödvändigtvis är framgång-1 Med andra ord, vi anser en "länk" schemaläggning, inte "node" schemaläggning. ful), (A[s]: s = 0, 1,...................................................................................................................... För en F-lattice-genomförbar belastning ρ, genom att multiplicera den erbjudna belastningen med F, hanterar vi hädanefter positiva heltalsvärdenad belastning,  och Z +, d.v.s. l motsvarar antalet begärda tidslotter över länk l ut ur F tidslotter. Vi kallar en grupp F time-slots en ram genom hela detta papper. I vårt ramverk, lattice-parameter F är en systemomfattande parameter som är känd för varje nod i nätverket a-priori. Således, i hela detta papper, antar vi implicit att lattice-parametern, betecknad av F, är fast. Dessutom använder vi för enkelhetens skull termerna "genomströmningsoptimalt" och "genomförbart" för att hänvisa till "F-lattice-genomströmningsoptimalt" respektive "Flattice-genomförbart", om det inte uttryckligen behövs. I detta dokument, vi anser "frame-based" schemaläggning algoritmer, där schemaläggning mönster bestäms på en frameby-frame basis (dvs, F tidslotter) 2, och vi kommer att se att det är tillräckligt att överväga sådan klass av algoritmer. Definition 3.1: Vi definierar ett bildschema (FS) som ska vara en följd av F-länkscheman, dvs. en L-×F-matris, C(F,  ska) = (c ls: l = 1,...,  och s = 1,..., F), där c ls = 1 om en överföring är planerad över länk l på tid s, och 0 annars. Dessutom, l-th rad vektor av C(F,  på), sägs vara en slot schema över l. A FS C(F,  på) sägs vara möjligt, om alla F-länk scheman (kolumn vektorer) i C(F) är framgångsrika. Som nämnts i avsnitt I utgår vi från att en nod endast har kunskap om den lokala erbjudna lasten (dvs. ankomsttaxan) på var och en av dess utgående länkar. Således, för alla l  på L, L = F s=1 c ls, dvs antalet schemalagda tidslotter på varje länk är lika med den belastning som erbjuds på den länken. Definition 3.2: Vi definierar dessutom en överföringsprioritering, R = (r ls : l = 1,...,  till, s = 1,..., F) där r ls = 1 (r ls = 0) om c ls = 1 och dess prioritet är hög (låg) och NUL annars (c ls = 0). I detta dokument anser vi följande klass av framescheduling algoritmer: (F,  på), enligt definition 2.5. Vårt mål i detta dokument är att utveckla en DRS 2 Således använder vi hädanefter en term "time-slot s" för att hänvisa till s-th timelot inuti en ram. Vi använder vanligtvis's' och 't' för att hänvisa till index för en time-slot respektive en ram. Detta dokument i sin helhet granskades av experter på ämnesområdet IEEE Communications Society för offentliggörande i förfarandet IEEE INFOCOM 2007. Schemaläggningsalgoritm som finner en genomförbar ramplan inom ett begränsat antal ramar, och som upprätthåller schemat därefter, för varje given genomförbar belastning. Det är lätt att se att en DRS-algoritm som uppfyller sådana egenskaper uppnår latticethroughput-optimalitet. Således räcker det att överväga familjen av DRS algoritmer. Nu härleder vi två villkor, som, om de uppfylls, säkerställer att en DRS-algoritm är genomströmningsoptimal: (i) FSC (Feasibility Sustenance Condition), där om en FS konvergerar till en genomförbar, det måste upprätthållas därefter, och (ii) FIC (Finite Improvement Condition), där innan konvergering till en genomförbar FS, en sekvens av FS över ramar tenderar att gradvis "nära" till en genomförbar FS med positiv sannolikhet. Vi definierar först ett "avstånd" mellan två FS (under samma topologi och belastning), C = (c ls ) och C = (c ls ), att vara: Observera att D(C, C ) = 0 innebär C = C. Definition 3.4: För en given fast belastning och topologi, låt den aktuella ramen vara t i. Ämne dessa två villkor, har vi följande teorem: Theorem 3.1: För varje fast möjlig erbjuden belastning och topologi, överväga en DRS algoritm Π som uppfyller FSC och FIC. Vi har att (i) Π konvergerar till en genomförbar FS, och därmed Π är genomputoptimal. (ii) Låt τ Π (C) vara konvergenstiden för Π till en genomförbar FS för en given inledande ram schema C. Då,  och t Z +, Det finns konstanter 0 < K Π < ∞ och 0 < p Π < 1, så att Pr τ Π (C) > tK Π ≤ p t Π. På grund av utrymmesbegränsningar, hoppar vi över beviset, som finns i [20]. Skiss över bevis är följande: För det första är det lätt att se att en sekvens av FS över ramar bildar en Markov kedja. Då, FIC innebär att vi kan konstruera en konvergerande väg till en genomförbar FS (säg, C ) inom en ändlig tid, eftersom D(C, C ) är övre gräns. FIC och FSC gör det möjligt för oss att verifiera genomströmningsoptimalitet av en DRS-algoritm. Dessutom kan den anpassas/förstärkas, och fortfarande vara throughput-optimal, så länge den utökade versionen uppfyller FIC och FSC. I denna uppsats utvecklar vi en "baslinje" DRS algoritm (RCAMA) med historik 1 i Avsnitt IV, och sedan utöka RCAMA till ARCAMA (Adaptive RCAMA) med flera ramhistorier för bättre anpassning till belastning/topologi förändringar i Avsnitt V, med både RCAMA och ARCAMA tillfredsställande FSC och FIC.
I REF föreslås en tvistebaserad distribuerad algoritm, RCAMA, med hjälp av en fysisk interferensmodell.
On Optimal MAC Scheduling With Physical Interference
{'venue': 'IEEE INFOCOM 2007 - 26th IEEE International Conference on Computer Communications', 'journal': 'IEEE INFOCOM 2007 - 26th IEEE International Conference on Computer Communications', 'mag_field_of_study': ['Computer Science']}