Discrete Black Widow Optimization Algorithm for Multi-Objective IoT Application Placement in Fog Computing Environments

Due to the wide use of the cloud-fog environment, the researchers attach great importance to its performance. Because of the complexity of cloud fog, the optimal application placement strategy is one of the important factors influencing its performance [8, 12]. Different applications placement strategies are proposed in the literature with the aim to improve the computing efficiency of the cloud-fog environment [6-8]. In this section, we present the previous application placement strategies, focusing on their nature as exact, heuristic, and metaheuristic solutions.

2.1 Exact solutions

Previous studies have used Integer Linear Programming (ILP) solvers to obtain exact solutions for application placement in fog infrastructure. Skarlat et al. [13] employed the IBM CPLEX solver and Java ILP within the Ifogsim simulator [14] to address the service placement problem in a fog environment. Their optimization aimed to minimize the usage of the fog environment while considering the application's Quality of Service (QoS) requirements. The results showed that their optimization reduced the execution cost, and the solution did not violate the application deadline.

Similarly, Minh et al. [15] used an ILP solver to offer a service placement policy that maximizes the placement of services in a fog landscape, resulting in improvements in terms of delay and energy usage. Arkian et al. [16] formulated the service placement problem in a fog environment as mixed-integer nonlinear programming (MINLP), with the objective of lowering the total cost while meeting the application's QoS requirements. The simulation findings demonstrated cost, energy, and latency improvements.

Tran et al. [17] recommended service placement in a decentralized fog landscape based on context-aware data such as resource consumption, location, and reaction time. Their proposed method was found to be efficient for maximizing fog device utilization and decreasing latency. However, other optimization methods are less prevalent, and only a few scholars have investigated their application in fog computing. For example, in the study [12], the problem was formulated using constraint programming to satisfy the QoS criterion, and Choco-solver was used to solve it.

2.2 Heuristics approaches

Exact solution algorithms, such as ILP solvers, are frequently employed methods for tackling the issue of application placement in fog computing systems. However, due to their time-consuming nature, these algorithms are not suitable for large-scale infrastructure. As an alternative, heuristics algorithms, such as search-based strategies, are used to find feasible solutions within an acceptable timeframe.

In the literature, researchers have suggested and explored various search-based algorithms to optimize application placement in fog infrastructure. One such approach is the greedy backtracking heuristic algorithm proposed by Brogi and Forti [18], which employs fail-first or fail-last strategies to select the candidate node. Brogi et al. [19] extended the backtracking search algorithm [18] to estimate QoS assurance using the Monte Carlo method. Xia et al. [20] proposed a backtracking service placement solution that minimizes the response time of IoT applications.

Similarly, Lera et al. [5] proposed a first-fit heuristic algorithm to place services in fog device communities, optimizing QoS and service availability. Benamer et al. [21] proposed an exact and Latency Aware-Placement Heuristic (LAPH) algorithm to place IoT modules to reduce overall latency, with simulation results showing that the heuristic approach is significantly closer to the optimal solution within a short period of time. Finally, Azizi et al. [4] proposed a heuristic algorithm called most delay-sensitive application (MDAF) first for QoS-aware service placement, which prioritizes time-sensitive applications closer to the data source, resulting in improvements in latency and cost compared to the edge ward algorithm [14].

2.3 Meta-heuristics approaches

In the current big data era, which includes fields like social networks, health services, neuroscience, and eLearning, massive amounts of high-dimensional data are ubiquitous. The fast expansion of data and the need for responses in a short time create difficulties in effectively and efficiently managing applications and data, so it is desirable to apply intelligent optimization techniques as metaheuristics. Metaheuristics are optimization algorithms that are characterized by their simplicity, it obtains promising results in several optimization problems [22]. Metaheuristic algorithms can be simply changed to address specific issues. It efficiently examines the search space by balancing its two primary basic strategies, exploration and exploitation of the search space [23].

