Royal Society Publishing

Wireless sensor node localization

Ákos Lédeczi , Miklós Maróti

Abstract

For most wireless sensor network (WSN) applications, the positions of the sensor nodes need to be known. Global positioning systems have not fitted into WSNs very well owing to their price, power consumption, accuracy and limitations in their operating environment. Hence, the last decade has brought about a large number of proposed methods for WSN node localization. They show tremendous variation in the physical phenomena they use, the signal properties they measure, the resources they consume, as well as in their accuracy, range, advantages and limitations. This paper provides a high-level, comprehensive overview of this very active research area.

1. Introduction

Wireless sensor networks (WSNs) are typically used to measure one or more physical phenomena in a widely distributed area. In most WSN applications, the measured sensor values are tagged with both a timestamp and the location of a given sensor. Hence, the positions of the sensor nodes need to be known. The required accuracy of this location information is completely application dependent. A structural monitoring system might require centimetre-scale accuracy, while a forest fire warning system works well with a 100 m of uncertainty.

Accuracy is only one of the design drivers of localization. Since sensor nodes run on battery power, any WSN application or service needs to be energy efficient, and localization is no exception. Many WSN applications rely on a large number of sensors; hence, per-node monetary cost is an important consideration as well. The speed of localization is also an important factor. It may be fine to spend minutes localizing nodes for a static, long-term deployment since it only needs to be done once. For mobile applications, on the other hand, the localization needs to keep up with the mobility. Finally, the operating environment of the system puts significant constraints on localization as well. Some approaches work better indoors than outdoors, or in urban areas, caves, forests, or even under water. Hence, there is no universal solution to localization, and we cannot expect one to emerge any time soon, if ever.

Nevertheless, one might argue that global positioning systems (GPSs) have made other approaches obsolete as far as outdoor localization is concerned. Indeed, GPSs have made tremendous progress in the past decade while the WSN localization research summarized in this paper was carried out, yet they still do not meet the design constraints of many WSN applications. Low-cost GPS receivers, such as those that can be found in almost all smartphones today, exhibit tens of metres of typical error. High-end GPS chips can cost hundreds of dollars, use 50 mW of power or more, and provide up to 1 m accuracy with an unobstructed view of the sky. This is in stark contrast with the goal of many WSN systems to have nodes that cost tens of dollars and run for months or even years on a single charge. Furthermore, some WSN applications need sub-metre accuracy [1] that only differential or survey-grade GPS equipment can provide, but at the prohibitively high cost of thousands of dollars. Hence, this paper focuses on localization techniques other than GPSs. The interested reader is referred to Elliott & Kaplan [2] for an excellent overview of GPS-based localization.

WSN node localization approaches are typically characterized as either range-free or range-based. Most range-free techniques rely on radio connectivity alone and try to map the topology of the communication network to physical coordinates. One might consider such range-free methods as simply extreme cases of range-based approaches where the range is estimated relative to the maximum communication range of the radio using a single bit: 1 means within range and 0 means out of range. Nevertheless, range-free techniques are quite inaccurate as the communication range is highly variable and dependent on the environment, owing primarily to non-line-of-sight (LOS) conditions, multi-path fading, and hardware/antenna variations. Errors of 50–100% of the radio range are common [3]. The advantages of range-free methods include simplicity and low cost, as no additional hardware is necessary. A representative range-free method is presented in He et al. [3].

Most WSN localization techniques are infrastructure free; that is, no additional equipment is available other than the sensor nodes themselves to carry out the localization. Sometimes the locations of a few nodes, called the anchors, are known, and, hence, the resulting coordinates are absolute. Otherwise, the node locations can only be determined relative to one another.

The term self-localization is sometimes used to indicate that the WSN itself performs the localization of its nodes. For static WSN deployments, one can get around performing self-localization. Sometimes, it is feasible to deploy the sensors in pre-surveyed locations. These locations can be established at or before deployment time using external equipment. When higher accuracy is required, for instance, a differential GPS could even be used, since its cost and power requirements are not part of the WSN itself.

