基于链路共享度的网络编码多播路由算法

(广西大学 计算机与电子信息学院，南宁 530004)

基金项目：国家自然科学基金资助项目(60962002)；广西高校人才小高地建设创新团队资助计划项目(桂教人[2007]71号)；广西信息与通讯技术重点实验室资助项目(20904)；2010年广西研究生教育创新计划项目(105931003089)

FoundationItem:The National Natural Science Foundation of China(No.60962002);Program to Sponsor Teams for Innovation in the Construction of Talent Highlands in Guangxi Institutions of Higher Learning (GUIJIAOREN[2007]71);Foundation of Guangxi Key Laboratory of Information and Communication(No.20904)；2010 Innovation Projects of Guangxi Graduate Education(No.105931003089)

1 引 言

网络编码理论是对传统的存储-转发通信机制的重要变革，其本质是允许网络的中间节点对传输的数据进行编码操作处理[1]，以此来解决存储-转发的路由策略中所遇到的带宽瓶颈问题。文献[1]首次指出采用网络编码可以实现多播网络的传输容量上界，这也是网络编码最初被人们认识的主要优点，随后的一系列研究表明，网络编码在网络鲁棒性以及负载均衡性等方面也都表现出优越的性能。

针对网络编码的编码方案是目前的一个重要研究方向，其主要解决码字的构造问题，以便有效求得每条链路的编码向量。文献[2]给出了网络编码的代数编码框架并提出了网络编码的指数时间算法；文献[3]给出了网络编码的多项式时间算法；Ho等人提出了一种分布式算法，即随机网络编码算法[4]；文献[5]针对移动Ad Hoc网络，给出了一种冗余网络编码算法，具有较高的实际应用价值。

然而，网络编码要成功应用于多播传输中，其数据分发分为两个阶段：构造编码子图，即确定数据从信源到信宿的最佳分发路径；确定编码方案，即确定节点对收到的数据的编码模式。针对编码子图的构造问题，文献[6]给出了基于最大流的网络编码组播路由算法；文献[7]提出了一种在约简网络上搜索多播路径的方法;对于应用广泛的无线mesh网络，文献[8-9]中提出了适用网络编码的路由算法。但是，上述方法并没有考虑多条路径的最大共享链路，对网络资源的利用率不高。

传统的IP多播路由算法通过建立最短路径树(SPT)来实现数据分发，然而网络编码子图是mesh形状的拓扑结构，不同于传统多播树算法。本文提出一种新的基于链路共享度的网络编码多播路由算法(NCMSL)，其中链路共享度考虑在不增加链路负载的情况下减少链路资源消耗，而非文献[10]中的以链路代价的增加来增加链路的可共享性。仿真结果表明，结合随机网络编码，该算法能大幅度提高多播传输的性能。

2 随机网络编码

给定有向无环图G=(V,E,T)，V是节点集合，E是链路集合，T是信宿节点集合。信源S发送h维信息符号向量[x1,x2,…,xh]给信宿节点t(t∈T)。在随机网络编码中[4]，每个编码节点在一定大小的有限域GF(q)中独立地为其每条输出链路随机选取编码系数并对输入链路上的信息进行线性编码组合后转发到输出链路。每条链路上传输的编码信息有一个全局编码向量GC(e)与信源发送的原始h维信息向量相对应，使得链路e上传输的信息符号Y(e)满足下列关系：

Y(e)=GC(e)1×h×[x1x2…xh]T=

(1)

对于信宿节点t而言，可以通过其h条输入链路上的编码信息符号恢复h维原始信息符号。假设信宿t的h条输入链路分别为e1,e2,…,eh，各条链路上传输的编码信息构成向量[Y(e1)Y(e2) …Y(eh)]T，全局编码向量为[GC(e1)GC(e2)…GC(eh)]T，则：

(2)

式中，GC(ei)j表示t的第i条输入链路传输的编码信息对应于第j个原始信息符号的全局编码系数。

从式(2)可知，当且仅当h条输入链路上的全局编码向量构成的矩阵满秩时，信宿t通过X=GC-1Y可恢复出原始h维信息向量。

