1 Introduction

The random deployment of sensors in area of interest generates non-uniform distribution of sensors, but also non-identification of their positions. Equipping nodes with GPS module is a very expensive solution and inefficient in some areas (Karl and Willig 2006; Mao et al. 2007; Kulaib et al. 2011). Hence, research for better solutions to determine nodes position without using GPS is a real challenge for researchers, these solutions should be implemented with low cost, low localization error, energy efficiency and a coverage of all nodes of the network. Localization represents solutions and techniques proposed to define position of all nodes belonging to WSN after their deployment (Sichitiu and Ramadurai 2004). Localization is very important, especially, to know the position of sensor signaling the appearance of an event, and trigger a quick action if necessary, or to control the coverage of area of interest. In order to locate different nodes of network, solutions proposed in literature are essentially based on the use of anchors (beacon, landmark, or seed) which represent nodes whose positions are known, either by the use of GPS module or by manual location (Mao et al. 2007) (Chelouah et al. 2017). These solutions are classified into two large families, according to whether they are based on the estimation of distances (angles) or not, called respectively: range based methods and range free methods (Nazir et al. 2012; Mistry and Mistry 2015; Zhang et al. 2018; Sheltami et al. 2017).

Among the numerous techniques proposed in literature belonging to Range based family, we quote: RSSI, AoA, ToA, TDoA (Yang and Wu 2015). In RSSI (Received Signal Strength Indicator), attenuation of signal during its propagation is exploited to calculate the distance between nodes. This method is characterized by its low computational complexity, and its low cost since no additional hardware investment is required. AoA (Angle of Arrival) consists in calculating the direction (angle) between two nodes. This approach is characterized by an additional hardware required (several spatially separated microphones and a speaker). ToA (Time of Arrival) is based on the calculation of signal reception time to estimate the distance between the transmitter and the receiver, which must be synchronized. TDoA (Time Difference of Arrival) requires ultra sound or audible frequencies in addition to radio signal. This method is known for its accuracy but it is very costly. Among the techniques proposed belonging to Range free methods, we quote: Centroid, APIT, DV HOP (He et al. 2011). The first method is based on connectivity to define the polygon composed of beacons belonging to unknown node communication range. The geometric center of this polygon represents its estimated position. The accuracy of this technique is related to density and distribution of anchors. In APIT (Approximate Point-In-Triangle), unknown node determines all possible combinations of triangles that can be formed by its proximate anchor nodes; the estimated node location is the center of gravity of all triangles where the node resides. DV HOP technique uses a Distance Vector exchange, each node of network obtains the distance separating them from anchors in number of hops, and exchanges updates with its neighbors only. A landmark estimates an average size of one hop per correction, and then uses trilateration to calculate its position.

In order to reduce the number of expensive GPS equipped node, and to address a problem of bad deployment of anchors, mobile anchor seems to be a good solution (Halder and Ghosal 2016). Mobile anchor is a node which knows its own position, by equipped it with GPS for example, and is able to traverse area of interest for assisting deployed sensors to determine their locations. A fundamental research issue of localization based on mobile anchor is to determine the trajectory of mobile anchor, which could be either static or dynamic. In static path planning scheme, the trajectory is known before start the movement of mobile, where as in dynamic path planning scheme, the trajectory is determined during the displacement considering the real distribution of unknown node. Many trajectories are proposed such as: CIRCLE, SCAN, Double SCAN, Spiral, Hilbert, Z-curve (Koutsonikolas et al. 2006; Yue et al. 2015; Hu et al. 2008; Rezazadeh et al. 2015; Bala Subramanian et al. 2020).

The works dealing with localization problems and other issues relating to WSN with decentralized methods have proved their efficiency comparing to centralized approaches, namely in terms of energy, time and communication flow (Mitici et al. 2014; Al-Hattab et al. 2017; Cascone et al. 2010; D’Apice et al. 2011).

