一种基于离散萤火虫算法的片上网络映射方法

摘要

本发明公开了一种基于离散萤火虫算法的片上网络映射方法，其特征包括以下步骤：步骤1.参数定义；步骤2.初始化萤火虫个体集合及参数；步骤3.检查迭代终止条件，若满足迭代终止条件，则执行步骤9，否则执行步骤4；步骤4.获取第G次迭代时的最优萤火虫及全局最优萤火虫；步骤5.判断萤火虫个体的移动条件；步骤6.遍历萤火虫个体集合，并按照步骤5判断所有萤火虫个体的移动条件，遍历完成则执行步骤8；步骤7.更新萤火虫个体；步骤8.更新第G次迭代时的最优萤火虫；步骤9.获得最优映射方案。本发明能缩短优化时间，提高求解精度，获得更优映射结果。

主权项

一种基于离散萤火虫算法的片上网络映射方法，所述片上网络是由资源节点和通讯节点组成，其特征是按如下步骤进行：步骤1、参数定义：定义所述片上网络的拓扑结构为R，且R＝{L,M,N}，L表示片上网络的行数，M表示片上网络的列数，N表示片上网络的层数，L>0,M>0,N>0；以所述拓扑结构R的任一顶点为原点o，以所述拓扑结构R的行方向为x轴，列方向为y轴，层方向为z轴，建立笛卡尔直角坐标系o‑xyz；令IP核c表征为所述片上网络的资源节点,则IP核集合为C＝{c₀,c₁,…,c_a,…,c_A‑1},A表示IP核总数，A≤L×M×N，c_a表示所述片上网络中的第a个IP核，0≤a≤A‑1；定义萤火虫个体集合为X＝{X₁(t₁),X₂(t₂),…,X_k(t_k),…,X_K(t_K)}，K表示萤火虫个体总数，1≤k≤K，t表示萤火虫个体的更新次数，t≥0，t_k表示第k只萤火虫个体的更新次数，X_k(t_k)表示第t_k次更新后的第k只萤火虫个体；定义P^k(t_k)为所述第t_k次更新后的第k只萤火虫个体X_k(t_k)的映射方案，P^k(t_k)＝{map(r₀),map(r₁),...,map(r_i),...,map(r_T‑1)}，r表示所述片上网络中的通讯节点，T为所述片上网络中的通讯节点总数，T＝L×M×N，r_i表示所述片上网络中的第i个通讯节点，0≤i≤T‑1；假设按照所述第k只萤火虫个体X_k(t_k)的映射方案P^k(t_k)对所述IP核集合C进行映射后，若所述第i个通讯节点r_i上未映射有IP核，则定义map(r_i)＝‑1；若所述第i个通讯节点r_i上映射有IP核，则定义map(r_i)＝a，表示映射在第i个通讯节点r_i上的IP核为第a个IP核c_a；定义所述第k只萤火虫个体X_k(t_k)的荧光亮度为I^k(t_k)；定义所述第k只萤火虫个体X_k(t_k)的映射方案的总通讯量为所述第k只萤火虫个体X_k(t_k)的荧光亮度I^k(t_k)；定义Q^k(t_k)＝{R,P^k(t_k)}表示所述片上网络的拓扑结构R和所述第k只萤火虫个体X_k(t_k)的映射方案P^k(t_k)的拼接；则将所述第k只萤火虫个体X_k(t_k)表征为X_k(t_k)＝{Q^k(t_k),I^k(t_k)}；定义w_k为第k只萤火虫X_k(t_k)与其他任意一只萤火虫个体之间计算归一化距离的次数，w_k＞0；定义为第w_k次计算的第k只萤火虫X_k(t_k)和其他任一只萤火虫个体X_s(t_s)之间的归一化距离，1≤s≤K，且s≠k；定义光强吸收因子为γ，γ∈[0,1]、迭代次数为G、最大迭代次数为GMax、最大随机步长为α、最大吸引度为β₀；步骤2、初始化萤火虫个体集合及参数：步骤2.1、随机产生映射方案P^k(t_k)，获得所述片上网络中映射有IP核的通讯节点的坐标；步骤2.2、利用式(1)获得荧光亮度I^k(t_k)：$I^k\left(t_k\right)=\underset{i=1}{\overset{L\times M\times N}{\Sigma }}\underset{j=1}{\overset{L\times M\times N}{\Sigma }}{v}_{i,j}\times h_{i,j}---\left(1\right)$式(1)中,v_i,j表示映射有IP核的第i个通讯节点r_i与映射有IP核的第j个通讯节点r_j之间的通讯量；h_i,j表示映射有IP核的第i个通讯节点r_i与映射有IP核的第j个通讯节点r_j之间的跳数，令映射有IP核的第i个通讯节点r_i的坐标为(i_x,i_y,i_z)，映射有IP核的第j个通讯节点r_j的坐标为(j_x,j_y,j_z)，则h_i,j＝|i_x‑j_x|+|i_y‑j_y|+|i_z‑j_z|；步骤2.3、按照步骤2.1和步骤2.2，初始化萤火虫个体集合中的每一个萤火虫个体；步骤2.4、初始化迭代次数G＝0，输入光强吸收因子γ，γ∈[0,1]、最大迭代次数GMax＝gmax、最大随机步长α＝step，最大吸引度β₀＝1，更新次数t_k＝0，计算归一化距离的次数w_k＝1；步骤3、令迭代终止条件为G≥GMax，若满足所述迭代终止条件，则执行步骤9，否则执行步骤4；步骤4、获取第G次迭代时的最优萤火虫X_min(G)及全局最优萤火虫X_gmin(G)：遍历所述萤火虫个体集合并比较任意两只萤火虫个体的荧光亮度，寻找荧光亮度最小的萤火虫个体记为第G次迭代时的最优萤火虫X_min(G)；当G＝0时，全局最优萤火虫X_gmin(G)＝X_min(G)，当G≠0时，若X_gmin(G)＞X_min(G)，则更新全局最优萤火虫X_gmin(G)＝X_min(G)，否则全局最优萤火虫X_gmin(G)保持不变；步骤5、判断第k只萤火虫个体X_k(t_k)的移动条件：步骤5.1、令s＝1，则第t₁次更新后的第1只萤火虫个体表示为X₁(t₁)；步骤5.2、判断s＝K是否成立，若成立则执行步骤6，否则执行步骤5.3；步骤5.3、将w_k+1赋值给w_k，利用式(2)获得所述第k只萤火虫个体X_k(t_k)到第s只萤火虫个体X_s(t_s)之间的归一化距离$d_{\mathrm{uni}}^{k,s}\left(w_k\right)=\frac{d_{k,s}-d_{\min }^{k,s}}{d_{\max }^{k,s}-d_{\min }^{k,s}}---\left(\text{2}\right)$式(2)中，d_k,s表示第k只萤火虫个体X_k(t_k)的映射方案P^k(t_k)到第s只萤火虫个体X_s(t_s)的映射方案P^s(t_s)之间相差的跳数，表示第k只萤火虫个体X_k(t_k)的映射方案P^k(t_k)到第s只萤火虫个体X_s(t_s)的映射方案P^s(t_s)之间相差的跳数的理论最大值，表示第k只萤火虫个体X_k(t_k)的映射方案P^k(t_k)到第s只萤火虫个体X_s(t_s)的映射方案P^s(t_s)之间相差的跳数的理论最小值；步骤5.4、根据式(3)所示的移动条件，判断第k只萤火虫个体X_k(t_k)是否向第s只萤火虫个体X_s(t_s)移动，若满足所述移动条件，则执行步骤7，否则，将s+1赋值给s，并执行步骤5.2；$\frac{1}{I^k\left(t_k\right)}<\frac{1}{I^s\left(t_s\right)}\times \exp (-{\mathrm{\gamma d}}_{\mathrm{uni}}^{k,s}\left(w_k\right))---\left(3\right)$式(3)中，表示由于第k只萤火虫个体X_k(t_k)和第s只萤火虫个体X_s(t_s)之间的距离使第s只萤火虫个体X_s(t_s)的荧光亮度倒数的衰减；步骤6、遍历所述萤火虫个体集合，并按照步骤5判断所有萤火虫个体的移动条件，遍历完成则执行步骤8；步骤7、更新萤火虫个体X_k(t_k)步骤7.1、利用式(4)获得所述第t_k次更新后的第k只萤火虫个体X_k(t_k)与第s只萤火虫个体X_s(t_s)之间的吸引度β_k,s(t_k)：${\beta }_{k,s}\left(t_k\right)=\frac{{\beta }_0}{1+\gamma {\left(d_{\mathrm{uni}}^{k,s}\left(w_k\right)\right)}^2}---\left(4\right)$步骤7.2、根据第k只萤火虫个体X_k(t_k)与第s只萤火虫个体X_s(t_s)之间的吸引度β_k,s(t_k)按照β移动步骤规则发生移动，并将移动后的萤火虫个体X_k(t_k)记为X_k(t_k)'；步骤7.3、所述移动后的萤火虫个体X_k(t_k)'根据所述最大随机步长α按照第一α移动步骤规则再次发生移动，并将更新次数t_k+1赋值给t_k，从而获得第t_k次更新后的第k只萤火虫个体X_k(t_k)中的映射方案P^k(t_k)；步骤7.4、根据更新后的第k只萤火虫个体X_k(t_k)中的Q^k(t_k)＝{R,P^k(t_k)}，利用式(1)获得更新后的第k只萤火虫个体X_k(t_k)中的荧光亮度I^k(t_k)；步骤7.5、根据所述片上网络的拓扑结构R、所述更新后的第k只萤火虫个体X_k(t_k)的映射方案P^k(t_k)以及荧光亮度I^k(t_k)，获得更新后的第k只萤火虫个体X_k(t_k)，并将s+1赋值给s后，执行步骤5.2；步骤8、更新第G次迭代时的最优萤火虫X_min(G)：步骤8.1、第G次迭代的最优萤火虫X_min(G)按照第二α移动步骤规则发生移动，从而获得更新后的第G次迭代最优萤火虫X_min(G)'中的映射方案P^min(G)'；步骤8.2、根据更新后的第G次迭代时的最优萤火虫X_min(G)'中的片上网络的拓扑结构R和映射方案P^min(G)'，利用式(1)获得第G次迭代时的最优萤火虫X_min(G)'中的荧光亮度I^min(G)'；步骤8.3、将G+1赋值给G，并执行步骤3；步骤9、获得最优映射方案：所述全局最优萤火虫X_gmin(G)的映射方案P^gmin(G)为所述最优映射方案。