集中式网络编码组播路由算法*

徐光宪，赖俊宁

辽宁工程技术大学 电子与信息工程学院，辽宁 葫芦岛 125105

集中式网络编码组播路由算法*

徐光宪，赖俊宁+

辽宁工程技术大学 电子与信息工程学院，辽宁 葫芦岛 125105

Abstract:From magnifying multicast capacity and reducing multicast delay,this paper proposes a centralized network coding cycle augmented multicast routing algorithm(NCCA)to further improve the transmission rate of multicast communication.Firstly,each node traverses the link state packets to get the topology information of the network by breadth first search(BFS)algorithm.Then,each sink node augments routing set by using Dijkstra algorithm and selects the optimal routing set.Finally,the routing sets of all sink nodes are combined to get the entirety routing of multicast group.The theoretical analysis and simulation results show that the NCCA multicast routing algorithm can further improve the transmission rate of multicast communication in a stable network.

Key words:network coding;multicast capacity;multicast delay;multicast transmission rate

从提高组播容量和降低组播延迟入手，提出了一种集中式网络编码循环增广组播路由算法（centralized network coding cycle augmented multicast routing algorithm，NCCA），从而进一步提高了组播通信的传输速率。首先各节点通过广度优先搜索（breadth first search，BFS）算法遍历链路状态分组获得整个网络的拓扑信息，以Dijkstra算法为基础增广每个信宿节点的路由集，然后选出最优路由集，最后将所有信宿节点的路由集进行组合，得到组播组的整体路由。通过对算法进行理论分析及仿真实验，证明了NCCA组播路由算法在较稳定的网络上能进一步提高组播通信的传输速率。

网络编码；组播容量；组播延迟；组播传输速率

1 引言

传统网络的信息传输大部分是基于存储和转发的路由机制，Ahlswede等人[1]于2000年首次提出了网络编码的基本原理，它允许中间节点对输入信息进行编码，在提高网络吞吐量，改善负载均衡，减小传输延迟，增强网络鲁棒性和提高信息安全性等方面具有重要意义。近年来网络编码在优化与安全等领域得到了深入研究，对组播路由的研究也逐渐成为网络编码的新热点。

早期的组播路由算法有KMB组播路由算法、最小代价启发式组播路由算法（minimum path cost heuristic multicast algorithm，MPH）和轻量自适应组播路由算法（lightweight adaptive multicast algorithm，LAM）等[2]。KMB和MPH为集中式的Steiner最小树启发式算法，在此基础上衍生出的新型组播路由算法有基于加权节点的最小代价路径启发式算法（node weight based minimum cost path heuristic algorithm，NWMPH）[3]和多跳自组织按需距离矢量组播路由算法（multicast ad-hoc on-demand distance vector routing algorithm，MAODV）[4]等。NWMPH算法在MPH算法基础上通过加权公式对所有非正则点进行权值计算，从而构造组播树，是一种基于加权节点的表驱动启发式算法。MAODV是分布式AODV按需路由协议在组播方式下的扩展，是适用于自组网的分布式距离向量多播路由算法，可以实现快速移动节点间的通信。文献[5]首次应用网络编码思想提出了一种基于最大流的网络编码组播路由算法（max-flow based network coding multicast routing algorithm，NCMA），各信宿节点进行一次增广，通过组合得到组播组的整体路由。

本文从提高组播容量和降低组播延迟入手，提出了一种集中式网络编码循环增广组播路由算法（centralized network coding cycle augmented multicast routing algorithm，NCCA），从而进一步提高了组播通信的传输速率。NCCA是一种集中式组播路由算法，首先每个路由节点都需要通过周期性发布动态的链路状态分组获得网络信息，然后维护整个网络的拓扑信息，最后根据网络拓扑信息独立地构造多播树。针对NCMA一次增广不一定能得到网络的最大组播容量和最小组播延迟的问题，本文运用NCCA选出每个信宿的最优路由集，将所有信宿的路由集进行组合，得到组播组的整体路由。仿真实验表明，在中等网络规模下，应用NCCA组播路由算法在较稳定的网络上能进一步提高组播通信的传输速率。

