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

有效

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

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

本發(fā)明屬于網(wǎng)絡(luò)通信計(jì)算領(lǐng)域，涉及一種組播路由方法，可用于提高因特網(wǎng)的服務(wù)質(zhì)量。

背景技術(shù)

從上個(gè)世紀(jì)末到本世紀(jì)初是網(wǎng)絡(luò)技術(shù)大發(fā)展的時(shí)代，特別是以因特網(wǎng)為代表的IP網(wǎng)絡(luò)更是日新月異。因特網(wǎng)上的用戶數(shù)量持續(xù)呈爆炸性增長(zhǎng)，網(wǎng)上的應(yīng)用由傳統(tǒng)的電子郵件轉(zhuǎn)向FTP、WWW等應(yīng)用。此外，基于因特網(wǎng)的新應(yīng)用和業(yè)務(wù)也在不斷地推出，如電子商務(wù)、IP電話、視頻會(huì)議等。但是，要滿足這些業(yè)務(wù)的需求，特別是要保證一些實(shí)時(shí)業(yè)務(wù)的帶寬、時(shí)延等特殊需求，以目前因特網(wǎng)中的盡力而為的服務(wù)是難于完成的。盡力而為服務(wù)的特點(diǎn)是對(duì)所有應(yīng)用提供同種數(shù)據(jù)傳輸服務(wù)，對(duì)網(wǎng)絡(luò)的資源缺乏有效的分配和管理，當(dāng)網(wǎng)絡(luò)負(fù)載較輕時(shí)，各個(gè)應(yīng)用得到的傳輸服務(wù)質(zhì)量尚可，但是隨著用戶數(shù)目的增多，網(wǎng)絡(luò)的負(fù)載也將增加，此時(shí)，各種應(yīng)用的行為表現(xiàn)為無(wú)序地競(jìng)爭(zhēng)網(wǎng)絡(luò)資源，造成網(wǎng)絡(luò)資源的不合理占用各種應(yīng)用各為其利，其結(jié)果是服務(wù)質(zhì)量互相惡化。目前的因特網(wǎng)技術(shù)急需進(jìn)行改進(jìn)以提供有效的資源分配與管理。如前所述的網(wǎng)絡(luò)應(yīng)用，如視頻會(huì)議、交互式游戲、聲音/視頻電話、實(shí)時(shí)多媒體播放、分布式計(jì)算、視頻點(diǎn)播和遠(yuǎn)程教學(xué)等網(wǎng)絡(luò)應(yīng)用的特點(diǎn)是涉及多個(gè)成員的交互，本質(zhì)上具有組播的特征。

KPP是較早提出的一個(gè)時(shí)延受限組播路由方法，它借鑒了KMB方法的思想，首先構(gòu)造一個(gè)只包含源節(jié)點(diǎn)和目的節(jié)點(diǎn)集合的完全圖，這個(gè)完全圖中的每條邊對(duì)應(yīng)原圖中兩個(gè)節(jié)點(diǎn)之間滿足時(shí)延約束的費(fèi)用最短路：然后從完全圖中產(chǎn)生一個(gè)時(shí)延受限生成樹(shù)；最后將生成樹(shù)的邊用原圖中的時(shí)延受限最小費(fèi)用路徑代替，并去掉產(chǎn)生的回路。這種方法的缺點(diǎn)是：復(fù)雜度高；當(dāng)解存在時(shí)，它可能會(huì)找不到最優(yōu)解。

BSMA方法是對(duì)KPP方法的一種改進(jìn)，它采用先找到問(wèn)題的可行解，然后對(duì)可行解進(jìn)行改進(jìn)，使其性能更加接近最優(yōu)解的方法，具體過(guò)程是：先用LD方法生成組播樹(shù)；然后用費(fèi)用更小的且滿足時(shí)延要求的超邊代替生成樹(shù)中費(fèi)用較大的?超邊，在替換費(fèi)用高的超邊時(shí)用到了k最短路徑方法，其中超邊是指一條起始和中止節(jié)點(diǎn)都為度大于或等于2的節(jié)點(diǎn)的一條路徑，超邊也可以是兩個(gè)目的節(jié)點(diǎn)之間的一條路徑，或者是一條度大于2的節(jié)點(diǎn)和目的節(jié)點(diǎn)之間的一條路徑；反復(fù)進(jìn)行這一步驟，直到整個(gè)生成樹(shù)的費(fèi)用不能再減小為止。該方法的缺點(diǎn)是求解過(guò)程復(fù)雜，不適用于優(yōu)化大規(guī)模網(wǎng)絡(luò)。

最近幾年提出的基于遺傳方法的解決組播路由的方法，雖然比經(jīng)典方法加強(qiáng)了全局搜索能力，但是它容易陷入“早熟”，很難得到最優(yōu)組播樹(shù)。而基于人工免疫理論解決組播路由的方法，需要通過(guò)不斷的科隆種群才能夠保持種群的多樣性，得到最優(yōu)組播樹(shù)，但這樣使得方法的時(shí)效性大大降低。

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

本發(fā)明的目的在于克服已有技術(shù)的不足，提出一種基于量子進(jìn)化的組播路由方法，以減小求解組播樹(shù)時(shí)間，獲得較小的組播樹(shù)代價(jià)，降低運(yùn)算法雜度，提高網(wǎng)絡(luò)的時(shí)效性。

實(shí)現(xiàn)本發(fā)明的技術(shù)思路是：將組播路由問(wèn)題看作組合優(yōu)化問(wèn)題，用量子計(jì)算搜索使組播樹(shù)代價(jià)最小化的序列組合作為最優(yōu)解；利用量子計(jì)算快速的全局收斂性，搜索構(gòu)成組播樹(shù)問(wèn)題的最優(yōu)解，逼近最優(yōu)組播樹(shù)服務(wù)的性能。具體實(shí)現(xiàn)步驟如下：

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

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

(3)對(duì)每個(gè)目的節(jié)點(diǎn)的前2^N條(N∈[1，4])備選路徑集進(jìn)行量子編碼，獲得一個(gè)狀態(tài)矩陣；