The main contribution of this paper is to find locations of all sensors of the network with estimated positions as close as possible to the real positions; the method is implemented in a decentralized way. To do so, we have opted to use only one mobile anchor moving around the region of interest with spiral trajectory, in order to avoid having unlocalized sensors due to a low number of static anchors and / or their bad deployment. The first step of our approach consist on periodic diffusions of the mobile anchor positions during its travel. Next, each unknown node uses RSSI to estimate its distance to all mobile anchor positions from which it received a broadcast message. Thereafter, the estimated position is calculated by combining multilateration and the geometric center of the cloud of point that surround the real position of the unknown node, by considering some constraints.

The rest of this paper is organized as follows: Problem statement and related concepts are presented in Sect. 2. Section 3 describes in detail our contribution. Finally, in Sect. 4, we compare its efficiency to other existing algorithms using simulation.

2 Problem formulation

The present work is an extension of further work reported in Larbi-Mezeghrane et al. (2017), which consists in monitoring the perimeter P of a region of interest with circular shape of radius R. All sensors are deployed randomly around perimeter, over a range of \( [R-Depl\_Ring/2, R+Depl\_Ring/2 ] \) meters (abbreviations are defined in Table 1). In the previous work, positions of sensors are assumed to be known, to focus only on the coverage issue. In this work, the goal is to define (x, y) coordinates of each sensor in WSN. The proposed approach consists of using a single moving anchor that adopts a spiral trajectory and diffusing its position periodically. We believe that this trajectory is more suited to our deployment zone presented above. The proposed approach determines the cloud of points that surround the solution; these points are selected from the set of intersection points of all beacons received by the unknown node, by selecting only points that contribute to define the minimum weight of the cloud of points. The estimated position of the unknown node represents the geometric center of this cloud.

2.1 List of the used abbreviations

The list of abbreviations used in this paper is detailed in Table 1.

Table 1 List of the used abbreviations
Full size table

2.2 Basic model and assumptions

Our approach relies on the following assumptions:

  • Area of Interest is a region with circular shape of radius R and perimeter P.

  • Nodes are deployed randomly around perimeter P, with ring width of deployment zone over a range of \( [ R-Depl\_Ring/2,R+Depl\_Ring/2] \) meters.

  • Each sensor has a detection module, a communication module and a processing module.

  • We assume that all nodes have the same communication radius.

  • Once sensors are deployed, they are supposed to be static.

  • A protocol that supports all necessary informations for a communication within the network is assumed to be present.

  • There is only one mobile anchor moving around the region of interest; we assume that it has sufficient energy for moving and broadcasting position informations during the localization process.

  • The emission circles are considered as perfect.

  • Mobile anchor adopts a spiral trajectory with constant speed.

  • After each time interval t, mobile anchor broadcasts its position.

  • The trajectory length depends on the number of broadcasts (NbBroadcast).

2.3 Illustration of mobile node trajectory

The mobile anchor moves with spiral trajectory according to formulas 1 and 2 :

$$\begin{aligned} r_n=Br_{min}+n*\Delta d \end{aligned}$$
(1)

where:

\( r_n \)::

radius of \( n^{th} \) broadcast ;

\( Br_{min} \) ::

minimum radius of \(Depl\_Ring\);

\( \Delta d \) ::

variation in radius of each broadcast, it is given by:

$$\begin{aligned} \Delta d =\left( Br_{max}-Br_{min} \right) /NbBroadcast \end{aligned}$$
(2)

The angle turned is given by formula 3:

$$\begin{aligned} \theta _{n}=\sum _{i=1}^{n} v * t/r_{i} \end{aligned}$$
(3)

where:

\( \theta _n \)::

Angle of \( n^{th} \) broadcast ;

v::

Speed of mobile anchor ;

t::

Time inter broadcast.

Figure 1 illustrates sensors distribution in deployment area, mobile anchor trajectory and positions of broadcasting messages with 120 diffusions. The flowchart describing the general scheme of the proposed solution is shown in Fig. 2. Details of each step are presented in algorithms of Sect. 3.

