RAJIV GANDHI INSTITUTE OF TECHNOLOGY

GOVERNMENT ENGINEERING COLLEGE

KOTTAYAM - 686 501

DEPARTMENT OF
COMPUTER SCIENCE AND ENGINEERING

CSQ 413 - SEMINAR REPORT

SMRETO: Stable Matching for Reliable and Efficient Task Offloading in
Fog-Enabled IoT Networks

Submitted by
ARUN MARTIN
(REG NO: KTE21CS013)

Seventh Semester B.Tech in CSE

APJ ABDUL KALAM TECHNOLOGICAL UNIVERSITY

THIRUVANANTHAPURAM
NOVEMBER 2024
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
RAJIV GANDHI INSTITUTE OF TECHNOLOGY
GOVERNMENT ENGINEERING COLLEGE
KOTTAYAM - 686 501

CERTIFICATE

This is to certify that this seminar report entitled "SMRETO: Stable

Matching for Reliable and Efficient Task Offloading in Fog-Enabled
IoT Networks" is a bonafide report of the seminar presented by ARUN
MARTIN (KTE21CS013) under our guidance towards partial fulfilment
of the requirement for the award of Degree of Bachelor of Technology in
Computer Science and Engineering of APJ Abdul Kalam Technological
University during the year 2024-2025.

Prof. Geethu Sasidharan Prof. Nisha K K.

Assistant Professor Assistant Professor
Seminar Guide Seminar Co-ordinator

Prof. Kavitha N
Associate Professor
Head of Department
 Acknowledgements
I would like to express my sincere gratitude to all those who have supported
and guided me throughout the preparation and completion of this seminar
report.
First and foremost, I am deeply thankful to Prof. Geethu Sasidharan,
my seminar guide, for her invaluable guidance, constant encouragement,
and insightful suggestions. Her expertise and support played a crucial role
in helping me shape this report.
I would also like to express my sincere gratitude to Dr. Prince A,
Principal for fostering an environment of academic excellence and for
providing me with the necessary resources and facilities to carry out this
work.
I would also like to extend my heartfelt thanks to Prof. Kavitha
N, Associate Professor & Head, Department of Computer Science
and Engineering, for her dedication to promoting quality education and
research has been a source of inspiration throughout this journey.
I would also like to express my heartfelt gratitude to Seminar Coordinator
Prof. Nisha K K for her support and guidance thorugh various phases of
seminar.
I am particularly grateful to my friends and classmates for their
encouragement and feedback, which inspired me to continuously improve
my work. Additionally, I owe a debt of gratitude to my family for their
unwavering support and motivation throughout this process.
Finally, I thank all those who have directly or indirectly contributed to
the successful completion of this seminar.
Thank you.

i
 Abstract
This seminar presentation that I am handling today will be exploring a
task offloading algorithm in fog- enabled IoT networks. The objective is
to suggest an energy efficient and minimal task outage algorithm for task
offloading in fog-enabled networks. The experiment provides an efficient
way for task offloading with minimal usage of computational resources of
the fog nodes taking advantage of variable sized VRUs(Virtual Resource
Units).
The proposed method includes two algorithms – one for providing
preferences for fog nodes and IoT tasks over opposite sets while the other
algorithm focuses on matching them both with using minimal computational
resources and energy efficiency. The energy consumption models and
network models are detailed .The proposed algorithm details the usage
of minimal resources for task completion for reducing task outages. The
experiment also consist of comparisons with similar algorithms comparing
aspects of mean task latency, system resource utilization, task outages and
energy consumption.

ii
 Contents

Acknowledgements i

Abstract ii

1 Introduction 1

2 Literature Review 3
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 Energy-efficient task offloading for time-sensitive
applications in fog computing [1] . . . . . . . . . . . . . . . 3
2.3 Intelligent deployment of dedicated servers: Rebalancing
the computing resource in IoT [2] . . . . . . . . . . . . . . 3
2.4 An optimal relay scheme for outage minimization in
fog-based Internet-of-Things (IoT) networks [3] . . . . . . . 4
2.5 Location of fog nodes for reduction of energy consumption
of end-user devices [4] . . . . . . . . . . . . . . . . . . . . 4
2.6 Prioritized task distribution considering opportunistic fog
computing nodes [5] . . . . . . . . . . . . . . . . . . . . . 4
2.7 LETO: An efficient load balanced strategy for task
offloading in IoT-fog systems [6] . . . . . . . . . . . . . . . 5
2.8 Resolving multitask competition for constrained resources
in dispersed computing: A bilateral matching game [7] . . . 5
2.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

3 Proposed System 7
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.2 System Model . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.3 Latency Model . . . . . . . . . . . . . . . . . . . . . . . . 8
3.3.1 Transmission Delay . . . . . . . . . . . . . . . . . . 8

iii
 Contents

3.3.2 Queuing Delay at the Fog Node . . . . . . . . . . . 9

