It's also possible that a mobile phone (if it's on the top floors of a tall building) can be connected to a transmitter in a neighboring cell, causing the accuracy to go down to kilometers. Calls from mobile phones in multi-story buildings provide information that will, at best, identify a few buildings or the block that the call originated, but rescue teams need more-detailed information to find emergency victims.

Solutions to increase the accuracy of mobile networks already exist in which mobile clients are located with the help of supplementary information (e.g., postal-code information, streets, town names, etc.). Accuracy is further improved by using the time taken by the signal to reach the mobile device. But due to lack of directional information, users can be located anywhere in a circular band (or a section of a circular band) around a base station, so uncertainty remains.

A Wireless World

It's important to solve indoor positioning problems, because by 2005 there will be 184 million U.S. wireless subscribers (Jupiter Research, 2001). Moreover, according to the National Emergency Number Association, more than 30 percent of 911 calls in the United States originate from mobile phones--a number expected to soon outpace 911 wire-line calls.

A multitude of applications and services would benefit from indoor positioning and navigation. Location-positioning technologies such as the Global Positioning System (GPS) and initiatives such as the U.S. Federal Communications Commission's E-911 mandate generated a lot of interest in location-based services (LBSs). However, despite GPS technology and the positioning capabilities of cellular networks, millions of square meters of indoor space (i.e., office buildings, shopping malls, airports, convention centers, etc.) are out of reach.

During the last decade, however, advances in location positioning technology made it possible to locate objects and people indoors at an accuracy of up to +/- three feet. Table 1 indicates companies actively doing location research, some of which are already deploying indoor LBS applications.

Promising Indoor LBS Applications

Indoor positioning technologies relate people, objects and events in space. Alert-based LBSs, also called spatial-trigger (proactive) services such as "Buddy Finder" or "Product Finder," are among the most fundamental in consumer needs and interests. They notify users if important events happen within their proximity, which can be when a friend enters a specified perimeter or when a product is on sale in a store that cell-phone users happen to be passing by (shown as the "Trigger Zone" in Figure 1).

Figure 1. Alert-based LBSs notify users if important events happen within their proximity, which can be when a friend enters a specified perimeter or when a product is on sale in a store that a cell-phone user happens to be passing.

The core functionality of such applications is similar across most LBS applications: find an object, person, place or event. Common applications fall into the categories presented in Table 2.

Real-world examples of indoor LBS applications include MIT Cricket's WayFinder, which uses positioning information obtained from Cricket's sensors and a map server to present a location-dependent "active map" to users, highlighting locations as they move. The application, running on a handheld computer, can help sighted or blind people navigate toward a destination in an unfamiliar setting. For example, WayFinder could lead a person from a building's entry lobby to a seminar room.

More-precise positioning technologies could enable navigation to specific items within a store's aisle. Users should be able to identify features of their surroundings by pointing at them, so special sensors have to be integrated into mobile devices that determine direction. Using MIT Cricket's ViewFinder, users can point in any direction and specify a "sweep angle" and maximum distance.

Also, mobile "phonemarks," similar to Web bookmarks, could be used to store content of interest for later use. Detailed georeferencing and phonemarks open the possibility of querying objects such as products in a shopping window or paintings in a museum. YDreams' FluidShopping product was designed to reduce the anxieties of shoppers through Internet-enabled mobile phones, helping shoppers find the products they want to buy.

Roles and Types of Infrastructure

Building a positioning system that works well indoors is a challenge, because signals reflected off walls, floors and ceilings tend to confuse sensors, and often there are obstructions between sensors and objects being tracked. GPS and cellular-network-based positioning aren't appropriate for indoor use due to loss of line-of-sight as well as signal blockage, fading and shadowing.

Nevertheless, the indoor world can provide a more controlled environment, and several positioning methods can be used alone or combined:

* Triangulation

