Location Based Services (LBS) Technology Overview

Location Based Technologies

I have often wondered whether people really understand Location Based Services (LBS) technology and whether they would like a bit more insight into how exactly location based services work, and more importantly — what information is actually passed from your phone to a server in order to establish your exact location co-ordinates. Most of the time, the accuracy of your co-ordinates is entirely correlated to the accuracy of the method being used to determine your location — such that some methods use mathematical approximations to determine your location, and others use global positioning data bounced from satellites to gain a more accurate understanding of your position. Of course, some use a combination of both. All of the methods I will explain below do, very much, depend on your surroundings as well. Obviously, if you are surrounded by iron sheeting 100 meters underneath the ground — your location will be pretty hard to determine. Conversely, if you are standing next to a mobile phone tower and can see 5 other towers and have a clear vision of the sky — your position is going to be very accurate.

I will make special mention now that all this information is entirely understood by industry professionals, so nothing that I am going to detail here is “secret” or contains some sort of “special sauce” which I know that other people don’t. The idea of this post is to give people out there, who don’t know really anything about Location Based Services (LBS), a better understanding of the technologies which are utilized in a non-technical format.

Parameters on your Phone

Before I dive into an explanation about what types of location based technologies are actually out there — a good place to start is what information actually sits on your mobile phone which allows location based services to actually work.

A typical mobile phone contains a whole bunch of communication information which tells the mobile phone what network operator your mobile phone is connected with, and how to optimize your mobile signal in order to ascertain the best signal strength. You can usually access all this information by typing in a special character combination on your mobile phone which will take you to the engineering information screen. Most of you out there won’t really be all that interested in checking this stuff out because it’s a whole bunch of numbers that aren’t going to make sense — but for those that want too, just search the internet for your handset model and the unique engineering unlock code. It’s usually pretty easy to find.

So what information is available?

The information displayed on your phone varies from handset to handset, and I do not recommend that you meddle with it. Sure thing you can view it, but do not attempt to change predefined settings on your mobile phone or you might render it useless. While I could go through all the information listed, I am only going to focus on the location information that is really used as it’s most relevant to this post. It’s below as follows:

• AcsClas — Access priority class (not supported if 0000)
• MSTxPwr — Maximum allows transmit power in dBm
• MCC — Mobile Country Code
• MNC — Mobile Network Code.
• LAC — Location Area Code
• Cell ID or CID — Base Station Identity
• Radio Frequency (RF) Signal– The relevant signal strength between your current tower and the adjacent one
• Hopping — Whether any frequency hopping is in operation
• DTX — Whether Discontinuous Transmission is in operation

So what does all this stuff mean ? Basically, all this information informs your network of where you are at any one time. This is done by your network operator knowing the relevant latitude and longitude of all relevant base stations — or mobile phone towers — in your country and correlating this information with the information shown above to determine your approximate position (this is called ‘network driven location approximation’).

For example, typically the process goes like this for signal strength or time based location identification:

1. Identification of your MCC & MNC occurs which recognizes the relevant country and network operator you are in/with.
2. Identification of the relevant LAC, or your location area code, to determine the approximate regional area you are in.
3. Identification of your Cell ID or CID — the relevant cell or mobile tower that your mobile is connected too.
4. The combination of your RF, Hopping and DTX allows both your network operator and your mobile phone to ascertain which signal is the stronger, and thereby determine a priority of mobile base stations (Cell IDs) with which your mobile should be connected. This can be done through signal strength and timing responses of your phone with the relevant cell tower.
5. Because your network operator has a database of relevant latitude and longitudes of all Cell IDs, or mobile base stations, they are then able to approximate your position using “triangulation” or “quadrangulation” techniques.
6. These techniques typically use a complex mathematical method of determining your location, which really relies on the good old Pythagoras theorem you were taught in school. For triangulation, this is then combined with a calculation to determine the barycenter of the mobile base tower ‘triangle’ (determined by the strongest three base stations) to determine your approximate position. (I’m not going to go into quadrangulation but you get the gist!)

