Chapter 6: Alternative Navigation System
As was shown in Chapter 5, GPS navigation is not perfect,
even with DGPS correction the system cannot always track a
pedestrian. A reliable backup for the primary navigational
system must be incorporated into the design. To this end,
research on a practical and accurate system has been
conducted, and is presented here.
A revised diagram of the Strider Box, showing the
incorporation of the ANS is presented in
Fig. 23
. As was
described in Chapter 5, the pedometer and digital compass
were chosen because they are inexpensive, lightweight,
accurate and readably available. The switching circuit was
added because the computer that will be used may not have
enough ports to handle the GPS, DGPS, voice synthesizer and
the ANS.
When the pedometer makes contact with the spring, which is
connected to +5 volts, the voltage at the microcontroller
will fluctuate due to the bouncing inherent with mechanical
switches. This is shown in
Fig. 24
. Debouncing of this
switch will be done through software.
The Vector 2X digital compass by Precision Navigation Inc.
is connected to the I/O (Input / Output) pins of the
microcontroller, and the clocking of the data stream from
the compass is done through software. The data being
clocked in is a 16-bit Binary number that ranges from 0
through decimal 359, indicating the direction in degrees
the compass is facing.
As it stands Strider has a laptop computer with a voice
synthesizer plugged into it, a keypad for access to the
system, and a Strider Box (with GPS and DGPS contained
within). The Strider Box is plugged into the laptop's
RS-232
comm port, and the voice synthesizer, depending upon
the type, can plug into the PCMCIA slot, parallel port,
second RS-232 port (if available), or could be software
driven. The ANS must not take up an additional port
because we do not know which port the voice synthesizer
will use. Therefore, the system must be connected in
series with the Strider Box and the laptop computer. A
first attempt at the new Strider Box layout and
packet
communication is shown in
Fig. 25
.
The original idea of a buffer for combining GPS and ANS
packets as shown in
Fig. 25
was abandoned once the
microcontroller was chosen. The idea of filtering and
integrating the two packet streams was examined but because
the laptop computer through software could combine the two
data streams, this seemed to be the best solution. The new
design integrates the two packet streams with a physical
switching circuit as was shown in
Fig. 23
.
The switching circuit is a four 2-input NAND-gate
configuration with a single control line, and two
controllable data lines. When the computer signals the ANS
to send its data, the microcontroller will toggle the
control line of the switching circuit. This prevents the
GPS receiver from transmitting, and allows the ANS to
transmit its data over the same RS-232 connection.
Fig. 26
shows the NAND gate configuration, which was implemented,
and
Fig. 27
shows what this circuit equates to with a MUX.
Initially the Motorola HC705-K series microcontroller was
used in the ANS because it was readily available, and since
it contained an EPROM that could be reprogrammed a number
of times during the debugging and testing phase of
development. This microcontroller was very limited: With
only 512 bytes of ROM, and 32 bytes of RAM which included
stack space, programming it was very difficult. The
HC705-K had one
IRQ
(Interrupt Request) line, and ten
programmable I/O lines. A simplified schematic diagram
showing the original design is shown here in
Fig. 28
.
Problems arose due to the memory constraints of the HC705-K
microcontroller. Since there were only 512 bytes of ROM
space and only 32 bytes of RAM, trying to keep the program
within these limits was difficult, and eventually
impossible. The memory required to store the steps in a
given direction took 18 bytes of RAM, with a resolution of
twenty degrees, i.e. 360(degrees) / 20(degree resolution) =
18. In addition, 5 bytes of RAM was taken up for the
ISR
(Interrupt Service Routine), which only left 9 bytes of RAM
for the entire program. To improve memory usage, variables
were used more than once, and all eight bits of the
variables were used to keep state. There was a trade off
with RAM and ROM, as RAM efficiency increased the amount of
ROM space used also increased, and before long there was no
memory left. There were also problems with the number of
interrupts for this microcontroller. With only one
interrupt, steps were missed while either sending data to
the computer, or receiving data from the compass.
Due to all of the EPROM erasing and reprogramming, one of
the pins broke off the microcontroller, and instead of
trying to repair it, it was decided to move up to the next
series of this microcontroller. The HC705-J series
microcontroller was chosen with 1024 bytes of ROM and 64
bytes of RAM, and up to five IRQs. In addition, since it
is the same brand of microcontroller, all of the code
written for the HC705-K microcontroller would run on the
HC705-J microcontroller.
The schematic diagram shown in Fig. 28 was revised with the
new microcontroller. A simplified schematic diagram is
shown in
Fig. 29
. Additional features were added because
of the increased number of I/O and IRQ lines. The
microcontroller now has complete control over the compass,
as well as an interrupt-driven switch for calibrating the
compass externally. Both the computer request line and
pedometer are now interrupt-driven. Neither the HC705-K
nor the HC705-J microcontroller contain a
UART
(Universal
Asynchronous Receiver-Transmitter), so all data sent to the
computer had to be manually clocked out through software,
details on this will be described in section 6.3.4.
A complete schematic diagram is shown next in
Fig. 30
.
Table 4
contains the component values for the schematic
diagram.
Table 4: Parts List for the Alternative Navigation System
|
Component
|
Value
|
Component
|
Value
|
|
VIN
|
+12 volts
|
C1
|
27 pF
|
|
XTAL
|
4.00 MHz
|
C2
|
27 pF
|
|
Bat1
|
3.6 volt
|
C3
|
10 uF
|
|
T1
|
LM340T5
|
C4
|
0.01 uF
|
|
D1
|
1N4148
|
C5
|
10 uF
|
|
D2
|
1N4148
|
C6
|
10 uF
|
|
D3
|
1N4148
|
C7
|
10 uF
|
|
R1
|
5 Kohms
|
C8
|
10 uF
|
|
R2
|
5 Kohms
|
C9
|
10 uF
|
The ANS currently runs on 5 volts, and draws 9mA. This
results in a power consumption of 45mW.
Figure 30: Schematic Diagram of the Alternative Navigation
System
There are still a few shortcomings with the HC705-J
microcontroller. With only an 8-bit signed accumulator and
X-register; many temporary variables had to be used. When
an interrupt occurs, polling of the IRQ line and Ports A0
through A3 had to be done to determine which IRQ line
caused the interrupt. The internal timer of the
microcontroller cannot be reset, it is either on or off,
and when it is turned on it doesn't reset itself.
Therefore, if the timer is set to cause a software
interrupt every 8.2 ms, when the timer is first turned on
the first interrupt could happen any time from 0 through
8.2 ms.
The internal clock of the microcontroller is set by the
on-chip oscillator. This oscillator is set by the external
crystal oscillator or fosc at 4.00 MHz, as shown in Fig.
30. The frequency fosc of the external oscillator is
divided by two to produce the internal operating frequency
fop at 2.00 MHz.
[14]
Due to the limited memory space for both program and
variables, programming the microcontroller was not an easy
task. The programming language used was assembly with the
instruction set and technical specifications of the chip
given in the HC05 MC68HC705J1A Technical Data manual.
[14]
The complete documented assembly code for the ANS can be
found in
Appendix J
.
The main program of the ANS is quite simple. First the
program goes through an initialization phase where all
variables are set, all I/O ports are initialized, and the
external devices are enabled. Next, the processor waits
for something to happen.
When a step occurs, the pedometer causes an interrupt and
the program will debounce and registers the step taken.
Next, the program signals the compass to send the current
direction the compass is facing. Once the data from the
compass is ready to be sent, the compass signals the
microcontroller that it can start retrieving the data.
Once the data from the compass is in the microcontroller,
the number of steps taken since the last direction obtained
is stored in a vector, indexed via the direction of travel.
Periodically the computer will signal the microcontroller
to send its data. The microcontroller will then stop the
GPS receiver from transmitting over the same data line,
send its data to the computer, re-enable the GPS receiver
to transmit, clear the data array, and the process starts
all over again.
Table 5
shows the state table of the ANS
and its corresponding state diagram is in
Fig. 31
.
Fig. 32
has the flow diagram of the main program.
Table 5: State Table for the Alternative Navigation System
|
State
|
Meaning
|
|
0
|
Idle, nothing happening
|
|
1
|
Step occurring
|
|
2
|
Step occurred waiting for direction
|
|
3
|
Waiting for direction and new step occurring
|
The first attempt at debouncing the pedometer through
software seemed to work when testing was done with an ideal
switch but when the actual pedometer was used, multiple
steps were recorded for each step taken.
The first attempt used was, after the interrupt occurred,
to wait in a loop until polling of the IRQ line resulted in
fifteen consecutive 5volt readings indicating that the step
had occurred. This is shown in
Fig. 33
.
In theory during the mechanical bouncing phase of a step,
the counter would be continuously reset, until the voltage
stays at the 5volt level for fifteen consecutive polls of
the IRQ line. This would indicate that a step had taken
place. There are a number of flaws with this method for
debouncing the pedometer. By continuously looping until
fifteen consecutive 5volt readings are recorded, a
potential endless loop may occur. In addition, what is to
say that fifteen polls during the mechanical bouncing phase
could not result in all being at the 5volt level, and
multiple step detections could result during this phase.
This method for debouncing the pedometer was rejected
because multiple step detections did occur for a single
step taken, and a new method for debouncing the circuit was
implemented.
A different approach to debouncing the pedometer uses the
internal timer of the microcontroller to wait a specific
number of milliseconds after the completion of a step
before registering the step as a valid one. Once the onset
of a step occurs the internal interrupt timer is enabled,
and it will cause an interrupt every 8.2 ms. During this
interrupt the ISR (Interrupt Service Routine) will check to
see if the Pedometer has bounced, and if so will reset the
total time to wait back to zero. Once the entire 205 ms
has elapsed the step is then registered. The total time
waited after the step has occurred is set at 205 ms, or
twenty-five 8.2 ms timer interrupts. This is shown in
Fig. 34
.
Fig. 35
shows a magnified view of the mechanical
bouncing and its affect on the 205 ms counter.
As seen in
Fig. 35
, the delay counter can start increasing
during the mechanical bouncing phase. This is why there is
a delay of 205 ms before registering the step as valid.
Otherwise, by reducing the delay time, multiple step
detections could occur for the same step caused by this
mechanical bouncing of the switch. This 205 ms delay
before registering a step was found by trial and error. An
initial value of 100 ms was chosen, and during field tests,
it was found that for every step taken one to three steps
were registered. Doubling this initial delay time resulted
in a one-to-one mapping of steps taken to steps recorded.
Using a debounce timer of 205 ms results in accurately
recording up to four steps per second by the user. If the
user is taking more than four steps per second, the device
is not being used in the manner it was intended.
This new method for debouncing the pedometer was
successful, and for each step taken, only one step was
recorded. Pseudocode for both the Pedometer's and Timer's
ISR can be found in
Appendix K
, and Figures 36 and 37 show
the flowcharts of these routines.
The Vector 2X compass is configured in a Slave mode of
operation. In Slave mode, the microcontroller generates
the data clock. With the M/S pin open, as shown in Fig.
30, Slave mode is enabled. Clocking of the data does not
have to be uniform in this mode, which means clocking in of
the direction can be interrupted to record a new step, or
send data to the computer.
Appendix I
offers the Vector 2X
Compass's technical specifications.
In Slave mode, the microcontroller signals the compass for
data by lowering the P/C pin (Poll / Continuous) for at
least 10 ms. A 10 ms pulse indicates the polling method, by
holding low P/C, the compass will continuously send its
direction. Upon pulsing P/C the EOC (End OF Conversion)
line goes from high to low, and will return high when the
compass has the new direction calculated and the data is
ready to be clocked out. Once the EOC line returns high, a
minimum of 10 ms must be waited before lowering the SS
(Slave Select) line, which stays low until the completion
of the data retrieval process. By lowering the SS line,
SDO
(Serial Data Output) switches from a tri-state mode to
an output. In Slave mode, SCLK (Serial Clock Input) is an
input, and the clock is generated externally by the
microcontroller. Sixteen complete clock cycles must be
generated (i.e. sixteen falling and rising edges) for the
compass heading to be acquired through SDO. Data is valid
on the rising edge of the each clock cycle, and the maximum
frequency of SCLK is 1 MHz. The data can be in either in
BCD (Binary Coded Decimal) or Binary format. It was
decided to use Binary as the data format. Using a 16-bit
Binary number to represent a decimal number ranging from 0
through 359 degrees, implies that the first 7 bits are all
zeros.
Fig. 38
shows the basic compass schematic diagram,
and
Fig. 39
illustrates the timing diagram of the compass
in Slave mode.
![Figure 39: Data Clock Timing Diagram [12]](fig39.gif)
s
Calibration of the compass must be done each time power to
the compass is lost. This is why the backup Battery BAT1
in
Fig. 30
was added, to ensure that the compass has power
even after the device is turned off. The current drawn for
the purpose of keeping the internal memory of the compass
valid is less than 1 mA, and BAT1 will last for at least
six months. An external switch SW1 as shown in
Fig. 30
was
added to manually calibrate the compass. By pressing the
switch the compass will take a reading of the magnetic
fields applied to the compass, next the user turns 180
degrees and presses the switch again. The compass will
then record this new magnetic field, and based upon the
field strengths of the two magnetic fields, it will
determine which direction is north, and store this in its
internal memory. This method for calibrating the compass
can be in error, if another magnetic field is presently
acting upon the compass during the calibration phase. In
this case the compass will "think" north is in the
direction of the secondary applied magnetic field.
Unfortunately, this is the only method for calibration.
Additional software can be added to try to minimize this
effect. With the aid of GPS and DGPS to determine
direction of travel, the compass direction can be verified,
and be re-calibrated if necessary. The pseudocode for the
calibration of the compass can be found in
Appendix L
.
For each step taken, the compass is polled and a direction
is requested. If multiple steps occur before the direction
is obtained all steps are assumed to be in the direction
finally obtained from the compass, and is stored
accordingly. The compass can only be polled once per
direction, by toggling the P/C line for at least 10 ms, and
cannot be polled again until the direction requested has
been completely clocked out of SDO. The time to completely
clock out the data from the compass varies because
pedometer bouncing and other interrupts are still enabled.
Consequently, if multiple steps occur while a direction is
being obtained, all those steps are assumed to be in the
same direction as the initial step. Once the compass has
signaled the microcontroller that a direction is valid and
ready to be sent, the program reads in the first eight bits
of the direction into the accumulator, since the
accumulator can only store eight bits. It then tests the
LSB
(Least Significant Bit) of the accumulator to see if
the direction that will be obtained is in the order of 256
through 359 degrees. This information is stored and the
next eight bits are read into the accumulator. The
accumulator now has a binary number between 0 through 255
decimal, but with the information stored about the LSB from
the first eight data bits known, we have a direction
ranging from 0 through 359 degrees.
Currently the storage array holds eighteen data elements
and for directions ranging from 0 through 359 degrees this
results in a twenty-degree resolution. When a step is
taken, and the corresponding direction is obtained, the
step taken is indexed into the storage array offset by the
direction. For example, if one step is taken and the
direction obtained from the compass equals 260 degrees, the
corresponding storage array position would be 260 / 20 =
13. This resolution of twenty degrees can be brought to a
resolution of ten degrees without increasing the size of
the storage array. This is accomplished by using the array
elements for two different directions and the sign of the
number indicates the direction of the step. Positive
numbers are used to indicate directions ranging from 0
through 179 degrees, and negative numbers to indicate
directions from 180 through 359 degrees. For example, if a
step is taken at 90 degrees, +1 is added to array element
9, and if a step is taken at 270 degrees –1 is added to
array element 9. This is because if a person takes a step
east, then turns around and takes a step west, the net
result is 0, or in fact they essentially have not moved.
Table 6
shows the mapping from the 9 bits of relevant data
received from the compass into the eighteen-element storage
array. The maximum number of steps that can be recorded in
any direction therefore is reduced. Originally 255 steps
(unsigned) could be recorded, now 127 steps in the forward
direction (i.e. 0 through 179 degrees) and 128 steps in the
reverse direction (i.e. 180 through 359 degrees) can be
recorded. These limits are of no concern since the array
will be cleared after the data is sent to the computer,
which is done every couple of seconds.
Appendix M
has the
pseudocode for the obtaining the direction from the compass.
Table 6: Compass Direction Mapped to Storage Array
|
Degrees
|
Dec
Signed 8-bit
|
Hex
8-bit
|
Binary
|
Array
Position
|
Direction
|
|
0
|
0
|
0
|
0 0000 0000
|
0
|
+
|
|
1
|
1
|
1
|
0 0000 0001
|
0
|
+
|
|
2
|
2
|
2
|
0 0000 0010
|
0
|
+
|
|
…
|
…
|
…
|
…
|
|
|
|
9
|
9
|
9
|
0 0000 1001
|
0
|
+
|
|
10
|
10
|
A
|
0 0000 1010
|
1
|
+
|
|
11
|
11
|
B
|
0 0000 1011
|
1
|
+
|
|
…
|
…
|
…
|
…
|
|
|
|
126
|
126
|
7E
|
0 0111 1110
|
12
|
+
|
|
127
|
127
|
7F
|
0 0111 1111
|
12
|
+
|
|
128
|
-128
|
80
|
0 1000 0000
|
12
|
+
|
|
129
|
-127
|
81
|
0 1000 0001
|
12
|
+
|
|
130
|
-126
|
82
|
0 1000 0010
|
13
|
+
|
|
…
|
…
|
…
|
…
|
|
|
|
178
|
-78
|
B2
|
0 1011 0010
|
17
|
+
|
|
179
|
-77
|
B3
|
0 1011 0011
|
17
|
+
|
|
180
|
-76
|
B4
|
0 1011 0100
|
0
|
-
|
|
181
|
-75
|
B5
|
0 1011 0101
|
0
|
-
|
|
…
|
…
|
…
|
…
|
|
|
|
252
|
-4
|
FC
|
0 1111 1100
|
7
|
-
|
|
253
|
-3
|
FD
|
0 1111 1101
|
7
|
-
|
|
254
|
-2
|
FE
|
0 1111 1110
|
7
|
-
|
|
255
|
-1
|
FF
|
0 1111 1111
|
7
|
-
|
|
256
|
0
|
0
|
1 0000 0000
|
7
|
-
|
|
257
|
1
|
1
|
1 0000 0001
|
7
|
-
|
|
258
|
2
|
2
|
1 0000 0010
|
7
|
-
|
|
259
|
3
|
3
|
1 0000 0011
|
7
|
-
|
|
260
|
4
|
4
|
1 0000 0100
|
8
|
-
|
|
…
|
…
|
…
|
…
|
|
|
|
355
|
99
|
63
|
1 0110 0011
|
17
|
-
|
|
356
|
100
|
64
|
1 0110 0100
|
17
|
-
|
|
357
|
101
|
65
|
1 0110 0101
|
17
|
-
|
|
358
|
102
|
66
|
1 0110 0110
|
17
|
-
|
|
359
|
103
|
67
|
1 0110 0111
|
17
|
-
|
Directions + indicate (0 - 179 degrees), Directions -
indicate (180-359 degrees)
Without the aid of a separate UART, all data sent to the
computer had to be precisely clocked out. With the aid of
a Motorola Application Note on the HC05 Serial
Communication Techniques
[14]
, a data module was written to
send data to a serial port at 9600 baud, 8 bit, no parity,
and 1 stop bit. Strider uses the same baud rate and port
settings to communicate with the GPS receiver. This will
simplify integration of the ANS with Strider.
The computer will periodically signal the microcontroller
to send its data by raising the
RTS
(Request to Send) line,
which causes an interrupt in the microcontroller. When the
interrupt occurs, the program turns off all other
interrupts because timing is critical for clocking out the
data to the computer. The GPS receiver is then prevented
from transmitting and the microcontroller has control over
the RS-232 connection to the computer. First the
header
is
sent (AA Hex) or (10101010 Binary), next the 18 bytes of
the storage array, and finally the
CRC
(Cyclic Redundancy
Check) byte. The CRC byte is calculated by simply adding
up all the data bytes sent including the header. With an
8-bit signed accumulator and limited mathematical
operations there was not much else that could be done in
tandem while sending the data to the computer.
Preprocessing of the CRC value was considered but due to
the limited memory and speed of this microcontroller it was
felt that anything more would reduce system performance.
Besides, currently the CRC value is only used by the
computer to verify that the data is correct, and if it does
not match the CRC value generated, the data is ignored and
lost. A method for re-transmitting the data if the CRC
check fails must still be done.
Appendix N
has the
pseudocode for sending the ANS data to the computer, and
Fig. 40
has the flow diagram for this routine.
For testing the ANS, a small C-language windows program was
designed. Every two seconds the program will signal the
ANS by raising RTS (Request to Send) line to send its data
and then read in the data from the serial port. After
verifying the CRC value it would process the data and draw
on the screen the steps taken in the appropriate direction.
The program acts like an "etch-a-sketch", with north being
the top of the screen. The program can also save the data
obtained to disk, and later redraw an old path travelled.
This provided the testing necessary to verify that the ANS
works. Test results will be presented in Chapter 7. See
Appendix O
for the pseudocode of this test program.
The cable that was used connecting the computer to the ANS
was a null modem cable that only had three wires. So when
the RTS line was raised through software, nothing happened,
and it was assumed that there was a problem with the
windows programming environment. After a lot of time was
spent looking for software problems, finally the cause of
the problem was discovered and corrected.
The program was compiled and tested on a Pentium 200
machine, and timing was a problem. The computer would
raise the RTS line, start reading in the data from its
buffered UART chip, but before all of the data could be
sent to the computer, it would empty the buffer. The
packet length would be less than the twenty bytes expected
and would fail, and therefore the program would lower the
RTS line, and the data would be lost. This problem was
overcome by raising the RTS line for 40 ms, which is more
than enough time for the microcontroller to send its 20
bytes of data at 9600 baud. Then the computer would read
in the entire packet, which solved the timing problem.
After the program was running correctly on the Pentium 200,
field tests outside were done on a laptop computer. The
computer is a 33 MHz 486 laptop, which introduced another
timing problem. The processing speed of the laptop was too
slow to handle the messages generated to draw the steps on
the screen, and would occasionally miss some messages.
Instead of asynchronously posting the windows messages,
messages were synchronized with a windows "SendMessage"
command, which solved the problem.
This ANS completes the third requirement of this thesis, a
reliable and accurate alternative for when GPS fails. This
system will accurately track a user as they travel,
providing the instantaneous direction and number of steps
taken in the given direction of travel. Calibration of
steps taken, to distance travelled, can be done
"on-the-fly" through software, using when available, the
GPS and DGPS solutions. This system can be easily
integrated with Strider to complete the personal guidance
system as set forth by this thesis. The next chapter
provides the results of testing the ANS.
