《多播路由算法的理論分析和證明方法論述》-MPH論文資料庫(kù)說(shuō)課講解

1、Good is good, but better carries it.精益求精，善益求善。多播路由算法的理論分析和證明方法論述MPH論文資料庫(kù)-多播路由算法的理論分析和證明方法論述MPH論文資料庫(kù)摘要:多播通信是從一個(gè)源點(diǎn)同時(shí)向網(wǎng)絡(luò)中的多個(gè)成員發(fā)送分組的通信服務(wù),一個(gè)最小代價(jià)的多播路由算法是NP完全的,在時(shí)間敏感的應(yīng)用中其運(yùn)行時(shí)間是一個(gè)關(guān)鍵問(wèn)題.MPH(MinimumPathCostHeuristic)算法是一個(gè)著名的啟發(fā)式最小代價(jià)多播路由算法,本文對(duì)該算法進(jìn)行了理論分析和證明,并做了廣泛的仿真實(shí)驗(yàn),結(jié)果表明其時(shí)間復(fù)雜度是O(m2n)而不是過(guò)去文獻(xiàn)中所給出的O(m2n+e).關(guān)鍵詞:多播路由

2、最小成本時(shí)間復(fù)雜度Abstract:Multicastingisacommunicationservicethatallowsasourcetoefficientlytransmitcopiesofdatapackettoasetofdestinationnodes.TheruntimeofmulticastroutingalgorithmisakeyprobleminrealtimeapplicationssincefindingaminimumcostmulticasttreeisNP-completeness.MPH(MinimumPathCostHeuristic)algorithmi

3、safamousheuristicsolutiontomulticastrouting.Inthispaper,weshowthattheO(nm2+e)timecomplexityofMPHinpreviousliteraturesisnotcorrectbytheoryanalysisandexten-sivesimulation,wherenisnumberofnetworknodes,misnumberofdestinationnodesandeisnumberofnetworkedges.Furthermore,aprecisetimeboundO(nm2)isproposed.Ke

