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.
Thanks for clarifying those terms. I didn't mention trilateration since it's never brought up in the forum, only triangulation, and since neither applies to Wi-Fi MAC address location lookup or GSM Cell ID location lookup - as deployed in the iPhone - I didn't want to introduce another term that would lead readers astray. GPS of course uses a form of trilateration, however forum users never associate the term triangulation (or trilateration for that matter) with GPS, but rather with the other two methods (GSM Cell ID and Wi-Fi MAC address), which are not tri-anything'ed.
Again, GSM Cell ID location lookup - as deployed by the iPhone and Google Maps - does not perform any distance or angle measurements whatsoever. It relays a single Cell ID to the server and the server responds with a range of likely locations, which the map app represents as a blue circle.
Not only does the Google writeup (which I linked to in my original memo) state that, I have conducted extensive field tests with the iPhone and GSM Cell ID location lookup that confirm that this is exactly how it works. For instance, as long as I'm camped on the same sector, I will always get the exact same blue circle in Google maps, same point of origin and same radius, no matter how far I am from the base station. In an extreme case, I was 20.5 miles (near the maximum theoretical limit for GSM transmissions) from a serving base station, yet Google maps plotted me within the immediate vicinity of that cell. There was no distance measurement involved (although the GSM system is theoretically capable of that via the timing advance parameter), hence, the iPhone performed neither triangulation nor trilateration. It simply performed a location lookup based on a single Cell ID.
As far as Skyhook, it is well possible (as I conceded in my original memo) that the Wi-Fi MAC address location lookup utilizes multiple Wi-Fi base stations simultaneously. However, this does still not qualify as triangulation or trilateration, since no true angle or distance measurement is involved. Of course, the iPhone could relay the received signal strength of the Wi-Fi signal to Skyhook's servers, but that hardly translates into a distance measurement. Who's to say whether a received Wi-Fi signal strength of -99 dBm is due to a distance of 500 yards from the base station or due to a 6" steel-reinforced concrete wall between me and a base station 20 feet away? You can't! There's no way the iPhone (or Skyhook) can know how far away you are from an access point, hence, again, no triangulation or trilateration.
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).
But that's exactly what iPhone does.
Some way of measuring the radius of the distance from that reference point is used.
Ideally - yes, but with the iPhone - no.
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.
Having more than one reference point in the case of Wi-Fi MAC address location lookup can narrow down your location to a smaller cloud, but it's not a trilaterated location fix.
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.
According to Skyhook Wireless, their WiFi location system performs this way:
With only 1 Wifi in range, the location error is ~700 feet. Makes sense since it is giving you basically the location of the Wifi access point.
With 3 to 4 Wifi access points in range, the error is ~150 feet.
In a dense urban environment, with many more WiFi's, the location error is ~50 feet.
From what I read last January, Apple opted for only the 150 foot range.
How do you think they are doing that? You need to look at the patents and numerous technical articles on Wifi LBS. The math involved is more than simple geometry, but thinking about it conceptually as Tri or multi -something is not really wrong. They claim to use a number of possible algorithms, including triangulation and multiple RSSI fingerprint maps or wieghted RSSI maps. This is right in the patent.
When they drive down a urban street, they are making an RSSI field strength 'fingerprint' map of the received wifi signals. The 'fingerprint' incorporates the integrated wifi ID, etc and the summed signal with all the losses that may be between the access points and the car. When you are on that same street, they try to match that fingerprint to what your wifi device is receiving. There is a lot of uncertainty math involved here. That is why the field is rich with technical papers. But the map is of signal strength in most systems, although other beacon id's or timing signatures have been used. Hence, the signal strength map is a form of distance measurement. I do agree, that signal strength from one or 2 wifi tells you very little since a RF shield can vary the reception quite badly. But from a cloud of numerous wifi's and with the fingerprint map, fancy algorithms can be quite wonderful.
So with these fingerprint maps, they do indeed know where you are (or how far you are) from the mesh of wifi's in your range. And they have GPS'd the WiFi access points beforehand. It is not a single point wifi identification.
This is why I said that I am quite impressed that it works at all. It seems that systems like this are being used or plan to be used in hospitals to locate which room that someone left the emergency cart in - by making use of the already installed wifi system base in hospitals. Pretty neat.
My guess, however, is when you are not on the mapped main street, but tucked away in your home or apartment, you are in an unmapped area,and you probably only get the fix of one wifi point and hence that access points location, with a huge 700 foot error radius. They probably only map the most main type of streets, not every side road. Don't really know.
I don't know what Google is doing. Perhaps they only use one tower and give you the location of it. But as you said in your memo, the towers are sectored, so at the very least they have found you one angle, since for a 3 sectored tower, that maps you into a one of the 120 degree sectors. Where I live, I normally can be seen by 3 or 4 towers, each with different RSSI dbm's If google were smart (and they are) that information can give you a fuzzy idea of where you might be, better than using the id of one tower. If you were on the fringe of your tower (20 miles out) and not picked up by another cell, you must be pretty far in the boonies.
And for certain, the ATT E911 TruePosition system does use timing signals, multiple towers when it can, and tri or multi lateration to find you. My original comment was geared toward GSM cell tower E911 systems, that do use trilateration. Not really google's method. If I hit 911 on my Nokia, this is the system used. Since the system is controlled by the police, even your iphone will probably use that first. And maybe the AGPS too. Good question. I've read that SiRF, the GPS chip maker, has just licensed Skyhook software directly into their chips, to help speed up processing and for hybrid coverage indoors or urban canyons.
I'm not trying to have a tit for tat argument with you on language. I'm just pointing out that it is a lot more complicated that just returning which single wifi access point you are using, at least in dense urban environments. It is more like a real geomapping, using WiFi's as little on earth GPS sats. I concede that I don't know what Google is doing, but real GSM Cell tower location services are a form of tri or multi lateration.
When they drive down a urban street, they are making an RSSI field strength 'fingerprint' map of the received wifi signals. The 'fingerprint' incorporates the integrated wifi ID, etc and the summed signal with all the losses that may be between the access points and the car. When you are on that same street, they try to match that fingerprint to what your wifi device is receiving. There is a lot of uncertainty math involved here. That is why the field is rich with technical papers. But the map is of signal strength in most systems, although other beacon id's or timing signatures have been used. Hence, the signal strength map is a form of distance measurement. I do agree, that signal strength from one or 2 wifi tells you very little since a RF shield can vary the reception quite badly. But from a cloud of numerous wifi's and with the fingerprint map, fancy algorithms can be quite wonderful.
So with these fingerprint maps, they do indeed know where you are (or how far you are) from the mesh of wifi's in your range. It is not a single point wifi identification.
I think we both agree on how Skyhook Wireless's Wi-Fi MAC address location lookup works in principle. The difference between your point of view and my own simply lies in whether we're willing to put all of this under the category of triangulation/trilateration. Uncertainty math and fuzzy algorithms are rarely considered essential elements of trigonometry and triangulation. But that's just my take, if you want to disagree that's fine by me as well.
I don't know what Google is doing. Perhaps they only use one tower and give you the location of it. But as you said in your memo, the towers are sectored, so at the very least they have found you one angle, since for a 3 sectored tower, that maps you into a one of the 120 degree sectors. Where I live, I normally can be seen by 3 or 4 towers, each with different RSSI dbm's If google were smart (and they are) that information can give you a fuzzy idea of where you might be, better than using the id of one tower. If you were on the fringe of your tower (20 miles out) and not picked up by another cell, you must be pretty far in the boonies.
Ok, let me try and explain the Google thing again, because I don't think I made myself fully clear. Google has no idea where the GSM base stations are located, nor do they care. Google has no concept of 120 degree GSM base station sectors either. All they know is that your mobile is served by a particular sector with a particular Cell ID (CGI) and that their database shows that other mobiles before you have reported being served by that same sector while at such and such location. So they conclude that if other mobiles have seen that sector from points X, Y, and Z, then you're probably somewhere between (or near) those points, and that's what the blue circle indicates. It's a range of locations previously reported by other mobiles while being served from that same sector with the same Cell ID.
In my 20.5 mile example cited above, my iPhone was actually able to see several other sectors, all of which were closer to me than the serving sector. However, due to topography of the terrain, it just so happened that the farthest sector had the greatest signal strength and hence was my serving sector. The iPhone definitely saw neighboring sectors in the vicinity, which would have allowed for a much better location fix, but again, the way Google's GSM Cell ID location lookup works is to only correlate the Cell ID of the serving sector with previous reports for that same sector. Since I was in a somewhat contrived situation where my serving sector was actually the farthest away, it seems that they hadn't gotten any previous reports of that Cell ID being seen in that locale, hence the position fix I received from Google was limited to an area much closer to the serving base station, where users would routinely camp on that sector. I only brought it up as proof positive that Google's algorithms doesn't take any distance measurements into account, and hence can't possibly qualify as trilateration.
And for certain, the ATT E911 TruePosition system does use timing signals, multiple towers when it can, and trilateration to find you.
No question about it. AT&T's e911 system gets a much better location fix than Google Maps, but that's a network based system, and the information is only available to AT&T. The mobile can not determine it's own location using that same system. TruePosition is absolutely based on trilateration and is a proper application of that term, but there's nothing in the iPhone that's in any way special or unique to the TruePosition system. In fact, AT&T specifically chose a network based e911 location system so they wouldn't have to police and retrofit their entire fleet of mobiles deployed in the field, the way VZW, Sprint, ALLTEL, and every other CDMA carrier had to do.
My original comment was geared toward GSM cell tower E911 systems, that do use trilateration. Not really google's method.
Ok, thanks for clarifying that. However, if your comments were geared towards something that I didn't even cover in my original memo, it may have been slightly presumptive and preemptive of you to state that I "made some incorrect statements". If the scope of your statements is unrelated to the scope of my statements, then even if your statements are correct and different from my statements, you can't conclude that my statements were made in error. That's a logical fallacy.
I'm not trying to have a tit for tat argument with you on language. I'm just pointing out that it is a lot more complicated that just returning which single wifi access point you are using, at least in dense urban environments. I concede that I don't know what Google is doing, but real GSM Cell tower location services are a form of tri or multi lateration.
Fair enough. I think we thoroughly established what each of us was trying to get across, all true, just referring to different things.
Ok, let me try and explain the Google thing again, because I don't think I made myself fully clear. Google has no idea where the GSM base stations are located, nor do they care. Google has no concept of 120 degree GSM base station sectors either. All they know is that your mobile is served by a particular sector with a particular Cell ID (CGI) and that their database shows that other mobiles before you have reported being served by that same sector while at such and such location. So they conclude that if other mobiles have seen that sector from points X, Y, and Z, then you're probably somewhere between (or near) those points, and that's what the blue circle indicates. It's a range of locations previously reported by other mobiles while being served from that same sector with the same Cell ID.
In my 20.5 mile example cited above, my iPhone was actually able to see several other sectors, all of which were closer to me than the serving sector. However, due to topography of the terrain, it just so happened that the farthest sector had the greatest signal strength and hence was my serving sector. The iPhone definitely saw neighboring sectors in the vicinity, which would have allowed for a much better location fix, but again, the way Google's GSM Cell ID location lookup works is to only correlate the Cell ID of the serving sector with previous reports for that same sector. Since I was in a somewhat contrived situation where my serving sector was actually the farthest away, it seems that they hadn't gotten any previous reports of that Cell ID being seen in that locale, hence the position fix I received from Google was limited to an area much closer to the serving base station, where users would routinely camp on that sector. I only brought it up as proof positive that Google's algorithms doesn't take any distance measurements into account, and hence can't possibly qualify as trilateration.
Ok, now I'm even more confused about google's method of location. Maybe you can help me out.
If Google has no idea of a cell tower's base stations GPS location, but counts on reports of previous mobile users in range of that Cell ID's tower, how do they get those lat,long (X,Y,Z location) reports from the previous mobile user in the first place? Is the user sending his exact or even fuzzy rough location to Google? Are they counting on the previous mobile having a aGPS?
I thought the idea was for google to tell you where you are,not vice versa. And if there were no previous users in a new, different cell ID tower range, then they can't tell you anything until after the first guy shows up and leaves?
What am I missing?
In your 20.5 mile experience you say that they had no previous reports of that Cell ID being in that locale, so they placed you 20 miles away, close to the tower. So if you went back again, would they place you more properly? How did they learn from your being there to update their database? In that situation, how would they ever place you anywhere else except at the tower, 20 miles away? How do they know were users camp except in a 20 mile radius from he tower?
A co worker of mine was in Europe with a non-iphone, but with 2.0 Google maps. He was also able to see tower's ID's. When he first hit '0' to get his location, it was off in position,and placed him near the only receiving tower that showed up. A few minutes later, he noticed that another tower was in sight, so he had two now. Hitting '0' again, Google placed him more correctly at a distance between the two cell towers. That would only happen, that i can see, if they were using both towers. He was hoping to see a third tower, but no luck.
the problem with aGPS in IPhone and most phones that have aGPS is the fact that standard mode is never allowed. Meaning that the aGPS chip will not allow you to switch to a satellite only mode. Most aGPS chips are always on satellite and cellular tower mode.
Why is this an issue....it means to use GPS you need to use the cellular network and thus you are paying for cellular usage.
With my HTC Artemis and other phones with true standard GPS chipset. I never pay to use GPS with TomTom or other software, since it is a satellite only connection.
If Google has no idea of a cell tower's base stations GPS location, but counts on reports of previous mobile users in range of that Cell ID's tower, how do they get those lat,long (X,Y,Z location) reports from the previous mobile user in the first place? Is the user sending his exact or even fuzzy rough location to Google? Are they counting on the previous mobile having a aGPS?
As stated in the Google link
If the phone has GPS, the Maps application on the phone sends the GPS coordinates along with the cell ID to the Google location server. Over millions of such updates, across multiple phones, carriers, and times, the server clusters the GPS updates corresponding to a particular cell ID to find their rough center. So when a phone without GPS needs its own location, the application on the phone queries the Google location server with the cell tower ID to translate that into a geographic location, i.e., lat/long coordinates.
Also, from what I know about GSM technology, unlike CDMA, a GSM cell phone only talks to one tower at a time. Therefore the Google Maps application would only have the cell id of one tower.
... how do they get those lat,long (X,Y,Z location) reports from the previous mobile user in the first place? Is the user sending his exact or even fuzzy rough location to Google? Are they counting on the previous mobile having a aGPS?
Yes, all the Windows Mobile, Blackberry and Symbian phones with GPS that were running Google Maps Mobile (GMM) starting back in 2006, were secretly being used to collect a cell tower database.
This was revealed in late 2007 when Google debuted the Locator service for non-GPS phones (and a few months after that for the iPhone).
Google is still silently collecting info. The software agreement we made in iTunes to get Google Locator, states that Google can collect our searches and location anonymously, and even show all our anonymous positions in realtime on a map.
A co worker of mine was in Europe with a non-iphone, but with 2.0 Google maps. He was also able to see tower's ID's. When he first hit '0' to get his location, it was off in position,and placed him near the only receiving tower that showed up. A few minutes later, he noticed that another tower was in sight, so he had two now. Hitting '0' again, Google placed him more correctly at a distance between the two cell towers.
Sounds like that's where others with real GPS had used Google Maps while connected to the second tower. Therefore GMM would place your friend there. In other words, there weren't any other searches done with onboard GPS in other positions around the second tower.
Also, from what I know about GSM technology, unlike CDMA, a GSM cell phone only talks to one tower at a time. Therefore the Google Maps application would only have the cell id of one tower.
GSM may have only one voice connect, but the data beacons from several Cell tower are aware of your phone presence. Really this was the first LBS system used many year ago. My phones will list 3,4 or more towers, the ID's and the dBm signal strength to received by my phone. It should not be hard for Google to suck those other ID out of the phone too.
Thanks for the post and from others.
"
Originally Posted by KDarling
Yes, all the Windows Mobile, Blackberry and Symbian phones with GPS that were running Google Maps Mobile (GMM) starting back in 2006, were secretly being used to collect a cell tower database.
So it seems that Google makes a map or fingerprint of likely locations based upon GPS location services within a cell or cells of tower's range. This is not too different from the WiFi based system where the Skyhook driver has the GPS and is mapping out his presence relative to the wifi access points that he finds via reverse triangulation. I suspect that google is being a little coy, doing more than they want to say. This is from their web page http://www.google.com/support/mobile...73&topic=13541
"These cells come with identification numbers, but no location information. Google takes geo-contextual information [from anonymous GPS-readings, etc] and associates this information with the cell at that location to develop a database of cell locations. Based on this information, Google uses various algorithms to approximate your location relative to the cells(plural) nearest you."
Since the maps or "geo-contextual information". is made from GPS it is a little far fetched to say they have nothing to do with those location techniques, IMO. Similar to reading a paper map and ignoring how it was made.
But really, I thought it was not very hard to get the GPS locations of cell towers. I thought they were published on some FCC site or the like. Isn't that true? So I think Google knows the site locations, they are just wanting to get some gps mapped space inside their range for their multiple algorithms. I'm sure, like others, they use different math models depending on the conditions.
Ok, now I'm even more confused about google's method of location. Maybe you can help me out.
If Google has no idea of a cell tower's base stations GPS location, but counts on reports of previous mobile users in range of that Cell ID's tower, how do they get those lat,long (X,Y,Z location) reports from the previous mobile user in the first place? Is the user sending his exact or even fuzzy rough location to Google? Are they counting on the previous mobile having a aGPS?
I thought the idea was for google to tell you where you are,not vice versa. And if there were no previous users in a new, different cell ID tower range, then they can't tell you anything until after the first guy shows up and leaves?
What am I missing?
You're not missing a thing! That's exactly how it works.
In your 20.5 mile experience you say that they had no previous reports of that Cell ID being in that locale, so they placed you 20 miles away, close to the tower. So if you went back again, would they place you more properly? How did they learn from your being there to update their database? In that situation, how would they ever place you anywhere else except at the tower, 20 miles away? How do they know were users camp except in a 20 mile radius from he tower?
Well, in my case since I was using an iPhone that doesn't have GPS, the correct location was never communicated to Google, so they were unable to capture that locale as a possible match for the Cell ID of the sector that happened to serve me at the time. If another user with say a BJ II should visit that same locale and initiate a Google location inquiry, then they'd be able to add that point to their database, and then if I return some time after that, the blue circle might be widened to include that locale. (In reality however, I doubt that would happen since I assume that their algorithms eliminate unprobable locations, even if they have been properly reported. I would assume they heavily weigh those locations that are clustered close together and reported frequently, rather than some exotic far away location that was reported once.)
Also, from what I know about GSM technology, unlike CDMA, a GSM cell phone only talks to one tower at a time. Therefore the Google Maps application would only have the cell id of one tower.
While it is true that a GSM mobile always communicates with exactly one sector at a time, the mobile is aware of other sectors in the vicinity, those are called neighbor cells. The mobile keeps an up-to-date list of neighbor cells and routinely performs signal strength measurements on each of them and reports the results (along with each CGI) to the serving sector. These data are then used in handoff procedures.
Anyway, my point was that while it would be possible for a location determination entity to consider the neighbor cell data in addition to the serving sector's CGI, this is just not how Google's LBS currently works.
But really, I thought it was not very hard to get the GPS locations of cell towers. I thought they were published on some FCC site or the like. Isn't that true? So I think Google knows the site locations, they are just wanting to get some gps mapped space inside their range for their multiple algorithms. I'm sure, like others, they use different math models depending on the conditions.
I believe only free standing towers over a certain height are registered with the FCC. But very many sites are not towers, rather on buildings, bridge supports, utility towers, etc. I think those are not registered at all.
I believe only free standing towers over a certain height are registered with the FCC. But very many sites are not towers, rather on buildings, bridge supports, utility towers, etc. I think those are not registered at all.
If I remember correctly from my radio days, all commercial transmitting stations, certainly above a specific effective radiated power, must be licensed by the FCC, and the location given on the license, at least by street address.
Yes, tower locations and most antennae are registered with the FCC. But that's all. There is no Cell Id or often even (because of subleasing) carrier information.
So locations alone are pretty useless. For example, in a one mile radius of the Empire State Building, there are around 100 towers and over 2,000 antennae (!). Trying to figure out which cell id belongs to which, is impossible.
The only way to use those towers is to empirically collect the association between a certain location and the cell id(s) that are available.
Such collecting is not a new idea. For years, there have been public freeware projects where volunteers collected cell id (and wifi) information. Google and Skyhook simply commercialized the idea.
The same concept is used by the military, in case of GPS jamming or satellite destruction. In that case, public radio / TV station and cell locations would be used to derive location.
One more piece of critical info: cells can change ID. Especially when being sold between carriers. CDMA towers often do so, for reasons I'm not clear about. But most likely it's done to prevent people from using them to create a database.
Carriers like to sell location based services. Giving out public cell id / tower location information would undermine that business. Rumor says that the iPhone Locate Me didn't work at first in the UK because that carrier used to change Cell IDs on a daily basis (!).
But really, I thought it was not very hard to get the GPS locations of cell towers. I thought they were published on some FCC site or the like. Isn't that true?
The short answer is: mostly no.
The somewhat longer answer goes like this: cellular licenses have a geographic coverage requirement, and in order to enforce that, the FCC requires that cellular carriers submit the location and propagation characteristics of all base stations the make up the CGSA (cellular geographic service area). Those are the sites that are located near the boundary of the CMA (cellular market area), and hence tend to be rural boomer sites that cover a very large area. (Typically, a CMA has a large city in the center and more rural counties around it.) Anyway, due to those requirements, the FCC ULS (universal licensing system) can be used to obtain the location of those sites that define the CGSA. However, in reality, most sites cover a small area and are clustered tightly together in the center of the CMA, and therefore do not contribute to the CGSA. For instance, in my CMA, AT&T has well over 200 sites deployed, but the ULS only lists about 20 of them, that's roughly 10%. You could go visit those sites and collect the CGI of each sector, but you'd be missing 90% of the sites (and probably 97% of the CGIs reported in location queries).
Now that's only for cellular. PCS is a different story altogether. Since PCS licenses do not have a geographic coverage stipulation, no site reporting is required at all. It is nearly impossible to obtain PCS sites via the ULS.
Apart from the ULS, there is ASR, the antenna structure registration system. This database encompasses all antenna structures that must be registered with the FCC, not just those used for CMRS, but anything, including radio, TV, microwave point-to-point, public safety, you name it. But there's two problems with that. First, only sites that exceed a certain height (or are in the approach path of an airport) need to be registered (this precludes many urban and suburban sites), and second, the sites that are registered with the ASR list the site owner, not the lessee. Since most CMRS carriers do not build their own sites, but rather lease space on existing sites to place their antennas, most listings you will find are for tower companies such as Global Tower, Pinnacle, American Tower, Crown Castle, etc. rather than for the CMRS carrier that may be using that site.
In summary, it is far from trivial to create a complete database of carrier site locations with associated CGIs. Of course it can be done, but it's not a matter of perusing public records and be done with it.
This is exactly why Google chose to empirically build their own database of CGI location ranges. It actually makes more sense this way, because even if you had a complete and accurate list of CGI and base station location, that doesn't necessarily help you in locating the mobile, but rather the base station itself, which is of no particular interest to a mobile user. Unless you have a complete CGI-location database and are able to perform distance measurements from the mobile to multiple sites (which would allow for trilateration), Google's approach is more practical, albeit less accurate.
Originally Posted by Viewfly
Reply With Quote
Bookmarks