1 Introduction

Wireless sensor network (WSN) has been widely spread in industry, agriculture, smart home and other fields for its attractive advantages, such as self-organizing, low-power consumption and scalability [1,2,3,4]. However, many application scenarios of WSN have the constraints of electromagnetic obstacle or interference, such as metal structures, equipment and other electromagnetic signals in the same frequency band, and the battery is usually used as power to gain the portability and efficiency related benefits. Therefore, the geographical distribution and power supply of WSN is restricted, and the network characteristics, such as energy efficiency, stable connectivity, survivability and low cost, should be specially designed in these applications [5,6,7,8].

A WSN is composed of sink nodes, sensor nodes (SNs) and relay nodes (RNs). Generally, the number and location of SNs and sink nodes are fixed and known, the communication distance of SNs is short, compared with that of RNs and sink nodes, to save power, and the RNs are necessary to forward SNs data to the sink nodes. The electromagnetic obstacle or interference in constrained scenarios may attenuate the effective transmission distance or even block the transmission of wireless signals, hence the RNs cannot be deployed anywhere we want. Therefore, the constrained Relay Node Deployment (RND) problem is more practical and challenging compared with the unconstrained RND problem [9,10,11,12,13,14,15,16]. The constrained RND for optimizing different network characteristics has been widely explored in literatures, and it has been proven to be NP-hard [17,18,19,20,21,22,23,24,25].

Depending on whether the SNs will forward data from other SNs and RNs, the WSN has two network structures, namely single-tiered network and two-tiered network [18, 20]. The two-tiered network is composed by a data-acquisition layer formed by SNs and a data-forwarding layer formed by RNs and sink nodes. SNs in a two-tiered network do not forward data from other SNs and RNs, hence they can consume less energy. RNs in a two-tiered network are responsible for data forwarding and optimizing network characteristics. The constrained RND for two-tiered WSN is further explored in this paper. Furthermore, the two-tiered WSN here is static, which means that the number and location of RNs are fixed and known after deployment.

Many efforts have been focused on the approximate solution of the constrained RND for two-tiered WSN: (a) the Steiner Tree based approach considering the constraints of pre-specified candidate locations and survivability, (b) the Integer Linear Program (ILP) based method with the constraints of reliability and lifetime, (c) the set-covering and the pruning-substitution based heuristic algorithm with the constraints of connectivity and delay, (d) the Artificial Bee Colony based swarm intelligence algorithm [17,18,19,20,21,22,23,24,25]. Although these methods are solved offline, they will encounter the problem of low efficiency or even failure when solving large-scale RND problems. Furthermore, the multi-constraint optimization performance of these methods should be further improved when solving the constrained RND problems that are simultaneously limited by network cost, lifetime, survivability and reliability.

Motivated by these reasons, the constrained RND problem for two-tiered WSN is further explored in this paper. Inspired by the minimum spanning tree and Steiner tree based approaches for RND problem, a simple idea to save the number of deployed RNs is to find the candidate deployment locations of RNs on the shortest path between the SNs and the sink [11, 14, 19, 20]. Then, all shortest paths form an effective extraction of the constrained deployment space, which can effectively reduce the solution space of the constrained RND problem and improve the solution efficiency. Besides, as an important approach to promote the reliability of wireless communication, the retransmission mechanism has been widely involved in WSN protocols [26, 27]. However, its effect on increasing energy cost has not been considered by the approximate solutions of RND problem. In a WSN, the lifetime of a node powered by battery depends on its power consumption measured by the wireless communication distance and traffic volume [11]. Therefore, the lifetime of two-tiered WSN can be considered over as soon as the battery power of one relay node in the network is completely depleted [9,10,11]. At last, an ILP based approach is proposed to improve the multi-constraint optimization performance when solving constrained RND problem that are simultaneously limited by network cost, lifetime, survivability and reliability. As a summary, the main contributions of this paper are as follows:

  1. (a)

    The shortest path search is used to extract the constrained three-dimensional deployment space, and to improve the solution efficiency of the constrained RND problem.

  2. (b)

    The retransmission mechanism is used to improve the energy consumption model of RNs, and thus to improve the practicability of the deployment approach.

  3. (c)

    An ILP based optimization model is proposed to find the least and optimal RNs, and to maximize the network lifetime under the constraints of specific network survivability and reliability.

The rest of this paper is organized as follows. In Sect. 2, the related works are presented. Section 3 presents the ILP based fast multi-constraint deployment strategy. Section 4 presents the simulation results. Finally, the paper is concluded in Sect. 5.

2 Related Work

In this section, the description and extraction of deployment space, assessment of wireless channel and optimization approach in the existing work is presented.

