Location Sensing Systems For Ubiquitous Computing 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.

In simple terms, Location Sensing means determining the exact location of a person or object. It can be accessible with mobile devices through the mobile network and utilizes the ability to make use of the geographical position of the mobile device.

GPS, the most widely used location sensing system, is used as a running example throughout the context.

Types of Location Sensing:

Control Plane Locating - In Control Plane Locating, for phones with GPS features, the location is obtained based on the radio signal delay of the closest cell-phone towers. In GPS enabled devices, the location is determined if one knows its distance from other, already known locations.

GSM Localization - It is the use of GSM mobile phones to determine the location of the user. The geographical position of the device is found out through various techniques like Time Difference Of Arrival (TDOA) or Enhanced Observed Time Difference (E-OTD).

Near LBS (NLBS) - In Near-LBS (Location Based Service), local-range technologies such as Bluetooth, WLAN, Infrared, Zigbee, RFID, Near Field Communication technologies etc., are used to match devices to nearby services. This method is suitable for use especially in closed premises, restricted/regional areas as it allows user to access information based on their surroundings.

Indoor Local Positioning - Technologies such as Zigbee, Bluetooth, UWB (Ultra Wide Band), RFID (Radio Frequency Identification) and Wi-Fi are used for Indoor Location Sensing.

Existing Location Systems

Some of the existing location systems that we are going to deal with in this review are GPS, Active Badges, Active Bats, Cricket and MotionStar.

Location Sensing Techniques:

Determining the location of an object generally involves individual or combinations of the following three major techniques.


Triangulation is the process of determining the location of a point by measuring angles to it from known points at either end of a fixed baseline, rather than measuring distances to the point directly (trilateration). The point can then be fixed as the third point of a triangle with one known side and two known angles.


Lateration computes the position of an object by measuring its distance from multiple reference positions. In two dimensions, calculating an object's position require distance measurements from 3 non-collinear points. In 3 dimensions, it requires distance measurements from 4 non-coplanar points are required.

There are 3 general approaches to measuring the distances required by the lateration technique.

Direct - It requires physical action or movement. Measuring the distance using this method is difficult due to the complexities involved in coordinating autonomous physical movement.

Time-of-Flight - Measuring distance from an object to some point P using time-of-flight means measuring the time it takes to travel between the object and point P at a known velocity. The object itself may be moving, such as an airplane travelling at a known velocity for a given time interval, or, as is far more typical, the object is approximately stationary and we are instead observing the difference in transmission and arrival time of an emitted signal.[1]

Attenuation - As the distance from the emission source increases, the intensity of an emitted signal decreases. The decrease relative to the original intensity is called attenuation.


Angulation is similar to lateration except, instead of distances, angles are used for determining the position of an object.

Two dimensional Angulation - Requires one length measurement (say, distance between two reference points) and two angles.

Three dimensional Angulation - One length measurement, one azimuth measurement, and two angle measurements are needed in three dimensional angulation so as to specify a precise position.


A proximity location sensing technique entails determining when an object is "near" a known location. The presence of the object is sensed using a physical phenomenon with limited range. There are 3 general approaches to sensing proximity:

Detecting physical contact - Detecting physical contact with an object is the most basic type of proximity sensing. Capacitive field detectors, Touch sensors, and Pressure sensors can be used for this purpose.

Monitoring wireless cellular access points - Monitoring when a mobile device is in range of one or more access points in a wireless cellular network.

Observing automatic ID systems - It uses automatic identification systems such as credit card point-of-sale terminals, computer login histories, land-line telephone records, electronic card lock logs, and identification tags such as electronic highway E-Toll systems, UPC product codes, and injectable livestock identification capsules. If the device scanning the label, interrogating the tag, or monitoring the transaction has a known location, the location of the mobile object can be inferred.[1]

Scene Analysis:

The scene analysis location sensing technique uses features of a scene observed from a particular vantage point to draw conclusions about the location of the observer or of objects in the scene.

Static Scene Analysis - The features observed are looked up in a predefined dataset that maps them to object locations.

Differential Scene Analysis - The difference between successive scenes are tracked to estimate location. Differences in the scenes will correspond to movements of the observer and if features in the scenes are known to be at specific positions, the observer can compute its own position relative to them.

Properties of Location Systems:

When discussing and classifying location sensing systems, a broad set of issues arise. However they are independent of the techniques and technologies a system uses. Although certainly not all orthogonal, nor equally applicable to every system, the classification axes introduced do form a reasonable taxonomy for characterizing or evaluating location systems.

