An Indoor Localization Survey Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

The environment where localization is performed is known beforehand and can therefore be prepared to actively support positioning. That is, fixed reference units can be deployed in this environment, from the interaction of which the location of a mobile target can be derived.

. A 2D or 3D geometric location model can be applied to describe location information. This would typically be a local Cartesian or polar coordinate system, delivering x, y and z coordinates, or latitude, longitude and altitude, respectively. In certain applications, a context based, logical location model might be more appropriate. E.g. to express that a person is situated in a certain room, one can use a label (kitchen, living room, etc.) to refer to this room. This logical model can be derived from the geometric location model.

. The system's scale does not exceed a few hundred meters. Localization systems limited to a relatively small area are often referred to as local positioning systems (LPS), in order to explicitly distinguish them from large scale implementations like 2G/3G cellular network positioning systems, or global navigation satellite systems (GNSS). Indoor systems fall into the LPS category by nature.

. In all cases, positioning can be performed using relative or absolute localization methods, or both.

. Localization is performed in air.

. There may be differences regarding the environmental and ambient conditions where positioning must be performed (different walls, resulting in a varying grade of reflection, scattering and attenuation). These changes must be taken into account when choosing the localization technology.

2 Demands and performance measures in indoor localization [2].

In order to judge an implementation, its performance parameters must be analyzed.

. One of the major performance parameters of a localization system is its accuracy. This term indicates how far the estimated location deviates from the true location. Accuracy is often confused with precision. Precision is a measure of the reproducibility of a measurement. Therefore, when a statement is made about the resolution of a localization system, accuracy is commonly supplemented by precision (e.g. 20 cm accuracy over 90% of the time). For the applications mentioned above, the required localization accuracy ranges roughly from ±5 cm (fine-grained robot positioning) to about ±1m (coarse-grained guidance system). In some cases, even less accuracy is sufficient, for instance in occupancy detection in a room.

. Cost is a critical issue, particularly in applications where numerous units have to be equipped with localization technology, such as ad hoc sensor networks. It is therefore reasonable to use inexpensive standard off-the-shelf components whenever possible. Besides the mobile targets, infrastructure, deployment and maintenance cost must be considered.

. Power consumption must be considered, especially when a large number of battery driven mobile units are involved.

. Scalability; On the one hand, the system's outer borders must be easily extendable (e.g. by adding further rooms to the covered area). On the other hand, the system must be able to cope with an increasing number of mobile targets that need be located concurrently.

. The estimation cycle length, i.e., the time between two location updates, must be considered in some cases.

. Robustness; this includes the level of immunity against interference from other sources, but also from ambient.

. Particularly in those systems where active tags are carried around by humans, device size and weigh must be taken into account. If these are large and heavy, the positioning system might be turned down by its users for concerns of convenience.

. The utilized technology must be compatible with human beings and their animal companions that work or live within range of the localization system.

3 Relative and absolute positioning.

This classification is based on the type of sensors utilized, and the way of processing the gathered sensor data in order to compute the location of the target.. There exist a number of other classifications, one of them being the discrimination between indoor and outdoor positioning.

3.1 Relative positioning.

Relative positioning, also known as dead reckoning, describes the procedure of determining the current location of a mobile target by using course and velocity information. It can be subdivided into two approaches:

Odometry : Angular position data collected from rotary encoders placed at motor axles or wheels is recorded for a given length of time. Starting from a known position, the present location of a unit can then be determined by reconstructing the covered path. Odometry is fully self-contained but on the other side susceptible for errors caused by e.g. wheel slippage.

Inertial navigation systems (INS) use gyroscopes and accelerometers to measure the rate of rotation and acceleration of a unit. Position information is computed by integrating the measured data twice. Like odometric systems, inertial navigation is self-contained, but in the same way errors can accumulate without bounds. An inertial system can help to compensate momentary odometric errors.

The joint method utilizing both odometric and inertial sensors is sometimes referred to as gyrodometry.

3.2 Absolute positioning.

The absolute position of a mobile unit can be determined with the aid of fixed reference points located in the environment. The position of these reference points is known a priori. These references can be active or passive components. This section introduces three approaches:

Active beacons [3] are static components located at fixed and known positions of the environment. There are two different types of beacons: self-acting beacons that periodically emit a certain signature (e.g., a unique bit sequence), and sensitive beacons. Sensitive beacons either act as listeners or actively reflect a received signature emitted by the mobile unit. Beacon signals can be used for localization based on trilateration or triangulation techniques. Depending on the target application, ultrasound, RF or infrared transmission is used for range or angle estimation. The actual distance between a beacon and the mobile unit can be determined by either time of flight (TOF), phase shift or signal attenuation measurement. For example, TOF is computed in GPS receivers, while many laser ranging systems are based on phase shift measurement. Precise distance measurement using electromagnetic waves is tricky due to the high signal propagation speed.

Landmark recognition; Landmarks are static features of an environment that can be recognized by a mobile unit. Most of the time, landmarks are geometric shapes like rectangles, lines or barcodes. Besides these artificial objects, also natural items such as doors can serve as landmarks. Also, the general term scene analysis is often used in this context. Mobile units trying to localize themselves in an environment use camera vision and feature extraction to analyze the current scene. Once a landmark has been reliably recognized and identified, the unit's current position relative to the corresponding landmark can be calculated. This is accomplished by triangulation and trilateration as well as other methods. For this landmark recognition, no active components must be deployed in the environment. On the other hand, landmarks must be carefully designed and placed in order to guarantee reliable operation. This includes, for example, sufficient contrast (and possibly hue) relative to the background. An insufficient design and setup may lead to problems as soon as ambient conditions such as lighting change. Also, considerably more processing resources are necessary for landmark based positioning than for active beacon systems. As all optical approaches, these systems suffer at situations where an obstacle is located between the camera and the landmark, thus shadowing the landmark.

Model matching. In some applications, a mobile unit must be able to build a map or world model of an unknown environment while at the same time localizing itself within that map. While moving and exploring, a reference world model is created. Positioning is accomplished by comparing this (possibly pre-stored) reference model to a local model generated from on-board sensor data. Thus, two issues must be addressed: map building and map matching. Map building can also be accomplished in an offline training phase. Features of the environment are sometimes called fingerprints. Typically, no single sensor technique can collect all relevant data in a natural environment to guarantee reliable operation. Heterogeneous sensor systems are hence combined, for example laser radar, a sonar and an odometric system. Received radio signal characteristics such as signal strength or multipath patterns are also commonly used. Model matching is rather costly regarding the demands on processing, memory and therefore energy resources.

3.3 Comparison.

As mentioned before, all of the presented methods have certain strengths and weaknesses. The major drawback of relative positioning systems is their susceptibility for unbounded accumulated errors. So while easy to implement in most cases, dead reckoning should not be used as a stand alone solution. Instead, it may be combined with an absolute localization system. Regarding absolute position determining, both landmark recognition as well as model matching have very high demands on the processing performance of the mobile unit and are hence costly. Contrary to this, trilateration / triangulation based localization using active beacons can be performed with less computing efforts.

4 Localization schemes [4].

4.1 Trilateration.

Trilateration is a technique to compute a position of an object m, given its distances lam, lbm and lcm to three (in 2D. 3D localization requires four non-coplanar references) fixed non-collinear reference objects a, b and c (see Fig.1). For every distance lpm between m and p (with p {a, b, c}), a circle at (xp, yp) with radius lpm can be drawn around p. The point of intersection of three of these circles then yields the coordinates (xm, ym) of m. Therefore, trilateration can be expressed as finding the solution to the following system of quadratic equations:

(xm − xa)2 + (ym − ya)2 = lam2

(xm − xb)2 + (ym − yb)2 = lbm2

(xm − xc)2 + (ym − yc)2 = lcm2

Figure 1: Trilateration scheme

Trilateration requires the measurement of distances between the mobile unit and the reference units. This can be achieved by measuring either of the following:

. Time of flight (TOF)

. Phase shift

. Signal strength

4.2 Time of arrival measurements.

In order to obtain the range between two units m and p, beacon signals are transmitted between these devices. Typically, for time of flight range measurements a clock is needed on both units. If these clocks are synchronized, and if the time of emission of the beacon signal is known, then from the time of arrival (TOA) the time of flight (TOF) tpm can be determined. Multiplying by the signal propagation speed v yields the distance between the objects, lpm. In many applications one of the objects is not equipped with an appropriate clock at all, or the clocks are not synchronized. In this case, the distance lpm between the two units can be determined by sending a beacon signal from m to p and measuring the roundtrip time ∆tpm = 2 tpm + tr, given that the signal is reflected by object p:

