# Low-Complexity Localization and Tracking in Hybrid Wireless Sensor Networks

Authors: S. Kianoush; E. Goldoni; A. Savioli; P. Gamba
Journal: ISRN Sensor Networks
 (2012)

---

## Abstract

Localization in Wireless Sensor Networks (WSNs) is an important research topic: readings come from sensors scattered in the environment, and most of applications assume that the exact position of the sensors is known. Due to power restrictions, WSN nodes are not usually equipped with a global positioning system—hence, many techniques have been developed in order to estimate the position of nodes according to some measurements over the radio channel. In this paper, we propose a new technique to track a moving target by combining distance measurements obtained from both narrowband IEEE 802.15.4 and Ultrawideband (UWB) radios, and then exploiting a novel speed-based algorithm for bounding the error. This process is applied to a real dataset collected during a measurement campaign, and its performance is compared against a Kalman filter. Results show that our algorithm is able to track target path with good accuracy and low computational impact.


---

## Body

## 1. Introduction

A Wireless Sensor Network (WSN) consists of a number of autonomous elements spatially distributed in an environment to monitor physical parameters, detect events, or track objects. These core elements of a WSN are called nodes, and each of them has a radio transceiver, a microcontroller, and a power source like an energy harvester or a battery. In addition, a node is connected to a number of sensors, and the acquired values are cooperatively processed and delivered wirelessly through the network. Size, energy, and cost constraints of the nodes result in corresponding limits on the available resources, namely, memory, communications bandwidth, and computational power—these limits must always be considered while developing and designing new algorithms.The development of WSNs was initially motivated by military applications, such as battlefield surveillance, and in the last years they have received considerable attention from many computer science, electronics, and telecommunications researchers. Nowadays, WSNs are used in many industrial and consumer applications, such as home automation, industrial control, structural monitoring, pedestrian navigation, and assets tracking. In all these applications, positional information about one or more devices of the network is a crucial aspect and has motivated a lot of research efforts. A common approach for estimating the unknown position of a sensor node is to exploit ranging information obtained from some fixed-position nodes, hereafter referred as “anchors” [1, 2].Distance estimation between two antennas is made possible by the received radio waves feature, and can be done in different ways. For example, the strength of the received signal may be used to estimate distance, assuming to knowthe transmitted power and the signal attenuations. Differently, the travel time of a pulse from a transmitter to the receiver can provide a distance estimate by exploiting the propagation speed of the radio signal—this latter method usually provides accurate range estimations, but requires precise synchronization among the nodes [3].The algorithms used to estimate the position from range measurements—such as Min-Max, Multilaterate, Maximum Likelihood, and so forth—are very well known and widely investigated [4]. Unfortunately, many applications are located in indoor scenarios, where the radio channel is mainly unpredictable due to signal's reflections against walls, floors, and ceilings, which cause multipath phenomena [5]. In scenarios with static or slowly changing node positions, this interference leads to stochastic variations of the radio signal behavior dictated by a path-loss model [6], and these random effects result in large localization errors [7].In this paper, we will use two geometrical based localization algorithms—MinMax and Multilateration—in order to estimate the target position, and we propose two novel algorithms for fusing efficiently the range information provided by the narrowband IEEE 802.15.4 radio standard and an Ultrawideband (UWB) localization system. Furthermore, we will investigate an effective way to improve localization accuracy exploiting the estimated target speed. This velocity-based tracking filter, in opposition to the current research trends, requires minimal information to be tuned, has minimum computational impact, and features enough accuracy to be employed in a lot of practical, noncritical applications.The paper is organized as follows: Section2 shows an analysis of some related works, while Section 3 describes the proposed methodology used to estimate the positions. In Section 4 the experimental setup, tests results, and their analysis are provided, and in Section 5 conclusions will be drawn.


## 2. Related Work

Localization in WSNs is a well-investigated topic, and many works can be found in literature [2, 3]. Nonetheless, it is still an open issue: noise and multipath phenomena have a high impact on low-power radio signals, leading to severe performance degradation in indoor environments. The position of a target node can be computed using its distance from some fixed anchor nodes—radio signal strength or time of arrival measurements are usually exploited in sensor networks to obtain an estimation of the amount of space between two antennas [7]. These measurements feed a geometry or statistical based algorithm that determine the final position. Some of these algorithms are very accurate in finding the position, but might be really computational intensive—hence, approximated variants algorithms have been developed to reduce the complexity, representing a trade-off between accuracy and complexity [2, 6].A way to improve ranging accuracy consists of using ancillary radio hardware, such as multiple and/or directional antennas [8], and equipping them with an absorbing plate in order to bound reflections and multipaths. The results obtained in [9, 10] have demonstrated that hardware upgrades can lead to satisfactory results.Other interesting works focused on channel modeling and anchor nodes density, showing that an accurate estimation of the target position can be achieved by knowing the behavior of the radio channel in the specific environment [3, 11]. These solutions are generally more energy demanding or require dedicated hardware, since more expensive and complex devices are usually needed. Thus, there is still a lot of interest in studying how to achieve accurate radio-based localization without using adhoc hardware or tying the system to a single environment.If the target is moving, raw positions coming out from the localization algorithm can be fed into a dedicated tracking procedure. This step is required for filtering out noisy measurements and follow the actual trajectory of the target as close as possible. These filters might exploit additional data coming from different sources, such as inertial sensors or topological information about the environment. Once again, some of the proposed tracking filters are very accurate but exploit sophisticated, time-consuming algorithms that cannot be easily run over simple sensor nodes [13].In this work, we want therefore to analyze how it could be possible to design a low-complexity tracking system for WSNs. Moreover, it is assumed that UWB radios provide accurate ranges with an error below a few centimeters, experimental results show that this is not always the case [14], due to the presence of walls and time synchronization issues among the nodes. For this reason, the proposed approach includes fusion of range information coming from different radio technologies as a processing step prior to the tracking routine.