3.3.3 Computation Latency at the Fog Node . . . . . . . . 9
3.3.4 Result Download Latency . . . . . . . . . . . . . . 9
3.4 Energy Consumption Model . . . . . . . . . . . . . . . . . 10
3.4.1 Energy Consumption of IoT devices . . . . . . . . . 10
3.4.2 Energy Consumption of Fog Nodes . . . . . . . . . 10
3.4.3 Total Energy Consumed . . . . . . . . . . . . . . . 10
3.5 Minimum Resource Requirement of IoT Device Tasks to
Reduce Task Outages . . . . . . . . . . . . . . . . . . . . . 10
3.6 Matching Concepts . . . . . . . . . . . . . . . . . . . . . . 11
3.7 Variable Sized VRUs and Quota of Fog Nodes . . . . . . . . 12
3.8 Proposed Algorithms . . . . . . . . . . . . . . . . . . . . . 13
3.8.1 Input Generation for Matching Algorithm . . . . . . 14
3.8.2 SMRETO Algorithm . . . . . . . . . . . . . . . . . 14
3.8.3 Working of SMRETO Algorithm . . . . . . . . . . 15
3.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

4 Simulation Setup and Result Analysis 19

4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4.2 Simulation Setup . . . . . . . . . . . . . . . . . . . . . . . 19
4.3 Results and Analysis . . . . . . . . . . . . . . . . . . . . . 20
4.3.1 Task Outages . . . . . . . . . . . . . . . . . . . . . 21
4.3.2 Fog Node Resource Utilization . . . . . . . . . . . . 22
4.3.3 Energy and Task Latency . . . . . . . . . . . . . . . 23
4.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

5 Conclusion 26

References 27

Dept of CSE - RIT - Kottayam iv

 List of Figures

2.1 Literature Review Comparison . . . . . . . . . . . . . . . . 6

3.1 The model of the Proposed system. . . . . . . . . . . . . . . 8

3.2 Matching with fixed and variable sized VRUs . . . . . . . . 13
3.3 Working of SMRETO Algorithm . . . . . . . . . . . . . . . 16

4.1 MATLAB Simulation Setup . . . . . . . . . . . . . . . . . 20

4.2 Task Outages . . . . . . . . . . . . . . . . . . . . . . . . . 21
4.3 Utilization of system resources . . . . . . . . . . . . . . . . 22
4.4 System energy consumed . . . . . . . . . . . . . . . . . . . 23
4.5 Mean energy per accepted task . . . . . . . . . . . . . . . . 23
4.6 Mean task latency . . . . . . . . . . . . . . . . . . . . . . . 24

v
 Chapter 1

Introduction
The development of fully autonomous systems using Artificial Intelligence
(AI) and learning techniques has been the primary focus of research
over the last decade. This has resulted in quantum advances in wireless
communications, advanced sensing and the Internet of Things(IoT). These
advancements have revolutionized the way humans and machines interact
with each other.
Future IoT applications will be extremely demanding in terms of data
rate, reliability, and connectivity. These demands paved the way for
the emergence of Fifth Generation (5G) communication systems, and
while 5G is still in the implementation phase, researchers have begun
to envision the next generation of communication networks, namely 6G.
With these technologies, billions of devices will be connected to each
other over the Internet. This will evolve the communication focus
from ubiquitous connectivity to automated and intelligent connectivity,
necessitating de-centralized computation closer to the network edge.
Fog computing is a decentralised computing architecture commonly
associated with IoT technology. The basis of fog computing is to
overcome the drawbacks of cloud computing such as centralised computing
architecture and usually large distance between cloud servers and IoT
devices.Although fog computing has many benefits for IoT applications,
there are a few QoS challenges that require special attention. Latency
improvement and energy efficiency continue to be the primary features of
QoS in fog computing; however, demand for additional QoS features such as
reduced task outages to improve network utilisation and energy efficiency,
has gained attention from many researchers in recent years.
When a task suffers from outage, QoS suffers, and users lose faith in the

1
 Chapter 1. Introduction

system’s ability to provide continuous services.Task outages can occur for

a variety of reasons, including scarcity of appropriate resources at the fog
node, an unexpected delay in task transmission, and a failure to allocate
resources while considering a task’s end-to-end resource requirement.
Matching theory is a simple algorithm that logically divides a fog node’s
available computation resources into fixed-sized Virtual Resource Units
(VRUs) and matches these VRUs to IoT device tasks, ensuring that all
players’ objectives are met. Fixed sized VRUs simplify the matching
process but have the drawback of providing all matched tasks with the same
resources from a fog node. The number of VRUs with a fog node determines
the maximum number of tasks that can be served by a fog node.
The proposal is that by using variable-sized VRUs rather than fixed sized
VRUs tailored to specific resource requirements of IoT device tasks, we can
greatly increase the number of useful VRUs per fog node. As a result, a fog
node will be able to serve more tasks with the same resources, reducing task
outages. Variable sized VRUs pose a serious matching problem because the
total number of VRUs formed from fog node computation resources cannot
be predicted in advance due to their variable size. This generates a unique
matching challenge in which the total capacity of a fog node to accept the
number of tasks is unknown until the matching process is completed. To
address this issue, we propose SMRETO, a novel many-to-one matching
algorithm.

Dept of CSE - RIT - Kottayam 2

 Chapter 2

Literature Review