The goal of many WSN applications is to locate something such as a moving object or a source of a signal. Such approaches are often referred to as target localization, source localization or simply localization. In contrast with the subject of this article, the sensor nodes themselves are assumed to have known locations in these systems. To disambiguate the term localization when it is not clear from the context, the expression self-localization will be used for WSN node localization in this article.

The rest of this paper focuses almost exclusively on range-based self-localization in WSNs. First, it surveys different ranging methods. The subsequent section reviews the broad spectrum of localization algorithms that transform range estimates into coordinates. This is followed by a brief description of radio interferometric localization, a representative example that demonstrates the complexities of this important area. A summary of possible future trends concludes the paper.

2. Ranging

Probably the most important factor that differentiates between the various ranging approaches is the physical phenomenon utilized. Figure 1 provides an ontology of the different methodologies. In WSNs, the use of radio frequency (RF) signals is the most common, as a radio transceiver is typically available on most sensor nodes. RF propagation, however, presents significant challenges to accurate ranging on resource-constrained, low-cost hardware. Radio waves propagate at the speed of light, making time-based approaches extremely challenging. WSN transceivers operate at relatively high frequencies—hundreds of megahertz to multiple gigahertz—requiring high sampling rates and significant computing power to carry out range-specific RF signal processing. Conversely, the simplest technique based on received RF energy is highly susceptible to multi-path fading and other error sources.

Figure 1.

Ranging ontology. GPS, global positioning system; RSSI, received signal strength indicator; ToF, time of flight; UWB, ultra-wideband.

Many of these problems are avoided using acoustic signals instead. The speed of sound is six orders of magnitude slower than the speed of light, so most acoustic techniques measure the propagation time between pairs of nodes. As the distributed sensor nodes do not share a global clock, they need to either rely on a time synchronization service or provide some other means to create a shared time reference between the source and the destination of the acoustic signal.

Ultrasonic systems are typically very accurate, as it is easy to detect the arrival time of a high-frequency signal, resulting in centimetre-level ranging accuracy [4,5]. However, the practical range of such systems is limited to 10 or so metres, as high-frequency signals are quickly attenuated in the air. Since ultrasonic transducers are directional, multiple transducers are needed per node to provide 360° coverage. On the other hand, the beneficial side effect of this is the capability to supply bearing information along with the range estimate. Acoustic methods are susceptible to errors due to non-LOS conditions. If, however, there is LOS, then multi-path propagation is not a problem, since the LOS component will always arrive first. As noise and wind have detrimental effects, ultrasonic approaches are mainly used in indoor settings.

The audible acoustic range has also been used for ranging in WSNs. To compensate for the lower frequency, a linear chirp signal is transmitted. Cross correlation or a matched filter on the receiver side provides precise time of arrival (ToA) detection [6]. These systems have a longer range (up to 100 m depending on the sound energy used), but somewhat less accuracy than ultrasonic methods. While microphones are small, speakers that can generate high enough sound energy for a reasonable range need to be bigger and require more power. Consequently, a practical system would need to be asymmetrical, with small, passive sensor nodes listening for signals from one or more larger transmitters. The fact that an audible signal is used makes the appeal of these techniques quite limited.

Camera networks are a subclass of WSNs in which the sensors themselves provide a way for self-localization and self-orientation (also called calibration). Cameras with overlapping views can observe a set of feature points and deduce their relative positions. However, the obtained coordinates are relative to a scaling factor [7] that needs to be determined via other means. In simultaneous localization and tracking, a moving object is observed and tracked instead of a set of feature points [8]. The numerous assumptions and initial results have not yet allowed for practical applications.

