Using Metaheuristic OFA Algorithm for Service Placement in Fog Computing

Riza Altunay and Omer Faruk Bay

1Department of Information Systems,Gazi University,Ankara,06680,Turkey

2Department of Computer Technologies,Ondokuz Mayis University,Samsun,55100,Turkey

3Department of Electrical-Electronics Engineering,Gazi University,Ankara,06560,Turkey

ABSTRACT The use of fog computing in the Internet of Things(IoT)has emerged as a crucial solution,bringing cloud services closer to end users to process large amounts of data generated within the system.Despite its advantages,the increasing task demands from IoT objects often overload fog devices with limited resources,resulting in system delays,high network usage,and increased energy consumption.One of the major challenges in fog computing for IoT applications is the efficient deployment of services between fog clouds.To address this challenge,we propose a novel Optimal Foraging Algorithm (OFA) for task placement on appropriate fog devices,taking into account the limited resources of each fog node.The OFA algorithm optimizes task sharing between fog devices by evaluating incoming task requests based on their types and allocating the services to the most suitable fog nodes.In our study,we compare the performance of the OFA algorithm with two other popular algorithms:Genetic Algorithm(GA)and Randomized Search Algorithm(RA).Through extensive simulation experiments,our findings demonstrate significant improvements achieved by the OFA algorithm.Specifically,it leads to up to 39.06%reduction in energy consumption for the Elektroensefalografi(EEG)application,up to 25.86%decrease in CPU utilization for the Intelligent surveillance through distributed camera networks(DCNS)application,up to 57.94%reduction in network utilization,and up to 23.83%improvement in runtime,outperforming other algorithms.As a result,the proposed OFA algorithm enhances the system’s efficiency by effectively allocating incoming task requests to the appropriate fog devices,mitigating the challenges posed by resource limitations and contributing to a more optimized IoT ecosystem.

KEYWORDS Internet of Things;cloud computing;fog computing

1 Introduction

With the rapid proliferation of technology,encompassing smartphones,wearable devices,industrial tools,and various other domains,the number of internet-connected devices has experienced significant growth.This surge in interconnectedness has given rise to the concept of the IoT,which was initially introduced by a group of academics in 1991.As IoT devices often face processing capacity and resource limitations,the adoption of cloud services has become a necessity [1].Nevertheless,the escalating utilization of cloud services and devices has brought forth challenges,including issues related to distributed data arising from diverse geographical locations,increased bandwidth usage,and end-to-end delays.To effectively tackle these challenges,fog computing has emerged as a viable solution[2].Fog computing is strategically positioned between the cloud and IoT devices,serving as a decentralized infrastructure comprised of diverse fog nodes that offer management,storage,and communication capabilities [3].Moreover,fog computing brings additional advantages,including data protection and secure communication [4,5].However,due to the heterogeneity and limited resources of fog nodes,achieving effective service placement poses a significant challenge.In response to this issue,several metaheuristic algorithms have been proposed to address task scheduling in the IoT system.These algorithms encompass the Fireworks Algorithm (FWA) [6],Marine Predators Algorithm(MPA)[7],Bee Algorithm(BA)[8],Particle Swarm Optimization(PSO)[9],and Genetic Algorithm(GA)[10].Abohamama et al.proposed a semi-dynamic real-time task scheduling algorithm that leverages a modified version of the genetic algorithm to optimize task scheduling[11].Ghobaei-Arani et al.utilized the meta-intuitive whale optimization algorithm to allocate tasks on fog devices and enhance service quality[12].On the other hand,Dubey et al.introduced a fog device framework that improves delays,computational costs,load balancing,and energy consumption in the IoT system,utilizing Cuckoo and PSO algorithms[13].Maiti et al.proposed a fog node layout to minimize delays using algorithms such as Simulated Annealing (SA),Genetic Algorithm (GA),and Particle Swarm Optimization(PSO).Their findings indicated that the GA-SA algorithm proved to be the most efficient in minimizing delays[14].

