As mobile devices are to be with the users, they offer the promise of new applications, such as users' gazetteers discovery [6] and life-log presentation [14,11,12]. Cellular phones are the most promising device because users carry their mobile phones together almost all the time. Our research concentrates on the acquisition of personal gazetteers with using mobile phones with Global Positioning System (GPS) equipment.
A personal gazetteer records places that are meaningful for a specific person [6]. References [7,8] argued for the advantages of personal gazetteers which are based on a notion of place, rather than physical location.
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: Bun-dang (My home): latitude (37.34831), longitude (127.1176) Yong-in (work): latitude (37.22959), longitude (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 [2]. Now that standard mobile phones can be harnessed with a GPS chipset, GPS calls can track the user's location more accurately than the Pseudo-Noise (PN) signals given from near base stations can do [5,1,3,4]. 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 [2,4,5]. We assume a new way to reduce the regular GPS-call rates into irregular and low rates by deciding the proper GPS-call times according to PN signal patterns. Before we suggest our method, we had better look over the mobile network system.
The wireless network for a mobile phone system is built upon an underlying cellular architecture [1,3,4,5]. The service area is sectioned into a collection of cells, which are serviced by different 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 connection of the mobile switching center, base station controllers, and base stations, along with the air-link between the base stations and the mobiles forms the collector network. The collector network is interconnected by the backbone of the Personal Communication Service (PCS) network consists of the wire-line networks (such as Integrated Services Digital Network: ISDN, Public Switched Telephone Network: PSTN, and the Internet).
The mobile switching center broadcasts a page message over a designated forward control channel via the base stations in a set of cells where the mobile is likely to be present. All the mobiles listen to the page message, and only the target phone sends a response message back over a reverse channel. In case no response message from the mobile is available, the system has to page the limited number of paging channels. To put an upper bound on the amount of location uncertainty, a mobile is made to report from time to time, called a location update.
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 [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 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 [1,4,5].
To put an upper bound on the amount of location uncertainty, many location management approaches use a probability model for the user's passage [4,3,1]. The mobile's last known position and its surroundings are also considered to guess the most probable current position. That is, the probability decreases in an omni-directional way, inversely proportional to the increasing distance from the last known position.
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. Gang-Nam) 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. [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 movietheater." Gang-Nam area (i.e. the southern downtown of Seoul) has many offices and coffee-shops for social networks.
Also GPS systems have difficulties in tracking locations in urban canyons due to poor satellite availability [10]. Owing to high buildings in the built-up area like Gang-Nam, GPS receivers may acquire a less number of satellites, which may be insufficient to obtain good precision. However, Pseudo-Noise signals (or cellids) of mobile phones have little line-of-sight (LOS) issues that make GPS less effective in urban canyons than in plains. The field test trajectory is shown in Figure 1. We designed four pathways and passed along them twice, each in different days. The pathways were gone repeatedly during eight days for checking the consistency of cell-id patterns at the same areas in different periods of time. We drove a car at about 5 to 60 km/h speeds, in order to simulate both walking and driving conditions. 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). 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 [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 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 [14]. We might recall this order in how we gained knowledge about the layout of the city where we live. At first, we remember the appearance of prominent landmarks in a region -the house with a funny shape, the nice smelling bakery, etc. Next, we learn the proceduralized verbal knowledge of how to get from one place to another, that is, route knowledge. Finally, we draw an accurate or abstract map of the environment. This is survey knowledge, which represents geographical knowledge generalized across many experiences [12]. 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 ubiPCMM06:2nd International Workshop on Personalized Context Modeling and Management for UbiComp Applications 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.
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.
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 1 st ) 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.