• Lateration: Time of flight, attenuation
• Angulation: Arrival angle of a signal against a baseline can be measured using signal strength or time difference of arrival (e.g., UbiScene's UbiTags)

* Scene analysis

• Use of a feature as a reference point (e.g., Microsoft RADAR)

* Proximity

• Physical contact through pressure sensors (e.g., SmartFloor)
• Monitoring (e.g., Active Badge)
• Observing (e.g., automatic ID systems)

Specific location-positioning systems include Active Badge, Microsoft RADAR, MIT Cricket and HP Labs' SmartLOCUS, which enable more accuracy-centric LBS applications.

The simplest case is to leverage existing communication infrastructure, such as Wi-Fi networks that provide general-purpose wireless networking, without setting up additional location-tracking components. That's why Microsoft's Wi-Fi-based network, "Choice," deployed two location services: a location-based Buddy List service and an OnSale Alert service that looks at user profiles and alerts them of relevant sales within the vicinity (shown as the "Trigger Zone" in Figure 1).

"The MS Choice Network advertises itself through Wi-Fi beacons," says Victor Bahl, a research scientist at Microsoft. "The client device picks up the beacons and associates with the closest Wi-Fi access point. It then sends out a request for an Internet address. Choice returns a short-term Internet address, and the client's browser is directed to a Web site with links to MS Passport."

The Active Badge system was one of the earliest indoor systems for position information. Badges are worn by people or attached to mobile computers. Location is derived by adding information from an infrared (IR) network that tracks objects with an IR badge, periodically transmitting a unique ID using IR transmitters. Fixed IR receivers pick up the information and relay it via a wired network to location-manager software.

Microsoft's RADAR uses 802.11 WaveLAN wireless networking technology, which allows wireless large-area network (LAN)-enabled mobile devices to compute locations based on signal strengths of known infrastructure access points (APs). The system calculates 2-D position coordinates via empirical methods based on comparison ("fingerprinting") with previous measured locations mapped on a radio map or using mathematical models of indoor radio-signal propagation.

MIT Cricket uses proximity lateration and time of flight. To enable its sensors to gather distance information (ratio of height to distance), Cricket implements a local coordinate system using four active beacons instrumented with known positions in space. The beacons are configured with coordinates (as shown in Figure 2) and broadcast information on a radio frequency (RF) channel sensed by compass receivers. In this sense, the MIT Cricket system behaves as a form of indoor GPS.

HP Labs SmartLOCUS uses synchronized RF and ultrasound differential time-of-flight measurements to determine the inter-nodal range between any two nodes. With a multitude of nodes in the system, a distributed localization algorithm operates on the ranges to create a self-organizing coordinate system.

HP Labs researchers developed several techniques to create relative coordinate geometries with little user intervention. To create an absolute frame of reference and tie inter-nodal topology to building geometry, a minimum of three or four nodes (for 2-D or 3-D localizations) must be pre-assigned to suitable fixed locations. All the remaining nodes are free to move, and locations are continuously updated and known to the rest of the system.

Absolute and Relative Positioning

Absolute positioning locates users to x,y positions. Using the Wi-Fi cell-ID positioning method, Wi-Fi APs transmitting RF signals augmented with physical coordinates can be used to estimate locations of mobile hosts by distance measurements.

The strength of the RF signals arriving from APs can be related to the position of a mobile terminal and used to infer location, but accuracy is limited by cell size. Handing off location to a room can be done with a tolerance level using methods such as location fingerprinting ("snapping").

Relative positioning pinpoints users "inside a room," for example, as opposed to locating them to an exact x,y position. Similar to absolute positioning, relative positioning works by referencing Wi-Fi access points (APs) that are, in this case, symbolic.

Wi-Fi APs transmitting RF signals augmented with relative position can be used to estimate mobile user locations. Position is derived based on the Wi-Fi AP that a user accessed, of which the location is known.

If "User 1" accesses "AP #201_1," for example, he or she is mapped/referenced to "Room 201." Moreover, each AP has an access range/perimeter that's represented so a user accessing AP1 is "within" the range of that AP, which may or may not be defined to a specific metric distance.

Current Limitations

One complication is that a device may not always "bind" to the nearest AP, but instead to one that's most "available," which isn't always related to incoming signal strength. However, such a tendency can be managed in Wi-Fi networks using techniques such as lowering transmit power to reduce cell size.

"Handing off" locations based on absolute position of one AP to another can be performed with a specified tolerance level (i.e., "snapping"). Additional precision in determining absolute position can be obtained by enhancing the target space with RF beacons and/or other specialized communication hardware. Within the indoor world, different zones of positioning types can co-exist.

Designing a location system for a single environment presents difficulties when the system is applied to other environments. Depending on the positioning system's purpose, different environments may need to handle different sensor data (dealing with relative vs. absolute positioning). A positioning system must successfully bridge the differences among different types of sensors.

Currently, most indoor LBS applications are based on self-contained systems (vertical implementation of all the necessary components such as location-positioning servers, middleware, applications, etc.) that provide a “one-size-fits-all” solution. But the optimum strategy must use an open architecture and platform capable of uniting and integrating different features and functions from various infrastructure (sensor) providers in a distributed way to create a variety of different value propositions for diverse customers.

Cyril Brigone, a researcher from HP Labs, explains what this means for indoor LBS application development. "Current applications using sensor networks are often implemented in a vertical way," Brigone notes. "There is no way for an application to share/access/control the sensing resources without knowing the sensor/network specificities."

Also, positioning sensors have limitations that result in position drift and uncertainty. Hybrid systems attempt to compensate for the shortcomings of a single technology by using multiple sensor types.

According to Jeffrey Hightower, a researcher at the University of Washington, "Sensor technologies have tradeoffs. Measurements have error. Sensor fusion allows the addition, replacement, handoff and multiplicity of technologies under a single location programming interface. Moreover, research shows that probabilistic algorithms like Bayes filters are an accurate, flexible and practical way to implement fusion and manage inherently uncertain location information."

Open Interoperability Standards

A hybrid positioning system will require open interoperability standards, which function as the "glue" among infrastructure types and their components. Without this glue, implementing such applications is complex and presents technological challenges tied to market challenges, impeding industry growth.

The coordinate system used in MIT Cricket uses
beacons that are configured with coordinates and
broadcast information on a radio-frequency channel
sensed by compass receivers.

The process of standardization has been important in creating and growing global markets for computing and communications systems. For example, communication network standards enable interoperability among equipment from different manufacturers, lower costs and reassure users that technology investments will be viable beyond the short term. However, because the market for indoor LBS is in its infancy and requirements for indoor LBS applications are just beginning to be understood, caution must be taken to avoid making early decisions that will impede market adoption.

Although current audiences and markets for outdoor LBSs are easily defined, applications for indoor services are less obvious. Collaboration among different infrastructure providers is of great importance.

The benefits of such collaboration can be seen from the Open Geospatial Consortium's OpenLS initiative, which brought together key industry players to build and consolidate a standards infrastructure for outdoor LBSs. The standards allowed different companies to focus on different aspects of the LBS value chain: middleware, applications, services, etc. I believe a similar situation will emerge for the indoor world of LBS and lead to a corresponding "micro- micro-LBS/micro-geography standards initiative.

In terms of the positioning infrastructure, this can be already seen with the Bluetooth Special Interest Group—the Local Positioning Work Group—which is defining a Local Positioning Profile (LPP) for Bluetooth. In LPP, a set of XML messages, the Local Positioning Messaging Protocol (LPMP), can be used to exchange location information among devices. The location can be latitude and longitude (absolute position), and a hierarchical (relative or “symbolic” position) message can be exchanged with information about the environment.