一種網(wǎng)絡(luò)編碼的多播路由算法

《一種網(wǎng)絡(luò)編碼的多播路由算法》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、２００８年２月西安電子科技大學(xué)學(xué)報(bào)（自然科學(xué)版）Ｆｅｂ．２００８第３５卷第１期犑犗犝犚犖犃犔犗犉犡犐犇犐犃犖犝犖犐犞犈犚犛犐犜犢Ｖｏｌ．３５Ｎｏ．１一種網(wǎng)絡(luò)編碼的多播路由算法王靜１，劉景美１，王新梅１，袁榮亮２，劉向陽３（１．西安電子科技大學(xué)綜合業(yè)務(wù)網(wǎng)理論及關(guān)鍵技術(shù)國家重點(diǎn)實(shí)驗(yàn)室，陜西西安７１００７１；２．西安科技大學(xué)通信與信息工程學(xué)院，陜西西安７１００５４；３．西安通信學(xué)院軍事綜合信息網(wǎng)教研室，陜西西安７１０１０６）摘要：提出一種基于網(wǎng)絡(luò)編碼的新多播路由算法，該算法借助Ｄｉｊｋｓｔｒａ約簡網(wǎng)絡(luò)搜索源節(jié)點(diǎn)到各接收節(jié)點(diǎn)的

2、路徑族，并在搜索過程中考慮不同路徑族之間鏈路的共享，以降低帶寬資源消耗，改善鏈路負(fù)載均衡，提高了網(wǎng)絡(luò)性能．仿真驗(yàn)證了算法的有效性，而且其性能逼近基于網(wǎng)絡(luò)編碼的最小費(fèi)用多播算法．最后，數(shù)學(xué)分析表明該算法節(jié)約了４０％左右的計(jì)算量．關(guān)鍵詞：網(wǎng)絡(luò)編碼；多播傳輸；路由算法；資源消耗；負(fù)載均衡中圖分類號(hào)：ＴＮ９１３．１＋１文獻(xiàn)標(biāo)識(shí)碼：Ａ文章編號(hào)：１００１２４００（２００８）０１００７１０５犕狌犾狋犻犮犪狊狋狉狅狌狋犻狀犵犪犾犵狅狉犻狋犺犿犳狅狉狀犲狋狑狅狉犽犮狅犱犻狀犵１，犔犐犝犑犻狀犵犿犲犻１，犠犃犖犌犡犻狀犿犲犻１，

3、犢犝犃犖犚狅狀犵犾犻犪狀犵２，犔犐犝犡犻犪狀犵狔犪狀犵３犠犃犖犌犑犻狀犵（１．ＳｔａｔｅＫｅｙＬａｂ．ｏｆＩｎｔｅｇｒａｔｅｄＳｅｒｖｉｃｅＮｅｔｗｏｒｋｓ，ＸｉｄｉａｎＵｎｉｖ．，Ｘｉ′ａｎ７１００７１，Ｃｈｉｎａ；２．Ｃｏｍｍｕｎ．＆ＩｎｆｏｒｍａｔｉｏｎＥｎｇ．Ｃｏｌｌｅｇｅ，Ｘｉ′ａｎＵｎｉｖ．ｏｆＳｃｉｅｎｃｅ＆Ｔｅｃｈ．，Ｘｉ′ａｎ７１００５４，Ｃｈｉｎａ；３．ＭｉｌｉｔａｒｙＣｏｍｐｒｅｈｅｎｓｉｖｅＩｎｆｏｒｍａｔｉｏｎＮｅｔｗｏｒｋＴｅａｃｈｉｎｇＯｆｆｉｃｅ，Ｘｉ′ａｎＣｏｍｍｕｎ．Ｃｏｌｌｅｇ

4、ｅ，Ｘｉ′ａｎ７１０１０６，Ｃｈｉｎａ）犃犫狊狋狉犪犮狋：Ｔｈｉｓｐａｐｅｒｐｒｅｓｅｎｔｓａｎｅｗｍｕｌｔｉｃａｓｔｒｏｕｔｉｎｇａｌｇｏｒｉｔｈｍｆｏｒｎｅｔｗｏｒｋｃｏｄｉｎｇ．ＴｈｅａｌｇｏｒｉｔｈｍｓｅａｒｃｈｅｓｔｈｅｒｏｕｔｉｎｇｇｒｏｕｐｓｆｒｏｍｓｏｕｒｃｅｔｏｅａｃｈｓｉｎｋｂｙｕｓｉｎｇｔｈｅＤｉｊｋｓｔｒａｒｅｄｕｃｔｉｏｎｎｅｔｗｏｒｋ．Ｉｎｔｈｅｐｒｏｃｅｓｓｏｆｓｅａｒｃｈｉｎｇ，ｌｉｎｋｓｈａｒｉｎｇｂｅｔｗｅｅｎｄｉｆｆｅｒｅｎｔｐａｔｈｇｒｏｕｐｓｉｓｃｏｎｓｉｄｅｒｅｄｔｏｄｅｃ