There are other less frequently used physical phenomena employed for ranging in WSNs. Lighthouse, an early innovative optical system, applied two directional light sources rotating in orthogonal planes as a single anchor node [9]. Nodes equipped with light sensors were able to measure the time they were exposed to the light and to determine their ranges to the axes of rotation. Recently, a magnetic field induced by coils on the Earth's surface was used to track underground animals tagged with magnetometers [10]. For underwater localization, water pressure provides very accurate depth estimates. Air pressure is more variable, but it can be used to estimate elevation change in the short term.

Of special relevance to practical localization/tracking in WSNs is the fact that the price of inertial measurement units (IMUs) is dropping. For example, the $600 MEMS-based analogue device ADIS16360 unit has a tri-axis accelerometer and a tri-axis gyroscope, performs the necessary digital signal processing and other computations on-board, and provides a digital interface. Although IMUs cannot be used alone because of error accumulation, they can be very useful in multi-modal ranging of mobile sensors. We expect to see them appear in high-end WSNs in the near future.

The overwhelming majority of ranging techniques in WSNs rely on RF or acoustic signals. However, there is a lot of variation based on which attributes of the signal are being measured to deduce range information. Figure 1 summarizes the different approaches.

(a) Time

Measuring time is perhaps the most natural way to estimate range as the speed of signal propagation is well known. Acoustic systems rely on time measurements almost exclusively, as the speed of sound is low enough to process the signal on even severely resource-constrained sensor nodes. Measuring time of flight (ToF) is the most widely used technique. In the usual arrangement, a sensor node broadcasts a radio message to indicate the start of the measurement procedure and then immediately emits a characteristic acoustic signal. When neighbouring nodes receive the radio message, they start a timer and begin sampling their microphones. When they detect the arrival of the sound, they stop the timer. The elapsed time and the known speed of sound provide a range estimate. As the sending and receiving of the radio message takes a negligible amount of time compared with the propagation time of the acoustic signal, it is usually disregarded. A more significant source of error is the temperature dependence of the speed of sound. This can easily be compensated for by measuring the temperature and adjusting the speed used in calculations accordingly. As acoustic ranging is sensitive to noise, measurements are usually performed multiple times to enable outlier elimination and averaging. An advantage of ToF ranging is that the WSN does not need an explicit time synchronization service. The radio message at the beginning of the procedure provides a shared time reference.

A technique that requires time synchronization but does away with the need for radio messages is based on the time difference of arrival (TDoA) principle. Here, multiple nodes detect the same acoustic event and take the pairwise difference in arrival times. The measured TDoA provides the distance difference of the two nodes from the source; hence, it defines a hyperbola (in two dimensions). The unknown positions, however, are the foci of the hyperbola, making the determination of those locations complicated. Thus, the TDoA approach is a better fit for determining the location of acoustic sources by measuring the TDoA between known locations than for node self-localization. If the sensor node has multiple microphones, then the TDoA on multiple channels provides a bearing estimate to the source. This can be used for self-localization, but again works better for source localization.

The high speed of light makes time-based RF ranging extremely challenging. High-end WSNs for outdoor deployments may be able to afford the relatively high cost, high power and somewhat limited accuracy of GPSs, but most WSN applications must rely on other methods.

Nanosecond-precision time synchronization in WSNs is out of the question, making two-way ToF ranging the only feasible approach. In this scheme, one node transmits a radio signal and simultaneously starts a timer. When the second node detects the signal, it immediately transmits a signal back to the first node, which stops its timer when it detects the arrival of the return signal. The delay on the second node between reception and retransmission must be known (or measured) very precisely, and is subtracted from the measured time. Then, the delay and the speed of light are used to estimate the range.

The most well-known RF technology that uses two-way ToF ranging is ultra-wideband (UWB). UWB is based on sending high-bandwidth pulses that are short enough to avoid multi-path fading, as there is typically no time overlap between the LOS signal and reflections. Hence, the technology works well in indoor environments, providing centimetre-scale precision. UWB localization systems have an asymmetrical architecture: sophisticated base stations serve a potentially large number of inexpensive tags. A disadvantage of this technology is its high cost due to the base stations. This has prevented the application of UWB in WSNs so far.

