SensorNet Architectures for Indoor Location Detection

Undergraduate Student: Christopher S. Caplinger

Advisors: Ari Trachtenberg, David Starobinski

Need

Reliable communication systems are becoming increasingly important for a variety of practical applications. In particular, coordination between equipment and personnel is vital in disaster areas or harsh environments. While well-known tri-lateration techniques, such as GPS, can be effectively utilized in clear, outdoor areas, many real-life environments are unfit for signal propagation (and therefore existing forms of location detection).

Therefore, a reliable and robust system of indoor location detection (in harsh environments) is important/useful for many practical applications,

such as:

• dense indoor or urban settings
• underwater
• underground
• emergency environments, such as:
  • building collapse
  • extreme weather
  • determining location of trapped firefighters or portable equipment

Alternative technologies

Outdoor

Tri-Lateration (GPS):

Functionality:

• Uses a system of tri-lateration of position and time among 4 satellites to provide location information.
• Able to effectively locate a position within a few meters.

Disadvantages:

• Tri-lateration techniques are difficult to adapt without significant (and potentially catastrophic error), due to signal propagation properties that are difficult to predict.
• Signal strength/time-of-flight measurements do not accurately convey distance information, due to the difficulty in characterizing and modeling:
  • Occlusions
  • Reflections
  • Noise
• Also sensitive to sensor displacement and structural changes.
• Multi-path effects limit the usefulness of tri-lateration systems in harsh environments.

Indoor

Infrared (IR) “Active Badge”

Functionality:

• Each person has a badge which periodically emits a unique ID. These ID signals are fdlskjfs by several receivers. The location of the person or object is then determined by proximity to nearest receiver.

Disadvantages:

• Dynamic communication environments, such as:
  • people moving
  • smoke, other impurities in the air
  • wall collapse

render proximity-based systems ineffective. As a result, this system is not robust or flexible enough to provide accurate location detection within harsh, dynamic environments.

Ultrasound (US)

Functionality:

• Proximity-based, but accuracy is improved by measuring the time of flight with respect to a reference RF signal.
• Time-of-arrival signal is compared to a reference RF signal from known sensors in order to calculate location.

Real-world examples:

• 'Active Bat'
• 'Cricket” (MIT)'

Disadvantages:

• Not designed for robustness
  • If line of sight is obstructed or altered by changing room dynamics, the system fails.
• This system is particularly susceptible to sensor destruction.

Radio (RF) "Fingerprinting"

Functionality:

• Based on received signal strength.
• A specific location region is identified by a unique set of features (i.e. a fingerprint) of the sensed signal.
• First, the system pre-computes a Signal-to-Noise Ratio for the building. A vector of signal strengths received at various base stations is then compared to this SNR map in order to determine position.

• Powerful: RF able to penetrate many surfaces/objects
• Long range
• Scalability
• Maintenance benefits

Real-world examples:

• “SpotON”
• “Nibble”

Disadvantages:

• Potential for sensor failure in harsh environments.
• Introduction of new paths from spurious reflectors (i.e. people moving/shifting structures) can lead to system failure.
• Sensitive to environmental conditions.
• Requires careful and complex planning.

ID-Codes

In general, existing location detection systems lack the robustness needed to protect against equipment failure and changing topology. Proximity-based systems are particularly prone to failure in harsh or dynamic environments, due to the fact that generally, if one sensor is removed or destroyed, the entire system will fail.

Project Goals and Requirements

• To determine the practical and theoretical considerations in the proper design and setup of a location detection system within a dynamic/harsh environment.
• The system must be reliable and robust.
• The system must protect the localization network against unanticipated changes in topology and signal propagation path.

System Overview

The Identifying Codes-based system can be viewed as a particular case of fingerprinting.

In this system, the first step is to divide the coverage area into a finite set of regions, with each region being represented by a single point. These points are then named and mapped to nodes in a graph (figure a). When these physical points are able to directly communicate with one another, the nodes are shown to be connected by lines drawn on the graph (figure b).

figure a

figure b

The problem is then to determine the nodes on which to place and activate the sensors, such that each node is within the communication range of a different set of sensors. For this problem, a greedy algorithm, titled ID-CODE, is utilized. This algorithm produces irreducible ID codes from which no codeword can be removed without violating the unique identification of a position. This algorithm will be further analyzed in the 'ID-CODE Algorithm' section of this page.

figure c shows the sensor placement in the physical coverage area, determined by ID-CODE. Black dots show sensor locations, while X's nodes without sensors.

figure d shows the sensor placement in graphical form, with connections shown as lines between nodes.

figure c

figure d

As can be seen in figures c and d, only a small subset of sensors are 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 detected at any location of interest, with specific regard to physical proximity. In this way, a user can identify its location by simply tallying which beacons it can detect.

As can be seen, significantly fewer sensors are required to cover a localization area. Therefore, redundant sensors can be added to the system to counteract spurious connections or sensor failures, thus increasing the overall robustness of the system.

ID-CODE Algorithm

The main challenge in designing ID-CODE-based system is to position sensors so that every resolvable location can be identified unambiguously. must find optimal ID code to guarantee that each point selected in a given area is covered by a unique set of transmitters.

Testing and Results

In order to verify the effectiveness of the ID-Code-based location detection scheme, an experimental testbed was developed. The testbed (located on the 4th floor of the Boston University Photonics Building) utilizes five laptop computers (four as transmitters, one as a receiver) equipped with IEEE 802.11 transceivers. Each transmitter sends 40 packets per second at a rate of 5.5 Mb/s and a transmission power of 100 mW. Shown in figure e, this experimental testbed features ten distinct nodes (identified by white circles) and four transmitters (identified by white circles with X's) with specific locations determined by the ID-CODE algorithm. This contour map also shows the resolution achieved by the location detection system. The map shows resolutions varying from 0 to 70 feet, with darker shades corresponding to a higher resolutions. Although the system consists of only four transmitters, it achieves a reasonable resolution, usually within 50 feet of the correct area.

figure f compares the results of the ID-Code-based system with a simple proximity-based location detection scheme. In this scheme, the user's location is defined by the transmitter from which it correctly receives the largest number of packets. figure f shows the CDF of the system resolution for both location detection schemes. As can be seen, a larger number of positions are within the given error distance for the ID-Code-based system. This resolution gain is a direct result of the use of identifying code techniques.

figure e

figure f

-- ChrisCaplinger - 25 Nov 2008