PROCEEDINGS OF THE 1st WORKSHOP ON POSITIONING, NAVIGATION AND COMMUNICATION (WPNC04)

Hybridised Positioning Algorithms in Location Based Services

Abstract - There is an increasing demand to accurately and quickly determine the position of a mobile terminal, at low cost. Location Based Applications are becoming increasingly popular and available, and provide the user with a wealth of information based on their location. This paper describes different techniques proposed for locating users. An algorithm is then derived for deciding the best method based on user circumstances and requirements, known as a hybridisation technique. The initial phase of the concept has been implemented in the IST project LoVEUS which is described here. Finally the results and the scope of future steps are provided.

INTRODUCTION

There are a variety of methods available to locate the user, such as cell-ID, RxPowerLevels, GPS, Assisted-GPS (AGPS), Angle of Arrival (AOA), Time of Arrival (TOA), and Observed Time Difference on Arrival (OTDOA). These methods will be discussed in this paper, comparing their relative advantages and disadvantages. For different types of services at different times, it may be better to use one method over another. This depends on various factors including Required accuracy level Locality (urban, rural, GPS coverage blackspot) Required time for getting the position Cost

The major factor to be considered is the scenario that the user is faced with. For example a greater degree of accuracy is required for giving the user walking or driving directions while they are moving, than for locating nearby hotels. The techniques available are also important: if the user equipment has GPS functionality available as some emerging mobile handsets do then the location accuracy would be greatly improved over a handset that does not include GPS. Some of the techniques considered require specific infrastructure in the mobile network operators network. As users roam between networks while they travel, it is important that positioning can take place based on the techniques available at the time a request is made. The cost of the positioning is also a key influence, in order to satisfy users and the mobile network operator.

101

PROCEEDINGS OF THE 1st WORKSHOP ON POSITIONING, NAVIGATION AND COMMUNICATION (WPNC04)

EXISTING POSITIONING TECHNIQUES

2.1 Cell-ID In this method the serving cell identifier (cell-ID) is used to locate the user. The accuracy in this method depends upon the radius of the cell. For urban areas, e.g. in a large city, this may be a few hundred metres; in rural areas it could be up to 30km. 2.2 Cell-ID and RxPowerLevels This information is used to locate the mobile subscriber with good accuracy and high speed. The mobile terminal gathers information concerning the serving cell and the power level received from it. Along with the same information about other cells in the locality, this data is passed back to a server within the network operators network (this is done over the internet over GPRS or UMTS). The network server then calculates the position of the user based on the positions of the cell base stations and the power at which they are transmitting. 2.3 Global Positioning System (GPS) The GPS positioning method measures the distance from the satellites to the receiver by determining the pseudo ranges (code phases). The system extracts the time of arrival of the signal from the contents of the satellite transmitted message. It then computes the position of the satellites by evaluating the ephemeris data at the indicated time of arrival. Finally it is possible to calculate the position of the receiving antenna and the clock bias of the receiver by using this information. 2.4 Assisted Global Positioning System (A-GPS) The basic idea of assisted GPS is to establish a GPS reference network whose receivers have clear views of the sky and can operate continuously. This reference network is also connected with the cellular infrastructure, and continuously monitors the real-time constellation status and provides precise data such as satellite visibility, ephemeris and clock correction, Doppler, and even the pseudorandom noise code phase for each satellite at a particular epoch time. At the request of the mobile phone or location-based application, the assist data derived from the GPS reference network is transmitted to the mobile phone GPS receiver to aid fast start-up and to increase the sensor sensitivity. Acquisition time is reduced because the Doppler versus code phase uncertainty space is much smaller than in conventional GPS due to the fact that the search space has been predicted by the reference receiver and network. This allows for rapid search speed and for a much narrower signal search bandwidth which enhances sensitivity 2.5 Angle of Arrival (AOA) This requires a minimum of two base stations with directional antennae. It measure the angle of arrival of signals, coming from a particular mobile subscriber, at the two base stations, and from this can calculate the users position. This is illustrated in the figure below:

Figure 1 Angle of Arrival [2]

102

PROCEEDINGS OF THE 1st WORKSHOP ON POSITIONING, NAVIGATION AND COMMUNICATION (WPNC04)

