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

1、圖論在多播生成樹快速算法的應(yīng)用摘要：為了有效地支持多播通信,路由(路徑)選擇是一個(gè)關(guān)鍵問題。路由選擇負(fù)責(zé)對(duì)源與目的結(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ā)展，在

2、Internet上產(chǎn)生了許多新的應(yīng)用，其中有很多是高帶寬的多媒體應(yīng)用，這就帶來(lái)了帶寬的急劇消耗和網(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é)對(duì)源與目的結(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)容:首先對(duì)一個(gè)網(wǎng)絡(luò)

3、的鏈路進(jìn)行準(zhǔn)確描述,定義鏈路代價(jià)函數(shù)(一般可由信道容量、信道利用率或報(bào)文延遲時(shí)間這幾種因素確定),計(jì)算最短路徑,建立路由選擇表或路由數(shù)據(jù)庫(kù)。根據(jù)網(wǎng)絡(luò)拓?fù)浜妥泳W(wǎng)款式選擇適當(dāng)算法,并設(shè)計(jì)出實(shí)現(xiàn)算法的過(guò)程,模擬測(cè)試和運(yùn)行。其中計(jì)算最短路徑是整個(gè)設(shè)計(jì)過(guò)程中較為關(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)地傳輸,而要采用樹的傳輸方式。一般采用多播生成

4、樹來(lái)描述多播數(shù)據(jù)包在網(wǎng)絡(luò)中經(jīng)過(guò)的路徑。將多播路徑基于樹結(jié)構(gòu)有兩點(diǎn)理由:(1)信息可以沿著樹枝并行地傳送到不同的目的地;(2)僅在樹叉處復(fù)制信息,傳送信息的拷貝數(shù)最小,從而使網(wǎng)絡(luò)流量最低,占用的網(wǎng)絡(luò)資源最少。多播樹的質(zhì)量評(píng)價(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),如果它不含任何回路,我們就叫它是

5、林,如果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分屬于不同的連通支。定理1 e=(u,v)是割邊,當(dāng)且僅當(dāng)e不屬于G的任何回路。定理2設(shè)T是結(jié)點(diǎn)數(shù)為n2的樹,則下列性質(zhì)等價(jià):1.T連通且無(wú)回路。2.T連通且每條邊都是割邊。3.T連通且有n-1條邊。4.T有

6、n-1條邊且無(wú)回路。5.T的任意兩結(jié)點(diǎn)間有唯一道路。6.T無(wú)回路,但在任兩結(jié)點(diǎn)間加上一條邊后恰有一個(gè)回路.定理3樹T中一定存在樹葉結(jié)點(diǎn)。定義3如果T是圖G的支撐子圖,而且又是一棵樹,則稱r是G的一棵支撐樹,或稱生成樹,又簡(jiǎn)稱為G的樹。2.2.多播網(wǎng)絡(luò)模型為簡(jiǎn)化對(duì)問題的討論,我們通常將一個(gè)通信網(wǎng)絡(luò)表示為一個(gè)帶權(quán)無(wú)向圖G=(V，E，C)，其中V代表網(wǎng)絡(luò)中結(jié)點(diǎn)(Node)的集合;E是一組邊(edge)的集合,|V|和|E|分別代表結(jié)點(diǎn)和邊的數(shù)目。每條邊用對(duì)應(yīng)的兩個(gè)結(jié)點(diǎn)u,v來(lái)表示:(u,v)一對(duì)結(jié)點(diǎn)對(duì)應(yīng)的兩條邊u(,v)和(v,u)費(fèi)用相等,即這兩條邊對(duì)稱;C是各邊對(duì)應(yīng)費(fèi)用(cost)的集合。圖G中

7、結(jié)點(diǎn)v的度(degree)是指與v關(guān)聯(lián)的邊的條數(shù)。在多播網(wǎng)絡(luò)中數(shù)據(jù)包由源結(jié)點(diǎn)sV生成,并發(fā)送給所有的多播組成員,多播組成員結(jié)點(diǎn)他稱為端結(jié)點(diǎn))的集合MV。由無(wú)向圖G=(V,E,C)中生成一棵有向樹T=(Vt,Et)若滿足以下三個(gè)條件則稱其為多播生成樹:1)VtV,EtE。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