The conventional wisdom is that custom hardware is necessary for RF two-way ToF ranging in WSNs. Lanzisera et al. [11] have built a sensor node that is even able to achieve reasonable accuracy in such unfavourable RF environments as a coal mine under LOS conditions. Recently, however, Mazomenos et al. [12] demonstrated metre-scale accuracy using COTS sensor nodes and actual radio messages. They estimated the extra delay of the measurement by placing the two nodes right next to each other while performing a large number of ranging operations and considering the actual propagation time to be zero. They then moved the nodes apart and repeated the ranging operations. By averaging the results and subtracting the estimated additional delay, they were able to achieve sub-clock-period timing accuracy, an absolute necessity considering that the RF signal travels almost 20 m during a single clock period on the particular hardware used (16 MHz oscillator). Even though this technique has not been used to localize a WSN deployment yet, the reported ranging results are very encouraging.

(b) Amplitude/power

Most radio transceiver chips can supply an estimate of the received RF power in a given band via the received signal strength indicator (RSSI) signal. Given the known transmit power and a propagation model, the RSSI can be used to estimate the range accordingly. This technique is extremely simple and cheap (in terms of resources required), but, unfortunately, it is very inaccurate. One can expect about 10–20% average error in outdoor deployments and worse indoors. RF signal propagation is highly dependent on the environment and is dynamic. The actual path loss observed can be significantly different from what the propagation model predicts. Most systems, therefore, use a set of fixed base stations at known locations and build a map of RSS values for each such beacon in the entire coverage area at deployment time. Localization is then performed by measuring the set of RSS values and finding the closest match in the RSS map. This approach provides much better accuracy, but at a high deployment cost. For practical applications, high beacon density is required. Also, most environments are dynamically changing, limiting the achievable precision. Note that this is not a strictly range-based method, as the ranges to the beacons are never actually computed, but, because of the large number of measurements required, it is closer in spirit to range-based methods than to simple connectivity-based range-free approaches.

There are commercially available systems based on this technique. Cisco location-based services [13] provide asset tracking on top of their regular WiFi infrastructure. While it is difficult to quantify the accuracy of such a system deployed in a large heterogeneous environment—for example, a hospital—the typical error for a real-world system is reported to be less than 10 m.

(c) Phase

Measuring the phase of a stationary periodic signal between a transmitter and a receiver provides information about their distance. This method, however, comes with its own set of challenges. If the wavelength is shorter than the measured range, then the phase only provides the distance modulo the wavelength. Hence, the measurement needs to be carried out at multiple frequencies, and a set of diophantine equations needs to be solved in the ideal case. In practice, noisy measurements mandate an optimization procedure instead. Without precise time synchronization, the unknown transmit phase needs to be compensated for.

A variant of this approach avoids both of these problems using multiple antennas on the same node and measuring the received phase difference between them. This gives a bearing estimate to the source of the RF signal. Phase-based approaches are all sensitive to multi-path, as each additional propagation path causes an extra phase shift, resulting in a possibly significant error. This is especially problematic when the nodes are on the ground, as ground reflections at low angles of incidence can significantly attenuate the LOS signal.

3. Localization

Localization is usually a two-step process: first, one or several ranging methods are employed to collect data from the physical environment, then, an algorithm computes the location of the nodes from the collected data. In this section, we focus on the various localization algorithms. To better grasp the complexity of this task, we first establish an ontology of the localization algorithm based on

  • — the type of ranging data (time, power, connectivity, multi-modal, etc.),

  • — the error distribution of the ranging data (under- or overestimate, noise, etc.),

  • — the amount of a priori information (anchor nodes, planar deployment, etc.),

  • — the mobility of the nodes (static versus mobile),

  • — the computational algorithm (direct formula, optimization, etc.), and

  • — the execution environment (centralized versus distributed, mixed).

