Cricket: A Location-Support System

for Pervasive Mobile Computing

9807-04

Progress Report: January 1, 2002—June 30, 2002

Hari Balakrishnan and John Guttag

Project Overview

Cricket is an indoor location system that uses a combination of RF and ultrasound hardware. Cricket has a unique decentralized architecture using autonomous beacons transmitting location and spatial information to passive listeners (attached to static and mobile devices). The Cricket architecture provides a degree of scalability and autonomy (ease of deployment) well beyond other location systems, and facilitates the preservation of user privacy to a degree not seen in other systems. We believe that these features augur well for its widespread deployment, provided many technical challenges can be solved. Solving these problems and building a true production system are the goals of this project; we are fundamentally interested in real users and real developers using Cricket, rather than in implementing “only” a proof-of-concept prototype. We started working on Cricket (in its current form) in mid-1999 (very early stage designs) and came up with a high-level solution (untested) around September 1999 under the NTT-funded WIND project. Since then, we have been working on both the core Cricket system (design, implementation, evaluation, deployment) and on support for location-aware applications (INS for resource discovery, stream migration, connection migration). The overarching long-term goal of the research is to design context-aware systems and applications and understand how such systems should be engineered.

Progress Through June 2002

1. Auto-configuration algorithms. As we deploy Cricket in the LCS/AI building and as other groups deploy it, a significant problem is beacon configuration. We have been working on a decentralized and scalable algorithm by which coordinates can be automatically obtained by the beacons, without manual intervention. We have developed a simple “ball-and-springs” model for this, inspired by physics. The high-level idea is for each beacon to use its current estimates of its coordinates, together with single-hop distance estimates to nearest neighbors (obtained using RF and ultrasound combination) to calculate its new coordinates by modeling the difference between the estimated distance and sampled distance using a spring model of restoring force.

We found that this alone, while promising, does not work, since the system ends up in local minima. We also proved conditions under which this model does work. So, now, we are exploring methods to have the system first converge to a situation where the ball-and-springs idea can provably work, and then run the springs model on it.

2. Cricket software compass. We have made progress on designing a production-quality compass, which can enable a variety of new applications. We have also worked with Prof. Teller’s group to produce an initial prototype software flashlight application.

3. INS/Twine (Scalable intentional resource discovery). A paper on INS/Twine for scalable resource discovery using Internet-scale distributed hash tables was accepted to the new international conference on pervasive computing (Pervasive 2002).

Research Plan for the Next Six Months

1. Auto-configuration in Cricket. We plan to continue work on this problem to produce a practical working algorithm with theoretically provable performance and correctness properties.

2. Continue development of Compass and compass applications.

3. Monitoring and control applications. So far, our application efforts have been targeted towards human-centric “finding” applications. A large class of location-aware applications are in monitoring and control, e.g., large-scale asset tracking, theft prevention, sensor/actuator monitoring, etc. We plan to understand this domain better and investigate challenges therein. As a starting point, we have started working with the people in the LCS/AI reading room to design and automatic tracking system for all the books, journals, periodicals, etc. in the room.