The beacon signal may be passively (reflection at surface) or actively (retransmission) reflected. The passive reflection technique is well known as RADAR (radio detection and ranging), which is used in large scale outdoor environments. When optical radiation or acoustic waves are used, the terms LIDAR and SONAR (light detection and ranging / sound navigation and ranging), respectively, are applied. Passive reflection indoors is not feasible for most signal technologies (e.g. RF) because of the high degree of multipath occurrences (i.e., echoes due to signal reflection at walls and objects). For an active reflection, beacon retransmission latency tr must be considered. In the passive case tr = 0 holds. If active beacons are deployed in the area, commonly the one-way measurement approach is applied, i.e. the units must be synchronized. In case of radio signals, synchronization of the clocks is critical. Due to the high propagation speed, even a small synchronization deviation may result in huge measurement errors.

4.3 Phase shift.

The time of flight between two objects p and q can also be determined using a continuous periodic signal, e.g. a (periodically) modulated RF carrier. The signal generated and transmitted by unit p is after the time of flight received by unit q. Internally, unit q generates the same signal and performs a cross correlation between the internal and the received signal. If the units are perfectly synchronized, i.e. the signals are generated concurrently; the result of this operation yields the phase difference _ of the two signals. This phase difference is proportional to the distance between the two objects, d. The distance can then be computed as: , where v is the signal propagation speed and T the signal period. To avoid any ambiguities, must hold.

If the signal is passively reflected by an object, no synchronization is required, and the roundtrip time can be measured. This type of roundtrip time measurement is often used with mobile robots. These robots scan their environment for obstacles using rotating infrared laser beams or ultrasonic waves. The modulated emitted signal is auto-correlated with the reflected received signal. The time of flight corresponds to the phase shift of the modulation signal.

4.4 Received signal strength (RSS).

A common ranging approach that goes without intricate clock synchronization is based on signal attenuation. That is, range is deduced from the received signal strength (RSS). However, indoor RF signal strength is non-linear with distance and covered with non-Gaussian noise as a result of multipath effects and environmental effects such as building geometry and traffic. A number of empirical models have been set up. However, these models strongly depend on signal properties and on the environment in which measurements are performed. Due to the large uncertainty of the path loss model RSS rarely provides the accuracy required for indoor range estimation. Instead of ranging, in most implementations exploiting RSS information, a map of fingerprints is built in a training phase. During operation, measurements are correlated with the map data in order to estimate location.

4.5 Hyperbolic localization.

Instead of acquiring times of arrival (TOA) between reference units and the mobile unit, commonly time differences of arrival (TDOA) are measured. The setup of the resulting localization principle which is commonly referred to as hyperbolic localization is shown in Fig. 2.

Figure 2: Hyperbolic localization scheme

Signals emitted from the mobile unit m are received by three reference units a, b and c. lpq denotes the physical distance between nodes p and q, with p, q {a, b, c,m}). For the exact solution in the plane, two TDOA measurements are required which yield the distance differences d1 and d2. In 3D, three TDOA measurements (i.e., four reference units) are necessary. Unlike TOA measurements, TDOA measurements are independent of the signal emission time. Therefore, only the reference units must be synchronized among each other. The term hyperbolic arises from the fact that each distance difference yields a hyperbola A common drawback of the direct hyperbolic positioning approaches mentioned so far is that they yield multiple solutions. The Taylor series method does not - but on the other hand it requires an initial location estimate. An alternative localization paradigm exhibiting none of these constraints is using a non-linear optimization strategy.

4.6 Triangulation

Localization based on trilateration implies that participants must be able to measure distances (or distance differences) between each other. Triangulation works in a similar manner, but instead of distances, angles are measured. In fact, it can be shown that triangulation can be transformed to trilateration by simple means. Two cases can be distinguished, as illustrated in Fig. 2.3.

. The mobile unit measures angles towards signals emitted by fixed reference units (see Fig. 3(a)). The collected data yield position and orientation.

Figure 3: Triangulation schemes

. Reference units measure angles towards the signal emitted by the mobile unit (see Fig. 3(b)). Only a location estimate, but not the orientation of the mobile target, can be obtained. However, compared to hyperbolic localization, only two reference units need be deployed (in 2D), instead of three.

4.7 Angle of arrival measurement [5].