2.6 Time of Arrival (TOA) The Time of Arrival method locates the mobile terminal by triangulation from a minimum of three base stations. Because the speed of electromagnetic waves is known, it is possible to calculate the distance from each base station by observing the time taken to arrive. This method assumes that all transmitters and receivers are perfectly synchronised and ignores reflections or interference that will affect the position accuracy. The time of arrival method is shown in the figure below:

Figure 2 Time of Arrival [2] 2.7 Observed Time Difference on Arrival (OTDOA) Although a mobile phone is only ever registered with a single base station at any one time, it is constantly exchanging data with other nearby base stations. This allows it to be handed over quickly and efficiently if and when it moves out of the current cell's coverage area. By measuring the time difference in the reception of a transmitted signal at three different base stations, a phone's relative distance from each station can be calculated. From these figures, the mobile phone's location can be determined. Each OTDOA measurement for a pair of downlink transmissions describes a line of constant difference (a hyperbola) along which the UE may be located. The UE's position is determined by the intersection of these lines for at least two pairs of Node Bs. The accuracy of the position estimates made with this technique depends on the precision of the timing measurements; the relative position of the Node Bs involved and is also subject to the effects of multipath radio propagation. No specific hardware support, either hardware or software, is required in the mobile phone. However, a major hardware investment by the network operator is needed to support OTDOA in a GSM network. The reason is that GSM base stations are not synchronised with each other and it is not possible, without additional hardware, to measure the relative times at which signals are received at the base stations. To overcome this problem, additional network elements that simply transmit a beacon signal from fixed known locations are needed. These beacon transmitters are called Location Measurement Units (LMUs) and effectively allow base stations to synchronise with one another. Because of the need for LMUs, and because mobile phones are not always within range of three base stations, OTDOA isn't a particularly attractive technology for GSM networks. In theory, though, it is capable of an accuracy of between 50 and 200 metres. In a 3G network, however, base stations are synchronised, so the need for LMUs is obviated. Furthermore, because the cells are smaller, the likelihood of a mobile phone being within range of three base stations is increased and an accuracy of around 20 metres is achievable.

103

PROCEEDINGS OF THE 1st WORKSHOP ON POSITIONING, NAVIGATION AND COMMUNICATION (WPNC04)

2.8 Handset vs. network based Of the techniques, some are implemented solely on the network side, and some can work on the handset independently of the network (e.g. GPS). A comparison of accuracy in different environments is depicted below (Figure 3). The engine for positioning presented in this paper allows for the use of network and handset based positioning techniques, and pays particular attention to those which combine both types. For example, a technique has been developed in which the mobile terminal collects information concerning the serving cell and its neighbours, and the signal power level received from each. This data is then passed to a server within the operators network which can calculate position based on the locations of these cells, and the power transmitted. This solution offers a good degree of accuracy, at minimal cost for the user (a few Kbytes of data transferred) and low infrastructure cost for the operator (one server connected to the internet and the network operations centre).

Hybrid Handset Improving Accuracy Network

Figure 3 - Hybridised Techniques

COMPARISON

The first step for setting a decision criterion among the available options is to identify the relevance of each technique with regard to user requirements. Although the demand for location based services will grow, the limited network and handset resources should be managed among all running services. Hence it may be quite appropriate at some time to allocate large resources to accurate positioning, while at other times tracking the user within an urban cell may suffice. The following table depicts this comparison for different methods.
Table 1 - Comparison of positioning techniques

Method Cell-ID Cell-ID-RxPower GPS A-GPS Angle of Arrival

Coverage (Urban/Rural) Good/good Good/good Moderate/good Moderate/good Good/moderate

Time of Arrival Good/low Observed Time Moderate/low Difference on Arrival

Accuracy Cost Cell radius Server in network TBD (expected to Server in network; be 30-200m) software on handset 5-50m Hardware in handset 5-50m Hardware in handset; reference receivers in network 50-300m Directional Antennae and servers in network 50-200m Servers in network 50-200m Servers in network

104

PROCEEDINGS OF THE 1st WORKSHOP ON POSITIONING, NAVIGATION AND COMMUNICATION (WPNC04)

From the table above it is apparent that the use of higher accuracy techniques requires further modifications in both hardware and software components of the handset and the network. AOA and OTDOA methods, however, require many more modifications in the network side, since introduction of new network elements is necessary. A-GPS, on the other hand, requires moderate modifications: the introduction of a GPS reference receiver in the BTS/Node B side is required. It can therefore be concluded that if the Cell-ID based method can be more accurate, its combination with A-GPS will be very attractive.