Several metaheuristic algorithms have been applied to the application placement issue throughout the last decade. Brogi and Forti [18] provided a framework for installation of IoT services in fog. To eliminate communication delays, they devised a Genetic Algorithm (GA). The suggested approach demonstrates a shorter deployment time than cloud-only placement, a first-fit solution, and an exact solution. Bitam et al. [24] suggested a multi-objective work scheduling issue in a fog environment using the bee life method to find a point where there is a compromise between the amount of memory available and the time it takes to process a task. The evaluation findings of their suggested method surpass those of Particle Swarm Optimization (PSO) and GA. Ayoubi et al. [25] presented an autonomous service placement using a four-phase methodology: monitoring, analysis, decision, and execution. The authors applied the Strength Pareto Evolutionary Algorithm II (SPEA-II) to make decisions in multi-objective optimization. Many performance criteria indicate that the suggested approach surpasses existing state-of-the-art approaches. Canali and Lancellotti [26] suggest a genetic algorithm for service placement by mapping data streams from the sensor to the fog node, the delay in transmission between sensors and nodes is the optimization aim of their research. Djemai et al. [27] introduced IoT application mapping as a dual-objective optimization problem to reduce system energy usage and boost QoS. The authors presented a method for placement based on DPSO. The results of simulations indicate that the DPSO approach decreases energy usage and reaction time overall.

Guerrero et al. [28] addressed a multi-objective service placement issue in a random fog network infrastructure, considering three optimization objectives: network latency, service dispersion, and resource consumption. The authors used three evolutionary algorithms. The experimental results showed the effectiveness of both NSGA-II and MOEA/D compared to WSGA. Salimian et al. [29] proposed an automatic application placement to optimize the system performance and the execution cost in a three-layer hierarchical architecture based on the GWO algorithm. According to the simulations, the proposed GWO algorithm outperforms the other five mentioned algorithms. Yadav et al. [30] developed a hybrid algorithm using traditional GA and PSO algorithms called GAPSO to optimize execution time and energy consumption. The results of the experiments demonstrate that GAPSO outperforms the GA and the PSO. Natesha and Guddeti [31] formulated the application placement as a multiobjective optimization problem and used the Elitism Genetic Algorithm (EGA) to optimize execution time, cost, and energy consumption. The results of simulations showed that the proposed EGA outperformed the GAPSO [30] and the other mentioned heuristic approaches.

Previous studies have utilized various techniques for modeling the IoT application placement problem, as summarized in Table 1. These include exact solutions such as ILP heuristic approaches and metaheuristic algorithms. While exact solution offer precision they can be impractical for large scale deployments. Heuristic approaches may provide fast solution but my not always guarantee optimality. Metaheuristic algorithms may struggle to balance between exploration and exploitation. In this paper, we propose a novel metaheuristic approach that aims to balance between solution quality and computational efficiency by considering application requirements and nodes capabilities.

Table 1. Summary of existing optimization approaches for application placement in fog computing environment

In this section, we discuss the structure of our fog computing system and define application placement as a combinatorial optimization approach.

4.1 System architecture

Fog computing is a system that is characterized by high levels of distribution and flexibility that allows data to be processed closer to the user’s location, resulting in lower latency, greater efficiency, improved scalability, and better resource utilization. This system comprises cloud servers, fog servers, a fog broker, and IoT devices.

1.png

Figure 1. An overview of our system model

The fog broker receives applications from IoT devices and deploys them on either fog nodes or cloud nodes based on their requirements and the availability of resources. After execution, the results are sent back to the fog broker and then to the IoT devices. Fog computing allows for the dynamic distribution of applications across various resources while ensuring optimal performance. Figure 1 illustrates the typical system architecture of a fog computing infrastructure, which consists of IoT devices, fog nodes, and cloud nodes.

4.2 Application model

As shown in Figure 2, IoT applications are built on a concept of sense-process-act in which raw data is collected by IoT devices (sensors), processed by services running in fog and cloud nodes, and the processed data is sent to the actuators. The service placement in fog nodes depends on the resources requested by the services and the availability of these resources in the fog nodes.

2.png

Figure 2. Application model [33]