The process of direction finding (DF) is usually accomplished by an angle of arrival (AOA) measurement. The particular measurement arrangement depends on the signal technology used for localization. For instance, many sensing elements like ultrasonic transducers or infrared photodiodes have directional receiving patterns while e.g. rod antennas do not. Therefore, different approaches must be applied to obtain angle information. The most straightforward technique is using mechanically steered narrow beam width elements to perform an angular sweep, like in laser scanners. However, mechanical components are error prone and demand additional control circuitry and thus cost. Therefore they should be avoided in receiver design. Instead, angle diversity techniques are utilized in order to exploit the directionality of the receiver. The most common all-electronic techniques are:

. Direction finding using an array of several angularly displaced directional sensors.

Figure 4: Angle of arrival measurement

Fig. 2.4(a) shows such a detector incorporating a number of infrared photodiodes.

. Direction finding of pulses by TDOA. Fig. 4(b) shows an arrangement of two sensors s1 and s2 located at a distance r. We assume that both sensors detect a beacon signal originating from the same signal source located at a distance l. For we can consider the incoming signals to be parallel. The runtime difference ∆t is proportional to the difference of propagation paths, ∆l. The angle α can therefore be determined as where ∆l resp. ∆t can be determined by a TDOA measurement. Note that in the case of electromagnetic waves, an extremely high timing resolution is required for this TOF measurement in order to achieve an acceptable granularity of angles. Therefore this approach is rarely used in practice.

. Direction finding of continuous wave signals by multiple omni-directional detector elements arranged under a fixed displacement (typically, an antenna array). A common direction finding array is the uniform linear array (ULA). In this configuration, the elements are placed on a straight line having equal spacing. Typically, this inter-element spacing is in the order of half the wavelength of the carrier frequency of the received signal. The array usually consists of 4 − 10 elements. The signal received by either antenna is sampled and passed to a digital signal processor (DSP), where a direction finding algorithm is applied. Often used approaches include beamforming and the MUSIC algorithm. The angular resolution is limited by the number of elements, signal to noise ratio, hardware non-idealities and calibration errors.

4.8 Comparison of absolute positioning techniques.

RSS has a very low accuracy and thus strongly depends on additional algorithmic support.

TOA is based on the assumption that all units have a synchronized time reference. The same is true for TDOA except for the fact that the time of emission of the signal is irrelevant. Hence, only the reference units, but not the mobile unit, must be synchronized.

The advantage of AOA techniques over TOA and TDOA is that no units need be synchronized at all. However, the trade-off is that significantly larger and more complex hardware is required. Furthermore, the location estimate degrades as the mobile target moves farther from the reference units.

The discussed techniques are wide-spread among state of the art implementations. In certain systems, hybrid techniques (e.g. TDOA plus AOA) are used. In most systems, redundant reference units are deployed in order to increase system scale and overcome shadowing of single reference units. The resulting scheme is sometimes called multilateration to indicate the use of additional units.

5 Stochastic methodologies

An important issue in any sensor system is measurement uncertainty: Measurements are only accurate to a certain degree. As a result, the estimate of the system is erroneous. There are several pieces of information that - if available - can help to delimit this error. Knowledge about the statistical error distribution can be exploited to make assumptions of a dynamic system's state. In the case of a localization system, the state of the system is defined by 2D or 3D coordinates, but it can as well incorporate orientation and velocity information. Note that the error distributions may be individually shaped for each sensor. It is a challenge to merge the output of different kinds of sensors. This process is commonly referred to as sensor fusion. An assumption on the current location of a mobile target (commonly called belief ) can further be backed up if information on the system history (i.e., the previous state) is available. For instance, it is likely that if a person resides at position (x, y) at one point in time, he/she will still be close to (x, y) one moment later. For this inference, knowledge about the dynamics of the system must be available (e.g., how fast can a person move at most).

A large number of approaches are available today ( Bayesian filters, Kalman filter and the particle filter).

6 Employed signal technologies.

Not only the positioning technique is a characteristic of a localization system, but also the technology it is based on. Absolute localization systems are commonly ultrasonic, infrared, optical, magnetic field or radio based. These technologies differ in many properties, most importantly range, robustness against ambient variations and signal propagation issues. Among the latter are signal velocity and degree of reflection, scattering and attenuation at walls and obstacles. Naturally, the design of the transceivers and the data processing hardware differs according to the signal technology. Therefore, cost, power consumption and the required computing resources can vary significantly.