4、ywords:multicastrouting;minimumcost;timecomplexity1引言多播通信(multicast)技術(shù)是網(wǎng)絡(luò)中的一個(gè)源點(diǎn)同時(shí)向網(wǎng)絡(luò)中的多個(gè)成員節(jié)點(diǎn)(端節(jié)點(diǎn))發(fā)送分組的通信服務(wù).它有利于節(jié)省網(wǎng)絡(luò)資源,在現(xiàn)代計(jì)算機(jī)通信中有著重大的應(yīng)用價(jià)值.多播路由(又叫多播樹)是從源點(diǎn)到各端節(jié)點(diǎn)的路徑,最小成本的多播路由的確定是NP完全的.MPH是一個(gè)出色的啟發(fā)式算法,在文獻(xiàn)16中都有描述,文獻(xiàn)2,3提出了改進(jìn)的MPH算法以減少多播樹的構(gòu)造時(shí)間.文1在將MPH算法與其它算法進(jìn)行性能比較時(shí),認(rèn)為MPH算法的時(shí)間復(fù)雜度在端節(jié)點(diǎn)到其它節(jié)點(diǎn)的最短路徑已知的條件下(后文都是基于這個(gè)條件

5、)是O(m2n+e),n是網(wǎng)絡(luò)節(jié)點(diǎn)數(shù),m是端節(jié)點(diǎn)數(shù),e是網(wǎng)絡(luò)中的邊數(shù).文2,3運(yùn)用文1的分析方法和結(jié)論也進(jìn)行了有關(guān)算法的性能分析和比較.本文認(rèn)為文13對(duì)MPH算法和有關(guān)算法的時(shí)間復(fù)雜性度量是不正確的,理論分析和仿真結(jié)果表明MPH的時(shí)間復(fù)雜度應(yīng)該是O(m2n).2MPH算法通信網(wǎng)絡(luò)可模型為一個(gè)帶權(quán)無(wú)向圖G=(V,E,c),V是節(jié)點(diǎn)集合,E是邊的集合,邊代表節(jié)點(diǎn)間的通信鏈路.G中節(jié)點(diǎn)個(gè)數(shù)為n,節(jié)點(diǎn)標(biāo)記為vi(i=1,2,n),邊標(biāo)記為vi,vj,(1i定義1節(jié)點(diǎn)vi,vj之間的最短路徑是連通vi,vj的路徑中各邊成本之和最小的一條路徑.節(jié)點(diǎn)到樹的最短路徑是指該節(jié)點(diǎn)到樹中各節(jié)點(diǎn)的最短路徑中成本最小的

6、那一條路徑.定義2最小成本多播樹.給定一個(gè)無(wú)向圖G=(V,E,c),源節(jié)點(diǎn)s,一個(gè)端節(jié)點(diǎn)集合ZV,尋找G的一個(gè)子圖(樹)T=(Vt,Et,ct),若滿足源節(jié)點(diǎn)到其它任一端節(jié)點(diǎn)存在一條路徑,Steiner節(jié)點(diǎn)(源節(jié)點(diǎn)和端節(jié)點(diǎn)以外的節(jié)點(diǎn))的度大于或等于2,TG,VtV,EtE,ZVt,則T是關(guān)于s和Z的一棵多播樹.若T的成本ct=vi,vjEtcost(vi,vj)是所有關(guān)于s和Z的多播樹中最小的,則T是最小成本多播樹.MPH算法是一個(gè)啟發(fā)式最小成本多播樹算法,其基本思想如下:(1)部分多播樹T開始只包括源節(jié)點(diǎn)s.(2)從余下的端節(jié)點(diǎn)中選取到樹T的最短路徑(如有多個(gè)則隨機(jī)選擇一個(gè)),端節(jié)點(diǎn)及路徑上

7、的所有節(jié)點(diǎn)并入Vt,路徑上的邊并入Et.(3)重復(fù)步驟(2),(3)直到Z中所有的節(jié)點(diǎn)包含到Vt中,此時(shí)的T即為近似最小成本多播樹.3算法時(shí)間復(fù)雜度分析文13認(rèn)為MPH算法中,對(duì)每一個(gè)即將加入到部分多播生成樹的端節(jié)點(diǎn)的選擇,最多需進(jìn)行mn次最短路徑的比較,m個(gè)端節(jié)點(diǎn)一個(gè)一個(gè)地加入,共需進(jìn)行m2n次比較.另外,將選定的端節(jié)點(diǎn)到樹T的最短路徑上的節(jié)點(diǎn)和邊加入到多播生成樹的次數(shù)最多是e.因而,MPH算法的時(shí)間復(fù)雜度為O(m2n+e).我們把MPH算法的操作分為三部分:端節(jié)點(diǎn)的加入所需的最短路徑的比較次數(shù);最短路徑上的邊的加入次數(shù);最短路徑上的節(jié)點(diǎn)的加入次數(shù).(1)最短路徑的比較次數(shù)MPH算法中,端節(jié)

8、點(diǎn)到部分多播生成樹的最短的最短路徑的確定需進(jìn)行的最大比較次數(shù)為:O(mi=0(n-m+i)(m-i)=O(3m2n+2m3-3m2+3mn-m6)=O(m2n)文3基于MPH算法介紹了一種改進(jìn)的算法FMPH,有利于減少最短路徑的比較次數(shù).但文3關(guān)于比較次數(shù)為O(m2k),k為多播生成樹中任意一個(gè)端節(jié)點(diǎn)的路徑節(jié)點(diǎn)個(gè)數(shù)的結(jié)論是值得商榷的.因?yàn)楦鶕?jù)原文定義2,k可能是0,最壞情況下也可能是O(n).作為對(duì)算法復(fù)雜性的度量,任意的k是不妥當(dāng)?shù)?(2)邊的加入次數(shù)當(dāng)從余下的端節(jié)點(diǎn)確定了到部分多播生成樹的最短路徑后,還需將該路徑上的邊并入部分多播生成樹.HYPERLINK/format/論文格式為了確立這

9、部分操作所需考察的邊的數(shù)目,我們先證明下面的定理.定理1設(shè)T=(V,E)是網(wǎng)絡(luò)圖G=(V,E)的一棵子樹(可擴(kuò)展為子圖),節(jié)點(diǎn)vmV,vmV,vm到樹T的最短路徑path(vm,T)=(V,E),則EE=.證明用反證法.由定義1,設(shè)vm到樹T的最短路徑是vm、vt節(jié)點(diǎn)間的最短路徑,vtV.如果EE,則至少有一條邊vi,vjE,vi,vjE,即有viV,vjV,則vi,vj兩個(gè)節(jié)點(diǎn)至少有一個(gè)節(jié)點(diǎn)不是vt,不妨設(shè)該節(jié)點(diǎn)是vj.由于vj是vm到vt的最短路徑上的節(jié)點(diǎn),則vm到vj的距離小于vm到vt的距離,這說(shuō)明vm到樹T的最短路徑是vm、vj節(jié)點(diǎn)間的最短路徑,這同vm到樹T的最短路徑是vm、vt節(jié)

10、點(diǎn)間的最短路徑的假設(shè)是矛盾的,所以定理1成立.由定理1,MPH算法中向部分多播生成樹加入選定的最短路徑上的邊時(shí)所需處理的邊的最大數(shù)目應(yīng)是n-1.因?yàn)樽罱K生成的多播樹最大是包括n個(gè)節(jié)點(diǎn)的一棵生成樹,且該樹在構(gòu)造時(shí)所處理的邊是沒(méi)有重復(fù)的.而文13認(rèn)為處理的邊的最大數(shù)目是O(e),對(duì)稀松圖,這部分計(jì)算量對(duì)算法總的時(shí)間復(fù)雜性的影響不是太大,但是對(duì)稠密圖卻可能使對(duì)算法的性能分析得到錯(cuò)誤的結(jié)論,因?yàn)檫叺目倲?shù)e是O(n2)條.例如,稠密圖中當(dāng)mn時(shí)邊的加入的計(jì)算量成為算法的主要部分,O(m2n+e)=O(e)=O(n2),是實(shí)際計(jì)算時(shí)間的O(n)倍.另外,文2在對(duì)LSMPH算法、文3在對(duì)FMPH算法的時(shí)間復(fù)

