## 1 Introduction  
Over the last years, Wireless Sensor Networks (WSNs) have attracted a great interest in both industry and academy. This fact is because of the open possibilities for monitoring systems and environments with reduced deployment and maintenance costs. As a result, many practical applications were rolled out with the advancement of technologies. For instance, they were successfully applied for smart grids, smart farming, and smart buildings [1; 2; 3]. A Traditional Wireless Sensor Network (T-WSN) is composed of many sensors capturing information and a single sink node (or several ones) collecting all data. The sensors have some interesting features, which encourage the use of this technology. For instance, they are small, power-autonomous, wireless, cheap, and able to capture different types of measures in the same device. Moreover, the wire absence facilitates the network deployment, meaning a reduction of the deployment costs. These features, among others, allow considering WSNs in environments, where the deployment of wired technologies would be expensive or even impossible [4]. Nevertheless, WSNs also present important shortcomings, e.g., latency, coverage, energy efficiency, computing capacity, security, and network lifetime. Such factors are important for maintaining the Quality of Service (QoS), which is critical for many real-world applications [5]. One aspect of great importance in WSNs is energy efficiency. This fact is due to sensors are usually powered by batteries, whose replacement is often difficult, involving a cost and a loss of performance [6]. In case that a T-WSN considers a simple star topology, the energy cost distribution is similar for all sensors over the operation time. However, in a real scenario, the topology is quite different because of network size, application requirements, or land orography. Under these circumstances, it is usual to consider a multi-hop topology, where sensors relay data. As expected, the energy cost distribution in a multi-hop topology could be unbalanced due to the relaying task of sensors, generating bottlenecks, i.e., sensors subject to higher energy costs than others, meaning that batteries drain faster. These bottlenecks could generate disconnected areas in the WNS, negatively affecting QoS. A possible solution to this issue is the T-WSN deployment with redundant sensors. However, this focus implies high maintenance and deployment costs. In response to the need to avoid bottlenecks in multi-hop topologies, a device specialized in communication tasks and called Relay Node (RN) was added to T-WSNs [7]. RNs send all information received to the sink node, so reducing the workload of sensors in the vicinity. There are two different approaches under this network model: Single-Tiered and Two-Tiered WSNs, ST-WSNs and TT-WSNs, respectively. The first model considers that all devices can communicate among them by following a multi-hop routing protocol. The second model is a cluster-based network, where the sensors send data to the RN in one hop; then, the RN forwards the data to the sink node in one or more hops, where the path only includes other RNs and the sink node. In both network models, RNs should have higher energy capacity than sensors, e.g., having large batteries, being plugged into the grid, or being energy-harvesting devices. As a consequence, RNs are significantly more expensive than sensors, and then their deployment should be carefully studied to maximise the investment. The deployment of WSNs was defined as a Non-deterministic Polynomial-time hard (NP-hard) optimization problem in the literature [8; 9]. As known, exact techniques are not recommended for solving NP-hard problems, due to computing time increases exponentially with the problem dimension. Instead, approximate techniques should be considered, e.g., heuristics and metaheuristics [10]. Note that it is possible to solve NP-hard problems using exact techniques for instances of limited size [11].