Vi anser att problemet med dataflödesoptimal schemaläggning i trådlösa nätverk är föremål för störningsbegränsningar. Vi modellerar störningen med hjälp av en familj av K-hop-interferensmodeller. Vi definierar en K-hop-interferensmodell som en som inga två länkar inom K-hopen kan överföra samtidigt (observera att IEEE 802.11 DCF motsvarar en 2-hop-interferensmodell). För en given K måste en dataflödesoptimal schemaläggare lösa ett maximalt viktat matchningsproblem under K-hop-interferensbegränsningar. För K = 1, är det resulterande problemet det klassiska Maximum Weighted Matching problemet, som kan lösas i polynom tid. Vi visar dock att för K > 1, de resulterande problemen är NP-Hard och kan inte approximeras inom en faktor som växer polynomiskt med antalet noder. Intressant nog visar vi att för specifika typer av grafer, som kan användas för att modellera den underliggande konnektivitet grafen i ett brett spektrum av trådlösa nätverk, de resulterande problemen medger polynom tid approximation system. Vi visar också att en enkel girig matchande algoritm ger en konstant faktor approximation till schemaläggning problem för alla K i detta fall. Vi visar sedan att under en inställning med en-hop trafik och ingen hastighetskontroll, den maximala schemaläggning politik som beaktas i senaste relaterade arbeten kan uppnå en konstant del av kapacitetsregionen för nätverk vars konnektivitet graf kan representeras med hjälp av en av ovanstående klasser av grafer. Dessa resultat är uppmuntrande eftersom de tyder på att man kan utveckla distribuerade algoritmer för att uppnå nära optimal genomströmning vid ett brett spektrum av trådlösa nätverk. Tillstånd att göra digitala eller papperskopior av hela eller delar av detta arbete för personligt bruk eller klassrum beviljas utan avgift, förutsatt att kopiorna inte görs eller distribueras för vinst eller kommersiella fördelar och att kopiorna är försedda med detta meddelande och den fullständiga hänvisningen på första sidan. För att kopiera på annat sätt, för att återpublicera, för att posta på servrar eller för att omfördela till listor, krävs tidigare specifik behörighet och/eller avgift.  Kategorier och ämnesdeskriptorer Teori, algoritmer
Forskning har visat att K-hop länkinterferensmodellen kan användas för att effektivt fånga protokollmodellen REF.
On the complexity of scheduling in wireless networks
{'venue': "MobiCom '06", 'journal': None, 'mag_field_of_study': ['Computer Science']}