基于混合云环境的科学工作流数据布局方法

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN112632615A(43)申请公布日2021.04.09(21)申请号202011599293.1(22)申请日2020.12.30(71)申请人福州大学地址350108福建省福州市闽侯县福州大学城乌龙江北大道2号福州大学(72)发明人刘漳辉　赵旭　林兵　陈星　(74)专利代理机构福州元创专利商标代理有限公司35100代理人陈明鑫　蔡学俊(51)Int.Cl.G06F21/62(2013.01)G06N3/00(2006.01)权利要求书3页说明书15页附图3页(54)发明名称基于混合云环境的科学工作流数据布局方法(57)摘要本发明涉及一种基于混合云环境的科学工作流数据布局方法，包括以下步骤：步骤S1:设定隐私数据集和数据中心最大容量条件，并初始化相关参数；步骤S2:以最小化数据模糊传输时间为目标，并考虑到数据中心的容量约束，在引入不确定性概念后，构建混合云环境下面向模糊时间优化的科学工作流数据布局模型；步骤S3:构建若干初始 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 ；步骤S4:构建粒子到数据布局结果的映射关系；步骤S5:基于改进的FGA‑DPSO的数据布局算法，获取最优方案。本发明基于混合云环境，实现有效的科学工作流数据布局。CN112632615ACN112632615A权　利　要　求　书1/3页1.一种基于混合云环境的科学工作流数据布局方法，其特征在于，包括以下步骤：步骤S1:设定隐私数据集和数据中心最大容量条件，并初始化相关参数；步骤S2:以最小化数据模糊传输时间为目标，并考虑到数据中心的容量约束，在引入不确定性概念后，构建混合云环境下面向模糊时间优化的科学工作流数据布局模型；步骤S3:构建若干初始方案；步骤S4:构建粒子到数据布局结果的映射关系；步骤S5:基于改进的FGA‑DPSO的数据布局算法，获取最优方案。2.根据权利要求1所述的基于混合云环境的科学工作流数据布局方法，其特征在于，所述混合云环境由一定数量的公有数据中心和一定数量的私有数据中心构成，其中私有数据中心容量一定，具体的如式(1)所示：其中：DCpub表示公有数据中心集合；DCpri表示私有数据中心集合；dci表示编号为i的数据中心；Vi表示数据中心的最大容量；Δi∈{0,1}表示数据中心dci的属性，若dci∈DCpub，则Δi＝0，dci只能存放公有数据，若dci∈DCpri，则Δi＝1，dci可以存放公有数据和隐私数据。3.根据权利要求1所述的基于混合云环境的科学工作流数据布局方法，其特征在于，所述科学工作流由任务和数据集构成所述任务之间存在数据依赖关系，即一个任务的输出数据集可能是其他任务的输入数据集，还存在时序上的先后关系，即只有当一个任务的前驱任务全部执行完毕，该任务才能执行，当所有任务执行完毕后，该科学工作流也随即结束；所述数据集分为隐私数据集和公有数据集两类：隐私数据集只能存放在固定的私有数据中心，以其为输入数据集的任务也必须调度到该数据中心上运行；公有数据集则无存储位置限制；具体的科学工作流为有向无环图G，如式(2)所示：其中：T表示科学工作流中所有任务的集合；E表示科学工作流中不同任务之间的所有数据依赖关系的集合，DS表示科学工作流中所有数据集的集合；tc表示编号为c的任务；eij表示任务ti与任务tj之间的数据依赖关系，且ti是tj的直接先驱任务；dsl表示编号为l的数据集；Ii表示任务ti的输入数据集合；Oi表示任务ti的输出数据集合；DC(ti)表示任务ti的执行数据中心；vi表示数据集dsi的大小；gti表示生成数据集dsi的任务编号，其中初始数据集的gti为0；lci表示存放数据集dsi的数据中心编号。2CN112632615A权　利　要　求　书2/3页4.根据权利要求1所述的基于混合云环境的科学工作流数据布局方法，其特征在于，所述混合云环境下面向模糊时间优化的科学工作流数据布局模型，具体为：其中uij＝{0,1}表示数据集dsj是否存放于数据中心dci，是则uij＝1，否则uij＝0。5.根据权利要求1所述的基于混合云环境的科学工作流数据布局方法，其特征在于，所述步骤S4具体为：①初始化每个数据中心的已存储数据量dccur(i)为0，布局方案的总模糊传输时间设置为②初始化完成后，按照每个初始数据集对应的编号，将其放置到对应编号的数据中心，更新该数据中心的已存储量dccur(X[i])并进行判断，即若该数据中心的已存储量超过该数据中心的最大容量，则该粒子对应的解不可行，中止当前操作并返回；③按执行顺序遍历所有任务，在遍历过程中总是选择模糊传输时间最小的数据中心dcj将任务tj放置并进行判断，当该粒子对应的解不可行，即数据中心dcj的当前存储量、任务tj的输入数据集大小sum(Ij)和输出数据集大小sum(Oj)之和超出该数据中心的最大容量时，中止当前操作并返回；反之，则将任务tj的输出数据集Oj放置到对应的数据中心并更新已存储量；④按执行顺序遍历所有任务，计算每条需要跨数据中心传输的数据集所花费的模糊数据传输时间累加得到总模糊传输时间⑤输出和该编码粒子及其对应的数据布局策略。6.根据权利要求1所述的基于混合云环境的科学工作流数据布局方法，其特征在于，所述步骤S5具体为：步骤S51:随机生成一个含有N个粒子的初始种群；步骤S52:将每个初始粒子记为自己的历史最优个体；步骤S53:评估初始种群中每个粒子的适应度函数值；步骤S54:采用比较运算，找出并记录初始种群的全局最优个体Xbest；步骤S55：设置惯性权重w、个体认知因子c1、种群认知因子c2和最大迭代次数Itera_max步骤S56：对个体进行变异和交叉操作，完成粒子更新，并根据比较运算更新粒子和种群的历史最优个体；步骤S57:更新惯性权重w、个体认知因子c1、种群认知因子c2；步骤S58:循环步骤S56‑57，直至迭代达到最大迭代次数Itera_max，得到全局最优个体。7.根据权利要求6所述的基于混合云环境的科学工作流数据布局方法，其特征在于，所述适应度函数值如式(17)所示：其中：F(S)表示数据布局策略S的适应度函数；表示粒子Xi的数据模糊传输时3CN112632615A权　利　要　求　书3/3页间。8.根据权利要求6所述的基于混合云环境的科学工作流数据布局方法，其特征在于，所述步骤S54具体为:对于惯性部分，采用变异操作，定义运算符如式(20)：其中：r0∈(0,1)表示随机因子；Mu()表示随机地在取值范围内改变编码粒子中的一个分位，即变异操作；对于其中的个体认知和种群认知部分，采用交叉操作，定义运算符⊕如式(22)和式(23)所示：其中：r1,r2∈(0,1)表示随机因子；Cp(Ai(t+1),pi(t))和Cg(Bi(t+1),g(t))表示随机选择编码粒子Ai(t+1)和Bi(t+1)的两个随机分位，并与pi(t)和g(t)相同位置上的数值进行交叉；粒子的更新过程改进为式(25)：9.根据权利要求6所述的基于混合云环境的科学工作流数据布局方法，其特征在于，所述惯性权重w如式(26)所示：其中：d(Xi(t),g(t))表示当前粒子Xi(t)对应的解与当前种群历史最优粒子g(t)对应的解的差异程度。10.根据权利要求6所述的基于混合云环境的科学工作流数据布局方法，其特征在于，所述比较预算具体为：对于三角模糊数定义三个比较值：定义取大运算法则如下：若则否则若则否则若则否则。4CN112632615A说　明　书1/15页基于混合云环境的科学工作流数据布局方法技术领域[0001]本发明涉及信息技术领域，具体涉及一种基于混合云环境的科学工作流数据布局方法。背景技术[0002]随着大数据技术的广泛应用，现代网络环境产生的数据量日益增长，传统的网格计算等分布式计算已经不能满足海量数据的处理需要，云计算成为了研究热点。混合云环境具有高共享性、高利用性和可定制的优点，由分布在不同地理位置上的数据中心组成，是包括多个私有数据中心和公有数据中心的混合网络计算环境：公有云具有高可靠性和容量极大等优点，其核心特质是资源共享；私有云具有高灵活性和高安全性等优点，能够在工作运行过程中保证数据的隐私。[0003]许多工作步骤严格的科学研究因为流程的复杂和数据量的不断增加，无法人工管理这些科学研究过程，所以采用工作流技术来管理。用于管理、监控和执行这些科学过程的工作流叫做科学工作流。科学工作流涉及到的数据量巨大，通常需要存储于分布在不同地理位置的数据中心，而在科学工作流的运行过程中需要跨数据中心传输这些数据，所以以减少科学工作流运行时的数据传输时间为目标，在带宽有限的条件下对混合云环境下的科学工作流进行数据布局是必要的。发明内容[0004]有鉴于此，本发明的目的在于提供一种基于混合云环境的科学工作流数据布局方法，有效的对科学工作流数据进行布局。[0005]为实现上述目的，本发明采用如下技术方案：[0006]一种基于混合云环境的科学工作流数据布局方法，包括以下步骤：[0007]步骤S1:设定隐私数据集和数据中心最大容量条件，并初始化相关参数；[0008]步骤S2:以最小化数据模糊传输时间为目标，并考虑到数据中心的容量约束，在引入不确定性概念后，构建混合云环境下面向模糊时间优化的科学工作流数据布局模型；[0009]步骤S3:构建若干初始方案；[0010]步骤S4:构建粒子到数据布局结果的映射关系；[0011]步骤S5:基于改进的FGA‑DPSO的数据布局算法，获取最优方案。[0012]进一步的，所述混合云环境由一定数量的公有数据中心和一定数量的私有数据中心构成，其中私有数据中心容量一定，具体的如式(1)所示：[0013][0014]其中：DCpub表示公有数据中心集合；DCpri表示私有数据中心集合；dci表示编号为i5CN112632615A说　明　书2/15页的数据中心；Vi表示数据中心的最大容量；Δi∈{0,1}表示数据中心dci的属性，若dci∈DCpub，则Δi＝0，dci只能存放公有数据，若dci∈DCpri，则Δi＝1，dci可以存放公有数据和隐私数据。[0015]进一步的，所述科学工作流由任务和数据集构成[0016]所述任务之间存在数据依赖关系，即一个任务的输出数据集可能是其他任务的输入数据集，还存在时序上的先后关系，即只有当一个任务的前驱任务全部执行完毕，该任务才能执行，当所有任务执行完毕后，该科学工作流也随即结束；[0017]所述数据集分为隐私数据集和公有数据集两类：隐私数据集只能存放在固定的私有数据中心，以其为输入数据集的任务也必须调度到该数据中心上运行；公有数据集则无存储位置限制；[0018]具体的科学工作流为有向无环图G，如式(2)所示：[0019][0020]其中：T表示科学工作流中所有任务的集合；E表示科学工作流中不同任务之间的所有数据依赖关系的集合，DS表示科学工作流中所有数据集的集合；tc表示编号为c的任务；eij表示任务ti与任务tj之间的数据依赖关系，且ti是tj的直接先驱任务；dsl表示编号为l的数据集；Ii表示任务ti的输入数据集合；Oi表示任务ti的输出数据集合；DC(ti)表示任务ti的执行数据中心；vi表示数据集dsi的大小；gti表示生成数据集dsi的任务编号，其中初始数据集的gti为0；lci表示存放数据集dsi的数据中心编号。[0021]进一步的，所述混合云环境下面向模糊时间优化的科学工作流数据布局模型，具体为：[0022][0023]其中uij＝{0,1}表示数据集dsj是否存放于数据中心dci，是则uij＝1，否则uij＝0。[0024]进一步的，所述步骤S4具体为：[0025]①初始化每个数据中心的已存储数据量dccur(i)为0，布局方案的总模糊传输时间设置为[0026]②初始化完成后，按照每个初始数据集对应的编号，将其放置到对应编号的数据中心，更新该数据中心的已存储量dccur(X[i])并进行判断，即若该数据中心的已存储量超过该数据中心的最大容量，则该粒子对应的解不可行，中止当前操作并返回；6CN112632615A说　明　书3/15页[0027]③按执行顺序遍历所有任务，在遍历过程中总是选择模糊传输时间最小的数据中心dcj将任务tj放置并进行判断，当该粒子对应的解不可行，即数据中心dcj的当前存储量、任务tj的输入数据集大小sum(Ij)和输出数据集大小sum(Oj)之和超出该数据中心的最大容量时，中止当前操作并返回；反之，则将任务tj的输出数据集Oj放置到对应的数据中心并更新已存储量；[0028]④按执行顺序遍历所有任务，计算每条需要跨数据中心传输的数据集所花费的模糊数据传输时间累加得到总模糊传输时间[0029]⑤输出和该编码粒子及其对应的数据布局策略。[0030]进一步的，所述步骤S5具体为：[0031]步骤S51:随机生成一个含有N个粒子的初始种群；[0032]步骤S52:将每个初始粒子记为自己的历史最优个体；[0033]步骤S53:评估初始种群中每个粒子的适应度函数值；[0034]步骤S54:采用比较运算，找出并记录初始种群的全局最优个体Xbest；[0035]步骤S55：设置惯性权重w、个体认知因子c1、种群认知因子c2和最大迭代次数Itera_max[0036]步骤S56：对个体进行变异和交叉操作，完成粒子更新，并根据比较运算更新粒子和种群的历史最优个体；[0037]步骤S57:更新惯性权重w、个体认知因子c1、种群认知因子c2；[0038]步骤S58:循环步骤S56‑57，直至迭代达到最大迭代次数Itera_max，得到全局最优个体。[0039]进一步的，所述适应度函数值如式(17)所示：[0040][0041]其中：F(S)表示数据布局策略S的适应度函数；表示粒子Xi的数据模糊传输时间。[0042]进一步的，所述步骤S54具体为:对于惯性部分，采用变异操作，定义运算符如式(20)：[0043][0044]其中：r0∈(0,1)表示随机因子；Mu()表示随机地在取值范围内改变编码粒子中的一个分位，即变异操作；[0045]对于其中的个体认知和种群认知部分，采用交叉操作，定义运算符如式(22)和式(23)所示：[0046]7CN112632615A说　明　书4/15页[0047][0048]其中：r1,r2∈(0,1)表示随机因子；Cp(Ai(t+1),pi(t))和Cg(Bi(t+1),g(t))表示随机选择编码粒子Ai(t+1)和Bi(t+1)的两个随机分位，并与pi(t)和g(t)相同位置上的数值进行交叉；[0049]粒子的更新过程改进为式(25)：[0050][0051]进一步的，所述惯性权重w如式(26)所示：[0052][0053]其中：d(Xi(t),g(t))表示当前粒子Xi(t)对应的解与当前种群历史最优粒子g(t)对应的解的差异程度。[0054]进一步的，所述比较预算具体为对于三角模糊数定义三个比较值：[0055][0056]定义取大运算法则如下：若则否则若则否则若则否则[0057]本发明与现有技术相比具有以下有益效果：[0058]本发明综合考虑了混合云环境下数据布局特点、科学工作流任务之间的数据依赖关系、私有数据中心最大容量、云间带宽与波动，基于模糊理论将数据传输时间模糊化以适应实际网络环境，有效的对科学工作流数据进行布局。附图说明[0059]图1是本发明方法流程图；[0060]图2是本发明一实施例中不同算法在不同科学工作流下的平均模糊传输时间；[0061]图3是本发明一实施例中私有云数据中心个数不同时3种算法的平均数据模糊传输时间；[0062]图4是本发明一实施例中私有云数据中心容量不同时3种算法的平均数据模糊传输时间；[0063]图5是本发明一实施例中数据中心间带宽不同时3种算法的平均数据模糊传输时间。具体实施方式[0064]下面结合附图及实施例对本发明做进一步说明。[0065]请参照图1，本发明提供一种基于混合云环境的科学工作流数据布局方法，包括以下步骤：8CN112632615A说　明　书5/15页[0066]步骤S1:设定隐私数据集和数据中心最大容量条件，并初始化相关参数；[0067]步骤S2:以最小化数据模糊传输时间为目标，并考虑到数据中心的容量约束，在引入不确定性概念后，构建混合云环境下面向模糊时间优化的科学工作流数据布局模型；[0068]步骤S3:构建若干初始方案；[0069]步骤S4:构建粒子到数据布局结果的映射关系；[0070]步骤S5:基于改进的FGA‑DPSO的数据布局算法，获取最优方案。[0071]在本实施例中，混合云环境由一定数量的公有数据中心和一定数量的私有数据中心构成，其中私有数据中心容量一定，公有数据中心容量不设上限。定义混合云环境DC如式(1)所示：[0072][0073]其中：DCpub表示公有数据中心集合；DCpri表示私有数据中心集合；dci表示编号为i的数据中心；Vi表示数据中心的最大容量；Δi∈{0,1}表示数据中心dci的属性，若dci∈DCpub，则Δi＝0，dci只能存放公有数据，若dci∈DCpri，则Δi＝1，dci可以存放公有数据和隐私数据。另外，对于任意2个数据中心dci和dcj，bij表示它们之间的网络带宽值，设所有数据中心之间的网络带宽值已知，且会产生一定范围内的波动。[0074]在本实施例中，所述科学工作流由任务和数据集构成一个任务可能与多个数据集相关，一个数据集也可能与多个任务相关。[0075]任务之间存在数据依赖关系，即一个任务的输出数据集可能是其他任务的输入数据集，还存在时序上的先后关系，即只有当一个任务的前驱任务全部执行完毕，该任务才能执行，当所有任务执行完毕后，该科学工作流也随即结束；[0076]数据集可分为初始数据集和生成数据集两类：一个科学工作流的原始输入数据集称为初始数据集，运行过程中产生的数据集称为生成数据集。数据集还可分为隐私数据集和公有数据集两类：隐私数据集只能存放在固定的私有数据中心，以其为输入数据集的任务也必须调度到该数据中心上运行；公有数据集则无存储位置限制。[0077]综上所述，定义科学工作流为有向无环图G，如式(2)所示：[0078][0079]其中：T表示科学工作流中所有任务的集合；E表示科学工作流中不同任务之间的所有数据依赖关系的集合，DS表示科学工作流中所有数据集的集合；tc表示编号为c的任务；eij表示任务ti与任务tj之间的数据依赖关系，且ti是tj的直接先驱任务；dsl表示编号为l的数据集；Ii表示任务ti的输入数据集合；Oi表示任务ti的输出数据集合；DC(ti)表示任务9CN112632615A说　明　书6/15页ti的执行数据中心；vi表示数据集dsi的大小；gti表示生成数据集dsi的任务编号，其中初始数据集的gti为0；lci表示存放数据集dsi的数据中心编号。[0080]在本实施例中，基于模糊理论，引入三角模糊数来表示数据在数据中心之间的传输时间。对于每个独立的数据传输过程，映射＜dci,dsk,dcj＞表示数据集dsk从数据中心dci传输到数据中心dcj，该过程产生的数据传输时间如式(3)所示：[0081][0082]其中：和分别是该三角模糊数的下界元素与上界元素，其差值表示三角模糊数的模糊程度。当时，三角模糊数退化为一个清晰数，即实数。该三角模糊数的隶属函数表达式如式(4)所示：[0083][0084]隶属函数表示元素x属于该模糊区间的程度，当时，元素x完全属于该区间。[0085]在本实施例中，采用的模糊数的运算，具体包括如下：[0086](1)模型涉及到了模糊数之间的加法运算和比较运算。[0087]对于2个三角模糊数和有：[0088]①加法运算(用于计算模糊数据传输时间)[0089][0090]②比较运算(用于定性比较模糊完成时间的大小，从而选取合适的值)[0091]对于三角模糊数定义三个比较值：[0092][0093]定义取大运算法则如下：若则否则若则否则若则否则[0094](2)模型涉及到了模糊数与实数之间的加减运算、乘除运算和模糊化与去模糊化运算。[0095]对于1个三角模糊数和1个清晰数t，有：[0096]①加减运算[0097][0098][0099]②乘除运算(其中除法运算指用模糊数除以清晰数，该清晰数的值不为0)[0100]10CN112632615A说　明　书7/15页[0101][0102]③模糊化与去模糊化运算[0103]模糊化运算：对于清晰值s，有几种将其模糊化为的方法，如专家定义法、概率分布法和范围定义法等。本文采取如下方法，即：[0104][0105]其中δ1＜1,δ2＞1，且均为对应范围的随机数。[0106]去模糊化运算：去模糊化运算一般用于定量比较模糊数的大小，常常在对结果进行 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 时使用。基于模糊事件概率测度的概念，定义模糊数在均匀分布和比例分布下的均值和 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 差，其中比例分布适用于传输时间的不确定性问题。对于三角模糊数其均值和标准差由式(12)给出：[0107][0108]其中：表示模糊数的均值，反映了模糊数在概率测度下的最可能值；表示模糊数的标准差，反映了模糊数不确定性程度；表示标准差的所占权重。[0109]在本实施例中，数据布局策略的目的是在满足数据集隐私比例、任务执行顺序和数据中心容量约束的前提下，最小化数据模糊传输时间。由于只有当一个任务所需的所有数据集都在同一个数据中心时，该任务才能够执行，而向一个数据中心调度任务的时间远小于向该数据中心传输数据的传输时间，所以任务调度并非模型重点，模型主要关注数据布局策略。每个任务在执行前，总是选择将该任务调度至模糊传输时间最少的数据中心。整个数据布局策略定义如式(13)所示：[0110][0111]其中：M表示数据集合DS到数据中心集合DC的映射关系；{dci,dsk,dcj}为数据集dsk从数据中心dci传输到到数据中心dcj；为映射{dci,dsk,dcj}的模糊传输时间；11CN112632615A说　明　书8/15页表示数据布局过程中跨数据中心的数据传输所造成的总模糊时间；eijk＝{0,1}表示表示数据布局过程中是否存在数据集dsk从数据中心dci传输到数据中心dcj，若存在，则eijk为1，否则eijk为0。[0112]在本实施例中，以最小化数据模糊传输时间为目标并考虑到数据中心的容量约束，在引入不确定性概念后，混合云环境下面向模糊时间优化的科学工作流数据布局问题可形式化表示为式(14)：[0113][0114]其中uij＝{0,1}表示数据集dsj是否存放于数据中心dci，是则uij＝1，否则uij＝0。[0115]在本实施例中，基于粒子群优化算法(PSO,Particle Swarm Optimization)、遗传算法(GA,Genetic Algorithm)和模糊理论(Fuzzy Theory)，以最小化传输时间为目标，提出了FGA‑DPSO算法，具体的：[0116]传统的PSO算法是受到飞鸟集群活动的规律性启发而建立的一个简化模型，其利用个体对信息的共享使整个群体的运动在问题求解空间中产生从无序到有序的演化过程，最终获得最优解。每个优化问题的解都是搜索空间中的一只鸟，称为“粒子”。算法随机初始化出固定规模的粒子群，在之后的每次迭代中，粒子通过跟踪2个最优解来更新自己，分别是粒子自己所找到的最优解和整个种群所找到的最优解。粒子的更新包含2个方面：[0117]①速度更新如式(15)所示，[0118]Vi(t+1)＝wVi(t)+c1r1[pi(t)‑Xi(t)]+c2r2[g(t)‑Xi(t)]；   (15)[0119]②位置更新如式(16)所示，[0120]Xi(t+1)＝Xi(t)+Vi(t+1).[0121](16)[0122]适应度函数定义为：由于数据模糊传输时间是算法的优化目标，故直接将其定义为适应度函数值:[0123][0124]其中：F(S)表示数据布局策略S的适应度函数；表示粒子Xi的数据模糊传输时间。若布局在某个数据中心的数据集大小之和不超过该数据中心的最大容量，则该粒子为可行解，否则为不可行解。对于可行解与不可行解之间的取舍，直接选择可行解；对于可行解之间的取舍，选择适应度函数最小的粒子；对于不可行解之间的取舍，同样选择适应度函数最小的粒子，因为其在后续操作中更有可能变为可行解。[0125]粒子的编码方式需要满足完备性、非冗余性和健全性三个原则。本发明采取离散编码方法来构建n维粒子，其中n表示该科学工作流涉及到的数据集数量。粒子i在第t次迭代的位置Xi(t)的表达形式如式(18)所示：[0126][0127]X3(10)＝[1,2,4,3,2,1,3,4,2,1].   (19)[0128]式(19)为一个粒子编码示例，该粒子编号为3，当前迭代次数为10，数据集数量n为12CN112632615A说　明　书9/15页10，数据中心数量为4，下划线表示对应位置的数据集为隐私数据集，隐私数据集在后续的更新过程中的存储数据中心不可改动。[0129]本发明引入遗传算法中的交叉和变异操作到传统PSO算法中。需要注意，数据集中存在一定比例的隐私数据集，在粒子的更新过程中需要注意固定隐私数据集的存储数据中心不可改动。[0130]对于其中的惯性部分，引入遗传算法中的变异操作，定义运算符如式(20)：[0131][0132]其中：r0∈(0,1)表示随机因子；Mu()表示随机地在取值范围内改变编码粒子中的一个分位，即变异操作。需要注意：隐私数据集所在分位不可变异；不可行解对应的粒子应选取导致该粒子不可行的位置进行变异，即选择分位为超载的数据中心编号的位置进行变异。[0133]对于其中的个体认知和种群认知部分，引入遗传算法中的交叉操作，定义运算符如式(22)和式(23)所示：[0134][0135][0136]其中：r1,r2∈(0,1)表示随机因子；Cp(Ai(t+1),pi(t))和Cg(Bi(t+1),g(t))表示随机选择编码粒子Ai(t+1)和Bi(t+1)的两个随机分位，并与pi(t)和g(t)相同位置上的数值进行交叉。需要注意，交叉时不可改变隐私数据集的存放编号。[0137]综上所述，粒子的更新过程改进为式(25)：[0138][0139]在本实施例中，粒子到数据布局结果的映射具体为：[0140]输入：(G,DC,X)[0141]输出：(DS,DC,Map,)13CN112632615A说　明　书10/15页[0142][0143]在本实施例中，优选的，式(15)中的惯性权重w对原始PSO算法的收敛性和搜索能力有直接作用，能影响粒子在解空间搜索时的速度。本文设计了一种惯性权重w的定义方法，它能够按照当前粒子对应解的优劣程度，即与种群历史最优的粒子的差异程度，来自适应调整w的值，如式(26)所示：[0144][0145]其中：d(Xi(t),g(t))表示当前粒子Xi(t)对应的解与当前种群历史最优粒子g(t)对应的解的差异程度，即相同分位上不同取值的个数。在算法的运行初期，d(Xi(t),g(t))通常较大，w的值也相应较大，此时需要扩大粒子在解空间的搜索范围以寻找最优解，也避免过早地陷入局部最优；在算法的运行后期，d(Xi(t),g(t))通常较小，w的值也相应较小，14CN112632615A说　明　书11/15页此时需要缩小粒子的搜索范围并加速粒子在当前搜索范围内的速度，以更快的速度找到最优解。[0146]优选的，个体认知因子c1和种群认知因子c2采取梯度下降方法来定义。[0147]在本实施例中，所述FGA‑DPSO的伪代码，具体为[0148]输入：(G,DC)[0149]输出：Xbest[0150][0151][0152]实施例1：[0153]在本实施例中科学工作流模型来自对5个深入研究的不同科学领域，CyberShake,Epigenomics,Inspiral,Montage和Sipht。每个科学领域都有不同任务数量的科学工作流，每个科学工作流都有独特的任务结构、数据集数量以及计算需求，选取每个领域的中型(约50个任务)工作流进行实验。实验参数与环境设置如表1所示，其中参数意义见详见前文。[0154]表1实验环境与参数设置15CN112632615A说　明　书12/15页[0155][0156][0157]下列是除表1所示参数和环境外的额外设置。[0158]①最大容量设置：基准容量设置为3个私有云数据中心的最大容量均设置为基准容量的2.6倍。[0159]②数据中心之间带宽设置(单位：M/s)：dc1与{dc2,dc3,dc4}之间的带宽设置为{10,20,30}；dc2与{dc3,dc4}之间的带宽设置为{150,150}；dc3与{dc4}之间的带宽设置为{100}。[0160]③隐私数据集比例设置：由于不同工作流之间数据集数量的差异，领域为CyberShake,Epigenomics,Inspiral,Montage和Sipht的科学工作流的隐私数据集比例分别设置为[0.25,0.2,0.2,0.2,0.02]。[0161]④模糊参数设置：基于模糊理论，将数据传输时间T模糊化为对应的三角模糊数具体模糊化方法在前文已介绍，模糊参数设置为：σ1＝0.85,σ2＝1.2。[0162]本实施例中，为验证FGA‑DPSO的有效性，基于模糊理论，考虑科学工作流的应用场景和隐私设置、容量约束等限制条件，改进了传统数据布局中经常使用的随机算法(RA,Randomized Algorithm)和贪婪算法(GA,Greedy Algorithm)，称为条件模糊随机算法(CFRA,Constraint Fuzzy Randomized Algorithm)和条件模糊贪婪算法(CFGA,Constraint Fuzzy Greedy Algorithm)，其中条件是指在数据布局的过程中需满足数据中心的最大容量要求和数据集的隐私比例要求、模糊是指将数据传输时间模糊化，最后与本发明提出的FGA‑DPSO进行对比。16CN112632615A说　明　书13/15页[0163]CFRA算法流程[0164]①设定隐私数据集和数据中心最大容量条件，初始化相关参数，与FGA‑DPSO相同的参数对应的值保持一致；[0165]②依照FGA‑DPSO的离散编码方式生成满足条件的随机种群，种群包含一定数量的个体，每个个体代表数据布局的一个候选解；[0166]③定义适应度函数为该个体编码对应解的模糊传输时间，个体编码到数据布局策略的方式见算法1；[0167]④遍历计算每个个体的适应度值并与种群当前最优个体比较优劣性，若当前个体更优则更新种群最优个体；[0168]⑤遍历结束，输出最优个体及其对应的适应度值。[0169]CFGA算法流程[0170]①设定隐私数据集和数据中心最大容量条件，初始化相关参数，与FGA‑DPSO相同的参数对应的值保持一致；[0171]②设计数据布局方案。按照科学工作流的任务执行序列遍历每个任务所有尚未布局的数据集，进行判断：若当前任务已经布局，依据贪婪原则，将该数据集布局到当前任务的执行数据中心；若当前任务尚未布局但该任务存在已经布局的数据集，依据贪婪原则，将该数据集布局在与已布局数据集相同的数据中心；若当前任务尚未布局且该任务不存在已经布局的数据集，则随机布局该数据集到容量未满的数据中心；[0172]③计算当前布局方案的数据模糊传输时间。[0173]为了避免结果的随机性，对5种科学工作流在不同环境设置下分别进行10组独立重复实验，记录相关数据并取其平均值如表2，数据传输时间单位为s。[0174]表2不同算法在不同科学工作流下的平均模糊传输时间[0175][0176]为了使各算法之间的对比更加直观，后续不同实验环境下的对比结果对模糊数据传输时间进行了去模糊化处理，具体方法详见第2.1节定义4，其中设置为1。17CN112632615A说　明　书14/15页[0177]图3‑1为默认实验环境下5种科学工作流在不同执行算法下的模糊时间的去模糊化结果，其中科学工作流类型名称均用首字母表示，对该结果分析如下。[0178]①从算法来看，FGA‑DPSO算法的性能最优，其次是CFRA算法，而CFGA算法的性能较差。CFGA算法表现较差的原因主要是贪心类算法在执行过程中具有易陷入局部最优解的特点，从而忽视了全局；CFRA算法的总体表现优于CFGA，这是因为CFRA搜索解的空间更为广阔，不会陷入局部最优解，因此在随机次数较多时往往能得到较优解，但CFRA算法在每一次生成解时，没有根据当前染色体的性能进行自适应调整，所以性能较FGA‑DPSO差。[0179]②从工作流来看，相同算法在不同领域的科学工作流环境下的传输时间差异很大，这主要是由于虽然这些科学工作流包含的任务规模都是50左右，但是它们各自涉及到的数据集数量有很大差异，如CyberShake科学工作流使用数据集次数仅有70左右，而Sipht科学工作流使用数据集次数多达4000，这就造成了后者所需要的传输时间远大于前者。[0180]在真实环境中，混合云环境中的私有数据中心数量有时会发生变化，所以需要对FGA‑DPSO在私有数据中心数量变化时的表现进行实验对比。同时为了与之前结果对比，实验采取控制变量法，即仅改变私有云数据中心数量而不改变其他默认设置。实验测试了私有云数据中心的数量分别为{3,5,6,8,10}时3种不同算法的结果，其中新增私有数据中心与公有数据中心之间的带宽设置为20M/s，与其他私有数据中心之间的带宽设置为120M/s。[0181]针对私有数据中心数量变化的实验结果如图3‑2所示，对其分析如下：[0182]①从算法来看，FGA‑DPSO算法的性能最优，其次是CFRA算法，而CFGA算法的性能较差。原因与图3‑1相同，不再赘述。[0183]②从私有数据中心来看，随着其数量的增加，3种算法的传输时间呈上升趋势，这主要是由于随着私有数据中心数量的增加，依照隐私比例随机设置的隐私数据集分散且固定在更多的私有数据中心，涉及到隐私数据集的固定任务所需要运行的位置便越来越分散，从而导致传输时间上升。[0184]本发明模型中引入了私有数据中心最大容量作为约束条件，因此需要测试FGA‑DPSO算法对私有数据中心最大容量的敏感程度。实验采用控制变量法，选取具有代表性的CyberShake科学工作流，将私有数据中心最大容量相对于基准容量倍数分别调整为{2,2.6,3,5,8}，其余设置保持默认，结果见图3‑3。[0185]私有云数据中心容量不同时3种算法的平均数据模糊传输时间如图3‑3所示，分析如下。[0186]①随着私有数据中心最大容量的增加而数据中心之间的带宽保持不变，每个数据中心存放更多的数据集，造成每个任务所需要的数据集越来越集中在该任务所运行的数据中心，因此FGA‑DPSO算法的传输时间总体呈现出下降的趋势。[0187]②虽然传输时间总体呈下降趋势，但观察图像可以发现，传输时间下降最快是在数据最大中心容量相对于基准容量倍数从2倍到3倍之间，最慢是在数据最大中心容量相对于基准容量倍数从5倍到8倍之间。这是由于当数据中心最大容量相对较小时，数据中心的可用空间较小，数据集的布局位置受到的限制则较大，因此最大容量增加对传输时间影响显著；当数据中心最大容量相对较大时，每个数据中心均可存放大量的数据集，足够满足科学工作流的运行要求，因此最大容量增加对传输时间影响不大。[0188]由于本发明模型引入模糊理论主要是基于对数据中心之间带宽变化的考量，因此18CN112632615A说　明　书15/15页有必要验证算法在数据中心之间不同带宽下的表现。实验采用控制变量法，选取具有代表性的CyberShake科学工作流，将数据中心之间带宽相对于默认带宽的倍数分别为{0.5,0.8,1.5,3,5}，其余设置保持默认。[0189]数据中心间带宽不同时3种算法的平均数据模糊传输时间结果如图3‑4所示，随着数据中心之间的带宽增加，传输时间显著降低。实验表明了数据中心之间带宽的变化并不会显著影响算法对数据集的布局策略。[0190]以上所述仅为本发明的较佳实施例，凡依本发明申请专利范围所做的均等变化与修饰，皆应属本发明的涵盖范围。19CN112632615A说　明　书　附　图1/3页图1图220CN112632615A说　明　书　附　图2/3页图321CN112632615A说　明　书　附　图3/3页图4图522