In their study on service placement,Mohamed et al.[15] combined two distinct algorithms to determine the most optimal and shortest path while selecting the nearest fog node for users.Their approach resulted in successful improvements in network usage,distance optimization,load balancing,and data transmission.Zare et al.[16] employed the Asynchronous Advantage Actor-Critic (A3C)algorithm,developed in the field of deep and reinforcement learning,to ensure high-quality service delivery.Skarlat et al.[17] used the Genetic Algorithm (GA) to showcase the efficient utilization of fog resources,leading to reductions in communication delays within the network.Additionally,Saif et al.[18] employed the Grey Wolf Optimizer algorithm to address energy consumption and minimize delays in the system.The literature review highlights that fog computing is adopted to address the growing number of objects and their demands in cloud computing.However,due to the limited resources of fog clouds,they are unable to accommodate all requests.As a result,the increasing number of requests adversely impacts bandwidth usage,energy consumption,processing costs,and operation time.To tackle these challenges,numerous studies have been conducted,focusing on areas such as resource sharing,task scheduling,and load balancing to mitigate the issues associated with limited fog cloud resources.In current studies,the service placement problem remains a critical issue that requires improvement,particularly concerning the placement of applications from objects onto fog clouds with limited resources.The primary objective of this study is to implement the Optimal Foraging Algorithm (OFA) to efficiently allocate services onto application modules.The proposed Optimal Foraging Algorithm (OFA) has been subjected to comparison with various algorithms,focusing on basic comparison functions and optimization problems [19].The algorithm’s strong performance in optimization problems,its novelty in IoT applications,and its promising potential for success due to its unique structure were regarded as a novel perspective,leading to its application in this study.The working logic and pseudo code of the algorithm are elaborated upon in Section 3.In the deployment of IoT applications on fog nodes,it is crucial to ascertain the requirements of the applications and the desired service quality to ensure compatibility with the existing fog nodes and applications.During the service distribution stage,where services are allocated to suitable fog clouds based on application types,the OFA metaheuristic algorithm is employed to generate appropriate solutions[19].

The obtained solutions are first internally compared using various metrics and subsequently pitted against the GA and RA algorithms in terms of energy consumption,bandwidth usage,processing cost,and execution time.Through these comparisons,the advantages of the proposed algorithm are demonstrated.

The contributions of this study to the literature can be summarized as follows:(1)Optimization of efficient service placement between fog devices in fog cloud-based IoT using a three-layer architecture;(2) Introduction of the Optimal Foraging Algorithm (OFA) for service placement,marking its application for the first time in IoT;(3)Demonstration through simulation results that the proposed algorithm outperforms other algorithms in terms of energy consumption,CPU usage,bandwidth usage,and runtime.The study is structured into six parts.The first part introduces the topic and provides a comprehensive literature review.The second part presents detailed information about the system architecture and formulates the problem being addressed.In the third part,the proposed optimization algorithm is thoroughly explained,along with its operational principles.The fourth part showcases the performance values obtained from the experimentation.In the fifth part,a numerical analysis of the algorithm is presented,including relevant data and insights.Finally,the sixth part concludes the study,summarizing the findings and discussing the overall status of the manuscript.

2 System Architecture and Problem Formulation

The system operates on a layered architecture as shown in Fig.1.The highest layer is referred to as the cloud layer,which is a distributed data center accessible to all internet-connected devices and not used at a specific location [20].The middle layer,on the other hand,is where fog computing is implemented,and where fog devices are located,providing real-time computing that considers current operations [21].The bottom layer is where various smart and non-smart objects with a distributed structure,such as computers,smartphones,and machines,are connected[22].

In IoT applications,the limited resources and distributed nature of the heterogeneous and decentralized fog nodes,as well as their changing processing capacities over time,pose challenges in the service placement stage.To determine when and where services will be placed,service placement is required.The proposed algorithm addresses these challenges and enables the efficient allocation of application modules to fog nodes.The architecture used in the system includes entities and services.Entities are composed of components such as cloud,client,and fog nodes,while services are application modules that are received from objects to be run in the system.The system possesses all the necessary information about fog clouds and incoming mission requests during its operation.As a result,the services are efficiently directed to the relevant fog cloud.Each node runs the tasks assigned by the system.Applications can be sent to fog nodes as modules or sets of modules.Each application module has properties such as processing power,memory,storage,bandwidth,etc.Service modules are categorized into three different types:client,global,and regular modules.Client modules can only be processed on client nodes,while global modules can be processed on nodes other than client nodes.Modules other than these can be processed on both types of nodes.The proposed decisionmaking algorithm in the system aims to improve system performance by placing services on nodes with limited hardware capabilities under a certain service quality constraint.In this study,energy consumption,processing cost,bandwidth,and execution time are determined as performance criteria.These performance criteria and the quality of service are formulated and calculated separately as shown below.