8、 V之間的最短路徑是指從u到v代價(jià)最小的路徑,用P(u,v)表示。結(jié)點(diǎn)u到樹的最短路徑是指該結(jié)點(diǎn)到樹的各結(jié)點(diǎn)最短路徑中代價(jià)最小的那條,該路徑用PS(u,v)表示(uV-VtvVt),其中結(jié)點(diǎn)v被稱為結(jié)點(diǎn)u的最小接應(yīng)結(jié)點(diǎn)。結(jié)點(diǎn)到樹的最短路徑也被稱為樹到結(jié)點(diǎn)的最短路徑,結(jié)點(diǎn)到樹最短路徑的代價(jià)稱為結(jié)點(diǎn)到樹的最小距離。定義3最短路徑(最小時(shí)延)多播生成樹是所有生成樹中,源結(jié)點(diǎn):到所有端結(jié)點(diǎn)的路徑都是最短路徑的生成樹。即在給定的帶權(quán)無(wú)向圖G=(V,E,C)中,G的關(guān)于結(jié)點(diǎn)s的最短路徑樹是具有以下性質(zhì)的G的一個(gè)子圖T=(V',E',C')。1 V=V'。2 T是連通且無(wú)回路

9、的。結(jié)點(diǎn)s到T中的其余結(jié)點(diǎn)(即V-s)的路徑都是帶權(quán)無(wú)向圖G中的最短路徑。定義4路徑結(jié)點(diǎn):結(jié)點(diǎn)u(uV-Vt)到生成樹的最短路徑上,結(jié)點(diǎn)與最小接應(yīng)結(jié)點(diǎn)之間的Steiner結(jié)點(diǎn)稱為該結(jié)點(diǎn)的路徑結(jié)點(diǎn)。定義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)無(wú)向圖G=(V，E，C),源結(jié)點(diǎn)為s,構(gòu)建最短路徑樹可以采用圖論

10、中的Dijkstra算法實(shí)現(xiàn)。Dijkstra是解決關(guān)于帶權(quán)圖的最短路徑問題的一種貪心算法,它要一個(gè)個(gè)地找出從源結(jié)點(diǎn)(s)出發(fā)到所有其他結(jié)點(diǎn)的最短路徑。Dijkstra算法的本質(zhì)特征是能夠確定路徑順序,按照加權(quán)長(zhǎng)度順序首先找出最短路徑,直至最后找出從源結(jié)點(diǎn)到所有結(jié)點(diǎn)的最短路徑中最長(zhǎng)的那一條最短路徑。首先,引進(jìn)一個(gè)輔助向量D,它的每個(gè)分量Di表示當(dāng)前所找到的從源點(diǎn)s到每個(gè)終點(diǎn)vi的最短路徑的長(zhǎng)度。它的初態(tài)為:若從s到vi有弧,則Di為弧上的權(quán)值;否則置Di為。顯然長(zhǎng)度為Dj=minDi viV的路徑就是從s出發(fā)長(zhǎng)度最短的一條最短路徑。此路徑為(s,vj)。假設(shè)改次最短路徑的終點(diǎn)是vk,則可想而知

11、,這條路徑或者是(s,vk),或者是(s,vj,vk)。它的長(zhǎng)度或者是從s到vk的弧上的權(quán)值,或者是Dj和從vj到vk的弧上的權(quán)值之和。一般情況下,假設(shè)T為已求得最短路徑的終點(diǎn)的集合,則可證明:下一條最短路徑(設(shè)其終點(diǎn)為x)或者是弧(v,x),或者是中間只經(jīng)過(guò)T中的頂點(diǎn)而最后到達(dá)頂點(diǎn)x的路徑。在一般情況下,下一條長(zhǎng)度次短的最短路徑的是Dj=minDi viV-T其中, Di或者是弧(s,vi)上的權(quán)值,或者是Dk(vkT)和弧(vk,vi)上的權(quán)值之和。根據(jù)以上分析,可以得到如下描述的算法:(1)設(shè)用帶權(quán)的鄰接矩陣arcs來(lái)表示帶權(quán)圖,arcsij表示弧(vk,vj)上的權(quán)值。若(vi,vj)

12、不存在,則置arcsij為(在計(jì)算機(jī)上可用允許的最大值代替)。T為已找到從s出發(fā)的最短路徑的終點(diǎn)的集合,它的初始狀態(tài)為空集。那么,從s出發(fā)到圖上其余各頂點(diǎn)(終點(diǎn))v,.可能達(dá)到的最短路徑長(zhǎng)度的初值為:Di=arcsLocate VexG,vi viV (2)選擇vj,使得Dj=minDi viV-Tvj就是當(dāng)前求得的一條從s出發(fā)的最短路徑的終點(diǎn)。令T=Tj (3)修改從s出發(fā)到集合V-T上任一頂點(diǎn)vk可達(dá)的最短路徑的長(zhǎng)度。如果Dj+arcsjk<Dk則修改Dk為Dk=Dj+arcsjk (4)重復(fù)操作(2)、(3)共n-1次。由此求得從s到圖上其余各頂點(diǎn)的最短路徑是依路徑長(zhǎng)度遞增的序列。

13、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)劣,對(duì)整個(gè)網(wǎng)絡(luò)的性能有重要的影響。目前一般采用Dijkstra算法計(jì)算網(wǎng)絡(luò)中點(diǎn)到點(diǎn)的最短路徑。作為一種靜態(tài)算法,Dijkstra算法無(wú)疑是現(xiàn)有算法中最優(yōu)的。但當(dāng)網(wǎng)絡(luò)環(huán)境動(dòng)態(tài)變化時(shí),若仍然采用Dijkstra算法重新計(jì)算最短路徑,會(huì)帶來(lái)以下兩方面的問題:一是計(jì)算復(fù)雜性較高,浪費(fèi)大量的CPU時(shí)間。二是由于網(wǎng)絡(luò)中有可能存在費(fèi)用相同的兩條或兩條以上最短路徑。完全重新計(jì)算有可能帶來(lái)不必要的網(wǎng)絡(luò)路由變化,使路由器頻繁改變其路由表,造成網(wǎng)絡(luò)狀態(tài)的不穩(wěn)定。針對(duì)動(dòng)

