1 Introduction

It has been estimated that the number of deployed smart devices connected through the Internet of Things (IoT) will be around 75 billion by 2025 [1], while the amount of data generated by these devices is expected to be 73.1 zettabytes per year [2], as opposed to 1.1 zettabytes of data per year estimated in 2016 [3]. Most of this massive amount of data requires real-time processing to make efficient decisions [4]. However, the majority of the end devices in IoT are battery powered and have limited processing and storage capabilities. Therefore, they are unable to satisfy the requirements of the applications that need massive data processing. Hence, it is necessary to utilize a resourceful computing paradigm that enables processing the data generated from the end IoT devices. This paradigm is often called cloud computing [5]. The cloud computing paradigm provides extensive processing power and unlimited storage through powerful virtual servers, which enables fast processing and unbounded storage. It can be useful for applications that are not delay sensitive and do not require higher responsiveness. However, it may not be an attractive solution for applications that require real-time processing and high responsiveness, due to the high network bandwidth usage and large end-to-end delay for continuously pushing large bulks of raw data. For this purpose, fog computing [6] has been designed as a promising computing paradigm for tackling the aforementioned issues related to limited device resources, limited bandwidth, and large end-to-end latency, by bringing computation, storage, and networking services directly to the network edge. Here, we describe “Edge” as any intelligent computing resources along the path between data sources and cloud data centers. These computing resources are referred to as edge devices. Some examples of edge devices include routers, switches, and smart gateways.

As fog-based systems ensure additional computing capabilities at the edge of a network, users can profit from the advantages of fog computing mainly by means of computation offloadingFootnote 1, which is a mechanism that can overcome the problem of resource constraints at the edge devices. Edge devices are connected to devices that have computation, storage, and networking capabilities such as routers and switches. Specifically, it can help to improve the performance of computation-intensive applications and battery life. However, selection of the tasks to be offloaded is a challenging problem. Generally, the purpose of decision making on task offloading is to ascertain whether the offloading is cost-effective for the user equipment in respect of energy consumption and execution delay [7].

Another challenge in computation offloading is making a decision about which node to assign to the offloaded task (i.e., service placementFootnote 2 problem), while considering the selected metrics such as energy consumption and/or latency. Since the fog nodes are geographically distributed, resource-constrained, and highly dynamic, service placement problem becomes extremely difficult to solve. Several studies have addressed the aforementioned problem. Different strategies and techniques have been considered with a goal of designing efficient computing offloading and service placement schemes in fog environment. In this survey, we review a broad range of the recent existing studies that focus on these issues, and explore the strategies and techniques proposed in the literature. First, we present the concept of fog computing and application domains. Second, we consider application models for offloading, computation offloading decisions, and provide a classification of the various algorithms proposed for computation offloading. Finally, we discuss optimization methodologies and performance metrics for service placement, and present a classification scheme for service placement methodologies and techniques.

We can list the main contributions of this survey as follows:

  1. 1.

    We provide an exhaustive overview of the computing offloading problem, by identifying several factors that can affect the offloading decision, presenting the key application models for offloading to fog environment, and classifying the algorithms and techniques that have been proposed recently for the computing offloading problem. The proposed classification is based on the offloading type and objective parameters.

  2. 2.

    We propose a novel classification for the optimization strategies that have been proposed to solve the service placement problem for IoT applications over fog nodes. This classification is based on the used methods and the optimization objectives.

  3. 3.

    Finally, we highlight the open challenges and discuss the future research directions in fog-based systems.

The rest of the paper is organized as follows. Section 2 summarizes existing surveys on fog computing. Section 3 presents an overview of fog computing paradigm: definition, architecture, main characteristics, advantages, application domains, as well as the differences and similarities with related computing paradigms. Section 4 introduces the concepts of computation offloading: application models and the proposed methodologies for designing computation offloading schemes. Section 5 introduces the service placement problem, performance metrics, and proposed optimization methods. Finally, Sect. 7 concludes the paper.

2 Related work

Different aspects and challenges of fog computing have been addressed by several surveys. Mahmud et al. [8] focus on key services that fog computing provide. Further, they present the major factors that have been considered for efficient resource and service provisioning in fog. Varshney and Simmhan [9] state the characteristics and requirements of applications that push the need for using the fog environment. Hong and Varghese [10] classify the architectures, infrastructure, and underlying algorithms for managing resources in fog/edge computing. Ren et al. [11] discuss the state-of-the-art research in terms of computation offloading, caching, security, and privacy in edge computing and related computing technologies. Yi et al. [12] mainly discuss the issues related to fog networking. Mouradian et al. [13] review the proposed architectures and algorithms for building fog. The authors in [14, 15] summarize the proposed approaches for resource management such as resource allocation, task scheduling, resource provisioning, task offloading, and application placement, with a focus on the relevant resource management issues. In [16], the authors provide a comprehensive review of existing literature that use stochastic offloading mechanisms in computation paradigms. Furthermore, they provide a comprehensive comparison of offloading mechanisms based on Markov chain. The authors of [17] present an exhaustive overview of IoT–Fog–Cloud ecosystems and mainly discuss the standards, tools, and applications that have been used. In [18], the authors provide a comprehensive overview of various aspects of application management. They present an extensive exploration in IoT applications architecture distributed over fog nodes. They discuss programming models, service types, workload types, interaction methods, and functional layouts. Moreover, they overview the relevant elements associated with application placement such as mapping techniques and placement strategies. Ranesh Kumarnaha et al. [19] present a comprehensive review of existing literature with a focus on the requirements perspective related to infrastructure, platform, and application in fog computing. They further summarize some existing research studies in resource allocation, scheduling, and fault tolerance in fog with some application examples. The survey in [20] summarizes the characteristics of fog architecture and presents the main similarities with and differences from cloud. The paper also presents the key technologies applied in fog. In [21], the authors give a comparative discussion about fog computing and its related computing paradigms. Moreover, they summarize the software and tools for fog computing, as well as the applications that are exploited for the fog technology. Additionally, they investigate the problem of resource management, security, and privacy. The authors of [22] take a closer look at networking, latency, and energy consumption models in fog computing, and discuss the issues related to service allocation and resource management in a fog infrastructure. Several others surveys discussed similarities and differences of fog computing compared to the related computing paradigms, fog architectures, application domains, as well as the challenges and open issues [22,23,24,25].