It’s important to realize that what I have just detailed is a really simplistic overview of a network method of location identification — in real life it’s quite complex. Additionally, the method illustrated above is really just for network identification using signal strength or timing based calculations. There are, of course, many other methods, as well as hybrid combination’s of these technologies which is all detailed in the next section.

Location Based Service Position Technologies

OK, so we have briefly covered what’s available in your mobile phone as well as how your mobile and network operators use this information. Now let’s cover what technologies are out there, the pro’s-and-con’s of each and an overall conclusion.

Here is a table that covers the main types of location technologies out there:

Location AccuracyTime to FixPrerequisites GPSHigh Precision“Sky Line of Sight”

5–20m

~ 10–15 mins start

~ 1–2 sec updates

Device support only (HW)A-GPSVery High

Requires “Sky Line of Sight” 5–50m

~ 10–40 sec start

~ 5–10 sec updates

Requires specific device support Hardware(HW), GPS reference network.OTDOA (WCDMA)

E-OTD (GSM)

AFLT (CDMA)

Medium Strength

Depends on cell density 40–400m

~ 6–10 secondsRequires Base Station Support (BSS), MSC and HLR support and usually always requires

network operator involvement

Cell-IDQuite Weak

Dependent on cell density

Between 100–5500m

~ 4–8 secondsNeeds Mobile Switch Center (MSC) and Home Location Register (HLR) support, or requires device and Cell-ID database.WiFiQuite Strong

Dependent on WiFi AP density

< 50–250m

~ 4–8 secondsDevice and network support.

Requires WiFi DB.

Summary of the Table

GPS

Global Positioning Systems are basically a series of 24 (now 32 as of March 2008) Medium Earth Orbit Satellites (around 12,500 miles above the earth) which transmit exact microwave signals that allow GPS receivers to determine their exact location, speed, direction and time. A GPS receiver calculates your position by timing the signals sent by the GPS Satellites to your current location on Earth, and the receiver uses the arrival time of each signal to measure the distance to each satellite. Trialateration (triangulation) is used to determine the device’s location given the number of signals received from each relative satellite, and this information is then decoded into useful formats such as latitude and longitude. Typically, latitude, longitude, time and altitude are the 4 data sets that need to be interpreted — with the position time being relative to the GPS information and signal quality. This is why you need a clear ‘line of site’ with the sky in order for GPS to really work effectively because the receiver must have constant signal connection with a least 3 satellites in order to accurately determine your position.

Assisted GPS or A-GPS

This type of technology has garnered a whole bunch of attention recently because A-GPS is what is contained in the new iPhone 3G. Assisted GPS is basically an improvement on GPS because it combines the information received from satellites, with the information from your local base station. As explained previously, your mobile phone is connected to a relative base station or wireless network at any particular point during the day. Assisted GPS basically takes the known location of this base station and combines it with the information gathered from the GPS chip to improve the relative speed of locating your exact position. If your GPS chip is able to already have an approximate idea of where it is located on the planet, then it is able to look specifically for satellites in the region where you are located, instead of scanning for random signals and interpreting them. By using available network information, your GPS chip can more easily narrow its vision to search for signals in your current country and region. This basically reduces the time to fix your location because the data being collected improves the quality of the GPS receiver.

The biggest issue with Assisted GPS is of course, its reliance on the network operator to provide network data to the GPS chip. As indicated, for A-GPS to work, it requires the network operator to provide some information about the Cell ID in order to ascertain the relative, or approximate, latitude and longitude of the device. Alternatively, this information can be provided by WiFi network connections assuming they have position information contained in them, and WiFi is supported by the device.

Cell ID (or Base Station)/ WiFi Databases

Mobile devices must always have a relative wireless access point (for Wifi devices) or base station in order to determine the location of the device. The simplest example of location identification using this method is when you see your neighborhood or suburb name on the main screen of your phone. Your Cell ID or WAP point is transmitted to your network operator who is able to determine where you are located generally.

