## 1 Introduction  
A wireless sensor network (WSN) is a multi-hop self-organizing information perception and data collection system. It can obtain detailed and accurate data in a variety of environments and pass the information between people and the objective world [1, 2]. Among the many challenges in WSN applications, one of the most basic problems is how to deploy sensor nodes (SNs) reasonably in order to meet the service quality of the network. In a WSN composed of ordinary nodes, the energy of the nodes is limited [3] and the communication burden of certain nodes is heavy, which easily causes the network to stop working prematurely [4]. To tackle this problem, a large number of redundant SNs generally need to be deployed in the network; however, this causes a lot of additional costs. The alternative solution is to reasonably deploy a small number of relay nodes (RNs) with high energy in the traditional WSN [5]; that is, the accurate calculation the location of RNs can help to replace the large number of redundant SNs deployed. Based on their deployment, related research can be divided into the categories of single-tiered and two-tiered WSN RN deployments [4]. All devices deployed in single-tiered WSN (ST-WSN) follow the same multi-hop routing rules except for the sink node. In the deployment of two-tiered WSN (TT-WSN), ordinary nodes only send data to RNs in one hop, and RNs only send information to sink nodes or other RNs. Finally, RNs send information to the sink. Due to the high cost of RNs, scholars are greatly concerned with how to deploy the fewest RNs in a network. However, when there are a fixed number of RNs, another problem that cannot be ignored is how to deploy them to form the optimal upper-layer skeleton of the network in order to optimize its lifetime. This problem is NP-Hard [6], and must be solved with non-traditional methods. Both RNs and SNs deployed in an ST-WSN forward the received packets. The deployment of a minimum number of RNs has been studied in a series of fixed candidate locations in a WSN with guaranteed network connectivity [7]. As an extension of this study, [PERSON] et al. [8] investigated how to deploy a minimum number of RNs in an energy harvesting WSN while ensuring the connectivity and lifetime of the network. The candidate locations with energy harvesting potential were predetermined. [PERSON] et al. [9] used a multi-objective algorithm to optimize the energy consumption and the number of routes for a single-tiered WSN. [PERSON] et al. [10] proposed a branch-and-cut algorithm to deploy a minimum number of RNs in certain candidate locations in an ST-WSN to ensure that the duration of sensor node and base station communication satisfies a predetermined delay bound. [PERSON] et al. [11] proposed a multi-objective network repair algorithm to restore the connectivity of WSNs in unknown regions. [PERSON] and [PERSON] [12] studied the problem of how to ensure network connectivity by deploying RNs in an ST-WSN. They transformed the RN deployment problem into a mixed integer programming model using genetic algorithms and simulated annealing algorithms to find the minimum number of RNs to be deployed and their reasonable locations. [PERSON] and [PERSON] [4] investigated how to deploy RNs in a ST-WSN based on a meta-heuristic algorithm. Their aims was to optimize the average energy consumption of the network as well as its average sensing area. Compared to ST-WSNs, TT-WSNs are more balanced in energy consumption for SNs, although they are more complex in network topology formation. A genetic algorithm-based clustering method was proposed to optimize the lifetime of a TT-WSN with different delays in [13]. In their study, a multi-objective and top level GA was applied to obtain clustering schemes to optimize the network lifetime for different delay values. The low level GA is used in each cluster in order to find the most efficient topology for the transmission of data from sensor nodes to the cluster head.