Although some of the mentioned surveys explore the computation offloading and service placement problem in fog computing, we notice that these studies are limited in the following perspectives:

  • They omit the comprehensive summary of the relevant elements of the offloading operation such as application model definitions, resolution strategies, offloading decision, and offloading type.

  • Additionally, the aforementioned surveys do not provide an exhaustive review regarding the optimization strategies and their technical formulations for application placement. In particular, the machine learning-based intelligent solution strategies are neglected.

  • They do not provide an insight into how to choose the best optimization strategy for the application placement under different objectives, as one optimization method may be better than the other for certain types of applications/scenarios.

The aforementioned limitations of the existing surveys motivated us to initiate this survey which is mainly dedicated to achieving an exhaustive and comprehensible overview of relevant computing offloading aspects and the service placement problem in fog computing.

3 Overview of fog computing

Fog computing, proposed first by Cisco in 2012 [26], is defined as a distributed computing infrastructure that extends cloud-like services to the network edge by delivering computation and storage resources closer to users [27]. According to the OpenFog Consortium [28],

Fog Computing is a horizontal, system-level architecture that distributes computing, storage, control, and networking functions closer to the users along a Cloud-to-Thing continuum.

As opposed to cloud computing, fog computing introduces fog servers and fog nodes, which are devices physically closer to the users than their cloud counterparts, with a goal of handling some of the application workload closer to the network edge. Any device such as a controller, smart gateway, switch, router, or embedded server, which possesses capabilities for processing, networking and storage, may be employed as a fog node. The advantage of these devices is wider deployment opportunities, as they can be placed at any location where network connection is available, such as inside factory buildings, alongside railways, inside of vehicles, and even on power poles. The main idea behind this approach is to optimize the transmission time it takes for data to reach the intended processing nodes, since deploying nodes closer to the edge of a network shortens the data transmission time to a negligible delay [27]. According to OpenFog, fog nodes are equipped with intelligent algorithms that facilitate processing and storing data, as well as forwarding data from edge devices to fog, and from fog to cloud via smart networking.

3.1 Fog architecture

A number of architectures for fog computing have been proposed, most of which have a three-layer structure as illustrated in Fig. 1. A typical fog architecture comprises an IoT layer (also known as end layer) that consists of IoT devices, a fog layer that consists of fog nodes, and a cloud layer with a cloud data center and services [29], which are discussed in more detail below.

  • IoT layer It is the lowest layer located at the nearest proximity to the end users. It incorporates various sensor nodes (temperature and humidity sensors, cameras, etc.) and actuators that may be distributed over a wide geographical area. Devices placed at this layer are responsible for collecting data about their environment, and dispatching the gathered data to the upper layer for further processing and/or storage.

  • Fog layer It is an intermediary layer between a cloud and end devices, which consists of heterogeneous fog devices (e.g., access points, switches, routers, gateways, base stations, fog servers, etc.) that have relatively limited processing, storage, and communication capabilities. These fog nodes maintain a connection to cloud servers and can forward requests to cloud data centers. Fog nodes that have very limited processing, storage, and other capabilities are considered to be low-level nodes, while nodes with more abundant resources are classified as high-level nodes. Fog nodes may also be categorized as either stationary (if fixed at a certain location), or mobile, such as smartphones, vehicles, and drones [29, 30].

  • Cloud layer It is the top layer in a fog computing architecture. Cloud layer incorporates a number of servers and data centers, which are capable of executing complex processing and analysis, storing huge amounts of data, and providing feedback and results back to fog nodes [29, 30].

Fig. 1
figure 1

Illustration of a fog computing architecture

Full size image

Considering this layered fog architecture, it is evident that fog services are located in a much closer proximity to the end users, allowing a denser geographical distribution, and offering a better mobility support, as opposed to a cloud environment in which services may reside in much farther locations necessitating wider bandwidths. Furthermore, a fog ecosystem also contributes to reduced latency and provides context awareness due to fog node localization, resulting in pervasive, scalable, and united network connectivity [3].

3.2 Key characteristics and advantages of fog computing

The distinct characteristics and advantages of fog computing can be listed as follows.

  • Low latency: The key motivation behind this emerging paradigm is to decrease the data transmission latency while increasing the data transmission rate [31]. Some novel applications such as intelligent vehicle-to-vehicle communication networks, virtual reality, and online gaming have an extremely high requirement for low delay. For instance, in a virtual reality application, a small delay in range of milliseconds can damage the user experience [23]. Due to the close proximity of fog nodes to end users, fog computing is capable of providing support for low latency and time-sensitive applications [11].

  • Support for mobility: In applications such as vehicular networks the movement of the nodes can considerably affect the system performance, especially in scenarios that require handling fast channel changes [11]. Fog computing can facilitate the mobility of the end users through providing computational and storage resources over the entire network, as opposed to a traditional centralized cloud ecosystem [29].

  • Bandwidth: Preprocessing of data before transferring it to a cloud for further analysis or storage plays an important role in reducing the network traffic. Fog computing enables data filtering and aggregation to be performed locally in order to speed up the execution of certain tasks that would otherwise take too long under a limited network bandwidth [29].

  • Scalability: There are IoT scenarios in which a huge number of end users needs to be managed along with enormous amounts of data produced by billions of heterogeneous IoT objects with different performances and costs. In such scenarios, having fog nodes widely distributed and deployed in close proximity to the users plays an important role in making IoT applications scalable and adaptable to the network changes [11].

3.3 Fog computing issues

Fog computing paradigm promises to offer effective solutions for a number of problems that afflict IoT and cloud computing applications. Nevertheless, it also comes with its own challenges that need to be grasped and tackled in order for it to become an effective computing solution. Some of the fog-specific issues are discussed below.

  • Resource management Fog environment contains heterogeneous fog nodes with limited computing and storage performance capabilities, which makes it harder to manage resource allocation, scheduling, and sharing. Efficient management solutions are needed for determining appropriate task placement strategies that satisfy applications’ requirements (e.g., solutions based on priority and migration) [32]. Furthermore, in order to provide mobility support, particularly in the case of connected objects, resources may need to be pre-allocated using effective methods such as probabilistic ones based on user history [33]. Therefore, a framework that enables the performance evaluation of resource management policies in IoT or fog computing infrastructures is a necessity [3].

  • Privacy and security Some of the proposed solutions for security issues in fog computing focus on intrusion detection, access control, authentication, and detection of various other malicious activities including denial of service (DoS) attacks and port scanning. Introducing security mechanisms in fog computing is necessary for each level of the fog architecture [12].

  • Energy management A fog infrastructure incorporates a large number of geographically distributed nodes. As a result, energy consumption in a fog ecosystem is higher in comparison with that of a cloud [23, 33]. Significant research efforts are needed to develop effective solutions for energy management. For example, data processing and communication protocols that are less costly in terms of energy consumption need to be developed [33].

  • Quality of service (QoS) One of the most important measures of network service quality in general is QoS, and this holds for fog computing as well. In [34], the authors consider QoS in fog computing based on four metrics: connectivity, reliability, capacity, and latency. Other metrics such as energy efficiency, bandwidth, and security may be taken into consideration as well, depending on the application requirements. The challenge with QoS provisioning often entails making trade-offs between different QoS metrics, which is further complicated by a varying and often dynamic nature of different applications.

