Abstract-A fundamentalt problem i trådlösa nätverk är den maximala länken schemaläggning (eller maximal oberoende uppsättning) problem: med tanke på en uppsättning L av länkar, beräkna den största möjliga delmängd L ′  på länkar som kan schemaläggas samtidigt utan störningar. Detta problem är särskilt utmanande i den fysiska interferensmodellen baserad på SINR-begränsningar (s.k. SINR-modellen), som har fått stort intresse under de senaste åren. Konstant faktor approximation algoritmer har utvecklats för detta problem, men låg komplexitet distribuerade algoritmer som ger samma approximation garanti i SINR-modellen är inte kända. Distribuerade algoritmer är särskilt utmanande i denna modell, på grund av dess icke-lokalitet. I detta dokument utvecklar vi en uppsättning snabba distribuerade algoritmer i SINR-modellen, vilket ger konstant approximation för maximal länk schemaläggning problem under enhetlig makttilldelning. Vi finner att olika aspekter av tillgänglig teknik, såsom fullständig/halvkomplex kommunikation, och icke-adaptiv/adaptiv effektstyrning, har en betydande inverkan på algoritmens prestanda; dessa frågor har inte undersökts i samband med distribuerade algoritmer i SINR-modellen tidigare. Våra algoritmers körtid är O(g(L) log c m), där c = 1, 2, 3 för olika problemfall, och g(L) är den "länkmångfald" som bestäms av den logaritmiska skalan av en kommunikationslänklängd. Eftersom g(L) är liten och förblir i ett konstant intervall i de flesta fall, fungerar våra algoritmer som den första uppsättningen av "sublinjära" tidsfördelad lösning. Algoritmerna är randomiserade och använder sig på ett avgörande sätt av fysisk bäraravkänning i distribuerade kommunikationssteg.
I REF konstaterade Pei och Vullikanti att olika aspekter av tillgänglig teknik, såsom fullständig/halvkomplex kommunikation och icke-adaptiv/adaptiv effektstyrning, har en betydande inverkan på algoritmens prestanda.
Efficient Algorithms for Maximum Link Scheduling in Distributed Computing Models with SINR Constraints
{'venue': None, 'journal': 'arXiv: Distributed, Parallel, and Cluster Computing', 'mag_field_of_study': ['Computer Science']}