Page 1 of 2

range mapping algorithm

PostPosted: Tue Jul 19, 2005 8:06 pm
by thrillho
Hi,

I've searched but was unable to find the script or answer to my question, so here goes:

Does anyone know the general algorithm for determining an Access point's range based on signal strength or snr?

Someone here has to, because someone wrote the script pictured on this page: http://eyecannon.com/wardrive.html (scroll down, it's the one with the blue circles)

if no one knows off the answer, could they point me to the source of that script (if it exists) so that I might learn.

thanks!

PostPosted: Tue Jul 19, 2005 8:14 pm
by King_Ice_Flash
Most of them go by how far away you were when the weakest, then the center is the point of the strongest signal.

You could not calculate range by SNR, because of the environmental effects, and the hardware circumstances.

PostPosted: Tue Jul 19, 2005 8:19 pm
by Thorn
There is no accurate algorithm. Too many variables come into play, such as doors, windows, construction materials, etc.

Those are gpsdrive maps from kismet. They are educated guesses, based on several readings, but are not necessarily accurate.

PostPosted: Tue Jul 19, 2005 8:25 pm
by thrillho
well, I am looking for something that is on-the-fly and not something that would require me to encircle a single access point for extended periods of time.

ideally, it would be able to use something outputted by netstumbler during a wardriving session (I was just assuming signal strength/lat-lon coords would be the best bet). does such a thing even exist or is it even plausible? I was under the impression that this is what happens here
and in GPSMaps range circles.

Also, I'm not concerned with how accurate this is, I'd just like to be able to implement something similar to GPSMap's range mapping on a windows platform.

PostPosted: Tue Jul 19, 2005 8:41 pm
by Thorn
thrillho wrote:... Also, I'm not concerned with how accurate this is, I'd just like to be able to implement something similar to GPSMap's range mapping on a windows platform.


The simplest way to do that would be exactly what KIF said above:


King_Ice_Flash wrote:Most of them go by how far away you were when the weakest, then the center is the point of the strongest signal.


In other words, sort your readings of a particular network highest to lowest.

1) The Long/Lat of the highest Signal strength becomes the center of your circle.
2) The Long/Lat of the lowest Signal becomes a point on the radius of the circle.

3) Invoke the circle_draw_by_radius function of whatever graphics calls you're using, using the info from steps 1 & 2.

Repeat for next AP.

Oh yeah. Just a thought, but you'll proably need to do some sort of filtering on things like the Sear's Service trucks' (and other mobile) SSIDs. Otherwise, you could have some circles several hundred miles in diameter if a truck happens to be pacing you on the highway.

PostPosted: Wed Jul 20, 2005 2:07 pm
by thrillho
thanks for the replies. I was hoping not to have to learn vbscript to do this, but I might look into getting my feet wet. As an alternative, I found and came up with this if anyone is interested:

http://loop.interop.com/comments.php?id=92_0_1_0_C

This page proposes a method for measuring wireless network range by finding the mapl (maximum acceptable path loss). mapl is found by finding the difference between transmit and receive powers of the access point. Netstumbler outputs the receive power as Signal. Transmit power is determined on a per router basis, but I did a little bit of digging through various manufacturers' tech specs and found that the average for an unmodified router is between 15-20 dBm. Therefore, in my crude example, I use 15 dBm since I want to compute the minimum distance for good signal.

The range for an access point with a mapl of 70 is 10m. range increases by a factor of 2 everytime mapl increases by 10. therefore a mapl of 80 produces a range of 20m, and a mapl of 90 a range of 40m. I fitted a curve to these numbers and came up with the equation of:

range = .0781*e^(.0693*mapl)


This is probably not accurate do to the fact that you are using the receive power that netstumbler outputted having last seen the network and you could be anywhere within it's effective area coverage. However, I thought I'd share my findings for whoever might want to use them.

