本发明公开了一种支持跨节点计算任务抗毁接替的任务与资源匹配方法，包括获取网络参数；对任意一个任务调度节点计算优化匹配关系集合；对优化匹配关系集合中的每一对任务‑任务执行节点对计算邻居节点集合；对邻居节点集合中的每一个候选备份节点计算链路连通频度预测值、链路吞吐能力预测值和备份资源复用率预测值；对任务调度节点所对应的所有任务执行节点选择抗毁接替节点；重复上述步骤直至为所有任务调度节点所对应的所有任务执行节点选定抗毁接替节点；更新通信网络的网络参数；重复上述步骤进行持续的任务与资源匹配。本发明保证了任务抗毁接替的需求，而且减少了空闲状态的资源数量，提高了资源利用率，可靠性高、稳定性好且适用性较广。
1.一种支持跨节点计算任务抗毁接替的任务与资源匹配方法，包括如下步骤：S1.获取通信网络的网络参数；
S2.针对任意一个任务调度节点，计算得到拟调度任务与资源提供节点之间的优化匹配关系集合；
S3.步骤S2所述的任务调度节点，针对步骤S2获取的优化匹配关系集合中的每一对任务‑任务执行节点对，计算得到每一个任务执行节点的所有具备不小于对应任务所需要资源量的空闲资源的邻居节点集合；
S4.步骤S2所述的任务调度节点，针对步骤S3得到的邻居节点集合中的每一个候选备份节点，计算对应的链路连通频度预测值、链路吞吐能力预测值和备份资源复用率预测值；
S5.根据步骤S4得到的预测值，对步骤S2所述的任务调度节点所对应的所有任务执行节点，选择对应的抗毁接替节点；
S6.重复步骤S2～S5，直至为所有任务调度节点所对应的所有任务执行节点选定抗毁接替节点；
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进行循环计算；
5.根据权利要求4所述的支持跨节点计算任务抗毁接替的任务与资源匹配方法，其特征在于步骤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的值；
对拟调度任务集合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‑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'；
8.根据权利要求7所述的支持跨节点计算任务抗毁接替的任务与资源匹配方法，其特征在于步骤S4所述的计算对应的链路连通频度预测值、链路吞吐能力预测值和备份资源复用率预测值，具体为采用如下步骤计算得到预测值：a.构建第一统计总和变量SUM、第二统计总和变量Δ、第一统计计数变量COU、第二统计计数变量Δ+和第三统计计数变量Δ‑，并初始化；
b.针对每一个候选备份节点k，计算节点k的历史链路连通频度值的总和值并赋予第一统计总和变量SUM，同时计算节点k的历史链路连通频度值的平均值并赋予变量c.针对每一个候选备份节点k，对节点k的每一个历史链路连通频度值进行如下判断：若历史链路连通频度值大于变量 则第二统计计数变量Δ+加1，否则第三统计计数变量Δ‑加1；同时将每一个历史链路连通频度值与变量 的差值进行平方后再求和，得到中间变量Δ1；
d.计算第二统计总和变量Δ为 其中COU为第一统计计数变量，取值为候选备份节点的总数；
若Δ+＞Δ‑，则链路连通频度预测值 取值为若Δ+≤Δ‑，则链路连通频度预测值 取值为f.针对每一个候选备份节点k，计算节点k的历史链路吞吐能力值的总和值并赋予第一统计总和变量SUM，同时计算节点k的历史链路吞吐能力值的平均值并赋予变量g.针对每一个候选备份节点k，对节点k的每一个历史链路吞吐能力值进行如下判断：若历史链路吞吐能力值大于变量 则第二统计计数变量Δ+加1，否则第三统计计数变量Δ‑加1；同时将每一个历史链路吞吐能力值与变量 的差值进行平方后再求和，得到中间变量Δ1；
h.计算第二统计总和变量Δ为 其中COU为第一统计计数变量，取值为候选备份节点的总数；
若Δ+＞Δ‑，则链路吞吐能力预测值 取值为若Δ+≤Δ‑，则链路吞吐能力预测值 取值为j.针对每一个候选备份节点k，计算节点k的历史备份资源复用率的总和值并赋予第一统计总和变量SUM，同时计算节点k的历史备份资源复用率的平均值并赋予变量k.针对每一个候选备份节点k，对节点k的每一个历史备份资源复用率进行如下判断：若历史备份资源复用率大于变量 则第二统计计数变量Δ+加1，否则第三统计计数变量Δ‑加1；同时将每一个历史备份资源复用率与变量 的差值进行平方后再求和，得到中间变量Δ1；
l.计算第二统计总和变量Δ为 其中COU为第一统计计数变量，取值为候选备份节点的总数；
若Δ+＞Δ‑，则备份资源复用率预测值 取值为若Δ+≤Δ‑，则备份资源复用率预测值 取值为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'不变；
1)‑1‑3.更新当前周期结束时的通信链路连通频度值 的值为更新当前周期结束时的通信链路吐吞能力值 并将 加入到集合Lc中；具体为采用如下步骤进行更新当前周期结束时的通信链路吐吞能力值
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为环境噪声功率密度；
更新当前周期结束时的通信链路吐吞能力值 为 其中δ为权值参数； 为上一周期结束时的通信链路吐吞能力值；
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；
4)‑3.将k的值从1一直取值至K，并对每一个k的取值，均进行如下计算：和
4)‑4.将k的值从1一直取值至K，并对每一个k的取值，均再次进行如下操作：计算距离变量
其中， 为设定的距离下限阈值； 为设定的距离上限阈值；较大设定值、中等设定值和较小设定值为事先设定的值，且要求较大设定值>中等设定值>较小设定值；
4)‑5.将k的值从1一直取值至K，并对每一个k的取值，均再次进行如下操作：计算求和变量
其中， 为设定的求和下限阈值； 为设定的求和上限阈值；大设定值、中设定值和小设定值为事先设定的值，且要求大设定值>中设定值>小设定值；
4)‑6.将k的值从1一直取值至K，并对每一个k的取值，均再次进行如下操作：计算资源复用率 φk为任务调度节点i的资源视图中第k个提供备份资源的节点备份资源复用率；
5)返回集合Ll、Lc和Lφ，完成通信网络的网络参数更新。
支持跨节点计算任务抗毁接替的任务与资源匹配方法
技术领域
[0001] 本发明属于分散计算领域，具体涉及一种支持跨节点计算任务抗毁接替的任务与资源匹配方法。
背景技术
[0002] 随着经济技术的发展，人们对于通信质量的要求越来越高。因此，如何保证通信系统在恶劣环境下的通信质量，一直是通信领域研究的重中之重。
[0003] 在恶劣无线通信环境下，特别是面向网络吞吐量严重受限而用户应用又要求具有近乎于实时响应的环境下，为解决计算任务复杂多变与节点资源严重受限的矛盾，基于分
散计算的应用模式是一种值得探究的解决方案。在分散计算环境下，为保障已被调度的任
务能在恶劣的通信环境(比如战场环境，或者严重自然灾害环境等)下生存下来，并顺利完
成对应的应用和通信工作，需要研究跨节点计算任务的抗毁接替模式。为实现任务在计算
节点间的抗毁接替，原则上具有与任务匹配算力的分散计算节点应多于1个，且节点之间互
为对等关系，并具有互为备份的能力。但是，这里的互为备份能力并不能依赖传统的静态固
化备份机制，而应探讨弹性可扩展的动态备份机制、支持跨节点计算任务抗毁接替的子任
务分配与资源匹配方法。
[0004] 但是，目前尚未有一种可靠、稳定且适用性较广的支持跨节点计算任务抗毁接替的任务与资源匹配方法。
发明内容
[0005] 本发明的目的在于提供一种可靠性高、稳定性好且适用性较广的支持跨节点计算任务抗毁接替的任务与资源匹配方法。
[0006] 本发明提供的这种支持跨节点计算任务抗毁接替的任务与资源匹配方法，包括如下步骤：
[0007] S1.获取通信网络的网络参数；
[0008] S2.针对任意一个任务调度节点，计算得到拟调度任务与资源提供节点之间的优化匹配关系集合；
[0009] S3.步骤S2所述的任务调度节点，针对步骤S2获取的优化匹配关系集合中的每一对任务‑任务执行节点对，计算得到每一个任务执行节点的所有具备不小于对应任务所需
要资源量的空闲资源的邻居节点集合；
[0010] S4.步骤S2所述的任务调度节点，针对步骤S3得到的邻居节点集合中的每一个候选备份节点，计算对应的链路连通频度预测值、链路吞吐能力预测值和备份资源复用率预
测值；
[0011] S5.根据步骤S4得到的预测值，对步骤S2所述的任务调度节点所对应的所有任务执行节点，选择对应的抗毁接替节点；
[0012] S6.重复步骤S2～S5，直至为所有任务调度节点所对应的所有任务执行节点选定抗毁接替节点；
[0013] S7.更新通信网络的网络参数；
[0014] S8.重复步骤S2～S7，持续进行支持跨节点计算任务抗毁接替的任务与资源匹配。
[0015] 步骤S2所述的针对任意一个任务调度节点，计算得到拟调度任务与资源提供节点之间的优化匹配关系集合，具体为采用如下步骤得到优化匹配关系集合：
[0016] A.将拟调度任务集合A中的所有元素以1～M进行标示；同时将资源提供节点集合B中的所有元素以1～N进行标示；
[0017] B.设置边‑权重二维矩阵WM×N，用于存储拟调度任务集合A和资源提供节点集合B之间的边及相应的权重；
[0018] C.初始化边‑权重二维矩阵WM×N中的所有元素值；
[0019] D.以二分图构建算法计算得到带权二分图G(A,B,WM×N)；
[0020] E.以KM算法处理步骤D中得到的带权二分图G(A,B,WM×N)，从而得到拟调度任务与资源提供节点之间的优化匹配关系集合。
[0021] 步骤D中所述的以二分图构建算法计算得到带权二分图G(A,B,WM×N)，具体为采用如下步骤计算得到带权二分图G(A,B,WM×N)：
[0022] 针对拟调度任务集合A中的每一个任务Am所需要的资源量am，以及资源提供节点集合B中的每一个节点Bn所能够提供的资源量bn，进行如下对比：
[0023] 若元素Am所需要的资源量am不大于节点Bn所能够提供的资源量bn，则令
[0024] 若元素Am所需要的资源量am大于节点Bn所能够提供的资源量bn，则令wmn＝0；
[0025] 对拟调度任务集合A中的每一个任务Am，均以上述步骤与资源提供节点集合B中的每一个节点Bn所能够提供的资源量bn进行对比，从而得到边‑权重二维矩阵WM×N中的每一个
元素wmn，并与拟调度任务集合A和资源提供节点集合B一同构成带权二分图G(A,B,WM×N)；
[0026] 其中，m的取值为1,2,...,M，n的取值为1,2,...,N； 为向下取整函数。
[0027] 步骤E所述的以KM算法处理步骤D中得到的带权二分图G(A,B,WM×N)，从而得到拟调度任务与资源提供节点之间的优化匹配关系集合，具体为采用如下步骤得到优化匹配关系
集合：
[0028] E1.设置第一一维矩阵DAM用于存储拟调度任务集合A中元素的顶标值，其中dam为第一一维矩阵DAM中的第m个元素；
[0029] E2.设置第二一维矩阵DBN用于存储资源提供节点集合B中元素的顶标值，其中dbn为第二一维矩阵DBN中的第n个元素；
[0030] E3.针对第一一维矩阵DAM中的每一个元素dam，将dam的值初始化为任务Am在带权二分图G(A,B,WM×N)中权值最大的边的权值；
[0031] E4.针对第二一维矩阵DBN中的每一个元素dbn，将dbn的值初始化为0；
[0032] E5.根据第一一维矩阵DAM、第二一维矩阵DBN和带权二分图G(A,B,WM×N)，采用相等子图构建算法得到相等子图G(A,B,EWM×N)；
[0033] E6.根据步骤E5得到的相等子图G(A,B,EWM×N)，采用匈牙利算法计算得到优化匹配关系集合FM或非增广路径的交错路径；
[0034] E7.对步骤E6采用的匈牙利算法计算得到的结果进行判断：
[0035] 若得到的结果为优化匹配关系集合FM，则直接输出优化匹配关系集合FM，步骤E结束；
[0036] 若得到的结果为非增广路径的交错路径，则将非增广路径的交错路径中属于拟调度任务集合A的元素所对应的顶标值减去第一设定值，并将非增广路径的交错路径中属于
资源提供节点集合B的元素所对应的顶标值增加第二设定值；
[0037] E8.对步骤E7得到的修改后的第一一维矩阵DAM和第二一维矩阵DBN中的所有元素进行判断：
[0038] 若第一一维矩阵DAM中的所有元素值均大于0且第二一维矩阵DBN中的所有元素值均大于0，则返回步骤E5进行循环计算；
[0039] 否则，则步骤E结束。
[0040] 步骤E5所述的采用相等子图构建算法得到相等子图G(A,B,EWM×N)，具体为采用如下步骤计算得到相等子图G(A,B,EWM×N)：
[0041] E5‑1.初始化相等子图二维矩阵EWM×N中每个元素awmn；
[0042] E5‑2.针对拟调度任务集合A所对应的第一一维矩阵DAM中的每一个元素dam，以及资源提供节点集合B所对应的第二一维矩阵DBN的每一个元素dbn，进行如下判断：
[0043] 若dam+dbn的值与边‑权重二维矩阵WM×N中的对应元素wmn的值相等，则将相等子图二维矩阵EWM×N中的元素awmn的值设定为wmn的值；
[0044] 否则，则保持awmn的值为初值；
[0045] 对拟调度任务集合A所对应的第一一维矩阵DAM中的每一个元素dam，均以上述步骤与资源提供节点集合B所对应的第二一维矩阵DBN的每一个元素dbn进行判断，从而得到相等
子图二维矩阵EWM×N中每个元素awmn，并与拟调度任务集合A和资源提供节点集合B一同构成
相等子图G(A,B,EWM×N)；
[0046] 其中，m的取值为1,2,...,M，n的取值为1,2,...,N。
[0047] 步骤E6所述的根据步骤E5得到的相等子图G(A,B,EWM×N)，采用匈牙利算法计算得到优化匹配关系集合FM或非增广路径的交错路径，具体为采用如下步骤计算得到优化匹配
关系集合FM或非增广路径的交错路径：
[0048] E6‑1.构建优化匹配关系集合FM、拟调度任务集合A所对应的A已匹配节点集合MA和资源提供节点集合B所对应的B已匹配节点集合MB，并均进行初始化；
[0049] E6‑2.针对拟调度任务集合A中每一个未匹配的节点mm，根据节点mm、A已匹配节点集合MA、B已匹配节点集合MB和相等子图G(A,B,EWM×N)，采用增广或交错路径求解算法，得到
一条以mm为起点的交错路径；
[0050] E6‑3.对步骤E6‑2所得到的交错路径，进行如下判断：
[0051] 若交错路径为增广路径，则将该路径上的偶数边从优化匹配关系集合FM中移除，同时将该路径上的奇数边加入优化匹配关系集合FM；
[0052] 若交错路径为非增广路径，则直接返回该交错路径为非增广路径的交错路径。
[0053] 步骤E6‑2所述的采用增广或交错路径求解算法，得到一条以mm为起点的交错路径，具体为采用如下步骤计算得到交错路径：
[0054] E6‑2‑1.构建增广路径队列ZP和交错路径队列JP，并进行初始化；
[0055] E6‑2‑2.将第一中间变量x设定为节点mm；
[0056] E6‑2‑3.针对资源提供节点集合B中的每一个节点n，令第二中间变量y设定为节点n，并进行判断：
[0057] 若第二中间变量 且相等子图二维矩阵EWM×N中对应的元素ewx,y大于0，则将边x→y加入到增广路径队列ZP；
[0058] 否则，则判断：若y∈MB且相等子图二维矩阵EWM×N中对应的元素ewx,y大于0，则将边x→y加入到交错路径队列JP，同时在优化匹配关系集合FM总找到y的匹配顶点m'，并将第一
中间变量x设定为节点m'；
[0059] 否则，则保持第一中间变量x为原值；
[0060] 最后，返回交错路径队列JP。
[0061] 步骤S4所述的计算对应的链路连通频度预测值、链路吞吐能力预测值和备份资源复用率预测值，具体为采用如下步骤计算得到预测值：
[0062] a.构建第一统计总和变量SUM、第二统计总和变量Δ、第一统计计数变量COU、第二统计计数变量Δ+和第三统计计数变量Δ‑，并初始化；
[0063] b.针对每一个候选备份节点k，计算节点k的历史链路连通频度值的总和值并赋予第一统计总和变量SUM，同时计算节点k的历史链路连通频度值的平均值并赋予变量
[0064] c.针对每一个候选备份节点k，对节点k的每一个历史链路连通频度值进行如下判断：
[0065] 若历史链路连通频度值大于变量 则第二统计计数变量Δ+加1，否则第三统计计数变量Δ‑加1；同时将每一个历史链路连通频度值与变量 的差值进行平方后再求和，
得到中间变量Δ1；
[0066] d.计算第二统计总和变量Δ为 其中COU为第一统计计数变量，取值为候选备份节点的总数；
[0067] e.再次进行判断：
[0068] 若Δ+＞Δ‑，则链路连通频度预测值 取值为
[0069] 若Δ+≤Δ‑，则链路连通频度预测值 取值为
[0070] f.针对每一个候选备份节点k，计算节点k的历史链路吞吐能力值的总和值并赋予第一统计总和变量SUM，同时计算节点k的历史链路吞吐能力值的平均值并赋予变量
[0071] g.针对每一个候选备份节点k，对节点k的每一个历史链路吞吐能力值进行如下判断：
[0072] 若历史链路吞吐能力值大于变量 则第二统计计数变量Δ+加1，否则第三统计计数变量Δ‑加1；同时将每一个历史链路吞吐能力值与变量 的差值进行平方后再求和，
得到中间变量Δ1；
[0073] h.计算第二统计总和变量Δ为 其中COU为第一统计计数变量，取值为候选备份节点的总数；
[0074] i.再次进行判断：
[0075] 若Δ+＞Δ‑，则链路吞吐能力预测值 取值为
[0076] 若Δ+≤Δ‑，则链路吞吐能力预测值 取值为
[0077] j.针对每一个候选备份节点k，计算节点k的历史备份资源复用率的总和值并赋予第一统计总和变量SUM，同时计算节点k的历史备份资源复用率的平均值并赋予变量
[0078] k.针对每一个候选备份节点k，对节点k的每一个历史备份资源复用率进行如下判断：
[0079] 若历史备份资源复用率大于变量 则第二统计计数变量Δ+加1，否则第三统计计数变量Δ‑加1；同时将每一个历史备份资源复用率与变量 的差值进行平方后再求和，
得到中间变量Δ1；
[0080] l.计算第二统计总和变量Δ为 其中COU为第一统计计数变量，取值为候选备份节点的总数；
[0081] m.再次进行判断：
[0082] 若Δ+＞Δ‑，则备份资源复用率预测值 取值为
[0083] 若Δ+≤Δ‑，则备份资源复用率预测值 取值为
[0084] n.最后，返回链路连通频度预测值 链路吞吐能力预测值 和备份资源复用率预测值
[0085] 步骤S5所述的根据步骤S4得到的预测值，对步骤S2所述的任务调度节点所对应的所有任务执行节点，选择对应的抗毁接替节点，具体为采用如下步骤选择对应的抗毁接替
节点：
[0086] (1)为任务执行节点j选出至多3个备份资源复用率预测值最低的候选邻居；
[0087] (2)在步骤(1)得到的候选邻居中，再选择最多2个具有最强链路吞吐能力预测值的候选邻居；
[0088] (3)在步骤(2)得到的邻居中，选择1个具有最好的链路连通频度预测值的邻居，作为任务执行节点j的抗毁接替节点。
[0089] 步骤S7所述的更新通信网络的网络参数，具体为采用如下步骤进行更新：
[0090] 1)针对抗毁接替节点集合KH中的每一个备份节点k，完成如下动作：
[0091] 从优化匹配关系集合OM中找到备份节点k的服务对象j；
[0092] 更新当前周期结束时的通信链路连通频度值 并将 加入到集合Ll中；
[0093] 更新当前周期结束时的通信链路吐吞能力值 并将 加入到集合Lc中；
[0094] 2)获取其他任务调度节点的位置坐标；
[0095] 3)统计当前任务调度节点i的资源视图中提供备份资源的节点数；资源视图的定义为当前任务调度节点i所能探测到的节点集合；
[0096] 4)根据步骤2)获取的位置坐标、当前任务调度节点i的资源视图和对应的提供备份资源的节点数，更新当前周期结束时的所有备份节点的资源复用率 并将 加入集合
Lφ；其中k∈KH
[0097] 5)返回集合Ll、Lc和Lφ，完成通信网络的网络参数更新。
[0098] 步骤1)所述的更新当前周期结束时的通信链路连通频度值 具体为采用如下步骤进行更新：
[0099] 1)‑1‑1.构建网络环境更新周期τn、第一计数变量N和第二计数变量N'，并初始化；其中第二计数变量N'用于备份节点k与其服务对象j的连通计数；其中备份节点k所对应的
服务对象j为任务执行节点j；
[0100] 1)‑1‑2.针对当前任务调度与执行周期t内的每个网络环境更新周期τn，均进行如下操作：
[0101] 获取在τn期间更新的任务执行节点j的坐标(xj,yj)；
[0102] 获取在τn期间更新的任务执行节点j所对应的备份节点k的坐标(xk,yk)；
[0103] 进行如下判断：
[0104] 若 则第二计数变量N'增加1；否则，则保持第二计数变量N'不变；
[0105] 第一计数变量N增加1；
[0106] 1)‑1‑3.更新当前周期结束时的通信链路连通频度值 的值为
[0107] 步骤1)所述的更新当前周期结束时的通信链路吐吞能力值 具体为采用如下步骤进行更新：
[0108] 1)‑2‑1.对通信链路吐吞能力值 进行初始化；
[0109] 1)‑2‑2.针对当前任务调度与执行周期t内的每个网络环境更新周期τn，均进行如下操作：
[0110] 获取在τn期间更新的任务执行节点j的坐标(xj,yj)；
[0111] 获取在τn期间更新的任务执行节点j所对应的备份节点k的坐标(xk,yk)；
[0112] 计算中间距离变量
[0113] 计算中间信道增益变量 其中gj,k为链路j→k的信道增益；为任务执行节点j的最大发射功率；α为链路j→k的路径损耗指数；
[0114] 计算中间带宽变量 其中W为链路j→k的带宽；N0为环境噪声功率密度；
[0115] 更新当前周期结束时的通信链路吐吞能力值 为其中δ为权值参数； 为上一周期结束时的通信链路吐吞能力值。
[0116] 步骤4)所述的更新当前周期结束时的所有备份节点的资源复用率 具体为采用如下步骤进行更新：
[0117] 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)}；
[0118] 4)‑2.将j的值从1一直取值至J，并对每一个j的取值，均进行如下判断：
[0119] 若k的值等于算式 的值，则将二维矩阵MJK所对应的元素mjk的值设定1；
[0120] 否则，则保持mjk为原值；
[0121] 4)‑3.将k的值从1一直取值至K，并对每一个k的取值，均进行如下计算：和
[0122] 4)‑4.将k的值从1一直取值至K，并对每一个k的取值，均再次进行如下操作：
[0123] 计算距离变量
[0124] 若 则设定变量bk为较大设定值；
[0125] 若 则设定变量bk为中等设定值；
[0126] 否则，则设定变量bk为较小设定值；
[0127] 其中， 为设定的距离下限阈值； 为设定的距离上限阈值；较大设定值、中等设定值和较小设定值为事先设定的值，且要求较大设定值>中等设定值>较小设定值；
[0128] 4)‑5.将k的值从1一直取值至K，并对每一个k的取值，均再次进行如下操作：
[0129] 计算求和变量
[0130] 若 则设定变量ck为小设定值；
[0131] 若 则设定变量ck为中设定值；
[0132] 否则，则设定设定变量ck为大设定值；
[0133] 其中， 为设定的求和下限阈值； 为设定的求和上限阈值；大设定值、中设定值和小设定值为事先设定的值，且要求大设定值>中设定值>小设定值；
[0134] 4)‑6.将k的值从1一直取值至K，并对每一个k的取值，均再次进行如下操作：计算资源复用率 φk为任务调度节点i的资源视图中第k个提供备份资源
的节点备份资源复用率。
[0135] 本发明提供的这种支持跨节点计算任务抗毁接替的任务与资源匹配方法，通过创新性的网络资源计算和分配，不仅保证了任务抗毁接替的需求，而且能够较好的减少空闲
状态的资源数量，从而较好的提高了资源利用率，而且本发明方法可靠性高、稳定性好且适
用性较广。
附图说明
[0136] 图1为典型的子任务分配与资源匹配示意图。
[0137] 图2为本发明方法的方法流程示意图。
[0138] 图3为本发明方法的实施例的测试环境示例图。
[0139] 图4为本发明方法与对比方法在不同任务调度周期下的性能表现对比示意图。
[0140] 图5为本发明方法在不同任务调度数情况下的性能随任务调度周期的变化情况示意图。
具体实施方式
[0141] 本发明提出一种支持跨节点计算任务抗毁接替的任务分配与资源匹配方案。末端为避免因任务执行节点损毁造成的任务执行失败，除了需要为每一个被调度执行的任务分
配给一个主执行节点外，还应选择一个或多个合适的分散计算节点进行该任务的预置。但
这与传统的“一主一备”或“一主多备”的资源分配模式不同，这种预置只是将该任务相关的
代码和执行环境的个性化要求进行预置，且以资源占用量尽量最小化的状态存在，在实际
接替之前重要资源(如CPU和内存等)并非被占用来仅做静态的空闲待命。因此，本发明的目
标是在确保计算任务抗毁接替需求的前提下，尽量减少空闲状态的资源数量，以尽量提高
资源利用率。
[0142] 节点间相互周期性地向其相邻节点广播其资源状态信息，因此，有任务发布需求的节点在了解其周围区域节点的资源状态的基础上，执行任务调度操作。为满足计算任务
抗毁接替的要求，假定系统可以已经确定了合适的实施调度的任务总量，以便确保在预留
合理备份资源的前提下，实施任务的优化调度。图1展示了任务分配与资源匹配示例。任务
当前使用资源量是确定其备份资源量的重要依据。在条件允许情况下，备份资源量应不小
于当前使用资源量。实际上，资源量通常严重受限，因此，备份资源不能简单地认为仅供抗
毁接替时使用，而应视情况被合理调度以提高资源利用率，前提是抗毁接替功能被置为最
高优先级。依据其是否承担备份任务，以及在承担备份任务中的层级关系，将资源进行级别
划分，以便于对各种级别资源进行合理调度使用。如图1所示，2级备份资源的使用需要依赖
1级备份资源首先被使用，因此，实际被使用的概率会低于1级备份资源。从而，复用2级备份
资源的任务面临被退出的风险会小于复用1级备份资源的任务。
[0143] 针对提供备份资源的计算节点也可以进行抗毁接替的优先级划分。依据每个提供备份资源的计算节点的历史表现预测其未来表现，从而给其标定优先级，其优先级高的，在
抗毁接替需求出现时，优先选用。
[0144] 每个提供备份资源的节点都周期性向任务调度节点汇报其备份资源的使用状态信息。该类状态信息包括提供备份资源的节点与相应的拟接替任务执行节点的相对位置、
通信链路状况、当前备份资源被复用状况等。基于这类状态信息，任务调度节点为每个提供
备份资源的节点计算如下度量值：链路连通频度、平均通信链路吞吐能力、备份资源复用
率。
[0145] 针对链路连通频度的估算如下：在相对位置信息的汇报次数中，互相位于物理通信范围内的次数与汇报总次数之比；针对平均通信链路吞吐能力的估算如下：依据每一段
时间内汇报的通信链路状况，使用香农定理估算最大发射功率下的数据传输率，再对该段
时间内的历史值进行加权合成；针对备份资源复用率的估算如下：基于k‑means聚类算法
(KM算法)，以提供备份资源的节点数量为参数k，以提供备份资源的节点坐标为初始聚类中
心，以任务分配节点到聚类中心的距离为度量值进行聚类，产生k个簇团。以簇团内提供备
份资源的节点位置离中心点的距离值划分为“近”、“中”、“远”三级，以簇团内任务分配节点
数量划分为“小”、“中”、“大”三级，再以这两个维度综合衡量提供备份资源的节点的潜在资
源复用负载。通过组合可以构成9种潜在资源复用负载等级，例如，若距离聚类后的中心为
“近”的提供备份资源的节点所在的簇团的任务分配节点数量属于“大”，则该提供备份资源
的节点的潜在资源复用负载可能最重。
[0146] 上述三种度量值可以分别表示为链路连通频度、平均通信链路吞吐能力、备份资源复用率时序图。依据这些时序图，可以确定承担抗毁接替任务的备份资源选择的优先级。
[0147] 如图2所示为本发明方法的方法流程示意图：本发明提供的这种支持跨节点计算任务抗毁接替的任务与资源匹配方法，包括如下步骤：
[0148] S1.获取通信网络的网络参数；
[0149] S2.针对任意一个任务调度节点，计算得到拟调度任务与资源提供节点之间的优化匹配关系集合；具体为采用如下步骤得到优化匹配关系集合：
[0150] A.将拟调度任务集合A中的所有元素以1～M进行标示；同时将资源提供节点集合B中的所有元素以1～N进行标示；
[0151] B.设置边‑权重二维矩阵WM×N，用于存储拟调度任务集合A和资源提供节点集合B之间的边及相应的权重；
[0152] C.初始化边‑权重二维矩阵WM×N中的所有元素值；
[0153] D.以二分图构建算法计算得到带权二分图G(A,B,WM×N)；
[0154] E.以KM算法处理步骤D中得到的带权二分图G(A,B,WM×N)，从而得到拟调度任务与资源提供节点之间的优化匹配关系集合；
[0155] 步骤A～步骤E部分的伪代码如下：
[0156]
[0157]
[0158] 在具体实施时：
[0159] 采用如下步骤计算得到带权二分图G(A,B,WM×N)：
[0160] 针对拟调度任务集合A中的每一个任务Am所需要的资源量am，以及资源提供节点集合B中的每一个节点Bn所能够提供的资源量bn，进行如下对比：
[0161] 若元素Am所需要的资源量am不大于节点Bn所能够提供的资源量bn，则令
[0162] 否则，则令wmn＝0；
[0163] 对拟调度任务集合A中的每一个任务Am，均以上述步骤与资源提供节点集合B中的每一个节点Bn所能够提供的资源量bn进行对比，从而得到边‑权重二维矩阵WM×N中的每一个
元素wmn，并与拟调度任务集合A和资源提供节点集合B一同构成带权二分图G(A,B,WM×N)；
[0164] 其中，m的取值为1,2,...,M，n的取值为1,2,...,N； 为向下取整函数；
[0165] 该部分的伪代码如下：
[0166]
[0167]
[0168] 采用如下步骤得到优化匹配关系集合：
[0169] E1.设置第一一维矩阵DAM用于存储拟调度任务集合A中元素的顶标值，其中dam为第一一维矩阵DAM中的第m个元素；
[0170] E2.设置第二一维矩阵DBN用于存储资源提供节点集合B中元素的顶标值，其中dbn为第二一维矩阵DBN中的第n个元素；
[0171] E3.针对第一一维矩阵DAM中的每一个元素dam，将dam的值初始化为任务Am在带权二分图G(A,B,WM×N)中权值最大的边的权值；
[0172] E4.针对第二一维矩阵DBN中的每一个元素dbn，将dbn的值初始化为0；
[0173] E5.根据第一一维矩阵DAM、第二一维矩阵DBN和带权二分图G(A,B,WM×N)，采用相等子图构建算法得到相等子图G(A,B,EWM×N)；
[0174] E6.根据步骤E5得到的相等子图G(A,B,EWM×N)，采用匈牙利算法计算得到优化匹配关系集合FM或非增广路径的交错路径；
[0175] E7.对步骤E6采用的匈牙利算法计算得到的结果进行判断：
[0176] 若得到的结果为优化匹配关系集合FM，则直接输出优化匹配关系集合FM，步骤E结束；
[0177] 若得到的结果为非增广路径的交错路径，则将非增广路径的交错路径中属于拟调度任务集合A的元素所对应的顶标值减去第一设定值，并将非增广路径的交错路径中属于
资源提供节点集合B的元素所对应的顶标值增加第二设定值；
[0178] E8.对步骤E7得到的修改后的第一一维矩阵DAM和第二一维矩阵DBN中的所有元素进行判断：
[0179] 若第一一维矩阵DAM中的所有元素值均大于0且第二一维矩阵DBN中的所有元素值均大于0，则返回步骤E5进行循环计算；
[0180] 否则，则步骤E结束。
[0181] 该部分的伪代码如下：
[0182]
[0183] 采用如下步骤计算得到相等子图G(A,B,EWM×N)：
[0184] E5‑1.初始化相等子图二维矩阵EWM×N中每个元素awmn；
[0185] E5‑2.针对拟调度任务集合A所对应的第一一维矩阵DAM中的每一个元素dam，以及资源提供节点集合B所对应的第二一维矩阵DBN的每一个元素dbn，进行如下判断：
[0186] 若dam+dbn的值与边‑权重二维矩阵WM×N中的对应元素wmn的值相等，则将相等子图二维矩阵EWM×N中的元素awmn的值设定为wmn的值；
[0187] 否则，则保持awmn的值为初值；
[0188] 对拟调度任务集合A所对应的第一一维矩阵DAM中的每一个元素dam，均以上述步骤与资源提供节点集合B所对应的第二一维矩阵DBN的每一个元素dbn进行判断，从而得到相等
子图二维矩阵EWM×N中每个元素awmn，并与拟调度任务集合A和资源提供节点集合B一同构成
相等子图G(A,B,EWM×N)；
[0189] 其中，m的取值为1,2,...,M，n的取值为1,2,...,N；
[0190] 该部分的伪代码如下：
[0191]
[0192]
[0193] 采用如下步骤计算得到优化匹配关系集合FM或非增广路径的交错路径：
[0194] E6‑1.构建优化匹配关系集合FM、拟调度任务集合A所对应的A已匹配节点集合MA和资源提供节点集合B所对应的B已匹配节点集合MB，并均进行初始化；
[0195] E6‑2.针对拟调度任务集合A中每一个未匹配的节点mm，根据节点mm、A已匹配节点集合MA、B已匹配节点集合MB和相等子图G(A,B,EWM×N)，采用增广或交错路径求解算法，得到
一条以mm为起点的交错路径；
[0196] E6‑3.对步骤E6‑2所得到的交错路径，进行如下判断：
[0197] 若交错路径为增广路径，则将该路径上的偶数边从优化匹配关系集合FM中移除，同时将该路径上的奇数边加入优化匹配关系集合FM；
[0198] 若交错路径为非增广路径，则直接返回该交错路径为非增广路径的交错路径；
[0199] 该部分的伪代码如下：
[0200]
[0201]
[0202] 具体为采用如下步骤计算得到交错路径：
[0203] E6‑2‑1.构建增广路径队列ZP和交错路径队列JP，并进行初始化；
[0204] E6‑2‑2.将第一中间变量x设定为节点mm；
[0205] E6‑2‑3.针对资源提供节点集合B中的每一个节点n，令第二中间变量y设定为节点n，并进行判断：
[0206] 若第二中间变量 且相等子图二维矩阵EWM×N中对应的元素ewx,y大于0，则将边x→y加入到增广路径队列ZP；
[0207] 否则，则判断：若y∈MB且相等子图二维矩阵EWM×N中对应的元素ewx,y大于0，则将边x→y加入到交错路径队列JP，同时在优化匹配关系集合FM总找到y的匹配顶点m'，并将第一
中间变量x设定为节点m'；
[0208] 否则，则保持第一中间变量x为原值；
[0209] 最后，返回交错路径队列JP；
[0210] 该部分的伪代码如下：
[0211]
[0212]
[0213] S3.步骤S2所述的任务调度节点，针对步骤S2获取的优化匹配关系集合中的每一对任务‑任务执行节点对，计算得到每一个任务执行节点的所有具备不小于对应任务所需
要资源量的空闲资源的邻居节点集合；
[0214] S4.步骤S2所述的任务调度节点，针对步骤S3得到的邻居节点集合中的每一个候选备份节点，计算对应的链路连通频度预测值、链路吞吐能力预测值和备份资源复用率预
测值；
[0215] 具体为采用如下步骤计算得到预测值：
[0216] a.构建第一统计总和变量SUM、第二统计总和变量Δ、第一统计计数变量COU、第二统计计数变量Δ+和第三统计计数变量Δ‑，并初始化；
[0217] b.针对每一个候选备份节点k，计算节点k的历史链路连通频度值的总和值并赋予第一统计总和变量SUM，同时计算节点k的历史链路连通频度值的平均值并赋予变量
[0218] c.针对每一个候选备份节点k，对节点k的每一个历史链路连通频度值进行如下判断：
[0219] 若历史链路连通频度值大于变量 则第二统计计数变量Δ+加1，否则第三统计计数变量Δ‑加1；同时将每一个历史链路连通频度值与变量 的差值进行平方后再求和，
得到中间变量Δ1；
[0220] d.计算第二统计总和变量Δ为 其中COU为第一统计计数变量，取值为候选备份节点的总数；
[0221] e.再次进行判断：
[0222] 若Δ+＞Δ‑，则链路连通频度预测值 取值为
[0223] 若Δ+≤Δ‑，则链路连通频度预测值 取值为
[0224] f.针对每一个候选备份节点k，计算节点k的历史链路吞吐能力值的总和值并赋予第一统计总和变量SUM，同时计算节点k的历史链路吞吐能力值的平均值并赋予变量
[0225] g.针对每一个候选备份节点k，对节点k的每一个历史链路吞吐能力值进行如下判断：
[0226] 若历史链路吞吐能力值大于变量 则第二统计计数变量Δ+加1，否则第三统计计数变量Δ‑加1；同时将每一个历史链路吞吐能力值与变量 的差值进行平方后再求和，
得到中间变量Δ1；
[0227] h.计算第二统计总和变量Δ为 其中COU为第一统计计数变量，取值为候选备份节点的总数；
[0228] i.再次进行判断：
[0229] 若Δ+＞Δ‑，则链路吞吐能力预测值 取值为
[0230] 若Δ+≤Δ‑，则链路吞吐能力预测值 取值为
[0231] j.针对每一个候选备份节点k，计算节点k的历史备份资源复用率的总和值并赋予第一统计总和变量SUM，同时计算节点k的历史备份资源复用率的平均值并赋予变量
[0232] k.针对每一个候选备份节点k，对节点k的每一个历史备份资源复用率进行如下判断：
[0233] 若历史备份资源复用率大于变量 则第二统计计数变量Δ+加1，否则第三统计计数变量Δ‑加1；同时将每一个历史备份资源复用率与变量 的差值进行平方后再求和，
得到中间变量Δ1；
[0234] l.计算第二统计总和变量Δ为 其中COU为第一统计计数变量，取值为候选备份节点的总数；
[0235] m.再次进行判断：
[0236] 若Δ+＞Δ‑，则备份资源复用率预测值 取值为
[0237] 若Δ+≤Δ‑，则备份资源复用率预测值 取值为
[0238] n.最后，返回链路连通频度预测值 链路吞吐能力预测值 和备份资源复用率预测值
[0239] 该部分的伪代码如下：
[0240]
[0241] S5.根据步骤S4得到的预测值，对步骤S2所述的任务调度节点所对应的所有任务执行节点，选择对应的抗毁接替节点；
[0242] 采用如下步骤选择对应的抗毁接替节点：
[0243] (1)为任务执行节点j选出至多3个备份资源复用率预测值最低的候选邻居；
[0244] (2)在步骤(1)得到的候选邻居中，再选择最多2个具有最强链路吞吐能力预测值的候选邻居；
[0245] (3)在步骤(2)得到的邻居中，选择1个具有最好的链路连通频度预测值的邻居，作为任务执行节点j的抗毁接替节点。
[0246] 步骤S7所述的更新通信网络的网络参数，具体为采用如下步骤进行更新：
[0247] 1)针对抗毁接替节点集合KH中的每一个备份节点k，完成如下动作：
[0248] 从优化匹配关系集合OM中找到备份节点k的服务对象j；
[0249] 更新当前周期结束时的通信链路连通频度值 并将 加入到集合Ll中；
[0250] 更新当前周期结束时的通信链路吐吞能力值 并将 加入到集合Lc中；
[0251] 2)获取其他任务调度节点的位置坐标；
[0252] 3)统计当前任务调度节点i的资源视图中提供备份资源的节点数；资源视图的定义为当前任务调度节点i所能探测到的节点集合；
[0253] 4)根据步骤2)获取的位置坐标、当前任务调度节点i的资源视图和对应的提供备份资源的节点数，更新当前周期结束时的所有备份节点的资源复用率 并将 加入集合
Lφ；其中k∈KH
[0254] 5)返回集合Ll、Lc和Lφ，完成通信网络的网络参数更新；
[0255] 该部分的伪代码如下：
[0256]
[0257]
[0258] 采用如下步骤进行更新当前周期结束时的通信链路连通频度值
[0259] 1)‑1‑1.构建网络环境更新周期τn、第一计数变量N和第二计数变量N'，并初始化；其中第二计数变量N'用于备份节点k与其服务对象j的连通计数；其中备份节点k所对应的
服务对象j为任务执行节点j；
[0260] 1)‑1‑2.针对当前任务调度与执行周期t内的每个网络环境更新周期τn，均进行如下操作：
[0261] 获取在τn期间更新的任务执行节点j的坐标(xj,yj)；
[0262] 获取在τn期间更新的任务执行节点j所对应的备份节点k的坐标(xk,yk)；
[0263] 进行如下判断：
[0264] 若 则第二计数变量N'增加1；否则，则保持第二计数变量N'不变；
[0265] 第一计数变量N增加1；
[0266] 1)‑1‑3.更新当前周期结束时的通信链路连通频度值 的值为
[0267] 该部分的伪代码如下：
[0268]
[0269]
[0270] 采用如下步骤更新当前周期结束时的通信链路吐吞能力值
[0271] 1)‑2‑1.对通信链路吐吞能力值 进行初始化；
[0272] 1)‑2‑2.针对当前任务调度与执行周期t内的每个网络环境更新周期τn，均进行如下操作：
[0273] 获取在τn期间更新的任务执行节点j的坐标(xj,yj)；
[0274] 获取在τn期间更新的任务执行节点j所对应的备份节点k的坐标(xk,yk)；
[0275] 计算中间距离变量
[0276] 计算中间信道增益变量 其中gj,k为链路j→k的信道增益；为任务执行节点j的最大发射功率；α为链路j→k的路径损耗指数；
[0277] 计算中间带宽变量 其中W为链路j→k的带宽；N0为环境噪声功率密度；
[0278] 更新当前周期结束时的通信链路吐吞能力值 为其中δ为权值参数； 为上一周期结束时的通信链路吐吞能力值；
[0279] 该部分的伪代码如下：
[0280]
[0281] 采用如下步骤更新当前周期结束时的所有备份节点的资源复用率
[0282] 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)}；
[0283] 4)‑2.将j的值从1一直取值至J，并对每一个j的取值，均进行如下判断：
[0284] 若k的值等于算式 的值，则将二维矩阵MJK所对应的元素mjk的值设定1；
[0285] 否则，则保持mjk为原值；
[0286] 4)‑3.将k的值从1一直取值至K，并对每一个k的取值，均进行如下计算：和
[0287] 4)‑4.将k的值从1一直取值至K，并对每一个k的取值，均再次进行如下操作：
[0288] 计算距离变量
[0289] 若 则设定变量bk为较大设定值(比如5)；
[0290] 若 则设定变量bk为中等设定值(比如3)；
[0291] 否则，则设定变量bk为较小设定值(比如1)；
[0292] 其中， 为设定的距离下限阈值； 为设定的距离上限阈值；较大设定值、中等设定值和较小设定值为事先设定的值，且要求较大设定值>中等设定值>较小设定值；
[0293] 4)‑5.将k的值从1一直取值至K，并对每一个k的取值，均再次进行如下操作：
[0294] 计算求和变量
[0295] 若 则设定变量ck为小设定值(比如1)；
[0296] 若 则设定变量ck为中设定值(比如3)；
[0297] 否则，则设定设定变量ck为大设定值(比如5)；
[0298] 其中， 为设定的求和下限阈值； 为设定的求和上限阈值；大设定值、中设定值和小设定值为事先设定的值，且要求大设定值>中设定值>小设定值；
[0299] 4)‑6.将k的值从1一直取值至K，并对每一个k的取值，均再次进行如下操作：计算资源复用率 φk为任务调度节点i的资源视图中第k个提供备份资源
的节点备份资源复用率；该部分的伪代码如下：
[0300]
[0301]
[0302] S6.重复步骤S2～S5，直至为所有任务调度节点所对应的所有任务执行节点选定抗毁接替节点；
[0303] S7.更新通信网络的网络参数；
[0304] S8.重复步骤S2～S7，持续进行支持跨节点计算任务抗毁接替的任务与资源匹配。
[0305] 上述步骤中，步骤S2～步骤S5的算法步骤，其伪代码如下：
[0306]
[0307]
[0308] 以下结合一个实施例，对本发明进行进一步说明：
[0309] 本发明使用OMNeT++搭建仿真网络。在半径500米的圆形平台内设置50个节点，每个节点的初始坐标、计算资源(例如，CPU数量)、通信半径等参数在仿真系统初始化时从“数
据文件(后缀为ini)”读入，而数据文件中的数据是事先准备好的，其坐标数据在半径500米
的圆形平台内随机生成、每个节点的空闲CPU数量在从0至16的范围内随机抽取、每个节点
的通信半径为250米。
[0310] 仿真系统启动后，每个节点坐标位置每隔时间间隔T重新刷新一次。为简化刷新过程，可在当前值的基础上随机增加或减少0～50％。设定一个固定ID的节点为任务调度节
点，其上需要调度执行的任务按标准的小任务统计数量。一个标准的小任务需要至少一个
CPU持续T时间方能成功完成。为了体现资源总是受限的军事环境特点，应该将任务调度节
点上需要调度的小任务数量设置得足够多，使其需要的资源总量比任务调度节点获得的资
源视图中的资源量要多。假设任务调度节点仅能实时地获得其两跳通信范围内的预测资源
视图，并根据这个资源视图，将任务分配到所选择的任务执行节点上，且设置任务执行节点
以一定概率损毁。若损毁发生，任务调度节点则将发生损毁节点上的任务调度到其它有空
闲资源的节点上执行，若无资源可用，则宣告该任务失败。
[0311] 指定一个固定ID号的节点充当任务调度节点的主角，另外为该主角配置一个任务调度节点集合充当配角。主角可以为每个任务分配任务执行节点、配置抗毁接替节点、计算
与记录抗毁接替节点的链路连通频度、平均通信链路吞吐能力、备份资源复用率等指标数
据，而配角仅为自身需调度的任务寻找可用的空余资源，例如，抗毁接替节点上为主角所调
度任务预留的备份资源，或其它未使用资源(但必须以主角的使用需求优先)。仿真网络示
例于图3。
[0312] 任务执行节点(主角)依据系统事先确定的拟调度任务数(例如根据某种权衡模型得出拟调度任务数N)和当前可用资源量，利用本发明方案实施任务分配与资源匹配，确定
任务的执行节点、任务执行节点的抗毁接替节点。通过如下两组仿真来验证实际效果。首
先，在不同任务调度周期下，设置拟调度的任务数相同，由于每个调度周期仿真环境会变
化，导致资源视图发生变化，可用资源总量也可能发生变化。这时，分析三种任务分配方案
的表现，即每个任务是否都能获得任务执行节点，以及任务执行节点是否都能获得抗毁接
替节点。其中，最大任务优先方案的做法：将任务按所需资源量降序排列，同时将可用的任
务执行节点按能提供的资源量降序排列，依次取出未分配资源的最大资源需求量任务，在
可用的任务执行节点队列中搜索一个能满足其资源要求的资源量最小的任务执行节点。随
机分配方案的做法：仅将可用的任务执行节点按能提供的资源量降序排列，随机取出未分
配资源的任务，在可用的任务执行节点队列中搜索一个能满足其资源要求的资源量最小的
任务执行节点。仿真结果如图4所示。在图4(a)中，由于节点的分布情况使得各个子任务的
所需资源数均能满足，因此每个子任务都能获得对应的任务执行节点，各个任务调度周期
均获得任务执行节点比例为100％。图4(b)显示本方案相比其余两种对比方案任务执行节
点获得接替节点的比例更高，说明本方案的任务分配更能使用动态环境特点。同时由于不
同任务调度周期中节点分布情况具有随机性以及节点损毁概率的随机变化，导致任务执行
节点可用的接替节点资源也具有随机性，因此执行节点获得抗毁接替节点的比例呈现随机
性。
[0313] 然后，在不同任务调度周期下，仿真分配方案取不同拟调度的任务数时的性能表现如图5所示，这里任务执行节点损毁概率统一设置为10％。从图5(a)中，可以看到，由于不
同任务调度周期中节点分布情况具有随机性以及节点损毁概率的随机变化，因此，不同任
务调度总数下的任务存活率也呈现随机变化趋势。基于类似因素，从图5(b)中，也看到不同
任务调度总数下的资源利用率也呈现随机变化趋势。基于某种权衡模型得出拟调度任务数
N是较为合理的任务调度数，当高于或低于这个值时，性能表现都欠佳。这说明在任一可用
资源量下，会有一个较为合理的拟调度的任务数，找到这个合理值甚为关键。
