# GASP: Genetic Algorithms for Service Placement in Fog Computing Systems
## 2 Problem Definition
### Optimization Model  
The main problem in the considered fog scenario is how to map on the fog nodes the data flows coming from the sensors. To this aim, we define an optimization problem where we use as the main decision variable a matrix of Boolean flags, \(x_{i,j}\). In our model, \(x_{i,j}=1\) if and only if sensor \(i\) is sending data to fog node \(j\); otherwise, \(x_{i,j}=0\). As the function of fog nodes is to preprocess the incoming data performing filtering and aggregation, we consider that all the data of a sensor must be sent to the same fog node and cannot be distributed across the fog layer.  
Again, the reader may refer to Table 1 for a summary of the parameters used in our model.  
The optimization model to address the previously-described problem can be formalized as follows, with an approach similar to the problem of allocating requests over a distributed infrastructure, such as VMs on a cloud [10; 12; 13]. In particular, we introduce a matrix of Boolean decision variables \(X=\{x_{i,j}\}\) that is used to define the objective function and the constraints as follows,  
\[\min obj(X)=\sum_{i\in S}\sum_{j\in J}x_{i,j}\cdot\left(\frac{1}{\mu_{j}- \lambda_{j}}+\delta_{i,j}\right) \tag{1}\]  
\begin{table}
\begin{tabular}{c l} \hline \hline
**Symbol** & **Meaning/Role** \\ \hline
**Decision Variables** \\ \hline \(x_{i,j}\) & Sending data flow from sensor \(i\) to fog node \(j\) \\ \hline
**Model Parameters** \\ \hline \(\mathcal{S}\) & Set of sensors \\ \(\mathcal{F}\) & Set of Fog nodes \\ \(\lambda_{i}\) & Outgoing data rate from sensor \(i\) \\ \(\lambda_{j}\) & Incoming data rate at fog node \(j\) \\ \(1/\mu_{j}\) & Processing time at fog node \(j\) \\ \(\delta_{i,j}\) & Communication latency between sensor \(i\) to fog node \(j\) \\ \hline
**Model Variables** \\ \hline \(i\) & Index of a sensor \\ \(j\) & Index of a fog node \\ \hline \hline \end{tabular}
\end{table}
Table 1: Notation.  
subject to  
\[\lambda_{j}=\sum_{i\in\mathcal{S}}x_{i,j}\cdot\lambda_{i} \forall j\in\mathcal{F}, \tag{2}\] \[\sum_{j\in\mathcal{F}}x_{i,j}=1 \forall i\in\mathcal{S},\] (3) \[\lambda_{j}<\mu_{j} \forall j\in\mathcal{F},\] (4) \[x_{i,j}=\{0,1\}, \forall i\in\mathcal{S},j\in\mathcal{F}, \tag{5}\]  
In the problem formalization, objective function (1) aims to reduce the total (and hence the average) latency and processing time from every sensor to the fog computing nodes. The expression of response time used for our objective function is consistent with other studies in literature focusing on distributed cloud infrastructures [14]. Specifically, the average processing time is derived from [PERSON]'s result applied to a M/G/1 model and considers just the average arrival frequency \(\lambda_{j}\) and the processing rate \(\mu_{j}\) of each fog node \(j\). This definition of the response time has been widely adopted in literature, for example in [14]. The second part of the objective function, that is, the latency contribution, effectively captures the communication delay of a geographically distributed infrastructure using the latency \(\delta_{i,j}\).  
Together with the objective function, we have a set of constraints. Equation (2) defines the incoming load, \(\lambda_{j}\), on each fog node, \(j\). Constraint (3) means that for every sensor, \(i\), we direct its output to one and only one fog node. Constraint (4) guarantees that, for every fog node \(j\), we avoid a congestion situation, where the incoming load \(\lambda_{j}\) exceeds the processing capability \(\mu_{j}\) of that node. Finally, constraint (5) defines the Boolean nature of the decision variables \(x_{i,j}\).