3.4 Applications benefiting from fog computing

Figure 2 illustrates a scope of applications that stand to gain from the fog computing paradigm. In this subsection, we discuss some of those applications that can benefit from fog computing to a great extent.

Fig. 2
figure 2

Applications benefiting from fog computing paradigm

Full size image

3.4.1 Healthcare

Healthcare applications and services, especially applications for remote monitoring of critical patients whose physiological states may rapidly deteriorate necessitating agile response and decision making, are time-critical applications that demand real-time processing. In unpredictable network conditions, delivery of health data may become subject to high latency, making the data deficient, unreliable, and in some cases even useless. This issue may incur even worse outcomes for data that requires cascade-based analysis such as electrocardiogram (ECG) or electroencephalogram (EEG) signals [35, 36]. This type of problematic scenarios may be prevented through employing solutions based on fog computing.

Cao et al. [37] proposed a fog-based system called FAST, which enables detection, prediction, and avoidance of falls for patients who suffered a stroke. Their fall detection learning algorithm was distributed across both edge and cloud resources, enabling a shorter response time in comparison with other proposed solutions that are solely based on cloud implementation.

3.4.2 Augmented reality

Fog computing may also play a major role in enhancing the performance of augmented reality applications, which are highly delay-sensitive, as the user experience depends mainly on real-time response [33]

An example is the Augmented Brain Computer Interface developed by Zao et al. [38], which is capable of detecting the states of a user’s brain in real-life situations using data collected through EEG headsets. Since both fog and cloud servers are utilized, the system is capable of perpetual real-time classification of a user’s brain state performed at the fog layer, while employing cloud servers for regular tuning of classification models.

3.4.3 Traffic management system

The efficiency of a traffic signaling management system relies heavily on achieving real-time and location-aware system response. Fog computing can improve intercommunication between vehicles, access points, and traffic signals for the overall enhancement of such systems [39].

3.4.4 Caching and processing for improved networking

Fog computing may also facilitate caching and processing operations for websites that work with large databases and huge amounts of data that needs to be processed, such as social networking, library, or online shopping websites, with the goal of improving their performance by reducing overall time and space complexity [40]. Zhu et al. [41] proposed one such solution in which users connect to the Internet through devices placed in the fog layer, which act as relays for all HTTP requests. The fog devices improve the response time through employing various optimization tasks depending on the scenarios and network conditions. For instance, if congestion occurs in the network, users may be provided lower-resolution graphics by a fog device in order to maintain acceptable response time. Another example of optimization would be choosing appropriate resolution for graphics based on the browser’s rendering capabilities on a client machine [33].

3.5 Related technologies

Other middleware technologies such as mobile edge computing (MEC) and Cloudlets that have been proposed in the literature also fall within the scope of fog computing [3]:

  • Cloudlets refer to servers or clusters of servers that have plenty of resources and are deployed in a single-hop proximity of mobiles users. They employ virtual machines (VMs) for enabling mobile devices to offload tasks in applications that require intensive computation [42]. The key motivation for employing cloudlets is to enable mobile devices that have scarce computational and storage resources to offload their intensive computation to the cloudlets, especially in applications that have stringent end-to-end latency requirements, with the goal of guaranteeing real-time interactive responses, which is something a distant cloud environment cannot guarantee. Another advantage of cloudlets is the fact that they can exist as a standalone environment acting as a full cloud at the edge of a network without cloud interaction, even though they actually reside in the middle of a three-tier hierarchy (mobile device - cloudlet - cloud) [13].

  • Mobile edge computing (MEC) was put forward by the European Telecommunication Standards Institute (ETSI) with the goal of enabling cloud computing capabilities closer to the mobile subscribers and within the radio access network (RAN) [13]. MEC services can be set up at different platforms such as LTE base stations (eNodeB) and 3G radio network controllers (RNC) [13]. The main goal of MEC is to improve application performance and consequently user experience by enabling the processing of user requests at the network edge, and as a result, reducing network congestion [3]. Some of the target applications include augmented reality and video processing.

A brief comparison between Cloudlets, MEC, and fog computing is given in Table 1.

Table 1 Comparison of fog, MEC, and cloudlet [13]
Full size table

4 Computation offloading for fog computing paradigm

With the emergence and rapid proliferation of IoT applications, the necessity to efficiently manage the execution of increasingly complex tasks based on the varying requirements of different applications has also risen. Some of these differences stem from the varying capabilities of user devices. For instance, some devices such as smartphones may require faster response necessitating additional computational resources, whereas some devices may need to be able to accumulate and process data before dispatching it to the cloud, thus, requiring creation of local services [43]. In order to free mobile devices with limited resources from performing complex tasks, computation offloading has been proposed by both industry and academia as a promising solution for effective integration of resources in computing ecosystems that are designed based on edge-fog-cloud paradigm. Offloading of computation-intensive tasks from constrained end devices to fog or cloud servers can significantly save energy and reduce response time [11].

4.1 Computing offloading decision

Offloading decision could be affected by several factors. This subsection discusses principal determinants and criteria used in making decisions whether proceeding with offloading or avoiding it would be more cost-effective.

4.1.1 Latency requirements

IoT applications that have strict latency requirements in the order of milliseconds can be considerably affected by the distance between nodes. In order to reduce end-to-end latency in such applications, offloading tasks such as data analytics at the network edge can prove to be very effective and lead to much faster response [44]. An example would be offloading a part of or the entire content from a multimedia services cloud to be cached at an edge or fog node in order to bring the content to a closer proximity to users for faster access [45].

4.1.2 Load balancing

Load balancing within a service provider’s ecosystem plays an important role with regards to optimizing processor throughput, response time, and resource utilization, as well as prevention of node overload, since a device that has reached its processing capacity is not capable of performing any additional tasks. In such scenarios, tasks could be appropriately distributed among multiple nodes/servers in a fog data center with the goal of balancing the load of incoming requests [45].

4.1.3 Intensive computation and other resource constraints

