>>
YOUSSEF: Hello everyone and thank you for coming. I'm Moustafa Youssef from Egypt-Japan
University of Science and Technology. And today, I'm going to share with you our recent
result on the Location--Locationoid project where we target an accurate and energy-efficient
localization for GSM phones in general and for the Android platform in particular. So,
as we all know, location-based services has been gaining momentum recently, and application
rangees from finding the nearest pharmacy to, "My--are there any of my friends near
by now? Is there anyone interested in playing Chess now?" and so on. And the applications--the
list of applications keep increasing everyday. And there are commercial services that are
being offered in a larger scale like Google Latitude and Places, Facebook Places and they
keep coming everyday as I said. However, whenever we talk about localization for cell phone,
we need to keep in mind the energy consumption of the localization technology we are using,
because of course if your localization algorithms leads to depleting the battery very fast no
one will be willing to use it because energy is a very scarce resource on mobile phones.
Currently, the most commonly used and known technique for cell phone localization is the
GPS. However, GPS, as we all know, requires--is an energy hungry device. It require--it consumes
a lot of energy as I would go and define later in my talk today, and it doesn't work in every
place. So, for example, it doesn't work in the indoor environments, it doesn't work in
areas with tall buildings because it require line of sight to the satellites. And at the
same time, the recent applications, like navigation for example in Google phones, Android-based
phones, and Nokia phones and other popular phone--cell phones requires that you do your
localization very frequently. So, for example, in order to track your car you need to get
the GPS location very frequently and this can lead to killing the battery very fast
on your cell phone. So the problem we are trying to target is how to do localization
on cell phones with high accuracy but at the same time you should be able to do it in an
energy efficient manner so that you conserve the energy on your cell phone. So the Locationoid
project, what we--has different components. One of them, for example, is to perform GSM-based
localization using GSM network, not using GPS so that you are not using the energy hungry
GPS device. Another component is to do power-profiling for the different location components on the
Android OS so that we can quantify how much energy each component takes when it's running.
And once we do this profiling, we propose an energy efficient technique for obtaining
the cell phone location using the internal sensor. It is not using the GSM network nor
using the GPS, but depending on the internal sensors, mainly the accelerometer and the
compass. Finally, what we do in this project is that we propose a bar management layer
that runs on the--on top of the location provider in the Android system that can combine all
these components together to obtain, as I said, accurate and energy efficient localization
system. So in the rest of my talk, I have two main components. The first one is CellSense
where we try to obtain an accurate location estimate in GSM network using Probabilistic
RSSI's fingerprinting techniques. And in the second part, we propose GAC, which is a hybrid
GPS/Accelerometer/Compass technique, that uses the internal sensors to obtain the cell
phone location with minimum energy. And the final I will conclude my talk. So the first
part of my talk is about CellSense: A Probabilistic RSSI-based GSM Localization System. And if
we try to compare the GPS localization to GSM localization we can see that GPS is an
energy hungry device, doesn't work in all areas. As I said, it doesn't work indoors,
for example. And it is not available in all cell phones, it's just--it's only available
on high-end cell phones. On the other hand, GSM-based localization systems consumes minimal
energy or if any on top of the standard phone operation. Since your phone is already connected
to the GSM network and it's performing the standard GSM protocol, if you do localization
using the GSM signal you are consuming minimal amount of power in addition to the standard
GSM operation. So this is good. And it works everywhere GSM signal is available. So when
you are indoor you can obtain a GSM signal. Your localization technique can work in indoor
environments. And finally, GSM Standard, according to Wikipedia, is available on 80% to 85% of
the cell phones in the world. So again, you have a very large coverage in terms of devices.
So it's attractive. So if you focus on GSM-based localization, the current techniques that
are being deployed on cell phones or handset-based techniques are mainly Cell-ID based techniques
or RSSI-Based. By Cell-ID based, what we mean is that if you have your cell phone and you
can hear from a cell tower, the system estimates your location as the location of the cell
tower you are associated with. This provides an efficient way of obtaining your location.
However, it's a very coarse-grained accuracy because on the average, your accuracy will
be half of the coverage range of the cell tower. If you have more than one cell tower,
like here we have three cell towers, your estimated location will be the center of mass
of all the cell towers you can hear from. So, as we said, this provides an efficient
way of obtaining your location but it's a very coarse-grained accuracy. Recently, there
have been techniques that uses RSSI that receives the signals strength to estimate the cell
phone location. However, since RSSI is a very complex function of distance we can not use
a propagation model to estimate our location. Typically, what's being done is you use what
we call an RF fingerprint. An RF fingerprint is basically you tabulate the characteristics
of the signal strengths at different locations in the area of interest. So, for example,
if I want to do a cell phone localization in Mountain View I go to different locations
in Mountain View and collect signal strengths to information at different location and I
store this information in what we call an RF fingerprint. It's a database of signal
strengths characteristics at different locations. During an online phase, the tracking phase,
I am standing at an unknown location and I am receiving a signal strength's vector from
different cell towers and I'm trying to find the location in the fingerprints that I stored
in offline phase that is closest to where I received signal strengths. You can imagine
of course that using an RF fingerprint is a time-consuming process because you have
to do--go to different locations and stand there to collect the signal strengths. However,
this is typically done in a process that's called wardriving where you ride your car
and you have a cell phone with GPS that's connected to a computer and you are collecting
the location information and signal strengths information at the same time. And many of
the current commercial systems like StreetView under My Location from Google currently have
cars that roams the streets. So in order, for example, to get the pictures of the screen--as--the
streets in the Google Map application, and while you are doing this you can piggyback
your radio map construction in the same process. So it is not something that you had to do
particularly for localization, you can do it for other applications, too. So our wardriving
overhead is very minimal here, too. So currently, there are up to my knowledge, there are two
main techniques for using RSSI localization in GSM networks. One is deterministic fingerprinting.
And by this, what I mean is that the red dots represent the locations where you have the
fingerprint, so at each of these locations you stand and collect the signal strength's
characteristics. And here I assume you have only one cell tower, and the characteristics
that is stored in the radio map in deterministic techniques it's average signal is--signal
strength from this cell tower. So you stand at this location, you collect a number of
samples and you store in your radio map's average signal strengths you hear it from
this cell tower. The red dot represents an unknown location. You are currently standing
at this yellow dot and you want to know which of the red dots I am standing at currently.
So in order now to do that, deterministic fingerprinting techniques, what they do is
they calculate and locate the distance between the unknown location, the signal strengths
at the unknown location and the signal strengths stored in the radio map, and they return the
closest location in the radio map in terms of signal strengths as the estimated location.
So in this example, the closest location is -32 to -28 and it's returned it as your estimated
location. We believe that deterministic fingerprinting techniques provide coarse-grained accuracy
and that's why we proposed probabilistic techniques that can help enhance the accuracy of localization
as I will talk in the next part of my talk. There have been also proposals using probabilistic
techniques before what is called the Gaussian processes, and the idea here, their goal was
to reduce the fingerprint construction overheads. So instead of collecting 1,000 samples, for
example, you collect only 100 and then you try to interpolate these 100 samples to obtain
more samples. So you are reducing the number of points you need to collect and in order
to do that you assume a Gaussian process model and a propagation model to obtain the remaining
of the samples. You could imagine, in order to do these interpolations, your computation
overhead will be very high. And actually I believe that there is no actual reduction
in terms of the overhead. Why? Because in order to collect 100 samples you will need
to drive--do the wardriving anywhere, anyway. So if you will do the wardriving, it doesn't
matter if you collect 100 samples or 1,000 samples because you already drove the streets.
So it doesn't save much in terms of fingerprint size. So our approach is to use probabilistic
fingerprinting and hopefully we can obtain more accurate localization. And instead of
storing in the radio maps, the red dots, the average signal strengths, we need to store
the entire signal strengths histogram. So that gives you more information about the
signal strengths behavior. And using this extra information you can obtain more accurate
localization. However, the challenge here, in order to obtain a signal strengths histogram,
you need to stand at each location for a certain amount of time so that you can collect enough
samples to construct your histogram. So by this you are complicating the radio map construction
process because instead of driving continuously by your car you will have to stop at each
location. So this will increase your time significantly. So what we proposed in CellSense
is how can we reduce this overhead in terms of constructing the radio map. So I'll talk
about the two phases which is the offline phase, constructing the radio map, and then
the tracking phase, estimating the location once you have your radio map in place. So
in order to solve the overhead of the construction of the radio map, we use gridding approach.
So your area of interest is divided into a grid where each cell represents a virtual
location. So that--yeah, here the--again, the red dots represents the fingerprints location
where you collected these dots with continuous driving by the car--your car. You don't have
to stop at each point you continuously drive and based on your sample grid you will obtain
these red dots. However, we construct the histogram not for each dot but for each cell.
So we use the points within each cell to construct the histogram of this cell and then we use
the center of mass of this cell as the radio map location. So we reduce the problem, and
instead of using each red dot, you're using the grid cell. Of course, we have a barometer
here which is the grid cell length, how large your grid size should be. And by this barometer,
we can control the accuracy of the system and to trade it off with the scalability of
the system, because the larger your cell size, the less your grid--number of grid cells and,
hence, is the better your scalability but your accuracy will decrease. And we'll quantify
this later in the evaluation section. So this is the offline phase. What we do is we divide
the area into grid cell and construct a histogram for each cell. During the tracking phase,
you are standing at unknown location, L, and you will find--you are receiving a signal
strength vector of Q dimension, where Q is the number of cell towers you can hear. In
the GSM standards you can hear up to seven cell towers so each component represents the
signal strength from one sand bell from a cell tower. And what we want to find is the
location, L, in the radio maps that maximizes the probability of this, L giving the received
signal strength vector S. Using vision-inversion, you can find that the probability of L will
give you an S, equals the probability of--not equal--the locations that maximizes the probability
of L in given S is the same location that maximizes the probability of S to give an
L. And I remind you, the probability of S to give an L is what we store in the radio
map. So this information on the right-hand side can be obtained from the constructed
radio map. Assuming the cell towers are independent, you can obtain this by multiplying the individual
components. And in order to enhance our accuracy--the technique--the accuracy for our techniques
better, what we do is that we use more than one sample. So instead of using just one sample
before estimation, we use N sample at one time for estimation. You have more information
so you should expect to get a better accuracy, and in this case, you multiply the samples
and the cell towers. We have also approach to processing the step where we average--instead
of determining the most probable location, we return the average of the top K most probable
locations, and then we'd see also that this enhances our location estimation process.
So how well did we before? In order to test our systems--our system, we experimented with
two different test beds, one in the Smart Village in Cairo which is a typical rural
area, and another in Alexandria which is a typical urban area. We have two datasets;
one for testing and then an independent one for training for the areas--for the two different
test beds. And of course in the rural area, you can notice that the density of cell towers
is less than the density of cell towers in the urban area. This figure shows the median
error as we change the grid cell size. So as expected, as you increase the grid cell
size what happens is that your localization accuracy decreases since your size of the
grid size increase. However, if you look at 400 meter grid size, you can see the accuracy
is comparable to very low size grid sizes. So this is good news that you can have relatively
large cell sizes but at the same time you can obtain good accuracy. In terms of the
number of samples you use concurrently to estimate your location, you can see as we
increase the number of samples we use in the location estimates your accuracy trend is
enhancing. But at the same time, you're required to wait more samples in order to get these
N samples. So your latency will increase so you'll have a tradeoff between latency and
the accuracy of location estimation. This is the last barometer which is how many locations
you average as opposed to processing the steps when instead of returning the most probable
location. You return the K most probable--the average of the most K probable locations.
And again, as you see, as you increase the value of K, your accuracy--median error decreases
and your accuracy is enhanced. Comparing our technique to other techniques, we have here--we
compare our techniques in CellSense, which is the red curve, with the deterministic fingerprinting
techniques, the blue curve, and the Gaussian processes, the green curve, and with Google
My Location technique, which is the purple curve. For Google, what we do is that we send
the query, the cell tower to using the Google EDI to the servers and we obtain the location
estimates. The other two techniques, we implemented--as we implemented our system. We can see from
the figures, this is the CDF of distance error which gives you the probability of--that your
location will be less than a certain error. So you can see the median error at 0.5 for
our technique. It's better than the other techniques with at least 23.8%. This is--this
was in the rural areas. For the urban areas, we have even better accuracy. We can achieve
up to 86.4% better than any of the other techniques. This table summarizes the results in number--I'm
not sure if it's clear. In terms of running the time, we are slightly more than the determined
estimating techniques of probalistiic printing techniques that gives about 76 milliseconds
per location estimate and our techniques takes about 90 milliseconds per location estimates.
Google My Location, of course, since it's Cell-ID based, it doesn't do any--a lot of
processing, so it's about 12 milliseconds to obtain your location estimates. So as we
said, you have a tradeoff between time and accuracy. So in conclusion, we--CellSense
is a probabilistic fingerprint-based GSM localization technique that uses gridding to reduce the
fingerprint construction overheads and to scale the system. And its accuracy is better
than any of the current techniques for GSM localization by at least 23.8% in rural areas
and 68.--86.4% in urban areas. I now switch gears to another localization system which
we developed within the context of this project which is GAC: A Hybrid GPS/Accelerometer/Compass
Localization Scheme. This technique doesn't use GSM for localization but instead uses
the accelerometer and the compass available in smartphones in order to do localization
combined with the GPS. So the motivation for this work is that many of today's smartphones
contains accelerometer and a compass and it's mainly used for screen auto-rotation. So if
you rotate your phone, the--this rotation action is detected by the accelerometer so
the accelerometer is continuously running. It's used for gaming control and for other--many
other applications like flip to silent; you flip your phone in order to silent--silence
it. And whenever people talk about localization techniques, they usually focus on the accuracy
of the localization technique and they ignore the dimension of energy consumption. However,
if you think about it, at some applications, I don't need very high accuracy of localization.
So, for example, it's for me, it's--if I need just to know that I am in Mountain View I'd
be happy with a one kilometer accuracy. I don't need meter accuracy. One kilometer would
be very fine for me. So can I leverage this coarse-grained accuracy to reduce the energy
consumption of my localization technique? And this is what we are trying to target here.
We are trying to study this tradeoff and give control to the application developer so that
he can choose whether he needs accurate localization or an energy-efficient localization. The GAC
Approach, simply the overall idea is that it obtains an initial position estimate using
GPS and then it turns off the GPS and switches to the accelerometer and the compass to estimate
the location. And from time to time it synchronizes back with the GPS because of the accumulation
of error. So instead of using the GPS continuously, you are duty cycling it with low--very low
duty cycle to enhance your energy consumption. So in the--this part of the talk, I'll start
by talking about the Android power profiling for the different location components in the
Android phone, and then I talk about our proposed hybrid technique, and finally, I'll talk about
power-aware location--power management layer in the location platform, and then finally,
I will conclude. So in order to profile the power consumption of the different location
components, we did it on an Android Dream G1 phone and we used a Monsoon power monitoring
device. And the way it works is that you replace the battery of your cell phone with the battery
that comes with the device, and you connect it to the device and you have an application
running on your computer that tells you the current drain from the battery so that you
can, when you are running different components, you can know which component is using which
amount of current. And since voltage is constant, you can use the current as an indication of
the power consumption. The battery that is used to provide 1150 milliampere per hour.
This is the capacity the battery. For the GPS, we can see this is the typical curve
you get from your power monitoring device when you turn it on. It's almost consumes
an average of about 140 milliampere per hour--sorry--100 milliampere. For the accelerometer and the
compass, the chip that comes on the HTC Dream phone combine the accelerometer and the compass
on the same chip. This means that if you are querying the compass or you are querying the
accelerometer both of them are running and you are almost consuming the same amount of
power, and you have a 3D accelerometer from this chip. The Android over API provides four
different data rates for querying the Android accelerometer. And this is a typical curve
you can get from--when the accelerometer is running in the user interface mode. You can
see it consumes about 40 or 45 average current during its operation. We'll confide this more
in numbers later. So these are the different four modes of operation. You have the normal
data mode where you can have four samples per second up to the fastest mode where you
can have up to 50 samples per second. And the power consumption is not linear in the
number of samples you collect. And our hypothesis for that is that you have two modes of operation,
slow and fast, and that's why it is not linear. However, we didn't have access to the data
sheet of the accelerometer and the compass chip to confirm our hypothesis for that. Comparing
the different techniques, you can see that GPS consumes about 140 milliampere when it's
running. Compared to the normal mode of operation of the accelerometer it's more than an order
of magnitude, more power consumption, which gives you an idea that if you run the GPS,
for example, it consumes 11.73 of the battery in one hour, which means that your battery
you can run for eight or nine hours. If you use the accelerometer in the normal mode,
your battery would run to 100 hours. So it's significant saving in energy if you can't
turn off the GPS and depend on the accelerometer for your location estimates. As another advantage,
I'm telling you that the accelerometer is already running all the time in the background
so that the operating system can detect the auto-orientation of the phone--that you change
the orientation of the phone. So again, if you base your estimate on the accelerometer
in the normal mode you are not consuming any more energy than the standard phone operation.
So are getting it for zero energy consumption in addition to the standard phone operation.
So this is an extra advantage. So we'll talk about how we leverage this in our estimation.
As we mentioned, the basic--you have this state machine of the--very simple state machine
of the GAC operation. You have a synchronization state and the estimation state. In the synchronization
state, you obtain a GPS location estimate and you also calculate the current speed from
the GPS and calculate the offset between the accelerometer--speed estimated from the accelerometer
and the speed and estimated from the GPS for correction. I'll show it to you in the demo.
Once you obtain this information you obtain a fix, or after a certain amount of time you
switch to the estimation process where you switch off the GPS and base all your estimates
on the accelerometer and compass only. And from the accelerometer and the compass you
obtain the displacement and direction and you combine them to obtain your new estimates.
And periodically, from time to time, you switch back to synchronization state to compensate
for the accumulated error and distributes forever until your localization is done. In
order to obtain the position estimate, you use a standard Newton Laws to obtain the position
estimates of the accelerometer and the compass. I will not go into the details, the only thing
I need to highlight here is that we need to take the curvature of Earth into account.
So the--the Earth--the Earth is like a sphere, you cannot use Euclidean distance in order
to calculate your location. And instead, we use the Vincenty's formula which is an accurate
to millimeter accuracy on the Earth's ellipsoids in order to obtain the location estimates,
okay? In order to evaluate our system, we have two different test beds, one in highways
and the other in inside cities, and we study the effect of change and synchronization period
on accuracy and we compare our system with EnLoc. EnLoc is similar to our system with
the exception that it doesn't use accelerometer or compass. So the way it works is that it
obtains a GPS fix, it estimates the current speed and the direction, and that's--it assumes
that these speed and direction will be fixed until the next synchronization points it doesn't
use the accelerometer and compass in between. So we compare our system with this very simple
technique using linear prediction. In order to evaluate our system, we had a debugging
tool based on Google Maps where we draw the GPS traces and the estimated traces. And I
can show you an actual demo from it. So what we are seeing here is the debugging tool.
It gives you information like the total trip distance on the top, then the trip duration,
your average speed, your error at the final points of the trace, your route mean square
error, and your maximum error, and you can control the synchronization frequency in second.
Currently, it's set--as you can see here, the current value is 10 seconds so this means
that every 10 seconds you turn on your GPS to synchronize with it. And you can change
it up to 102 minutes so that--to see the effects. And down here, you can see the trace. This
is a highway in Alexandria City. The green ticks represents the GPS trace which is taken
the ground truth and these yellow and red ticks represents our estimated location. The
yellow dots represent the synchronization periods; the period you turn on the GPS. And
then you--after the yellow dots ticks finishes--finish, your GPS is completely turned on and you are
only using the accelerometer and the compass for estimating the location. And it's 10 seconds,
that's why it's short, we'll change it now to see the effect. You can see, for example,
if I'm synchronizing every 10 seconds, my estimate is very accurate to some extent.
My route mean square error is six meters. If I increase it, for example, to 60 synchronization
every minute instead of every second, I synchronize it to every minute, you can see the error
accumulation here. So again, you have the same--you turn the
GPS for the same period and the red period is where the GPS is completely turned off.
You have a lot of duty cycles so your energy consumption is much less, but at the same
time you are not synchronizing with the GPS more frequently so you have more accumulation
of error. I remind you here we are not using any heuristics instead of the localization
system. So I'm not using the street map to match the estimated location to--I can slap
it to the street. I'm not doing this here. We can of course enhance this, but we are
doing this here. Of course, you can click on any points and give you more information.
If you click on the point it tells you when it was collected from the start of the trace
[INDISTINCT] estimated speed, you can see that the GPS is below 16.5 and the hourly
estimated speed from the accelerometer was 16.6; very close. It gives you the X and Y
acceleration. It gives you the GPS altitude and the accuracy of the GPS. We have other
figures, too. This is the same point I clicked on only a different figure. The blue curve
gives you as estimated GPS speed and the red curve gives you the estimated speed using
the accelerometer and the compass or GAC in general. And you can see there is a drift
in the middle and that's the cause of the drift from the actual position. And at this
point, there was a synchronization with the GPS that's why the accuracy was snapped again
to the accurate--the estimated location. We have our--this is for the accelerometer for
the compass. The blue curve is the direction estimated from the GPS. The red curve is the
direction estimated from the compass. And you can see there is an offset between the
two. In order to correct for this was--what we do is that during synchronization periods,
we calculate this offset and then we remove it from the estimated direction. So during
this period we estimate this offset and we subtract the offset from this curve which
gives you the orange curve on top of the blue curve. We have other figures, that's the accelerometer
reading and the difference from--true acceleration and estimated acceleration. You can see it's
within plus or negative .2 meter squared per seconds. Let's go back and see numbers. This
is the debugging tool were to give us the numbers accuracy and so on. In terms of our
consumption, what we see here is comparison between the different techniques for different
synchronization periods on the X axis in seconds. And the Y axis gives us the milliampere per
hour consumption of different techniques. You can see that the GPS, if you leave it
on all the time, it consumes as we said about 140 milliampere per hour. For our technique,
comparing our technique to the EnLoc, EnLoc is slightly better than our technique in terms
of energy. And the reason for that, as we said, EnLoc doesn't use the accelerometer
and the compass and our technique uses the accelerometer. So the difference between the
blue curve and the green curve is the power consumption of the accelerometer and the compass.
However, as I mentioned, since the accelerometer is running all the time in the background
to detect the change in the orientation of the phone we are not using any extra power
consumption on top of the standard operation. If you take this into account and remove it,
we find that our technique consumes the same amount of energy as the EnLoc technique. So
we are consuming the same amount of energy and you can see that the saving in power consumption
is exponential compared to the GPS. As you increase your synchronization time you're
saving in power consumption decreases exponentially so this is significant saving. In terms of
accuracy, this shows the accuracy for highways. Let's focus first on the green and the blue
curves. The green curve is our technique root mean square error and the blue curve is the
EnLoc linear predictor root mean square error. You can see that for short synchronization
period are 250 seconds, there is no difference between the two techniques. However, as you
increase your synchronization period beyond that, EnLoc is actually--gives better accuracy
than our technique. And the reason for that is that here we are on the highways where
you are usually moving in a straight line. So the assumption if EnLoc is accurate, we
are using the accelerometer and the compass, but we are not synchronizing frequently enough
so we have accumulation of error that decreases our accuracy. So as we see--as I said in small
synchronization period, we have the same accuracy, but if you want to move to higher synchronization
period EnLoc will be better for you if you are using the highway. The main advantage
of our technique appears in intra-city driving. So here, we are driving inside the city and
again, the green curve is our technique and the blue curve is EnLoc technique, and you
can see that we are significantly better than in terms of accuracy, EnLoc, even for small
synchronization period. And the reason here is that the EnLoc assumption of moving in
a straight line is no longer valid because within a city you are changing directions,
making turns and so on, and also you are changing the acceleration. EnLoc assumes that the acceleration
would be fixed until the next synchronization point which is not true when you are moving
inside the city. You are accelerating and de-accelerating because of the traffic. The
nice thing here is that the red curve gives you the power consumption. So what you can
see is that we are saving exponentially in terms of energy but we are losing linear in
terms of accuracy. So you can benefit significantly in terms of energy consumption with very little
loss in accuracy using our technique. So I'll talk briefly on the power-aware management
layer in the location platform. Currently, in order to obtain your location estimate
what you have to do is construct a location listener, you register it with the location
provider and you specify whether you need to use GPS or network-based provider, and
when you are done, you un-register your listener and that's it. However, the developer doesn't
have control over the accuracy or energy he is requiring. All he can say is that, "I need
my location update," for example, "every 10 seconds," or whatever. It doesn't--he cannot
say that, "I need my accuracy to within one kilometer or 10 meters," or whatever. He give
it in terms power or energy budget. He cannot say that, "I need an accurate location so
that my battery can last for 10 hours or for one day," for example. The developer doesn't
have control over this. It would be ideal if we can extend the location provider of
the Android a rating system so that we can give this ABI to the developer so that he
can have all the old ABI and the new ABI that gives him control or her over the energy accuracy
tradeoff that we presented in the previous technique. So this is what we are proposing;
to have a power management layer where the application requests the location accuracy
and the energy or synchronization frequency and the power management layer will determine
the best location provider to use and how long it should use and how frequently it should
report the accuracy. To give you an idea about the saving, this figure shows the accuracy
of the GPS chip when the GPS is turned on for 60 seconds, and this is done periodically.
You can see that you start with very coarse-grained accuracy when you have a cold start and your
accuracy drops exponentially and then it saturates at the end. So at the end, you are consuming--you
have--you're almost having the same accuracy but you are consuming power with no enhancement
in accuracy. It would be better if I can stop. I say, "I don't want any more accuracy since
this accuracy is good enough for me," and then switch off the GPS chip to enhance your
energy efficiency. This is the same curve, it was running it for 10 seconds. And as I
said, if I am good with 250 accuracy, so why not turn off the chip to save energy. So,
in summary, what we provided in the second part of my talk is power profiling for the
GPS, and the accelerometer, and the compass on the HTC Dream Android-powered mobile phones.
We showed that GPS consumes an order of magnitude energy more than the accelerometer and the
compass and we proposed the hybrid GPS accelerometer or compass-based scheme that uses the accelerometer
very infrequently in order to do synchronization and then depends on the accelerometer and
the compass to reduce the energy consumption. We showed that our technique can give exponential
saving in energy with linear loss in accuracy, which is very promising. And our scheme doesn't
lead to improvement--significant improvement in highways when you are having--over EnLoc
when you are having long synchronization period. However, it has significant improvement inside
cities where you have large number of turns and accelerations and de-accelerations. Currently,
we are working on perform a complete power profiling for the Android platform of the
different components so that we are taking the operating system overhead into account
also in the power management layer. And we are also thinking of integrating the power
profiling results into the Android emulator so that when developers are working on the
emulator on the Android phones they can have a sense of how long the battery will last
when you are using this component or this technique on your phone. We are also experimenting
using Kalman filters on the other statistical techniques to further enhance the accuracy
and also experimenting with dynamically adapting the synchronization bid. And instead of having
a fixed synchronization period, how can we adaptively change it based on the accuracy
so that we can further enhance the energy consumption. I would like to acknowledge Google
for their support for this research and this concludes my talk. Questions?
>> Can you talk more about how can you handle the different orientations?
>> YOUSSEF: Can you raise your... >> [INDISTINCT]
>> YOUSSEF: Yes. So in order to do this experiment we assumed that the orientation--the phone
is fixed, it can maybe on the dashboard of the car or on your bicycle. So the question
was, "Can you talk more about how can you handle the different orientations?" The Android
phones come with an orientation sensor at the same time so you can experiment with taking
this reading in order to detect its orientation of the phone and then reorient it to the standard
coordinates and use it. Once it's oriented, you can use the same technique without any
modifications. However, our initial results on that shows that you have very large amount
of noise. It is not that accurate. But again, if you assume that mostly when you are driving,
you will not be carrying the phone in your hand it will be fixed to some orientation
on the dashboard. So, for example, you can do an initial calibration when you start your
calibration--system and then use it from there. Other questions?
>> [INDISTINCT] >> YOUSSEF: Very interesting question. The
question is, "We said that EnLoc is better in highways than our technique and then we
are better in intra-cities. So did you thought about switching between the two techniques
based on the driving better?" Yes. And that's why I didn't include it the current work.
One way of course is combining both techniques. So, for example, you can detect it from the
movement better from the accelerometer that the user is driving with a constant speed
or he is not making a large number of turns and based on this, you can say I am on the
highway. So in this case, I can switch completely to EnLoc and disable the accelerometer and
the compass, it will give me better accuracy and it will save me more energy. So this is
a very good idea. Yeah. Other questions? >> [INDISTINCT]
>> YOUSSEF: I have one or two towers? >> Yes. [INDISTINCT]
>> YOUSSEF: The question here is that, "In the first technique where we are doing RSSI-based
GSM localization, if you have an area with a sparse radio map, so as far as cell tower
dynasty, you have say two cell towers and you will have many locations with similar
fingerprints, meaning the signal strengths of these locations would be the same. So how
would you do--would you select one of them randomly or you select the top most?" The
brand threshold which is, K, which is supposed to process the step, what it does is that
it returns to you the average of the top most K locations. So on this case, if you have
two locations similar to fingerprint, what it will does, it will give you to use a center
of mass of these similar locations and it will be weighted by the probability. So in
order to taking that--the average, it's a weighted average we're using as the probability.
So the location with the highest probability will have more weight than the location with
a low probability. So in this case, you are taking the weighted average as center of mass--actually,
it's the center of mass of all location taking weight as the probability of the location.
Of course, your localization accuracy will not be as good as when you have seven towers.
But in this case--this is the best you can do. Okay, actually this is--I was talking
with the--another group in the morning about the same idea which was how can you do localization
with [INDISTINCT] low end phones where you get information only actually from one cell
tower, not two. So if you have a low end in the phone, usually it will give you just as
that information from the associated cell tower. So if you are doing this, how can I
enhance the accuracy based on this? And one technique is what you are talking about is
taking the history information into account so that I can get a better estimate. So I'm
not just taking this sample; I'm taking the history of sample with me to better enhance
the accuracy. >> So, can we have [INDISTINCT]
>> YOUSSEF: Right. Actually, in the [INDISTINCT] assumption is usually taking for mathematical
feasibility and tractability, yeah. >> How much [INDISTINCT]
>> YOUSSEF: Actually, we haven't experimented with taking correlation into account. Actually,
in our previous work in Wi-Fi based on the localization, we had to work for taking correlation
between samples from the same access point. Actually, you can go with the assumptions
that samples from different cell towers are independent. But if you--when we talked about
using N samples at the same time, we assume that samples who are from the same tower are
independent, but actually they are very highly correlated. So you use the--modeled this before
using auto-regression and we obtained better results when we take correlation into account.
But it will take you more processing overheads in order to remove this correlation. So it's...
>> [INDISTINCT] >> YOUSSEF: Can also...
>> [INDISTINCT] >> YOUSSEF: And do a collection like what
happened in the assisted GPS, for example. Yeah, that's variable, too. Very good question.
Sure. >> [INDISTINCT]
>> YOUSSEF: Right. That's a good question. The question is, "Did you try to use different
phones in your experiment or you just used one phone?" Because when you use different
phones each one has a different receiver sensitivity so the radio map constructed by one would
be different from the radio map constructed from the other. Actually, what we did is that
all the phones we used were G1 phones but we used different G1 phones. So at least from
the same model we tried different phones and all of them of course gave similar results.
We tried with Nexus1 phones, but we didn't have concrete results--figure graph. We just
had it in a demo that we can walk and give us similar accuracy. What we did also is we
tried different service providers. So not just one service provider, we tried with--Egypt
has three major providers, we tried with the three of them and they gave us comparable
results of course depending on the cell tower dynasty. What we're also planning to do is
to do automatic mapping between different phones. So even if there is a difference between
phones in terms of the receiver sensitivity and the antenna that and so on, can we have
an automatic way of taking the radio map constructed by one phone and to map it automatically to
another phone. This is something that we are looking into now, too. That is a very good
question. [INDISTINCT] >> [INDISTINCT] does that have any effect
on the [INDISTINCT] >> YOUSSEF: In which technique?
>> [INDISTINCT] >> YOUSSEF: The first technique, of course.
In Egypt, we didn't have any significant tall buildings that can affect the reception. As
I said, we are taking GPS as a [INDISTINCT]. So for this, we are assuming it has zero error.
So, no, the answer, we didn't try any kind of [INDISTINCT] or so on. If you have a data
that we can use for evaluation, it would be great to look into it. Thanks. You have another
question? >> We have another question [INDISTINCT] it
looks like the way you access [INDISTINCT] >> YOUSSEF: The way we do it is that...
>> [INDISTINCT]
>> YOUSSEF: On the streets. >> On the streets?
>> YOUSSEF: Yes. >> So, have you tried actually doing any [INDISTINCT]
have you tried actually walking with [INDISTINCT] >> YOUSSEF: Again, not formally so we don't
have figures for this but we do it on the demo. So, you'll be inside the building that
would give you a location better than the--we had actually a demo--of course, it is not
calibrated here, but while we can show we have a demo where it can shows our four techniques
I'm comparing with and you can see the estimated location using all the techniques and it will
have the same accuracy. But we didn't have an exact numbers that your accuracy degrades
by this amount when you are doing this. Sure. >> [INDISTINCT] if you feel like you wanted
to power the [INDISTINCT] actually beside the use of the particular parts [INDISTINCT]
so it looks like it wouldn't have been [INDISTINCT] what enable to turn the application based
on the [INDISTINCT] >> YOUSSEF: Good question. The question is,
"When I talked about the power management layer on top of the location provider we said
that I'll give the application, developer and API to specify his accuracy and energy
consumption requirements." So the question was, "What if you have conflicting the applications?
Each one of them requesting a different criteria that conflict the other power management layer?"
This is a very good question just on--from the top of my head. In the worst case, you
will be working with the least of them. So in this case you are not doing any worst than
the current API, but if you can do better you will do better. Something similar that
you introduced in the latest API is that, if I remember scheduling the events instead
of waking up randomly, you combine applications that wake up at the same period of time and
make them all wake at the same time. So if you want to say, "I need to wake every 10
seconds," and you are spaced apart every second, actually you will be waking up every second--every
10 seconds. So what you can do is that you align them together so that you can obtain
same thing. So maybe it's something along these lines can be used as a location provider
too. But actually it's an interesting problem that needs more thoughts about it, you know.
Any questions? >> How long does it take this [INDISTINCT]
>> YOUSSEF: It depends on many factors, including are you indoors, outdoors, have a clear line
of sight to satellites or not, is it a cold start or normal start and so on. So there
are a lot of factors in our technique. If you remember the state machine whose saying,
obtain a fix or timeout. So this timeout is used that if you're fix takes a lot of times
then you will timeout and the move to the estimation INDISTINCT] so that you don't consume
a lot of energy waiting for a GPS fix. And hopefully when you come later to the synchronization
state, you will start from--not from the beginning from some point so that you will enhance the--take
shorter time in order to obtain the next fix. >> So is this kind of part of the [INDISTINCT]
>> YOUSSEF: Its fixed as I said from the demo as you saw the synchronization period was
fixed at. We fixed it at some time. When you increase it, it's a start as the time I will
showing you as XX is a start of the synchronization period. And that's the time you stay in synchronization
period is fixed regardless of the synchronization period. Okay.
>> And you have the sort of [INDISTINCT] >> YOUSSEF: For what?
>> Intercity driving. >> YOUSSEF: You need the Intercity driving.
>> Yeah. The error [INDISTINCT] >> YOUSSEF: This one?
>> [INDISTINCT] >> YOUSSEF: Oh, I don't think I have that,
because all of them are highway. You talk about this?
>> Yeah. >> YOUSSEF: I fail when I--all the dataset
I have here is for the highways. Sorry for that.
>> Does the [INDISTINCT] >> Does what?
>> Does the [INDISTINCT] >> YOUSSEF: Actually, there's a better way
when you take it more from the compass. So, when you make a turn a compass will give you
a better estimate of the direction. So, you just take that from [INDISTINCT] to estimate
the displacement, how much you move along this direction. That's why we combine both.
Actually, in the slides--here this is from Intercity driving, but I don't have the data
with me. So, this is within city. But it is a static. It is not--I cannot change the parameters.
Okay. >> [INDISTINCT]
>> YOUSSEF: Inside what? >> Inside a car.
>> YOUSSEF: A car. >> Yeah. [INDISTINCT]
>> YOUSSEF: Because of the magnetic field? >> Yeah. [INDISTINCT]
>> YOUSSEF: So, the question is, "If you use the compass inside the car, there is a magnetic
field that may affect the accuracy of the compass."
>> [INDISTINCT] >> YOUSSEF: Right. And actually, we are showing
it here. We do have it and in order to reduce it we do some averaging and filtering on the
accelometer, the compass reading. And that's why maybe, it was--this was one of the reasons
for this figure I was talking about, this is the reading from the compass from an actual
experiments inside the car. And the blue curve is the estimated direction from the GPS. The
red curve is the raw data you get from the compass reading from the phone, and the orange
curve is the corrected figure taking, to offset into account the initial offset into account.
So if you just used it--actually, the red curve is an averaging of the raw data. And
then on top of this we do more processing to obtain the orange curve. So, yes, it's
noisy but we try to reduce the noise by some processing on top of that. Any more questions?
Okay. Thank you very much for your time.