2.1 Introduction
In this section, we discuss our literature review in the fog computing
environment, with a focus on reducing task outages through latency or
energy improvement with and without using matching techniques for
resource allocation. Our emphasis will be on comprehending how fog node
computation resources are logically partitioned into Virtual Resource Units
(VRUs) and then allocated to IoT device tasks using matching theory.

2.2 Energy-efficient task offloading for time-sensitive

applications in fog computing [1]
Y.L. Jiang, Y.S. Chen, S.W. Yang and C.H. Wu

The number of accepted tasks decreases because the end-to-end resource

requirement of a sensor device task is not considered when making resource
allocation decisions. As a result, this paper propose an energy-efficient
offloading decision mechanism that ensures no task outage of any accepted
task by considering both: (1) the task’s end-to-end processing time and,
(2) tasks already held in the fog node queue. Non-availability of sufficient
resources with the fog nodes and their poor cite planning also contribute to
a decrease in the number of accepted tasks, as this places an additional load
on network resources in order to complete targeted tasks in time.

2.3 Intelligent deployment of dedicated servers:

Rebalancing the computing resource in IoT [2]
Y. Wu, Y. Wang, Y. Wei and S. Leng

3
 Chapter 2. Literature Review

Achieved latency improvement through forward deployment of computing

servers to encourage fog nodes to offload their maximum tasks to these
servers. Forward deployment of resources also significantly reduces the
resources required to achieve latency, increasing the number of accepted
tasks.

2.4 An optimal relay scheme for outage minimization in

fog-based Internet-of-Things (IoT) networks [3]
B. Omoniwa, R. Hussain, M. Adil, A. Shakeel, A. K. Tahir, Q. U. Hasan

Achieved energy efficiency in Wireless Sensor Network (WSN) by using

fixed and mobile fog nodes to relay sensor node data to main fog node/cloud
servers. The mobile relay fog nodes adjust their location (i.e., it addresses
the fog node cite planning problem) to increase transmission energy and
ensure no task outages.

2.5 Location of fog nodes for reduction of energy

consumption of end-user devices [4]
R. A. C. da Silva and N. L. S. da Fonseca

Solved the fog node location and resource planning problem to improve
energy efficiency and increase the number of accepted tasks. It
accomplishes this by ensuring the availability of required resources at the
fog node and by processing the maximum number of tasks and applications
in the fog node.

2.6 Prioritized task distribution considering

opportunistic fog computing nodes [5]
Y. Kyung

Formulated a prioritised task distribution scheme that categorises incoming

task requests as delay sensitive or delay insensitive. Delay sensitive tasks
are processed by static fog nodes to meet the delay requirements, while
Dept of CSE - RIT - Kottayam 4
 Chapter 2. Literature Review

delay insensitive tasks are processed by opportunistic fog nodes to relieve

load on the fog nodes. This reduces task latency and outages.

2.7 LETO: An efficient load balanced strategy for task

offloading in IoT-fog systems [6]
C. Swain, M. N. Sahoo and A. Satpathy

Formulated the offloading problem as a one-to-many matching game with

minimum and maximum quotas to achieve balanced task assignments to
fog nodes while minimising task completion time and outages. He used
multi-stage DAA, in which initial matching is done with the minimum quota
of each fog node to ensure load balancing. If any tasks remain, DAA is run
again with the maximum fog node quota to match these tasks only.

2.8 Resolving multitask competition for constrained

resources in dispersed computing: A bilateral
matching game [7]
H. Wu, J. Zhang, Z. Cai, Q. Ni, T. Zhou, J. Yu

On the other hand, used a one-to-many matching game with the market
matching concept to achieve energy efficiency in the network. In this
concept, fog nodes act as vendors and tasks act as the buyers, with prices
fluctuating until a stable market situation is reached. Fixed sized VRUs are
used and IoT devices make their own matching decisions.

2.9 Summary
The research on task outages in non-matching and matching based
resource allocation appears to take two distinct approaches: non-matching
based techniques attempt to reduce task outages by reducing resource
requirements from fog nodes, allowing them to serve a greater number of
tasks with the same resources, whereas matching based techniques attempt
to reduce task outages by formulating preference profiles in such a way
Dept of CSE - RIT - Kottayam 5
 Chapter 2. Literature Review

that the number of accepted tasks at fog nodes is maximised. In review of

the literature, no work were found that used the matching technique to do
resource allocation in fog computing for minimum computation resource
requirements of tasks in order to minimise task outages. The reason for this
gap is obvious: the matching technique lacks the ability to allocate resources
for specific resource requirements of tasks in fog computing.
The parameters used to compare different offloading techniques are
summarised in Figure 2.1. As you can see SMRETO algorithm outperforms
in every aspect for an algorithm to perform over the alternative options even
providing the option of Variable VRUs which makes them way better over
other algorithms.

Figure 2.1: Literature Review Comparison

The paper proposes a novel concept of variable-sized VRUs with fog

nodes to make the resource allocation process flexible in the many-to-one
matching algorithm. These VRUs are sized based on the task’s exact
resource requirements. Only with variable-sized VRUs, a many-to-one
matching algorithm can allocate computation resources to tasks based on
their exact requirements. This conserves valuable fog node computation
resources, allowing a fog node to serve more tasks with the same resources.
With the introduction of variable-size VRUs, the scope of many-to-one
matching applications to resource allocation problems will be expanded.

