[發(fā)明專利]一種基于遺傳算法的光多播樹最小代價(jià)路由方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201310606366.9
• 申請(qǐng)日: 2013-11-25
• 公開（公告）號(hào): CN103685020B
• 公開（公告）日: 2017-07-28
• 發(fā)明（設(shè)計(jì)）人: 劉煥淋;秦亮;陳高翔;代洪躍;徐一帆
• 申請(qǐng)（專利權(quán)）人: 重慶郵電大學(xué)
• 主分類號(hào): H04L12/721
• 分類號(hào): H04L12/721;H04L12/761
• 代理公司: 重慶市恒信知識(shí)產(chǎn)權(quán)代理有限公司50102
• 代理人: 劉小紅

技術(shù)領(lǐng)域

本發(fā)明涉及通信技術(shù)領(lǐng)域，具體涉及一種基于遺傳算法的光多播樹最小代價(jià)路由方法。

背景技術(shù)

隨著視頻會(huì)議、網(wǎng)絡(luò)電視、多媒體遠(yuǎn)程教育等多播業(yè)務(wù)的快速發(fā)展，網(wǎng)絡(luò)帶寬的消耗以及擁塞發(fā)生的快速增加，傳統(tǒng)通信網(wǎng)正面臨著帶寬資源不足、網(wǎng)絡(luò)吞吐量低、業(yè)務(wù)阻塞率上升等嚴(yán)重的問(wèn)題，網(wǎng)絡(luò)的資源日趨緊張。由于光網(wǎng)絡(luò)具有高帶寬和高速率的信息傳輸能力，其暫時(shí)解決了傳統(tǒng)電域網(wǎng)絡(luò)中帶寬資源不足等問(wèn)題。不過(guò)，近年來(lái)隨著寬帶業(yè)務(wù)和多播應(yīng)用的持續(xù)快速增長(zhǎng)，光網(wǎng)絡(luò)再次面臨帶寬資源不足、網(wǎng)絡(luò)阻塞率持續(xù)增高等諸多問(wèn)題。網(wǎng)絡(luò)編碼有提高網(wǎng)絡(luò)吞吐量、均衡網(wǎng)絡(luò)負(fù)載、增加網(wǎng)絡(luò)帶寬利用率、減少網(wǎng)絡(luò)資源損耗、提高網(wǎng)絡(luò)安全性、減少能量消耗等優(yōu)點(diǎn)，因而，基于網(wǎng)絡(luò)編碼的路由方式越來(lái)越受到研究者的重視。將網(wǎng)絡(luò)編碼引入到光網(wǎng)絡(luò)中，利用網(wǎng)絡(luò)編碼的優(yōu)點(diǎn)來(lái)解決光網(wǎng)絡(luò)帶寬資源不足等問(wèn)題不失為一個(gè)有效的方法。因此，我們提出一種單源多宿最小代價(jià)多播樹的構(gòu)造方法解決最小代價(jià)光多播樹路由選擇問(wèn)題。

不同于傳統(tǒng)的路由方式，基于網(wǎng)絡(luò)編碼的路由方式不僅允許網(wǎng)絡(luò)的中間節(jié)點(diǎn)對(duì)收到的信息進(jìn)行存儲(chǔ)和轉(zhuǎn)發(fā)，還能進(jìn)行信息編碼壓縮操作。基于網(wǎng)絡(luò)編碼構(gòu)造光多播樹路由一般包括2個(gè)步驟：(1)確定網(wǎng)絡(luò)目的節(jié)點(diǎn)的信息接收速率；(2)根據(jù)目的節(jié)點(diǎn)的信息接收速率為每個(gè)目的節(jié)點(diǎn)確定邊分離路徑數(shù)目。為了使網(wǎng)絡(luò)目的節(jié)點(diǎn)正確的解碼出原始信息，所有目的節(jié)點(diǎn)接收速率相同，該速率一般小于等于所有目的節(jié)點(diǎn)的最大流中的最小值。但是，在通信網(wǎng)絡(luò)的中間節(jié)點(diǎn)進(jìn)行網(wǎng)絡(luò)編碼操作，將會(huì)增加通信網(wǎng)絡(luò)相應(yīng)的開銷和代價(jià)，如：增加中間節(jié)點(diǎn)計(jì)算的復(fù)雜度；增加緩存器的需求量，用于儲(chǔ)存解碼輸入邊的信息；帶來(lái)網(wǎng)絡(luò)時(shí)延增加等。因而，本申請(qǐng)的最小代價(jià)多播樹是尋找滿足光多播路由所需鏈路數(shù)目總和最少、編碼操作次數(shù)最少的一種信息傳輸方法。

