基于分布式架构的Costas序列搜索系统的设计与实现

作     者：余凡 

作者单位：南京邮电大学 

学位级别：硕士

导师姓名：姚建国

授予年度：2021年

学科分类：082403[工学-水声工程] 08[工学] 081203[工学-计算机应用技术] 0824[工学-船舶与海洋工程] 0835[工学-软件工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：Costas序列 穷举法搜索 分治递归 任务窃取 分布式 

摘      要：Costas序列具有理想的自相关被广泛应用于遥测、无线通信和密码学等领域,但是对某些特殊阶数的Costas序列的存在性问题尚未有较深入的研究成果。为了研究高阶Costas序列,论文对Costas序列的特点和构造方法进行了研究,讨论了代数构造法和穷举法的差异,并着重对穷举法的高效实现进行了深入的研究,为解决高阶序列搜索效率问题提出了用分布式计算的思想来构造Costas序列的搜索系统。针对分布式搜索系统的实现,本文的研究内容主要分为以下两部分,并通过实验数据证明了论文设计的搜索系统能显著提高Costas序列的搜索速度。第一部分从Costas序列的定义出发对Costas序列的单机搜索效率进行优化,针对Costas序列搜索任务的特点提出基于任务窃取机制的分治递归多线程调度算法。对多线程环境下的遍历搜索,由于Costas序列分布的不均匀性,传统多线程搜索方式指定任务后只能由固定的线程完成所有计算任务,而不同的任务计算量存在差异,导致线程资源浪费。当线程任务量较大时,通过分治递归对任务进行切割,线程之间利用任务窃取机制使线程池中的线程负载均衡,实现最大程度利用线程资源。第二部分针对单机性能存在瓶颈的问题提出基于分布式架构实现Costas序列搜索系统。由于高阶Costas序列遍历搜索的计算量较大,单机搜索高阶序列消耗的时间较长。因此研究使用分布式架构对高阶搜索任务进行分解,并使用网络中间件,如数据库、缓存、消息队列等对计算任务进行可靠的分发和汇总,由多机协同实现高效的搜索。该搜索系统的结构采用管理端/消费端模式,管理端负责任务的分解和汇总等,消费端负责执行任务和返回计算结果。管理端和消费端高度解耦,在管理端性能足够的前提下,通过合理的参数配置可动态增减消费端数量,实现对系统运算能力的动态扩缩容。管理端和消费端通过中间件保障任务信息的可靠传递,并且三者均支持跨平台和集群部署,最终实现高效的高阶Costas序列搜索系统。