With the resource-constrained IoT devices, it is often the case that computation or storage requirements of an application exceed the capabilities of the device. In such cases, it is necessary to offload demanding tasks to other nodes that have more available resources (e.g., utilizing a cloud for updating map according to satellite data in a geographical map service application on a smartphone) [44, 45].

4.1.4 Privacy and security

In scenarios in which privacy and security concerns are raised, offloading may be preferred based on the susceptibility and privacy of data or tasks. For instance, data handled in a hospital or company may be transferred from a local storage to a private cloud. Likewise, a user may prefer to store private data in a personal mobile edge cloud instead of a smartphone [46].

4.1.5 Long-term storage

Depending upon the service type, long-term storage may take a lot of space. Thus, it may not be practical or sometimes even possible to satisfy storage requirements on small end devices such as smartphones. Offloading storage tasks in such cases to a cloud server that has abundant storage space for allocation is a practical solution [45].

4.1.6 Network bandwidth

In IoT applications, end users generate enormous amounts of data; however, these systems usually have limited bandwidth. Therefore, enabling data preprocessing and analytics at the network edge/fog layers can considerably minimize the network traffic load, and improve the overall network performance [44].

4.1.7 Energy efficiency

Energy is another important indicator that must be considered when making offloading decisions. The existing studies show that users usually prefer longer battery life over other features. A distributed nature of a fog environment that integrates many fog nodes enables distributed and more energy-efficient computation models as opposed to a centralized cloud-based model of computation [33]. Figure 3 illustrates how energy consumption affects decision making in fog. In this figure, we assume that the tasks of IoT devices (i.e., tablet, smart phone, and VR glasses) are partitioned into six sub computations (C1-C6). Then, it is decided which sub-computations will be offloaded based on the energy concern. Basically, a computation offloading decision may prevail on the following:

  • Local execution The entire computation is executed on a local device instead of performing offloading to fog servers. This situation occurs either when offloading is not cost-effective or when fog resources are unavailable. The tablet in Fig. 3 executes all computations locally.

  • Partial offloading Offloading only a part of the whole computation to fog nodes, while having the rest of the computation tasks executed locally. The VR glasses in Fig. 3 execute four computations locally and offload the remaining two to the fog server.

  • Full offloading Offloading the entire computation to be processed by fog nodes. The smart phone in Fig. 3 offloads all computations to the fog server.

Fig. 3
figure 3

Possible outputs of computing offloading decision for different application components at mobile devices

Full size image

4.2 Application models for computation offloading

Generally, mobile applications can be divided into N components, which makes it possible to implement partial/full offloading. Each component may differ in the amount of computation and latency requirements. Therefore, it is necessary to determine which components should be offloaded. As illustrated in Fig. 3, the first, second, third, and fourth components of the application at VR glasses are locally executed, while the fifth and sixth components are offloaded to the fog network. Likewise, all components can be fully offloaded in case of insufficient resources on mobile devices. In many applications, there are also some components that cannot be offloaded in any case (e.g., data I/O, camera, etc., which must be processed locally). Furthermore, some components are dependent on each other, and this dependency cannot be neglected in the offloading process, especially in cases when the outputs of some components act as inputs to other components, otherwise the execution performance could suffer greatly. Three prominent models for partitioning of applications in the process of offloading are task graph, inter-dependent modules, and deep neural network [10].

Task graph The simplest model for application partitioning is the task graph, usually represented as a directed acyclic graph (DAG), which is a widely used construction in cloud and fog computing for describing dependencies between components in complex distributed applications. In [47,48,49,50], the task-graph-based models were applied to model applications, which denote the dependency between different sub-tasks and the automated partitioning strategies for generating an optimal offloading. Furthermore, DAG can contain other relevant information in its vertices such as the number of necessary CPU cycles and the amount of required memory, as well as in its edges such as representing the amount of I/O data as edge weights [51].

Inter-dependent modules In this model, a large-scale application is partitioned into a set of modules that are deployed over the distributed nodes. Each component has different size and computation complexity. The dependencies between modules can be expressed as a unidirectional data flow. After the deployment of all modules, each module is expected to finish its computation within a fixed time. For example, [52] employs an inter-dependent module-based model to deploy a set of applications over fog nodes. The set of components represents the functionalities of applications, and each output of a module is served as an input to another module. The module management problem is tackled using linear programming and a heuristic approach, while considering both strict deadline and resource optimization.

Deep neural network (DNN) model DNN model has become increasingly popular as the core machine learning technique. It can be deployed as multilayers, distributed over different nodes, where each node is a processing element called neuron that applies a function to its inputs and generates an output. Different neurons are directly connected, and each connection defines a flow of data between two neurons. The output of a layer serves as an input to the next layer. The depth of a DNN is determined by the number of layers. An example application is a fog computing based industrial manufacture inspection application, which detects possible defects regarding the product, and sends back recommendations and production status [53]. This application is implemented as a 6-layer DNN model. The application computations are distributed among mobile devices, fog nodes, and a cloud server based on the computation costs. The main idea is to enable processing immensely large amount of data in real-time, which is achieved through adapting a deep learning-based classification model the fog computing paradigm with the goal of alleviating the computational burden of the central servers with the help of fog nodes.

Likewise, another research works focus on the distribution of the DNN across user devices, fog and cloud nodes, particularly to achieve low end-to-end latency and high energy efficiency [54, 55]. In [54], the authors designed a DNN-based Neurosurgeon framework to automatically partition the computation between mobile devices and fog nodes. The proposed Neurosurgeon framework models the partitioning between layers in order to achieve low end-to-end latency and energy efficiency. Their idea was to consider different partitioning points in the network and predict the energy consumption at each of those points, so that a partitioning which optimizes data transfer delay and minimizes energy consumption can be chosen. Similarly, their study was extended by employing distributed DNN across hierarchical fog nodes in [55].

A mobile application can be considered as a sequence of tasks. A task can be represented as \(T \langle I, D, W \rangle\) where I stands for the size of the input in bits, D for the completion deadline of the task in seconds, and W for the computation workload expressed in CPU cycles per bit. Tools such as task profilers can be used to estimate these parameters, which are essential parts of applications in terms of capturing the fundamental properties of mobile applications including computation and communication requirements. Furthermore, they can also assist with estimation of execution latency and energy consumption [51].

4.3 Proposed offloading algorithms and techniques

In this subsection, we present several offloading algorithms and techniques for fog computing recently proposed in the literature. Similar to [11], we classify the existing studies into three categories according to their optimization objectives: (1) studies that focus solely on minimizing energy consumption; (2) studies whose primary aim is to minimize delay; and (iii) studies that consider both energy and delay as metrics for optimization. Table 2 summarizes the surveyed studies.

