Improved 3D localization algorithm for large scale wireless sensor networks

Improved 3D localization algorithm for large scale wireless sensor networks Rahma Mani 1,2 •Antonio Rios-Navarro 2 •Jose-Luis Sevillano-Ramos 2 •Noureddine Liouane 1 ÓThe Author(s) 2023 Abstract As localization represents the main core of various wireless sensor network applications, several localization algorithms have been suggested in wireless sensor network research. In this article, we put forward an iterative bounding box algorithm enhanced by a Kalman filter to refine the unknown node’s estimated position. In fact, several research efforts are currently in progress to extend the 2D positioning algorithm in WSNs to 3D that reflects reality and the most practical applications. Subsequently, we replace a large number of GPS-equipped anchors with a single mobile anchor. In our studies, we consider the type of range-free sensor network exploiting the wireless sensors connectivity. We assess the performance of our algorithm using exhaustive experiments on several isotropic and anisotropic topologies. Our proposed algorithm can fulfill the joint goals of algorithm transparency and accuracy for various scenarios by evaluating parameters such as localization accuracy whilst changing other simulation parameters such as the effect of communication range, mobile anchor node position and sensor node deployment topology. It has been proven by the results of the experiments that the proposed algorithm effectively reduces the location error without requiring more equipment or increasing the communication cost. Keywords Localization Mobility 3D Bounding_box Wireless sensor networks DV_Hop Kalman filter 1 Introduction The wireless sensor network is composed essentially of sensors capable to collect and transmit data autonomously. The sensors can be deployed randomly in a defined area to detect a phenomenon. The applications of this particular ad-hoc network, wireless sensor network (WSN), are invading many fields such as the IoT, IIOT, e-health, e-logistics, e-agriculture, etc. Some of these applications have potential, such as surveillance of natural parks, surveillance of nuclear power plants, forest fire detection, etc. The main purpose of almost all the applications in WSN is to determine when and where a marked event occurs which is considered an identifier of that occurrence. Some of the nodes constituting a WSN environment are considered anchors that have a stable source of location information via the global positioning system (GPS). For computational processing scenarios, we consider the advancement of power management strategies for better solutions in particular for low-power WSN using an alternative method than using several GPS devices for a low cost and computational effort. In this work, our main goal is to find an efficient algorithm to achieve highly accurate data and higher localizable nodes with lower computational effort, memory size and energy. We are concerned with the strategy of a mobile anchor node to reduce hardware costs. Our proposal is based on the bounding box approach to identify the possible location area of the unknown node. Also, the proposed approach &Rahma Mani [email protected] Antonio Rios-Navarro [email protected] Jose-Luis Sevillano-Ramos [email protected] Noureddine Liouane [email protected] 1 Electrical Engineering Department, University of Monastir, 5019 Monastir, Tunisia 2 Architecture and Computer Technology, University of Seville, 41012 Seville, Spain (0123456789().,-volV)(0123456789().,-volV) researchers have utilized a range of techniques including machine learning and neural networks [1–3]. Various types of fields deployed in WSNs require localization techniques to be used in different applications. Some applications such as healthcare treatment, environmental monitoring, and agricultural management require the deployment of nodes in three-dimensional (3D) irregularly shaped fields. The localization of sensor nodes in different types of fields is a challenge [4]. In 3D fields, network connectivity can be more diverse compared to the 2D scenarios and WSN boundary conditions become more important [5]. Rangefree localization algorithms are most appropriate for largescale WSNs since they do not require any additional hardware on the sensor nodes to be used to measure the radio signal characteristics. The most well-known of these algorithms are techniques based on hops [6]. These types of algorithms use only the connectivity between nodes to determine the minimum number of hops and subsequently to estimate the distance [7]. Hop-based techniques use the length of hops between sensor nodes and reference nodes for the estimation of the location. Also, mobile localization techniques do not need additional hardware and estimate the node site area sequentially. The localization with a mobile beacon in WSN was proposed in various research works in literature as a solution for sensor nodes to compute their positions in real time. In fact, the unknown nodes receive three or more signals from the same beacon node from different locations and calculate their locations by applying a trilateration or multilateration algorithm [8]. In this way, we are defining some of the popular range-free methods employed for localization for WSN with the presence of mobility. We can mention the most wellknown method Monte Carlo localization (MCL) algorithm proposed by Lingxuan Hu et al. [9]. Using one mobile anchor [10], the authors presented the mobile anchor centroid localization (MACL) algorithm for localization in WSNs. The described algorithm is based on radio frequency connectivity and the centroid method for preliminary localization via the single mobile anchor. The considered path planning for the localization process is spiral trajectory. The former algorithm produced acceptable results for some WSN deployment scenarios, but due to the filtering operation, integrated into the algorithm, it is possible to reject the effect of some anchor positions to improve the localization accuracy. In [11], the mobile anchor assisted localization algorithm based on regular hexagon (MAALRH) is presented. This method is designed based on the regular hexagon in 2D-WSNs which maximizes the ratio of localized nodes and minimizes the average localization errors. Moreover, for overcoming the irregularity of the communication range and the co-lin- earity problem, a boundary compensation method (BCM) is described. Furthermore, different path planning for a uses an infinite impulse response filter which is a Kalman filter that approximates the states of a dynamic system from a set of noisy or incomplete information. For wireless sensor network localization problem, the KF algorithm iteratively refines the positions determined by the bounding box algorithm (BBX) in order to improve the accuracy of the undetermined node positions. Actually, KF uses the dynamic model of the geolocation system, modeled by state equations and onboard sensor measurements, to obtain an estimate of the state vector that minimizes the covariance error. In effect, an important interest oriented to mobility that has a major role in such networks. The combination of mobile systems and WSNs creates what we will be working on, the mobile wireless sensor networks (MWSNs). In a large-scale network, the cost value is important for the application’s deployment. MWSNs help to solve this problem by decreasing the number of anchors which costs more than normal nodes. Therefore, every localization process needs an anchor node to provide information and references to unknown nodes. Consequently, using the range-free method, specifically, the connectivity process of all nodes estimates their inter-dis- tance via the calculation of the lowest number of hops. Thus, MWSN is capable of deploying a single anchor in the network and determining the positions of unknown nodes based on information about the number of hops and the path of the anchor. The mobile anchor node trajectory could be random or has a predetermined path planning. The purpose is to calculate the connectivity information and then try to compute the positions of unknown nodes using an iterative bounding box. Besides, using a highly utilized filter, Kalman Filter, to refine the localization process and improve localization accuracy. The rest of the paper is organized as follows: After the introduction in Sect. 1, the related works will be presented in detail in Sect. 2.As an introduction to our algorithm, we represent in Sect. 3 the basics of the Kalman filter in general. Section 4 is about the proposed algorithm. In Sect. 5, a comparative study between the experimental results has been presented and analyzed. Finally, we discuss this work and conclude this paper and we put forward the future work in Sect. 6. 2 Related works Wireless sensor networks (WSNs) have become increasingly prevalent in the Internet of Things (IoT) and Industrial Internet of Things (IIoT) due to their ability to exploit the capabilities of 5 G networks. Many research efforts have been focused on addressing various challenges related to WSNs, including location tracking, routing, task allocation, spectral optimization, energy optimization, and more. To improve the performance of these networks, mobile anchor is presented like HILBERT, CIRCLE and S-CURVE. The research work in [12] presents a mobile anchor node for localization using the trilateration method and path planning choice with two objective functions such as the reduction of localization errors and minimizing the energy consumption for WSNs. Moreover, the inter-dis- tance between the mobile anchor and the unknown nodes is estimated with the RSSI indicator. In addition, the localization errors are analyzed for five trajectories for mobile anchors like SPIRAL, SCAN, DOUBLE SCAN and HILBERT path. The authors of the paper [13] proposed a collaborative localization algorithm with bounding restrictions for wireless mobile networks. The proposed technique implies trajectory prediction using Newton’s polynomial interpolation and bounding box. Earlier, most localization techniques were based on numerical computation of many network parameters such as transmitter or receiver power, network connectivity information, transmission range, transmission and reception time, etc. These parameters have many restrictions, such as environmental conditions and complications related to the environment. The Monte Carlo boxed (MCB) [14] localization method has been proposed by Baggio Aline and Koen Langendoen where the samples are defined by constructing a box on the basis of MCL. This algorithm accelerates the design of position samples, which improves localization accuracy. Many improvements of MCB are presented in the literature, such as RSSI-MCB [15], IMCB [16] and MCB-PSO [17]. Specifically, in range-based cases, many localization techniques in the literature have concentrated on minimizing localization errors during the localization operation. In [18], the uncentered Kalman filter (UKF) and particle filter (PF) were presented based on the Kalman filter (KF) for localization. The published localization technique can be used for any kind of wireless sensor network problem and in particular for Autonomous robot localization. 3 The basics of Kalman-filter The Kalman filter is a method to estimate parameters of a system that evolves in time from noisy measurements. This filter can be found in many fields related to signal processing, radar, image processing, etc. An example of the use of this filter could be the determination of the position and speed of a vehicle from GPS data provided by several satellites. The power of this filter is its capability to fix errors and forecast parameters, both from the sensors and from the actual model. In fact, in order to implement a Kalman filter, the system of which we want to estimate its parameters must be modeled in a linear way. Variants of the Kalman filter exist to take into account non-linear models. In a conventional approach for estimation, such as the least squares method, a single error in the modeling of the system necessarily leads to an error in the estimation. The strength of the Kalman filter is that it integrates an inaccuracy element on the actual model, making it possible to obtain correct estimations in spite of modeling errors (as long as these errors remain reasonable). Another strength of the algorithm is its capacity to determine the average error of its estimate. Indeed, the Kalman tool provides a matrix of the estimated parameters, as well as a covariance matrix of the error. This provides information about the accuracy of the estimate, which might be valuable in many different purposes. Another advantage of the Kalman filter is that the convergence of this error is guaranteed. The Kalman filter process can be divided into two steps. The first step of prediction is according to the model of the system. For this, the Kalman filter uses the previous estimation of values for the system’s parameters and errors and predicts the new parameters and errors based on the system model. The second step will update this prediction with the new measurements. These measurements will allow obtaining an estimate of the parameters and the error from the prediction model. The whole process is illustrated in Fig. 1. If the model contains errors, this stage of the update will make it possible to correct them. 4 The proposed algorithm Kalman filter is generally widely used with range-based methods for filtering the Received Signal Strength Indication ‘RSSI’ signal to properly estimate distances. Indeed, in our case, it is important to carefully consider features of the hop-based methods such as network coverage, node mobility and communication range, in order to ensure that the range-free mobile anchor sensor network is able to effectively cover and monitor the large scale domain, as well as achieve accurate nodes location in different scenarios. In fact, we propose a novel localization strategy for wireless sensor networks with a mobile anchor node, utilizing a combination of a Kalman filter and bounding box localization algorithm (BBLA-KF). Our approach utilizes connectivity measurement and the nonlinear bounding box techniques to identify the bounded possible location zone for the unknown nodes, and then applies the kalman filter to minimize uncertainty in the connectivity process and achieve high levels of accuracy in determining the bounded-boxes. This innovative approach holds the potential to significantly improve localization accuracy in wireless sensor networks in isotropic and anisotropic 3-Dimensional fields. 4.1 Mobility method The WSN exploits one mobile anchor that moves in any direction following a planned path in the deployment area. The mobile anchor node can be a vehicle, a robot or a drone, etc., which is equipped with GPS. As in our case as illustrated in Fig. 2, the mobile anchor try to detect the occurrence of target events inside the region of interest and then assess the positions of the target events. The mobile anchor node is able to tackle the problem of the low density of anchors. Communication in a mobile network does not cost much because only one anchor communicates its position information. Subsequently, the rest of the nodes assess their positions using the information provided by the mobile anchor. At each position kof the mobile anchor, as it travels through the network, the anchor node transmits a packet to its neighboring nodes to inform them of its current position (xMk,yMk,zMk) and the minimum hop-count Hk, where k¼1;2;...N. Figure 3is a model illustrating an example that calculates the hop count of the unknown node UN6. 4.2 Mobile 3D bounding box algorithm 3D- MBBX The bounding box algorithm makes reference to the construction of a Monte Carlo box (MCB) with a range of khops considered. Using a mobile anchor for the localization process is a good alternative to the use of multiple anchor nodes and reduces the complexity of the wireless Fig. 1 The Kalman-filter algorithm Fig. 2 Localization provided by mobile anchor node sensor network. Each time the anchor node travels in the network, it distributes its information to the connected unknown nodes. With repeated occurrences of a moving anchor, unknown nodes recursively approximate their detection area with a rectangular bounding box and enhance location accuracy over time. The bounding box proposed in our algorithm uses cubes to make an estimate of the locations of the unknown node extended over the 3D structure of the sensor nodes. Figure 4shows the principle of the moving bounding box algorithm. We notice that each unknown node possesses its own unique search area computed by the anchor in its transmission range. The purpose of using the bounding box is to determine the search space of the unknown node, which is intended to minimize the complexity along with the computation time compared to the trilateration method. Let us regard a connectivity-based wireless sensor network composed of Nnnodes that are distributed randomly in the area of interest. The communication range of each sensor node is set equal to Rand the connected sensor nodes are all networked. As with the original DV-Hop algorithm, the minimum number of hops between the nodes and the mobile anchor node is estimated. The 3D bounding box method searches the possible area where the unknown node can be placed. Network connectivity measurement and bounding box localization method are used to identify the bounded possible location zone. The 3D bounding box method algorithm exploits cubic shapes as an alternative to spherical shapes. The 3D-MBBX limits the possible area of a node’s location. In Fig. 4, we differentiate between the MQkanchor boxes and the QNbounding box. For each position of the moving anchor Mk, an anchor box MQkis set as a cube whose center lies at the position of the anchor node (xMk,yMk,zMk), with edges of size 2 hMk Rwhere hMk is the minimum number of hops between the mobile node Mkat each position k¼1;2;3...Naand the unknown nodes. The coordinates of the anchor box MQkare defined by the following system of equations: x MK ¼xMK hMK R xþ MK ¼xMK þhMK R y MK ¼yMK hMK R yþ MK ¼yMK þhMK R z MK ¼zMK hMK R zþ MK ¼zMK þhMK R 8 > > > > > > > > < > > > > > > > > : ð1Þ For each anchor node MK, we define the box range MQk which defines the location of the unknown node as follows: MQk¼ x Mk xþ Mk y Mk yþ Mk z Mk zþ Mk 2 6 4 3 7 5ð2Þ The bounding box Qkdetermines the intersection of all Fig. 3 Flooding phase and hop-count values Fig. 4 3D bounding box localization method for 3D- WSN anchor boxes MQkvia the Max-Min algorithm as mentioned in the following form: Qk¼ maxðx MK Þminðxþ MkÞ maxðy MK Þminðyþ MkÞ maxðz MK Þminðzþ MkÞ 2 6 4 3 7 5ð3Þ So let Qkbe the bounding box of an unknown node UNi where iis between 1...Nn. Subsequently, the node will upgrade its bounding box using the constraint set by the anchor Mkwhen the anchor moves to Mkþ1at position (xMkþ1,yMkþ1,zMkþ1). The recursive rules for updating the bounding box are given by: Qk¼MQ1\MQ2...MQk1\MQk;8k¼1...Na ¼Qk1\MQk ð4Þ then, Qk¼ x kxþ k y kyþ k z kzþ k 2 6 4 3 7 5ð5Þ The final location of the unknown node UNiis then calculated as the centroid of the resulting Qkbounding box. Afterwards, the measured location Xmes ¼ ðxmes ;ymes ;zmesÞof the unknown node UNiis yielded by the centroid of the bounding box of Qk.: Xmes ¼1 2 110000 001100 000011 2 6 4 3 7 5 xþ x yþ y zþ z 2 6 6 6 6 6 6 6 6 4 3 7 7 7 7 7 7 7 7 5 ð6Þ 4.3 Kalman filter refinement process The Kalman filter represents an optimal algorithm to predict the location of the unknown nodes in the presence of noisy measurements. The Kalman Filter is then used to minimize uncertainty produced by the connectivity process. Indeed, through time, for each anchor node position, the Kalman filter refines the measured coordinate of the unknown node position Xmes kwhich is determined by the mobile bounding box localization approach with the anchor positions Mkand the covariance of the perceived noise. The Kalman filter recursively approximates the unknown node position Xkthrough the discrete-time equation of state: Xk¼AXk1þwkð7Þ wherein Xk¼ðxk;yk;zkÞTis the approximate position of the unknown node when the anchor is at station k, the vector of process noise wkconsiders the perturbations on the position of the unknown node. Similarly, the noise of the process adopts a Gaussian distribution modeled by a random noise vector of mean zero and a covariance matrix Nk. In this scenario, we consider the position of the unknown node as fixed and unaltered during the localization process, so the value of wkis null. The transition matrix A33= Identity Matrix. For this system, the measurement equation is visualized as follows: Zmes k¼HXmes kþvkð8Þ vk Nð0;RkÞwhere Xmes k¼ðxmes ;ymes ;zmesÞTis the measurement vector given by the moving bounding box process Qk¼Qk1\MQkwhich estimates the measurements at position kof the anchor in which Xmes kis the centroid of Qk. This step is posterior to the flooding phase where the hopcounts between anchor Mkand unknown nodes are found. His the observation matrix with H33= Identity Matrix and vkis the vector of observation noise supposed to be a normally distributed vector of random variables with zero average and covariance matrix R. Considering the two models the prediction equation and the update equation, the Kalman filter algorithm iteratively follows the evolution of the state via the following flowchart (Fig. 5). 5 Simulation results and discussion The performance evaluation of our BBLA-KF algorithm is performed by studies in the case of a 3D-WSN for an isotropic shape and in the case of a 3D-C form for an anisotropic shape. The impact of the change of the 3D- WSN properties on the results of the localization is analyzed by evaluating the average localization error (ALE) that is presented by the next expression: ALE ¼PN 1ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi ðxk;mes xkÞ2þðyk;mes ykÞ2þðzk;mes zkÞ2 q RN ð9Þ This section presents some metrics that compare our proposed method’s performance with other methods in different situations. Performance measures are produced by simulation through the MATLAB software, the results are compared to other algorithms of localization like RRBL [19], OIDVHop [20], PERLA [21], I3D-DVLAIN [22] and DV-Hop-3D [23]. These algorithms are selected as a combination of the classical and the latest hop-based methods. Consequently, we evaluated the reported BBLAKF localization algorithm at different isotropic conditions and node densities, following a similar simulation methodology, albeit with more in-depth analysis, to that used in [24] for a simpler two-dimensional protocol. In all our experiments, we consider that 400 sensor nodes are uniformly and randomly distributed in a detection area of 100 m100 m100 m where there are no obstacles and considering always a communication range error between 0–10%. A mobile anchor node is set up to handle the location of unknown nodes. The trajectory of the mobile anchor node is considered a random waypoint (RWP). In our simulation case, the positions of the mobile anchor are considered as a set of virtually fixed anchors. 5.1 Experimental analysis of positioning We use MATLAB to build our sensing area, in order to follow up on the point that all nodes are able to be located. We distribute 340 unknown nodes and 60 anchor nodes randomly and uniformly in the deployment zone. Nodes distribution is shown in Fig. 6, where yellow stars represent anchor node positions, and red (*) represent unknown nodes. We examine our method in the environment shown in Fig. 6. Then, we get the result of MATLAB simulation shown in Fig. 7, where (*) is the true node location and (o) the estimated location. From the graph, we can see that the BBLA-KF method can locate the unknown nodes very well, and give a higher precision. Figure 8is the result obtained after conducting a number of tests for evaluating the convergence of the BBLA-KF algorithm towards the real positions. From the figure, we can see the efficiency of our proposed algorithm to converge. Figure 9give the convergence of ALE over the number of iterations. This behavior may be due to the use of the Kalman filter in position adjustment, which utilizes a set of observed measurements through time, including statistical noise and other imprecisions, and generates estimates of unknown variables that tend to be more precise. Figure 10 shows the location error of all unknown nodes. It can be seen that the biggest error does not exceed 7 m equivalent to 40% of R, communication range. The error range is acceptable for mobile WSN Localization. 5.2 Comparison of the localization accuracy of different localization techniques Following, we present some simulation results that compare the localization accuracy performance of our proposed algorithm BBLA-KF versus RRBL, OIDVHop, PERLA, I3D-DVLAIN and DV-Hop-3D. We perform simulations to compare the performance in the same scenario set in Sect. 3. The I3DDVLAIN, OIDV-Hop, PERLA, and DV- Hop-3D algorithms were run for one hundred aleatory displays and the percentage of localization error for all trials is shown in Table 1. Compared to other existing algorithms, the results of our algorithm are better. When we look at the average value at the end of 100 trials, we find that BBLA-KF has an average of 23% while I3D- DVLAIN has an average LE of about 25%, DV-Hop has about 37%, OIDV-Hop has about 39%, and PERLA has about 35%. The resulting localization error of BBLA-KF is the lowest among the five techniques compared. This shows that our newly proposed algorithm is much more accurate than the other algorithms. We may justify this with the fact that our proposed algorithm is built on both the bounding box method and the Kalman filter to match the estimated position. Therefore, BBLA-KF performs better in terms of localization accuracy. Fig. 5 The proposed BBLA-KF algorithm 5.3 Influence of the variation of the number of nodes We notice that the ALE for BBLA-KF is smaller than that of I3D-DVLAIN, OIDV-Hop, PERLA and DV-Hop- 3D for the same value of the total number of nodes. The ALE for DV-Hop-3D, OIDV-Hop, and PERLA decreases slowly as compared to BBLA-KF. The grade in ALE is very significant from 100 to 300 nodes for BBLA-KF, which means that the rate of ALE improvement was elevated at lower node densities and the variation in ALE was decreased at greater node densities. Also, there is a fall of around 40% in ALE for BBLA-KF as compared to DV- Hop-3D and a fall of 20% with respect to I3D-DVLAIN, as Fig. 6 3D-WSN nodes distribution Fig. 7 Localization results of our proposed algorithm The performance of the presented algorithms is evaluated for various node densities in 3D fields. The number of nodes (anchor nodes and unknown nodes) is increased from 100 to 800 and the ratio of reference nodes is kept at 15% with a communication range of 18 m. The simulation parameters are presented in Table 2. The simulation results of the influence of the number of nodes are illustrated in Fig. 11. seen in Fig. 11. Figure 12 gives the cumulative distribution functions (CDFs) of the average localization error for different WSN densities. For example, in this figure, we notice that for 100 nodes, 14% of the unknown nodes are localized with an error less than 0.25 of the communication range ‘‘R’’, while for 200 nodes, only 42% of the unknown nodes are localized with an error inferior to 0.25R. However, for 400 nodes the localization error is 91% and for 800 nodes, all the unknown nodes are localized with an error less than the previous error range. Next, Table 3 resume the CDFs of localization error for different number of nodes. We can interpret from the Table 3that for the case of 100 nodes, there are some nodes non-localizable which is explained by the fact that the localization error is greater than the communication range. We also find that as the number of nodes decreases, the CDFs tend to decrease. This may be due to the growth in network connectivity, which is intended to give an accurate estimate of the distance between nodes in large-scale WSNs. In conclusion, we can say that increasing the density of nodes improves the performance of the algorithm by improving the accuracy. Fig. 8 Convergence of BBLAKF algorithm towards the real positions Fig. 9 Average localization error of unknown nodes over the number of iterations Noureddine Liouane is professor in the Engineering Department at the ENIM-Monastir. He received a MSEE degree in 1988 from the ENSET at Tunis University and the Ph.D. degree from Ecole Centrale de Lille, France in 1998. His research interests include evolutionary optimization methods for events systems, computer science and operational research.