2 相关知识

2.1 广度优先搜索算法遍历链路状态分组

广度优先搜索（breadth first search，BFS）算法从各节点访问所有与之相邻的节点，访问完这些节点后，再访问与这些节点相邻的未被访问的节点，重复整个过程直到所有的节点都被访问，通过序列号控制链路状态分组的扩散过程[6]。发布的链路状态分组包括一个发送方标识、序列号、年龄以及一个包含距离的邻居列表。每当链路状态发生改变时重新创建并发布分组，从而构造实时的网络拓扑。

2.2 Dijkstra算法寻路

NCCA以Dijkstra算法寻路，它的基本思路是先建立一个网络图，图中的每个节点代表一台路由器，每条弧代表一条通信链路。每一个节点都有一个两项的标号，标号第一项是最短路径上对应的前趋节点，第二项是这个路径的长度，每个标号分为暂时的或永久的，初始时所有标号都是暂时的。初始时所有的节点都标记为无限远，随着算法的不断进行，当确定了一个标号为从原点到该节点的最短路径时，标号变成永久的并且不再改变。此时信宿节点到组播源范围内的节点都会生成自己的标号，每个标号都对应着各自的路由选择，标记为永久节点后可通过反向追踪确定最短路径[2]。

其中路径长度可以凭借跳数、传输延迟、队列长度和带宽等衡量，本文用延迟ts作为路径长度的度量。为了满足不同服务类型[7]信号的延迟要求，通常设置一个组播延迟上界sd，延迟过大的路由被舍弃，从而避免因传输延迟而造成的信号质量问题，但是延迟上界往往使网络达不到理论上的最大组播容量。

2.3 网络编码

设d为编码节点的输入链路，e为输出链路，局部编码向量m(e)={mde∈GF(2m):d∈In[tail(e)]}，输入的信息向量为y(d)，输出的编码信息向量为y(e)，那么生成y(e)的公式为：

设组播率为hs，组播源信息向量组成一个L行hs列原始信息矩阵A，全局编码向量组成hs行hs列的编码矩阵B，信宿Ti接收到的L行hs列的编码信息矩阵为C。根据网络编码进行的矩阵变换A×B=C，仅当编码矩阵B满秩时，每个信宿节点Ti可以计算编码矩阵B的逆矩阵B-1并存储在内存中，根据A=C×B-1解出原始矩阵A。其中B由全局编码向量g(dTij)组成，而C由编码信息向量y(dTij)组成，dTij为信宿Ti的第j条输入链路，y(dTij)与g(dTij)的代数关系为：

2.4 NCCA多播树

网络编码组播路由必须保证有hs个分离路径输入每个信宿节点，并且每条分离路径的全局编码向量线性无关。NCCA所确定的路由集实质上都构成了一棵以每个信源节点为根的多播树，连接了多播组中所有信宿节点，它本质上同Steiner最小树是一致的，只不过算法通过调整运算策略充分利用了带宽资源。在多个组播源的网络中，有些Steiner节点可能属于不同的组播树，选择其中入度大于出度的节点为编码节点，然后分配局部编码向量，最后生成满秩的编码矩阵。文献[8]给出了一种网络编码小生境最小代价优化（network coding simple-genetic minimum-cost，NCSM）协议。

3 NCCA组播路由算法

3.1 NCCA组播路由算法原理

组播传输速率v表示单位时间内信宿接收到信息的大小，组播容量c表示网络中组播率hs的上限，组播容量c越大，传输速率v也越高。组播延迟d指的是一次组播中信息从发出到接收所经历的时间，组播延迟d越小，传输速率v就越高[9]。因此可从提高组播容量和降低组播延迟入手，进一步提高组播通信的传输速率。

经典的组播蝴蝶网络如图1所示。假设每条链路带宽为1单位，传输分组大小为1单位，s1和s2分别发送信息分组a、b至t1和t2，根据最大流最小割定理可知最大组播容量为2[1]。

