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).