Mobile Location Techniques

Mobile Location Techniques INTRODUCTION: With the rapid increase in number of mobile users, a massive number of calls originate from mobile subscribers, all over the world, everyday. With the increasing number of mobile users and originating calls, there is also an increase in emergency calls that originate from mobile stations. In many emergency cases the position is unknown to the caller, or he cannot explain properly. Thus there is a strong need to locate any mobile user in emergency situation. Hence the scope of mobile positioning is vital. Due to importance of mobile positioning, the need to locate any mobile user in emergency was also called by Federal Communications Commission (FCC) and European Countries. For instance, the Federal Communications Commission (FCC) made a proposal to include location in the 911 emergency service number, which resulted in the E911 ruling [2]. Currently, all the legacy handsets used in public cellular networks in the USA must provide the location of the customer whenever this number is dialled. The European Commission (EC) adopted a similar regulation to include location in emergency services on 112 [2]. The FCC in USA took the first step in this direction. Initially by 2001, the mobile operators are required to provide the accurate location of an emergency caller. The current requirement of FCC is to locate 67% of emergency callers must be located within 100 meters and 95% of the callers must be located with an error of no more than 300 meters. [3] Applications: Mobile location can be used for a number of services by mobile operators. Some of them are discussed here: An important application of mobile location is to provide emergency services. By knowing the location of a mobile user, emergency vehicle can be directed to that location. Hence there is an increase in public safety and services. Another interest in exploiting the mobile location is to apply location sensitive billing. By knowing the location of mobile subscribers an operator can offer competitive tariff e.g. users can be offered more calls from their mobile to home or office. Asset tracking and fleet management is another application of mobile location. Using the location of mobile travellers can be informed about location. Mobile location can be used to effectively manage fleet and traffic conditions. There are two main categories for mobile positioning,Handset Based positioning and Network based positioning. Handset Based techniques needs special type of handset hardware or the installation of specialized network software in existing handsets e.g. GPS and A-GPS. GPS receiver determines its own position by sending and receiving signals from at least four satellites. The time to reach satellite signal to GPS receiver is used as a parameter. The accuracy of GPS based systems is very high. And the coverage of satellite is very good in outdoor environment. However, drawback is inability of GPS to operate in indoor and heavily populated urban environment. GPS lacks positioning where signals of the satellite cannot be fully covered. Another problem is related to existing handsets in market. A large number of existing handsets lack the built in GPS receivers. Thus using this method a huge number of people can not get benefit or can not be located in case of emergency. Also Embedding a GP S receiver into mobile devices leads to increased cost, size, and battery consumption [1]. Thus hundreds of millions of handsets in market need to be replaced or modified. In contrast, Network Based Techniques determine the position of a mobile user by measuring its signal parameters when received at the network Base Station (BS). Here BS receives signal from Mobile Station (MS) and sends them to a central site where location estimation algorithms are used to estimate location. In this method there is no need to change or replace existing handsets. It would require change in a few thousands of network nodes (Base Stations) than to change hundred of thousands of mobile stations. Hence, it can be implemented easily, less costly using existing technology. And still can provide a very good estimate of position of a mobile user. The future technologies also support network based positioning. Infact many positioning techniques can not be implemented using existing GSM technology. Using advanced technologies their efficiency will greatly increase. The Network based positioning is also feasible for network operators as it would help them to implement location sensitive billing and location related services. Thus based on a certain location the operator can implement a specific price plan e.g. less price calls to home or office number. It will also help them to generate more revenue. Another advantage of network based techniques is the security of the subscribers. Using an algorithm at network side also ensures that the position of subscriber is known only to emergency service or mobile operator. Thus it also increases the safety and security of the subscribers. The network based techniques have several advantages like low cost, ease of implementation, implementation using existing technologies and methods, beneficial for a large number of people. However, the main issue with this technique is its accuracy. Despite a number of efforts to reduce error and increase accuracy there is still no unbiased estimation method present. All of the methods produce good results under certain conditions or circumstances. Thus there is no general prediction for result using an algorithm. The main problems in incorrect positioning are multipath propagation, fading and low SNR. The efforts are continuously being made to minimize these and hence increase accuracy and thus performance. The project will emphasize on comparing various existing network based location techniques. Some of the common techniques will be studied in detail. Base on these existing methods, a number of positioning algorithms are also studied in detail to implement major positioning techniques. The algorithms will then be implemented using MATLAB. The results of algorithms will be compared to actual position of mobile station so as to measure the performance of each of them. Final thing is to develop an online benchmarking tool to compare location evaluation estimates using different techniques. The tool should be able to run user uploaded measurements in to its own algorithms. The results will then be compared to user submitted results to perform a benchmark. Existing Literature Review A number of mobile location techniques are common nowadays. These techniques can be divided into three main types: Mobile Based Techniques Network Based Techniques Indirect Techniques These techniques are briefly explained below: Mobile Based Techniques: In this method, a number of geographically separated transmitters are used by the mobile station to exploit its own position. It is also known as Self Positioning. Thus mobile station (MS) locates itself by using signals from a number of transmitters or base stations (BS). Example of mobile based positioning is GPS and A-GPS. In GPS based positioning GPS receiver uses signals from geographically distributed satellites to exploit its own position. Network Based Techniques: This method uses a number of transmitters in a network to locate position of an unknown receiver. It uses resources of the network only. The signals from the MS are used by a number of BS to locate the MS. This technique can be implemented using different type of parameters e.g. Cell Global Identity (CGI), Cell Global Identity with Timing Advance (CGI-TA), Enhanced Cell Global Identity (E-CGI), Time of Arrival (TOA), Angle of Arrival (AOA), Time Difference of Arrival (TDOA). Indirect Techniques: In this technique mobile or network can be assisted to locate a mobile station. Thus base station can send positioning data to mobile station to locate itself. Similarly measurements can be uploaded from MS to BS to locate mobile station. It involves measurements sent from MS to BS for positioning at BS or vice versa. There are a number of network based mobile positioning techniques in use today. In such techniques a number of involved base stations (BS) use signal from mobile station (MS) to locate the position of MS. The common methods are Signal Strength, Time of Arrival, Time Difference of Arrival, Angle of Arrival, or hybrid techniques. Each of the existing method has its own advantages and disadvantages. A major problem with all methods is the accuracy. It depends on cell size, cell environment, number of cells, multipath propagations and distance between MS and serving base station. Some other common parameters for performance measurement include applicability, robustness, etc. The existing methods have been described in detail below: Cell Global Identity: The CGI method to locate a mobile user is most easy and straight forward. In this method, the position of mobile user is estimated by using the cell identity of serving base station. Thus the mobile can be located anywhere in a call coverage area. It is very simple to implement. However, the positioning error may range from a few meters to a few kilometres. The accuracy will be dependent on the size of serving base station. Another problem with this method is that mobile station is not always connected to nearest base station. In this case the location of mobile cannot be even estimated. Enhanced-CGI: To overcome errors in basic CGI technique another method is used. The basic idea was to split the coverage area of a base station into two or more areas, mostly three 120 degree areas. Each area within a base station can then be issued with a separate identity. Hence in this way the position of mobile can be narrow down to a small area. Although this method is easy to implement yet error is large enough from practical point of view. CGI with Timing Advance: The CGI technique can also be improved by using the timing advance feature of GSM. Timing advance is a value that corresponds to the time it takes for a signal to reach from MS to BS. In GSM timing advance is a feature used by the base station to synchronise with mobile station. On step timing advance is equal to a change in 1100 m of round-trip time (the time signal takes to reach from base station to mobile and then back to base station). The timing advance is assigned by base station for each mobile station. Using the timing advance feature a mobile user can be located within 550 meters approximately. Time of Arrival: Although CGI method provides a good estimation of mobile position, the error is still large enough from emergency view point. Another method to locate mobile is using the arrival time of signals at base stations involved. The distance of mobile can be estimated by using information about time of arrival i.e. D = t / c Where t is the time of arrival of signal at base station and c is the speed of light. The distance will be the estimated mobile position. However the mobile can be located anywhere on circular path centred at base station and radius equal to estimated distance D. The exact position of mobile can be estimated by using same type of measurements from two other neighbouring base stations. Ideally the positioning circles from all the three base stations must intersect at a point, which will be the position of mobile. However, practically, the circles dont intersect at a single point rather they make a small area in which the mobile is potentially located. This method is really better than CGI because it gives more accurate results. The time of arrival method requires accurate synchronization or reference between mobile and base station to correctly measure the arrival time. The results, however, depends on environment of cell clutter, atmospheric conditions, and multipath propagation. In worst atmospheric conditions the results may vary severely. Angle of Arrival: In this method the position of the mobile is located by using the direction of signal arriving from mobile station to the serving and, at least one other base station. The direction or angle of arrival is measured at base station by using arrays of antennas. Angle measurement at one base station will give the position of mobile to be located at a straight line at a certain angle with base station. Measurement from another involved base station will produce another positioning line. Ideally the mobile must be located at the intersection of two lines from involved base stations. In practice, however, they may not intersect at all at a single point. The angle of arrival is good because it can be implemented using a small number of base stations. Thus it is best when the number of base stations visible to mobile is very low. The angle of arrival method is very sensitive to measurement errors of angle. So a very small error in angle measurement results in a much larger error in position o f mobile. Time Difference of Arrival: The time of arrival method requires a strict synchronisation or reference between mobile and base station. To overcome this problem, the difference of arrival time at a pair of base station is used for measurements. A pair of base stations is used to record one time difference measurement. The result will be a circle on which mobile can be anywhere. Ideally the three circles will intersect at one point. This point will be the position of mobile. In actual practice the method will give a small area in which mobile must be located. The difference of arrival time eliminates the need of synchronisation as required by time of arrival. This method can be used as to run entirely on network side or to run with mobile assistance. The performance of time difference method is greatly improved than time of arrival. The main advantage of this method is elimination of timing requirement. However, on the other hand, the number of involved base station must be at least four including primary base st ation. Thus only then three sets of measurements can be obtained. The time difference of arrival method is more frequently used due to ease of implementation. Data correlation method: The Database Correlation Method makes use of the signal information seen by mobile station. The signal information from all of the coverage area seen by mobile station is stored in a database at network side. The signal information may include signal strength, signal timing, signal delay etc. When position of the mobile is required, the stored data in database is used by a positioning server to do so. The signal measurements sent to the database depends on the environment. The resolution of such measurements must be set so as to achieve certain accuracy. In GSM a sub-band resolution is used by the Base Station Controller (BSC) to facilitate the handover process. Pilot Correlation Method: Algorithms Search: There are a number of positioning algorithms in present literature. These algorithms make use of the measurements done by the mobile station. The measurements required for each algorithm may vary. However, some common measurements may include Cell ID, LAC, Signal Strength, Timing Advance, Time of Arrival, and Direction (Angle) of Arrival. Also these measurements may be carried out only on network side i.e., by primary base station or they can be performed with assistance of mobile station. The algorithms for all of the major positioning methods are studied in detail. Although there is a large number of algorithms in literature yet each of them has own advantages and disadvantages. Each algorithm is based on some assumptions and limitations. For this reason we can not say which one is best. But the one which gives acceptable accuracy is thought to be the good one. Cell Global Identity (CGI): The Cell ID is the very basic method to locate mobile station. It is used to make a rough estimate of mobile position. With this method the mobile can be located anywhere within a cell. Thus the accuracy is very poor. The mobile station measures periodically the id of serving base station and up to 6 neighbouring base station. Thus no special algorithm is needed to locate Cell ID. By looking at mobile measurements the Cell ID can be located. Enhanced Cell ID: Due to very poor accuracy of basic Cell ID, a number of enhancements have been made to it. Thus measurements like signal strength, Timing Advance can be used in conjunction with Cell ID to improve accuracy. Two algorithms which show good results are Enhancement to CGI using Signal Strength and Positioning using Timing Advance. In the first algorithm the signal strength is taken as a parameter. The power received by mobile station from primary base station and up to six neighbouring cells is feedback to primary base station. The primary base station thus knows the power transmitted by it and power received by mobile station. Then the distance calculation is possible by using the known path loss. Using Okumura-Hata Path Loss model [4] the distance between mobile and base station is calculated. The mathematical form of this model is [4]; Urban areas: LdB = A + B log10 R E Suburban areas: LdB = A + B log10 R C Open areas: LdB = A + B log10 R D A = 69.55 + 26.16 log10 fc 13.82 log10 hb B = 44.9 6.55 log10 hb C = 2 (log10 (fc / 28))2 + 5.4 D = 4.78 ( log10 fc )2 + 18.33 log10 fc + 40.94 E = 3.2 ( log10 ( 11.7554 hm ))2 4.97 for large cities, fc = 300MHz E = 8.29 ( log10 ( 1.54 hm ))2 1.1 for large cities, fc E = ( 1.1 log10 fc 0.7 ) hm ( 1.56 log10 fc 0.8 ) for medium to small cities Definition of parameters: hm mobile station antenna height above local terrain height [m] dm distance between the mobile and the building h0 typically height of a building above local terrain height [m] lhbbase station antenna height above local terrain height [m] rgreat circle distance between base station and mobile [m] R=r x 10-3 great circle distance between base station and mobile [km] f carrier frequency [Hz] fc=f x 10-6 carrier frequency [MHz] ? free space wavelength [m] This model is fairly simple so it is used for a large number of situations. The distance calculation is easy from this model using known path loss in pre-defined environment. The mobile will be located anywhere on the circle of estimated distance with centre at base station. A minimum of three base stations are used for such measurements. Ideally the three circles will intersect at a single point. This point will be the position of mobile station. The triangulation technique is used to find the intersection coordinates of circles. Time of Arrival: Although CGI provides the position of mobile station yet the accuracy is not sufficient for many purposes. To improve accuracy the time of arrival method is used. It gives good results than CGI in most of the situations. A number of algorithms describing time of arrival method are in literature. Each of them has some advantages and some short comings. Also each algorithm works best under some specific conditions e.g. in line of sight (LOS) or non-line of sight (NLOS) conditions. A good algorithm which gives acceptable results in many situations is A Constrained Least Squares Approach to Mobile Positioning: Algorithms and Optimality. This algorithm uses a least square approach to estimate position of mobile station. The distance between mobile station and base station is estimated by using the fact that signals travel in free space at a speed equal to speed of light. Thus mathematically, Di =Ti / c i = 1, 2 N Where D is the estimated distance, T is the TOA measurement, i denote the number of base station and c is the speed of light. The mobile station will be located anywhere on the circle with radius D centered at base station i. Same TOA measurements are performed by at least three base stations. The position of mobile will be the intersection of three circles. Ideally this will be a single point. But in practice, due to multipath propagation and fading, it will give a small area. The mobile station will be located in this area. To reduce positioning error the algorithm uses a least square error approach. Thus the distance between every point in that area and each mobile station is calculated. The point where the sum of squares of distances is minimized will be the estimated position of mobile station. To get TOA measurements, base station and mobile station must be synchronized properly or there must be a reference point. Thus a strict timing requirement is necessary. Angle of Arrival: In LOS conditions this method is the best to use. A number of algorithms describing this method are in literature. All of these algorithms require a dominant LOS path to correctly perform angle of arrival measurements at base station. Thus this method is best in open areas and suburban areas. In dense urban environment this technique produces severe errors due to NLOS and multipath propagation. A number of algorithms are studied in detail. A good algorithm is A Constrained Least Squares Approach to Mobile Positioning: Algorithms and Optimality. It produces results with acceptable accuracy. According to this algorithm, to perform angle of arrival measurements, base station must be provided with multiple antenna arrays. A minimum of two base stations will be required to perform such measurements. The signal from mobile station will reach base station at a certain angle with horizontal axis. This angle can be measured by base station using antenna arrays. Mathematically, it is given by tan (fi) =(y yi / x xi) , i = 1, 2, . . . , M. The angle of arrival measurement from one base station will result in a straight line. This line is also called Line of Bearing (LOB). It will be at a certain angle between horizontal axis and base station. The mobile will be located any where on the LOB. A similar measurement will be done using another involved base station. It will result in producing another angle of arrival or LOB. The point where the two line of bearing intersects will be the position of mobile station. Ideally two lines will intersect at a unique point. However, practically they may not intersect at a point. In this situation the angle of arrival method need further measurements from other involved base station. This method produces very accurate results in LOS situation. However, the results depend critically on the measured angle. Thus a very small error in angle measurement may lead to positioning error of hundreds of meters. Another disadvantage is the cost of this method. It requires antenna arrays at each base station to measure AOA. Hence cost of implementation increases. Time Difference of Arrival: The time difference of arrival uses the difference in arrival times of signals at a pair of base stations. The time difference of arrival measurements are done with reference to primary base station. A good algorithm in literature is the Performance Comparison of TOA and TDOA Based Location Estimation Algorithms in LOS Environment. It explains the working of different types of TDOA approach. It also compares the performance of each of the type. However it uses a LOS approach. In open areas LOS assumption is valid but in heavily populated urban areas this assumption is invalid. Another good algorithm which explains the TDOA measurements is is A Constrained Least Squares Approach to Mobile Positioning: Algorithms and Optimality . In this algorithm, the primary (Serving) base station is the reference base station. The time of arrival measurements are performed using the reference base station. Thus the estimated distance between mobile station and reference base station is d1 and that of mobile station and a neighbouring base station is di. Thus the TDOA measurements are given by, d1 = t1 / c di = ti / c, i = 2,3 .. N Where d1 is the distance between mobile station and reference (primary) base station and di are the distances between mobile station and other three neighbouring base stations. The TDOA measurement between reference and second base station is given by TDOA= d1-di i = 2,3, .N This will be the error free TDOA measurement at a pair of base stations. The measurement including error is given by; TDOA= (d1 di) + error The error is modelled as a Gaussian distributed random variable with zero-mean. Such measurements are taken from at least three pairs of base stations. The triangulation technique is then employed to get the position of mobile station. The TDOA method is superior to time of arrival (TOA) in sense that it eliminates the need for timing reference. Thus it is easy to implement. Due to no timing requirement TDOA method is more frequently used than TOA method. Database correlation method: Despite of a number of algorithm which perform fairly well in urban areas there is still a need to further improve it. Due to severe multipath and fading effects LOS assumption is not valid in urban areas. The Database Correlation Method is a good method to counter effect multi path and fading. It can be implemented by utilizing the measurements performed in existing GSM systems. It can be implemented by making Signal Strength as a parameter. A ggod algorithm to implement Database Correlation Method is Database Correlation Method for GSM Location by Heikki Laitinen, Jaakko Lahteenmaki, Tero Nordstrom'. In this algorithm the DCM is implemented by using signal strength measurements performed by handset. The algorithm explains the way database correlation method can be implemented in GSM. The measurements performed in the coverage area are performed by mobile station and are stored in database. Thus the database will consists pre-measured samples of signal measurements in the coverage l ocation. When the need to locate mobile station arises, the primary base station asks mobile station to perform signal strength measurements and feedback to it. The BS sends these measurements to location server. The location server then calculates the difference between stored fingerprint and actual measurement. The point where the difference between fingerprint and actual measurement is minimum will be the estimated position of mobile station. The estimated position will also contain some error in it due to fading, NLOS path and multipath propagation. However this error will be drastically less than the error in other techniques applied under same conditions. The database correlation method has the advantage that it can be implemented in any type of system like GSM, CDMA,UMTS,etc. References: Network-Based Wireless Location IEEE SIGNAL PROCESSING MAGAZINE JULY 2005 A New Time-Based Algorithm for Positioning Mobile Terminals in Wireless NetworksIsrael Martin-Escalona and Francisco Barcelo-Arroyo, EURASIP Journal on Advances in Signal Processing Mobile Positioning Using Wireless NetworksIEEE SIGNAL PROCESSING MAGAZINE JULY 2005 Path loss models S-72.333 Physical layer methods in wireless communication systems Sylvain Ranvier / Radio Laboratory / TKK 23 November 2004 Performance Comparison of TOA and TDOA Based Location Estimation Algorithms in LOS Environment Guowei Shen, Rudolf Zetik, and Reiner S. Thoma A Constrained Least Squares Approach to Mobile Positioning: Algorithms and Optimality K.W. Cheung,1 H. C. So,1 W.-K.Ma,2 and Y. T. Chan3 Database Correlation Method for GSM Location Heikki Laitinen, Jaakko Lahteenmaki, Tero Nordstrom