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