Figure 1:System architecture

2.1 Quality of Service

After including application cycles in the system,it is checked if the task is completed on time while providing Quality of Service(QoS).Operation delays and transmission delays that arise while transferring the application between two nodes are calculated during this process.The importance of service quality has increased due to the growing number of devices and the emergence of diverse services [23].QoS is considered to be fulfilled if the application cycles are processed and their tasks are completed.Eq.(1) is used to calculate QoS,when representing the cost of CQperformance,Q,denotes the total number of application loops.represents each loop within the application,andshows the completion times of tasks in the application.q refers to the total delay in application loops,indicates the total processing delays between two nodes,andrepresents the total transmission delays between two nodes.By taking these delays into account,it is checked whether QoS is ensured during the transfer of an application between two nodes[24].

2.2 Power Cost

The equation in Eq.(2)is used to calculate the cost of energy consumption by taking into account the transaction cost used during the application and the cost spent on network transmission.It is important to note that in fog computing,sending data to distant clouds can lead to excessive energy consumption[25].The power consumption cost(CPw)is obtained by summing up the processing cost(CP)and the transmission cost(CB).To calculate CP,the difference between the power consumption while active (fbPw) and the power consumption while idle (fiPw) is multiplied by the connection usage percentage.To calculate CB,the power consumption is multiplied by the connection usage percentage at full transmission capacity(fTx)[24].

2.3 Processing Cost

The system’s processing capacity is increased by using a low-cost processor.When operating the system,it is important to consider the processing capacity used by each resource and to take processing costs into account when allocating tasks [26].Eq.(3) calculates the processing cost (CP) is the sum of the ratio of the total amount of processing capacity to the utilized capacity multiplied byPn×mMipsrepresents the total amount of processing capacity required for all modules placed in node n.ap×indicates the capacity utilised by multiplying the processing capacity of node n by the resource utilisation percentage(ap).f Fogindicates whether the node is a fog node.If n=0,it is a client node[24].

2.4 Bandwidth Cost

2.5 Execution Time

It is the time in milliseconds from the start of the system to the completion of the optimization phase.

3 Proposed Optimization Algorithm

OFA is a global optimization algorithm that monitors the foraging behaviour of animals and determines their position accordingly.In addition,the OFA algorithm is used to solve optimization problems in many fields such as classification and regression problems [28],ranking problems in industry [29],and healthcare [30,31].It is a known fact that animals in nature need food in order to survive and continue their generations.Foraging is a fairly common phenomenon to meet these needs.Animals consider three situations while foraging [19].Where to look for food,When to look for new food,What type of food to choose? In the proposed algorithm,individuals prefer foraging areas according to the rules they have determined.When an area is determined,the first thing to consider is how valuable the food is.If the food found is valuable,more individuals in the community move there.The search for valuable food continues as long as they live.When the OFA algorithm is summarized mathematically,the following stages emerge.

3.1 OFA Algorithm Steps

First of all,for the d-dimensional array in N number of food-seeking individuals and R constraint space,each individual is specified as X=[x1,x2,x3,...,xd]T.In this direction,the objective function is defined as in Eq.(5)[19].

F(x),objective function value and F(×?)is the optimal objective function value,x?is the optimal vector.Here,maximum optimization problem of F(x) is equivalent to the minimum optimization problem of-F(x),withlower and upper limit values,respectively.In order to create individuals,N number of individuals are produced by using Eq.(6)[19].

When the recurrence rates are accepted as t for the current number and as t+1 for the next iteration,the best individuals are shown with Eq.(7) and the remaining individuals are shown with Eq.(8).k variable is shown as k=t/tmax,t shows the number of valid iterations,tmaxshows the maximum number of iteration,shows the randomly selected individual,shows the worst individual of the population,r1iand r2ishow the random numbers distributed between 0 and 1[19].