4.3.1 Minimizing energy consumption

Minimizing the energy consumption in the computation offloading process is an optimization problem that has caught a lot of attention in research. Zhao et al. [56] proposed a full offloading algorithm that minimizes the energy consumption of mobile devices in a fog/cloud system while meeting the application’s latency and maximum transmission power requirements. The offloading decision to either fog or cloud is made dynamically based on the computed energy consumption of both models. Offloading to fog entails data transfer from the device to a fog node, the device idle time energy consumption, and the energy consumption that results from the actual computation at the fog node. Offloading to a cloud node, on the other hand, involves additional data transfer from the fog node to the cloud, idle time energy consumption of both device and fog node, as well as the energy consumed during the execution of the computation at the cloud. The experimental testing done through simulation showed that the proposed algorithm improves energy consumption of the system over a model solely based on cloud computing.

Chang et al. [57] designed a distributed algorithm based on the alternating direction method of multipliers (ADMM) technique to offload tasks in multi-user fog systems with the main purpose of minimizing energy consumption while satisfying the latency constraint. A queuing model is used to efficiently model the energy consumption at a mobile device and fog nodes. The simulation results have shown that the energy consumption is decreased when the offloading probability is increased while using a lower transmission power.

Table 2 Overview of the papers that focus on fog-based computation offloading
Full size table

4.3.2 Minimizing delay

Minimizing the latency in healthcare applications is of a crucial importance, especially in emergency response scenarios. Craciunescu et al. [58] investigated offloading cloud tasks such as storage and processing of healthcare data closer to the network edge (to fog nodes) in order to decrease the application latency and guarantee a quick response for patients in case of an emergency. They tested the proposed method in an e-Health laboratory and achieved a decrease in latency of two to four seconds in comparison with the cloud-only implementation.

Another challenging problem associated with making offloading decision for end-to-end latency optimization is selection of optimal fog site that will take the workload. If a number of users aggregate at a single fog node (e.g., a cloudlet), while leaving other nodes unused, this may lead to overloading some nodes while wasting the capacity of the others [11]. Sun and Ansari [59] investigated this problem and employed software defined networking (SDN) technology to propose a latency-aware offloading solution for mobile devices in an ecosystem of geographically distributed cloudlets. Their objective was to minimize the average response time which entails both network and cloudlet delays by selecting optimal cloudlets to be allocated for computational workload.

Harvesting renewable energy was explored by Mao et al. [67]. They developed a low-complexity dynamic computation offloading algorithm based on Lyapunov optimization, designed for mobile devices that are powered with renewable energy. The algorithm adjusts the CPU clock frequency, transmission power, and computation offloading decision with the goal of minimizing energy cost, execution delay, and task failure. They showed that the proposed algorithm is asymptotically optimal and provides improved performance in regard to energy conservation and decreasing offloading failure.

4.3.3 Jointly minimizing energy consumption and delay

A number of studies have investigated fog-based computation offloading taking both energy consumption and delay into account. Machine learning techniques have been employed in studies that propose offloading solutions that minimize delay and energy consumption in fog environments. In [60], Alli and Alam (2019) proposed a secure offloading solution for a fog-cloud environment. A machine learning-based particle swarm optimization (PSO) algorithm is designed to choose an optimal fog node to which offloading will incur the minimum processing delay between a mobile device and the fog. A fog node which has a high available computing capacity and maintaining energy is selected as an optimal fog node. In case the selected fog node is not capable of handling the incoming workload, a dynamic offloading to cloud servers based on Q-learning mechanism comes into play. During the offloading process, first a classification of the task is employed based on the task size, complexity, and latency. Then, the tasks are offloaded to either a private or public cloud accordingly. Finally, the authors applied a neural-fuzzy model to evaluate the security of the incoming tasks before offloading. The simulation results confirmed that the proposed approach reduces the delay and energy consumption compared to other existing solutions.

The joint minimization of energy consumption and delay in fog environment is also investigated in [62], where the authors formulated a multi-objective optimization problem using the nonlinear programming method to simultaneously optimize the energy consumption, latency, and the offloading cost. They applied queuing models to different elements of the fog network in order to deeply study the system cost. The simulation results showed that by adjusting the offloading probability and transmission power, the trade-off between energy, delay, and cost can be optimized.

Ma et al. [66] proposed a computing offloading strategy that enables multiple homogeneous and heterogeneous mobile devices to offload their computation to multiple wireless access points (APs) with the main purpose of minimizing energy consumption and delay. The total energy consumed during the offloading process consists of the transmission energy, the scanning energy of the APs, and the maintaining energy consumed to uphold the interface during transmission. They designed distributed offloading algorithms based on game theory in the context of homogeneous and heterogeneous mobile devices. The performance of the proposed algorithms is compared with local computation algorithm and random selection (the mobile user chooses one AP). The simulation results revealed that in the context of heterogeneous devices the proposed offloading policy can optimize the energy and delay compared to other algorithms, while increasing the number of mobile devices; however, in the context of homogeneous devices, it can improve the system cost for only up to ten mobile devices by 20% compared to others algorithms.

With the same goal of the aforementioned study, the problem of minimizing energy consumption and performance delay was similarly formulated using the game theory approach in [61, 63]. In [63], the authors designed an offloading scheme to optimize the system cost in terms of energy consumption and delay of the offloading process. Furthermore, the authors used the price of anarchy of the proposed scheme to quantify the distance between the proposed scheme and the optimal performance. In [61], the authors designed a dynamic offloading computation algorithm for a fog system with energy harvesting mobiles devices. They used queuing theory in their formalization to deeply derive the uplink-transmission energy consumption and response time models during the offloading process. Compared to the other existing algorithms, their proposed algorithm can achieve better results when the requests arrival rate is minimal.

Another idea that targets minimizing both energy consumption and delay was presented in [65]. Du et al. [65] formulated an optimization problem using mixed-integer nonlinear programming with the main goal to minimize the maximal cost in terms of energy consumption and delay for each offloading decision: local execution, fog processing, and cloud computing in multi-user fog/cloud computing systems. Furthermore, they designed an algorithm that makes an offloading decision with the minimum cost value of latency and energy, which performs computation resource allocation based on the final solution. The simulation results showed that the number of beneficial UE from the computation offloading is close to the total number of UEs compared to the method based only on local execution.

