PDA

View Full Version : [Discussion] Location Tracking Using 802.11 Wireless Access Points



Asimovian
08-04-2011, 10:34 PM
Hello everyone,

This post may or may not be of use or interest to members here but I think it’s a bit of interesting information and could possibly be used in some applications.

I'm far from an expert in any of this field so I welcome any contributions, corrections, additions, or comments. Please be nice :) as I’ve only collected this information out of interest so I’m probably missing a lot.

I'll try to keep this as a general outline of the methodology and technology. I've gathered this information from a lot of different sources (referenced below) so please refer to them if you’d like more in-depth explanations.

Also apologies for the images, photobucket does some weird things sometimes.

1. Intro
Wireless routers, access points and other RF devices are now a very common and often overlooked piece of hardware. Using the Received Signal Strength Indicator from one or multiple devices and basic math knowledge we can find the distance from these devices and calculate a location. The main reason why this has not become commonplace, and anyone who has experimented with this will know, is that location tracking using these signals is not very accurate. Robotics in general requires a high level of precision often within fractions of a millimetre. Having a vague location within a few feet just isn’t good enough.

However, there are situations where this may be acceptable and there are a few steps that can be taken to increase the accuracy of the reading.

2. Theory
2.1 Triangulation and trilateration

The most suited (and easiest) method for calculating the location of a device with this setup is triangulation. A simplified version of this method was first described in patent #7,283,127, issued October 16, 2007, which claims the methods for triangulation of static magnetic fields. In this method you find the RSSI from a transmitter, move to another location and find the RSSI value again from the same transmitter, then use simple trigonometry to calculate the position of the device. In real life this is much more complicated and variables such as terrain, obstructions, heat and atmospheric effects, reflections, refraction, and antenna design need to be taken into consideration.

In theory if we have the output power of the transmitter, the gain of the receiving and transmitting antennas, power drop-off, and the received signal strength, it should be possible to calculate a location with just two samples. At point A in the figure below, with the signal strength and power drop-off you should be able to determine the distance from the transmitter. Perform the same at point B and the possible locations of the transmitter are where dA and dB meet. If the strength of the transmitter is unknown it is now a simultaneous equation with three unknowns therefore three data points are required. If well placed there should only be one or two possible locations.

http://i4.photobucket.com/albums/y120/KAJ85/TrackingbySignalStrength.png
The equation that this theory works off is the general inverse-square law for propagation of electromagnetic energy in a spherical shell from a point source.


RSSI = kI / r2
Where:
RSSI is the RSSI field strength measured from each antenna
I is the intensity of the transmitting source
r is the distance from the source to the antenna
k is a constant of proportionality that is assumed to be known or the same for each antenna.

Michael Harney goes into a lot more detail of this equation in his article, Wireless Triangulation Using RSSI Signals. See link at the bottom for more info.

Expanding on the above equation, as the RF energy is generally emitted in a spherical shell, we can then use trilateration to find the location of a transmitter in a three dimensional space.

2.2 RSSI (dBm vs mW)

Accuracy and precision. As I’ve already mentioned above these are key factors in location tracking and especially in robotics. The IEEE 802.11 standard defines a mechanism by which RF energy is to be measured by the circuitry on a wireless NIC. This numeric value is an integer with an allowable range of 0-255 (a 1-byte value) called the Received Signal Strength Indicator. No vendors have chosen to actually measure 256 different signal levels so the brand of hardware used will impact on the accuracy of the reading. For example Cisco uses 101 separate values for RF energy whereas Symbol only uses 31.

Most users view RSSI everyday usually in the form of a small icon that shows a number of bars to indicate how strong the signal is in their current location. This is most commonly viewed on laptops and mobile phones. The problem is this measurement is extremely vague, four bars could represent anywhere between 5 metres to 50 metres away. As the number of ‘bars’ is not a measurement worth taking we can either use dBm or mW which are both common ways of measuring the RSSI. The type of measurement we take as the RSSI will have a large effect on the accuracy of the location calculated.

