The emergence of network-enabled devices and the potential utility of ubiquitous network connectivity has made the development of pervasive computing environments an attractive research goal. A compelling set of applications enabled by these technology trends are "location-dependent," i.e., applications that adapt their behavior and user interface to the current location of the user. We have already started seeing the commercial deployment of such applications in outdoor settings (e.g., Hertz's NeverLost navigator on rental cars), where location information is obtained via wide-area technologies like the Global Positioning System (GPS) or using the cellular infrastructure. While such applications are useful, the widespread deployment of location-dependent applications *inside* office buildings and homes has the potential to fundamentally change the way we interact with our immediate environment, where computing elements will be "ubiquitous" [Weiser91] or "pervasive" [Dertouzos99].

As part of the NTT-funded WIND (Wireless Networks of Devices) project (http://wind.lcs.mit.edu/projects/wind/) and the Oxygen effort (http://oxygen.lcs.mit.edu/), we have been developing middleware and protocols for networks of devices and mobile computers. We developed and demonstrated an intentional naming system (INS) for resource discovery in mobile environments and a congestion manager (CM) for adaptive audio and video delivery.

We propose to continue this work by investigating mechanisms by which applications and users can automatically obtain location information and learn about and navigate services based on geographic attributes such as physical location. The deliverable from this project will be hardware and software for an accurate "indoor GPS" and its integration with the rest of the WIND system developed under previous NTT funding. The applications of Cricket will include an active map navigation tool that will change as the user moves, and which will allow the user to discover and access diverse services (advertised using intentional names) in any area.

Obtaining location information for applications in an indoor environment in an unobtrusive and private manner is a challenging task. Indoor environments are harsher than outdoor ones in their treatment of radio signals because of multipath effects and dead spots inside buildings. User-privacy concerns are an important consideration in the successful deployment of these applications. Furthermore, the administration of the hardware and software infrastructure used for this must be minimal because of the large number (potentially over several thousand in a typical building) of devices and networked services that need this information.

We plan to develop a system that allows applications running on user devices and service nodes to learn their physical location. Once this information is obtained, services will advertise themselves to a resource discovery service, in our case INS [INS00], which will then resolve requests for any service. Users do not advertise themselves unless they want to be discovered by others; they learn about services in their vicinity via an active map that is sent from a map server, and interact with services by constructing queries for services at a required location.

Cricket uses "beacons" to disseminate information about a geographic space to "listeners." A beacon is a small device attached to some location in the geographic space it advertises. Typically, it is installed by the "owner" of the location (e.g., the occupant of a room in an office or home, or a building administrator) at an unobtrusive location like a ceiling or wall. Cricket does not attach any semantics to the space advertised by the beacon; any short string can be disseminated, such as the name of a server to contact to learn more about the space, a name resolver for the space, or a service location protocol directory agent. The boundary between spaces can be real (e.g., a wall between rooms) or virtual (e.g., the front of a room, or a small part of an auditorium).

To obtain information about a space, every mobile and static node has a "listener" attached to it. A listener is a small device that listens to messages from beacons, and uses these messages to infer the location (space) of the node. The listener also provides an API to programs running on the node that allows applications to learn where they are, so that they can use this information to appropriately advertise themselves (in particular, a location attribute) to a resource discovery service. No manual configuration of a listener is required.

Cricket has the following design goals that follow from the nature of our applications and from deployment considerations:

1. User privacy. Maintaining user privacy is perhaps the most important issue if Cricket's user base is to extend beyond the research community.

2. Decentralized administration. Our goal is early deployment beyond our research group to users throughout the AI Lab and the Laboratory for Computer Science. We believe that the scalable way to achieve deployment and administration is to eliminate all centralized control and management. This leads to a simple usage model where an "owner" of spaces in a building (e.g.,the occupant of a room) picks up one or more location beacons, turns them on and uses a simple utility program to set the string corresponding to the location he wants advertised. All that needs to be done after this is to attach the beacon(s) to some convenient spot in the room.

3. Form-factor. To achieve building-wide deployment on mobile devices, we need Cricket listeners to be both small and inexpensive. Our goal is hardware on the order of 2 square inches with a serial port interface to attach to devices.

4. Granularity. Resolution accuracy of location information is a useful figure-of-merit in characterizing any location tracking or support system. For our applications, granularity on the order of a portion of a room is needed. Our goal is a system that can be accurate to within a small number of feet inside a building where ambient electromagnetic radiation can cause radio frequency (RF) signals to behave in unpredictable ways.

Our preliminary experiments have shown that a purely RF-based system is hard to engineer and its algorithms are both complicated and do not provide accurate location information. We therefore plan to use both RF and ultrasonic signals transmitted from the beacons.

Each listener has both RF and ultrasonic receivers. The idea is to transmit, at the same time, data associated with the location on the RF and an ultrasonic pulse from a beacon. In the absence of any interference of multipath effects, a listener can observe the difference in time between the reception of the first RF bit and the arrival of the ultrasonic pulse. Because sound travels at 1 foot/ms and the speed of light (RF) is virtually infinite relative to that of sound, this time difference is a good estimate of the distance from the beacon to the listener.

To infer its location, the listener need not sense the direction from which beacon signals are coming. If only one beacon can be heard, there is no ambiguity about which space the listener is in. If multiple beacons can be heard, the listener is assumed to be in the space of the closest beacon. If there is no closest beacon (i.e., more than one beacon is found to be at a similar distance), an arbitrary choice is made.

There are a number of fundamental problems that need to be solved before a system based on this basic idea can actually work.

These include:

1. Interference from multiple beacons. We propose to handle this using a decentralized, randomized algorithm where each beacon adaptively learns how many others there are in the vicinity, and uses a random time interval based on this to transmit its own information.

2. Inference algorithms. The main function of the listener is to infer its best location by gathering and analyzing information from the various beacons it hears. It therefore needs to correlate signals and handle interference and multipath. Ultrasonic signals present a special challenge, since they suffer from severe multipath effects with reflections reaching a receiver tens of milliseconds after the original reception (which may have been lost). This can confound a listener trying to correlate RF and ultrasonic signals. We propose to tackle this problem using a statistical decoding algorithm that constructs a maximum-likelihood estimator at the listener.

3. Hardware design. Our intention is to design the beacon and listener hardware from commercial off-the-shelf components, which include the microcontroller, radio, ultrasonic tone-detector, and power supply.

4. Energy-efficiency. An important deployment consideration is energy; a system that requires replacing beacon or listener batteries every few hours or every day is inadequate; we would like the batteries to last at least several days in our prototype.

Every day, several people visit LCS and AI, often for several hours. An important application enabled by Cricket will make life easier for a new visitor.

Consider the following scenario:

When visitors walks in, they pick up a handheld computer from headquarters; the handheld is their predominant computing device for the duration of their stay here. As they move in the building from room to room, an active map, which automatically changes as they move reflecting their current location, guides them to where they needs to be next. Unobtrusively attached to the handheld is the Cricket listener hardware, and the building is awash with beacons advertising information understood by the active map application. On the map also appear various devices and services of interest, for example

• Televisions which the visitor can tune in to catch the latest news or weather,

• Public printers where visitors can print out material without the burden of contacting an administrator and messing with arcane configuration information. Furthermore, the job will automatically be sent to the nearest, least-loaded printer and the visitor will be told how to get to it, and

• Locations of interesting talks and things happening in the building.

The handheld has no pre-configured software other than the WIND middleware; the map is obtained by querying the intentional naming system for a map server, which disseminates the appropriate map to the handheld client based on the intentional name of the map request. The ability to control and navigate new services (e.g., a new television) is achieved by transmitting mobile code from the service to the handheld using INS. If visitors so desire, their own personal laptop or handheld computer can be easily made part of the WIND/Oxygen network by simply turning it on and downloading the WIND/Oxygen software.

In our current design, the map server stores its maps as GIF images. We believe that a more systematic way of storing these based on Professor Teller's project would be useful, since it will allow more interesting queries of maps. We intend to explore this in collaboration with his group as our research matures.

[Dertouzos99] M. Dertouzos, "The Future of Computing," Scientific American, August 1999. Available from http://www.sciam.com/1999/0899issue/0899dertouzos.html

[INS00] MIT LCS Networks and Mobile Systems Group, "The Intentional Naming System," http://nms.lcs.mit.edu/projects/ins/

[Weiser91] M. Weiser, "The computer for the 21st century," Scientific American, September 1991.