**Post: #1**

[attachment=2696]

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 http://www.seminarprojects.org/t-Simple-...ositioning for more about Simple Hardware-Oriented Algorithms For Cellular Mobiles Positioning