一种网络编码的多播路由算法

《一种网络编码的多播路由算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、２００８年２月西安电子科技大学学报（自然科学版）Ｆｅｂ．２００８第３５卷第１期犑犗犝犚犖犃犔犗犉犡犐犇犐犃犖犝犖犐犞犈犚犛犐犜犢Ｖｏｌ．３５Ｎｏ．１一种网络编码的多播路由算法王静１，刘景美１，王新梅１，袁荣亮２，刘向阳３（１．西安电子科技大学综合业务网理论及关键技术国家重点实验室，陕西西安７１００７１；２．西安科技大学通信与信息工程学院，陕西西安７１００５４；３．西安通信学院军事综合信息网教研室，陕西西安７１０１０６）摘要：提出一种基于网络编码的新多播路由算法，该算法借助Ｄｉｊｋｓｔｒａ约简网络搜索源节点到各接收节点的

2、路径族，并在搜索过程中考虑不同路径族之间链路的共享，以降低带宽资源消耗，改善链路负载均衡，提高了网络性能．仿真验证了算法的有效性，而且其性能逼近基于网络编码的最小费用多播算法．最后，数学分析表明该算法节约了４０％左右的计算量．关键词：网络编码；多播传输；路由算法；资源消耗；负载均衡中图分类号：ＴＮ９１３．１＋１文献标识码：Ａ文章编号：１００１２４００（２００８）０１００７１０５犕狌犾狋犻犮犪狊狋狉狅狌狋犻狀犵犪犾犵狅狉犻狋犺犿犳狅狉狀犲狋狑狅狉犽犮狅犱犻狀犵１，犔犐犝犑犻狀犵犿犲犻１，犠犃犖犌犡犻狀犿犲犻１，

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

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

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

6、ｃｅｃｏｍｐｕｔａｔｉｏｎｂｙ４０％ａｔｌｅａｓｔ．犓犲狔犠狅狉犱狊：ｎｅｔｗｏｒｋｃｏｄｉｎｇ；ｍｕｌｔｉｃａｓｔｔｒａｎｓｍｉｓｓｉｏｎ；ｒｏｕｔｉｎｇａｌｇｏｒｉｔｈｍ；ｒｅｓｏｕｒｃｅｃｏｎｓｕｍｐｔｉｏｎ；ｌｏａｄｂａｌａｎｃｅ近年来，多播传输成为现代通信中一个重要的组成部分．如果仅仅使用目前的多播传播技术，很多网络实际传输速率并不能达到网络本身所能提供的速率上限，即目前的技术还没有充分地利用网络资源．传统的网络节点只是将收到的数据路由、转发，并不进行数据的数学运算．文献［１］在２０００年首次提出了网络编码理

7、论，其核心思想是网络中的节点可采用不加冗余的编码，以充分利用已有网络资源进行更加有效的数据传输．此思想突破了一直以来数据传输的固定模式，从而为进一步提高目前的网络传输速率奠定了基础．基于网络编码的多播传输，其传输速率可以达到最大流，即网络流量的理论上限值．［２］鉴于目前基于网络编码的路由算法没有更好地考虑网络的带宽资源消耗和链路负载均衡性能，笔者提出了一种新的基于网络编码的多播路由算法．该算法与传统路由算法相比在资源消耗和负载均衡方面的［３］性能有很大提高，且非常接近最小费用多播算法．收稿日期：２００７０５１０基金

8、项目：国家自然科学基金资助（６０５０２０４６，９０６０４００９，６０５０３０１０）；华为高校科技基金资助（ＹＪＣＢ２００６００１ＲＥ）；８６３基金资助（２００７ＡＡ０１Ｚ２１５）作者简介：王静（１９８２），女，西安电子科技大学博士研究生，Ｅｍａｉｌ：ｊｉｎｇｗａｎｇ＠ｍａｉｌ．ｘｉｄｉａｎ．ｅｄｕ．ｃｎ．７２西安电子科技大学学