圖論及其應(yīng)用論文

實(shí)用文檔圖論在多播生成樹快速算法的應(yīng)用摘要：為了有效地支持多播通信,路由(路徑)選擇是一個(gè)關(guān)鍵問題。路由選擇負(fù)責(zé)對源與目的結(jié)點(diǎn)間的多條可行路徑根據(jù)某種目標(biāo)加以選擇、例如網(wǎng)絡(luò)資源消耗最低化就是路由選擇的重要目標(biāo)。解決多播路由的方法涉及到“樹”的構(gòu)造,如果能構(gòu)造出合理的多播樹,就可以在滿足業(yè)務(wù)需要的前提下,盡量少占用網(wǎng)絡(luò)資源。本篇論文以圖論為基礎(chǔ)，主要探討和研究了多播生成樹問題。主要探討了單約束的單樹多播這種情況，介紹了經(jīng)典的Dijkstra算法，并在此基礎(chǔ)上提出了動(dòng)態(tài)最短路徑樹算法。關(guān)鍵詞:圖論路由最短路徑多播樹Dijkstra算法1.多播生成樹問題的提出隨著Internet的爆炸性發(fā)展，在Internet上產(chǎn)生了許多新的應(yīng)用，其中有很多是高帶寬的多媒體應(yīng)用，這就帶來了帶寬的急劇消耗和網(wǎng)絡(luò)擁擠問題。為了緩解這一問題，人們提出了IP多播技術(shù)。多播技術(shù)是一種允許一個(gè)或多個(gè)發(fā)送者（多播源）發(fā)送單一的數(shù)據(jù)包到多個(gè)接收者的網(wǎng)絡(luò)技術(shù)。該技術(shù)有助于緩解當(dāng)前Internet上膨脹的業(yè)務(wù)量而導(dǎo)致的擁塞問題。為了有效地支持多播通信,路由(或路徑)選擇是一個(gè)需要討論的關(guān)鍵問題。路由選擇負(fù)責(zé)對源與目的結(jié)點(diǎn)間的多條可行路徑根據(jù)某種目標(biāo)加以選擇。路由選擇算法是計(jì)算機(jī)網(wǎng)絡(luò)中的一個(gè)重要研究課題,它直接關(guān)系到網(wǎng)絡(luò)效率、傳輸延遲和吞吐量等通信網(wǎng)絡(luò)的主要技術(shù)性能指標(biāo)。路由選擇算法的設(shè)計(jì)一般包括以下內(nèi)容:首先對一個(gè)網(wǎng)絡(luò)的鏈路進(jìn)行準(zhǔn)確描述,定義鏈路代價(jià)函數(shù)(一般可由信道容量、信道利用率或報(bào)文延遲時(shí)間這幾種因素確定),計(jì)算最短路徑,建立路由選擇表或路由數(shù)據(jù)庫。根據(jù)網(wǎng)絡(luò)拓?fù)浜妥泳W(wǎng)款式選擇適當(dāng)算法,并設(shè)計(jì)出實(shí)現(xiàn)算法的過程,模擬測試和運(yùn)行。其中計(jì)算最短路徑是整個(gè)設(shè)計(jì)過程中較為關(guān)鍵的一環(huán)。多播路由選擇要保證實(shí)現(xiàn)的目標(biāo)是,數(shù)據(jù)能夠到達(dá)所有的接收者。同時(shí),在整個(gè)通信網(wǎng)絡(luò)的任何一條鏈路上數(shù)據(jù)最多傳送一次。在一條鏈路上是否傳輸數(shù)據(jù)依賴于此鏈路上是否有該數(shù)據(jù)的接收者。多播之所以能節(jié)約帶寬,就是因?yàn)樵诰W(wǎng)絡(luò)的任何一條鏈路上數(shù)據(jù)最多傳送一次。要實(shí)現(xiàn)這個(gè)目標(biāo),多播的傳輸就不能像單播一樣點(diǎn)到點(diǎn)地傳輸,而要采用樹的傳輸方式。一般采用多播生成樹來描述多播數(shù)據(jù)包在網(wǎng)絡(luò)中經(jīng)過的路徑。將多播路徑基于樹結(jié)構(gòu)有兩點(diǎn)理由:(1)信息可以沿著樹枝并行地傳送到不同的目的地;(2)僅在樹叉處復(fù)制信息,傳送信息的拷貝數(shù)最小,從而使網(wǎng)絡(luò)流量最低,占用的網(wǎng)絡(luò)資源最少。多播樹的質(zhì)量評價(jià)一般有兩個(gè)尺度,最短路徑和最小代價(jià)。最短路徑和最小代價(jià)可以被表述為不同的函數(shù),如最小代價(jià)可以表述為使用緩沖區(qū)的數(shù)量、占用信道的所需交納的費(fèi)用,包丟失率等;最短路徑可以表述為傳輸、處理、排隊(duì)時(shí)延的結(jié)合。多播生成樹算法沿著優(yōu)化這兩個(gè)尺度(最短路徑和最小代價(jià))的方向,己經(jīng)有了很大的發(fā)展。2.多播生成樹問題的圖論基礎(chǔ)2.1.樹給定一個(gè)圖G=(V,E),如果它不含任何回路,我們就叫它是林,如果G又是連通的,即這個(gè)林只有一個(gè)連通支,就稱它是樹。樹是圖論中最重要的概念之一,在自然和社會(huì)科學(xué)中的許多領(lǐng)域都有廣泛的應(yīng)用。定義1一個(gè)不含任何回路的連通圖稱為樹,用T表示。T中的邊稱為樹枝,度為1的結(jié)點(diǎn)稱為樹葉。樹的每條邊都不會(huì)屬于任何回路。這樣的邊叫割邊。定義2設(shè)e是圖G的一條邊,若G`=G-e比G的連通支數(shù)增加,則稱e是G的一條割邊。顯然,圖G刪去割邊=e（u,v)之后,結(jié)點(diǎn)u和v分屬于不同的連通支。定理1e=(u,v)是割邊,當(dāng)且僅當(dāng)e不屬于G的任何回路。定理2設(shè)T是結(jié)點(diǎn)數(shù)為n≥2的樹,則下列性質(zhì)等價(jià):1.T連通且無回路。2.T連通且每條邊都是割邊。3.T連通且有n-1條邊。4.T有n-1條邊且無回路。5.T的任意兩結(jié)點(diǎn)間有唯一道路。6.T無回路,但在任兩結(jié)點(diǎn)間加上一條邊后恰有一個(gè)回路.定理3樹T中一定存在樹葉結(jié)點(diǎn)。定義3如果T是圖G的支撐子圖,而且又是一棵樹,則稱r是G的一棵支撐樹,或稱生成樹,又簡稱為G的樹。2.2.多播網(wǎng)絡(luò)模型為簡化對問題的討論,我們通常將一個(gè)通信網(wǎng)絡(luò)表示為一個(gè)帶權(quán)無向圖G=(V，E，C)，其中V代表網(wǎng)絡(luò)中結(jié)點(diǎn)(Node)的集合;E是一組邊(edge)的集合,|V|和|E|分別代表結(jié)點(diǎn)和邊的數(shù)目。每條邊用對應(yīng)的兩個(gè)結(jié)點(diǎn)u,v來表示:(u,v)一對結(jié)點(diǎn)對應(yīng)的兩條邊u(,v)和(v,u)費(fèi)用相等,即這兩條邊對稱;C是各邊對應(yīng)費(fèi)用(cost)的集合。圖G中結(jié)點(diǎn)v的度(degree)是指與v關(guān)聯(lián)的邊的條數(shù)。在多播網(wǎng)絡(luò)中數(shù)據(jù)包由源結(jié)點(diǎn)s∈V生成,并發(fā)送給所有的多播組成員,多播組成員結(jié)點(diǎn)他稱為端結(jié)點(diǎn))的集合M?V。由無向圖G=(V,E,C)中生成一棵有向樹T=(V1)Vt?V,2)源結(jié)點(diǎn)s到每一個(gè)端結(jié)點(diǎn)都有通路,并且s的入度為0。,樹中其余結(jié)點(diǎn)的入度為1。3)端結(jié)點(diǎn)的出度大于或等于0,其余結(jié)點(diǎn)的出度均大于或等于1。一棵多播樹T的總費(fèi)用是指樹T中各邊費(fèi)用之和。定義1最小代價(jià)多播生成樹是所有生成樹中,總費(fèi)用最小的生成樹。多播樹中源結(jié)點(diǎn)s和端結(jié)點(diǎn)M以外的結(jié)點(diǎn)稱為Steiner結(jié)點(diǎn)。定義2最短路徑:結(jié)點(diǎn)u,v?V之間的最短路徑是指從u到v代價(jià)最小的路徑,用P(u,v)表示。結(jié)點(diǎn)u到樹的最短路徑是指該結(jié)點(diǎn)到樹的各結(jié)點(diǎn)最短路徑中代價(jià)最小的那條,該路徑用PS(u,v)表示(u∈V?定義3最短路徑(最小時(shí)延)多播生成樹是所有生成樹中,源結(jié)點(diǎn):到所有端結(jié)點(diǎn)的路徑都是最短路徑的生成樹。即在給定的帶權(quán)無向圖G=(V,E,C)中,G的關(guān)于結(jié)點(diǎn)s的最短路徑樹是具有以下性質(zhì)的G的一個(gè)子圖T=(V1V=V'2T是連通且無回路的。結(jié)點(diǎn)s到T中的其余結(jié)點(diǎn)(即V-s)的路徑都是帶權(quán)無向圖G中的最短路徑。定義4路徑結(jié)點(diǎn):結(jié)點(diǎn)u(u∈V?Vt定義5衛(wèi)星結(jié)點(diǎn):在生成樹中,一個(gè)端結(jié)點(diǎn)與鄰近端結(jié)點(diǎn)之間的Steiner結(jié)點(diǎn)稱為該端結(jié)點(diǎn)的衛(wèi)星結(jié)點(diǎn)。3.多播生成樹基本算法構(gòu)建最短路徑樹和最小生成樹在圖論中最基本的算法是Dijkstra算法和Prim算法,這兩個(gè)經(jīng)典算法幾乎是所有其他單約束的單樹多播算法的源泉和理論基礎(chǔ)，本文主要介紹了Dijkstra算法。Dijkstra算法給定個(gè)一個(gè)帶權(quán)無向圖G=(V，E，C),源結(jié)點(diǎn)為s,構(gòu)建最短路徑樹可以采用圖論中的Dijkstra算法實(shí)現(xiàn)。Dijkstra是解決關(guān)于帶權(quán)圖的最短路徑問題的一種貪心算法,它要一個(gè)個(gè)地找出從源結(jié)點(diǎn)(s)出發(fā)到所有其他結(jié)點(diǎn)的最短路徑。Dijkstra算法的本質(zhì)特征是能夠確定路徑順序,按照加權(quán)長度順序首先找出最短路徑,直至最后找出從源結(jié)點(diǎn)到所有結(jié)點(diǎn)的最短路徑中最長的那一條最短路徑。首先,引進(jìn)一個(gè)輔助向量D,它的每個(gè)分量D[i]表示當(dāng)前所找到的從源點(diǎn)s到每個(gè)終點(diǎn)vi的最短路徑的長度。它的初態(tài)為:若從s到vi有弧,則D[i]為弧上的權(quán)值;否則置D[i]為∞D(zhuǎn)j的路徑就是從s出發(fā)長度最短的一條最短路徑。此路徑為(s,vj假設(shè)改次最短路徑的終點(diǎn)是vk,則可想而知,這條路徑或者是(s,vk),或者是(s,vj,vk)一般情況下,假設(shè)T為已求得最短路徑的終點(diǎn)的集合,則可證明:下一條最短路徑(設(shè)其終點(diǎn)為x)或者是弧(v,x),或者是中間只經(jīng)過T中的頂點(diǎn)而最后到達(dá)頂點(diǎn)x的路徑。在一般情況下,下一條長度次短的最短路徑的是Dj其中,Di或者是弧(s,vi)上的權(quán)值,或者是D[k](根據(jù)以上分析,可以得到如下描述的算法:(1)設(shè)用帶權(quán)的鄰接矩陣arcs來表示帶權(quán)圖,arcs[i][j]表示弧(vk,vj)上的權(quán)值。若(vi,vDi(2)選擇vj,使得Djvj就是當(dāng)前求得的一條從s出發(fā)的最短路徑的終點(diǎn)。令T=T∪{j}(3)修改從s出發(fā)到集合V-T上任一頂點(diǎn)vk可達(dá)的最短路徑的長度。如果Dj則修改D[k]為Dk(4)重復(fù)操作(2)、(3)共n-1次。由此求得從s到圖上其余各頂點(diǎn)的最短路徑是依路徑長度遞增的序列。4.網(wǎng)絡(luò)最短路徑的動(dòng)態(tài)算法(DMDT)通信網(wǎng)絡(luò)中,一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)最短路徑的計(jì)算是許多路由算法的基礎(chǔ),該算法的優(yōu)劣直接關(guān)系到最終路由選擇的成敗和優(yōu)劣,對整個(gè)網(wǎng)絡(luò)的性能有重要的影響。目前一般采用Dijkstra算法計(jì)算網(wǎng)絡(luò)中點(diǎn)到點(diǎn)的最短路徑。作為一種靜態(tài)算法,Dijkstra算法無疑是現(xiàn)有算法中最優(yōu)的。但當(dāng)網(wǎng)絡(luò)環(huán)境動(dòng)態(tài)變化時(shí),若仍然采用Dijkstra算法重新計(jì)算最短路徑,會(huì)帶來以下兩方面的問題:一是計(jì)算復(fù)雜性較高,浪費(fèi)大量的CPU時(shí)間。二是由于網(wǎng)絡(luò)中有可能存在費(fèi)用相同的兩條或兩條以上最短路徑。完全重新計(jì)算有可能帶來不必要的網(wǎng)絡(luò)路由變化,使路由器頻繁改變其路由表,造成網(wǎng)絡(luò)狀態(tài)的不穩(wěn)定。針對動(dòng)態(tài)變化的網(wǎng)絡(luò)環(huán)境,可以對Dijkstar算法進(jìn)行改進(jìn),提出一種快速的動(dòng)態(tài)最短路徑算法DMDT。隨機(jī)網(wǎng)絡(luò)模型的仿真結(jié)果表明,用DMDT算法計(jì)算得到的最短路徑與Dijkstra算法相同,但它計(jì)算所需的時(shí)間大大低于Dijkstra算法,其時(shí)間復(fù)雜度一般為O(mn),其中n為網(wǎng)絡(luò)中結(jié)點(diǎn)數(shù),m一般遠(yuǎn)小于n。DMDT算法所得到的最短路徑樹相對穩(wěn)定,最大程度的利用了網(wǎng)絡(luò)環(huán)境變化前已計(jì)算的最短路徑樹,避免了網(wǎng)絡(luò)中路由表的頻繁變化,使網(wǎng)絡(luò)處于不穩(wěn)定的狀態(tài)。動(dòng)態(tài)最短路徑算法的基本過程如下:(1)判斷帶權(quán)無向圖G=(V，E，C)中費(fèi)用變化的邊Ai是否是原來最短路徑樹上的邊,如果Ai是原來最短路徑樹上的邊則將邊Ai(2)如果邊Ai的費(fèi)用Ci變大,則把結(jié)點(diǎn)u及其所有子孫結(jié)點(diǎn)記為集合T2,帶權(quán)無向G=(V，E，C)中其余的結(jié)點(diǎn)(V?T如果邊Ai的費(fèi)用Ci變小,則把結(jié)點(diǎn)u及其所有子孫結(jié)點(diǎn)和源結(jié)點(diǎn)、到結(jié)點(diǎn)s的最短路徑上的結(jié)點(diǎn)(包括源結(jié)點(diǎn))s記為集合不,帶權(quán)無向圖G=(V，E，C)中其余的結(jié)點(diǎn)(V?T1(3)如果邊Ai的費(fèi)用Ci(4)如果邊Ai的費(fèi)用Ci變小,記為Ci'(Ci>Ci'),另記在原最短路徑樹上u到源結(jié)點(diǎn)s的最短路徑的值為Disu,v到源結(jié)點(diǎn)s的最短路徑的值為Disv。如果Disu(5)如果(Disu?Disv?Ci')的值大于(Disv?Disu?Ci')的值,則把結(jié)點(diǎn)u的父結(jié)點(diǎn)指向v,同時(shí)把結(jié)點(diǎn)u及其所有子孫結(jié)點(diǎn)和源結(jié)點(diǎn)s到結(jié)點(diǎn)v的最短路徑上的結(jié)點(diǎn)(包括源結(jié)點(diǎn)s和結(jié)點(diǎn)v)記為集合T1,帶權(quán)無向圖G=(V，E，C)中其余的結(jié)點(diǎn)(V?T1(6)記集合T1,中各點(diǎn)為T1i,T2[i]到源結(jié)點(diǎn)的最短路徑的值為DisT1i,用Acrs[u][v]表示結(jié)點(diǎn)u到v直接連接的費(fèi)用,如果結(jié)點(diǎn)u和v并不直接連接,則置arcs[u][v]為無窮大。記集合T2中各點(diǎn)為如果T2中的T2[j]與T1中的所有點(diǎn)都不直接連接,則DsiT2[j]記為無窮大。否則DisT2[j]=min{arcs[T2(7)選擇集合T2中DisT2[j]最小的結(jié)點(diǎn),記為T2j,修改T2j的父結(jié)點(diǎn)為DisT2[j],在T1中對應(yīng)的結(jié)點(diǎn),將結(jié)點(diǎn)T2j加入集合不中,結(jié)點(diǎn)T2j結(jié)點(diǎn)的最短路徑的值結(jié)為DisT2[j]DisT則DisT2j>arcs[Dijkstra算法的時(shí)間復(fù)雜度是O(n2),DMDT算法的時(shí)間復(fù)雜度為0(nk),k為生成樹中可能改變的結(jié)點(diǎn)個(gè)數(shù),在最壞情況下,k=n-1,但在實(shí)際應(yīng)用中,最壞情況幾乎不可能出現(xiàn),一般情況下,k遠(yuǎn)遠(yuǎn)小于n,相