## 5 Grasp
### Feature Selection  
Given a WSN with \(N\) nodes, it is safe to say that node importance inside such network significantly varies from one to another. Since all the nodes must finally transmit their data to the sink node (i.e., base station), it can be seen that the furthest nodes will act as _leaves_ by only sending data, without needing to retransmit another node's packets. However, nodes very close to the base station will most likely act as bridge nodes, retransmitting the data from the rest of the nodes that are unable to reach the base station by themselves. Having this in mind, we have defined three features that allow us to rank the importance of the nodes in order to reduce the number of criticality tests. These features are the following:  
* Connectivity: Given a node \(i\in N\), node connectivity is defined as \(C=|\{\,j\,|\,j\
eq i,\,distance(i,j)\leq T_{range}^{max}\,\}|\) where \(T_{range}^{max}\) refers to the maximum possible range that a node can transmit using the more costly transmission level shown in Table 1.
* Hops to base station: For a node \(i\), this feature is defined, as its name indicates, as \(H=\left\lceil\frac{distance(i,bs)}{T_{range}^{max}}\right\rceil\), where \(bs\) stands for base station and \(T_{range}^{max}\) refers to the maximum possible range that a node can transmit using the more costly transmission level shown in Table 1.  
These two initial features can be calculated prior to obtaining any solution for a given network, since the only requirement for calculating them is the distance between nodes, which can be extracted from the node coordinates. However, we also define another feature directly related to the solution of the base case scenario (i.e., when no critical nodes are removed from the network):  
* Relay: A node \(i\) defines its relay as the number of outgoing connections. This number is equal to the amount of ingoing connections plus its own generated ones. Given the solution matrix \(f\) and the value \(f_{ij}\) which indicates how much data node \(i\) sends to node \(j\), the relay for node \(i\) is defined as \(R=\sum_{j\in N}f_{ij}\). Once all the features are defined, it is needed to see whether their use actually allows us to reduce the number of nodes to test for criticality without losing precision in the solution. In order to do so, 10 network topologies of \(N=100\) nodes are created by using a random node distribution in a 200 m radius area. These topologies are then analyzed using the GRASP meta-heuristic presented in Section 5.1 for obtaining the identification of the critical nodes by testing all the possible nodes and subset of nodes for both the latency and the lifetime model. Once the critical nodes are identified, we search their ranking position in the three features. It is worth mentioning that the nodes pinpointed as critical may actually not be the correct ones obtained by the analogous MIP model. However, we firstly analyze the features by only checking the GRASP, and, in Section 6, we analyze the percentage of identification success. Tables 2 and 3 show the overall percentage of success for each critical node subset tested and different individual feature thresholds for the latency and the lifetime models, respectively. Specifically, the top 3, 5, and 10 are used for both connectivity and relay. The hops to base station, however, differ  
from the two tests: in the case of the latency, it is sufficient to have \(H=1\) in order to achieve a 100% success. The lifetime model needs to extend this range up to \(H=2\) to achieve the same result. As it can be seen, the hops feature is a really good critical node predictor, since all the critical nodes are always very close to the base station. Relay is also a good predictor, since the values obtained for the _top 10_ are very high in both scenarios. However, connectivity does not seem to offer good reliability to identify critical nodes.