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 <egs@cs.cornell.edu>; 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 <B0050238850@mail.usadatanet.net> for <egs@cs.cornell.edu>;
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 <kwalsh@CS.Cornell.EDU>
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 <egs@cs.cornell.edu>; 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 <egs@cs.cornell.edu>; 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 <jsy6@cornell.edu>
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 <egs@cs.cornell.edu>; 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 <egs@cs.cornell.edu>; 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 <hs247@cornell.edu>
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 <egs@cs.cornell.edu>; 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 <egs@cs.cornell.edu>; 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: <E1C39121-D691-11D6-9E50-003065EE5F0A@cornell.edu>
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 <egs@cs.cornell.edu>; 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 <egs@cs.cornell.edu>; 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 <mr228@cornell.edu>
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 <egs@cs.cornell.edu>; 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 <egs@cs.cornell.edu>; 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 <bd39@cornell.edu>
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 <egs@popsrv.cs.cornell.edu>; 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" <shafat@CS.Cornell.EDU>
To: "Emin Gun Sirer" <egs@CS.Cornell.EDU>
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 <egs@CS.Cornell.EDU>; 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 <tmroeder@CS.Cornell.EDU>
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 <egs@CS.Cornell.EDU>
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 <egs@CS.Cornell.EDU>; 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 <tmroeder@CS.Cornell.EDU>
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 <egs@CS.Cornell.EDU>
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 <egs@CS.Cornell.EDU>; 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 <egs@CS.Cornell.EDU>; 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 <smw17@cornell.edu>
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 <egs@CS.Cornell.EDU>
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 <egs@cs.cornell.edu>; 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 <egs@cs.cornell.edu>; Thu, 3 Oct 2002 11:17:06 -0400 (EDT)
Date: Thu, 3 Oct 2002 11:17:06 -0400 (EDT)
From: Alan Shieh <ashieh@CS.Cornell.EDU>
To: <egs@CS.Cornell.EDU>
Subject: 615 PAPER 27
Message-ID: <Pine.GSO.4.33.0210031116110.24505-100000@zinger.cs.cornell.edu>
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 <egs@cs.cornell.edu>; 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 <egs@cs.cornell.edu>; Thu, 3 Oct 2002 11:36:01 -0400 (EDT)
Message-ID: <019d01c26af2$9320deb0$a7e8ec84@XIN>
From: "Xin Zhang" <xz56@cornell.edu>
To: "Emin Gun Sirer" <egs@CS.Cornell.EDU>
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 <egs@cs.cornell.edu>; 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: <Pine.SOL.3.91.1021003112411.12237A-100000@travelers.mail.cornell.edu>
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 <egs@cs.cornell.edu>; 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 <egs@cs.cornell.edu>; 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 <mvp9@cornell.edu>
Subject: 615 PAPER 27
Mime-Version: 1.0
Content-Type: text/html; charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
<html>
<font face=3D"Times New Roman, Times">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. <br>
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.<br>
<x-tab> </x-tab>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 <i>random</i> in their graphs is
not encouraging.<br>
<x-tab> </x-tab>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.<br>
<x-tab> </x-tab>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.<br>
<x-tab> </x-tab>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. <br>
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? </font></html>
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 <egs@cs.cornell.edu>; 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 <egs@cs.cornell.edu>; Thu, 3 Oct 2002 11:58:37 -0400 (EDT)
Content-Type: text/plain;
charset="iso-8859-1"
From: Matt Piotrowski <mtp22@cornell.edu>
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 <egs@cs.cornell.edu>; 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 <egs@cs.cornell.edu>; Thu, 3 Oct 2002 12:03:59 -0400 (EDT)
Date: Thu, 3 Oct 2002 12:03:53 -0400 (EDT)
From: Adam Kravetz <adam@graphics.cornell.edu>
To: egs@CS.Cornell.EDU
Subject: 615 PAPER 27
Message-ID: <Pine.BSF.4.44.0210031108380.17918-100000@envy.graphics.cornell.edu>
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 <egs@cs.cornell.edu>; 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 <egs@cs.cornell.edu>; 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: <Pine.SOL.3.91.1021003120450.29989A-100000@travelers.mail.cornell.edu>
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 <egs@cs.cornell.edu>; 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 <egs@popsrv.cs.cornell.edu>; 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" <liuhz@CS.Cornell.EDU>
To: "Gun Sirer" <egs@CS.Cornell.EDU>
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 <egs@sundial.cs.cornell.edu>; 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 <egs@snoball.cs.cornell.edu>; Thu, 3 Oct 2002 12:47:33 -0400 (EDT)
Date: Thu, 3 Oct 2002 12:47:33 -0400 (EDT)
From: Prakash Linga <linga@CS.Cornell.EDU>
To: Emin Gun Sirer <egs@CS.Cornell.EDU>
Subject: 615 PAPER 27
Message-ID: <Pine.GSO.4.33.0210031246490.5493-100000@snoball.cs.cornell.edu>
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 <egs@popsrv.cs.cornell.edu>; 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" <yao@CS.Cornell.EDU>
To: "Gun Sirer" <egs@CS.Cornell.EDU>
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 <egs@cs.cornell.edu>; 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 <egs@cs.cornell.edu>; 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" <aed13@cornell.edu>
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 <egs@cs.cornell.edu>; 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 <egs@cs.cornell.edu>; 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 <sc329@cornell.edu>
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 <egs@popsrv.cs.cornell.edu>; 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" <vivi@CS.Cornell.EDU>
To: "Gun Sirer" <egs@CS.Cornell.EDU>
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.