technology goes mobile: my response to tech crunch.

The Japanese have been on this for YEARS.... but tech crunch is right--finally we are  catching up. (GO US--get it us--U.S. --ok not funny) with all of the technology out there and all the new devices and apps jumping the band wagon, thank you that someone finally wrote this post! It explains new technologies, apis, the different kinds of APIs, and why mobile devices are essential ingredients to our technological marketing and communication futures.

June 4, 2008

Location Technologies Primer

Guest Author

36 comments »

The rise of the mobile device is upon us, even if it's arriving a little late to the U.S.

The reason why mobile devices will become so important - they'll help us (and our friends, and maybe everyone) know where we are at all times, driving social, advertising and other applications. Being location aware is the single most important feature in a mobile device that otherwise suffers in comparison with desktop and laptop Internet devices - terrible screen size and resolution, poor battery life, slow connectivity and less than satisfying data input choices.

But being location aware more than makes up for those limitations. Social networking will fundamentally change as your device knows who's around you, for example. Startups like Loopt, Brightekite and Limbo are all offering social networking products that leverage location awareness.

Other types of killer applications will also be built on the back of location aware technologies, and the advertising possibilities are substantial (care to stop by that Starbucks you are diving by for a free latte?).

The carriers generally know where we are all the time (or can easily find out), but they guard this information jealously and rarely disclose it to third parties. But that isn't stopping Google, Apple and a host of other startups from finding ways to get that information anyway.

Eric Carr, the VP of Location Technologies at Loopt, is the guy we go to when we have questions about new location technologies. Instead of just calling him every day, we asked him to write a primer on the core technologies being used to solve the location problem. Luckily for all of us, he agreed.

His post is below. We'll be referring back to this regularly as we talk about new applications that leverage these technologies.

---

Mobile location-based services (LBS) are generating renewed interest as both the market and technology mature to support the growing set of innovative services being released and in development today. This is being driven by new Location APIs and new location technologies, which are making it easier for mobile location developers to gain access to location information and develop innovative new LBS apps.

This article is a brief primer on the key location technologies that are emerging.

	Location Precision	TTFF	Requirements
WiFi MAC	Relatively High Depends on WiFi AP density < 100-200m	~ 4 seconds	Requires device support and network request. Requires WiFi DB.
Cell-ID	Relatively Low Depends on cell density 100-5000m	~ 4 seconds	Requires support from MSC and HLR, or Requires device and Cell-ID DB.
OTDOA (WCDMA) E-OTD (GSM) AFLT (CDMA)	Medium Precision Depends on cell density 40-400m	~ 6 seconds	Requires support from BSS, MSC and HLR. (require carrier network involvement)
A-GPS	High Precision "Sky Line of Sight" 5-50m	~ 10-30 sec start 5-10 sec updates	Device support (HW), GPS reference network.
GPS	High Precision "Sky Line of Sight" 5-20m	10-15 minutes start 1-2 sec updates	Device support (HW)

Positioning Technologies

This section will review the primary positioning technologies in use today.

GPS

GPS is a system of 32 satellites orbiting 12,600 miles above the earth. The system was designed such that 6 (and usually more) satellites should be visible from any vantage point on earth. GPS works by making extremely precise distance estimates from timing the delay time of signals (1 ns ~ 1ft) sent from the GPS satellites to earth. Trialateration (triangulation) is used to determine the device's location given at least 3 or more satellites. When a GPS receiver is turned on, it looks for and locks on to visible GPS satellites to begin receiving and decoding the GPS broadcast signal. The GPS almanac data provides a list of visible satellites. The GPS ephemeris data provides precise timing and location information for each satellite. Latitude, longitude, time and altitude are the 4 dimensions that must be solved for (usually the first 3). Position acquisition time is driven by previously collected GPS information and GPS signal quality. GPS is accurate to 5-20m depending on environmental conditions.

Assisted GPS or A-GPS

Assisted GPS is an improvement on GPS, primarily for mobile devices with network connectivity. Since mobile devices are connected to a wireless network on a known wireless base station, the location of the base station can be used to aid the GPS calculation. Assisted GPS takes the known location of the base station and provides synthetic or seed data to the mobile device's GPS chip to improve the speed of GPS signal acquisition. For instance, if the GPS chip knows that it should "see" a specific set of 4-5 GPS satellites at it's coarse location, the GPS chip is able to narrow the search of signals to acquire. This reduces the amount of time required for the GPS chip in collecting ephemeris data and improves the sensitivity of the GPS chip in processing noisier GPS signals. This allows for a faster location fix time and makes possible GPS use in some indoor environments.

Assisted GPS does require device chipset support and network communication. The A-GPS server has traditionally resides in the operator's network. However, there is trending towards device manufacturers offering similar services for their devices specifically. For A-GPS to work, an initial position estimate is required. This has traditionally been via the operator's Cell-ID database. Additional initial position estimate options are being made available with 3rd party Cell-ID and WiFi databases.