## 3. System Description

In recent years, there has been a growing attention to cognitive networks [15]. Differently from traditional devices, a cognitive node is able to exploit different portions of the spectrum and different modulation techniques according to channel conditions. To this aim, special type of radios able to autoreconfigure their transmitting hardware at software level have been deeply investigated for the next generation of mobile devices. This capability is obtained using a special kind of radio, called Software Defined Radio [15]: in such devices the behavior of the radio can be adapted on the fly, so that more than one standard can work over the same device. This particular radio hardware might be used in WSN too. A possible application of such hardware might be a sensor node supporting both narrowband and UWB communications by switching between the IEEE 802.15.4 and IEEE 802.15.4a standards when needed.For this reasons, a node able to communicate using different radio frequencies might obtain distance information in more than one way, such as through the ToA of an UWB signal and the RSSI value of an IEEE 802.15.4 transceiver. The outcome would be a set of estimates having different accuracies and time resolutions. Hence, in this work we propose a method to fuse measurements coming from multiple radio sources. Specifically, we considered Time of Arrival (ToA) values from UWB radios and the Received Signal Strength Indicator (RSSI) provided by IEEE 802.15.4 narrowband RF modules, although this method is technology-agnostic and could be applied to other ranging techniques. We also want to show the benefits of a simple algorithm to improve positioning accuracy in a radio-hybrid WSN tracking system without increasing the computational complexity. To this aim, we implement a novel velocity algorithm, which relies on the speed of the target node to bound the positional error.


### 3.1. Radio Ranging

Nowadays, most of existing hardware platforms for wireless sensor networks use radio modules complying with the IEEE 802.15.4 standard. This standard was designed specifically for low-power and low-data rate communications in Wireless Personal Area Networks (WPAN), and it defines the Physical (PHY) and the Medium Access Control (MAC) layers [3].The original IEEE 802.15.4 standard was released in 2003 and later revised in 2006, and it operates in three possible unlicensed frequency bands: 868 MHz (Europe), 915 MHz (North America), and 2.4 GHz worldwide. The original version of the standard uses a physical layer based on Direct Sequence Spread Spectrum (DSSS) technique, having data rates from 20 kbps up to 250 kbps. Coexistence of multiple networks is enabled by frequency multiplexing, which divides each band in channels. The 2006 revision has improved the data rates for the lowest bands, although 250 kb/s is still the maximum achievable bandwidth, and additional modulation schemes has been defined. The majority of commercially available off-the-shelf radio modules operates in the 2.4 GHz band, relies on DSSS modulation, and transmits at 250 kb/s over 2 MHz wide channels.The IEEE 802.15.4 standard requires the PHY layer to provide an 8-bit integer value as a linear estimate of the received signal power, expressed in dB—this value is commonly known as the Received Signal Strength Indicator (RSSI). The idea behind this indicator is that the transmission power at the sender directly affects the received strength—hence, according to Friis free space path loss law, RSSI decreases quadratically with the distance [6]. However, in real-world deployment the ideal distribution is not always applicable: the radio signal is affected by a lot of degrading effects, such as multipath and shadowing. All these phenomena deeply impact the accuracy of RSSI measurements, often resulting in inaccuracies in the estimated distance [8].In recent years, Ultrawideband (UWB) technologies have emerged as a viable solution for short-range wireless communications in Personal Area Networks. Compared to narrowband modulations, like the one used in IEEE 802.15.4, UWB increases significantly the robustness of the transmissions spreading the signal over a very large bandwidth—usually 500 MHz. In addition, due to the large bandwidth operations, UWB signals feature very fine-grained time resolutions. Robustness and high time resolution are key factors for a precise localization, and this has motivated the definition of an UWB-based physical layer for wireless sensor network alternative the IEEE 802.15.4, called IEEE 802.15.4a.The IEEE 802.15.4a standard has been released in 2007. Its UWB physical layer exploits an Impulse-Radio approach to transmit short pulses and to provide accurate ranging capabilities [3]. Specifically, it provides primitives for precision ranging using Time of Arrival (ToA): the travel time of the signal from the transmitter to the receiving node is used to measure the distance between the two antennas. The UWB physical layer of IEEE 802.15.4a allocates frequencies in three ranges: a sub 1 GHz band, a band between 3 and 5 GHz, and a third band between 6 and 10 GHz. All these bands are divided into channels having a bandwidth of 500 MHz or more, providing a minimum data rate of 850 Kbit/s and range estimation errors below 1 meter under line-of-sight conditions.Hence, while RSSI in IEEE 802.15.4 is greatly affected by multipath fading and channel variability, TOA-based ranging with UWB is more robust but has strict requirements in terms of clock synchronization and processing time.