Dept of CSE - RIT - Kottayam 6

 Chapter 3

Proposed System

3.1 Introduction
This chapter provides a detailed discussion on the system model and its
functioning, followed by an explanation of the latency and energy models.
It then covers the calculation of the minimum resource requirements for IoT
tasks and the concept of matching IoT tasks with fog nodes. Additionally,
the chapter details the concept of variable-sized VRUs. The proposed
algorithms and their mechanisms are also described in detail within the
chapter elaborately.

3.2 System Model

The paper considered an IoT-fog interconnection network, as shown in
Figure. 3.1. It consists of n fog nodes and m IoT devices, denoted as F
= {f1 ,f2 , . . . , fn } and D = {d1 , d2 , . . . , dm }, respectively. For
resource allocation decisions in the network, a fog node is designated as
the Fog Node Controller (FNC), and it assigns tasks to fog nodes using a
many-to-one matching game, as discussed later in this article. It is assumed
that each IoT device generates a single heterogeneous sized task, which is
represented by the task set, T = {t1 , t2 , . . . , tm }, where task tm corresponds
to the task generated by the IoT device dm .
It is assumed that IoT devices have limited computational capabilities
and must rely on fog node resources to complete their tasks. When a task
tm is generated, the IoT device dm sends an offloading request to the FNC
in the form of a tuple (Wm , Cbit , T max
m ), where Wm (in bits) represents the
input task size, Cbit (cycles) represents the number of Central Processor Unit
(CPU) cycles required to compute one bit of the task and, T max
m (seconds)

7
 Chapter 3. Proposed System

represents the task deadline. When using matching theory for resource
allocation, other researchers logically partition computation resources Cfn
of fog node fn into homogeneous sized VRUs, whereas VRUs between
different fog nodes are considered heterogeneous sized. In contrast, we
present a novel concept of variable sized VRUs with fog nodes, the size of
which adjusts dynamically to meet the precise resource requirements of IoT
device tasks.
The model of the Proposed system is shown in the following figure:

Figure 3.1: The model of the Proposed system.

3.3 Latency Model

The latency incurred in computing IoT device tasks at the fog node is
determined by:

3.3.1 Transmission Delay

It is the time it takes to transmit a task from an IoT device to a fog node.
It is assumed that an active up-link with dedicated bandwidth Bumn exists
between an IoT device dm and a fog node fn . The task uplink rate Rumn is
calculated as :

Dept of CSE - RIT - Kottayam 8

 Chapter 3. Proposed System

u
 
p g n
Rumn = Bumn log2 1 + mn2 (Eq.1)
σ
where, pumn represents the transmit power of dm , σ represents the white
noise power and gn represents the channel gain. The channel gain varies
inversely with the distance between dm and fn . The transmission time of a
task tm with size Wm is calculated as:

Wm
Tumn = u
(Eq.2)
Rmn

3.3.2 Queuing Delay at the Fog Node

This is the amount of time a task spends in the fog node queue before it
is executed. In this paper, dedicated fog node computation resources are
assigned to each task, resulting in no queuing delay at the fog node.

3.3.3 Computation Latency at the Fog Node

This is the amount of time spent at the fog node actually performing the
task. Given that cnm is the amount of computational resources allocated by
fog node fn for task tm from its total free computation resource Cfn , the
task computation latency at fn is calculated as:

Wm Cbit
Tfmn = (Eq.3)
cnm

3.3.4 Result Download Latency

It is the amount of time required to transmit the processed output from the
fog node to the relevant IoT device. In this paper, assumption is that the
output Om is very small in comparison to the input, so download latency is
ignored.
Total computation latency of task tm is the sum of all above latencies and
from Eq.2 and 3:

Wm Wm Cbit
Ttot
mn = u
+ (Eq.4)
Rmn cnm
Dept of CSE - RIT - Kottayam 9
 Chapter 3. Proposed System

3.4 Energy Consumption Model

Both IoT devices and fog nodes consume energy during the task offloading
process in the following ways:

3.4.1 Energy Consumption of IoT devices

The energy consumed by the IoT device while offloading tasks to the fog
node is calculated as:

Edmn =Pumn Tumn (Eq.5)

3.4.2 Energy Consumption of Fog Nodes

The fog node consumes energy in: (1) receiving the task offloaded from the
IoT device dm and (2) computing the received task. We know that the time
it takes an IoT device to transmit a task is the same as the time it takes a fog
node to receive it. If Prmn is the fog node power consumed by the fog node
in receiving the offloaded task and Pcn is the power consumed by the fog
node in task computation, then the energy consumed in task computation at
the fog node can be calculated as :

Efnm =Prmn Tumn + Pcn Tfmn (Eq.6)

3.4.3 Total Energy Consumed

It is the sum of energy consumed by IoT devices and the fog node:

Em =Edmn + Efnm (Eq.7)

3.5 Minimum Resource Requirement of IoT Device Tasks

to Reduce Task Outages
According to the previously stated definition, a task outage occurs when it
is not completed by the deadline. Eq.4 describes the relationship between

Dept of CSE - RIT - Kottayam 10

 Chapter 3. Proposed System

allocated fog node computation resources and task completion time. To

