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.

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.