We consider that IoT devices generate data that is sent to a variety of applications. Each one is encapsulated in a single processing module that may be separately implemented across the system nodes. In this context, the application can be modelled as a monolithic service [33]. The requested processing, memory, and bandwidth resources characterize each application. The amount of resources requested will vary depending on the type of application.

4.3 Application placement problem formulation

The placement of application entails assigning a set of applications to the best available nodes in a distributed system, while taking into account the different characteristics of each application and node. We assume a set of m fog-cloud nodes $F N=\left\{F N_1, F N_2, F N_3, \ldots, F N_m\right\}$, each node i encompasses computing resources Ri {CPUi (MIPS), RAMi (Mb), bandwidthi (Mbps)}.

We also assume that exist n applications $A=\left\{A_1, A_2, A_3, \ldots, A_n\right\}$ sent to the fog broker to be placed. Each application $A_j$ is characterized by requested resources $\operatorname{Req}_j$ {CPUj (MIPS), RAMj (Mb), bandwidthj (Mbps)}.

The application placement in the system is mathematically modeled as follows:

Let R = [CPUi, RAMi, Bwi] be a matrix with m rows (fog nodes) and 3 columns (CPU, RAM, Bandwidth) representing the available resources of fog nodes.

$R=\left(\begin{array}{ccc}C P U_1 & R A M_1 & B w_1 \\ C P U_2 & R A M_2 & B w_2 \\ \ldots & \ldots & \ldots \\ C P U_m & R A M_m & B w_m\end{array}\right)$             (1)

where, CPUi, RAMi, Bwi represent available CPU (in MIPS), RAM (in Mb) and Bandwidth (in Mbps) of the ith fog nodes respectively.

Let Req= [CPUj, RAMj, Bwj] be a matrix with n rows (applications) and 3 columns (resource requirements).

$R e q=\left(\begin{array}{ccc}C P U_1 & R A M_1 & B w_1 \\ C P U_2 & R A M_2 & B w_2 \\ \ldots & \ldots & \ldots \\ C P U_n & R A M_n & B w_n\end{array}\right)$              (2)

where, CPUj, RAMj, Bwj resource requirements CPU (in MIPS), RAM (in Mb) and Bandwidth (in Mbps) of the jth application respectively.

Let P be a binary matrix with n rows and m columns, where Pij = 1 if the jth application is executed in the ith node and Pij = 0 otherwise. Such as the sum of each, row equal to one.

$P=\left(\begin{array}{cccc}P_{11} & P_{12} & \cdots & P_{1 n} \\ P_{21} & P_{22} & \cdots & P_{2 n} \\ \vdots & \vdots & \ddots & \vdots \\ P_{m 1} & P_{m 2} & \cdots & P_{m n}\end{array}\right)$                 (3)

Let Placement Cost Matrix (PCM) be three-dimensional matrix with n rows m columns and three slices (one for each resource).

$P C M=$

$\operatorname{PCM}(: ;: ; 1)=\left(\begin{array}{cccc}P C M_{111} & P C M_{121} & \cdots & P C M_{1 n 1} \\ P C M_{211} & P C M_{221} & \cdots & P C M_{2 n 1} \\ \vdots & \vdots & \ddots & \vdots \\ P C M_{m 11} & P C M_{m 21} & \cdots & P C M_{m n 1}\end{array}\right)$

$\operatorname{PCM}(: ;: ; 2)=\left(\begin{array}{cccc}P C M_{112} & P C M_{122} & \cdots & P_{1 n 2} \\ P C M_{212} & P C M_{222} & \cdots & P_{12 n 2} \\ \vdots & \vdots & \ddots & \vdots \\ P C M_{m 12} & P C M_{m 22} & \cdots & P C M_{m n 2}\end{array}\right)$

            $\operatorname{PCM}(: ;: ; 3)=\left(\begin{array}{cccc}P C M_{113} & P C M_{123} & \cdots & P C M_{1 n 3} \\ P C M_{213} & P C M_{223} & \cdots & P C M_{2 n 3} \\ \vdots & \vdots & \ddots & \vdots \\ P C M_{m 13} & P C M_{m 23} & \cdots & P C M_{m n 3}\end{array}\right)$            (4)

