I detta dokument tar vi upp schemaläggningsproblemen i trådlösa ad hoc-nätverk genom att utnyttja den beräkningsfördel som kommer när sådana schemaläggningsproblem kan representeras av klofria konfliktgrafer där vi betraktar ett trådlöst sändningsmedium. Det är möjligt att formulera ett schemaläggningsproblem för nätkodade flöden som att hitta maximal viktad oberoende uppsättning (MWIS) i konfliktgrafen över nätet. Att hitta MWIS av en allmän graf är NP-hård vilket leder till en NPhard komplexitet schemaläggning. I en klofri konfliktgraf, MWIS kan hittas i polynom tid som leder till en genomströmning-optimal schemaläggning. Vi visar att konfliktgrafen över vissa trådlösa ad hoc-nätverk är klorfri. För att få fram klofria konfliktdiagram i allmänna nätverk föreslår vi att man inför ytterligare konflikter (kanter) samtidigt som minskningen av MWIS-storleken hålls minimal. I detta syfte inför vi ett iterativt optimeringsproblem för att bestämma var man ska införa kanter och undersöka dess effektiva genomförande. Dessutom exemplifierar vi några fysiska ändringar för att manipulera konfliktgrafen i ett nätverk och föreslår också en blandad schemaläggningsstrategi för specifika nätverk. Vi drar slutsatsen att klo brott metod genom att lägga till extra kanter kan prestera nästan optimalt under de nödvändiga antagandena.
Det tillvägagångssätt som används i REF för att ta itu med den situation där konfliktgraferna inte är klofria är att lägga till kanter till konfliktgrafen för att få en klofri graf.
Nearly Optimal Scheduling of Wireless Ad Hoc Networks in Polynomial Time
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}