1.一种支持跨节点计算任务抗毁接替的任务与资源匹配方法,包括如下步骤:S1.获取通信网络的网络参数;
S2.针对任意一个任务调度节点,计算得到拟调度任务与资源提供节点之间的优化匹配关系集合;
S3.步骤S2所述的任务调度节点,针对步骤S2获取的优化匹配关系集合中的每一对任务‑任务执行节点对,计算得到每一个任务执行节点的所有具备不小于对应任务所需要资源量的空闲资源的邻居节点集合;
S4.步骤S2所述的任务调度节点,针对步骤S3得到的邻居节点集合中的每一个候选备份节点,计算对应的链路连通频度预测值、链路吞吐能力预测值和备份资源复用率预测值;
S5.根据步骤S4得到的预测值,对步骤S2所述的任务调度节点所对应的所有任务执行节点,选择对应的抗毁接替节点;
S6.重复步骤S2~S5,直至为所有任务调度节点所对应的所有任务执行节点选定抗毁接替节点;
S7.更新通信网络的网络参数;
S8.重复步骤S2~S7,持续进行支持跨节点计算任务抗毁接替的任务与资源匹配。
2.根据权利要求1所述的支持跨节点计算任务抗毁接替的任务与资源匹配方法,其特征在于步骤S2所述的针对任意一个任务调度节点,计算得到拟调度任务与资源提供节点之间的优化匹配关系集合,具体为采用如下步骤得到优化匹配关系集合:A.将拟调度任务集合A中的所有元素以1~M进行标示;同时将资源提供节点集合B中的所有元素以1~N进行标示;
B.设置边‑权重二维矩阵WM×N,用于存储拟调度任务集合A和资源提供节点集合B之间的边及相应的权重;
C.初始化边‑权重二维矩阵WM×N中的所有元素值;
D.以二分图构建算法计算得到带权二分图G(A,B,WM×N);
E.以KM算法处理步骤D中得到的带权二分图G(A,B,WM×N),从而得到拟调度任务与资源提供节点之间的优化匹配关系集合。
3.根据权利要求2所述的支持跨节点计算任务抗毁接替的任务与资源匹配方法,其特征在于步骤D中所述的以二分图构建算法计算得到带权二分图G(A,B,WM×N),具体为采用如下步骤计算得到带权二分图G(A,B,WM×N):针对拟调度任务集合A中的每一个任务Am所需要的资源量am,以及资源提供节点集合B中的每一个节点Bn所能够提供的资源量bn,进行如下对比:若元素Am所需要的资源量am不大于节点Bn所能够提供的资源量bn,则令若元素Am所需要的资源量am大于节点Bn所能够提供的资源量bn,则令wmn=0;
对拟调度任务集合A中的每一个任务Am,均以上述步骤与资源提供节点集合B中的每一个节点Bn所能够提供的资源量bn进行对比,从而得到边‑权重二维矩阵WM×N中的每一个元素wmn,并与拟调度任务集合A和资源提供节点集合B一同构成带权二分图G(A,B,WM×N);
其中,m的取值为1,2,...,M,n的取值为1,2,...,N; 为向下取整函数。
4.根据权利要求3所述的支持跨节点计算任务抗毁接替的任务与资源匹配方法,其特征在于步骤E所述的以KM算法处理步骤D中得到的带权二分图G(A,B,WM×N),从而得到拟调度任务与资源提供节点之间的优化匹配关系集合,具体为采用如下步骤得到优化匹配关系集合:
E1.设置第一一维矩阵DAM用于存储拟调度任务集合A中元素的顶标值,其中dam为第一一维矩阵DAM中的第m个元素;
E2.设置第二一维矩阵DBN用于存储资源提供节点集合B中元素的顶标值,其中dbn为第二一维矩阵DBN中的第n个元素;
E3.针对第一一维矩阵DAM中的每一个元素dam,将dam的值初始化为任务Am在带权二分图G(A,B,WM×N)中权值最大的边的权值;
E4.针对第二一维矩阵DBN中的每一个元素dbn,将dbn的值初始化为0;
E5.根据第一一维矩阵DAM、第二一维矩阵DBN和带权二分图G(A,B,WM×N),采用相等子图构建算法得到相等子图G(A,B,EWM×N);
E6.根据步骤E5得到的相等子图G(A,B,EWM×N),采用匈牙利算法计算得到优化匹配关系集合FM或非增广路径的交错路径;
E7.对步骤E6采用的匈牙利算法计算得到的结果进行判断:若得到的结果为优化匹配关系集合FM,则直接输出优化匹配关系集合FM,步骤E结束;
若得到的结果为非增广路径的交错路径,则将非增广路径的交错路径中属于拟调度任务集合A的元素所对应的顶标值减去第一设定值,并将非增广路径的交错路径中属于资源提供节点集合B的元素所对应的顶标值增加第二设定值;
E8.对步骤E7得到的修改后的第一一维矩阵DAM和第二一维矩阵DBN中的所有元素进行判断:
若第一一维矩阵DAM中的所有元素值均大于0且第二一维矩阵DBN中的所有元素值均大于0,则返回步骤E5进行循环计算;
否则,则步骤E结束。
5.根据权利要求5所述的支持跨节点计算任务抗毁接替的任务与资源匹配方法,其特征在于步骤E5所述的采用相等子图构建算法得到相等子图G(A,B,EWM×N),具体为采用如下步骤计算得到相等子图G(A,B,EWM×N):E5‑1.初始化相等子图二维矩阵EWM×N中每个元素awmn;
E5‑2.针对拟调度任务集合A所对应的第一一维矩阵DAM中的每一个元素dam,以及资源提供节点集合B所对应的第二一维矩阵DBN的每一个元素dbn,进行如下判断:若dam+dbn的值与边‑权重二维矩阵WM×N中的对应元素wmn的值相等,则将相等子图二维矩阵EWM×N中的元素awmn的值设定为wmn的值;
否则,则保持awmn的值为初值;
对拟调度任务集合A所对应的第一一维矩阵DAM中的每一个元素dam,均以上述步骤与资源提供节点集合B所对应的第二一维矩阵DBN的每一个元素dbn进行判断,从而得到相等子图二维矩阵EWM×N中每个元素awmn,并与拟调度任务集合A和资源提供节点集合B一同构成相等子图G(A,B,EWM×N);
其中,m的取值为1,2,...,M,n的取值为1,2,...,N。
6.根据权利要求5所述的支持跨节点计算任务抗毁接替的任务与资源匹配方法,其特征在于步骤E6所述的根据步骤E5得到的相等子图G(A,B,EWM×N),采用匈牙利算法计算得到优化匹配关系集合FM或非增广路径的交错路径,具体为采用如下步骤计算得到优化匹配关系集合FM或非增广路径的交错路径:E6‑1.构建优化匹配关系集合FM、拟调度任务集合A所对应的A已匹配节点集合MA和资源提供节点集合B所对应的B已匹配节点集合MB,并均进行初始化;
E6‑2.针对拟调度任务集合A中每一个未匹配的节点mm,根据节点mm、A已匹配节点集合MA、B已匹配节点集合MB和相等子图G(A,B,EWM×N),采用增广或交错路径求解算法,得到一条以mm为起点的交错路径;
E6‑3.对步骤E6‑2所得到的交错路径,进行如下判断:若交错路径为增广路径,则将该路径上的偶数边从优化匹配关系集合FM中移除,同时将该路径上的奇数边加入优化匹配关系集合FM;
若交错路径为非增广路径,则直接返回该交错路径为非增广路径的交错路径。
7.根据权利要求6所述的支持跨节点计算任务抗毁接替的任务与资源匹配方法,其特征在于步骤E6‑2所述的采用增广或交错路径求解算法,得到一条以mm为起点的交错路径,具体为采用如下步骤计算得到交错路径:E6‑2‑1.构建增广路径队列ZP和交错路径队列JP,并进行初始化;
E6‑2‑2.将第一中间变量x设定为节点mm;
E6‑2‑3.针对资源提供节点集合B中的每一个节点n,令第二中间变量y设定为节点n,并进行判断:
若第二中间变量 且相等子图二维矩阵EWM×N中对应的元素ewx,y大于0,则将边x→y加入到增广路径队列ZP;
否则,则判断:若y∈MB且相等子图二维矩阵EWM×N中对应的元素ewx,y大于0,则将边x→y加入到交错路径队列JP,同时在优化匹配关系集合FM总找到y的匹配顶点m',并将第一中间变量x设定为节点m';
否则,则保持第一中间变量x为原值;
最后,返回交错路径队列JP。
8.根据权利要求7所述的支持跨节点计算任务抗毁接替的任务与资源匹配方法,其特征在于步骤S4所述的计算对应的链路连通频度预测值、链路吞吐能力预测值和备份资源复用率预测值,具体为采用如下步骤计算得到预测值:a.构建第一统计总和变量SUM、第二统计总和变量Δ、第一统计计数变量COU、第二统计计数变量Δ+和第三统计计数变量Δ‑,并初始化;
b.针对每一个候选备份节点k,计算节点k的历史链路连通频度值的总和值并赋予第一统计总和变量SUM,同时计算节点k的历史链路连通频度值的平均值并赋予变量c.针对每一个候选备份节点k,对节点k的每一个历史链路连通频度值进行如下判断:若历史链路连通频度值大于变量 则第二统计计数变量Δ+加1,否则第三统计计数变量Δ‑加1;同时将每一个历史链路连通频度值与变量 的差值进行平方后再求和,得到中间变量Δ1;
d.计算第二统计总和变量Δ为 其中COU为第一统计计数变量,取值为候选备份节点的总数;
e.再次进行判断:
若Δ+>Δ‑,则链路连通频度预测值 取值为若Δ+≤Δ‑,则链路连通频度预测值 取值为f.针对每一个候选备份节点k,计算节点k的历史链路吞吐能力值的总和值并赋予第一统计总和变量SUM,同时计算节点k的历史链路吞吐能力值的平均值并赋予变量g.针对每一个候选备份节点k,对节点k的每一个历史链路吞吐能力值进行如下判断:若历史链路吞吐能力值大于变量 则第二统计计数变量Δ+加1,否则第三统计计数变量Δ‑加1;同时将每一个历史链路吞吐能力值与变量 的差值进行平方后再求和,得到中间变量Δ1;
h.计算第二统计总和变量Δ为 其中COU为第一统计计数变量,取值为候选备份节点的总数;
i.再次进行判断:
若Δ+>Δ‑,则链路吞吐能力预测值 取值为若Δ+≤Δ‑,则链路吞吐能力预测值 取值为j.针对每一个候选备份节点k,计算节点k的历史备份资源复用率的总和值并赋予第一统计总和变量SUM,同时计算节点k的历史备份资源复用率的平均值并赋予变量k.针对每一个候选备份节点k,对节点k的每一个历史备份资源复用率进行如下判断:若历史备份资源复用率大于变量 则第二统计计数变量Δ+加1,否则第三统计计数变量Δ‑加1;同时将每一个历史备份资源复用率与变量 的差值进行平方后再求和,得到中间变量Δ1;
l.计算第二统计总和变量Δ为 其中COU为第一统计计数变量,取值为候选备份节点的总数;
m.再次进行判断:
若Δ+>Δ‑,则备份资源复用率预测值 取值为若Δ+≤Δ‑,则备份资源复用率预测值 取值为n.最后,返回链路连通频度预测值 链路吞吐能力预测值 和备份资源复用率预测值
9.根据权利要求8所述的支持跨节点计算任务抗毁接替的任务与资源匹配方法,其特征在于步骤S5所述的根据步骤S4得到的预测值,对步骤S2所述的任务调度节点所对应的所有任务执行节点,选择对应的抗毁接替节点,具体为采用如下步骤选择对应的抗毁接替节点:
(1)为任务执行节点j选出至多3个备份资源复用率预测值最低的候选邻居;
(2)在步骤(1)得到的候选邻居中,再选择最多2个具有最强链路吞吐能力预测值的候选邻居;
(3)在步骤(2)得到的邻居中,选择1个具有最好的链路连通频度预测值的邻居,作为任务执行节点j的抗毁接替节点。
10.根据权利要求9所述的支持跨节点计算任务抗毁接替的任务与资源匹配方法,其特征在于步骤S7所述的更新通信网络的网络参数,具体为采用如下步骤进行更新:
1)针对抗毁接替节点集合KH中的每一个备份节点k,完成如下动作:从优化匹配关系集合OM中找到备份节点k的服务对象j;
更新当前周期结束时的通信链路连通频度值 并将 加入到集合Ll中;具体为采用如下步骤进行更新当前周期结束时的通信链路连通频度值
1)‑1‑1.构建网络环境更新周期τn、第一计数变量N和第二计数变量N',并初始化;其中第二计数变量N'用于备份节点k与其服务对象j的连通计数;其中备份节点k所对应的服务对象j为任务执行节点j;
1)‑1‑2.针对当前任务调度与执行周期t内的每个网络环境更新周期τn,均进行如下操作:
获取在τn期间更新的任务执行节点j的坐标(xj,yj);
获取在τn期间更新的任务执行节点j所对应的备份节点k的坐标(xk,yk);
进行如下判断:
若 则第二计数变量N'增加1;否则,则保持第二计数变量N'不变;
第一计数变量N增加1;
1)‑1‑3.更新当前周期结束时的通信链路连通频度值 的值为更新当前周期结束时的通信链路吐吞能力值 并将 加入到集合Lc中;具体为采用如下步骤进行更新当前周期结束时的通信链路吐吞能力值
1)‑2‑1.对通信链路吐吞能力值 进行初始化;
1)‑2‑2.针对当前任务调度与执行周期t内的每个网络环境更新周期τn,均进行如下操作:
获取在τn期间更新的任务执行节点j的坐标(xj,yj);
获取在τn期间更新的任务执行节点j所对应的备份节点k的坐标(xk,yk);
计算中间距离变量
计算中间信道增益变量 其中gj,k为链路j→k的信道增益; 为任务执行节点j的最大发射功率;α为链路j→k的路径损耗指数;
计算中间带宽变量 其中W为链路j→k的带宽;N0为环境噪声功率密度;
更新当前周期结束时的通信链路吐吞能力值 为 其中δ为权值参数; 为上一周期结束时的通信链路吐吞能力值;
2)获取其他任务调度节点的位置坐标;
3)统计当前任务调度节点i的资源视图中提供备份资源的节点数;资源视图的定义为当前任务调度节点i所能探测到的节点;
4)根据步骤2)获取的位置坐标、当前任务调度节点i的资源视图和对应的提供备份资源的节点数,更新当前周期结束时的所有备份节点的资源复用率 并将 加入集合Lφ;其中k∈KH;具体为采用如下步骤进行更新:
4)‑1.构建簇团数K并初始化为任务调度节点i的资源视图中提供备份资源的节点数;
以提供备份资源的节点坐标为簇团的参考中心,构建坐标点集合ZXYk={(zx1,zy1),(zx2,zy2),...,(zxk,zyk)},其中(zxii,zyii)为ii个参考中心的坐标,ii的取值为1,2,...,K;构建二维矩阵MJK用于记录簇团成员关系,并初始化;将任务调度节点的坐标点集合记为RXYJ={(rx1,ry1),(rx2,ry2),...,(rxJ,ryJ)};
4)‑2.将j的值从1一直取值至J,并对每一个j的取值,均进行如下判断:若k的值等于算式 的值,则将二维矩阵MJK所对应的元素mjk的值设定1;
否则,则保持mjk为原值;
4)‑3.将k的值从1一直取值至K,并对每一个k的取值,均进行如下计算:和
4)‑4.将k的值从1一直取值至K,并对每一个k的取值,均再次进行如下操作:计算距离变量
若 则设定变量bk为较大设定值;
若 则设定变量bk为中等设定值;
否则,则设定变量bk为较小设定值;
其中, 为设定的距离下限阈值; 为设定的距离上限阈值;较大设定值、中等设定值和较小设定值为事先设定的值,且要求较大设定值>中等设定值>较小设定值;
4)‑5.将k的值从1一直取值至K,并对每一个k的取值,均再次进行如下操作:计算求和变量
若 则设定变量ck为小设定值;
若 则设定变量ck为中设定值;
否则,则设定设定变量ck为大设定值;
其中, 为设定的求和下限阈值; 为设定的求和上限阈值;大设定值、中设定值和小设定值为事先设定的值,且要求大设定值>中设定值>小设定值;
4)‑6.将k的值从1一直取值至K,并对每一个k的取值,均再次进行如下操作:计算资源复用率 φk为任务调度节点i的资源视图中第k个提供备份资源的节点备份资源复用率;
5)返回集合Ll、Lc和Lφ,完成通信网络的网络参数更新。