1 Introduction

With the development of microelectro mechanical system, chip system and wireless communication technology, there is rapid development in sensor nodes of low power, limited resources and multifunction. The sensor nodes are available for information collection, data processing and wireless communication. Wireless sensor networks (WSNs) are multi-hop ad hoc networks which consist of a large number of senor nodes [1, 2]. WSNs perceive, collect and process information of sensor nodes within network coverage. WSNs have been applied in many fields, such as smart grids [3, 4], military, industry, smart home, medical care, marine and other fields, especially natural disaster monitoring, early warning and rescue [5, 6]. WSNs have a wide application prospect.

In many applications of WSNs, collection of all information requires accurate locations of sensor nodes. Therefore, localization is one of the core technologies of WSNs [7]. Currently, satellite localization systems, such as global positioning system (GPS) and Beidou localization system, are used outdoors. But node’s energy in WSNs is limited [8, 9]. The related satellite localization module requires tens of milliamps working current. Its energy consumption is equivalent to the energy consumption of node wireless communication. In the long-term environmental monitoring applications, it’s necessary to reduce energy consumption and cost of sensor nodes. Therefore not all sensor nodes need to be equipped with satellite localization modules.

In WSNs, some scholars study localization algorithms of mobile nodes with static located beacon nodes [10–13]. But those algorithms need many static nodes which install satellite localization modules to locate the mobile nodes. The system cost is high. Some scholars study localization algorithms of sensor nodes with a few located mobile beacon nodes, and get some achievements. Reference [7] classifies the localization algorithm with mobile beacon nodes into two categories: geometric localization algorithm and path planning localization algorithms, and presents the typical algorithms, such as SCAN, DOUBLE_SCAN, HIBERT and backtracking greedy algorithm. Reference [14] proposes a spiral movement trajectory of mobile beacon node to broadcast its location information. To solve the imbalance distribution problem caused by beacon nodes, reference [15] proposes node localization optimization algorithm of mobile sensor network based on Monte Carlo method. The algorithm selects the nodes of high localization accuracy as temporary anchor nodes, which help other nodes to locate. And through Monte Carlo box and particle filter of unlocated nodes, the algorithm realizes precise localization of nodes. However, the algorithm doesn’t use the mobility of beacon nodes. Reference [16] proposes a circular movement path (CIRCLES), which can reduce collinear sojourn locations. Reference [17] divides the monitoring area into several grids, and proposes a movement algorithm for beacon node. When unlocated sensor node communicates with beacon node, it gets the RSSI (received signal strength indication) value and uses localization method of three points to calculate its location. Reference [18] proposes a modified HIBERT movement path of beacon node. The path can improve localization accuracy of unlocated sensor nodes. Reference [19] proposes a superior path planning mechanism for mobile beacon-assisted localization (ZSCAN). The beacon node which moves along the path can locate all deployed sensor nodes. Reference [20] proposes a localization algorithm with mobile beacon node based on trilateral measurement method. In the algorithm, beacon node moves along the triangular trajectory and broadcasts its current location periodically. All sensor nodes calculate their locations according to the location information of beacon node. The beacon nodes in references [14–20] require covering the entire monitoring area. The movement paths are relatively longer. They do not consider the actual distribution of sensor nodes. When sensor nodes distribute unevenly, there is few sensor nodes around some parts of movement path, therefore the path should be reduced. According to the information of sensor nodes in the vicinity, reference [21] uses virtual force theory to obtain the movement path of beacon node, and proposes a dynamic movement strategy. According to the area size estimation of each static sensor node, reference [22] proposes guiding mechanism of beacon node and obtains an efficient movement path to improve the localization accuracy of sensor nodes. Reference [23] proposes a dynamic beacon mobility scheduling algorithm for beacon node (DBMS). According to the RSS (received signal strength) information of sensor nodes in the vicinity, DBMS algorithm heuristically selects the next moving target, and uses depth-first traversal method in graph theory to traverse all sensor nodes. But the beacon nodes in references [21–23] move to traverse the nearby locations of each sensor node and the movement paths are longer.

References [14–23] study the movement paths of beacon node which full cover the movement area or the sensor nodes. But in real projects, the energy consumption of movement in beacon node is large and energy supply is limited. It cannot support the node’s moving for a long time. When network starts, it is necessary to realize the localization of most sensor nodes as soon as possible. Therefore, on the basis of above references, considering that maximum movement distance of beacon node is limited, the node localization algorithm of wireless sensor networks with mobile beacon node (NLA_MB) is proposed. NLA_MB algorithm divides the movement area of beacon node into some hexagonal grids, and establishes optimization model of node localization errors according to the movement path constraint, movement distance constraint and other constraints of beacon node. According to estimated coordinates of guide sensor nodes, beacon node uses heuristic method to solve the optimization model approximately based on virtual force theory, and obtains a movement path which is suitable for the current nodes distribution. When beacon node moves along the path, a part of sensor nodes receive three or more beacon node’s non-collinear locations, use maximum likelihood estimation algorithm to calculate their own location coordinates, mark as anchor sensor nodes, and broadcast their location information packets. According to the location information of beacon node and anchor sensor nodes, other sensor nodes estimate their own location coordinates, mark as guide sensor nodes and send the locations to beacon node. NLA_MB algorithm is suitable for the different distribution scenarios of sensor nodes, such as full coverage distribution, L-type distribution, Tian-type distribution and U-type distribution. It improves the localization accuracy of sensor nodes.

