Cricket: A Location Support System

for Pervasive Mobile Computing

9807-04

Progress Report: July 1, 2002 ≠ December 31, 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 December 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.

In the previous report, we had stated: ≥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.≤

We have made further progress on this hard problem and our current simulations show our algorithm working well. We still need to develop the theory proving the algorithmπs properties, which is our current work.

2. Cricket v2 design. Our main system-level progress has been a new design for the Cricket system hardware. This will be fabbed in the next few months. We have also been integrating Cricket with specialized sensors for sensing things like lighting, temperature, sound, etc. for in-building deployment.

3. TinyOS software substrate. We have been porting Berkeleyπs TinyOS to the Cricket platform to offer a general-purpose programmable platform for location-aware sensor computing.

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. 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.

3. Complete the TinyOS software integration.