The concept of granularity needs to be taken into consideration when taking RSSI measurements using dBm or mW. Since the RSSI value is an integer it must increase or decrease in integer steps. Using the example given above for Cisco, which uses 101 different ‘steps’, the range of actual energy being measured must be divided into the number of steps supported by the manufacturer. Therefore, if the RSSI changes by 1, it means that the power level changed by some proportion in the measured power range. What this means is that all possible energy levels whether dBm or mW, are not able to be represented by the integer set of RSSI values.

http://i4.photobucket.com/albums/y120/KAJ85/RFgraph.png
Using the above graph we can see that there is not much change in dBm values above roughly 5 mW. The graph also shows that the slope of change for dBm below 5mW is roughly linear. Due to the logarithmic nature of the curve, many vendors make a mapping table of RSSI to dBm, which allow for adjustments to be made to fit the curve. This also seems to be the best method for relating distance to RSSI which is what I have tested in the section below.

2.3 Propagation Issues

This is another area that is huge so I’ll only briefly discuss it. There is an article titled “An Introduction to Indoor Radio Propagation”, available at http://www.sss-mag.com/indoor.html that comes up with an approximation for losses at 2.4GHz inside buildings.

The three basic mechanisms of radio propagation are attributed to reflection, diffraction and scattering. All three of these phenomenon cause radio signal distortions and give rise to signal fades, as well as additional signal propagation losses. Even outdoors in perfect conditions it is hard to get an accurate reading as multipath signals (reflections) and scattered or diffracted signal can cause variations as much as 30 to 40 dBm. When shifting indoors this turns to a near impossible task as you now have walls and ceilings made of different materials and many other objects and structures that will affect the signal differently.

Radio propagation phenomenon can be handled by a practical system at distances out to perhaps 100 metres using the following relationship (at 2.4GHz):


Path Loss (in dB) = 40 + 35 * [LOG (D in metres)]

Thus a 10 metre path will give a loss of about 75dB and a 100 metre path gives a path loss of about 110dB. Again this is theory that is explained further in the referenced article “An Introduction to Indoor Radio Propagation” and extensive site testing would need to be carried out to evaluate suitability.

3. Practical

I have barely scratched the surface testing some of the theories above but I’d like to share my progress so far and will update as I learn more. Any suggestions would be welcome.

For initial testing I’ve been using the following simple tools:

Microsoft Excel 2007 – To record RSSI at set distances from the transmitter. This was then used to create a polynomial best fit line to find the quadratic equation for the line, which can then be rearranged to find the distance when given the RSSI.

WirelessNetView – Free program available from http://www.nirsoft.net that allows RSSI reads of all detected transmitters to be exported to xml, txt, tab, csv, html files.

Step 1 An access point (HP Procurve 420 in this case) was set up in the centre of a large empty room with no obstructions.

Step 2 Concentric circles were marked every 1 metre away from the transmitter from 1 to 10 metres.

Step 3 Ten RSSI readings were taken at different locations around the transmitter at each marked distance. I couldn’t find how many ‘steps’ HP uses to measure RF strength but -45dBm seemed to be max signal strength and this increased up to -75dBm 10 metres away. Obviously more readings will increase the accuracy of the final location.

Step 4 All data recorded in Excel then graphed. Polynomial best fit line shows an equation of y = -0.1214x2 – 2.3614x – 44.74 where y is the RSSI value.

http://i4.photobucket.com/albums/y120/KAJ85/BestFit.png
Step 5 Rearrange the equation to find distance when given RSSI. The general form of a quadratic equation is ax2 + bx + c = 0 and there will be two possible answers. We can rearrange this as follows (forgive the formatting, I’ve copied out of excel):

Distance from transmitter = (-b + SQRT (b2 – 4 * a (c – y))) / (2 * a)

And

Distance from transmitter = (-b - SQRT (b2 – 4 * a (c – y))) / (2 * a)

Step 6 To test I stood 5 metres away from the transmitter and captured an RSSI reading of -68dBm. After putting this into the above equations you receive the values -26.6428 and 7.19137. The obviously incorrect result from the first root can be discarded.

