答辩公告
我的位置在: 首页 > 答辩公告 > 正文
李琪博士生答辩公告
浏览次数:日期:2021-09-06编辑:研究生秘书

学位论文简介

随着分布式系统的发展,分布式系统的典型应用包含集群系统和众包系统。集群系统是内部网络把一组计算机硬件和计算机软件紧密连接起来的系统,此系统可以互相协作,共同完成计算任务。论文发现在已有的分布式系统中有很多缺陷:没有较为完善的数学模型来最大化集群系统的利润并从理论上提供性能保证;缺乏一个较为完善的数学模型来考虑集群系统中多维资源(CPU和内存)的分配问题并从理论上提供性能保证;没有较为完善的数学模型来最大化众包系统的利润并从理论上提供性能保证;缺乏一个较为完善的数学模型来考虑众包系统中工作者能力可变的任务分配问题并从理论上提供性能保证。本文主要围绕集群系统和众包系统中存在的问题分别展开研究,其主要工作和创新点如下:

1.在集群系统中提出了一种最大化平台利润的模型,此模型不仅考虑了作业的效用,而且考虑了资源的消耗。本文根据消耗函数的类型提出了两种利润模型:资源消耗函数为凸函数的模型和资源消耗函数为线性函数的模型。然后本文用primal-dual方法去求解此模型,进而得到一个近似解。为了证明算法的有效性,本文利用dual-fitting方法分析原始目标值和对偶目标值在相邻时隙中的增长量,最后证明出增长量的竞争比是个常数。最后本文把基础算法的性能和本文调度算法的性能作对比,实验测试结果表明该研究设计的算法能将平台的利润提高24%

 

2.在集群系统中提出了一种消耗多维资源(CPU和内存)的模型,此模型的目标是每次选择作业中的部分任务进行调度,以此来最大化系统中作业的效用。在此资源分配模型中本文考虑了两大难点:作业预算和多维资源消耗。为了解决作业预算问题,本文把长期约束条件转化为短期约束条件,并且在每个时隙中设计出了高效的在线资源分配算法。为了解决多维资源消耗问题,本文首先固定一种消耗资源,然后寻找另一种最佳的消耗资源。本文对比已有模型的基础算法,实验结果表明本文的调度算法能将作业的效用提高20%。另外,还可以利用本文的技术解决其他的凸优化问题。

 

3.在众包系统中提出了一种新的利润最大化模型,该模型可以满足任务和工作者的异质性。本文根据众包的类型考虑了两种利润模型:一个任务对一个工作者的模型和多个任务对一个工作者的模型。此优化模型利用原始对偶方法处理效用凹函数和成本凸函数,并且设计了两种高效的在线任务调度算法。本文将整数问题转换为小数问题来解决NP-hard问题。在这些调度算法中,本文把任务和工作者构造成一个伪树,目的是把任务分配给合适的工作者。为了证明算法的有效性,本章利用dual-fitting方法在所有时隙中分析原始目标值和对偶目标值的竞争比。此外,通过模拟实验来检验调度算法的性能,这些调度算法的性能比基础算法好且在总利润方面提高了19%

 

4.在众包系统中提出了一种新的MABMulti-Armed Bandit )多臂老虎机调度模型去最大化大任务的效用,且考虑了工作者的能力是可变的。本文可以处理短期约束条件并且考虑了多维大规模任务和较小的约束条件违规情况。本文根据过去时隙中工作者完成的工作量来估计每个工作者的处理能力,有利于任务分配。此外,本文设计了一种在线调度算法,该调度算法通过Gradient-Descent方法更新对偶变量。本文采用一种新的方法来分析在线算法的性能,该方法随着时间的增长产生次线性的regret。此外,在总效用上本文设计的调度算法比基础算法好且提高了15%

主要学术成果

  1. Li qi, Cai lijun; Profit Maximization in Mobile Crowdsourcing: A Competitive Analysis. IEEE ACCESS, 2021, 9:27827-27839 (第一作者,中科院SCI-2区收录,IF20193.745

  2. [2] Li qi, Cai lijun; Online Task SchedulingWithWorkers Variabilities in Crowdsourcing. IEEE ACCESS, 2021,(第一作者,中科院SCI-2区收录,在线发表)

  3. Li qi; A Novel Game-Theoretic Model for Content-Adaptive Image Steganography. ICDCS, 2017: 232-237(第一作者,CCF B

  4. 李琪;一种基于Arnold 变换的数字图像自适应隐写算法, 通信学报, 2016, 37(06)192-198(第一作者中文核心CCF B类期刊)

  5. 李琪;基于百度云存储的数字取证研究,计算机科学, 2015, 42(10)40-51(第一作者中文CCF B类期刊)

  6. Li qi, Cai lijun; A Dual Approach for Online Scheduling of Approximation Jobs. Frontiers of Computer Science, 2021, (under review)(第一作者,中科院SCI-2区收录,小修)