Using evolutionary algorithms to resolve 3-dimensional geometries encoded in indeterminate data-sets
Rollings, Graham
Date: 7 November 2011
Thesis or dissertation
Publisher
University of Exeter
Degree Title
PhD in Computer Science
Abstract
This thesis concerns the development of optimisation algorithms to determine the
relative co-location, (localisation), of a number of freely-flying 'Smart Dust mote' sensor
platform elements using a non-deterministic data-set derived from the duplex wireless transmissions between elements. Smart dust motes are miniaturised, ...
This thesis concerns the development of optimisation algorithms to determine the
relative co-location, (localisation), of a number of freely-flying 'Smart Dust mote' sensor
platform elements using a non-deterministic data-set derived from the duplex wireless transmissions between elements. Smart dust motes are miniaturised, microprocessor
based, electronic sensor platforms, frequently used for a wide range of remote
environmental monitoring applications; including specific climate synoptic observation
research and more general meteorology.
For the application proposed in this thesis a cluster of the notional smart dust motes
are configured to imitate discrete 'Radio Drop Sonde' elements of the wireless enabled
monitoring system in use by meteorological research organisations worldwide. This
cluster is modelled in software in order to establish the relative positions during the
'flight' ; the normal mode of deployment for the Drop Sonde is by ejection from an
aeroplane into an upper-air zone of interest, such as a storm cloud.
Therefore the underlying research question is, how to track a number of these independent, duplex wireless linked, free-flying monitoring devices in 3-dimensions and time (to give the monitored data complete spatio-temporal validity). This represents a significant practical challenge, the solution applied in this thesis was to generate 3-dimensional geometries using the only 'real-time' data available; the Radio Signal Strength Indicator (RSSI) data is generated through the 'normal' duplex wireless communications between motes. Individual RSSI values can be considered as a 'representation of the distance magnitude' between wireless devices; when collated into a spatio-temporal data-set it 'encodes' the relative, co-locational, 3-dimensional geometry of all devices in the cluster.
The reconstruction, (or decoding), of the 3-dimensional geometries encoded in the
spatio-temporal data-set is a complex problem that is addressed through the application
of various algorithms. These include, Random Search, and optimisation algorithms,
such as the Stochastic Hill-climber, and various forms of Evolutionary Algorithm.
It was found that the performance of the geometric reconstruction could be improved
through identification of salient aspects of the modelled environment, the result was
heuristic operators. In general these led to a decrease in the time taken to reach a
convergent solution or a reduction in the number of candidate search space solutions
that must be considered. The software model written for this thesis has been implemented
to generalise the fundamental characteristics of an optimisation algorithm and
to incorporate them into a generic software framework; this then provides the common
code to all model algorithms used.
Doctoral Theses
Doctoral College
Item views 0
Full item downloads 0