14、態(tài)變化的網(wǎng)絡(luò)環(huán)境,可以對(duì)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算法所得到的最短路徑樹相對(duì)穩(wěn)定,最大程度的利用了網(wǎng)絡(luò)環(huán)境變化前已計(jì)算的最短路徑樹,避免了網(wǎng)絡(luò)中路由表的頻繁變化,使網(wǎng)絡(luò)處于不穩(wěn)定的狀態(tài)。動(dòng)態(tài)最短路徑算法的基本過(guò)程如下:(1)判斷帶權(quán)無(wú)向圖G=(V，E，C)中費(fèi)用變化的邊Ai是否是原來(lái)最短路徑樹上的邊,如果Ai是原來(lái)最短路徑樹上的邊則將邊Ai兩

15、個(gè)端點(diǎn)中離源結(jié)點(diǎn)較遠(yuǎn)的端點(diǎn)記為u,較近的端點(diǎn)記為v(即v是u的父結(jié)點(diǎn))轉(zhuǎn)第2步,如果Ai不是原來(lái)最短路徑樹上的邊,則將邊Ai的兩個(gè)端點(diǎn)分別記為u和v，轉(zhuǎn)第3步。(2)如果邊Ai的費(fèi)用Ci變大,則把結(jié)點(diǎn)u及其所有子孫結(jié)點(diǎn)記為集合T2,帶權(quán)無(wú)向G=(V，E，C)中其余的結(jié)點(diǎn)(V-T2)記為集合T1。如果邊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)無(wú)向圖G=(V，E，C)中其余的結(jié)點(diǎn)(V-T1)記為集合T2,轉(zhuǎn)第6步.(3)如果邊Ai的費(fèi)用Ci變大,結(jié)束。(4)如果邊Ai的費(fèi)用Ci變小,記為Ci'(Ci>Ci

16、9;),另記在原最短路徑樹上u到源結(jié)點(diǎn)s的最短路徑的值為Disu,v到源結(jié)點(diǎn)s的最短路徑的值為Disv。如果Disu小于(Disu+ Ci')并且Disv小于(Disu+ Ci')則結(jié)束,否則轉(zhuǎn)第5步。(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)無(wú)向圖G=(V，E，C)中其余的結(jié)點(diǎn)(V-T1)記為集合T2。反之則把結(jié)點(diǎn)v父結(jié)點(diǎn)指向u,同時(shí)把結(jié)點(diǎn)v及其所有子孫結(jié)點(diǎn)和源結(jié)點(diǎn)s到結(jié)點(diǎn)u的最短路徑上的

17、結(jié)點(diǎn)(包括源結(jié)點(diǎn)s,和結(jié)點(diǎn)u)記為集合T1,帶權(quán)無(wú)向圖G=(V，E，C)中其余的結(jié)點(diǎn)(V-T1)記為集合T2,轉(zhuǎn)第6步。(6)記集合T1,中各點(diǎn)為T1i,T2i到源結(jié)點(diǎn)的最短路徑的值為DisT1i,用Acrsuv表示結(jié)點(diǎn)u到v直接連接的費(fèi)用,如果結(jié)點(diǎn)u和v并不直接連接,則置arcsuv為無(wú)窮大。記集合T2中各點(diǎn)為T2j, T2j的距離記為DisT2 j,DsiT2 j的值計(jì)算如下:如果T2中的T2j與T1中的所有點(diǎn)都不直接連接,則DsiT2j記為無(wú)窮大。否則DisT2j=minarcsT2jT1i+ DisT1i T1i是集合T1中任一點(diǎn)。(7)選擇集合T2中DisT2j最小的結(jié)點(diǎn),記為T2j,修改T2j的父結(jié)點(diǎn)為DisT2j,在T1中對(duì)應(yīng)的結(jié)點(diǎn),將結(jié)點(diǎn)T2j加入集合不中,結(jié)點(diǎn)T2j結(jié)點(diǎn)的最短路徑的值結(jié)為DisT2jDisT1T2j= DisT2j,同時(shí)在集合T2中刪去結(jié)點(diǎn)T2j,若集合T2為空,則程序結(jié)束。否則如果DisT2j>arcsT2jT2j+DisT1T2j則DisT2j>arcsT2jT2j+DisT1T2j, DisT2j是集合工中任一點(diǎn),重復(fù)執(zhí)行第7步。Dijkstra算法的時(shí)間復(fù)雜度是O(n2),DMDT算法的時(shí)間復(fù)雜度為0(nk),k為生成樹中可能改變的結(jié)點(diǎn)個(gè)數(shù),在最壞情況