## 4 Problem Statement  
Given a WSN of \(N\) mica2 nodes [14], represented as \(V=\{1,\,2,\,...\,N\}\), a subset of critical node candidates \(N_{c}\in V\), the number of critical nodes to remove \(C\) and a table \(T\) shown in Table 1 of the possible transmission levels and the energy needed to transmit at each of these levels, a solution is found when each node \(i\), apart from the Base Station and the critical nodes under testing, transmits to a node \(j\) at a transmission level \(k\). Note that the chosen transmission level \(k\) is the least possible level that permits the interconnection between sensor \(i\) and \(j\) range-wise, in order to reduce energy consumption levels at the minimum possible ones. Therefore, a solution is represented by two vectors, namely _send_ and _key_, both of size \(N\). The former stores, for each position \(i\), the node \(j\) to which data are sent. Likewise, the later stores the transmission level \(k\) needed for that communication. A solution is considered valid if \(1<=\textit{send}_{i}<=N\) and \(0<=\textit{key}_{i}<=|T|\ \forall i\in V\setminus N_{c}\):  
\[\sum_{n\in V}calculatePathCost(n,G_{current}). \tag{1}\]  
Two different objective functions are considered, covering two of the major and most important requirements a WSN should have, latency and lifetime. The former makes reference to the required time to transmit data from one sensor to the sink node, whilst the latter refers to the amount of _time steps_ the network can be maintained alive without needing to charge or change node batteries if every node creates and transmits a single data packet at each aforementioned _time step_. We consider networklatency as the summation of the hops needed from each sensor to reach the base station, as shown in Equation (1). The _calculatePathCost_ returns such value for a given node and a given network state. Additionally, network lifetime is defined as the amount of packets that can be generated in each node until the critical one runs out of energy. It is worth noticing that this value is equal for all the nodes, and can be seen as the number of time slots \(t\) that the network is alive if, at each time slot, one packet is generated and transmitted in each of the network nodes apart from the base station:  
\[Lifetime=\frac{battery}{E_{rx}*input+E_{tx}*output}. \tag{2}\]  
Equation (2) shows a general definition for lifetime, where _battery_ is the amount of energy each node initially has, \(E_{rx}\) and \(E_{tx}\) are the values needed for receiving and transmitting a single packet, respectively, and \(input\) and \(output\) are the number of connections each node sends and transmits, respectively. In order to find the most influential subset of critical nodes of size \(C\), it is needed to calculate the impact of each possible subset formed by the candidates. That is, given \(N_{c}\), we compute all the possible combinations without order _Perms_. Each of these combinations is then analyzed to see its impact in terms of the current objective function under testing. Once all the solutions are found, nodes pertaining to the combination \(Perms_{i}\) with the worst solution are considered the critical nodes. Figure 1 shows the framework used for such analysis. Firstly, a new network of \(N\) nodes is created. This network is randomly generated by selecting \(N\) node coordinates within the radius range under study. Figure 2 shows an example of a network of \(N=100\) sensors distributed across a disk shaped area of 200 m radius. After that, we initially run the GRASP without removing any node to store the reference value. In the event of not finding a valid solution due to the randomness of the network generation tool, the network is re-generated. This process is done iteratively until a valid network is found.