avoid an outage, the bare minimum computation resources cmin
nm required by
a task from the fog node can be determined by reverse-calculating the fog
node computation resources in Eq.4 by equating Ttot max
mn to Tm as:

Wm Cbit
cmin
nm = (Eq.8)
(Tmmax − Tmn
u )

Because an IoT device has a different distance and transmission rate

from each fog node, an IoT device task will require a different amount of
computation resources from each fog node to complete by the deadline.
The computation resource requirement in Eq.8 accounts for both task
transmission time from the IoT device to the fog node and task computation
time at the fog node. Only fog nodes with Cfn ≥ cmin
nm can complete tm
before the deadline and avoid an outage.

3.6 Matching Concepts

Formally, matching game is expressed as per definition 1:
Definition 1:
Let F and T be two sets of fog nodes and IoT device tasks, respectively. A
matching assignment defined over (F,T) has two sets of preference relations
≻F and ≻T that allows each player (fn ∈ F) to indicate preference over all
players (tm ∈ T) in the opposite set, and vice versa.
Definition 2:
Matching assignment is based on a mapping function λ , such that:

λ(tm ) ⊆ F and |λ(tm )| ≤ 1 (Eq.9a)

λ(fn ) ⊆ T and |λ(fn )| ≤ qn

s.t Σ qn
1 cnm ≤ cf n (Eq.9b)

fn ∈ λ(tm ) ⇐⇒ tm ∈ λ(fn ) (Eq.9c)

Dept of CSE - RIT - Kottayam 11

 Chapter 3. Proposed System

Condition (9a) shows that an IoT device task tm can only have one match
with single fog node only. The condition (9b) states that a fog node can
have qn matches with qn IoT device tasks only if the sum of computation
resources allotted to these IoT device tasks does not exceed the fog node’s
total free computational resources Cfn . Condition (9c) implies that tm is
matched to fn if fn is matched to tm .

3.7 Variable Sized VRUs and Quota of Fog Nodes

The quota represents a fog node’s capacity to accept a specific number of
tasks and it is determined by the number of VRUs into which fog node
computation resources are logically partitioned. In our work, we introduced
the concept of variable-sized VRUs that are tailored to the heterogeneous
resource requirements of tasks. The number of such VRUs that will be
formed from the computation resources of a fog node cannot be predicted
in advance. Hence, once the matching process starts, we must treat a fog
node’s quota as one until it receives a match. If a fog node receives a
match and has some free computation resources, its quota must be treated
as two. Similarly, the fog node’s quota increases until all of its computation
resources are depleted. We will know the quota of each fog node once the
matching process is completed.

Dept of CSE - RIT - Kottayam 12

 Chapter 3. Proposed System

Figure 3.2: Matching with fixed and variable sized VRUs

Consider Figure.3.2, which depicts a matching process with fixed-sized

VRUs on the left and a matching process with variable-sized VRUs on the
right. There are six tasks that require [0.5, 0.5, 0.6, 0.6, 0.7, 0.7] GHz CPU
cycles from the only fog node available to complete before the deadline. The
fog node has 4 GHz to serve all tasks, which are logically partitioned into
four fixed sized VRUs of 1 GHz each. Since the fog node has a quota of four,
it matches with four tasks and allocates 1 GHz of computation resources to
each, while two tasks suffer outage.
Variable-sized VRUs are precisely sized to the resource requirements of
IoT device tasks, so they will match all six tasks while saving 0.4 GHz of
the fog node’s computation resources. The fog node can use these resources
to accept more tasks. In Figure.3.2. If we are in the middle of the matching
process, the fog node’s quota will be seven, and if the matching process is
finished, the fog node’s quota will be six.

3.8 Proposed Algorithms

In this model, two algorithms are used in FNC to match fog node
computation resources to tasks:

Dept of CSE - RIT - Kottayam 13

 Chapter 3. Proposed System

3.8.1 Input Generation for Matching Algorithm

Calculates the transmission rate between IoT devices and fog nodes to
determine the minimum resource requirement cmin
nm for each task tm from
each fog node. Generates association sets and preference profiles using the
steps shown in Algorithm 1.
Algorithm 1 Input Generation for Matching Algorithm
max
Input : Wm , Cm , Tm , and CSI
Output: cmin A A
nm , fn , tm , ≻fn , and ≻tm
1 for ∀t do
2 for ∀f do
3 Calculate transmission rate Rumn
Calculate resource requirement cmin
nm
Generate association sets
4 end
5 end
6 for ∀t ∈ fnA do
7 Calculate fog nodes preference profile ≻fn
8 end
9 for ∀f ∈ tA
m do
10 Calculate IoT device task preference profile ≻tm
11 end

3.8.2 SMRETO Algorithm

The proposed SMRETO is a modified DAA implementation that uses

variable-sized VRUs with fog nodes. SMRETO computes fog node quota
on the go, based on the resource requirements of the held task proposal and
the fog node’s remaining computation resources. The steps involved are
shown in Algorithm 2.

Dept of CSE - RIT - Kottayam 14

 Chapter 3. Proposed System

Algorithm 2 Proposed Matching Algorithm