3 链路共享度

在网络编码的编码子图中，需要建立信源到每个信宿的多播传输路径。其中每个信宿节点的多条可分离路径构成一个路径集，不同信宿节点的路径集中会有共享链路。

定义1(共享链路)：设P(t1)和P(t2)分别为信源S到信宿t1和t2的路径上的链路集合，若P(t1)∩P(t2)={e}，则称{e}为路径P(t1)和P(t2)的共享链路。

定义2(链路共享度)：对于一个有向无环图G=(V,E),其中V为节点集，E为边集。indeg(i)表示节点i的入度， outdeg(i)表示节点i的出度。对有向链路e=(v,u),记λi(e)=v,λo(e)=u,λi(e)和λo(e)分别表示链路e的两个端点。链路e的链路共享度如式(3)所示：

D(e)=indeg(λi(e))+outdeg(λo(e))-1，
∀e∈E

(3)

链路共享度D(e)越大，则多条路径同时经过链路e的可能性越大。

定义3(可分离路径)[11]：两条路径是可分离路径当且仅当它们之间没有共享链路。

图1表明，在图1(a)所示的网络拓扑中，若要分别搜索信源S到信宿t1和t2的两条可分离路径，依据链路共享度的定义，应尽量选择链路(v1,v5)、(v2,v6)或(v3,v5)加入到所构建的路径集中。图1(b)、(c)分别为依据链路共享度搜索到的t1和t2的两条可分离路径的一种情况，(d)为合并后的路径，可见t1和t2共享了4条链路带宽资源。

(a)网络拓扑

(b)t1的可分离路径

(c)t2的可分离路径

(d)基于链路共享度的传输路径

图1 链路共享度
Fig.1 Link shareability

4 NCMSL算法描述

为了构建低代价的网络编码子图，需要考虑多播传输路径中链路的共享度。不同信宿节点的路径集中共享链路的数目越多，则网络编码子图中执行编码操作的节点数目越少，能有效减少网络中节点的计算开销和消耗的链路带宽资源，提高带宽资源的可共享性。

对于多播网络，要执行网络编码，需要确定每个信宿节点的多条可分离路径，使得传输信息通过多条可分离路径传送；不同的信宿节点的可分离路径集构成网络编码子图。

著名的Dijstra[12]算法是解决最短路径问题的有效方法，借助其搜索路径的思想，可简化路径搜索过程。本文提出的基于链路可共享度的网络编码多播路由算法(NCMSL)描述如下：

输入：网络G=(V,E,S,T), 多播网络信息传输速率h，以及可分离路径数目L；

输出：所有信宿tk的L(L≤h)条可分离路径，tk∈T。

步骤2:搜索信源S到信宿tk的第r(1≤r≤L)条可分离路径:

(1)D(i,j)表示链路e=(i,j)的共享度;令A=⟩，A′=V，Par(s)=0，Par(i)为当前搜索路径上节点i的前驱标号，用于回溯时追踪路径;Wi表示信源S(i∈V)到节点i的路径共享度(约定路径共享度为路径上所有链路共享度之和)，初始化为0；Ws初始化为某一足够大的正整数m。

(2)如果A=V,则Wtk为信源S到信宿tk的最大路径共享度，通过Par数组所记录的信息反向追踪可以获得最大共享度路径，结束；否则转入步骤3。

(3)从A′中找到共享度标号W最大的节点j，把它从A′中删除，加入A。在A中，对于所有从j出发的有向链路(j,i)∈V,若Wi

步骤3：若链路(i,j)存在于信宿tk的可分离路径集中，则将其对应的链路从网络拓扑图中删除，并更新链路共享度矩阵D，使得链路(i,j)不参与信宿tk的下一条可分离路径的搜索过程。

步骤4：若已找到tk的L条可分离路径，则转步骤5；否则，重复步骤2。