Fig. 1
figure 1

Environment of the proposed localization solution

Full size image
Fig. 2
figure 2

Flowchart of the proposed localization solution

Full size image

3 Proposed Localization Algorithm

Algorithm 1 will be executed by the mobile anchor, whereas algorithm 2 and  3 will be executed by all nodes of the network (unknown nodes).

figure a
figure b
figure c

To better understand the functioning of our solution, we present an example explaining step by step how an unknow node determines its position, by executing our algorithm.

Let \( N_i \) an unknow node, and let \( B_1 \), \( B_2 \), \( B_3 \), \( B_4 \), \( B_5 \) be the broadcasts received by \( N_i \) (Outputs of algorithm 1).

Node \( N_i \) starts with saving broadcasts positions, and then calculates all distances separating it to each diffusion (Lines 3, 4 of algorithm 2). This allows us to draw up the table 2.

Table 2 Positions of broadcasts received by \( N_i \)
Full size table

From calculated distances (Outputs of algorithm 2) and send positions of beacon message (Outputs of algorithm 1 ), we construct following circles (Lines 2-4 of algorithm 3):

  • \( Circle\left( B_{1},\widehat{d_{1}} \right) \)

  • \( Circle\left( B_{2},\widehat{d_{2}} \right) \)

  • \( Circle\left( B_{3},\widehat{d_{3}} \right) \)

  • \( Circle\left( B_{4},\widehat{d_{4}} \right) \)

  • \( Circle\left( B_{5},\widehat{d_{5}} \right) \)

Figure 3 illustrates the different constructed circles, next we build the Table 3 from circles previously defined by treating the lines 5–7 of algorithm 3. We seek for pairs of intersection points (\( Couple_k \left( IP_1,IP_2 \right) \)) of all circles two by two (the abbreviations are explained in Table 1), by excluding combinations of circles having distance between their centers less than 10 m. Given that no distance is less than 10 m, all couples will be kept. Subsequently, we calculate the distance between intersection points composing each pair. The pair with the largest distance will be then selected as the candidate point (pair highlighted in bold)

Fig. 3
figure 3

Geometric illustration of position calculation

Full size image
Table 3 Coordinates of the different intersection points
Full size table

\( Couple_{Max}\left( Cand_1,Cand_2\right) = Couple_k \left( IP_1,IP_2 \right) \) with distance between \( IP_1 \) and \( IP_2 \) is the greatest one ( couple number 8 in Table 3 ). Consequently, the first candidate point, \( Cand_1 \) is the point whose coordinates are (85, 68; 240, 41) , and the second candidate point \( Cand_2 \) is the point whose coordinates are (121, 08; 156, 64)

The distance matrix \( MatDist\left( Cand_{1} \right) \) associated to the first candidate point is as follows: (by treating the line 8 of algorithm 3)

\( MatDist\left( Cand_{1} \right) = \begin{pmatrix} 2,49 &{} 38,90 &{} 14,04 &{} 3,02 &{} 2,88 &{} 17,45 &{} 2,24 &{} 11,62 &{} 21,27\\ 50,76 &{} 2,23 &{} 1,73 &{} 8,29 &{} 25,68 &{} 3,93 &{} 41,01 &{} 2,13 &{} 4,39\\ \end{pmatrix}\)

The weight of candidate point \( Cand_{1} \), denoted as \( Weight\left( Cand_{1} \right) \), is equal to the sum of minimums of columns of matrix \(MatDist\left( Cand_{1} \right) \). It is calculated as follows : (by treating the line 9 of algorithm 3)

\( Weight\left( Cand_{1} \right) =2,49+ 2,23+1,73+3,02+2,88+3,93+2,24+2,13+4,39\)

\( Weight\left( Cand_{1} \right) =25,03\)

Similarly:

\( MatDist\left( Cand_{2} \right) = \begin{pmatrix} 90,21 &{} 115,45 &{} 93,92 &{} 89,30 &{} 90,09 &{} 99,35 &{} 91,92 &{} 95,53 &{} 98,42\\ 91,19 &{} 91,9 &{} 91,42 &{} 83,12 &{} 80,28 &{} 92,3 &{} 64,93 &{} 91,88 &{} 92,82\\ \end{pmatrix}\)

$$\begin{aligned} Weight\left( Cand_{2} \right)&=90,21+91,9+91,42+83,12+80,28+92,3+64,93+ \\&\ \ \ \ 91,88+92,82 \end{aligned}$$

\(Weight\left( Cand_{2} \right) =778,87\)

We notice that \( Weight\left( Cand_{1} \right) < Weight\left( Cand_{2} \right) \), consequently \( Cand_{1} \) will be selected for the creation of the point cloud. This cloud will be composed of points represented on Table 4. (by treating the line 10 and 11 of algorithm 3)

Table 4 Coordinates of the selected cloud of points
Full size table

The geometric center is obtained as follows: (the last step of our algorithm)

$$\begin{aligned} {\widehat{x}}&=( 83,8 +83,45+ 87,04 +84,03 +83,51 +81,76 +83,45 +83,55 \\&\ \ \ \ +81,29 )/9 \end{aligned}$$

\( {\widehat{x}}=83,54\)

$$\begin{aligned} {\widehat{y}}&=( 238,78+ 240,48+ 241,48+ 237,89+ 238,52+ 240,15+ 240,5 + 240,5\\&\ \ \ \ + 240,5 )/9 \end{aligned}$$

\( {\widehat{y}}=239,87\)

\( \left( {\widehat{x}},{\widehat{y}} \right) =\left( 83,54\ ; 239,87 \right) \)

\( \left( {\widehat{x}},{\widehat{y}} \right) \) represents the estimated coordinates of the position of nœud \( N_i \) as shown in the figure 4.

Fig. 4
figure 4

Geometric illustration of the cloud of point

Full size image

4 Simulation

To evaluate the performance of our proposed approach, the simulation has been implemented using Matlab. We have used the same parameters as those reported in Larbi-Mezeghrane et al. (2017). The detailed experimental parameters are set as Table 5 shows.

Table 5 Setting of simulation parameters
Full size table

We have compared our approach with trilateration method, both approaches calculate distance with RSSI, we have assumed that all RSSI measurement errors were independent zero-mean, unit-variance Gaussian random variables. In order to ensure a fair comparison, both approaches have been applied on same set of RSSI distance obtained for each node.

Fig. 5
figure 5

Variation of localization errors for the first 100 sensor nodes

Full size image

Figure 5 compares localization errors obtained by the two approaches for different sensor nodes of network. For the sake of clarity and readability in reading the graph, we reproduced the results of first 100 nodes only. We can clearly observe that our approach gives better results in terms of localization errors for practically all nodes. This can be explained by the fact of associating the multilateration, by exploiting all the received broadcast messages, and the constraints defined for the creation of the cloud of points, as well as the geometric center makes possible to determine an estimated position very close to the real position.

Fig. 6
figure 6

Average localization error vs number of broadcasts

Full size image

Figure 6 shows the average localization error (ALE) obtained by our approach comparing with trilateration, by varying the number of broadcasts. It is clear that our approach reduces considerably ALE and has a coherent behavior by augmenting the number of broadcast. By contrary, results obtained by trilateration were weaker with an unstable variation. We also notice the growing increase of ALE with the number of diffusions. This could be explained by the increasing of the number of broadcasts which makes the associated positions very close to each other and tends to make its collinear. This has a negative effect on the estimation of the position. Contrary, in our approach, a bad ALE is obtained when mobile anchor broadcasts a small number of positional messages, but when the number of diffusion increases ALE decreases. This comes down to the multilateration that allows us to exploit all the broadcasts received, in order to make the cloud of points denser and geometric center closer to the real position. But also to the constraints added in our algorithm to avoid the colinearity of broadcasts positions. When the number of broadcasts is not sufficient to localize all nodes of the network, our approach relies on neighbour nodes that were already localized (we name them pseudo anchor) to help unknown nodes for calculating their positions. This scenario solves a problem of unlocalized nodes, but the position is obtained with error accumulation. This is supported by Fig. 7, which illustrates the number of pseudo anchors participating in localization. We notice that this number is bigger in the first simulations and vanishes after a given number of broadcasts (\( \sim 125 \) broadcasts), the numbers coincide in the last two figures.