Fig.1 Typical butterfly network图1 典型的蝴蝶网络

传统组播路由算法如MAODV和NWMPH，都以每个信源为根构造Steiner最小树来实现组播。以s1为根的树可能为s1—n1—n2—(t1,t2)，以s2为根的树可能为s2—n1—n2—(t1,t2)。链路n1—n2在带宽受限的情况下，由于节点n1的入度大于出度，信息分组a和b需要在节点n1处排队，使信宿不能同时接收到分组a和b，而且这种组播策略共占用了8条链路（1次s1—n1和s2—n1，2 次n1—n2,n2—t1和n2—t2），不能达到理论上的最大组播容量。

而NCMA与NCCA都以网络编码为原理，得到以s1为根的树可能为s1—n1(t1)—n2—t2，s2为根的树可能为s2—n1(t2)—n2—t1，信息分组a和b在n1编码成a+b，信宿t1和t2就能同时接收到a和b了，而且只占用了7条链路（1次s1—t1,s2—t2,s1—n1,s2—n1,n1—n2,n2—t1和n2—t2），确实可以达到理论上的最大组播容量2。

在路由方面，NCMA为确定组播组的路由集，应用Dijkstra算法对信宿到所有信源按延迟顺序进行寻路，每次寻路获得到达某个信源的一个新路径并保存，然后在拓扑图中去掉这个信源和途经的链路，对图进行下一次寻路，允许分离路径经过同一节点，直到路径无法满足要求则指定为最终路由集并保存，这个过程称作一次增广[10]。NCMA只进行了一次增广，因此NCMA可能无法达到最大组播容量。例如t1增广分离路径时，如果路径t1—n2—n1—s1延迟小于路径t1—s1，NCMA按顺序首选t1—n2—n1—s1会占用信息分组b经过n1—n2的带宽，最后只能得到路由集s1—n1—n2—t1。而NCCA在每次选路前首先进行路径等级划分，在图1蝴蝶网络选路时考虑了首选第2路径t1—s1，再选择第1路径t1—n2—n1—s2的情况，增广出路由集s1—n1(t1)—n2—t2。然后比较得到的路由集，最后选择了组播容量为2单位的s1—n1(t1)—n2—t2。

3.2 NCCA组播路由算法流程

NCCA组播路由算法的总体设计框图如图2所示。定义参数si为由链表构造的路径，ts为路由延迟，S为组播路由集，TS为临时组播路由集，d为组播延迟，c为组播容量，Td、Tc分别是临时组播延迟和容量，i为首选路径的循环参数，n为首选路径等级，q为循环选路模块的循环参数，fd为首选路径延迟，sd为标准延迟上界。

NCCA组播路由算法主程序调用了5个模块：BFS模块负责在网络中遍历链路状态分组，并且在节点内存中构造图和优先队列，目的是为了使每个节点获得网络的拓扑信息，在链路出现断路的情况下删除受影响的路由。模块需设置初始参数n=1，c=0，d=+∞，S=∅。D模块由Dijkstra算法子模块和排序子模块组成。Dijkstra算法子模块对图执行一次Dijkstra算法，得到信宿到所有组播源范围内节点的标号，通过排序子模块寻找第n路径，选取当前图的第n路径并计算其延迟ts。循环模块的作用是在首选第n路径下，以q≤n作为循环终止条件扩充路由集。修订图模块运行在所有链路带宽为1单位，传输分组大小为1单位的前提下，它的作用是在一组增广中，在图中删除每次选路的链路从而修订拓扑图。容量和延迟比较模块按照先选最大容量再选最小延迟的顺序比较出c和d以及所对应的路径集S。各模块通过主程序整合在一起，最后将各信宿的最优路由集组成组播组的整体路由。