质量管理体系的不断完善对于提升钣金工艺技术水平具有良好的推动作用。结合上文分析的情况来看，我国的钣金企业目前在生产设计、设备管理以及原材料管控等多个方面都存在明显的缺陷，这不但会导致企业的发展迟滞，更会给整个行业带来不利的影响。通过完善质量管理体系，建设更高的技术标准与统一管理模式，可以实现优胜劣汰，将一些粗放的生产企业淘汰，同时引入先进的生产技术与制造工艺，净化市场环境的同时也促进了我国钣金工艺技术的发展。

步骤5：若k=|T|结束；否则，更新Copy-D矩阵，将当前信宿节点tk的可分离路径集中的链路在矩阵Copy-D中对应的链路共享度加m，即增大该链路的可共享性，使得后续信宿的可分离路径尽量共享该链路，置k=k+1，接着重复步骤2～4，为避免不同信宿可分离路径集之间的相互影响，每次初始搜索当前信宿的可分离路径时都使用更新后的Copy-D矩阵作为链路共享度矩阵。

5 性能仿真与分析

5.1 网络拓扑与编码模式

仿真实验中采用随机网络拓扑[13]，网络节点均匀分布，节点度控制在5.1～5.3之间，且利用随机网络编码进行编码。仿真结果如图2所示。从图2中可以看出，解码成功率随有限域增大而增大，当q为28时，解码成功率接近于1，且28的计算复杂度适中，因此在后续仿真实验中取q=28。

图2 有限域大小对解码成功率的影响Fig.2 Effect of finite field on decoding probability

5.2 性能仿真与结果分析

5.2.1平均带宽资源消耗

平均带宽资源消耗定义为多播算法中总的带宽消耗与网络多播速率的比值。仿真中假定带宽资源足够大，信源S的多播传输速率为200 bit/s。随机生成的网络拓扑中节点数为50，为每个信宿寻找4条可分离路径则，基于链路共享度的网络编码多播算法(NCMSL)与基于最短路径树(SPT)的传统IP多播算法的平均带宽资源消耗对比如图3所示。

图3 不同多播路由算法的带宽资源消耗(节点总数n=50)Fig.3 Bandwidth consumption of different algorithms(n=50)

仿真结果表明，随着信宿节点的增加，网络中平均带宽资源消耗是不断增加的，并且SPT算法的平均带宽资源消耗远远大于NCMSL算法的平均带宽资源消耗。这是因为随着信宿节点的增加，NCMSL算法中多个信宿节点的可分离路径集中可共享链路的数目越多，并且由于每个信宿节点的多播信息流是均匀分布在其多条可分离路径集中，因此每条链路的带宽消耗很小；而SPT多播路由算法中，信宿节点增加时，建立多播路径树所需的链路数目随之增加，并且由于到达每个信宿节点只有一条路径，因此要实现多播传输速率必须增加每条链路的带宽资源消耗。从图中可以看出，信宿节点数目越多，基于NCMSL的网络编码算法相比SPT算法对带宽资源的利用率越高。

5.2.2网络负载均衡性

当前Internet中网络资源有限，当带宽资源分布不均时，使得网络负载集中于少数几条链路上，便会产生网络拥塞现象，甚至会发生链路瘫痪，对整个网络性能造成严重影响。因此在设计路由算法时，应均衡合理利用网络中的带宽资源，使得整个网络负载均匀分布在较广泛的通信链路上。

图4所示为NCMSL网络编码多播算法和基于SPT的多播算法在网络负载分布均衡性方面的比较，其中网络负载均衡性表示多播算法中使用的链路数目占网络中总链路数目的百分比。从图中可以看出，NCMSL算法采用的链路数目在整个网络中的比例远远大于SPT算法采用的链路数目在整个网络中的比例，且NCMSL算法中每条链路的负载只有h/4,而SPT算法中每条链路的负载为h。NCMSL使得整个网络负载分布有更好的均衡性，减小了网络阻塞的概率。而SPT算法中网络负载仅仅集中在少数链路上，当网络中传输的信息流速率增加时，会大大增加每条链路的负担。

图4 不同多播路由算法的网络负载均衡性(节点总数n=50)Fig.4 Banalance of network load in different algorithms(n=50)