4. Conclusion

The end result indicates I am 7 metres away from the transmitter when taking a reading at the 5 metre mark. As we can see from this initial result there is already a large variance of 2 metres so it is not really suitable for tracking an object accurately within a room but for finding the general location of an object in a large area it may be acceptable.

What’s Next:

- Gather a lot more RSSI vs distance data to improve the accuracy of the best fit line which should increase the accuracy of the distance provided by the above equation. Also take readings from distances up to 50 metres away.
- Start looking at propagation of RF signals through different materials and room sizes
- Data gathering with Cisco hardware to see if this improves accuracy
- Make a grid with transmitters at set locations identified by their MAC, then overlay a map on the grid and track a mobile device travelling through the grid. (This is the end goal)

I’ll post updates as I learn something new but as I mentioned before this is only out of interest and not even a hobby so it may be a while before I post anything new. Feel free to offer comments or suggestions on what I could do to improve accuracy or the project in general. I hope this has offered some readers a bit of interesting information.

5. References and Further Reading

Bahl, P & Padmanabhan VN, RADAR: An In-Building RF-based User Location and Tracking System, http://research.microsoft.com/en-us/um/people/padmanab/papers/infocom2000.pdf

Harney, M, Wireless Triangulation Using RSSI Signals, http://www.eetimes.com/design/microwave-rf-design/4019032/Wireless-triangulation-using-RSSI-signals

Interlink Networks, A Practical Approach to Identifying and Tracking Unauthorized 802.11 Cards and Access Points, 2002

SpreadSpectrumScene, An Introduction to Indoor Radio Propagation, http://sss-mag.com/prop.html

WildPackets, Converting Signal Strength Percentage to dBm Values, http://www.wildpackets.com/elements/whitepapers/Converting_Signal_Strength.pdf, 2002.

sasith90
02-09-2012, 06:04 AM
This information is realy valuable for me, I'm really interested on this,

parallax
02-09-2012, 12:13 PM
Very nice preliminary work! I have only had time to briefly read through your post, but my initial thoughts are that there are two key points to take into consideration here. I apologize in advance if you have already covered them...

Interference: It appears that your calculations are based upon the ideal mathematical model (i.e. no signal loss and/or outside influences) with the exceptions of diffusion, etc. . Many RF signals are influenced by other environmental factors. For instance: 2.4GHz signals are severely hampered by the presence of water. Humid days will see a noticeable change in signal strength, and the presence of something like a tree (a great repository for water) in between you and the access point will also hamper the signal. I know that your initial tests were situated in an area with no obstructions, but for practical use, both of these things will have to be considered.

Out of curiosity, where are you (or did you) go to school? This is written like a pilot study or a technical paper...

I look forward to reading your further findings!

Asimovian
02-10-2012, 12:47 AM
I thought this post may have snuck past unnoticed by many as I posted over 6 months ago.

parralax, I did very briefly cover signal propagation loss caused by reflection, diffraction, and scattering but this is a huge area to cover and I'm not even vaguely ready to try and understand some of the principles this is concerned with yet. I'm just focusing on finding distance vs signal strength properties when conditions are perfect (or as perfect as I can make them) and slowly add on the more complex issues.


parralax said: Out of curiosity, where are you (or did you) go to school? This is written like a pilot study or a technical paper...
I've actually got a business degree :D I'm just able to take information from a lot of different sources and collate it into a semi-understandable piece of text. Thanks for the kind comment though. I do regret not studying mechatronics or something similar, if there's one thing I could change in my past it would be that.

Unfortunately I haven't had a chance to perform any further testing since my post above but have started studying my Cisco CCNA and CCNP Wireless certifications which will hopefully give me further insight into the signal propagation issues and give me a chance to test the accuracy of Cisco hardware.

I'm looking at changing employers in the near future so I may have some spare time to get back to this in the next couple of months. If I do find something interesting you guys will be the first to know.

sasith90
02-11-2012, 07:34 PM
OK
I'm a Undergraduate Student, I'm going to implement this technology as a part of my Final project, So all of your posts about this technology wil give me a very good help for my future studies,

