From kwalsh@CS.Cornell.EDU Wed Oct 2 19:07:24 2002 Received: from mail.usadatanet.net (mail.usadatanet.net [208.48.41.252]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g92N7Nh28319 for ; Wed, 2 Oct 2002 19:07:23 -0400 (EDT) Received: from home.cs.cornell.edu (unverified [208.51.228.46]) by mail.usadatanet.net (Vircom SMTPRS 5.1.202) with ESMTP id for ; Wed, 2 Oct 2002 18:58:49 -0400 Message-Id: <5.1.1.6.0.20021002180208.00a76ca0@mail.flashmail.com> X-Sender: (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1.1 Date: Wed, 02 Oct 2002 19:06:58 -0400 To: egs@CS.Cornell.EDU From: Kevin Walsh Subject: 615 PAPER 27 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed (a) The Cricket Location-Support System (b) RADAR: An In-Building RF-Based User Location and Tracking System (c) GPS-less Low Cost Outdoor Localization For Very Small Devices Three papers tackle the problem of determining the location of devices, but make very different assumptions based on the intended applications. The application space can be roughly divided along the following axes: indoor vs outdoor; fine grained vs coarse grained; light weight (low power/cost) vs heavy wieght (high power/cost). The Global Positioning System (GPS) works well with medium- to coarse-grained (tens of meters) outdoor heavy-weight applications, where receivers are relatively expensive (accurate clocks) and high-power. The GPS-less paper is designed for medium-grained (meters) outdoor light-weight applications at low cost and low power. For indoor use, Cricket and RADAR both aim for fine-grain (tenths of meters) indoor light-weight applications, although very different approaches are taken. GPS uses triangulation by measuring propagation-time from highly synchronized satellites. GPS-less instead relies on measurements of signal strength as measured from nearby radio beacons. We assume that beacons can determine their location by other means (manual configuration, GPS, etc.). Under the assumption that connectivity is a binary function only of distance, a node estimates it's location as the centroid of the locations of all neighboring beacons. Here, connectivity is based on meeting some threshold (90%) of beacon messages. The method is demonstrated to be somewhat effective outdoors in a flat 10x10m parking lot, where signal propagation is nearly ideal (uniform and spherical). From the simulated data, however, it appears as if the largest source of error is that a node does not estimate which of its neighboring beacons is closest, but instead assumes that all "connected" beacons are equidistant and all "non-connected" beacons are disregarded. This seems artificial and wasteful. Why not weight each beacon by the percentage of successfully received beacon messages, (presumably) allowing a node to estimate closer to "high connectivity" beacons and further from "low connectivity" beacons. It is also unclear weather large blobs of water (ie people, trees, etc.), rock, metal (walls, infrastructure), etc., will allow this system to work at all, since they all seriously distort RF signals. RADAR works on a similar principle as GPS-less, but measures the signal strength to all neighboring beacons. The difficulty indoors is that simple centroid estimation will tend to ignore the effects of walls, line-of-sight, bodies (the observer in particular), etc. Instead, an off-line calibration phase is needed to collect data samples from many locations. Then a best-fit matching/interpolation algorithm can fit real-time data to the pre-measured data in order to find the location. Here, the authors choose to use a centroid in the signal strength difference space, but it is not clear why this is a good idea. The authors data shows that the best-fit algorithm works somewhat better than simply choosing the location of the strongest beacon as the estimated location, which in turn works somewhat better than simple random guessing. A significant problem, however, is in the difficult calibration phase, as well as the non-ideal propagation of RF signals (as before). CRICKET tackles the same indoor location problem by using custom (but cheap) hardware. Beacons simultaneously broadcast both RF and ultrasound (US) signals, which travel at vastly different speeds. A node calculates the difference in arrival time, an can use this as an estimate of distance. Despite the non-ideal RF propagation in terms of signal strength, it is reasonable to assume that the propagation time will be reasonably well-behaved (ie, pretty fast). Unfortunately, the US propagation time depends on numerous factors, including temperature, air density, objects in the room, etc. This prevents nodes from determining absolute location. However, the authors find an interesting solution to the problem. If beacons are cheap, then many can be placed in each room, including one on each side of, and equidistant to, imaginary division lines between spaces. Now, all that is needed is for a node to find the nearest beacon (not the absolute distance from a beacon). This allows the node to determine in which room (zone) it is. Aside from some interesting applications mentioned in the CRICKET paper, it is not clear what the uses will be for such services. Some new services might be: - Location-based service detection: physically close services can be linked or advertised, or the location of a distant service found - Interactive maps, or user-guided tours: a PDA could provide location-dependent information or advice to the holder - Calibration of sensor network: Data collection is often meaningless if the location of the sensor is unknown. In a static network, it is difficult to accurately measure the position of each sensor. In a mobile network (oceanography?), nodes need a way to determine their location directly. - Tracking: all sorts of tracking (both of objects and people) applications will probably drive this type of research. Industries are very concerned with keeping tabs on the location of equipment, inventory, employees, guests, etc. - Physical archiving: The RADAR paper gives an example of a user trying to locate a specific book in a library. Assuming the object's (book's) actual position is known, the location tracking device can guide the user to the object. One way to catalog the location of objects in the first place would be to use the location tracker when archiving each object. From jsy6@postoffice2.mail.cornell.edu Wed Oct 2 23:54:18 2002 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.10) with ESMTP id g933sIh29276 for ; Wed, 2 Oct 2002 23:54:18 -0400 (EDT) Received: from Janet.cornell.edu (syr-24-58-41-193.twcny.rr.com [24.58.41.193]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id XAA23539 for ; Wed, 2 Oct 2002 23:54:14 -0400 (EDT) Message-Id: <5.1.0.14.2.20021002235212.00b40028@postoffice2.mail.cornell.edu> X-Sender: jsy6@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Wed, 02 Oct 2002 23:53:27 -0400 To: egs@CS.Cornell.EDU From: Janet Suzie Yoon Subject: 615 PAPER 27 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed Cricket is an in-building location-support service rather than a location-tracking one. Its primary goal is to provide a low cost way for mobile and static devices to learn of their location in a heterogeneous network while preserving user privacy, scalability, and room-size granularity. Cricket works in the following way: for each space beacons are strategically placed (in order to help demarcate boundaries and reduce ultrasonic interference). For each device, a listener is installed. The beacon concurrently emits a RF and an ultrasonic pulse. Since the speed of sound is significantly slower than the speed of light (RF), a listener will first detect the RF signal which will then trigger its ultrasonic receiver. By calculating the time difference of the RF and ultrasonic signal, the listener is able to calculate its distance from the beacon. More importantly, the listener computes an estimate of the closest beacon by using the Min-Mode algorithm, which performs well despite interference and the multi-path effect. User privacy is maintained by allowing clients to learn of their location without the need of querying some centralized tracking system. Since no central entity keeps track of each client, Cricket provides a scalable decentralized administration. The decoupling of tracking services and obtaining location info allows Cricket to work in a wide range of network technologies. Demarcating boundaries between different regions is obtained by strategic placement of beacons. The cost of beacons and listeners is $10 each since no custom hardware is needed. RADAR is another location service for an in-building environment. Unlike Cricket, RADAR is a locating and tracking service that relies on a centralized database. More preprocessing is involved. First, the hosts and base stations synchronize their clocks. The mobile hosts then periodically broadcast UDP packets. The base stations record the signal strength of the broadcasts along with the synchronized timestamp. The tuples of base station, signal strength, and timestamp is collected during the off-line and real-time phase. During the off-line phase, the host must indicate its current location using a map of the floor and the RF signal strength is stored in the centralized database. During the real-time phase, this set of signal strength measurements is used to computer the best fit of observed signal strength for the current transmitter position. This approach is known as triangulation. In the specs, the mobile hosts are the beacons and the base stations record the periodically broadcasted information. RADAR would be more scalable if the base stations transmitted the beacons and the hosts measured the signal strength. A low-cost connectivity-based service for unconstrained outdoor localization is introduced in the third paper. The design goals are RF-based (which requires less power, size, and cost requirements than GPS), receiver based (hosts and not the reference points responsible for localization calculations in order to make it scalable), ad hoc, low response time, low energy, adaptive fidelity. Static reference points are first positioned in known locations. The reference points periodically beacon their respective positions exactly once in a given timeframe. Since reference points' regions overlap, neighboring reference points are synchronized to avoid collision. Each mobile host listens to these beacons for a fixed timeframe. Each host localizes itself to the centroid of the reference points whose beacons it received. Location estimates improve with an increase in region overlap. Due to Cricket's untapped possibility of hosts obtaining location information from remote nodes, Cricket's location service can be used to provide a somewhat ad hoc energy efficient networking scheme. RADAR can be used to locate nearby resources such as printers. RADAR and Cricket can be used to create a location-based naming service for devices. An application of a GPS-less outdoor localization scheme would be monitoring natural resources, such as water and soil, and environmental changes. From hs247@cornell.edu Thu Oct 3 01:24:24 2002 Received: from mailout6-0.nyroc.rr.com (mailout6-1.nyroc.rr.com [24.92.226.177]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g935OOh17420 for ; Thu, 3 Oct 2002 01:24:24 -0400 (EDT) Received: from hubby.cornell.edu (syr-24-58-42-130.twcny.rr.com [24.58.42.130]) by mailout6-0.nyroc.rr.com (8.11.6/RoadRunner 1.20) with ESMTP id g935OIx13640 for ; Thu, 3 Oct 2002 01:24:18 -0400 (EDT) Message-Id: <5.1.0.14.2.20021003012354.00b8d158@postoffice2.mail.cornell.edu> X-Sender: hs247@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Thu, 03 Oct 2002 01:24:18 -0400 To: egs@CS.Cornell.EDU From: Hubert Sun Subject: 615 Paper 27 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed This set of papers looks at networks which try to determine a location of a node. Cricket, Radar, GPS-less Outdoor Localization (from here on refered to as GPS-Less), and Active Badge all try to determine where a mobile node is but each one is intended for a different environments. Cricket and Radar are designed for nodes with more power such as laptops in an indoor environment. GPS-less and Badge were designed for nodes with very little power. GPS-less was designed for an outdoor setting. Cricket's idea is to have devices called beacons. The owner of these beacons can set them up anywhere in an indoor setting. These beacons periodically beacon an unique identifier and location information, which listeners (the nodes) can hear. The beacons send both infrared and RF waves. From this information, the listeners can determine their distances from the beacons and thus their position. To avoid contention, each beacon's waves are sent at randomized intervals. Cricket is meant for indoor environments and to deal with reflection off objects common in indoor settings, it uses a MinMode calculation where statistical mode of samples are taken from each beacon, and uses the minimum distance value from all the modes. In experiments, with good beacon setup, we can get accurate location information down to a few feet. One advantage of Cricket is that it decentralises work to the mobile nodes making it more scalable. Radar is also meant for indoor settings. How it differs is that instead of beacons it sets up "radars" which have zones that overlap. The mobile node beacons a message periodically (Opposite of Cricket). They first created a testbed with FreeBSD machines acting as radars, and laptops being the mobile nodes. They found that the ability to calculate the machines position not only depended on where they were but what direction they were pointed in. Two methods were used to gather data and calculate location: Empirical Method, and Radio Propagation Model. Though Empirical method provided more accurate data, the portability of it made it the less viable option because when radars are moved, recalibration is needed and new data has to be collected. The accuracy of Radar is about 2-3 meters. Unlike Cricket, Radar is a centralized model that collects data perhaps making it less scalable. GPS-Less differs from the above two in that GPS-Less was built for really small devices in an outdoor setting that don't have the power to run GPS. One can imagine these to be sensor nodes placed on animals or used for measurement in the physical world. These devices are really small and unintrusive. In this network, a set of overlapping nodes that know their location are used as static reference points. They are suppose to coordinate between neighbours so their RF beacons do not contend with each other. Other nodes in their network can then infer their positions for the beacons of selected number of reference points. The average error in localization was about 1.83 meters, but with a standard deviation of 1.07m! The Active badge is again meant for low powered nodes. This system was designed to track employees in a building. Each badge would beacon an infrared identifier every 15 seconds. This system tries to take advantage off existing networks to detect the location of these beacons. Things like a computer workstations could be equipped with sensors to listen to these beacons. The information is then sent back to a centralized server where one can map these sensors and their locations. (Not much detail in this paper of how the sensors actually worked and how they determine the location of these badges, but they just described a working system). How can localization be applied to different applications? Systems like Badge, GPS-Less are ideal for tracking nodes. The papers described a hospital setting or an office setting. And in GPS-less, it would be used to track animals in biological studies. Since most badges and small devices are cheap, they could be ideal to deploy in a setting like a ski hill or search and rescue where one would want to beacon for help, or want to search for a person lost in an avalanche. When would it be useful for nodes to know where they are? This happens every day. People get lost on highways, people get lost in malls. Whenever anybody is in a new setting, it could be useful to find out where they are on a map. How about knowing where your neighbouring nodes are? One could imagine a setting like Cricket where once nodes know where they are, they can advertise it. This could be useful in looking up of devices. Where is the closest printer? Where is the closest vending machine? In a military setting, knowing the location of your mates are key. Question like: who is the best position to fire? Distributed nodes can elect leaders based upon "best" location. In general, giving a node location information gives it a sense. Humans can infer where they are from their eyes and hearing. Location services in a way give nodes that sense. This could also help in the artificial intelligence area. Can we some how make a robot navigate through a building to fetch coffee? Knowing its own location and the location of the coffee machine, one could imagine that this could be possible. From mp98@cornell.edu Thu Oct 3 01:35:32 2002 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.10) with ESMTP id g935ZWh19533 for ; Thu, 3 Oct 2002 01:35:32 -0400 (EDT) Received: from cornell.edu (r109493.resnet.cornell.edu [128.253.240.252]) by postoffice.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id BAA09818 for ; Thu, 3 Oct 2002 01:35:29 -0400 (EDT) From: mp98@cornell.edu Date: Thu, 3 Oct 2002 01:35:10 -0400 Mime-Version: 1.0 (Apple Message framework v546) Content-Type: text/plain; charset=US-ASCII; format=flowed Subject: 615 Paper 27 To: egs@CS.Cornell.EDU Content-Transfer-Encoding: 7bit Message-Id: X-Mailer: Apple Mail (2.546) Cricket is a system wherein beacons are scattered around a building. Each beacon simultaneously transmits an RF signal containing a unique identifier and an ultrasound pulse at random intervals (the random intervals help avoid collisions). Based on the delay between receiving the RF signal and the ultra sound, a listening node can approximate its distance to the beacon and find its closest beacon to determine which room it is in. The authors suggest using this information for various services, such as maps. A nice feature of Cricket is that it is passive, which allows for privacy. Cricket could potentially be used to solve the hidden node problem: All hosts advertise what room they feel they're in and bidirectional links are assumed only between those nodes in the same room. RADAR is a considerably more invasive protocol sections of which (The whole world will be better when we get our users to wear omni-directional antennas so we can track where they are in buildings) really makes one understand why it comes from Microsoft research. In RADAR, base stations are scattered around the area in which RADAR is operating and the signal strength of a user's beacon is measured against either previously recorded signal strengths at known locations or (if that is impossible) a model of signal strength based upon Floor Attenuation Factor. A problem with this approach is that unlike the entirely passive CRICKET protocol, in order to do their work, the base stations need to know something of the signal strength of the user's card--If the user's signal strength does not match that which is expected, all measurements will be inaccurate. Note however that unlike Cricket, Radar does allow one to compare the locations of ad hoc nodes. It would be possible using this protocol to compute routing paths and information based on geographic location. Also, if node movement can be measured, one could possibly classify nodes in the network as 'moving' and 'stationary' and proactively expect certain links to break. Also a node disconnected from an ad-hoc network separate from the base stations could still communicate with them and perhaps the base stations could provide suggestions as to where to move to rejoin the network. The final protocol is somewhat similar to Cricket in that it is mostly passive and requires no large amount of infrastructure. This GPS-less localization, however, only uses RF signals, rather than RF signals and ultra-sound to find location. The basic idea is that static beacons should cover an area in a pattern like the world's worst Venn diagram, and a mobile node can figure out which beacons it can hear, and will figure out which intersection it is locating in. Unfortunately this protocol requires some set up (i.e. a constant spaced grid of beacons with overlapping coverage), the beacons must propagate perfectly (i.e. this is only useful in an environment without obstructions like walls) and unlike cricket, the mobile host must have some knowledge of the beacon placement. Because of this, the applications of this protocol, while it is attractively simple, are hard to imagine. Possibly with wide enough coverage, it could be used to track the movements of animals or network users in a field. It could also possibly be used in an auditorium or stadium (tracking sports players around a field). As a supplement to Ad-Hoc networks, assuming that the mobile nodes can gain knowledge of the mesh, it could be used to find neighbors and even paths: Because the overlapping areas have a grid-like geographic metaphor, one could imagine planned route based on the location of the destination. From mr228@cornell.edu Thu Oct 3 01:53:45 2002 Received: from cornell.edu (cornell.edu [132.236.56.6]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g935rih23584 for ; Thu, 3 Oct 2002 01:53:44 -0400 (EDT) Received: from cornell.edu (syr-24-58-48-238.twcny.rr.com [24.58.48.238]) by cornell.edu (8.9.3/8.9.3) with ESMTP id BAA19371 for ; Thu, 3 Oct 2002 01:53:38 -0400 (EDT) Message-ID: <3D9BDB65.72944DDE@cornell.edu> Date: Thu, 03 Oct 2002 01:53:41 -0400 From: Mark Robson X-Mailer: Mozilla 4.76 [en] (Windows NT 5.0; U) X-Accept-Language: en MIME-Version: 1.0 To: egs@CS.Cornell.EDU Subject: 615 PAPER 27 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit These papers all discuss ways for small devices to determine their location. While GPS receivers can already do this, GPS cannot be quite as precise as these systems. Cricket and RADAR are designed for indoor use and both claim to be accurate to within very small ranges. The "GPS-less..." paper describes a system for outdoor use that is less precise than Cricket or RADAR, but much more precise as compared to plain GPS. RADAR works by measuring signal strength from a number of receivers and then attempting to triangulate it position. Cricket uses both RF and ultrasound signals and computes distance from a receiver using the time differential of the propagation of these two waves. The GPS-less system has each node receiving beacons from base stations that "know" their locations. A node can then 'geometrically' determine where it is located. It seems to me to be GPS but with nearby, lower power base stations instead of satellites. Based on the (surely not impartial) qualitative analysis presented in the Cricket paper, it seems Cricket is the best of these systems, certainly for indoor use anyway. Each of the systems more-or-less has the goal of producing a low-cost, decentralized network that is easy to deploy and takes into account user privacy concerns. Cricket seems to meet these better than the other systems. There is a wide-range of interesting applications of such location technology. While customers may have serious privacy concerns with it, one can imagine retailers wanting to know what aisles shoppers walk down and in what order to better layout their stores. Targeted advertising and/or additional product information may also be obtained in this way. A small device capable of audio and/or video is carried by the customer and in return for carrying it, customers are eligible for coupons and other deals on products as these pass by them in the store. Tracking customers' purchases is the function of shoppers' club cards and the discounts received provide the incentive for customers to use them. Museums (stores, etc.) could provide automatic "tour-guides" by using location systems. When you walk up to a particular exhibit, a particular audio or video stream plays on a personal device your carry with you. This is already done in some museums (e.g. EMP is Seattle), however those typically require the user to type in a number or point an infrared sensor at the exhibit. There are obvious applications of this technology to the field of robotics. Car navigation assistance systems such as Hertz's NeverLost mentioned in the Cricket paper may also benefit from these types of systems. GPS systems may not provide enough specificity of location for these services. Location-specific information could be obtained on cell phones that are capable of such location identification (depending on granularity required, this may be doable with GPS also): Finding the closest movie theater showing a particular movie, finding the closest restaurant of a certain type, finding the closest... -- Mark Robson From bd39@cornell.edu Thu Oct 3 02:11:21 2002 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.10) with ESMTP id g936BKh26803 for ; Thu, 3 Oct 2002 02:11:21 -0400 (EDT) Received: from boweilaptop.cornell.edu (r102439.resnet.cornell.edu [128.253.163.42]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id CAA27906 for ; Thu, 3 Oct 2002 02:11:21 -0400 (EDT) Message-Id: <5.1.0.14.2.20021003013959.02596478@postoffice2.mail.cornell.edu> X-Sender: bd39@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Thu, 03 Oct 2002 02:08:25 -0400 To: egs@CS.Cornell.EDU From: Bowei Du Subject: 615 PAPER 27 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed Localization Services CRICKET The CRICKET system allow mobile devices to learn about their physical location within a building. CRICKET does not support precise coordinates; rather CRICKET devices are able to determine which location they are currently in closest proximity to. The cricket system consists of: - Beacons, devices installed in each location, which beacon an RF signal containing some form of useful ID string and a UV signal. Beacon broadcasts are jittered randomly to avoid collisions. - Receivers, which passively listen to beacons and uses UV and RF propagation speed differences to determine the distance to the originating beacon. The two signals also help resolve beacon broadcast collisions and reflections of signals. RF is used to designate first contact with the beacon, and the UV propagation difference from the RF can be used to determine distance. - Measurements of the distances have some degree of error, and the paper describes three methods of dealing with the received data, MinMean, which averages calculated distance values, and MinMode, which selects the distance estimate that has been derived the most. (Majority doesn't seem to be relevant, it doesn't even use any distance metric. It's interesting that distance estimates only bought about %5 gain in error rate.) - Authors performed experiments with the beacons and receivers, which demonstrated the proof of concept and helped tune beacon placement rules. Things of note: - Distributed operation: Setup of beacons only requires the owner of a location to maintain beacons in his/her location, not registration with a centralize server. However - this means that this is a prequisite to have human intervene to lay out the beacons. - Privacy. Paper notes that many location based systems rely on a centralized tracking system. The CRICKET beacons has no knowledge of the recievers of their beacons and location determination is completely passive. This is also a fallout from the distributed nature of CRICKET. - Who wants to maintain a building with thousands of independent battery powered beacons? I guess the idea would be to have every electronic device participate in the beaconing somehow. But then this would lead to suboptimal placement of the beacons... - Does not yield true location - only nearest known beacon. - Granularity is based upon the number of beacons and locations installed. RADAR: RADAR uses triangulation to determine the location of a device. By analysing the radio signal strength of base stations, it is possible to derive a best guess as to the distance the device is away from the location. Location determination data is generated in two ways. First, there is an empirical measurement of the radio signal strength from the beacons in many places on the map (grid), in various radio orientations. The data from these measurements was then used in a nearest neighbor search of the received signal strength. Better locations were obtained by a average of k-nearest neighbor locations obtained from the search. A second method employed was the modeling of the signal strength of the receiver based upon a propagation model that included the effects of walls on the signal. This model was then used to compute the data used in the nearest neighbor search. Some aspects of RADAR: - Need to know prior measurements of the radio signals to do a nearest neighbor search or need to know exact topology for generation of the data. - Comparison measures not really very revealing, especially the random metric. - Assumes a symmetry of radio strength and propagation of the receiver and transmitter. - How good is BS signal strength as a variable? GPS-less localization: The localization scheme of this paper uses the reception of packets from known reference points to determine the location of a node. All reference points broadcast a beacon. Location is calculated by taking the average of the coordinates of the references heard. - Uses ideal radio model - only works for wide, open spaces - could also factor in signal strength as well, but complicates radio propagation model - Field needs to be rather dense with reference points to be accurate Active-Badge: The active badge system involves a badge that beacons, and a large set of receivers. Location is determined by a receiver (who's location is predetermined) overhearing a badge beacon, and reporting it to a central server, which then updates its database of badge locations. - implemented commercial system - centralized, high cost to fully deploy Location based services: A few location based applications were already mentioned in the articles, i.e. use of a printer that is physically local, routing of telephone calls, contacts to the physically closest phone. Other typical services include map location services (a dot as to where one is in a building) and big brother services (dots as to where employees are in a building). Some scientific applications could be in sensor networks. One can imagine having several uber-sensors which are equipped with GPS units, and many lesser sensors which are not GPS equipped. When dropped over a field (or into a stream), the GPS enabled sensors will be able to determine where they are exactly. All other sensors use the GPS information and location services to approximately compute their position. Instant messaging - Chat could indicate that the person you are talking to is right next door. Then a message would appear suggesting actual face time. Meeting scheduling - The location of various individuals who are scheduled to arrive at a meeting. Who is tardy and where they are. Context aware computing - For example, standing next to a power plug, the computer informs the user to plug in and recharge. Inside meeting rooms, cell phones set themselves to vibrate instead of ring. For the forgetful, their lost devices can be self aware as to their own location. Devices close to a computer can be used. For example, a set of local speakers and microphone when a laptop computer used for a presentation is brought in close proximity. Security - taking certain devices away from a certain area will trigger an alarm or change the security level at which the device operates. Intelligent environments - devices in the environment that conform to who is present - i.e. smart house. Power efficiency - BS sees that all nodes can be covered are a certain distance away, and reduces transmission power accordingly. Also, sensors tracking an event can calculate a trajectory and alert nodes in the path of the event to listen, while nodes not in the trajectory can sleep. Services needed near a location can be active, while further from a location, nodes can power down. Directional Broadcast/Sends - An event is only of interest in a certain direction, send in that direction. From shafat@CS.Cornell.EDU Thu Oct 3 02:53:43 2002 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.10) with ESMTP id g936rhh06428 for ; Thu, 3 Oct 2002 02:53:43 -0400 (EDT) Subject: 615 PAPER 27 MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Date: Thu, 3 Oct 2002 02:53:42 -0400 Message-ID: <47BCBC2A65D1D5478176F5615EA7976D134F9C@opus.cs.cornell.edu> content-class: urn:content-classes:message X-MimeOLE: Produced By Microsoft Exchange V6.0.5762.3 X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 27 Thread-Index: AcJqqZwyo8VugLOGSV6zihcZ08vO2Q== From: "Syed Shafat Zaman" To: "Emin Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from base64 to 8bit by sundial.cs.cornell.edu id g936rhh06428 The first of the four papers describes Cricket - an innovative location-support system for mobile, location-dependent and in-building applications. It is based on beacons placed at different parts of a building that communicate with listeners attached to various devices using radio and ultrasound signals. Utmost emphasis is placed on user privacy and decentralized administration which makes this system unique from others proposed in the past. In the Cricket system, instead of a centralized database tracking users and devices spread across a building, each user or device has the option of announcing its presence/service to a map server which only then makes it known to other components in the vicinity. Cricket is also capable of working with various network technologies and can be deployed at a very cheap cost and with minimum effort. Much of the paper talks about effective localization techniques, and the chosen method shows promising experiment results in terms of precision, granularity and accuracy. The second paper introduces a similar system called RADAR which is also based on radio signals, but unlike Cricket is a location tracking system. It relies heavily on a pre-determined RF signal database which increases the cost of deployment significantly. The paper talks at length on the main two ways of creating this database - Empirical Method, and the Radio Propagation Model. The latter is relatively easier to implement as it is based on a propagation model that works well with the physical nature of the setting. However, the signal strength values it generates for the database are not as accurate as the ones generated by the Empirical Method, and it definitely lacks the precision and granularity provided by Cricket. Another huge disadvantage is that in RADAR, the database has to be built from scratch every time there is a change in the building layout, or if the base stations are moved. This adds an extra overhead in cases where such changes might be frequent. The third paper is slightly different from the other two in the sense that it proposes a low cost system for outdoor localization. This removes a lot of the problems that in-building systems have to take into account - more specifically the problems of physical barriers, multipaths etc. The design goals include a receiver-based system for scalability, and for ease of deployment - an ad hoc solution. The nodes in this system communicate with each other using energy-efficient, low-cost radio-frequency transceivers. The localization algorithm presented depends on the overlapping transmission range of neighboring nodes to approximate the location of a node. This coarse grained localization approach seems to work well in the initial tests, although a lot of things still need to be cleaned up for an effective implementation of the system. Finally, the last paper presents a slightly outdated system called Active Badge which tracks the staff in an office setting with the help of infrared signal emitting badges and sensors that are placed all around the host building. There is a designated master node that is connected to a server, and is responsible for collecting and processing information from all the sensors. Localization in this system is helped by the physical boundaries (walls) in the setting as infrared signals do not traverse through these boundaries like radio signals do. This property enables the sensors to accurately locate a person in any room of the building. All these localization systems give rise to an exciting world of opportunities, especially for mobile users/devices. The Cricket paper describes a scenario where an individual would be able to walk around with a mobile device (eg. a laptop) and use services like printers, fax-machines placed all over the building. Building "smart houses" is another possibility. Any home equipment like ovens, TV, washing machines can be hooked up with listeners and be controlled from a single location in the house. For outdoor localization, the third paper suggests examples such as tagging wild animals or birds to monitor their behavior, or migration patterns. There are numerous other ways that could make use of these localization systems. From tmroeder@CS.Cornell.EDU Thu Oct 3 09:30:05 2002 Received: from dhcp99-233.cs.cornell.edu (dhcp99-233.cs.cornell.edu [128.84.99.233]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g93DU4h25793 for ; Thu, 3 Oct 2002 09:30:04 -0400 (EDT) Received: (from tmroeder@localhost) by dhcp99-233.cs.cornell.edu (8.11.6/8.11.6) id g93DSLe05039; Thu, 3 Oct 2002 09:28:21 -0400 From: Thomas Roeder MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-ID: <15772.17909.99433.198030@dhcp99-233.cs.cornell.edu> Date: Thu, 3 Oct 2002 09:28:21 -0400 To: Emin Gun Sirer Subject: 615 PAPER #27 X-Mailer: VM 7.07 under Emacs 21.2.1 The Cricket protocol, part of the Oxygen project at MIT, uses ultrasound and RF to get an estimate of the object's position relative to a collection of beacons which must be set up very carefully. It is very cheap to construct, and is entirely listener-based. It thus respects the privacy of the user. It even allows the objects to get information on other objects via UDP if they have a way to communicate with these other objects independently. They actually have error bars on a graph. :-) This system is tailored to be used indoors. The RADAR protocol, which was proposed by a group from Microsoft Research (using FreeBSD in their simulations, interestingly enough :-) uses a collection of base stations and mobile stations in a two-pass system. First, information must be gathered about the space in an "off-line" mode and then the users can infer their positions correctly given that information and the beacons they receive. The researchers have also tried to factor in the orientation of the receiver with respect to the beacon into their calculations. The more estimates they have and measurements from the various beacons, the better they can do. This system is tailored to be used indoors. The GPS-less localization software is entirely meant to be used outdoors, and would not work in an indoor environment due to the various path effects and difficulties with their simple model for RF transmission. They are particularly interested in using this work for low power nodes which cannot afford the power costs to use GPS. They use connectivity almost as a mini-GPS system to compute their position with respect to a uniform grid of nodes. Given these systems, there are many possible applications that I could imagine. The first to come to mind is a classroom in which the professor has a class list associated with students' current position in the classroom (this would obviously have to be by the students' consent, given the nature of these protocols). This would be particularly useful in huge classes, where the professor would never know everyone's name otherwise. Given Cricket and its UDP capabilities, you could do a system of Find a Friend...if you both had some network connection as well as Cricket and were in the same building, you could allow each other to see the other's position in the building on the map. You could send this via some application or use the fact that Cricket can get location information directly from the location manager of another computer by UDP (although you'd still have to have some way to find and connect to this computer first). Given the GPS-less ideas for the outdoors, you could use sensors with limited mobility to automatically replace sensors that have died: each one could pass along its position to the others so that if it goes down, another sensor could be sent automatically to take its place, given the last position it was known to occupy. Given either of the indoor versions, you could have your handheld automatically request favorite services if they exist in a given location (this requires Intentional Naming to a degree). There are, I am sure, many other possible applications of these ideas, but these are the few that came to me quickly. From tmroeder@CS.Cornell.EDU Thu Oct 3 09:43:09 2002 Received: from dhcp99-233.cs.cornell.edu (dhcp99-233.cs.cornell.edu [128.84.99.233]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g93Dh9h28622 for ; Thu, 3 Oct 2002 09:43:09 -0400 (EDT) Received: (from tmroeder@localhost) by dhcp99-233.cs.cornell.edu (8.11.6/8.11.6) id g93DfPe05109; Thu, 3 Oct 2002 09:41:25 -0400 From: Thomas Roeder MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-ID: <15772.18693.282563.928106@dhcp99-233.cs.cornell.edu> Date: Thu, 3 Oct 2002 09:41:25 -0400 To: Emin Gun Sirer Subject: 615 PAPER #27 X-Mailer: VM 7.07 under Emacs 21.2.1 I forgot this paper in my readings: here's additional write-up ActiveBadge uses IR and emits a pulse every several seconds. It is entirely designed for indoor use. It increases and decreases the frequency of its pulses with respect to the ambient light that it senses, thus at night it is almost off. The information is relayed to a central server over wired Ethernet, and was used (at least in the context of the developers of the system) for tracking people so that phone calls can reach them correctly. It was also used to find people for other purposes, such as office meetings. I would suggest one other application in the context of the active badge system, and that is computer sessions following people around an office building. If I sit down at a computer that is not in use, the computer could notice who I am, and request my session without me having to explicitly type the request at the station. There are significant privacy and security issues with this system which remain to be addressed. From smw17@cornell.edu Thu Oct 3 10:23:20 2002 Received: from cornell.edu (cornell.edu [132.236.56.6]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g93ENKh06890 for ; Thu, 3 Oct 2002 10:23:20 -0400 (EDT) Received: from cornell.edu (syr-24-161-107-202.twcny.rr.com [24.161.107.202]) by cornell.edu (8.9.3/8.9.3) with ESMTP id KAA26197 for ; Thu, 3 Oct 2002 10:23:16 -0400 (EDT) Message-ID: <3D9C520A.909@cornell.edu> Date: Thu, 03 Oct 2002 10:19:54 -0400 From: Sean Welch User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.0; en-US; rv:0.9.4.1) Gecko/20020508 Netscape6/6.2.3 X-Accept-Language: en-us MIME-Version: 1.0 To: Emin Gun Sirer Subject: 615 PAPER 27 Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit Cricket - Cricket is a localization system for distributed nodes based on the propagation delay between RF carriers and ultrasonic sound wave propagation. Beacon nodes are placed in areas in which localization is desired, and each individual node determines the nearest beacon and the rough distance to the beacon. In order to simplify the detection, a slow RF frame is used to guarantee that the ultra-sonic beacon is contained within the RF frame. Cricket is primarily intended to locate the nearest beacon rather than the absolute location, and assuming that the beacon locations are properly selected good results can be obtained. Poor beacon placement can lead to significant errors due to inter-beacon interference. The entire process is performed at the reciever, which alleviates some concerns of location detection systems also operating as location tracking systems, perserving user privacy. RADAR - A fixed environment solution is presented, with testing performed in an office type setting. The idea here is to empirically determine the propagation characteristics within a given location, and use this empirical data to permit triangulation with known base station locations. The method shows results within 3 meters (50%) in indoor settings, a significant improvement over the strongest base station method. They note that orientation differences between calibration may in the worst case increase the localization error to about 5 meters. A less complex scheme is also presented, using the Wall Attenuation Factor model for signal propagation. The propogation model 50th percentile is 4.3m, compared to the 3m of the empirical method. GPS-less Localization - The authors first provide an overview of different localization methodologies, including timing-based schemes, signal strength schemes, an interesting scheme based on characterizing the nature of the multi-path distortion, and a directionality scheme such as the VOR/VORTAC aircraft navigation systems. They then present a method for short-range localization based on a spherical propagation model for the transmitted signal. They create a grid of reference points, each at a known fixed position. A node localizes itself by using the centroid of all nearby reference nodes to create its estimated position. In outdoor applications where the spherical propagation model is valid, they report 2m accuracy using this scheme. The assumed propagation model breaks down in indoor situations, and the authors report that due to this, their scheme is not feasible for indoor applications. Active Badge - Active badge is a simple predecessor to many of these schemes. It consists of an IR badge worn by an employee and a series of IR detectors spread throughout a building. The detectors are linked by a wired network into a central system that can then build a database of badge sightings by detectors, allowing people to search for an individual (call forwarding is the example used in the paper), or to see how many people use a given room. The Active Badge system is a very basic localization system, for a somewhat specific set of tasks. Potential Schemes with Localization a) Rapid/Harsh Environment Sensor Networks - concept - Enable the rapid deployment of lightweight sensor nodes, potentially in hostile or remote locations that make conventional deployments unattractive (some similarities to smart dust systems). - node dispersal would include a small fraction of higher functionality nodes if an uplink (i.e. - satillite) or long-range communication is required - Shortly after dispersal, relative positioning combined with absolute position references by the dispersors is used to create a pseudo-static routing scheme to achieve minimum power/maximum lifetime routes to the uplink nodes - Based on location information, directional antennas may also be attractive, both for their higher path gain at a given power and their lower emissions of useless RF power (security, noise, and power concerns) - Could also envision a homogeneous network with a queried response from an external source requiring intelligent routing during the query. b) Appliance Networks - Concept - Enable intelligent appliances and industrial systems capable of inter- system coordination for better resource use - example - Toaster Oven and Microwave on same electrical circuit. If both devices recognize the other and the potential to overload the circuit breaker, they could reduce power temporarily or schedule power use when other devices are less heavily used. c) Intelligent Resource Detection and Utilization - Concept - Provide meaningful interface to human users, such as 'print to closest printer' rather than 'print to device attached to node 172.22.5.233'. d) Movement Aware Routing - Concept - Use the location information to judge the movement rate, and to estimate when link breakage is probable. From here, schemes such as intelligent route invalidation and link forwarding/handoff can be implemented. - Pseudo-static routes - From the network information, provide a mechanism for nodes to identify and make efficient use of relatively stationary, stable routes. e) Adaptive Link Adjustment - Concept - Use geographic feedback and either directional or adjustible power systems to improve link coverage in sparse areas - Detect networks liable to partitioning and attempt to improve linkage to maintain connectivity - Node protection - Identify key routing nodes seperating potential network partitons. Adjust routing protocols to reduce unnecessary loads on key network nodes - Can be combined with power aware routing (especially for less mobile networks) to improve network power efficiency From ashieh@CS.Cornell.EDU Thu Oct 3 11:17:08 2002 Received: from zinger.cs.cornell.edu (zinger.cs.cornell.edu [128.84.96.55]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g93FH7h17917 for ; Thu, 3 Oct 2002 11:17:07 -0400 (EDT) Received: from localhost (ashieh@localhost) by zinger.cs.cornell.edu (8.11.3/8.11.3/C-3.2) with ESMTP id g93FH6403751 for ; Thu, 3 Oct 2002 11:17:06 -0400 (EDT) Date: Thu, 3 Oct 2002 11:17:06 -0400 (EDT) From: Alan Shieh To: Subject: 615 PAPER 27 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII * Cricket Cricket contributes a low-cost location system that supports decentralized setup & coordination and protects the anonymity of a mobile user (the mobile hardware is listen-only). Each owner of a space independently installs a beacon that identifies a particular space. Only beacons of adjacent spaces can interfere with each other. Cricket employs social solutions (e.g. reorienting beacons to avoid crosstalk) instead of more sophisticated technological solutions. The location information for each space is provided in isolation from that of any other space: thus, the user has to query a server associated with that space to learn its actual location on some map, or query a some local database. ** Shortcomings Potentially, a hostile beacon can advertise very attractive information, and encode signed timing information in the service name or address that it puts out. A query for this name or address then yields the location of the user. The user cannot make a query without ever approaching a beacon (because the computed name has an embedded signature and timestamp), and can only save old timing information (so the attacker can detect when a user is trying to mislead him). The user would have to engage in a counter-conspiracy (perhaps employing some sort of source-masking privacy protocol with co-conspirators) to send these malicious beacon names to other users in real-time to confuse the tracking software. Alternatively, beacons can be forced to be short, or signed with the private key of a CA; this however introduces a (slight) need for centralized control. A node could also detect a rapidly changing beacon and refuse to query for information. ** Possible extensions It's possible for a mobile node (optionally equipped with accelerometers and gyros) to infer a connectivity graph while the user is moving. Even without the motion detection hardware, one could construct enough connectivity information to apply a pathfinding algorithm and allow the user to navigate (possibly requiring local backtracking to find the movement direction corresponding to an edge in the connectivity graph, assuming no beacons go down). This provides a much more anonymous navigation system: the user need not transmit ANY queries for location information, and so beacons cannot perform some sort of directed attack to find location information of the user. See above in shortcomings. * RADAR RADAR investigates the use of 802.11 signal strength for finding locations in buildings with base-stations. Two models of operation were evaluated: an empirical mode and a simulation mode. In the empirical mode, signal strengths of different base-stations were sampled at various points on a floor of a building, at different orientations (since signal strength is highly directional). In the simulation mode, a radio propagation model was used along with a building layout (to determine intervening obstacles) to predict the signal strengths at various points and orientations. Signal strength of the 3 hearable base stations are combined with position into a tuple and are entered into a database. The current signal strength readings are then joined against this database, and the closest datapoints to the current reading are taken to infer some position. Orientation dependence was found to be a severe limiting factor for accuracy, since entries for different orientations are found in the same database, and so it's likely for a k-nearest query to find entries for the same position, but different orientations. The empirical mode was found to be superior to the simulation mode (see below for a possible way to level the playing field). Both approaches suffer from temporal variations in signal strength (e.g., different number of people in the building, different distribution of people, changing temperature or humidity). ** Shortcomings The system is not accurate enough to localize a user's position to a particular room in a building. ** Possible extensions Although not explicitly stated in this paper, RADAR can support anonymous location services. Adding a MEMS gyroscope and a few accelerometers would directly provide orientation information at low incremental power increase. This information would help disambiguate database lookups, and could potentially allow the analytic model to perform better than the empirical model. With the analytic model, a new database could be generated on the fly, for the current orientation, in a second or two. This query-dependent database would potentially provide much better spatial resolution, since the database is not poisoned with information from different orientations. With k base stations in the vicinity, it may be better to perform triangulation using k queries with k-1 signal strengths. Conceivably, the user's body is only strongly blocking at most one of the base stations at any time. * GPS-less Low Cost Outdoor Localization For Very Small Devices This paper presents a scheme in which reference nodes are placed in predefined locations in a grid. A mobile node then listens for beacons from the reference nodes, and computes the connection quality with each beacon, that is, how many of the expected beacons in a given time interval were actually heard. Each node above a certain threshold is then chosen as the closest neighbors, and the centroid between the reference nodes taken as the estimated position. This is an implicitly anonymous system. ** Shortcomings The authors argue that RF strength is highly sensitive to multipath issues, and so it should not be used for localization. However, the connectivity metric that they actually used is dependent on both signal strength and interference. The R/d analysis was somewhat sloppy. The authors could have directly computed the expected loss rate based on distance to determine whether adding more nodes would significantly change the relative connectivity metrics. ** Extensions Combine signal strength and collision detection. If two overlapping messages are received, and one survives due to FEC, while the other does not, we know that that the suriving has a higher signal strength, and in fact we know that it has a higher signal strength by at least some dB. This could be used to infer signal strength, or to define more localization regions. This would be useful if it is known that only 2 beacons caused the interference; we can bound the probability of higher # of interfering packets with some sort of randomized CBR beaconing. * Active Badge Active Badge employs a fixed IR receiver infrastructure in each room, and a mobile IR beacon placed on each user. The fixed receivers notify a central server that the user has entered a particular room. The server enters this information in a database. In the test application, this database was used for adaptive call routing; if a user was not at his/her desk, then the receptionist or PBX would redirect the call to a phone near his present location. ** Shortcomings A user must sacrifice anonymity to provide himself with location information. This system also requires extensive dedicated infrastructure, and is highly centralized. ** Extensions Since the active badge is such a simple technology and amenable to minaturization, a person could conceivably wear multiple badges at canonical points on his body (perhaps as part of a belt or shirt). A dense population of sample nodes within an area (federation of wireless sensors motes plugged into wall sockets) could thus determine fine-grain position and orientation information (perhaps taking into account directionality (if IR transmit strength is low) or reflection losses (if transmit strength is high)). Applications: - Location-indexed information retrieval. Information for the current space is automatically displayed on a PDA or wearable computer. One could use this to build a knowledge base for tourists or visitors, to augment an employee training program (e.g. pull up documentation for the local piece of equipment or manufacturing process associated with a location), to bring up the results of joining some personal database with the calendar in a PIM (time/location with affiliated documentation for a meeting or appointment), or to support an active map system. This application can require very fine granularity and for the mobile node to be aware of its location. However, using a location system to do this may be overkill, as a user is probably happy to manually click on a map (assuming they know where they are). - Support dynamic collaboration groups. Typically, information sharing in groups requires one to explicitly predefine some group of people who should know about a discussion. In a public discussion forum, this overhead may be rather excessive. A location system installed in a discussion area can detect the participants in a discussion and automatically record a collaboration group (and optionally, depending on privacy considerations, record information about the discussion itself). - Inventory/personnel management & tracking in a warehouse or store. - Help customers find an employee for assistance in a large store. - Shopping agent. A user specifies a shopping list (perhaps tagged with levels of confidentiality and priority). The location system affiliated with a store (or shopping center - in this case, provides some hierarchical access) provides a pointer to a database, which the agent joins with the shopping list and displays a summary. Depending on which stage the user is in his shopping experience which can be inferred from movement patterns by the mobile device itself without informing anyone else. E.g. car->parking lot->going into mall + early in the morning = just starting the trip, should display a high-level overview of how the user should accomplish his/her shopping. Going into a store provides more fine-grained information. Leaving the store/shopping area provides a reminder of forgotten items.) The agent can also hierarchically query servers for stores that have been previously visited and known to be in the same vicinity (perhaps a 1-2mile radius, join with some business GIS database) to provide feedback on relative pricing. In general, a location system provides more information for an agent's inference engine to determine what a user intends to do, thus requiring the user to provide less specific information about his/her actions to the agent. From xz56@cornell.edu Thu Oct 3 11:36:03 2002 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.10) with ESMTP id g93Fa2h22006 for ; Thu, 3 Oct 2002 11:36:02 -0400 (EDT) Received: from XIN (dhcp-ece-167.ece.cornell.edu [132.236.232.167]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with SMTP id LAA00500 for ; Thu, 3 Oct 2002 11:36:01 -0400 (EDT) Message-ID: <019d01c26af2$9320deb0$a7e8ec84@XIN> From: "Xin Zhang" To: "Emin Gun Sirer" Subject: 615 PAPER 27 Date: Thu, 3 Oct 2002 11:35:58 -0400 MIME-Version: 1.0 Content-Type: text/plain; charset="Windows-1252" Content-Transfer-Encoding: 7bit X-Priority: 3 X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook Express 6.00.2600.0000 X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2600.0000 Active Badge system was an early location-tracking (vs.location-supporting, concept introduced in Cricket later on) system. A badge worn by each user periodically sends a unique IR signal as request and fixed sensors relay these signal to the location manager which will provide accurate location information. The drawbacks are related to the using of IR frequency, uniqueness of signal to each user, active request by user and central manager. Since this system can provide accurate location information to users in a building-wide range, the services could be provided are tracking of each user by some administrator, producing active map and thus facilitating the access to services as printer, etc. by users and organizing the distribution of nodes by the manager. RADAR, different from "active badge system", is an RF-based location-tracking system. The use of RF signals has advantage in coverage and thus reducing the cost and providing data service at the same time. How it works? There are several BS's (Base Stations) in the building continuously sending signals. Each user receives these signals and sends the strength of them to some receivers which can calculate the location of the user either by matching it into its empirical data table or data calculated from the radio propagation model and send back the location info to users. Also four different matching algs were introduced: Random, strongest, MMSE and multiple nearest neighbors. Since it offers the same service as in "active badge", the applications facilitated by "active badge" can also be provided by this system. Cricket improved in the aspects of user-privacy by letting fixed beacons send periodic signal and users receive and calculate itself's location, lower load (beacons sending signal based on adjustable period), accuracy (using RF and ultrasonic sound to decide the nearest beacon). Since Cricket conserves user-privacy, the location is only self-awarded by user it self, so the applications aided by this service is only on user's side. Combined with active-map, it can decide what are the nearest servers near to it. GPS-less low cost outdoor localization system distinguishes from the other three system in that it is an out-door system. But it uses similar approach as that in Cricket though with the only difference that it uses pure RF (scalability is improved by getting rid of ultrasonic) and decides the location by signal strength (which cannot give a good result due to the adverse transmission conditions with multipath, fading, etc and connectivity. This location information offered to outdoor users is much cheaper and simpler than GPS and thus can be mounted on sensors. With this information, they can do more efficient routing (e.g. directed diffusion without construction the gradients) and also helpful in data processing in-network. The categorization and analysis in GPS-less paper on the localization is pretty good. From vrg3@cornell.edu Thu Oct 3 11:44:47 2002 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.10) with ESMTP id g93Filh24025 for ; Thu, 3 Oct 2002 11:44:47 -0400 (EDT) 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 LAA14975; Thu, 3 Oct 2002 11:44:45 -0400 (EDT) Date: Thu, 3 Oct 2002 11:44:45 -0400 (EDT) From: vrg3@cornell.edu X-Sender: vrg3@travelers.mail.cornell.edu To: egs@CS.Cornell.EDU Subject: 615 PAPER 27 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII These four papers present different schemes for allowing mobile nodes to determine their physical locations. The Active Badge system uses simple infrared beacons mounted on each mobile unit and a deployed network of permanently mounted infrared sensors. RADAR simply uses existing 802.11 wireless cards whose firmware reports signal strength to software; a model of signal propagation and the presence of multiple base stations allows a form of triangulation. Bulusu et al's localization scheme is also based on RF signal propagation but is designed for outdoor use. Cricket uses simultaneous RF and ultrasound beacons, and compares the time-of-flight. A mobile network whose nodes know their locations has potential. An example is the location-based scheme for alleviating the packet storm problem which we have examined. The Human-Computer Interaction lab here at Cornell has spent time working on a project at the Johnson museum which would allow visitors with properly configured PDAs to receive on-demand information about the particular pieces of art they were viewing. Other projects include a kind of virtual graffiti wall, where users could post messages which are bound to a physical location, viewed by other users who pass by the same area. With a cellular phone, it could sometimes be helpful to know about the nodes closest to you. There are times when you would like to be able to reach certain nodes to relay important information (like if you need to tell the Honda Accord in front of you that its right rear tire is flat). This would approximate the kind of connectivity achieved by the broadcast medium of CB radio. Localization also allows for the possibility of nodes navigating relative to other nodes. If you had a system of autonomous entities which could not use a GPS-type system, either due to cost or physical limitations, but could implement one of these localization techniques, they could still determine their positions and velocities, albeit at reduced precision. An example of such a system is an autonomous underwater vehicle navigating relative to floating beacons; GPS does not work underwater. From mvp9@cornell.edu Thu Oct 3 11:57:02 2002 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.10) with ESMTP id g93Fv2h26685 for ; Thu, 3 Oct 2002 11:57:02 -0400 (EDT) Received: from zoopark.cornell.edu (syr-24-58-46-186.twcny.rr.com [24.58.46.186]) by postoffice.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id LAA16619 for ; Thu, 3 Oct 2002 11:56:59 -0400 (EDT) Message-Id: <5.1.0.14.2.20021003115611.01a67fd8@postoffice.mail.cornell.edu> X-Sender: mvp9@postoffice.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Thu, 03 Oct 2002 11:57:00 -0400 To: egs@CS.Cornell.EDU From: mike polyakov Subject: 615 PAPER 27 Mime-Version: 1.0 Content-Type: text/html; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable The papers presented herein discuss the solutions to roughly the same problem: locating something mobile.  While in the first 3, the focus is to locate a computer or device, in the active badge system the goal is locating a person (wearing the badge).  Priorities of the projects differ, as do their success.  Cricket authors, for example, aimed to also preserve privacy and low-cost, while those were not explicitly goals for the others. 
Of the ones reviewed, Cricket appears most reasonable and successful.  Localization is completely separated from other services and protocols, configuration and management is minimal, and the accuracy (in the experiment) is virtually perfect.  Of course, there are downsides.  The number of beacons required is rather large  at least 2 at every open juncture of virtual spaces, so the cost and the maintenance effort adds up  and this is continuous, as opposed to the rare setup required for RADAR discussed below.  There is a question of interference from ultrasound sources that may be found in environments where localization services would be desired.  It would also be interesting to see how the 1 foot resolution would change under the presence of a lot of densely spaced interference, sort of the combination of positions 1 and 2 of their experiments, it=92s hard to believe it could maintain so few errors.
        RADAR, which is made to function in the same environment as Cricket but in a GPS-like fashion, performs far more poorly due to its relying solely on RF signal strength for calculating location.  Under both phases of operation, RADAR=92s accuracy is relatively low  there is only a chance that you=92ll be within 2-3 meters of the returned location.  The data gathering phase for the empirical model is extensive, although, arguably no more so than setting up the army of beacons that would be required to cover the same space in Cricket.  The increase in error from the use of the FAF propagation model is tolerable, depending on your application.  The signal servers can be reduced to simple transmitters and their low number is attractive (I=92m curious how one does triangulation with less than 3 points as they claim!).  As a side note, the comparison of their results to random in their graphs is not encouraging.
        The paper on outdoor localization without use of GPS presents a different scenario.  The algorithm is simple and comprehensible.  The drawback is the dependence on a large number of reference nodes, and the additional disadvantage that increases of granularity of positioning due to additional reference nodes quickly shrink, destroying the basis for their claim of arbitrary granularity.  The issue of initializing the reference nodes with a location is also to be considered, but it is not crucial.  Potential uses will be discussed below.
        Finally, Want et al. present the Active Badge Location System, which does exactly that  locates active badges within a building.  The badges communicate via IR beacons to sensors spread out through the building which then send their data to a central processing station.  There is little detail of the actual protocol or potential problems, but as an (apparently) successful run has been conducted, it seems to function sufficiently well for some applications.  Drawbacks including extensive wiring for the sensors and their configuration, as well as the vulnerability of IR to sunlight and its limited range.  Finally, as the authors point out, the issue of privacy is to be considered, but it directly contradicts the motivation of the system, and it turns out to be unimportant anyway.
        The systems presented offer support to a variety of services.  The Active badge system, which is focused on others locating the carrier of the badge, is best suited to redirecting unprompted information to a user  pages, telephone calls, emails, various notifications  and finding them by others  in hospitals and secure zones.  Its goal seems to be to alert the central station to a user=92s location, not necessarily nodes in the vicinity, although the functionality can be extended to that of the other systems discussed.  Cricket and RADAR have similar potential  finding services (printers, coke machines, bathrooms, ethernet sockets, etc), mapping, and things like having the lighting or air conditioning be sensitive to presence  so that in a building otherwise kept dark (at night) a person can walk through and have the light automatically turn on in their immediate vicinity  also a possible use for the badge system. 
The variety of services a device may wish to find or activate is endless, but an additional use Cricket=92s accuracy allows it, is for guiding autonomous robots.  In the near future  or even now  a robot, say a mail carrier, can ride around the building, using accurate maps to guide itself through halls and possibly even door ways.  A similar situation might be envisioned for Bulusu et al=92s outdoor system.  Although, there the focus is more on something like sensor nets; perhaps monitoring animal movements in a zoo?
From mtp22@cornell.edu Thu Oct 3 11:58:39 2002 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.10) with ESMTP id g93Fwdh26947 for ; Thu, 3 Oct 2002 11:58:39 -0400 (EDT) Received: from narnia (syr-24-58-57-15.twcny.rr.com [24.58.57.15]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with SMTP id LAA02519 for ; Thu, 3 Oct 2002 11:58:37 -0400 (EDT) Content-Type: text/plain; charset="iso-8859-1" From: Matt Piotrowski Reply-To: mtp22@cornell.edu To: egs@CS.Cornell.EDU Subject: 615 Paper 27 Date: Thu, 3 Oct 2002 11:58:50 -0400 X-Mailer: KMail [version 1.2] MIME-Version: 1.0 Message-Id: <02100311585003.00770@narnia> Content-Transfer-Encoding: 8bit The goal of active badge, radar, cricket, and GPS-less low-cost outdoor localization (GPSL) is to let nodes know where they are in a network. With the exception of GPSL, all of these papers discuss such localization inside buildings. Active badge accomplishes this by attaching a badge to each node participating in the network; this badge transmit a unique ID via infrared to a receiver in the room. The location of the node is then associated with that receiver, which communicates this through a wired network. Radar accomplishes localization through RF signals. The strength of the RF signal is used to estimate the distance between a node and a receiver. This estimate is sent to a central database where the node's location is determined by triangulation. Cricket accomplishes localization using a set of beacons which advertise their location to nodes around them. The nodes can choose to receive this information and use a combination of RF and ultrasound to figure out how far they are from the beacon. GPSL accomplishes localization using RF and distinguishing certain nodes to be reference points. The reference points beacon periodically and other nodes in the network use a connectivity metric to determine where they are. One service that could be provided using this technology is maps. A node could say, "I am here at x", please give me the map for this location. Another service is room-based control of media devices. A node could transmit a control message to a media device, such as a TV, and say, "turn volume up, room x", where x is the room that the node knows it's in because of the localization technology. Also, the TV would know it's in room 2 and so it wouldn't accept conflicting "turn volume down, room y" messages. The node could then easily move to another room and control a completely different set of devices. Another service could be a store map. You could imagine someone in a store asking where something is to a computer and the computer responding based on localization data from that department. From adam@graphics.cornell.edu Thu Oct 3 12:04:04 2002 Received: from bach.graphics.cornell.edu (bach.graphics.cornell.edu [128.84.247.50]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g93G44h28034 for ; Thu, 3 Oct 2002 12:04:04 -0400 (EDT) Received: from envy.graphics.cornell.edu (envy.graphics.cornell.edu [128.84.247.206]) by bach.graphics.cornell.edu (8.12.1/8.12.1) with ESMTP id g93G3x0k044539 for ; Thu, 3 Oct 2002 12:03:59 -0400 (EDT) Date: Thu, 3 Oct 2002 12:03:53 -0400 (EDT) From: Adam Kravetz To: egs@CS.Cornell.EDU Subject: 615 PAPER 27 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Cricket: The cricket paper presents one of many ways to work on location-aware technology, but does it in a different way. A cricket is simply a beacon that "chirps" or gives off an identification string, one which could include where to get further info, or just simply be a pointer into a database. This is not a new idea, and has been tryed using GPS data, Active Badge, and Triangulation of Cellular or 802.11 signals. First the cricket team realizes the limitations of the RF type technologies and try to make there implementation more robust (although they note that this may also have limitations) by using ultrasonic pulses coupled w/ RF frequencies. By producing two signals that propogate at different speeds (RF at C and Ultrasonic at @ 1 m/s) the receiver can take the difference and determine location. Techinical details aside however the basis for the cricket is to provide cheap, easy to deploy "room size" location sensitive granularity. It does provide this and can have many advantages, it seems to work well and could certainly be improved to work even better (integration w/ 802.11 or other infrastructure). RADAR: Same premise as cricket, but instead of passive "beaconing" from locations, determine where people are instead of letting them "find there way" as w/ cricket. This poses some ethical questions as well as being more intrusive and more closely parallels the "big brother is watching you" sentiments of mobility, location-aware tech than a more passive system like cricket does. The technical details boil down to having a number of base stations deployed that try to pick up signals from an RoamAbout NIC and determine position by signal attenuation. GPS-Less: This paper deals w/ again the same topic, but in an outdoor fashion. It has the basic goals of being low energy, cost, adaptive, and ad-hoc. They use RF based signalling, which IMHO isn't the best, but could be coupled w/ other info (like cricket does) to be more robust. The experimental results of this tech show that while it is feasible the cricket seems to be a better option since it has better results, and although isn't high strength, could be extended to be used outside. These techs in general pose many new questions. There are of course the ethical issues that go along w/ being able "track" people throughout a network. Further another set of issues arise based on location which is that the anonymity is lost, a freedom to do as you please for lack of repurcussions based on disassociation from physical being and online persona (that is why people have screen names disjoint from there own names). Ethics aside these technologies have the ability to provide us w/ massive amounts of "power" to be much smarter about the way we use computers and work. First ad-hoc networking algs can benefit greatly from location based information. Newer algs could be developed, much like the suggestion from the Broadcast Storms paper that could exploit this information. Routing could be seamless and more direct, convergence could be better in ad-hoc nets. Further movement could be tracked, predicted and pre-routed to the future destination (imagine one node moving across a field, and routing packets individually so they arrive via many different routes as the node traverses the field). Pro-active forward looking routing is much more possible w/ location information. Second information sharing based on locality has always been an issue, the ideas of "virtual signboards" are not new but could certainly be implemented in nicer fashion. The E-grafitti project from the HCI lab at cornell (http://www.hci.cornell.edu publication is: (E-graffiti: Evaluation Real -World Use Of a Context-Aware System. Interacting With Computers: Special Issue on Universal Usability) built a system a number of years ago w/ these goals in mind. The idea that your personal device could be used as a roving billboard, however is not new either and has the potential for exploitation. Localization could be used to share resources (processing power, bandwidth, etc) in a way that hasn't been thought of before. Imagine that you want to run 47 processes on your handheld but can't. If you could farm out some of the processes to willing, local people (finding these people via a 2-way localized network) then you could use otherwise unused resources to improve efficiency. Further you could easily have "dynamic serving" happening based on requests. Imagine a webpage being served by one node in an ad-hoc net w/ localization info. If there have been a number of scattered requests across a network, then high demand from this server later, the previous requests (based on location) can work as mirrors, providing their data instead of contacting the farther off server, saving net congestion. From ag75@cornell.edu Thu Oct 3 12:06:05 2002 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.10) with ESMTP id g93G65h28275 for ; Thu, 3 Oct 2002 12:06:05 -0400 (EDT) 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 MAA01353 for ; Thu, 3 Oct 2002 12:06:02 -0400 (EDT) Date: Thu, 3 Oct 2002 12:06:00 -0400 (EDT) From: ag75@cornell.edu X-Sender: ag75@travelers.mail.cornell.edu To: egs@CS.Cornell.EDU Subject: 615 PAPER 27 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII In this week's papers we are presented with 4 systems designed to provide location information. Some of these systems are designed to be used inside buildings. These systems use either IR or RF signals and can't use GPS because it doesn't work inside buildings. One of the systems is designed to be used in outdoor environments. This systems uses RF signals and doesn't use GPS because of such considerations as size, cost and power requirements of GPS. Most authors agreed that considerations such as user privacy, decentralized administration, low cost, ease of deployment, scalability, granularity, size and power requirements of the devices are very important when designing a location information system. Each of the system that are presented deals satisfactory with at least some of these considerations. Throughout their papers the authors give many different uses for these location information systems. Several in-building location-dependent applications such as in-building active maps and device control can be developed using location information systems. The uses of active maps are pretty obvious, and device control can be used to provide services such as MP3 streaming and printing. Another application of these systems is finding a book in the library, though this would require more fine-grained information. Yet another application is improving telephone interfaces. Features, such as call forwarding, can be automated using location information. Along these lines, things such as logging and access control can be implemented for security and other purposes. Several outdoor uses of location information are also presented. Applications include environmental monitoring in the water and soil, and tagging animals for research purposes. From pj39@cornell.edu Thu Oct 3 12:08:44 2002 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.10) with ESMTP id g93G8ih29175 for ; Thu, 3 Oct 2002 12:08:44 -0400 (EDT) Received: by travelers.mail.cornell.edu (8.9.3/8.9.3) id MAA03363; Thu, 3 Oct 2002 12:08:41 -0400 (EDT) Date: Thu, 3 Oct 2002 12:08:41 -0400 (EDT) From: pj39@cornell.edu Message-Id: <200210031608.MAA03363@travelers.mail.cornell.edu> To: egs@CS.Cornell.EDU Errors-To: pj39@cornell.edu Reply-To: pj39@cornell.edu MIME-Version: 1.0 Content-Type: text/plain Content-Transfer-Encoding: 7bit X-Mailer: IMP/PHP3 Imap webMail Program 2.0.9 Sender: pj39@cornell.edu X-Originating-IP: 128.84.223.189 Subject: 615 PAPER 27 The Cricket Location-Support System RADAR: An In-Building RF-Based User Location and Tracking System GPS-less Low Cost Outdoor Localization For Very Small Devices The Active Badge Location System The above four paper focusses on determining the location of devices. The Cricket, RADAR and Active Badge is designed to have an applicaton space inside a builing whereas GPS is mean to be outdoor. The design goals of Cricket assumes user privacy, decentralized administration, network hetoerogenity, low cost ($10) and portion-of-a-room granularity. It uses a combination of Radio Frequency (RF) and ultrasound signals to provide a location-support service to users and applications. Beacons are monunted on walls and ceilings throughout a building, and the mobile nodes analyze information from that is listens from beacons. With Cricket several-location dependent applications such as in-builidng active maps and device control can be developed. RADAR uses radio-frequency for loacating and tracking users inside a building. It records and processes signal strengths at multiple base stations positioned at overlapping coverage area. RADAR combines empirical measurements with signal propagation modeling to determine user location and thereby location aware services and applications. RADAR can be used to develop in-building applications to locate users. GPS less uses RF communication capability to find location speicific information for very small, low cost outdoor devices. Here nodes localize themselves to the centroid of their proximate reference points using a connectivity metric. It is receiver based, adaptive and the granularity of reference points available. It requires no coordination amongst reference points. Simulation results suggest that granularity of localization can be further improved by increasing the overlap of reference points. GPS less can be used for localization of non GPS enabled outdoor nodes. Active badge system is an in building location system. Its application has been envisioned in office to assist the PBX operator/receptionist to locate the employees. It uses a tag in the form of Active Badge which emits a unique code every 15 seconds (beacon). These beacons are picked up by network sensors spread across the building. There is also a master sensor tht polls the sensors for badge sightings. Cricket is suitable of localization of persons within and organization. Its possible use is integration with PBX or telephone so that users can receive calls while they are mobile. From liuhz@CS.Cornell.EDU Thu Oct 3 12:44:59 2002 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.10) with ESMTP id g93Giwh07134 for ; Thu, 3 Oct 2002 12:44:58 -0400 (EDT) content-class: urn:content-classes:message Subject: 615 PAPER 27 MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" X-MimeOLE: Produced By Microsoft Exchange V6.0.5762.3 Date: Thu, 3 Oct 2002 12:44:58 -0400 Message-ID: <706871B20764CD449DB0E8E3D81C4D4302CEE63F@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 27 Thread-Index: AcJq/DWYiZ4r0ZfAQSivFFPpy0AYDA== From: "Hongzhou Liu" To: "Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from base64 to 8bit by sundial.cs.cornell.edu id g93Giwh07134 These three papers introduce three localization algorithms for different environment: RADAR, Cricket, and GPS-less low cost outdoor localization for very small devices(we can call it miniGPS). Among them RADAR and cricket are designed for in-building context, while miniGPS can only be used in outdoor unconstrained environments. Cricket is a location-support system focusing on user privacy and decentralized administration. Small devices called beacon are placed all over the building and transmit both RF and ultrasonic signals periodically. The receiver, when receive these signals, estimates its location according to the difference between the time-of-flight of RF and ultrasonic . The RADAR system implements a location service utilizing the information obtained from an already existing RF data network. It uses the RF signal strength as an indicator of the distance between a transmitter and a receiver. The system builds a data base of RF signal strength at a set of fixed position during the off-line phase. During real-time operation, the measured signal strength is sent to a central computer, which examices the signal-strength database and find the best match for the current transmitter position. The miniGPS system is based an idealized radio mode. It estimates proximity information accordint to simple connectivity metrics. Some reference points are positioned throughout the investigated area. A small device is placed at each reference point and transmits RF signals periodically. The receiver infers its proximity to a set of reference points according to its receiving rate of signals from these reference points. MiniGPS is still a immature system. It's vulnerable to noise. Havint these localization systems, it's possible to build an interesting class of location-aware services, such as printing to the nearest printer, navigating through a building, outdoor biological and environmental monitoring etc. In the cricket paper, it introduces an application called Floorplan that uses Cricket and a map server to present a location-dependent "active" map to the user. Floorplan can display the user's location and dynamically update the services available in the vincity to him when he moves. Recall in previous papers. We discussed broadcast storm and battery conservation. If we can know the exact position of each node in the ad hoc network, then we can reduce the trasmission range of each node to the minimun possible value(still able to reach next hop) to save power consumption and eliminate all the unnecessay broadcast. We can also use location information of hosts to aid ad hoc routing. For example, in cluster-based routing protocols, we can put nodes that are near to each other geographically into one cluster, thus make clustering more reasonable. From linga@CS.Cornell.EDU Thu Oct 3 12:47:34 2002 Received: from snoball.cs.cornell.edu (snoball.cs.cornell.edu [128.84.96.54]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g93GlXh07954 for ; Thu, 3 Oct 2002 12:47:33 -0400 (EDT) Received: from localhost (linga@localhost) by snoball.cs.cornell.edu (8.11.3/8.11.3/C-3.2) with ESMTP id g93GlXa05506 for ; Thu, 3 Oct 2002 12:47:33 -0400 (EDT) Date: Thu, 3 Oct 2002 12:47:33 -0400 (EDT) From: Prakash Linga To: Emin Gun Sirer Subject: 615 PAPER 27 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII The Cricket Location-Support System ----------------------------------- This is a decentralized, low cost location-support system for inbuiliding, mobile and location-dependent applications. Goals include: decentralized control, low cost, user privacy, room-size granularity. Main idea is to allow for users/services to learn their location; services use this to advertise their location to a resource discovery serive (INS, IETF); users learn about the services in their area (using an active map sent from a map server application) and hence interact with the services. A location-support system instead of location-tracking system is used to support decentralized control, respect user privacy and allow for accommodating multiple resource discovery services. A beacon advertises the space it is responsible for by transmitting signals. Any node is attached with a listener so that it can intercept the signals from the nearby beacon(s) and deduce the location. A combination of RF and ultrasound signals are used and the user infers the distance from the beacon by measuring the time of flight of the signals (time difference between the first bit of RF and the ultrasound signal). Authors use randomization to reduce interference (instead of a heavy weight solution like carrier-sense-style-channel access protocol.) Beacon transmission times are chosen uniformly at random from an interval [r1, r2]. Different interference scenarios are discussed and in each case a practical solution is proposed. For better acuracy listeners collect muliple samples and use an inference alrogithm to deduce the location. Three inference algorithms have been investigated: Majority, MinMean, MinMode. Experiments show that MinMode works the best. A number of resource discovery facilities can be used with Cricket. A number of applications can be run over cricket- ex: Floorplan is an active map navigation utility using cricket and a map server to provide a location dependent active map to the user. Pros: Decentralized, low cost (each cricket device costs < 10$), respects user privacy, works with room-sized granularity. Cricket is therefore a good location-support system for implementing location-dependent applications. Cons: Experimental results very limited. No experiments justifying some claims like scalability. RADAR ----- This is a RF based location-tracking system for in-builiding, mobile location-dependent applications. Prior systems were mostly based on IR technology and so have serious limitations: does not work well in presence of sunlight, high costs and poor scalability because of limited range of IR. So the authors propose using RF based wireless network. The protocol has two phases: the off-line phase where data collection is done; a real-time phase wherein the user location is inferred. Signal strength(SS) is used as a means to infer user location. In both the phases, tuples of the form (t, bs, ss) where t is the timestamp of the base station bs and ss is the signal strength are collected by the base station. In addition, in the data collection phase the base station also records the location and direction of the user sending the signal (say, the user indicates his/her current location by clicking on a map of the area). The collected data is processed (to obtain attributes like mean, median and standard deviation) and this processed data is used in future to determine a match. Now during the real-time phase, using a set of measurements at different base stations we infer the location of the user using triangulation. Experimental results show that this emperical method is better than other strategies like random selection of a base station or strongest base station selection. Averaging on the data set containing the max signal strength over 2-4 neighbors improves the location estimation a little bit. Authors also propose the radio propagation model as an alternative to the emperical method. Here a model of indoor signal propagation is used to generate some theoretical data sets and these are used for comparision. WAF propagation works the best and is cost effective. Pros: One of the first approaches to use RF signals and hence come up with a more robust location-tracking system (compared to those using IR technology). Emperical method proposed in the paper can be used to estimate the location of the user to a high degree of accuracy but the data set needs to be large enough with samples corresponding to different user orientations. Cons: This is not scalable and is a centralized solution. User privacy is not respected and is not a cost-effective solution. Also emperical methods accuracy is very dependent on the data set collected and the math models need not always do a good job. GPS-less -------- Authors propose a light-weight solution for localization in an outdoor environment using a simple connectivity-metric method. Desgin goals: RF-based, Receiver-based (for scalability), ad hoc, low energy, adaptive fidelity (adapt to available granularity). Classification of localization methods: fine-grained (timing-based, signal-strength-based, signal-pattern-matching-based, directionality-based); course-grained. An idealized radio model is considered (Assumptions: Perfect spherical radio propagation, identical transmission range for all radios). To decide its position, each node listens for a fixed time interval t and during this interval collects all the beacon signals received from different reference points. From this data, it infers a collection of reference points for which the connectivity-metrics exceed a certain threshold. Now the location of the node approximated with the centroid of these reference points. Authors show some initial results which show that this model works well for outdoor unconstrained environments. Pros: Low cost solution which is apparently scalable, adhoc and adaptive. Uses a simple idealistic model which appears to approximate the real scenario for outdoor unconstrained environments. Cons: Experimental results not adequate to conclude that their simplistic model is good enuogh and their approach does work in practise. Active Badges ------------- This is a location-tracking system using IR signals. Authors claim that IR technology is already exploited commercially and is inexpensive and hence an ideal choice for Active Badges. In this scheme each node is associated with a badge which transmits a unique IR signal periodically (say every 10 seconds). There are sensors at various points (say at the ceilings of the room/building) which detect these IR signals and forwards this information to a location manager software. This software informs requesting services and applications of the same. The users location is identified with the receiver that detects its existence. Walls of the room act as natural barriers and hence helps sensors within a room to detect users in the room. Pros: Looks like one of the first papers on a location-tracking system to enable location-dependent applications. Cons: IR technology has too many drawbacks: limited range; sunlight causes problems; high costs. Also a lot of infrastructure is required in terms up wiring up all the sensors networks. New applications and services enabled ------------------------------------- Location-tracking or location-support sytems have enabled many exiting location-dependent services and applications. Most important services enabled are are the active maps services and the resource discovery services. Given that we know the location we could get the map of the current location and the services/resources available at this location. This enables context-aware applications which can use the location information for better cooperation between devices and also to choose the best of the available resources for efficient operation. One very interesting application in this area is that of using robots. Robots are users which can learn the services available in this location, the map of the location, obstacles and navigational aids. This can make help move some of the functionality away from the robot and hence simplify the design of the robot (we no longer need the robot to decide which route to take, detect printers, etc) and could drastically improve their functionality. GPS is now being extensively used for navigational support (in cars for example). Localization also enables new routing strategies and new ways of reducing power consumption in multi-hop wireless networks (using the GPS-less outdoor solution). Also if we have a dynamic sensor network (with mobile sensors) we could detect the location of the sensor and associated the collected data with the current location of the sensor. From yao@CS.Cornell.EDU Thu Oct 3 12:53:50 2002 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.10) with ESMTP id g93Groh09057 for ; Thu, 3 Oct 2002 12:53:50 -0400 (EDT) content-class: urn:content-classes:message Subject: 615 PAPER 27 MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" X-MimeOLE: Produced By Microsoft Exchange V6.0.5762.3 Date: Thu, 3 Oct 2002 12:53:50 -0400 Message-ID: <706871B20764CD449DB0E8E3D81C4D4302ED4C41@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 27 Thread-Index: AcJq/XKw7Fnu2bY7RXu2J5BanCGj6Q== From: "Yong Yao" To: "Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from base64 to 8bit by sundial.cs.cornell.edu id g93Groh09057 Summarization: The three topology & location services papers presents different methodologies to acquire location information for mobile nodes in ad-hoc network. Considering pracitcal limitations, such as the small size, form factor, cost and power constraints, they preclude to rely on GPS on all nodes to get location information. A distribute and reliable kind of location service is expected. The Cricket paper proposes how to combine RF and ultrasound signals to infer the nearest reference point of a node. The position of the node is then set as same as the location of that point. Such method is preferred in scenarios like office buildings and homes, where the topology information of the environment is available, and only approximate estimation of the location is required, for example, in the room granularity. The second paper assumes idealized radio model, and proposes a localized algorithm to estimate the node's location from nearby reference points. A node keeps monitoring beacon messages from its neighbor reference points, and sets its location as the centroid of them. It also disucsses the effects of the deployment of reference nodes on the accuracy. The RADAR paper explains how to obtain the location information from the RF signal strength, which acts as an indicator of the distance between a transmitter and a receiver. Usually, the RF signal strength is sent to a central computer to find out the transmitter position. It uses a triangular based approach to compute the location of the moving node. New services: Location infromation is critical to many upper applications at different layers. Some of them are listed below, 1. Geographical routing. With location information available at individual node, geographical routing protocol can be implemented in ad-hoc network even with high mobility. Since a node simply forwards a packet to its neighbor, which is closest to the destination, or follows some special rules to recover from the 'dead end', the cost to maintain a route is minimal. If the density of the network is high, the spatio information acts as a good indicator of the direction to the destination. Several geographical routing algorithms have been proposed recently, like GPSR, and proved very efficient. 2. Data centric storage. For a large scale sensor network, which generates huge amount of information continuously at sensor nodes, it is better to store data in-network in a distributed manner, instead of sending everything back to the server, since in-network processing or on-demand query processing usually reduce data size significantly. One possibility to support such data centric storage scheme is to hash data to different locations in network according to their types. There might or might not be a node in the exact position, but the routing protocol can deliver the data packet to the nearest node to the exact position. To get data of a special type, the sever simply forwards a request to the node cloest to the hashed postion of the data type. 3. Build a virtual model of the physical world. Computers can help people to explore the physical world, and recent technology advanes have enabled processing or representing large amount of data. But it is not a trivial problem of how to obtain these data from the outside. One solution is to deploy large amount of nodes to monitor the physical world and collect data from them to central computers for processing. Many applications exist, like monitoring and tracking moving objects. However, such data are usually useless unless their positions are also known, that is why the location service is so important to these applications. 4. A more detailed example could be a map service. Imagine people are wandering inside a building, equipped with a small PDA. The PDA can locate its position from other reference points pre-installed in the building, and display a map to the user. The position of the user is highlighted to help the user to find out where he is and which attractions are around him. Such touring system is especially useful in office buildings, theatres, museums and parks. Yong From aed13@cornell.edu Thu Oct 3 13:08:38 2002 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.10) with ESMTP id g93H8bh12163 for ; Thu, 3 Oct 2002 13:08:37 -0400 (EDT) Received: from andyd-laptop.cornell.edu (dhcp-576.rover.cornell.edu [128.84.26.64]) by postoffice.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id NAA23334 for ; Thu, 3 Oct 2002 13:08:35 -0400 (EDT) Message-Id: <5.1.0.14.2.20021003122647.048ebd60@postoffice.mail.cornell.edu> X-Sender: aed13@postoffice.mail.cornell.edu X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Thu, 03 Oct 2002 13:08:40 -0400 To: egs@CS.Cornell.EDU From: "Andrew E. Davis" Subject: 615 PAPER27 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed The paper "The Cricket Location-Support System" introduces the concept of a low-cost indoor location support system. Location support differs from location tracking in that each node knows it's relative location but the location is not known by a centralized infrastructure, thereby maintaining privacy. Cricket developed a system of low cost beacons and listeners utilizing radio frequency messages and ultrasonic pulses to identify a listeners nearest location beacon. Distance from each beacon is calculated from the difference in time between the rf message and ultrasonic pulse. The paper describes the development of the cricket implementation and interface with intentional naming system to provide discovery services. The paper "RADAR: An In-Building RF-based User Location and Tracking System" takes the reverse approach and develops a location tracking service for indoor use. The paper uses radio frequency triangulation from multiple receiving base stations to calculate the location. The paper concludes that this methodology is capable of tracking users within 2 to 3 meters despite RF interference issues The paper "GPS-less Low Cost Outdoor Localization for Very Small Devices" focuses on the localization problem of wireless sensor networks with the hope of re-using existing radio frequency communication to determine location. The paper focuses on the establishment of a set an overlapping set of reference points, and uses signal strength and connectivity to interpolate location. The paper evaluates the the system with 4 reference points and evaluates the accuracy at 121 points inside the grid. The paper shows a viable method for radio based location, given independent reference points, and points out a number of underlying(and re-occurring) problems of distributed ad-hoc rf systems. The last paper "Active Badge System" uses the concept of a location service to improve the services available in a PBX call routing system. The system utilizes existing infa-red technology to emit a unique sequence for a tenth of a second every 15 seconds. The location information is collected centrally to enable call routing, forwarding and direct intercom type paging. All 4 papers introduce location based systems designed for specific applications, either indoors, outdoors, sensory network, or call routing. The overall concept of a location service can be abstracted into two categories: location support service, and location tracking services which place different responsibilities on who knows the information. Application level services can be developed on-top of both services, and can be further abstracted by discovery services. From sc329@cornell.edu Thu Oct 3 13:19:32 2002 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.10) with ESMTP id g93HJVh14337 for ; Thu, 3 Oct 2002 13:19:31 -0400 (EDT) Received: from sangeeth.cornell.edu (syr-24-58-36-135.twcny.rr.com [24.58.36.135]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id NAA00706 for ; Thu, 3 Oct 2002 13:19:30 -0400 (EDT) Message-Id: <5.1.0.14.2.20021003131747.035b6870@postoffice2.mail.cornell.edu> X-Sender: sc329@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Thu, 03 Oct 2002 13:19:30 -0400 To: egs@CS.Cornell.EDU From: Sangeeth Chandrakumar Subject: 615 PAPER 27 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed Submitted by - Sangeeth Chandrakumar CRICKET presents a location-support system for in-building, mobile, location dependent applications. The main goals of the system were user privacy, decentralized administration, network heterogenity and low cost. The system uses a creative idea of transmitting a concurrent ultrasonic pulse along with each RF advertisement. The listener correlates them to each other, and estimates the distance from the base station by calculating the propogation delay between the two. The paper also presents three inference algorithms to calculate the distance: majority, MinMean and MinMode, of which MinMode seems to perform the best among the three. However, the placement and configuration of beacons have a significant effect on the interference of the signals. RADAR is another in-building user location and tracking system, that is based purely on RF signal strength. The system consists of mobile hosts that broadcast beacons to base stations. RADAR uses signal strength gatheres at multiple receiver locations to triangulate the position of the mobile node. The authors present results based upon an emperical evaluation and a random method and strongest base station method. The emperical method gives the best results. This is however aided by an offline process which builds a data base of signal strength at a set of fixed receivers. This data base is then looked up for accurate location discovery. With the empirical method, the system tracks users to a proximity of 3 metres. In the third paper, the authors review various localization techniques and evaluate the effectiveness of a simple connectivity-metric method for localization in outdoor environments that make use of inherent RF communicaton capabilities of the device. The paper proposes a method for coarse grained localization based on an idealized radio model and also describes a simple implementation of the model. In this model, they use outdoor radio signal propagation model to measure the signal strength of received beacon signals to estimate distance. Thier calculation show that, the granularity of the distance can eb improved by increasing the overlap range of the reference points. The one drawback of all these paper is that the experiments are all based on a single user, they do not explain how the systems perform with multiple users. Services enabled by such systems: - Cricket seems very promising in that it is decentralized and has user privacy. With the concept of a virtual space, a user based on its location, can discover and use variety of services. - User location systems can have many applications. To a user shopping in a mall, tracking the location of the user would help in sending out coupons and other advertisements to his device. Moreover things like shopping patterns etc could be studied for future customization of services. From vivi@CS.Cornell.EDU Thu Oct 3 21:27:51 2002 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.10) with ESMTP id g941Rph07410 for ; Thu, 3 Oct 2002 21:27:51 -0400 (EDT) content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Subject: 615paper27 X-MimeOLE: Produced By Microsoft Exchange V6.0.5762.3 Date: Thu, 3 Oct 2002 21:27:50 -0400 Message-ID: <47BCBC2A65D1D5478176F5615EA7976D11AF85@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615paper27 Thread-Index: AcJrRUFG0RcgZZ/3Tjy6Jg6f1fr23A== From: "Vivek Vishnumurthy" To: "Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id g941Rph07410 These papers discuss Location-Support and Location-Tracking Systems. A Location-Support system is one where a user wants to be aware of his/her current location, and the system supports this need. A Location-Tracking system is one where the system, to function, needs to be aware of the location of all users and the system is built to provide this functionality. Among the papers being discussed, Cricket and the "GPS-less ..." papers describe Location-Support systems, and RADAR and the Active Badge papers describe Location-Tracking systems. Except the "GPS-less" system, all the others are designed to work indoors. In Cricket, stationary Beacons transmit periodic RF packets immediately followed by an Ultrasonic pulse. When a receiver (mobile host) receives the RF packet, it waits for the subsequent ultrasonic pulse. It estimates its distance to the transmitter using the time gap between its reception of the RF and ultrasonic samples. This distance estimate is further used to determine which transmitter is the one closest to this receiver. Some features of Cricket are: inexpensive ("$10") components, decentralization, and privacy (nobody else knows about the location of a user). With Cricket, any user is aware of all the available services in the vicinity. (Information about services is contained in the Beacon signals). Thus a user, for example, can issue a request to print a document at the nearest printer, or find a shortest path to the nearest rest-room. RADAR is a RF based system where the mobile users transmit periodic RF signals and stationary receivers listen in on these signals. Location tracking is done using one of two methods : The Empirical method, or by using a Radio Propagation Model. In the empirical method (during the offline phase), signal strength samples from all distinct locations in the floor for the four different orientations(N,E,W,S) are collected and stored. During run-time, on receiving signals from a user, the user's position is estimated to be that pre-defined location whose (already stored) magnitude of the signals most closely matches that of the user. Though the Empirical approach gives very good estimates of the location of the user, there is a substantial cost of initialising the database. An alternate approach used utilises the Wall Attenuation Factor model to estimate the distance between the user and the receiver. This model takes into account the singal attenuation due to walls that block the line of sight between the user and the receiver. RADAR can be used in scenarios where access to certain parts of the building or the time of use of certain parts of the building is to be restricted based on the identity of the user. The "GPS-less" RF-based system utilises a very simple model to estimate user locations outdoors. There is a fixed number of transmitters, and the location of a user is estimated to be the centroid of the polygon formed by all transmitters whose signals are audible to the user. This model cannot be used indoors because of problems caused due to reflections. These systems enable location-determination to a reasonable accuracy. But all of these location estimates are restricted to 2 dimensions., ie., none of these give an estimate of the user's altitude, so these systems cannot be used to give a user the view of available facilities on other floors. Some of the services enabled by these systems: -- In hospitals with frequent emergency calls, location-tracking enables issue of specific calls to the personnel nearest to the emergency situation. -- Different levels(differing periods of access) of access to different parts of a building, based on the identity of the user. -- In a wireless network, where the destination of the path to be taken by a user is known, suggestion of potential routes that could minimize congestion (and therefore the possibility of a call being terminated) can be made possible. -- (As mentioned in the Active Badge paper) More efficient call handling in organizations is possible, because the receptionist has knowledge of the location of all empliyees, and the call can be directed to the exact location where the required employee is.