Taxonomy/Classification of Location Systems:

To address the problem of location sensing, the following classifiers have been introduced:

Physical position and symbolic location:

Generally speaking, a location system can provide two kinds of information: physical and symbolic. GPS provides physical positions. For example, our building is situated at 55°56′55″ N by 122°18′23″ W, at a 20.5-meter elevation. In contrast, symbolic location encompasses abstract ideas of where something is: in the kitchen, next to a mailbox, in Edinburgh zoo, on a train approaching Waverley.

The physical position provided by a system can be augmented to provide the corresponding symbolic location. For example, a laptop equipped with a GPS receiver can access a separate database that contains the positions and geometric service regions of other objects to provide applications with symbolic information[2]

Absolute versus relative location:

An absolute location system uses a shared reference grid for all located objects. All GPS receivers use latitude, longitude, and altitude or their equivalents, such as Universal Transverse Mercator coordinates for reporting location. Two GPS receivers placed at the same position will report equivalent position readings, and 47°39′17″ N by 122°18′23″ W refers to the same place regardless of GPS receiver.

In a relative system, each object has its own frame of reference. For example, a mountain rescue team that is searching for avalanche victims might use a handheld computer to locate victims' avalanche transceivers. Each rescuer's device reports the victims' position relative to itself. From the relative location of the person, an absolute location can be obtained with respect to a second reference point.

Localized location computation:

In localized location computation, privacy can be ensured in a way that no other object or entity can know the location unless the object specifically takes action to publish that information. For example, orbiting GPS satellites have no knowledge about who uses the signals they transmit. Online map servers such as Expedia (http://maps.expedia.com) and old-fashioned road atlases and print maps also fall into this category.

In contrast to the above, some systems require the located object to periodically broadcast, respond with, or otherwise emit telemetry data to allow the external infrastructure to locate it. This infrastructure can find objects in its purview without directly involving the objects in the computation. Placing the burden on the infrastructure will decrease the power and computational demands on the objects being located. This will make many more applications possible due to smaller form factors and lower costs.

Accuracy and precision

A location system should report locations accurately and consistently from measurement to measurement. Some inexpensive GPS receivers can locate positions to within 10 meters for approximately 95 percent of measurements. More expensive differential units usually do much better, reaching 1 to 3 meter accuracies 99 percent of the time. These distances denote the accuracy, or grain size, of the position information GPS can provide. The percentages denote precision, or how often we can expect to get that accuracy.

The ad hoc sensor networking and smart dust community (http://www.darpa.mil/ito/research/sensit) often addresses the related issue of adaptive fidelity. A location system with this ability can adjust its precision in response to dynamic situations such as partial failures or directives to conserve battery power.

Since both are important for us, the two attributes must be placed in a common framework for comparison. To arrive at a concise quantitative summary of accuracy and precision, we can assess the error distribution incurred when locating objects, along with any relevant dependencies such as the necessary density of infrastructural elements. For example, "Using five base stations per 300 square meters of indoor floor space, location-sensing system X can accurately locate objects within error margins defined by a Gaussian distribution centered at the objects' true locations and having a standard deviation of 2 meters."

Sensor fusion seeks to improve accuracy and precision by integrating many locations or positioning systems to form hierarchical and overlapping levels of resolution. Statistically merging error distributions is an effective way to assess the combined effect of multiple sensors.


To assess the scale of a location-sensing system, we consider its coverage area per unit of infrastructure and the number of objects the system can locate per unit of infrastructure per time interval. Time reflects an important consideration because of the limited bandwidth available in sensing objects. For example, a radio-frequency based technology can only tolerate a maximum number of communications before the channel becomes congested. Beyond this threshold, either latency in determining the objects' positions will increase or a loss in accuracy will occur because the system calculates the objects' positions less frequently.

Systems can often expand to a larger scale by increasing the infrastructure. For example, a tag system that locates objects in a single building can operate on a campus by outfitting all campus buildings and outdoor areas with the necessary sensor infrastructure. Hindrances to scalability in a location system include not only the infrastructure cost but also middleware complexity-it may prove difficult to manage the larger and more distributed databases required for a campus-sized deployment.


For applications that need to recognize or classify located objects to take a specific action based on their location, an automatic identification mechanism is needed. For example, a proximity-location system consisting of tag scanners installed at key locations along the automatic baggage conveyers makes recognition a simple matter of printing the appropriate destination codes on the adhesive luggage check stickers. In contrast, GPS satellites have no inherent mechanism for recognizing individual receivers.

Systems with recognition capability may recognize only some feature types. For example, cameras and vision systems can easily distinguish the colour or shape of an object but cannot automatically recognize individual people or a particular apple drawn from a bushel basket.

A general technique for providing recognition capability assigns names or globally unique IDs (GUID) to objects the system locates. Once a tag, badge, or label on the object reveals its GUID, the infrastructure can access an external database to look up the name, type, or other semantic information about the object. It can also combine the GUID with other contextual information so it can interpret the same object differently under varying circumstances. For example, a person can retrieve the descriptions of objects in a museum in a specified language. The infrastructure can also reverse the GUID model to emit IDs such as URLs that mobile objects can recognize and use.2


We can assess the cost of a location-sensing system in several ways. Time costs include factors such as the installation process's length and the system's administration needs. Space costs involve the amount of installed infrastructure and the hardware's size and form factor.

Capital costs include factors such as the price per mobile unit or infrastructure element and the salaries of support personnel. A system that uses infrared beacons for broadcasting room IDs requires a beacon for every room in which users want the system to find them. In this case, both the infrastructure and the object the system locates contribute to the incremental cost.


Some systems will not function in certain environments. In general, we assess functional limitations by considering the characteristics of the underlying technologies that implement the location system:

One difficulty with GPS is that receivers usually cannot detect the satellites' transmissions indoors. This limitation has implications for the kind of applications we can build using GPS.

For example, because most wired phones are located indoors, even if its accuracy and precision were high enough to make it conceivable, GPS does not provide adequate support for an application that routes phone calls to the land-line phone nearest the intended recipient.

A possible solution that maintains GPS interaction yet works indoors uses a system of GPS repeaters mounted at the edges of buildings to rebroadcast the signals inside. Some tagging systems can read tags properly only when a single tag is present. In some cases, collocated systems that use the same operating frequency experience interference.

Survey of Location Systems

We can use our taxonomy to survey some of the research and commercial location technologies that are representative of the location-sensing field. Table 1 summarizes the properties of these technologies. In the table, the open circles indicate that the systems can be classified as either absolute or relative, and the checkmarks indicate that localized location computation (LLC) or recognition applies to the system. Physical-symbolic and absolute-relative are paired alternatives, and a system is usually one or the other in each category.

Active Badges

The Active Badge location system consists of a cellular proximity system that uses diffuse infrared technology. Each person the system can locate wears a small infrared badge like that shown in Figure 1. The badge emits a globally unique identifier every 10 seconds or on demand. A central server collects this data from fixed infrared sensors around the building, aggregates it, and provides an application programming interface for using the data.

The Active Badge system provides absolute location information. A badge's location is symbolic, representing, for example, the room-or other infrared constraining volume-in which the badge is located.

As with any diffuse infrared system, Active Badges have difficulty in locations with fluorescent lighting or direct sunlight because of the spurious infrared emissions these light sources generate. Diffuse infrared has an effective range of several meters, which limits cell sizes to small- or medium-sized rooms. In larger rooms, the system can use multiple infrared beacons.

Active Bats

The Active Bat location system uses an ultrasound time-of-flight lateration technique to provide more accurate physical positioning than Active Badges.5 Users and objects carry Active Bat tags. In response to a request the controller sends via short-range radio, a Bat emits an ultrasonic pulse to a grid of ceiling-mounted receivers. At the same time the controller sends the radio frequency request packet, it also sends a synchronized reset signal to the ceiling sensors using a wired serial network. Each ceiling sensor measures the time interval from reset to ultrasonic pulse arrival and computes its distance from the Bat. The local controller then forwards the distance measurements to a central controller, which performs the lateration computation. Statistical pruning eliminates erroneous sensor measurements caused by a ceiling sensor hearing a reflected ultrasound pulse instead of one that travelled along the direct path from the Bat to the sensor.

The system, as reported in 1999, can locate Bats to within 9 cm of their true position for 95 percent of the measurements, and work to improve the accuracy even further is in progress. It can also compute orientation information given predefined knowledge about the placement of Bats on the rigid form of an object and allowing for the ease with which ultrasound is obstructed. Each Bat has a GUID for addressing and recognition.

Using ultrasound time of flight this way requires a large fixed-sensor infrastructure throughout the ceiling and is rather sensitive to the precise placement of these sensors. Thus, scalability, ease of deployment, and cost are disadvantages of this approach.


Complementing the Active Bat system,6 the Cricket Location Support System uses ultrasound emitters to create the infrastructure and embeds receivers in the object being located. This approach forces the objects to perform all their own triangulation computations. Cricket uses the radio frequency signal not only for synchronization of the time measurement, but also to delineate the time region during which the receiver should consider the sounds it receives. The system can identify any ultrasound it hears after the end of the radio frequency packet as a reflection and ignore it. A randomized algorithm allows multiple uncoordinated beacons to coexist in the same space. Each beacon also transmits a string of data that describes the semantics of the areas it delineates using the short-range radio.

Cricket implements both the lateration and proximity techniques. Receiving multiple beacons lets receivers triangulate their position. Receiving only one beacon still provides useful proximity information when combined with the semantic string the beacon transmits on the radio.

Cricket's advantages include privacy and decentralized scalability, while its disadvantages include a lack of centralized management or monitoring and the computational burden-and consequently power burden-that timing and processing both the ultrasound pulses and RF data place on the mobile receivers.


Electromagnetic sensing offers a classic position tracking method.8 The large body of research and products that support virtual reality and motion capture for computer animation often offer modern incarnations of this technology. For example, Ascension offers a variety of motion-capture solutions, including Flock of Birds and, shown in Figure 2, the MotionStar DC magnetic tracker.9 These tracking systems generate axial DC magnetic-field pulses from a transmitting antenna in a fixed location. The system computes the position and orientation of the receiving antennas by measuring the response in three orthogonal axes to the transmitted field pulse, combined with the constant effect of the earth's magnetic field.

Tracking systems such as MotionStar sense precise physical positions relative to the magnetic transmitting antenna. These systems offer the advantage of very high precision and accuracy, on the order of less than 1 mm spatial resolution, 1 ms time resolution, and 0.1° orientation capability. Disadvantages include steep implementation costs and the need to tether the tracked object to a control unit. Further, the sensors must remain within 1 to 3 meters of the transmitter, and accuracy degrades with the presence of metallic objects in the environment.

Ad-hoc location sensing

The techniques for building ad hoc systems include triangulation, scene analysis, or proximity. This approach to locating objects without drawing on the infrastructure or central control borrows ideas from the ad hoc networking research community. In a purely ad hoc location-sensing system, all of the entities become mobile objects with the same sensors and capabilities.

To estimate their locations, objects cooperate with other nearby objects by sharing sensor data to factor out overall measurement error. In this way, a cluster of ad hoc objects converges to an accurate estimate of all nearby objects' positions. Objects in the cluster are located relative to one another or absolutely if some objects in the cluster occupy known locations.

Accuracy in a Location Sensing System - A Challenge

Comparing the accuracy and precision of different location sensing systems can be an arduous task because many system descriptions lack a concise summary of these parameters. We therefore suggest that future quantitative evaluations of location-sensing systems include the error distribution, summarizing the system's accuracy and precision and any relevant dependencies such as the density of infrastructural elements. For example, "Using five base stations per 300 square meters of indoor floor space, location-sensing system Xcan accurately locate objects within error margins defined by a Gaussian distribution centered at the objects' true location and a standard deviation of 2 meters." We strongly encourage the location-sensing research and development community to investigate how to best obtain and represent such error distributions.

In addition to its comparison value, researchers could use a location-sensing system's accurately described error distribution as partial input for simulating a system-even a hypothetical one. Prototyping an application with a simulator avoids the cost of purchasing, deploying, and configuring a hardware infrastructure when the goal is simply to evaluate the suitability of a certain location-sensing system. Preliminary work on this idea has begun.

Scope for research

Although location sensing is a mature enough field to define a space within a taxonomy and that the future work should generally focus on lowering cost, reducing the amount of infrastructure, improving scalability, and creating systems that are more flexible within the taxonomy, location sensing is now entering an exciting phase in which cross-pollination with ideas from other computer science and engineering disciplines motivates future research.


Comparing the accuracy and precision of different location sensing systems can be an arduous task because many system descriptions lack a concise summary of these parameters. Therefore it is suggested that future quantitative evaluations of location-sensing systems include the error distribution, summarizing the system's accuracy and precision and any relevant dependencies such as the density of infrastructural elements.