Abstract-Vi överväger ett kommunikationsnät och studera problemet med att utforma en hög genomströmning och låg fördröjning schemaläggning politik som bara kräver en polynom mängd beräkning vid varje steg. Den välkända policyn för maximal viktplanering, som föreslagits av Tassiulas och Ephremides (1992), har goda resultat när det gäller genomströmning och fördröjning, men för allmänna nätverk kan det vara mycket dyrt att beräkna. En relaterad randomiserad politik som föreslås av Tassiulas (1998) ger maximal genomströmning med endast en liten mängd beräkning per steg, men verkar framkalla exponentiellt stor genomsnittlig fördröjning. Dessa överväganden väcker vissa naturliga frågor. Är det möjligt att utforma en politik med låg komplexitet, hög genomströmning och låg fördröjning för ett allmänt nätverk? Leder Tassiulas randomiserade politik till en låg genomsnittlig försening? I detta dokument besvarar vi båda dessa frågor negativt. Vi anser att ett trådlöst nätverk fungerar enligt två alternativa interferensmodeller: a) en kombinatorisk modell med oberoende uppsättningar begränsningar och b) standard SINR (signal-till-interferensbrusförhållande) modell. Vi visar att om inte NP BPP (eller P = NP för deterministiska ankomster och deterministisk politik), och även om den nödvändiga genomströmningen är en mycket liten del av nätverkets kapacitet, det inte finns en låg fördröjning politik vars beräkning per tidssteg skala polynomialt med antalet köer. I synnerhet måste den genomsnittliga fördröjningen av Tassiulas randomiserade algoritm växa superpolynomiskt. För att fastställa våra resultat använder vi en smart grafomvandling som infördes av Lund och Yannakakis (1994).
För det första, även om mottrycket maximerar nätgenomströmningen, verkar den praktiska versionen (Tassiulas 1998) fortfarande framkalla stora genomsnittliga förseningar REF, vilket inte är önskvärt när det gäller trafiknät.
Hardness of Low Delay Network Scheduling
{'venue': 'IEEE Transactions on Information Theory', 'journal': 'IEEE Transactions on Information Theory', 'mag_field_of_study': ['Computer Science']}