The problem: Most current cell phones (except exceptionally new ones) do not come with built in GPS devices. Phones do however connect to radio towers within range, which broadcast ID’s. I am interested to determine if there is an easier way to generate lat/long location from radio towers, instead of using a bluetooth GPS device, by using inference from publically accessible data and geocoding, combined with the cell tower ID broadcast to my phone.
In many countries the latitude and longitude of cell towers is public data. In the US it is public sort of, when registering with FCC, the companies do not need to register the broadcast cell-id which is transmitted to the phones. To make matters more complex, different cell companies can broadcast different ID’s from the same towers. From this, many different projects have popped up to attempt to map cell-id to latitude and longitude. They work, I assume, to refine the results for each tower. The good news is, is that the FCC being a public entity is bound by the freedom of information act and must publish (even in a nasty form) it’s data. The FCC provides a large database of the exact location of towers, but we just don’t know what those towers are called and who uses them.
The idea here is that we can make some educated guesses in an attempt to refine the FCC data with what little information we are given by the tower itself and some simple server-side geocoding. Basically we are going hack the cell-id’s ‘into’ the FCC data, which we must assume will have missing towers and incomplete data as the requirement to register a tower only applies to certain tower types and array heights.
If you read my post about working with lat/long pairs in mysql and doing great circle searches, then you may find the following code snippets interesting as it is to work with doing computation on latitude and longitude. I worked these out by porting some and reading some math forums, they will come in handy for inferring my location in proximity of cell towers.
First we have a few support functions, converting to radians, and converting between lat/long types (Degree/minute/second format to degree’s and back):
function rad($v){
return ($v*M_PI/180);
}
/*
degree,minute,seconds to decimal degrees
note: this could also be done in a single line using ternary
*/
function dms2deg($D,$M,$S,$dir){
if(strpos(‘ WsSs’, $dir)>0){
return(-1 * ($D + ($M + $S/60)/60));
}else{
return($D + ($M + $S/60)/60);
}
}
function dms($rad) {
$d = abs($rad * 180 / M_PI);
$d += 1/7200; // add ½ second for rounding
$deg = floor($d);
$min = floor(($d-$deg)*60);
$sec = floor(($d-$deg-$min/60)*3600);
// add leading zeros if required
if ($deg< 100) $deg = ‘0′ + $deg;
if ($deg< 10) $deg = ‘0′ + $deg;
if ($min< 10) $min = ‘0′ + $min;
if ($sec< 10) $sec = ‘0′ + $sec;
return $deg + ‘\u00B0′ + $min + ‘\u2032′ + $sec + ‘\u2033′;
}
These are used in the following functions. First one thing we must have the ability to do is to determine the distance between two points on the map. We can use the following PHP function to do this:
/*
distance between two points using sherical law of cosines
cos c = cos a cos b + sin a sin b cos C
*/
function distance($lat1, $lon1, $lat2, $lon2, $units = ‘miles’){
$lat1 = rad($lat1); $lon1 = rad($lon1);
$lat2 = rad($lat2); $lon2 = rad($lon2);
switch ($units){
case “miles”: $r = 3963.1; break;;
case “nmiles”: $r = 3443.9; break;;
case “kilo”: $r = 6378; break;;
}
// this is another way to do it
#$rv = pi()/180;
#$a1 = $lat1 * $rv; $b1 = $lon1 * $rv;
#$a2 = $lat2 * $rv; $b2 = $lon2 * $rv;
#return (acos(cos($a1)*cos($b1)*cos($a2)*cos($b2) + cos($a1)*sin($b1)*cos($a2)*sin($b2) + sin($a1)*sin($a2)) * $r);
return acos(sin($lat1)*sin($lat2) + cos($lat1)*cos($lat2)*cos($lon2-$lon1)) * $r;
}
Next, it would be helpful to know the bearing from one point to another point.
/*
initial bearing from point 1 to point 2
*/
function bearing($lat1,$lon1, $lat2, $lon2) {
$y = sin($lon2-$lon1) * cos($lat2);
$x = cos($lat1)*sin($lat2) - sin($lat1)*cos($lat2)*cos($lon2-$lon1);
return atan2($y, $x);
}
We also would like to be able to find the exact midpoint between two points,
/*
find out what the midpoint between two points is
*/
function midpoint($lat1, $lon1, $lat2, $lon2) {
$lat1 = rad($lat1); $lon1 = rad($lon1);
$lat2 = rad($lat2); $lon2 = rad($lon2);
$dLon = $lon2 - $lon1;
$Bx = (cos($lat2) * cos($dLon));
$By = (cos($lat2) * sin($dLon));
$lat3 = atan2( sin($lat1) + sin($lat2), sqrt( (cos($lat1)+$Bx) * (cos($lat1)+$Bx) + ($By * $By)) );
$lon3 = $lon1 + atan2($By, cos($lat1) + $Bx);
if (!$lat3 || !$lon3) return false;
return array($lat3 * 180 / M_PI, $lon3 * 180 / M_PI);
}
Now that we can have some functions to work lat/long pairs we need to see how to put things together. I am going to use the following image to help explain some concepts first:
In this bad image, the 1-5 is the path we take and what we can see happening at each spot of our path. the lower-case letters are cell towers that might be broadcasting to us, but we only have a row in the FCC database knowing that a tower IS there, the uppercase ones are towers we know nothing of. We we have a little app (that will not be public just yet) that run all the time and notifies us with a beep when it finds a new cell-id and we then stop where we are and type in the nearest address which the server goecodes to our location with the cell-id’s and signal strength.
POINT 1, central park: We can see cell tower “a”, we geocode our location and mark down in the database that tower “a” is within range of the geocoded location we are at, all is good, and this is about as far as anyone has gotten so far. We run a great circle search from our location and mark the towers near us with the cell-id “a” and also make a note of the signal strength.
POINT 2, west side : We pick up an unknown tower “D” we mark it down along with a geocoded location, we also pick up “a” again and mark it again, along with signal strength and provide towers within our great circle the cell-id info. This helps refine ‘a’ but we assume we are further out as the signal strength is lower.
POINT 3, hells kitchen: we now pick up another tower “b” which we can mark in the database, we also pick up “a” within this, however both have low signal strength, we mark both with the cell-id’s and signal strength. And we can figure that we are about halfway between ‘a’ and ‘b’ we can also make some guesses about direction being travelled by using our current point along with current cell and more than one reading.
POINT 4, West village: Now we only have tower “b”, we mark this tower known with strength and it is known so again we are just confirming it’s presence.
POINT 5, Fulton street: again we have a known tower ‘c’, we mark it along with the signal strength, our prior mark was with tower ‘b’ we can infer by signal strength and our prior location that we should be about halfway between ‘b’ and ‘c’
A lot of this data can be refined as we go, but as you can see, with only a few real points and a few cell towers we can gather a lot of location data, also, we can keep a live map of our locations and where we have travelled. In some areas we can get location to within a reasonable degree that we could zoom a map to street level close by.
In an area such as Manhattan with the intense cell coverage, we can quickly refine our location to a reasonable area and pinpoint which row in the FCC database cooresponds to which cell-id by just walking around for a few minutes. In more rural areas this might be a slightly more interesting problem, but if you mark your headings as you travel we could even determine your location on the map by your speed and bearing.
As the movie progresses, the camera get closer to Theo, by the end of the movie we are running practically alongside Theo. This again is subtle, but involves you deeply with Theo and his perceptions.
