Using evolutionary algorithms to resolve 3-dimensional geometries encoded in indeterminate data-sets
Thesis or dissertation
University of Exeter
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.
EPSRC sourced bursary via The University of Exeter
Wright, C. David
PhD in Computer Science