Dynamic Cell-ID: Clever way to Block Google, but will it Backfire?
Location was once a unique asset for the mobile operators. You wanted to locate someone? only the mobile operator could find him/her. A valuable asset indeed, but as we now know most operators missed their opportunity to monetize it. Location is now being commoditzed and is available freely on many high end handsets, especially those that support GPS or WIFI. However Google also offers location based on the operators own base stations, and it does this in an aggregated way, across operators and countries. This service is available on any handset that supports Cell ID APIs (most smart phones and many Java devices). To be fair, operators still have the advantage of offering location across all devices, however. In addition, operator APIs are network based and don’t require that software be installed on devices which is an advantage for some applications.
How did Google build this database of operator base stations?
In case you have not already heard, it’s a simple crowd sourcing method: many handsets have both GPS and access to Cell ID. Each time one of these devices reports its GPS coordinates to Google (using Google applications like Maps) it also reports its Cell ID even if it is not required for that particular application. With so many devices reporting their location around all the base stations, Google can use a clustering algorithm to pinpoint the location of each base station and build a very accurate database. When devices that don’t have GPS (or are indoors) require a location fix, they simply report their Cell ID and Google can easily locate them with a database look up. As new base stations are added (tons are added all the time), Google quickly discovers them using the same method. Very clever indeed.
Can operators block Google from “stealing” their location information? Enter Dynamic Cell-ID
Dynamic Cell-ID is a way of dynamically assigning the Cell-ID that is reported to wireless devices by base stations. Rather than always reporting the same Cell ID, base stations report a different, dynamically generated Cell-ID. Only the operator can map the dynamic Cell-ID to the fixed Cell-ID that is required to infer location. Very clever too. You can find a patent application for dynamic Cell ID here and note the mention of shielding “illegal” service effectively. I know of at least one major European operator considering implementing this approach.
Should operators block Google? would this backfire?
As tempting as this dynamic Cell-ID approach sounds, blocking Google is not be in the best interest of operators. Imagine if Google Maps did not work for operator A customers, but it worked well for customers of operators B, C, and D? Would operator A be better off? Probably not. Customers could vote with their feet and switch to another operator. Although Google would have the option to pay the operator for access to its location API, this does not seem likely.
Water under the bridge
Rather than trying to regain control of location, operators should learn from this experience and move fast to monetize other assets before they too become commoditized. Examples of these include payments and subscriber profile. See also my post “Will Operators miss the Boat with Payments Too?”
What do you think about Dynamic Cell-ID? Should operators block Google in an effort to monetize location?
Francisco Kattan 
Great post. I noticed this in argentina, this summer, is amazing, Google maps always knows where I am.
I can tell that Claro Antennas are not mapped yet, but movistar antennas are very acurrate.
Carlos
February 7, 2010 at 4:52 pm
Hello Carlos. thank you for that report from Argentina. Yes, it’s amazing how Google is able to offer this service across geographies as well. Big advantage over operators who are highly fragmented.
I’m curious why Google has not yet mapped the Claro cell sites. Could it be that Claro does not have any handsets with both GPS and Cell ID that run Google apps (required for crowd sourcing the Cell ID database)? If that’s the case, this will be fixed soon. I noticed on their web site that they are advertising the Motorola Dext Android device already.
Another possibility is that Claro has implemented Dynamic Cell ID as discussed in this post, but I doubt this is the case.
franciscokattan
February 9, 2010 at 11:58 am
I also once thought Google was crowdsourcing Cell-ID data as well. I wrote about that here – http://goo.gl/cAAK
However, I confirmed they collect it while driving their street view data collection cars – http://goo.gl/k6Cs
Either way, dynamic Cell-ID sounds silly. Raw mobile location data no longer has value. It’s when it’s used as a piece of metadata that makes it valuable.
Jon Spinney
February 8, 2010 at 12:37 pm
Hi Jon. Thanks for the comments and the reference to your posts on this topic. Good stuff. Google itself has explained how it built its cell ID database and it is indeed by crowd sourcing and clustering. Here is Google’s explanation:
http://googlemobile.blogspot.com/2008/06/google-enables-location-aware.html
“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.”
I’m sure they would also collect cell ID data points as they drive the streets themselves. No reason not to. But driving the streets alone would not be sufficient to update the data base promptly as new cell sites are added (a frequent occurrence). Also, the crowd sourcing approach provides many more data points around each base station enabling Google to pinpoint the location of each tower more accurately.
Driving the streets also helps Google collect map images and point of interest data. As we now know, they did this in part to eliminate their dependence on pricey Navteq data and tp offer free navigation services (which they recently launched on Android 2 devices such as Droid, sending shares of Garmin and TomTom plummeting down).
In any case, Dynamic Cell-ID is a way to block Google regardless of the approach: crowd sourcing or driving the streets. I did not understand you point about Cell-ID not being valuable. Google Cell-ID does appear to have value to enable location on lower end devices that don’t have access to wifi or GPS. Also, when indoors and in rural areas GPS or WiFi is not sufficient. Can you clarify?
franciscokattan
February 8, 2010 at 2:54 pm
Hi Francisco, great post, as cell-id location is of great interest to us at Layar too. I can confirm that crowd-sourcing is used, from a first-hand conversation with the Google Manager who runs the Geo-Location team & created the crowd-sourced data-base.
Matt Miesnieks
February 9, 2010 at 1:02 am
Hello Matt. I can definitely see Layar using Cell ID for virtual reality apps. Thanks for confirming the method Google uses. Sounds like you heard from the horse’s mouth 😉
franciscokattan
February 10, 2010 at 5:43 pm
Hello guys. Do someone know what is the algorithm used by google to map cell id to locations. in other words, we know that google collects gps positions and cell id for these same positions. and when no gps available but only cell id, they will provide an approximated gps values.
How are they calculating these gps values?
Regards,
H. Touma
March 19, 2010 at 8:13 am
Hello H. Touma. I’m not aware of the actual algorithm used by Google – I don’t believe they have published it. But it is apparent, based on Google’s own description here:
http://googlemobile.blogspot.com/2008/06/google-enables-location-aware.html
that a simple clustering algorithm would work. With thousands of GPS coordinates clustering around each base station, it should not be too hard to compute the approximate location of the center of each cluster. The center of each cluster can be assumed to be the location of each base station.
If you are interested in more details on the algorithm, you may want to check the OpenCellID project at this location: http://www.opencellid.org It is an open source project to create a similar cell id database.
If someone out there has more details on the algorithm, please leave us a note.
franciscokattan
March 20, 2010 at 2:34 pm
Hello franciscokattan,
Regarding opencellid, I looked at their measuring algorithm and it works like the following: adding all gps lat/lon with the same cellid and dividing by the count number. This will return an approximate lat/lon.
I have tried this algorithm on 100,000 records of gps/cellid combinations and the result was an approximate of 1 to 2 km. Yes, sure a bigger number of cell towers will make the result more accurate, but i am sure there must be a smarter algorithm them just simply getting the average of gps positions.
I wonder how google map location, which is more accurate for the same country, is measuring the gps positions!!
Regards,
H. Touma
March 22, 2010 at 12:26 am
Hello H. Touma. Thank you very much for digging into this and sharing the results.
Perhaps I’m not understanding your results well, but if you mean that it is not possible to approximate the location of a base station to an accuracy level better than +/- 1-2 KM, I’m surprised to hear this.
I have not run through the math, but if Google can capture thousands of random GPS fixes around one base station AND if the accuracy of each GPS fix is around +/- 10 meters, I would think one could compute the location of the base station in question to a much higher level of accuracy than the 1-2 KM you suggest. But perhaps my intuition is off base.
Clearly, after the Cell ID database is complete and one wants to use this database to estimate the location of a device given its Cell ID, the accuracy of such fix would depend on the density of the base stations, possibly yielding accuracy levels as bad as 1-2 KM or even worse. But I did not think this is what you were referring to.
franciscokattan
March 24, 2010 at 7:12 pm
Hi!
In the cell-id database http://www.location-api.com we calculate cell center as the average position of the positions hooked to a specific cell. Before we do the average calculation we remove positions too far away from the cell center. The average accuracy is around 1200 meters when using one cell. By using triangulation based on signal strength from several cells we improve the accuracy. More information regarding network positioning methods can be found here: http://mediaevolution.se/nordicgame/white-paper-release-development-of-location-based-services/
Rikard Windh
May 14, 2010 at 1:57 pm
Rikard, thank you very much for sharing your results and the reference paper. For clarification, when you say that the accuracy is around 1200 meters (or better with triangulation) you are referring to the accuracy when locating a mobile device after the Cell ID database has been completed. This makes sense.
A related question that came up in this comment thread was:
When computing the location of a cell tower to begin with (with a crowd sourcing algorithm such as the one you described), what level of accuracy can be achieved? I imagine that we thoughts of positions around a cell tower the computed location of the cell tower itself would be much more accurate than the 1-2 KM that H. Touma suggested in an earlier comment (per my understanding of his comment). Is this correct? What level of accuracy can be achieved for this initial computation in your opinion?
Francisco Kattan
May 14, 2010 at 2:25 pm
Hi Francisco,
Interesting thread … on your question about the accuracy to which one can compute the location of the cell tower, I’d suggest that in many cases it’s actually not that relevant. What systems like Google’s are doing in simple terms is estimating the centroid of the geographical area where the corresponding cell serves – not the location of the cell tower/antenna itself. It’s only in the relatively rare case where the cell is omni-directional that the estimated centroid and the cell antenna location will tend to coincide.
So if we’re talking about the accuracy with which we can estimate the notional centroid of the coverage area for a particular cell, assuming the GPS/cell observations are all of similar quality (not always the case), then you have the 2-D equivalent of the standard error (http://en.wikipedia.org/wiki/Standard_error_(statistics)), and in the limit this can be very accurate.
In terms of determining a user’s location using only a Cell ID however, the average accuracy will depend on the size of the area covered by the corresponding cell. From what we’ve seen this typically ranges from 100m to 500m in major cities and grows to kilometres in more sparsely populated areas.
Hope this helps,
Malcolm
Malcolm Macnaughtan
June 16, 2010 at 7:46 pm
Hello Malcolm, very enlightening.
To be more rigorous we should have been talking about the centroid of the geographical area covered by the cell – no the location of the cell tower itself. Thank you for this contribution.
In any case, you have confirmed that Google should be able to estimate the location of these centroids very accurately which is the point I was trying to clarify. If Google has access to many thousand GPS/cell observations the standard error should approach zero, as you stated. In other words, Google’s Cell ID database is a very close approximation of the operator’s own database. Even better, it is aggregated across all operators and many countries.
Francisco Kattan
June 16, 2010 at 9:04 pm
[…] operator can map the dynamic Cell-ID to the fixed Cell-ID that is required to get the location (via this). In other words, if China Mobile (and later China Unicom, China Telecom) has this implemented, the […]
China Mobile Is To Implement Dynamic Cell-ID, LBS Services Need Pay for the Location : China Web 2.0 and Asia Tech News, Open Web Asia
January 5, 2011 at 5:34 pm
Hi Francisco,
We’re a startup from India looking to take smart tech to low end markets. Mobile triangulation and Google Maps’ database has helped us do just that; we use GSM based tracking on our vehicles with accuracy ranging from 200-500m inside the city and 1-3KM in the outskirts.
Using Google for this has been around for a while (4 years at least if this post is accurately dated – http://www.anddev.org/map-tutorials-f18/poor-mans-gps-cell-tower-id-location-area-code-lookup-t257.html).
Its disheartening that the crowd isn’t sourcing opensource projects like opencellid.org (cause Google’s just implemented 2500 requests per ip per day cap on geocoding, mapping etc).
-Gopi A.
Gopi Aravind
June 29, 2011 at 5:15 am
Hello Gopi. Thanks for the note.
Do you (or other readers) have any insights on why Google decided to cap this API?
Francisco Kattan
July 13, 2011 at 7:48 am
I’m not sure whether Google’s capped the cell-id conversion API. They haven’t even documented it! The limits I’m talking about apply to reverse-geocoding and retrieval of maps per IP address. This has forced us to do all the work at the unit’s end with its own unique IP address. Quite obviously they’re pushing serious users to move to their premium plans with a limit of 100K per day.
Gopi Aravind
July 13, 2011 at 11:56 am
[…] Maps etc.) – independent of any info from the cell tower operators/mobile network operators: Dynamic Cell-ID: Clever way to Block Google, but will it Backfire? | Francisco Kattan Reply With […]
Before Publishing to App Market - Page 2
November 22, 2013 at 4:41 am