CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Task Placement and Resource Allocation in Edge Computing Systems
KTH, School of Electrical Engineering and Computer Science (EECS), Computer Science, Network and Systems Engineering. Royal Inst Technol, KTH, Sch Elect Engn & Comp Sci, Dept Network & Syst Engn, Stockholm, Sweden..ORCID iD: 0000-0002-6466-8304
2020 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

The evolution of wireless and hardware technology has led to the rapiddevelopment of a variety of mobile applications. Common to these applicationsis that they have low latency and high computational requirementsthat often cannot be fulfilled by individual devices due to their insufficientcomputational power, memory and battery capacity. An emerging approachto meet increasing user demand for delay sensitive and computationally intensiveapplications is mobile edge computing. The core paradigm of mobileedge computing is to bring computing and storage resources close to the endusers and by doing so to relieve devices from computationally heavy workloadswhile meeting delay requirements of applications. However, the overallperformance of edge computing systems is determined by the efficiency of thejoint allocation of wireless and computing resources. The work in this thesisproposes decentralized algorithms for allocating these two resources in edgecomputing infrastructures.In the first part of the thesis, we consider the resource allocation andcomputational task scheduling problem in an edge computing system in whichwireless devices can use cloud resources and the resources of each other withthe objective to minimize their own perceived response times. We develop agame theoretical model of the problem, prove the existence of equilibrium taskallocations and propose an efficient decentralized algorithm that computes anequilibrium based on average system parameters.In the second part of the thesis, we consider the joint resource allocationand computational task assignment problem in an edge computing systemthat consists of an edge cloud that can be accessed by devices through multiplewireless links. We model the problem as a strategic game, in which eachdevice aims at minimizing a combination of its response time and energyconsumption. We prove the existence of equilibrium task allocations, and usegame theoretical tools for designing polynomial time decentralized algorithmswith a bounded approximation ratio. We then extend the analysis to a systemwith periodic tasks, and show that equilibrium task allocations still exist.Furthermore, we propose a polynomial complexity decentralized algorithmand characterize the structure of equilibria computed by the algorithm.In the third part of the thesis, we consider the joint resource allocation andcomputational task assignment problem in an edge computing system thatconsists of multiple edge clouds and wireless links managed by a single networkoperator. We model the interaction between the operator and devices thataim at minimizing their response times as a Stackelberg game. We expressthe optimal resource allocation policies in closed form, prove the existence ofStackelberg equilibria and propose an efficient decentralized algorithm with abounded approximation ratio. Finally, we consider the same edge computingsystem under network slicing, and based on a game theoretic treatment of theproblem we develop an approximation algorithm for assigning tasks to slicesand managing the resources across and within slices.By providing constructive equilibrium existence proofs, the results in thisthesis provide low complexity decentralized algorithms for allocating edgecomputing resources in a variety of edge computing infrastructures.

Abstract [sv]

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.

Place, publisher, year, edition, pages
Stockholm: KTH Royal Institute of Technology, 2020. , p. 62
Series
TRITA-EECS-AVL ; 2020:21
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Research subject
Electrical Engineering
Identifiers
URN: urn:nbn:se:kth:diva-272623ISBN: 978-91-7873-510-5 (print)OAI: oai:DiVA.org:kth-272623DiVA, id: diva2:1426233
Public defence
2020-05-27, https://kth-se.zoom.us/j/67035147251, Stockholm, 14:00 (English)
Opponent
Supervisors
Note

QC 20200424

Available from: 2020-04-24 Created: 2020-04-24 Last updated: 2020-05-18Bibliographically approved
List of papers
1. Decentralized Algorithm for Randomized Task Allocation in Fog Computing Systems
Open this publication in new window or tab >>Decentralized Algorithm for Randomized Task Allocation in Fog Computing Systems
2019 (English)In: IEEE/ACM Transactions on Networking, ISSN 1063-6692, E-ISSN 1558-2566, Vol. 27, no 1, p. 85-97Article in journal (Refereed) Published
Abstract [en]