The primary source of error in indoor localization is multipath propagation caused by signal reflections that overlap with the direct line of sight signal at the receiver. This is true for both sound and electromagnetic waves. The localization techniques described in the previous sections rely on the assumption that the direct line of sight signal can be discriminated from echos resulting from other propagation paths. Therefore, depending on the applied technology, more or less effort must be undertaken in order to detect the signal component that arrives first. Within a building, the ambient conditions such as temperature and humidity are subject to temporal and spatial variations. Temporal variations take place at different time scales, e.g. the time of day or season of the year. Spatial variations occur due to heaters or air conditioners, or direct sunlight in certain parts of a room. According to the utilized technology, these variations can have a heavy impact on the accuracy of the localization system. In the following, aspects of the above-mentioned signal technologies are stressed.

. Ultrasound is often used in indoor localization. Due to the low propagation speed highly accurate range measurements can be accomplished without much effort. For the same reason, multipath components can be separated easily. The The equation shows that the speed of sound is significantly affected by temperature changes. Depending on the desired accuracy, this effect must be combated in the design of a localization system. Contrary to ultrasound, the propagation of electromagnetic waves may be considered robust against ambient changes in air. Another drawback of ultrasound is the fact that the range of these signals is rather limited. The most commonly used - and therefore most inexpensive - ultrasound transducers operate at a center frequency of 40 kHz. Contrary to humans who do not hear sound above 20 kHz, some animals do. Some pets are able to hear frequencies up to 50 kHz (dogs) or 60 kHz (cats). Being permanently exposed to a stream of acoustic pulses may be perceived as noise pollution by these animals. Hence, these systems are perhaps not appropriate for domestic use. Naturally, transducers operating at higher frequencies can be employed. Unfortunately these devices are more expensive. Furthermore, they demand higher transmit power levels because the attenuation of sonic waves in air increases with frequency.

. Infrared components are compact and give rise to very low cost. One of the major challenges is suppressing interfering noise, mainly resulting from ambient light sources. Depending on the wavelength, IR reflects off most surfaces of indoor environments. The typical range is up to 5m. Usually, due to scattering, only the first reflection must be considered in multipath considerations. Furthermore, equal wavelengths can be used in adjacent rooms without interference because the entire infrared signal is blocked by obstacles or walls. Infrared can roughly be subdivided into active and passive approaches. Active infrared denotes systems where objects or beacons are equipped with IR transmitters such as light emitting diodes. In passive systems, objects are localized as a result of their natural emission of radiation. Of course, radiation is not only emitted by target objects but also by the environment. Therefore, only objects at a temperature other than that of the environment (e.g. humans in a room at 25.) can be detected. The indoor infrared channel has found good coverage among communication technology researchers in recent years.

IR is well applicable in sensitive areas like hospitals or in environments infested by strong EMI, e.g. industrial production sites. In these environments, radio may be critical since it interferes with vital medical equipment, or operation may be heavily confined due to EMI. Although infrared is immune to such interference, it is of course subject to noise. In most indoor environments there exists significant ambient natural (sunlight) and artificial (incandescent and fluorescent) lighting inducing noise in the infrared receiver. The interference of these noise sources can prevent infrared systems from operating at all or demand excessive transmission power levels. The emitted power is limited by concerns of power consumption and eye safety, especially at wavelengths < 1400 nm.

. Considerable advances have also been achieved in vision based localization systems. With the increasing sales of digital cameras and pervasive integration of cameras in mobile phones, components like CCD sensors and additional simple optics became inexpensive. However, vision systems still require significant computational and power resources for image processing, feature extraction etc. As a consequence, in spite of relatively inexpensive sensors, cost for vision based localization systems are remarkable, especially when multiple units must be equipped. Furthermore, these systems can be abused for a detailed observation of people.

. Using magnetic fields for positioning has the advantage that any nonmagnetic material can be penetrated by the field with no loss of position accuracy. These systems utilize sensors placed on the target objects to measure the DC magnetic field generated by a nearby transmitter source. Field propagation is usually limited to about 3m. Unfortunately this technology is extremely sensitive to interference from a number of sources like CRT monitors. Moreover the field can be affected by nearby objects comprised of magnetic materials. As a result, these localization systems require precise calibration and a static environment.

