=Paper=
{{Paper
|id=Vol-197/paper-6
|storemode=property
|title=Tracking a personalized trail effectively with a mobile phone
|pdfUrl=https://ceur-ws.org/Vol-197/Paper6.pdf
|volume=Vol-197
}}
==Tracking a personalized trail effectively with a mobile phone==
https://ceur-ws.org/Vol-197/Paper6.pdf
ubiPCMM06:2nd International Workshop on Personalized Context Modeling and Management for UbiComp Applications
Tracking a personalized trail effectively
with a mobile phone
Jong-Ho Lea, Hee-Seob Ryu, Sang-Goog Lee, Yong-Beom Lee, and Sang-Ryong Kim
Advanced Systems Research lab
Samsung Advanced Institute of Technology
P.O. box 111 Suwon
440-600, Republic of Korea
{john.lea, heeseob.ryu, sglee, leey, srkim}@samsung.com
ABSTRACT of personal gazetteers with using mobile phones with Global
This paper presents a solution to a problem of reducing the GPS Positioning System (GPS) equipment.
call incidences to record personal gazetteers and of adjusting the A personal gazetteer records places that are meaningful for a
granularity of localization on different distance scale according to specific person [6]. References [7, 8] argued for the advantages of
visiting experiences. Personal gazetteers usually list and describe personal gazetteers which are based on a notion of place, rather
users’ important places, such as home, work, restaurants, etc. The than physical location.
important places for mobile users can be easily logged by fixed-
rate GPS calls. But frequent GPS calls consume the battery of a We briefly define places as a textual label and some sort of
cellphone, so it is important to reduce the GPS call incidences geometric representation, such as a point, a set of points, or a
without the loss of location accuracy. We found out that the region. For example, my personal gazetteer might include places
pseudo-noise (PN) signals of mobile phones show stable patterns such as:
to estimate the places along the users’ path. According to these Bun-dang (My home): latitude (37.34831),
stable patterns, we can get the proper GPS call times both when longitude (127.1176)
the PN signals show whether the user stays long enough in his/her
point of interest (POI) and when he/she changes significantly Yong-in (work): latitude (37.22959), longitude
his/her location. The real road experiments demonstrate the (127.8298)
effectiveness and applicability of the GPS call reduction of this
In Korea, one degree of the latitude verges on 114.64 km, while
algorithm, and it is found to produce reliable personal life patterns
one degree of the longitude borders on 88 km. (Readers can
of POIs. After getting the patterns of POIs with reduced GPS calls,
imagine that my work place is not far from my home.)
naming the places is required. This paper also presents a user-
centric model of addressing the gazetteers, which will be adapted The complexity of the mobility tracking problem in a cellular
as the visiting rates of the same visited places increase. Familiarity environment has been reduced by the Global Positioning System
breeds concerns with the polished scalability of the address (GPS) usage [2]. Now that standard mobile phones can be
naming. harnessed with a GPS chipset, GPS calls can track the user’s
location more accurately than the Pseudo-Noise (PN) signals
Categories and Subject Descriptors given from near base stations can do [5, 1, 3, 4].
C.3 [Special purpose and application-based systems]: However, using GPS calls regularly within a cellphone device
Microprocessor/microcomputer applications; H.4.2 [Types of may result both to the interruption of the main communication
Systems]: Information systems applications – decision support. function and to the fast consumption of a mobile battery [2, 4, 5].
We assume a new way to reduce the regular GPS-call rates into
General Terms irregular and low rates by deciding the proper GPS-call times
Algorithms, Management, Measurement, Performance, Reliability, according to PN signal patterns. Before we suggest our method,
Experimentation, Human Factors we had better look over the mobile network system.
The wireless network for a mobile phone system is built upon an
Keywords underlying cellular architecture [1, 3, 4, 5]. The service area is
Mobile device, cellphone, GPS, POI, Pseudo-noise, cell-id, life sectioned into a collection of cells, which are serviced by different
patterns. base stations. Several base stations are wired to a base station
controller, and a number of base station controllers are further
connected to a mobile switching center. This hierarchical
1. INTRODUCTION connection of the mobile switching center, base station controllers,
As mobile devices are to be with the users, they offer the promise and base stations, along with the air-link between the base stations
of new applications, such as users’ gazetteers discovery [6] and and the mobiles forms the collector network. The collector
life-log presentation [14, 11, 12]. Cellular phones are the most network is interconnected by the backbone of the Personal
promising device because users carry their mobile phones together Communication Service (PCS) network consists of the wire-line
almost all the time. Our research concentrates on the acquisition networks (such as Integrated Services Digital Network: ISDN,
Public Switched Telephone Network: PSTN, and the Internet).
ubiPCMM06:2nd International Workshop on Personalized Context Modeling and Management for UbiComp Applications
The mobile switching center broadcasts a page message over a for the user’s passage [4, 3, 1]. The mobile’s last known position
designated forward control channel via the base stations in a set of and its surroundings are also considered to guess the most
cells where the mobile is likely to be present. All the mobiles probable current position. That is, the probability decreases in an
listen to the page message, and only the target phone sends a omni-directional way, inversely proportional to the increasing
response message back over a reverse channel. In case no distance from the last known position.
response message from the mobile is available, the system has to
We do not consider the probability model of the passage in this
page the limited number of paging channels. To put an upper
paper, however. We assume that the cell-id patterns will reveal the
bound on the amount of location uncertainty, a mobile is made to
underlying location areas in a reliable manner, nevertheless, with
report from time to time, called a location update.
the noises of temporary shifts.
This mechanism helps to solve the mobility tracking or location
management problem. The mobility tracking is to track down a
mobile user for satisfying these connectivity requirements.
2.2 Cell-id patterns in the field test
In this paper, we look at the mobility tracking solution with PNs We chose urban built-up areas for the field test on cell-id patterns.
or cell-ids. This outlook provides the insight to design an adaptive Especially we chose the southern downtown of Seoul (i.e. Gang-
onset time of GPS satellite call. Learning the cell-id patterns Nam) where is the most famous area for works and entertainments
endows the PN signals with a predictive power which reduces the in Seoul (and many handovers and transient shifts are expected).
frequent GPS calls. Then, we will discuss a user-centric address
Researches in environmental psychology show that people
model to label the POIs according to the familiarity (or the
naturally structure their experience around personally or socially
increasing visit frequency) of users with visited places.
meaningful places, such as homes, offices, schools, churches,
coffee-shops, pubs, etc. [8, 9, 12, 14]. Instead of using physical
location in personal gazetteers, people use to refer to places in
their descriptions, such as “the coffee-shop,” or “the movie-
2. USER MOBILITY WITH CELL-IDS theater.” Gang-Nam area (i.e. the southern downtown of Seoul)
2.1 The principles of Pseudo-Noise signals (or has many offices and coffee-shops for social networks.
cell-ids) Also GPS systems have difficulties in tracking locations in urban
The service area under a mobile switching center is partitioned canyons due to poor satellite availability [10]. Owing to high
into location areas (LA). The base stations must broadcast the buildings in the built-up area like Gang-Nam, GPS receivers may
location area id (along with the cell-id) to the mobiles as a part of acquire a less number of satellites, which may be insufficient to
the update scheme. obtain good precision. However, Pseudo-Noise signals (or cell-
A mobile phone must update whenever it crosses location areas, ids) of mobile phones have little line-of-sight (LOS) issues that
which are formed by non-overlapping grouping of neighboring make GPS less effective in urban canyons than in plains.
cells—governed by each different base station [5, 4, 3, 1]. The
wireless network for a Personal Communication Service (PCS) is
built upon this underlying cellular architecture of base stations,
which can be conjectured by PN patterns. Because base stations
must broadcast the PNs (or cell-ids) to assist the mobiles to follow
the update protocol, we can presume the location areas by the PN
patterns.
Each base station broadcasts three cell-ids, ranging from 0 to 512
and using only even numbers. There are relations among the three
PN signals (e.g.
α , β , γ ) as follows:
α + 168 mod 512 = β
β ± 168 mod 512 = γ (1)
A cellphone receives many PNs (or cell-ids), more than three,
from several base stations which locate within the user’s location Figure 1. Test trajectory in downtown Seoul (Gang-Nam),
area (LA). Depending on the factors such as the LA partitioning, including four subway stations: Kang-Nam station, Yeok-Sam
the call arrival rate and the user’s mobility, the main PN (called station, Seon-Roong station, and Sam-Sung station
PN1) for the communication may be temporarily updated or
handed over to alternative PNs, which are weaker than PN1 and
sometimes came from the other near base stations. This temporal The field test trajectory is shown in Figure 1. We designed four
shift makes it hard to estimate the LA assignments with only PN pathways and passed along them twice, each in different days. The
patterns [1, 4, 5]. pathways were gone repeatedly during eight days for checking the
To put an upper bound on the amount of location uncertainty, consistency of cell-id patterns at the same areas in different
many location management approaches use a probability model
ubiPCMM06:2nd International Workshop on Personalized Context Modeling and Management for UbiComp Applications
periods of time. We drove a car at about 5 to 60 km/h speeds, in From the eight-day experiments with four major districts (i.e.
order to simulate both walking and driving conditions. around four subway stations) in Seoul, we found that the PN1
patterns are relatively stable at different areas, even in realistic
moving profiles of mobiles with a speed variation (from walking
to driving) (see Figure 3 & 4). We can separate the boundary of
location area (LA) by considering the stable PN1 duration (see
Figure 2). The boundaries of PN1 patterns show variations from
200 m to 1 km wide, but we can differentiate the sub-areas in
reliable manners. Furthermore, there are some noises in the stable
PN1 patterns, which come from the temporary increase of external
factors, such as busy paging protocols filled to capacity or
blocking update protocols in built-up areas. (Refer to the red spots
in Figure 2)
We also found that the top & second strong pseudo-noise (PN or
cell-id) have stable dispositions, while the third PN fluctuates
even when a mobile stays still in the same area. For example,
Figure 3 and 4 show the stable propensities of PN1 and PN2 with
a fluctuating PN3, but steady even at the different places and
through the different period of different weekdays.
From these results of field experiments, we conjecture that if we
find some methods to filter the temporary noises from the stable
PN patterns, we could determine the right time to activate GPS
Figure 2. Coloring the PN1 areas along the test trajectory: The calls at lower rates than at regular fixed-rates. The next section
areas with different radii (100 m ~ 500 m) around subway will explain the algorithm of finding proper GPS onset times from
stations are grouped. the mobile PN patterns.
3. PROPOSED ALGORITHMS
3.1 Deciding GPS evoking time
In this paper, we kept the log of two cell-ids (i.e. the two topmost
PNs among strong PN alternatives) at every sampling time. The
interval between two sampling times could be varied according to
the conditions of previous sequences. Just as a 3-order Markov
chain, if three previous cell-ids in the sequence do not change,
then the sampling rate can be low-enough (i.e. 1 Hz). In other way,
if three previous cell-ids differ, then the sampling rate rockets to
higher rate (i.e. 6 Hz). Figure 5 depicts the main idea of our
algorithm.
Figure 3. Patterns of PN1 to PN3 in a point-of-interest: The
PN ranges from 0 to 511 on the Y axis, and are measured at
every 20 seconds (X axis). The two strong PNs (PN1 & PN2)
show stable patterns during a stay, while the third strongest
PN (PN3) vibrates a bit.
Figure 5. Reduction of GPS call incidences: The number of
GPS calls at regular rates (at yellow stars) can be replaced
Figure 4. Patterns of PN1 to PN3 in another POI: This area, with a single call (at the red star) according to the stable PN
different with the one in Figure 3, has three stable patterns of pattern. The PN ranges from 0 to 511 on the Y axis, and are
PN signals with temporary exchanges between PN1 and PN2. measured at every 5 minutes (X axis).
ubiPCMM06:2nd International Workshop on Personalized Context Modeling and Management for UbiComp Applications
As long as a mobile phone locates in a location area, the two nearside base stations. And also the digital map can suffer from
topmost pseudo-noise signals (i.e. PN1 & PN2) show stable cell- incomplete information such as missing street segments, etc. Thus
id patterns (see Figure 3 & 4) which lead to a fact that one GPS it needs to snap correctly the estimated location to the map
call (i.e. the red star in Figure 5) is enough to mark this location position in order to name the GPS position with proper tags (or
area, rather than the four times regular calls (i.e. the yellow stars textual labels).
in Figure 5).
At the next section, we develop a customized way of naming the
points-of-interest (POIs), considering the users’ habituation of the
location areas.
3.2 Labeling the POI with customized names
Even though our algorithm in 3.1 may save the power
consumption from frequent GPS activation, we cannot guarantee
the repeatability of the GPS coordinates even in the same area
because of unforeseen GPS call times and GPS errors. The
differences between GPS coordinates in the same area may not be
a big problem for displaying the spots in a map, but these may be
serious when we have to name the location with text automatically
(i.e. address, nearest road, near famous store, etc.).
For the navigational aids within the landscape framework, we can
use spatial maps or verbal route lists. When words in the map
database are used instead of maps, words in the route list can be
easily transformed to speech [12]. This verbally labeled route list
reduces error, shortens decision times, and reduces mental effort
in driving tasks relative to a map [13, 12].
Also we can easily conjecture that labeling the nearest address of
the GPS coordinates is not enough for users to easily understand
Figure 6. A procedure to make personal gazetteers with GPS the locations, such as “111 AA-street, BB city,” “98 AA-street,
and mobile cell-ids BB city,” etc. We need more comprehensible and more GPS
error-tolerant way of labeling the location automatically than just
returning the GPS-corresponding text or annotating the labels by
In this paper, a procedure to determine the GPS onset times from users. We may use some human factor to make a useful
the mobile cell-ids and to match the GPS location up with the map improvement in the automatic POI addressing.
for personal gazetteers was developed and used (see Figure 6).
People who repeatedly visit an area will gradually gain knowledge
There are four parts of our methods: the pseudo-noise in the order: landmark, route, survey [14]. We might recall this
receiving/sorting part, the pseudo-noise comparison part, the order in how we gained knowledge about the layout of the city
position determination/decision part, and the position where we live. At first, we remember the appearance of prominent
determination/map-matching part. The pseudo-noise landmarks in a region – the house with a funny shape, the nice
receiving/sorting part receives the pseudo-noise signals from smelling bakery, etc. Next, we learn the proceduralized verbal
several base stations, and then sorts them in accordance to their knowledge of how to get from one place to another, that is, route
signal strengths. The two topmost pseudo-noise signals are knowledge. Finally, we draw an accurate or abstract map of the
recorded and get stored in a PN database. environment. This is survey knowledge, which represents
The pseudo-noise comparison part fetches the previous pseudo- geographical knowledge generalized across many experiences
noise signals from the PN database, and compares them to the [12].
current cell-ids (or pseudo-noise signals). It determines whether a This tendency of getting an accurate mental representation of a
steady tendency exists or not. familiar environment leads to different aids (or labeling methods)
The next step is the position determination/decision part. This part depending on the level of familiarity with the visited regions. In
calculates the duration time of steady patterns of PN1 and PN2. If this paper, we can implement the differential method of labeling
the duration is over the threshold which can filter the temporary location as follows:
handovers and fluctuations, it looks into past histories of the We divide the full address into four parts and use appropriate part
associations between pseudo-noises and GPS locations. If there is for the context familiarity level. For example, instead of using the
no GPS location matching with the requested pseudo-noise (or full address “108 Wilmot Road, Deerfield, IL USA,” we divide
cell-id) and if the duration of steady patterns is over the threshold, this address into four parts (see Figure 7).
the GPS system finally activates and gets the location coordinates.
Many countries use different address labeling systems. North and
The final part is the position determination and map-matching part. South America use roads as the references of address system.
In many circumstances, the GPS coordinates are noisy and Swiss and Korea split lands into small parts with arbitrary
imprecise because urban built-up areas can hardly acquire the boundaries, and sub-divide the parts into the smaller ones if there
sufficient signals from both GPS satellites and pseudo-noise from
ubiPCMM06:2nd International Workshop on Personalized Context Modeling and Management for UbiComp Applications
are new houses or buildings to be constructed. United Kingdom clue to the location (unless it is the user’s home address) and it is
matches the names of districts with postcodes. France uses a the most GPS error-prone among the address level. Rather using
clock-wise numbering system starting from centers. Japan prefers the exact house number, we use the nearest prominent landmark
the block system and includes the building names in its address, for this case.
sometimes. German combines the block and road system.
To decide the nearest prominent landmark in the neighborhood,
Although there are the differences in the address systems, we can we first set a priority list for the prominence. We categorize the
roughly apply a division into four parts with the context class of buildings, road-shapes, transport stations/stops, etc., and
applicability of area granularity – it depends on the real size of the give priority to them. Second, we decide the neighborhood
corresponding sections’ lands. That is, the GPS granularity is boundary to search the nearest prominent landmark. We can set a
about 10 m radius, and it implies that at the finest fourth part a rough boundary with our method mentioned in 3.1. Then, as the
nearest building or a street name will be matched with the GPS number of visits increases, the boundary will be segregated into
coordinates. two smaller regions (see Figure 9).
In the boundary of a limited radius, the number of visits overflows
an old boundary (P) and makes a new boundary (Q) containing a
minimum number of visits (e.g. n>3) – that is why the two
members of P in the intersection become new parts of Q (see
Figure 9). When two boundaries P and Q are formed, the
prominent landmarks (P’ for P, Q’ for Q) are calculated according
to the priority of landmarks.
Figure 7. Four address levels with respect to local familiarity
The first part, (1), is the combination of state/province and
country, and we use it when we first visit a place and have no
previous history of the same state/country. The second part, (2), is
a city name where we use to label the visiting area in which we
have visited the same (1) part before. The third, (3), is a street
name without a house number, and we use (3) when the many
same (2) areas are recorded in the visit history. We can depict the
decision of label level in Figure 8. As the number of visits
increases, the familiarity of the area also increases, and as a result
users need more specific address (or position attribute) than
before in order to name several places in the same boundary.
Figure 9. Segregation of neighborhood into two areas
according to the increasing frequency of visits
Figure 8. The relationship between the visit frequency and the
level of address labeling: As a user visits a place more
frequently, the labeling level of address is to be getting more
specific for memory aids and differentiation among near places.
Figure 10. Reduced frequencies of GPS calls to find POIs: (PN
However, even in the case we are familiar with the (3) area, we value from 0 to 511 on the Y axis)
would not use the naming (4), because it does not give us a clear
ubiPCMM06:2nd International Workshop on Personalized Context Modeling and Management for UbiComp Applications
example shows a useful convergence of personal gazetteers with a
GPS-equipped mobile device.
4. RESULTS
From our data (i.e. recording 15 days), we found that every 5. CONCLUSION
fifteen-minute comparison of PN patterns was enough to This paper has presented a useful method to save the power
differentiate POIs (Points of Interests) of the user’s passage. consumption of GPS calls within mobile systems. Our method in
Fifteen-minute duration is good at filtering the temporary shifts of 3.1 also uses the reliable patterns of pseudo-noise signals given
pseudo-noise signals. from base stations within the location areas. These location areas
usually match to the personal and social points-of-interest (POIs).
We show the reduction of GPS call frequencies of our method,
Our method in 3.2 solves the GPS-error prone situation of the
comparing to regular rate sampling (per one hour) (see Figure 5 &
nearest address labeling. Therefore, the personal gazetteers may
10).
list the POIs with interesting patterns of stopover history both in a
Without using some probability model for the user’s passage, our map with reasonable boundaries and in textual labels with gradual
methods show reliable differentiation of POIs on the passage. convergence of the user’s life pattern. Using our methods may
Furthermore, our methods reduce the GPS call incidences ten develop many possible ways of presenting the mobile users’ life
times lower than the regular rates of every fifteen minute. patterns. One example of the personal gazetteer with our methods
is given in Figure 12.
6. REFERENCES
[1] Borkowski, J., Niemelä, J., and Lempiäinen, J. Enhanced
Performance of Cell ID+RTT by Implementing Forced Soft
Handover Algorithm, In Proc. 60th IEEE Vehicular
Technology Conference, LA, 2004, 3545-3549.
Figure 11. Tracing 15 days of a college boy in downtown Seoul
[2] Braasch, M. S., and Van Dierendonck, A. J. GPS Receiver
Architectures and Measurements, In Proceedings of IEEE,
87, 1999, 48-64.
[3] Caffery Jr., J., and Stuber, G. Subscriber Location in CDMA
Cellular Networks, IEEE Trans. on Vehicular Technology,
47, (May 1998), 406-416.
[4] Chung, Y. W. Effect of uncertainty of the position of mobile
terminals on the paging cost of an improved movement based
registration scheme, IEICE Trans. Communication, E86-B, 2,
2003.
[5] Hata, M., and Nagatsu, T. Mobile Location Using Signal
Strength Measurement in a Cellular System, IEEE Trans. On
Vehicular Technology, 29, (May 1980), 245-251.
[6] Zhou, C., Frankowski, D., Ludford, P., Shekhar, S., and
Terveen, L. Discovering Personal Gazetteers: An Interactive
Clustering Approach, In Proceedings of ACM GIS 2004,
Washington DC, 2004, 266-273.
Figure 12. An example of a personal gazetteer for a day
[7] Jones, Q., Grandhi, S., Whittaker, S., Chivakula, K., and
starting from 6 o’clock to 24 o’clock, abstracting a one-day
Terveen, L, Putting systems into place: A qualitative study of
stopover history of Figure 1
design requirements for location aware community systems,
In Proceedings of CSCW, 2004.
We also measured a trace of a college boy during 15 days (see [8] Genereux, R.,Ward, L., and Russell, J. The behavioral
Figure 11). He started to work a part time job at Gang-Nam (i.e. component in the meaning of places, Journal of
downtown Seoul). On the first day (July 1st) at downtown, the Environmental Psychology, 3, 1983, 43-55.
level (3) address was labeled for his visit (i.e. “YEOKSAM” in
[9] Kramer, B. Classification of generic places: Explorations
Figure 11) because he had 4 visit records in his history (P1 to P4).
with implications for evaluation, Journal of Environmental
After one week from the first visit, he visited there three more
Psychology, 15, 1995, 3-22.
times in different days. These visits make P1 boundary be the
prominent one, and the most prominent landmark (i.e. [10] Ochieng, W. Y., Quddus, M. A., and Noland, R. B.
“Minbyungcheol language academy”) in P1 will be the label of Positioning Algorithms for Transport Telematics
his visit. After one more week, he visited there 5 times in total and Applications, Journal of Geospatial Engineering, 6 (2), 2005,
the boundary should be shifted to a new boundary Q1, which has 10-30.
a new prominent landmark (i.e. “Pizza house”) at last. This case
ubiPCMM06:2nd International Workshop on Personalized Context Modeling and Management for UbiComp Applications
[11] Lea, J. H., Ryu, H. S., and Bae, S. H. Reducing the GPS-call [13] Srinivasan, R. and Jovanis, P. P. Effect of selected in-vehicle
incidences by tracking the mobile pseudo-noise patterns, route guidance systems on driver reaction times. Human
Samsung Tech. Conference, 2005. Factors, 39, 1997, 200-215.
[12] Wickens, C. D., and Hollands, J. G. Engineering psychology [14] Thorndyke, P. W., and Hayes-Roth, B. Spatial knowledge
and human performance (3rd). Prentice-Hall Inc., 2000. acquisition from maps and navigation. Paper presented at
the meetings of the Psychonomic Society, San Antonio, TX,
(Nov. 1978).