Fog computing is identified as a key enabler for using various emerging applications by battery powered and computationally constrained devices. In this paper, we consider devices that aim at improving their performance by choosing to offload their computational tasks to nearby devices or to an edge cloud. We develop a game theoretical model of the problem and use a variational inequality theory to compute an equilibrium task allocation in static mixed strategies. Based on the computed equilibrium strategy, we develop a decentralized algorithm for allocating the computational tasks among nearby devices and the edge cloud. We use the extensive simulations to provide insight into the performance of the proposed algorithm and compare its performance with the performance of a myopic best response algorithm that requires global knowledge of the system state. Despite the fact that the proposed algorithm relies on average system parameters only, our results show that it provides a good system performance close to that of the myopic best response algorithm.

Place, publisher, year, edition, pages
Institute of Electrical and Electronics Engineers (IEEE), 2019
Keywords
Computation offloading, fog computing, game theory, task placement, decentralized resource management
National Category
Computer Sciences
Identifiers
urn:nbn:se:kth:diva-245938 (URN)10.1109/TNET.2018.2880874 (DOI)000458851600007 ()2-s2.0-85058145086 (Scopus ID)
Note

QC 20190313

Available from: 2019-03-13 Created: 2019-03-13 Last updated: 2020-04-28Bibliographically approved
2. Selfish Decentralized Computation Offloading for Mobile Cloud Computing in Dense Wireless Networks
Open this publication in new window or tab >>Selfish Decentralized Computation Offloading for Mobile Cloud Computing in Dense Wireless Networks
2019 (English)In: IEEE Transactions on Mobile Computing, ISSN 1536-1233, E-ISSN 1558-0660, Vol. 18, no 1, p. 207-220Article in journal (Refereed) Published
Abstract [en]

Offloading computation to a mobile cloud is a promising solution to augment the computation capabilities of mobile devices. In this paper, we consider selfish mobile devices in a dense wireless network, in which individual mobile devices can offload computations through multiple access points or through the base station to a mobile cloud so as to minimize their computation costs. We provide a game theoretical analysis of the problem, prove the existence of pure strategy Nash equilibria, and provide an efficient decentralized algorithm for computing an equilibrium. For the case when the cloud computing resources scale with the number of mobile devices, we show that all improvement paths are finite. Furthermore, we provide an upper bound on the price of anarchy of the game, which serves as an upper bound on the approximation ratio of the proposed decentralized algorithms. We use simulations to evaluate the time complexity of computing Nash equilibria and to provide insights into the price of anarchy of the game under realistic scenarios. Our results show that the equilibrium cost may be close to optimal, and the convergence time is almost linear in the number of mobile devices.

Place, publisher, year, edition, pages
IEEE COMPUTER SOC, 2019
Keywords
Computation offloading, mobile edge computing, Nash equilibria, decentralized algorithms
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
urn:nbn:se:kth:diva-269571 (URN)10.1109/TMC.2018.2829874 (DOI)000452441000016 ()2-s2.0-85045992116 (Scopus ID)
Note

QC 20200406

Available from: 2020-04-06 Created: 2020-04-06 Last updated: 2020-04-28Bibliographically approved
3. Computation Offloading Scheduling for Periodic Tasks in Mobile Edge Computing
Open this publication in new window or tab >>Computation Offloading Scheduling for Periodic Tasks in Mobile Edge Computing
2020 (English)In: IEEE/ACM Transactions on Networking, ISSN 1063-6692, E-ISSN 1558-2566, Vol. 28, no 2, p. 667-680Article in journal (Refereed) Published
Abstract [en]

Motivated by various delay sensitive applications, we address the problem of coordinating the offloading decisions of wireless devices that periodically generate computationally intensive tasks. We consider autonomous devices that aim at minimizing their own cost by choosing when to perform their tasks and whether or not to offload their tasks to an edge cloud through one of the multiple wireless links. We develop a game theoretical model of the problem, prove the existence of pure strategy Nash equilibria and propose a polynomial complexity algorithm for computing an equilibrium. Furthermore, we characterize the structure of the equilibria, and by providing an upper bound on the price of anarchy of the game we establish an asymptotically tight bound on the approximation ratio of the proposed algorithm. Our simulation results show that the proposed algorithm achieves significant performance gain compared to uncoordinated computation offloading at a computational complexity that is on average linear in the number of devices.

