My origninal thoughts about locating cattle, etc. were to use the method we use for locating underwater devices: triangulation of three angles derived from the phase relationships of signals sent from the tracked object to three (or more) base stations. This method is in contrast to JBD's method of calculating position by the tracked object of time differences of signals sent from the base stations. The time difference (again using phase relationships) give distances. Three distances (like three angles) from base stations with known positions will give a location. The resulting location is sent along with data and identification back to the base network.
The problems we have seen with both of these, distance or angle, methods is in the size, power, and cost of the "tags."
What I currently think might be a better technology to study is the use of Passive RFID (Radio Frequency ID) technology, the method used by the EZ-Pass Highway toll collection, and numerous biology data collection projects (see http://www.fs.fed.us/eng/pubs/html/98241201/98241201.htm and http://en.wikipedia.org/wiki/Transponder_timing). The greatest benefit is the size, power, and cost of the tags is reduced to such an extent that it becomes feasible to scale the number of track objects up to the thousands. The down side is that the distance from scanner to tag is quite small and therefore there need to be more, but it is not unreasonable (see http://www.retailtechnologyreview.com/absolutenm/templates/retail_rfid.aspx?articleid=642&zoneid=2 and http://members.surfbest.net/eaglesnest/rfidspct.htm). If, instead of using UHF, using VHF frequencies, the range can be as much as 100 meters.
It is conceivable, though I haven't researched this, that by using the mesh network of base stations with known locations and the relative transponder signal strength and/or two-way transponder response time, along with a bunch of statistics, that fairly precise location can be determined. Isn't this how our cell phones can give location without using GPS?
RFID requires close proximity to read the tags (the military has a system that can read tags up to 300' away - but it requires a comparatively large tag and a high powered reader - neither of which are suitable for our application.) EZ-Pass uses a high powered reader, but even its range is about 30'. Most marathon RFID systems need a proximity of 7' or less.
Our application needs a "proximity" that's a MINIMUM of 300' (outdoor; line-of-site), which our prototype XBee's meet - and are a lot cheaper than RFID tags with equivalent range; better proximity (for farms) would be in terms of thousands of feet or miles, which the XBee Pros give - but they consume more power. Rangeland would require ranges in miles to tens of miles. But simply adding anchor points may accomplish the same purpose.
Unfortunately, cell phones don't provide sub-meter accuracy. There are several systems in use by the cell manufacturers, Wikipedia has a good description of the various techniques. Of course, most farms are located in rural areas - notorious for lack of cell towers.
I originally wanted to have "inch" accuracy, but I'm willing to be a little sloppy on that. I do need identification of the tag, and get as close as possible; which is why I wanted a very high resolution clock on the radios. With synchronized high resolution clocks on both sides of the signal, we can calculate a rather precise distance between the endpoints, and not have to worry about software/interfacing latencies. (Although I believe the XBee's mesh networking may complicate or render that approach impossible. Without further testing, we can't be sure.)
I should point out that the XBee's provide a received signal strength metric, but its only accurate to 2 decimal places (-40db to current gain setting). But I don't believe this will provide sufficient accuracy in determining distance.
Okay. RFID is out for this project. How about an active transponder, maybe done with the Xbee? With this the positioning is done by the base stations. All that would be necessary on the tags would be to transmit replies to a queries from the base stations. I assume (big word here) that the turn-around time from request received to reply transmitted could be held constant. From my sketchy reading and conversations with cohorts here at CCOM (Center for Coastal and Ocean Mapping), the clock error problem is eliminated in this way. The positioning is determined by the sum of the two way transmission and the turn around time.
I like the two way transmission idea. The anchor point doesn't have to be quite as fast - but still needs to be able to sense the departure and return times within 300 microseconds. And we can "fake" a signal by wiring the TX to the RX on the ear tag.
I too am making the assumption that turn-around time is constant - at least between the XBees. We'll need to empirically test how much latency the mesh network adds too.
I'll start looking at a device driver to do this (because it needs to be done at interrupt level to keep the OS from introducing latency). Once I get the driver done and tested, we'll need more beaglebones and XBees to test/write the trilateralization logic.
Oh, I guess we'll be needing the GPS interface logic written too. That is critical for translating the "local" positioning info into global positions.
So, I guess the real next step is software architecture planning.
Some testing here indicates that two-way time-of-flight measurement won't work with XBees. I suspect it has a lot to do with:
Hey guys,
Sorry I'm probably late to the game but I have been tied up moving into a new apartment and office last week. This discussion has made great reading material though!
Just to make sure I've understood, it's settled that a good clock is only needed on the anchor station? Seems like this turn-around technique is a nice solution and will yield an absolute answer for each individual anchor (ie: it will tell you node 32 is 50m away).
I just wanted to offer another idea which I thought came up in one of the discussion threads but I can't seem to find and that's to use ratios:
If you have 3 anchors and they all receive the SAME signal from a node, they will have three different times when they clocked in the message (let's say, 00:01, 00:02, 00:03). The differential in time received will help determine the relative difference of the node (that is, if the node is distance X away from node 3, then it is 2x/3 from node 2, and x/3 from node 1 - a unique point satisfies that relation). I like the turn-around method better since it immediately yields absolute distance and doesn't require synchronization but if that becomes a problem for technical reasons, this could be another approach.
The differential times are all that's needed from the anchor points to calculate the distances, so it would make the logic/coding a lot easier.
But turn-around does eliminate the need for synchronization at least...
Synchronization won't be too bad since distance will be easier to calculate (even without GPS) since both sides have good & identical clocks. Actually, it would be neat to do this without GPS which makes this system entirely relative until you take some global references from GPS!
The problem of synchronization without GPS is a difficult one. Each CPU clock will drift at a different rate which may be temperature dependent. While it is possible to build a mesh protocol to find a common time, it will require both transceiver and CPU resources which might need to be used for other things at the time. The GPS with PPS is ultra accurate PPS signals have an accuracy ranging from a 12 picoseconds to a few microseconds per second, or 2.0 nanoseconds to a few milliseconds per day and sets a common standard time for anything that uses it. There may still be problems finding deterministic latencies in the radio and CPU.
I believe Louis was indicating that we could do positioning without GPS; which is technically correct but not necessarily desirable, and assumes we know exactly where the anchor points (aka base stations) are located.
Synchronization of the end points (ear tags) with the anchor point is no longer required since the anchor point will be sending the signal to the end points (ear tags), which will just echo it back; and all timing (with a 700 MHz clock) occurs on the anchor point. However, synchronization of the anchor points will be required for the reasons you pointed out. Since all the anchor points will have GPS's on them, this can be done with reasonable accuracy, and be checked/re-done frequently.
Latency in the radio, GPS, and CPU (deterministic and non-deterministic) will have to be empirically determined. And we'll have to re-run the tests with every new batch of processors, CPUs, GPSs and XBees. Sigh.
But, not in the first version!
The majority of the GPS errors in location of the Base Stations for the Farm Item Locator will be exactly the same for each base station. Some of the errors are accounted for by differential GPS and WAAS GPS correctors, but this just gets you down to the meter to three meter accuracy. In surveying, the errors and corrections are computed locally at a base station to the survey and then applied, either immediately (RTK) or in post processing (PPK). A professional grade base station costs upward from $50k. Not in the budget for this project.
I wonder if we can't cobble together a low end version of the same concept? We might have to actually survey in the location of one station, the base-base station, and the others could figure out where they are. A good RTK/PPK positon (used on objects that move, like cows and tractors) would have accuracy of a few inches.