Related Work

Localization approaches typically rely on some form of communication between reference points with known positions and the receiver node that needs to be localized. We classify the various localization approaches into two broad categories based on the granularity of information inferred during this communication. Approaches that infer fine-grained information such as the distance to a reference point based on signal strength or timing measurements fall into the category of finegrained localization methods; those that infer coarse-grained information such as proximity to a given reference point are categorized as coarse-grained localization methods.

Fine-Grained Localization

Fine-grained localization methods can be classified further into range-finding and directionality-based methods, depending on whether ranges or angles relative to reference points are being inferred. Additionally, signal pattern matching methods are also included in fine-grained localization methods.

In range-finding methods, the ranges of the receiver node to several reference points are determined by one of several timing- or signal-strength-based techniques. The position of the node can then be computed using multilateration (e.g., see [2]). We discuss timing- and signal-strength-based rangefinding methods separately.

Timing

The distance between the receiver node and a reference point can be inferred from the time of flight of the communication signal.

The time of flight may be calculated using the timing advance technique which measures the amount the timing of the measuring unit has to be advanced in order for the received signal to fit into the correct time slot. This technique is used in GPS [1] and Pinpoint’s Local Positioning System (LPS) [3]. GPS measures one-way flight time, whereas LPS measures round-trip time (thereby eliminating the need for time synchronization).

GPS [1] is a wide-area radio positioning system. In GPS each satellite transmits a unique code, a copy of which is created in real time in the user-set receiver by the internal electronics. The receiver then gradually time shifts its internal clock until it corresponds to the received code, an event called lock-on. Once locked on to a satellite, the receiver can determine the exact timing of the received signal in reference to its own internal clock. If that clock were perfectly synchronized with the satellite’s atomic clocks, the distance to each satellite could be determined by subtracting a known transmission time from the calculated receive time. In real GPS receivers, the internal clock is not quite accurate enough. An inaccuracy of a mere microsecond corresponds to a 300-m error.

Pinpoint’s 3D-iD system [3] is an LPS that covers an entire three-dimensional indoor space and is capable of determining the 3-D location of items within that space. The LPS subdivides the interior of the building into cell areas that vary in size with the desired level of coverage. The cells are each handled by a cell controller which is attached by a coaxial cable to up to 16 antennas. It provides an accuracy of 10 m for most indoor applications, although some may require accuracy of 2 m. The main drawback of this system is that it is centralized, and requires significant infrastructural setup.

Alternately, the time of flight can be calculated by making explicit time-of-arrival measurements based on two distinct modalities of communication, ultrasound and radio, as in the Active Bat [2] and more recently in [4]. These two modalities travel at vastly different speeds (350 ms–1 and 3 x 10–8 ms–1, respectively), enabling the radio signal to be used for synchronization between the transmitter and the receiver, and the ultrasound signal to be used for ranging. The Active Bat system, however, relies on significant effort for deployment indoors. Ultrasound systems may not work very well outdoors because they all use a single transmission frequency (40 kHz), and hence there is a high probability of interference from other ultrasound sources.

Signal Strength

An important characteristic of radio propagation is the increased attenuation of the radio signal as the distance between the transmitter and receiver increases. Radio propagation models [5] in various environments have been well researched and have traditionally focused on predicting the average received signal strength at a given distance from the transmitter (large-scale propagation models), as well as the variability of the signal strength in close spatial proximity to a location (small-scale or fading models). In the RADAR system [6], Bahl et al. suggest estimating distance based on signal strength in indoor environments. They compute distance from measured signal strength by applying a wall attenuation factor (WAF) based signal propagation model. The distance information is then used to locate a user by triangulation. This approach, however, yielded lower accuracies than RF mapping of signal strengths corresponding to various locations for their system. Their RF-mapping-based approach is quite effective indoors, unlike ours, but requires extensive infrastructural effort, making it unsuitable for rapid or ad hoc deployment.

Signal Pattern Matching

Another fine-grained localization technique is the proprietary Location Pattern Matching technology, used in U.S. Wireless Corporation’s RadioCamera system [7]. Instead of exploiting signal timing or signal strength, it relies on signal structure characteristics. It turns the multipath phenomenon to surprisingly good use: by combining the multipath pattern with other signal characteristics, it creates a signature unique to a given location. The Radio- Camera system includes a signal signature database for a location grid of a specific service area. To generate this database, a vehicle drives through the coverage area transmitting signals to a monitoring site. The system analyzes the incoming signals, compiles a unique signature for each square in the location grid, and stores it in the database. Neighboring grid points are spaced about 30 m apart. To determine the position of a mobile transmitter, the RadioCamera system matches the transmitter’s signal signature to an entry in the database. The system can use data from only a single point to determine location. Moving traffic and changes in foliage or weather do not affect the system’s capabilities. The major drawback of this technique, as with RADAR [6], is the substantial effort needed for generation of the signal signature database. Consequently, it is not suited for the ad hoc deployment scenarios in which we are interested.

Directionality

Another way of estimating location is to compute the angle of each reference point with respect to the mobile node in some reference frame. The position of the mobile node can then be computed using triangulation methods.

An important example of directionality-based systems are the VOR/VORTAC stations [8], which were used for long distance aviation navigation prior to GPS. The VOR station transmits a unique omnidirectional signal that allows an aircraft aloft to determine its bearing relative to the VOR station. The VOR signal is electrically phased so that the received signal is different in various parts of the 360° circle. By determining which of the 360 different radials it is receiving, the aircraft can determine the direction of each VOR station relative to its current position.

Small aperture direction finding is yet another directionality- based technique used in cellular networks. It requires a complex antenna array at each cell site location. The antenna arrays can in principle work together to determine the angle (relative to the cell site) from which a cellular signal originated. When several cell sites can determine their respective angles of arrival, the cell phone location can be estimated by triangulation. There are two drawbacks of this approach which make it inapplicable to our application domain. The cost of the complex antenna array implies that it can be placed only at the cell sites. Second, the cell sites are responsible for determining the location of the mobile node, which will not scale well when we have a large number of such nodes and desire a receiver-based approach.

Directionality-based methods are not very effective in indoor environments because of multipath effects.

Coarse-Grained Localization

The work we describe in this article is perhaps most similar to earlier work done in coarse-grained localization for indoor environments using infrared (IR) technology.

The Active Badge [9] system was one of the earliest indoor localization systems. Each person or object is tagged with an Active Badge. The badge transmits a unique IR signal every 10 s, which is received by sensors placed at fixed positions within a building and relayed to the location manager software. The location manager software is able to provide information about the person’s location to the requesting services and applications.

Another system based on IR technology is described in [10]. This system requires IR transmitters to be located at fixed positions inside the ceiling of the building. An optical sensor sitting on a head-mounted unit senses the IR beacons, and system software determines the position of the person.

Both these IR-based solutions perform quite well in indoor environments, because IR range is fairly small and can be limited to the logical boundaries of a region, such as a room (by walls). On the other hand, the same technique cannot be applied using RF in indoor environments, because RF propagation in indoor environments suffers from severe multipath effects that make it impossible to limit the RF range to exactly within a room. The short range of IR, which facilitates location, is also a major drawback of these systems because the building has to be wired with a significant number of sensors. In the few places where such systems have been deployed, sensors have been physically wired in every room of the building. Such a system scales poorly, and incurs significant installation, configuration, and maintenance costs. IR also tends to perform poorly in the presence of direct sunlight and hence cannot be used outdoors.