1 Introduction

In recent years, China’s ecological environment is getting worse with increasing pollution. How to monitor and control environmental pollution effectively has become a top issue the Chinese government and the community concern about. Compared with those traditional methods which are combined with sparse monitoring station and artificial sampling strategy, a large-scale distributed environment monitoring system constructed by Internet of Things (IoT) technology provides a practical solution for environmental monitoring, which has a lot of advantages such as high real-time performance, low cost, simple maintenance and high degree of intelligence [1]. In the area of environmental monitoring Wireless Sensor Networks (WSNs) applications, the sensor localization is one of the important research tasks [1]. The sensed data or the detected events will be meaningless without accurate location information of sensor nodes. Therefore, how to get the location information of sensor nodes in the environment perception is the problem to be solved in this paper.

Due to sensor nodes in WSNs with such characteristics as limited energy, poor reliability, large scale, random distribution, susceptible to interference [2], the localization method about WSNs should satisfy the requirements like self-organizing, robustness, energy efficient, distributed computing and so on [3, 4]. Currently, localization methods for WSNs can be classified into various kinds. Today the most widely used method in outdoor localization is Global Position System (GPS) positioning technology [5,6,7]. Although there are some advantages like high positioning accuracy, good real-time performance and good anti-interference ability about GPS, it is really difficult to equip for each node in resource-constrained large-scale distributed WSNs because of its limitations like high energy consumption, cost and system complexity. Common localization algorithms for WSNs can be divided into range-based localization algorithm and range-free localization algorithm [8]. Range-based localization algorithms (RSSI [9, 10], TOA [11] and TDOA [12], etc.) need to measure the distance or angle among nodes during the process of locating, so that they have a higher requirement on hardware and can be influenced by the measurement environment easily. Range-free localization algorithms mainly include centroid algorithm [13], DV Hop algorithm [14], amorphous algorithm [15], etc. This kind of localization algorithms achieve lower localization accuracy than range-based localization algorithms, but they don’t require to measure the distance or angle among nodes, which can reduce the requirement of hardware, and the influence of environment. To the best of our knowledge, it is difficult to find a universal location algorithm which is suitable for various applications taking into account the large differences among various applications’ background. However, it seems advisable to choose or design an appropriate localization algorithm after considering the network scale, cost and accuracy requirements.

In our previous work [16,17,18], a distributed WSN for online water quality monitoring was designed. Furthermore, a suitable localization algorithm was designed according to the characteristics of environmental monitoring by combining genetic algorithm with GPS in [19]. In that study, accurate position information of beacon nodes is collected by using GPS firstly, and then calculate the positions of the unknown nodes preliminarily using improved genetic algorithm. In another literature about our work [20], an iterative localization algorithm based on minimum condition number is proposed. The presented algorithms in [20] has begun considering the characteristics of environmental monitoring applications, but there are still some following disadvantages. Firstly, the presented algorithms used an iterative method to locate, and the first located nodes will be treated as the temporary beacon nodes, which will result in the accumulation of the positioning error. Secondly, a basic premise of above algorithms is the high connectivity of network, which requires dense node deployment instead of random toss node deployment in reality. Thirdly, considering the characteristics of limited hardware resources in the distributed WSNs, the algorithms seem too complex and difficult to realize. In order to find a solution to above problems, this paper intend to absorb the features and advantages of aforementioned locating algorithms and proposes a WSN localization algorithm based on the improved particle swarm optimization algorithm and adaptive mobile nodes.

The remainder of this paper is organized as follows. Section 2 describes the model we use in this work, including wireless channel model and bacon node deployment model. Section 3 introduces an iterative localization method based on improved PSO algorithm. Section 4 presents a further improved localization method combined with improved PSO algorithm and adaptive mobile node. Section 5 gives some results of simulation experiments and Sect. 6 concludes the paper.

2 Model Description