Furthermore, apart from exploitation of renewable energy, a technique known as dynamic voltage scaling (DVS) has also been utilized as an energy conservation method. Wang et al. [64] proposed an algorithm for partial task offloading in mobile edge computing based on DVS technique, which has bi-objective optimization function of minimizing both energy consumption and latency. The DVS is employed on mobile devices for the purpose of adjusting the processing speed in order to conserve energy.

5 Service placement in fog computing

Fog computing is usually deployed in a heterogeneous and constrained environment, which leads to a complex and sophisticated resource management. Thereby, enabling an efficient deployment for offloaded applications is a critical challenge. A major question that arises is how to manage task execution. More precisely, to which nodes a particular task should be assigned, and what metrics should be considered to evaluate deployment performance. Several studies have addressed these questions and many strategies have been proposed accordingly. We review these proposed strategies in the following subsections. First, we present the existing challenges according the application placement. Then, we discuss the optimization metrics that have been considered. Finally, we cover application placement algorithms that have been proposed so far.

Before reviewing the recent studies that focus on service placement, let us define this problem formally. Let A be a multi-service (multi-component) application with a set of requirements R, and let I be a distributed fog infrastructure. Service placement into fog infrastructure is a mapping of each service in A to a computation fog/cloud node in I, while meeting all requirements in R, and optimizing a set of objectives metrics O used to evaluate the placement performance.

5.1 Service placement challenges

A number of challenges regarding the problem of service placement in fog computing arise [49]:

  1. 1.

    Device heterogeneity: A suitable placement of services in a fog environment is impeded by heterogeneity of devices that are present at any of the network layers and locations.

  2. 2.

    Constraint diversity: Different IoT applications have diverse constraints and requirements that need to be satisfied in order for proper performance to be provided. These constraints/requirements may involve either consumable or non-consumable properties such as computing and bandwidth resources as the former, and latency or privacy as the latter. Meeting the diverse application requirements necessitates an intelligent approach in service selection.

  3. 3.

    Multi-tenancy: A fog infrastructure needs to be able to support the placement of multiple applications that require simultaneous management.

  4. 4.

    Scalability: The complexity of placement problem dramatically increases with a growing infrastructure size (number of devices) and application size (number of components), which makes it even harder to deal with this large-scale problem.

5.2 Optimization metrics

The problem of resource allocation and service placement in a fog system entails optimization of one or more specified metrics, the values of which need to be either minimized or maximized depending on a metric’s contribution to the system performance [49]. This subsection discusses the most widely considered optimization metrics in fog systems.

Latency: Reducing end-to-end latency of cloud-based delay-sensitive applications is one of the most important goals of fog computing, since it allows efficient monitoring and faster response of applications to their environment. There has been a lot of research that focuses on minimizing the latency of services placed on fog resources while meeting a number of constraints [62, 68, 69].

Energy consumption: Minimizing energy consumption in IoT in general and fog computing in particular is yet another crucial issue, especially due to the fact that IoT and fog devices have limited resources; hence, making energy consumption one of the most important metrics for performance optimization. It involves minimizing energy needed for transferring services from end users to fog nodes, energy consumed by the nodes for processing, and energy needed to transfer a service from a fog node to a cloud if necessary, all of which reduces the lifespan of a fog network.

Resource utilization: Optimizing resource utilization is another important metric in fog computing with a goal to maximize the number of services deployed over suitable fog nodes. The proposed approaches generally make deployment decisions that maximize the number of satisfied application requests (e.g., via prioritization of applications that have the closest deadline) [70, 71].

Cost: There are two main types of costs depending on the viewpoint (providers vs. users): data transmission cost (i.e., networking cost) and service execution cost. Other types of costs include expenses related to storage, deployment, etc.

QoS assurance: QoS provisioning may be associated with minimizing delays, but also many other metrics as well, some of which may not result in delay reduction. For example, if QoS is measured as the percentage of requests executed before a deadline, then guaranteeing QoS would involve keeping the execution times below a threshold, not necessarily resulting in delay minimization.

5.3 Proposed service placement strategies

In the literature, several studies have addressed the service placement problem in the fog environment. These studies were motivated by optimization objectives such as minimizing latency, reducing energy consumption, or improving the quality of service. In Table 3, we give a classification of the state-of-the-art studies according to the employed optimization strategies: (i) machine learning (ii) mathematical programming, (iii) heuristics, (iv) meta-heuristics, and (v) other methods. In the second column of this table, we list the application types each method focuses on. We give the objective metrics in column three. In the last two columns of this table, we note the advantages and limitations of each method.

Table 3 Summary of the case studies
Full size table

5.3.1 Mathematical programming

Mathematical programming is often used to solve optimization problems by formulating them as a mathematical model with constraints and an objective function. Then, the solution domain of the objective function is explored with the main purpose to either maximize or minimize its value, while guaranteeing to return the optimum solution. However, it is important to note that checking the whole solution space suffers from extremely high execution time, and is only feasible for smaller problems, unlike the complex service placement problem in a fog environment [29]. Different types of mathematical programming models such linear, nonlinear, and mixed-linear are studied in fog computing.

In [72], the authors proposed a framework for resource allocation in a fog computing environment. They defined a model based on integer linear programming (ILP) to optimize the placement of tasks in clusters of fog nodes. Each cluster is controlled by an efficient fog node, which plays the role of a broker and task orchestrator: it receives tasks to be executed from different IoT devices and places them in the cluster. Tasks that cannot be placed (e.g., due to a lack of resources) are redirected to the cloud. The objective function of their task placement model is to (i) maximize the number of tasks executed within each cluster, and therefore reduce the response time, and (ii) choose for each task a fog node that conforms to the processing resource requirements (i.e., CPU, RAM, storage, and bandwidth), and the node closest to the controller in terms of latency.

Furthermore, Daneshfar et al. [73], in addition to proposing a fog infrastructure, formulated the service placement problem as an ILP model with the goal to minimize the total cost of providing services when services are deployed onto fog nodes. Their formulation allows for a user to multi-cast their tasks to multiple fog servers in order to guarantee resource availability. They associated an availability value for each fog node, a cost of execution for each task (identical for all fog nodes), a maximum budget of time for each user to perform their tasks, and a maximum server number for each user to submit their tasks. The objective function of their model makes it possible to find a placement solution and multi-cast all tasks at a lower cost while respecting the desired availability for each user.

Similarly, Velasquez et al. [75] proposed an ILP-based approach for optimizing the placement of IoT services in fog with the following objectives: (i) minimize the number of jumps between the user and the requested service location in fog to minimize the latency, (ii) minimize the number of existing jumps between cooperative services, and (iii) minimize the total number of offloaded services compared to the previous offloading to improve the system stability.