Input : Cn , cmin A A
nm , fn , tm , ≻fn , and ≻tm
Output: Matching assignment: λ
1 For better understanding, lets name the proposing task as tp ,
proposals held as th , and rejected proposal as tr .
2 while (∀t, λ(tm ) ⊆ F ∨ tA
m = ϕ) do
3 for ∀t do
4 Propose top fn in ≻tm .
if (first proposal with fn ) then
5 Hold tp .
6 else if (th ≻fn tp ) then
7 if (∀ proposals Σ cmin
nm ≤ Cnm ) then
8 Hold tp .
9 else
10 Reject tp and ∀tm′ s.t. tp ≻fn tm′ delete tm′
′
from fnA and fn from tA
m .
11 end
12 else
13 if (∀ proposals Σ cmin
nm ≤ Cnm ) then
14 Hold tp along with other th .
Reject tp and ∀tm′ s.t. tp ≻fn tm′ delete tm′
′
from fnA and fn from tA
m .
15 else
′ ′
16 for tp and ∀th s.t. tp ≻fn th do
17 Keep rejecting lowest proposals in ≻fn until Σ cmin
nm ≤ Cnm .
′
∀tm′ s.t. tr ≻fn tm′ delete tm′ from fnA and fn from tA
m .
18 end
19 end
20 end
21 end
22 end

3.8.3 Working of SMRETO Algorithm

The quota of all fog nodes is set to one. IoT device tasks propose the
fog node in the order defined by their preference profile ≻tm . For the
first proposal, if the fog node has more computation resources than the
minimum resource requirements of the proposing task, the proposal is held.
For the remaining proposals, SMRETO compares the preference of the new
proposal to the preference of the held proposals. If the preference for the
new proposal is lower than the preference for the held proposals, SMRETO
determines whether the fog node has enough remaining resources to serve
both the new and held proposals.

Dept of CSE - RIT - Kottayam 15

 Chapter 3. Proposed System

If the fog node has the required resources, all proposals are retained;
otherwise, the new proposal is rejected. All tasks in fA
n that have not yet
proposed to fn , but are lower in the preference profile ≻fn than the rejected
proposal are removed from fA A
n and fn is removed from tm′ . (This step
ensures that no lower priority tasks are accepted under any circumstances
if a higher priority task is rejected.)

Figure 3.3: Working of SMRETO Algorithm

In case 1 of Figure.3.3, when task 7 proposes fog node, regardless

of its preference over the held proposals, the proposal of task 7 is held
because fog node has enough resources to compute task 7 with already held
proposals. If the new proposal has a higher preference than at least one of
the held proposals, SMRETO determines whether the fog node can serve
all of the proposals or not. If yes, all proposals are retained; otherwise,
SMRETO evaluates the serviceability of new and held proposals with a
lower preference than the received proposal. It starts rejecting the held
proposals in reverse order of ≻fn until the resource requirements of the
remaining proposals can be met within Cfn . Even after rejecting all held

Dept of CSE - RIT - Kottayam 16

 Chapter 3. Proposed System

proposals with lower preference than the proposing task, the fog node may
lack the resources to accept that task. In that case, the proposing task is also
rejected.
In case 2 of Figure.3.3, when task 5 proposes the fog node, its priority
order with the fog is higher than held proposals of tasks 1, 7, and 6. Task
5 requires 0.9 GHz resources, but the fog node only has 0.3 GHz of free
computation resources. Thus, the fog node cannot retain the proposal of task
5, and if it rejects the proposal of task 5, it must also reject the proposals of
tasks 1, 7, and 6. To avoid large scale rejections, the fog node first rejects the
least preferred of the fog node’s held proposals, task 6, and then determines
whether it can now serve the remaining held proposals. The fog node still
lacks the resources required to compute the remaining tasks. The fog node
then rejects the least preferred held proposal of task 7 and finds that it can
now serve the remaining tasks. The fog node retains proposals of tasks 5
and 1 and removes tasks 7, 6, and 8 from its association set. The fog node
updates its quota information.
The rejected IoT device task proposes to the next fog node in its
preference profile. The process is repeated until all tasks are either matched
or they have exhausted the options of fog nodes in their association sets.
The proposed SMRETO starts matching with a fog node quota value of
one. With each new proposal, SMRETO recalculates a fog node’s quota as:
(a) If the fog node keeps the new proposal along with the held proposals, the
fog node’s quota is increased by one; (b) If the new proposal is accepted but
one of the held proposals is rejected, fog node’s quota remains unchanged,
and (c) If more than one held proposal is rejected, the fog node’s quota is
reduced by one less than the number of held proposals rejected. The number
of matches with a fog node will be the final quota for the fog node.

3.9 Summary
This chapter presented the system model alongside a detailed diagram.
It then examined the latency and energy consumption models, outlining
expected latency, its influencing factors, and energy consumption. The

Dept of CSE - RIT - Kottayam 17

 Chapter 3. Proposed System

minimum resource requirements for tasks were calculated, and the

concept of matching IoT tasks with fog nodes was explained. The
advantages of variable-sized VRUs compared to fixed-sized ones were also
discussed. Finally, the proposed algorithms and their detailed operation
were thoroughly described.

Dept of CSE - RIT - Kottayam 18

 Chapter 4