排序子模块负责把不同延迟的路由划分为多个等级，按照路径延迟从小到大划分等级，第n等级的称为第n路径。在每次执行Dijkstra算法后，信宿节点到组播源范围内的节点都会生成自己的标号，包括组播源的邻居节点。等级划分的规则为选择第n路径时，若存在直接到信源节点Si的第n路径，就选择这条路径，不存在时查找一条最远的第m路径(m＜n)。最远的第m路径是指组播源邻居节点的标号中延迟项(ts)最大的标号所对应的路径。沿着这条路径前溯一个节点，查找这个节点的邻居，选择一个第n-m近的邻居即可找到第n路径。当前溯的节点没有第n-m近的邻居，则依此类推，继续前溯直到找到第n路径。根据选择的第n路径，保留最下游变更过的节点的标号，然后对变更过的节点逐个向上游重新标号，直到重新标记到组播源为止，根据新标号确定这条第n路径和它的延迟。每次执行Dijkstra算法后都要进行路径等级划分，从而选择第n路径。选择第n路径是为了按顺序循环使算法收敛。

如图2，NCCA组播路由算法主程序中的D模块与循环模块由一个小循环连接构成，小循环凭借参数i自加运行，负责为信宿到信源寻一条路径si并保存到路由集Ts中，增广路由集的公式为：

通过排序子模块计算单个路径延迟ts，将最大的延迟作为路由集的组播延迟Td，然后修订拓扑图。当ts≥d，ts≥sd或无法生成新路径时跳出小循环，保存路由集的组播容量Tc，进入容量/延迟比较模块。

初始化图由两个参数q和n控制。初始化图与容量/延迟比较模块由一个中循环以及一个大循环结构连接构成，中循环凭借参数q运行，q≤n作为其终止条件。每次循环得到一个路由集TS，并把容量和延迟的值赋给Tc和Td，在容量/延迟比较模块与c和d进行比较，将比较值重新赋给c和d，得到新路由集S=opt[S,TS]，然后初始化图将参数i和q置1。新路由集S中d和c满足式（4）和（5）：

Fig.2 NCCAoverall design diagram图2 NCCA总体设计框图

大循环凭借参数n运行，n为首选路径等级，每次循环后n自加，整个算法通过终止条件fd≤d达到收敛，跳出大循环输出组播容量最大且组播延迟最小的路由集S。

3.3 收敛性以及算法复杂度分析

为了减少运算量，每次寻路后将这条路由延迟ts与sd和d进行比较，如果ts≥sd或ts≥d，则停止这组增广并跳到下一组。由于逐次比较最优路由方案，组播延迟d会越来越小。而按等级首选第n路径，首选路径延迟fd会不断增大，最后必有d=fd，达到收敛。此后的路由集中fd不可能小于d，即不可能再增广出更优的路由集，因此把fd≤d作为循环增广的收敛条件。

用邻接链表表示拓扑图，用斐波那契堆实现优先队列，Dijkstra算法的时间复杂度为O(E+nlgn)。NCCA求信宿节点到每个信源节点的最短路径，则每个信源需调用一次Dijkstra算法，设组播率为hs，算法循环k次达到收敛，则算法的时间复杂度为O(khs(E+lgn))。对于空间复杂度，首先需要空间n保存距离，另需空间n存储前一个节点以保存路径，此外还需一个斐波那契堆及其反向指针，而且NCCA算法在每个节点保存hs条最短路径，每次更新路径集的代价相当于把hs个长度为4n的表合并在一起，因此NCCA的空间复杂度为O(4nhs)。

4 NCCA路由算法仿真

本文仿真环境为Dell PC机，处理器为Intel®CoreTM-M480 I5 CPU@2.67 GHz，4 GB内存，操作系统为32位Win7系统，安装并使用了VC++6.0、Cyg-Win、Matlab R2011b和NS2-allinone2.26软件。

4.1 构建网络拓扑

GT-ITM是NS2自带的开源网络拓扑生成工具，使用GT-ITM建立K均值聚类Waxman随机拓扑模型（K-means Waxman random network topology model，KRTG），KRTG模型节点和边分布均匀，避免了重叠或距离过近，能生成度数收敛的连通图[11]。将n个节点按KRTG模型分布在平面上，生成链路，从而构建连通图的概率分布为：