Zeng et al. [74] considered service placement problem with task scheduling and workload balancing in software-defined embedded systems with a support of fog computing. They formulated the problem as a mixed-integer nonlinear programming (MINLP) problem and reduced it to a mixed-integer linear programming (MILP) problem to solve it with a commercial tool Gurobi. They compared the proposed method to server-greedy (i.e., cloud-ward) and client-greedy (i.e., edge-ward) placement strategies, and demonstrated through extensive simulations that their solution is computationally efficient even for such a high-complexity problem, while achieving improvements in performance and response time.

5.3.2 Heuristics

A dynamic and mobile nature of a fog infrastructure makes the service placement problem extremely complex in terms of computation, and an exact analysis of the entire solution space is practically inapplicable. Hence, heuristic approaches are often explored as they provide means to obtain solutions in a reasonable amount of time. Heuristics are a set of rules and techniques that facilitate getting feasible solutions for computationally complex problems. Nevertheless, they do not provide any performance guarantees [29].

Here, we present some of the most recent studies that employ heuristics for this problem. Xia et al. [49] proposed an objective function, which aims to minimize average response time of an application deployed onto a set of fog nodes. They developed two backtrack search-based algorithms, namely exhaustive search and native search, to find placement solutions. Exhaustive search tries to visit all existing solutions and returns the optimal one that minimizes the average response time, whereas native search returns the first found solution. Based on native search, they proposed two heuristics: the first one aims at minimizing the response time returned by the naive search and the second one accelerates the search process. The simulation results showed that the combination of both heuristics makes the placement decision-making process more scalable, which leads to a lower average response time.

Gu et al. [76] proposed a binary linear programming-based model and heuristics for task assignment in a MEC environment. Their model optimizes overall energy consumption induced by the execution and transmission of tasks, while ensuring that the delay constraint required by all tasks is satisfied. In their heuristics, server nodes (which process tasks) publish their performance among themselves (the frequency of the CPU). Then, each task is sent (from its source) to a potential server node for execution. The choice of a node is made by a function based on energy consumption. Upon receiving tasks, there are two possible cases: (i) the receiving node meets the required delay, and as a result, the task is handled by that node; and (ii) the node does not meet the required delay, in which case the task is forwarded to one of the nodes based on shared information about the nodes’ performance. This is done without any task administrators.

In [77], Yousefpour et al. proposed an algorithm that adopts the concept of load sharing to place tasks in a fog infrastructure, in which fog nodes collaborate with each other to execute the received request. Their algorithm aims to optimize the end-to-end service delay. A fog node accepts to execute the received request based on its estimated waiting time; otherwise, it forwards the request to one of its neighbors or to the cloud. In addition, probabilistic models are built to estimate the time it takes to complete a task in a fog node.

In [34], Taneja et al. proposed heuristics to place IoT service requests in a fog infrastructure. Their idea is to sort in ascending order: (i) fog nodes according to their processing performance, and (ii) service requests according to the amount of resources required. Then, for each service request, their heuristics search for a fog node that meets the processing performance required by that request. Unplaced service requests are redirected to the cloud. Although the proposed approach is simple and easy to deploy, it has several drawbacks: it does not consider constraints on the execution time of services, nor the balancing of the workload between fog nodes.

In [47], Mahmoud et al. proposed an energy-aware allocation heuristic for placing application tasks on fog devices with objective to minimize energy consumption. Their idea is to use the dynamic voltage and frequency scaling technology to adjust the CPU frequency of fog devices in a way to ensure a minimum increment of the energy consumption.

In [48], Lera et al. proposed a heuristic based method which aims to minimize the fog network delays that occur between interlinked services, while optimizing the QoS and the service availability for the users. Their heuristic involves prioritizing the applications with the shortest deadlines in the application placement process.

Furthermore, Mahmud et al. [52] proposed a first -fit-based service placement approach that aims at (i) minimizing the total service delay. They aim to guarantee applications’ QoS in satisfying service delivery deadlines.

5.3.3 Metaheuristics

Metaheuristic methods are generally inspired by nature. The main idea of these approaches is to try and improve the result in a reasonable time through an iterative process of searching for better solutions while trying to avoid getting stuck in local optima, unlike heuristic approaches that are prone to this problem. A number of metaheuristic techniques have been proposed in the literature, such as genetic algorithms (GAs) [82], ant colony optimization (ACO) [83], and particle swarm optimization (PSO) [84]. These algorithms are typically based on the idea of population (solution) evolution, in which the best solutions for a given objective are usually preserved for the next evolutionary step of obtaining a new generation of solutions with a hope of getting a fitter population [29].

Mebrek et al. [68] proposed a GA for optimizing task placement in a fog infrastructure. Their algorithm optimizes energy consumption incurred by the transfer and execution of tasks, while satisfying the delay constraints required for each task. In their optimization model, a task’s response time includes the time it takes to deliver the task, the time it takes to complete it, and possibly the time it takes to redirect the query to the cloud (in the case of insufficient resources).

Li et al. [78] combined the fuzzy clustering algorithm with PSO to propose a resource scheduling method for fog computing. Their algorithm divides users’ requirements into different classes: computing requirements, bandwidth requirements, and storage requirements. In addition, fog resources are classified according to their capabilities: storage, computing, and bandwidth resources, in order to match them to tasks.

In [69], Bitam et al. (2018) proposed a novel bio-inspired method, namely bees life algorithm (BLA), to address the task allocation problem in a fog computing environment. The aim of the study is to optimize the distribution of tasks among fog nodes by achieving optimal trade-off between CPU execution time and the memory used by fog nodes. The empirical evaluation of the performance in terms of response time and memory cost of the proposed method showed that it outperformed the existing PSO and GA approaches.

5.3.4 Machine learning

Machine learning techniques have also been employed by researchers to solve the service placement problem in fog systems. Deep reinforcement learning is the most used technique for service placement in fog computing. This technique enables learning policy in unknown environment through a trade-off between exploration and exploitation. In [79], Tang et al. exploited deep reinforcement learning technique to solve the service placement problem in fog computing. After modeling the problem as a multidimensional Markov decision process that aims to minimize communication delay, power consumption, and migration costs, they proposed a Q-learning algorithm to determine the optimal learning policy for placement decision making. The proposal took into account user mobility and was evaluated over a medium-sized infrastructure using real data.

