基于XOR选择重传ARQ的网络编码多播路由算法

Journal of Systems Engineering and Electronics ›› 2010, Vol. 32 ›› Issue (4): 865-868.

基于XOR选择重传ARQ的网络编码多播路由算法

王静¹，刘景美²，刘向阳³，王新梅²

(1. 长安大学信息工程学院，陕西西安 710064；
2. 西安电子科技大学综合业务网国家重点实验室，陕西西安 710071；
3. 西安通信学院军事综合信息网教研室，陕西西安 710106)

出版日期:2010-04-23 发布日期:2010-01-03

Multicast routing algorithm with network coding based on XOR selective repeat ARQ

WANG Jing¹, LIU Jing-mei², LIU Xiang-yang³, WANG Xin-mei²

(1. School of Information Engineering, Chang’an Univ., Xi’an 710064, China;
2. State Key Laboratory of Integrated Service Networks, Xidian Univ., Xi’an 710071, China;
3. Military Comprehensive Information Network Teaching Office, Xi’an Communication Coll., Xi’an 710106, China)

Online:2010-04-23 Published:2010-01-03

摘要/Abstract

摘要：

针对XOR选择重传ARQ协议，提出了一种基于网络编码的多播路由算法，有效地恢复链路传输错误。该算法分为两种情况：一是信源发送正常的数据包，在信源节点与各接收节点之间建立多播路径族，并考虑不同路径族之间链路的共享；二是信源发送XOR数据包，搜索信源节点到各接收节点的最短路径，并考虑最短路径之间的链路共享。仿真结果表明，该算法有效地提高了网络吞吐量，在资源消耗方面较传统的多播路由算法有更好的表现，非常接近基于网络编码的最小费用多播算法。数学分析表明,该算法的复杂度远小于最小费用多播算法。

Abstract:

A new multicast routing algorithm with network coding to deal with transmission errors in the data links is proposed, which is based on XOR selective repeat ARQ. More specifically, this scheme contains two cases: when the source transmits the normal data packets, the routing groups from source to each sink are searched, and link-sharing between different path groups is considered in the process of searching; when the source transmits the XOR data packets, the shortest paths from source to each sink are searched, and link-sharing between different shortest paths is also considered. Simulation results show that this algorithm increases the network throughput effectively. Meanwhile, compared with traditional multicast routing algorithms, the performances of the routing algorithm are improved at a great extent in resource consumption, and closer to the minimum-cost multicast algorithm based on network coding. Mathematic analysis indicates that the complexity of the proposed algorithm is much lower than that of the minimum-cost multicast algorithm.

王静，刘景美，刘向阳，王新梅. 基于XOR选择重传ARQ的网络编码多播路由算法[J]. Journal of Systems Engineering and Electronics, 2010, 32(4): 865-868.

WANG Jing, LIU Jing-mei, LIU Xiang-yang, WANG Xin-mei. Multicast routing algorithm with network coding based on XOR selective repeat ARQ[J]. Journal of Systems Engineering and Electronics, 2010, 32(4): 865-868.