[發(fā)明專利]基于量子進化的組播路由優(yōu)化方法

有效

• 申請?zhí)枺?/td>: 200910022289.6
• 申請日: 2009-04-30
• 公開（公告）號: CN101616074A
• 公開（公告）日: 2009-12-30
• 發(fā)明（設(shè)計）人: 李陽陽;趙京京;焦李成;馬文萍;韓紅;吳建設(shè)
• 申請（專利權(quán)）人: 西安電子科技大學(xué)
• 主分類號: H04L12/56
• 分類號: H04L12/56;H04L12/18;H04L1/00;G06N3/12
• 代理公司: 陜西電子工業(yè)專利中心
• 代理人: 王品華;朱紅星

1.一種基于量子進化的組播路由優(yōu)化方法，包括如下步驟：

(1)生成隨機網(wǎng)絡(luò)，并在網(wǎng)絡(luò)中設(shè)置源節(jié)點、目的節(jié)點，給定運行參數(shù)和最大允許時延；

(2)對每個給定的目的節(jié)點求解所有滿足時延條件的備選路徑集，并按升序排列；

(3)對每個目的節(jié)點的前2^N條，按如下步驟備選路徑集進行量子編碼，獲得一個狀態(tài)矩陣q^t，其中N∈[1，4]：

3a)當(dāng)有m個目的節(jié)點時，計算量子比特個體編碼的長度為m×N個比特位；

3b)依次用其中N個比特位表示第m個目的節(jié)點選取的第n條路徑的狀態(tài)，得到一個量子個體的狀態(tài)矩陣為：

qt=α11tα12t...α1Nt...αm1tαm2t...αmNtβ11tβ11t...β1Nt...βm1tβm2t...βmNt,]]>

這里滿足歸一化條件|α_ij|²+|β_ij|²＝1，(i＝1，2，...，m，j＝1，2，...，N)，并且所有α_ij，β_ij都初始化為q^t表示一個在第t代量子比特個體在0和1之間的疊加狀態(tài)；

(4)對表示各個目的節(jié)點備選路徑集編碼的狀態(tài)矩陣q^t進行量子觀測，得到一組二進制串；

(5)對上述的二進制串進行解碼，得到每個目的節(jié)點所選路徑，由這些所選路經(jīng)構(gòu)成一棵組播樹，并計算該組播樹的適應(yīng)度函數(shù)；Fitness＝1/MultiTreeCost，其中MultiTreeCost是組播樹代價；

(6)對表示各個目的節(jié)點備選路徑集編碼的狀態(tài)矩陣q^t，通過量子旋轉(zhuǎn)門進行量子變異；

(7)對表示變異后的各個目的節(jié)點備選路徑集編碼的狀態(tài)矩陣進行量子觀測，得到一組新的二進制串；

(8)對新的二進制串進行解碼，得到每個目的節(jié)點新選路徑，由這些新選路經(jīng)構(gòu)成一棵組播樹，并計算該樹的適應(yīng)度函數(shù)，如果新的組播樹適應(yīng)度函數(shù)優(yōu)于步驟(5)中的適應(yīng)度函數(shù)，則采用由這些新選路經(jīng)構(gòu)成組播樹的方式作為搜索到的最優(yōu)組播樹構(gòu)建方式，否則繼續(xù)采用步驟(5)中的構(gòu)建方式作為搜索到的最優(yōu)組播樹構(gòu)建方式；

(9)判斷是否滿足終止條件，如果滿足終止條件，結(jié)束優(yōu)化并采用最終搜索到的最優(yōu)組播樹構(gòu)建方式，將信息以并行方式發(fā)送到不同的目的節(jié)點，否則，繼續(xù)執(zhí)行第(5)步。