Simulation Setup and Result Analysis

4.1 Introduction
The upcoming chapter will focus on the simulation setup, providing
a comprehensive overview of the environment and parameters used to
evaluate the system’s performance. It will also present a detailed analysis
of the results, addressing key factors such as task outages, mean task
latency, and system energy consumption. Each of these aspects will be
explored in depth to understand their impact on overall system efficiency.
Furthermore, the proposed method will be systematically compared against
existing solutions, highlighting differences and improvements. The results
will then be carefully analyzed and critically evaluated to draw meaningful
conclusions.

4.2 Simulation Setup

Setup a fog network simulation setup in MATLAB and implemented
the task offloading scenario. The value of key simulation parameters is
displayed in the table shown in Figure.4.1. The fog network consists of 5 fog
nodes spread across an area of 100 m ×100 m. The computation resources
(cycles/s) and the computational power (W) of fog nodes are considered to
be heterogeneous and uniformly distributed in the range of 4–6 GHz and
0.35-0.55 W respectively. The number of IoT devices are considered to
be in the range of 200 to 1000, with a difference of 100 devices between
simulation iterations. Each IoT device generates a single task with input
task size (bits), CPU cycles required to complete the task (cyles/s) and, task
deadline (s) uniformly distributed in the range of 300–600 Kb, 500–750
million cycles and, 20–30 s.

19
 Chapter 4. Simulation Setup and Result Analysis

Figure 4.1: MATLAB Simulation Setup

Each IoT device has an active up-link with a dedicated bandwidth of 10

MB with each fog node, ensuring no channel access wait time. Considering
PCS-1900 GSM band, the free space path loss in dB between an IoT device
dm and fog node fn is calculated as: PLm,n =38.02 + 20 logdm,n . The channel
gain gn is then calculated as: gn =10 −P Lm,n /10 . The communication channel
is assumed to be noisy, with noise power σ 2 =10 −10 .

4.3 Results and Analysis

The primary performance metric used to compare proposed SMRETO to
baseline schemes is the reduction in the number of task outages under
different workload scenarios. The auxiliary performance metrics are the
percentage of total available computation resources used, total system
energy consumed, mean energy per task measured in Joules, and task
execution time measured in seconds.
The proposed SMRETO allocates the bare minimum computation
resources to each task in order to conserve fog node resources and serve
more tasks with the same fog node resources. If some fog node computation
resources remain unused in low workload scenarios, we can scale up the
allocated resources from unused fog node computation resources to improve
Dept of CSE - RIT - Kottayam 20
 Chapter 4. Simulation Setup and Result Analysis

energy efficiency even further.

4.3.1 Task Outages

Figure 4.2: Task Outages

Figure 4.2 shows the number of task outages experienced by all of the
schemes under consideration. The results clearly show that the proposed
scheme SMRETO outperforms other competing algorithms in terms of task
outages. Other baseline schemes can only match SMRETO’s performance
in low workload scenarios (when the number of tasks is low), whereas
SMRETO performs best in high workload scenarios. The key to such
performance is allocating resources for task deadlines in order to maximise
the number of accepted tasks at the fog nodes. This is made possible by
variable-sized VRUs with fog nodes that can precisely size to the resource
requirements of the matched IoT device tasks. The results show that with
variable-sized VRUs, task outages occur only when fog node resources are
completely depleted in high workload scenarios.

Dept of CSE - RIT - Kottayam 21

 Chapter 4. Simulation Setup and Result Analysis

4.3.2 Fog Node Resource Utilization

Figure 4.3: Utilization of system resources

Figure 4.3 shows the percentage of total fog node resources used to serve
the accepted tasks. In comparison to the baseline schemes, the proposed
SMRETO uses the least amount of the fog node’s computation resources
to compute the same number of tasks. In contrast, other baseline schemes
use more resources to serve a smaller number of tasks. When these results
are compared to those in Figure 4.2, they show that in a high workload
scenario, some fog node resources remain unused, while the baseline
schemes experience task outages. This inability to fully utilise available
resources stems from the inherent limitation associated with fixed-size
VRUs, which are always under-sized or over-sized in comparison to IoT
device resource requirements. Only over-sized VRUs will be matched to an
IoT device task to avoid task outage. When the system is overloaded, there
will always be some under-sized VRUs and some IoT device tasks with high
resource demands, both of which will remain unmatched. The solution is to
use flexible sized VRUs, as SMRETO has done.

Dept of CSE - RIT - Kottayam 22

 Chapter 4. Simulation Setup and Result Analysis

4.3.3 Energy and Task Latency

Figure 4.4: System energy consumed

Figure 4.5: Mean energy per accepted task

Dept of CSE - RIT - Kottayam 23

 Chapter 4. Simulation Setup and Result Analysis

Figure 4.6: Mean task latency

Figure 4.4 shows the system energy consumed in computing all accepted
tasks, Figure 4.5 shows the corresponding mean energy consumed in
computing a single task, and Figure 4.6 shows the mean task latency.
The three figures show the results when the proposed SMRETO fully
utilises the fog node computation resources. These figures show that
when the workload is low to medium, SMRETO outperforms all baseline
schemes. This is because variable-sized VRUs in the proposed SMRETO
can dynamically adjust their sizes and use all available computation
resources. However, when the workload is high, even the proposed
SMRETO experiences task outages. In this case, SMRETO consumes all
fog node computation resources to avoid task outages and has no spare
computation resources to improve energy efficiency. In such cases, the
proposed SMRETO algorithm trades off energy and time efficiency for a
lower number of task outages.

