From wbell@CS.Cornell.EDU Mon Oct 29 21:00:20 2001 Return-Path: Received: from postoffice.mail.cornell.edu (postoffice.mail.cornell.edu [132.236.56.7]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f9U20Io21547 for ; Mon, 29 Oct 2001 21:00:18 -0500 (EST) Received: from dhcp-190.rover.cornell.edu (dhcp-190.rover.cornell.edu [128.84.24.190]) by postoffice.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id VAA07876 for ; Mon, 29 Oct 2001 21:00:17 -0500 (EST) Subject: 615 PAPER #48 From: Walter Bell To: egs@CS.Cornell.EDU Content-Type: text/plain Content-Transfer-Encoding: 7bit X-Mailer: Evolution/0.16.99+cvs.2001.10.18.15.19 (Preview Release) Date: 29 Oct 2001 20:59:55 -0500 Message-Id: <1004407217.1131.20.camel@brute> Mime-Version: 1.0 48) The Cricket Location-Support System This paper presents the design of the Cricket Location-Support System which allows for location aware services and applications. Cricket differs from other works that it allows clients to be aware of their location in contrast to services based on location tracking systems which have fundamental administrative and privacy issues. The goal of cricket is to place selected beacons (Crickets) throughout the desired region which beacon a unique string. All services available for this region associate themselves with this unique string either via explicit configuration or by having the service have access to a listener device which picks up the beacon and hence learns it's nearest Cricket. Client devices carry listeners which allow them to determine their current region and availability of services. In the cricket model, all location awareness is located in the client and does not need to be communicated to the network unless desired which removes the privacy problem of other systems. Crickets are simple beacon devices that transmit an ultrasonic sound as well as an RF signal which allows their relative location to be determined with good accuracy, allowing good delineation of regions in the environment. The Crickets randomly send out their unique id in order to not collide with each other, and through listeners, client devices can tell what Crickets are nearby and therefore what services are local. My major question is if this is worth all the effort for increased privacy. Sure, if the client does not desire to interact with the services, it cannot be located because only it knows it's location. However, any communication will inform entities in the network of its location either via queries to directory services or use of location specific services. Any map application is going to be performing repeated queries to a directory informing it of the client's location. It would seem all the effort and additional hardware doesn't provide much benefit over location tracking systems. The only way to not have your location known is to not use services, which defeats the purpose of this endeavor. It would seem to be a better approach to concentrate on location tracking systems and making the location data of individual devices not persistent or more secure. Cricket claims lower administrative costs than other location tracking systems, which I just don't believe given that some administrative entity will be in charge of such devices and will need to continually find all the devices that have moved are malfunctioning. This instead of a global infrastructure based system such as RADAR seems be be much more difficult to implement. From gleason@CS.Cornell.EDU Tue Oct 30 03:16:56 2001 Return-Path: Received: from postoffice2.mail.cornell.edu (postoffice2.mail.cornell.edu [132.236.56.10]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f9U8Gto28336 for ; Tue, 30 Oct 2001 03:16:55 -0500 (EST) Received: from cypher.cs.cornell.edu (dhcp-147.rover.cornell.edu [128.84.24.147]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id DAA17965 for ; Tue, 30 Oct 2001 03:16:48 -0500 (EST) Message-Id: <5.0.2.1.2.20011030031616.00ad7770@postoffice.mail.cornell.edu> X-Sender: gleason@pop.cs.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.0.2 Date: Tue, 30 Oct 2001 03:16:33 -0500 To: egs@CS.Cornell.EDU From: Sunny Gleason Subject: 615 PAPER #48 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed 48) The Cricket Location-Support System The Cricket paper introduces a number of interesting ideas in the realm of location-aware computing. 1) Implementation of a "location support" system, in contrast to a "location tracking" system 2) Utilization of RF as well as ultrasonic transmissions for obtaining distance information 3) Deployment of a completely specialized network for location awareness The emphasis on "location support" versus "location tracking" is unique to this paper. The authors argue that client location resolution should be a passive process, in the interests of preserving user privacy. I think the more valid concern is scalability -- it certainly makes more sense to have a fixed number of location transmitters in a given area. However, given the typical lackluster security deployed in wireless applications, the ability to home in on one's position "covertly" may or may not be a desirable property for many applications. I think the decision to use a hybrid approach to distancing is very creative. I was surprised by the accuracy that they obtained using ultrasonic frequencies. However, I would feel really bad for any pet dogs, bats, or porpoises that may wander into the area. I think that the deployment of a completely dedicated infrastructure for location support is somewhat unrealistic, whatever the cost of the devices. It would seem more practical to use their concepts to build a hierarchical, hybrid passive system out of existing infrastructure. For example, GPS -> Cellular -> 802.11 -> Bluetooth -> IRda/Ultrasound. With the advent of PAN standards for inter-device communication, this might be a feasible alternative to dedicated location-support systems. From viran@csl.cornell.edu Tue Oct 30 09:52:39 2001 Return-Path: Received: from moore.csl.cornell.edu (moore.csl.cornell.edu [132.236.71.83]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f9UEqbo02864 for ; Tue, 30 Oct 2001 09:52:37 -0500 (EST) Received: from localhost (viran@localhost) by moore.csl.cornell.edu (8.11.3/8.9.2) with ESMTP id f9UEqWu05712 for ; Tue, 30 Oct 2001 09:52:32 -0500 (EST) (envelope-from viran@moore.csl.cornell.edu) X-Authentication-Warning: moore.csl.cornell.edu: viran owned process doing -bs Date: Tue, 30 Oct 2001 09:52:32 -0500 (EST) From: "Virantha N. Ekanayake" To: Subject: 615 Paper 48 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII This paper describes a decentralized method of self-locating mobile nodes within a building. The nodes passively listen to beacons that are positioned within each discrete area, and determine which is closer. The beaconing itself is a combination of RF and ultrasonic broadcasts, whose differential arrival times give an indication of distance. Since the nodes do not communicate with a centralized tracking system to determine their location, this system provides a measure of privacy until the node actually wants to broadcast a service. Admittedly, the privacy issues don't seem that important since on first glance, any attempt to use the system by broadcasting a service immediately allows centralized tracking. However, it may be that a node just wishes to know it's own movement pattern and does not wish to take part in a global services network. It could also be used to just activate services within the current geographic area -- perhaps the user wandered into a room with an email access terminal (which it can figure out apriori from the room beacon code), and the user device can establish line of sight connectivity to the email terminal and download messages, all without notifying a centralized mapping and naming service. Perhaps you could use signal beacons that advertise the NON-presence of any services in the current area, so the mobile device could shut itself down or go into a low-power mode. Seen in this light, the location-support system presented here, along with it's low cost, appears to be a very interesting and useful innovation. The paper was well written, and the feasability of the system was explored very thoroughly. The only downside to the method that I can see is that you are flooding the area with ultrasonic energy (admittedly, at 40kHz it's slightly above a dog's hearing range) but I'm not sure what the EPA or PETA would have to say. On the plus side, it should keep the skunks, squirrels, bats, mice and birds away from the area. :) From eyh5@ee.cornell.edu Tue Oct 30 09:57:31 2001 Return-Path: Received: from memphis.ece.cornell.edu (memphis.ece.cornell.edu [128.84.81.8]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f9UEvUo03503 for ; Tue, 30 Oct 2001 09:57:30 -0500 (EST) Received: from james (james.ee.cornell.edu [128.84.236.65]) by memphis.ece.cornell.edu (8.11.6/8.11.2) with ESMTP id f9UEvNk01501 for ; Tue, 30 Oct 2001 09:57:23 -0500 Date: Tue, 30 Oct 2001 09:55:58 -0500 (EST) From: Edward Hua To: egs@CS.Cornell.EDU Subject: 615 Paper # 48 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Cricket Location-Support System Nissanka B. Priyantha, Anit Chakraborty, Hari Balakrishnan This is paper presents a technique, or rather, a commercially available product, that can be used to determine the location of a mobile or static device inside a building. According to the authors, five objectives were borne in mind while designing the Cricket: user privacy, decentralized administration for scalability, network heterogeneity, cost-effectiveness, and room granularity. The hardware of the Cricket has two components: a beacon and a listener. The beacon is installed fixed (e.g., on a wall or ceiling), and serves as a reference point. The listener can be attached to either a static or mobile device running networking applications. It monitors the signals from the listner to compute its relative distance, and thus obtains information of its current location. The beacon sends off signals in two forms: a RF signal and an ultrasound signal. This approach, according to the authors, resolves the issue of having excessive RF signals bouncing all over the place in a confined space, as the application is used indoors. The signal sent from the beacon contains two pieces of information: a location string and a unique identifier. The pair thus uniquely identifies a particular signal from a particular beacon across the deployed network. The authors also address the issue of interference from neighboring beacons, which essentially comes when there is a mismatch between the received RF signal and the received ultrasound signal by the listener. Much of the paper is presented from a implementation perspective. It is then followed by the results from the actual deployment of the Cricket system. To a very large degree, the success of the Cricket system depends on installing the beacons at proper, or near-optimal, locations inside a building. Therefore, in this paper, the authors also provide some guidelines on choosing the installation locations, orientation of the beacons with respect to each other, and their parametrical configurations. In this paper, it is not clear whether the listener receives enough information from the beacon to compute its location with respect to the other neighboring listeners in the vicinity. This information is essential when it comes to communications amongst these listeners and their attached devices. If this information is not provided to the listeners, then the Cricket system is not a truly de-centralized model, as the listener may still require access to the beacon or some other centralized server to retrieve such information. From ranveer@CS.Cornell.EDU Tue Oct 30 10:49:57 2001 Return-Path: Received: from exchange.cs.cornell.edu (exchange.cs.cornell.edu [128.84.97.8]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f9UFnuo12236 for ; Tue, 30 Oct 2001 10:49:56 -0500 (EST) content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" X-MimeOLE: Produced By Microsoft Exchange V6.0.4712.0 Subject: 615 PAPER 48 Date: Tue, 30 Oct 2001 10:49:56 -0500 Message-ID: <706871B20764CD449DB0E8E3D81C4D430213A7BB@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 48 Thread-Index: AcFhWoXJaj5dcRwwQkeGh1sa+HSLUA== From: "Ranveer Chandra" To: "Emin Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from base64 to 8bit by sundial.cs.cornell.edu id f9UFnuo12236 The Cricket Location-Support System This paper proposes a coarse-grained indoor location-support system. The idea is to have cricket beacons installed efficiently so that a node can determine his location without compromising privacy. Privacy, security and manageability are the main motivation of this work. A combination of RF and ultrasound transmissions from the cricket beacons are used by the user to calculate his location within the precision of a few feet. Cricket seems to be the first location-support system without providing a complete architecture for location tracking. In this system, a user is aware of his location, but this information is not available at any centralized server. The main uses of a location support system is when a node wishes to take location and environment-aware actions and cricket seems well suited for such an application. The best feature of the Cricket system is its decentralized set up. Cricket beacons are cheap to install and provide a good solution to the privacy concerns of a mobile user. However, Cricket does not provide accurate location information. It provides precision within a few feet, while BAT and RADAR do much better. Cricket uses the idea of the BAT system of using a combination of RF and ultrasound to determine location. A 3-d location of BAT beacons allow it to provide a more accurate information which is a tradeoff with respect to the cost of deployment. However, it would be unfair to compare Cricket with either BAT or RADAR since Cricket does not aim to solve the problem of location tracking and has completely different design goals. Overall Cricket performs well in what it aims to do!!! From avneesh@csl.cornell.edu Tue Oct 30 10:51:39 2001 Return-Path: Received: from capricorn.ds.csl.cornell.edu (capricorn.csl.cornell.edu [132.236.71.92]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f9UFpbo12670 for ; Tue, 30 Oct 2001 10:51:37 -0500 (EST) content-class: urn:content-classes:message Subject: 615 Paper 48 MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Date: Tue, 30 Oct 2001 10:53:09 -0500 Message-ID: <97C142C1212ED545B0023A177F5349C4053B21@capricorn.ds.csl.cornell.edu> X-MimeOLE: Produced By Microsoft Exchange V6.0.4712.0 X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 Paper 48 Thread-Index: AcFhWvjQjpt7mMMOQ+G9O3cSdCcZAA== From: "Avneesh Bhatnagar" To: Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id f9UFpbo12670 The Cricket Location-Support System Summary/CRitique The Cricket location support system builds a decentralized location discovery mechanism, which involves the use of two inexpensive devices: a beacon and a listener. The beacon is attached to a stationary location and is a reference device, while the listener polls signals from the beacon to deduce the location information. The beaconing process includes two different waves: RF component and an ultrasonic compononent, the former being the faster wave. This is done in order to alleviate the effects of ultrasound multipath effects and RF interference. These signals are correlated to each other and a distance estimate is derived using the difference between RF and ultrasonic signal propagation times. Each beacon transmits a generic location string and an identifier. Since this is a location support system, not much emphasis has been placed upon the content of these messages, since that would depend on the underlying system. The paper also addresses means of reducing interference and gives results in both static and mobile scenarios. Three algorithms are suggested: a. MinMean b. MinMode c. Majority out of which the MinMode algorithm performs best since the statistic is the mode of the distribution, the results being supplemented by the fact that distance estimates exhibit modal behaviour. Another aspect of this system which arises due to the decentralized mechanism, is user privacy, which seems like a good idea, but I am not sure what the decentralized term means in this sense. To be truly decentralized, you should also be able to infer the location of other listeners, which might not have been addressed here. Applications of this service are many, so I think that its a good idea, although the locationing of the beacons is extremely important for location accuracy. From daehyun@csl.cornell.edu Tue Oct 30 11:09:47 2001 Return-Path: Received: from wilkes.csl.cornell.edu (wilkes.csl.cornell.edu [132.236.71.69]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f9UG9ko15536 for ; Tue, 30 Oct 2001 11:09:46 -0500 (EST) Received: (from daehyun@localhost) by wilkes.csl.cornell.edu (8.9.3/8.9.2) id LAA26150 for egs@cs.cornell.edu; Tue, 30 Oct 2001 11:09:41 -0500 (EST) (envelope-from daehyun) From: Daehyun Kim Message-Id: <200110301609.LAA26150@wilkes.csl.cornell.edu> Subject: 615 PAPER 48 To: egs@CS.Cornell.EDU Date: Tue, 30 Oct 2001 11:09:41 -0500 (EST) X-Mailer: ELM [version 2.4ME+ PL54 (25)] MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit This paper presented a location support system called Cricket. Cricket provides location information to nodes in an indoor environment. It is decentralized managed, supports user privacy and costs low. The main feature of Cricket is that there is no centralized management. Cricket is different form the conventional location tracking systems. It doest not track users or store information in a central database. This feature give some good properties. First, it preserves user privacy, because it doest not track users. Second, it is highly scalable, because there is no centralized server. Beacons spread through the building disseminate location information with RF and ultrasonic signals. Then, listeners attached nodes receive these signals and infer the space they are in. The implementation goal was 100% precision with a granularity of a few feet. They used decentralized randomized transmission algorithm for beacons to deal with interference and collision of signals and a algorithm - picking the beacon with minimum statistical mode - for listeners. This paper presented three experiment results. The first one showed the granularity, the second one the performance of static nodes and the third one the performance of moving nodes. I think the main contribution of this paper is that Cricket provides a location service without a centralized management. As shown in the comparison with other systems, Cricket seems to be the best. But I'd like to point out the maintenance problem. Usually decentralized systems are more difficult and expensive in maintenance. From ramasv@CS.Cornell.EDU Tue Oct 30 11:15:06 2001 Return-Path: Received: from exchange.cs.cornell.edu (exchange.cs.cornell.edu [128.84.97.8]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f9UGF4o16974 for ; Tue, 30 Oct 2001 11:15:04 -0500 (EST) content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" X-MimeOLE: Produced By Microsoft Exchange V6.0.4712.0 Subject: cs615 PAPER 48 Date: Tue, 30 Oct 2001 11:15:04 -0500 Message-ID: <706871B20764CD449DB0E8E3D81C4D4301E7F282@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: cs615 PAPER 48 Thread-Index: AcFhXgiCpmORBR6sTDecbJJc7IBViA== From: "Venu Ramasubramanian" To: "Emin Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id f9UGF4o16974 The Cricket Location Support System Cricket is a decentralized system that helps applications to infer their physical location with a coarse granularity (room). Cricket uses cheap hardware, has no centralized components to administer and allows users to locate themselves without compromising privacy. The applications could then make use of the location information to get hold of local services such as printer etc., but cricket itself does not concern with application level issues. Cricket achieves decentralization by intelligently placing beacons around the boundary of each locatable region such as a room. The beacons consist of cheap hardware that periodically sends an RF signal and an ultra-sonic signal. The time difference between the reception of the two indicates the distance of the listener from the beacon. Randomization is used to avoid collisions but this restricts the the number of beacons in a region to be very small (6). Listeners ony detect relative distance and hence can locate themselves only in very large spaces such as a room. The granularity depends on the number and placement of beacons around the boundary of partitions. The main advantages of cricket comes from the absence of centralized servers and assurance of user privacy. Virtual partitions can also be detected by intelligent beacon placement. However, optimal placement of beacons becomes very crucial especially because increased number of beacons cause more collisions of the periodic signal. The paper does not describe any efficient way to automatically find optimal beacon locations. Applications using the cricket location support system may eventually involve using centralized servers thus negating the advantages of cricket itself. Nevertheless, this kind of coarse location inference may suffice in enviroments such as buildings with many partitions. From teifel@csl.cornell.edu Tue Oct 30 12:09:22 2001 Return-Path: Received: from disney.csl.cornell.edu (disney.csl.cornell.edu [132.236.71.87]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f9UH9Lo26141 for ; Tue, 30 Oct 2001 12:09:21 -0500 (EST) Received: from localhost (teifel@localhost) by disney.csl.cornell.edu (8.11.3/8.9.2) with ESMTP id f9UH9Gg79020 for ; Tue, 30 Oct 2001 12:09:16 -0500 (EST) (envelope-from teifel@disney.csl.cornell.edu) X-Authentication-Warning: disney.csl.cornell.edu: teifel owned process doing -bs Date: Tue, 30 Oct 2001 12:09:15 -0500 (EST) From: "John R. Teifel" To: Subject: 615 PAPER 48 Message-ID: <20011030120055.J65596-100000@disney.csl.cornell.edu> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Cricket: This paper discusses the Cricket design, a location-support system for mobile, location-dependent applications. The main goals of this system is to provide user privacy, decentralized administration, network heterogeneity, low coast, and portion-of-a-room granularity. Cricket doesn't explicitly track user location, rather it allows devices to learn where they are and who they desire to communicate with. Unlike RADAR, it is more of a true ad hoc, distributed network. Cricket uses beacons to communicate network information to listeners. Every mobile (and possibly static) node has a listener attached to it. Beacons are composed of both RF and ultrasonic signals, from which specialized algorithms are able to extract relevant location and other information about the network and its topology. This system has been sucesseful at implementing in-building active maps and also mobile device control. Unlike RADAR it supports a heterogeneous network, decentralized control, and has low component cost to set up the network ($10--although I believe that this is in addition to any wireless cards, etc.). It should be noted that Cricket is simply a location-support service, not a location-tracking one. It would be interesting to see if additional location-hints that Cricket and RADAR provide can be used to improve adhoc network routing protocols. I think some additional auxiliary support (like Cricket provides) can help out adhoc networks... rather than simply providing on straight RF communication that the network uses for its main mode of data communication. From papadp@ece.cornell.edu Tue Oct 30 12:10:39 2001 Return-Path: Received: from memphis.ece.cornell.edu (memphis.ece.cornell.edu [128.84.81.8]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f9UHAco26411 for ; Tue, 30 Oct 2001 12:10:38 -0500 (EST) Received: from photon (photon.ece.cornell.edu [128.84.239.166]) by memphis.ece.cornell.edu (8.11.6/8.11.2) with ESMTP id f9UHAUk05142; Tue, 30 Oct 2001 12:10:30 -0500 Date: Tue, 30 Oct 2001 12:14:46 -0500 (EST) From: "Panagiotis (Panos) Papadimitratos" To: Emin Gun Sirer cc: Panagiotis Papadimitratos Subject: 615 PAPER 48 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Review of: "The Cricket Location-Support System," by N.B.Ptiyantha and H. Balakrishnan Pangiotis Papadimtratos papadp@ece.cornell.edu The proposed scheme, which appeared shortly after RADAR, combines unltrasonic beacons and RF singal measurements in order to provide accurate location information. It is based on cheap COTS and a deployment of beacons at each location. Its basic idea is to correlate the RF signal with the received beacons to infer the location by determining the closest beacon. In particular, beacons transmit an RF advertisment accompanied by a concurrent ultrasonic beacon. Portable devices use a listener, which upon receipt of the first few bits of the advertisement scan for the corresponding ultrasonic beacon. They produce an estimate of the beacon distance and then use one inference algorithm to provide for a maximum-likelihood-like estimate of which are the two correlated signals. The system performs in general better, in terms of error, when the portable device is not moving, and has as a stated goal the provision of the location estimate in a timely manner. Nevertheless, this is not adequately supported or contrasted to RADAR, active badge etc. It is also unclear how exactly the system is proven more secure and supports user privacy. In fact, the decentralized structure does alleviate the need to search a data base (as in RADAR), but if cricket wants to scale, it still needs centrlized mnagement, thus an analogous vulnerability. Moreover, privacy in location determination does not mean much, since the user probably seeks and attaches to a certain service/server. From samar@ece.cornell.edu Tue Oct 30 12:46:24 2001 Return-Path: Received: from memphis.ece.cornell.edu (memphis.ece.cornell.edu [128.84.81.8]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f9UHkNo01348 for ; Tue, 30 Oct 2001 12:46:23 -0500 (EST) Received: from descartes (descartes.ee.cornell.edu [128.84.236.60]) by memphis.ece.cornell.edu (8.11.6/8.11.2) with ESMTP id f9UHkFk06276 for ; Tue, 30 Oct 2001 12:46:15 -0500 Date: Tue, 30 Oct 2001 12:45:25 -0500 (EST) From: Prince Samar X-Sender: samar@descartes.ee.cornell.edu To: egs@CS.Cornell.EDU Subject: 615 PAPER 48 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII 48) The Cricket Location-Support System This paper presents design, implementation and evaluation of Cricket, which is a location support system based on the difference of the propagation speeds of radio frequency and the ultra-sonic frequency to determine the distance of the user from the beacon. The goals of designing the system have been: user privacy, decentralized administration, network heterogeneity, low cost and granularity. Beacons are deployed in the coverage area which give out randomized transmissions (RF as well as US at the same time) and the nodes use a decoding algorithm that uses the minimum of modes from different beacons to compute a maximum likelihood estimate of location. The user's listening device calculates an estimate of the distance to the beacon by determining the time interval between the receipt of the first bit of the RF signal and the receipt of the ultra-sonic pulse. This estimate helps in determining the position of the user coarsely (eg in a room). Smart placement of the beacons around the boundary of the room (or a virtual partition) may increase the granularity a little bit. Randomization helps in decreasing the probability of a collision but reduces the maximum number of beacons that can be placed in a certain region. Scalability of the system is dependent on a centralized administration, thus negating one of the advantages of cricket. Also smart placement of the beacon becomes a problem if this has to be done in each of its deployment. Although the granularity of cricket is not much, it does seem to attain the goals it was designed for. From andre@CS.Cornell.EDU Tue Oct 30 13:01:39 2001 Return-Path: Received: from postoffice.mail.cornell.edu (postoffice.mail.cornell.edu [132.236.56.7]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f9UI1bo04060; Tue, 30 Oct 2001 13:01:37 -0500 (EST) Received: from khaffy (d7b102.dialup.cornell.edu [128.253.157.102]) by postoffice.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id NAA06626; Tue, 30 Oct 2001 13:01:34 -0500 (EST) Received: from andre by khaffy with local (Exim 3.31 #1 (Debian)) id 15yXcB-000076-00; Tue, 30 Oct 2001 13:03:31 +0100 Date: Tue, 30 Oct 2001 13:03:31 +0100 From: =?iso-8859-1?Q?Andr=E9?= Allavena To: egs@CS.Cornell.EDU Cc: andre@CS.Cornell.EDU Subject: 615 PAPER 48 Message-ID: <20011030130330.A404@khaffy> Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Disposition: inline Content-Transfer-Encoding: 8bit User-Agent: Mutt/1.3.20i Sender: =?iso-8859-1?Q?Andr=E9_Allavena?= The Cricket Location Support System This paper presents location support scheme where the receiver is totaly passive (in other words, his confidentiality is preserved). There are beacons dissemited all over the place (at least one in each room) which periodically (in fact, at random time) adertise the name of the room (or a reference to a DNS). Those beacons send a HF signal as well as an ultrasonic signal (because the HF is not enough to localise the colsest one). Matching both allows to find with a good certainty the closest beacon. This is our position. Note that the precision of the location is limited by the number of beacons. Using random time to transmit and the ultrasonic messages overcomes the interferances between beacons. (Isn't there an issue using ultrasonic with animals?) The position of the beacons has to be carefuly choosen (so that a beacon in another room doesn't seem closer than the one in the room we are). This could beacome a headhake if one want to have many beacons all over the place. Installing them will also take a while. -- André Allavena (local) 154 A Valentine Place École Centrale Paris (France) Ithaca NY 14850 USA Cornell University (NY) (permanent) 879 Route de Beausoleil PhD in Computer Science 06320 La Turbie FRANCE From jcb35@cornell.edu Tue Oct 30 14:06:21 2001 Return-Path: Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f9UJ6Ko13047 for ; Tue, 30 Oct 2001 14:06:20 -0500 (EST) Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by travelers.mail.cornell.edu (8.9.3/8.9.3) with SMTP id OAA01575 for ; Tue, 30 Oct 2001 14:06:16 -0500 (EST) From: jcb35@cornell.edu Date: Tue, 30 Oct 2001 14:06:16 -0500 (EST) X-Sender: jcb35@travelers.mail.cornell.edu To: egs@CS.Cornell.EDU Subject: 615 PAPER 48 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII This paper evaluated a method of using triangulation over RF-based devices to track a mobile node's location. The RADAR system uses a method based on triangulation based on signal strength to approximate location. Their experiments were carried out on a floor with three base stations and one mobile laptop. By obtaining a tuple of the mean signal strength from a few base stations, they can try to accurately determine the location based on previous signal measurements by determining which tuple the measurements are "closest" to. They also store information about orientation, since the direction a wireless unit is facing can dramatically affect its signal. They mention the main limitation of their empirical model is that you must know the measurements of many of the tuples before you can be used. I could image this would not be reasonable for all cases. This method also seems highly dependent on the RF environment, since anything that would weaken a base station's signal could affect the location reading you are given. From jcb35@cornell.edu Tue Oct 30 14:21:12 2001 Return-Path: Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f9UJLBo15535 for ; Tue, 30 Oct 2001 14:21:11 -0500 (EST) Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by travelers.mail.cornell.edu (8.9.3/8.9.3) with SMTP id OAA12555 for ; Tue, 30 Oct 2001 14:21:04 -0500 (EST) From: jcb35@cornell.edu Date: Tue, 30 Oct 2001 14:21:04 -0500 (EST) X-Sender: jcb35@travelers.mail.cornell.edu To: egs@CS.Cornell.EDU Subject: 615 PAPER 48 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII (oops, sent the other paper here by accident earlier...) Cricket designs a location-support system for mobile systems with location dependent applications. Instead of trying to track users like RADAR, this system has a much different purpose from the outset - it wants to allow location dependent applications to be able to take advantage of nearby devices while maintianing decentralized administration and user privacy. Cricket users beacons to dissiminate information about a geographic space to the devices (listeners) that need to know location information. They were able to use a combination of RF and ultrasound hardware (the ultrasound was needed so that the mobile node could tell how far the "cricket" device was away) to measure who the closest device was, and in turn, what kind of services were available. In their experimental results, they show that they need to properly align the cricket devices so as to avoid ultrasonic leakage to other rooms. Their method seems to have a less acruate system that something like RADAR, but their requirements did not dictate a need to determine exact location. I think it would be interesting to try to use the ultrasound devices the way they did in cricket in radar, I would think that you could deteremine distances a little more accurately that their emperical method. The one thing I'm not clear on, however, is how this system necessarily maintains privacy. I would think that there is no garuntee that the crickets aren't tracking information about the nodes around then. From gupta@CS.Cornell.EDU Tue Oct 30 14:24:16 2001 Return-Path: Received: from ringding.cs.cornell.edu (ringding.cs.cornell.edu [128.84.96.109]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f9UJOFo16023 for ; Tue, 30 Oct 2001 14:24:15 -0500 (EST) From: Indranil Gupta Received: (from gupta@localhost) by ringding.cs.cornell.edu (8.11.3/8.11.3/C-3.2) id f9UJOEb25169 for egs@cs.cornell.edu; Tue, 30 Oct 2001 14:24:14 -0500 (EST) Message-Id: <200110301924.f9UJOEb25169@ringding.cs.cornell.edu> Subject: 615 PAPER 48 To: egs@CS.Cornell.EDU Date: Tue, 30 Oct 2001 14:24:14 -0500 (EST) X-Mailer: ELM [version 2.5 PL3] MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit The Cricket location-support system, N.B. Priyantha, A. Chakraborty, H. Balakrishnan. This paper describes a novel, inexpensive (cost per mobile host less than $ 10) hardware technique for measuring user location accurately. The hardware relies on the different between propagation speeds of RF and ultrasonic waves to estimate the distance from base stations. Triangulation is used thereafter. Errors in distance measurement can still occur, primarily because of multipath interference or interference in radio waves from different base stations. These are enumerated in the paper, and some of them solved. The data from each beacon is further smoothed over multiple trials - majority, min-mean and min-mode are different strategies evaluated, and the third one performs the best, giving the lowest error rates in location estimation. The paper also discusses several deployment issues, such differing propagation speeds due to differing temperature/humidity along the path. Comments: The use of RF _and_ ultrasonic waves eliminates the effect of interference if only RF waves were used. This idea also eliminates the need to deal with accurate propagation models for RF. The authors describe what kind of interference can cause their protocols to err in measuring the distance from a beacon. Their experimental set-up within the building reveals that the likelihood of these errors are small, but a discussion of the other kinds of scenarios that might make these instances more likely, and thus require a longer time to converge to the correct estimate (or converge to a wrong estimate altogether due to persisting interference). From haom@csl.cornell.edu Tue Oct 30 16:25:03 2001 Return-Path: Received: from mauchly.csl.cornell.edu (mauchly.csl.cornell.edu [132.236.71.68]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f9ULP1o13736 for ; Tue, 30 Oct 2001 16:25:01 -0500 (EST) Received: from localhost (haom@localhost) by mauchly.csl.cornell.edu (8.9.3/8.9.2) with ESMTP id QAA24394 for ; Tue, 30 Oct 2001 16:24:56 -0500 (EST) (envelope-from haom@mauchly.csl.cornell.edu) X-Authentication-Warning: mauchly.csl.cornell.edu: haom owned process doing -bs Date: Tue, 30 Oct 2001 16:24:56 -0500 (EST) From: Ming Hao To: Emin Gun Sirer Subject: 615 PAPER 48 In-Reply-To: <200110300148.f9U1mpm03163@zinger.cs.cornell.edu> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII The Cricket Location-Support System by Nissanka B. Priyantha it does not convince me that location dependant application inside a building will become popular. it even does not talk about what thos potential applications are. the architecture of Cricket is: there are many small devices which are placed around the building. those baecons are aware of the locations and advertise this info to its surrounding space. every node here has a listener attached to it. via listener, the node can get the location infomation. the main differnce from GPS is that the way getting location info is distributed. the position of node is determined by checking the distance of it away from a beacon. the distance is measured by measuring the differnce of arriving time of RF signal and ultrasonic signal. the listeners are totally passive. this ensures the privacy of the user and is one of main controbutions of this paper. but i think somewhere, the node has to be active to get more infomation from services which offsets the effort of getting the information passively. further, it is desirable to have a central database recording the locations of all the beacons because it makes management easier. though the beacons are placed in a distributed way and no central database is needed to record the info about beacons. but considering the number of beacons, replacing the out-of-order beacons is still a intiminating job. the idea is ok. but i still think it has no applications inside a building and in the outdoor environment, GPS is better choice. -ming Ming Hao PH.D Candidate, EE mh97@cornell.edu Cornell University Office: (607) 255-0817 Ithaca, NY 14853 http://www.ee.cornell.edu/~haom/