Detta dokument fokuserar på utformningen av bevisligen effektiva online länk schemaläggning algoritmer för multihop trådlösa nätverk. Vi betraktar enhop-flöden och enhop-interferensmodellen. Målet är tvåfaldigt: 1) maximera genomströmningen när flödeskällorna kontinuerligt injicerar paket i nätverket, och 2) minimera evakueringstiden när det inte finns några framtida paketankomster. De tidigare verken använder oftast den länkbaserade metoden, vilket leder till genomströmningseffektiva algoritmer men ofta inte garanterar tillfredsställande evakueringstidsprestanda. I detta dokument använder vi en ny nodbaserad metod och föreslår en servicebalanserad online schemaläggningsalgoritm, kallad NSB, som ger balanserade schemaläggningsmöjligheter till noderna med tung arbetsbelastning. Vi bevisar rigoröst att NSB garanterar att uppnå ett effektivitetsförhållande inte sämre (eller mindre) än 2/3 för genomströmningen och ett approximationsförhållande inte sämre (eller inte större) än 3/2 för evakueringstiden. Det är anmärkningsvärt att NSB är både genomströmningsoptimalt och utrymningstidoptimalt om den underliggande nätverksgrafen är bipartit. Vidare utvecklar vi en lägre komplexitets-NSB-algoritm, kallad LC-NSB, som ger samma prestandagarantier som NSB. Slutligen utför vi numeriska experiment för att belysa våra teoretiska resultat.
En annan intressant forskningslinje är den on-line node-baserade schemaläggningsalgoritmer som uppnår god prestanda bunden i genomströmning och evakueringstid REF.
Node-based Service-Balanced Scheduling for Provably Guaranteed Throughput and Evacuation Time Performance
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}