While individuals are deciding on whether to update their current location,they use prey selection model[32].Prey energy uses,advantageous prey energy usesvariables.In Eq.(9),t and t+1 positions are compared from each iteration result,if it is efficient,the current position is changed and if it is not,it continues a new iteration with the current position[19].

3.2 OFA Algorithm Pseudo Code

General operation logic of the algorithm is given above and the pseudo-code is shown in Algorithm 1.

Firstly,a population is created,consisting of a specific number of individuals.For each individual in the population,a random solution is generated.Subsequently,a module placement map is created,indicating feasible locations for modules within the solution.Based on this map,a tuple routing map and a module transition map are established,facilitating node selection for transferring modules to their destination nodes.The solutions obtained for each individual are then ranked according to their costs,with the individual having the lowest cost selected as the best solution.When creating a new individual,each one tends to move towards the best position.As individuals search for solutions close to their current location,the newly produced solutions remain in proximity to the previous ones.Each new solution is compared with the previous best solution.Following the comparison,if the location(i.e.,the cost)of the newly generated individual is better than the previous best solution,the next search continues with that solution.Conversely,if the generated solution is worse than the previous one,the current solution is retained.In this manner,solutions are generated for a number of iterations,and each time,the best solutions are compared with the previous one.Once the specified iteration is completed,the best solution obtained is selected as the final best solution.The simulation is then initiated,and the results are obtained and evaluated based on the chosen final best solution.

4 Performance Evaluation

There are entities consisting of cloud and fog nodes on physical topology in the operation of the system.Devices such as sensors and actuators that can receive data and apply the result after processing can be connected to these nodes.After the system is installed,the control unit performs the necessary checks and the system operates.Application packages sent on the system are distributed among the existing fog nodes with the proposed algorithm as data bundles and the system is operated.Each node has its properties.

4.1 Components of the System

During the system setup,there is one cloud,a proxy connected to the cloud,a varying number of fog nodes connected to the proxy,and objects have been used.The numbers used have been explicitly specified during the comparison stage.The processing capacities that can be used for all devices on the system,the idle power consumed by the nodes,and the amount of power consumed during operation are defined in Table 1.The results obtained during the operation of the system are produced based on these values.To evaluate the proposed system,a fog computing environment was created and simulated using the iFogSim[33]simulator,which is commonly used in academic publications.The algorithm was coded using the Java programming language.The experiments were conducted on a desktop computer with an Intel Core i7-6700 processor with a clock speed of 3.40 GHz and 8 GB of memory,using the EEG and DCNS,which are commonly used in academic publications.

Table 1:Components of the system

4.1.1 EEG Beam Tractor Game

EEG Beam Tractor Game is a type of game that takes place between two humans and uses augmented brain-computer interaction.The players’brain activities are measured using EEG devices and these measurements are transferred to a computer program that allows the players to play the game.Thus,players’brain activities enable them to control the objects in the game.The application consists of 5 modules:EEG sensor,screen,client,concentration calculator,and coordinator[34].EEG parameters are shown in Table 2.

Table 2:Application edges of the EEG tractor beam game

Many experiments have been performed using the OFA algorithm on EEG with systems containing different numbers of fog clouds.The results of the experiments are shown in Table 3.In Table 3,the Area column shows the number of fog clouds connected to the Proxy,the Device column shows the number of devices connected to the fog clouds,and the Fog Node column shows the total number of nodes on the system.Respectively,Energy(J)indicates the amount of energy consumed by the system,processed(MI)indicates the amount of data processed through the system,transferred(B)indicates the bandwidth used by the system,and Execution time(ms)indicates the operating time of the system.

Table 3:EEG simulation results

The horizontal axes of Fig.2 show the total number of nodes.In Fig.2a,the energy consumed by the system exhibits a linear increase.While Figs.2b–2d also show a general linear increase,there is a noticeable decrease in the values when the number of fog nodes is 17 and 22.This decrease,as observed in Table 3 in the Area domain,occurs due to an initial increase in the number of optimized fog clouds.The rise in the number of fog nodes results in additional resources for distributing services,thereby leading to these reductions.This increase has a positive impact on the system’s CPU usage,network usage,and runtime performance.

