Vi anser att delay-egenskaperna hos maxviktig opportunistisk schemaläggning i ett trådlöst fleranvändar-ON/OFF-system, t.ex. en fleranvändarnedlänk eller upplänk. Det är välkänt att schemaläggningen av maxvikten stabiliserar nätet (och därmed ger maximal genomströmning) när inmatningshastigheten är inne i nätverkskapacitetsregionen. Vi visar att när ankomst- och kanalprocesser är oberoende, är den genomsnittliga fördröjningen av maxviktspolitiken orderoptimal, i den meningen att den inte växer med antalet nätverkslänkar. Medan nyligen kögrupperade algoritmer är kända för att också ge orderoptimal fördröjning, är detta det första sådana resultat för den enklare klassen av maxviktspolicyer. Vi överväger fördröjningsegenskaperna hos maxvikts opportunistisk schemaläggning i ett trådlöst system med flera användare. Vi överväger särskilt ett system med N-överföringslänkar. Varje länk tar emot oberoende data som anländer slumpmässigt och måste köas för eventuell överföring. Separata köer upprätthålls av varje länk i 1..., N}, så att data som anländer till kö i måste överföras över länk i. Systemet fungerar i slitsad tid med normaliserade slots t  ska {0, 1, 2,.. .}. Jag vet inte vad du ska göra. Kanaltillstånden för varje länk varierar slumpmässigt från slot till slot, och varje slot t nätverksregulatorn observerar aktuella köbackloggar och nuvarande kanaltillstånd, och väljer en enda länk för trådlös överföring. Detta är ett klassiskt opportunistiskt schemaläggningsscenario, där nätverksschemaläggaren kan utnyttja kunskapen om den nuvarande tidens varierande kanaler. Det är väl känt att maxvikt schemaläggning politik är genomströmning optimal i sådana system, i den meningen att de tydligt stabilisera alla köer när inmatningshastigheten vektor är inne i nätverks kapacitet regionen. Detta stabilitetsresultat visades först av Tassiulas och Efremides [2] för specialfall av ON/OFF-kanaler, och generaliserades senare till multi-rate överföringsmodeller och system med effektfördelning [3] [4] [5] [6]. Fördröjningsegenskaperna för schemaläggning med maxvikt är dock mindre förståeliga. En genomsnittlig fördröjning som är linjär i N härleds i [5] [6]. Även om denna gräns är snäv när det gäller korrelerade ankomst- och kanalprocesser, anses den allmänt vara lös för oberoende ankomster och kanaler. I detta dokument fokuserar vi på det särskilda fallet med ON/OFF-kanaler och visar att den maximala viktpolicyn faktiskt ger en genomsnittlig försening som är O(1) enligt oberoende antaganden. Den genomsnittliga fördröjningen ökar alltså inte med nätstorleken Michael J. Neely är med elektroteknikavdelningen på
REF Köerna antas vara initierade så att
Delay analysis for max weight opportunistic scheduling in wireless systems
{'venue': '2008 46th Annual Allerton Conference on Communication, Control, and Computing', 'journal': '2008 46th Annual Allerton Conference on Communication, Control, and Computing', 'mag_field_of_study': ['Computer Science', 'Mathematics']}