An implementation of ultrasonic time-of

Surveying
technical
An implementation of ultrasonic
time-of-flight based localisation
by Gideon Ferreira, CSIR NRE Mining
The implementation of an underground localisation system, utilising ultrasonic and electromagnetic signals to
facilitate time-of-flight (TOF) based trilateration.
T
he localisation system described
is a 2D positioning system and
mainly finds its application
within excavations of the order of
30 m x 30 m x 1 m in tabular ore
bodies. The vertical height in the
application environment is limited
and no significant value is added by
determining this coordinate.
The system consists of a number of
beacons with known locations and a
number of objects that need to localise
themselves within a shared reference
grid. An object can only localise itself
within coverage of a sufficient number
of beacons, in this case at least three.
The system is required to resolve
coordinates with 10 cm accuracy.
Localisation is achieved by
implementing a trilateration algorithm
with an ordinary least squares (OLS)
estimator. With this approach, the
object only has to measure the
distance between itself and the
beacons, and know the associated
beacons’ locations in order to localise
itself. The OLS estimator is required (as
opposed to analytical methods), since
only approximate distances can be
measured as a result of noise inherent
in the system.
Objects determine the distance to
a given beacon by measuring the
time-of-flight (TOF) of an ultrasonic
signal emitted by a beacon. The TOF
is related to the distance between the
beacon and the object by the speed
at which the wave travels. In order to
measure TOF, the object has to know
when the signal was transmitted. To
accomplish this, a beacon periodically
emits the ultrasonic signal, together with
an electromagnetic signal at the same
instant, so that the TOF upon reception
by the object is given by the difference
between the arrival times of the two
signals. The technique assumes the TOF
of the electromagnetic signal to be zero,
allowing the electromagnetic signal to
act as a synchronisation mechanism.
Over time, an object acquires distance
measurements from different beacons
covering it and localises itself after the
sufficient number of distances has been
measured.
Beacon implementation
Beacons exist in a common
environment and periodically transmit
information that is utilised by any
number of objects within coverage. This
information includes the synchronised
ultrasonic and electromagnetic signals
used for ranging, a form of unique
identification and the beacon’s own
location. It should be possible for an
object to uniquely identify a beacon in
order to associate ranging results with
the transmitting beacon. The location of
a beacon is surveyed during installation
and stored in memory on the beacon.
Hardware and software description
In the design, location and identification
information are transmitted with a radio.
The radio signal is used for a number
of functions. Apart from transmitting a
beacon’s location and identification, the
start of the transmission serves as the
synchronisation mechanism and during
transmission the carrier is used to avoid
transmission collisions. Fig. 1 illustrates
the timing of the events during the
transmit process.
Fig. 1 and 2: Images of the beacon devices that make up the underground localisation system. These are screwed onto a roof bolt that is
mounted in the hanging wall.
22 PositionIT - April/May 2009
SURVEYING
technical
programmable duration. Typically, the
transmission has a duration of 16 cycles.
The radio frequency carrier is only
turned off after enough time has
passed for each object to have
received all the information and the
ultrasonic pulse, ensuring collisions
can be avoided during the complete
ultrasonic and radio transmission
cycle. This is achieved by taking into
account that the greatest distance
an ultrasonic pulse needs to travel is
approximately 30 m, assuming the
pulse takes longer to reach the objects
than a complete data transfer over the
radio link. The flow diagram in Fig. 4
summarises the described transmit
process that is implemented on the
main controller.
Fig. 3: Beacon transmit cycle.
Power consumption is improved by
turning the ultrasonic transmitter off
when it is not transmitting, to increase
battery life and reduce noise emissions.
Object implementation
An object’s main tasks are to acquire
information from a sufficient number
of beacons and then to localise itself
using this information. First of all,
the object needs to identify a unique
beacon and then determine the
distance from itself to the beacon.
This information is then stored and the
process repeated for different beacons.
After enough information has been
acquired, the object will execute the
estimation algorithm on the acquired
information and return an estimated
position.
Hardware and software description
The object also utilises a CC1100
radio transceiver and an ATmega128
microprocessor as the main system
controller. A fundamental component
of an object is the ultrasonic receiver
system.
transceiver generates an interrupt
on the controller at the instant
transmission begins, at which time an
ultrasonic pulse is emitted.
The receiver is implemented with a
two-stage amplifier having a large input
impedance and high gain, allowing an
object to detect faint ultrasonic signals
over a range of 30 m. The amplifier
also offers some band-pass filtering to
reduce noise.
A piezoelectric transducer is used to
generate the 40 kHz ultrasonic pulse.
The transducer is driven with a 40 V
peak-to-peak signal with the aid of a
bridge driver and a boost converter.
The main controller is responsible for
generating the control sequence to
emit the ultrasonic pulse, with software
Fig. 5 shows the input stage of the
receiver, implemented with a high input
impedance bootstrapped non-inverting
amplifier [1] having a gain of 58 dB.
The frequency response is shown in
Fig. 6. It has a rather wide bandwidth
and mainly filters out lower
frequencies.
Fig. 4: Beacon transmit process.
The radio is designed around a
CC 1100 transceiver, which is
configured and controlled through
its onboard serial peripheral
interface (SPI). Before transmission,
the transceiver is loaded with a
packet and configured to only
start transmitting after a clear
channel assessment is completed
to avoid collisions. An ATmega128
microprocessor is used as the
main controller in the system. The
PositionIT - April/May 2009
23
SURVEYING
technical
Fig. 5: Input stage.
Fig. 7: Output stage.
Fig. 6: Input stage frequency response.
Fig. 8: Output stage frequency response.
The output stage of the receiver is
shown in Fig. 7 and is implemented
with a multiple pole feedback filter.
The filter is centered on 40 kHz with
a bandwidth of 3 kHz allowing for
transducer tolerances. The gain of
the output stage is 38 dB and the
frequency response of the filter can be
seen in Fig. 8.
simple fixed threshold detector
is implemented with the analog
comparator, which interrupts the
controller upon detection. The detector
can easily be expanded to dynamically
adjust the threshold of the detector
by taking the received signal strength
indicator (RSSI), supplied by the radio
transceiver, into account.
In order for the object to measure
the TOF of the ultrasonic pulse, the
radio transceiver interrupts the main
controller at the instant reception is
started. The controller then starts a
timer with microsecond resolution,
pending the reception of the
ultrasonic pulse. In the meanwhile,
the packet transmitted from the
beacon is being transferred into the
receive FIFO of the radio transceiver,
containing the beacon identification
and location.
The timer on the controller is
immediately stopped when an
ultrasonic pulse is detected by the
analog comparator, resulting in the TOF
measurement.
The output of the ultrasonic receiver is
rectified and applied to the controller’s
onboard analog comparator. A
24 The TOF measurement is converted to
distance using Eqn. 1:
݀ ൌ ቌ͵͵ͳǡ͵ඨͳ ൅
ܶ
ቍ ൈ ܱܶ‫ܨ‬
ʹ͹͵ǡͳͷ
(1)
In this equation the influence of
temperature on the speed at which
sound travels can be seen, where T is
the ambient temperature in degrees
Celsius. The speed of sound in 0°C
dry air is approximately 331,3 m.s-1.
The temperature is currently taken
to be the average temperature of the
operating environment. Other external
effects such as humidity and pressure
are calibrated once by adding a
constant offset to the speed estimation
of sound. Should conditions vary more
than expected, the temperature sensor
onboard the radio transceiver can be
used to compensate for changes in
temperature.
The calculated distance is stored
with the beacon information that is
transferred from the radio transceiver.
The process is repeated until the
minimum number of required beacons
has been detected, after which the OLS
algorithm is executed. The algorithm
returns the object’s estimated location,
which is made available over a serial
communication interface. The flow
diagram in Fig. 9 summarises the
receive process implemented on the
main controller.
PositionIT - April/May 2009
SURVEYING
technical
Fig. 10: Typical system configuration.
Fig. 9: Object receive process.
OLS estimator
The estimator will be discussed with
regard to the simulation results
presented in this section. Fig. 10
illustrates the typical configuration of
the system, with beacons installed
on opposite sides of the excavation,
approximately 30 m apart, and
a number of objects inside the
excavation.
Fig. 11: OLS estimator performance.
Let Bi = (xi,yi) denote the ith beacon
with surveyed location and θ = (x,y)
an unknown object’s location. The
exact distance between the object and
the beacon is denoted with di(θ). A
method of linearisation is used by
Navidi et al. [2], in which a reference
point is introduced at the mean of the
beacon locations.
The distance between a beacon and
the reference point is denoted by dir
and the distance from the object to the
reference point by dr(θ). The actual
measurement made by an object for
the distance between itself and the ith
beacon is denoted by ri.
The OLS estimator minimises the
quantity given by Eqn. 2 [2].
௡
ଶ
෍ൣ݀௜௥
െ ‫ݎ‬௥ଶ െ ݀௜ ሺߠሻଶ ൧
௜ୀଵ
An earlier simulation result is
shown in Fig. 11, in which the
OLS estimator’s performance
PositionIT - April/May 2009
(2)
was investigated as a function of
the object’s location within the
excavation. Measurements were
simulated with a uniform error
distribution, using a standard
deviation of 1 m and zero mean. The
RMS error in the estimate is plotted
for each object in Fig. 9 and was
typically better than 70 cm. It was
noted that location estimates for
objects closer to the centre of the
excavation were more accurate than
estimates for objects close to the
sides of the excavation, as expected.
Conclusions
The implementation of an
underground localisation system
was described in this article. The
system comprises two types of
elements, viz. beacons with surveyed
locations and objects with unknown
locations that need to be estimated.
In order to accomplish this, objects
implement a trilateration algorithm
with an OLS estimator, which only
requires an object to measure the
distance between itself and the
beacons, and know the associated
beacons’ locations in order to localise
itself. Beacons periodically transmit
their locations over a radio channel
synchronised with an ultrasonic pulse.
Objects use the radio transmission
and ultrasonic pulse to determine
the distance between itself and the
transmitting beacon by measuring
the TOF of the ultrasonic pulse. A
fundamental component of the object
hardware is the receiver amplifier
that enables the object to detect
faint ultrasonic pulses over a range of
approximately 30 m.
References
[1] P Horowitz and W Hill: The Art of
Electronics, Cambridge University
Press, pp. 1039, New York, 1989.
[2] W Navidi, W S Murphy Jr. and
W Hereman: Statistical methods
in surveying by trilateration,
Computational Statistics & Data
Analysis, Vol. 27, pp. 209-227, 1998.
Contact Gideon Ferreira,
CSIR NRE Mining,
Tel 011 358-0091,
[email protected] 
25