其中，L为拓扑中所有节点距离的最大值，设a为网络的边长，则L=a；|V|为节点数；d(u,v)是节点u和v之间的欧式距离；α、β是取自(0,1]的实数。选择适当的值能使拓扑更接近真实网络。概率P(u,v)中，D是节点平均度。在实验中链路延迟调用λ=d(u,v)的泊松分布函数[12]，设置平面为100 km×100 km的正方形区域，坐标最小刻度为1，α=0.15，D=4。

4.2 应用NS2仿真NCCA组播路由算法

NS2是一款开放源代码的网络仿真软件，NS2中网络协议是可扩展的[13]。为了比较组播算法在有限带宽下传输速率的优劣，且为了方便重新修订拓扑图，设置Tcl仿真脚本中链路带宽为1.5 Mb/s，传输分组大小为1 Mb的CBR（constant bit rate）流，其中多余带宽留给传输链路状态分组。物理层选用IEEE-802.3u，Mac层协议采用CSMA/CD（carrier sense mul-tiple access with collision detection）实现媒体访问机制，采用TCP传输协议、RED（random early detection）队列管理协议、网络编码优化NCSM协议，接口队列类型为Queue/DropTail/PriQueue。

本文设计了两组实验对组播路由算法MAODV、NWMPH、NCCA和NCMA进行仿真。每个节点通过BFS算法以300 ms为周期发送链路状态分组来实现拓扑的实时更新，理论上每次BFS算法对整个网络扫描所消耗的时间是由网络拓扑结构所决定的，和网络直径有直接的关系。第一组实验在节点数50、100、150、200、250、300、350下分别随机生成30次拓扑模型，运行各算法并在算法执行过程中动态加入相同数量的组播源和信宿，直到达到最大组播容量。第二组实验在30组200节点的网络规模中仿真，在链路停留时间为 0.05、0.10、0.15、0.20、0.25、0.30、0.35 s的情况下使各算法达到最大组播容量。两组实验最终生成了记录算法执行过程参数的trace跟踪文件。

4.3 算法性能分析

针对两组实验的仿真结果trace文件，编写awk程序，将分析结果导入Matlab绘制对比折线图。awk的主要功能是以指定的模式搜索文件的每一行，在符合指定模式的行提取所需参数，直至搜索结束[14]。实验1提取组播容量c、组播延迟d和收敛时间t，并求平均值，分析比较在不同网络规模下各算法参数变化情况和性能差异。实验2提取传输速率v并求平均值，分析并比较网络在不同稳定性下各算法的传输速率变化情况和差异。通过NS2对实验1生成的trace文件进行awk程序分析，得到BFS算法在KRTG模型中网络规模分别为50、100、150、200、250、300、350时的平均时间消耗分别为76、102、125、144、158、173、186 ms。

实验1中MAODV、NWMPH、NCCA和NCMA算法运行结果的平均组播容量、平均组播延迟和平均收敛时间对比如图3、图4、图5所示。实验2中各算法运行结果的组播传输速率对比如图6所示。

Fig.3 Comparison of average multicast capacity for multicast routing algorithms图3 组播路由算法平均组播容量比较

Fig.4 Comparison of average multicast delay for multicast routing algorithms图4 组播路由算法平均组播延迟比较

图3和图4表明NCCA在组播容量和组播延迟上要好于MAODV、NWMPH和NCMA，这是由于MAODV、NWMPH和NCMA关键链路的占用以及少量的中心节点频繁被选为中继节点，导致路由路径存在较高的重叠率和较高的组播延迟。其中MAODV和NWMPH还不支持网络编码，导致较高的队列长度，因此组播容量较小。另一方面各算法在两项指标上有大致相似的变化趋势，这是因为随着网络规模的增加，更多中继节点使组播路由有更为丰富的选择。

如图5所示，NCCA的平均收敛时间大于其他算法，这是因为NCMA和MAODV的时间复杂度都为O(hsn2)，NWMPH的时间复杂度为O(mn2)，而NCCA的时间复杂度为O(khs(E+nlgn))，大于其他算法。随着网络规模的增加，NCCA的平均收敛时间大幅增加，而MAODV、NWMPH和NCMA则变化不明显，这表明网络规模对NCCA的收敛速度有较大影响。这是由于算法的时间复杂度受循环次数k的影响，对于规模很大的网络不易收敛。