4.4 Summary
In this chapter, the simulation setup for the proposed system was established
using MATLAB, with a detailed explanation of all relevant parameters
and configurations. The obtained results were thoroughly compared across

Dept of CSE - RIT - Kottayam 24

 Chapter 4. Simulation Setup and Result Analysis

multiple domains with existing algorithms, including METO, SPATO, and

ME. A comprehensive analysis was conducted to evaluate the performance
of these algorithms under varying workload conditions, ranging from
low to high. The behavior of each algorithm was examined in detail,
allowing for a nuanced comparison of their effectiveness across different
scenarios. The chapter provides an in-depth assessment of these conditions,
offering insights into how each algorithm responds to changing demands
and workloads.

Dept of CSE - RIT - Kottayam 25

 Chapter 5

Conclusion
This paper have proposed an IoT device to fog node task offloading
algorithm to minimize the number of task outages and reduce the system
energy consumption. To achieve these goals, the proposed technique uses
variable sized computing resources on the fog nodes (known as VRUs)
and IoT task requirements are based on the task deadline. The proposed
algorithm utilizes a many-to-one matching algorithm to allocate IoT tasks
to the variable sized VRUs.
The preference profile of IoT tasks and fog computing resources are
developed to ensure reduction of system energy consumption. The
unmatched resources at the fog nodes are also utilized towards computing of
allocated tasks. Simulation results highlight the advantages of the proposed
algorithm in terms of task outages and system energy consumption. The
proposed model can make signficant changes in various fields essentially
in real time system required fields with minimal task outages paving a new
way for efficient task offloading in fog enabled IoT networks.

26
 References
[1] Y. Kyung. "Prioritized task distribution considering opportunistic fog
computing nodes". Sensors, vol. 21, no. 8, 2021.

[2] Y. Wu, Y. Wang, Y. Wei , and S. Leng. "Intelligent deployment of

dedicated servers: Rebalancing the computing resource in iot". Proc.
IEEE Wireless Commun. Netw. Conf. Workshops (WCNCW), pp. 1-6,
2020.

[3] C. Swain, M. N. Sahoo, and A. Satpathy. "SPATO: A student project

allocation based task offloading in IoT-fog systems". IEEE Int. Conf.
Commun, 2021.

[4] R. A. C. da Silva , and N. L. S. da Fonseca. "Location of fog nodes for

reduction of energy consumption of end-user devices". IEEE Trans.
Green Commun. Netw., vol. 4, no. 2, 2020.

[5] F. Chiti, R. Fantacci, and B. Picano. "A matching game for tasks
offloading in integrated edge-fog computing systems". Trans. Emerg.
Telecommun. Technol., vol. 31, no. 2, 2020.

[6] C. Swain,M. N. Sahoo , and A. Satpathy. "LETO: An efficient load

balanced strategy for task offloading in iot-fog systems". Proc. IEEE
Int. Conf. Web Services (ICWS), pp. 459-464, 2021.

[7] C. Swain,M. N. Sahoo, A. Satpathy,K. Muhammad,S. Bakshi,

J. J. P. C. Rodrigues,and V. H. C. de Albuquerque. "METO:
Matching-theory-based efficient task offloading in IoT-fog
interconnection networks". IEEE Internet Things J., vol. 8, no.
16, 2021.

[8] U. M. Malik, M. A. Javed, J. Frnda, and J. Nedoma. "SMRETO: Stable

matching for reliable and efficient task offloading in fog-enabled IoT
networks". IEEE Access, vol. 10, 2022.

27
 Chapter 5. REFERENCES

[9] K. B. Letaief, Y. Shi, J. Lu, and J. Lu. "Edge artificial intelligence

for 6g: Vision, enabling technologies, and applications". IEEE J. Sel.
Areas Commun., vol. 40, no. 1, 2022.

[10] M. A. Javed,M. Z. Khan, U. Zafar,M. F. Siddiqui, R. Badar, B. M. Lee,

and F. Ahmad. "ODPV: An efficient protocol to mitigate data integrity
attacks in intelligent transport systems". IEEE Access, vol. 8, 2020.

[11] F. Chiti, R. Fantacci, and B. Picano. "A matching theory framework

for tasks offloading in fog computing for IoT systems". IEEE Internet
Things J., vol. 5, no. 6, 2018.

[12] Y.-L. Jiang, Y.-S. Chen, S.-W. Yang, and C.-H.Wu. "Energy-efficient
task offloading for time-sensitive applications in fog computing". IEEE
Syst. J., vol. 13, no. 3, 2019.

[13] H. Wu,J. Zhang, Z. Cai,Q. Ni,T. Zhou, J. Yu,,et al. "Resolving

multitask competition for constrained resources in dispersed
computing: A bilateral matching game". IEEE Internet Things
J., vol. 8, no. 23, 2021.

Dept of CSE - RIT - Kottayam 28