This paper presents a solution to a problem of reducing the GPS call incidences to record personal gazetteers and of adjusting the granularity of localization on different distance scale according to visiting experiences. Personal gazetteers usually list and describe users' important places, such as home, work, restaurants, etc. The important places for mobile users can be easily logged by fixedrate GPS calls. But frequent GPS calls consume the battery of a cellphone, so it is important to reduce the GPS call incidences without the loss of location accuracy. We found out that the pseudo-noise (PN) signals of mobile phones show stable patterns to estimate the places along the users' path. According to these stable patterns, we can get the proper GPS call times both when the PN signals show whether the user stays long enough in his/her point of interest (POI) and when he/she changes significantly his/her location. The real road experiments demonstrate the effectiveness and applicability of the GPS call reduction of this algorithm, and it is found to produce reliable personal life patterns of POIs. After getting the patterns of POIs with reduced GPS calls, naming the places is required. This paper also presents a usercentric model of addressing the gazetteers, which will be adapted as the visiting rates of the same visited places increase. Familiarity breeds concerns with the polished scalability of the address naming.
C.3 [Special purpose and application-based systems]: Microprocessor/microcomputer applications; H.4.2 [Types of Systems]: Information systems applications – decision support.
As mobile devices are to be with the users, they offer the promise
of new applications, such as users’ gazetteers discovery [
A personal gazetteer records places that are meaningful for a
specific person [
We briefly define places as a textual label and some sort of geometric representation, such as a point, a set of points, or a region. For example, my personal gazetteer might include places such as:
(127.8298)
In Korea, one degree of the latitude verges on 114.64 km, while
one degree of the longitude borders on 88 km. (Readers can
imagine that my work place is not far from my home.)
The complexity of the mobility tracking problem in a cellular
environment has been reduced by the Global Positioning System
(GPS) usage [
However, using GPS calls regularly within a cellphone device
may result both to the interruption of the main communication
function and to the fast consumption of a mobile battery [
The wireless network for a mobile phone system is built upon an
underlying cellular architecture [
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. In this paper, we look at the mobility tracking solution with PNs or cell-ids. This outlook provides the insight to design an adaptive onset time of GPS satellite call. Learning the cell-id patterns endows the PN signals with a predictive power which reduces the frequent GPS calls. Then, we will discuss a user-centric address model to label the POIs according to the familiarity (or the increasing visit frequency) of users with visited places.
The service area under a mobile switching center is partitioned into location areas (LA). The base stations must broadcast the location area id (along with the cell-id) to the mobiles as a part of the update scheme.
A mobile phone must update whenever it crosses location areas,
which are formed by non-overlapping grouping of neighboring
cells—governed by each different base station [
Each base station broadcasts three cell-ids, ranging from 0 to 512 and using only even numbers. There are relations among the three α ,β ,γ
) as follows: α + 168 β ± 168 mod mod 512 512 = β
= γ
A cellphone receives many PNs (or cell-ids), more than three,
from several base stations which locate within the user’s location
area (LA). Depending on the factors such as the LA partitioning,
the call arrival rate and the user’s mobility, the main PN (called
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
shift makes it hard to estimate the LA assignments with only PN
patterns [
To put an upper bound on the amount of location uncertainty,
many location management approaches use a probability model
(1)
for the user’s passage [
We do not consider the probability model of the passage in this paper, however. We assume that the cell-id patterns will reveal the underlying location areas in a reliable manner, nevertheless, with the noises of temporary shifts.
We chose urban built-up areas for the field test on cell-id patterns.
Especially we chose the southern downtown of Seoul (i.e.
GangNam) where is the most famous area for works and entertainments
in Seoul (and many handovers and transient shifts are expected).
Researches in environmental psychology show that people
naturally structure their experience around personally or socially
meaningful places, such as homes, offices, schools, churches,
coffee-shops, pubs, etc. [
From the eight-day experiments with four major districts (i.e. 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 calls at lower rates than at regular fixed-rates. The next section will explain the algorithm of finding proper GPS onset times from the mobile PN patterns.
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. As long as a mobile phone locates in a location area, the two topmost pseudo-noise signals (i.e. PN1 & PN2) show stable cellid patterns (see Figure 3 & 4) which lead to a fact that one GPS call (i.e. the red star in Figure 5) is enough to mark this location area, rather than the four times regular calls (i.e. the yellow stars in Figure 5). In this paper, a procedure to determine the GPS onset times from the mobile cell-ids and to match the GPS location up with the map for personal gazetteers was developed and used (see Figure 6). There are four parts of our methods: the pseudo-noise receiving/sorting part, the pseudo-noise comparison part, the position determination/decision part, and the position determination/map-matching part. The pseudo-noise receiving/sorting part receives the pseudo-noise signals from several base stations, and then sorts them in accordance to their signal strengths. The two topmost pseudo-noise signals are recorded and get stored in a PN database.
The pseudo-noise comparison part fetches the previous pseudonoise signals from the PN database, and compares them to the current cell-ids (or pseudo-noise signals). It determines whether a steady tendency exists or not.
The next step is the position determination/decision part. This part calculates the duration time of steady patterns of PN1 and PN2. If the duration is over the threshold which can filter the temporary handovers and fluctuations, it looks into past histories of the associations between pseudo-noises and GPS locations. If there is no GPS location matching with the requested pseudo-noise (or cell-id) and if the duration of steady patterns is over the threshold, the GPS system finally activates and gets the location coordinates. The final part is the position determination and map-matching part. In many circumstances, the GPS coordinates are noisy and imprecise because urban built-up areas can hardly acquire the sufficient signals from both GPS satellites and pseudo-noise from nearside base stations. And also the digital map can suffer from incomplete information such as missing street segments, etc. Thus it needs to snap correctly the estimated location to the map position in order to name the GPS position with proper tags (or textual labels).
At the next section, we develop a customized way of naming the points-of-interest (POIs), considering the users’ habituation of the location areas.
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 [
Also we can easily conjecture that labeling the nearest address of the GPS coordinates is not enough for users to easily understand the locations, such as “111 AA-street, BB city,” “98 AA-street, 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 users. We may use some human factor to make a useful improvement in the automatic POI addressing.
People who repeatedly visit an area will gradually gain knowledge
in the order: landmark, route, survey [
This tendency of getting an accurate mental representation of a familiar environment leads to different aids (or labeling methods) depending on the level of familiarity with the visited regions. In this paper, we can implement the differential method of labeling location as follows: We divide the full address into four parts and use appropriate part for the context familiarity level. For example, instead of using the full address “108 Wilmot Road, Deerfield, IL USA,” we divide this address into four parts (see Figure 7).
Many countries use different address labeling systems. North and South America use roads as the references of address system. Swiss and Korea split lands into small parts with arbitrary boundaries, and sub-divide the parts into the smaller ones if there are new houses or buildings to be constructed. United Kingdom matches the names of districts with postcodes. France uses a clock-wise numbering system starting from centers. Japan prefers the block system and includes the building names in its address, sometimes. German combines the block and road system. Although there are the differences in the address systems, we can roughly apply a division into four parts with the context applicability of area granularity – it depends on the real size of the corresponding sections’ lands. That is, the GPS granularity is about 10 m radius, and it implies that at the finest fourth part a nearest building or a street name will be matched with the GPS coordinates. 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. However, even in the case we are familiar with the (3) area, we would not use the naming (4), because it does not give us a clear clue to the location (unless it is the user’s home address) and it is the most GPS error-prone among the address level. Rather using the exact house number, we use the nearest prominent landmark for this case.
To decide the nearest prominent landmark in the neighborhood, we first set a priority list for the prominence. We categorize the class of buildings, road-shapes, transport stations/stops, etc., and give priority to them. Second, we decide the neighborhood boundary to search the nearest prominent landmark. We can set a rough boundary with our method mentioned in 3.1. Then, as the number of visits increases, the boundary will be segregated into 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.
From our data (i.e. recording 15 days), we found that every fifteen-minute comparison of PN patterns was enough to differentiate POIs (Points of Interests) of the user’s passage. Fifteen-minute duration is good at filtering the temporary shifts of pseudo-noise signals.
We show the reduction of GPS call frequencies of our method, comparing to regular rate sampling (per one hour) (see Figure 5 & 10).
Without using some probability model for the user’s passage, our methods show reliable differentiation of POIs on the passage. Furthermore, our methods reduce the GPS call incidences ten times lower than the regular rates of every fifteen minute. We also measured a trace of a college boy during 15 days (see Figure 11). He started to work a part time job at Gang-Nam (i.e. downtown Seoul). On the first day (July 1st) at downtown, the level (3) address was labeled for his visit (i.e. “YEOKSAM” in Figure 11) because he had 4 visit records in his history (P1 to P4). After one week from the first visit, he visited there three more times in different days. These visits make P1 boundary be the prominent one, and the most prominent landmark (i.e. “Minbyungcheol language academy”) in P1 will be the label of his visit. After one more week, he visited there 5 times in total and the boundary should be shifted to a new boundary Q1, which has a new prominent landmark (i.e. “Pizza house”) at last. This case example shows a useful convergence of personal gazetteers with a GPS-equipped mobile device.
This paper has presented a useful method to save the power consumption of GPS calls within mobile systems. Our method in 3.1 also uses the reliable patterns of pseudo-noise signals given from base stations within the location areas. These location areas usually match to the personal and social points-of-interest (POIs). Our method in 3.2 solves the GPS-error prone situation of the nearest address labeling. Therefore, the personal gazetteers may list the POIs with interesting patterns of stopover history both in a map with reasonable boundaries and in textual labels with gradual convergence of the user’s life pattern. Using our methods may develop many possible ways of presenting the mobile users’ life patterns. One example of the personal gazetteer with our methods is given in Figure 12.