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