[attachment=3398]
Simple Hardware-Oriented Algorithms For Cellular Mobiles Positioning
A.Pratheep kumar (Y7CS801)
A.Chandra Shekar Reddy (Y7CS805)
A.Jaya Lakshmi (Y7CS811)
R.V.R. & J.C. COLLEGE OF ENGINEERING
ACHARYA NAGARJUNA UNIVERSITY
GUNTUR - 19
ABSTRACT
Locating a mobile station position is one of the most significant features of cellular mobile phones in wireless communications. All location determination algorithms are based on trigonometric calculations which are usually implemented in software. we propose two new hardware oriented algorithms that use just simple add, shift and subtract operations in finding the location of a mobile station. The first algorithm uses fixed rotations to locate a mobile station position. The second algorithm is a dynamic version of the first one. It uses dynamic rotations to find the location of the mobile. Via simulation, the computational cost and error (in meter) for the traditional algorithm, the fixed rotation hardware-oriented algorithm, and the dynamic version are compared.
ACKNOWLEDGEMENT
The successful completion of any task would be incomplete without a
proper suggestion, guidance and environment. Combination of these three factors
acts like backbone to our term paper Simple Hardware-Oriented
Algorithms For Cellular Mobiles Positioning.
We regard our sincere thanks to our principal, Dr.P.S.Sankar Rao for providing support and stimulating environment. We would like to express our gratitude to the management of R.V.R & J.C College of Engineering for providing us with a pleasant environment and excellent lab facility.
We are greatly indebted to Dr. B.Raveendra Babu, Professor and HOD, Department of Computer Science and Engineering for valuable suggestions during course period. We express our sincere thanks to Mr A.V.Sri Nagesh, for timely help, guidance and providing us with the most essential materials required for the completion of this report and gave us moral support .
We would be thankful to all the teaching and non-teaching staff of the department of Computer Science & Engineering for cooperation given for the successful completion of term paper.
A. Pratheep kumar (Y7CS801)
A. Chandra Shekar Reddy (Y7CS805)
A. Jaya Lakshmi (Y7CS811)
TABLE OF CONTENTS
ABSTRACT
ACKNOWLEDGEMENT
LIST OF FIGURES
LIST OF TABLES
TERMS AND ACRONYMS
Chapter 1 INTRODUCTION
Chapter 2 CELLULAR LOCATION METHODS
2.1 Cell Identification
2.2 Signal strength
2.3 Angle of Arrival
2.4 Uplink time (difference) of arrival
2.5 Downlink observed time differences
2.6 Enhanced Observed Time Differences (E-OTD)
2.7 Observed Time Difference of Arrival (OTDOA)
Chapter 3 HYBRID METHODS
3.1 Angle of Arrival + Round Trip Time (AOA+RTT)
3.2 OTDOA + AOA
Chapter 4 HANDSET-BASED GPS LOCATION OF MOBILE
TERMINALS
4.1 GPS Overview
4.2 DGPS
4.3 Assisted GPS
Chapter 5 DATABASE CORRELATION
5.1 Generic location method
5.2 Application to GSM
Chapter 6 THE TRADITIONAL ALGORITHM
Chapter 7 HARDWARE-ORIENTED ALGORITHMS
7.1 Fixed vector rotation.
7.2 Dynamic vector rotation.
Chapter 8 SIMULATION RESULT AND ANALYSIS
Chapter 9 CONCLUSION
References
TERMS AND ACRONYMS
2G Second generation cellular mobile system (GSM)
3G Third generation cellular mobile system (UMTS)
3GPP Third Generation Partnership Project
AOA Angle of Arrival
BCCH Broadcast Control Channel
BS Base Station
BSC Base Station Controller
BTS Base Transceiver System
CBC Cell Broadcast Centre
CDMA Code Division Multiple Access (UMTS)
CPICH Common Pilot Channel
DCM Database Correlation Method
DGPS Differential GPS
DL Downlink
E911 Enhanced 911 (wireless Enhanced 911 emergency call
service in United States)
E-OTD Enhanced Observed Time Difference
ETSI European Telecommunications Standards Institute
FCC Federal Communications Committee
FDD Frequency Division Duplex
GDOP Geometrical Dilution of Precision
GMLC Gateway Mobile Location Centre
GPS Global Positioning System
GSM Global System for Mobile communication
HLR Home Location Register
HMM Hidden Markov Model
IPDL Idle Period Downlink
LAH Location-Aided Handover
LAM Location-Aided Mobility Management
LAP Location-Aided Planning
LCS Location Services
LIF Location Interoperability Forum
LMU Location Measurement Unit
LOS Line of Sight
MGIS Mobile Geographical Information System
MLC Mobile Location Centre
MS Mobile Station (Mobile phone)
MSC Mobile Switching Centre
NLOS Non-Line of Sight
OTDOA Observed Time Difference of Arrival
PCF Position Calculation Function
QoS Quality of Service
RTD Real Time Difference
RTT Round Trip Time
SA Selective Availability
SACCH Slow Associated Control Channel
SFN System Frame Number
SIM Subscriber Identification Module
SMLC Serving Mobile Location Centre
SMS Short Message Service
SPS Standard Positioning Service
SRNC Serving Radio Network Controller
TA Timing Advance
TA-IPDL Time Aligned-IPDL
TDD Time Division Duplex
TDMA Time Division Multiple Access
TDOA Time Difference of Arrival
TOA Time of Arrival
TS Technical Specification
TSG Technical Specification Group
UMTS Universal Mobile Telecommunication System
(CDMA)
UTRA UMTS Terrestrial Radio Access
UTRAN UMTS Terrestrial Radio Access Network
VLR Visitor Location Register
VMSC Visited Mobile Switching Centre
CHAPTER 1
INTRODUCTION
Recently, the wireless networks are growing rapidly throughout the world. Mobile users are increasing at incredible rates as they have different applications and services in their cell phones. In addition, mobile producers are providing lots of new and different services and applications. One of the most important new services is location-based services and applications. Therefore, chiefly in the US, the Federal Communications Commission (FCC) has regulated that all wireless communication service providers must be able to find mobile phonesâ„¢ position making emergency calls 911 with an accuracy of better than 125m rms, requesting for E-911 service.
Determining the mobile station position is divided to two main categories, network-based and mobile-based schemes. In network based implementation one or several base stations (BSs) make the necessary measurement results to a location centre where the position is calculated. The most significant advantage of network-based scheme is that handsets are not required to be changed for using the location services. However, these methods have high network cost and low precision. In the mobile-based scheme, the mobile station uses its received signals to do its calculation for finding its position. Although the mobile based schemes do not support old handsets, they have higher position precision.
Many methods for finding MSâ„¢s location have been proposed and discussed in the literature [1-16]. These include cell identification [1,2,3,5,8], angle of arrival (AOA) [3,4,7,8,10,12], time of arrival (TOA) [1,2,3,4,7,9-12] time difference of arrival (TDOA) [3,4,7,8,10,12], assisted global positioning system (AGPS) [3,7,8,11], enhanced observed time difference (EOTD) [3,6,11], received signal strength (RSS) [8,14], and more [3,9,10]. All of these methods use trigonometric computation to find the location of handset. Survey and comparison of these methods have been investigated in [10] and [8]. Besides, different proposed hybrid methods like combination of AOA and TOA or TOA and TDOA are discussed in [15] and [16].
consider the fixed rotation hardware-oriented algorithm followed by the detailed description of the dynamic rotation hardware-oriented algorithm. In section 4, we show our simulation results for the traditional algorithm, the fixed rotation hardware-oriented algorithm, and dynamic version. In section 5, the conclusion is presented.
CHAPTER 2
CELLULAR LOCATION METHODS
Cellular location methods use the signals of the cellular system to find the location of a mobile station. Since cellular systems were not originally designed for positioning, the implementation of different location methods may require new equipment to make the necessary measurements for location determination and new signalling to transfer themeasurement results to the location determination unit. Before presenting the cellular location methods and their implementation aspects, some concepts that will be used to classifydifferent methods based on the role of the mobile station (MS) and the network or on thelocation measurement principle are defined.
Based on the functions of the MS and the network, implementation of a location method belongs to one of the following categories:
¢ Network-based
¢ Mobile-based
¢ Mobile-assisted
In network-based implementation one or several base stations (BSs) make the necessary measurements and send the measurement results to a location centre where the position is calculated. Network-based implementation does not require any changes to existing handsets,which is a significant advantage compared to mobile-based or most mobile-assisted solutions.However, the MS must be in active mode to enable location measurements and thus positioning in idle mode is impossible.
In mobile-based implementation the MS makes measurements and position determination.This allows positioning in idle mode by measuring control channels which are continuously transmitted. Some assisting information, e.g. BS coordinates, might be needed from the network to enable location determination in the MS. Mobile-based implementation does not support legacy handsets
The third category, mobile-assisted implementation, includes solutions where the MS makes measurements and sends the results to a location centre in the network for further processing. Thus, the computational burden is transferred to a location centre where powerful processors are available. However, signalling delay and signalling load increase compared to a mobilebased solution, especially if the location result is needed at MS. Although mobile-assisted solutions typically do not support legacy handsets, it is possible to use the measurement reports that are continuously sent by GSM handsets to the network in active mode. Techniques that use these measurement reports, e.g. signal strength measurements, are often classified as network-based since they do not require any changes to existing handsets. Nevertheless, it is the MS that makes the measurements and therefore these techniques will be called mobile-assisted in the following.
The requirements set by different applications may favour different kinds of implementations. For example, emergency call location requires high reliability and it is highly desirable to locate these calls from legacy phones as well as new phones. Applications that use continuous tracking, e.g. route directions, require high accuracy and fast location with a fixed update rate.Since the location result is needed at MS in this case, these requirements are best met with a mobile-based solution. Some applications, e.g. traffic monitoring and location-aided networkplanning (LAP), require mass location capability at network. These requirements can only be
met by network-based or mobile-assisted implementations. Another classification is based on the measurement principle . The measurement principle of each method belongs to one of three categories:
¢ Multilateral
¢ Unilateral
¢ Bilateral
In multilateral techniques, several BSs make simultaneous (or almost simultaneous)
measurements. Multilateral measurement principle leads to network-based implementation.Unilateral means that the MS measures signals sent by several BSs and thus leads to mobilebased or mobile-assisted implementation. For bilateral techniques multiple measurements are not needed: either MS measures signal from a single BS or one BS measures signal from MS. This does not exclude any of the three implementation categories. Since multilateral techniques require co-ordination of simultaneous measurements at multiple sites, unilateral techniques are generally better for capacity and signalling load. Bilateral techniques are optimal for rural coverage since only one BS is involved.
2.1 Cell Identification
The simplest method for locating a mobile phone is based on cell identification. Since this is an inherent feature of all cellular systems, minimal changes to existing systems are needed. The cell ID only has to be associated with location, i.e. the coordinates of the BSs must be known (see Figure 1). This is a bilateral location principle that can be implemented as a network-based or mobile-based technique. In mobile-based implementation, the network would have to continuously transmit the coordinates on a control channel.
Figure 1. Positioning based on cell identification.
Another advantage of this method is that no calculations are needed to obtain location
information. Thus, cell ID based location is fast and suitable for applications requiring highcapacity. The drawback is that accuracy is directly dependent on cell radius, which can bevery large especially in rural areas. In dense urban areas location accuracy is considerably better due to the small cell radius of micro- and picocells. Nevertheless, this method is notaccurate enough for the purposes of CELLO project, since LAP, LAH and LAM all requiresub-cell position accuracy. Accuracy can be improved using information of cell coverage area(e.g. sector cells) and timing advance (TA) in GSM or round trip time (RTT) in UMTS. Even with these enhancements the accuracy is probably too low for CELLO applications.
2.2 Signal strength
Using signal strength measurements from the control channels of several BSs, the distances between the MS and the BSs can be estimated. Assuming two-dimensional geometry, an omnidirectional BS antenna, and free-space propagation conditions, signal level contours around BSs are circles. If signal levels from three different BSs are known, the location of the MS can be determined as the unique intersection point of the three circles. However, practical propagation conditions especially in urban areas are far from free-space propagation. Therefore, an environment-dependent propagation model for the dependence of received signal level on BS-MS distance should be used. In urban areas the received signal levelgenerally decreases more rapidly with distance than in open areas.
Multipath fading and shadowing poses a problem for distance estimation based on signallevel. The instantaneous, narrowband signal level may vary by as much as 30-40 dB over a distance of only a fraction of the wavelength. Random variations of this order of magnitude cause very large errors in distance estimates. However, fast fading can be smoothed out by averaging the signal strength over time and frequency band. Time-averaging only has a minor effect, due to the motion in the surrounding environment, if the MS is stationary. Contrary to fast fading, the random variations caused by shadowing can not be compensated. Thus, the variations in antenna orientation and local shadowing conditions around the MS (indoors, inside a vehicle etc.) are seen as random errors in distance estimates and consequently in position estimate. Location accuracy also depends on the accuracy of the propagation model
and the number of available measurements.
Signal strength method is unilateral and can be implemented as mobile-assisted or mobilebased method. Mobile-based implementation requires that BS coordinates are transmitted to the MS. Signal strength method is easy to implement in GSM, based on measurement report (see Table 1, p. 15) that are continuously transmitted from the MS back to the network in active mode. Therefore, it does not require any changes to existing phones, and is often calleda network-based method although it is the MS that performs the measurements. An alternative implementation is to modify the MSs to enable sending measurement reports in idle mode also. GSM phones with this capability are already available. Signal strength is an easy and low-cost method to enhance the accuracy of pure cell ID based location.However, it is questionable whether the accuracy is adequate for CELLO applications.
In UMTS DL the BSs send the common pilot channel (CPICH) with constant power of 33 dBm (10% of the max power). CPICH is unique in each cell and always present in the air. Before any other transmission each MS monitors the CPICH. Thus, each MS is able to measure the power levels of the nearest BSs common pilot channels. In UMTS, signal strength measurements may be slightly more reliable due to the wider bandwidth, which allows better smoothing of fast fading. On the other hand, the hearability problem preventsmeasurements of as many neighbouring BSs as it is possible in GSM.
2.3 Angle of Arrival
Signal angle of arrival (AOA) information, measured at the BS using an antenna array, can beused for positioning. Assuming two-dimensional geometry, angle of arrival measurement at two BSs is sufficient for unique location. This is illustrated in Figure 2, where the user location is determined as the point of intersection of two lines drawn from the BSs. It is seen that AOA technique requires line of sight between the MS and the BSs for accurate results. Also, the uncertainty in AOA measurement causes a position uncertainty that increases with MS-BS distance. Achieved accuracy depends on the number of available measurements, geometry of BSs around the MS and multipath propagation also.
Figure 2. Positioning with angle of arrival measurements.
Since AOA method needs line-of-sight propagation conditions to obtain correct location estimates, it is clearly not the method of choice in dense urban areas where line of sight to two BSs is seldom present. In [32], an rms location error of approximately 300 m with two BSs and 200 m with three BSs in an urban environment was observed. However, the AOA technique could be used in rural and suburban areas where the attainable accuracy is better and it is an advantage to be able to locate a MS which can only be measured by two BSs.
A major barrier to implement AOA method in existing 2G networks is the need for an antenna array at each BS. It would be very expensive to build an overlay of AOA sensors to existing cellular network. However, since it is a network-based method and supports legacy handsets, it is developed by several companies as an E911 solution. In 3G systems AOA measurements may become available without separate hardware if adaptive BS antennas (arrays) are widely deployed.
In addition to financial issues, AOA method may have a capacity problem. Multilateral measurement principle (measurement at several BSs) requires the co-ordination of almost simultaneous measurements at several BS sites, and it is difficult to serve a large number of users.
2.4 Uplink time (difference) of arrival
Signal time of arrival (TOA) measurements, performed either at the BSs or at the MS, can be used for positioning. If the BSs and the MS are fully synchronised, TOA measurements are directly related to the BS-MS distances and three measurements are needed for unique 2D location. However, if the network is not synchronised, such as GSM and UMTS FDD networks, TOA measurements can only be used in differential manner. Even in this case, a common time reference for the BSs is needed. Two TOA measurements then define a hyperbola, and four measurements are needed for unambiguous 2D location.
If the measurements are performed at BSs, it is a network-based multilateral technique. This technique has two drawbacks compared to downlink method: it is only possible to perform the measurements in dedicated mode and there may be capacity problems due to the multilateral measurement principle. The advantage is that due to the network-based implementation, uplink TOA supports legacy phones. It was taken into GSM standardisation as a candidate E911 solution [21]. In GSM implementation of uplink TOA technique, a common time reference, e.g. GPS receiver, is needed at each BS site. The location of an MS with call on is
accomplished by forcing the MS to request a handover to several neighbouring BSs. The MS then sends access bursts at full power, and TOA measurements are made from these bursts.
2.5 Downlink observed time differences
In the downlink time difference techniques, the MS observes time differences of signals from several BSs. These signals are typically control channel signals and therefore the MS can perform the measurements in idle mode as well as in dedicated mode. The clock differences of the BSs can be solved by having a reference receiver at known location continuously measuring the observed time differences. This is much simpler and more economical than synchronising the BS transmissions.
The accuracy of all time difference based techniques (uplink as well as downlink) depend on several factors. The accuracy of an individual time difference measurement depends on signal bandwidth and multipath channel. This is illustrated in Figure 3 with an error margin for each time difference measurement. In an urban area the error margin is typically larger, since heavy multipath makes it more difficult to detect the time of arrival of the first echo. If there is no line of sight between the MS and the BSs involved, the location estimates will be biased away from the BSs with no line of sight to the MS (see Figure 3). This is a problem especially in urban areas. In open areas the geometry of the BS configuration around the MS may introduce an additional error, which is described by geometrical dilution of precision
(GDOP). A favourable geometry is a uniform distribution of BSs around the MS. Also the number of available measurements has an effect on accuracy: generally it is better to have as many measurements as possible.
Figure 3. Positioning based on time difference measurements in open (left) and urban environment (right).
UMTS bandwidth is 5 MHz and it operates at a high chip rate 3.84 Mcps/s, which contributes to the better resolution in timing measurements compared to GSM. The timing resolution in UMTS with one sample per chip is ~0.26 µs which corresponds to the propagation distance of ~78 m. In GSM (bit rate 270.8 kBits/s) the bit duration is 3.69 µs and the corresponding propagation distance is ~1100 m. Thus, the finite timing advance (TA) allows to represent absolute distances with a resolution of 554 m. Oversampling of four times the chip rate is often used in the receiver [33]. For UMTS and GSM that means sampling with a rate of 4¢3.84Mcps and 4¢270.8kBit/s respectively. Thus the timing resolutions are improved to values ~65 ns in UMTS and ~923 ns in GSM corresponding to propagation distances ~19,5 m and ~277 m respectively. In timing techniques for obtaining the needed accuracy level of the
MS position estimates, oversampling will be quite mandatory. With advanced technology, it should be possible to achieve higher sampling rates. Thus, the sampling resolution in UMTS will also affect the timing accuracy in measurements. However, the bandwidth of the signal will ultimately determine the time delay measurement accuracy and increasing sampling rate can bring only limited improvement.
The downlink observed time difference techniques are unilateral mobile-assisted or mobilebased methods. In mobile-assisted implementation, the MS sends the results of time difference measurements to a location centre, where the location is calculated based on these measurements and measurements from the reference receiver. In mobile-based implementation, the coordinates of the BSs as well as the measurement results from the reference receivers are transmitted to the MS. In GSM and UMTS standardisation, these techniques are called Enhanced Observed Time Differences (E-OTD) and Observed Time Difference of Arrival (OTDOA), respectively. These techniques will be described in more detail in the following subsections
.
2.6 Enhanced Observed Time Differences (E-OTD)
In GSM, the time difference measurements are called observed time differences (OTDs). Unlike timing advances, OTD measurements observing several BSs are made by the MS without forcing handover, which makes them more attractive for location. However, the resolution at which OTD measurements are reported is only 554 m and the required synchronisation of the BSs is not guaranteed. These problems have been solved in the enhanced OTD (E-OTD) technique.
An experimental E-OTD network architecture is depicted in Figure 4. A handset with
modified software is able to report accurate OTD estimates by using sophisticated signal processing algorithms, for example multipath rejection, for finding the earliest arriving signal component. These OTD measurements are then sent via short message service (SMS) to a mobile location centre (MLC) which performs the location calculations. The synchronisation of the BSs is achieved by installing similar receivers as the MS in known locations, typically at the BS sites, to measure the timing differences between BSs. These real time differences (RTDs) are also sent to the MLC via SMS. Disadvantages of this technique are the need for software modifications to the handsets and the need for additional receivers. In operational
use, the information transfer will take place using specific signalling messages instead of SMS.
Figure 4. Network architecture for E-OTD concept.
2.7 Observed Time Difference of Arrival (OTDOA)
The OTDOA method in UMTS is based on measuring the difference in time of arrival of the downlink signals received at the MS. The OTDOA can be operated in two modes, MSassisted and MS-based, depending on where the position calculation is carried out. The MSassisted mode, in which the Serving Radio Network Controller (SRNC) carries out the position calculation, is mandatory and available in all UMTS mobile terminals. The MS-based mode availability depends on MS position calculation capabilities and the operator, as information about the BS positions and relative time differences (RTDs) have to be sent to the MS.
In UTRA TDD mode the BSs are synchronised, but in the UTRA FDD mode the BSs transmit asynchronously, so the relative time difference (RTD) of the actual transmissions of the downlink signals is also needed for the position estimate calculation of the MS. For carrying out these RTD measurements, additional network elements, Location Measurement Units (LMUs), are required. The other way for obtaining the RTD values is by synchronising the BSs, which gives a constant RTD. The BS synchronisation has to be very accurate, as 10 ns uncertainty corresponds to 3 m error in the position estimate. In addition, drift and jitter in synchronisation timing have to be controlled. This needed level of synchronisation accuracy is not easy to achieve and currently it is only technically feasible through satellite based timetransfer technique .
Power control is used in UMTS to prevent the near-far problem occurring in CDMA-based systems. On that account the mobile in the downlink direction cannot hear other BSs when it is near to its serving BS and the needed hearability from three BSs may not be attainable. In rural and hilly areas where the density of BSs is small, hearability is a major problem. One possible solution to the hearability problem in OTDOA is the downlink idle periods.
Idle Period Downlink (IPDL)
The OTDOA-IPDL method is based on the same measurements as the basic OTDOA. In order to improve the hearability of neighbouring BSs, the serving BS provides idle periods in continuous or burst mode. In continuous mode, the idle periods are active all time and one idle period is placed in every DL frame (10 ms). In the burst mode, the idle periods are arranged in bursts and an idle period spacing is under the operator's selection, e.g. 1 IPDL every 10 frames (100 ms). The idle periods are short and arranged in a pseudo random way. With longer idle periods, the achievable accuracy would be better because of longer integration time at the MS, but the system capacity would be reduced. During these periods the serving BS completely ceases its transmission and the MS is scheduled to make the needed OTDOA measurements (SFN-SFN) from the neighbour BSs now hearable. By supporting the IPDL, the OTDOA performance in MS will improve, as there will be less interference present during idle periods. Idle periods in the downlink are standardised for the
OTDOA-IPDL method, however the support of the idle periods is optional for the MSs.
Time Aligned-Idle Period Downlink (TA-IPDL)
Time Aligned-IPDL method is a modification of the standard IPDL. In TA-IPDL the idle periods are intentionally time aligned approximately 30µs across the BSs. Time alignment creates a common idle period, during which each BS will either cease transmission entirely, typically ~70% of the time, or transmit the common pilot, typically ~30% of the time . During the common idle period, the MSs are scheduled to make the needed OTDOA measurements. In simulations, the interference level is noticed to be lower for TA-IPDL than for IPDL. Due to lower interference, TDOA estimation is more accurate, more BSs will be hearable to MS and multipath rejection is more effective. TA-IPDL reduces the handset complexity, but additional signalling is needed as well as added complexity in the network. It has also been noticed that increasing the number of measured BSs without making LOS state estimations before location estimation, the accuracy is reduced. This is due
to increased probability of using NLOS measurements, which degrade the location estimation accuracy.
CHAPTER 3
HYBRID METHODS
Hybrid location techniques combine several of the methods described above to provide positioning estimates with better accuracy, reliability and coverage, including indoor, outdoor, urban and rural areas. The hybrid techniques are not standardised and all the needed signaling in the network may not be available. The drawbacks of hybrid systems are usually greater processing requirements and increased network costs. Usually using a hybrid i.e. involving two techniques, the cost will be as high as using two separate solutions.
3.1 Angle of Arrival + Round Trip Time (AOA+RTT)
A potential UMTS location technique especially in rural and suburban areas where a LOS connection between the MS and the serving BS is often present, is AOA-RTT hybrid in which even one BS is enough for location estimation. It is a bilateral network-based method that avoids the hearability problem since a single BS, equipped with an antenna array, can make the necessary measurements.
The location estimate accuracy of this technique is limited by the beamwidth of the antenna array and RTT resolution. As with AOA method, the location error will increase with BS-MS distance.
3.2 OTDOA + AOA
In UMTS, the OTDOA measurements will be available in every MS and deployment of antenna arrays will enable the AOA measurements without extra costs. The performance of both OTDOA and AOA techniques is decreased due to NLOS conditions. Even though the errors in AOA measurements due to NLOS conditions are correlated to the errors affecting the timing measurements involving the serving BS, they should be useful to the location estimation. the UMTS system using TA-IPDL has been simulated and the results show an improvement of 20%-60% in location error performance when using the available AOA data in rural, suburban and urban car scenarios.
Using the OTDOA-AOA hybrid the MS positioning may be made possible even in highly NLOS conditions or by measuring only two BSs. The accuracy of the hybrid is better than OTDOA or AOA alone and the coverage increases if two BSs are enough for location. Also, it avoids problems with high GDOP, e.g. in a highway scenario where the BSs are aligned with the highway. In this case, pure AOA positioning would suffer from dilution of precision.
CHAPTER 4
HANDSET-BASED GPS LOCATION OF MOBILE TERMINALS
For the last 5 years the FCC Report and Order has been the main driver for the adoption of Location Services by Mobile operators. The FCC clearly requires that wireless carriers be able to locate any caller requesting emergency assistance throughout its network. This requirement would appear to eliminate handset-based solutions, such as GPS, from consideration, as it would not be to integrate GPS or other location system components to all phones operating on a network by October 2001. In December 1997, however, FCC issued a supplementary notice (Memorandum and Opinion) showing that it would endorse a gradual
deployment of the location capability, especially if the proposal would help achieve higher levels of accuracy, and performance guarantees. The memorandum concludes that FCC will consider allowing the addition of GPS to new phones to meet Phase II requirements, recognising that most subscribers would be likely to replace their existing phones with GPSequipped handsets over a two- to three-year period.
4.1 GPS Overview
GPS is a Satellite Navigation System funded by and controlled by the US Department of Defense (DoD). Despite the large base of millions of civil users of the system world-wide, the system was designed for and is operated by the US military personnel. GPS provides specially coded satellite signals that may be only processed by a GPS receiver, enabling the receiver to compute position, velocity and time.
The basic measurement performed by a GPS receiver is the time required for a signal to propagate from one point in space to another. Because in the general case, the speed that RF signals travel is known with relative accuracy this time measurement can easily be converted to distance -range from the RF source. If the range from the receiver to four satellites is calculated, the receiver can accurately determine his position anywhere on earth. Four (4) GPS satellite signals are thus used to compute positions in three dimensions and the unknown time offset in the receiver clock. The system allows the military users to make use of an enriched signal set, achieving a much better guaranteed accuracy than civilian receivers may achieve.
The system's operation relies primarily on the GPS satellites. A number of 24 LEO-SV (Low Earth Orbit - Satellite Vehicles) are positioned in such orbits as to cover almost all of the earth surface, while at any time 4 to 6 are on stand-by in orbit to replace malfunctioning. They complete one full rotation about the Earth every 12 hours.
The users of the system take advantage of special purpose GPS receivers to convert the signals into position, velocity estimates, while the receiver may be also used as a highly accurate timing source. GPS receivers are used for navigation, positioning, time dissemination, and other research. Civil users worldwide use the Standard Positioning Service (SPS) without charge or restrictions.
According to the 1999 Federal Radionavigation Plan the predictable accuracy for GPS amounts to 100m (for 95% of the measured samples) horizontal accuracy and 340nsec timing accuracy (95%). These figures are however out-of-date since following May 2000. In thatdate, the main error source affecting the system, the "Selective Availability" - i.e. the intentional degradation of the system accuracy, was turned off by the US DoD. Figures and experience since that day show a ten-fold decrease in Expected Position Errors.
Figure 5. GPS Estimates over a 24h period for Static Receiver (SA Activated - prior to May 2000).
Although indispensable as the fundamental navigation system for use by the marine
community and recently by the aviation world, the system is not as well adapted for urban use as the system will need to have direct visibility (Line-of-Sight conditions) with the satellites used for the position calculation. This requirement immediately excludes the use within buildings or even in dense urban roads. Measurements in a typical route in the suburbs of Athens (the peripheral ring road) show the obvious low availability of visible satellites. It is remarkable that although the type of environment remains the same throughout the measuring period, there are cases that the number of received satellites will drop to as low as 3, allowing only 2D positioning.
Received Satellites Variation (Suburban)
Figure 6 - GPS satellite visibility, sub-urban environment
Further enhancements to the plain civilian positioning service are the techniques known as Differential GPS and Assisted GPS which we examine in the following. These techniques promise to effectively improve system performance parameters such as accuracy, time-tofirst-fix and coverage especially in the case where the system will be used in dense urban environments to provide location information and location-based services.
4.2 DGPS
The idea behind differential positioning techniques is to correct systematic bias errors at one location based on measured bias errors at a known position. In the case of DGPS a reference receiver, or DGPS Base Station (not to be confused with a GSM BS - although the two may be co-located), computes corrections for each satellite signal received. The DGPS Base Station then transmits the corrections to the co-observing receivers.
Because individual pseudo-ranges must be corrected prior to the formation of a navigationsolution, DGPS implementations require software in the reference receiver that can track all SVs in view and form individual pseudo-range corrections for each SV. These corrections are passed to the remote, or rover, receiver (i.e. the handheld) which must be capable of applying these individual pseudo-range corrections to each SV used in the navigation solution. DGPS removes common-mode errors, those errors common to both the reference and remote receivers (unlike multi-path or receiver noise). The following table summarises the main error sources, 95% estimates (2drms) of these errors and how these affect the overall estimate calculated by GPS with SA activated (as was the typical case before May 2000), without SA and in the case of differential GPS. The total horizontal error is also provided for comparison with the DGPS providing by far the most accurate estimate.
Table 1: Factors of inaccuracies in the horizontal position (Horizontal Dilution of
Precision = 2)
Differential position accuracy of a meter or even sub-meter level are possible with DGPS based on civilian (SPS) signals. Improvement in User Estimated Position Error (UEPE) is immense as may be seen in the next figures.
Figure 7 - GPS Positioning error over a 24h period (SA Activated - 10min. samples) - Trimble Electronics
Figure 8 - Differential GPS Positioning error over a 24h period (SA Activated - 10min.samples) - Trimble Electronics
For the purpose of locating a cellular terminal the reference station may be considered to be located at the BTS or even at the BSC/MSC, remaining within 100km from the served terminals. This condition guarantees that both the reference and the remote receiver are identically affected by bias errors. DGPS corrections are mostly transmitted in a standard format specified by the Radio Technical Commission Marine (RTCM) Special Committee SC-104 ver. 2, in 1990.
4.3 Assisted GPS
Assisted GPS methods aim to assist the handset in estimating its own position using GPS (and thus are categorised as handset-based / network-assisted). Such technologies - already market available - make it possible to receive GPS satellite data even at signal levels below known thresholds, allowing in some cases the estimation of users' positions even when user is indoors. Most methods require a additional circuitry in wireless phones and special purpose server. The handset passes GPS pseudorange measurements to the server, which estimates the caller's location. A variation of this method automatically updates the - embedded in the terminal - GPS receiver, with up-to-the-hour ephemeris information.
FIGURE 9- RANGE OF COVERAGE
Table 2: Major Technologies Table
Technology Handset impact Accuracy
Cell ID none Depends on the size of the cell
100m-3km
Cell ID + TA none 500m
TDOA none 100-200m
AOA none 100-200m
EOTD yes 20-200m
GPS/AGPS yes 5-30m
CHAPTER 5
DATABASE CORRELATION
5.1 Generic location method
Database Correlation Method (DCM) [19] is a generic location method that can be applied to any cellular network. The key idea is to store the signal information seen by a MS, from the whole coverage area of the location system, in a database that is used by a location server. The database should contain signal information samples, called fingerprints, with a resolution comparable to the accuracy that can be achieved with the method, and this resolution may vary in different environments. Depending on the particular cellular system, the signal fingerprints could include signal strength, signal time delay, or even channel impulse response. Any location-dependent signal information that can be measured by the MS is useful for the DCM technique. Also, it is possible to use measurements performed by the network as well as by the MS. When the MS needs to be located, the necessary measurements are performed and transmitted to the location server. The location server then calculates the MS location by comparing the transmitted fingerprint and the fingerprints of the database. The architecture of a DCM location system is illustrated in Figure 5. It is highlighted that
DCM can be implemented in any wireless system, the MS only needs to be able to transmit a location-dependent fingerprint to the location server. This fingerprint may consist of signals measured from GSM, UMTS and/or GPS. The location server must be powerful enough to process all location requests in a reasonable time. In a large-scale implementation, this may require distributed processing.
The major effort in applying DCM is the creation and maintenance of the database. The signal fingerprints for the database can be collected either by measurements or by a computational network planning tool. Measurements are more laborious but produce more accurate fingerprint data. Also a combination of measured and computed fingerprints can be used. The compensation for the effort to build the database is an optimal location accuracy in environments where the assumption of line-of-sight propagation is not valid, e.g. in dense urban and indoor environments. The only assumption is that the database contains up-to-date data. However, minor changes in the network or propagation environment, e.g. new buildings, will only be seen as lowered location accuracy if the database is not updated. Also, it should be noted that similar information that is contained in the DCM database is also needed in network planning. Therefore, the creation and maintenance of the database also support
network planning.
Figure 10. Architecture of a DCM-based location system.
.
5.2 Application to GSM
The essential location-dependent parameters defined in GSM standard are Location Area Code (LAC), serving cell ID, timing advance (TA), and the measured signal strength of the serving cell and its neighbours. In dedicated mode (call on) all these parameters are known both at the MS and the network (signal strength measurements from up to 6 neighbour cells are reported from the MS back to the network). However, in idle mode only the LAC is known at the network. The MS, on the other hand, continuously makes signal strength measurements and also knows the cell ID of the strongest cell. Thus, in order to locate an idlemode MS using these parameters, the MS must be able to transmit the available parameters to the location server. GSM handsets with the capability to send these measurements through SMS are already available.
LAC, cell ID, and TA, which is known with a resolution of 554 m in dedicated mode only, can be used for rough positioning only. Signal strength measurements must be used if more accurate location is needed. The idea of using previously measured signal strength contours in location determination was first presented in [12], where it was emphasised that instead of instantaneous signal strength, the median of samples collected over a sufficiently long period should be used to avoid the effects of fast fading. In GSM, signal strength values in idle mode are averages over a period of at least 5 seconds, which is sufficient to smooth out fast fading if the MS is in slow motion. Even if the MS is stationary, the 200 kHz bandwidth of GSM assures that signal strength samples from adjacent locations vary considerably less than in the case of a single-frequency carrier wave. In a fixed position, variations on the order of 10 dB are common, but over 20 dB variations can be seen if a strong signal path, e.g. a line-of-sight path, is suddenly obstructed. Therefore, the algorithm that uses signal strength values for positioning should not be too sensitive to such variations.
The algorithm used for finding the best match between the fingerprint to be located and the fingerprints of the database was simple: the difference between two fingerprints was calculated as
where fi is the signal strength of the request fingerprint on the ith Broadcast Control Channel, gi(k) is the signal strength of kth database fingerprint on the same channel, and the summation is taken over channels that are found in both fingerprints. Each channel that is found in only one of the fingerprints contributes to the penalty term p(k). The coordinates of the database fingerprint that minimises this difference are returned as the location result. It should be noted that the database search can be limited, based on LAC and cell ID, to a relatively small area.
TOA is one of the popular methods in use. It finds location of the mobile using the intersection of three circles. Under idle condition, a traversed distance is equal to multiplication of time by speed of the light in radio wave and wireless communication.
As mentioned before, mobile-based location schemes have better accuracy than network-based schemes. However, since the MS has restricted energy power, energy consumption should be minimized. One of the significant ways to accomplish this aim is to reduce and simplify instructions for finding the mobile position. In fact the energy dissipation reduction is carried out at different levels of abstraction: from algorithm level down to the implementation [17]. With all of these facts, we propose two new algorithms for finding Mobile Station (MS) position. The major advantages of our algorithms over previous methods are speed-up, low computation and communication overhead, and implementation simplicity. That is, all operations in our proposed algorithms are simple add, subtract, and shift operations. Hence, they can be implemented in hardware which is faster than software by using for example application specific integrated circuit (ASIC) chip. It should be noticed that our algorithms assumed that we have a local coordinate system in 2D space.
CHAPTER 6
THE TRADITIONAL ALGORITHM
Traditional (geometric) algorithm uses three base stations for finding the location of mobile station as shown in Fig. 1 Therefore, according to the TOA, the MS position is the intersection of the three circles centered at BS1, BS2, and BS3 with radiuses d1, d2, and d3 respectively. The traditional algorithm can be organized as follows [18]:
First of all, it finds distances between BSs and origin point (0,0) then it determines the BS which is more adjacent to the origin and takes it as the reference BS or BS1. BS2 is rotated by angle aso that the y coordinate of BS2 becomes same as that of BS1. After that, the intersection points of rotated BS2 with BS1 are calculated, and then rotated back by angle -ato find the right intersection points. The distance between BS3 and intersection point should be calculated to choose the minimum distance as the position of MS. According to Fig. 1, angle a is calculated as:
(1)
where is d distance between BSd1 and BS2. Therefore, the new coordinates of BS2 are:
(2)
Using circle equations for BS1 and BS2, we have:
(3)
(4)
Since y1=y21, in order to find intersection points, the following equations for x and y are used:
(5)
(6)
(7)
Besides, it is required to rotate back these two intersection points (xc1,yc1) and (xc2,yc2) by a to find the true intersection points (xt1,yt1) and (xt2,yt2).
Fig. 11. Mobile and Base station positions
Finally, because we have two intersection points, the distance between BS3 and intersection points is calculated and we choose the intersection point which has the minimum distance as the true position of MS. Following formula shows the minimum distance:
(8)
CHAPTER 7
HARDWARE-ORIENTED ALGORITHMS
Our new algorithms are based on simple logic operations through vector rotation. We have proposed two different approaches to locate a mobile station position;
1. Fixed vector rotation.
2. Dynamic vector rotation.
The algorithms are based on TOA and they use the same source of information as traditional algorithm. Nonetheless, they use a different way to determine the location of the mobile.
7.1 FIXEB VEXTOR ROTATION
The main idea of the fixed rotation algorithm is to use vector rotation with a fixed step angle s=arcsin(2-k), where k depends on the needed accuracy and do the rotation recursively step by step [1,2].
First of all, the most adjacent base station to the origin is chosen as the Reference BS or BS1. Then, the coordinates of BS1 are transferred to the origin and should be done for other BSs accordingly. BS2 should be rotated according to M matrix until its y coordinate reaches to the same y coordinate of BS1.
The rotation matrix M is as follows:
(9)
The sin and cos are approximated as:
(10)
(11)
where k>=8, to guarantee the approximation precision [19]. Therefore, BS2 coordinates are recursively rotated as follow:
(12)
(13)
As seen from equations (12) and (13) no trigonometric calculations are needed for BS2 rotation, instead simple add, subtract, and shift operations are used. After rotation of BS2, using parallel vector rotation the vector d1 from BS1 and the vector d2 from BS2 are rotated until their heads reach together. The vector rotation is illustrated in Fig. 12.
Hence, the smaller vector needs more rotation. According to Fig. 2, if BS2 has larger radius than BS1, the algorithm will be as follows:
Rotation equations for d1 and d2 are:
(14)
(15)
The first intersection point is calculated when two vectors heads reach the same position (xc1,yc1). Therefore, since the second one is symmetric to the first one in x coordinate, it is calculated as below:
xc2=xc1 and yc2=-yc1 (16)
Then, the intersection points have to be rotated back by a number of steps used for the rotation of BS2. Besides, the intersection points are transferred to their original coordinates. Also, the distances between intersection points and BS3 are calculated by using parallel vector rotation. Finally, the absolute difference value of distances with d3 should be calculated and the minimal value shows the true mobile station position.
7.2 DYNAMIC VECTOR ROTATION
The fundamental of our dynamic vector rotation approach is similar to fixed algorithm. However, in comparison with fixed rotation algorithm, we have used dynamic vector rotations for determining the position of mobile station. Therefore, the coordinates of BS2 are rotated step by step (with maximum possible step rotation size si) until the y coordinate of BS2 becomes same as y coordinate of BS1. Thus, According to(the absolute difference value between the y coordinate of BSy1 and BS2), the maximum possible step size is determined, where
(17)
Therefore, while y>=e , BS2 coordinates are recursively rotated as follows:
(18)
(19)
To illustrate the algorithm, one should look back to Fig. 2 After rotation of BS2 completely, initially the vectors of BS1 (i.e. radius d1) and BS2 (i.e. radius d2) are rotated until their heads intersect each others.
x1=d1 and y1=0 (20)
x11=d2 and y11=0 (21)
Parallel vector rotation is done by using d1 and d2. Before starting parallel vector rotation, we should find which BS has the largest radius since the largest radius should be rotated first. If BS1 has the largest radius, the rotation is performed as in the below algorithm.
Fig. 12. Parallel vector rotation
Rotation equations for d1 are:
(22)
(23)
Rotation equations for d2 are:
(24)
(25)
Before rotation of vectors, the maximum step rotation angle sin (si) should be determined. Step rotation is calculated according to the distance between coordinates of vectorsâ„¢ heads. The following equation is used;
(26)
Where m is the minimum of ( k+1, k+2,¦.,n) that satisfies , so that convergence is guaranteed.
When the vectors heads intersect each others, the intersection point (xc1,yc1) is found as a result of these rotations. The second intersection point is:
xc2=xc1 and yc2=-yc1 (27)
Then, the intersection points are rotated back by using the dynamic vector rotation and they are transferred to their original coordinates. Also, the distances between intersection points and BS3 are calculated by using the dynamic parallel vector rotation. Finally, the absolute difference value of distances with d3 is calculated and the minimal value shows that the true intersection point for the mobile station position.
CHAPTER 8
SIMULATION RESULT AND ANALYSIS
We used Matlab package for the simulation analysis. We wrote programs for traditional algorithm, the fixed rotation algorithm, and the dynamic rotation algorithm.
In each of these programs, we run the algorithms hundred times with random input for different k. We investigate computational costs and errors (in meter) for different accuracies, and different k values. The weights of the operations for calculating computational costs are shown in Table I [1,2,20].
Fig. 3 shows the computational cost which is equal to number of simple operation required by each algorithm versus k (which exploits for step by step rotation (2-k) and specifies the accuracy level).
TABLE 3
WEIGHT OF THE OPERATION
Fig .13. Computational Cost Versus k number
Fig .14. Error in distance versus k number
As seen in the figure, the computational cost of the traditional algorithm has a constant performance since rotation in traditional algorithm is done in one step. In both proposed algorithms, the computational costs increase when k increases. The computational cost of the fixed rotation algorithm is lower than that of the dynamic rotation algorithm for a specific k value. Also, the computational cost for both fixed rotation and the dynamic rotation algorithms is less than the traditional algorithm for k=9 and k=6 respectively.
After finding the mobile station position, the absolute difference of the real position of mobile and the simulated one shows the error (in meter). As it is shown in Fig. 4, the dynamic rotation algorithm has less error than the fixed onesâ„¢ for a specific k value. Besides, it shows that the fixed rotation algorithm satisfies the 911 regulation for k >7 whereas the dynamic rotation algorithm satisfies the rules with k>6.
CHAPTER 9
CONCLUSION
In this paper, we presented two hardware oriented algorithms to find the position of a mobile in a cellular network. Since all operations in our proposed algorithms are simple add, subtract, and shift, they are feasible to be implemented in hardware which is faster than software processing. In addition, they are simpler rather than previous hardware oriented algorithms [2] since they use four operations (add, shift, and subtract) less than previous ones. Moreover, for a specific k, the proposed algorithms
outperform the traditional one even in terms of software implementation. This is in addition to their unique possibility for hardware implementation compared with the traditional one. Also, it should be noted that the observed accuracy level is sufficient to satisfy E-911 standards.
REFERENCES
[1] M.Najiminaini, E.Doukhnitch, M.Salamah, and I.Kale. Design and Comparison of Hardware-oriented Algorithms for Cellular Mobiles Positioning, accepted in Seventh IASTED International Conferences, Montreal, June 2007.
[2] M. Salamah, E. Doukhnitch., and D. Deniz, A Fast Hardware-Oriented Algorithm for Cellular Mobiles Positioning, LCNS, vol. 3280, Spriger-Verlag 2004, pp. 267-277, ISSN 0302-9743.
[3] H. Laitinen, and et al, Cellular Location Technology, CELLO Project Technical Report ,CELLO-WP2-VTT-D03-007-Int, 2001
[4] T. Roos, P. Myllymaki, and H. Tirri, A Statistical Modeling Approach To Location Estimation, IEEE Transactions on Mobile Computing 1(1) ,2002, pp.59-69.
[5] H. Chi, and R. Jan, Cell-Based Positioning Method for Wireless Networks, Parallel and Distributed Systems, In Proc., Ninth Int . Conf. on 17-20, 2002, pp.357-380.
[6] M. A. Spirito, On the Accuracy of Cellular Mobile Station Location Estimation, IEEE Transactions on Vehicular Technology 50(3),2001, pp.674-685.
[7] H. Koshima, and J. Hoshen, Personal Locator Services Emerge, IEEE Spectrum 37(2), 2000, pp.41-48.
[8] Y. Zhao, Standardization of Mobile Phone Positioning for 3G systems, IEEE Communications Magazine 40(4),2002, pp.108-116.
[9] A. J. Weiss, On the Accuracy of a Cellular Location System Based on RSS Measurements, IEEE Transactions on Vehicular Technology 52(6) ,2003, pp.1508-1518.
[10] I. Jami, M. Ali, and R. F. Ormondroyd, Comparison of Methods of Locating and Tracking Cellular Mobiles, IEE Colloquium on Novel Methods of Location and Tracking of Cellular Mobiles and their System Applications, 1999, pp.1/1-1/6, ISSN 0963-3308.
[11] L. Lopes, E. Villier, and B. Ludden, GSM Standards Activity on Locaion, Novel Methods of Cellular Mobile and Their System Applications (Ref No 1999/046), IEE Colloquium, London, 1999, pp.7/1-7/6.
[12] G. G. Messier, and J. S. Nielsen, An Analysis of TOA-Based Location for IS-95 Mobiles, Vehicular Technology Conference, vol. 2, 1999, pp.1064-1071.
[13] J. J. Caffery, A New Approach to the Geometry of TOA Location, Vehicular Technology Conference , Boston, MA USA, Vol.4, 2000, pp.1943-1949.
[14] A. Hatami, K. Pahlavan, M. Heidari, and F. Akgul, On RSS and TOA based indoor geolocation - a comparative performance evaluation, IEEE Wireless Communications and Networking Conference 2006. (WCNC).vol. 1, 3-6 April 2006, pp.2267-2272.
[15] S. Venkatraman, and J. Caffery, Hybrid TOA/AOA Techniques for Mobile Location in Non-Line-of-sight Environments, in Proceedings of the Wireless Communications and Networking Conference (WCNC), IEEE, vol. 1, Atlanta, GA USA, 21-25 March, 2004, pp. 274-278.
[16] T. Mahdi, , S. Dirk, R. Vincent, and F. Pierrick, Mobile terminal positioning via power delay profile fingerprinting: reproducible validation simulations VTC 64th IEEE Vehicular Technology Conference 2006, 25“28 September 2006, Montréal, Canada
[17] A. Nannarelli, and T. Lang, Low-Power Divider, IEEE Transactions on Computers 48(1), 1999, pp.2-14
[18] Weisstein and W. Eric, Circle-Circle Intersection, From MathWorld A Wolfram Web Resource. Available:
http://mathworld.wolframCircle-CircleIntersection.html
[19] G. J. Henkstra, and F. A. Deprettere, Fast Rotations: Low-cost Arithmetic Methods for Orthonormal Rotation, In: Proc. Of 13th Sym. On Computer Arithmetic, 1997, pp.116-126.
[20] J. M. Muller, Elementary Function Algorithms and Implementation, Birkhauser, 1997.