Figure 2:(a)Energy consumption(b)CPU usage(c)Network usage(d)Execution time

4.1.2 DCNS(Intelligent Surveillance through Distributed Camera Networks)

DCNS refers to the deployment of multiple cameras across an area to monitor and analyze activities in real-time.The cameras capture video footage and detect moving objects by analyzing the images.A designated object is tracked by PTZ cameras and the images are transmitted to the user over the internet.The application consists of 5 modules: Motion Detector,Object Detector,Object Tracker,PTZ Control,and User Interface[33].DCNS parameters are shown in Table 4.The results of the experiments with the OFA algorithm on DCNS are shown in Table 5.

Table 4:Application edges of the DCNS

Table 5:DCNS simulation results

The horizontal axes of Fig.3 show the total number of nodes.In Figs.3a and 3c,a linear increase in energy consumption and network usage on the system is observed as the number of fog nodes increases.However,in Figs.3b and 3d,a decrease is noticed when the number of fog nodes is 17 and 22.This decrease is evident in Table 5,which corresponds to the optimization of fog nodes and occurs when the number of fog nodes is initially increased.The increase in the number of fog nodes provides additional resources for distributing services,resulting in positive effects on CPU usage and system runtime.

Figure 3:(a)Energy consumption(b)CPU usage(c)Network usage(d)Execution time

4.2 Algorithm Comparison

The EEG and DCNS were run on a layered architecture with the OFA algorithm,GA,and RA algorithms,respectively.Comparisons were made over values such as energy consumption,operation costs,bandwidth cost and execution time.Parameter settings determined for each algorithm to be run on the system are shown in Table 6 below.

Table 6:Algorithm parameters

4.2.1 Genetic Algorithm

Initially,a random population is generated.The genetic algorithm generates heuristic solutions using the previously generated solution information.In each iteration,the number of convergence is checked and new individuals are created according to the situation.The new individual formation is performed using three genetic operators.The first one is the selection operator,which controls fitness and ensures that the genes are transferred to the next generation.In this way,it transfers a certain percentage of genes of the best individuals to the next generation.Secondly,the crossover operator performs the process of crossing the two best individuals selected by the selection operator,and finally,new individuals are produced by adding random genes by the mutation operator in order not to produce the same solutions.The process is continued for the number of iterations and the best solution is obtained.

4.2.2 Random Algorithm

The RA algorithm generates random solutions without using the values generated in the previous solution for the specified number of iterations.The first generated solution is taken as the best solution.Each generated solution is compared with the best solution and if it is better,the better solution is selected as the best solution.On the other hand,if a certain number of identical solutions are generated by the convergence number,the loop is broken and the best solution is selected.Table 7 shows the EEG results.

Table 7:Simulation results in EEG

Fig.4 shows the comparison of energy consumption,processing costs,bandwidth cost and execution time of OFA algorithm with other algorithms.In the comparisons made on systems with different numbers of fog devices;Fig.4a shows that in terms of energy consumption,it improves 6%,0.5%,and 6% compared to the GA algorithm,6%,0.1%,39% compared to RA respectively in the experiment using 14,20,26 fog devices.Fig.4b shows that in the experiment using 14,20,26 fog devices,there is an increase of 0.06%,-0.1%,1%,respectively,in terms of cpu usage compared to GA,and an improvement of 4%,0.6%,4%,respectively,compared to RA.Fig.4c shows that the bandwidth usage using 14,20,and 26 fog devices improved by 6%,-8%,and 1%compared to GA,16%,16%,and 20% compared to RA,respectively.Fig.4d shows that in the experiment performed using 14,20,and 26 fog devices on the runtimes,it has improved by-6%,3%,-0.4%according to GA,8%,0.08%,13%according to RA,respectively.The experiments conducted on the EEG application demonstrate that the OFA algorithm outperforms both the GA and RA algorithms in terms of energy consumption,bandwidth usage,CPU usage,and runtime.

Figure 4:(a)Energy consumption(b)CPU usage(c)Network usage(d)Execution time

However,in certain trials,the OFA algorithm shows a slight lag compared to the GA algorithm.Table 8 shows the DCNS results.