Keywords
computation offloading, edge computing, game theory, decentralized resource management
National Category
Telecommunications Communication Systems Computer Systems
Research subject
Electrical Engineering
Identifiers
urn:nbn:se:kth:diva-272612 (URN)2-s2.0-85079604134 (Scopus ID)
Note

QC 20200427

Available from: 2020-04-23 Created: 2020-04-23 Last updated: 2020-05-25Bibliographically approved
4. Joint Management of Wireless and Computing Resources for Computation Offloading in Mobile Edge Clouds
Open this publication in new window or tab >>Joint Management of Wireless and Computing Resources for Computation Offloading in Mobile Edge Clouds
2019 (English)In: IEEE Transactions on Cloud Computing, ISSN 2168-7161, p. 1-14Article in journal (Refereed) Published
Abstract [en]

We consider the computation offloading problem in an edge computing system in which an operator jointly manages wireless and computing resources across devices that make their offloading decisions autonomously with the objective to minimize their own completion times. We develop a game theoretical model of the interaction between the devices and an operator that can implement one of two resource allocation policies, a cost minimizing or a time fair resource allocation policy. We express the optimal cost minimizing resource allocation policy in closed form and prove the existence of Stackelberg equilibria for both resource allocation policies. We propose two efficient decentralized algorithms that devices can use for computing equilibria of offloading decisions under the cost minimizing and the time fair resource allocation policies. We establish bounds on the price of anarchy of the games played by the devices and by doing so we show that the proposed algorithms have bounded approximation ratios. Our simulation results show that the cost minimizing resource allocation policy can achieve significantly lower completion times than the time fair allocation policy. At the same time, the convergence time of the proposed algorithms is approximately linear in the number of devices, and thus they could be effectively implemented for edge computing resource management.

Keywords
edge computing, resource management, computation offloading, game theory, decentralized algorithms
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
urn:nbn:se:kth:diva-272613 (URN)
Note

QC 20200427

Available from: 2020-04-23 Created: 2020-04-23 Last updated: 2020-04-28Bibliographically approved
5. Joint Wireless and Edge Computing Resource Management with Dynamic Network Slice Selection
Open this publication in new window or tab >>Joint Wireless and Edge Computing Resource Management with Dynamic Network Slice Selection
2020 (English)In: IEEE/ACM Transactions on Networking, ISSN 1063-6692, E-ISSN 1558-2566Article in journal (Refereed) Submitted
Abstract [en]

Network slicing is a promising approach for enabling low latency computation offloading in edge computing systems. In this paper, we consider an edge computing system under network slicing in which the wireless devices generate latency sensitive computational tasks. We address the problem of joint dynamic assignment of computational tasks to slices, management of radio resources across slices and management of radio and computing resources within slices. We formulate the Joint Slice Selection and Edge Resource Management (JSS-ERM) problem as a mixed-integer problem with the objective to minimize the completion time of computational tasks. We show that the JSS-ERM problem is NP-hard and develop an approximation algorithm with bounded approximation ratio based on a game theoretic treatment of the problem. We provide extensive simulation results to show that network slicing can improve the system performance compared to no slicing and that the proposed solution can achieve significant gains compared to the equal slicing policy. Our results also show that the computational complexity of the proposed algorithm is approximately linear in the number of devices.

National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Research subject
Electrical Engineering
Identifiers
urn:nbn:se:kth:diva-272614 (URN)
Note

QC 20200506

Available from: 2020-04-23 Created: 2020-04-23 Last updated: 2020-05-06Bibliographically approved

Open Access in DiVA

fulltext(1644 kB)89 downloads
File information
File name FULLTEXT01.pdfFile size 1644 kBChecksum SHA-512
180049755737d7185c2cd2d68da11184983a834d5f16169539f580aa07f578b43c2ec98fc63d3044dd5c31a5436e67ad2f270a72494c8ca9d5b28a7ad5fb8b58
Type fulltextMimetype application/pdf

Other links

Zoom register link for online defense

Search in DiVA

By author/editor
Josilo, Sladana
By organisation
Network and Systems Engineering
Electrical Engineering, Electronic Engineering, Information Engineering

Search outside of DiVA

GoogleGoogle Scholar
Total: 89 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 241 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf