A Whale Optimization Algorithm Based Resource Allocation Scheme for Cloud-Fog Based IoT Applications

Abstract

Fog computing has been prioritized over cloud computing in terms of latency-sensitive Internet of Things (IoT) based services. We consider a limited resource-based fog system where real-time tasks with heterogeneous resource configurations are required to allocate within the execution deadline. Two modules are designed to handle the real-time continuous streaming tasks. The first module is task classification and buffering (TCB), which classifies the task heterogeneity using dynamic fuzzy c-means clustering and buffers into parallel virtual queues according to enhanced least laxity time. The second module is task offloading and optimal resource allocation (TOORA), which decides to offload the task either to cloud or fog and also optimally assigns the resources of fog nodes using the whale optimization algorithm, which provides high throughput. The simulation results of our proposed algorithm, called whale optimized resource allocation (WORA), is compared with results of other models, such as shortest job first (SJF), multi-objective monotone increasing sorting-based (MOMIS) algorithm, and Fuzzy Logic based Real-time Task Scheduling (FLRTS) algorithm. When 100 to 700 tasks are executed in 15 fog nodes, the results show that the WORA algorithm saves 10.3% of the average cost of MOMIS and 21.9% of the average cost of FLRTS. When comparing the energy consumption, WORA consumes 18.5% less than MOMIS and 30.8% less than FLRTS. The WORA also performed 6.4% better than MOMIS and 12.9% better than FLRTS in terms of makespan and 2.6% better than MOMIS and 4.3% better than FLRTS in terms of successful completion of tasks.

1. Introduction

The Internet of Things (IoT) has expanded very quickly, providing many services in different domains, such as traffic management, vehicle networks, energy management, healthcare, smart homes, among others [1,2,3]. Addressing diverse requirements means connecting end devices, such as sensors, smart mobile phones, actuators, advanced vehicles, advanced appliance, smart meters, etc. Although real-time tasks demand heterogeneous resource requirements for processing, the processing of tasks at end devices with limited resources run down the performance, which forces them to switch to other computing environments. Cloud computing with a large resource center can compute these tasks of end devices with on-demand resource requirements.

Cloud servers are usually located remotely from the end devices. With increasing of end devices the task offloading is also increased. This excessive data transfer most likely will create network congestion and degrade the performance of the network. Most of the applications cannot afford the delay in processing the tasks in the cloud [4,5], as this is detrimental to the application sensitivity.

The above paradox is addressed with fog computing [6], which works in the middle tier between cloud and end devices. The fog computing being closer to end devices provides high-quality services by satisfying the requirements of delay-sensitive tasks and reducing the workload of the cloud server.

The devices (routers, gateways, embedded servers, controllers, etc.) that have the capability of computation, storage, and communication are treated as fog nodes. These nodes with limited resources and computation capability may not satisfy the requirement of heterogeneous resources for multiple tasks execution at a time [7,8]. The improper resource allocation may change the order of execution of tasks, which may lead to low throughput and failure in achieving deadlines of tasks.

The majority of the research work concerning IoT applications concentrates on exploration of fog computing or cloud computing environments individually. A relatively unexplored dimension in this research arena is a hybrid environment that can handle both delay-sensitive data and non-sensitive data with equal efficacy. This hybrid environment, termed as the cloud–fog model, is formed by combining both the cloud environment and the fog environment. There has not been a very significant number of studies carried out on the cloud–fog model. Therefore, the intricacies in handling the real-time heterogeneous tasks with different features such as deadline, data size, arrival time, and execution time, etc., are another challenge in the cloud–fog model. In this present work, the first task at hand is to process the heterogeneous tasks by multiple queues. As the fog node is limited in resources and resource allocation is a NP-hard problem [9,10], it motivates us to use meta-heuristic techniques for optimally allocating resources. The recent optimization technique named whale optimization algorithm (WOA) gives more optimal results under many complex situations. Therefore, the second motivation is to employ the whale optimization and explore the optimal solution for allocating resources. Energy consumption is another issue that leads to worldwide carbon emissions problem; thus, the third motivation is necessitating minimization of energy consumption in the cloud–fog model [11,12,13].

The primary objective is resource allocation for heterogeneous real-time tasks in the cloud–fog model within the deadline requirement of tasks, which can improve the makespan, task completion ratio, cost function, and energy consumption. In this paper, a three-tier cloud–fog model with parallel virtual queues architecture is considered.

The significant contributions of this work are as follows:

1

The task classification and buffering (TCB) module is designed for classifying tasks into different types using dynamic fuzzy c-means clustering, and these classified tasks are buffered in parallel virtual queues based on enhanced least laxity time scheduling.

2

Another module, named task offloading and optimal resource allocation (TOORA), is modeled for deciding on offloading the task in cloud or fog and uses WOA to allocate the resources of the fog node.

3

The approach is evaluating the metrics, such as makespan, cost, energy consumption, and the successful completed tasks within the deadline and comparing them with other algorithms such as SJF, MOMIS, and FLRTS for performance evaluation.

4

When 100 to 700 tasks are executed in 15 fog nodes, the results show that the WORA algorithm saves 10.3% of the average cost of MOMIS and 21.9% of the average cost of FLRTS. When comparing the energy consumption, WORA consumes 18.5% less than MOMIS and 30.8% less than FLRTS. The WORA is also performed 6.4% better than MOMIS and 12.9% better than FLRTS in terms of makespan and 2.6% better than MOMIS and 4.3% better than FLRTS in terms of successful completion of tasks.

The structure of the remaining sections are organized as follows. The survey on resource allocation in different environments is presented in Section 2. In Section 3 system model is described and problem is formulated. Section 4 describes the optimal resource allocation algorithm in fog nodes. Section 5 presents the performance evaluation of our proposed algorithm. Finally, the conclusion and future work are presented in Section 6.

2. Related Work

Currently, fog computing is the most popular research area in terms of service management. Many researchers are focused on the concept, architecture, and resource management issues of fog computing. The fog computing paradigm as a virtual platform was introduced by Bonomi et al. [14]. Refs. [15,16,17] highlighted the issues and challenges related to fog computing that need to be solved.

The cloud node contains massive storage and processors with high-speed network connectivity and various application services [18,19,20]. For assigning services to suitable service nodes with appropriate distribution of workload in every node, Chen et al. [21] proposed RQCSA and FSQSM, which improved the efficiency and minimized queue waiting time and makespan. Behzad et al. [22] proposed the queue based hybrid scheduling algorithm for storing jobs in the queue according to the order of priority. The job with lower quantum time is allocated with the CPU and executed. Venkataramanan et al. [23] studied the problem due to overflow of queue in wireless scheduling algorithm. In [24], the stability of the queue was achieved by applying a reinforcement learning approach to Lyapunov optimization for resource allocation of edge computing. Similarly, Eryilmaz and Srikant [25] stated that the length of the queue is bounded with the setting of the Lyapunov function drift. Hence, the Lyapunov function is important to control the virtual queue length. Some researchers have also used this queuing theory in fog computing. Iyapparaja et al. [26] designed a model based on queueing theory-based cuckoo search (QTCS) to improve QoS of resource allocation. Li et al. [4] considered heterogeneous tasks to be placed in parallel virtual queues. The task offloading is decided on the basis of the urgency of the task based on laxity time.

In the real world, continuous streaming data are generated that are required for online analysis. Most adaptive clustering is application-specific, so Sandhir and Kumar [27,28] proposed a modified fuzzy c-means clustering technique called dynamic fuzzy c-means (dFCM) clustering with the aid of a synthetic dataset. Most of the researchers in [1,4,29] considered laxity time for prioritizing the tasks: the lower laxity time task will be executed first. The laxity time is also estimated on account of the deadline, execution time, and current time, which also decided the task offloading. Ali et al. [30] proposed a fuzzy logic task scheduling algorithm for deciding tasks to be executed either in the fog node or cloud center. The tasks with constraints such as deadline and data size exploited the heterogeneous resources of fog nodes, which improved makespan, average turnaround time, delay rate, and successful task completion ratio. According to Pham et al. [10], resource allocation is a non-linear programming problem and an NP-hard problem. Such types of problem can be solved using three methods, including heuristic, meta heuristics, and hybrid. As there is no optimal performance guarantee of the heuristic method, one is forced to adopt a meta-heuristic method, such as a whale optimization algorithm, as a recent efficient optimization method. Here, WOA was used for solving allocation of power, secure throughput, and offloading in mobile edge computing. Hosseini et al. [31] used WOA for optimal resource allocation and minimized the total run-time of requested services in cloud center. Several optimization techniques in different platforms were studied [32,33,34].

Several studies have proposed solving resource allocation problems in different networks.

Table 1. Related work on resource allocation in different systems.

Article	Ideas	Target System	Improved Criteria	Limitations
Li et al. [4]	Laxity time and Lyapunov optimization	Fog computing	Throughput and task completion ratio	No other parameters are considered
Bae et al. [24]	Reinforcement learning and Lyapunov optimization	Edge computing	Time-average penalty cost cost	Operates with general non-convex and discontinuous penalty functions
Iyapparaja et al. [26]	Queueing theory-based cuckoo search	Fog computing	Response time and energy consumption	Resource allocation to the edge node is challenging
Ali et al. [30]	Fuzzy logic	Cloud–fog environment	Makespan, average turnaround time, success ratio of the tasks, and delay rate	Large-scale network
Pham et al. [10]	Whale optimization algorithm	Wireless network	System utility, overhead	Small dataset of user
Li et al. [4]	Fuzzy clustering with particle swarm optimization	Fog computing	User satisfaction	Small dataset of tasks
Rafique et al. [9]	Novel bio-inspired hybrid algorithm (NBIHA)	Fog computing	Average response time	Small dataset of tasks
Sun et al. [35]	Non-dominated sorting genetic algorithm (NSGA-II)	Fog computing	Reduced service latency and improved stability of task execution	Other parameters such as cost is not considered
Taneja and Devy [36]	Module mapping algorithm	Fog–cloud Infrastructure	Energy consumption, network usage, and end-to-end latency	Only compared with traditional cloud infrastructure
Mao et al. [11]	Energy-performance trade-off multi-resource cloud task scheduling algorithm (ETMCTSA)	Green cloud computing	Energy consumption, execution time, overhead	Small task dataset
Bharti and Mavi [37]	ETMCTSA for underutilized resources	Cloud computing	Energy consumption, overhead	Used 100 cloudlets
Anu and Singhrova [38]	Hybridization of priority, genetic algorithm, and PSO	Fog computing	Reduced energy consumption, waiting time, execution delay, and resource wastage	Considered end devices
Jia et al. [39]	Double-matching strategy based on deferred acceptance (DA-DMS)	Three-tier architecture (cloud data center, fog node, and users)	High-cost efficiency	Large-scale network
Feng et al. [40]	Particle swarm optimization with Pareto-dominant	Cloud computing	Large-scaled instances, middle-scaled instances, small-scaled instances	Did not use complex tasks and resources
Ni et al. [41]	Priced timed Petri nets strategy	Fog computing	Makespan, cost	Did not consider average completion time and fairness

summarizes the methodology, policies, and limitations of the resource allocation problem. Some research work is discussed here. Li et al. [4] combined the method of fuzzy c-means clustering and particle swarm optimization to design a new resource scheduling algorithm that improved user satisfaction. Rafique et al. [9] proposed a novel bio-inspired hybrid algorithm (NBIHA) for task scheduling and resource allocation of fog node, which reduced the average response time. Sun et al. [35] designed a resource scheduling model using improved non-dominated sorting genetic algorithm (NSGA-II) for the same fog clusters by which improved task execution and reduced service latency. In [36], Taneja and Devy handled the modules of fog-cloud model and mapped the modules to the mapping algorithm, that gave better performance to energy consumption, network usage, and end-to-end latency than that of traditional cloud infrastructure. In [11], Mao et al. designed separate energy-aware algorithm and time-aware algorithm for handling the task in a heterogeneous environment and developed a combined algorithms ETMCTSA that managed and controlled the performance of the cloud on the basis of parameter $\alpha$ of the algorithm. Bharti and Mavi [37] adopted ETMCTSA and discovered that underutilized resources of the cloud can increase the usage of resources. Anu and Singhrova [38] modeled P-GA-PSO algorithm that allocate resources efficiently in fog computing that reduced delay, waiting time, and energy consumption compared to round-robin and genetic algorithms. In a three-layer computing network, Jia et al. [39] presented an extension of the deferred acceptance algorithm called double-matching strategy (DA-DMS) that was a cost-efficient resource allocation in which a paired partner cannot change unilaterally for more cost-efficiency. In [40], an algorithm based on a Pareto-domination mechanism to particle swarm optimization algorithm searched for a multi-objective optimal solution. Ni et al. [41] modeled a dynamic algorithm based on PTPN, where the user can use appropriate resources from the available group of resources autonomously. Both price and cost are considered for the completion of the task. Many such resource allocation algorithms in different systems are found in [42,43,44,45,46,47,48].

Most of the research discussed different resource allocation methods in the fog environment, the cloud environment, and wireless networks. These studies also tried to improve metrics (i.e., response time, makespan, consumption of energy, overhead, etc.). This paper adopts WOA which can allocate resources optimally. The metrics such as cost, makespan, task completion ratio, and energy consumption are improved and compared with recent studies. The abbreviation table presented in

Table 2. Abbreviations and description.

Abbreviation	Description
TCB	Task classification and buffering
TOORA	Task offloading and optimal resource allocation
WORA	Whale optimized resource allocation
SJF	Shortest job first
MOMIS	Multi-objective monotone increasing sorting-based
FLRTS	Fuzzy logic-based real-time task scheduling
FCM	Fuzzy c-means
dFCM	Dynamic fuzzy c-means
EDF	Earliest deadline first
WOA	Whale Optimization Algorithm
WOASU	Whale optimization algorithm spiral updating
WOAEP	Whale optimization algorithm encircling prey

lists all abbreviations that are used in this paper.

3. System Model

Considering end devices, fog layer and cloud layer a three-tier cloud-fog model is designed as shown in Figure 1.

End devices: The end devices $\left\{i_1,i_2,i_3,\dots ..,i_n\right\}$ include sensors, actuators, mobile vehicles, smart cameras, etc. The end devices generate tasks $\left\{T_1,T_2,T_3,\dots ..,T_n\right\}$ with different resource requirements. These tasks are classified and buffered in fog node for further execution.

Fog layer: Fog nodes $\left\{f_1,f_2,f_3,\dots ..,f_m\right\}$ are the network devices (e.g., controller, router, gateways, embedded server). Every fog node consists of a set of containers $\left\{c_{i1},c_{i2},c_{i3},\dots ..,c_{ik}\right\}$. The tasks require different resource requirements (e.g., CPU, bandwidth, memory, and storage configuration) to process the data. Therefore, each container contains a set of resources $\left\{r_{ij}^1,r_{ij}^2,r_{ij}^3,\dots ..,r_{ij}^l\right\}$ where $r_{ij}^l=\left\{CPU,bandwidth,memory\right\}$. Due to the limited resource of fog nodes, all tasks cannot process at fog nodes simultaneously, thus necessitating buffering of tasks in the queue.

Cloud layer: This layer has a cloud server that includes unlimited resources. The cloud is placed far from fog nodes, thus causing data transmission latency. Even if there is data transmission latency for transferring tasks to the cloud, it completes its processing without waiting for resources, because of unlimited resources.

In the fog layer, two modules are designed as follows:

• Task classification and buffering (TCB): On the arrival of tasks at the fog node, the similar type of tasks are gathered and buffered in parallel virtual queues according to their execution order.
• Task offloading and optimal resource allocation (TOORA): All the tasks may not be assigned with fog resources by their deadline. The tasks may wait long time in queue which may lead failure of execution. These tasks can be transferred to cloud layer and achieved the deadline. The transmission of tasks may increase the transmission cost, thus, TOORA try to assign maximum tasks with fog resources.

  Table 3. Notations and description.

  Sl. No.	Notation	Description
  1	$i_n$	Represents end devices
  2	$f_m$	Represents fog nodes
  3	$c_{ik}$	Containers of fog node
  4	$r_{ij}^l$	Resources of a container
  5	$T_i$	Individual task where $iϵ[1,n]$
  6	$arr{t}_i$	Arrival time of ith task
  7	$etlo{w}_i$	Execution lower bound time of ith task
  8	$etu{p}_i$	Execution upper bound time of ith task
  9	$dsiz{e}_i$	Data size of ith task
  10	$resp{t}_i$	Response time of ith task
  11	$d{t}_i$	Deadline time of ith task
  12	$le{n}_i$	Number of instructions of ith task
  13	${\mu }_{ij}$	Membership of ith task to jth cluster center
  14	$v_j$	Cluster center
  15	$\alpha$	Error threshold
  16	$V_{XB}$	Xie–Beni index
  17	$\beta$	Membership threshold
  18	$l{f}_i$	Laxity time of ith task
  19	$ED{F}_i$	Earliest deadline first of ith task
  20	$Q_c$	$type-c$ queue
  21	$l{f}^{max}$	Maximum laxity time of head task of the queue
  22	$l{f}_i^j$	Laxity time of ith task of jth queue
  23	$\overrightarrow{W_b\left(t\right)}$	Best agent
  24	$\overrightarrow{A},\overrightarrow{C}$	Coefficient vectors
  25	$\overrightarrow{r}$	Random vector value lies in $[0,1]$
  26	$\overrightarrow{a}$	Parameter controller
  27	b	Constant used for logarithmic spiral shape
  28	l	Random value in $[-1,1]$
  29	$W_i$	Represents whale
  30	$c_1$	Processing cost per time unit for cloud
  31	$cc$	Communication cost per time unit for cloud
  32	$cf$	Communication cost per time unit for fog
  33	$ef$	Energy per unit for execution of the task in fog
  34	$e_{idle}$	Energy used when fog node is idle
  35	$ec$	Energy per unit for execution of task cloud
  36	$e_{comm}$	Energy per unit for transmission of data

  represents all notations of this paper.

3.1. Process Flow Model

The process flow model shows how the tasks are executed in the cloud–fog model by assigning limited resources of fog nodes. The following are presented and shown in Figure 2.

1

Step-1: The end devices collect data and send task requests to the nearest fog node.

2

Step-2: The task requests transfer from fog node to the TCB.

3

Step-3: The resource usage, data size, arrival time, deadline, etc., are estimated.

4

Step-4: Tasks are classified into different types in the TCB, which can be buffered in the waiting queue by running an algorithm for ordering the task.

5

Step-5: Tasks are transferred to the waiting queue for buffering.

6

Step-6: A set of tasks of the queues are transferred to the TOORA for further processing.

7

Step-7: TOORA makes a decision of task offloading so that task may execute in cloud server or fog node.

8

Step-8: The tasks meant for offloading to the cloud are transferred to the cloud server. The tasks are sent back to the end devices that are not achieved the deadline.

9

Step-9: An optimal resource allocation scheduler is run in the TOORA module to optimally assign resources of the fog node to the task.

10

Step-10: As the result of the algorithm, the tasks are assigned to the fog nodes.

11

Step-11: Each task is processed in the respective node.

12

Step-12: After completion of task execution, the result is sent back to the end devices through the fog node.

3.2. Problem Formulation

We are considering a set of fog nodes $F=\left\{f_1,f_2,f_3,\dots ..,f_m\right\}$, where every fog node consists of set of containers $f_i=\left\{c_{i1},c_{i2},c_{i3},\dots ..,c_{ik}\right\}$, and each container contains set of resource blocks $c_{ij}=\left\{r_{ij}^1,r_{ij}^2,r_{ij}^3,\dots ..,r_{ij}^l\right\}$. The resource can be represented as the collection of $r_{ij}^l=\left\{CPU,bandwidth,memory\right\}$. The fog node has limited resource capacity. The total resource of a fog node is

$$R_f=\sum _{i=1}^m\sum _{j=1}^k\sum _{l=1}^l{r}_{ij}^l$$

(1)

The allocated resource of a fog node cannot exceed than total resource of the fog node. Let $P_{f}i$$\left(t\right)$ be total tasks that process at t time in fog node $f_i$ where each task has different resource requirement configuration (i.e, $r_{T}i$ ). The total resource requirement is

$$R\left(T_{P}fi\left(t\right)\right)=\sum _{i=1}^{P_{fi}\left(t\right)}{r}_{T}i$$

(2)

The constraint of resource allocation can be represented as follows:

$$R\left(T_{P}fi\left(t\right)\right)\le R_f$$

(3)

Example: Suppose a fog node $f_1$ has three containers $c_1$, $c_2$, and $c_3$, and each container has three resource requirement configurations $r_{ij}^1$, $r_{ij}^2$, and $r_{ij}^3$. All the resource requirements with different configuration of $\left\{CPU,bandwidth,memory\right\}$ are represented as follows:

    $f_1=\left[\begin{array}{ccc}\left\{800,1000,1200\right\}& \left\{1100,1400,800\right\}& \left\{1600,1600,1540\right\}\\ \left\{880,980,1090\right\}& \left\{650,200,580\right\}& \left\{1800,1400,1620\right\}\\ \left\{1600,1100,1520\right\}& \left\{1040,1500,1040\right\}& \left\{1300,950,1150\right\}\end{array}\right]$    

Let one task with resource requirement of $\left\{800,900,1150\right\}$ try to allocate the resource of fog node $f_1$. There are several solutions to allocate the required resource of fog node $f_1$ (e.g., $\left\{800,1000,1200\right\}$,$\left\{1600,1600,1540\right\}$, $\left\{1800,1400,1620\right\}$, $\left\{1600,1100,1520\right\}$, $\left\{1040,1500,1040\right\}$, and $\left\{1300,950,1150\right\}$ ). By considering higher numbers of fog nodes, the resource availability will be increased. If we consider another task with resource requirements (e.g., $\left\{1900,1800,1200\right\}$), it may not be allocated in fog nodes and offloaded to cloud server. Therefore, our task is making the decision that the task will be executed either in the cloud server or a fog node and tasks will be optimally allocated the resources of fog nodes that processed at time t.

4. Proposed Work

To solve the above problem, two modules—task clasification and buffering (TCB) and task offloading and optimal resource allocation (TOORA)—are modeled. The working process of these modules is given below.

4.1. Task Classification and Buffering (TCB)

Due to computation incapability of end devices, the tasks are transferred to nearest fog. The latency-sensitive tasks need to be processed first, thus these tasks are transferred to fog node. As noted above, the fog nodes are limited in resources and prediction of resource allocation is not immediately possible, that forced for buffering of tasks in the queue. If the queue length is long, then the time complexity is high. Similar to [4], parallel virtual queues are considered for buffering the same type of tasks into separate virtual queues, which helps to reduce the time complexity, as shown in Figure 3.

Theorem 1.

Parallel virtual queues reduce the time complexity.

Proof. 

If a single queue with length M is considered for buffering tasks, then the time complexity for buffering all tasks is $O\left(M\right)$. If we consider four types of tasks that can be buffered in four separate virtual queues, then each queue length is $O(M/4)$. So, the time complexity is also decreased to $O(M/4)$.    □

The real-time tasks $T=\left\{T_1,T_2,T_3,\dots ..,T_n\right\}$ are streaming continuously from end devices and transferred to fog nodes. Each Task $T_i$ can be represented with $\left\{arr{t}_i,etlo{w}_i,etu{p}_i,dsiz{e}_i,le{n}_i,resp{t}_i,d{t}_i\right\}$, where $arr{t}_i$, $etlo{w}_i$, $etu{p}_i$, $dsiz{e}_i$, $le{n}_i$, $resp{t}_i$, $d{t}_i$ present arrival time, execution lower bound time, execution upper bound time, data size, number of instructions, response time, and deadline of the ith task, respectively. Assume that the tasks arrive at fog nodes in equal time intervals. The $arr{t}_i$, $dsiz{e}_i$, and $d{t}_i$ of a task cannot be predicted before the task’s arrival. The execution time of the task is also not predicted before completion of the task. However, the upper and lower bounds of execution time (i.e., $etlo{w}_i$ and $etu{p}_i$) can be estimated using machine learning algorithms proposed in [49]. As per estimation, $etu{p}_i$ should not exceed $d{t}_i-arr{t}_i$. Here, we set $etu{p}_i=d{t}_i-arr{t}_i$. Taking the above parameters of the task, the tasks can be classified into different types. The similar tasks can be grouped using a clustering algorithm. The tasks are overlapping, hence the FCM clustering algorithm is applied so that each task has a strong or weak association to the clusters. For the set of tasks T, the association to each cluster can be calculated as follows:

$$J_m(U,V;T)=\sum _{i=1}^n\sum _{j=1}^c{\left({\mu }_{ij}\right)}^m{∥T_i-v_j∥}^2$$

(4)

where n is the total tasks, m is the fuzziness index $mϵ\left[1,\infty \right]$, and ${\mu }_{ij}$ represents the membership of the ith task to jth cluster center. $(U,V)$ can minimize $J_m$ when $m>1$ and $∥T_i-v_j∥>2$ for all i and j. Then ${\mu }_{ij}$ is

$${\mu }_{ij}=1/\sum _{k=1}^c{\left(\frac{∥T_i-v_j∥}{∥T_k-v_j∥}\right)}^{\frac{2}{m-1}}$$

(5)

The cluster center can be calculated as

$$v_j=\frac{{\sum }_{i=1}^n{\left({\mu }_{ij}\right)}^m{T}_i}{{\sum }_{i=1}^n{\left({\mu }_{ij}\right)}^m}$$

(6)

An iteration technique is applied until the minimum of $J_m$ or minimum error criteria are satisfied. An error threshold $\alpha$ can satisfy the condition, ${∥V_{t-1}-V_t∥}_{err}\le \alpha$. The tasks are selected into a cluster using validity index. The Xie–Beni index [27,28] $V_{XB}$ is one of widely used validity index is used here and can be defined as

$$V_{XB}\left(U,V;T\right)=\frac{{\sum }_{j=1}^c{\sum }_{i=1}^n{\mu }_{ij}^2{∥T_i-v_j∥}^2}{n\left(\underset{\underset{i\ne k}{⏟}}{min}\left\{∥v_j-v_k∥\right\}\right)}$$

(7)

Fuzzy c-means cluster can classify the tasks for a given time interval t. As the tasks are streaming continuously, dFCM [27] is used adaptively to update cluster centers. A new cluster center is generated automatically with new cluster generation. Initially, $cmin$ number of clusters are generated, where $cmin\ge 2$. Upon arrival of new tasks, the membership of the present cluster is calculated. If the maximum membership value of the task exceeds or equals to membership threshold value ($\beta$), then it takes a new cluster center and generates a new cluster. Membership threshold ($\beta$) can avoid evaluation of cluster validity every time the tasks arrive. If the tasks satisfy the cluster membership, then there is no need to check for other, better clusters. The validity index is also evaluated when new centers are dissimilar to old ones. Then $\beta$ can have the condition

$$∥V_{old}-V_{new}∥>\beta$$

(8)

Let C number of clusters are there in time t and maximum membership value of a task is lower than $\beta$ then validity of clusters C is compared with $C-2$ to $C+2$. The clusters are generated using FCM and evaluated the validity index. The new cluster centers are generated for deviated tasks. This process is repeated to get the cluster center of best validity index until the arrival of tasks stop. The algorithm of task classification is as follows.

Algorithm 1 presents task classification using dFCM, which is discussed as follows. In this paper, an algorithm is presented using number of lines, and here, we consider the line number as a step. The parameters, such as threshold error $\alpha$, membership threshold $\beta$, and range of c (i.e., number of clusters) are initialized in step-1. Here we are considering that tasks are coming in the same interval of time, hence $tmax$ is considered as the last interval. Time interval t is initialized with 0 in step-2, and the initial number of cluster c is $cmin$ in step-3. The following steps are computed until t reaches $tmax$:

• In step-5, take all the arrival tasks T in time t.
• Calculate c number of cluster centers, i.e., $v_j$ and ${\mu }_{ij}$, using Equations (6) and (5); in steps 6 and 7.
• In steps 8–20, check if the maximum membership value (i.e., ${\mu }_{ij}$) of a task is more than or equal to membership threshold value (i.e., $\beta$). If true, then update ${\mu }_{ij}$ and $v_j$ until ${∥V_{t-1}-V_t∥}_{err}\le \alpha$, otherwise do steps 11–18 for $c-2$ to $c+2$ cluster centers. If no changes in clusters generated before then, store values of $v_j$, otherwise generate new cluster for deviated tasks and update c. Then, update ${\mu }_{ij}$ and $v_j$ until ${∥V_{t-1}-V_t∥}_{err}\le \alpha$ in step-20.
• In step-21, compute validity index using Equation (7) and select best clusters with best validity and assign to $C^{\prime }$ in step-22.
• Update the time interval t with t+1 in step-23.
• Finally, return clusters of tasks in step-25.

Algorithm 1 dFCM for task classification.

Input: Continuous streaming tasks $T=\left\{T_1,T_2,T_3,\dots ..,T_n\right\}$ Output: Cluster of tasks $C^{\prime }$ 1: Initialize $\mu$, $\beta$, $cmin$, $cmax$, $tmax$, $\alpha$; 2: $t\leftarrow 0$; 3: $c\leftarrow cmin$; 4: while  $t<tmax$ do 5:     Take a list of arrival tasks T at time t; 6:     Compute c number of $v_j$ using Equation (6); 7:     Compute ${\mu }_{ij}$ using Equation (5); 8:     if $max\left({\mu }_{ij}\right)\ge \beta$ then 9:         Update ${\mu }_{ij}$ and $v_j$ until ${∥V_{t-1}-V_t∥}_{err}\le \alpha$; 10:    else 11:         for number of clusters from c − 2 to c + 2 do 12:            if same number of clusters generated before then 13:                Store values of $v_j$; 14:            else 15:                Generate new cluster center for deviated tasks; 16:                $c\leftarrow c+1$; 17:            end if 18:         end for 19:         Update ${\mu }_{ij}$ and $v_j$ until ${∥V_{t-1}-V_t∥}_{err}\le \alpha$; 20:     end if 21:     Compute validity index using Equation (7); 22:     $C^{\prime }\leftarrow Selectclusterswithbestvalidity$; 23:     $t\leftarrow t+1$; 24: end while 25: Return clusters of task $C^{\prime }$;

On basis of the number of clusters, that number of virtual queues are modeled for buffering the tasks. The task can be buffered in the queue by comparing the level of urgency that presents how much time a task can wait. The level of urgency of the task can be determined multiple ways. Here, we are considering deadline and laxity time, which are most useful for finding maximum waiting time from current time. The upper bound execution time is considered as actual execution time of a task cannot predict before completion of task. The waiting time of a task is calculated using laxity time as follows:

$$l{f}_i=d{t}_i-\left(t+etu{p}_i\right)$$

(9)

According to the lowest laxity time, the tasks can be buffered in different queues. However, some tasks may have the same $l{f}_i$; those tasks are then grouped, and the earliest deadline first (EDF) time is considered for determining the waiting time. EDF of task i is calculated as follows:

$$ED{F}_i=d{t}_i-etu{p}_i$$

(10)

The algorithm for buffering the tasks in different queues is given below.

Algorithm 2 presents the task buffering in the queue that is discussed here. The results of Algorithm 1 are fed as the input of this algorithm (i.e., clusters of tasks). According to the number of clusters $C^{\prime }$, that number of queues are created (i.e., Q) in step-1. The following steps are computed for each cluster $C^{\prime }$.

• Compute $l{f}_i$ using Equation (9); for each task $T_i$ in step-4.
• Sort all the tasks $T_i$ according to $l{f}_i$ in ascending order in step-6.
• If any tasks have similar $l{f}_i$, then group them and store them in $LT$ in step-8.
• For each task of $LT$, compute $ED{F}_i$ using Equation (10), and sort the tasks according to $ED{F}_i$ in ascending order in steps 10–13.
• Insert all the tasks $T_i$ in queue $Q_i$ according to their $l{f}_i$ and $ED{F}_i$ in step-14.
• Finally, return the queues Q in step-16.

Algorithm 2 Buffering task in queues.

Input: Cluster of tasks $C^{\prime }$ Output: Tasks buffered in queues Q 1: Take number of queues with number of clusters $C^{\prime }$; 2: for each cluster c in $C^{\prime }$ do 3:     for each tasks $T_i$ in c do 4:         Compute $l{f}_i$ using Equation (9); 5:     end for 6:     Sort all the tasks $T_i$ according to $l{f}_i$ in ascending order; 7:     if some tasks having same $l{f}_i$ then 8:         $LT\leftarrow$ tasks of same $l{f}_i$; 9:     end if 10:     for each task $L{T}_i$ in $LT$ do 11:         Compute $ED{F}_i$ using Equation (10); 12:         Sort the task $L{T}_i$ in $LT$ according to $ED{F}_i$ in ascending order; 13:     end for 14:     Insert tasks of $T_i$ in queue $Q_i$ according to their $l{f}_i$ and $ED{F}_i$; 15: end for 16: Return Queues Q;

4.2. Task Offloading and Optimal Resource Allocation (TOORA)

The buffered tasks in virtual queues are going to be executed in either the cloud or fog node. The head tasks of each virtual queue are checked in parallel as to whether they will be executed in the cloud server or fog node or there may be a failure to achieve the deadline. The laxity time ($lf$) of the task is used to determine the participation of the number of tasks of each queue for further operations.

The laxity time $l{f}_i$ of tasks in each queue are compared with the maximum laxity time of the head task of the queues; if the laxity time $l{f}_i$ of the task is below or equivalent to maximum laxity time of the head task, then those tasks are fetched for further processing, which can be represented as follows:

$$l{f}^{max}=max\left(l{f}_{HT}^j\right)whereHT\leftarrow head\left(Q_j\right)and\forall jϵ[1,c]$$

(11)

$$l{f}_i^j\le l{f}^{max}whereiϵT_i,jϵQand{T}_iϵQ_j$$

(12)

The fetched tasks from queues are further processed in TOORA for deciding whether the task will be offloaded or failed due to longer waiting time with three conditions as follows:

• When $l{f}_i^j=0$, the deadline and executable upper bound time are nearly the same, so the task cannot wait for longer time to execute in fog node. therefore, the task must be moved to the cloud server for successful completion.
• When $l{f}_i^j<0$, the executable upper bound time is more than the deadline, thus, the task cannot complete before the deadline and is sent back to end devices requesting to increase the deadline.
• When $l{f}_i^j>0$, the task has enough time for executing successfully at the fog node before the deadline.

Algorithm 3 can be represented as follows for task offloading:

Algorithm 3 Task offloading at fog node.

Input:Tasks in $C^{\prime }$-type queues Output:Tasks at fog node $N{F}_c$, cloud $N{C}_c$ and Failure task $NFai{l}_c$ 1: for $j=1$ to $C^{\prime }$ do 2:     Compute $l{f}^{max}$ using Equation (11); 3: end for 4: for $j=1$ to $C^{\prime }$ do 5:     for $T_i$ of $Q_j$ do 6:         if $l{f}_i^j\le l{f}^{max}$ then 7:            Remove $T_i$ from $Q_j$; 8:            $TE\leftarrow T_i$; 9:         end if 10:     end for 11: end for 12: for i in TE do 13:     if $l{f}_i^j==0$ then 14:         $N{C}_c\leftarrow i$; 15:     else if $l{f}_i^j<0$ then 16:         $NFai{l}_c\leftarrow i$; 17:     else 18:         $N{F}_c\leftarrow i$; 19:     end if 20: end for 21: Return Queues $N{C}_c$, $N{F}_c$ and $NFai{l}_c$;

Algorithm 3 presents the task offloading at the fog node, which can distinguish the tasks of different types of queues. It takes all the tasks of $C^{\prime }$-type queues and considers the tasks that are eligible for processing at that time. The number of tasks from each queue can be considered by computing steps 1–11. First, maximum laxity time of the head tasks of queues is computed in steps 1–3; next, the tasks from all $C^{\prime }$-type queues whose laxity time is less than or equal to $l{f}^{max}$ are selected and stored in $TE$ list in steps 4–11. In steps 12–20, for each task in $TE$, check if laxity time of the ith task is equal to zero, then that task will send to the cloud server; if laxity time of the ith task is less than zero, then that task is marked as a failure and sent back to end devices for increasing the deadline; otherwise it will be executed in fog node. Finally, the tasks for fog node, the cloud, and failure are returned in step-21.

According to parallel virtual queues, let the number of tasks of type-c queue in time slot t be $Q_c\left(t\right)$ and $Q_c\left(0\right)=0$. The tasks leave the queue when tasks are allocated resources in fog node or moved to the cloud server. The current length of type-c queue in a given time can be evaluated based on total tasks arrived and removed from the queue at the previous time slot. If $N_c$ is total tasks of type-c that arrived, then the length of the queue can be evaluated as follows:

$$Q_c(t+1)=max[Q_c\left(t\right)+N_c\left(t\right)-N{C}_c\left(t\right)-N{F}_c\left(t\right)-NFai{l}_c\left(t\right),0]$$

(13)

where $N{C}_c\left(t\right)$, $N{F}_c\left(t\right)$, and $NFai{l}_c\left(t\right)$ contain total tasks that are moved to the cloud, tasks allocated for resources at fog node, and tasks that are failed at time slot t.

To improve throughput and avoid starvation of tasks, the length of the $Q_c\left(t\right)$ can be controlled using a Lyapunov function as follows:

$$LD\left(t\right)=\frac{1}{2}{\left[\sum _{c=1}^{C^{\prime }}{Q}_c\left(t\right)\right]}^2$$

(14)

The Lyapunov drift, a difference of the Lyapunov function of two slots, can be defined as follows:

$$\Delta LD\left(t\right)=LD(t+1)-LD\left(t\right)$$

(15)

Applying Equations (13)–(15), we can rewrite as follows:

$\Delta LD\left(t\right)⩽B\left(t\right)-{\sum }_{c=1}^{C^{\prime }}{Q}_c\left(t\right)\left[N{F}_c\left(t\right)+N{C}_c\left(t\right)+NFai{l}_c\left(t\right)-N_c\left(t\right)\right]$

$whereB\left(t\right)=\frac{1}{2}{\sum }_{c=1}^{C^{\prime }}{\left[N{F}_c\left(t\right)+N{C}_c\left(t\right)+NFai{l}_c\left(t\right)-N_c\left(t\right)\right]}^2$

The conditional expected Lyapunov drift can be represented as follows:

$$\begin{array}{c}E\left[\left.\begin{array}{c}\Delta LD\left(t\right)\end{array}\right|Q_u\left(t\right)\right]⩽B-{\displaystyle \sum _{c=1}^{C^{\prime }}}{Q}_c\left(t\right)E\left[\left.\begin{array}{c}(N{F}_c\left(t\right)+N{C}_c\left(t\right)+NFai{l}_c\left(t\right)-N_c\left(t\right))\end{array}\right|Q_u\left(t\right)\right]\\ where{Q}_u\left(t\right)={\displaystyle \sum _{c=1}^{C^{\prime }}}{Q}_c\left(t\right),E\left[\left.\begin{array}{c}B\left(t\right)\end{array}\right|Q_u\left(t\right)\right]\le BandB>0\end{array}$$

(16)

On basis of Lyapunov drift theory, if $\Delta LD\left(t\right)$ is equivalent to zero or non-positive value, then the queue length is stable. The stability of queue depends on ${\sum }_{c=1}^{C^{\prime }}{Q}_c\left(t\right)$. Although $N{C}_c\left(t\right)$, $N{F}_c\left(t\right)$, and $NFai{l}_c\left(t\right)$ can influence the value of Equation (16), the number of tasks in $N{C}_c\left(t\right)$ and $NFai{l}_c\left(t\right)$ are independent of tasks containing $N{F}_c\left(t\right)$. The tasks of $N{F}_c\left(t\right)$ are allocated to the available resources of fog nodes and satisfied the following:

$$\begin{array}{c}maximize{\displaystyle \sum _{i=1}^{C^{\prime }}}{Q}_c\left(t\right)N{F}_c\left(t\right),\\ s.t.{\displaystyle \sum _{i=1}^n}(N{F}_c\left(t\right)+N{F}_c^{{}^{\prime }}\left(t\right))r_{ij}^l\le R_f\end{array}$$

(17)

where $N{F}_c^{{}^{\prime }}$$\left(t\right)$ is the total ongoing tasks that cannot be released the resources in time t. The objective of our work is to satisfy Equation (17) and optimally allocate the resources. Most of the time meta-heuristic algorithms gives a near-optimal solution for the resource allocation problem [15,17]. Here, we are considering a meta-heuristic algorithm named whale optimization algorithm (WOA) [50]. The main strategy of WOA is the hunting behavior of one species of whale called Humpback. Humpback whales use the unique feeding method named bubble-net feeding to create circle around the prey and spread bubbles, so that the prey move to nearer surface of the ocean, as shown in Figure 4. The WOA get optimum solution using enclosing, bubble-net and explore methods.

In WOA, the random generated whale population are considered for optimization. These whales try to explore the location of prey and enclose them with bubble-net. During enclosing method, the whales upgrade their locations depending on best agent (i.e., target prey) as follows:

$$\overrightarrow{D}=|\overrightarrow{C}\otimes \overrightarrow{W_b\left(t\right)}-\overrightarrow{W\left(t\right)}|$$

(18)

$$\overrightarrow{W(t+1)}=\overrightarrow{W_b\left(t\right)}-\overrightarrow{A}\otimes \overrightarrow{D}$$

(19)

where $\overrightarrow{D}$ is the position vector difference of best agent ($W_b\left(t\right))$ and whales ($W\left(t\right)$), t is the present iteration, ⊗ is used for element-wise multiplication, and $\overrightarrow{A}$ and $\overrightarrow{C}$ are coefficient vectors and computed as   

$$\overrightarrow{A}=2\overrightarrow{a}\otimes \overrightarrow{r}-\overrightarrow{a}$$

(20)

$$\overrightarrow{C}=2\otimes \overrightarrow{r}$$

(21)

where every iteration decreases $\overrightarrow{a}$ from 2 to 0 linearly, and random vector $\overrightarrow{r}$ value lies in [0, 1]. The  control parameter $\overrightarrow{a}$ can be improved as $\overrightarrow{a}=2(1-\frac{t}{T_{max}})$ (where $T_{max}$ is the maximum iterations).

Equations (20) and (21) balance the exploration and exploitation. When $\overrightarrow{A}\ge 1$, exploration occurs, and exploitation occurs when $\overrightarrow{A}<1$. During exploitation, the probability of getting location solutions can be avoided by taking parameter $\overrightarrow{C}$ as a random value in [0, 2].

The bubble-net method has two approaches: shrinking enclosing and spiral updating. The shrinking enclosing can be achieved by taking $\overrightarrow{A}$ in [−1, 1] with a linear decreasing value of $\overrightarrow{a}$ in each iteration. The spiral updating inspired with helix-shaped movement of Humpback whales is applied to update the position of the best agent and the whales as follows:

$$\overrightarrow{D^{\prime }}=|\overrightarrow{W_b\left(t\right)}-\overrightarrow{W\left(t\right)}|$$

(22)

$$\overrightarrow{W(t+1)}=\overrightarrow{D^{\prime }}\otimes e^{bl}\otimes cos\left(2\pi l\right)+\overrightarrow{W_b\left(t\right)}$$

(23)

where a random generated l value lies in [−1, 1] and b is a constant used for logarithmic spiral shape.

The shrinking enclosing and spiral updating are performed simultaneously as whales move around the prey using both approaches. This behavior can be modeled by taking each approach with 50% probability as follows:   