Assuming that some sensor nodes are deployed in the outdoor environment randomly, those nodes are static and can be classified into two classes, the beacon node and the unknown node. At the same time, a small number of mobile nodes are deployed in such environment. Both beacon nodes and mobile nodes are equipped with GPS devices and solar battery to ensure accurate location and long power duration. S, B, U and M represent the sensing node set, the beacon node set, the unknown node set and the mobile node set respectively. Assuming that every node communication radius is the same, denoted as R, the location of each sensor node \(S_{n} \in S\) is denoted as (xn, yn).

2.1 Wireless Channel Model

In the WSNs mentioned above, each sensor node is equipped with a microcontroller and RF transceiver. When a node receives a wireless signal, the RSSI value of other nodes with the range of the communication radius R can be measured through the radio frequency transceiver. The classic Shadowing model is adopted here following Eq. (1) [21]:

$$p = p_{0} + 10n\log_{10} \left( {\frac{d}{{d_{0} }}} \right) + X_{0}$$
(1)

where d0 is the reference distance; p0 is the received signal strength at distance d0, which contains the loss caused by attenuation or the environment; d is the real distance; X0 is a Shading factor with dB as the unit, whose mean is 0 and mean square error (dB) is a normal random variable; p is the received signal strength at distance d; n is the path loss exponent, whose value depends on the type of environment and building. In actual measurement, X0 has little effect on the results. So that we can get the RSSI simplified ranging formula if d0 = 1 m, as shown in Eq. (2) [22]:

$$RSSI = A - 10n\log_{10} d$$
(2)

where RSSI is the received signal strength when the distance from the transmitting node is d, the unit is dBm; A is the received signal strength when the distance from the transmitting node is 1 m; n is a signal transmission factor, which is related to the propagation environment of the radio signal. Thus, the distance d can be calculated as:

$$d = 10^{{\frac{A - RSSI}{10n}}}$$
(3)

2.2 Beacon Node Deployment

As shown in Fig. 1, BA and BB are two beacon nodes, the unknown nodes are concentrated on one side of the interconnection between BA and BB. After measuring RSSI value, the distance between U1, BA and BB, denoted as dA1, dB1, dAB respectively, can be estimated by Eq. (3).

Fig. 1
figure 1

Location map of two beacon node

Full size image

According to Fig. 1, it is easy to derive Eq. (4) by cosine theorem.

$$\cos \alpha = \frac{{d_{A1}^{2} + d_{AB}^{2} - d_{B1}^{2} }}{{2d_{A1} d_{AB} }}$$
(4)

Then the position of the unknown node U1 can be calculated by Eq. (5).

$$x = d_{A1} \cos \alpha ,y = d_{A1} \sin \alpha$$
(5)

In literature [23], it has been proved that when the distance between the beacon nodes is larger, the influence of ranging error is smaller, it means the distance between the two beacon nodes dAB is larger, and the effect of ΔdAB on cosα is smaller. Intersection area of two communication circle is inversely proportional to the distance between the two beacon nodes dAB. In another hand, the area can be located is smaller when dAB is larger. As a result, the way of taking the value of dAB should be taken into comprehensive consideration.

The applicable precondition of aforementioned two beacon nodes’ localization method is that all unknown nodes must be on the same side of the two beacon nodes’ interconnection. Moreover, taking into account the cumulative error problem caused by the iterative localization method, a new beacon nodes deployment method is proposed in this paper. In the initialization phase, square grid division of the monitoring area is carried out firstly and make sure that all beacon nodes are deployed at the 4 vertices of each square. In Fig. 2, the monitoring area is divided into 4 grids with 9 beacon nodes, which are denoted as grid 1, 2, 3 and 4, respectively. The grid length (i.e. the distance between the two adjacent beacon nodes) is set to node communication radius R, the communication range of each beacon node in grid 1 is shown as an example.

Fig. 2
figure 2

Schematic diagram of grid node deployment

Full size image