By discretizing the continuous deployable area of the deployment space into candidate locations, the constrained RND problem can be converted into a tractable combinatorial optimization problem while preserving engineering-acceptable accuracy [12, 17, 18]. In [12], two discretization methods based on grid and intersection point are designed for small-scale and large-scale RND problem, respectively. The grid based discretization methods have also been involved in some Graph Theory based heuristic methods [17, 18]. Furthermore, the discretization method for three-dimensional space is rarely involved. In [17], a practical three-dimensional space discretization idea was used to describe a nuclear power plant.

Generally, the constrained RND problem can achieve a better result as the discretization is more deepened, but the solution process takes more time or even unacceptable long time. Therefore, the discretized deployment space should be reasonably extracted. At present, the spanning tree and the Steiner tree based methods have been involved to extract the unconstrained two-dimensional space [11, 12, 14, 18]. However, in the constrained deployment space, it is impractical to search the intersections of communication circles of nodes, or to find a simple straight path between two nodes. Therefore, a shortest path search approach can be involved when solving the constrained RND problems. In this paper, the Dijkstra based shortest path search approach is involved [28]. The idea is to search all shortest reachable paths between the SNs and sink nodes, and then an extracted candidate location set for RNs is formed by all the positions on these paths. Although this extraction may reduce the solution accuracy, the solution space is greatly compressed, and the subsequent simulation shows that the attenuation of the solution accuracy is acceptable.

The wireless channel can be affected by numerous parameters, such as noise, interferences, deployment space, communication distance, wireless transceiver performance, radio frequency band and transmission medium, etc. [7, 8, 29]. Furthermore, the link quality of wireless channel can affect the network characteristics, such as the energy consumption and network delay, and it is difficult and costly to be accurately calculated in practice. Therefore, a simple and effective evaluation method based on the communication distance and path-loss parameter has become an important research direction [30, 31]. In [17], a reliability model evaluates the communications in wireless channel with severe obstacle or long communication distance as low success rate, and these communications requires more transmissions (retransmission mechanism) and consumes more energy. The retransmission mechanism can improve the network reliability at the expense of more energy consumption, and its impact on energy consumption has been rarely involved in existing work [26, 27].

In the optimization approaches for the constrained RND problem, many efforts turn the RND problem into Steiner tree problem. In [19], the Steiner Tree based RNPc-P and RNPs-P solutions were proposed with the constraints of connectivity and survivability. This work has been further expanded in [18, 20, 21]. However, these efforts only focused on the constrained RND problem with few constraints, and the deployment space was two-dimensional. Besides, these Steiner Tree based methods can obtain accurate solutions, but their computational complexity is high, and currently there is no efficient strategy for large-scale RND problem. To solve this problem, some efficient heuristic methods have been proposed. The pruning-substitution, set-covering and subtree-mergence based heuristic methods were proposed in [22,23,24], respectively. However, the accuracy of such methods needs further verification, and currently they only involves the constraints of deployment costs and network survivability.

By reasonably discretizing the deployment space, the ILP-based methods convert the constrained RND problem into a convex optimization problem, which can balance the solution accuracy and efficiency. In [12], an ILP based deployment strategy with the constraints of network survivability and lifetime was proposed to solve the unconstrained RND problem in two-dimensional deployment space, and an intersection based approach was involved to solve the large-scale RND problem. In [17], a practical ILP based approach optimizing the number and location of RNs with the constraints of network connectivity and reliability was proposed for the WSN application in nuclear power plants. However, for two-tiered WSN, when solving the constrained RND problems that are simultaneously limited by network lifetime, survivability and reliability, the multi-constraint optimization performance of the ILP-based solution can be further improved.

3 Problem Formulation

An efficient ILP-based multi-constraint deployment strategy for two-tiered WSN is proposed in this section. It is assumed that the physical distribution and size of three-dimensional deployment space with electromagnetic obstacle, the locations of the SNs and one sink node, parameters related to the remaining energy and energy consumption of the RNs, and the data forwarding rates of the SNs are known and static. Based on these, the proposed strategy solves the RND problem for two-tiered network such that the following constraints are satisfied:

  1. (a)

    The number of deployed RNs is minimized.

  2. (b)

    The maximum energy consumption of RNs is minimized, that is, the lifetime of the network is maximized, when the same number of RNs is deployed.

  3. (c)

    Each sensor node can communicate with at least ks relay nodes, and ks ≥ 1.

  4. (d)

    Each relay node has kr effective paths to forward data to the sink node, and kr ≥ 1.

  5. (e)

    Each wireless channel (between nodes with non-zero data flow) meets a preset reliability.

  6. (f)

    The impact of wireless channel reliability on node energy consumption is involved.

  7. (g)

    The energy consumption of each relay node meets the constraints of preset limit.

  8. (h)

    The traffic of each relay node meets a preset capacity constraint.