現(xiàn)在研究證明：最小代價(jià)光多播樹是一個(gè)NP-complete問(wèn)題，目前的解決方法大部分是采用啟發(fā)式算法來(lái)解決這一問(wèn)題。但是，現(xiàn)有啟發(fā)式算法一般在特定網(wǎng)絡(luò)中效果較好，而在其他的網(wǎng)絡(luò)中效果卻不理想，而智能優(yōu)化算法在解決NP-complete問(wèn)題時(shí)，效果將會(huì)優(yōu)于啟發(fā)式算法，遺傳算法是智能優(yōu)化算法中較為成熟的一種算法。因此，我們提出一種基于遺傳算法的光多播樹最小代價(jià)路由方法。

發(fā)明內(nèi)容

針對(duì)以上現(xiàn)有技術(shù)中的不足，本發(fā)明的目的在于提供一種可以明顯地提高光網(wǎng)絡(luò)的帶寬資源利用率，減少網(wǎng)絡(luò)編碼操作次數(shù)的基于遺傳算法的光多播樹最小代價(jià)路由方法。本發(fā)明的技術(shù)方案如下：一種基于遺傳算法的光多播樹最小代價(jià)路由方法,其包括以下步驟：

101、獲取網(wǎng)絡(luò)拓?fù)銰（V，E），其中V表示網(wǎng)絡(luò)拓?fù)銰的節(jié)點(diǎn)集，E表示網(wǎng)絡(luò)中節(jié)點(diǎn)之間的連接邊，當(dāng)連接邊的容量n≥2時(shí)，則將該連接邊轉(zhuǎn)化為n條并列且容量為1的邊，完成初始化，跳轉(zhuǎn)至步驟102；

102、獲取步驟101中經(jīng)過(guò)初始化后網(wǎng)絡(luò)拓?fù)銰（V，E）的源節(jié)點(diǎn)S及目的節(jié)點(diǎn)集t，構(gòu)造源節(jié)點(diǎn)S到目的節(jié)點(diǎn)集t的多播樹，確定源節(jié)點(diǎn)S到目的節(jié)點(diǎn)集t的最大多播速率T，并設(shè)定目的節(jié)點(diǎn)的接收速率為k，其中1≤k≤T；獲取源節(jié)點(diǎn)S到目的節(jié)點(diǎn)t_i所有存在的N條路徑，其中目的節(jié)點(diǎn)t_i為目的節(jié)點(diǎn)集t中的一個(gè)元素，計(jì)算出該目的節(jié)點(diǎn)t_i的k條邊路徑組合的方式m_i，產(chǎn)生基因庫(kù),并采用遺傳算法構(gòu)造源節(jié)點(diǎn)S到目的節(jié)點(diǎn)集t的染色體種群,每個(gè)染色體表示網(wǎng)絡(luò)的一種路由方式,其中每個(gè)染色體由與目的節(jié)點(diǎn)的個(gè)數(shù)相等的U個(gè)基因組成，每個(gè)基因表示源節(jié)點(diǎn)S到對(duì)應(yīng)目的節(jié)點(diǎn)t_i的一種路徑；

103、構(gòu)造步驟102中染色體的適應(yīng)度函數(shù)

f=a₁*NC(R)+a₂*N_CL,且a₁>a₂

式中，f為適應(yīng)度函數(shù)值；NC(R)為滿足多播請(qǐng)求速率的多播樹的鏈路代價(jià)，N_CL為編碼鏈路數(shù)目；a₁、a₂為權(quán)重系數(shù)；

當(dāng)適應(yīng)度函數(shù)f根據(jù)遺傳算法迭代更新的次數(shù)大于或者等于設(shè)定次數(shù)N1時(shí)，則輸出該最優(yōu)染色體的路徑及適應(yīng)度函數(shù)值f，跳轉(zhuǎn)至步驟106；或當(dāng)適應(yīng)度函數(shù)f根據(jù)遺傳算法迭代更新的次數(shù)大于N2且適應(yīng)度函數(shù)值f不變時(shí)，則輸出該最優(yōu)染色體的路徑及適應(yīng)度函數(shù)值f，跳轉(zhuǎn)至步驟106，結(jié)束；否則，跳轉(zhuǎn)至步驟104；