From this short list, one can see that the field of WSN localization algorithms is very diverse. There is no single algorithm that is universally applicable.

(a) Ranging data

The localization algorithm takes measurement data that have been collected in the network. These ranging data can be of various types, as we have seen in the previous section, but it is important to realize that completely different ranging methods can produce similar ranging information. For example, both radio signal strength-based distance estimation and acoustic ToF measurement can produce a distance estimate between two nodes, although with completely different error characteristics. At this point, we do not care how particular ranging data were collected, but only what information it provides about the locations of the nodes.

ToF (mainly acoustic) measurements, UWB ranging and radio signal strength indicators all give an estimate of the distance between two nodes. Usually a preprocessing step is necessary to calculate this distance estimate (based on some physical model), but the processing step only involves the two nodes participating in the measurement.

The error characteristics of the measured distance depend on the type of ranging employed. For example, acoustic ToF ranging usually does not produce shorter distances than the actual one; however, longer distances are common because of blocked LOS and echoes [14]. Radio signal strength-based ranging has a completely different characteristic: it is more precise for shorter distances than for the longer ones, as the intensity of the signal decreases with the square of the distance (or higher in urban environments) [15]. The error in the ranging data can significantly be reduced by performing multiple measurements, although this mandates trading measurement time for precision.

There exist ranging techniques that do not produce pairwise distances; instead, they give estimates of distance differences. From TDoA data measured with an acoustic sensor, or in radio interferometry with anchor nodes, it is possible to calculate the distance difference dABdAC between three nodes A, B and C. Time or phase difference of arrival measurements can also be used to estimate the bearing of sensors relative to one another.

Many ranging methods can produce several types of ranging data, and localization algorithms can use ranging data coming from different modalities. This improves the performance of the localization, since the error characteristics of these modalities are usually different.

(b) A priori information and mobility

It is possible to calculate the relative positions of sensors, but, in most cases, we need the coordinates or locations of the sensors relative to the environment and not to each other. Therefore, localization techniques rely on some a priori information. This information can come from specially equipped nodes (e.g. with GPSs) or from a database of known locations of anchor nodes. Even if the network is static, it is much easier to survey just a few strategically placed anchor nodes than to determine the exact positions of all sensors.

Many published studies assume that the network is located on a two-dimensional plane, which significantly simplifies the design of the localization algorithm and can produce more stable and precise results. This is a good approximation of current deployments, where the spatial diversity in the Z-axis (elevation) is usually significantly smaller than in other axes. If the positions of the sensors are not constrained to the plane (or their elevation is not limited), then localization algorithms tend to suffer from instability, since they have more freedom to find sensor positions that better match the measured ranges but are farther from the true locations of the sensors [16].

Localization of mobile sensor nodes is more difficult than that of static ones. So far, we have assumed that all ranging data describe the same static deployment and environment. If the nodes are mobile or the environment changes, then the measurement time needs to be recorded together with the range estimates. In effect, the localization has to be performed in four dimensions: three-dimensional space and time. Unlike distance, time can be measured very precisely (relative to the speed of mobility) with wireless sensors [17], so ‘ranging’ errors are relatively small in this dimension. The mathematical formulae describing the physical system become more complicated, but the same algorithmic techniques can be applied as for static deployments.

We can differentiate between this static approach to mobile localization and that of on-line localization, where the positions of the sensors need to be known immediately or as soon as possible. In this case there is no time to record all measurements and perform post-processing; instead, we must maintain an estimate of the current system and perform localization based on changes, for example using extended Kalman filters [18]. The mathematical model of the movement of sensors is a very important piece of a priori information (e.g. the maximum speed), which affects the precision and response time of the system.

