Placeholder Image

Subtitles section Play video

  • >>

  • 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.

>>

Subtitles and vocabulary

Click the word to look it up Click the word to find further inforamtion about it