[發(fā)明專利]基于多環(huán)的光片上網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)設(shè)計(jì)方法

有效

• 申請?zhí)枺?/td>: 201710247926.4
• 申請日: 2017-04-17
• 公開（公告）號: CN106911521B
• 公開（公告）日: 2019-07-16
• 發(fā)明（設(shè)計(jì)）人: 朱李晶;顧華璽;王琨;楊銀堂;朱樟明;劉良凱
• 申請（專利權(quán)）人: 西安電子科技大學(xué)
• 主分類號: H04L12/24
• 分類號: H04L12/24;H04L12/801;H04L12/933;H04J14/02
• 代理公司: 陜西電子工業(yè)專利中心 61205
• 代理人: 韋全生;王品華

1.一種基于多環(huán)的光片上網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)設(shè)計(jì)方法，其特征在于包括如下步驟：

(1)設(shè)定環(huán)組集合G：包括u個(gè)環(huán)組g₁,g₂,g₃,...,g_q,...,g_u，q代表環(huán)組的序號，每個(gè)環(huán)組表示包含M個(gè)環(huán)R₁,R₂,...,R_r,...,R_M的多環(huán)網(wǎng)絡(luò)拓?fù)洌瑀代表環(huán)的序號，該多環(huán)網(wǎng)絡(luò)拓?fù)浒琋個(gè)互連的節(jié)點(diǎn)，環(huán)組g_q中的每個(gè)環(huán)R_r用含有N個(gè)比特位的二進(jìn)制序列C_1×N表示，則M個(gè)環(huán)可用二維數(shù)組C_M×N表示，C_M×N中第r行第s列的比特位用c_r,s表示，其中1≤r≤M，1≤s≤N，第r個(gè)環(huán)上不包含拓?fù)渚W(wǎng)絡(luò)中第s個(gè)節(jié)點(diǎn)用c_r,s＝0表示，第r個(gè)環(huán)上包含拓?fù)渚W(wǎng)絡(luò)中第s個(gè)節(jié)點(diǎn)用c_r,s＝1表示；

(2)對環(huán)組集合G進(jìn)行初始化：對環(huán)組集合G中u個(gè)二維數(shù)組C_M×N的每一個(gè)比特位c_r,s隨機(jī)賦0或1，得到初始化后環(huán)組集合G⁰；

(3)判斷初始化后環(huán)組集合G⁰中的每一個(gè)環(huán)組g_q是否不跨環(huán)，實(shí)現(xiàn)方法為：

3a)設(shè)每一位二進(jìn)制數(shù)值為d_i,j的跨環(huán)檢測數(shù)組D_N×N，其中i代表跨環(huán)檢測數(shù)組D_N×N行序號，j代表跨環(huán)檢測數(shù)組D_N×N的列序號，且1≤i≤N，1≤j≤N，當(dāng)i≠j時(shí)，根據(jù)d_i,j對應(yīng)的多環(huán)網(wǎng)絡(luò)拓?fù)渲械耐ㄐ殴?jié)點(diǎn)對(i,j)中的節(jié)點(diǎn)i和節(jié)點(diǎn)j是否直接互連給d_i,j賦值，若是，對d_i,j賦1，否則，對d_i,j賦0，當(dāng)i＝j(luò)時(shí)，對d_i,j賦1，得到賦值后的跨環(huán)檢測數(shù)組D'_N×N；

3b)根據(jù)賦值后的跨環(huán)檢測數(shù)組D'_N×N中的二進(jìn)制數(shù)值d_i,j是否存在0，判斷初始化后環(huán)組集合G⁰中的所有環(huán)組g_q是否跨環(huán)，若是，更新跨環(huán)的環(huán)組，并執(zhí)行步驟3a)，否則，設(shè)目的環(huán)組集合用Gⁿ表示，將初始化環(huán)組集合G⁰賦給目的環(huán)組集合Gⁿ，并執(zhí)行步驟(4)，其中n表示初始值為0的更新次數(shù)；

(4)計(jì)算目的環(huán)組集合Gⁿ中所有環(huán)組的網(wǎng)絡(luò)擁塞因子P_network1,P_network2,P_network3,...,P_networkq,...,P_networku，實(shí)現(xiàn)步驟為：

4a)計(jì)算環(huán)組g_q中的L條鏈路的鏈路占用率p₁,p₂,p₃,...,p_l,...,p_L：

查找環(huán)組g_q中連通通信節(jié)點(diǎn)對(i,j)的環(huán)的數(shù)量t_i,j，根據(jù)波導(dǎo)的雙向通信特性，推導(dǎo)出通信節(jié)點(diǎn)對(i,j)的路徑數(shù)為2t_i,j，通信節(jié)點(diǎn)對(i,j)以均勻概率選擇通信路徑，得到通信節(jié)點(diǎn)對(i,j)對2t_i,j個(gè)路徑上的每條鏈路施加的占用概率并利用占用概率計(jì)算環(huán)組g_q的L條鏈路的鏈路占用率p₁,p₂,p₃,...,p_l,...,p_L，其中，1≤i≤N，1≤j≤N，且i≠j，p_l代表第l條鏈路的鏈路占用率，計(jì)算公式為：

