Vi överväger schemaläggningsproblem i trådlösa nätverk med avseende på flexibla datahastigheter. Det vill säga, mer eller mindre data kan överföras per tid beroende på signalkvaliteten, som bestäms av förhållandet mellan signal och interferens plus-brus (SINR). Varje trådlös länk har en funktion för att kartlägga SINR-värden till respektive datahastighet. Vi måste bestämma vilka sändningar som utförs samtidigt och (beroende på problemvarianten) även vilka överföringsbefogenheter som används. I kapacitetsmaximering problem, strävar man efter att maximera den totala nätverksgenomströmningen, dvs. den summerade nyttan av alla länkar. För godtyckliga allmännyttiga funktioner (inte nödvändigtvis kontinuerliga sådana) presenterar vi en O(log n)-uppskattning när vi har n kommunikationsförfrågningar. Denna algoritm är byggd på en konstant-faktor approximation för specialfallet av respektive problem där nyttofunktioner endast består av ett enda steg. Med andra ord, varje länk har en individuell tröskel och vi syftar till att maximera antalet länkar vars tröskel är nöjd. På vägen förbättrar detta resultatet i [Kesselheim, SODA 2011] genom att inte bara utvidga det till enskilda tröskelvärden utan också visa en konstant approximationsfaktor oberoende av antaganden om det underliggande metriska utrymmet eller nätverksparametrarna. Dessutom anser vi att problemet med latensminimering är problematiskt. Här har varje länk en efterfrågan, t.ex., som representerar en mängd data. Vi måste beräkna ett schema av kortast möjliga längd så att för varje länk efterfrågan uppfylls, det vill säga den totala summerade nytta (eller överförda data) är minst lika stor som dess efterfrågan. Baserat på kapacitetsmaximeringsalgoritm, visar vi en O(log 2 n)-uppskattning för detta problem.
Den approximation av konstantfaktorn för Mwisl med enhetliga vikter och godtyckliga men fasta datahastigheter som föreslås i REF kan användas för att få O(log n)-uppskattningar för TDMA-länkschemaläggning och Mwisl med hastighetskontroll, där n är antalet länkar.
Approximation Algorithms for Wireless Link Scheduling with Flexible Data Rates
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}