Fig. 7
figure 7

Number of pseudo anchors participating in localization

Full size image

Figure 8 compares both approaches to messages exchanged. We notice that when the number of broadcasts is small, our approach exchanges an important number of messages comparing to trilateration. This might be explained by the fact that when a node does not receives enough messages enabling him to calculate his position, trilateration requests at least tree neighbourds. On the other hand, with our approach, the node requests all its neighbors already localized, in order to obtain an estimated position very close to the real position. However, when the number of broadcast increases, unlocalized nodes have to contact their neighbours but use only mobile anchor broadcasts, which is reflected by a linear variation of messages exchanged with the number of broadcasts. Figures 9 and  10 confirm our interpretation in terms of messages exchanged in the network, by separating received messages from those sent. The number of sent messages is very important when the number of diffusion is small, then decrements with the increase of the number of diffusion until its cancellation. As for messages received, they follow the same pace as the messages sent when the number of broadcast is low, thereafter their number varies proportionally with the number of broadcasts.

Fig. 8
figure 8

Total number of messages exchanged vs Number of broadcasts

Full size image
Fig. 9
figure 9

Number of messages sent vs Number of broadcasts

Full size image
Fig. 10
figure 10

Number of messages received vs Number of broadcasts

Full size image

Figure 11 shows the variation of ALE according to the variation of communication radius of mobile anchor. We note that the results achieved by trilateration method vary with non-uniform way which is difficult to interpret, this stems from the fact that to determine the position of unknow nodes, trilateration method relies on three beacon messages only whatever the position of their sending, since no pre-selection is made. Conversely, with our approach ALE is reduced by increasing the communication range of the mobile anchor. This amounts to the number of nodes receiving the same broadcast that results in the construction of a denser cloud of points, and, consequently, an estimated position closer to the real position.

Fig. 11
figure 11

Average location error vs Communication range

Full size image
Fig. 12
figure 12

Average location error vs Number of nodes

Full size image

We note in Fig. 12 that the ALE obtained by our approach is pratically constant (\( \sim 0.5\) m) this means that ALE does not vary with the increase of the number of nodes in network. It can be concluded that our approach gives good results even in a dense network.

Fig. 13
figure 13

Number of localized nodes vs Communication range

Full size image

Figure 13 illustrates the relationship between the number of nodes localized by the mobile anchor by varying its communication range. We note that for a communication range of less than 25 m no node could be localized by any of the two approaches, but when the communication range increases (between 25 and 55 m) the number of localized nodes increases considerably. We notice that trilateration localizes more nodes compared to our approach, but for the same interval, Fig. 11 shows that the average localization error for trilateration reaches its maximum. In other hand, with our approach, certainly fewer nodes are localized but the accuracy is better (see Fig. 11). When the communication range takes values greater than 60 m, all the nodes of the network are localized by both approaches

5 Conclusion

In this paper, we have studied the problem of localization in WSN; we have proposed an approach by combining two methods, multilateration by exploiting all broadcasting messages to create the cloud of points, and geometric center to select the closer point of the real position. Mobile anchor with spiral trajectory and sufficient broadcasting messages enables all nodes to get enough information to estimate their positions effectively. The approach reduces significantly localization average error, as shown in simulation results. In the present work, few performance parameters are studied, but in the future work, we aim to study more performance parameters and compare the results with other works. It is also interesting to consider the behavior of our approach in real environments with limited resources.