其中，l代表環(huán)組g_q的鏈路的序號，H表示鏈路l所在環(huán)R_r的節(jié)點(diǎn)數(shù)目，x,y表示在環(huán)R_r上的節(jié)點(diǎn)序號，且x≠y，對環(huán)組g_q的L條鏈路計(jì)算上式可得出環(huán)組g_q的L條鏈路的鏈路占用率p_l；

4b)根據(jù)鏈路占用率p₁,p₂,p₃,...,p_l,...,p_L，計(jì)算環(huán)組g_q的平均占用概率P_averageq，得到目的環(huán)組集合Gⁿ中u個(gè)環(huán)組的平均占用概率P_average1,P_average2,...,P_averageq,...,P_averageu，并按照從小到大的順序，對目的環(huán)組集合Gⁿ中u個(gè)環(huán)組的平均占用概率P_average1,P_average2,...,P_averageq,...,P_averageu進(jìn)行排序，得到平均占用概率排序E₁,E₂,E₃,...,E_q,...,E_u；

4c)根據(jù)步驟4a)求得的鏈路占用率p₁,p₂,p₃,...,p_l,...,p_L和步驟4b)求得的平均占用概率P_average1,P_average2,...,P_averageq,...,P_averageu，計(jì)算環(huán)組g_q的鏈路占用概率方差得目的環(huán)組集合Gⁿ中u個(gè)環(huán)組的鏈路占用概率方差并按照從小到大的順序，對目的環(huán)組集合Gⁿ中u個(gè)環(huán)組的鏈路占用概率方差進(jìn)行排序，得到占用概率方差排序F₁,F₂,F₃,...,F_q,...,F_u；

4d)根據(jù)步驟4b)求得的平均占用概率排序E₁,E₂,E₃,...,E_q,...,E_u和步驟4c)求得的占用概率方差排序F₁,F₂,F₃,...,F_q,...,F_u，計(jì)算目的環(huán)組集合Gⁿ中所有環(huán)組的網(wǎng)絡(luò)擁塞因子P_network1,P_network2,P_network3,...,P_networkq,...,P_networku，第q個(gè)環(huán)組的網(wǎng)絡(luò)擁塞因子P_networkq的計(jì)算公式為：

P_networkq＝αE_q+(1-α)F_q

其中α為可調(diào)參數(shù)，取值為0.5；

(5)按照目的環(huán)組集合Gⁿ中所有環(huán)組的網(wǎng)絡(luò)擁塞因子P_network1,P_network2,P_network3,...,P_networkq,...,P_networku從小到大的順序，對網(wǎng)絡(luò)擁塞因子P_network1,P_network2,P_network3,...,P_networkq,...,P_networku對應(yīng)的目的環(huán)組集合Gⁿ中的所有環(huán)組進(jìn)行排序，得到排序后的環(huán)組g₁,g₂,g₃,...g_q,...,g_u，并選出前2N個(gè)環(huán)組g₁,g₂,...,g_q,...,g_2N；

(6)對前2N個(gè)環(huán)組g₁,g₂,...,g_q,...,g_2N進(jìn)行優(yōu)化更新，得到目的環(huán)組集合Gⁿ，實(shí)現(xiàn)步驟為：

6a)將前2N個(gè)環(huán)組g₁,g₂,...,g_q,...,g_2N進(jìn)行兩兩隨機(jī)配對，得到N對環(huán)組v₁,v₂,...,v_w,...,v_N，其中w為環(huán)組對的序號；

6b)對N對環(huán)組v₁,v₂,...,v_w,...,v_N中的每個(gè)環(huán)組對v_w，進(jìn)行環(huán)組之間的比特串交換，得到交叉互換后的2N個(gè)環(huán)組g′₁,g'₂,...,g'_q,...,g'_2N；

6c)隨機(jī)查找交叉互換后的2N個(gè)環(huán)組g′₁,g'₂,...,g'_q,...,g'_2N中的每個(gè)環(huán)組g'_q對應(yīng)的二維數(shù)組C_M×N中的1個(gè)比特位c_r,s，若c_r,s＝1，對c_r,s賦0，若c_r,s＝0，對c_r,s賦1，得到隨機(jī)置換后的2N個(gè)環(huán)組g″₁,g″₂,...,g″_q,...,g″_2N；

6d)判斷隨機(jī)置換后的2N個(gè)環(huán)組g″₁,g″₂,...,g″_q,...,g″_2N是否跨環(huán)，若是，執(zhí)行步驟6a)，否則，將前2N個(gè)環(huán)組g₁,g₂,...,g_q,...,g_2N與隨機(jī)置換后的2N個(gè)環(huán)組g″₁,g″₂,...,g″_q,...,g″_2N合并，將更新次數(shù)n加1，得到目的環(huán)組集合Gⁿ；

(7)判斷目的環(huán)組集合Gⁿ的更新次數(shù)n是否小于設(shè)定的優(yōu)化更新門限值T，若是，執(zhí)行步驟(4)，否則，計(jì)算目的環(huán)組集合Gⁿ中4N個(gè)環(huán)組的網(wǎng)絡(luò)擁塞因子P_network1,P_network2,P_network3,...,P_network4N，得到擁塞概率因子最小的環(huán)組g_min，實(shí)現(xiàn)光片上網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的設(shè)計(jì)。