Keywords

1 Introduction

For large scale wireless sensor networks (WSNs), hierarchical structures are typically preferred due to the strong scalability and stability [1, 2]. A hierarchical WSN generally includes convergence nodes (CNs) and sensing nodes (SNs). An SN is mainly responsible for collecting information, and then forwarding it to the associated convergence node. And a CN collects data from the associated SNs and delivers them to servers. Typically, SNs are powered by batteries and it is not practical to replace or recharge them. While CNs are much less in number compared to SNs and typically have stable power supplies.

The deployment of CNs plays an important role in the performance of hierarchical WSNs and has aroused great interests. Reference [3] studied the deployment of heterogeneous wireless directional sensor networks in a three-dimensional intelligent city. A new distributed parallel multi-objective evolutionary algorithm was proposed to optimize the coverage, connectivity quality, lifetime, connectivity and reliability. In [4], the deployment of sensor nodes and relay nodes in industrial environments is studied with the objectives of optimizing the security, lifetime and coverage. In [5], a WSN is applied to air pollution mapping, which solves the optimization problem of sensor deployment. On the premise of ensuring network connectivity and considering node perception error, two kinds of air pollution map layout models are derived by using the integer linear programming method. Reference [6] proposed a distributed parallel coevolutionary multi-objective large-scale evolutionary algorithm to optimize the WSN deployment in the three-dimensional (3D) cabin space of a super large crude oil carrier to improve the coverage, network lifetime and reliability. In [7], a real coverage model of 3D environment based on Bresenham line of sight is proposed, and multi-objective genetic algorithm is used to solve the problem with the number and location of sensors as the target.

In this paper, we aim to optimize the deployment of CNs for the hierarchical WSN where the locations of SNs are determined due to the explicit requirements of the monitoring area. The goal is to make the total Tx power of the sensing layer node as low as possible, or make the Tx power of the sensing layer node as balanced as possible. Studies in [8] and [9] also investigated the optimal deployment of CNs in hierarchical clustering WSNs, however, the objective was to achieve the full coverage of SNs with the lowest total power of CNs, but not SNs. It makes more sense to lower the power consumption of SNs rather than CNs since it is the SNs rather than CNs that are power constrained.

The above optimization problems are both non-convex and NP-hard, so it is difficult to obtain analytical solutions by using classical optimization theory. Therefore, this paper introduces a state-of-the-art swarm intelligence optimization algorithm (SIOA): slime mould algorithm (SMA) [10] to search for the approximate optimal solutions of the optimization problems. SIOAs have been proved to be highly effective in solving complicated optimization problems [11,12,13]. Moreover, this paper fully considers the non-uniformity of the actual deployment environment, that is, there are various obstacles within the deployment environment, which cause different degrees of attenuation to the wireless signals. It should be noted that although we only concern two-dimensional deployment scenarios in this work, it is straightforward to extend the proposed scheme to 3D scenarios by adding the value of z-axis as an additional decision variable.

The performance of the SMA-based optimized deployment mechanism are verified by sufficient simulations. The simulation results show that, compared with the traditional uniform distribution wireless sensor model, the SMA-based optimal convergence layer deployment scheme can significantly reduce the total transmission power of the sensing layer nodes and balance the energy consumption among sensing layer nodes on the premise that all sensing layer nodes are covered by the signal.

The rest of this paper is organized as follows: Sect. 1 introduces the system model of wireless sensor network and the mathematical model of the optimization problem. Section 2 describes the detailed process of SMA based hierarchical wireless sensor network aggregation layer topology optimization mechanism. Section 3 describes the simulation experiment and gives the optimized results. Finally, Sect. 4 summarizes the paper.

2 System Model

Consider a hierarchical WSN deployed in the two-dimensional area M which is divided into two layers, namely the sensing layer and the convergence layer. We assume that there are \(N_{s}\) sensing nodes (SNs) in the sensing layer, denoted as \(\mathbb {S}=\left\{ {\mathrm {SN}}_{1},{\mathrm {SN}}_{2},\ldots ,{\mathrm {SN}}_{N_s}\right\} \) and \(N_c \left\{ N_{c}\ll N_{s} \right\} \) convergence nodes (CNs) in the convergence layer, denoted as \(\mathbb {C}=\left\{ {\mathrm {CN}}_{1},{\mathrm {CN}}_{2},\ldots ,{\mathrm {CN}}_{N_c} \right\} \). Each CN associates with at least one SN while each SN can be associated to only one CN.