where, PCMijk is the cost of placing the jth application on the ith node for the kth resource.

The objective function is to reduce executing time and cost by taking into account the available resources of the fog nodes and the application requirements.

The objective function can be defined as:

$\operatorname{Minimize}(F)=\alpha \times$ TotalTime $+\beta \times$ Totalcost                (5)

where, α and β are weighting factors that determine the relative importance of the execution time and the total cost in the objective function where $(\alpha+\beta=1)$.

The total time can be represented as:

$TotalTime =\max \left(\sum_{i=1}^m \sum_{j=1}^n \frac{\operatorname{Re} q_{(j, 1)}}{R_{(i, 1)}}\right)$            (6)

where, $\operatorname{Req}_{(j, 1)}$  represents the requested CPU by the jth application, $R_{(i, 1)}$  represents the available CPU on the ith fog node. Total execution time means maximum processing time of all nodes, which is calculated as the sum of the execution time of all applications in a single fog node divided by the available CPU in the node.

The total cost of placing the application on fog nodes can be calculated as the sum of the execution cost, memory cost and bandwidth cost. Let’s assume that CPT, CDP, and CPB are the cost per unit of CPU, RAM, and bandwidth respectively.

The total cost can be formulated as follows:

$\begin{aligned} \text { TotalCost }=\sum_{i=1}^m & \sum_{j=1}^n\left(\operatorname{Req}_{j 1} * P_{i j} * C P T+R e q_{j 2}\right. \left.* P_{i j} * C P D+\operatorname{Req}_{j 3} * P_{i j} * C P B\right)\end{aligned}$                                    (7)

where, $R e q_{j 1}, R e q_{j 2}, R e q_{j 3}$ are the CPU, RAM, and Bandwidth requirements of application $j$ respectively. Moreover, $P_{i j}$ represents the binary placement decision with $P_{i j}=1$ if the jth application is executed on the ith node, and $P_{i j}=0$ otherwise. By summing up the cost for each application and each fog node, we get the overall cost of placing all the application on the fog nodes.

Resource constraint: each fog node has limited computer power, memory, and network bandwidth. Therefore, we need to ensure that the total resource requirement of all applications that run on a fog node do not surpass the resource of that node. This condition can be stated as:

