# An Energy-Efficient Approach to Enhance Virtual Sensors Provisioning in Sensor Clouds Environments
## 4 The Proposed Approach
### ACOSIMv2--Ant Colony Optimization for Sensor Selection Based on Similarity
#### 4.2.2 Solution Construction Procedure  
Usually, an ACO algorithm executes in terms of iterations. At the beginning of a new iteration, artificial ants are launched, and each of them is responsible for building a solution. A solution is defined by the path that a specific ant took from a source towards a final destination. At the end of the iteration, all solutions are evaluated, and the better solution is chosen. ACO repeats this process until found a termination criteria, also called stopping condition. The most common used termination criteria are: (i) maximum number of iterations is exceeded; (ii) an acceptable solution is found; and (iii) all ants start to follow the same path (stagnation behavior). The provisioning problem defines a solution as a subset of nodes taken from the set of all nodes in the sensor cloud. Since ACASIMv2 creates cluster of similar nodes, in order to build a solution, the ant just needs to pass through all clusters and select at least one node. To explain how ACOSIMv2 runs, it will be used, as an example, a sensor cloud with five clusters created by ACASIMv2 (Figure 4b). Each cluster has a index \(c\) and also a sensor type \(t\) associated to it, since ACASIMv2 clusters sensor nodes by sensor types (or dimensions). Let \(N_{C}\) be the number of clusters created by ACASIMv2 (In the given example, \(N_{C}=5\)) and \(C_{c,t}\) (\(1\leq c\leq N_{C}\) and \(t\in TYPE\)) be the set of sensor nodes (\(SN_{i,j}\)) inside the \(c\)-\(th\) cluster. In Figure 4b, \(C_{1,T}=\{1,2\}\), \(C_{2,T}=\{4,3\}\), \(C_{3,H}=\{2\}\), \(C_{4,H}=\{4,1\}\), and \(C_{5,L}=\{1,2,3,4\}\), where \(T\), \(H\), and \(L\) stand for _Temperature_, _Humidity_, and _Light_ respectively. Let \(G=(V,E)\) be a graph, with \(V=\{SN_{i,j}|1\leq i\leq N,and1\leq j\leq N^{i}\}\), and \(E\) be the set of all the edges formed by the combination of nodes in \(C_{x,y}\) and \(C_{x+1,z}\), \(1\leq x<N_{C}\), \(y\in TYPE\), \(z\in TYPE\) (Figure 4c). At each iteration, \(N_{A}\) ants, starting from different nodes, begins its search process through the graph, as shown in Figure 4c (for the sake of simplicity, only one route taken by an ant is depicted). Let \(\Omega_{it}^{a}\subset V\) be the solution found by the \(a_{th}\) ant at the end of the \(it_{th}\) iteration. At the beginning of the next iteration \(\Omega_{it}^{a}=\{\varnothing\}\). Following the example, the ant starts its first interaction (\(a=1,it=1\)) at Node 1, from \(C_{1,T}\), heading to Node 4 at Cluster \(C_{2,T}\). After that, the ant starts exploring the next dimension, going to Node 4 at Cluster \(C_{3,H}\), heading to 1, at \(C_{4,H}\). Finally the ant gets to 1, at \(C_{5,L}\), with \(\Omega_{1}^{1}=\{1,4\}\). The middleware also associates which sensor types each node will deactivate. In the example, the sensor Node 4 does not need to monitor _Light_ variable anymore, since its measurements can be represented by sensor Node 1. The choice of the edge is based on a function that calculates the probability of each edge (Equation (15)). Thus, edges with higher probability have greater chances of being selected. The input of this function is the amount of pheromone on the edge and a heuristic value that represents the knowledge related to the specific problem (see Section 4.2.4). The path is finalized when the ant has gone through all the clusters. At least one sensor node from each cluster will be part of the solution. Consequently, the virtual sensor will have a complete view of the region of interest. After all ants have performed their search, a procedure is executed in which the values of the pheromones of the edges are updated (Equation (12)). The amount of pheromone to be deposited is related to the cost of the path that passes through the edges. Thus, the better the path, the greater the amount of pheromone deposited at its edges. In the provisioning problem, the cost is given by Equation (6) (see Section 4.2.3. Furthermore, there is an evaporation process that decreases the amount of pheromone already deposited.