The constraints (a) and (b) are the optimization objects, which are to maximize the lifetime when employing the minimal RNs. The (c) and (d) represent the limits of the network survivability for SNs and RNs separately. Among the ks RNs that one sensor node can communicate with, only one RN can collect the data of this sensor node, which will be the primary cluster head of this sensor node, and the remaining RNs will be the back-up cluster heads of this sensor node, and there are no data flow between this sensor node and its back-up cluster heads. The (e)–(h) represent the limits of the network reliability and energy consumption. The data collection in the network is assumed to be periodic, and hence an extensively used calculation method of lifetime, N-of-N lifetime, is adopted [12].

4 Notation

The input parameters of the proposed ILP based model are in Table 1.

Table 1 The input parameters
Full size table

The variables of the proposed ILP based model are in Table 2.

Table 2 The variables
Full size table

4.1 Network model and reliability evaluation model

The two-tiered network model and the reliability evaluation model of wireless channel are quoted from the existing work in [17]. In the two-tiered network model, S and R represent the sets of SNs and candidate positions for relay node in three-dimensional deployment space, respectively. The amount of elements in S and R is n and m, respectively. Each element in S and R is assigned with a unique number i (1 ≤ i ≤ n) and j (1 ≤ j ≤ m), respectively. In this paper, a relay node at location j will be interchangeably referred to ‘‘a RN at location j’’ or ‘‘RN j’’. All SNs in the data-acquisition layer and the sink node in the data-forwarding layer are distributed in the three-dimensional deployment space based on the application requirements, and their locations are known. The elements in R are selected from the discretized deployable area in deployment space.

The discretization approach of three-dimensional deployment space with electromagnetic obstacle is similar to that in [17], where the two-dimensional rectangle grid based discretization is implemented on deployable area under the control of the grid element scale, saying E_length. However, in this paper, the center of each grid element represents the location of a candidate deployable position of relay node, and all the centers form the candidate location set R for RNs. SNs and sink node with known locations are also located in such grid cells. For consistency, their centers are used to represent the locations of SNs and sink node.

The reliability evaluation model is used to estimate the likelihood of communication success over a channel between different network nodes, and the results are stored in P and Q. The element in Q can be calculated as follows:

$$ q_{j,k} = \left\{ {\begin{array}{*{20}l} {1,} \hfill & {if\,d_{{j,k \in L_{j} }} \le d_{0} ||d_{{j,k \in NL_{j} }} \le d_{0} \cdot \xi } \hfill \\ {1 - \left( {\frac{{d_{j,k} }}{{d_{max} }}} \right)^{r} ,} \hfill & {if\,d_{0} \le d_{{j,k \in L_{j} }} \le d_{max} } \hfill \\ {1 - \left( {\frac{{d_{j,k} }}{{d_{max} \cdot \xi }}} \right)^{r} , } \hfill & {if\,d_{0} \cdot \xi \le d_{{j,k \in NL_{j} }} \le d_{max} \cdot \xi } \hfill \\ {0,} \hfill & {others} \hfill \\ \end{array} } \right. $$
(1)

where j ≠ k, 1 ≤ j ≤ m, 1 ≤ k ≤ m + 1. d0 is the maximum distance that the free-space path loss can be applied. In line of sight (LOS), any pair of nodes with a distance less than d0 can communicate with absolute reliability. Lj is the set of relay nodes or sink node lying in LOS of relay node j. NLj is the set of relay nodes or sink node lying in non-LOS of relay node j. ξ is a reduction factor in [0,1], and represents the attenuation effect of electromagnetic obstacle on communication.

The calculation of element pij in P is similar to formula (1), but the related parameters should be changed, such as using smax instead of dmax. Besides, the selection process of R and the calculation of P and Q are independent of the ILP-based model, and the S, R, P and Q will be the input of the ILP-based model.

4.2 Shortest Path Search Based Extraction of Deployment Space

Generally, the ILP based optimization result can be improved with small grid element scale. However, this can increase the problem scale and lead to unacceptable solution time [12, 17]. The spanning tree and the Steiner tree based extraction methods have been involved to reduce the complexity in unconstrained deployment space [11, 16]. However, these methods will fail in the constrained deployment space with electromagnetic obstacle. The shortest path search can realize the feasible path discovery and has many effective researches, such as the Dijkstra, dynamic programming based methods and machine learning based methods [23, 28, 32, 33]. So far, the new shortest path search methods, especially the machine learning based new methods, are still highly viewed in many fields, such as the path planning for unmanned systems and mobile WSN [34]. All the above methods can be applied to the extraction of deployment space for a WSN in this paper, but are not limited to these.

In this paper, a shortest accessible path is explored from each sensor node to sink node by Dijkstra algorithm, and the Euclidean distance is used to calculate routing cost [28]. Finally, all candidate positions in the shortest accessible paths between SNs and sink node form an extraction set to replace the original grid set R. Considering that the elements in the extraction set account for a small part of R, this substitution can greatly reduce the computational complexity for solving the constrained RND. Besides, this substitution can retain acceptable calculation accuracy, and this will be verified in subsequent sections.

The shortest path search based extraction of deployment space is independent of the ILP-based model. The progressive complexity of the Dijkstra algorithm is still O(m2), where m represents the size of the candidate positions set R [28]. Considering the efficiency and robustness of Dijkstra algorithm, the shortest path search method will not become an efficiency bottleneck when solving the constrained RND problems.

4.3 Energy Consumption Model Considering the Retransmission Mechanism

In practice, WSN protocols use retransmission mechanism to improve the network reliability when data transmission failures, and further set an upper limit for the retransmissions (the rs in this paper) to prevent flooding of data transmission in nodes [26, 27]. Therefore, the energy consumption Ej of relay node j should contain the energy consumed by sending and receiving data multiple times for retransmission. Two cases can trigger the retransmission mechanism: (a) the receiving node cannot receive data; (b) the receiving node can receive data, but the sending node cannot receive an acknowledgement message from the receiving node. In the case of transmission failure, it is difficult to find its triggering mechanism, and then calculate whether the receiving node has generated additional energy consumption. Hence, it is assumed that the retransmission mechanism has no effect on the energy consumption of data reception, and will only increase the energy consumption for sending data due to multiple transmissions. Another important basis of this assumption is that wireless nodes consume more energy to send data than to receive the same data [35]. The P and Q store the communication reliability of all candidate wireless channels in the network. Statistically, the reciprocal of each element in P and Q represents the required number of transmissions before communication success in the corresponding wireless channel. Therefore, the amplification impact tdj,k of the retransmission mechanism on the energy consumption of wireless communication between relay node j and other relay node k or sink node is as follow:

$$ td_{j,k} = \left\{ {\begin{array}{*{20}l} {rs,} \hfill & {if\,\frac{1}{{q_{j,k} }} \ge rs || q_{j,k} \le 0} \hfill \\ {\frac{1}{{q_{j,k} }},} \hfill & {if\,\frac{1}{{q_{j,k} }} < rs} \hfill \\ \end{array} } \right. $$
(2)

The reciprocal of qjk represents the number of retransmissions from node j to node k in a statistical sense, and the tdj,k has two calculation model based on the value of qjk. Therefore, the amount of data transmitted by relay node j to other relay nodes or sink node in each round is as follow:

$$ TT_{j} = \mathop \sum \limits_{k = 1}^{m + 1} F_{j,k} \cdot td_{j,k} $$
(3)

Then, the energy Gj consumed by the amplifier amplifier of relay node j when sending data to the next node in its path to the sink node is as follow:

$$ G_{j} = \beta \mathop \sum \limits_{k = 1}^{m + 1} F_{j,k} \cdot td_{j,k} \cdot \left( {d_{j,k} } \right)^{r} $$
(4)

Finally, the energy Ej consumed by relay node j in each round is as follow [12]:

$$ E_{j} = \alpha_{1} \cdot \left( {R_{j} + w_{j} } \right) + \alpha_{2} \cdot TT_{j} + G_{j} $$
(5)

4.4 ILP-Based Formulation

The ILP-based formulation optimizing the number, location and lifetime of deployed RNs with the constraints of specific network survivability and reliability is proposed in this section. The objective function is as follow:

$$ {\mathbf{Minimize}}{ }\mathop \sum \limits_{j = 1}^{m} Y_{j} + \frac{{E_{max} }}{{E_{limit} }} $$
(6)

where the amount of RNs used in the data-forwarding layer of network is:

$$ \mathop \sum \limits_{j = 1}^{m} Y_{j} $$
(7)

The weight coefficient of the maximum energy consumption among all RNs is:

$$ \frac{{E_{max} }}{{E_{limit} }} $$
(8)

Subject to:

  1. (a)

    A relay node j can be used as the cluster head (primary or back-up) of the sensor node i, only if the reliability between i and j is greater than the reliability threshold pmin.

    $$ p_{i,j} \ge X_{i,j} \cdot p_{min} , \forall i,1 \le i \le n,\forall j,1 \le j \le m + 1 $$
    (9)
    $$ p_{i,j} \ge Z_{i,j} \cdot p_{min} , \forall i,1 \le i \le n,\forall j,1 \le j \le m + 1 $$
    (10)
  2. (b)

    A relay node j is included in the data-forwarding layer, if it is used as either a primary or a back-up cluster head by at least one sensor node i.

    $$ Y_{j} \ge X_{i,j} , \forall i,1 \le i \le n,\forall j,1 \le j \le m + 1 $$
    (11)
    $$ Y_{j} \ge Z_{i,j} , \forall i,1 \le i \le n,\forall j,1 \le j \le m + 1 $$
    (12)
  3. (c)

    A sensor node i can only communicate with one relay node, which is its primary cluster head.

    $$ \mathop \sum \limits_{j = 1}^{m + 1} X_{i,j} = 1, \forall i,1 \le i \le n $$
    (13)
  4. (d)

    For each sensor node i, its primary cluster head is distinct from its back-up cluster head(s).

    $$ X_{i,j} + Z_{i,j} \le 1, \forall i,1 \le i \le n,\forall j,1 \le j \le m $$
    (14)
  5. (e)

    Survivability-related calculations and constraints.

A sensor node must be covered by at least ks-1 back-up cluster heads.

$$ \mathop \sum \limits_{j = 1}^{m} Z_{i,j} \ge k_{s} - 1, \forall i,1 \le i \le n $$
(15)

If the communication reliability between relay node j and relay node k is greater than the reliability threshold qmin, the relay node k can help transmit the data of relay node j to the sink node. Then, the number of other relay nodes that the relay node j can use to route data towards the sink node is calculated as follow.

$$ C_{j} = \mathop \sum \limits_{{q_{j,k} \ge q_{min} }} Y_{k} ,\forall j,1 \le j \le m, j \ne k $$
(16)

If the communication reliability between a relay node j and the sink node is smaller than the reliability threshold qmin, there must be kr other relay nodes that j can forward its data.

$$ C_{j} \ge Y_{j} \cdot k_{r} , if \; q_{j,k} < q_{min} ,\forall j,1 \le j \le m $$
(17)
  1. (f)

    Flow-related calculations and constraints.

A relay node j cannot communicate with other relay node k, if the communication reliability between j and k is littler than the reliability threshold qmin.

$$ F_{j,k} = 0, if\; q_{j,k} \le q_{min} , j \ne k, \forall j,1 \le j \le m,\forall k,1 \le k \le m + 1 $$
(18)
$$ FF_{j,k} = 0, if\; q_{j,k} \le q_{min} , j \ne k, \forall j,1 \le j \le m,\forall k,1 \le k \le m + 1 $$
(19)

The total number of data received by relay node j from sensor node(s) is calculated as follow.

$$ w_{j} = \mathop \sum \limits_{i = 1}^{n} b_{i} \cdot X_{i,j} , \forall j,1 \le j \le m $$
(20)

The total number of data received by relay node j from other relay node(s) is calculated as follow.

$$ R_{j} = \mathop \sum \limits_{k = 1}^{m} F_{k,j} , \forall j,1 \le j \le m,k \ne j $$
(21)

The total number of data transmitted by relay node j (without retransmission mechanism) is calculated as follow.

$$ T_{j} = \mathop \sum \limits_{k = 1}^{m} F_{j,k} ,\forall j,1 \le j \le m,k \ne j $$
(22)

The amount of received data equals to the amount of transmitted data for a relay node.

$$ w_{j} + R_{j} = T_{j} ,\forall j,1 \le j \le m $$
(23)

The total number of data transmitted by relay node j considering retransmission mechanism is shown in formula (3).

The data flow from relay node j to other relay node k or sink node can be non-zero, only if the relay node k or sink node is included in the data-forwarding layer.

$$ F_{j,k} \le D_{limit} Y_{k} , j \ne k, \forall j,1 \le j \le m,\forall k,1 \le k \le m + 1 $$
(24)
$$ F_{j,k} \le D_{limit} FF_{j,k} , j \ne k, \forall j,1 \le j \le m,\forall k,1 \le k \le m + 1 $$
(25)
$$ F_{j,k} \le FF_{j,k} , j \ne k, \forall j,1 \le j \le m,\forall k,1 \le k \le m + 1 $$
(26)

The data flow between relay node j and other relay node k or sink node is unidirectional.

$$ FF_{j,k} + FF_{k,j} \le 1, j \ne k, \forall j,1 \le j \le m,\forall k,1 \le k \le m + 1 $$
(27)
  1. (g)

    Lifetime-related calculations and constraints.

The amount of energy Gj consumed by the amplifier in relay node j to send its data to the next node in its path to the sink node is shown in formula (4).

The amount of energy consumed by relay node j in each round Ej is shown in formula (5).

The energy consumption of relay node j cannot exceed the upper limit Elimit.

$$ E_{j} \le E_{limit} , \forall j,1 \le j \le m $$
(28)

The energy consumption of relay node j is not greater than Emax.

$$ E_{j} \le E_{max} , \forall j,1 \le j \le m $$
(29)

The maximum energy consumption of RNs cannot exceed the upper limit Elimit.

$$ E_{max} \le E_{limit} $$
(30)

4.5 Justification of the MILP Equations

The formula (7) is used to minimize the deployed RNs in the data-forwarding layer. When a candidate position j in R is used to deploy a relay node, Yj = 1, otherwise, Yj = 0. The formula (8) is used to minimize the maximum energy consumption among all deployed RNs. In addition, Emax ≤ Elimit always holds, and hence the result of formula (8) is a continuous variable within [0,1]. This design ensures that the value of formula (8) does not affect the minimization of the number of deployed RNs. Therefore, the objective function (6) can simultaneously minimize the maximum energy consumption of deployed RNs based on the solutions with minimum deployed RNs.

The formulas (9)–(14) set some basic network connection constraints, and the formulas (15)–(17) set the survivability-related calculations and constraints, and the formulas (3) and (18)–(27) set the flow-related calculations and constraints. These constraints are similar to the description in [12, 17], but there are two differences: (a) in this paper, the restriction that the distance from the data-forwarding node(s) of a relay node j to the sink node (base station in [12]) must be shorter than the distance from relay node j to the sink node is not involved when calculating Cj by formula (16). This considers the impact of electromagnetic obstacle on network deployment. As shown in Fig. 1a, if this restriction is involved, the path search will fails at the beginning because all candidate positions (P1–P5) surrounding SN have more long distance to the sink than the distance from SN to sink. (b) the constraint (27) is not involved in the existing work [17], and this constraint can prevents the bidirectional data flow on the same channel in the solution result.

The formulas (4)–(5) and (28)–(30) set the lifetime-related calculations and constraints. The first two constraints are described in Sect. 3.4. In constraint (28), the limit of energy consumption of a relay node j is set to Elimit. The Emax is a variable that stores the maximum energy consumption among all relay nodes. Therefore, as shown in constraint (29), the energy consumption of any relay node is no more than Emax. Furthermore, as shown in constraint (30), Emax has the same limit (Elimit) with other relay nodes. By minimizing the objective function (6), Emax in the solution must be the maximum energy consumption among all deployed relay nodes.

5 Simulation Results

A simulation scene is set up as shown in Fig. 1a, which contains four walls (left, right, front and back wall), ground surface and an electromagnetic obstacle surface. In Fig. 1b, it is the expanded view of the simulation scene, when the E_length is 35 m. All sensor nodes and sink node should be placed on the ground, where the sensor nodes are randomly distributed at the candidate positions, and the sink node is fixed at the square element closest to origin. Besides, the remaining candidate positions on the ground and four walls can be used to deploy relay nodes. The simulations are to find a deployment solution with optimized number and positions of relay nodes, and optimized network lifetime under the constraints of specific network survivability and reliability.

Fig. 1
figure 1

An illustration of the simulation scene

Full size image

The parameters are initialized as follows:

  1. (a)

    The communication-related initialization.

smax = 100 and dmax = 200, where the sensor nodes have shorter communication distance than the relay nodes to save power.

d0 = 20 m and ξ = 0.1, which consider that the electromagnetic obstacles made of metal (common in industrial and urban scenes) have a serious attenuation effect on the wireless communication.

bi = 16 bits, that is, the data produced by a sensor node is the same in each round.

$$ D_{limit} = \mathop \sum \limits_{i = 1}^{n} b_{i} . $$

rs = 3, as in [26] and [27], the maximum number of retransmissions on any channel is 3.

  1. (b)

    The energy-related initialization.

a1 = a2 = 50 nJ/bit, β = 0.1 nJ/bit/m2, r = 2, and the initial energy of each relay node is 5 J as in [12] and [17].

In the simulations, the influence of different parameters on the number of deployed RNs and network lifetime are analyzed, and the simulation results are compared with two excellent existing approaches to verify the practical value of the proposed strategy. The two existing approaches are: (a) the deployment strategy in [12] optimizing the number of deployed relay nodes under multi constraints (DSN). (b) the deployment strategy in [17] optimizing the number of deployed relay nodes and network reliability under multi constraints (DSNR). Furthermore, the proposed deployment strategy optimizing the number of deployed relay nodes and network lifetime under multi constraints is abbreviated as DSNL. It should be pointed out that both the DSN and DSNR do not involve an effective extraction method for constrained three-dimensional deployment space. Therefore, these three approaches will share the candidate position set of relay nodes R and the calculation method for energy consumption in this paper. All solutions are carried out on a DELL OPTIPLEX 9020 computer using Matlab R2013a and Lingo 12.0, where the Matlab R2013a is used to generate the initialized parameters, such as S, R, P, Q, dij and tdj,k, and the Lingo 12.0 is used to find an optimized solution under the multi constraints (1)–(30).

5.1 Impact of the Constraints of Energy and Reliability

In this section, the impact of the energy and reliability constraints is analyzed, and the performance of DSNL is compared with that of DSN and DSNR. The reliability threshold pmin, qmin and the upper limit of energy consumption for relay node Elimit are changed to analyze this impact, and both ks and kr are set to 1 without considering the network survivability. The lifetime in rounds is calculated by 5 J/Emax. The candidate position set R for relay node is formed by discretizing the simulation scene with E_length = 35 m (as shown in Fig. 1), and 10 sensor nodes are randomly deployed in the simulation scene, and the locations of these 10 sensor nodes are known and fixed in all simulations. All results are calculated from the same simulation scene. The reason for selecting E_length = 35 m will be detailed later.

The network lifetime achieved by the three approaches is shown in Fig. 2, where the reliability threshold pmin and qmin are equally set to 0.3, 0.5 and 0.7 in Fig. 2a–c, respectively. Correspondingly, the number of deployed relay nodes in these solutions is shown in Fig. 3, where the results of DSN, DSNR and DSNL are shown in Fig. 3a–c, respectively. Basically, both the lifetime and the number of deployed relay nodes decrease with the increase of Elimit. With different pmin, qmin and Elimit, the proposed DSNL approach can always achieve the best lifetime while using the least deployed relay nodes. By comparing the results of DSN and DSNL, it is shown that the number of deployed relay nodes used by the two approaches is always equal. This indicates that the objective function of the proposed DSNL can optimize the network energy consumption (lifetime) based on the optimization of the number of deployed relay nodes. In contrast, the DSNR approach uses more relay nodes compared with DSN and DSNL when pmin = qmin = 0.3 and Elimit = 100,000 nJ. This result indicates that the objective function of the DSNR approach cannot minimize the number of deployed relay nodes while optimizing the network reliability.

Fig. 2
figure 2

The impact of the multi constraints on lifetime

Full size image
Fig. 3
figure 3

The impact of the multi constraints on deployed relay nodes

Full size image

To analyze the algorithm efficiency, the comparison of solution time for the three approaches is shown in Fig. 4, where the reliability threshold pmin and qmin are equally set to 0.3, 0.5 and 0.7 in Fig. 4a–c, respectively. Basically, the solution time decreases with the increase of Elimit, and it increases with the increase of the reliability threshold pmin and qmin. The proposed DSNL approach always consumes the most solution time. Especially, the solution time of DSN, DSNR and DSNL is 2 h, 9 h and 51 h separately when pmin = qmin = 0.7 and Elimit = 50000nJ. This is still a simple scenario with a small number of nodes. When facing large-scale RND problems, these approaches will consume unacceptable time, and it is important to use the shortest path search based methods to extract the solution space for reducing the solution complexity. As a result, E_length = 35 m, forming a simple scenario with a small number of nodes, is adopted in this section to reduce the solution time while presenting the problem.

Fig. 4
figure 4

The impact of the multi constraints on solution time

Full size image

The unreliability, that is the unreliability levels for the sensor-relay channels and the relay-relay channels in [17], is an important part of the objective function of DSNR, and can optimize the network reliability by minimizing the unreliability. As shown in Fig. 5, the DSNR can always achieve the least unreliability, and the proposed DSNL cannot clearly optimize the network reliability. As a result, the proposed DSNL approach is not recommended for optimizing network reliability when solving the RND problems.

Fig. 5
figure 5

The impact of the multi constraints on network unreliablity

Full size image

5.2 Impact of the Amount of Candidate Positions for Relay Node

Considering the efficiency bottleneck of these three approaches in solving large-scale RND problems, the shortest path search approach is involved to reasonably extract the discrete deployment space, and then is used to form the candidate positions for relay node R. With different E_length, the amount of candidate positions in R changes. Therefore, the efficiency and accuracy of the proposed DSNL are analyzed with different R. Besides, in order to maintain the comparability of the simulation results, 10 sensors are still randomly deployed in this section, and both ks and kr are set to 1 without considering the network survivability.

The amount of candidate positions in R is shown in Fig. 6a, and the extraction rate, that is the ratio between the amount of candidate positions in R after extraction and the amount of candidate positions in R before extraction, is shown in Fig. 6b. When E_length = 35 m without extraction, the amount of candidate positions in R equals to the amount of candidate positions for relay node in the discrete space, and hence the extraction rate is 1. When involving extraction, the amount of candidate positions in R is 10, 15 and 32, and the corresponding extraction rate is 0.164, 0.116 and 0.05 while E_length = 35 m, 23 m and 11 m, separately. It is clear that the amount of candidate positions in R increases with the decrease of E_length, and the extraction rate decreases with the decrease of E_length. In other words, the extraction approach effectively reduces the complexity of the search space of RND problem.

Fig. 6
figure 6

The illustration of the amount of candidate positions in R

Full size image

The effect of the amount of candidate positions for relay node on algorithm performance is shown in Fig. 7, where the impact on lifetime and deployed relay nodes of the proposed DSNL approach is analyzed when pmin = qmin = 0.3. When E_length = 35 m, the result using extraction achieves more long lifetime at the cost of more deployed relay nodes compared with the result without extraction. Furthermore, the solution time of the result using extraction is reduced to several minutes while the solution time of the result without extraction is several hours as shown in Fig. 4a. Compared with the result when E_length = 35 m and without extraction, the result of E_length = 23 m and using extraction uses the same number of relay node, and achieves more long lifetime. Compared with the result when E_length = 35 m and without extraction, the result of E_length = 11 m and using extraction uses a slightly more number of relay node, and achieves the best lifetime. These results indicate that a reasonable setting for E_length can optimize both the network lifetime and the number of deployed relay nodes when using the proposed extraction method. Besides, the solution time of all results with extraction is in several minutes. Therefore, the proposed efficient multi-constraint deployment strategy can greatly ease the efficiency bottleneck while maintaining or even improving the algorithm performance.

Fig. 7
figure 7

The effect of the amount of candidate positions for relay node on algorithm performance

Full size image

5.3 Performance Comparison with Existing Approaches

In this section, two large-scale network containing 30 and 50 sensors respectively are used to analyze the performance of the proposed DSNL approach compared with the exiting work. Besides, the impact of the energy and survivability constraints is involved. In all simulations, the extraction method based on shortest path search, pmin = qmin = 0.1 and E_length = 11 m are adopted.

As shown in Figs. 8 and 9, both the lifetime and the number of deployed relay nodes decrease with the increase of Elimit, and the number of deployed relay nodes achieved by DSN and DSNL is always equal, and the DSNR approach tends to use more relay nodes, and the lifetime achieved by the proposed DSNL approach is always the best. These results are consistent with the conclusions in the Sect. 4.1. Furthermore, when involving survivability requirement for the RND problem (both ks and kr are set to 2), all the DSN, DSNR and DSNL approaches tend to use more relay nodes. However, as shown in Fig. 9b and d, the DSNR approach use the same number of relay nodes to solve the two RND problems with and without survivability constraint. This indicates that although the survivability constraint tend to deploy more relay nodes, exceptions may also occur, such as, in node-intensive deployment applications, nodes can maintain communication with each other, and then no additional nodes need to be deployed to meet the survivability constraint.

Fig. 8
figure 8

The performance comparison with existing approaches when n = 30

Full size image
Fig. 9
figure 9

The performance comparison with existing approaches when n = 50

Full size image

It is found that all the approaches involved in the simulations tend to fail when setting a high reliability constraint, such as pmin = qmin = 0.7 and using the proposed extraction approach to form R. This phenomenon can be explained as follow: when the algorithm search space R is obtained by the extraction method, the selectivity of the deployed nodes is reduced under the premise that the number of deployed nodes is minimized, and then the communication reliability between the nodes in the solution result is limited. This also further indicates that the proposed efficient multi-constraint deployment strategy is not recommended for optimizing network reliability when solving the RND problems.

6 Conclusions

An efficient multi-constraint deployment strategy is proposed in this paper, and it covers (a) extraction of three-dimensional discrete deployment space with shortest path search, (b) reliability evaluation of wireless channel in three-dimensional environment with electromagnetic obstacle, (c) energy consumption model for wireless communication under retransmission mechanism, (d) integer linear program-based formulation optimizing the amount, locations and lifetime of relay nodes under the constraints of network survivability and reliability. The comparative simulation results with existing advanced methods indicate that the proposed strategy can reduce the solution time to minutes while the solution time of the existing advanced methods is in hours when deploying dozens of sensors, and the result of the proposed strategy can use the same number or slightly more relay nodes to achieve the best network lifetime, but the proposed strategy is not recommended for optimizing the network reliability. Therefore, the proposed strategy can greatly ease the efficiency bottleneck while maintaining or even improving the algorithm performance. In future, the optimization of RND problem based on ILP approach can be further improved under multi constraints of lifetime, survivability, delay and reliability, and new shortest path search methods should be involved in the proposed approach to evaluate its effectiveness in complicate scenes with multiple obstacles.