. RF technology can further be split according to the frequency range used, i.e. narrow band and wideband systems. Narrow band systems often used for localization are Wireless LAN (IEEE 802.11b/g), Bluetooth (IEEE 802.15), and RFID (Radio frequency identification). WLAN operates in the 2.4 GHz ISM band at a range of 50 − 100m. In recent years, these systems have been installed in thousands of office buildings, homes and public places. Hence it seems worthwhile to employ these infrastructures for localization [6, 7]. Bluetooth has been designed as a cable replacement technology. Like WLAN, it operates in the 2.4 GHz band, but at lower data rate and - depending on the device class - at shorter range. Bluetooth has achieved considerable coverage, particularly in mobile appliances like laptops and PDAs. Neither WLAN nor Bluetooth provide localization capabilities. Commonly, RSS and signal to noise ratio information are exploited to deduce location.

RFID tags can be active or passive, that is, they are equipped with a battery or act as a battery-less transponder. Accordingly, their range is limited to a few ten meters for active and 1 − 2m for passive tags, respectively. RFID tags are inexpensive and - if passive - need no maintenance like battery charging or replacement. RFID is mostly used to obtain proximity information rather than true localization. That is, we can only tell that a tag is within range of an RFID reader, but not where. Short pulse ultra wideband (UWB) [8, 9] is yet another radio technology suitable for indoor localization. Two physical layers for high and moderate data rates (IEEE 802.15.3a/4a) are currently being specified. A wide frequency spectrum can be achieved by classic spread spectrum approaches like DSSS (direct sequence spread spectrum). The alternative idea in UWB is the usage of electromagnetic pulses with an extremely short pulse width in the order of 1 ns. This approach is particularly advantageous for localization in a cluttered indoor environment, where severe multipath fading occurs. Due to the short pulse length, the direct path can be discriminated from echos more easily.

In Tab. 2.1, the most important properties of the presented technologies in the context of indoor positioning are summarized.

Signal technology




Slow signal propagation

Facilitates slow clock speed

High accuracy

Susceptible to ambient variations

Might influence animals


Inexpensive components

Usually few multipath components

Range: 5m

Line of sight required

Susceptible to interference from ambient light or thermal radiation sources (depending on the used signal wavelength)

Optical (camera)

No active emitters required

No active emitters required Line of sight required

Illuminated environment required

Costly signal processing

DC magnetic field

High accuracy

Range: 1 − 3m

Highly susceptible to environmental interference

High deployment cost due to complex calibration procedure

Narrow band radio

Signal traverses through obstacles

Highly susceptible to multipath effects

Range of WLAN: 50 − 100m

Range of Bluetooth: 10 − 100m

(depending on device class)

Range of RFID: 1 − 2m (passive tags), a few ten meters (active tags)

Wideband radio

Signal traverses through obstacles

High accuracy

Fairly robust against multipath effects

Low power


Table 2.1: Employed signal technologies

7. Position estimation algorithms [10]

Position estimation can be defined as the process of estimating the position of a node, called the "target" node, in a wireless network by exchanging signals between the target node and a number of reference nodes. Also, depending on whether the position is estimated from the signals traveling between the nodes directly or not, two different position estimation schemes can be considered. Direct positioning refers to the case in which the position estimation is performed directly from the signals traveling between the nodes. On the other hand, two-step positioning extracts certain signal parameters from the signals First, and then estimates the position based on those signal parameters. Although the two-step positioning is suboptimal in general, it can have significantly lower complexity than the direct approach. Also, the performance of the two approaches is usually very close for sufficiently high signal bandwidths and/or signal-to-noise ratios (SNRs). Therefore, the two-step positioning is the common technique in most positioning systems.

In the first step of a two-step positioning algorithm, signal parameters, such as time-of-arrival (TOA) and received signal strength (RSS), are estimated. Then, in the second step, the position of the target node is estimated based on the signal parameters obtained in the first step, In the second step of position estimation, mapping (fingerprinting) approaches, geometric or statistical techniques can be used depending on the accuracy requirements and system constraints.

7.1. Estimation of Position Related Parameters

Depending on accuracy requirements and system constraints, various signal parameters can be estimated in the first-step of a positioning algorithm. Commonly, signal parameters employed in positioning are related to power, direction and/or timing of a received signal.

7.1.1. Received Signal Strength (RSS)

The power, or energy, of a signal traveling between two nodes is a signal parameter that contains information related to the distance ("range") between those nodes. The RSS parameter can be used together with a path-loss and shadowing model to provide a distance estimate.

Therefore, in the error-free case, an RSS estimate at a node determines the position of the other node on a circle for two-dimensional positioning, as shown in Figure 5.