结合图3和图4可以看出，NCMSL算法在采用更广泛的通信链路的同时却大大减小了带宽资源消耗，同时减小了每条链路的负载，较好地提高了整个多播网络的传输性能。由于NCMSL算法在搜索网络编码子图时，充分考虑了每条链路的共享性，同时使得每个信宿节点可以同时从多条可分离路径同时接收多播信息流，从而使得整个网络负载分布均匀，结合网络编码算法，可提高整个多播网络的吞吐量。

6 结束语

本文通过引入链路共享度的概念，使得构建的网络编码子图最小化。研究表明，通过每次搜索路径时寻找共享度最大的链路加入多播路径，可以有效减少参与编码的节点数目和链路数目，从而实现最小代价网络编码。NCMSL算法指出充分利用网络带宽资源是提高网络传输性能的有效途径。

参考文献：

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

[2] Koetter R, Medard M. An algebraic approach to network coding[J]. IEEE/ACM Transactions on Networking,2003,11(5):782-795.

[3] Jaggi S,Sanders P,Chou P A,et al.Polynomial time algorithms for multicast network code construction[J].IEEE Transactions on Information Theory,2005,51(6):1973-1982.

[4] Ho T, Medard M, Koetter R, et al. A random linear network coding approach to multicast[J]. IEEE Transactions on Information Theory,2006,52(10):4413-4430.

[5] 梁智怡，覃团发，罗建中.一种移动Ad Hoc网络的冗余网络编码方法[J]. 电讯技术,2010，50(1):81-86.

LIANG Zhi-yi, QIN Tuan-fa, LUO Jian-zhong.Post-redundancy network coding strategy in mobile ad hoc networks[J].Telecommunication Engineering,2010,50(1):81-86.(in Chinese)

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

TAO Shao-guo,HUANG Jia-qing,YANG Zong-kai,et al.Maxflow-based routing altorithm for network coding multicast[J].Computer Science，2008,35(6):107-117.(in Chinese)

[7] 王静，刘景美，王新梅. 基于网络编码的多播路由算法性能分析[J]. 电子与信息学报，2008,30(11):2605-2608.

WANG Jing, LIU Jing-mei, WANG Xin-mei. Performance analysis of multicast routing algorithm based on network coding[J].Journal of Electronics and Information Technology,2008,30(11):2605-2608. (in Chinese)

[8] 覃团发，廖素芸，罗会平，等. 支持网络编码的无线Mesh网络路由协议[J]. 北京邮电大学学报，2009，32(1):14-18.

QIN Tuan-fa, LIAO Su-yun, LUO Hui-ping, et al. A network coding aware routing protocol in wireless mesh network[J]. Journal of Beijing University of Posts and Telecommunications,2009,32(1):14-18.(in Chinese)

[9] 覃团发，廖素芸，罗会平. 无线mesh网络中网络编码的文件共享模型[J]. 电讯技术,2008，48(5):17-20.

QIN Tuan-fa,LIAO Su-yun,LUO Hui-ping.The file sharing model based on network coding for wireless mesh network[J].Telecommunication Engineering,2008,48(5):17-20.(in Chinese)

[10] 王东，曾锋，闵应骅.基于链路共享性的多播路由算法[J]. 湖南大学学报，2006,33(4):111-114.

WANG Dong, ZENG Feng, MIN Yin-hua. A multicast routing algorithm based on shareability analysis[J].Journal of Hunan University,2006,33(4):111-114. (in Chinese)

[11] Zhu Ying, Li Bao chun. Multicast with network coding in application-layer overlay networks[J]. IEEE Journal on Selected Areas in Communications,2004,22(1):107-120.

[12] 谢金星，刑文训，王振波.网络优化[M]. 北京：清华大学出版社,2009:62-63.

XIE Jin-xing, XING Wen-xun, WANG Zhen-bo. Network Optimization[M].Beijing: Tsinghua University Press,2009:62-63.(in Chinese)

[13] Waxman B M. Routing of multipoint connections[J]. IEEE Journal on Selected Areas in Commuications,1988,6(9):1617-1622.