Abstract-I detta dokument vi anser problemet med att maximera antalet stödda anslutningar i godtyckliga trådlösa nätverk där en överföring stöds om och endast om signal-till-interference-plus-buller förhållandet vid mottagaren är större än någon tröskel. Syftet är att välja överföringskrafter för varje anslutning för att maximera antalet anslutningar för vilka denna tröskel uppfylls. Vi anser att det är viktigt att analysera detta problem både i sin egen rätt och eftersom det uppstår som ett subproblem inom många andra områden av trådlösa nätverk. Vi studerar både komplexiteten i problemet och även presentera några spel teoretiska resultat om kapacitet som uppnås genom helt distribuerade algoritmer. Vi anser också att detta problem är intressant, eftersom det omfattar båda de kontinuerliga aspekterna (d.v.s. välja överföringsbefogenheter) samt diskreta aspekter (dvs. vilka anslutningar som ska stödjas). Våra resultat är: • Vi visar att maximera antalet stödda anslutningar är NP-hård, även när det inte finns något bakgrundsljud. Detta står i kontrast till problemet med att avgöra om en viss uppsättning anslutningar är möjlig eller inte, eftersom detta problem kan lösas genom linjär programmering. • Vi presenterar ett antal approximationsalgoritmer för problemet. Alla dessa approximationsalgoritmer körs i polynom tid och har ett approximationsförhållande som är oberoende av antalet anslutningar. • Vi undersöker en helt distribuerad algoritm och analyserar den som ett spel där en anslutning får en positiv payoff om den är framgångsrik och en negativ payoff om den misslyckas medan den sänder med icke-noll effekt. Vi visar att i detta spel finns det inte nödvändigtvis en ren Nash jämvikt men om en sådan jämvikt finns motsvarande pris anarki är oberoende av antalet anslutningar. Vi visar också att en blandad Nash-jämvikt motsvarar en probabilistisk överföringsstrategi och i detta fall finns alltid en sådan jämvikt och har ett pris på anarki som är oberoende av antalet anslutningar.
Problemet med gemensam planering och kraftfördelning är NP-hårda REF och ett suboptimalt tillvägagångssätt krävs för att maximera spektrumutnyttjandet.
Maximizing Capacity in Arbitrary Wireless Networks in the SINR Model: Complexity and Game Theory
{'venue': 'IEEE INFOCOM 2009', 'journal': 'IEEE INFOCOM 2009', 'mag_field_of_study': ['Computer Science']}