More recently, third party databases are being gathered in order to take away the potential monopoly that network operators have around this information. Google, for example, has been gathering this information by getting GPS users to download their mapping applications onto their phones, and then pairing your current GPS co-ordinates with your network information to map out every wireless access point and base station available. They do this by matching the signal strength and timing information, with the relevant MCC, MNC and Cell ID your mobile phone is connected with, and matching this up with your current latitude and longitude information passed from your GPS receiver — all this information in then bundled up and passed to the Google servers. This allows them to generate an approximate estimation of where exactly the base station is located and subsequently triangulating your location. No doubt, they also combine this with information contained in the current map tile you were viewing on the Google mapping application. All this information allows them to have a very extensive, and a very valuable location database. Of course, there are other companies doing the same thing in order to resell this information. SkyHook is a company which is basically hiring people to drive around in cars in all sorts of cities around the world to gather Wifi access point information and then resell this to developers who want location information. It’s really a combination of these methods which is going to provide the best location information moving forward.

WiFi databases basically take advantage of relevant Service Set Identifier (SSID) and Media Access Control (MAC) addresses of access points constantly. When you hook up your wireless router at home for example, you will notice the relevant SSID and MAC addresses when connecting to your wireless network. The MAC address is basically the unique device identifier which can be used to roughly identify where the receiving signal is coming from. As you would know from your home laptop or mobile device -most WiFi signals can only really extend a maximum distance of 50m-200m and so the position information from WiFi stations can be quite useful for easily determining your location. The obvious disadvantage is that you need to know hundreds of access points in order to make up a meaningful and worthwhile location database.

Signal Strength Triangulation

The example I provided in the mobile engineering information section above really explains how this process works. Basically, by leveraging the relative radio frequency (RF) of the signal strengths in the device and incorporating the base station information, a position is able to be determined. As explained previously, the complexity of the mathematics behind determining your location is really dependent on the quality of the data in the database. RF fingerprinting really looks at relative signal strengths of the base stations that the device is connected too, and prioritizes them in order to get the three strongest signals (triangulation). Basically, it then calculates the propagation of the RF signals and uses this to estimate your position relative to the latitude and longitude of the base stations. This type of method has been the most commonly used method of location identification because GPS and A-GPS chips are not widely available in mobile phones yet — although this is rapidly changing.

Time-Based Triangulation

Again, the example I provided at the beginning explains how this works broadly. The slight difference time-based triangulation has to signal strength triangulation, is that it looks at the relevant signal timing information from the network in order to ascertain your relative position to nearby base stations. Time Difference of Arrival (TDOA) and Advanced Forward link Triangulation (AFLT) are the most common methods of location determination under time-based identification. The biggest difference between the two methods (TDOA v AFLT) is where the timing difference is measured — either in the device itself or in the network. TDOA is the more complex method and makes it impossible for third party vendors to use this it because the calculation is done inside the network. This makes TDOA a “LBS network operator monopoly” method. The AFLT method is a CDMA method and uses CDMA as opposed to the more common GSM to make the position known. The other method which is worth a mention is the Enhanced Cell-ID method which incorporates both signal strength and timing data received from GSM signals in order calculate an in-network position. Again, this is a difficult method to commercialize because of the network operator reliance on calculating the timing of the signal. Network triangulation is really around 50m-500m in accuracy.

Conclusion

I could continue writing all day about which method is better, which has a better timing-to-fix and which is the best fall back option — but it seems this post has already gone on long enough. Obviously, there are a whole bunch of factors that I haven’t mentioned such as hardware reliance, chip quality, battery and CPU drain and other general aspects of wireless and mobile devices that must be taken into consideration. I haven’t gone into these areas predominately because they are factors that need to be considered by developers only and not by the people who just want to understand location based services and technology generally. I will mention, however, which is the LBS method is the best.

None of them : P

The reason for this is because it’s combination of all of them which makes LBS useful. When it is apparent that one method is clearly working really well, and another is not, then this is the most suitable method to be used — it’s that simple. The real key is to have a number of methods available in your device so that the best method is always utilized at the right occasion. This is why in some respect that A-GPS is one of the best LBS techniques -although it’s not all that common at the moment in mobile phones — because you get the best of both worlds by having GPS and Network Information determining your location at any one time. With that said, as I stated at the start, the strengths and weaknesses of each technique always come down to the environment you are located in, and the current conditions within this environment.