|
| Titre : |
Scheduling IoT Applications in Edge and Fog Computing Environments |
| Type de document : |
texte imprimé |
| Auteurs : |
Oussama Bencheikh, Auteur ; Dhikra Lamis Angag ; Chirihane Gherbi, Directeur de thèse |
| Editeur : |
Setif:UFA |
| Année de publication : |
2024 |
| Importance : |
1 vol (66 f .) |
| Format : |
29 cm |
| Langues : |
Anglais (eng) |
| Catégories : |
Thèses & Mémoires:Informatique
|
| Mots-clés : |
IoT
Edge
Fog
Task Scheduling
RTFIFO |
| Index. décimale : |
004 - Informatique |
| Résumé : |
The notable evolution of computing paradigms, driven by the growth of IoT devices,
has led to the emergence of Fog computing, a decentralized approach that addresses
bandwidth, latency, and connectivity challenges, enhancing cloud-IoT communication.
The objective of this master’s thesis is to study the task scheduling mechanism in
the computing paradigms, specifically Fog computing. By ameliorating the RTFIFO
(Resources Then First In First Out) scheduling approach, aiming to minimize the
number of rejected tasks. The amelioration is represented by proposing several approaches
in order to realize our goal. The first approach is RD-FIFO (Resources-then-
Deadlines-First-In-First-Out) based on the deadline characteristics. The second one
is the Multiple-Queue-RTFIFO (Multiple-Queue Resources-Then-FIFO) based on the
arrival time and requested resources, and the third one is the Hybrid-Multiple-Queue-
RDFIFO (Hybrid Multiple-Queue-Resources-then-Deadlines-FIFO) based on the arrival
time, the requested resources, and the deadline at a time. The last one is Hybrid
M-Q (RTFIFO-SJF) (Hybrid Multiple-Queue-Resources-then-First-In-First-Out-
Shortest-Job-First), which is based on the arrival time, the requested resources, and
the service time. We based our contributions on the Divide-and-Conquer approach,
classifying tasks according to their deadlines and requesting resources to avoid missed
deadlines, the variety of deadlines and requested resources of a task. After programming
our proposal methods and simulating the execution results, the Hybrid M-Q
(RTFIFO-SJF) was found to be the best method for minimizing the rejected tasks |
| Note de contenu : |
Sommaire
Abstract i
R´esum´e ii
Table of contents ix
List of figures xi
List of tables xii
List of algorithms xiii
Abbreviations xv
Introduction 1
1 State of the art 3
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Internet of Things (IoT) . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.1 IoT Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.2 Applications domains . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.3 IoT Characteristics . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.4 IoT Components . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.5 IoT Architectures . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.6 IoT Advantages and Disadvantages . . . . . . . . . . . . . . . . 11
1.3 Cloud Computing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.3.1 Definition of Cloud Computing . . . . . . . . . . . . . . . . . . 12
1.3.2 Cloud Characteristics . . . . . . . . . . . . . . . . . . . . . . . . 12
1.3.3 Types of Cloud . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.4 Edge Computing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.4.1 Definition of Edge Computing . . . . . . . . . . . . . . . . . . . 14
1.4.2 Edge Computing Architecture . . . . . . . . . . . . . . . . . . . 15
1.4.3 Basic Components of Edge Computing . . . . . . . . . . . . . . 15
1.4.4 Edge Computing Benefits . . . . . . . . . . . . . . . . . . . . . 16
1.4.5 Motivation, challenges and opportunities in edge computing . . 16
1.5 Fog Computing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.5.1 Definition of Fog Computing . . . . . . . . . . . . . . . . . . . . 17
1.5.2 Basic Components of Fog Computing . . . . . . . . . . . . . . . 17
1.5.3 Fog Computing Benefits . . . . . . . . . . . . . . . . . . . . . . 18
1.6 Difference Between Cloud, Fog and Edge Computing . . . . . . . . . . 19
1.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2 Related Review 22
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2 Task Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2.1 Task Scheduling Definition . . . . . . . . . . . . . . . . . . . . . 22
2.2.2 Task Scheduling Characteristics . . . . . . . . . . . . . . . . . . 23
2.3 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.3.1 Task scheduling approaches for Fog Computing . . . . . . . . . 24
2.3.2 Computation Offloading and Scheduling in Edge-Fog Cloud Computing
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.3.3 Efficient Task Scheduling for Applications on Clouds . . . . . . 30
2.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3 Contribution 33
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.2 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.3 Problematic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.4 Proposed approaches . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.4.1 RD-FIFO(Resources then Deadlines First In First Out) . . . . . 35
3.4.2 MultiQueueRTFIFO (Multiple-Queue Resources-Then-First-In-
First-Out) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.4.3 Hybrid Multiple-Queue-RDFIFO (Hybrid Multiple-Queue-Resourcesthen-
Deadlines-First-In-First-Out) . . . . . . . . . . . . . . . . . 42
3.4.4 Hybrid M-Q (RTFIFO-SJF) (Hybrid Multiple-Queue-Resourcesthen-
First-In-First-Out-Shortest-Job-First) . . . . . . . . . . . . 46
3.5 Comparison table of contributions . . . . . . . . . . . . . . . . . . . . . 50
3.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4 Implementation and Results 52
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.2 Programming Tool . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.3 Programming Language . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.4 The programming results . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.4.1 The RTFIFO programming results . . . . . . . . . . . . . . . . 53
4.4.2 The RD-FIFO programming results . . . . . . . . . . . . . . . . 54
4.4.3 The Multiple-Queue-RTFIFO programming results . . . . . . . 54
4.4.4 The Hybrid-Multiple-Queue-RDFIFO programming results . . . 55
4.4.5 The Hybrid M-Q (RTFIFO-SJF) programming results . . . . . 55
4.5 Simulation and results analysis . . . . . . . . . . . . . . . . . . . . . . 56
4.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 |
| Côte titre : |
MAI/0847 |
Scheduling IoT Applications in Edge and Fog Computing Environments [texte imprimé] / Oussama Bencheikh, Auteur ; Dhikra Lamis Angag ; Chirihane Gherbi, Directeur de thèse . - [S.l.] : Setif:UFA, 2024 . - 1 vol (66 f .) ; 29 cm. Langues : Anglais ( eng)
| Catégories : |
Thèses & Mémoires:Informatique
|
| Mots-clés : |
IoT
Edge
Fog
Task Scheduling
RTFIFO |
| Index. décimale : |
004 - Informatique |
| Résumé : |
The notable evolution of computing paradigms, driven by the growth of IoT devices,
has led to the emergence of Fog computing, a decentralized approach that addresses
bandwidth, latency, and connectivity challenges, enhancing cloud-IoT communication.
The objective of this master’s thesis is to study the task scheduling mechanism in
the computing paradigms, specifically Fog computing. By ameliorating the RTFIFO
(Resources Then First In First Out) scheduling approach, aiming to minimize the
number of rejected tasks. The amelioration is represented by proposing several approaches
in order to realize our goal. The first approach is RD-FIFO (Resources-then-
Deadlines-First-In-First-Out) based on the deadline characteristics. The second one
is the Multiple-Queue-RTFIFO (Multiple-Queue Resources-Then-FIFO) based on the
arrival time and requested resources, and the third one is the Hybrid-Multiple-Queue-
RDFIFO (Hybrid Multiple-Queue-Resources-then-Deadlines-FIFO) based on the arrival
time, the requested resources, and the deadline at a time. The last one is Hybrid
M-Q (RTFIFO-SJF) (Hybrid Multiple-Queue-Resources-then-First-In-First-Out-
Shortest-Job-First), which is based on the arrival time, the requested resources, and
the service time. We based our contributions on the Divide-and-Conquer approach,
classifying tasks according to their deadlines and requesting resources to avoid missed
deadlines, the variety of deadlines and requested resources of a task. After programming
our proposal methods and simulating the execution results, the Hybrid M-Q
(RTFIFO-SJF) was found to be the best method for minimizing the rejected tasks |
| Note de contenu : |
Sommaire
Abstract i
R´esum´e ii
Table of contents ix
List of figures xi
List of tables xii
List of algorithms xiii
Abbreviations xv
Introduction 1
1 State of the art 3
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Internet of Things (IoT) . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.1 IoT Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.2 Applications domains . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.3 IoT Characteristics . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.4 IoT Components . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.5 IoT Architectures . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.6 IoT Advantages and Disadvantages . . . . . . . . . . . . . . . . 11
1.3 Cloud Computing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.3.1 Definition of Cloud Computing . . . . . . . . . . . . . . . . . . 12
1.3.2 Cloud Characteristics . . . . . . . . . . . . . . . . . . . . . . . . 12
1.3.3 Types of Cloud . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.4 Edge Computing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.4.1 Definition of Edge Computing . . . . . . . . . . . . . . . . . . . 14
1.4.2 Edge Computing Architecture . . . . . . . . . . . . . . . . . . . 15
1.4.3 Basic Components of Edge Computing . . . . . . . . . . . . . . 15
1.4.4 Edge Computing Benefits . . . . . . . . . . . . . . . . . . . . . 16
1.4.5 Motivation, challenges and opportunities in edge computing . . 16
1.5 Fog Computing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.5.1 Definition of Fog Computing . . . . . . . . . . . . . . . . . . . . 17
1.5.2 Basic Components of Fog Computing . . . . . . . . . . . . . . . 17
1.5.3 Fog Computing Benefits . . . . . . . . . . . . . . . . . . . . . . 18
1.6 Difference Between Cloud, Fog and Edge Computing . . . . . . . . . . 19
1.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2 Related Review 22
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2 Task Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2.1 Task Scheduling Definition . . . . . . . . . . . . . . . . . . . . . 22
2.2.2 Task Scheduling Characteristics . . . . . . . . . . . . . . . . . . 23
2.3 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.3.1 Task scheduling approaches for Fog Computing . . . . . . . . . 24
2.3.2 Computation Offloading and Scheduling in Edge-Fog Cloud Computing
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.3.3 Efficient Task Scheduling for Applications on Clouds . . . . . . 30
2.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3 Contribution 33
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.2 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.3 Problematic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.4 Proposed approaches . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.4.1 RD-FIFO(Resources then Deadlines First In First Out) . . . . . 35
3.4.2 MultiQueueRTFIFO (Multiple-Queue Resources-Then-First-In-
First-Out) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.4.3 Hybrid Multiple-Queue-RDFIFO (Hybrid Multiple-Queue-Resourcesthen-
Deadlines-First-In-First-Out) . . . . . . . . . . . . . . . . . 42
3.4.4 Hybrid M-Q (RTFIFO-SJF) (Hybrid Multiple-Queue-Resourcesthen-
First-In-First-Out-Shortest-Job-First) . . . . . . . . . . . . 46
3.5 Comparison table of contributions . . . . . . . . . . . . . . . . . . . . . 50
3.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4 Implementation and Results 52
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.2 Programming Tool . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.3 Programming Language . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.4 The programming results . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.4.1 The RTFIFO programming results . . . . . . . . . . . . . . . . 53
4.4.2 The RD-FIFO programming results . . . . . . . . . . . . . . . . 54
4.4.3 The Multiple-Queue-RTFIFO programming results . . . . . . . 54
4.4.4 The Hybrid-Multiple-Queue-RDFIFO programming results . . . 55
4.4.5 The Hybrid M-Q (RTFIFO-SJF) programming results . . . . . 55
4.5 Simulation and results analysis . . . . . . . . . . . . . . . . . . . . . . 56
4.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 |
| Côte titre : |
MAI/0847 |
|
Ajouter le résultat dans votre panier Affiner la recherche
