Simple HardwareOriented Algorithms For Cellular Mobiles Positioning presentation
seminar topics Active In SP Posts: 559 Joined: Mar 2010 
17032010, 08:48 AM
Simple HardwareOriented Algorithms For Cellular Mobiles Positioning.ppt (Size: 2.68 MB / Downloads: 66) Simple HardwareOriented Algorithms For Cellular Mobiles Positioning Presented by Batch no:1 A. Pratheep kumar(y7cs801) A. Chandrasekhar reddy(y7cs805) A. Jaya lakshmi(y7cs811) Abstract Locating a mobile station positioning. All locations determine algorithms that are based trigonometric calculations. We use two new hardware oriented algorithms. Two new hardware oriented algorithms that use just simple operations 1. Add 2. Subtract 3. Shift The first algorithm uses fixed rotations to locate a mobile station position. The second is a dynamic version of the first one . Keywords Vector rotation. Location determination. Hardware Oriented Algorithm. Vector rotation Cntd.. What is a Vector Vector Rotation Vector rotation also used in graphics computations in computer games. Cntd.. The two methods are: 1.Method of Moller and Hughes 2.Product operator formula. Cntd.. Method of Moller and Hughes: The product of two reflections is a rotation using reflections defined by the Householder matrix. Translation and Scaling may be required. Cntd.. Product operator formalism: In NMR spectroscopy, magnetic resonance imaging, a simplified form of vector rotation, the product operator formalism can be mostly used. Location determination: Location determination is locating mobile station. Different methods are used to describe location determination Hardware oriented algorithms: The algorithms implementing based on hardware. These algorithms are executed only in read only memory. One of the most important new services is locationbased services and applications. Introduction Wireless networks are growing rapidly throughout the world. Mobile users are increasing at incredible rates. mobile producers are providing lots of new and different services and applications. different services: * 2" QVGA active display * 2 MP camera * MP3 player * 3.5 mm AV connector * USB 2.0 * Bluetooth * Flash Lite * GPRS,TCP/IP support Chiefly in the US, the FCC has regulated that all wireless communication service providers must be able to find mobile phones . Determining mobile station position is divided to two main categories: 1. Networkbased scheme 2. Mobilebased scheme NetworkBased scheme: In networkbased scheme one or several base stations make the necessary measurement results to a location centre where the position is to be calculated. Cntd.. Handsets are not required to change the location services. Network based methods have high network cost and low position. Accuracy of networkbased techniques The accuracy of networkbased techniques varies, with cell identification as the least accurate and triangulation as the most accurate. Triangulation is the process of determining the location of a point by measuring angles to it from known points at either end of a fixed baseline, rather than measuring distances to the point directly. The point can then be fixed as the third point of a triangle with one known side and two known angles. Cont.. The accuracy of networkbased techniques is closely dependent on the concentration of base station cells, with urban environments achieving the highest possible accuracy. Advantage of networkbased techniques They can be implemented nonintrusively, without affecting the handsets. Mobilebased scheme These methods have high network cost and low precision. Here the mobile station uses its received signals to do its calculation for finding its position. Advantages Mobile based location schemes have better accuracy than network based schemes. Drawback with MBS To address the issue of foreign handsets that are roaming in the network They do not support old handsets This technique (from mobile operator's point of view) is the necessity of installing software on the handset. They have higher position precision. Hybrid positioning systems Hybrid positioning systems use a combination of networkbased and handsetbased technologies for location determination. One example would be Assisted GPS, which uses both GPS and network information to compute the location. Advantages Hybridbased techniques give the best accuracy of the three but inherit the limitations and challenges of networkbased and handsetbased technologies. Location Based Services for Mobile Devices Technologies Location Technologies GPS  Global Positioning System AGPS  Assisted GPS Cell ID Cell ID + Timing Advance Signal Strength Based AOA  Angle Of Arrival TOA  Time Of Arrival TDOA  Time Difference of Arrival EOTD  Enhanced Observed Time Difference GPS History Mariners relied upon the sun for latitude, and clocks for longitude With the launc h of Sputnik in 1957, radiobased global positioning became a (theoretical) possibility TRANSIT This was a very crude form of GPS using only one satellite (1960s) Submarines used it Could only be used every 3545 minutes Submarine had to be still TIMATION (1960s) Another satellite (TIMATION I) was launched to enhance the TRANSIT system Major innovation was the inclusion of an atomic clock Submarines could now be in motion and use the system NAVSTAR In 1973, NAVSTAR began research & development 1978 â€œ the first 4 satellites were launched Operated by the Department of Defense Primary mission is to provide exact coordinates for land, sea & airbased military forces Cost about $18,000,000,000 to developÂ¦ so far There are three components of GPS 1.) Space (e.g. satellites) 2.) Control (i.e. a ground station at a known geographic location) 3.) User How it works Satellites The GPS receiver precisely measures the time it takes a signal to travel from a satellite to the receiver There are lots and lots of satellites Anyone want to guess how many Details 6 orbital planes, included at 55 degrees to the equator, each with 4 satellites 21 active satellites, 3 backups Orbit the earth at 12,541 miles and have an orbital period of 11 hrs. 56 min. Satellite Triangulation How many points do you need Using one satellite narrows the distance to a sphere around the satellite Using two satellites, youâ„¢ll find your location within a circle (previous slide) Using three satellites limits your location to only 2 points Usually, it is possible to determine which point Using four satellites confirms your location and gives you 2 readings for altitude Usually you can determine which is correct The importance of time Both satellites and receivers generate Pseudo Random Noise (PRN) A Link 1 (L1) carrier signal is generated at 1575.42 MHz and Link 2 (L2) carrier signal is generated at 1227.60 MHz Carrier signals are modulated to produce coded signals, such as C/A code (at 1.023 MHz) and the P code (at 10.23 MHz) The frequencies are frequencymodulated to produce stepfunctions The codes repeat every millisecond The satellites come with cesium or rubidium clocks Time lag Selective Acquisition The US military was concerned about the possibility of terrorists or other unfriendly people using GPS to precisely guide a missile (or other unfriendly device) The deliberately introduced errors in the time embedded in the signal This caused locations to be up to 100m off Turned off on 2 May 2000 2010 GPS III system will launch Should be even more accurate than the 8m accuracy limit currently in place Tech: AGPS GPS has a slow time to fix unless it is permanently tracking satellites To solve the inherent restrictions with GPS, Assisted GPS was proposed Assisted GPS is based upon providing GPS satellite information to the handset, via the cellular network Tech: AGPS Assisted GPS gives improvements in Time to First Fix Battery Life Sensitivity Cost Assistance Data Satellite Position Time information Visible GPS List Sensitivity Tech: Cell ID Cell ID: the cell that the mobile is connected to Operatorâ„¢s know where their cell sites are Accuracy is dependent on cell density Can be implemented both network based or device based Cell identification It is a simplest method. Cell ID is associated with the location. It uses a bilateral principle. Tech: Cell ID Tech: Cell ID + Timing Advance (TA) TA is the time delay between the mobile and serving base station Resolution is 500 meters Serving cell identity and TA are available in networks Tech: Signal Strength Based Measure signal strength from the control channels of several Base Stations If signal levels from 3 different BSs are known, itâ„¢s possible to calculate the location Tech: Signal Strength Based Tech: AOA  Angle Of Arrival Measure the angle of arrived signal between base station and mobile station Location error increases as mobile is far from BSs Tech: TOA  Time Of Arrival Measure the time of arrived signal between base station and mobile station Mobile station locates at the intersection point which will be made by more than 3 circles Tech: TDOA â€œ Time Difference Of Arrival Measure the time difference of arrived signal between base station and mobile station : Minimum three base stations Mobile station locates at the intersection point which will be made by more than 3 hyperbolas Tech: TDOA â€œ Time Difference Of Arrival Tech: EOTD â€œ Enhanced Observed Time Difference Added device, LMU (Location Measurement Unit), whose location is known LMU and mobile station measure the time difference of arrived signal from base station at the same time Mobile station locates at the intersection point which will be made by more than 3 hyperbolas Tech: EOTD â€œ Enhanced Observed Time Difference EOTD Range Of Coverage Major Technologies Table Applications Network Optimization InCar & Personal Navigation and wayfinding Emergency (E911) Monitoring traffic flow using device location & optimization Automated Mapping Family Tracking/ FindAFriend Find the Nearest Store/place Tourist Information/Automated Guide Live public transport info Games Fleet Management Locationbased Billing Demographic Statistics Target Marketing Other applications TOA is one of the popular methods in use. Mobile based schemes have better accuracy than network based schemes. Our aim to reduce and simplify instruction for finding mobile positions. There are several draw backs are there in traditional algorithms use in this concept. we eliminate these draw backs we introduce two algorithms. Advantages of these algorithms are 1. Speed up. 2. Sow computation. 3. Communication overhead. 4. Implementation simplicity. The structure of this paper contains as follows Traditional algorithm implementation. Hard ware oriented algorithms implementation. Our simulations results for algorithm. Conclusion. 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 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 Fixed vector rotation The main idea of the fixed rotation algorithm is to use vector rotation with a fixed step angle 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. where k>=8, to guarantee the approximation precision 105 . Therefore, BS2 coordinates are recursively rotated as follow: 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. 2. Hence, the smaller vector needs more rotation. According to Fig. 2, if BS2 has larger radius than BS1, the algorithm will be as follows: While (xi+xi1>d) Rotate d2 While (yi1>yi) Rotate d1 End While End While Rotation equations for d1 and d2 are: 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: 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. 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. 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. According to y (the absolute difference value between the y coordinate of BS1 and BS2), the maximum possible step size is determined, where 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 While xi = xi+xi1d =e Rotate d1 by step angle si While yi = yi  yi1 =e Rotate d2 by step size angle sj End While End While Rotation equations for d1 are: Rotation equations for d2 are: 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; 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 Simulations We used Matlab package for the simulation analysis. We wrote programs for traditional algorithm, the fixed rotation algorithm, and the dynamic rotation algorithm. 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 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. 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. 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 E911 standards. Thank you please read topicideashowtoSimpleHardwareOrientedAlgorithmsForCellularMobilesPositioning for more about Simple HardwareOriented Algorithms For Cellular Mobiles Positioning Use Search at http://topicideas.net/search.php wisely To Get Information About Project Topic and Seminar ideas with report/source code along pdf and ppt presenaion