Network Base Station Database

Since mobile devices (both cellular and WiFi) are associated with a wireless access point / base station, it is possible to use the position of the base station as a proxy for the location of the device. In a simple case, the base station the device is associated with is returned as the device's location. Mobile operators view their base station databases as proprietary network information and have not generally shared it with 3rd parties. There are a number of 3rd parties who have begun to accumulate detailed Cell-ID and WiFi databases that can then be used to locate devices.

Network database collection approaches fall into two camps: 3rd party driven or user-generated. SkyHook is the best example of a 3rd party driven approach where SkyHook employs a fleet of drivers that drive cities collecting WiFi access point information. Google and Navizon are companies that employ user-generated approaches where data is fed back from mobile devices with the appropriate client software installed. To build a database, these user-generated approaches can either leverage the collection of both GPS and base station signals, or leverage the collection of base station signals with existing known reference base station locations. It is likely a mix of fleet and user-generated approaches will be necessary to ensure high accuracy, rapid updating intervals, and low acquisition costs going forward for both Cell-ID and WiFi database collection.

3rd party Cell-ID databases have focused primarily on GSM/WCDMA networks since GSM/WCDMA base station identifiers have been relatively static over time. In contrast, CDMA networks change base station identifiers much more frequently, making it harder to build an accurate base station database without carrier involvement. The accuracy of a Cell-ID position will depend on the density of the wireless network. Urban areas will lead to more precise estimates, rural areas to much less precise estimates. Accuracy should be in the 100-5000m range depending on the network density of base stations. However, Cell-ID will at best provide a coarse level estimate of location. (WiMAX networks use a higher frequency than cellular network, requiring denser base stations, resulting in higher accuracy Cell-ID location.)

3rd party WiFi databases have propagated in the last few years. These take advantage of WiFi standard beacons that broadcast both the SSID and MAC address of the access point constantly. The SSID is used to create the list of available WiFi access points seen on many WiFi laptop connections. The MAC address is a unique identifier that can be collected and used to roughly identify where the receiving device is located. Since most WiFi signals propagate a maximum distance of 100-150m, if a WiFi access point is observed, a relatively precise position determination can be made.

Both Cell-ID and WiFi approaches can benefit from observing multiple base stations and incorporating radio strength information to calculate more accurate Cell-ID derived location.

Network Triangulation (signal strength-based)

The majority of positioning determination innovation is occurring in the area of leveraging the RF signal strength of signals received by the device and incorporating network information (known position of base stations). The algorithms range in complexity and depend on the availability of modeled or true RF signal propagation characteristics. RF fingerprinting takes the locations of known base stations, either empirically or analytically calculates the propagation of RF signals, and uses the resulting RF base map and signals received at the device to estimate the device's position. There are also a number of client-side solutions that are leveraging the availability of multiple cell-ids on the device to more accurately determine device location. RF based approaches are also being incorporated as a fall-back techniques when A-GPS is not available.

Network Triangulation (time-based)

There are some position technologies that make use of signal timing information from the network to make a position determination (vs. GPS which uses timing information from satellites). Time Difference of Arrival (TDOA) and Advanced Forward Link Triangulation (AFLT) are two of the more well known methods. The primary difference in methods is where the timing difference is determined: in-network or on-device.

TDOA was the positioning technology selected by GSM/WCDMA operators in the US for E911 purposes. Unfortunately, the amount of signaling traffic required to make a position estimate is not trivial. This has made the TDOA technology not a viable option for commercial LBS services.

AFLT is a CDMA specific technology that uses the signaling characteristics of a CDMA to make a positioning determination. This acts as a fall-back method for CDMA devices if A-GPS is not successful and the network was requested to make a location determination.

Enhanced Cell-ID is an approach that uses signal strength and timing received from the GSM signal to make an in-network calculation of location which is more accurate than Cell-ID alone. Enhanced Cell-ID also can make use of sector information since many cellular base stations are directional in nature (IE 3 sectors with each sector covering 120 degrees from the base station).

Network triangulation is accurate to 40-400m depending on environmental conditions.

Hybrid approaches

From the descriptions above, it should be clear no one position technology is best for all use cases. The positioning technology market is pursuing hybrid approaches where the strengths of each technique are leveraged where appropriate. Since A-GPS requires a location estimate to start with, other less accurate location technologies can be leveraged to seed the A-GPS algorithm. Each location technique also is more successful in different environments (namely urban vs. rural and in-doors vs. out-doors). Luckily, the strengths and weaknesses of many of these position technologies are complementary, motivating further exploration of hybrid location approaches.

Evaluating Positioning Technologies

After a brief understanding of position determination methodologies, it is valuable to define how each positioning method should be evaluated. A few key categories are listed below and described. There are of course others that could be relevant depending on the location use case. Each position determination technique has strengths and weaknesses across each dimension that will be discussed in the following section.

Positioning Accuracy and Uncertainty

