一种应用于仿真网格系统的生物智能调度方法

摘要

一种应用与仿真网格系统的生物智能调度方法，根据不同节点上仿真模型的特点、仿真应用任务量的大小、采用面向角色模型方式，将一个仿真应用分解为一组存在数据输入输出关系的计算子任务并形成相应的仿真作业资源组；并生成任务资源的配比权重，采用树状层次角色图表示一个仿真网格应用中各个任务之间的数据相关性，通过多路径混合蚁群智能调度方法使得选定的子任务调度路径消耗量最低，实现仿真高性能计算作业的高效调度。其优点是：保证仿真应用资源大部分时间处于适量负载的工作状态，从而为资源拥有者带来更多的经济利益；保证仿真任务能在尽量短的时间内完成，但又不致于花费太多的计算费用。

主权项

一种应用于仿真网格系统的生物智能调度方法，其特征在于：根据不同节点上仿真模型的特点、仿真应用任务的大小、采用面向角色模型方式，将一个仿真应用任务分解为一组存在数据输入输出关系的计算子任务并形成相应的仿真作业资源；并生成资源的配比权重，采用树状层次角色图表示一个仿真网格应用中各个任务之间的数据相关性，通过多路径混合蚁群智能调度方法使得选定的子任务调度路径消耗量最低，实现仿真高性能计算作业的高效调度；其步骤如下：(1)将仿真应用任务根据任务所需要的资源和任务的执行序列，生成仿真网络中的就绪资源，记Q＝{Q_i：i＝1，2，…，q}为资源类型集；记R＝{R_i：i＝1，2，…，r}为资源集，每个资源有且仅有唯一的资源类型，即存在惟一的Q_k∈Q与之对应；任务的执行时间μ_ik，表示任务在资源类型为Q_k的某一资源上的预计执行时间，记表示任务i在资源类型为Q_k的某一资源上执行；记P={P_i：i＝1，2，…，p}为仿真网格中不同地理位置的战术节点集合，i为战术节点位置编号，而每个资源就处于某个地理位置节点上，即存在唯一的P_m∈P与之对应，P_m为m位置的战术节点；记B={B_mn：P_m，P_n∈P}为不同节点间的传输带宽，B_mn为m位置上的战术节点到n位置上的战术节点间的传输带宽，记D＝{D_mn：P_m，P_n∈P}为不同节点间的传输延迟，P_n为n位置的战术节点；当m=n时，B_mn=0，D_mn=0，D_mn为m位置上的战术节点到n位置上的战术节点间的传输延迟；记T_r为在资源R_r∈R上执行的所有任务的集合，记为在资源R_r∈R上执行的所有任务的约束条件集合；若P_m，P_n∈P，则从任务i到任务j的数据传输时间为：$d_{\mathrm{ij}}=\left\{\begin{array}{cc}0,& \mathrm{if}\exists E_r,(i,j)\in E_r\\ {\lambda }_{\mathrm{ij}}\times B_{\mathrm{mn}}+D_{\mathrm{mn}},& \mathrm{others}\end{array}\right.$表示当任务i与任务j在同一地理位置节点执行时，没有传输延迟，即D_mn＝0；当任务i与任务j在同一地理位置节点的同一资源上执行时，不需要进行数据传输，即d_ij=0；令和分别表示任务i的开始执行时刻和完成执行时刻，任务i的执行时间通过选取执行最小时间损耗的任务来确定任务的执行序列，根据任务所需要的资源和任务的执行序列，生成仿真网格中的就绪资源；(2)通过仿真网络中资源的状态和相关属性；结合资源的权限向量生成资源配比矩阵，形成资源的配比方程，生成资源的配比权重，根据仿真网格中的就绪资源，定义向量R表示用户角色集；若系统中的用户角色个数为n，则有：R=[role₁，role₂，...，role_n]^T若系统中被操作的资源个数为m，则有：R(t)=[r₁(t)，r₂(t)，...，r_m(t)]^T系统的状态是由系统中所有资源的状态所决定的，记为：ST(t)=[st₁(t),st₂(t)，...，st_m(t)]^T若将系统中某个确定的role_i对某确定对象r_i(t)的相关属性的授权约束条件记为c_ij，r_i(t)表示系统中t时刻操作的资源i，c_ij表示t时刻第j个用户对第i资源的相关属性授权约束条件，则role_i对r_i(t)的操作可以表示为：pro_ij，pro_ij表示t时刻第j个用户对第i个资源的操作；其中，如果role_i不具备对资源r_i(t)的操作，则可记为pro_ij＝0称为空操作，如果role_i对r_i(t)的可能操作不只一个，则pro_ij表示由这些操作构成的向量，这样，若定义pro_ij所对应的角色role_i对r_i(t)的操作算子为η_ij，η_ij为t时刻第j个用户对第i个资源的操作算子，且k为某一确定的时间点，则有η_ij·r_j(k)=r_j(k+1)这里，空操作对应的算子称为空操作算子，记为η₀，η₀作用到r_i(t)或st_j(t)后，其中st_j(t)为t时刻系统状态，不改变相应的资源的属性和状态；由于在整个仿真网格系统中，资源在角色间的流转是由资源的状态驱动的，所以角色是否能够对资源执行操作，是由当前资源的状态所决定的，因此将资源状态约束下的角色对资源的操作算子记为η_ij，则有η_ij=f_i(η_ij,r_ij,st_j(t))式中，函数f_i的功能为：根据某一确定时刻t的资源状态st_j(t)，利用角色对该资源操作的约束条件来判断角色role_i是否可对r_i(k)执行操作算子η_ij，即则可得到系统中资源状态约束下的资源配比矩阵为：$\left[\begin{array}{cccc}{\eta }_{11}& {\eta }_{12}& ······& {\eta }_{1m}\\ {\eta }_{21}& {\eta }_{22}& ······& {\eta }_{2m}\\ ······& ······& ······& ······\\ {\eta }_{n1}& {\eta }_{n2}& ······& {\eta }_{\mathrm{nm}}\end{array}\right]$该矩阵的列向量记为：η_j=[η_1j,η_2j，...，η_nj]^T表示系统中n个角色在st_j(t)约束下的对资源r_j(t)的操作算子向量，其中j=0，1，…，m，则可构造如下对角阵形式：$G=\left[\begin{array}{cccc}{\eta }_{11}& 0& ······& 0\\ 0& {\eta }_{22}& ······& 0\\ ······& ······& ······& ·······\\ 0& 0& ······& {\eta }_{\mathrm{nn}}\end{array}\right]---\left(a\right)$由于系统是动态系统，所以系统的状态是变化的，则可以得到系统的状态方程为：st(k+1)=G·st(k) (b)即$\left[\begin{array}{c}{\mathrm{st}}_1(k+1)\\ {\mathrm{st}}_2(k+1)\\ ······\\ {\mathrm{st}}_m(k+1)\end{array}\right]=\left[\begin{array}{cccc}{\eta }_{11}& 0& ······& 0\\ 0& {\eta }_{22}& ······& 0\\ ······& ······& ······& ······\\ 0& 0& ······& {\eta }_{\mathrm{nn}}\end{array}\right]·\left[\begin{array}{c}{\mathrm{st}}_1\left(k\right)\\ {\mathrm{st}}_2\left(k\right)\\ ······\\ {\mathrm{st}}_m\left(k\right)\end{array}\right]---\left(c\right)$其中，G称为控制矩阵，由公式(a)，(b)和(c)可知，G是与系统状态st(t)相关的，所以系统是一个非线性系统；${\mathrm{st}}_j(k+1)={\eta }_{j·}{\mathrm{st}}_j\left(k\right)=\left[\begin{array}{c}{\eta }_{1j}\left(k\right)\\ {\eta }_{2j}\left(k\right)\\ ······\\ {\eta }_{\mathrm{nj}}\left(k\right)\end{array}\right]·{\mathrm{st}}_j\left(k\right)=\left[\begin{array}{c}{\eta }_{1j}\left(k\right)·{\mathrm{st}}_j\left(k\right)\\ {\eta }_{2j}\left(k\right)·{\mathrm{st}}_j\left(k\right)\\ ······\\ {\eta }_{\mathrm{nj}}\left(k\right)·{\mathrm{st}}_j\left(k\right)\end{array}\right]---\left(d\right)$相应的资源配比方程为：r(k+1)=G·r(k)从上式可知，由对角矩阵G可以求出k+1个资源的配比权重；(3)根据资源的配比权重，将资源的调度配比路径选择过程通过人工蚂蚁的搜索实现，其算法公式为(i)，并分为三个阶段，即开始阶段、中间阶段和结束阶段；算法中搜索的开始阶段，路径上信息元素量根据相应路由的延时约束满足程度进行更新，蚂蚁主要选择延时约束和带宽约束较好的路径，其信息元素更新公式为(f)；当信息量积累到一定程度进入中间阶段，其链路上的信息量已足以体现延时约束方面的优势，此时用延时抖动约束满足程度对对应路径上的信息元素量进行更新，这样在原来延时约束满足程度好、剩余带宽较大路由中，延时抖动约束满足程度高的路径上的信息量就越来越多，促使蚂蚁选择这些路径，其信息元素更新公式为(g)；当搜索过程进入结束阶段时，用信息元素丢失率约束满足程度更新信息元素，搜索过程完成后，选择搜索成本高的个体进入下一次迭代，下一代更新信息量时，路径上的信息元素量则因为经过的蚂蚁比较多而获得增加的机会比较大，这样最终迭代结果是蚂蚁选择了各个约束条件满足程度都相对较高的路径中成本较低的路径，其信息元素更新公式为(h)；算法(i)中整体更新信息元素量时路径(i，j)上第k个蚂蚁的信息量按如下公式更新：${\tau }_{\mathrm{ij}}^k(t+1)=(1-\rho ){\tau }_{\mathrm{ij}}^k\left(t\right)+\rho ·\Delta {\tau }_{\mathrm{ij}}^k\left(t\right)+c---\left(e\right)$其中是t+1时刻蚂蚁k在路径(i，j)上留下的信息元素的量，ρ是蚂蚁信息元素更新权值，一般取值0～1，c为常数变量可随机取值，是t时刻蚂蚁k在路径(i，j)上留下的信息元素的量，在蚂蚁搜索的开始阶段、中间阶段、结束阶段分别根据公式(f)、(g)、(h)确定：其中是延时度量的惩罚函数，在为理想状态下没有延时，取其值均为0，即在不满足延时约束的路径上不增加信息元素量，从而减少下次迭代中蚂蚁选择该路径的机率；所述的多路径混合蚁群智能调度方法，在使算法具有较强搜索能力的同时，避免出现停滞现象，该算法使用自适应随机比率选择规则信息元素量，使得t时刻该蚂蚁在1状态下选择路径(i，j)的概率按照公式(i)得出，即对位于节点i的蚂蚁k，按公式(i)选择随机规则：$h\left(j\right)=\left\{\begin{array}{cc}\arg \max \left\{\tau \underset{u\in J_k\left(i\right)}{(i,u)\times {\eta }^{\beta }}(i,u)\right\},& \mathrm{if}(q\le q(\lambda \left(t\right))\\ s,& \mathrm{otherwise}\end{array}\right.---\left(i\right)$q(λ(t))=λ(t)／N其中λ(t)∈[2，N]表示算法在第t次迭代时的路径均衡量，N表示节点数，有q(λ(t))∈[2／N，1]，其中q(λ(t))表示第t次迭代时N个节点平均路径均衡量，q为[0，1]上一致分布的随机数，τ(i，u)表示节点i与节点u之间的信息素量，η(i，u)表示节点i与节点u之间的启发式因子，β表示启发式因子的强弱；网格节点中的通信链路称为路径，在选择路径过程中，t时刻蚂蚁k在1状态下选择路径(i，j)的概率表示如下：$p_{\mathrm{ij}}^{\mathrm{lk}}\left(t\right)=\left\{\begin{array}{c}{\xi }_{\mathrm{ij}}^k\times \frac{{\left({\alpha }_{(i,j)}^k\left(t\right)\right)}^{\partial }/{\left({\beta }_{(i,j)}^k\left(t\right)\right)}^{\alpha }}{\underset{i\in v_{i}j\in v-v_i}{\Sigma }{\left({\alpha }_{(i,j)}^k\left(t\right)\right)}^{\partial }/{\left({\beta }_{(i,j)}^k\left(t\right)\right)}^{\partial }}\times \frac{{\left({\eta }_{\mathrm{ij}}^{\mathrm{lk}}\left(t\right)\right)}^{\alpha }}{\underset{i\in v_{i}j\in v-v_i}{\Sigma }{\left({\eta }_{(i,j)}^k\left(t\right)\right)}^{\alpha }},q<q_0---\left(j\right)\\ h\left(j\right)\end{array}\right.$其中${\alpha }_{\mathrm{ij}}^k\left(t\right)=\frac{{\tau }_{(i,j)}^k\left(t\right)}{\underset{i\in v_{k}j\in v-v_k}{\Sigma }{\tau }_{(i,j)}^k\left(t\right)},{\beta }_{\mathrm{ij}}^k\left(t\right)=\frac{\underset{p=1}{\overset{m}{\Sigma }}{\tau }_{(i,j)}^p\left(t\right)}{\underset{p=1}{\overset{m}{\Sigma }}\underset{i\in v_k,j\in v-v_k}{\Sigma }{\tau }_{(i,j)}^p\left(t\right)}$分别称为路径(i，j)对蚂蚁k的吸引力和排斥力，蚂蚁k选择路径(i，j)的概率p_k(i,j)按照公式(k)可以得出$p_k(i,j)=\left\{\begin{array}{c}\frac{\left[\tau (i,j)\right]·{\left[\eta (i,j)\right]}^{\beta }}{\underset{s\in J_k\left(i\right)}{\Sigma }\left[\tau (i,s)\right]·{\left[\eta (i,s)\right]}^{\beta }},\mathrm{ifj}\in J_k\left(i\right)\\ 0,\mathrm{otherwise}\end{array}\right.---\left(k\right)$同时蚂蚁k在路径(i，j)上的信息元素更新方程为：${\alpha }_{\mathrm{ij}}^k={\mathrm{t\alpha }}_{\mathrm{ij}}^{\mathrm{old}}+M/f---\left(l\right)$其中为第i级第j个节点上人工蚂蚁k产生的信息元素强度；t表示信息元素强度的残留系数，取[0.5，0.9]；M为路径常数；f为大于0的常数。