發(fā)布時(shí)間：2024-06-29 14:35

　　k最短路徑應(yīng)用在大數(shù)據(jù)中心和高性能計(jì)算集群網(wǎng)絡(luò)中具有低延遲,高帶寬等優(yōu)點(diǎn),因而受到研究人員的廣泛關(guān)注。為了實(shí)現(xiàn)網(wǎng)絡(luò)節(jié)點(diǎn)在k最短路徑策略中信息的可靠傳遞,本文研究鏈路失效模型下k最短路徑的可靠性和期望路徑長(zhǎng)度問題,主要結(jié)論如下:1.本文考慮了節(jié)點(diǎn)可靠,鏈路可能失效的可靠性模型中,k最短路徑的等長(zhǎng)路徑選擇問題,并將等長(zhǎng)路徑的選擇問題轉(zhuǎn)化為一個(gè)可靠性優(yōu)化問題。最終提出了精確算法和基于蒙特卡洛模擬的近似算法求解該問題,實(shí)例表明了近似算法的有效性。2.本文建立了期望k最短路徑長(zhǎng)度的參數(shù)去衡量網(wǎng)絡(luò)性能,并證明了廣義德布魯因圖的期望k最短路徑長(zhǎng)度擁有近似最優(yōu)的性能。仿真結(jié)果有效地驗(yàn)證了理論分析。

【文章頁數(shù)】：41 頁

【學(xué)位級(jí)別】：碩士

【部分圖文】：

圖２．１可靠性算法示意圖間??Ｆｉ．?２．１?Ａｎ?ｉｌｌｕｓｔｒａｔｉｏｎ?ｆｏｒ?ｒｅｌｉａｂｉｌｉｔａｌｏｒｉｔｈｍｓ?Ｊ２３１??

鏈路??的集合，Ｐ是每條鏈路獨(dú)立正常運(yùn)行的概率。詳細(xì)假設(shè)如下：??（１）網(wǎng)絡(luò)中的每條鏈路都以相同的概率９?＝?１－０失效。??（２）網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)都是完美的。??（３）所有鏈路失效都是獨(dú)立的。??２．２．１料可靠性的精確算法??本文主要研宄的是可靠性（兩終端可靠性），即考慮給定....

圖２．２因子定理示意圖Ｍ??Ｆｉｇ．?２．２?Ａｎ?ｉｌｌｕｓｔｒａｔｉｏｎ?ｆｏｒ?ｆａｃｔｏｒｉｎｇ?ｄｅｃｏｍｐｏｓｉｔｉｏｎ?ａｌｇｏｒｉｔｈｍ?１２３１??

華東理工大學(xué)碩士學(xué)位論文?第７頁??（１）容斥原理算法＿２５］［２６］??容斥原理算法主要利用概率論的相關(guān)理論。其中￡；，￡；，．．．，￡：表示《個(gè)事件，則??Ｅ＇，Ｅ２，…，瓦中至少有一個(gè)事件發(fā)生的概率公式：??ＷＧ）?＝?Ｐｒ％?Ｕ?￡＂２?Ｕ?…Ｕ??＝Ｚｋ?ＰＫ＆）?－?....

圖２．３網(wǎng)絡(luò)Ｇ和子網(wǎng)絡(luò)：Ｇｉ）網(wǎng)絡(luò)＝?１，＜?＝?４?（的子網(wǎng)絡(luò)Ｗ?（ｃ）子網(wǎng)絡(luò)Ｇ／??Ｆｉｇ．?２．３?Ａ?Ｎｅｔｗｏｒｋ?Ｇ?ａｎｄ?ｓｕｂｎｅｔｗｏｒｋｓ：ａ）?Ａ?ｎｅｔｗｏｒｋ?Ｇ?ｗｉｔｈ?ｓ?＝?１?ａｎｄ?ｔ?＝?４（ｂ）Ａ．?ｓｕｂｎｅｔｗｏｒｋ?Ｇ２１?（ｃ）?Ａ?ｓｕｂｎｅｔｗｏｒｋ??

．１?ｔ最短可靠路徑??經(jīng)典的ｔ最短路徑問題作為最短路徑問題的泛化，通過尋求網(wǎng)絡(luò)源節(jié)點(diǎn)與終端節(jié)??點(diǎn)ｆ之間的最短路徑，次短路徑，次次短路徑，．．．，直到找到第＆短的路徑，最終形成??灸最短路徑集合，提供給用戶用于支持決策。經(jīng)典的Ａ最短路徑在選擇第／（１ＵＳ幻短路??徑的時(shí)候，重點(diǎn)....

圖３．１?８?jìng)�(gè)節(jié)點(diǎn)，點(diǎn)度為３的ＧＤＢＧ?（８，?３）．??Ｆｉｇ．?３．１．?ＧＤＢＧ?（８，?３）?ｗｉｔｈ?８?ｎｏｄｅｓ?ａｎｄ?３?ｄｅｇｒｅｅｓ?ｏｆ?ｅａｃｈ?ｎｏｄｅ．??

期望Ａ最短路徑長(zhǎng)度的下界。接下來，我們將會(huì)考慮廣義德布魯因圖的期望ｉｔ最短路徑??長(zhǎng)度。??３，２．２廣義德布魯因圖的期望最短路徑長(zhǎng)度分析??廣義德布魯因圖（Ｇｅｎｅｒａｌｉｚｅｄ?Ｄｅ?Ｂｒｕｉｊｎ?Ｇｒａｐｈ，?ＧＤＢＧ）是一種特殊的有向正則圖，??和隨機(jī)正則圖不同，它是一種....

本文編號(hào)：3997700