Fig 5: measure of the RSS and its circle of uncertainty

A signal traveling from one node to another experiences fast (multipath) fading, shadowing and path-loss. Ideally, averaging RSS over a sufficiently long time interval excludes the effects of multipath fading and shadowing. In practice, the observation interval is not long enough to mitigate the effects of shadowing. Therefore, the received power is commonly modeled to include both path-loss and shadowing effects, the latter of which are modeled as a zero mean Gaussian random variable. The accuracy deterioratesas the distance between the nodes increases.

7.1.2. Angle of Arrival (AOA)

The angle between two nodes can be determined by estimating the AOA parameter of a signal traveling between the nodes (Figure 6). Commonly, antenna arrays are employed in order to estimate the AOA of a signal6. The main principle behind the AOA estimation via antenna arrays is that differences in arrival times of an incoming signal at different antenna elements include the angle information if the array geometry is known.

Figure 6: AOA measurement between two nodes.

For narrowband signals, time differences can be represented as phase shifts. Therefore, the combinations of the phase shifted versions of received signals at different array elements can be tested in order to estimate the AOA. However, for wideband systems, time delayed versions of received signals should be considered, since a time delay cannot be represented by a unique phase value for a wideband signal. In order to study the effects of system parameters on the achievable accuracy of an AOA estimator, consider a uniform linear array (ULA) with Na elements and assume the same fading coefficient  for all signals arriving at the array elements.

It is observed that as the SNR, effective bandwidth, inter-element spacing and/or the number of antenna elements is increased, the accuracy of AOA estimation also increases. It is also noted that a ULA cannot detect obtuse angles as accurate as it can detect acute angles.

7.1.3. Time of Arrival (TOA)

Similar to the RSS parameter, estimating the flight time of a signal traveling from one node to another, called TOA, provides information related to the distance between those two nodes. Therefore, in the absence of any errors, a TOA estimate provides an uncertainty region in the shape of a circle as shown in Figure x.

In order to calculate the TOA parameter for a signal traveling between two nodes, the nodes must either have a common clock, or exchange timing information by certain protocols.

Conventionally, TOA estimation is performed via correlator or matched filter (MF) receivers. In practical systems, the signal arrives at the receiver via multiple signal paths. In such multipath environments, the conventional schemes become suboptimal as they use the transmitted signal to set their template signals or MF impulse responses. In order to obtain accurate TOA estimation in multipath environments, high resolution time delay estimation techniques, have been studied for narrowband systems, and first path detection algorithms are proposed for ultra-wideband (UWB) systems.

It is observed that unlike the RSS estimation, the accuracy of the TOA estimation can be improved by increasing the SNR and/or the effective signal bandwidth. Therefore, for (ultra) wideband systems, TOA estimation can provide very accurate distance information.

7.1.4. Time Difference of Arrival (TDOA)

In the absence of synchronization between the target node and the reference nodes, the TDOA estimation can be performed if there is synchronization among the reference nodes. In this case, the difference between the arrival times of two signals traveling between the target node and the two reference nodes is estimated, which determines the position of the target node on a hyperbola, with foci at the two reference nodes, as shown in Figure 7.

Figure 7: A TDOA measurement

One way to estimate TDOA is to first estimate TOA for each signal traveling between the target node and a reference node, and then to obtain the difference between the two estimates. Since the target node and the reference nodes are not synchronized, the TOA estimates include a timing offset, which is the same in all estimates as the reference nodes are synchronized, in addition to the time of flight.

Another way to implement TDOA estimation is to perform cross-correlations of the two signals traveling between the target node and the reference nodes, and to calculate the delay corresponding to the largest cross-correlation value.

Although the cross-correlation based TDOA estimation works well for single path channels and white noise models, its performance can degrade considerably over multipath channels and/or colored noise. In order to improve the performance of the cross-correlation scheme and, generalized cross-correlation (GCC) techniques are proposed. In GCC based TDOA estimation, filtered versions of the signals are cross-correlated, which corresponds to shaping the cross-power spectral density (cross-PSD) of the transmitted signals, in order to provide robustness against colored noise.

7.1.5 Other Position Related Parameters

In some positioning systems, two or more of the position related parameters, studied in the previous subsections, can be employed in order to obtain more information about the position of the target node.