2 Algorithm principle

NLA_MB algorithm is a 2-dimensional localization algorithm and assumes that when WSNs start, there are unlocated static sensor nodes and one mobile beacon node in 2-dimensional area [24]. Beacon node installs GPS or Beidou satellite localization module, and knows its own location coordinates. Beacon node’s movement area is set before WSNs start, namely beacon node also knows its movement area. If there are multiple beacon nodes, the movement area is divided with the methods, such as clustering methods and graph theory methods. Each beacon node is responsible for a part of the area. Therefore, node localization problem with multiple beacon nodes is converted to node localization problem with single beacon node.

As shown in Fig. 1, there are beacon node, anchor sensor nodes, guide sensor nodes and unlocated sensor nodes. In the area sensor nodes are randomly distributed and need to know their own locations. Meanwhile, in order to reduce the system cost and energy consumption, a mobile beacon node assists to locate the sensor nodes. Beacon node stays at the initial center of grid, selects an unstayed vertex of grid to move to. It stays at the location and sends its location information packet some time, and moves to another unstayed center of grid which has the vertex. Because three adjacent locations are not collinear, when beacon node selects sojourn location, it deletes the location which is collinear with last two locations. Beacon node keeps moving and sending its location information packet until it reaches maximum movement distance. Sensor nodes receive the information of more than 3 non-collinear locations of beacon node, collect RSSI value during communication, use Kalman filter to reduce communication noise, calculate their own coordinates by maximum likelihood estimation algorithm, mark themselves as anchor sensor nodes and broadcast their locations to assist other sensor nodes which are not located by beacon node. The sensor nodes whose locations are not located by beacon node, estimate their locations based on the location information of beacon node and anchor sensor nodes in the vicinity, mark themselves as guide sensor nodes, send their locations to beacon node and guide the movement of beacon node. Both anchor sensor nodes and guide sensor nodes obtain their locations, but the locations of anchor sensor nodes are more precise than the locations of guide sensor nodes.

Fig. 1
figure 1

Principle of NLA_MB algorithm

Full size image

As shown in Fig. 2, when WSNs start, beacon node needs to divide its movement area into a number of hexagonal grids of uniform size [25], and needs to number all hexagonal grids and vertices of the grids in the movement area according to the principle of from left to right and from bottom to top. For example, grid(2,1) represents a hexagonal grid which is in column 2 from the left and row 1 from the bottom. Ding(2,2) represents the vertex which is in column 2 from the left, and row 2 from the bottom. But NLA_MB algorithm needs to solve the following three problems. First, how to use mathematical formulas to express the constraint conditions, such as movement path constraint, movement distance constraint, etc. How to establish the optimization model of node localization errors. Second, how do sensor nodes calculate their own coordinates with beacon node’ movement and location information of anchor sensor nodes? Third, how beacon node use heuristic algorithm to solve the optimization model approximately and obtain movement path? The specific solutions to the three problems are as follows.

Fig. 2
figure 2

Numbering method

Full size image

2.1 Constraint analysis and optimization model establishment

2.1.1 Constraint analysis

As shown in Fig. 1 and Fig. 2, if current sojourn location of beacon node is center of grid, next sojourn location is vertex of the grid. If current sojourn location is vertex of grid, next sojourn location is center of the grid which has the vertex. Then when current sojourn location of beacon node is center of grid, the next optional location set is