According to the number of beacon nodes can be detected by the unknown node, the grid 1 can be divided into three types of region, denoted as I, II and III. The unknown nodes in the region I can detect 4 beacon nodes, 3 beacon nodes by the unknown nodes in the region II, and the unknown nodes in the region III can only detect 2 beacon nodes. Taking into account the distribution of the unknown nodes in the grid and such two important factors as coverage density and connectivity, the monitoring area with grid coverage can be divided into dense distribution grid and sparse distribution grid, which are defined as follows:

Densely distributed grid In such a grid, the coverage density of the unknown nodes is high and there must be a number of unknown nodes distributed in region I or II. If there is an unknown node in region III, that unknown node must be able to detect at least one neighbor nodes in region I or II within its communication range.

Sparsely distributed grid In such a grid, unknown nodes may be distributed in region I and region II and there must appear island node in region III, which is defined that such an unknown node in the region III cannot detect the neighbor nodes in region I or II within its communication range.

There are two classes of unknown nodes in densely distributed grid (grid 1 in Fig. 2, for example) in accordance with the number of detected beacon nodes within their communication range. The first class of those unknown nodes distributed in region I or II, which is able to detect 3 beacon nodes at least. Oppositely, the second class of those unknown nodes distributed in region III, which can only detect less than three beacon nodes. For the first class, the maximum likelihood estimation method is used mostly to solve such multilateral measurement problem. However, due to the fact that the maximum likelihood estimation method is greatly affected by the measurement error, this paper uses an improved particle swarm optimization algorithm to solve an optimization problem which is used to calculate the unknown node’s location.

3 Iterative Localization Method Based on Improved PSO Algorithm

3.1 Improved Particle Swarm Optimization Algorithm

Particle Swarm Optimization (PSO) is a kind of optimization algorithms which is used to simulate the behavior of swarm intelligence. The basic idea of PSO is initializing a group of particles randomly, each particle is considered as a potential optimal solution of the extremum optimization problem, and the characteristics of each particle are represented by its position, speed and fitness. Assuming there is a population X = (X1, X2, …, XN) composed by N particles in a D dimensional space, where the location of i-th particle in the D dimensional space can be expressed as Xi = [xi1, xi2,…, xiD]T. Then the fitness of each particle’s position Xi is calculated according to the objective function. If supposing the velocity of i-th particle is Vi, the individual extremum is Pi, and the population’s global extremum is Pg, it is feasible to adopt Eqs. (6) and (7) in each iteration to update one particle’s velocity and position according to the individual’s extremum Pid and the global extremum Pgd.

$$V_{id}^{k + 1} = \omega V_{id}^{k} + c_{1} r_{1} (P_{id}^{k} - X_{id}^{k} ) + c_{2} r_{2} (P_{gd}^{k} - X_{id}^{k} )$$
(6)
$$X_{id}^{k + 1} = X_{id}^{k} + V_{id}^{k + 1}$$
(7)

where Vid and Xid are speed and position, respectively; \(d \in (1,D)\) is the dimension of space; \(i \in (1,N)\) is the label number of particles; k is the current number of iterations; c1 and c2 are non-negative constants, called learning factors; r1 and r2 are random numbers in the [0,1] uniform distribution; ω is the inertia weight coefficient, which reflects the degree of the particle’s inheritance to the current speed. In [24], Shi firstly introduced the inertia weight coefficient into PSO algorithm and put forward the linear-decreasing inertia weight. He pointed out that larger inertia weight coefficient was conducive to global search, while smaller inertia weight coefficient was more conducive to local search. In order to balance the ability of global searching and local improvement better, the improved particle swarm optimization algorithm adopts the adaptive inertia weight coefficient in Eq. (8):