In addition to the RSS, AOA and T(D)OA parameters and their combinations, another scheme for position related parameter estimation involves obtaining multipath power delay profile (PDP) or channel impulse response (CIR) related to a received signal. In some cases, PDP or CIR estimation can provide significantly more information about the position of the target node than the previously studied schemes. However, extracting the position information from such parameters commonly requires a database consisting of previous PDP (or CIR) estimates. Therefore, algorithms employing PDP or CIR estimation implement training phases, before the actual position estimation process begins.

7.2 Position Estimation

The second step of a two-step positioning algorithm involves estimation of position from the position related parameters estimated in the first step. Depending on the presence of a database (training data), two types of position estimation techniques can be considered:

Mapping (Fingerprinting) techniques use a database that consists of previously estimated signal parameters at known positions to estimate the position of the target node. Commonly, the database is obtained by a training (off-line) phase before the real-time positioning starts.

Geometric and statistical techniques do not utilize such a database, and estimate the position of the target node directly from the signal parameters estimated in the first step of the positioning algorithm by using geometric relationships and statistical approaches, respectively.

7.2.1 Mapping Techniques

The main idea behind position estimation via mapping techniques is to determine a regression scheme based on a set of training data, and then to estimate position of a given node according to that regression function.

A mapping technique first determines a position estimation rule (pattern matching algorithm/regression function), and then estimates the position l of a given target node based on a parameter vector m related to that target node. Some common mapping techniques employed in position estimation include k-nearest-neighbor (k-NN) estimation, support vector regression (SVR) and neural networks.

Due to its simplicity, the k-NN estimation technique is considered in this section in order to provide intuition on mapping based position estimation. In its simplest form, the k-NN estimation technique estimates the position of the target node as the position vector in the training set T corresponding to the parameter vector that has the shortest distance to the given (estimated) parameter vector m.

The main advantage of mapping techniques is that they can provide very accurate position estimation in challenging environments with multipath and NLOS propagation. However, the main disadvantage is the requirement that the training database should be large enough and representative of the current environment for accurate position estimation. In other words, the database should be updated frequently enough so that the channel characteristics in the training and position estimation phases do not differ significantly. Such an update requirement can be very costly for positioning systems operating in dynamic environments, such as for an outdoor positioning system.

In the absence of a training database, the position is estimated directly from the position related parameters obtained in the first step of a two-step positioning algorithm. In this case, one can employ either a deterministic approach and estimate the position according to certain geometric relationships, or a statistical approach and try to obtain the most likely position for the target node.

7.2.2. Geometric techniques

They solve for the position of the target node as the intersection of position lines obtained from a set of position related parameters at a number of reference nodes. An RSS or a TOA parameter defines a circle for the position of the target node; hence three parameter estimates can be used to determine the position via trilateration. On the other hand, an AOA parameter defines a straight line passing through the target node and the reference node. Therefore, two AOA parameters are sufficient to locate the target node via triangulation. In the case of TDOA based positioning, each TDOA parameter determines a hyperbola for the position of the target node. For three reference nodes, two range differences (obtained from TDOA parameters) define two hyperbolas, the intersection of which yields the position of the target node. However, the position may not always be determined uniquely depending on the geometrical conditioning of the nodes.

The geometric techniques can also be applied to hybrid systems, in which multiple types of position related parameters, such as TDOA/AOA or TOA/TDOA, are employed in position determination.

One of the disadvantages of geometric techniques is that they do not provide a theoretical framework in the presence of noise in position related parameters. When the position lines intersect at multiple points, instead of a single point, due to random errors in the parameter estimation step, the geometric approach does not provide any inside as to which point to choose as the position of the target node. In addition, as the number of parameters increases, the number of intersections increases even further.

7.2.3. Statistical Techniques

Unlike the geometric techniques, the statistical approach presents a theoretical framework for position estimation in the presence of multiple position related parameter estimates with or without noise.

Depending on the available information related to the noise term, parametric or nonparametric approaches can be followed. In the case that the probability density function of the noise is known except for a set of parameters, parametric approaches, such as Bayesian and maximum likelihood (ML) estimation, can be employed. In the absence of information about the form of the probability density function of the noise, non-parametric techniques need to be used. Although the form of the density function is unknown in the nonparametric case, there can still be some generic information about some of its parameters, such as its variance and symmetry properties, which can be used to design non-parametric estimation rules, such as the least median of squares technique, the residual weighting algorithm and the variance weighted least squares technique.