Various real-life environments are exceptionally harsh for signal propagation, rendering well-known trilateration techniques (e.g. GPS) unsuitable for localization. Alternative proximity-based techniques, based on placing sensors near every location of interest, can be fairly complicated to set up, and are often sensitive to sensor failures or corruptions. The authors propose a different paradigm for robust localization based on identifying codes, a concept borrowed from the information theory literature. This chapter describes theoretical and practical considerations in designing and implementing such a localization infrastructure, together with experimental data supporting the potential benefits of the proposed technique.
TopProblem Statement
Dense indoor or urban settings, underwater or underground systems, and many emergency environments typically exhibit signal propagation properties that are extremely difficult to predict. Within these environments, signal strength or time-of-flight measurements do not accurately convey distance information, often due to spurious multi-path effects, occlusions, or noise that is very hard to characterize or model. As a result, traditional trilateration techniques, such as the Global Positioning System (GPS), are very hard to adapt to such systems without significant and often catastrophic error.
In practice, many schemes for localization in such environments are proximity-based, meaning that the location of an object is determined by the closest sensor. Generally, these systems are based on short range sensing techniques such as infrared in the Active Badge system (Want, Hopper, Falcao, & Gibbons, 1992), ultrasound (combined with RF) in the Cricket system (Priyantha, Chakraborty, & Balakrishnan, 2000), Bluetooth in (Aalto, Göthlin, Korhonen, & Ojala, 2004), and radio frequency identification - RFID in the LANDMARK system (Ni, Liu, Lau, & Patil, 2005). Some of these approaches utilize several nearby sensors to make the localization more accurate, but the underlying system organization remains proximity-based, so that the sensing area must be divided into similarly-sized regions, typically with minimal intersection. Properly setting up such systems can be fairly complicated, and the localization provided can be sensitive to sensor failures or corruptions, as well as interferences due to the significant environment changes that might take place.
Another approach to localization involves careful measurement and mapping of signal features within the coverage area. These methods are commonly referred to as fingerprinting, since a specific location region is identified by a unique set of features (i.e. a fingerprint) of the sensed signal. One of the most common fingerprinting techniques is based on the signal strength (or signal to noise ratio) of a received RF signal. Systems such as RADAR (Bahl & Padmanabhan, 2000), SpotOn (Hightower, Borriello, & Want, 2000), and Nibble (Castro, Chiu, Kremenek, & Muntz, 2001) map the signal strength received from several beacons onto a coverage area in order to train a probabilistic localizer. Other similar systems focus on commercially used communication standards to provide localization services, such as Wi-Fi (Ladd et al., 2002), and Groupe Spécial Mobile - GSM (Varshavsky, de Lara, Hightower, LaMarca, & Otsason, 2007). These systems usually perform with relatively high accuracy, although they require careful and complex planning. There are also inherent issues with robustness in such systems, since signal strength or signal to noise ratio are susceptible to the radio frequency - RF propagation channel, and can vary considerably with small changes within the environment, especially in the environments considered.
The performance of a location detection system can be characterized by many measures: resolution, responsiveness (delay until detection), etc. For many applications an important performance measure is the probability of correctly determining the region in which a target is located (i.e. the correctness of the system). For example, within the context of emergency response systems, correctness is usually much more important than resolution: to locate a trapped victim, it is usually sufficient to know her general location (e.g. floor and room); on the other hand, sending rescuers to the wrong location in an emergency situation can be deadly.
Motivated by these applications, localization schemes have been proposed that are based on identifying codes (Ray, Starobinski, Trachtenberg, & Ungrangsi, 2004), a concept borrowed from information-theory with links to coverings and superimposed codes. In this approach, only a small subset of sensors is activated as beacons. The subset is chosen so that its sensors have an identification property, meaning that a unique (or identifying) collection of these beacons can be detect at any location of interest, with specific regard to physical proximity. As such, a user can identify its location by simply tallying which beacons it can detect.