We divide the two-dimensional area M into m\(\times \)m grids. Each grid is covered by one SN, that is, \(N_{s} =m^{2} \). It is assumed that each SN is located in the center of the small square. The position of \({\mathrm {SN}}_{i}\left( i=1,2,\cdots ,N_{s} \right) \) is denoted as \(L_{{\mathrm {SN}}_{i}}=\left( x_{{\mathrm {SN}}_{i}}, y_{{\mathrm {SN}}_{i}}\right) \), and its Tx power is denoted as \(p_{i}\left( p_{\min } \le p_{i} \le p_{\max }\right) \). The position of \({\mathrm {CN}}_{j}\left( j=1,2, \ldots , N_c\right) \) is \(L_{{\mathrm {CN}}_{j}}=\left( x_{{\mathrm {CN}}_{j}}, y_{{\mathrm {CN}}_{j}}\right) \). The receiving sensitivity of a CN is \(p_{0}\). Meanwhile, we assume that each wireless link between a SN and a CN is bidirectional under the same transmission power, that is, as long as the signal of \({\mathrm {SN}}_{i}\) can effectively cover \({\mathrm {CN}}_{j}\) , the signal of \({\mathrm {CN}}_{j}\) can also effectively cover \({\mathrm {SN}}_{i}\).

In this paper, the propagation attenuation of wireless signal from \({\mathrm {SN}}_{i}\) to \({\mathrm {CN}}_{j}\) is modeled as \( \alpha =\beta _{0}+10 \gamma \lg \frac{d_{i, j}}{d_{0}}+\beta _{1}, \) where \(\gamma \) represents the attenuation factor, which depends on the surrounding environment; \(\beta _{0}\) represents the attenuation of its signal caused by obstacles; \(d_{0}\) is the reference distance; \(\beta _{1}\) is the received power of \(d_{0}\) at the reference distance; \(d_{i, j}=\sqrt{\left( x_{{\mathrm {SN}}_{i}}-x_{{\mathrm {CN}}_{j}}\right) ^{2}+\left( y_{{\mathrm {SN}}_{i}}-y_{{\mathrm {CN}}_{j}}\right) ^{2}}\) is the distance from \({\mathrm {SN}}_{i}\) to \({\mathrm {CN}}_{j}\).

In order to better simulate the real environment, the target area M is set as a non-uniform environment, that is, there are various obstacles within M. These obstacles cause addition attenuation. If the line from \({\mathrm {SN}}_{i}\) to \({\mathrm {CN}}_{j}\), denoted as \(L_{i,j}\) passes through an obstacle, the attenuation caused by this obstacle is then taken into account.

The Boolean expression to judge whether \({\mathrm {SN}}_{i}\) is effectively covered by \({\mathrm {CN}}_{j}\) is as follows:

$$\begin{aligned} C\left( {\mathrm {SN}}_{i}, {\mathrm {CN}}_{j}\right) =\left\{ \begin{array}{ll}1, &{} \text{ if } p_{i}-\alpha \ge p_{0} \\ 0, &{} \text{ otherwise } \end{array}\right. \end{aligned}$$
(1)

Consequently, the indicator that whether \({\mathrm {SN}}_{i}\) is covered by at least one CN can be defined as \( C\left( {\mathrm {SN}}_{i}\right) =1-\prod _{{\mathrm {CN}}_{j} \in G}\left[ 1-C\left( {\mathrm {SN}}_{i}, {\mathrm {CN}}_{j}\right) \right] , \) and the coverage rate of the sensing nodes can be expressed as \( E(S, G)=\frac{1}{N_s} \sum _{{\mathrm {SN}}_{i} \in S} C\left( {\mathrm {SN}}_{i}\right) . \)

We use the variance to evaluate the energy consumption balance among sensing nodes, which is calculated as \( \sigma =\frac{1}{N_s} \sum _{{\mathrm {SN}}_{i} \in S}\left( p_{i}-\bar{p}\right) ^{2}, \) where \(\bar{p}=\frac{1}{N_s} \sum _{{\mathrm {SN}}_{i} \in S} p_{i}\) represents the average power of the sensing nodes.

The optimization problem in this paper is to optimize the locations of the convergence nodes on the premise of ensuring the full coverage of the sensing nodes, so that 1) the total transmission power of the sensing nodes can be minimized, and 2) the transmission power can be balanced as far as possible. Therefore, the mathematical model of the optimization problem is defined as follows:

$$\begin{aligned} \begin{aligned}&OP1:{\min \limits _{\mathbf {L}_{CN}}}\left( {\sum \nolimits _{S{N_i} \in S} {{p_i}} } \right) \\&OP2:{\min \limits _{\mathbf {L}_{CN}}}\sigma \\ {\text {s.t.}}~&{E}\left( {S,G} \right) = 1 \end{aligned}\ \end{aligned}$$
(2)

where \(\mathbf {L}_{\text {CN}}=\left\{ \left( x_{{\mathrm {CN}}_{1}}, y_{{\mathrm {CN}}_{1}}\right) ,\left( x_{{\mathrm {CN}}_{2}}, y_{{\mathrm {CN}}_{2}}\right) , \cdots ,\left( x_{{\mathrm {CN}}_{N_{c}}}, y_{{\mathrm {CN}}_{N_{c}}}\right) \right\} \) is the location vector for convergence nodes, the constraint is the full coverage requirement.

