ResearchSpace

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

Show simple item record

dc.contributor.author Focke, RW
dc.date.accessioned 2016-10-13T13:41:15Z
dc.date.available 2016-10-13T13:41:15Z
dc.date.issued 2015-02
dc.identifier.citation Focke, R.W. 2015. Investigating the use of interval algebra to schedule mechanically steered multistatic radars. PhD Thesis. University of Cape Town, Department of Electrical Engineering en_US
dc.identifier.uri http://radarmasters.co.za/wp-content/uploads/2014/01/rfocke_thesis.pdf
dc.identifier.uri http://hdl.handle.net/10204/8831
dc.description A thesis submitted to the Department of Electrical Engineering, University of Cape Town, in fulfilment of the requirements for the Degree of Doctor of Philosophy en_US
dc.description.abstract The findings presented in this thesis support the hypothesis that Interval Algebra (IA), as a temporal reasoning language, should perform scheduling of sensor dwells efficiently 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 supercomputers. 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_US
dc.language.iso en en_US
dc.publisher University of Cape Town en_US
dc.relation.ispartofseries Worklist;15401
dc.subject Multistatic radars en_US
dc.subject Scheduling en_US
dc.subject Surveillance en_US
dc.subject Radar networks en_US
dc.subject Process refinement en_US
dc.subject Resource management en_US
dc.subject Mechanically Steered Multistatic Surveillance Radar Networks en_US
dc.subject MSMSRNs en_US
dc.title Investigating the use of interval algebra to schedule mechanically steered multistatic radars en_US
dc.type Report en_US
dc.identifier.apacitation Focke, R. (2015). <i>Investigating the use of interval algebra to schedule mechanically steered multistatic radars</i> (Worklist;15401). University of Cape Town. Retrieved from http://hdl.handle.net/10204/8831 en_ZA
dc.identifier.chicagocitation Focke, RW <i>Investigating the use of interval algebra to schedule mechanically steered multistatic radars.</i> Worklist;15401. University of Cape Town, 2015. http://hdl.handle.net/10204/8831 en_ZA
dc.identifier.vancouvercitation Focke R. Investigating the use of interval algebra to schedule mechanically steered multistatic radars. 2015 [cited yyyy month dd]. Available from: http://hdl.handle.net/10204/8831 en_ZA
dc.identifier.ris TY - Report AU - Focke, RW 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 efficiently 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 supercomputers. 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-02 DB - ResearchSpace DP - CSIR KW - Multistatic radars KW - Scheduling KW - Surveillance KW - Radar networks KW - Process refinement KW - Resource management KW - Mechanically Steered Multistatic Surveillance Radar Networks KW - MSMSRNs LK - https://researchspace.csir.co.za 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/10204/8831 ER - en_ZA


Files in this item

This item appears in the following Collection(s)

Show simple item record