Table 8:Simulation results in DCNS

Fig.5 shows the comparison of energy consumption,operation costs,bandwidth cost,and execution time of the OFA algorithm with other algorithms.In DCNS,the OFA algorithm has better results than the others.In the comparisons made on systems with different numbers of fog devices;Fig.5a shows that the OFA algorithm consumes less energy than other algorithms,even if it is a small amount.Fig.5b shows that the OFA algorithm improves the CPU usage by 12%,15%,and 2%compared to GA and 25%,12%,and 10%compared to RA in the experiments with 14,20,and 26 fog devices,respectively.Fig.5c shows that the bandwidth usage improved by 86%,5%,15%according to GA,47%,57%,and 19%according to RA,respectively,in the experiment using 14,20,26 fog devices.Fig.5d shows that it improves 6%,11%,0.14%compared to GA,-7%,23%,and 8%compared to RA,respectively,in the experiment using 14,20,26 fog devices on run times.As a result,it is shown that the OFA algorithm is more efficient than both GA and RA in terms of energy consumption,bandwidth usage,and runtime,while it is slightly behind the RA algorithm in the experiment using 26 devices only in runtimes.

Figure 5:(a)Energy consumption(b)CPU usage(c)Network usage(d)Execution time

5 Discussion

The proposed algorithm is compared with the study conducted by Arora and Singh [32],where heterogeneous modules were sent to fog devices in the network.The comparison is made on the“Intelligent Surveillance” application using the same configuration settings in the iFogSim [29]environment,with results presented in Table 9.The findings indicate that the average network usage improved by 36%in MB,and the average runtime improved by 37%in milisecond.In another study by Gavaber and Rajabzadeh[35],which focused on the efficiency of the system by adding fog devices in the fog layer,a comparison was made on the “EEG” application in terms of average energy consumption and application cycle delay.The results showed that the average energy consumption was reduced by 71% in MJ,and the application cycle delay decreased by 69% in milisecond.These values are also presented in detail in Table 9.It is evident that the proposed algorithm consistently reduces network usage across different applications,contributing to energy consumption reduction and affecting runtime positively.However,it is important to note that the increase in the number of nodes can lead to higher overall consumption values in any system.Since the constraints of the system used have not been tested in real-life scenarios,the extent to which it may impact the results differently remains unknown.Nevertheless,the authors state that future studies will include real-world trials.

Table 9:Literature comparisons

6 Conclusion

In this study,the OFA algorithm is proposed to facilitate efficient service placement in a fog computing network.The algorithm achieves an effective distribution of applications among fog nodes based on their respective application types.The main objective of this research is to enhance the system’s performance in terms of energy consumption,network usage,processing cost,and runtime.To evaluate the proposed algorithm,comparative analyses were conducted with the GA and RA algorithms using the iFogSim simulation tool.Two different configurations were simulated to assess the algorithm’s performance comprehensively.The results obtained through simulations demonstrate the effectiveness and significance of the proposed algorithm in outperforming the alternatives concerning energy consumption,network usage,processing cost,and runtime.The algorithm exhibits stability and maintains its efficiency even as workloads increase,displaying linear growth patterns.This study showcases the promising performance and capabilities of the proposed algorithm in the context of service placement within the fog computing environment.Future work aims to assess the algorithm’s real-world application performance and further enhance the system’s data security to ensure the confidentiality and integrity of shared data.

Acknowledgement:As author,I would like to thank my Ph.D.advisor of Gazi University and his advisory is Prof.Dr.Omer Faruk Bay for their support and assistance.This research has been produced from a part of Riza Altunay’s Ph.D.dissertation in Gazi University,Institute of Informatics,and Department of Information Systems.

Funding Statement:The authors received no specific funding for this study.

Author Contributions:Study conception and design:R.Altunay,O.F.Bay;data collection:R.Altunay;analysis and interpretation of results:R.Altunay,O.F.Bay;draft manuscript preparation:R.Altunay.All authors reviewed the results and approved the final version of the manuscript.

Availability of Data and Materials:Data available within the article or its supplementary materials.The authors confirm that the data supporting the findings of this study are available within the article.

Conflicts of Interest:The authors declare that they have no conflicts of interest to report regarding the present study.