Vi studerar topologikontrollproblem i ad hoc-nätverk, där nätverksnoder får välja sina strömnivåer för att säkerställa önskade konnektivitetsegenskaper. Till skillnad från de flesta andra arbete på detta ämne, antar vi att nätverksnoder ägs av olika enheter, vars enda mål är att maximera sitt eget verktyg att de kommer ut ur nätverket utan att överväga den totala prestandan i nätverket. Spelteori är det lämpliga verktyget för att studera sådana själviska noder: vi definierar flera topologi kontrollspel där noderna behöver välja effektnivåer för att ansluta till andra noder i nätverket för att nå sina kommunikationspartners samtidigt minimera sina kostnader. Vi studerar Nash equilibria och visar att -bland de spel vi definierar - dessa kan bara garanteras att existera om alla nätverksnoder krävs för att anslutas till alla andra noder (vi kallar detta Starka Anslutningsspel). Vi ger asymptotiskt snäva gränser för det värsta fallet kvalitet på en Nash jämvikt i Strong Connectivity Game och vi förbättrar dessa gränser för slumpmässigt fördelade noder. Vi studerar sedan den beräkningsmässiga komplexiteten av att hitta Nash equilibria och visar att en polynom-tid algoritm finner Nash equilibria vars kostnader är som mest en faktor 2 av den minsta möjliga kostnaden; för en variation som kallas Connectivity Game, där varje nod bara krävs för att anslutas (eventuellt via mellanliggande noder) till en given uppsättning noder, visar vi att besvara frågan, om en Nash jämvikt finns, är NP -hard, om nätverksgrafen uppfyller triangeln ojämlikhet. För ett andra spel som heter Reachability Game, där varje nod försöker nå så många andra noder som möjligt, medan minimera sin radie, visar vi att 1 + o(1)-ungefärliga Nash equilibria finns för slumpmässigt fördelade noder. Vårt arbete är ett första steg mot spelteoretiska analyser av ad hoc-nätverk. * Los Alamos National Laboratory Report LA-UR-03-3269.
The Strong Connectivity Game REF är ett specialfall av Connectivity Game där varje vertex måste ansluta till varje annan vertex.
Equilibria in topology control games for ad hoc networks
{'venue': "DIALM-POMC '03", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}