$\left\{\begin{array}{l}\sum_{j=1}^n\left(R e q_{j 1} * P_{i j}\right) \leq C P U_i \\ \sum_{j=1}^n\left(\operatorname{Req}_{j 2} * P_{i j}\right) \leq R A M_i \forall i=1,2, \ldots, n \\ \sum_{j=1}^n\left(\operatorname{Req}_{j 3} * P_{i j}\right) \leq B w_i\end{array}\right.$                  (8)

Binary constraint: each application must be placed on only one fog node. this constraint can be mathematically expressed as:

$\sum_{j=1}^m P_{i j}=1, \forall i=1,2, \ldots, n$                 (9)

In this section, we present the experimental results and analysis of the performance of our proposed DBWO algorithm in simulated Fog environments. We compare our approach with recent literature methods in terms of application placement in cloud-fog environments, and provide details on the experimental setting, evaluation metrics, and comparative results in the following sub-sections.

6.1 Experimental settings 

To evaluate the DBWO algorithm, experiments are performed using the Ifogsim [9] simulator, an open-source simulator based on Cloudsim, programmed in Java. The tests are conducted on a personal computer equipped with a 64-bit Windows 10 operating system, an Intel Core i5-4310u 2.00 GHz CPU, and 4 GB of memory, ensuring consistency and reproducibility of the experimental setup. The proposed DBWO algorithm has been tested using a set of fog-cloud nodes and their respective physical resource capabilities as detailed in Table 3. Additionally, we utilize the same application requirements as presented in Table 4 across all experiments for a fair comparison among the DBWO algorithm and the other algorithms under evaluation.

Table 3. Fog-cloud nodes characteristics

Table 4. Applications requirements

6.2 Evaluation metrics

The primary objective of this study is to achieve a balance between the execution time and total cost of application placement in the proposed system.

-The execution time that represents how long the system needs to execute all the applications, it is calculated using Eq. (6).

-The total cost that represents the required amount of money must be used to execute all the IoT applications in the system; it is calculated using Eq. (7).

6.3 DBWO evaluation and convergence study

7.png

Figure 7. Convergence curve of the DBWO algorithm

The convergence of DBWO is experimentally analyzed. Figure 7 presents the results of our algorithm in fog environment placing 100 applications in 10 fog nodes and 5 cloud the application requirement and the fog-cloud nodes characteristics are shown respectively in Table 3, Table 4. DBWO reached the best fitness value when the population size is 200 and the number of generations is 100. Hence, we use these values for the rest of the experiments.

6.4 Comparison with other approaches

Since our proposed DBWO is a Swarm-based metaheuristic, we compared it to the following four recently proposed swarm-based IoT application placement Algorithms. The comparison is made in terms of execution time and cost.

EGA [31], which is a multi-objective Elitism-based Genetic Algorithm, it aims to reduce service time, cost, and energy usage.

DPSO [27] is a discrete version of the particle swarm optimization algorithm that is proposed to the IoT services placement with the aims to minimizing the cost and maximizing the quality of experience.

BLA [24] is a placement approach based on bees life metaheuristic to solve scheduling problem in fog computing system. It aims to minimizing the CPU execution time and the allocated memory.

GWO [29] is a gray wolf optimization algorithm proposed to optimize the IoT application placement execution cost.

Table 5 displays the parameter settings used for the proposed algorithm and the other four algorithms. We have varied the parameter values to evaluate their effect on the performance of the proposed algorithm as shown in Figure 7. Our results indicate that the proposed algorithm achieves near-optimal performance when the number of individuals is 200 and the generation number is 100.

The DBWO’s other parameters are set as in the original version of the BWO [9], where procreation rate is 0.6 , the mutation rate is 0.4, and the cannibalism rate is 0.44, and the parameters of the compared algorithms are fixed as in their papers. All these settings provide insight into how to tune the parameters in order to achieve the highest performance of the proposed algorithm for the problem at hand. For the rest of the experiment, we use the same parameters for all the algorithms in Table 5.

Table 5. Parameters setting for the DBWO and the compared algorithms

We considered two different network topologies: fog-only and cloud-fog. In the first scenario, we used a fog-only topology, which only contained fog nodes. In the second scenario, we used a cloud-fog topology that contained both fog nodes and cloud nodes. This difference in the network topologies had a significant effect on the results of our study the fog-only topology was limited in its capabilities, while the cloud-fog topology was able to take advantage of the additional resources provided by the cloud nodes. We analyze the impact of varying the number of applications on the fitness value, the execution time, and the total cost.

6.5 First scenario: Application placement in fog only topology

The fitness value, which represents the quality of the solution in terms of both the execution time and total cost, was calculated as the mean of 10 independent runs in Figure 8. The results showed that the best performance was achieved with algorithm DBWO, followed by algorithms GWO, EGA, DPSO, and BLA respectively. It is clear that DBWO outperformed the other algorithms with a fitness value of 0.941 when compared to the other four algorithms, which is better than GWO, EGA, DPSO, and BLA by 4.30%, 5.35%, 5.77%, and 9.87% respectively.

8.png

Figure 8. Fitness value of DBWO, GWO, EGA, DPSO and BLA algorithms in the first scenario

In the first scenario, we defined a fog-only topology with 10 fog nodes, available resource characteristics listed in Table 3, and varying application request numbers ranging from 40 to 500 requests. The application requirements were specified in Table 4. The balancing factors $\alpha$ and $\beta$ of the fitness function were set to 0.5, which gave equal weight to execution time and overall cost. Each algorithm was then executed, the results obtained were compared in terms of fitness value, execution time, and total cost, as shown in Figures 9-11 respectively.

9.png

Figure 9. Applications placement exaction time in the first scenario

The execution time for each of the five algorithms was also evaluated, and the results in Figure 9 illustrate that the DBWO algorithm took the least amount of time to complete. The DBWO algorithm, for example, runs 400 applications in an average time of 1946.20, whereas the other algorithms took 2105.50, 2130.74, 2185.50, and 2352.14 for GWO, EGA, DPSO, and BLA respectively to complete the same data set. Overall, the DBWO algorithm outperformed the other algorithms in terms of execution time, with less execution time than GWO, EGA, DPSO, and BLA by 8.13%, 10.39%, 11.05%, and 19.12% respectively.

10.png

Figure 10. Applications placement total cost in the first scenario

In Figure 10, the results for the total cost of the five algorithms are shown for the fog-only scenario. The DBWO algorithm had the lowest total cost, but as the topology consisted only of fog nodes, the processing, memory, and bandwidth costs were similar for all nodes. However, even in this scenario, the DBWO algorithm outperformed the other four algorithms (GWO, EGA, DPSO, and BLA) and achieved better overall performance, reducing the total cost in all data sets by 0.45%, 0.50%, 0.62%, and 0.74% respectively. This comparison shows that the DBWO algorithm can be an effective tool for optimizing fog-based IoT networks in terms of both time efficiency and cost reduction compared to other algorithms.

6.6 Second scenario: Application placement in fog and cloud topology

In the second scenario, we defined a more complex topology of 27 nodes composed of 20 fog nodes and 7 cloud nodes, using the characteristics mentioned above. This allowed us to utilize the advantages of both fog and cloud nodes, as the fog nodes had better connectivity and responsiveness but limited resources, whereas the cloud nodes provided higher processing power and memory while also requiring a greater monetary cost. In this scenario, we varied the number of requested applications from 100 to 1000, and, according to Table 3, the application requirement was generated at random. We performed simulations to determine the performance of both physical topologies, exploring their respective impacts on application execution time, fitness value, and cost.

The fitness value of the five algorithms is depicted in Figure 11. The results showed that using both fog and cloud nodes allowed us to balance the performance between execution time and cost. Figure 11, clearly shows that the proposed DBWO outperforms all of the compared algorithms across all applications simples by 8%, 12.16%, 13%, and 15.16% for DPSO, EGA, GWO, and BLA respectively. With an average fitness value of 0.63.

11.png

Figure 11. Fitness value of DBWO, GWO, EGA, DPSO and BLA algorithms in the second scenario

12.png

Figure 12. Applications placement exaction time in the second scenario

13.png

Figure 13. Applications placement total cost in the second scenario

In all of the experiment, the DBWO had the lowest execution time and total cost compared to other algorithms as illustrated in Figure 12. In terms of execution time, DBWO outperformed DPSO, EGA, GWO, and BLA by 1.95%, 9.16%, 7.25%, and 10.11% respectively. In terms of cost, as illustrated in Figure 13. It outperformed them by 2.9%, 4.19%, 7.70%, and 8.0% respectively.

6.7 Analysis of experimental results

According to the analysis of the results in the two scenarios in which DBWO was tested and compared with EGA, DPSO, GWO, and BLA. In both scenarios, DBWO outperformed the compared algorithms in terms of fitness value, in fog only topology with improvement range from 4.30% to 9.87%. Similarly, in the fog cloud topology showed notable performance improvement, with fitness value range from 8% to 15.16%. Notably, DBWO proved to be particularly effective in the more complex topology, where its performance improvement was most pronounced.  

It is clear that DBWO surpassed the other algorithms in terms of efficiency in both execution time and total cost in both scenarios, where the first scenario was a simple fog only scenario and the second scenario was a more complex scenario consisting of both fog and cloud nodes. In simple environments, GWO performed better than EGA, DPSO, and BLA. When the environment was more complex, DPSO provided better results than GWO, EGA, and BLA However, DBWO provided better results than all the algorithms in both scenarios, confirming its versatility and adaptability in optimizing resource utilization and enhancing the scalability of fog environments.