project topics Active In SP Posts: 2,492 Joined: Mar 2010 
25042010, 12:24 PM
Simple HardwareOriented Algorithms For Cellular Mobiles Positioning presentation.docx (Size: 635.72 KB / Downloads: 42) Simple HardwareOriented 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 hardwareoriented 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 HardwareOriented 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 nonteaching 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 (EOTD) 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 HANDSETBASED 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 HARDWAREORIENTED 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) EOTD 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 LocationAided Handover LAM LocationAided Mobility Management LAP LocationAided 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 NonLine 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 TAIPDL Time AlignedIPDL 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 locationbased 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 E911 service. Determining the mobile station position is divided to two main categories, networkbased and mobilebased 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 networkbased 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 mobilebased 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 [116]. 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,912] 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 hardwareoriented algorithm followed by the detailed description of the dynamic rotation hardwareoriented algorithm. In section 4, we show our simulation results for the traditional algorithm, the fixed rotation hardwareoriented 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: Â¢ Networkbased Â¢ Mobilebased Â¢ Mobileassisted In networkbased 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. Networkbased implementation does not require any changes to existing handsets,which is a significant advantage compared to mobilebased or most mobileassisted solutions.However, the MS must be in active mode to enable location measurements and thus positioning in idle mode is impossible. In mobilebased 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. Mobilebased implementation does not support legacy handsets The third category, mobileassisted 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 mobileassisted 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 networkbased 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 mobileassisted 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 mobilebased solution. Some applications, e.g. traffic monitoring and locationaided networkplanning (LAP), require mass location capability at network. These requirements can only be met by networkbased or mobileassisted 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 networkbased implementation.Unilateral means that the MS measures signals sent by several BSs and thus leads to mobilebased or mobileassisted 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 coordination 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 networkbased or mobilebased technique. In mobilebased 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 and implimentation, since LAP, LAH and LAM all requiresubcell 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 twodimensional geometry, an omnidirectional BS antenna, and freespace 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 freespace propagation. Therefore, an environmentdependent propagation model for the dependence of received signal level on BSMS 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 3040 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. Timeaveraging 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 mobileassisted or mobilebased method. Mobilebased 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 networkbased 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 lowcost 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 twodimensional 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 MSBS 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 lineofsight 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 networkbased 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 coordination 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 BSMS 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 networkbased 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 networkbased 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 mobileassisted or mobilebased methods. In mobileassisted 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 mobilebased 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 (EOTD) 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 (EOTD) 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 (EOTD) technique. An experimental EOTD 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 EOTD 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 MSbased, 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 MSbased 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 nearfar problem occurring in CDMAbased 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 OTDOAIPDL 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 (SFNSFN) 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 OTDOAIPDL method, however the support of the idle periods is optional for the MSs. Time AlignedIdle Period Downlink (TAIPDL) Time AlignedIPDL method is a modification of the standard IPDL. In TAIPDL 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 TAIPDL 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. TAIPDL 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 AOARTT hybrid in which even one BS is enough for location estimation. It is a bilateral networkbased 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 BSMS 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 TAIPDL 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 OTDOAAOA 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 HANDSETBASED 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 handsetbased 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 threeyear 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 worldwide, 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 LEOSV (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 standby 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 outofdate 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 tenfold 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 (LineofSight 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, suburban 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, timetofirstfix and coverage especially in the case where the system will be used in dense urban environments to provide location information and locationbased 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 colocated), computes corrections for each satellite signal received. The DGPS Base Station then transmits the corrections to the coobserving receivers. Because individual pseudoranges 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 pseudorange 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 pseudorange corrections to each SV used in the navigation solution. DGPS removes commonmode errors, those errors common to both the reference and remote receivers (unlike multipath 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 submeter 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 SC104 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 handsetbased / networkassisted). 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 uptothehour 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 100m3km Cell ID + TA none 500m TDOA none 100200m AOA none 100200m EOTD yes 20200m GPS/AGPS yes 530m 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 locationdependent 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 locationdependent 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 largescale 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 lineofsight propagation is not valid, e.g. in dense urban and indoor environments. The only assumption is that the database contains uptodate 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 DCMbased location system. . 5.2 Application to GSM The essential locationdependent 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 singlefrequency 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 lineofsight 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, mobilebased location schemes have better accuracy than networkbased 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 speedup, 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 HARDWAREORIENTED 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(2k), 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 (2k) 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 E911 standards. REFERENCES [1] M.Najiminaini, E.Doukhnitch, M.Salamah, and I.Kale. Design and Comparison of Hardwareoriented Algorithms for Cellular Mobiles Positioning, accepted in Seventh IASTED International Conferences, Montreal, June 2007. [2] M. Salamah, E. Doukhnitch., and D. Deniz, A Fast HardwareOriented Algorithm for Cellular Mobiles Positioning, LCNS, vol. 3280, SprigerVerlag 2004, pp. 267277, ISSN 03029743. [3] H. Laitinen, and et al, Cellular Location Technology, CELLO Project Technical Report ,CELLOWP2VTTD03007Int, 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.5969. [5] H. Chi, and R. Jan, CellBased Positioning Method for Wireless Networks, Parallel and Distributed Systems, In Proc., Ninth Int . Conf. on 1720, 2002, pp.357380. [6] M. A. Spirito, On the Accuracy of Cellular Mobile Station Location Estimation, IEEE Transactions on Vehicular Technology 50(3),2001, pp.674685. [7] H. Koshima, and J. Hoshen, Personal Locator Services Emerge, IEEE Spectrum 37(2), 2000, pp.4148. [8] Y. Zhao, Standardization of Mobile Phone Positioning for 3G systems, IEEE Communications Magazine 40(4),2002, pp.108116. [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.15081518. [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/11/6, ISSN 09633308. [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/17/6. [12] G. G. Messier, and J. S. Nielsen, An Analysis of TOABased Location for IS95 Mobiles, Vehicular Technology Conference, vol. 2, 1999, pp.10641071. [13] J. J. Caffery, A New Approach to the Geometry of TOA Location, Vehicular Technology Conference , Boston, MA USA, Vol.4, 2000, pp.19431949. [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, 36 April 2006, pp.22672272. [15] S. Venkatraman, and J. Caffery, Hybrid TOA/AOA Techniques for Mobile Location in NonLineofsight Environments, in Proceedings of the Wireless Communications and Networking Conference (WCNC), IEEE, vol. 1, Atlanta, GA USA, 2125 March, 2004, pp. 274278. [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, LowPower Divider, IEEE Transactions on Computers 48(1), 1999, pp.214 [18] Weisstein and W. Eric, CircleCircle Intersection, From MathWorld A Wolfram Web Resource. Available: mathworld.wolframCircleCircleIntersection.html [19] G. J. Henkstra, and F. A. Deprettere, Fast Rotations: Lowcost Arithmetic Methods for Orthonormal Rotation, In: Proc. Of 13th Sym. On Computer Arithmetic, 1997, pp.116126. [20] J. M. Muller, Elementary Function Algorithms and Implementation, Birkhauser, 1997. Use Search at http://topicideas.net/search.php wisely To Get Information About Project Topic and Seminar ideas with report/source code along pdf and ppt presenaion