$$\overrightarrow{W(t+1)}=\left\{\begin{array}{cc}\overrightarrow{W_b\left(t\right)}-\overrightarrow{A}\otimes \overrightarrow{D}& ifprob<0.5\\ \overrightarrow{D^{\prime }}\otimes e^{bl}\otimes cos\left(2\pi l\right)+\overrightarrow{W_b\left(t\right)}& ifprob\ge 0.5\end{array}\right.$$

(24)

where $prob\in [0,1]$. When the coefficient vector $\overrightarrow{A}$ is greater than 1, the explore method is applied in which the whale location is replaced with a random whale rather than best agent. Thus, the algorithm can extend the search to a global search and can be represented as follows:  

$$\overrightarrow{D}=|\overrightarrow{C}\otimes \overrightarrow{W_{rand}\left(t\right)}-\overrightarrow{W\left(t\right)}|$$

(25)

$$\overrightarrow{W(t+1)}=\overrightarrow{W_{rand}\left(t\right)}-\overrightarrow{A}\otimes \overrightarrow{D}$$

(26)

The bubble-net attach exploits the local solution from the current solution; whereas explore method tries to get a global solution from the population.

Here, we are considering WOA for allocating resources of fog nodes. Our whale optimized resource allocation (WORA) algorithm begins with generating a population of whales. Each whale denotes a random solution for a resource allocation problem. The fitness of each whale is calculated using a fitness function and selects a best solution with minimum fitness value as the current best agent. After this, the whales begin searching the global solution by updating each whale values of A, C, a, l, $rob$ in each iteration. Where A and C are random coefficients, a is decreasing from 2 to 0 linearly, $prob$ is [0, 1], and l is [2, 0]. Distance function is the most important function in WOA, which is designed for a continuous problem. As resource allocation problem is a discrete problem, the distance function can be modified. Whale creation, fitness function, and distance function as per our model is discussed below.

• Whale creation: In our algorithm, each whale denotes a solution to the resource allocation problem. If we have a set of resources $R=r_{0,0}^1,r_{1,0}^2,r_{1,1}^0$ and a set of request tasks $T=T_0,T_1$, then the whale can be represented as a random combination of resource with task $W=[\{r_{0,0}^1,T_0\},\{r_{1,0}^2,T_1\}]$. The resource is represented as $[f,c,r,CPU,bw,mem]$, where f, c, r, $CPU$, $bw$, and $mem$ represent fog node, container of the fog node, resource block of the container, CPU usage, bandwidth, and available memory, respectively. The task can be represented as $[id,CPU,bw,mem]$, which denote task identification number, requirement of CPU usage, bandwidth, and memory. For example,
  $R=\left\{\right[0,0,1,800,1000,1200],[1,0,2,750,1800,1080],[1,1,0,1800,2400,1620\left]\right\}$
  $T=\left\{\right[0,600,500,500],[1,700,800,1000\left]\right\}$
  Then a whale can be generated as follows:
  $W1$ = $\left[\begin{array}{c}\left\{\right[0,0,1,800,1000,1200],[0,600,500,500\left]\right\}\\ \left\{\right[1,0,2,750,1800,1080],[1,700,800,1000\left]\right\}\end{array}\right]$
  $W2$ = $\left[\begin{array}{c}\left\{\right[0,0,1,800,1000,1200],[1,700,800,1000\left]\right\}\\ \left\{\right[1,0,2,750,1800,1080],[0,600,500,500\left]\right\}\end{array}\right]$
  $W3$ = $\left[\begin{array}{c}\left\{\right[1,0,2,750,1800,1080],[0,6,150,500\left]\right\},\\ \left\{\right[1,1,0,1800,2400,1620],[1,700,800,1000\left]\right\}\end{array}\right]$
  In a similar fashion, all the whales are generated.
• Fitness function: For each whale, the fitness function is the optimal resource allocation to the task and can be calculated as

  $$f=\sum _{k=1}^{len\left(W\right)}\frac{\left\{(r_{ij}^l\left[cpu\right]-T_i\left[cpu\right])+(r_{ij}^l\left[bw\right]-T_i\left[bw\right])+(r_{ij}^l\left[mem\right]-T_i\left[mem\right])\right\}}{len\left(W\right)}$$

  (27)
  The whale with minimum fitness is the optimum solution. Hence, the goal of the algorithm is the minimization of the fitness function.
  The population can be generated by the collection of whales with their corresponding fitness.

  $$pop=\left\{[w_1,w_1\left(f\right)],[w_2,w_2\left(f\right)],\dots [w_p,w_p\left(f\right)]\right\}$$

  (28)
• Distance function: The most important function of WOA is the distance function. As three parameters (i.e., CPU usage, bandwidth, and memory) are considered, the distance function can be redefined as follows:

  $$\begin{array}{c}CP{U}_D=|\overrightarrow{C}\otimes W_i\left[CPU\right]-W_j\left[CPU\right]|\\ b{w}_D=|\overrightarrow{C}\otimes W_i\left[bw\right]-W_j\left[bw\right]|\\ me{m}_D=|\overrightarrow{C}\otimes W_i\left[mem\right]-W_j\left[mem\right]|\\ \overrightarrow{D}=[CP{U}_D,b{w}_D,me{m}_D]\end{array}wherei\ne j$$

  (29)

  $$\begin{array}{c}CP{U}_{D^{\prime }}=|W_i\left[CPU\right]-W_j\left[CPU\right]|\\ b{w}_{D^{\prime }}=|W_i\left[bw\right]-W_j\left[bw\right]|\\ me{m}_{D^{\prime }}=|W_i\left[mem\right]-W_j\left[mem\right]|\\ \overrightarrow{D^{\prime }}=[CP{U}_{D^{\prime }},b{w}_{D^{\prime }},me{m}_{D^{\prime }}]\end{array}wherei\ne j$$

  (30)

The WORA algorithm is given below.

Algorithm 4 presents assignment of fog resources to the tasks contained in $NF$. We initialize the whale population $W_i$ where $i=1,2,3,\dots P$, time t is 0, and the maximum iteration is $T_{max}$ in step-1. The best search agent $W_b\left(t\right)$ that has minimum fitness value is identified in step-2. While t is less than $T_{max}$, steps 3–21 are performed as follows:

• For each whale, steps 4–16 are performed. The value of A, C, a, l, and $prob$ are found in step 5.
• If $prob$ is less than 0.5, then check the absolute value of A in steps 6 and 7. If the absolute value of A is less than 1, then update D and $W_i$ using Equations (18), (19), and (29) in step 8. Otherwise, select a random whale $W_{rand}$ and update D and $W_i$ using Equations (25), (26), and (29) in steps 10 and 11.
• If p is greater than 0.5, then update $D^{\prime }$ and $W_i$ using Equations (22), (23), and (30) in step 14.
• After updating, amend $W_i$ that goes beyond the search space in step 17. Then compute the fitness of all $W_i$ and update the best search agent with minimum fitness in steps 18 and 19.
• Increment t by 1 in step 20.

Finally, return the best search agent that has optimal resource allocation to the tasks in step 22.

The complexity of an algorithm measures both space and time complexity. The space complexity is the amount of space occupied by the algorithm. In the WORA algorithm, the space complexity is related to the population size and the dimension of the problem. The population size is P and the dimension of the problem is D. Then, the space complexity is $O(P\ast D)$. In WORA, $D=3$ for $\{CPU,bw,mem\}$, thus the space complexity is $O\left(P\right)$.

For time complexity, three major processes (i.e., initialization of the best whale, main loop for updating, and return of best solution) are considered. In WORA, $T_{max}$ is the maximum iterations.

Initializing the best whale takes $O\left(P\right)$ times. The main loop updates the parameters, the whale that goes beyond the search space, and the optimum solution. The time complexity of these three stages are as follows:

Time required for updating the parameters is $O(P\ast D)$;

Time required for searching whales beyond the search space is $O\left(P\right)$;

Time for updating of optimal solution is $O\left(P\right)$;

Time required for main loop is the sum of above the operations $T_{max}(O\left(P\right)+O(P\ast D)+O\left(P\right))\cong O\left(P\right)$ where $D=3$ and ignored;

The time required for last step $O\left(1\right)$.

Therefore, total time complexity of WORA algorithm is $O\left(P\right)$.

Algorithm 4 Whale optimized resource allocation (WORA) algorithm.

Input: Set of resources R and tasks for fog node $NF$ where $NF={\sum }_{c=1}^{C^{\prime }}N{F}_c$ Output: Best solution for resource allocation $W_b$ 1: Initialize the whale population $pop$ with $W_i$, where $i=1,2,\dots P$, iteration $t=0$, maximum iteration $T_{max}$; 2: Identify the best search agent $W_b\left(t\right)$; 3: while  $t<T_{max}$do 4:     for k = 1 to P do 5:         Amend A, C, a, l and $prob$; 6:         if $prob<0.5$ then 7:            if $\left|A\right|<1$ then 8:                Amend D and $W_i$ by Equations (18), (19) and (29); 9:            else 10:                Choose a random whale $W_{rand}$; 11:                Amend D and $W_i$ by Equations (25), (26) and (29); 12:            end if 13:         else 14:            Amend $D^{\prime }$ and $W_i$ by Equations (22), (23) and (30); 15:         end if 16:     end for 17:     Amend $W_i$ that goes beyond the search space; 18:     Compute fitness of whale $W_i$; 19:     Update $W_b$ of best search agent; 20:     $t\leftarrow t+1$; 21: end while 22: Return $W_b$;

The following lemmas [51] are required for optimal convergence of the algorithm:

Lemma 1.

The population $\left\{W\left(t\right),t=1,2,....\right\}$ of WOA supports Markov chain which is finite and homogeneous.

Lemma 2.

The population $\left\{W\left(t\right),t=1,2,....\right\}$ of WOA absorb Markov process.

Lemma 3.

If an individual of WOASU is stuck in local optima $lp\left(t\right)$ in the tth iteration, the transition probability of population $\left\{W\left(t\right),t=1,2,....\right\}$ is

$$P\left(\left.\begin{array}{c}{W}_i(t+1)=lp(t+1)\end{array}\right|W_i\left(t\right)=lp\left(t\right)\right)=\left\{\begin{array}{cc}1& lp\left(t\right)=lp(t+1)\\ 0& lp\left(t\right)\ne lp(t+1)\end{array}\right.$$

(31)

Lemma 4.

The probability of convergence of WOASU algorithm towards the global optimal solution cannot possible.

Lemma 5.

If an individual of WOAEP is stuck in the local optima $lp\left(t\right)$ in the tth iteration, the transition probability of population $\left\{W\left(t\right),t=1,2,....\right\}$ is

$$P\left(\left.\begin{array}{c}{W}_i(t+1)=lp(t+1)\end{array}\right|W_i\left(t\right)=lp\left(t\right)\right)=\left\{\begin{array}{ccc}1& lp\left(t\right)=lp(t+1)& ifA=0orC=1\\ 0& lp\left(t\right)=lp(t+1)& ifA\ne 0andC\ne 1\end{array}\right.$$

(32)

Lemma 6.

The WOAEP can converge in probability to the global optimum.

Lemma 7.

WOA can converge in probability to the global optimum.

In the WORA algorithm, each whale represents random combination of resource with task as $W=\left[\left\{r_{0,0}^1,T_0\right\},\left\{r_{1,0}^2,T_1\right\}\right]$. The valid whales, where the amount of $[CPU,bw,mem]$ of resource is more than the requested task, can be considered for generating the populations. The fitness function, Equation (27), calculates the average minimum difference of requested resource to allocated resource. Thus, the best whale is the whale that has the minimum fitness value. Using Lemmas 1–7, it is proved that WOA with spiral updating or enclosing method with probability of 50% can converge to a global optimum. Even if WOA is trapped to local optima by executing spiral updating mechanism, it can be come out from local optima using the enclosing mechanism. The WORA algorithm also adopts both spiral updating and enclosing method with 50% probability. Hence, the WORA algorithm can converge to global optima with probability to a point in infinite iterations.

The whole process of Algorithms 1–4 of our work is shown in the flowchart in Figure 5.

5. Performance Evaluation

This section provides simulation setup, metrics performance, and evaluation of WORA compared with other algorithms.

5.1. Simulation Setup

We used python for implementing and evaluating our proposed algorithm. The hardware or software taken for the simulation is given in

Table 4. Hardware/software specification.

Sl. No.	Hardware/Software	Configuration
1	System	Intel® Core ™ i5-4590 CPU @ 3.30 GHz
2	Memory (RAM)	4 GB
3	Operating System	Windows 8.1 Pro

. We assumed different resource configurations for the different containers of the fog. Each fog has different resource configurations, hence each resource of the containers of fog is also different. The tasks are configured randomly.

Table 5. Resource configuration of cloud–fog infrastructure and task.

Name	Values
CPU rate of cloud	44,800 MIPS
Bandwidth of cloud	15,000 Mbps
Memory of cloud	40,000 MB
CPU rate of fog	22,800 MIPS
Bandwidth of fog	10,000 Mbps
Memory of fog	10,000 MB
Arrival time of tasks ($arrtim{e}_i$)	[0, 10] ms
Execution lower bound of task ($etlo{w}_i$)	[1, 6] ms
Execution upper bound of task ($etu{p}_i$)	$[0,6]+etlow$ ms
Execution time ($e{t}_i$)	($[etlow,etup]$) ms
Data size of task	[10, 500] MB
deadline	$max(et,20)+arrtime$
resptime	$arrtime+etlow$
No. of Instructions ($le{n}_i$)	[10, 1700] MI
Bandwidth required for task	[10, 1800] Mbps
Memory required for task	[10, 1800] MB
CPU required for task	[10, 2200] MIPS

gives a detailed configuration of cloud–fog infrastructure and tasks.

We performed extended simulations with varied number of tasks and fog nodes in the system. The results of WORA are compared with SJF, FLRTS [30], and MOMIS [4]. We considered 3 to 20 fog nodes and 8 to 700 tasks.

5.2. Performance Metrics

Here, the algorithm considered cost, energy consumption, makespan, and completion of task ratio as the performance metrics. All are defined below.

• Cost: Cost is the amount of monetary cost for processing the tasks in cloud and fog nodes. The cloud charges cost for both processing and communication, whereas the fog node only charges a cost for communication [1]. The cost of the system is defined as follows:

  $$cost=\sum _{i=1}^n\left\{\begin{array}{cc}{c}_1\ast e{t}_i+cc\ast (d{s}_i+\frac{le{n}_i}{b{w}_c})& i\in N{C}_c\\ cf\ast e{t}_i& i\in N{F}_c\end{array}\right.$$

  (33)
• Energy consumption: The total amount of energy consumed to execute all the tasks of a system is represented with $Energyconsumption$ metric. The total energy consumed in fog nodes is summed of the energy consumption for executing tasks and utilization of energy of the fog nodes being idle. When tasks are executed in the cloud, then total energy is summed of consumed energy for the execution of the task and also energy for transferring the task and data. The total consumed energy is as follows:

  $$energy=\sum _{i=1}^n\left\{\begin{array}{cc}ef\ast e{t}_i+e_{idle}& i\in N{F}_c\\ ec\ast e{t}_i+e_{comm}\ast (d{s}_i+\frac{le{n}_i}{b{w}_c})& i\in N{C}_c\end{array}\right.$$

  (34)
• Makespan: The time required for completing all the tasks in the system is represented as $Makespan$ [30]. It can be computed as

  $$makespan=\underset{i}{\underbrace{max}}(res{p}_i+e{t}_i))i\in [N{C}_c,N{F}_c]$$

  (35)
• Task completion ratio: $Taskcompletionratio$ is the ratio of total tasks successfully completed within the deadlines.

  $$Taskcompletionratio=\frac{{\sum }_{c=1}^{C^{\prime }}\left(N{C}_c+N{F}_c\right)}{{\sum }_{c=1}^{C^{\prime }}\left(N{C}_c+N{F}_c+NFai{l}_c\right)}$$

  (36)

The parameters for evaluating the metrics are given

Table 6. Simulation parameters and values setup.

Parameters	Values
Processing cost per time unit for cloud ($c_1$)	0.5 G$/s
Communication cost per time unit for cloud ($cc$)	0.7 G$/s
Communication cost per time unit for fog ($cf$)	[0.3, 0.7] G$/s
Energy per unit for execution of the task in fog ($ef$)	[1, 5] w
Energy used when fog node is idle ($e_{idle}$)	0.05 w
Energy per unit for execution of task cloud ($ec$)	10 w
Energy per unit for transmission of data ($e_{comm}$)	2 w

.

5.3. Performance Analysis

Several experiments were carried out with different scenarios. When three fog nodes are considered where each fog node has three containers and each container has three resource blocks, Figure 6 shows the cost, energy consumption, makespan, and task completion ratio of varying tasks.

The proposed WORA algorithm is analyzed and compared with other three algorithms considering the metrics that we have taken. Figure 7 compares expenditure of cost of WORA with the other three algorithms with different numbers of fog nodes with 500 tasks. With an increase in fog nodes, the resource blocks are increased. Hence, a larger number of tasks are assigned to the fog nodes and a small number of tasks are transferred to the cloud for execution, which reduces the cost. The SJF algorithm forwards tasks to the cloud while the required resource is unavailable in the fog layer. The deadline as well as transmission delay of the task are considered in FLRTS. The tasks with a soft deadline or minimal latency are forwarded to the cloud. Therefore, less tasks are executed at the fog nodes in the FLRTS algorithm, which can increase the cost. Most of the tasks are assigned with resources of fog nodes in the MOMIS algorithm. Hence, the cost of the system is nearer of our WORA algorithm. The proposed WORA algorithm saves 23.89% of the average cost of FLRTS and 17.24% of the average cost of MOMIS algorithm.

Figure 8 shows the computation of energy consumption with the number of fog nodes handling 500 tasks. It can be observed that increasing fog nodes can reduce energy consumption, because most of the tasks are executed in fog nodes where less tasks are moved to the cloud. When comparing the average energy consumption, it is observed that the WORA algorithm consumes 23.8% less energy than MOMIS and 30.76% less energy than FLRTS.

When considering makespan with the number of fog nodes handling 500 tasks in Figure 9, it is observed that with an increase in fog nodes, the makespan is decreased. Instead of waiting for resources, the tasks are executed when fog nodes increases, which decreases the makespan. It is also observed that our WORA algorithm performed 6.8% better than MOMIS and 9% better than FLRTS in terms of makespan.

When 500 tasks are executed in different fog nodes from 5 to 20, Figure 10 shows that our WORA algorithm performed 3.51% better than MOMIS and 5.4% better than FLRTS in terms of successful completion ratio of task.

When 15 fog nodes are considered with tasks varying from 100 to 700, Figure 11 shows that cost increased with increasing tasks. Our WORA algorithm saves 10.3% of the average cost of MOMIS and 21.9% of the average cost of FLRTS. Similarly, the WORA algorithm saves 18.57% of the average energy of MOMIS and 30.8% of the average energy of FLRTS, shown in Figure 12. Figure 13 shows that WORA performed 6.4% better than MOMIS and 12.9% better than FLRTS in terms of makespan. The successful completion of tasks within the deadline is shown in Figure 14, where it is observed that WORA is 2.6% better than MOMIS and 4.3% better than FLRTS.

In our WORA algorithm, whale optimization algorithm is used for resource allocation. The tasks have arrived at different time intervals. Figure 15 shows the minimum fitness value in different time intervals for numbers of tasks in three fog nodes.

6. Conclusions

In this work, two modules—task classification and buffering (TCB) and task offloading and optimized resource allocation (TOORA)—are modeled for buffering the tasks in several queues according to their types, using the enhanced least laxity time the tasks are transferred to the cloud or fog. Considering the resource demand and deadline constraints of the tasks, a WOA is applied to assign the task to the optimal resource block of the fog node. The simulation results of our WORA algorithm evaluate metrics such as cost, energy consumption, makespan, and successful completion ratio of tasks and compare them with the standard SJF algorithm and existing algorithms such as MOMIS and FLRTS. When 500 tasks are executed in different fog nodes (e.g., 5 to 20), the results show that the WORA algorithm saves 23.89% of the average cost of FLRTS and 17.24% of the average cost of MOMIS. In terms of energy consumption, the WORA algorithm consumed 23.8% less energy than MOMIS and 30.76% less energy than FLRTS. Similarly, the WORA algorithm performed 6.8% better than MOMIS and 9% better than FLRTS in terms of makespan; and the WORA algorithm performed 3.51% better than MOMIS and 5.4% better than FLRTS in terms of successful completion ratio of the task. Similarly, when 100 to 700 tasks are executed in 15 fog nodes, it was observed that the WORA algorithm performed 3.51% better than MOMIS and 5.4% better than FLRTS in terms of successful completion ratio of the task, saving 18.57% of the average energy of MOMIS and 30.8% of the average energy of FLRTS. WORA performed 6.4% better than MOMIS and 12.9% better than FLRTS in terms of makespan and 2.6% better than MOMIS and 4.3% better than FLRTS in terms of successful completion ratio of the task. In the future, we will consider other metrics, such as throughput and delay rate for evaluating the performance of the algorithm. We also expand our research for virtual machine (VM) migration to balance the resource allocation.