Fig.5 Comparison of average multicast convergence time for multicast routing algorithms图5 组播路由算法平均收敛时间比较

Fig.6 Comparison of average multicast transmission rate for multicast routing algorithms图6 组播路由算法平均传输速率比较

如图6所示，适用于自组网的分布式路由协议MAODV在链路停留时间较短时组播传输速率最高，说明MAODV适用于变化频繁的网络。NCCA在链路停留时间较长时有较高的组播传输速率，表明NCCA适用于相对稳定的网络。原因是NCCA的收敛速度较慢，链路的频繁变动会带来很大的节点开销，而如果链路较稳定，NCCA便能充分利用其优化组播容量和组播延迟的优势。另一方面随着链路停留时间的增加，NCCA和NCMA的组播传输速率大幅增加，而MAODV和NWMPH则变化不明显，这是因为MAODV和NWMPH中节点无法进行网络编码，导致了较重的队列拥塞。

5 结束语

本文提出的NCCA组播路由算法选择最大组播容量和最小组播延迟的路由集，从而提高了组播网络的传输速率。但是目前NCCA还存在很多有待改进的地方。首先这种路由算法在网络拓扑变换频繁的情况下，传输速率会变得很低，这是较高的收敛次数k造成的，未来在循环模块可采取遗传算法降低收敛次数，减少不必要情况的查找，从而从整体上降低NCCA的时间复杂度。算法目前只在K均值聚类Waxman随机拓扑模型中进行了仿真，属于节点间地位平等的平面式网络，不能完全准确反映实际的Internet特性，应扩展到BA、GLP或LWTC幂律型网络模型。此外修订图模块假定链路带宽全部为1单位，没能反映真实网络的带宽情况，还处于简易的去链路模型，修订图模块的细节还有待完善。最后可以将集中式NCCA改为分布式路由算法，并使用MPR（multi-point relay）广播中继机制[15]，进一步提升带宽利用率，减小寻路开销，提高可扩展性，以适应不同的网络类型。

[1]Ahlswede R,Cai Ning,Li S Y R,et al.Network information flow[J].IEEE Transactions on Information Theory,2000,46(4):1204-1216.

[2]Chen Xiaohui.Multicast routing algorithms'simulation platform designing[D].Dalian:Dalian University of Technology,2006.

[3]Wang Xiaolong.Algorithm and application research of Steiner problem in graphs[D].Nanjing:Nanjing University of Posts and Telecommunications,2015.

[4]Wu Jichun.Research of routing protocols of ad hoc networkand NS2 simulations[D].Wuhan:Wuhan University of Technology,2005.

[5]Tao Shaoguo,Huang Jiaqing,Yang Zongkai,el al.Maxflow based routing algorithm for network coding multicast[J].Computer Science,2008,35(6):109-112.

[6]Yu Yanping.Studies on multicast routing algorithms[D].Hangzhou:Zhejiang University,2002.

[7]Hao Kun,Jin Zhigang.Mechanism of P2P file distribution based on deterministic network coding[J].Journal of Applied Sciences,2014,32(3):247-251.

[8]Xu Guangxian,Wu Wei,Zhou Jia.Research on application of niche genetic algorithm in the network coding optimization[J].Computer Engineering,2015,41(7):152-157.

[9]Yang Weihua,Wang Hongbo,Cheng Shiduan,et al.Min-cut multi-path routing algorithm[J].Journal of Software,2012,23(8):2119-2122.

[10]Du Weiqi.The research of multipath routing protocol based on network coding in wireless sensor network[D].Nanjing:Nanjing University of Posts and Telecommunications,2014.

[11]Shi Min.The routing algorithm research on PTN network management[D].Wuhan:Wuhan University of Technology,2013.

[12]Shen Meng.Research on efficient embedding and traffic management for network virtualization[D].Beijing:Tsinghua University,2014.