Another source of a priori information can be surveyed ‘maps’ of the environment. This can include the expected RSSI values of messages coming from beacon nodes, or the intensity of light, sound or other characteristics of a particular place. This information is recorded at some granularity and stored in a database. The position estimate of the sensor can be calculated by finding the pre-surveyed position that best matches the measured values [19,20].

(c) Localization algorithm

Probably the most important design choice is whether the algorithm is executed within the WSN, or all ranging data are collected in a centralized place where a computer with more resources can calculate the locations. If the ranging data need to be collected, then a message routing protocol must be employed, which comes with its own problems (increased delay, increased energy consumption, reliability issues, etc.). On the other hand, most of the algorithms we are going to discuss cannot be executed on the sensor nodes because of the lack of adequate computational or storage resources.

The easiest case is when the location of a sensor can be calculated by a mathematical formula, e.g. from measured distances to known positions. This localization method can be realized in the network; for example, if the anchor nodes are densely deployed and know their position, then every other node could potentially measure the ranges to three or more anchors and calculate their own position. The same approach could be used for distance differences if enough measurements are known and they have low error.

In general, measured range values have significant errors and are usually not in a form that can be used to derive a closed mathematical formula for the position of the sensors. Therefore, optimization techniques are used to obtain the estimated location with the least amount of error with respect to measured ranges. Every optimization problem has a goal function which needs to be minimized or maximized. This goal function depends on the type of ranging data, but in general can be classified as either (i) representing the localization error or (ii) counting the number of supporting measurements for a given location estimate.

The presence of measurement errors poses a significant challenge to the optimization approach, since a single bad measurement with large error can skew the results. To counter this problem, one can use the number of supporting measurements as a goal function. For example, the common least-squares range error estimate can be replaced by the number of measured ranges which support (or are close enough to) the calculated distances between the estimated positions. This goal function is resistant to bad measurements, but it is not continuous and very hard to solve. Genetic algorithms and interval arithmetic-based optimization algorithms were found to be effective when properly guided.

The easiest optimization approach is the so-called spring model, where the unknown variables are the location coordinates of the sensors, and the goal function is the sum of the errors between the measured ranges and the calculated distances. Variations of this technique have been used in many localization approaches (one can even treat connectivity-based localization in this way), but, in general, this approach is very sensitive to the initial location estimates of the sensors. The optimization procedure can be performed centrally by a nonlinear optimizer, or via a genetic algorithm, or it can be executed in the network where each node only needs to know its own position and those of its neighbours.

The optimization approaches can be adapted to various ranging data, including distance differences, signal phase, angle of arrival, RSS, etc. The most important advantage of the optimization approach is that it can easily incorporate measurement data with different modalities, at least at the model level. However, the resulting optimization problems are usually very hard to solve, as the corresponding goal function is not linear and has many local minima.

Map-based localization requires a (usually large) database of previous measurements to estimate the locations of sensors. Instead of using mathematical formulae to calculate the goal function, this approach uses the database to find the number of supporting measurements for any given location. Usually this process is very fast (much faster than the optimization method) and can be executed independently for each node. Very good localization results can be achieved with detailed maps [21].

4. A representative approach

To illustrate the challenges of self-localization using the typical resource-constrained hardware platforms of WSNs, we selected the radio interferometric positioning system (RIPS) as a representative example [22].

RIPS is a phase measurement-based RF localization method specifically designed for WSNs. It avoids having to process high-frequency RF signals directly by relying on radio interferometry in a unique way. The novel idea behind radio interferometric ranging is to use two transmitters to create an interference signal directly. If the frequencies of the two emitters are almost the same, then the composite signal will have a low-frequency envelope defined by the difference of the two transmit frequencies. While this low frequency is not an actual spectral component of the signal (only the amplitude of the signal is modulated at that rate), nonlinear transformation and filtering can produce a signal with that fundamental frequency. The RSSI signal available on most RF transceivers does exactly that, and can be sampled and processed on the resource-constrained sensor nodes to estimate its phase.

