De regler som styr tillgängligheten och kvaliteten på anslutningar i ett trådlöst nätverk beskrivs av fysiska modeller såsom modellen signal-till-interferens och bullerförhållande (SINR). För en samling av samtidigt sändande stationer i planet är det möjligt att identifiera en mottagningszon för varje station, bestående av de punkter där överföringen tas emot korrekt. Det resulterande SINR-diagrammet delar upp planet i en mottagningszon per station och det återstående planet där ingen station kan höras. SINR-diagram verkar vara grundläggande för att förstå beteendet hos trådlösa nätverk, och kan spela en viktig roll i utvecklingen av lämpliga algoritmer för sådana nätverk, kanske i likhet med den roll som Voronoi-diagram spelar i studiet av närhetsfrågor och relaterade frågor i beräkningsgeometri. De är beroende av förenklade grafbaserade modeller, t.ex. modellen för enhetsdiskett (UDG), som på ett behändigt sätt tar bort störningsrelaterade komplikationer och gör det lättare att hantera algoritmiska problem, men som följaktligen inte exakt fångar upp vissa viktiga aspekter av trådlösa nätverk. Det aktuella dokumentet fokuserar på att få en grundläggande förståelse av SINR-diagram, deras egenskaper och deras användbarhet i algoritmiska tillämpningar. Speciellt, baserat på några algebraiska egenskaper polynom som definierar de mottagningszoner vi visar att antar enhetliga kraftöverföringar, är mottagningszoner konvexa och relativt väl rundade. Dessa resultat används sedan för att utveckla en effektiv approximationsalgoritm för ett grundläggande punktplatsproblem i trådlösa nätverk.
Eftersom i den enhetliga inställningen, är mottagningszoner konvexa och fett REF ], kan singularitetspunkterna i en zon lätt hanteras.
SINR diagrams: towards algorithmically usable SINR models of wireless networks
{'venue': "PODC '09", 'journal': None, 'mag_field_of_study': ['Computer Science']}