$$ {N}_g=\left\{\begin{array}{l}\left\{ ding\left(1,2j-1\right), ding\left(1,2j\right), ding\left(1,2j+1\right)\right\}\kern15.45002em {p}_g=p\left(1,j\right)\\ {}\left\{ ding\left(n-1,2j-1\right), ding\left(n-1,2j\right), ding\left(n-1,2j+1\right)\right\}\kern11.60001em {p}_g=p\left(n,j\right)\\ {}\left\{ ding\left(i-1,1\right), ding\left(i-1,2\right), ding\left(i,1\right), ding\left(i,2\right)\right\}\kern13.90002em {p}_g=p\left(i,1\right)\kern0.2em \mathrm{and}\kern0.2em i\kern0.2em is\ even\\ {}\left\{ ding\left(i-1,2\mathrm{m}\right), ding\left(i-1,2\mathrm{m}+1\right), ding\left(i,2\mathrm{m}\right), ding\left(i,2\mathrm{m}+1\right)\right\}\kern8.699997em {p}_g=p\left(i,m+1\right)\mathrm{and}\kern0.2em i\kern0.2em is\ even\\ {}\left\{ ding\left(i-1,2\mathrm{j}\hbox{-} 2\right), ding\left(i-1,2j-1\right), ding\left(i-1,2j\right), ding\left(i,2\mathrm{j}\hbox{-} 2\right), ding\left(i,2j-1\right), ding\left(i,2j\right)\right\}\kern0.7em \mathrm{others}\ \mathrm{when}\kern0.2em i\kern0.2em is\ even\\ {}\left\{ ding\left(i-1,2\mathrm{j}\hbox{-} 1\right), ding\left(i-1,2j\right), ding\left(i-1,2j+1\right), ding\left(i,2\mathrm{j}\hbox{-} 1\right), ding\left(i,2j\right), ding\left(i,2j+1\right)\right\}\kern1em \mathrm{others}\ \mathrm{when}\kern0.2em i\kern0.2em is\kern0.2em \mathrm{odd}\end{array}\right. $$
(1)

Where, N g  represents the set of next optional locations when current sojourn location is p g . p g represents current sojourn location. p(i, j) represents the center location of grid(i, j). m represents the number of grids in the first column. n is an odd number which represents the number of grid’s columns in the movement area of beacon node. When current sojourn location of beacon node is vertex of grid, the next optional location set is

$$ {N}_g=\left\{\begin{array}{l}\left\{p\left(i,1\right),p\left(i+1,1\right)\right\}\kern9.75em {p}_g= ding\left(i,1\right)\\ {}\left\{p\left(i,m\right),p\left(i+1,m+1\right)\right\}\kern7.599995em {p}_g= ding\left(i,2m+1\right)\mathrm{and}\kern0.2em i\kern0.3em \mathrm{is}\kern0.2em \mathrm{odd}\kern0.1em \\ {}\left\{p\left(i,m+1\right),p\left(i+1,m\right)\right\}\kern7.599995em {p}_g= ding\left(i,2m+1\right)\mathrm{and}\kern0.2em i\kern0.3em \mathrm{is}\kern0.3em \mathrm{even}\kern0.3em \\ {}\left\{p\left(i,\left(j\hbox{-} 1\right)/2\right),p\left(i,\left(j+1\right)/2\right),p\left(i+1\right.,\left(j+1\right)/2\right\}\kern4.199998em \mathrm{others}\ \mathrm{when}\kern0.2em i\kern0.2em is\kern0.2em \mathrm{odd}\kern0.3em \mathrm{and}\kern0.2em j\kern0.2em \mathrm{is}\kern0.2em \mathrm{odd}\kern0.2em \\ {}\left\{p\left(i,j/2\right),p\left(i+1,j/2\right),p\left(i+1\right.,j/2+1\right\}\kern7.3em \mathrm{others}\ \mathrm{when}\kern0.2em i\kern0.2em is\kern0.2em \mathrm{odd}\kern0.3em \mathrm{and}\kern0.2em j\kern0.2em \mathrm{is}\ \mathrm{even}\kern0.2em \\ {}\left\{p\left(i,\left(j+1\right)/2\right),p\left(i+1,\left(j-1\right)/2\right),p\left(i+1\right.,\left(j+1\right)/2\right\}\kern2.2em \mathrm{others}\ \mathrm{when}\kern0.2em i\kern0.2em is\ even\kern0.3em \mathrm{and}\kern0.2em j\kern0.2em \mathrm{is}\kern0.2em \mathrm{odd}\\ {}\left\{p\left(i,j/2\right),p\left(i,j/2+1\right),p\left(i+1,j/2\right.\right\}\kern9em \mathrm{others}\ \mathrm{when}\kern0.2em i\kern0.2em is\ even\kern0.3em \mathrm{and}\kern0.2em j\kern0.2em \mathrm{is}\ \mathrm{even}\end{array}\right. $$
(2)

The movement path of beacon node, which is the set of sojourn locations, is represented as\( P=\left\{{p}_1,{p}_2,\dots, {p}_{N_p}\right\} \). Where, p v represents the sojourn location of beacon node and is a 1*3 vector[k 1   k 2   k 3]. The first element k 1of the vector represents the column number of the sojourn location. The second element of the vector k 2 represents the row number of the sojourn location. The third element of the vector k 3 represents the type of the sojourn location, and the value is 0 (center of grid) or 1 (vertex of grid). According to the set N g of neighbor optional locations, there are three movement path constraints. The first constraint is set constraint (3) of neighbor optional locations. The constraint requires beacon node to select an element from the set N g of neighbor optional locations as next sojourn location.

$$ {p}_{g+1}\in {N}_g,g=1,2,\ldots,{N}_p-1 $$
(3)

Where, N p represents the number of sojourn locations of beacon node.

The second constraint is non-repeat selection constraint (4). The constraint requires that beacon node doesn’t stay at the same location twice. Then there is no same element in the path P.

$$ {p}_g\ne {p}_v,\forall {p}_g\in P,\forall {p}_v\in P,g\ne v $$
(4)

The third constraint is non-collinear constraint (5). If the sojourn locations of beacon node are collinear, it is difficult to calculate location coordinates of sensor nodes. Therefore, in order to avoid the collinearity of sojourn locations, the constraint requires that three consecutive sojourn locations are not collinear. \( {\uplambda}_{p_g\kern0.2em ,{p}_{g+1}\kern0.3em ,{p}_{g+2}} \) represents an identifier whether three consecutive sojourn locations p g  , p g + 1 , p g + 2 in the path P is collinear. \( {\uplambda}_{p_g\kern0.2em ,{p}_{g+1}\kern0.3em ,{p}_{g+2}}=1 \)represents the three sojourn locations are collinear, otherwise they are not collinear. Thus, the non-collinear constraint is

$$ {\uplambda}_{p_g\kern0.2em ,{p}_{g+1}\kern0.3em ,{p}_{g+2}}=0,\kern0.4em g=1,2,\dots, {N}_p-2 $$
(5)

Because energy of beacon node is limited, the maximum movement distance is limited. Then movement distance constraint is.

$$ {\displaystyle \sum_{g=1,2,\dots, {N}_p-1}d\left({p}_g,{p}_{g+1}\right)}\le {d}_{th},{p}_g\in P $$
(6)

Where, d th represents the maximum movement distance of beacon node.

2.1.2 Optimization model establishment

According to the set constraint of neighbor optional locations, non-repeat selection constraint, non-collinear constraint and movement distance constraint, the optimization model is established as follows to find the path whose movement distance does not exceed the maximum value and minimize the localization error of sensor nodes.

$$ \begin{array}{c}\hfill \begin{array}{l}\begin{array}{l} \min \left( error(P)\right)\hfill \\ {}\mathrm{s}.\mathrm{t}.{p}_{g+1}\in {N}_g,g=1,2,\dots, {N}_p-1\hfill \end{array}\hfill \\ {}{p}_g\ne {p}_v,\forall {p}_g\in P,\forall {p}_v\in P,g\ne v\hfill \end{array}\hfill \\ {}P=\left\{{p}_1,{p}_2,\dots, {p}_{N_p}\right\}\hfill \\ {}{\uplambda}_{p_{g,}{{}_{p_{{}_{g+1},}}}_{p_{g+2}}}=0,g=1,2,\dots, {N}_p-2\hfill \\ {}\hfill {\displaystyle \sum_{g=1,2,\dots, {N}_p-1}d\left({p}_g,{p}_{g+1}\right)}\le {d}_{th},{p}_g\in P\hfill \end{array} $$
(7)

Where, error(P) represents the average localization error value between the locations calculated by sensor nodes themselves and their real locations, when beacon node moves along the path P. That means, when beacon node stays at one location, it broadcasts location information packet which contains ID, location coordinates and other information. Anchor sensor nodes broadcast their location information packets which contain their own ID, location coordinates and other information. The guide sensor node and unlocated sensor node receives the location information packet of anchor point (beacon node or anchor sensor node), reads its location information and RSSI value of communication link, uses Kalman filter to reduce the communication noise, and calculates the distance to anchor point. When the sensor node obtains more than three non-collinear location coordinates of anchor points and the distances to each anchor point, it calculates the location coordinates by maximum likelihood estimation algorithm (MLE). As shown in Fig. 3, there are n known locations of anchor points. The distances to the anchor points are d 1 、d 2 、d 3 …… d n , which are calculated by RSSI values.

$$ 2\left[\begin{array}{c}\hfill {x}_n-{x}_1\hfill \\ {}\hfill \vdots \hfill \\ {}\hfill {x}_n-{x}_{n-1}\hfill \end{array}\begin{array}{c}\hfill {y}_n-{y}_1\hfill \\ {}\hfill \vdots \hfill \\ {}\hfill {y}_n-{y}_{n-1}\hfill \end{array}\right]\left[\begin{array}{c}\hfill {x}^R\hfill \\ {}\hfill {y}^R\hfill \end{array}\right]=\left[\begin{array}{c}\hfill \left({d}_1^2-{d}_n^2\right)-\left({x}_1^2-{x}_n^2\right)-\left({y}_1^2-{y}_n^2\right)\hfill \\ {}\hfill \vdots \hfill \\ {}\hfill \left({d}_{n-1}^2-{d}_n^2\right)-\left({x}_{n-1}^2-{x}_n^2\right)-\left({y}_{n-1}^2-{y}_n^2\right)\hfill \end{array}\right] $$
(8)
Fig. 3
figure 3

Maximum likelihood estimation algorithm

Full size image

Where, (x R, y R)represents the calculated horizontal and vertical coordinates. (x 1, y 1), (x 2, y 2)…(x n , y n ) represents the coordinates of anchor points.

If sensor node m receives the information of more than 3 non-collinear locations of beacon node, it solves the formula (8) and obtains its own coordinates\( \left({x}_m^R,{y}_m^R\right) \).Then it marks as anchor sensor node and broadcasts its location information. Otherwise, according to the location information of beacon node and anchor sensor nodes, sensor node m estimates its location coordinates\( \left({x}_m^R,{y}_m^R\right) \). If sensor node m does not calculate its own location, \( \left({x}_m^R,{y}_m^R\right) \)is (0, 0). The average localization error of sensor nodes is

$$ error(P)=\frac{{\displaystyle \sum_{m\in {V}_R}\sqrt{{\left({x}_m^R-{x}_m\right)}^2+{\left({y}_m^R-{y}_m\right)}^2}}}{N} $$
(9)

Where,x m and y m respectively represent real horizontal coordinate and vertical coordinate of sensor node m. V R represents a set of sensor nodes. N represents the number of sensor nodes.

2.2 Heuristic method of approximate solution

If optimization method is used to solve the model (7) directly, because of great computation, it is difficult to be applied to the beacon node with limited computing power. Therefore, heuristic method based on virtual force theory is used to solve the model (7) approximately. The method is as follows.

First, beacon node stays at initial location for some time, then moves to two non-collinear sojourn locations randomly, and broadcasts its own location information at the three locations. Sensor nodes in the vicinity receive the 3 non-collinear location information of beacon node, calculate their location coordinates, mark as anchor sensor nodes and broadcast their location information packets. Other sensor node receives location information of beacon node or anchor sensor nodes (anchor points). If one sensor node receives the information of more than 2 non-collinear locations of anchor points, it estimates its coordinates, makes as guide sensor node and broadcasts its location to beacon node directly or through one anchor sensor node. Although the localization error of estimated coordinates of guide sensor nodes is large, they can be used as reference points for the movement of beacon node. Beacon node receives the estimated location information of guide sensor nodes, updates its estimated location information table, and calculates the virtual attractive forces of guide sensor nodes to beacon node.

$$ \overrightarrow{F_w}={x}_w\overrightarrow{d_w}/\left|\overrightarrow{d_w}\right| $$
(10)

Where, \( \overrightarrow{F_w} \)represents the virtual attractive force of guide sensor node w to beacon node, x w represents the attractive force coefficient of guide sensor nodes, \( \overrightarrow{d_{\mathrm{w}}} \)represents the directed distance vector of beacon node to guide sensor node w. \( \left|\overrightarrow{d_{\mathrm{w}}}\right| \)represents the morn of distance vector \( \overrightarrow{d_{\mathrm{w}}} \), namely the distance value. According to the attractive forces of guide sensor nodes, final composition of forces \( \overrightarrow{F} \) is calculated [26, 27].

$$ \overrightarrow{F}={\displaystyle \sum_w\overrightarrow{F_w}} $$
(11)

Beacon node analyzes the set of next optional locations N g , and deletes the locations which beacon node stays at before from the set. Beacon node analyzes residual location elements, deletes the location which is collinear with last two sojourn locations, and obtains the updated set of locations \( {N}_g^{\prime } \). For example, as shown in Fig. 4, when beacon node stays at the vertex ding (2,2), it deletes stayed center of grid (2,1) from the set of next optional locations N g , and obtains the updated next optional location set \( {N}_g^{\prime }=\left\{ grid\left(2,2\right), grid\left(3,1\right)\right\} \). When beacon node stays at the center of grid(2,2), it deletes sojourn locations ding(2,2) and collinear sojourn locations ding(1,4), and obtains the updated next optional location set \( {N}_g^{\prime }=\left\{ ding\left(1,2\right), ding\left(1,3\right), ding\left(2,3\right), ding\left(2,4\right)\right\} \). If the location set \( {N}_g^{\prime } \) is empty, it indicates that all elements in the set N g do not accord with the constraint (4) and (5). The path gets into a dead end. Beacon node has to find an updated location set \( {N}_g^{\prime } \) which is not empty along the reverse path. Distance vector of current sojourn location to each neighbor optional location in the set \( {N}_g^{\prime } \) is obtained. Therefore, through above sojourn location selection method, the path accords with non-repeat selection constraint (4) and non-collinear constraints (5). Then the angles between force\( \overrightarrow{F} \)and each distance vector are calculated.

$$ \delta =\mathrm{acos}\left(\frac{\overrightarrow{F}\ast \overrightarrow{d_{sg}}}{\left|\overrightarrow{F}\right|\ast \left|\overrightarrow{d_{sg}}\right|}\right) $$
(12)
Fig. 4
figure 4

The sojourn location selection of beacon node

Full size image

Where, acos() represents the inverse cosine function, \( \overrightarrow{d_{sg}} \)represents the distance vector from current sojourn location of beacon node to its next location. \( \left|\overrightarrow{d_{sg}}\right| \)represents the morn of vector. The location which has the smallest angle is selected as next sojourn location, therefore the path accords with set constraint (3) of neighbor optional locations. In short, based on virtual force theory, beacon node selects next sojourn location from neighbor optional location set, which accords with constraint (3)-(5), until the path does not accord with movement distance constraint (6).

Beacon node moves towards the area where many guide sensor nodes distribute. The beacon node communicates with those sensor nodes directly, and sends its accurate location coordinates. Therefore, the localization accuracy of sensor node is improved.

3 Algorithm implementation

NLA_MB algorithm is a distributed algorithm. After network starts, sensor nodes and beacon node execute their own algorithms respectively. As shown in Fig. 5, the steps of each sensor node are as follows.

  • Step 1: After network starts, parameters are initialized. Sensor node defines itself as unlocated sensor node and there are other unlocated sensor nodes in its communication range. Namely, Lflag = 0, Nflag = 0. Where,Lflag represents an identifier whether the sensor node completes localization. Nflag represents an identifier whether there are guide sensor nodes or unlocated sensor nodes in its communication range.

  • Step 2: The value of Lflag is judged. If it is 1, go to Step 5. If a location information packet is received, its source is judged. If it is from neighbor anchor sensor node, the sensor node ID, location coordinates, link RSSI value and other information are obtained. The validity of the information is analyzed. If it is valid, the information is added to the location information table of neighbor anchor sensor nodes. If the packet is from beacon node, the beacon node ID, location coordinates, link RSSI value and other information are obtained. The validity of the information is analyzed. If it is valid, the information is added to the location information table of beacon node.

  • Step 3: Whether the number of non-collinear locations in the location information table of beacon node is more than 2 is judged. If it is, according to the RSSI value, the distances to each anchor point are calculated, and its own location coordinates \( \left({x}_m^R,{y}_m^R\right) \) is calculated by maximum likelihood estimation algorithm. Then the sensor node is marked as anchor sensor node,Lflag = 1and beacon node is informed. Go to Step 2.

  • Step 4: If the number of non-collinear locations in the location information table of beacon node is less than 2, the locations which have high RSSI value in the location information table of neighbor anchor sensor nodes and non-collinear with locations in the location information table of beacon node are selected. Then the information of more than 3 non-collinear locations is obtained. Maximum likelihood estimation algorithm is used to estimate its own coordinates\( \left({x}_m^R,{y}_m^R\right) \). The sensor node is marked as guide sensor node. When beacon node appears in the communication area of its own or any neighbor anchor sensor node, the guide sensor node sends the location information packet to beacon node directly or through the neighbor sensor node. Go to step 2.

  • Step 5: Only location information packets of beacon node are received and its location updates. Whether Nflag is 1 is judged. If it is 0, its own location information packet is broadcasted to guide sensor nodes and unlocated sensor nodes. If there is no feedback packet, it means that guide sensor node or unlocated sensor node nearby doesn’t exit. Nflag = 1. Go to step 2.

Fig. 5
figure 5

Work flow chart of each sensor node

Full size image

As shown in Fig. 6, the steps of beacon node are as follows.

  • Step 1: The parameters are initialized, such as attractive force coefficientx w , maximum movement distanced th , current movement distanced 1 = 0, etc.

  • Step 2: The movement area of beacon node is divided into some hexagonal grids. With Beidou localization module, latitude and longitude are obtained and turned into earth location coordinates. Initial sojourn location set P y  = {p 1} is recorded and its location information packet is broadcasted.

  • Step3: The following operation is executed twice. The neighbor location which is not stayed at before is selected and moved to. Location set P y is updated. The movement distance is calculated and added to current movement distance d 1. With Beidou localization module, its own location coordinates is obtained and its location information packet is broadcasted.

  • Step 4: Directly or through anchor sensor nodes, location information packets of surrounding guide sensor nodes are received. The validity of the information is analyzed. The valid information is added to estimated location information table of guide sensor nodes.

  • Step 5: In the next optional location set N g , the location which is stayed at before and the locations which are collinear with last two sojourn locations are deleted. The new optional location set \( {N}_g^{\prime } \) is obtained. If the set \( {N}_g^{\prime } \) is empty, beacon node finds a non-empty set \( {N}_g^{\prime } \)along the selected path reversely. According to the locations of sensor nodes in the estimated location information table, the vectors from current location to each location in the set \( {N}_g^{\prime } \) are obtained. Angles between the composition of forces and each vector are calculated. The neighbor location of minimum angle is selected as next sojourn location. The location set P y is updated.

  • Step 6: The sojourn location is moved to and stayed at. The movement distance is calculated and added to current movement distance d 1. With Beidou localization module, its own location coordinates is obtained and its location information packet is broadcasted. If the information packet is received from an anchor sensor node, the information of the node is deleted from estimated location information table of guide sensor nodes.

  • Step 7: If d 1 ≤ d th , go to step 4, otherwise the moving is finished and localization algorithm is completed.

Fig. 6
figure 6

Work flow chart of beacon node

Full size image

The movement path of beacon node is obtained by loop executing the key steps 4–6. The goal of improving localization accuracy of sensor nodes with limited movement distance of beacon node is achieved.

4 Algorithm simulation

4.1 Algorithm simulation parameters and performance parameters

In the NLA_MB algorithm, the communication of location information packet needs to provide the effective RSSI value of communication link, and different wireless module has different RSSI characteristic, therefore the communication radius of effective location information packet is determined by the wireless module in the node. If side length of hexagonal grid reduces, the number of grids, effective movement of beacon node and complexity of NLA_MB algorithm enhance. The side length of hexagonal grid is determined by location accuracy requirement of practical application. In the algorithm simulation, the communication radius of effective location information packet is 40 m, and the side length of hexagonal grid is \( 40/\sqrt{3} \)m. The following parameters are defined to calculate the algorithm performance parameters, such as average localization error of sensor nodes, number of sojourn locations of beacon node, number of anchor sensor nodes and average number of anchor points of sensor nodes. The side length of simulation area is 160 m. The number of sensor nodes is 100. The maximum movement distances 300 m, 400 m, 500 m, 600 m, 700 m and 800 m of beacon node are considered. The initial location is the center of the grid(2,1).

Average localization error of sensor nodes is defined as the average localization error of all sensor nodes between located coordinates and real coordinates. Number of sojourn locations is defined as the sojourn number of beacon node along the movement path. Number of anchor sensor nodes is defined as the number of sensor nodes which calculate their locations according to the location information of beacon node moving along the selected path. The average number of anchor points of sensor nodes is defined as average number of anchor points which each sensor node has in the localization implementation process.

4.2 Analysis of simulation result

Simulation parameters in Section 4.1 are selected. Some distribution scenarios of sensor nodes are considered, such as full coverage distribution, L-type distribution, Tian-type distribution and U-type distribution. 20 topologies are generated randomly for each distribution. Average localization error of sensor node, number of sojourn locations of beacon node, number of anchor sensor nodes and average number of anchor points of NLA_MB, DOUBLE_SCAN [7], ZSCAN [19], MLE, RSCAN and DBMS [23] algorithms in each topology are calculated separately. The average values are the simulation results. Where, the beacon node in MLE algorithm randomly moves 3 times to locate sensor nodes in the vicinity. Beacon node in RSCAN algorithm randomly selects a grid’s center or vertex which is not stayed at before as next sojourn location. Beacon node in DOUBLE_SCAN, ZSCAN and DBMS algorithms use the methods in the related references to select movement path. In the six algorithms, if sensor node receives the information of more than 2 non-collinear sojourn locations from beacon node, their location coordinates are calculated directly. Otherwise the location coordinates of sensor nodes are calculated by the location information of anchor sensor nodes and beacon node. The simulation results in full coverage distribution, L-type distribution, Tian-type distribution and U-type distribution are as follows. The simulation results of maximum movement distance 600 m are selected to illustrate the movement path of beacon node.

4.2.1 Full coverage distribution of sensor nodes

As shown in Figs. 7, 100 sensor nodes randomly distribute in the simulation area. In NLA_MB algorithm, according to the location information of guide sensor nodes, beacon node finds a movement path which is less than 600 m and composed of 51 sojourn locations. The path moves through the area where many sensor nodes distribute. Beacon node appears in the vicinity of many sensor nodes, and provides its accurate location information. Therefore localization accuracy of these sensor nodes is improved.

Fig. 7
figure 7

Beacon node’s movement path of NLA_MB algorithm in full coverage distribution

Full size image

As shown in Fig. 8, NLA_MB and RSCAN algorithms both use the same hexagonal grids, maximum movement distance and movement distance each time, so the two algorithms have the same number of sojourn locations. In the two algorithms, the distance between each two neighbor sojourn locations is shorter, so the number of sojourn locations is larger than other algorithms’. The ZSCAN, DOUBLE_SCAN, DBMS and MLE algorithms consider the full coverage of the simulation area. Their distances between each two neighbor sojourn locations are larger. Therefore NLA_MB algorithm has the largest number of sojourn locations. The beacon node in MLE algorithm only moves 3 times randomly, and its number of sojourn locations is smallest.

Fig. 8
figure 8

Comparison of number of sojourn locations in full coverage distribution

Full size image

As shown in Fig. 9, according to the estimated locations of guide sensor nodes, NLA_MB algorithm determines the movement path. It covers more sensor nodes with limited movement distance. While other algorithms’ movement path only move through a part of the simulation area or the whole path with less sojourn locations. Therefore, when beacon node moves along the selected path, the average number of anchor points in NLA_MB algorithm is most. The beacon node in MLE algorithm basically does not move, thus the average number of anchor points is least.

Fig. 9
figure 9

Comparison of average number of anchor points in full coverage distribution

Full size image

As shown in Fig. 10, when maximum movement distances are 300 m, 400 m, 500 m and 600 m, the moving area of beacon node in NLA_MB algorithm is largest, other algorithms only move through a part of simulation area and cover less sensor nodes. Therefore, the number of anchor sensor nodes in NLA_MB algorithm is most. When maximum movement distance is 700 m or 800 m, beacon node in ZSCAN and DOUBLE_SCAN algorithms move through the whole simulation area. Thus, when maximum movement distance is 700 m, the number of anchor sensor nodes in ZSCAN algorithm is a few more than that in NLA_MB algorithm. When maximum movement distance is 800 m, the number of anchor sensor nodes in DOUBLE_SCAN algorithm is a few more than that in NLA_MB algorithm. But the numbers of anchor sensor nodes in those three algorithms have little difference, and are all higher than that in MLE, RSCAN and DBMS algorithms.

Fig. 10
figure 10

Comparison of the number of anchor sensor nodes in full coverage distribution

Full size image

In NLA_MB algorithm, beacon node moves to the area where most guide sensor nodes distribute. Along the movement path, beacon node stays at the nearby locations of most sensor nodes, and provides accurate location information. The beacon node in MLE algorithm does not move, and sensor nodes only calculate their coordinates according to the location information of sensor nodes in the vicinity. The localization accumulated error is large. Beacon node in RSCAN algorithm moves randomly. Because of limited movement distance, beacon node in DBMS algorithm only moves through a part of the simulation area. In ZSCAN and DOUBLE_SCAN algorithms, the number of sojourn locations of beacon node is smaller. Therefore, as shown in Fig. 11, average localization error of sensor nodes in NLA_MB algorithm is least and average localization error of sensor nodes in MLE algorithm is largest.

Fig. 11
figure 11

Comparison of average localization errors of sensor nodes in full coverage distribution

Full size image

4.2.2 L-type distribution of sensor nodes

As shown in Fig. 12, there is no sensor node in the square area, whose vertex coordinates are (80 m, 80 m), (80 m, 160 m), (160 m, 80 m) and (160 m, 160 m). In NLA_MB algorithm, the movement path of beacon node avoids the upper right corner of the area where no sensor node distributes and likes alphabet L. The path is concentrated in the area where many sensor nodes distribute, thus improves localization accuracy of sensor nodes.

Fig. 12
figure 12

Beacon node’s movement path of NLA_MB algorithm in L-type distribution

Full size image

As shown in Fig. 13, the average localization error of NLA_MB algorithm is lower than other algorithms’. The sensor nodes in L-type distribution concentrates relatively, therefore, with the same maximum movement distance, NLA MB algorithm in L-type distribution has less average localization error than NLA MB algorithm in full coverage distribution. The number of sojourn locations, number of anchor sensor nodes and average number of anchor points of all algorithms in the L-type distribution are similar to the ones in Section 4.2.1 in full coverage distribution. The paper doesn’t elaborate similar simulation results. Related content can refer to Section 4.2.1.

Fig. 13
figure 13

Comparison of average localization errors of sensor nodes in L-type distribution

Full size image

4.2.3 Tian-type distribution of sensor nodes

As shown in Fig. 14, in the simulation area, there are four squares of side length 40 m where no sensor node distributes. The distribution of sensor nodes like Chinese character Tian(田). In NLA_MB algorithm, the movement path of beacon node mainly concentrates in the cross area where many sensor nodes distribute. The movement path covers many sensor nodes and improves localization accuracy of sensor nodes.

Fig. 14
figure 14

Beacon node’s movement path of NLA_MB algorithm in Tian-type distribution

Full size image

As shown in Fig. 15, average localization error of NLA_MB algorithm is still lower than other algorithms’. Because sensor nodes in Tian-type distribution disperse relatively, the number of anchor sensor nodes with same movement distance decreases. The number of guide sensor nodes increases. Therefore, with the same maximum movement distance, average localization error of NLA_MB algorithm in Tian-type distribution is a little higher than that in full coverage distribution. The number of sojourn locations, number of anchor sensor nodes and average number of anchor points of all algorithms in the Tian-type are similar to the ones in Section 4.2.1 in full coverage distribution. The paper doesn’t elaborate similar simulation results. Related content can refer to Section 4.2.1.

Fig. 15
figure 15

Comparison of average localization errors of sensor nodes in Tian-type distribution

Full size image

4.2.4 U-type distribution of sensor nodes

As shown in Fig. 16, in the simulation area, there is no sensor node in U-type aperture area. In NLA_MB algorithm, the movement path of beacon node avoids the area where no sensor node distributes and likes alphabet U. It conforms to the actual distribution of sensor nodes, and improves localization accuracy of sensor nodes.

Fig. 16
figure 16

Beacon node’s movement path of NLA_MB algorithm in U-type distribution

Full size image

As shown in Fig. 17, average localization error of NLA_MB algorithm is still lower than other algorithms’. Because sensor nodes are concentrated distribution in U-type distribution, it is difficult for beacon node to locate the sensor nodes at the top of U type. Therefore, with the same maximum movement distance, the average localization error of NLA_MB algorithm in U-type distribution is similar to that in full coverage distribution. The number of sojourn locations, number of anchor sensor nodes and average number of anchor points of all algorithms in the U-type are similar to the ones in Section 4.2.1 in full coverage distribution. The paper doesn’t elaborate similar simulation results. Related content can refer to Section 4.2.1.

Fig. 17
figure 17

Comparison of average localization errors of sensor nodes in U-type distribution

Full size image

In short, no matter full coverage distribution, L-type distribution, Tian-type distribution, or U-type distribution, in NLA_MB algorithm beacon node can find the suitable movement path. When maximum movement distance is limited, NLA_MB algorithm increases the number of sojourn locations of beacon node and average number of anchor points of sensor nodes, and maintains a high coverage of sensor nodes. Therefore, it reduces average localization error of sensor nodes and improves localization accuracy.

5 Conclusion

Limited movement distance of beacon node in WSNs is considered. Node localization algorithm of wireless sensor networks with mobile beacon node (NLA_MB) is proposed. Firstly, the algorithm assumptions, constraints and optimization model are proposed. Secondly, based on virtual force theory, beacon node uses heuristic method to solve the model approximately. Namely according to estimated location information of guide sensor nodes, beacon node determines the next sojourn location and finds the movement path. When beacon node moves along the path, sensor nodes obtain different location information of beacon node and calculate their own location coordinates. The sensor nodes which are not located by beacon node, calculate their own coordinates according to the location information of anchor points. Thirdly, the implementation steps of NLA_MB algorithm are proposed. Finally, algorithm simulation parameters and performance parameters are given. The performance of NLA_MB, DOUBLE_SCAN, ZSCAN, MLE, RSCAN and DBMS algorithms are compared in the full coverage distribution, L-type distribution, Tian-type distribution and U-type distribution.

In short, NLA_MB algorithm is a distributed algorithm. It obtains the movement path which is suitable for the current distribution of sensor nodes, thereby reduces average localization error of sensor nodes and improves localization accuracy. However NLA_MB algorithm requires beacon node and anchor sensor nodes to send their location information packets frequently, thus has large communication overhead. Therefore, the next stage is to find the movement strategy of beacon node, which can reduce the communication overhead.