5、ｒｅａｓｅｂａｎｄｗｉｄｔｈｒｅｓｏｕｒｃｅｃｏｎｓｕｍｐｔｉｏｎａｎｄｉｍｐｒｏｖｅｌｏａｄｂａｌａｎｃｅ．Ｓｉｍｕｌａｔｉｏｎｒｅｓｕｌｔｓｓｈｏｗｔｈａｔｔｈｅｒｏｕｔｉｎｇａｌｇｏｒｉｔｈｍｉｓｅｆｆｅｃｔｉｖｅ，ａｎｄｔｈａｔｉｔｓｐｅｒｆｏｒｍａｎｃｅｉｓｃｌｏｓｅｒｔｏｔｈａｔｏｆｔｈｅｍｉｎｉｍｕｍｃｏｓｔｍｕｌｔｉｃａｓｔａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎｎｅｔｗｏｒｋｃｏｄｉｎｇ．Ｆｉｎａｌｌｙ，ｍａｔｈｅｍａｔｉｃａｌａｎａｌｙｓｉｓｉｎｄｉｃａｔｅｓｔｈａｔｔｈｅａｌｇｏｒｉｔｈｍｃａｎｒｅｄｕ

6、ｃｅｃｏｍｐｕｔａｔｉｏｎｂｙ４０％ａｔｌｅａｓｔ．犓犲狔犠狅狉犱狊：ｎｅｔｗｏｒｋｃｏｄｉｎｇ；ｍｕｌｔｉｃａｓｔｔｒａｎｓｍｉｓｓｉｏｎ；ｒｏｕｔｉｎｇａｌｇｏｒｉｔｈｍ；ｒｅｓｏｕｒｃｅｃｏｎｓｕｍｐｔｉｏｎ；ｌｏａｄｂａｌａｎｃｅ近年來，多播傳輸成為現(xiàn)代通信中一個(gè)重要的組成部分．如果僅僅使用目前的多播傳播技術(shù)，很多網(wǎng)絡(luò)實(shí)際傳輸速率并不能達(dá)到網(wǎng)絡(luò)本身所能提供的速率上限，即目前的技術(shù)還沒有充分地利用網(wǎng)絡(luò)資源．傳統(tǒng)的網(wǎng)絡(luò)節(jié)點(diǎn)只是將收到的數(shù)據(jù)路由、轉(zhuǎn)發(fā)，并不進(jìn)行數(shù)據(jù)的數(shù)學(xué)運(yùn)算．文獻(xiàn)［１］在２０００年首次提出了網(wǎng)絡(luò)編碼理

7、論，其核心思想是網(wǎng)絡(luò)中的節(jié)點(diǎn)可采用不加冗余的編碼，以充分利用已有網(wǎng)絡(luò)資源進(jìn)行更加有效的數(shù)據(jù)傳輸．此思想突破了一直以來數(shù)據(jù)傳輸?shù)墓潭Ｊ?，從而為進(jìn)一步提高目前的網(wǎng)絡(luò)傳輸速率奠定了基礎(chǔ)．基于網(wǎng)絡(luò)編碼的多播傳輸，其傳輸速率可以達(dá)到最大流，即網(wǎng)絡(luò)流量的理論上限值．［２］鑒于目前基于網(wǎng)絡(luò)編碼的路由算法沒有更好地考慮網(wǎng)絡(luò)的帶寬資源消耗和鏈路負(fù)載均衡性能，筆者提出了一種新的基于網(wǎng)絡(luò)編碼的多播路由算法．該算法與傳統(tǒng)路由算法相比在資源消耗和負(fù)載均衡方面的［３］性能有很大提高，且非常接近最小費(fèi)用多播算法．收稿日期：２００７０５１０基金

8、項(xiàng)目：國家自然科學(xué)基金資助（６０５０２０４６，９０６０４００９，６０５０３０１０）；華為高?？萍蓟鹳Y助（ＹＪＣＢ２００６００１ＲＥ）；８６３基金資助（２００７ＡＡ０１Ｚ２１５）作者簡介：王靜（１９８２），女，西安電子科技大學(xué)博士研究生，Ｅｍａｉｌ：ｊｉｎｇｗａｎｇ＠ｍａｉｌ．ｘｉｄｉａｎ．ｅｄｕ．ｃｎ．７２西安電子科技大學(xué)學(xué)