By Brad Tombaugh 17 July 2010
Brad@Tombaugh.orgwww.Tombaugh.orgBrad@FullCircleTechSolutions.comwww.FullCircleTechSolutions.comBTombaugh@gmail.comTombaugh.BlogSpot.comDraft 1.0
Introduction:
One of the side-effects of
"wardriving" to detect the locations of
wireless access point (WAP) using a mobile device such as a laptop computer with a
GPS is that all of the locations of the WiFi hotspots all appear on a map at the location where they were detected, not where the source of the radio signal originates. This generally means that all of the mapped locations of detected networks are marked in the middle of a street.
Theorum:
The geographic location of a
wireless access point (WAP) can be approximated by recording the
GPS coordinates and signal strength in three or more locations. The point of origin can then be calculated using
trilateration.
To optimize efficiency for use with a mobile device such as a smartphone, use of a simple algorythm to capture four points, corresponding to the minimum and maximum latitude and longitude coordinates where the signal from the WAP can be conveniently measured.
Assumptions:
The maximum signal range of a typical commercially produced, consumer-grade wireless access point is roughly 300 ft or 100m.
Since most commercial wireless equipment is provided with an omni-directional antenna, its assumed that the radio signal radiation pattern can be expected to be roughly circular.
While buildings and terrian can reduce the range of wireless signals, in a typical residential area the interference could be assumed to be roughly equal in all directions. Thus, it can be safely ignored when estimating the location of the access point.
The radiated power of the wireless radio signal decays using the
inverse square law, decreasing exponentially with distance. The further from the source of the signal, the lower the power reading.
The radiated power of a typical wireless access point can be expected to be in range of a maximum of -10
dBm to a minimum usable signal strength of -95
dBm.
Due to a maximum distance of less than 500 feet, simple Cartesian coordinates could be used, rather than
great circles or
Vincenty's Formula.
The observed wireless access points are assumed to be stationery, remaining in a fixed position. I.e. not another mobile device, but a wireless access point/base station.
Approach:
To estimate the actual geographic location coordinates of a wireless access point in a residential or commercial building, readings are typically taken with a laptop computer or wi-fi equipped smartphone. A built-in or externally connected GPS is used to record the coordinates where a signal reading is taken. In practice, readings are generally taken while driving in a moving vehicle on a public street, or perhaps walking with a smartphone. Typical practice for
"wardriving" applications such as KisMac are to record the GPS location at the first point where a reading of a particular wireless access point is acquired. The
Basic Service Set Identifier (BSSID) and
MAC address are recorded for identification. The deficency of this practice is that all of the recorded wireless access points appear to be on streets when the coordinates are mapped, and do not reflect the true origin of the wireless access point.
Commercial applications like
SkyHook Wireless record a large number of readings from many points, and use a server-based application to aggregate the results. This approach is impractical for a single laptop or mobile device.
Rather than collecting a large number of points, only three points are needed to trilaterate the location. The question is how to determine which of many possible points should be recorded. My approach is a simple process to record coordinates and signal strength at the four "corner points" with the minimum and maximum values for latitude and longitude. This can be determined using a simple calculation to see if the observed point is greater than the previously recorded maximum for either latitude or longitude, or if the point is less than the previously recorded minimum values.
Once four points have been collected, the approximate location of the origin can be calculated by determining the intersection of four circles representing the recorded coordinates as the origins of each circle, having a radius relative to signal strength reading.
Since Android smartphones report the signal strength in
dBm, ranging in value from -10dBm maximum signal strength, to a minimum detectable signal strength of -100dBm, it is easy to approximate the distance from the source by using the absolute value of the signal strength as the distance in meters. This correlates to an approximate distance of 30ft or 10m where the signal strength is the strongest, to approximately 300ft or 100m where the signal strength is the weakest.
Calculation:
Calculation of the intersection of four circles is based on this
article at Mathworks:
yes, four circles n radii is known..... all are different radii also...... can u tell me the algorithm for it...... i must find center for the intersection area also.......... i hav an image to show the intersection area made by four circle but i don know how to post it..... recommend any site to post pic for view......
Ok, if the radii are known, then just do this. We know the equations of each circle.
(x - x1)^2 + (y-y1)^2 = R1^2
(x - x2)^2 + (y-y2)^2 = R2^2
(x - x3)^2 + (y-y3)^2 = R3^2
(x - x4)^2 + (y-y4)^2 = R4^2
Subtract one from the rest. Thus
2*(x2 - x1)*x + 2*(y2 - y1)*y = R2^2 - R1^2 + x1^2 - x2^2
2*(x3 - x1)*x + 2*(y3 - y1)*y = R3^2 - R1^2 + x1^2 - x3^2
2*(x4 - x1)*x + 2*(y4 - y1)*y = R4^2 - R1^2 + x1^2 - x4^2
This is a linear system of 3 equations in the two unknowns (x,y). Solve using backslash (\ operator in Matlab).
A = 2*[(x2 - x1),(y2 - y1);(x3 - x1),(y3 - y1);(x4 - x1),(y4 - y1)];
rhs = [R2^2 - R1^2 + x1^2 - x2^2 + y1^2 - y2^2; ...
R3^2 - R1^2 + x1^2 - x3^2 + y1^2 - y3^2; ...
R4^2 - R1^2 + x1^2 - x4^2 + y1^2 - y4^2];
xy = A\rhs
This will derive an estimate of the center coordinates.
See an
illustration.
Alternate Calculation:
Since the calculation of the intersection of four circles is rather complex to perform on a mobile device, we can approximate the position by determining the bounding rectangle where the four minimum and maximum latitude and longitude points where the wireless signal was detected. This may not work in all cases, but can serve as an illustration of the approach. In particular, this approach would not yeild good results for cases where there are not detection points from at least three sides. The origin of the signal would have to be contained within the area defined by the detection points.
We can further refine the bounding rectangle which should contain the origin of the signal source by determining the boundries implied by the relative signal strengths measured at each of the points. For example, if the signal strength measured at the northern-most point was -90dBm, we would assume that the source of the signal must be within approximately 90m south of the coordiantes recorded. By calculating the coordinates with maximum distances from the points of detection, based on the signal strengths measured at each point, we can determine a small area bounded by these points. There should be a high probability that the source of the wireless signal originates from within this bounding rectangle. Taking the geometric centroid of this bounding rectangle should approximate the origin of the wireless signal.
This can be illustrated by the
interactive map linked here. The white circle drawn in the center of the map represents the actual location of the wireless access point, or the origin. The blue circle represents the approximate range from the northern-most point of detection, based on the signal strength. The yellow circle represents the eastern-most point of detection, the red circle for the southern-most, and the orange circle representing the western-most point of detection.
From this set of coordinates, we can draw a bounding rectangle shown in purple, which represents the range of coordinates where the wireless signal could be detected. Based on the layout of streets and accessability of the area, the actual origin of the signal could be contained with this bounding rectange if the points of detection were accessible from at least three sides, or possibly all four sides. However, in cases where the wireless signal can only be observed from one side, such as a facing street, the bounding rectangle defined by the points of observation would not encompass the origin, but would be adjacent to it.
Because we cannot be certain that the set of detection points actually enclose the point of origin, and to determine the smallest possible area with the highest probability of containing the point of origin, we calculate a bounding rectangle by determining a set of points which are the furthest possible distance from the minimum and maximum geographic coordinates based on the measured signal strength.
The bounding rectangle shown in green on the map below represents the most likely boundries in which the signal originates, by calculating the distances infered from the measured signal strength at the extreme coordinates where the wireless access point could be detected.
Implementation Approach:
The
Android smartphone environment is well suited to this approach, since it combines a
wireless network transceiver, with signal strength reported in
dBm, with a
GPS receiver with good precision, along with enough computing power and data storage to record the detected coordinates. The
Android-Wardrive application by Raffaele Ragni is particularly well-suited to this approach because it already records its data in a
Sqlite3 database. It also shows a map of the detected wireless access points using the
Google Maps API, and can export to an online database or a
Google Earth KML file.
The first step to implementing this approach would be to extend the Sqlite3 database schema to include four additional coordinate pairs as well as their signal strength. The existing coordinates could be retained to map the initial point of detection, and could be updated by the geolocation calculation.
Due to the computing overhead involved in performing the calculations, it would not be recommended to attempt to calculate the geolocation in real time. There will be significant amount of additional overhead in collecting the additional data points, especially in an area with multiple wireless access points. Additionally, the method for geolocation requires that a reasonable survey be completed to detect the greatest diversity of locations for best results.
During the initial detection of a new wireless access point, in addition to logging the current geographic coordinates and BSSID, the initial coordinates and signal strength should be written to each of the peripheral coordinate pairs.
With each subsequent reading, the current location point would be compared with the four peripheral coordinate points. If the new reading is further North (current latitude > stored Northern latitude) then the new coordinates (both latitude and longitude of the current location) along with the signal strength should be written as the Northern-most coordiantes. If the new location is further South (current latitude < stored Southern Latitude) than the current location coordinates (both latitude and longitude) and the signal strength should be stored as the new Southern-most point of detection. Similar comparisons should be made for each of the extreme East and West points of detection using the maximum and minimum longitude. It is both possible and likely that during the initial data collection, each new point detected could replace two of the previously recorded coordinate pairs.
The geolocation calculation could either be added as an addition option under the menu, or could be combined with the Export to KML option.