PostPosted: Thu Jul 21, 2005 10:11 pm
by streaker69
Your example and your formula may work in a perfect world (good job on the research though, it's seldom we see such good information) but unfortunately, I think you'll find in practice that it doesn't work. Building materials, trees, shrubberies and even sunspots can interfere with your readings. You might get a rough guess on range, but it would probably be a really rough guess.

Plus you'd get different readings based upon direction of which you're passing the AP. For example, one of my AP's is in my pantry. Opposite the AP is a metal ductwork for the central air system. If you were to be in direct line with that ductwork in relation to the AP, you'd have a degraded signal in comparison to approaching the AP from another direction.

I guess you could do some testing and maybe tweak your formula somewhat to take into account for building materials and such.

PostPosted: Fri Jul 22, 2005 5:20 am
by Thorn
It is interesting, but something kept nagging me about the MAPL method. I finally realised what it is that's bothering me about it: From a standpoint of "If we set up an AP at Point X, then we should be able to get a usable signal up to Y meters away", then the MAPL would appear to deliver good estimates. For the "average guy" setting about an "average AP" this is probably fine, since he's just determining a rough range.

For what we are doing though, I'm not sure this will work very well. First of all, we don't have a known point where the AP is located. The best we have is a point where we received the highest Signal level reading. We tend to assume that this is the point in space where we are closest to the AP, although this isn't always true. Due to multi-path and the nature of 2.4GHz RF, the signal can and will travel in some pretty strange ways.*

Secondly, what we are doing with an active scanner (ie. NetStumbler) involves two transmitted signals. One from the mobile unit running NS or MS, and one from the responding AP. In order to make this method work for what we are doing, you would need to work out the MAPL for your mobile rig and work that into the equation.

Finally, this method doesn't take a number things into consideration which will influence an actual signal: Things like the antenna gain, height above ground, RF-LOS and constuction material at all play a part. The MAPL may be a good starting point for some real world algorithms, but I think it may need to be tweaked for actual mapping from WarDriving.

*For a good real world example of how signals can bounce, look at this thread:
http://www.netstumbler.org/showthread.php?t=6058

PostPosted: Fri Jul 22, 2005 5:57 am
by thrillho
thorn and streaker, you are right. I finished the new plotting utility last night and the results are just as thorn suggested. here is a screenshot of part of a driven area.

screenshot

as you can see in the northern half of the picture, as I drive down the street, networks are plotted as being in the middle of the street. this is because the point at which I picked up the signal is closest to the middle...however I could be anywhere within the AP's effective range.

also, it does work much better when you are able to get closer in toward an AP. I live in the area depicted in the southern portion of the picture (google earth is a tad outdated, there are no woods there anymore). when I parked my car right next to the apartment complex, I was able to get much stronger and more plausible ranges.

so, this was an interesting experiment, but it looks like I will be learning vbscript to actually accomplish this (shouldn't be too hard though...just need to learn I/O).

PostPosted: Fri Jul 22, 2005 6:31 am
by Thorn
THis thread from last year may be of interest:
http://www.netstumbler.org/showthread.php?t=12096

actually...

PostPosted: Thu Jul 28, 2005 5:31 pm
by deymious
Actually determining location based on signal strength is very hard. I've been working on just that for nearly the past year at school and it hasn't gotten any easier. We have a statistics package running a radio propagation model with more than enough training data at 2000 iterations per measurement, and the best we can get indoors is about 1 to 5 feet off. The signal is captured by a 19dB CNC antenna wired to an Aironet PCMCIA card (no internal antenna). Outdoors is easier, but once the range increases insane things happen. The problem is, sadly, the radio frequency chosen. 2.4GHz is in the unlicensed band... and the reason is that it pretty much sucks at going farther than 20ft without getting scattered all over the place, so no one wanted to license it (also it isn't powerful enough to disrupt much other stuff). ANY hard, or densely-packed material (metal, trees, concrete, asphalt, dirt, etc.) more than 4 inches thick will COMPLETELY bounce a 2.4 GHz signal... and if the object is thinner, it will only partially disrupt the signal, but in roughly linear proportion. AM and FM waves have MUCH longer wavelengths (MHz as opposed to GHz), which make them bouncable only by things like mountains or lots of skyscrapers and such. The way to go is probably to just record all the info and post process it. Keep in mind, I can only get 1 to 5 foot accuracy with a radio map... if you're trying to do this without a radio thumbprint of the area it gets very hard very fast. If you know anythng about statistics and probability modelling check out Bayesian networks and the M4 model. If not... don't despair at rough results... it isn't easy when you have a lab, people to work with, and research funds to draw on.

PostPosted: Wed Nov 16, 2005 7:30 am
by xmat
Hi,

I found this discussion very useful. I would like to apply the mapl formula for a statistical study that looks at the probability of an AP being situated within a specific radius of a given monitoring location. My intent is not to find the precise location of the AP, but to be able to say that there is an X probability that it could be found within X meters of the monitoring location.

I am not an engineer and I would need help understanding the way in which the Mapl value is calculated. From the article thrillho referenced on the forum it appears that mapl is basically the Signal value, as recorded by Netstumbler, minus the sensitivity value, which varies from AP to AP, right? Now, suppose Netstumbler gives a Signal value of -75db and the ap sensitivity value is 15db. Since signal values are always negative the Mapl value should be -75-15=-90. Or am I wrong? Should we use the signal absolute value, and we have 75-15=60?

Second, e^(.06*mapl) is the natural log exponent, right?

Third, I came up with this excel formula for calculating the range

=0.0781*EXP(0.0693*(SIG-SENS)) where Sig is the signal value and sens is the sensitivity value. Is this OK?

Fourth, is there a quick method for finding the sensitivities for the different devices--I am thinking of a website or database--so that I could assign each access point its specific sensitivity value before I run the formula?

I would appreciate your help and once again you all did a excelent job with emphasizing the positives and negatives of this issue.

Sorin A. Matei
__________________
SAM

PostPosted: Thu Nov 24, 2005 7:05 pm
by DreadedOne509
Would it be possible to script a triangulation formulae to determine approximate location using signal strength(s1, s2, s3), latitude(t1, t2, t3), longitude (g1, g2, g3), and SNR (r1, r2, r3) ? It may not be exact, but I would think it would more often than not be more accurate than using just one record. If you mapped your route out ahead of time, so as to approach known AP's from different angles (120 degress off from previous optimally). The actual angle could be determined from the Lat/Long point, could get even more accuracy.

PostPosted: Thu Nov 24, 2005 7:07 pm
by streaker69
DreadedOne509 wrote:Would it be possible to script a triangulation formulae to determine approximate location using signal strength(s1, s2, s3), latitude(t1, t2, t3), longitude (g1, g2, g3), and SNR (r1, r2, r3) ? It may not be exact, but I would think it would more often than not be more accurate than using just one record. If you mapped your route out ahead of time, so as to approach known AP's from different angles (120 degress off from previous optimally). The actual angle could be determined from the Lat/Long point, could get even more accuracy.


Please read/re-read post #7.

PostPosted: Thu Nov 24, 2005 7:50 pm
by DreadedOne509
streaker69 wrote:Please read/re-read post #7.


Read, and re-read post #7, and you made some valid points regarding direction and possible obstructions that could reduce the signal strength seen by NS thereby causing an inherent inaccuracy in the result.

However, with some 'knowns' you could reduce the amount of error by triangulating the information that is easily garnered by NS.

Image In this example the NS1 is the first of 3
readings from within NS. NS2, and NS3 are the subsequent readings
with matching suspected AP locations in relation to the unknown actual AP location.
Could even throw out the result from NS1 since it is out of bounds, and split the difference between NS2, and NS3 for even greater accuracy.

Notice that there is an obstruction blocking the NS1 reading making it appear much further away than it actually is, where as NS2, and NS3 have no such obstructions and their suspected location is much closer to the actual location of the AP. Using a triangulation formulae to plot location would be much closer to the truth than if you were just using NS1 information.

Yes, I understand that it would be almost impossible to get 100% accuracy, but with triangulaion you could get a lot more accurate than the current guesses.