17-03-2010, 08:48 AM
Simple Hardware-Oriented Algorithms For Cellular Mobiles Positioning.ppt (Size: 2.68 MB / Downloads: 82)
Simple Hardware-Oriented 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 location-based 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. Network-based scheme
2. Mobile-based scheme
Network-Based scheme:
In network-based 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 network-based techniques
The accuracy of network-based 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 network-based techniques is closely dependent on the concentration of base station cells, with urban environments achieving the highest possible accuracy.
Advantage of network-based techniques
They can be implemented non-intrusively, without affecting the handsets.
Mobile-based 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 network-based and handset-based technologies for location determination.
One example would be Assisted GPS, which uses both GPS and network information to compute the location.
Advantages
Hybrid-based techniques give the best accuracy of the three but inherit the limitations and challenges of network-based and handset-based 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, radio-based 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 35-45 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 & air-based
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 frequency-modulated to produce step-functions
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
In-Car & Personal Navigation and wayfinding
Emergency (E911)
Monitoring traffic flow using device location & optimization
Automated Mapping
Family Tracking/ Find-A-Friend
Find the Nearest Store/place
Tourist Information/Automated Guide
Live public transport info
Games
Fleet Management
Location-based 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 10-5 . 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+xi1-d |=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 E-911 standards.
Thank you
please read https://seminarproject.net/Thread-Simple...ositioning for more about Simple Hardware-Oriented Algorithms For Cellular Mobiles Positioning