11、雜度的分析上對(duì)邊的度量存在同樣的問(wèn)題,這里不再贅述.(3)最短路徑上的節(jié)點(diǎn)的加入次數(shù)多播生成樹的節(jié)點(diǎn)數(shù)最多是n,故節(jié)點(diǎn)的加入所需的最大次數(shù)是O(n).綜上所述,MPH算法的時(shí)間復(fù)雜度應(yīng)是O(m2n+n+n)=O(m2n),而O(m2n+e)的結(jié)論是不正確的.4仿真實(shí)驗(yàn)為了更好的說(shuō)明文13的結(jié)論O(m2n+e)中的e相對(duì)于n的偏差程度,我們進(jìn)行了仿真實(shí)驗(yàn).實(shí)驗(yàn)中采用Wax-man在文獻(xiàn)7中介紹的方法生成隨機(jī)網(wǎng)絡(luò)圖.n個(gè)節(jié)點(diǎn)中任意一對(duì)節(jié)點(diǎn)u,v之間是否存在一條邊由連通概率p(u,v)確定,p(u,v)=e-d(u,v)/L,(0,1).邊長(zhǎng)即成本d(u,v)隨機(jī)分布在(0,L)中,L表示邊長(zhǎng)的變動(dòng)

12、期間.,是調(diào)整網(wǎng)絡(luò)特性的參數(shù),增加,長(zhǎng)邊相對(duì)短邊的比增加;增加,節(jié)點(diǎn)的度增加,即邊越稠密.共進(jìn)行了3組對(duì)照實(shí)驗(yàn),n=300,L=100,=02,分別為09,06,03.每一組參數(shù)生成300個(gè)隨機(jī)網(wǎng)絡(luò)圖.對(duì)每一個(gè)網(wǎng)絡(luò)圖,記錄網(wǎng)絡(luò)圖的總邊數(shù),圖1(a).O(e)相對(duì)實(shí)際處理邊數(shù)的偏差程度;(b).O(n)相對(duì)實(shí)際處理邊數(shù)的偏差程度300次實(shí)驗(yàn)的平均值記為e;隨機(jī)選擇指定數(shù)目的端節(jié)點(diǎn),記錄MPH算法構(gòu)造多播生成樹時(shí)所實(shí)際處理的邊數(shù),平均值記為real.比值e/real、n/real分別示于圖1.從圖1(a)可以看出用e來(lái)作為MPH算法的邊的處理次數(shù)是實(shí)際處理次數(shù)的102倍數(shù),而且邊越稠密,偏差越大;

13、端節(jié)點(diǎn)數(shù)越少,偏差越大.而從圖1(b)可以看出以n來(lái)作為MPH算法的邊的處理次數(shù)是合理的,并且?guī)缀醪皇苓叺某砻艹潭鹊挠绊?5結(jié)論理論分析和仿真結(jié)果表明多播路由算法MPH的時(shí)間復(fù)雜度應(yīng)該是O(m2n),而文13對(duì)MPH算法和有關(guān)算法的時(shí)間復(fù)雜性度量是不正確的.參考文獻(xiàn):1SRamanathan.MulticasttreegenerationinnetworkswithasymmetriclinksJ.IEEEACMTrans.OnNetworking,1996,4(4):558-568.2李漢兵,喻建平,謝維信.局部搜索最小路徑費(fèi)用算法J.電子學(xué)報(bào),2000,28(5):92-95.3胡光岷,李

14、樂(lè)民,安紅巖.最小代價(jià)多播生成樹的快速算法J.電子學(xué)報(bào),2002,30(6):880-882.4PawelWinter.Steinerprobleminnetworks:asurneyJ.Networks,1987,17(2):129-167.5FKHwang.Steinertreeproblems/dxmphlw/J.Networks,1992,22(1):55-89.6HFSalama,DSReeves.Evaluationofmulticastroutingalgorithmsforreal-timecommunicationonhighspeednetworksJ.IEEEJournalonselectedareasincommunication,1997,15(3):332-349.7Mwaxman.RoutingofmultipointconnectionsJ.IEEEJournalonSe-lectedAreasincommunication,1988,6(9):1617-1621.本文由無(wú)憂論文網(wǎng)碩士（博士、職稱、畢業(yè)）論文下載與發(fā)表中心獨(dú)家提供資源，如有雷同，純屬盜版。歡迎各位光臨獲取更多有用資料。碩士論文網(wǎng)：/master_degree.html博士論文網(wǎng)：/doctor_degree.html英語(yǔ)論文網(wǎng)：會(huì)計(jì)論文發(fā)表網(wǎng)：教育論文發(fā)表網(wǎng):