And if anyone know more about this technology please reply to this tread or send me a mail to this address

[email protected]

Thank You
Sasith Fernando

Jethro
02-17-2012, 08:15 AM
This is fantastic - you have performed some great research! Here is a simple program I wrote that allows you to find the location of the transmitter based on this algorithm - http://signaldisplay.com/triangulation.exe (it is command line for now - a GUI version will come a little later). Try keeping the source in the same plane as the recievers (no variation in z-axis) and see how accurate it is, then adjust the height above the plane and see how accurate the z-coordinate is separate from the x-y coordinates. Great work!

sasith90
03-09-2012, 12:41 AM
Hi ,
I think this article is written in Client view, that means how to find the Location of the Wireless Client by the Client , isn't it ? Client knows the receiving dB value of the signal strength from all APs (Access Points), then Client can find it's location by doing some calculations according to it's statistics.

But my problem is to to find the Location of the Client by the Wireless AP (Transmitter), How can we use this Technology to find this ?

Thank You

Jethro
03-10-2012, 08:55 AM
It is written from "client view" - the client finds its location and then transmits it back to the AP, if the AP needs to know it. Otherwise the AP needs three other access points and triangulates to the client. Here is an android app that uses this method to triangulate:

https://play.google.com/store/apps/details?id=com.thatsbydesign.wrl&feature=search_result#?t=W251bGwsMSwyLDEsImNvbS50a GF0c2J5ZGVzaWduLndybCJd

Asimovian
03-11-2012, 03:04 AM
It is possible doing it from an access point. I'll make a more detailed post tomorrow with a few screenshots when I'm back at work.

You would still need a central location to collect RSSI readings from multiple access points and then perform estimated location calculations. Using the above method on the client means I can collect all data and perform calculations at a single point. If I was rolling this out to multiple clients I would create a service that sent back all RSSI data from detected access points when queried.

The problem with the above is that you need to control the clients and have admin level access to them. What happens if you are trying to detect the location of an intruder on your network where you have limited or no access to their computer? This is where you would use the access points perspective.

sasith90
03-12-2012, 12:15 AM
It is written from "client view" - the client finds its location and then transmits it back to the AP, if the AP needs to know it. Otherwise the AP needs three other access points and triangulates to the client. Here is an android app that uses this method to triangulate:

https://play.google.com/store/apps/details?id=com.thatsbydesign.wrl&feature=search_result#?t=W251bGwsMSwyLDEsImNvbS50a GF0c2J5ZGVzaWduLndybCJd

Yes I'm agree with you,
but I think AP also can gather information from all the clients so, It can do calculations to find the location of Clients

sasith90
03-12-2012, 12:18 AM
It is possible doing it from an access point. I'll make a more detailed post tomorrow with a few screenshots when I'm back at work.

You would still need a central location to collect RSSI readings from multiple access points and then perform estimated location calculations. Using the above method on the client means I can collect all data and perform calculations at a single point. If I was rolling this out to multiple clients I would create a service that sent back all RSSI data from detected access points when queried.

The problem with the above is that you need to control the clients and have admin level access to them. What happens if you are trying to detect the location of an intruder on your network where you have limited or no access to their computer? This is where you would use the access points perspective.

Yes, I can understand,
I appreciate your respond for knowledge sharing, this is very important to my project.
I'm planning to test this in real environment, Do you have any experience with implementing this ?


Thank You
Sasith Fernando

sasith90
03-25-2012, 10:57 PM
This is fantastic - you have performed some great research! Here is a simple program I wrote that allows you to find the location of the transmitter based on this algorithm - http://signaldisplay.com/triangulation.exe (it is command line for now - a GUI version will come a little later). Try keeping the source in the same plane as the recievers (no variation in z-axis) and see how accurate it is, then adjust the height above the plane and see how accurate the z-coordinate is separate from the x-y coordinates. Great work!

Hi

Can you please give you cording of this program that will be a great help for me,

please send it to my email

[email protected]


Thank You
Sasith Fernando