The Cricket Location-Support System Nissanka B. Priyantha, Anit Chakraborty, and Hari Balakrishnan MIT Laboratory for Computer Science Cambridge, MA 02139 {bodhi, achakra, hari} @lcs.mit.edu Abstract This paper presents the design, implementation, and evaluation of Cricket, a location-support system for in-building, mobile, location- dependent applications. It allows applications running on mobile and static nodes to learn their physical location by using listeners that hear and analyze information from beacons spread throughout the building. Cricket is the result of several design goals, including user privacy, decentralized administration, network heterogeneity, and low cost. Rather than explicitly tracking user location, Cricket helps devices learn where they are and lets them decide whom to advertise this information to; it does not rely on any centralized management or control and there is no explicit coordination be- tween beacons; it provides information to devices regardless of their type of network connectivity; and each Cricket device is made from off-the-shelf components and costs less than U.S. $10. We describe the randomized algorithm used by beacons to transmit information, the use of concurrent radio and ultrasonic signals to infer distance, the listener inference algorithms to overcome multipath and inter- ference, and practical beacon configuration and positioning tech- niques that improve accuracy. Our experience with Cricket shows that several location-dependent applications such as in-building ac- tive maps and device control can be developed with little effort or manual configuration. I Introduction The emergence of network-enabled devices and the promise of ubiquitous network connectivity has made the development of per- vasive computing environments an attractive research goal. A com- pelling set of applications enabled by these technology trends are context-aware, location-dependent ones, which adapt their behav- ior and user interface to the current location in space, for which they need to know their physical location with some degree of accuracy. We have started seeing the commercial deployment of such appli- cations in outdoor settings (e.g., Hertz's NeverLost navigator on This research was supported in part by NTT Corporation, DARPA (Grant No. MDA972-99-1-0014), and IBM. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the lull citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. MOBICOM 2000 Boston MA USA Copyright ACM 2000 1-58113-197-6/00/08...$5.00 rental cars [13]), where location information is obtained via wide- area technologies like the Global Positioning System (GPS) [10] or using the cellular infrastructure. We believe that the widespread deployment of location-dependent applications inside office build- ings and homes has the potential to fundamentally change the way we interact with our immediate environment, where computing ele- ments will be "ubiquitous" [20] or "pervasive" [8, 4]. In particular, our work will enable a new class of location-based applications and user interactions in the context of Project Oxygen at MIT [16]. The design and deployment of a system for obtaining location and spatial information in an indoor environment is a challenging task for several reasons, including the preservation of user privacy, ad- ministration and management overheads, system scalability, and the harsh nature of indoor wireless channels. The degree of privacy of- fered by the system is an important deployment consideration, since people often value their privacy highly. The administrative overhead to manage and maintain the hardware and software infrastructure must be minimal because of the potentially large number (possibly several thousands in a building) of devices and networked services that would be part of the system, and the communication protocols must be able to scale to a high spatial density of devices. Finally, in- door environments often contain substantial amounts of metal and other such reflective materials that affect the propagation of radio frequency (RF) signals in non-trivial ways, causing severe multi- path effects, dead-spots, noise, and interference. Our goal is 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 advertise themselves to a resource discovery service such as the MIT Intentional Naming System (INS) [2], IETF Service Location Protocol [18], Berkeley Service Discovery Service [7], or Sun's Jini discovery service [14]. User applications 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 application, and interact with services by constructing queries for services at a re- quired location. By separating the processes of tracking services and obtaining location information, multiple resource discovery systems can be handled. By not tracking users and services, user- privacy concerns are adequately met. We emphasize that our goal is a location-support system, rather than a conventional location- tracking system that tracks and stores location information for ser- vices and users in a centrally maintained database. Over the past many months, we have designed and implemented Cricket, a location-support system for building-wide deployment in the context of Project Oxygen, and have conducted several experi- ments with it. We have integrated it with INS for resource discov- ery, and an active map application, which together enable location- 32
`
`Sonitor Exhibit 1019
`IPR of U.S. Patent No. 9,622,030
`
`

`

`dependent applications (and users) to discover and interact with services. This paper describes our design goals (later in this sec- tion), system architecture and algorithms (Section 2), implementa- tion (Section 3), experimental results (Section 4), applications (Sec- tion 5), and a detailed comparison with previous location-tracking systems (Section 6). The design of Cricket was driven by the following specific goals, which followed from the nature of our applications and from de- ployment considerations: • User privacy. Whenever a system for providing location in- formation to clients has been deployed in the past, the issue of user privacy has arisen. This is because many previous sys- tems were location tracking systems, where a database kept track of the locations of all the entities, including users in the system. To address this concem, we designed a location sup- port system, which allows clients to learn their location with- out centralized tracking in order to construct location-specific queries for resources. • Decentralized administration. Our goal is widespread building-wide deployment. We believe that it is not possible to deploy and administer a system in a scalable way when all control and management functions are centralized. Our design is decentralized - the "owner" of a space in a building (e.g.,the occupant of a room) configures and installs a location bea- con that announces the identity of that space (some character string) and each beacon seamlessly integrates with the rest of the system. Location receiver hardware, called a listener, is attached to every device of interest to a user. Listeners use an inference algorithm to determine the space in which they are currently located by listening to beacon announcements. And there is no need to keep track of individual components within the system. • Network heterogeneity. A wide variety of network technolo- gies exist in most building environments. In our own labora- tory, devices and users connected over 10/100 Mbps Ethemet, three different types of indoor wireless LANs, cellular digital packet data (CDPD), infrared, public telephone, and power- line using X10 21. Independent of which technology they use to serve or gain access to information, many services and clients can benefit from learning their location in an automatic way, and we would like to accommodate them. In our design, we achieve this by decoupling the Cricket system from other data communication mechanisms. • Cost. Achieving building-wide deployment requires cost- effective components. We use commercial, off-the-shelf, inex- pensive components in Cricket, setting and meeting the goal of less than U.S. $10 per location beacon and listener. Our de- sign involves no custom hardware and is small enough to fit in one's palm. • Room-sized granularity. Our goal is a system where spatial regions can be determined to within a few square feet, so as to distinguish portions of rooms. This requires the ability to demarcate and determine boundaries between regions corre- sponding to different beacons. Cricket uses a combination of RF and ultrasound to provide a location-support service to users and applications. Wall- and ceiling-mounted beacons are spread through the building, publish- ing location information on an RF signal. With each RF advertise- ment, the beacon transmits a concurrent ultrasonic pulse. The listen- ers receive these RF and ultrasonic signals, correlate them to each other, and infer the space they are currently in. We describe the de- tails of the technologies, the system parameters and configuration, and the algorithms and protocols used in Cricket. The beacons use a decentralized randomized transmission algorithm to minimize col- lisions and interference amongst each other. The listeners imple- ment a decoding algorithm to overcome the effects of ultrasound multipath and RF interference. We investigate the performance of three decoding algorithms and find that picking the location corre- sponding to the beacon with minimum statistical mode performs the best, maximizing the likelihood of making the correct choice. We also discuss some practical deployment considerations when using ultrasound hardware, and some location-dependent applications we have developed using Cricket. 2 System architecture Cricket uses beacons to disseminate information about a geo- graphic space to listeners. A beacon is a small device attached to some location within the geographic space it advertises. Typically, it is obtained by the "owner" of the location (e.g., the occupant of a room in an office or home, or a building administrator) and placed at an unobtrusive location like a ceiling or wall. Cricket does not at- tach 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 or a name resolver for the space to discover resources. Cricket beacons are inexpensive and more than one of them can be used in any space for fault-tolerance and better coverage. 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 space it is currently in. The listener provides an API to programs running on the node that allow them to learn where they are, so that they can use this information to appropriately advertise themselves and their location to a resource discovery service. The listener can be attached to both static and mobile nodes. For example, when a user attaches a new static service to the network (e.g., a printer), she does not need to configure it with a location or other any attribute; all she does is attach a listener to it. Within a few seconds, the listener infers its current location from the set of beacons it hears, and informs the device software about this via the API. This information can then be used in its own service ad- vertisements. When a mobile computer has a listener attached to it, the listener constantly listens to beacons to infer its location. As the computer (e.g., a hand-held computer carried by a person) moves in a building, the navigation software running on it uses the listener API to update its current location. Then, by sending this informa- tion securely to a map server (for example), it can obtain updates to the map displayed to the user. Furthermore, services appear as icons on the map that are a function of the user's current location. The services themselves learn their location information using their own listener devices, avoiding the need for any per-node configura- tion. The only configuration required in Cricket is setting the string for 33
`
`

`

`a space that is disseminated by a beacon. The specific string is a function of the resource discovery protocol being used, and Cricket allows any one of several possibilities (in Section 5 we describe our implementation platform and integration with INS). Cricket also provides a way by which the owner of a room can securely set and change the space identifier that is sent in the advertisements. This is done by sending a special message over the same RF channel that is used for the advertisements, after authenticating the user via a password. At this stage, we have chosen to allow this change only from within physical proximity of the room or location where the beacon is located. This makes the system somewhat more secure than if we allowed this to be done from afar. The boundaries between adjacent spaces can either be real, as in a wall separating two rooms, or virtual, as in a non-physical partition used to separate portions of a room. The precision of the system is determined by how well the listener can detect the boundary be- tween two spaces, while the granularity of the system is the small- est possible size for a geographic space such that boundaries can be detected with a high degree of precision. A third metric, accuracy is used to calibrate individual beacons and listeners; it is the degree to which the distance from a beacon, estimated by a listener, matches the true distance. While our experiments show that the distance ac- curacy of our hardware is smaller than a few inches, what matters is the precision and granularity of the system. These depend on the algorithms and the placement of beacons across boundaries. Our goal is a system with a close-to-100% precision with a granularity of a few feet (a portion of a room). The rest of this section describes the design of Cricket, focusing on three fundamental issues: (i) mechanism for determining the loca- tion (the beacon-listener protocol), (ii) the listener algorithms and techniques for handling beacon interference, and (iii) beacon con- figuration and positioning. 2.1 Determining the location At the beginning we were hopeful that a purely RF-based sys- tem could be engineered and made to work well, providing lo- cation information at the granularity of a room, and ideally, por- tions of rooms. Our approach attempted to limit the coverage of an RF transmitter to define the granularity of a geographic-space, and using received signal strength to infer best location. Despite many weeks of experimentation and significant tuning, this did not yield satisfactory results 6. This was mainly because RF propaga- tion within buildings deviates heavily from empirical mathematical models (e.g., see also 5), and in our environment, the correspond- ing signal behavior with our inexpensive, off-the-shelf radios was not reproducible across time. We therefore decided to use a combination of RF and ultrasound hardware to enable a listener to determine the distance to bea- cons, from which the closest beacon can be more unambiguously inferred. We achieve this by measuring the one-way propagation time of the ultrasonic signals emitted by a beacon, taking advan- tage of the fact that the speed of sound in air (about 1.13 ft/ms at room temperature) is much smaller than the speed of light (RF) in air. On each transmission, a beacon concurrently sends information about the space over RF, together with an ultrasonic pulse. When the listener hears the RF signal, it uses the first few bits as training information and then turns on its ultrasonic receiver. It then listens 34 for the ultrasonic pulse, which will usually arrive a short time later. The listener uses the time difference between the receipt of the first bit of RF information and the ultrasonic signal to determine the dis- tance to the beacon. Of course, the value of the estimated distance is not as important as the decision of which the closest beacon is. The use of time-of-flight of signals to measure distance is not a new concept. GPS uses the one-way delay of radio waves from satellites to estimate distance, while radio-altimeters in aircrafts use the time for an electromagnetic signal to reflect off the ground to determine altitude. Collision avoidance mechanisms used in robotics 17 de- termine the distance to obstacles by measuring the time-of-flight of an ultrasonic signal being bounced off them. It is also possible to measure the distance using the relative veloc- ity of two signals. It is common practice to use the time elapsed between observing a lightning (electromagnetic waves) and accom- panied thunder (sound) to estimate the distance to the lightning. The Bat system (detailed in Section 6) uses this idea to determine a mobile transmitter's position in space, where an array of calibrated receivers measure the time of flight of an ultrasonic signal emitted by a mobile transmitter in response to an RF signal from a base station sent to the transmitter and all the receivers. 2.2 Reducing interference While Cricket has the attractive property that its decentralized bea- con network is easy to configure and manage, it comes at the ab- sence of explicit coordination. There is no explicit scheduling or coordination between the transmissions of different beacons that may be in close proximity, and listeners do not transmit any infor- mation to avoid compromising privacy. This lack of coordination can cause RF transmissions from different beacons to collide, and may cause a listener to wrongly correlate the RF data of one bea- con with the ultrasonic signal of another, yielding false results. Fur- thermore, ultrasonic reception suffers from severe muhipath effects caused by reflections from walls and other objects, and these are or- ders of magnitude longer in time than RF multipath because of the relatively long propagation time for sound waves in air. In fact, this is one of the reasons it is hard to modulate data on the ultrasonic signal, which makes it a pure pulse. Thus, the listener's task is to gather various RF and ultrasound (US) samples, deduce and corre- late the {REUS} pairs that were sent concurrently by the different beacons, and choose the space identifier sent from the pair with the closest distance. We decided not to implement a full-fledged carder-sense-style channel-access protocol to avoid collisions in order to maintain simplicity and reduce overall energy consumption. Instead, we han- dle the problem of collisions using randomization. Rather than us- ing a fixed or deterministic transmission schedule, beacon transmis- sion times are chosen randomly with a uniform distribution within an interval R1, R2ms. Thus, the broadcasts of different beacons are statistically independent, which avoids repeated synchroniza- tion and prevents persistent collisions. The choice of random in- terval is governed by the number of beacons we typically expect will be within range of each other and the time it takes for the transmitted information to reach the listeners, which depends on the message size and link bandwidth. In our implementation, we use an average frequency of four times per second distributed in 150, 350ms. A smaller frequency increases the amount of time be-
`
`

`

`fore a statistically significant location inference can be made, while a higher frequency increases the probability of collisions. We plan to extend this technique to include a listening component that will allow each beacon to infer the number of beacons in its proximity and appropriately scale the beaconing frequency. We minimize errors due to RF and ultrasonic interference among beacons by two methods: (i) proper selection of system parameters to reduce the chance of false correlations, and (ii) listener inference algorithms based on statistical analysis of correlated {RF, US} sam- pies. 2.2.1 System parameters In addition to transmitting a string corresponding to the space, each beacon transmits a unique identifier. The combination of the loca- tion string and identifier is unique across the entire system. This allows the listener to correlate the RF and ultrasonic beacon signals correctly. The raw line-of-sight range of our ultrasonic transmitter-receiver pair is around 50 feet, when both the transmitter and the receiver are facing each other. However, by mounting the ultrasonic transmitters carefully, as described in Section 3.3, we are able to reduce the effective range to around 30 feet in the absence of any obstacles. The line-of-sight range of the RF transmitter-receiver pair is about 80 feet, which drops to about 40 feet when there is an obstacle (e.g., a wall). Since RF can travel farther than an ultrasonic transmission and can also travel through certain obstacles, it is almost impossible for a listener to receive an ultrasonic signal without receiving the corresponding RF signal. We discovered that one way to reduce the occurrence of false cor- relations is to use a relatively sluggish RF data transmission rate! Instead, if we used a high-bandwidth RF channel, the data identify- ing a space would reach a listener before the ultrasound pulse was detected. I.e., ifS is the size in bits of the message sent over the RF channel with a transmission rate of b bits/s, and 7- is the maximum propagation time for an ultrasonic signal in air between a beacon and a listener, a value of b < S/7- would mean that the ultrasonic signal corresponding to a given RF message would arrive while the S message bits are still being received. Together with the fact that the range of our ultrasound is smaller than our RF, this establishes that any potentially correlated ultrasound pulse must arrive while an RF message is being received. In the absence of interfering bea- con transmissions, this check suffices to do the correct correlation. The specific parameters used in our implementation are described in Section 3. We now proceed to investigate the different interference scenarios that are possible. 2.2.2 Interference scenarios To better understand the effects of interference and multipath (due to reflected signals) on distance estimation, we characterize the dif- ferent RF and ultrasonic signals that a listener can hear. Consider the RF and ultrasonic signals sent by a beacon A and an interfering beacon I. The listener potentially hears the following signals: • RF-A. The RF signal from A. • US-A. The direct ultrasonic signal from A. 1L~'-A i i US -A US -I RFs overlap Figure 1: RF-A:US-I interaction, with US-A arriving after US-I. The two RF transmissions overlap in time at the listener. • US-RA. The reflected ultrasonic signal from A. • RF-I. The RF signal from I. • US-I. The direct ultrasonic signal from I. • US-RI. The reflected ultrasonic signal from I. We only need to consider the cases when a US pulse arrives while some RF signal is being received. The reception of the first ultra- sonic signal US-A, US-RA, US-I, or US-RI while RF-A is being received will cause the listener to calculate the distance to A using the time interval between the detection of RF-A and the particular ultrasonic signal. This is because the listener, after receiving the RF signal from a beacon, waits for the first occurrence of an ultrasonic pulse to determine the distance. All subsequent ultrasonic recep- tions that arrive during this RF message are ignored. Of course, if the direct signal US-A is the first one to be received, the listener correctly estimates the distance to A. However, the wrong correla- tion of any other ultrasonic signal with RF-A could be problematic. Case 1: RF-A:US-RA. This combination with the reflected ultra- sonic signal from A causes the estimated distance to be larger than the actual distance to A. This situation can occur only if the di- rect signal US-A was never received by the listener. However, the problems caused by this to the system can be reduced by prop- erly aligned beacons (Section 3.3), as well as using multiple inde- pendent beacons per geographic space. In addition, in our experi- ence, we have found that the ability of the ultrasonic waves to bend around obstacle edges (diffraction) makes this a relatively infre- quent occurrence since the direct signal is usually detected before the reflected one. Case 2: RF-A:US-I. This is the combination of RF-A with the di- rect ultrasonic signal from an interfering beacon I, which arrives before the ultrasonic signal US-A. Since an ultrasonic pulse can only be received by a listener while the corresponding RF data packet is being received, RF-I should also be in transit to the lis- tener. Hence RF-A and RF-I should overlap at the listener as shown in Figure 1. 35
`
`

`

`If RF-A and RF-I are comparable in signal strength, they will col- lide, causing the listener to ignore this event because both RF mes- sages will be corrupted. On the other hand, if the signal strength of RF-I is substantially larger than RF-A, the two may not collide and the listener will end up calculating the correct distance to beacon I. The only situation that leads to a wrong distance estimate is when the signal strength of RF-I is much smaller than RF-A, causing the listener to use the RF-A:US-I combination to determine the dis- tance to A. We reduce the chances of this event by using RF sig- nals with longer range than US signals. This generally ensures a strong RF reception whenever the corresponding ultrasonic signal is received (hence the receipt of US-I, in general ensures a strong RF-I). Case 3. RF-A:US-RI. This occurs when a stray reflected signal from an interfering beacon I appears before US-A. As before, this can lead to wrong distance estimates as well. Although cases 2 and 3 may lead to incorrect distance estimates, our use of randomization reduces the repeated calculation of wrong estimates. If there are a large number of beacons in close proximity to each other, there can be a non-negligible number of wrong dis- tance estimates at the receivers. At this point, we have engineered our system to ensure that there are not more than five or six beacons that are within range of each other at any location. In addition, listeners do not simply use the first sample pair they get to infer their best location. Rather, they collect multiple samples and use an inference algorithm for this. 2.2.3 Beacon position inference We develop and compare three simple algorithms to determine which the closest beacon is, overcoming the interference problems of the previous section: Majority, MinMean, and MinMode. In our analysis of these algorithms, the distance estimate is rounded to the nearest ten inches and the data put into different bins according to how frequently they occur. This is done for each beacon sepa- rately. Furthermore, isolated stray samples are eliminated from the analysis; a small threshold number of consistent values (two, in our implementation) are needed before the corresponding sample is in- cluded for analysis. • Majority. This is the simplest algorithm, which pays no at- tention to the distance estimates and simply picks the beacon with the highest frequency of occurrence in the data set. This algorithm does not use ultrasonic signals for determining the closest beacon, but as we find in our experiments, this does not perform well. We investigate this primarily for compari- son with the other algorithms. • MinMean. Here, the listener calculates the mean distance from each unique beacon for the set of data points within the data set. Then, it selects the beacon with the minimum mean as the closest one. The advantage of this algorithm is that it can be computed with very little state, since a new sample up- dates the mean in a straightforward way. The problem with this algorithm is that it is not immune to multipath effects that cause the distance estimates to display modal behavior; where computing a statistic like the mean (or median) is not reflec- tive of any actual beacon position. 36 Room A Room B 0 0 Beacon A Listener Beacon B Figure 2: The nearest beacon to a listener may not be in the same geographic space. I C.0 • ..... Beacons Location C • I .................................... x ! ........................ <~ Physical Boundary xl Bl I Imaginary Boundary ~ • / Location A J. B.0 A.I Location B • • ix - A.0 I x ® x Figure 3: Correct positioning of beacons. • MinMode. Since the distance estimates often show significant modal behavior due to reflections, our approach to obtaining a highest-likelihood estimate is to compute the per-beacon sta- tistical modes over the past n samples (or time window). For each beacon, the listener then picks the distance correspond- ing to the mode of the distribution, and uses the beacon that has the minimum distance value from among all the modes. We find that this is robust to stray signals and performs well in both static and mobile cases. Section 4 discusses the results of our experiments. We note that these are by no means the only possible algorithms, but these are representative of the precision attainable with different degrees of processing at the listeners. 2.3 Beacon positioning and configuration The positioning of a beacon within a room or space plays a non- trivial role in enabling listeners to make the correct choice of their location. For example, consider the positioning shown in Figure 2. Although the receiver is in Room A, the listener finds the beacon in Room B to be closer and will end up using the space identifier advertised by the latter. One way of overcoming this is to maintain a centralized repository of the physical locations of each beacon and provide this data to listeners. Systems like the Bat essentially use this type of approach, where the central controller knows where each wall- or ceiling- mounted device is located, but it suffers from two problems that make it unsuitable for us. First, user-privacy is compromised be- cause a listener now needs to make active contact to learn where
`
`

`

`it is (observe that in Cricket, a listener is completely passive). Sec- ond, it requires a centrally managed service, which does not suit our autonomously managed environment particularly well. Fortunately, there is a simple engineering solution to this problem that preserves privacy and is decentralized. Whenever a beacon is placed to demarcate a physical or virtual boundary corresponding to a different space, it must be placed at a fixed distance away from the boundary demarcating the two spaces. Figure 3 shows an example of this in a setting with both real and virtual boundaries. Such place- ment ensures that a listener rarely makes a wrong choice, unless caught within a small distance (1 foot in our current implementa- tion) from the boundary between two beacons advertising different spaces. In this case, it is often equally valid to pick either beacon as the closest. 3 Implementation In this section, we describe the implementation of Cricket. We de- scribe the system parameters and hardware configuration, the API provided by the listener to applications running on the attached node, and some deployment issues with ultrasonic hardware. 180 ~ Figure 4: The radiation pattern of an ultrasonic transmitter. 3.2 Listener API 3.1 System parameters and hardware The message size of a beacon RF transmission is 7 bytes long in our implementation, and the RF transmission rate of our radios is 1200 bits/s. It therefore takes about 47 ms for the message to completely reach a listener, during which time an ultrasonic pulse can travel at most about 47 feet. The typical range of our RF radios is about 30 feet in the building. No listener can therefore be farther away than this to detect which space it is in. Cricket is implemented using inexpensive, off-the-shelf, simple hardware parts that cost less than U.S. $10 per beacon and listener. The beacon consists of a PIC micro-controller running at 10MHz, with 68 bytes of RAM and 1024 words of program memory. It uses a low-power SAW resonator-based RF transmitter and a single-chip RF receiver, both operating in