$$\omega = \left\{ {\begin{array}{*{20}c} {\omega_{\hbox{min} } - \frac{{(\omega_{\hbox{max} } - \omega_{\hbox{min} } )*(f - f_{\hbox{min} } )}}{{f_{avg} - f_{\hbox{min} } }},\quad f \le f_{avg} } \\ {\omega_{\hbox{max} } ,\quad f \ge f_{avg} } \\ \end{array} } \right.$$
(8)

where ωmax and ωmin represent the maximum and minimum values of ω respectively, f represents the current object function value of the particle, favg and fmin represent the average and minimum target value of all current particles respectively.

According to Eq. (8), it is known that the inertia weight coefficient increases when the target value of each particle tends to be consistent or local optimal; otherwise, the inertia weight coefficient decreases when the target value of each particle is relatively dispersed, and inertia weight coefficient is small when target function value is better than average target value, thus retaining the particles. On the contrary, inertia weight coefficient is large when the target function value is worse than the average target value of the particle, which make the particle move closer to the better search area.

3.2 Fitness Calculation

In the actual measurement, the range error between the unknown node and the beacon node is inevitable, which can be defined in Eq. (9):

$$f(x_{n} ,y_{n} ) = \sum\limits_{i = 1}^{k} {\left( {\sqrt {(x_{n} - x_{n,i} )^{2} + (y_{n} - y_{n,i} )^{2} } - d_{n,i} } \right)^{2} }$$
(9)

where (xn, yn) is the coordinate of an unknown node Un, (xn,i, yn,i) is the coordinate of i-th beacon node Bi which can be used to locate unknown nodes Un, dn,i is the distance between Un and beacon node Bi, which is estimated by Eq. (3).

In order to reduce the influence of the accumulative positioning error, Eq. (9) can be rewritten as:

$$f(x_{n} ,y_{n} ) = \sum\limits_{i = 1}^{k} {\frac{{\left( {\sqrt {(x_{n} - x_{n,i} )^{2} + (y_{n} - y_{n,i} )^{2} } - d_{n,i} } \right)^{2} }}{{d_{n,i} }}}$$
(10)

Equation (10) is used to calculate the fitness value in the improved PSO algorithm. Therefore, the calculation process of the unknown node’s location can be transformed into solving the minimum value of the fitness function problem. So far it is possible to locate the unknown nodes in region I and II accurately which are distributed in the dense distributed grid. As for the unknown nodes which are distributed in region III, due to the fact that the number of the beacon nodes is less than 3 in the initial stage, so the aforementioned method cannot be used directly. At this point, the neighbor nodes in region I or II which has been located in the previous stage will be regarded as new beacon nodes. At last, all the unknown nodes in region III can be located by using the improved PSO algorithm repeatedly.

3.3 The Process of Iterative Localization Algorithm Based on Improved PSO Algorithm

  • Step 1 The monitoring area is initialized with grid division, while the beacon nodes equipped with GPS and solar battery are deployed on the 4 vertices of the square grid, the unknown nodes are deployed in that grid. The distance between two adjacent beacon nodes is the node’s wireless communication radius R, and each beacon node can obtain its own position with the help of GPS. Beacon nodes broadcast its own node information, including its ID number and its location.

  • Step 2 An unknown node Un receives the broadcast information of beacon nodes, and calculate the distance from each beacon node according to measured RSSI value by Eq. (2).

  • Step 3 According to the number of beacon nodes which can be detected by that unknown node, Step 4 will be performed if the number of nodes can be detected reaches 3 (in region I or II), otherwise nothing is done and wait for next judgement (in region III).

  • Step 4 Initialize particle swarm. A population is generated with N particles, while the position and velocity of each particle are initialized to random values. The individual extreme value of i-th particle is initialized to the position of i-th particle.

  • Step 5 The fitness of each particle is calculated by Eq. (10). The particle’s position which has the smallest fitness is selected as the global extremum.

  • Step 6 The particle’s velocity and position are adjusted and updated by Eqs. (6), (7) and (8).

  • Step 7 The current fitness value of each updated particle is calculated and compared with the fitness value of the individual extreme value Pid of the particle. If the current fitness value of i-th particle is less than the fitness value of Pid, the current position of i-th particle is updated to the new individual extreme value Pid.

  • Step 8 The fitness value of each particle is compared with the fitness value of the global extreme value Pgd. If the current fitness of i-th particle is less than the fitness value of Pgd, the position of i-th particle is updated to the new global extreme value Pgd.

  • Step 9 When neither the calculated fitness value reaches the preset fitness value nor the number of iterations of the loop reaches the preset maximum number, it jumps to Step 6. Otherwise it exits the loop and output the coordinates of the global extreme value Pgd.

  • Step 10 Step 3 to Step 9 are performed repeatedly until all the unknown nodes which can detect at least 3 beacon nodes are located.

  • Step 11 For those unknown nodes in region III, the unknown nodes which have been located in aforementioned are treated as the new beacon nodes, then it jumps to Step 3.

4 Localization Method Combined with Improved PSO Algorithm and Adaptive Mobile Node for WSNs

The localization method mentioned above is able to locate the unknown nodes effectively in densely distributed grid. However, some island nodes may occur in sparsely distributed grid inevitably because of the node’s random toss deployment. For such island nodes, it is difficult to locate their positions through the method presented above as a result of small amount of neighbor nodes. In this paper, a localization method with the help of adaptive mobile node is proposed to solve above problem. For the sake of simplicity, we make adaptive mobile node moving to the center of sparse distributed grid where the island node exists in. Then such an adaptive mobile node will be regarded as a temporary beacon node, which can ensure that the island node is able to sense 3 beacon nodes at that moment. In the next step, the improved PSO algorithm proposed above could be used to locate island node’s position. If there exist many island nodes in the monitoring area, adaptive mobile node should be able to select an optimal path to move to the centers of each sparse distribution grid in proper order. In this way, the computation of the optimal path of the adaptive mobile node can be transformed into a typical traveling salesman problem (TSP). In this work, the genetic algorithm is used to solve this problem.

The processing flow of localization method combined with improved PSO algorithm and adaptive mobile node are described in Fig. 3.

Fig. 3
figure 3

Flow chart of localization method combined with improved PSO algorithm and adaptive mobile node

Full size image

5 Simulation Experiments

In order to verify the performance of the algorithm, MATLAB 7.10 environment is used to simulate and analyze the algorithm proposed in this paper. Firstly, we simulated the performance of iterative localization algorithm based on improved PSO algorithm in the dense distributed grid. The communication radius R is 100 m, and 20 unknown nodes are randomly distributed in a square grid of 100 m × 100 m. The 4 beacon nodes are deployed at the 4 vertices of the grid in the initial stage. Each node can estimate the distance between the neighbor nodes by the received RSSI value. In order to simplify the influence of environmental factors, the distance measurement error is set as normal distribution where the mean is 0, and the variance of the ranging error is set 3 m. The simulation parameters are set as follows: the population quantity of the particle swarm is 40, the learning factor c1 = c2 = 2, the maximum inertia weight coefficient ωmax = 0.9, the minimum inertia weight coefficient ωmin = 0.6, and the iteration step is 100.

Figure 4 shows the results of the simulation experiment of iterative localization algorithm based on improved PSO algorithm to locate the unknown nodes in the densely distributed grid. The simulation results verify the effectiveness and reliability of the algorithm. The location accuracy of the unknown nodes in the region I and II is very high. Due to the use of iterative localization method, the location error of those nodes in region III is slightly larger, which satisfied the expected analysis. In Fig. 4, ○ represents the true location, * represents the first calculated location, + represents the second calculated location.

Fig. 4
figure 4

Simulation performance in dense distributed grid

Full size image

In order to reduce the accumulative error caused by the multiple beacon nodes, Eq. (10) is modified to Eq. (11) to obtain the average localization error.

$$ERR = \frac{{\sum\nolimits_{i = 1}^{N} {\left( {\sqrt {(x_{n} - x_{n,i} )^{2} + (y_{n} - y_{n,i} )^{2} } - d_{n,i} } \right)^{2} } }}{N}$$
(11)

Figure 5 compares the average localization error between iterative localization algorithm based on improved PSO algorithm in this paper, the maximum likelihood estimation method, the localization algorithm based on improved genetic algorithm [19] and the iterative localization algorithm based on adaptive mesh [20]. In that simulation, 20% of the total nodes are beacon nodes based on improved genetic algorithm, two original beacon nodes based on the mesh adaptive iterative localization algorithm arranged in the edge of location area. The results show that, the positioning error of the four algorithms is increased with the increase of distance measurement error. Overall, the average position error of the proposed iterative localization algorithm based on improved particle swarm optimization algorithm and the maximum likelihood estimation method is relatively small, and the algorithm proposed in this paper is more effective. Because of the continual usage of the iterative method for localization algorithm based on improved genetic algorithm and localization algorithm based on adaptive grid, the results show that the average location error is good when range error is small, however, the average location error becomes much worse quickly when the average location error increases. Obviously, it is able to reduce the localization error effectively by raising the number of beacon nodes.

Fig. 5
figure 5

The relationship between the average location and location error

Full size image

The evolution time of iterative localization algorithm based on improved PSO algorithm, standard PSO algorithm and genetic algorithm are compared in Fig. 6. For the fairness, three algorithms have the same parameters as possible. The learning factor c1 = c2 = 2, the number of iterations is 100, the population size is 40, the maximum inertia weight coefficient ωmax = 0.9, the minimum inertia weight coefficient ωmin = 0.6. It can be seen from the results that the iterative localization algorithm based on improved PSO converges faster than the algorithm based on standard PSO. The improved PSO algorithm balance the global searching ability and the local improvement of the PSO algorithm due to the nonlinear dynamic inertia weight coefficient formula. GA has similar performance to the improved PSO algorithm, but the PSO retains a population-based global search strategy. It is easy to operate the speed–displacement model and avoid the complicated genetic operations.

Fig. 6
figure 6

The relationship between the average location and location error

Full size image

Figure 7 shows the performance comparison of the three algorithms when the size of the population dropped to 5. The result shows that the performance of PSO algorithm still maintains its excellent performance compared with GA algorithm. It can be seen that the PSO algorithm is not very sensitive to the size of the population, i.e. the performance decline is not significant when the number of populations is decreasing.

Fig. 7
figure 7

The relationship between the average location and location error (population size: 5)

Full size image

Figure 8 shows the relationship between the communication range and the average location error. It can be seen from the results that with the increase of the communication range, the location error decreases. Overall, the downtrend of location error is nonlinear, with the communication range increase, the location error decrease very fast at the beginning, when the communication range increases to a certain extent, the location error tends to be stable. Through the simulation, after balancing location error, power consumption and other aspects, we consider the best communication range should be set as 90–95 m. Figure 9 shows the optimal path of the mobile node.

Fig. 8
figure 8

Relationship between the communication range and the average location error

Full size image
Fig. 9
figure 9

Optimal path of mobile node

Full size image

6 Conclusions

This paper proposes a new iterative localization algorithm based on PSO in the applications of environment monitoring. We focus on absorbing the features and advantages of locating algorithms nowadays and finding a suitable solution in our application. To the best of our knowledge, we divide the monitoring area into two kinds of grids according to coverage density and connectivity, which are densely distributed grid and sparsely distributed grid. Then we present an iterative localization method based on improved PSO algorithm to locate the unknown nodes in densely distributed grid. For those isolated unknown nodes in sparsely distributed grid, which is named island node in this paper, a localization method with the help of adaptive mobile node is introduced. The simulation results show that the algorithm has the advantages of small location error and little influence by environmental factors. Due to the low cost of this method, we hope it would have broader application prospect in future.