# GASP: Genetic Algorithms for Service Placement in Fog Computing Systems
## 2 Problem Definition
### Mapping Problem  
Our problem concerns the management of data flows in a fog infrastructure such as the one shown in Figure 1b. The infrastructure, which we assume to be deployed in a smart city scenario, is composed of three layers: a sensor layer, which produces data (represented as a set of wireless sensors at the bottom of the figure); a fog layer, which is responsible for a preliminary processing of data from the sensors (second layer in the figure); and a cloud layer, which is the final destination of the data (at the top of the figure). The underlying application logic involves the typical services of a smart city scenario. Sensors collect information about the city status, such as traffic intensity or air quality [9]. Such data should be collected at the level of a Cloud infrastructure to provide value-added services such as traffic or pollution forecast. The proposed fog layer intermediates the communication between the sensors and the cloud to provide scalability and reliability in the smart city services.  
In our model, we assume a stationary scenario, where a set of similar sensors, \(\mathcal{S}\), are distributed over an area (we consider the sensors to be not moving; although, a different scenario, where mobility is taken into account, can be easily introduced in our model). Furthermore, we assume that sensors are producing data at a steady rate, with a frequency that we denote as \(\lambda_{i}\) for the generic sensor \(i\) (for a summary of the symbols used in the model, the reader may refer to Table 1). The fog layer comprises a set of nodes \(\mathcal{F}\) that receive data from the sensors and perform operations on them. These operations typically include preprocessing of the data, such as filtering and/or aggregation, or may include some form of analysis to identify anomalies or problems as fast as possible. The refined data samples from the fog nodes are then sent to a cloud platform where additional analysis is carried out and where all the information is stored. These additional analysis tasks are typically highly expensive from a computational point of view.  
As the problem concerning the management of large cloud data centers has been widely addressed in the literature [10; 11], we do not consider the inner details of the cloud layer in our problem modeling, such as the computation time at the level of the cloud data center. Similarly, we do not consider the network-based latency due to the communication between the fog nodes and the cloud data center, as we assume this latency to be the same for all fog nodes and hence having no impact on the optimum mapping solution. Instead, we focus our attention to the problem of coordinating the communication of the elements in the sensor layer with the nodes in the fog layer. Specifically, we want to guarantee a high QoS, in terms of fast response. To this aim, we model the response time according to a queuing theory-based formulation, considering that the response time has two major contributions that should be taken into account:  
* Network-based latency due to the communication between the sensor and the fog nodes. We denote this value as \(\delta_{i,j}\), where \(i\) is a sensor and \(j\) is a fog node.
* Computation time on the fog node. According to queuing theory, this time depends on the computation cost of the request (we denote as \(1/\mu_{j}\) the time to process a packet of data from a sensor on fog node \(j\), relying on the typical queuing theory notation) and on the rate, \(\lambda_{j}\), of the jobs incoming at fog node \(j\), where the value of \(\lambda_{j}\) is the sum of all the outgoing data rates, \(\lambda_{i}\), of all the sensors, \(i\), that are communicating with the fog node \(j\). For the sake of clarity we summarize the symbols used throughout the paper in Table 1.