[13]Zhou Derong,Xia Ling,Shu Tao,et al.Research on virtual simulation platform of NS2 network protocol[J].Experimental Technology and Management,2014,31(3):87-90.

[14]Tian Shengwen.Research on construction of overlay network with Internet infrastructure awareness[D].Beijing:Beijing University of Posts and Telecommunications,2015.

[15]Li Wen.Research on multipath parallel transmission network technology in mobile communication network[D].Beijing:Beijing University of Posts and Telecommunications,2015.

附中文参考文献：

[2]陈晓卉.组播路由算法仿真平台设计[D].大连:大连理工大学,2006.

[3]王小龙.图的Steiner最小树问题的算法与应用研究[D].南京:南京邮电大学,2015.

[4]吴继春.AdHoc网络路由协议的研究与NS2仿真[D].武汉:武汉理工大学,2005.

[5]陶少国,黄佳庆,杨宗凯,等.基于最大流的网络编码组播路由算法[J].计算机科学,2008,35(6):109-112.

[6]余燕平.多播路由算法的研究[D].杭州:浙江大学,2002.

[7]郝琨,金志刚.一种基于确定性网络编码的P2P文件分发机制[J].应用科学学报,2014,32(3):247-251.

[8]徐光宪,吴巍,周佳.小生境遗传算法在网络编码优化中的应用研究[J].计算机工程,2015,41(7):152-157.

[9]杨卫华,王洪波,程时端,等.最小割路径路由算法[J].软件学报,2012,23(8):2119-2122.

[10]杜蔚琪.基于网络编码的无线传感网多径路由协议的设计与实现[D].南京:南京邮电大学,2014.

[11]师敏.基于PTN网管的路由路径算法研究[D].武汉:武汉理工大学,2013.

[12]沈蒙.网络虚拟化中的高效映射与流量管理研究[D].北京:清华大学,2014.

[13]周德荣,夏龄,舒涛,等.NS2网络协议虚拟仿真实验平台研究[J].实验技术与管理,2014,31(3):87-90.

[14]田生文.基础设施感知的覆盖网络构建理论研究[D].北京:北京邮电大学,2015.

[15]李文.机动通信网络中的多路径并行传输组网技术研究[D].北京:北京邮电大学,2015.

Centralized Network Coding Multicast RoutingAlgorithm*

XU Guangxian,LAI Junning+
College of Electronics and Information Engineering,Liaoning Technical University,Huludao,Liaoning 125105,China

A

TP393.02

+Corresponding author:E-mail:15604293995@163.com

XU Guangxian,LAI Junning.Centralized network coding multicast routing algorithm.Journal of Frontiers of Computer Science and Technology,2017,11(10)：1621-1628.

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology

1673-9418/2017/11(10)-1621-08

10.3778/j.issn.1673-9418.1608013

E-mail:fcst@vip.163.com

http://www.ceaj.org

Tel:+86-10-89056056

*The National Science and Technology Supporting Plan Foundation of China under Grant No.F2013BAH12F00(国家科技支撑计划项目);the Innovation and Entrepreneurship Training Program for College Students of Liaoning Province under Grant No.201610147047(辽宁省大学生创新创业训练计划项目).

Received 2016-08,Accepted 2016-10.

CNKI网络优先出版:2016-10-31,http://www.cnki.net/kcms/detail/11.5602.TP.20161031.1650.008.html

XU Guangxian was born in 1977.He received the Ph.D.degree from Liaoning Technical University.Now he is a professor and Ph.D.supervisor at Liaoning Technical University.His research interests include network coding and information processing.

徐光宪（1977—），男，江苏盐城人，博士，辽宁工程技术大学教授、博士生导师，主要研究领域为网络编码，信息处理。

LAI Junning was born in 1992.He is an M.S.candidate at Liaoning Technical University.His research interests include network coding and information processing.

赖俊宁（1992—），男，辽宁阜新人，辽宁工程技术大学硕士研究生，主要研究领域为网络编码，信息处理。