Investigating the use of interval algebra to schedule mechanically steered multistatic radars

Simple item page
dc.contributor.advisorInggs, Michael Ren_ZA
dc.contributor.advisorDe Villiers, J Pen_ZA
dc.contributor.authorFocke, Richard Wilhelmen_ZA
dc.date.accessioned2015-12-01T08:56:30Z
dc.date.available2015-12-01T08:56:30Z
dc.date.issued2015en_ZA
dc.descriptionIncludes bibliographical referencesen_ZA
dc.description.abstractThe findings presented in this thesis support the hypothesis that Interval Algebra (IA), as a temporal reasoning language, should perform scheduling of sensor dwells effciently and effectively. Scheduling of multistatic radars was identified as a promising research area, as it builds upon prior research into monostatic and bistatic radars in South Africa. The hypothesis can be validated by answering three research questions. Can IA allow a multistatic radar system to make more multistatic measurements of targets? Can IA perform as well as established multisensor scheduling techniques in terms of computational requirements? Is it possible to enhance the performance of IA by making use of parallel processing architectures? Answering the first two research questions required selecting a comparison algorithm that is already used extensively in scheduling. The Greedy Randomised Adaptive Search Procedure (GRASP) was selected as it represents two of the biggest groupings of existing scheduling algorithms. Furthermore, greedy optimisations are often preferred as they converge to optimal solutions quicker. Two scheduling scenarios were devised which made use of a binary mechanically steered surveillance radar network. One environment made use of a very simplistic model of the information fusion system, the other implemented all the details rigorously. The first environment was used to compare IA to GRASP, while the second tested a nimble IA scheduler. For both these environments Monte-Carlo simulations were used to test random target locations and motion. A novel IA algorithm that makes use of reduced point algebra was generated that allowed execution time to be reduced. Another, simpler novel contribution was an IA algorithm that ensured that radar tasks are only added to the IA network when required. Using these two techniques it was possible for IA to meet both the performance and execution time of GRASP, as allows for a richer set of constraints than required to perform multistatic scheduling. The Nimble IA Scheduler is a novel contribution which solves the realistic requirement of handling fast-moving and accelerating targets, and provides a small performance increase for the surveillance system. Answering the last research question required implementing IA on a parallel processing architecture. General-Purpose Graphical Processing Units (GP-GPUs) were selected since no published research made use these architectures and they should be well suited to solving constraint satisfaction problems. A novel parallel IA path consistency algorithm was generated in OpenCL building upon parallel versions found in the literature for super-computers. Monte-Carlo simulations were run where both the serial and parallel versions were used to solve path consistency for randomly generated IA networks. The results for the GP-GPU identified that for large networks there was speed-up of between two to three times for consistent networks under three conditions. Firstly, the IA network must be sufficiently large to warrant copying the data to the GP-GPU. Secondly, the IA network must have a percentage of known constraints between 25% and 75%. Thirdly, the average number of IA operators should be less than 9.8. Thus, IA can provide equivalent performance to GRASP if the constraints are reduced. Given problems that require a richer set of constraints, these can easily be handled using IA. Nimble IA scheduling can provide a means to increase the multistatic measurements made and reduce those that are missed due to prediction inaccuracies. IA path consistency can also be used on GP-GPUs but only provides speed-ups under specific conditions.en_ZA
dc.identifier.apacitationFocke, R. W. (2015). <i>Investigating the use of interval algebra to schedule mechanically steered multistatic radars</i>. (Thesis). University of Cape Town ,Faculty of Engineering & the Built Environment ,Department of Electrical Engineering. Retrieved from http://hdl.handle.net/11427/15477en_ZA
dc.identifier.chicagocitationFocke, Richard Wilhelm. <i>"Investigating the use of interval algebra to schedule mechanically steered multistatic radars."</i> Thesis., University of Cape Town ,Faculty of Engineering & the Built Environment ,Department of Electrical Engineering, 2015. http://hdl.handle.net/11427/15477en_ZA
dc.identifier.citationFocke, R. 2015. Investigating the use of interval algebra to schedule mechanically steered multistatic radars. University of Cape Town.en_ZA
dc.identifier.ris TY - Thesis / Dissertation AU - Focke, Richard Wilhelm AB - The findings presented in this thesis support the hypothesis that Interval Algebra (IA), as a temporal reasoning language, should perform scheduling of sensor dwells effciently and effectively. Scheduling of multistatic radars was identified as a promising research area, as it builds upon prior research into monostatic and bistatic radars in South Africa. The hypothesis can be validated by answering three research questions. Can IA allow a multistatic radar system to make more multistatic measurements of targets? Can IA perform as well as established multisensor scheduling techniques in terms of computational requirements? Is it possible to enhance the performance of IA by making use of parallel processing architectures? Answering the first two research questions required selecting a comparison algorithm that is already used extensively in scheduling. The Greedy Randomised Adaptive Search Procedure (GRASP) was selected as it represents two of the biggest groupings of existing scheduling algorithms. Furthermore, greedy optimisations are often preferred as they converge to optimal solutions quicker. Two scheduling scenarios were devised which made use of a binary mechanically steered surveillance radar network. One environment made use of a very simplistic model of the information fusion system, the other implemented all the details rigorously. The first environment was used to compare IA to GRASP, while the second tested a nimble IA scheduler. For both these environments Monte-Carlo simulations were used to test random target locations and motion. A novel IA algorithm that makes use of reduced point algebra was generated that allowed execution time to be reduced. Another, simpler novel contribution was an IA algorithm that ensured that radar tasks are only added to the IA network when required. Using these two techniques it was possible for IA to meet both the performance and execution time of GRASP, as allows for a richer set of constraints than required to perform multistatic scheduling. The Nimble IA Scheduler is a novel contribution which solves the realistic requirement of handling fast-moving and accelerating targets, and provides a small performance increase for the surveillance system. Answering the last research question required implementing IA on a parallel processing architecture. General-Purpose Graphical Processing Units (GP-GPUs) were selected since no published research made use these architectures and they should be well suited to solving constraint satisfaction problems. A novel parallel IA path consistency algorithm was generated in OpenCL building upon parallel versions found in the literature for super-computers. Monte-Carlo simulations were run where both the serial and parallel versions were used to solve path consistency for randomly generated IA networks. The results for the GP-GPU identified that for large networks there was speed-up of between two to three times for consistent networks under three conditions. Firstly, the IA network must be sufficiently large to warrant copying the data to the GP-GPU. Secondly, the IA network must have a percentage of known constraints between 25% and 75%. Thirdly, the average number of IA operators should be less than 9.8. Thus, IA can provide equivalent performance to GRASP if the constraints are reduced. Given problems that require a richer set of constraints, these can easily be handled using IA. Nimble IA scheduling can provide a means to increase the multistatic measurements made and reduce those that are missed due to prediction inaccuracies. IA path consistency can also be used on GP-GPUs but only provides speed-ups under specific conditions. DA - 2015 DB - OpenUCT DP - University of Cape Town LK - https://open.uct.ac.za PB - University of Cape Town PY - 2015 T1 - Investigating the use of interval algebra to schedule mechanically steered multistatic radars TI - Investigating the use of interval algebra to schedule mechanically steered multistatic radars UR - http://hdl.handle.net/11427/15477 ER - en_ZA
dc.identifier.urihttp://hdl.handle.net/11427/15477
dc.identifier.vancouvercitationFocke RW. Investigating the use of interval algebra to schedule mechanically steered multistatic radars. [Thesis]. University of Cape Town ,Faculty of Engineering & the Built Environment ,Department of Electrical Engineering, 2015 [cited yyyy month dd]. Available from: http://hdl.handle.net/11427/15477en_ZA
dc.language.isoengen_ZA
dc.publisher.departmentDepartment of Electrical Engineeringen_ZA
dc.publisher.facultyFaculty of Engineering and the Built Environment
dc.publisher.institutionUniversity of Cape Town
dc.subject.otherElectrical Engineeringen_ZA
dc.titleInvestigating the use of interval algebra to schedule mechanically steered multistatic radarsen_ZA
dc.typeDoctoral Thesis
dc.type.qualificationlevelDoctoral
dc.type.qualificationnamePhDen_ZA
uct.type.filetypeText
uct.type.filetypeImage
uct.type.publicationResearchen_ZA
uct.type.resourceThesisen_ZA
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
thesis_ebe_2015_fckric001-thesis.pdf
Size:
1.21 MB
Format:
Adobe Portable Document Format
Description:
Download
Collections
PhD / Doctoral