3 SMA Based Optimal Deployment Scheme

The location vector of CNs (\(\mathbf {L}_{\text {CN}}\)) is mapped to the position of a slime mould in the super dimensional space. That is, each individual in the swarm represents a candidate solution of (2). Slime moulds approach food according to the smell in the air which is interpreted as the fitness in the optimization algorithm. In this paper, the fitness is defined as follows:

$$\begin{aligned} \mathcal {F(\mathbf {L}_{\text {CN}})}=\left\{ \begin{array}{l} \text {OP1}:~\sum _{{\mathrm {SN}}_{i} \in S} p_{i},\\ \text {OP2}:~\sigma . \end{array}\right. \end{aligned}$$
(3)

The approach behavior and contraction mode of the ith slime mould in the swarm in the tth iteration can be modeled as

$$\begin{aligned} \mathbf {L}_{\text {CN}}(t+1, i)=\left\{ \begin{array}{l} r_{0}\left( \mathbf {B}_{u}-\mathbf {B}_{l}\right) +\mathbf {B}_{l}, r_{1}<z \\ \mathbf {L}_{\text {CN}}^{\text{ best } }(t)+\mathbf {v}_{b} \cdot \left( \mathbf {w} \cdot \mathbf {L}_{\text {CN}}^{A}(t)-\mathbf {L}_{\text {CN}}^{B}(t)\right) , r_{1} \ge z, r_{2}<p \\ \mathbf {v}_{c} \cdot \mathbf {L}_{\text {CN}}(t, i), r_{1} \ge z, r_{2} \ge p \end{array}\right. \end{aligned}$$
(4)

The variables and vectors involved in (4) are explained as follows. \(\mathbf {B}_{u}\) and \(\mathbf {B}_{l}\) are upper and lower bound of location coordinates. \(r_{0}\), \(r_{1}\) and \(r_{2}\) are random values within the range of [0, 1]. z is a predefined threshold. \(\left. \mathbf {L}_{\text {CN}}(t, i)\right| _{N_{p} \times 2 N_{c}}\) is the ith individual in the tth iteration and \(N_{p}\) is the population size. \(\mathbf {L}_{\text {CN}}^{\text{ best } }(t)\) is the best individual, that is, the individual achieves the best fitness by the tth iteration. \(\mathbf {V}_{b}\) and \(\mathbf {V}_{c}\) are two random factors where \(\left| \mathbf {v}_{b}\right| \le {\text {arctanh}}\left( -\frac{t}{\max _{t} t}+1\right) \) and \(\left| \mathbf {v}_{c}\right| \le \frac{t}{\max _{t} t}\), respectively. \(t=1,2,\ldots , {\text {iter}}_{\max }\) is the current iteration and \(\mathbf {L}_{\text {CN}}^{\mathrm {A}}(t)\) and \(\mathbf {L}_{\text {CN}}^{\mathrm {B}}(t)\) represent two individuals randomly selected from the swarm. p can be calculated as:

$$\begin{aligned} p=\tanh \left| \mathcal {F}(t, i)-\mathcal {F}_{\text {best}}(t)\right| , i=1,2, \ldots , N_{p} \end{aligned}$$
(5)

where \(\mathcal {F}(t, i)\) returns the fitness of the ih individual in \(\mathbf {L}_{\text {CN}}(t), \mathcal {F}_{\text {best}}(t)=\mathcal {F}\left( \mathbf {L}_{\text {CN}}^{\text{ best } }(t)\right) \). \(\mathbf {w}\) is the fitness weight vector which can be calculated as:

$$\begin{aligned} \overline{\mathbf {w}\left( \mathbf {I}_{\mathcal {F}}(i)\right) }=\left\{ \begin{array}{ll}1+r \cdot \log \left( \frac{\mathcal {F}_{\text {best}}(t)-\mathcal {F}(t,i)}{\mathcal {F}_{\text {best}}(t)-\mathcal {F}_{\text {worst}}(t)}+1\right) , &{} \text{ condition } \\ 1-r \cdot \log \left( \frac{\mathcal {F}_{\text {best}}(t)-\mathcal {F}(t,i)}{\mathcal {F}_{\text {best}}(t)-\mathcal {F}_{\text {worst}}(t)}+1\right) , &{} \text{ others } \end{array}\right. \end{aligned}$$
(6)

where \(r \in [0,1]\) is a random value, the condition indicates that \(\mathcal {F}\left( \mathbf {L}_{\text {CN}}^{i}(t)\right) \) ranks first half of the population, \(\mathcal {F}_{\text {worst}}(t)\) is the worst fitness value obtained in the iterative process currently, \(\mathbf {I}_{\mathcal {F}}\) denotes the sequence of fitness values sorted in ascending order.

The pseudo code of the SMA-based optimal CN deployment scheme is summarized in Algorithm 1.

figure a

4 Simulation Experiment

In this study, a two-dimensional space M of 100 m \(\times \) 100 m is simulated and divided into 20 \(\times \) 20 grids, as shown in Fig. 1(a). One sensing node is placed in the center of each grid. Initially, 36 convergence nodes are evenly placed in the target area (green triangles in Fig. 1(a)). In order to better simulate the heterogeneous environment in real life, we also add some common obstacles in the simulation space. The attenuation introduced by load bearing walls, rick walls and wooden walls is 30 dB, 15 dB and 10 dB respectively. The maximum and minimum powers of sensing layer node are 23.5 dBm and 1 dBm, respectively. The attenuation factor (\(\gamma \)) is 3, the reference distance (\(d_{0}\)) is 1 m.

We assume that each SN knows the location of the associated CN and always adjusts its Tx power to the lowest value which ensures a reliable connection. In the initial layout, the minimum total Tx power of the sensing nodes is 10680.39 mW. The association between the convergence nodes and the sensing nodes is shown in Fig. 1(a). The Tx power of each sensing node is shown in Fig. 1(b). It can be observed that the TX powers of sensing nodes are distributed over a considerable large range. The Tx power variance is 1127.76.

4.1 Optimization on Total Tx Power

Firstly, the deployment of convergence nodes is optimized with the objective of minimizing the total Tx power of sensing nodes by the proposed SMA-based scheme. The population size is 500 and the maximum number of iteration is 2000. The optimization process is shown in Fig. 1(c). It can be seen from the figure that in the first 500 iterations, slime moulds are looking for a higher quality food source, and the total Tx power remains unchanged. With the continuous iteration of the algorithm, it can be seen that the total Tx power of the sensing nodes is significantly reduced. The total Tx power remains stable after about 1800 iterations, with the value of 6032.16 mW. Compared with the total Tx power of 10680.39 mW before optimization, a 43.52% reduction is achieved. The optimized locations of the convergence nodes and the association between the sensing nodes and convergence nodes are shown in Fig. 1(d).

4.2 Optimization on Energy Consumption Balance

Then, we optimize the deployment of the convergence nodes to minimize the variance of the TX powers of the sensing nodes, so that the energy consumption of the sensing nodes can be balanced. The optimization process is shown in Fig. 1(e). Similarly, it can be observed that the variance of the Tx power starts to drop after 500 iterations and remains stable at the value of 166.72 after about 1500 iterations, which is only 14.78% of the original. Figure 1(f) depicts the distribution of the TX powers of the sensing nodes after optimization. Compared with Fig. 1(b), the TX powers is much more balanced at this time. The optimized locations of the convergence nodes and the association between the sensing nodes and convergence nodes are shown in Fig. 1(d).

We further evaluated the survival rate of sensing nodes and the survival time of the WSN. It is assumed that each sensing node has the same total energy \(\left( 1 \times 10^{4} \mathrm {~J}\right) \) and that each sensing node transmits and receives data for a period of 10 ms per second. A sensing node is considered dead if its energy decreases to 0. In addition, the whole WSN is considered dead if 30% of the sensing nodes die.

Figure 1(h) compares the survival rate and the network survival time between the traditional uniform deployment and the optimized one. It can be found that the death rates drop significantly in the optimized deployed WSNs compared with the uniformly deployed WSN. The uniformly deployed WSN stops working (30% of SNs run out of energy) after 307056 s, while as a contrast, only 4% and 1.75% of SNs die in the OP1-optimized scenario (OP1) and the OP2-optimized scenario (OP2) by then, respectively. The OP1-optimized WSN can survive for 892536 s. And the OP2-optimized WSN lives much longer than the other two. It continues working for up to 1020668 s.

Fig. 1.
figure 1

(a) Initial deployment and associations between SNs and CNs, (b) Tx powers of SNs in initial deployment, (c) OP1: Converge curve of the total Tx power of SNs, (d) OP1: Associations between SNs and CNs, (e) OP2: Converge curve of the total Tx power of SNs, (f) OP2: Tx powers of SNs, (g) OP2: Associations between SNs and CNs, (f). Survival rate of SNs.

Full size image

5 Conclusion

In this paper, we propose an optimized convergence node deployment scheme for hierarchical WSNs based on SMA. The objectives are to minimize the total Tx power or balance the power consumption among sensing nodes on the premise of full coverage of the sensing nodes.

Moreover, this paper fully considers various obstacles which introduce additional signal attenuation within the target area. Experimental results show that the optimal deployment scheme can greatly reduce the total energy consumption of the sensing nodes, promote the energy consumption balance among sensing nodes, and prolong the network lifetime.