The transmit phases of the two transmitters, however, are unknown. To measure these or to synchronize the nodes to transmit in-phase is not feasible in WSNs today. However, taking the relative phase offset of the signal at two receivers eliminates the transmit phase. While the receivers need to be time synchronized in this scheme, the required precision is determined by the frequency of the RSSI signal and not that of the original RF signal which is several orders of magnitude higher.

The measured phase difference is a function of the relative positions of the four nodes involved (two transmitters and two receivers) and the carrier frequency (figure 2). Therefore, this method is not pairwise ranging. It provides an estimate of the linear combination of the pairwise ranges of the four nodes involved, referred to as the quad-range. The following equation is shown to be true in Maróti et al. [22]: Embedded Image4.1where dABCD=dAD+dBCdACdBD is the quad-range, λ is the carrier wavelength, and φCD is the measured relative phase offset of the RSSI signal between nodes C and D.

Figure 2.

Radio interferometric ranging. (Online version in colour.)

To resolve the modulo ambiguity, ranging needs to be repeated at multiple carrier frequencies. As a quad-range estimate applies to a set of four nodes, it is not enough to simply compute their relative positions. In fact, at least six nodes are necessary to obtain enough equations to solve for the location of all nodes in two dimensions [22].

Noise, multi-path and other measurement errors have an interesting effect on the distribution of range estimates because of the modulo factor. A typical estimate will either be very close to the true range or will be an integer multiple of the wavelength away from it. The distribution can be considered a superposition of Gaussians, with their means full wavelengths from each other.

To support moderate multi-path environments where a substantial fraction of range estimates have large errors, RIPS performs range estimation and localization in an iterative manner [23]. Obtaining the range from the noisy phase measurements at various carrier frequencies is a least-squares optimization procedure. Then, a genetic algorithm performs the localization, minimizing an error function. This function is not defined as a simple average quad-range error. Instead, it is defined as the combination of a quad-range error measure and the number of bad range estimates. Hence, large outliers cannot distort the results if there are enough reasonable range estimates. The resulting location estimates are used in a new round of ranging estimation: the least-squares optimization is repeated using the same phase measurements, but the search is constrained by the current node location estimates. This is repeated for several iterations and allows the range estimation to recover from a few bad phase measurements due to multi-path. They may cause the global minimum of the least-squares estimate to be completely wrong, but the iterative procedure can find a local minimum corresponding to the correct solution.

While RIPS is admittedly complex and, hence, relatively slow (i.e. a full quad-range measurement at multiple frequencies takes a few tenths of a second), its combination of high accuracy (centimetre scale) and long effective range (even longer than the radio communication range) is unparalleled in WSNs. The most significant attribute of RIPS is that it measures the phase of a low-frequency signal, yet the measured phase corresponds to the wavelength of the high-frequency carrier signal. RIPS has been implemented on Mica2 nodes [24], a low-cost ($80), severely resource-constrained (4 kB RAM) COTS sensor node. The demonstrated accuracy is centimetre scale, while the maximum range is about 160 m. In other words, the accuracy is similar to ultrasonic methods at an order of magnitude longer range and with no extra hardware requirements. Its range is similar to RSSI-based techniques with two orders of magnitude better accuracy. It also compares favourably with GPSs. Low-cost GPS receivers provide two to three orders of magnitude higher error and require an extra chip per node, increasing the size, price and power consumption of the mote. Conversely, GPSs provide absolute coordinates in a short amount of time. The main limitation of RIPS is its susceptibility to multi-path. Hence, it does not currently work indoors.

