Article 26788 of sci.geo.satellite-nav: Path: matra.meer.net!news.spies.com!news.sgi.com!csulb.edu!gatech!news.sprintlink.net!news-peer.sprintlink.net!newsfeed.internetmci.com!csn!nntp-xfer-1.csn.net!news-2.csn.net!lwjames From: lwjames@csn.net (Dr. Lawrence W. James) Newsgroups: sci.geo.satellite-nav Subject: GPS in the Forest Date: Tue, 15 Oct 1996 08:13:24 -0600 Organization: James Associates Lines: 175 Message-ID: NNTP-Posting-Host: 204.131.233.22 Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit X-Newsreader: Yet Another NewsWatcher 2.3.1 As one reads through the postings in this news group about using a GPS receiver in the forest, there are seemingly two major groups of posters: those who report acceptable results, and those who report consistent failure. Some of those reporting failure theorize that a fully parallel receiver might have resulted in success, but there are few if any side by side comparisons with enough data to eliminate the statistical noise inherent in GPS receiver performance measurement. A closer examination shows that most of those reporting acceptable results leave their GPS receivers on all the time as they enter and travel through the forest (perhaps with a remote antenna on the top of their backpack or their hat), whereas those who report failure generally try to turn on their GPS receiver at a spot in the forest to get a fix. Let us examine why. I know that modern GPS receivers use a Kalman filter to optimize noise reduction, but I am going to assume here that the Kalman filter is absent because it makes the explanation easier to understand. The Kalman filter does the same thing, only better with velocities and accelerations and Doppler shifts included. In our simplified GPS receiver tracking only 4 satellites, there are 8 variables. There is the time delay (or pseudo-range) for each of the 4 satellite signals to reach the receiver. There is the actual correct time. There is the latitude, longitude, and altitude of the receiver position. Under normal conditions, the time delay of the 4 satellite signals are treated as the measured knowns, and the actual time and position coordinates are treated as unknowns. We have 4 equations in 4 unknowns, and the unknowns are calculated from the knowns. What happens if we are walking through the forest and a tree blocks one of the signals from the satellites? All of a sudden we have 3 knowns and 5 unknowns (the time delay from the blocked satellite signal is now unknown). What we can do is to assume that the altitude stays the same as it was at the last reading before we lost the signal. We now have 4 knowns ( 3 time delays and the altitude) and 4 unknowns (the actual time, the latitude, the longitude, and the time delay to the satellite with the lost signal). After rearranging the equations, we can again solve for the 4 unknowns. Note that we not only get a lat-long position and the actual time, we also get the time delay to the 4th satellite, so the receiver knows exactly where (in the time domain) to look for it to pick it up again as soon as we move enough that the signal is no longer blocked. This assumption of a constant altitude is extremely good for a short time period, and gets worse as the time that the satellite is blocked lengthens. Still, on foot, it is good enough for several seconds to perhaps a minute or so if one is climbing, or much longer on a flat stretch. What happens if two of the satellite signals are blocked? Even assuming a constant altitude, we have 3 knowns and 5 unknowns. One of the unknowns is time. If we want our position to within 50 meters, we need the actual time to within about .17 microseconds (from the speed of radio waves in air). No handheld unit can have a clock accurate to 170 nanoseconds! Or can it? Just before the signal was lost the actual time was known. The GPS receiver can also know from the calculated times it has been receiving: the time difference between its internal clock and the actual time, the drift rate of its internal clock relative to the true time, and (with a built in temperature sensor like the Garmins have), the temperature dependence of that drift rate. Hence, for some period of time from the loss of the second satellite signal, we can know the actual time from the internal receiver clock. As the satellite signal stays blocked, the error will increase only by the tiny difference between the actual drift rate and the calculated drift rate at the operating temperature. Hence the corrected internal clock time is valid to within the required 170 nanoseconds for some period of time, at least many seconds. So now we rearrange the equations again, and using 2 satellite time delays, the altitude and the time as the 4 knowns, we solve for the latitude, longitude and the other two satellite time delays so we know how to reaquire them quickly. What happens when three of the satellite signals are blocked? We have to make another assumption. The most reasonable one to make is that the speed of the receiver over the ground (not necessarily the direction) remains constant. Using this assumption linking the changes in latitude and longitude to the time, the time from the internal clock, and the fixed altitude, we can solve for the latitude and longitude and the expected time delays of the three missing satellite signals using only the measured time delay of the one remaining signal. What happens when all of the satellite signals are blocked? We make one more assumption. Not only do we assume a constant speed, we assume a constant direction. Essentially we are extrapolating our current position from our previous position and our vector velocity with no signals from the satellites. With this extrapolation, the receiver still knows how to reaquire the satellites quickly when one or more signals break through the trees. Obviously the more assumptions we make and the longer we have to use the assumptions in place of real signals, the more the error in our position will grow. Still, in walking through a real forest, signals are blocked by trees intermittently on a time scale that makes this approach very reasonable. A smart receiver will indicate that it no longer knows where it is, not when a short temporary dropout occurs, but when the assumption(s) have been used so long that their continued validity is questionable. What advantage does a multi-channel parallel receiver have in this process over a sequential multiplexing receiver? None, except that, with optimum use of the multiple channels, reaquistion of a reappearing signal when one or more of the assumptions is violated to some extent during the signal blockage would be faster by the ratio of the number of channels. We are talking about a difference between perhaps a second or two, and a quarter or a half of a second in practical situations. In summary, our GPS receiver which is left on while moving through the forest is quite capable of knowing where it is and where (in the time domain) to find the satellite signals even when one or more or even all of them are repeatedly blocked for short periods of time. In addition, our receiver which is left on has in its memory the ephemeris data of all of the satellites which are above the horizon, so it can use a satellite signal in the position solution the instant it locks onto it. Now, let us look at the receiver which is carried into the forest and turned on at some point. What assumptions can it make? It assumes that it is near where it was when it was last turned off. That may be miles to hundreds of miles away, and hundreds to thousands of feet in altitude difference. It knows the time to within seconds to perhaps a minute or two, nowhere near the 100 nanosecond time scale. It has the satellite almanac data, but is missing at least the ephemeris data for the satellites which have come over the horizon since it was turned off, if not all of the ephemeris data. Hence it has to search for a satellite signal in two "dimensions", the alignment of the spread-spectrum code in time and the Doppler shift, and then download the ephemeris data from the satellite once it finds it. A slight temporary signal dropout (say the wind is blowing the trees around) could cause it to loose a bit or two, requiring the data signal to "go around" once again to get the necessary data. The receiver will normally start the search with the satellite which is closest to straight overhead since it has the smallest possible range of Doppler shift values. However, in a forest, the signal from that satellite may be blocked. This is where a many-channel receiver can have a significant advantage over a sequencing receiver, as it can search for several satellites at once and find the ones which are not blocked without taking too much time. A sequential receiver could take a longer time (as in minutes) to do a through search for a couple of blocked satellites before it moves on to look for others. In the meantime, the earth's rotation, the satellite movement, and/or the movement of the receiver could block new signals and unblock the ones already searched for. No position can be indicated until the receiver has locked onto and downloaded error-free data from at least 3 satellites (altitude already known) and preferably from 4 satellites. Let us assume a thick forest where 35% of the time while walking through the forest 4 satellite signals are available, 30% of the time 3 signals are available, 20% of the time 2 signals are available, 10% of the time 1 signal is available, and 5% of the time no signals are available. There may be more than 4 satellites in the sky, but the ones nearest the horizon are assumed always blocked by the trees. A well-designed receiver which was turned on before entering the forest and allowed to collect ephemeris data for all of the visible satellites, and then was left on as one walked into and through the forest at a reasonably steady speed and direction could maintain an accurate position using the approach outlined here. (A related approach is actually used in the best GPS receivers, but by no means in all). In comparison, those who leave their GPS receiver off most of the time, stop moving, pull it out, and turn it on, have a 35% chance of never getting a position reading no matter how long they wait, parallel receiver or not. They have a 30 % chance of getting only a 2D reading, and a 35% chance of getting a full 3D position reading. Moving could help, but most people who use this approach stop to take a reading. Moving could also, in the worst case, bring satellites in and out of being blocked opposite to the search sequence, and interrupt ephemeris downloads, greatly lengthening the time to a reading. If you have a receiver which has been on as you are walking and it currently has signals from only 1 or 2 satellites, you can move around while looking at the satellite page and find a better location. The re-acquire time is compatible with the time scale on which you are moving around. If your receiver has been off, it is quite difficult to move around to find a good spot because the search time for the initial acquisition is long compared with the time scale in which you comfortably move around. A parallel receiver helps, but doesn't completely eliminate this problem. The moral of the story is: Hey, if you read this far, you know what the moral of this story is! Larry James James Associates -- your favorite Garmin dealer http://www.csn.net/~lwjames Article 26825 of sci.geo.satellite-nav: Path: matra.meer.net!news.spies.com!news.sgi.com!news.mathworks.com!news-peer.gsl.net!news.gsl.net!portc01.blue.aol.com!newsstand.cit.cornell.edu!cornellcs!uw-beaver!nntp.cs.ubc.ca!cs.ubc.ca!cs.ubc.ca!not-for-mail From: davem@cs.ubc.ca (Dave Martindale) Newsgroups: sci.geo.satellite-nav Subject: Re: GPS in the Forest Date: 15 Oct 1996 11:53:48 -0700 Organization: Computer Science, University of B.C., Vancouver, B.C., Canada Lines: 58 Message-ID: <540mjs$j5i@harpo.cs.ubc.ca> References: NNTP-Posting-Host: harpo.cs.ubc.ca lwjames@csn.net (Dr. Lawrence W. James) writes: >What advantage does a multi-channel parallel receiver have in this process >over a sequential multiplexing receiver? None, except that, with optimum >use of the multiple channels, reaquistion of a reappearing signal when one >or more of the assumptions is violated to some extent during the signal >blockage would be faster by the ratio of the number of channels. We are >talking about a difference between perhaps a second or two, and a quarter >or a half of a second in practical situations. >In summary, our GPS receiver which is left on while moving through the >forest is quite capable of knowing where it is and where (in the time >domain) to find the satellite signals even when one or more or even all of >them are repeatedly blocked for short periods of time. In addition, our >receiver which is left on has in its memory the ephemeris data of all of >the satellites which are above the horizon, so it can use a satellite >signal in the position solution the instant it locks onto it. That's true *if* the signals remain unblocked long enough for the receiver to find them. For example, the low-cost Garmin units scan all 8 satellites they are tracking every second. If a satellite that has been blocked comes back into view for a full second or more, the receiver *will* be able to see it sometime during its scan. If the satellite is where it should be (really, if the GPS receiver is where it thinks it is), then one second should be enough for the receiver to reaquire the satellite. But if the satellite only appears occasionally through the tree cover, and only for a fraction of a second at a time because of the motion of the receiver, then the probability of the receiver seeing the satellite becomes much smaller. Essentially, an 8-channel scanning receiver is "blind" to any given satellite 7/8 of the time. If all of the satellites are visible all the time (aviation or boating use), "checking in" with each satellite once a second should work very well. But if each satellite appears only for short periods and is then gone again, and the visibility period is small compared to the scan period, the chance of finding the satellite's signal is small. On the other hand, a parallel receiver can watch all of the satellites in use continuously. As long as the receiver is pretty close to where it thinks it is, the receiver should be able to reaquire any satellite if it reappears for a small fraction of a second. Under these circumstances, it could have as much as an 8 times increased likelihood of getting usable tracking information from a satellite than an 8-channel multiplexing receiver has. So when each satellite's signal is blocked most of the time, and appears only for short periods of a fraction of a second (not a bad model of walking under heavy but not complete tree cover), the parallel receiver might have a large advantage. Of course, all this assumes that *each* channel of the parallel receiver is as capable as the single channel of the multiplexing receiver. That isn't necessarily how things happen in real designs. By the way, I have tried walking under relatively heavy tree cover with a Garmin 38. I started out in a clear area and the Garmin was in 3D navigation mode before I entered the trees. The Garmin continued to indicate that it had a position for several minutes, but then it gave up. Dave Article 26999 of sci.geo.satellite-nav: Path: matra.meer.net!news.neumedia.net!uunet!in3.uu.net!www.nntp.primenet.com!nntp.primenet.com!enews.sgi.com!lll-winken.llnl.gov!elroy.jpl.nasa.gov!news.msfc.nasa.gov!centauri.hq.nasa.gov!newsfeed.gsfc.nasa.gov!usenet From: "Tom Clark (W3IWI)" Newsgroups: sci.geo.satellite-nav Subject: Re: GPS in the Forest Date: Thu, 17 Oct 1996 04:36:56 +0100 Organization: NASA Goddard Space Flight Center -- Greenbelt, Maryland USA Lines: 42 Message-ID: <3265A9D8.B90@tomcat.gsfc.nasa.gov> References: <542clt$697@news.belwue.de> Reply-To: clark@tomcat.gsfc.nasa.gov NNTP-Posting-Host: vlbi.gsfc.nasa.gov Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Mailer: Mozilla 3.0Gold (Win95; I) Heinrich Pfeifer wrote: > Now my question: a ball intersects with a circle in *two* points normally. > (Or not at all, but this case is not what we want.) How can the receiver > decide which point is the correct one? > > I guess it takes the point with the smaller velocity. Or maybe one point is > far out in space. > > Some time ago, my Garmin missed the right point. Just after fixing, it showed > a speed of 160 km/h for half a minute, while I (and it) was sitting in my > garden. Then it came with an error message. The last position stored was at > an altitude of 11 000 meters (while I'm living at 230 meters). Did my > receiver decide for the wrong one of the two points? Remember that the "balls" originate at the satellite and have radii equal to the distance from you to the satellite -- i.e. > 10,000 km. Therefore the other intersection point is thousands of km away (and for good geometry, is probably at an altitude ~20,000 km). More likely the error either came from very poor geometry, or because the "seed" position was in error, or because the receiver got a "false lock". Much more serious than the intersecting "balls" is that the code signal sent by the GPS satellites repeats once per millisecond, which means that the range to each satellite is ambiguous at 300 km intervals. So instead of being simple balls/ circles as you described it, the determination is made on the intersection of a number of concentric "balls". The navigation algorithms in your receiver can discard some ambiguities as impossible (like below the surface of the earth or far in space or as producing unrealistic velocities), but you aid the receiver by "seeding" it with an approximate position. Most manufacturers suggest +/- 100-150 km (i.e. about +/-1 degree in lat/lon) for the "seed" accuracy to speed the convergence of the solution. You can see this in action -- intentionally change your lat or lon by about 5 degrees (about 500 km) and you will see that the receiver is very slow to get to the right answer. Tom Clark Article 26879 of sci.geo.satellite-nav: Newsgroups: sci.geo.satellite-nav Path: matra.meer.net!news.spies.com!news.sgi.com!howland.erols.net!feed1.news.erols.com!uunet!news-in2.uu.net!newsfeed.pitt.edu!bb3.andrew.cmu.edu!cantaloupe.srv.cs.cmu.edu!newshost!usenet From: Jim Large Subject: Re: GPS in the Forest Content-Type: text/plain; charset=us-ascii Message-ID: <326655EC.171@nomos.com> Sender: usenet@nomos.com (Usenet news) Nntp-Posting-Host: dhcp-141 Content-Transfer-Encoding: 7bit Organization: Nomos (R) Corporation References: <542clt$697@news.belwue.de> Mime-Version: 1.0 Date: Thu, 17 Oct 1996 15:51:08 GMT X-Mailer: Mozilla 2.01 (Win95; I) Lines: 36 Heinrich Pfeifer wrote: > Provided that the timebase of the reciever is correct (which is > ensured by the fourth SV), reception of only one SV signal gives us > a ball as the locus of receiver position. Reception of two SVs > gives us the intersection of two balls, i.e. a circle, as the locus > of receiver position. Reception of three SVs gives us the > intersection of that circle with a third ball as the locus of > receiver position. The fourth SV is needed for the timebase > correction, not for geometry. This "fourth satellite provides the time base" idea seems to be popular. But, if it was true, then you could get a 3D fix from just three satellites. Suppose your receiver could see three satellites, A, B, and C. Why could it not compute its distance to A using B as the time base, compute distance to B using C as the time base, and finally, compute distance to C using A as the time base? What is that fourth satellite *REALLY* needed for? I think the answer is that the problem can't be solved in steps as you suggest. For example, consider the first step of computing the distance to A using B as the time base. Well the signal from B is subject to the same speed-of-light time delay as the signal from A. If you don't know the distance to B, how can B tell you the time with enough accuracy to compute the distance to A? It can't. Given two satellites, A and B, the only thing your receiver can know about them is the DIFFERENCE between their time delays, and therefore the difference between their distances from itself. Given four satellite signals, A, B, C, and D, your receiver can compute six time deltas, A-B, A-C, A-D, B-C, B-D, and C-D. I'm pretty sure that what happens next is that the software solves a system of simultaneous equations in which the knowns are the orbital elements of the satellites and six time deltas, and the unknowns are the positions of the four satellites, your own position, and the time. -- Jim Large Article 27050 of sci.geo.satellite-nav: Path: matra.meer.net!news.neumedia.net!uunet!in3.uu.net!www.nntp.primenet.com!nntp.primenet.com!howland.erols.net!news-peer.gsl.net!news.gsl.net!usenet.eel.ufl.edu!news.ultranet.com!news.sprintlink.net!news-pen-14.sprintlink.net!news.net-connect.net!news From: "J. Anthony Cavell, PLS" Newsgroups: sci.geo.satellite-nav Subject: Re: GPS in the Forest Date: Thu, 17 Oct 1996 12:12:47 -0500 Organization: Navigation Electroincs, Inc. Lines: 57 Message-ID: <3266690E.70B4@net-connect.net> References: <542clt$697@news.belwue.de> <326655EC.171@nomos.com> Reply-To: gpsman@net-connect.net NNTP-Posting-Host: as48.net-connect.net Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Mailer: Mozilla 3.0b7Gold (Win95; I) Jim Large wrote: > > Heinrich Pfeifer wrote: > > Provided that the timebase of the reciever is correct (which is > > ensured by the fourth SV), . . . > > . . . The fourth SV is needed for the timebase > > correction, not for geometry. > > This "fourth satellite provides the time base" idea seems to be popular. > But, if it was true, then you could get a 3D fix from just three > satellites. Suppose your receiver could see three satellites, A, B, and > C. Why could it not compute its distance to A using B as the time base, > compute distance to B using C as the time base, and finally, compute > distance to C using A as the time base? What is that fourth satellite > *REALLY* needed for? > > I think the answer is that the problem can't be solved in steps as you > suggest. For example, consider the first step of computing the distance > to A using B as the time base. Well the signal from B is subject to the > same speed-of-light time delay as the signal from A. If you don't know > the distance to B, how can B tell you the time with enough accuracy to > compute the distance to A? It can't. Given two satellites, A and B, > the only thing your receiver can know about them is the DIFFERENCE > between their time delays, and therefore the difference between their > distances from itself. > > Given four satellite signals, A, B, C, and D, your receiver can compute > six time deltas, A-B, A-C, A-D, B-C, B-D, and C-D. I'm pretty sure that > what happens next is that the software solves a system of simultaneous > equations in which the knowns are the orbital elements of the satellites > and six time deltas, and the unknowns are the positions of the four > satellites, your own position, and the time. > > -- Jim Large Dear Jim: You are both partially correct. Four satellites are indeed needed for a 3-D solution. Yes four sources of data are needed to simultaneously solve for four unknowns x, y, z & t. And, no, the solution is not performed stepwise. However, for illustrative purposed is is most easily explained as if the solution was so done. Physically the illustration of the geometric truths that one's position may be reckoned by considering the intersection of several spheres of radii equal to the ranges to the satellites can be very enlightening. Sometimes the residual concept after such an illustration may be one of a stepwise solution. GOOD Thread!!! -- J. Anthony Cavell, PLS _______ ______ Vice President /_____ / / @ \ /____ / Navigation Electronics, Inc. /_____ /===(@ % @)===/____ / 200 Toledo Drive /______/ \ @ / /_____/ Lafayette, LA 70506 "G P S m a n" Article 26899 of sci.geo.satellite-nav: Path: matra.meer.net!news.spies.com!nntp1.jpl.nasa.gov!news.uoregon.edu!arclight.uoregon.edu!usenet.eel.ufl.edu!news.mathworks.com!news-peer.gsl.net!news.gsl.net!uwm.edu!math.ohio-state.edu!news.physics.uiowa.edu!news.uiowa.edu!news From: WhiteR@CRPL.Cedar-Rapids.lib.IA.US (Robert S. White) Newsgroups: sci.geo.satellite-nav Subject: Re: GPS in the Forest Date: 17 Oct 1996 23:45:53 GMT Organization: a little Lines: 25 Message-ID: <546gfh$cqo@flood.weeg.uiowa.edu> References: <542clt$697@news.belwue.de> <326655EC.171@nomos.com> <3266690E.70B4@net-connect.net> NNTP-Posting-Host: ppp-106.cedar-rapids.lib.ia.us Mime-Version: 1.0 Content-Type: Text/Plain; charset=US-ASCII X-Newsreader: WinVN 0.99.8 (beta 2) In article <3266690E.70B4@net-connect.net>, gpsman@net-connect.net says... >You are both partially correct. Four satellites are indeed needed for a >3-D solution. Yes four sources of data are needed to simultaneously >solve for four unknowns x, y, z & t. And, no, the solution is not >performed stepwise. But if the receiver was tracking 4 SVs for a while it may have had enough time for its Kalman filter to thoroughly model its clock errors. Then when it goes down to just 3 SVs tracked it can "ride the clock" for the fourth unknown. This can be good enough for a few minutes until the situation changes and a fourth SV is reacquired. Otherwise the Kalman filter implementation can grow the variances to a point that determined 3 SV nav with clock riding is disallowed. >GOOD Thread!!! Agreed! ___________________________________________________________________________ Robert S. White -- an embedded systems software engineer WhiteR@CRPL.Cedar-Rapids.lib.IA.US -- It's long, but I pay for it!