[發明專利]一種基于離散螢火蟲算法的片上網絡映射方法

有效

• 申請號: 201410346056.2
• 申請日: 2014-07-18
• 公開（公告）號: CN104079439B
• 公開（公告）日: 2017-02-22
• 發明（設計）人: 杜高明;劉鑫;張多利;宋宇鯤;歐陽昊;尹勇生
• 申請（專利權）人: 合肥工業大學
• 主分類號: H04L12/24
• 分類號: H04L12/24;G06F17/50;G06F15/173
• 代理公司: 安徽省合肥新安專利代理有限責任公司34101
• 代理人: 何梅生

1.一種基于離散螢火蟲算法的片上網絡映射方法，所述片上網絡是由資源節點和通訊節點組成，其特征是按如下步驟進行：

步驟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)：

Ik(tk)=Σi=1L×M×NΣj=1L×M×Nvi,j×hi,j---(1)]]>

式(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)之間的歸一化距離

dunik,s(wk)=dk,s-dmink,sdmaxk,s-dmink,s---(2)]]>

式(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；

1Ik(tk)<1Is(ts)×exp(-γdunik,s(wk))---(3)]]>

式(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)：

βk,s(tk)=β01+γ(dunik,s(wk))2---(4)]]>

步驟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)為所述最優映射方案。