發(fā)布時間：2023-12-27 19:16

　　如今,人類社會存儲和交換的信息總量呈幾何級數(shù)飛速增長,數(shù)據(jù)傳輸?shù)耐掏铝亢蛯崟r性亟待提升。然而,現(xiàn)有的網(wǎng)絡(luò)編碼研究專注于提升吞吐量,忽略了實時性對大數(shù)據(jù)網(wǎng)絡(luò)多路徑傳輸性能的重大影響。為此,文中針對線性網(wǎng)絡(luò)編碼的最快到達(dá)問題,提出一種矩陣優(yōu)化相乘的關(guān)鍵路徑算法,以提高算法的實時性。具體地,使用抽象代數(shù)分析關(guān)鍵路徑算法,構(gòu)造了關(guān)鍵路徑的交換環(huán)代數(shù),并證明了最優(yōu)子結(jié)構(gòu)性質(zhì)。仿真結(jié)果顯示,隨著網(wǎng)絡(luò)節(jié)點個數(shù)n的增加,基于Strassen思想優(yōu)化的關(guān)鍵路徑算法能夠極大地降低計算復(fù)雜度,成功將時間復(fù)雜度降至O(n^2.81lg n),縮短了傳播時延,提高了數(shù)據(jù)傳輸?shù)膶崟r性。當(dāng)n>6時,相比基于重復(fù)平方關(guān)鍵路徑算法,基于Strassen關(guān)鍵路徑算法的時間開銷的增長速率明顯更低;特別地,當(dāng)n=12時,基于Strassen關(guān)鍵路徑算法的計算量約是基于重復(fù)平方關(guān)鍵路徑算法的2/3,而其所需的時間開銷約為后者的1/2。

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

【文章目錄】：
1 引言
2 線性網(wǎng)絡(luò)編碼下關(guān)鍵路徑的代數(shù)結(jié)構(gòu)
3 線性網(wǎng)絡(luò)編碼下的關(guān)鍵路徑算法
4 關(guān)鍵路徑算法理論驗證模型的分析
5 關(guān)鍵路徑算法的優(yōu)化
6 仿真結(jié)果分析
結(jié)束語



本文編號：3875740