Task Placement and Resource Allocation in Edge Computing Systems

Tid: On 2020-05-27 kl 14.00

Plats: Zoom register link for online defense (English)

Ämnesområde: Elektro- och systemteknik

Respondent: Sladana Josilo , Nätverk och systemteknik, Royal Inst Technol, KTH, Sch Elect Engn & Comp Sci, Dept Network & Syst Engn, Stockholm, Sweden.

Opponent: Professor Ben Liang,

Handledare: György Dán, Nätverk och systemteknik

Abstract

Teknologiska framsteg inom trådlös teknik och hårdvara har lett till en snabb utvecklingav en rad olika mobilapplikationer. Mobilapplikationerna behöver ha låglatens och hög beräkningskraft vilket ofta inte kan uppfyllas av enskilda enheterpå grund av bland annat bristande minne och batterikapacitet. En växande trendför att möta den ökade efterfrågan på applikationer med höga krav på latens ochberäkningsförmåga är så kallad ”mobile edge computing”. Grunden i mobile edgecomputing är att placera beräknings- och lagringsresurser nära slutanvändarna.Detta befriar enheter från krävande beräkningar och uppgifter samtidigt som deuppfyller applikationernas latenskrav. Den totala prestandan för mobile edge computingbestäms dock av effektiviteten av den gemensamma tilldelningen av trådlösaresurser och beräkningsresurser. Den här avhandlingen föreslår decentraliserade algoritmerför att fördela dessa resurser i infrastruktur för mobile edge computing.I den första delen av avhandlingen behandlar vi resursfördelning och schemaläggningav beräkningsuppgifter i ett edge computing system, där trådlösa enheterkan använda både molnresurser och varandras resurser för att minimera sinaupplevda svarstider. Vi utvecklar en spelteoretisk modell av problemet, bevisar attjämviktsuppgiftstilldelningar finns och föreslår en effektiv decentraliserad algoritmsom beräknar en jämvikt baserad på genomsnittliga systemparametrar.I den andra delen av avhandlingen behandlar vi resursfördelning och tilldelningenav beräkningsuppgifter i ett edge computing system som består av ett edge cloudsom kan nås av enheter via flera trådlösa länkar. Vi modellerar problemet som ettstrategiskt spel, där varje enhet syftar till att minimera en kombination av dessresponstid och energiförbrukning. Vi bevisar att jämviktsuppgiftstilldelningar finnsoch använder spelteoretiska verktyg för att designa polynomiska decentraliseradetillnärmningsalgoritmer. Vi utvidgar sedan analysen till ett system med periodiskauppgifter och visar att jämviktsuppgiftstilldelningar fortfarande finns. Vidare föreslårvi en decentraliserad algoritm med polynomisk komplexitet och karakteriserarstrukturen för jämvikter som beräknas av algoritmen.I den tredje delen av avhandlingen angriper vi problemet av resursfördelning ochtilldelningen av beräkningsuppgifter i ett edge computing system som består av fleratrådlösa länkar och flera edge clouds som hanteras av en enda nätoperatör. Vimodellerar interaktionen mellan operatören och enheter som syftar till att minimeraderas responstider som ett Stackelberg-spel. Vi formulerar de optimala resursfördelningspolicyernai sluten form, bevisar att Stackelberg-jämvikter finns och föreslåren effektiv decentraliserad algoritm med ett begränsat tillnärmningsförhållande.Slutligen analyserar vi samma kantberäkningssystem under nätverksskivning, ochbaserat på en spelteoretisk behandling av problemet utvecklar vi en tillnärmningsalgoritmför att tilldela uppgifter till olika delar och hantera resurserna både mellanoch inom delar.Genom att visa konstruktiva bevis på jämvikt ger resultaten i den här avhandlingendecentraliserade algoritmer med låg komplexitet för fördelning av edge computingresurser i en rad olika infrastrukturer för edge computing.

urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-272623