I noticed that many posters in this forum incorrectly use the term "triangulation" when referring to the iPhone's Locate Me feature, indicating that there is a lot of confusion and misunderstanding about this technology. A quick search reveals no fewer than 250 posts that contain that term.
The point of this memo is to clarify how iPhone's Locate Me works and how it is different from triangulation.
So let's start with triangulation. Wikipedia features a good comprehensive article on the subject that you can study at your leisure.
In short however, triangulation has something to do with a triangle, and a triangle always has 3 corners and 3 vertices. Triangulation attempts to determine the unknown position of one of the 3 corners based on a few known entities, for instance the distance between the other 2 corners (1 vertex) and two angles, or the distance between each of the 2 known corners and the unknown corner (2 vertices) and 1 angle, or something else along those lines. Using several trigonometrical laws, the 3rd corner can then be determined. The important thing about triangulation is:
for it to work, 2 fixed reference points are required
the result (the location of the third corner) will be exact
Now let's look at how the iPhone determines location.
iPhone uses one of three methods to determine (or approximate) the user's location:
GSM Cell ID location lookup (available both in iPhone and iPhone 3G)
Wi-Fi MAC address location lookup (available both in iPhone and iPhone 3G)
A-GPS (available only in iPhone 3G)
Neither of these methods is based upon triangulation.
The first method is Cell ID location lookup, which works as follows: A GSM handset always communicates with exactly one sector of a base station, and each GSM sector in the world has a globally unique identifier, known as CGI (cell global identity). The CGI consists of 4 fields, the MCC (mobile country code), the MNC (mobile network code), the LAC (local area code), and the CID (cell ID). (Even though this method is usually called Cell ID-based location lookup, it actually requires the entire CGI, of which the CID is only one component.) So each GSM mobile is always tuned to exactly one serving sector, and part of the channel overhead messaging of that sector is to broadcast its CGI. (The iPhone displays each component of the CGI in the Field Test application under Cell Information.) When the user invokes the Locate Me feature, iPhone sends the CGI to the Google server, which then correlates it against its Cell ID database to retrieve a range of locations that previous users have reported being at when connected to that same CGI. (A short writeup about this can be found here.) Since each sector covers a rather large area (depending on cell size, the radius of a serving sector can be anywhere from about 0.2 mi all the way up to 22 mi), the resulting location fix is only approximate. Note also that the mobile only reports the CGI of the one (and only) serving sector, so triangulation of the mobile's position is impossible, since that would require at least two known reference points (base stations).
Although CGI-based triangulation is actually possible when taking into account non-serving neighbor sectors (the positions of which are known to the subscriber's wireless carrier), receive signal strength (which can serve as an approximation for distance from the base station) and/or timing advance (which provides a much better approximation of distance from the base station), the iPhone and Google Maps app don't use any of these parameters and are hence unable to perform triangulation.
The second method is Wi-Fi MAC address based location lookup. It actually works quite similar to Cell ID location lookup. Each Wi-Fi base station (access point) is permanently provisioned with a globally unique MAC address which is constantly being broadcast as part of the 802.11 protocol stack. When the user initiates a Locate Me query and the iPhone is within Wi-Fi coverage, it will send the MAC address of the serving Wi-Fi base station to Skyhook Wireless, which has compiled a database of known Wi-Fi access points, their MAC addresses, and approximate location. If Skyhook finds a match for the MAC address provided, it will then return the approximate location of the base station. Since Wi-Fi base station radiation patterns are typically omni-directional (non sectored) and since the mobile cannot determine its distance from the base station, the position fix will actually return the location of the base station, not the location of the mobile. However, since Wi-Fi has a relatively small coverage area, the mobile is assumed to be in close proximity of the base station. Note that this method also does not fit the definition of triangulation, as only a single fixed reference point is available.
Due to the CDMA-based nature of the physical layer communication in 802.11b/g, the iPhone may actually see several Wi-Fi base stations simultaneously. It could conceivably provide the MAC addresses of all Wi-Fi base stations within range to Skyhook, and Skyhook could conceivably aggregate and consolidate the various positions of each base station that corresponds to a MAC address provided in the query, and therefore provide a fix based on several known reference points. I don't know if Skyhook has this capability and whether the iPhone software would be able to take advantage of it, but in any case even if it does, I would not call this triangulation, since an exact location fix of the mobile is still not possible. Referencing multiple Wi-Fi base stations merely positions the mobile into a smaller range of uncertainty, somewhere between (or around) those base stations, but without a distance or angle measurement, triangulation is still not possible.
Lastly, the iPhone 3G will offer assisted GPS capabilities. GPS is a fairly complex matter and readers are invited to study it at their leisure. Suffice it to say that a GPS location fix is based upon complex algorithms that resolve subtle timing differences between signals received from precision timing sources in orbit. If anything, out of the three methods described, GPS would come closest (at least in spirit) to using triangulation, as a receiver essentially determines its relative distance from known (although not fixed) reference points. In either case, posters on this forum usually do not use the term triangulation in reference to GPS, but rather in reference to GSM Cell ID location lookup and Wi-Fi MAC address location lookup, neither of which is actually based upon triangulation as explained above.
In conclusion, the term "triangulation" should best be avoided in reference to the iPhone or any of its 3 location determination (or approximation) methods as it doesn't properly apply to any of them.
I hope this little memo will prove useful to some readers and help reduce the use of incorrect terminology throughout the iPhone forum.
Last edited by XFF; 02-08-2010 at 02:52 PM.
Reason: removed dead link and fixed spelling error
I am a little confused. My Verizon phone was able to roam on GSM because they used TDMA. Tell it was shutdown. The phone recognizes it as Analog. If PCS has TDMA, It could be technically be used on GSM.
Originally Posted by Tabla
Y'know, I'm used to hysterical 14-year-old ******** on the internet, but this is exceptional. Never before in human history have so many nerds hyperventilated so publicly over so little.
Old Phones - Samsung Galaxy S, iPhone, Tilt, 8125, Imate Jam, SE Z600
Carrier
Deathstar
Feedback Score
0
You do realize that your definition of triangulation is completely off, while yes it does refer to a triangle in most cases, in this case (or rather when it comes to location based services), it gets fuzzy.
Even when using GPS receivers (phone, pnd, in car etc etc), they do triangulation based on time and distance from the satellites, in some cases more then 3 (up to 12 in the iphone I think??). The original definition of triangulation has blurred over the years as technology grows and they make up new definitions.
Thanks for writing such a good definition and why people's use of the term "triangulation" with Google Maps is wrong. I already knew most of the info but never bothered to write a post about it. Great writeup....thanks !!
XFF, as you have time would you mind expounding on the difference between GPS, aGPS, and A-GPS (assuming I have my acronyms correct)? I've seen so many posts on here complaining that the 3G iPhone has bad/lame/crappy/fake GPS when in reality it's A-GPS is an improvement over what we all know as "standard" GPS. I understand why that's the case conceptually but you seem to have much better technical knowledge that I and therefore a better means of explaining it.
This would make a great sticky or at least one that we could all copy/paste into the "iPhone 3G GPS sux" posts as need be.
That is the most narrow definition I've ever seen. What is it called if you use four points? I wouldn't call that a good wikipedia article. Not only does it need to be cleaned up, it doesn't cite any sources.
The left speaker is the only speaker. The right speaker is the microphone.
Even if you adopt a more broad definition of "triangulation" (as provided here), there's still no way to apply it to the GSM Cell ID location lookup and/or Wi-Fi MAC address location lookup methods deployed by iPhone.
Using the broader definition of triangulation, one could conceivably apply it to GPS, although a GPS location fix happens in a 3-dimensional (or actually 4-dimensional) space. The problem is that posters in the forum usually refer to the 2 other methods as triangulation, which are most certainly not, by any definition of the word.
You do realize that your definition of triangulation is completely off, while yes it does refer to a triangle in most cases, in this case (or rather when it comes to location based services), it gets fuzzy.
Even when using GPS receivers (phone, pnd, in car etc etc), they do triangulation based on time and distance from the satellites, in some cases more then 3 (up to 12 in the iphone I think??). The original definition of triangulation has blurred over the years as technology grows and they make up new definitions.
I already conceded (twice now) that the term "triangulation" (in its broad interpretation) could be applied to GPS. However, it can not be applied to GSM Cell ID location lookup and Wi-Fi MAC address location lookup. There simply isn't anything resembling triangulation deployed in these methods. Posters never use the term to refer to GPS (which would be somewhat acceptable), but rather to refer to the other two methods (which is definitely wrong).
I already conceded (twice now) that the term "triangulation" (in its broad interpretation) could be applied to GPS. However, it can not be applied to GSM Cell ID location lookup and Wi-Fi MAC address location lookup.There simply isn't anything resembling triangulation deployed in these methods. Posters never use the term to refer to GPS (which would be somewhat acceptable), but rather to refer to the other two methods (which is definitely wrong).
The OP has made some incorrect statements.
The correct term is 'Trilateration' which is similar to 'Triangulation'. They are similar concepts and used interchangeablely, even if technically not exactly the same. I don't blame anyone for using the incorrect term. The error is made among professionals and even in patents. GPS, Wi-FI Mac address location, and GSM Cell tower location methods use trilateration. See definitions below.
In 'triangulation', one determines the angles from a reference point(s) to the object. In 'trilateration', the distance from reference point(s) to the object are used to calculate the angles. The distance is measured by time-of-flight, relative signal strength (RSSI), etc between the user and reference point(s). The intersection of a series of overlapping circles or spheres from each reference point indicates the location of the user.
For example, in the WiFi Mac Address location system, Skyhook's US Patent (what is used by Apple in the iPhone) states (US Patent 7,305,245):
"Claim 1...using the calculated locations for the identified Wi-Fi access points and the signal strengths of said received messages and the chosen location-determination algorithm to determine the location of the user-device.
The method of claim 1 wherein the plurality of location-determination algorithms includes a triangulation technique"
They really mean trilateration. In fact Skyhook relies on lots of WiFi points, not just one.
The Encyclopedia Britannica entry is:
"Trilateration is method of surveying in which the lengths of the sides of a triangle are measured, usually by electronic means, and, from this information, angles are computed. By constructing a series of triangles adjacent to one another, a surveyor can obtain other distances and angles that would not otherwise be measurable. Formerly, trilateration was little used in comparison to triangulation, a method for determining two sides and an angle of a triangle from the length of one side and two angles, because of the difficulty of the computations involved. But the development of electronic distance-measuring devices has made trilateration a common and preferred system. Except that only lines are measured, while all angles are computed, the field procedures for trilateration are like those for triangulation."
I hope this clears up the misunderstanding. Just having the ID of a WiFI or cell tower is not enough (unless you want the location of the Wifi or tower instead of yourself). Some way of measuring the radius of the distance from that reference point is used. Having 3 or 4 points will tell you well enough, but with errors in all measurements, the more references one has, the lower the location errors.
- In simple terms, how exactly does WiFi location fix is determined? I know that "when the user initiates a Locate Me query and the iPhone is within Wi-Fi coverage, it will send the MAC address of the serving Wi-Fi base station to Skyhook Wireless, which has compiled a database of known Wi-Fi access points, their MAC addresses, and approximate location." But how does Skyhook know the location of those WiFi MAC addresses in the first place? For instance, how will Skyhook learn the location of the access point (AP) in my house? How extensive is Skyhooks database? Does it contain commercial APs or just any AP? Also, does the iPhone have to connect to an access point to determine this, or is merely scanning the air for WiFi APs enough? I suppose if connection to the AP is not necessary, then data returned from Skyhook will be received via the cellular network. Also, when I search around my neighborhood most APs are secured either with WEP or WPA, so if a connection is necessary, that removes most APs from the possible reference points, yes or no? In addition, making WiFi connections takes time, in the order of a few seconds, how is the iPhone going to have time to compute all this if you are driving a car? You'll be gone from the AP signal range by the time the query returns from Skyhook. Just driving a few blocks around my house, my laptop can see dozens of APs all coming from random directions, and the list of APs is overwhelmed very quickly as you drive by. How will the iPhone cope with such large amount of APs coming and going as you drive? Will this cause the iPhone to flood Skyhook with MAC address location requests?
- Another thing I need some clarification is when XFF says that "a GPS location fix is based upon complex algorithms that resolve subtle timing differences between signals received from precision timing sources in orbit.". So does this mean that the iPhone 3G has real satellite receiver hardware built-in just like any Garmin navigator to determine location? If so, this means that the iPhone cannot use this method indoors, correct? This also means the iPhone 3G needs to be exposed to the sky in order to determine its location using satellites.
So if I understand this correctly, the iPhone 3G can get a location fix using satellites when outdoors and it will use the other methods when indoors. Correct?
Skyhook collected the hotspots by hiring people to drive around. See if they came by your place here: Skyhook hotspot collecting
(If a person moves and takes their router with them after being surveyed in one place, then later you can get shown as being at their old location.)
The WiFi positioning doesn't need a connection. It just looks for the stations that are broadcasting their SSIDs, and uses their hardware MAC address.
As for flooding Skyhook with requests, it wouldn't normally work that way, since it's not making location requests on its own. The app has to ask. So yeah, driving down the road might just do that, unless they're smart enough to send back a cache of MAC locations in your current direction. This all assumes you're talking about the original phone using just WiFi, not the GPS one.
So if I understand this correctly, the iPhone 3G can get a location fix using satellites when outdoors and it will use the other methods when indoors. Correct?
- In simple terms, how exactly does WiFi location fix is determined? I know that "when the user initiates a Locate Me query and the iPhone is within Wi-Fi coverage, it will send the MAC address of the serving Wi-Fi base station to Skyhook Wireless, which has compiled a database of known Wi-Fi access points, their MAC addresses, and approximate location." But how does Skyhook know the location of those WiFi MAC addresses in the first place? For instance, how will Skyhook learn the location of the access point (AP) in my house? How extensive is Skyhooks database? Does it contain commercial APs or just any AP? Also, does the iPhone have to connect to an access point to determine this, or is merely scanning the air for WiFi APs enough? I suppose if connection to the AP is not necessary, then data returned from Skyhook will be received via the cellular network. Also, when I search around my neighborhood most APs are secured either with WEP or WPA, so if a connection is necessary, that removes most APs from the possible reference points, yes or no?In addition, making WiFi connections takes time, in the order of a few seconds, how is the iPhone going to have time to compute all this if you are driving a car? You'll be gone from the AP signal range by the time the query returns from Skyhook. Just driving a few blocks around my house, my laptop can see dozens of APs all coming from random directions, and the list of APs is overwhelmed very quickly as you drive by. How will the iPhone cope with such large amount of APs coming and going as you drive? Will this cause the iPhone to flood Skyhook with MAC address location requests?
- Another thing I need some clarification is when XFF says that "a GPS location fix is based upon complex algorithms that resolve subtle timing differences between signals received from precision timing sources in orbit.". So does this mean that the iPhone 3G has real satellite receiver hardware built-in just like any Garmin navigator to determine location? If so, this means that the iPhone cannot use this method indoors, correct? This also means the iPhone 3G needs to be exposed to the sky in order to determine its location using satellites.
So if I understand this correctly, the iPhone 3G can get a location fix using satellites when outdoors and it will use the other methods when indoors. Correct?
Thanks....
Hi Bobolito,
The buzz word in LBS, Location Based Services, is hybrid technologies. Combining multiple LBS systems, to get the best location fix.
Part of the Skyhook system is to create a extremely massive data base of Wi-Fi points by hiring drivers in special cars to drive around and collect the data base of public and private wifi access points - yes even the one in your home.
They are hiring drivers, BTW. WiFi have ID'd beacon signals that go up to 500- 600 feet away. It is not necessary to get the kind of quality signal (nor worry about WPA, WEP keys) to do wifi data transfer that limits WiFi's range...they are only looking at the beacon signal. The GPS in the car then reverse triangulates (or trilaterates) the wifi's coordinates into the Skyhook servers. The patents deal with how to do all of this in an efficient manner. I'm impressed when I hear that it works! The more Wifi's the better.
From this massive 'cloud' of wifi's, and the relative signal strength your iphone sees from nearby wifis, a server based complicated algorithm checks if any wifi's have moved, and then determines your possible location by several methods - including a form of trilateration. It takes about 100 to 200 milliseconds. It works indoors and outdoors. I don't know how well it works driving in a car, but moving or walking is actually helpful in some of the positioning algorithms because your movement help narrow in your location in the 'cloud' and can predict where you might be going (esp if you are following a map). But my understanding is the iphone software answers a single request for location, not a multiple request(s) as if you are driving.
Clearly it works best in urban areas where there are millions of wifis, not in rural areas. But in urban areas, this is where GPS systems can fail - indoors and in urban "no see um sky" canyons.
The GPS in the phone is an A-GPS chip (assisted GPS). Yes it works the same as the Garmin chip, BUT, it gets assistance from the Cell towers known location to reduce the processing time and CPU power needed to get that first quick fix on your location. It then uses the GPS sat's to follow your path and improved accuracy. It will not work indoors well as all GPS's don't. A real Garmin GPS has the horsepower to do it on its own, but it can take seconds to get your fix. I don't know if ATT is charging extra monthly to use the A-GPS service. Others have.
And last, but not least, for a real E911 situation, ATT has a very good trilateral LBS system based on Cell Towers that was FCC required. That is independent of anything the iphone has. We all get that for free.
So yes you are right, but it is not a black/white situation. It is a hybrid of A-GPS, Wifi and Cell tower. And most of the processing is done in servers not the iphone. And your home Wifi is part of the system!!
and download the free application called Loki. It will locate your pc on google maps, etc.
You can see how it works, without getting a iphone.
I'm on my own WiFi, of course, and considering I'm in a building with a 60 or so wifi's, Loki placed me a city block away. Not quite the 20-60 feet advertised. Go figure, but still useful.
Originally Posted by gpatrick900
Reply With Quote
WiFi have ID'd beacon signals that go up to 500- 600 feet away. It is not necessary to get the kind of quality signal (nor worry about WPA, WEP keys) to do wifi data transfer that limits WiFi's range...they are only looking at the beacon signal. The GPS in the car then reverse triangulates (or trilaterates) the wifi's coordinates into the Skyhook servers. The patents deal with how to do all of this in an efficient manner. I'm impressed when I hear that it works! 
The more Wifi's the better.
Bookmarks