Many variations of RIPS have appeared in literature. Triploc groups together the two transmitters and one of the receivers into an anchor ‘node’ that forms a quasi-antenna array [25]. As three of the four nodes are at known locations within a half wavelength of each other, a single phase measurement at a single carrier frequency constrains a receiver to a hyperbola in two dimensions. If this unknown receiver is not too close to the anchor (at least two wavelengths away), then the asymptote of the hyperbola provides an accurate approximation of the bearing to the node from the anchor. In other words, a sensor node with its single antenna makes a phase measurement of the RSSI signal, and it alone supplies its bearing from a known point. Hence, it can determine its location from two such measurements using triangulation, provided it is not collinear with the two anchors. Furthermore, an anchor here is nothing more than three sensor nodes placed next to each other with no extra hardware requirement.

RIPS has been shown to be able to estimate the speed of a moving sensor node by measuring its Doppler shift [26]. This is remarkable because a node moving at 1 m s−1 induces less than 1 Hz Doppler shift in a 400 MHz signal. However, it can be shown that the same Doppler shift appears in the interference signal that can be measured on the sensor node. If the relative speed of the node is measured at multiple known points, then not only the velocity but also the location of the node can be determined. Hence, RIPS can be used for cooperative tracking as well.

5. Future

In spite of the tremendous progress in wireless sensor node localization in the past decade, a universal solution has not emerged. The picture in outdoor localization is becoming clear. When GPSs emerged as a standard feature on mobile phones, the economies of scale caused the price of receivers to drop sharply while their performance kept increasing. An entry-level GPS receiver chip costs $10 today. While its accuracy is not what a typical WSN application requires, higher end receiver modules do provide 1 m accuracy with a clear view of the sky. Their price is in the $200–300 range. While the power requirements of GPSs have decreased significantly, they are still relatively high. For static deployments, however, GPS chips can be turned off after a location has been established. That is not true for mobile applications, but mobility itself consumes much more energy than the GPS or any electronic component does. Hence, as their limitations slowly disappear, GPSs are expected to dominate outdoor WSN applications in the future.

The interesting and difficult research challenges lie in indoor localization. The radio propagation environment in dense urban environments and inside buildings is extremely complex and dynamic. UWB provides high precision at a high cost. Also, because of its high bandwidth requirements, regulatory agencies limit the power UWB can legally use, severely restricting its effective range. These two factors have prevented UWB from widespread adoption in WSNs. Nevertheless, there is ongoing development of UWB technologies, so it may become the ultimate solution in indoor localization in the future.

Map-based RSSI techniques are available commercially. The most promising of these piggyback on existing WiFi infrastructures to control the cost. Nevertheless, map establishment is still time consuming and costly, and the dynamic RF environment limits precision to room-level. Also, the technique is inherently limited to long-term deployments. Military or emergency response applications, in which rapid deployment and high accuracy are primary requirements, still lack a feasible localization approach.

We believe that the future lies in multi-modal localization. The underlying idea is to use multiple sensors measuring different physical phenomena. They can overcome each other's limitations, or one can take over when the other becomes unavailable in the given environment. For example, GPSs can be augmented by an IMU as is frequently done in unmanned aerial vehicle navigation. For mobile sensor node tracking, the IMU can be used to provide tracking when the GPS-lock is lost, e.g. when the node moves inside a building. Of course, the longer the tracking relies on the IMU, the larger the error will grow. Air pressure sensors can be used to identify when the node moves from one floor to another. A pair of cameras can be used to measure ranges to objects in the environment and simultaneously build a three-dimensional map of it. In GPS-lacking environments, localization can also rely on signals of opportunity, such as TV broadcast stations and cell towers. These are all active areas of research today.

The utility, availability, precision, resource requirements, price and size of these different sensing modalities vary greatly. The decision of what combination of which methods to use is necessarily dictated by the requirements of the given application. Therefore, node localization, especially indoors, will remain highly application dependent for the foreseeable future.

Acknowledgements

This research was partially supported by ARO MURI grant W911NF-06-1-0076 and the TÁMOP-4.2.2/08/1/2008-0008 programme of the Hungarian National Development Agency.

Footnotes

References

View Abstract