Location, Location, Location (Radio)
By roger on Aug 05, 2009
Location, Location, Location (Radio)
This post is a follow-on to my previous post about determining location using the accelerometer. That post proved to be quite popular, and at the time I promised to follow up with a post about finding location via the radio. Well that was some time ago, but finally, here's more about location. This time, as promised, we will talk about how to derive location from a radio. Can you tell where a Sun SPOT device is, using its radio? As with the accelerometer, unfortunately, the news isn't very good. Its quite difficult to get an accurate position from the Sun SPOT radio, but we'll talk through some of the techniques used to figure out where you are in radio space. We'll talk quite a bit about radio propagation. We'll toss in a little math, but nothing too complicated I promise. I hope you enjoy it.
Generally, to find a location using the radio, we want to find our position relative to other devices of known location. There are two basic techniques. Either we need to figure out the distance and bearing to another device of known location (a vector), or we need to find the distance to multiple devices and triangulate to infer a location.
Direction and Distance to a Known Location
In the first technique we need three things to establish the location of the Sun SPOT. We must know the 1) Bearing and 2) Distance to a 3) station of known location. In the diagram above I call the station of known location station, "Home Base." In order to figure out its bearing we need to calculate an angle relative to a known direction. If we had some way to directionally detect radio waves, we could use a magnetometer to get an absolute direction to compare to and then calculate a bearing off of that. Of course, this would mean that we would need to use a directional antenna or other means of determining the direction of the radio signal from the Home Base. Since we don't have a servo controlled, directional antenna on the Sun SPOT, nor a magnetometer, this is very difficult to measure.
Distance to Multiple Known Locations
Since direction is not likely to be an easy thing to calculate, we can take another approach. Perhaps it would be easier to determine our position by simply using distance to multiple known locations. In the image above, if we know that we are 100 meters to Green Base, then we know we are somewhere on 100m diameter sphere (remember radio waves propagate in 3 dimensions, not just a two dimensional circle) with the Green Base as a center. If we also know that we are 80 meters from the red base, then we know that we are somewhere along the intersection of the green sphere and an 80m diameter sphere with the Red Base as a center. The intersection of two spheres is an ellipse, with three spheres you get two points and finally with a known distance from four other devices, you should be able to pinpoint your location. Of course, most methods of measuring distance in the real world are not completely accurate, so more distances makes for more accuracy in your estimation of position.
One common problem with this technique is that it usually takes time to get these distances. To put it another way you cannot get all the distances simultaneously. If you move between measurements it will affect the accuracy of your estimate. The process assumes that you don't move between measurements. So we must either assume that both our device and the devices we are measuring are stopped during the measurement or apply a level of uncertainty relative to the total amount we and the reference locations could move during the measurement.
Time of Flight
Great, now we've reduced the location problem to just being able to measure distance. This should be easier right? A logical way to measure distance would be by calculating "time of flight" of the radio signal. In other words, calculate how long it takes the signal to get from transmitter to receiver. Let's take a look at this. Radio waves propagate at the speed of light or about 299,792,458 m/sec. This means that a radio wave covers one meter in about 0.000000003334 seconds or just over 3.3 nanoseconds. So, it can cover 3 times the radio range of a typical Sun SPOT in a single microsecond. One thing for sure is that we will need very accurate timings if there is any chance of getting reasonable accuracy to our measurements. The current eSPOT has a 180 MHz clock, or just over 5.5 nanaoseconds/clock. This means that every clock cycle corresponds to about 1.7 meters of radio propagation. Furthermore, the IEEE 802.15.4 radio standard that the eSPOT uses can transmit at 250kbits/sec. That means that a single bit has nearly 1200 meters between its start and finish. Or to put it another way, since the Sun SPOT range is roughly 100m, the start of a bit is always received long before the end of a bit is sent. This isn't strictly true because IEEE 802.15.4 radios use a more complex coding scheme than just sending a bit as an on or off (I explain this amore below), but the point still stands. A bit is much too large a resolution within a few meters.
For this method of measuring distance to have any chance of working we must measure the onset of the leading or trailing end of a bit - some sort of an instantaneous synchronization signal. It would be quite difficult to get any accuracy at all if any software were in the loop because timing is so critical. In order for this to be practical, we would need to have the ability to time tag arriving packets in hardware and not wait a potentially variable amount of time for something like an interrupt to get serviced. Additionally, we would probably need something similar on the output so that we could time tag packets as they are actually being sent. Its not good enough to time stamp them as they are put into the queue to be sent, they would need to be stamped as they are sent out.
However, even if you were able to get the exact time that a packet leaves one device and the exact time that it is received by another, there is still the problem of synchronizing clocks. It would appear that we would have to have clocks that are synchronized to the nanosecond. This seems like another very difficult task until you consider the following. Lets assume that at time Sun SPOT device has a clock time of while Sun SPOT has a clock time of . At exactly this moment, sends our synchronization signal over the radio. We would like to know the propagation time . We know that will receive the signal at time where
the problem is we don't know . We don't know the exact reading of another Sun SPOT device's clock at any given time. Either together with the synchronization signal or in a separate message can tell what time it believes the signal was sent (ie ). Since the clocks are not calibrated, this may have little relation to the time on the other Sun SPOT device. Using the information available to it, could calculate a preliminary propagation time () as:
Unless by dumb luck the clocks are synchronized to the nanosecond (not likely), we know that is incorrect. Let's suppose further that the difference between the two clocks is .
We know that the true propagation time, , is different from the calculated one, , by .
We really need to know the difference in the clocks, , before we can calculate the true propagation time, . Suppose that we repeat the experiment going the opposite direction. Then if we assume that the clocks do not drift with respect to each other (a big if at this level) and that the next synchronization signal is sent at and received at then we get:
Now if we make further assumptions that the devices have not moved and that the speed of light has remained basically constant (which for our purposes it is probably reasonable to assume), then we can assume that the propagation time is also incorrect by but in the opposite direction.
Therefore now that we know , we can plug it in to get the true propagation time:
These values can be measures, so new we have the true propagation time, . Now we just divide by the speed of light to get the distance in meters:
This means that in theory, with proper hardware support we should be able to determine the distance to another device by measuring the time of flight of the radio signal. Practically however, even with hardware assistance, its hard to see how we would get more than about ten of meters of accuracy under good conditions, which is one tenth of the range of an eSPOT. Actually measuring with this precision and accuracy proves quite difficult.
However, our problems with this method aren't over yet. To most computer scientists, the idea sending a bit over a radio seems quite natural, but actually radio waves aren't digital. Digital bits are a convenient simplification that we apply to the real analog world. The signal that is sent is not a bit but an analog encoding of a bit. In 2.4 GHz IEEE 802.15.4 radios used by the eSPOT, data is encoded using Offset Quadrature Phase-Shift Keying (OQPSK). This encoding scheme must be decoded by the receiver and turned into bits. As the signal travels in the air and is affected by its surroundings, other signals and general noise, the characteristic of this signal can change. This means that the receiver needs to do some work to interpret the signal it is receiving. It needs to listen to it long enough to interpret what it is hearing. While this happens very quickly, the time required to notice the signal changes could actually vary slightly depending on the shape of the received signal. Even a few nanoseconds of variations will affect the accuracy of our distance estimations.
The current eSPOT hardware does include some ability to time stamp received packets in hardware, but its not clear to me that is has anything like the required accuracy or precision for the task of measuring time of flight.
Distance From Signal Strength
This leaves us looking for other ways of measuring distance using the radio. Perhaps the most promising is the use of Radio Signal Strength (RSS). It seems intuitive that RSS and distance transmitted are related by the inverse square law. In theory as distance goes up, RSS goes down and vice versa. As I've often found in life, the difference between theory and practice in much greater in practice than it is in theory. In the real world we find this is not strictly true.
One of the early programs that we wrote for the Sun SPOTs was a simple Therimin simulation. The Therimin is a unique electronic instrument that lets the user play music by waving their hands near two antennas that protrude from the device. One controls the volume and the other controls the pitch. Our version was inspired by this, but quite a bit simpler. It simply translated RSS values between two Sun SPOT devices into pitch values for a MIDI synthesizer. Unfortunately, we found it very frustrating to play because there was no strict mapping between distance and the notes that were played. We could start with the two Sun SPOT devices far apart and then slowly bring them together. We would expect this to create an increasing musical scale on the MIDI keyboard. While it was true that holding the SPOTs close together would cause a high note to play and holding them far apart would cause a low note to play, the transition from far to near was full of ups and downs. We double checked our code, but everything seemed to be in order. What was going on?
The problem was that radio propagation is fairly complex thing. At the 2.4GHz frequency range that the eSPOT uses for its radio, the signal propagates by line-of-sight. This generally means that if two eSPOTs are within visual range of each other and <~100m from each other, then should be able to communicate. The problem is that many factors can affect this signal propagation. Early on in the life of the Sun SPOT project, many of our demonstrations would be working perfectly until a crowd of people entered the room to see the demo. We experienced our own little version of a Heisenbug (a bug whose behavior changes when you try to observe it). These, "ugly bags of mostly water" (as Enterprise computer once referred to humans) tend to absorb radio signals. Remember that microwave ovens work in a similar frequency range. The eSPOT radios don't put out anywhere near enough energy to cook a hotdog or much or anything, but people and other water based items in the vicinity can absorb signals. Our observers changed the radio characteristics of our demonstration area just enough to upset our demo.
It turns out that line-of-sight propagation is much more than it may seem. A Sun SPOT does not have a highly directional antenna, so it transmits in all directions, not just toward the intended receiver. While some of this signal finds its way directly to the receiver, more of it will wander off in other directions. If one of these wandering signals bounces in such as way that the bounced signal also finds its way to the receiver, it will have taken a slightly longer path to the receiver than the direct signal. Because of this, it will arrive slightly out of phase with the direct signal. When a signal is received along two or more different routes, the condition is called multipath propagation. The receiver receives a mixture of these tow signals. The amount that the multiple paths affect the signal will change depending on the amount of delay and the strength of the signals experiences being mixed, as shown in the figures below:
The receiver will receive a signal that is the direct signal and the reflected signal mixed together. In mathematical terms this means the signals are added. The first graph shows two signals that are received slightly out of phase with each other (the same signal, just delayed slightly) and the red line is the sum of these signals. The RSS is measured as the amplitude (difference between the lowest and highest values) of the signal received. As you can see, the red line has more amplitude, and so a device receiving this signal will register a stronger signal strength than a device just receiving a direct line-of-sight signal. However, the signals don't always mix in a way that has a positive effect on signal strength.
Sometimes the way these signals add has a net negative effect on the signal strength. In the second graph, the two signals in black add to produce a red signal that has lower amplitude (and signal strength) than either signal individually. They are canceling each other out. You can imagine a situation where the reflected signal is delayed by exactly half a wavelength and thus effectively cancels the original signal completely. In addition to the phase shift caused by the delay, there is usually a bit of difference in amplitude between the signals because the direct signal is usually stronger than the reflected signal. This, and the fact that there are usually many reflected signals, will often keep the signal from being completely cancelled out, so in practice signals will vary significantly and in ways that are difficult to predict, but rarely will cancel completely.
There is something called the Fresnel zone (pronounced fray-NELL) that is an ellipsoid area around of the direct line between two communicating devices. The zones help to define the effects of the reflections. You can calculate the size of radius of the Fresnel zone with the following equation:
where is the distance in meters between the devices, is the frequency in GHz, is the Fresnel zone and is the radius in meters. So for example, if two Sun SPOT devices are 100m apart, and they use the built-in 2.4GHz radios, we get a value for of 1.77m for zone 1. This is the radius of the zone at its widest point (in the middle). Reflections in Fresnel zone 1 tend to cancel the original signal. Along an ellipsoid shape that is zone 2 (2.5m in our case) the signals will tend to add. Fresnel zone 3 would produce an value of 3.06m, and so on. In general, reflections in odd numbered zones tend to cancel the direct signal while signals in the even number zones tend to add to the signal strength. It is good to keep at least Fresnel zone 1 clear if possible.
Of course, if the two devices are closer together, then is smaller. So, for example, if the two devices are only 1 meter apart, then zone 1 would be a mere 17cm. Zone 2 would be 25cm. So moving something reflective to radio waves that is half way between the two devices only 8cm can make the difference between a very strong signal and a very weak signal. Of course, something closer to either device (the end of the ellipsoid) would have to move even less to have a similar effect. Near either of the devices, something moving only a few centimeters could completely change the signal characteristics. Similarly, moving a Sun SPOT device only a few centimeters could completely change the characteristics of the multi-path signal that is reaching it.
We can construct a hypothetical extreme case. The wavelength of the radio signals sent by the eSPOT is about 12.5 cm. This means that in the extreme case of a direct signal and a reflected signal of equal amplitude at right angles to each other, you can go from double signal strength to no signal at all in half a wavelength which is just over 6 cm. Note that this will be true regardless of how far away the two devices are from each other. This makes it very difficult to find a correlation between distance and Radio Signal Strength.
This brings up another question about these radio waves. What types of materials will affect the propagation of a radio signal? We know that they travel optimally through open air (or a vacuum). We know that, at this high frequency, many things tend to affect the signal. In general, metal will reflect signals and water will absorb it, but most things will do some amount of each. Plastic, paper and drywall tend to have little effect on the signal since they aren't metallic and have little water in them. A metal white board in a room can have a large effect on radio propagation. One of the most important materials is the ground. It can both absorb and reflect. Reflections from the ground are a common cause of interference. If we want to keep Fresnel zone 1 clear and get 100m of transmission, then we know from the calculation above that we need to keep them at least 1.7m off the ground and would prefer to be closer to 2.5m.
The story gets even more complicated when we look more closely at the what is going on. There are three phenomena at work when the radio waves encounter a an obstacle: reflection, diffraction and refraction. We discussed reflection earlier. Diffraction occurs when a wave passes by an obstacle or through a small opening and appears to bend. Refraction is the change in direction as a result of a change in speed of a wave as it travels through different media. Refraction is the least common since the speed of light is fairly constant within the realm where we working. However, the diffraction has a real effect. In particular, there is a phenomenon called Edge Diffraction that applies to radio propagation in these frequencies.
Imagine a Sun SPOT device transmitting a signal over a an open area with a single obstruction in it that can block the radio waves. One would expect that the obstruction would create a a radio "shadow" where no signal can reach. Instead, the signal at this point creates a new wavefront at the edge of the obstruction that propagates into the shadow area providing a weak, but sometimes usable diffracted signal. The area of direct propagation just beyond the top of the obstruction now exhibits an interference pattern with the refracted signal causing sporadic losses in the area labeled diffraction loss. Also, some of the signal will be reflected and this will create an interference pattern with the direct propagation wave in the area in front of the obstacle. All these affect signal strength. A similar condition occurs with a radio signal goes through a small opening. Diffraction occurs at the edges and interference patterns result that cause difficult to predict changes in signal strength.
If we want to get really esoteric, there are atmospheric conditions that can affect signal propagation. For instance humidity in the air can affect signal strength. Remember, water tends to absorb radio signals. This means that in addition to objects in the vicinity of the propagation path, even changes in the weather can affect signal strength. This effect is usually not as strong as some of the others mentioned above, but is can be noticeable. In some cases it can cause an effect known as Tropospheric Ducting where signals find paths through "pipes in the sky" created by certain atmospheric conditions that can go on for thousands of miles. This can cause otherwise line of sight signals to travel great distances around the earth. I've never heard of anything like this happening with a radio signal from an eSPOT, but it does show the counter intuitive nature of radio propagation. Besides, "Tropospheric Ducting" is just a cool term to be able to throw out in conversation, so I thought I'd tell you a little about it.
Radio Space Shape
As if all this weren't enough, most of these schemes assume a uniform signal radiating in all directions from the Sun SPOT device. This is simply not true in practice. The diagram at left shows the actual measured propagation pattern of the eSPOT antenna. If it were very uniform, we would see a spherical shape. Instead we see an indescribable shape with all sorts of different lobes and divots. You can see a > 10dB difference between the strongest and weakest edges of the signal. This means that you can change the signal strength can easily more than double just by changing the rotation of the Sun SPOT device. So the orientation of an eSPOT is very important in controlling for signal strength.
Of course, given what we've learned about diffraction and reflection of radio signals, you can see that this also means that in some cases a stronger signal may be aimed as a reflection rather than a direct route which will cause all sorts of confusion when it comes to signal interference and cancellation.
So where does this leave us? Just like with the accelerometer, finding the location of a Sun SPOT using the radio does not look very promising. In theory, we might be able to determine location if the following conditions were met:
1) There are no obstacles anywhere near the Sun SPOT devices or the area between them (for many Fresnel zones) that could reflect, refract, diffract or absorb the signal.
2) The Sun SPOT devices are many meters off the ground
3) The Sun SPOT devices do not change orientation with respect to each other.
4) The Sun SPOT devices don't move between measurements
If ANY of these rules is broken the result is a radio space that is for all practical purposes nearly impossible to predict. On a large scale, the closer devices are the greater their signal strength, but locally this will not hold true.
I'd be happy to be proven wrong. As always, all my gloom and doom may inspire someone to figure out a good way around these limitations and prove that you can measure location with radio and/or acceleration. Sometimes there is no greater motivation than saying it can't be done. Have fun. In the mean time, if you get unexpected readings of radio signal strength, now you may at least have an idea why it is happening.
I stand by now for your questions and comments.