is Íslenska en English

Lokaverkefni (Meistara)

Háskólinn í Reykjavík > Tæknisvið / School of Technology > MSc Tölvunarfræðideild / Department of Computer Science >

Vinsamlegast notið þetta auðkenni þegar þið vitnið til verksins eða tengið í það: http://hdl.handle.net/1946/16281

Titill: 
  • Titill er á ensku Experimental analysis of throughput maximization for combinatorial spectrum auctions.
  • Greining með hermunum á hámörkun afkasta í fjölrása tíðniuppboðum.
Námsstig: 
  • Meistara
Útdráttur: 
  • Útdráttur er á ensku

    A somewhat artificial scarcity of spectrum is due to static allocation to so called Primary Users (PUs) who use it only intermittently. A promising solution uses market approaches to redistribute limited time access rights to so called Secondary Users (SUs) (Hoefer, Kesselheim, & Vöcking, 2011). A reasonable approach, concisely termed "eBay in the Sky" (Zhou, Gandhi, Suri, & Zheng, 2008), auctions licenses for SUs regularly.
    We employ the physical or signal-to-interference-plus-noise-ratio (SINR) model to model wireless communication in the plane. We auction m channels to n links randomly scattered in the plane, with probability p of attaching to a previously placed link, known as preferential attachment (Ásgeirsson et al., 2012). Links have symmetric and downward sloping valuations. Since finding an optimal allocation is known to be NP-hard (Goussevskaia, Oswald, & Wattenhofer, 2007) we compare several approximation algorithms in simulations, namely GREEDYLENGTH, GREEDYWEIGHT, BUCKETLENGTH,
    BUCKETWEIGHT, LOCALRATIO, GREEDYINTERFERENCE, and a Linear Programming Algorithm (LP) (Hoefer & Kesselheim, 2012). The performance of all algorithms is compared varying three dimensions, n, m and p. Algorithms GREEDYWEIGHT, LOCALRATIO and LP quite consistently rank first, second and third, respectively. In further simulations, varying valuations, LOCALRATIO outperformed GREEDYWEIGHT.
    An attempt was made to turn GREEDYWEIGHT and LOCALRATIO into truthful mechanisms using VCG-like payments. Neither payment scheme turned out to be truthful. A known method turns LP solutions into truthful-inexpectation mechanisms (Lavi & Swamy, 2005). While there is no known truthful mechanism for GREEDYWEIGHT and LOCALRATIO, LP algorithm may be used at the price of lower social welfare. In practice GREEDYWEIGHT and LOCALRATIO may be used to allocate channels in a first-price auction.

  • Skortur á tíðni fyrir þráðlaus samskipti er að hluta tilkominn vegna þess að forgangsnotendur fá úthlutað tíðni til langs tíma en nota hana ekki stöðugt. Markaðsaðferðir gætu komið sér vel til að endurúthluta tíðni til skamms tíma til annarra notenda (Hoefer et al., 2011). Ein slík aðferð, nefnd "‘eBay á himni"’ (Zhou et al., 2008), býður reglulega upp skammtímanotkunarleyfi á tíðni til annarra notenda.
    Við notumst við efnislega (SINR) líkanið fyrir þráðlaus samskipti á sléttu. Boðnar eru upp m rásir sem n tenglar geta boðið í. Með líkum p er tengill staðsettur nálægt einhverjum tengli sem er þegar á sléttunni, annars er staðsetning tengils valin af handahófi (Ásgeirsson et al., 2012). Tenglar hafa áhuga á því hversu margar rásir þeir fá, en bjóða minna fyrir hverja viðbótarrás. Samanlagt verðmat tengla fyrir rásir sem þeir fá úthlutað er skilgreint sem velferð. Sýnt hefur verið að ekki er hægt að finna kjörlausn á margliðutíma (Goussevskaia et al., 2007), því berum við saman velferð nokkurra nálgunarreiknita með hermunum, það er GREEDYLENGTH, GREEDYWEIGHT, BUCKETLENGTH, BUCKETWEIGHT, LOCALRATIO, GREEDYINTERFERENCE og reiknirit sem byggir á línulegri bestun (LP) (Hoefer & Kesselheim, 2012). Velferð er borin saman á þremur víddum, það er n, m og p. Reikniritin GREEDYWEIGHT, LOCALRATIO og LP, finna lausnir með mestri velferð. Verðmati tengla var breytt í frekari hermunum, þar var LOCALRATIO með meiri velferð en GREEDYWEIGHT.
    Uppboð eru skilgreind sannorð ef bjóðendur hagnast á því að bjóða sitt rétta verðmat.
    Reynt var að búa til sannorð uppboð fyrir GREEDYWEIGHT og LOCALRATIO, með greiðslum sem svipa til VCG, en tókst í hvorugu tilviki. Vitað er um aðferð sem breytir lausnum úr línulegum bestunarlíkönum í væntanlega sannorð uppboð (Lavi & Swamy, 2005). Meðan ekki er vitað um sannorð uppboð fyrir GREEDYWEIGHT and LOCALRATIO, er hægt að notast við LP reiknitið með aðeins minni velferð. Notast má við GREEDYWEIGHT og LOCALRATIO, ef tenglar eru látnir borga sama verð og þeir bjóða.

Styrktaraðili: 
  • Styrktaraðili er á ensku This research is supported by Rannsóknarsjóður research grant number 90032021.
Samþykkt: 
  • 28.8.2013
URI: 
  • http://hdl.handle.net/1946/16281


Skrár
Skráarnafn Stærð AðgangurLýsingSkráartegund 
OnlineMScHIB.pdf457.83 kBOpinnHeildartextiPDFSkoða/Opna