HYBRIDISATION

The natural progression from the above conclusions is to evolve the positioning methods into a hybrid solution. The basic idea of the hybridisation is to combine the position methods in such a way so as to fully exploit their strong points, compensate for the weaknesses, and provide the most appropriate and economical position solution according to the requirements set by the applications. In considering techniques for the hybridisation it is wise to design a system with scalability and future positioning techniques in mind. Behind the algorithm is a powerful database that can be frequently updated with details of positioning techniques, scenarios etc... The algorithm selects the appropriate technique based on the application scenario at the time the request is made. In order to understand more about the hybridisation, the following section provides details about an implementation of the algorithm for a real application.

IMPLEMENTATION

A reduced version of the engine is currently being implemented as part of an EU IST project, Location Aware Visually Enhanced Ubiquitous Services (LoVEUS). This is using readily available positioning techniques (Received power levels and Cell-ID from the network side and GPS from the handset side) to provide location information to a real application (LoVEUS). The LoVEUS application provides the user with personalised, tourism-oriented multimedia information related to the location and orientation within cultural sites or urban settings, occasionally enriched with relevant advertisements. A digital compass is combined with all positioning methods. It gives the orientation of the device. This is an additional requirement, since the LoVEUS application targets at markets that are interested in very accurate positioning and detailed navigation. The positioning algorithm does not use the information received from the digital compass, which is sent directly to the LoVEUS application. The picture below (Figure 4) is a high-level description of the hybrid positioning algorithm proposed. As mentioned previously, the methods selected to provide positioning information are Cell-ID, GPS and assisted GPS when available from the network. CellID can provide the initial position of the mobile equipment quickly, whereas GPS gives a more accurate position but has longer acquisition times and its operation consumes a significant amount of power from the handset. Assisted GPS gives a solution to the long response times and therefore the power consumption problem.

105

PROCEEDINGS OF THE 1st WORKSHOP ON POSITIONING, NAVIGATION AND COMMUNICATION (WPNC04)

GPS
Longitude, Latitude

A-GPS

Longitude, Latitude

COORDINATES (3GPP 23.032/ NMEA 0183)

Motorola Positioning Algorithm

ORIENTATION (NMEA 0183 standard)

Cell-ID

Digital Compass

orientation

Magnetic Displacement (Future)

Figure 4 Hybridisation algorithm in LoVEUS [3] The algorithm needs to select the most applicable positioning method. The selection criteria are the accuracy that the application requires and the power consumption that the user is likely to be willing to sacrifice for the application. The principle of the selection mechanism is choosing the fastest and most power-saving solution from the ones which can satisfy the quality requirement in the position request.

CONCLUSIONS

This paper explains different techniques for locating a user mobile, and proposes an algorithm for hybridising these methods, based on the transient user requirements. It draws on the results of the IST LoVEUS project, locating the user using Cell-ID, RxPowerLevel and GPS. As the adoption of location-based services on mobile devices increases, the choice of positioning algorithms will become more important. A hybrid solution, using the most appropriate method in a given situation will be beneficial to both the network operator and their potential customers. Future work will concentrate on incorporating more methods and hybridising them into a unified algorithm, which would choose the best option in given circumstances.

ACKNOWLEDGEMENTS
The LoVEUS consortium (Intracom S.A, Greece; Road Editions S.A, Greece; Ogilvy Interactive, Greece; Universite Catholique de Louvain, Belgium; Motorola Ltd., UK; Oy Arbonaut, Finland; Fraunhofer IGD, Germany; Vodafone, Greece).

REFERENCES
[1] Federal Communications Commission, Enhanced 911, URL: http://www.fcc.gov/911/enhanced/ [2] Yilin Zhao, Mobile Phone Location Determination and Its Impact on Intelligent Transportation Systems, IEEE Transactions on Intelligent Transportation Systems, Vol. 1, No. 1, March 2000 [3] LoVEUS internal documents, URL: http://loveus.intranet.gr/ [4] Geng Ren, The Hybridisation of Cell-ID and GPS Position technologies in 2/2.5G Cellular Network MSc paper, Motorola and University of Exeter, 2003
106