Accuracy will vary depending on environmental conditions (indoors, urban environment, signal quality, etc.). Accuracy can vary from 5-20m (GPS) to 50-5000m+ (Cell-ID). Each positioning technology will also have varying error ranges depending, again, on a broad set of environmental conditions.

Generally, the positioning industry has been driven by GPS chipset manufacturers who are motivated to provide the highest accuracy, lowest uncertainty possible location solution. GPS-level accuracy is necessary for navigation and other turn-by-turn level accuracy user cases. However, there is a wide range of LBS apps that can make do with "lower" levels of accuracy which can be provided by WiFi, Cell-ID or other hybrid approaches. Accuracy is important, but it is only one of the factors that should be considered in weighing available positioning options.

Positioning Latency or Time To First Fix (TTFF)

Positioning latency is a critical factor in driving the usability and responsiveness of a location-aware app. In the mobile app space, acquiring a location quickly is paramount to offering a compelling user experience.

Positioning latency or TTFF is most commonly associated with portable GPS receivers or Personal Navigation Devices (PNDs). Without network assistance, GPS receivers can take on the order of 5-10 minutes before a first fix. This is a function of the time required to lock on to and receive enough information from the GPS satellites in space. Assisted GPS is able to improve this fix time to 10-30 seconds by synthetically seeding the GPS receiver with network data and accelerating the GPS acquisition and position determination process. Assisted GPS still requires data exchange and computation on both a network server and on the device, making it challenging to reduce TTFF further. Other non-GPS based technologies are able to determine a location estimate in below 10 seconds (IE WiFi or Cell-ID were looking up a location in a database is all that is required).

Positioning Determination Ubiquity

A positioning technology is not useful if it is not available in the area where your mobile device is. GPS-based methods have a strong advantage here since it is a globally accessible method and will work even if the mobile device is not associated with a mobile network (there are clear disadvantages in that situation, but it could work). WiFi methods are constrained to areas where there are wireless WiFi Access Points. This is generally not a problem in urban or suburban areas (where most interesting LBS Apps are targeting).

Indoors vs. outdoors is another factor to consider. GPS, generally, does not work well inside buildings. Whereas, WiFi is most likely best suited for indoor positioning determinations.

Positioning Fallback Options

Related to positioning ubiquity and hybrid approaches, devices are expected to make the best location calculation given available information. IE if GPS fails, a network-based method or Cell-ID location is desired to be returned vs. a message of "failed, try again later." The challenge is since many methods rely on base station databases, the device must optimize how the a LBS App location request is handled. If the network is asked to make the location calculation (IE A-GPS MS-Assist), then all available network information can be used. Hybrid approaches on-device and off-device must take into consideration returning the best known position estimate in a timely manner, even if the preferred method fails.

There are also a number of device-specific dimensions that are critical to keep in mind which drive position determination implementation on device.

Device Impact (battery, CPU drain)

Assisted GPS chip performance has improved considerably over the last few years. However, receiving and processing signals from space still takes a large amount of energy. GPS antenna placement is also critical as more devices add additional RF technologies (WiFi, Bluetooth, additional cellular bands). GPS integration continues to be an important art for device manufacturers.

Most of these positioning technologies involve some level of network data connectivity that can also impact device battery life. There are a number of on-device caching solutions that are evolving for both GPS and WiFi/Cell-ID approaches that minimize the amount of network traffic required to make a position fix. However, given most LBS Apps are making use of network connections, location becomes a limited portion of App traffic.

Device Prevalence / Support

Assisted GPS was adopted by CDMA carriers to support the FCC's E911 mandate. Qualcomm has added GPS chips to it's line of core chips. This has enabled CDMA operators worldwide to deploy innovative mobile LBS Apps leveraging A-GPS. The GSM/WCDMA world has been slow in adopting A-GPS, with forecasts of 2009-2010 being the year of broader device support.

WiFi has seen relatively limited support in mobile devices to date. There are a growing set of high-end smart phones that are integrating WiFi and driving the market (namely the Apple iPhone, HTC, Nokia, RIM and others). WiFi could be viewed as a competitor to 3G data services operators are interested in up-selling users with. WiFi also creates additional technical challenges (antenna placement, additional battery draw, etc.) which continue to improve, but remains important considerations for device manufacturers.

Device Location APIs

The availability and accessibility of Location APIs on mobile devices has been spotty at best to date. RIM, Nokia and Motorola iDEN have provided device specific Location APIs that have motivated strong initial interest from developers. The Apple iPhone and Google Android Location APIs will spur additional interest ongoing. Existing J2ME (JSR-179) and BREW (IPOSDET) API exist today for a wide set of feature phones.

However, operator involvement has made it challenging for some developers to gain easy access to location. It is clear device vedors are using location as a competitive differentiator to better position their device platforms relative to others. However, universal Location APIs still remain a challenge with the fragmentation of different APIs, devices and operator policies.