Cell-based positioning for improving LBS

Markus Ray

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

Markus Ray

Figure 3: Example for visualizing prominent places in GoogleEarth. Yellow rectangles indicate the composition of cell-based positions for prominent places.

Step-by-step, for each hour of day, the visiting frequencies of the prominent places are compared and the prominent place with the highest representation is selected for the sequence. In order to avoid toggling in the sequence at transition times of one prominent place to another, smoothed distributions are used for prominent place selections.
A typical daily routine of a work day of an Austrian employee (All volunteers are Austrian) is manually defined as

i) being at home (at night/early morning), being at work (in the morning)

ii) being somewhere else (in the afternoon/evening) and

iii) being at home (in the evening/night)

From this daily routine three classes of prominent places ‘home’, ‘work’ and ‘spare time’ are derived. Hence, the sequence which is to be compared to the computed sequence is {‘home’, ‘work’, ‘spare time’, ‘home’}.
For classification, the first element of the computed sequence is taken and labeled with the first element of the manually defined sequence. By assuming the computed sequence is {‘unknown 3’, ‘unknown 2’, ‘unknown 1’, ‘unknown 3’} – ‘unknown3’ is labeled to ‘home’. The same is done with the next element (here ‘unknown2’ is labeled to ‘work’). Finally all other elements of the computed sequence are classified as ‘spare time’ untilthe end is reached (Here ‘unknown 1’ is labeled as ‘spare time’). Once-classified prominent places are not re-classified.

Experimental results

validated by a 250 000 cell-based positioning data set obtained during a half year of permanent observation. Eleven of twelve home locations (92%) and nine of ten work locations (90%) have been found and correctly classified (Two volunteers moved their home during observation phase). Each volunteer has validated the result based on her provided cell-based positioning data with respect to the correctness of found and classified prominent places. All found prominent places are close to the real location. Geographical accuracy of the found places mainly depends on the cell-network distribution in the surrounding area and cannot be influenced by the used method. Hence, no quantitative validation about the localization quality was performed.
In Figure 3 is an example for visualizing the results in Google Earth. This visualization was used to validate the results together with the volunteers.
The demonstrated grouping and classification results are promising and can be used as basis for improved LBS.

Acknowledgements
The author gratefully acknowledges the support of the Austrian Mobile Phone Provider “mobilkom austria” by providing a web interface for obtaining cell-based positioning data for free. The author also thanks the volunteers for providing their position information over this long time period.

References

[1] Ray, M. and Schrom-Feiertag, H.: Cell-based Finding and Classification of Prominent Places of Mobile Phone Users, In: Proceedings 4th International Symposium on Location Based Services & TeleCartography, November 2007

[2] Zhou C., Frankowski D., Ludford P., Shekhar S. and Terveen L.: Discovering Personally Meaningful Places: An Interactive Clustering Approach, In: ACM Transactions on Information Systems, Vol. 25, No.3, Article 12, July 2007

[3] Hightower J., Consolvo S., LaMarca A., Smith I. and Hughes J.: Learning and Recognizing the Places We Go, In: Proceedings of Ubicomp’05, 2005

[4] Ashbrook D. and Starner, T.: Using GPS to learn significant locations and predict movement across multiple users, In: Proceedings of Personal and Ubiquitous Computing 7, 2003

[5] Marmasse N. and Schmandt
C.: Location-aware information delivery with commotion, In: Proceedings Second International Symposium on Handheld and Ubiquitous Computing (HUC).
Volume 1927., Springer-Verlag, 2000

[6] Nurmi P. and Koolwaaij J.: Identifying meaningful locations, Submitted to: Conference on Mobile and Ubiquitous Systems: Networking and Services, 2006.

[7] Laasonen K.: Clustering and prediction of mobile user routes from cellular data, In: Proceedings of the 9th European Conference on Principles and Practice of Knowledge Discovery in Databases (PKDD). Lecture Notes in Artificial Intelligence, vol. 3721. Springer-Verlag, 2005.