带有端口约束的文件传输调度问题的算法研究

来源 :大连理工大学 | 被引量 : 0次 | 上传用户:TIGERKING2009
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
在分布式网络中,各节点之间进行大文件的传输是现在生产和生活中经常出现的场景,由于物理条件的限制,单个节点不可能同时进行所有文件的传输。在这种情况下,安排文件在何时开始传输从而使得收益最大成了一个非常值得研究的问题。文件传输调度问题正是在这种背景下产生的。本文关注的是最基本的带有端口约束的文件传输调度问题——给定节点以及需要在节点间传输的文件,其中节点之间是全连通的,不允许文件经中间节点转发,并且文件的传输不允许中断,在满足端口约束的情况下,设计文件传输调度方案,使得所有文件完成传输的时间最短。本文提出了两个新的求解带有端口约束的文件传输调度问题的整数规划模型M3和M4。与现有的模型M1和M2相比,通过设计不同的决策变量和表示约束的方式,本文提出了具有更少变量数和约束数的新模型M3。另外,本文还通过在模型M3中引入基本下界,进一步减少了模型的约束数,获得了改进的模型M4。本文进行了大量的数值实验,验证了本文提出的模型M3和M4的优越性,尤其是模型M4。与现有的最好的整数规划模型相比,求解相同的实例时模型M4平均只需要其约14.3%的时间。另外,本文提出的模型M4可以求解更大规模的实例(高达100个节点,600条边),平均仅需不到150秒,而现有的模型在合理的时间内(600秒)无法求解这样的实例。除了研究求解带有端口约束的文件传输调度问题的精确方法以外,本文还提出了一个更高效的基于变邻域搜索的启发式算法Modified-VNS。根据文件传输调度问题本身的特性,本文设计了更合适的局部搜索算法,平衡了搜索邻域时搜索的深度和广度。另外,本文还设计了新的解的表示方式以及根据解的表示方式构建可行调度方案的方法,大大降低了计算解的目标函数值的时间开销。通过大量的对比实验,本文验证了算法Modified-VNS的高效性。和现有的基于变邻域搜索的启发式算法相比,算法ModifiedVNS获得的解不仅具有更高的质量(和最优解之间的gap小于1%),并且花费更少的时间。即使和现有的最快的启发式算法相比,算法Modified-VNS平均也仅需其约14.4%的求解时间。
其他文献
共价有机骨架(Covalent organic framework,COFs)是一类由小分子有机单体通过共价键连接而成的晶态多孔材料。由于其具有规则的骨架、大的比表面积、开放的多孔结构、丰富的官能团、良好的吸附性能、多样的设计合成方案等特点,COFs被认为是可用于固相微萃取(Solid-phase microextraction,SPME)纤维涂层的高效材料。一方面,通过设计不同几何形状的有机单体
学位
当前人工智能的安全受到普遍的关注,多种防治措施在积极开展。联邦学习主要从技术层面入手,着重探究其中的隐私性与安全性。一方面,联邦学习方案大多都采用同一密钥的加密算法,无法抵御恶意服务器和参与者的合谋攻击。同时,针对模型梯度的攻击也会导致私有数据泄露。另一方面,参与者之间存在资源和数据异构,导致其对模型性能贡献程度不同,合理评估参与者性能并确定选择方法也是一个值得关注的问题。本文提出了一种联邦学习场
学位
随着位置感知技术的发展,轨迹数据越来越容易被收集并应用到城市交通、移动医疗等方面。但当轨迹数据与疾病、年龄等属性一起收集时,往往包含大量的用户敏感信息,如果未对这些数据进行有效的隐私处理而直接发布,攻击者很容易发动背景知识攻击,导致用户隐私泄露。差分隐私作为一种无关背景知识的强隐私保护模型在数据发布的隐私保护中被广泛应用。如何在保护轨迹数据隐私的同时,提高数据可用性是目前研究的热点之一。差分隐私目
学位
由于物联网迅猛发展以及大规模智能终端接入,静态边缘节点无法高效解决资源不足的设备与密集型任务之间的冲突问题。无人机充当移动基站可在通信设施不足地区或地震等自然灾害情况下快速通信和处理设备任务。然而,基于无人机基站的卸载研究大多忽略历史数据的重要价值和终端设备产生任务的规律性。此外,现有研究很少考虑大规模任务卸载,未考虑随着终端设备产生任务的改变会导致所需无人机数量的改变。本文创建多无人机集群辅助移
学位
近年来,随着边缘计算的应用普及,卸载策略需要适应日渐复杂的通信场景,同时,任务分割与共享往往只发生在边缘服务器和用户间,大量用户的空余计算资源没有得到有效利用。因此,如何建立适应5G通信场景的卸载策略与怎样完善任务共享卸载计算方案成为了边缘计算中的两个亟待解决的问题。首先,以往卸载策略研究大多结合传统的通信方式进行独立讨论,缺乏对计算资源分配过程及最终结果反馈。因此,传统方案在5G时代缺乏应用性与
学位
软件已经成为人们日常生活中不可或缺的一部分,因此保证软件的安全性是研究领域中热门话题。软件的可重复构建就是其中的一个研究方向,软件的可重复构建在确认软件的源代码和软件的二进制之间的对应关系中承担着重要的作用。但是在修复软件不可重复构建故障的工作中存在着一系列的挑战。在这些挑战中本文将主要关心以下两方面的挑战:(1)故障定位粒度不够精细;(2)修复补丁手动生成。为了应对这些挑战,本文提出了一种新的研
学位
Agent理论和技术作为分布式人工智能的重要研究方向之一,近些年被应用到计算机支持的各种应用中。Agent理论的核心研究内容是多agent系统,它为内部独立的agent提供了一种称为联盟的协作模式,这种模式让agent可以自发地形成联盟并分配一定资源去共同完成一项任务,从而提高任务完成效率和个人收益。作为多agent系统中亟待解决的关键问题,联盟结构生成(Coalition Structure G
学位
区块链去中心化导致了交易隐私数据泄露,引发信息安全问题。零知识范围证明,旨在机密验证交易数据范围区间,处理链上隐私保护和交易机密监管问题。而区块链交易吞吐量的倍增,提高了区块链对范围证明方案的性能需求。现有范围证明的证据生成及验证性能仍不如预期,且数据适配性和可聚合性较差,无法处理浮点数范围问题,也无法实现计算成本恒定的聚合证明,严重限制了链上机密交易性能。针对上述问题,本文主要工作内容如下:(1
学位
由于区块链的共识机制范围是全体节点,基于区块链的加密货币的可扩展性存在严重的瓶颈。支付通道网络作为一种有前途的解决方案被提出。支付通道网络将区块链上的交易转移到链下的支付通道上进行,大大提高了交易速度。支付通道网络的路由算法对于优化支付通道网络的成功率、交易费用以及交易延迟至关重要。支付通道网络上的交易会在交易路径的任何支付通道余额不足的情况下失败。因此,为每个交易选择资金充足的支付通道作为交易路
学位
小样本学习针对的是只有少量有标签样本的任务。由于样本信息较少,使得小样本学习成为深度学习应用中的一个挑战。本文的目的就是希望通过深度学习模型和度量学习的思想,在少量样本中提取更有类别代表性的特征,来提高小样本分类任务的准确性。具体地讲,度量学习方法旨在学习样本间的度量关系。在小样本学习图像分类问题中,度量学习的思想体现在,分类过程使用相似性度量的方式来判断两个样本是否属于同一个类别,而度量的对象就
学位