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

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

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



本文編號(hào)：3875740