Dynamic clusters
| industrial collaborators: | Motorola |
| academic collaborators: | ESGI64 |
| initiated : | 2008/06/05 |
| last updated: | 2010/05/25 |
Study group report 2008: dynamic clusters (Motorola)
This is the final report on the problem of dynamic location of phone call clusters, brought to ESGI64 by Motorola. Click on the link at the bottom to download the full report as a pdf document.
Report coordinator
Tristram Armour (Industrial Mathematics KTN)
Executive summary
When mobile handsets are making a call, a measurement report is sent to the serving base station periodically which includes the signal strengths to the base station and the next six strongest signals of the surrounding base stations. Motorola asked the Study Group if it was possible to say whether we could use this information to infer if phone calls occur in clusters and if it was possible to determine the locations, size and other features of these clusters. The Study Group found clusters in 'signal space,' that is, handsets reporting similar signal strengths with
the same base stations and explored methods of locating these clusters geographically.
Introduction
A common problem in cellular systems is identifying the locations of users on the system. Although mobile handsets incorporating GPS systems do exist, their use is far from widespread and likely to remain so until battery-life problems are solved. In addition, GPS does not function well inside buildings or in heavily built-up areas, and may only provide a crude estimate of location.
Position estimation is often performed to provide individual users with location-specific information - for example proximity to shops or stations - or to provide contextual advertising or mapping assistance. The Study Group was asked to analyse the traffic distributions and densities rather than the locations of individual subscribers: is the traffic evenly spread over the serving area, or are there localised clusters of heavy traffic for example, at station or theatre exits? Are these clusters static, or do they change over time? What is the size of these clusters, and how accurate are the estimates of the cluster location and size? Furthermore, can the distribution of the subscribers be classified as in-building or outdoor by observing the data? Additional classification of the traffic would be to cluster the users in terms of their mobility (static/pedestrian/vehicular) and distribution in the vertical.
The information gathered from the clustering analysis would be invaluable for network operators wishing to determine where they should be integrating additional network capacity, for example through the introduction of picocells, femtocells, and WLAN access points. Combining the cluster information with call models and sample tariffs can provide detailed business plans to support analysis of likely return on investment.
Mobile handsets (MS) are usually in contact with one or more base stations (BS) during and between calls. The mobile measures the received signal strength from nearby base stations and attempts to access the BS with the strongest signal when a call is to be established. As the user moves around the system, the varying signal strengths received from neighbouring BSs are recorded by the mobile and reported to the serving BS. If the user moves out of the coverage area of the serving BS, a handover can be performed which allocates the MS to a new serving BS.
The MS sends the RSSI (Received Signal Strength Indication) information back to the serving BS in the form of periodic measurement reports (MR). The primary function of the MRs is for handover and mobility control; however it is possible to sample and store the MRs by analysing the communication links from the BS to its controller (RNC), or by call-trace techniques at the BS itself. In this way a large number of MRs can be captured from the entire population of MS in an area being served by a group of cells. Many techniques have been proposed and implemented which attempt to derive the MS location from the MRs, commonly based around a triangulation approach or TDOA (time difference of arrival). Although these techniques can be effective in some situations, there are a number of problems to be solved. Firstly, there may only be RSSI information from the serving cell (and no other neighbours) for many MS. Secondly, the BS in a GSM system are unsynchronised and their timing references may drift relative to each other, introducing
Figure 1: A measurement report being sent to the serving base station.
errors in the timing measurements reported by the MS. Thirdly, the signal received by the MS is attenuated by other factors such as Rayleigh and Rician fading caused by obstructions, multipath scattering, and also Doppler effects caused by mobility. The combined effects of all these factors need to be considered when producing a location estimate for a specific MS.
Data
The GSM data we were given was a subset of MRs reported to a base
station in a ten hour period. Every 480 ms, each handset making a call sends an MR to the serving BS containing the signal strength (power) of the serving BS and 6 strongest signals from the neighbouring BSs, the signal quality (related to the bit error rate) and the timing advance (TA) to the serving base station. The timing advance is an integer and is a synchronisation variable which enables the handset to send the data to the correct time slot allocated for the handset at the serving base station. If TA = n, the handset is approximately between 550n and 550(n + 1) metres from the serving BS along the strongest signal path. (Each TA unit represents 3.69 μs shift in the time slot which corresponds to approximately 1100 m difference to the round-trip distance.) We would like to use this information together with the signal strengths to produce a better estimate of the location of the handsets.
There are two types of base stations, some are omni-directional i.e. the power output is evenly spread over 360 degrees from the BS whilst others are directional. The directional antennae concentrate their signal in a 120 degree arc. So at any one BS location, we could have one omni-directional BS or three directional BSs. Together with the MR data, we had the location (latitude and longitude coordinates) and power output of each BS and the azimuth for the directional antennae BSs.
Signal space and physical space
Although each MR only reported up to six of the strongest signals from the neighbouring BSs, there were 52 different neighbouring BSs recorded in the whole data. We can think of a measurement report as a projection from the 'signal space' in R^53 to a seven-dimensional subspace. Each point in this signal space may map to several different points in the 'physical space' where the handsets are located.
Proposed solution
Using a high dimensional cluster analysis technique we can try and identify clusters in the signal space. Using extra information in the MRs, we can start to analyse the cluster and possibly split the cluster up further depending on what we find. For example, if the cluster moves rapidly in signal space with time, we could assume that the handsets are moving. However, this may not be true in all cases - for example, if a rumour spread through a crowd, a cluster in signal space would be moving even
though the people themselves remain still. If we find that some handsets of the cluster have a weak signal quality (related to the bit error rate) compared to the others, we could conclude that there is a cluster indoors and one outdoors.
Further work is required to verify whether clusters in signal space correspond to clusters in physical space. However, with some careful analysis of the clusters and their MRs we could map these signals into physical space using for example, the triangulation method proposed in the report in section 2.3.
Click on the link below to view the full report.