In addition, Li at al. [80] proposed a deep reinforcement learning–based framework to decide the task scheduling strategy in hierarchical fog computing. They developed a four-layer neural network that incorporates two convolution layers and two fully connected layers, used to solve the scheduling problem after extensive training. Their main objective is guarantying QoS to the user by providing a minimum computing in cloud and bandwidth cost. The proposed framework is composed of a task scheduler and a fog node manager, and it operates as follows. The task scheduler collects the state information about all fog nodes and task requests, and forwards it to a learning network to generate several scheduling decisions. After that, the task scheduler chooses and forwards the best-valued decision to the fog node manager who allocates the fog nodes to the task requests based on that decision. Finally, a mobile device dispatches its data to the assigned fog node for processing.

5.3.5 Other strategies

A number of other strategies have also been investigated in the literature. In [62], Liu et al. formulated a multi-objective convex optimization problem with a set of constraints, which involves minimizing energy consumption, performance delay, and payment cost in fog-based mobile cloud computing (MCC) systems. First, they transformed the formulated multi-objective problem into a single objective problem using the scalarization method by applying a set of weight factors to reflect the importance of each objective including energy cost, execution time, and payment cost. Then, they addressed the problem by proposing an Interior point method-based algorithm, in which they focus on increasing the offloading probability for each service request in order to optimize the energy consumed by the mobile device, and strengthening the mobile device’s transmission power in order to reduce the execution time for request processing.

In [85], Wang et al. proposed a Hungarian algorithm based approach to task assignment in a mobile edge infrastructure, in which user tasks are divided into sub-tasks and assigned to effectively selected neighboring edge servers considering their characteristics including location, computing capacity, and the estimated waiting time. Their main purpose is to reduce the energy consumption with respect to a task’s delay constraint. The proposed approach is compared with greedy assignment and non-assignment methods.

5.4 Discussions

Based on our extensive review, we identified four main classes of commonly used approaches to deal with IoT application placement problem in fog computing: (1) mathematical programming such as integer linear programming (ILP), (2) heuristics such as best-fit, worst-fit, and backtracking search strategies, (3) meta-heuristics such as GA and PSO algorithms, and 4) machine learning-based approaches such as deep reinforcement learning.

From the scalability perspective, ILP-based service placement approaches suffer from a high computational CPU times as the problem size increases. The ILP solvers cannot handle the large number of variables in a reasonable time frame. ILP-based methods are not an efficient choice for a fog environment with a large number of resources and optimization parameters. On the other hand, heuristic and meta-heuristic approaches have much shorter execution times when compared to ILP-based methods; however, they do not guarantee the optimal solutions. Therefore, ILP-based methods are good candidates for small-sized problems, while heuristic and meta-heuristic methods can be preferred for large-sized problems. Furthermore, solutions returned by ILP-based methods can be used for evaluating heuristics and meta-heuristics. Finally, machine learning-based approaches such as deep reinforcement learning strategies suffer from a long training time in problems with large solution space for decision making.

When we consider the capabilities of aforementioned methods for the service placement problem, ILP is used to express the problem with mathematical formulations under the given constrains and objective function for systematically identifying the best candidate solution, with the aim of maximizing/minimizing the objective function. Meta-heuristic approaches like GA algorithms start by improving an initial valid placement iteratively. However, determining an initial valid placement is not an easy task due to the heterogeneous fog nodes and strict constraints of emergent IoT services. Heuristic approaches try to find a global optimal placement through an iterative optimization process; however, the initial solution may force the final solution to be a local optimal one. Therefore, both heuristics and meta-heuristics need good design decisions in terms of finding the global optimum. Deep reinforcement learning enables learning policy through an online approach under certain criteria. It can converge to the optimal decision for service placement problem. Nevertheless, the large solution space leads to long training times. Machine learning-based approaches are also suitable for fast changing environments of the fog systems. Most of the reviewed studies in this work apply Q-learning algorithm to search for optimal learning policy based on a trade-off between exploration and exploitation without any prior environment knowledge. Hence, Q-learning may be a suitable reinforcement learning method for decision making with limited information and a dynamic environment like the fog problems discussed in this survey.

6 Future research directions

After rigorously reviewing the previous studies, we observed some open issues in fog computing that can lead the future research on this topic to excel. We can list them as follows:

  1. 1.

    As we presented in Table 3, one of the most common disadvantages of the previous studies is not considering the mobility of the edge devices. They also do not take the user mobility into account. Therefore, a future work can focus on optimization methods that consider QoS along with the user mobility [86].

  2. 2.

    Most of the previous studies do not focus on handling multiple applications from numerous users. In such cases, real-time processing and online scheduling can be difficult problems to solve. Therefore, the new real-time and online scheduling methods for multiple applications coming from a number of different users can be an interesting problem to tackle [87].

  3. 3.

    Most of the existing service placement methods focus on energy, performance, cost, and QoS metrics. However, meeting QoS is very difficult in the presence of faulty fog nodes. Therefore, incorporating fault tolerance in service placement and computation offloading is a crucial issue. Thus, a new fault-tolerant offloading algorithms can be a good addition to the literature [87].

  4. 4.

    The prior work generally does not consider straggler nodes. However, a straggler can be present at any time in a network. This may pose a risk for the operation and QoS of the overall system. Therefore, identifying the straggler nodes in a network and mitigating their danger to the system are also very important problems to study [88].

  5. 5.

    Most of the previous task scheduling and offloading methods assume independent tasks. Therefore, there is still a huge need for considering dependent task scheduling under several factors such as communication overhead among edge devices and also fog devices. This problem becomes a very difficult optimization problem to solve when the number of metrics is increased [88].

  6. 6.

    Finally, applying machine learning algorithms on different network problems is still an open research area. Particularly, using these algorithms to predict the future network behavior is a very interesting research topic.

7 Conclusion

The fog computing concept brings computation resources closer to the network edge. This development has paved the way for the end users to offload their computation-intensive and delay-sensitive applications to fog nodes, in order to meet the strict application requirements of latency and to reduce energy consumption at end users. In this paper, we surveyed recent research related to computation offloading and service placement in fog. In particular, we have identified and classified the different approaches and strategies that have been developed according to their objectives. In this regard, the fog paradigm incurs critical challenges that need to be addressed to satisfy both users and service providers. Moreover, recent research validates the results of the proposed methods mostly in simplistic scenarios, while the tests under real assumptions have not been taken into account.

As the second contribution of this work, we reviewed the existing application placement strategies in fog computing from the perspectives of mapping techniques and placement objectives. We proposed separate taxonomies for each of the aspects of application placement and discussed their associated research issues. We also highlighted a perspective model for offloading applications in fog environments and presented several research directions for further exploration of the fog computing-related problems.