### 3.2. Hybrid Positioning

Range measurements coming from the radios, regardless the way they are obtained, may be used as inputs for algorithms, which compute the position of the target node. These algorithms can be based either on geometry considerations or statistical methods. We chose two simple geometric techniques: Multilateration and Min-Max. Their selection was driven by their wide use in literature because of their low complexity and good performances [3, 8].Min-Max is a deterministic localization algorithm characterized by a low-computational complexity—it estimates the position of the target within an area delimited by maximum and minimum distances from the known anchors. Range measurements of relative distances between the agent and the anchor nodes are considered, and these distances are used to create squares surrounding the anchors. The estimated target position is the center of the intersection of these bounding boxes—this point can be easily computed by finding the maximum of all the lowest values of the coordinates and the minimum of all maximum values.Multilateration is a simple range-based, decentralized localization algorithm based on geometry principles. An unknown node has position(x,y), and ranges are defined as the estimated distances—obtained for example by TOA or RSS measurements—between the unknown node and N anchor nodes at known coordinates (xi,yi), where i=1,2,…,N. In presence of error-free distance estimations, the ith anchor defines a circle centered in (xi,yi), with radius di, and having the target point (x,y) belonging to the circumference.  The intersection of three circles is sufficient to determine the position of the target node. However, the intersections can be zero or more than one if range measurements are affected by errors, and some geometrical rules must be used to cope with this issue [8, 16].Both localization algorithms need at least three measurements to produce an estimate. However, increasing the number of anchors does not continuously improve the accuracy. On the contrary, adding noisy values may degrade the output [6, 8]. Hence, our system uses only the 6 smallest range data and discards the other values at each step. The assumption underlying this choice is that higher distances are less accurate: this is consistent with the exponential path-loss model. Additionally, this assumption makes perfect sense in an indoor environment, where higher distances might increase the probability of having walls and other obstacles between the anchors and the node.Once the best data for each source have been selected, the measurements need be fused. We have identified two possible techniques for combining the different data coming from our cognitive device: the first method is called Partial-mix (hereafter P-mix) while the second will be referred to as F-mix, which stands for Full-mix.In P-mix the localization algorithm is executed independently for the two sets of range measurement, resulting a set of two points. The fused estimated position is the barycenter of these points—this approach may be generalized to an arbitrary number of measurement sets. In our case, we have only a pair of radio source, and the final position is the intermediate point between the two positions.In F-mix, all the measurements available are combined together, regardless the source—then, according to our criteria, the values are sorted and the best 6 values are used to produce a single estimation.P-mix can be extended to include weights in the calculus of the barycenter, for example, to give more credit to one range system if we know that it will always be more accurate than the others in some areas of the environment. On the contrary, F-mix is more flexible and can be used with no variations in presence of range technologies that provides value with different frequencies. Moreover, F-mix is more robust: if all the anchors belonging to one source are really distant and unreliable, their results are automatically discarded while better values are used.


### 3.3. Velocity-Based Tracking

