Cell-based positioning
for improving LBS Markus Ray
Cell-based positioning technology can be used to provide valuable
knowledge for LBS even in indoor environments
Figure 2: Geographic distribution of cells in urban areas compared to rural areas
Most of today’s Location Based Services
(LBS) provide information based solely on
a users’ location, not taking into account
context knowledge about the user’s current
situation and needs. This often results in
low-quality and inappropriate information
to the user. Hence, in order to provide
user-oriented services, an improvement
of the response-quality of information
requests is required. Knowledge about
the coordinates of places where the user
regularly stays in her life combined with
semantics about such places can provide
valuable knowledge for LBS. Zhou et al.
[2] state that “the discovery of a person’s
meaningful places involves obtaining the
physical locations and their labels for a
person’s places that matter to his daily life
and routines”. This is in accordance with
Hightower et al. [3], who identified two
needed steps for finding meaningful places
of individual users: (1) finding physical
locations of meaningful places and (2)
assigning semantic information to those.
Two obvious meaningful places of persons
are locations like ‘home’ or ‘work’, but the
perception of meaningful places might also
include places where the user stays once
in a while (e.g.: visiting the grandparents
all three months). This article outlines a
methodology for finding and classifying
places where the user regularly stays
in her life, in the following denoted as
‘prominent places’. A detailed description
of this work has been published in [1].
Most of the previous research for finding
prominent places has been done based
on the Global Positioning System (GPS).
GPS is available worldwide and in general
provides accurate position measurements.
Since GPS is a satellite based technology,
an unobstructed view to at least foursatellites is required for calculating reliable
positions. Hence, within buildings or in
narrow streets no or corrupt positioning
data is available because of shadowing
effects. Most approaches for finding
stays of users are based on recurring GPS
dropouts like Ashbrook and Starner [4]
and Marmasse et al. [5]. To overcome
such a heuristic approach, Nurmi and
Koolwaaij [6] have presented a GSM celltransition
method supported by GPS for
finding meaningful places. In contrast to
GPS, cell-based positioning technology is
also available within buildings or urban
areas and positioning data can be easily
obtained by the GSM network using any
mobile phone. A cell-based approach for
clustering and predicting of mobile phone
users’ routes based on a cell-transition
graph has been presented by Laasonen [7].
Figure 1: Workflow of analyzing cell-data for finding (a) and classifying (b) prominent places
Collecting cell-data In order to draw meaningful conclusions
about the motion behavior of individuals,
a sufficiently large amount of localization
data is required. We have collected 250
000 cell-based position measurements
from ten volunteers obtained during
half a year of permanent observation
using a constant sample rate of five
minutes. On average, 25 000 positions
have been obtained from each volunteer
in cooperation with the biggest
Austrian mobile phone provider.
The volunteers agreed in providing
their positioning data from July 2006
to December 2006 by signing a special
contract regulating privacy issues.
The volunteers had full control and
transparency about the localization
activities via a SMS interface. It
Markus Ray
Human Centered Mobility
Technologies, Arsenal
research Vienna, Austria
Markus.Ray@arsenal.ac.at
lbs
was possible for each volunteer to
deactivate, activate and retrieve the
status of localization by sending a
SMS during the observation period.
Analyzing cell-data
The analysis is split into two steps.
First we take the collected cell-data to
find places where the volunteers’ spend
most of her time. The found places are
subsequently automatically annotated
with semantics by labeling them with e.g.
‘home’ or ‘work’ (see also Figure 1)
Finding prominent places
Prominent places are defined as places
where the user spends most of her time.
In general, such places will be mainly
‘home’ and ‘work’ locations. Hence,
cells where one volunteer has been
located more often than in others (using
a constant sample rate) must correspond
to her prominent places. Cell-candidates
are therefore first identified by filtering
out cells exceeding a high dwell time.
some cases there is a one-to-one relation
between a cell candidate and a prominent
place. However, it often happens that one
prominent place is assigned to multiple
cells: Each cell of a mobile phone network
covers a defined area with radio signals
to provide mobile telecommunication
to the end-user. In order to prevent
communication lacks due to shadowing
effects (e.g. caused by buildings), multiple
cells are sometimes used to cover one
area, leading to the above phenomenon.
If multiple cells are available in one area,
the cell with the strongest signal is selected
by the mobile phone if acknowledged
from the network. Both the mobile phone
and the network can initiate a change to
another cell at any time to ensure network
load balance and communication quality.
In our work, center-of-cell-coverage
localization was supported by the mobile
phone provider: After requesting the
current position of one volunteer, the
network returns the center coordinates
(theoretical center of radio-frequency
coverage) of the volunteer’s current cell.
Hence two cells available at one place
can have totally different coordinates
for positioning. In urban areas center-ofcell-
coverage localization is much more
accurate than in rural areas due to higher
geographical cell density (See Figure 2).
Grouping cell-candidates based on pairwise
Euclidian distances would therefore in
general not produce meaningful results.
We have therefore developed an approach
of an individual cell-network graph.
Nodes of the cell-network graph represent
cells and links represent cell changes.
The individual cell network graph is used
to calculate pairwise topological distances
between the potential cell-candidates using
the Dijkstra algorithm. Cell-candidates
are grouped if the topological distance
between them is lower or equal than
a predefined number of links. Due to
network characteristics, it might happen
that not all expected cell-candidates
representing one prominent place are
linked and therefore correct grouping
will fail. To overcome this case, a further
approach is used to add missing cells to
related prominent places by comparing
time series of visiting frequencies.
The assumption that visiting frequencies of
cell-candidates – which belong to the same
prominent place – should be drawn from a
similar underlying continuous distribution
allows us to use the Kolmogorov-Smirnov
test for grouping missing cell-candidates.
If the hypothesis for this test – two samples
have the same underlying distribution –
is not rejected, then these cell-candidates
are grouped. Finally all expected cellcandidates
should be successfully grouped. Classifying prominent places
After grouping is finished we can
compute a sequence of prominent places
ordered by visits through a work day
based on the visiting frequencies. At
the same time we can manually define
a daily routine for such work days By
comparing these two sequences we can
label the computed prominent places
for finally giving them semantics.
’.
.gif)