Multipath phenomena or issues in the leading-edge detection method on UWB signals may impact the ranging process, reducing the accuracy of the estimation. Similarly, walls or other obstacles may change the path-loss model used to infer range from RSSI data. Hence, the estimated trajectory of a moving target, defined as the temporal sequence of positions provided by any localization algorithm, is likely to be affected by some degree of uncertainty.To cope with this problem, a proper tracking algorithm is often employed to predict the path of the target and to cancel out noisy estimations [2]. This activity presents a number of challenges, for example, multimodal sensing, signal processing, and data fusion in real-time. Belief Propagation, Kalman, and Bayesian/Particle filters are the most used types of schemes for tracking in WSNs, but they not always meet the limitations imposed by technology in terms of energy and computational capability [17, 18]. This motivated our quest for a low-complexity algorithm, based on simple mathematical operations and able to track a target node without requiring any information about the surrounding environment or additional data exchange among anchors.Our tracking technique relies on the history of movements and a linear prediction model of the speed. The current position computed by our method is a function of the current coordinates and the previousN values of the velocity. In addition, it responds as an all-pass filter to decelerations, while it has the typical low-pass behavior of a finite impulse response filter to increases the speed. The latter feature is used to bound the movement of the target, reducing the impact of noisy positions significantly far away from the real ones. This filter has only one parameter, which is the amount N of past positions that are used in combination with the current estimation. The higher the value of N is, the more important the past history will be. We set all the weights of the window to the same value, although the filter could be easily modified to give more importance to recent estimations than the older ones.A possible scenario for this approach is, as example, pedestrian tracking. A walking person may have an average speed constant over time or can constantly accelerate, thus linearly varying his/her speed. The window sizeN should be kept small if the target is expected to vary frequently its speed, such as while visiting an exposition, while the window might be increased if the person is doing jogging in a park and has a constant speed. We also accept that the person can suddenly stop for some reasons: in this case, since the position does not change, the algorithm ignores previous speed estimations and sets the last coordinates as the actual ones.The estimation of the current position proceeds as follows: implementing a moving window of sizeN, a buffer stores the latest N estimated target positions Pi, and their corresponding time interval ti. A first velocity guess can be obtained by exploiting these values according to
(1)v^(i)=∑j=1N‖Pi-j+1-Pi-j‖∑j=1Nti-j,After having estimated the velocityv(i), we constrain the maximum displacement to a circle centered in xi with radius ri=v(i)×(Ti+1-Ti). A refined guess of the subsequent target location is obtained according to
(2)(x-xi)2-(y-yi)2=ri2.The estimation is eventually obtained through a comparison of the raw position provided by the localization algorithm and the bound provided by (2).As shown in Figure1, two situations are possible: if the estimated point falls inside the bound, it is assumed that this new position is accurate and it is taken as it is. On the other side, if the newest estimation falls outside the bound, then the measure might be affected by noise: the actual position is assumed to be along the direction of estimated point, but over the bound and not farther.The new estimated point is taken as is if it falls inside the bound (a), while it is moved over the circular bound if it is outside (b).
(a)
(b)A formal description in polar coordinates of the algorithm that provides the new positionP at the step i might be
(3)P^i=(l,θ),
where θ and l are defined, respectively, as
(4)θ=atan2(yi-y^i-1xi-x^i-1),(5)l={‖Pi-P^i-1‖,l<RbRb,l≥Rb,
and value Rb of the bounding radius is
(6)Rb=v-i,i-N⋅ti=ti⋅∑j=1Nli∑j=1Nti-j.


## 3.1. Radio Ranging

Nowadays, most of existing hardware platforms for wireless sensor networks use radio modules complying with the IEEE 802.15.4 standard. This standard was designed specifically for low-power and low-data rate communications in Wireless Personal Area Networks (WPAN), and it defines the Physical (PHY) and the Medium Access Control (MAC) layers [3].The original IEEE 802.15.4 standard was released in 2003 and later revised in 2006, and it operates in three possible unlicensed frequency bands: 868 MHz (Europe), 915 MHz (North America), and 2.4 GHz worldwide. The original version of the standard uses a physical layer based on Direct Sequence Spread Spectrum (DSSS) technique, having data rates from 20 kbps up to 250 kbps. Coexistence of multiple networks is enabled by frequency multiplexing, which divides each band in channels. The 2006 revision has improved the data rates for the lowest bands, although 250 kb/s is still the maximum achievable bandwidth, and additional modulation schemes has been defined. The majority of commercially available off-the-shelf radio modules operates in the 2.4 GHz band, relies on DSSS modulation, and transmits at 250 kb/s over 2 MHz wide channels.The IEEE 802.15.4 standard requires the PHY layer to provide an 8-bit integer value as a linear estimate of the received signal power, expressed in dB—this value is commonly known as the Received Signal Strength Indicator (RSSI). The idea behind this indicator is that the transmission power at the sender directly affects the received strength—hence, according to Friis free space path loss law, RSSI decreases quadratically with the distance [6]. However, in real-world deployment the ideal distribution is not always applicable: the radio signal is affected by a lot of degrading effects, such as multipath and shadowing. All these phenomena deeply impact the accuracy of RSSI measurements, often resulting in inaccuracies in the estimated distance [8].In recent years, Ultrawideband (UWB) technologies have emerged as a viable solution for short-range wireless communications in Personal Area Networks. Compared to narrowband modulations, like the one used in IEEE 802.15.4, UWB increases significantly the robustness of the transmissions spreading the signal over a very large bandwidth—usually 500 MHz. In addition, due to the large bandwidth operations, UWB signals feature very fine-grained time resolutions. Robustness and high time resolution are key factors for a precise localization, and this has motivated the definition of an UWB-based physical layer for wireless sensor network alternative the IEEE 802.15.4, called IEEE 802.15.4a.The IEEE 802.15.4a standard has been released in 2007. Its UWB physical layer exploits an Impulse-Radio approach to transmit short pulses and to provide accurate ranging capabilities [3]. Specifically, it provides primitives for precision ranging using Time of Arrival (ToA): the travel time of the signal from the transmitter to the receiving node is used to measure the distance between the two antennas. The UWB physical layer of IEEE 802.15.4a allocates frequencies in three ranges: a sub 1 GHz band, a band between 3 and 5 GHz, and a third band between 6 and 10 GHz. All these bands are divided into channels having a bandwidth of 500 MHz or more, providing a minimum data rate of 850 Kbit/s and range estimation errors below 1 meter under line-of-sight conditions.Hence, while RSSI in IEEE 802.15.4 is greatly affected by multipath fading and channel variability, TOA-based ranging with UWB is more robust but has strict requirements in terms of clock synchronization and processing time.


## 3.2. Hybrid Positioning

Range measurements coming from the radios, regardless the way they are obtained, may be used as inputs for algorithms, which compute the position of the target node. These algorithms can be based either on geometry considerations or statistical methods. We chose two simple geometric techniques: Multilateration and Min-Max. Their selection was driven by their wide use in literature because of their low complexity and good performances [3, 8].Min-Max is a deterministic localization algorithm characterized by a low-computational complexity—it estimates the position of the target within an area delimited by maximum and minimum distances from the known anchors. Range measurements of relative distances between the agent and the anchor nodes are considered, and these distances are used to create squares surrounding the anchors. The estimated target position is the center of the intersection of these bounding boxes—this point can be easily computed by finding the maximum of all the lowest values of the coordinates and the minimum of all maximum values.Multilateration is a simple range-based, decentralized localization algorithm based on geometry principles. An unknown node has position(x,y), and ranges are defined as the estimated distances—obtained for example by TOA or RSS measurements—between the unknown node and N anchor nodes at known coordinates (xi,yi), where i=1,2,…,N. In presence of error-free distance estimations, the ith anchor defines a circle centered in (xi,yi), with radius di, and having the target point (x,y) belonging to the circumference.  The intersection of three circles is sufficient to determine the position of the target node. However, the intersections can be zero or more than one if range measurements are affected by errors, and some geometrical rules must be used to cope with this issue [8, 16].Both localization algorithms need at least three measurements to produce an estimate. However, increasing the number of anchors does not continuously improve the accuracy. On the contrary, adding noisy values may degrade the output [6, 8]. Hence, our system uses only the 6 smallest range data and discards the other values at each step. The assumption underlying this choice is that higher distances are less accurate: this is consistent with the exponential path-loss model. Additionally, this assumption makes perfect sense in an indoor environment, where higher distances might increase the probability of having walls and other obstacles between the anchors and the node.Once the best data for each source have been selected, the measurements need be fused. We have identified two possible techniques for combining the different data coming from our cognitive device: the first method is called Partial-mix (hereafter P-mix) while the second will be referred to as F-mix, which stands for Full-mix.In P-mix the localization algorithm is executed independently for the two sets of range measurement, resulting a set of two points. The fused estimated position is the barycenter of these points—this approach may be generalized to an arbitrary number of measurement sets. In our case, we have only a pair of radio source, and the final position is the intermediate point between the two positions.In F-mix, all the measurements available are combined together, regardless the source—then, according to our criteria, the values are sorted and the best 6 values are used to produce a single estimation.P-mix can be extended to include weights in the calculus of the barycenter, for example, to give more credit to one range system if we know that it will always be more accurate than the others in some areas of the environment. On the contrary, F-mix is more flexible and can be used with no variations in presence of range technologies that provides value with different frequencies. Moreover, F-mix is more robust: if all the anchors belonging to one source are really distant and unreliable, their results are automatically discarded while better values are used.


## 3.3. Velocity-Based Tracking

Multipath phenomena or issues in the leading-edge detection method on UWB signals may impact the ranging process, reducing the accuracy of the estimation. Similarly, walls or other obstacles may change the path-loss model used to infer range from RSSI data. Hence, the estimated trajectory of a moving target, defined as the temporal sequence of positions provided by any localization algorithm, is likely to be affected by some degree of uncertainty.To cope with this problem, a proper tracking algorithm is often employed to predict the path of the target and to cancel out noisy estimations [2]. This activity presents a number of challenges, for example, multimodal sensing, signal processing, and data fusion in real-time. Belief Propagation, Kalman, and Bayesian/Particle filters are the most used types of schemes for tracking in WSNs, but they not always meet the limitations imposed by technology in terms of energy and computational capability [17, 18]. This motivated our quest for a low-complexity algorithm, based on simple mathematical operations and able to track a target node without requiring any information about the surrounding environment or additional data exchange among anchors.Our tracking technique relies on the history of movements and a linear prediction model of the speed. The current position computed by our method is a function of the current coordinates and the previousN values of the velocity. In addition, it responds as an all-pass filter to decelerations, while it has the typical low-pass behavior of a finite impulse response filter to increases the speed. The latter feature is used to bound the movement of the target, reducing the impact of noisy positions significantly far away from the real ones. This filter has only one parameter, which is the amount N of past positions that are used in combination with the current estimation. The higher the value of N is, the more important the past history will be. We set all the weights of the window to the same value, although the filter could be easily modified to give more importance to recent estimations than the older ones.A possible scenario for this approach is, as example, pedestrian tracking. A walking person may have an average speed constant over time or can constantly accelerate, thus linearly varying his/her speed. The window sizeN should be kept small if the target is expected to vary frequently its speed, such as while visiting an exposition, while the window might be increased if the person is doing jogging in a park and has a constant speed. We also accept that the person can suddenly stop for some reasons: in this case, since the position does not change, the algorithm ignores previous speed estimations and sets the last coordinates as the actual ones.The estimation of the current position proceeds as follows: implementing a moving window of sizeN, a buffer stores the latest N estimated target positions Pi, and their corresponding time interval ti. A first velocity guess can be obtained by exploiting these values according to
(1)v^(i)=∑j=1N‖Pi-j+1-Pi-j‖∑j=1Nti-j,After having estimated the velocityv(i), we constrain the maximum displacement to a circle centered in xi with radius ri=v(i)×(Ti+1-Ti). A refined guess of the subsequent target location is obtained according to
(2)(x-xi)2-(y-yi)2=ri2.The estimation is eventually obtained through a comparison of the raw position provided by the localization algorithm and the bound provided by (2).As shown in Figure1, two situations are possible: if the estimated point falls inside the bound, it is assumed that this new position is accurate and it is taken as it is. On the other side, if the newest estimation falls outside the bound, then the measure might be affected by noise: the actual position is assumed to be along the direction of estimated point, but over the bound and not farther.The new estimated point is taken as is if it falls inside the bound (a), while it is moved over the circular bound if it is outside (b).
(a)
(b)A formal description in polar coordinates of the algorithm that provides the new positionP at the step i might be
(3)P^i=(l,θ),
where θ and l are defined, respectively, as
(4)θ=atan2(yi-y^i-1xi-x^i-1),(5)l={‖Pi-P^i-1‖,l<RbRb,l≥Rb,
and value Rb of the bounding radius is
(6)Rb=v-i,i-N⋅ti=ti⋅∑j=1Nli∑j=1Nti-j.


## 4. Experimental Results

To validate the performance of the whole hybrid tracking algorithm, it was applied  to a database of measurements collected by researchers of University of Cesena in 2009. All the data come from a real sensor network [12] deployed inside a building of the faculty of Computer Science during an acquisition campaign made within the Newcom++ project.As shown in Figure2, a total of 21 IEEE 802.15.4-based anchors and 12 UWB devices were scattered in a 450 m2 floor at known locations, while the target device was a robot moving along a corridor on a 25 m rail—this set-up allows to know the exact position of the mobile node at each instant. Range measurements retrieved by the target device are used as inputs to the proposed approach, and the output of our system is eventually compared to the one obtained by a Kalman filter [19].Figure 2
The measurement scenario, where the green line defines the target path. Red and blue marks represent UWB and ZigBee anchor locations, respectively [12].Please note that a preliminary filter was employed in order to remove all UWB measures affected by system and software issues, as suggested in [12].


### 4.1. Hybrid Positioning

Since the moving target is equipped with different radios based on IEEE 802.15.4 and UWB transceivers, two different sets of range measurements for target position were collected.First, the datasets were considered separately. Localization performances were evaluated using narrowband or UWB data by Min-Max and Multilateration algorithms. Then, the two sets were combined using either the Partial-mix (P-mix) or Full-mix (F-mix) method previously described in Section 3.2.Table1 shows the RMSE (Root Mean Squared Error) for each of the four resulting situations. Analyzing the data, it is clear that the fusion of different range sources provides better results than using single source measurements. In particular, F-mix is the algorithm that best estimates the actual target position.Table 1
RMSE (in m) for the localization process using different combinations of algorithms and datasets.
802.15.4 only
UWB only
UWB + 802.15.4(P-mix)
UWB + 802.15.4(F-mix)
Min-max
1.15
1.45
1.15
1.05
Multilateration
1.25
1.51
1.21
1.19


### 4.2. Velocity-Based Tracking

Since positions estimated with a localization algorithm are not error free, an algorithm to improve the accuracy of the moving target must be employed. As described in Section3.3, a velocity-based tracking algorithm has been implemented.In this algorithm, the average speed is computed over a window of previous positions, and the estimated speed is used to constrain the maximum displacement of the next position estimate, in order to bound the errors. After many tests where the size of the window was changed, we found that the optimal value ofN is 6, which corresponds to about 3 s. We made two test sets on velocity-based tracking algorithm: the former was done using raw positions coming from localization algorithms, while in the latter we used P-mix or F-mix to fuse range measures. Table 2 summarizes the results of these tests.Table 2
RMSE (in m) of the velocity-based tracking algorithm.
802.15.4 only
UWB only
UWB + 802.15.4(P-mix)
UWB + 802.15.4(F-mix)
Min-max
0.75
0.80
0.74
0.72
Multilateration
0.80
0.91
0.76
0.75It stands out that the use of the velocity-based tracking algorithm reduces the localization RMSE over the whole track. In particular, the combination of velocity algorithm and F-mix allows reaching the minimum RMSE.In addition, apparently Min-Max is both the simplest and more accurate localization method. For this reason, we will use Min-Max only for further analysis and to compare our tracking algorithm against a Kalman filter.As already mentioned, filters like Kalman Filter, Particle Filters, and Belief Propagation are used for tracking purposes. Some of them are very accurate but have high complexity—Particle Filters—while others, like Kalman Filters, have lower accuracy but are less complex. Since our aim is to design a low complexity algorithm able to be implemented in WSN nodes, we selected the latter for comparisons. In Kalman filter, the estimated velocity value is included into status equations to guess next target position as follows:(7)xk=xk-1+K(zk-Hxk-1),(8)xk=Axk-1+wk-1,(9)zk=Hzk-1+vk-1,
where the 2×2 matrix A relates the states to the previous time step, while H is a 2 elements vector related to the measurements vector zk. The random vectors wk and vk model the process and measurement noise, respectively, and are both independent and Gaussian. Finally, to make the filter adaptive, the Kalman gain K in (7) is computed each time a new measurement coming from a localization algorithm is ready through a series of standard equations. For a complete discussion on this topic refer to [13, 18, 19] and references within.In our implementation,zk is populated with the position estimates coming from Min-Max or using Multilateration algorithms, while the velocity algorithm provides speed estimates; xk represents then position and speed estimation according to the physical model described by (4).Test results are shown in Table3, while Figure 3 graphically shows the movement tracked by both velocity-based and Kalman Filters when using Min-Max plus the F-mix fusion method.Table 3
Comparison of the RMSE (in meters) obtained using our novel technique or a Kalman filter.
802.15.4 only
UWB only
UWB + 802.15.4(P-mix)
UWB + 802.15.4(F-mix)
Velocity-based
0.75
0.81
0.74
0.72
Kalman
0.62
0.87
0.57
0.58Figure 3
Graphical comparison of the actual path, the estimated path using velocity-based filter, and the path computed when filtering with Kalman.Results show that velocity Algorithm and Kalman Filter have similar accuracies even if the complexity of the filters is different. To make the comparison among the two approaches more significant, it may be useful to investigate the computational effort required by the two methodologies. The velocity algorithm is based on scalar additions, products, and divisions of real numbers, and the square root and trigonometric operation can be efficiently implemented by using a lookup-table or one of the existing low-level mathematical libraries. On the other hand, Kalman filter requires matrix operations iteratively, and we expect that the computational effort is considerably higher with respect to our proposed method.In order to experimentally evaluate their different computational demands, both algorithms have been implemented on a StrongArm SA-110 running at 200 MHz, over the real-time Operating System VxWorks 5.1. More specifically, a quantitative analysis has been made by averaging the time needed to perform 1000 iterations. Results show that Kalman filtering requires an average time of 72 ms to compute the next position estimate, while the velocity-tracking approach requires only 12 ms. Hence, requiring less processor time for each tracking iteration, velocity algorithm and limits energy consumption. Moreover, assuming a sampling time of 50 ms (which is the case for our best data set), the Kalman filter will be too slow, while the velocity algorithm, although less precise, is suitable for real-time filtering.


## 4.1. Hybrid Positioning

Since the moving target is equipped with different radios based on IEEE 802.15.4 and UWB transceivers, two different sets of range measurements for target position were collected.First, the datasets were considered separately. Localization performances were evaluated using narrowband or UWB data by Min-Max and Multilateration algorithms. Then, the two sets were combined using either the Partial-mix (P-mix) or Full-mix (F-mix) method previously described in Section 3.2.Table1 shows the RMSE (Root Mean Squared Error) for each of the four resulting situations. Analyzing the data, it is clear that the fusion of different range sources provides better results than using single source measurements. In particular, F-mix is the algorithm that best estimates the actual target position.Table 1
RMSE (in m) for the localization process using different combinations of algorithms and datasets.
802.15.4 only
UWB only
UWB + 802.15.4(P-mix)
UWB + 802.15.4(F-mix)
Min-max
1.15
1.45
1.15
1.05
Multilateration
1.25
1.51
1.21
1.19


## 4.2. Velocity-Based Tracking

Since positions estimated with a localization algorithm are not error free, an algorithm to improve the accuracy of the moving target must be employed. As described in Section3.3, a velocity-based tracking algorithm has been implemented.In this algorithm, the average speed is computed over a window of previous positions, and the estimated speed is used to constrain the maximum displacement of the next position estimate, in order to bound the errors. After many tests where the size of the window was changed, we found that the optimal value ofN is 6, which corresponds to about 3 s. We made two test sets on velocity-based tracking algorithm: the former was done using raw positions coming from localization algorithms, while in the latter we used P-mix or F-mix to fuse range measures. Table 2 summarizes the results of these tests.Table 2
RMSE (in m) of the velocity-based tracking algorithm.
802.15.4 only
UWB only
UWB + 802.15.4(P-mix)
UWB + 802.15.4(F-mix)
Min-max
0.75
0.80
0.74
0.72
Multilateration
0.80
0.91
0.76
0.75It stands out that the use of the velocity-based tracking algorithm reduces the localization RMSE over the whole track. In particular, the combination of velocity algorithm and F-mix allows reaching the minimum RMSE.In addition, apparently Min-Max is both the simplest and more accurate localization method. For this reason, we will use Min-Max only for further analysis and to compare our tracking algorithm against a Kalman filter.As already mentioned, filters like Kalman Filter, Particle Filters, and Belief Propagation are used for tracking purposes. Some of them are very accurate but have high complexity—Particle Filters—while others, like Kalman Filters, have lower accuracy but are less complex. Since our aim is to design a low complexity algorithm able to be implemented in WSN nodes, we selected the latter for comparisons. In Kalman filter, the estimated velocity value is included into status equations to guess next target position as follows:(7)xk=xk-1+K(zk-Hxk-1),(8)xk=Axk-1+wk-1,(9)zk=Hzk-1+vk-1,
where the 2×2 matrix A relates the states to the previous time step, while H is a 2 elements vector related to the measurements vector zk. The random vectors wk and vk model the process and measurement noise, respectively, and are both independent and Gaussian. Finally, to make the filter adaptive, the Kalman gain K in (7) is computed each time a new measurement coming from a localization algorithm is ready through a series of standard equations. For a complete discussion on this topic refer to [13, 18, 19] and references within.In our implementation,zk is populated with the position estimates coming from Min-Max or using Multilateration algorithms, while the velocity algorithm provides speed estimates; xk represents then position and speed estimation according to the physical model described by (4).Test results are shown in Table3, while Figure 3 graphically shows the movement tracked by both velocity-based and Kalman Filters when using Min-Max plus the F-mix fusion method.Table 3
Comparison of the RMSE (in meters) obtained using our novel technique or a Kalman filter.
802.15.4 only
UWB only
UWB + 802.15.4(P-mix)
UWB + 802.15.4(F-mix)
Velocity-based
0.75
0.81
0.74
0.72
Kalman
0.62
0.87
0.57
0.58Figure 3
Graphical comparison of the actual path, the estimated path using velocity-based filter, and the path computed when filtering with Kalman.Results show that velocity Algorithm and Kalman Filter have similar accuracies even if the complexity of the filters is different. To make the comparison among the two approaches more significant, it may be useful to investigate the computational effort required by the two methodologies. The velocity algorithm is based on scalar additions, products, and divisions of real numbers, and the square root and trigonometric operation can be efficiently implemented by using a lookup-table or one of the existing low-level mathematical libraries. On the other hand, Kalman filter requires matrix operations iteratively, and we expect that the computational effort is considerably higher with respect to our proposed method.In order to experimentally evaluate their different computational demands, both algorithms have been implemented on a StrongArm SA-110 running at 200 MHz, over the real-time Operating System VxWorks 5.1. More specifically, a quantitative analysis has been made by averaging the time needed to perform 1000 iterations. Results show that Kalman filtering requires an average time of 72 ms to compute the next position estimate, while the velocity-tracking approach requires only 12 ms. Hence, requiring less processor time for each tracking iteration, velocity algorithm and limits energy consumption. Moreover, assuming a sampling time of 50 ms (which is the case for our best data set), the Kalman filter will be too slow, while the velocity algorithm, although less precise, is suitable for real-time filtering.


## 5. Conclusions

In this paper we compared the behavior of different localization algorithms for WSNs, such as Min-Max and Multilateration as well as more complex estimation procedure involving a velocity estimate and filtering. The peculiarity of this work is the joint exploitation of two sets of measurements from different wireless transmission systems for the same target, one using narrowband modulation and thus allowing localization using RSSI measurements, while the other exploiting UWB technology, where range measurements are based on ToA. We tested localization algorithms using both data streams, either separately or fused with proper algorithms. Results show that joint use of both datasets with the so-called F-mix algorithm improves the localization accuracy. As expected, the fusion of range measurements coming from different sources can help in better estimating target position.Moreover, a novel lightweight velocity-based tracking algorithm has been used to bound positioning errors, and tests revealed that the accuracy is improved again. If compared with standard Kalman Filter, our method performs slightly worse as far as the accuracy is concerned. However, Kalman is more complex and computational demanding. Hence, our novel velocity-based algorithm may be suitable if a localization system with tracking capability must be implemented over a cheap and low-power sensor node, with limited computational power.In future works, other radio standards, such as IEEE 802.11 or IEEE 802.15.1, will be used as additional sources of range measurements in order to test the data fusion algorithm with more than two datasets. This will help to understand in which conditions localization accuracy improvements can be achieved.



---

*Source: 430169-2012-08-23.xml*