基于网络编码的多源多核点光组播路由算法

黄 胜，王 琰，刘焕淋，秦 亮

(重庆邮电大学光纤通信技术重点实验室重庆 400065)

0 引言

组播技术是中间节点对信息进行复制与转发的信息传递技术［1］，与单播相比可极大地节省带宽。其中，光层组播通过分光器实现信息复制，与传统IP组播相比，避免了光/电/光转换，性能有所提高，且保证服务质量。不过，传统的光组播需消耗大量波长资源，使带宽资源紧张，网络传输质量下降［2］。2000年，Ahlswede等［3］首次提出了网络编码的概念，指出网络编码可有效减少链路使用波长数，提高网络吞吐量。2003年，Li等［4］提出了单源组播网络中具体的线性网络编码实现方式。从此，网络编码不再只停留在理论层面。

网络编码在光层组播中的应用需解决2个问题:①组播路由的确定，即编码子图［5］的构造;②编码方案的选取。光组播网络可分为单源［5－6］和多源［7］，其中，在单源光组播网络中，编码子图和编码方案的研究已比较成熟。多源光组播由于在生活中应用广泛(如多方视频会议等)一直受到研究者们关注，但相关的研究成果并不显著。多源组播网络路由问题的研究，即编码子图的构建，主要可分为2种:① 建立有源树［8］，即为每个源建立一棵组播树;② 在网络中建立共享树［9－14］，即寻找核心节点，以核心节点为根建立组播树。考虑到有源树占用较多网络资源且不一定能保证服务质量，现多采用建立共享树的方式来解决路由问题。而现有多源光组播中的编码方案仍存在或多或少的缺点，导致多源编码路由方法研究成果更少:如文献［7］根据源节点将多源网络划分为多个子图，从而把多源网络转换为单源，然后，运用线性网络编码，提高网络吞吐量。该算法不适用于大多数链路容量不支持划分为多个子图的网络，但确实解决了多源编码问题。根据上述2个方面的分析，本文选取核心节点将多源网络转换为单源，采用单源组播中的随机线性网络编码［15］方案，建立共享树来研究多源光组播中路由问题。

为解决基于网络编码的多源光组播路由问题，文献［10］提出一种基于分布式网络编码的共享树构建方法，根据源节点选取核心节点，并直接选择到各目的节点的2条通路构成共享树，均衡网络负载，减少波长消耗。但该算法会因目的节点数目增加而消耗大量链路与波长资源来传输编码信息保证解码。文献［11－12］均根据源节点选取核心节点，并设置该节点为编码节点，构建约简网络，以核心节点为根构造共享树，不过算法仿真拓扑源节点固定为2，只能通过增加源节点组播率来增加网络传输数据量，算法适用范围再次缩小，且该共享树构造方法同样受目的节点数目影响。文献［10－12］中都是在核心节点与每个目的节点之间寻找2条可分离路径构建共享树，因此，可能出现目的节点只接收到部分源节点数据的现象，或为接收到全部数据，牺牲编码子图中的波长资源，为解决该问题，本文参考了文献［6］中基于最大流思想构建编码子图的思想，即为最大流h寻找h条链路分离路径(路径间没有链路重合)，来保证实现网络最大流。

基于以上分析，本文在每个源节点需要将数据传输给所有的目的节点的特殊多源网络［3］，提出一种基于网络编码的多核组播路由算法(multi－core multicast routing algorithm based on network coding，MCMR－NC)，为最大流h寻找h条可分离路径构建共享树，并为目的节点寻找多个核心节点，这些核心节点负责解码并将解码信息传输给一定范围内的目的节点。与上述算法相比，本算法能最大限度减少目的节点数目对编码子图的影响，简化目的节点加入过程，减少链路、波长消耗。

1 基于网络编码的多源组播路由

因为多源光组播网络中编码方案的构造还不够成熟，所以，一般将多源光组播网络通过选取核心节点或划分子图等方式转换为相应的单源网络。将网络根据源节点划分子图相当于构建有源树，该方法占用较多网络资源，只适用于源节点很少的情况下解决路由问题。选取核心节点将多源网络转换为单源，相当于在以核心节点为源节点的单源网络中解决路由问题。该方法中多个源节点发送的数据可共享链路和波长资源，更为合理。

基于网络编码的组播路由问题基本相当于选择传输编码数据的通路，构建编码子图问题。

多源组播光网络转换为单源，运用随机线性网络编码进行数据传输的情况如图1所示。节点D有2条输入链路1条输出链路，为编码节点。图1a中，源节点发送数据总数为2，需2条链路分离路径使解码节点收到的数据分别为a，a⊕b和b，a⊕b，成功解码出a，b。将图1a推广到一般情况。

图1 组播网络编码示意图Fig.1 Network coding in multicast network

用有向赋权图G(V，E，W)表示多源组播网络，V为节点集;E为链路集;W为边权重集合，代表链路长短，称为链路代价;源节点集S={S1，S2，…，S|S|};目的节点集 D={D1，D2，…，D|D|};将网络中源节点和目的节点之外的节点称为中间节点，用集合M表示;网络中源节点组播率为1。

将源节点发送的数据用 k=［k1，k2，…，k|S|］表示;解码节点接收到的数据用 b=［b1，b2，…，b|S|］表示。由于网络采用随机线性网络编码，则编码子图中传输的数据均为源节点输出向量k中各元素的线性组合:bi=ci1k1+ci2k2+ … +ci|S|k|S|，i=1，2，…，|S|。解码节点接收到的信息可表示为

通过方程k=(C-1b)T可译出原始数据。由该方程可知，为保证C矩阵可逆，C应为满秩，此时需要传输的|S|个信息线性独立。

若想解码出原始数据，解码节点需接收到|S|个线性独立的编码信息。此时，需要|S|条通路传输这些编码信息，即组播率为1的多源组播路由中若要保证解码，必须有|S|条通路连接源节点与解码节点。该条件是网络编码光组播路由的前提。

文献［10－12］中均使用2条通路传输编码信息，一定程度上减少了编码子图大小，但当源节点发送信息增加，算法只能通过增大固定通路上的波长消耗来增加传输编码信息通路数，不利于网络总数据传输量增加。图1中，当源节点传输数据由2增加到4时，共享树(编码子图)上链路平均波长使用量增加1倍。文献［5］中引入链路共享度定义，增加编码子图中链路共用次数，减少编码子图。

以上算法均选取核心节点将网络转换为单源，并在保证解码的前提下，尽可能减小编码子图，优化网络链路代价和波长资源。但解码节点均为目的节点，使目的节点的增加对编码子图影响很大，解码所需编码信息传输消耗的波长资源和链路代价随之明显增加。

基于以上分析，本文提出一种寻找多个核心节点的网络组播共享树构建方法，首先，算法通过为源节点寻找单核点将网络转换为单源，然后，将解码设置到为目的节点选取的多个核心节点上，减少目的节点变化对编码子图大小的影响。通过用|S|条链路分离路径构建编码子图，使编码子图上波长消耗一直为1，增大网络总的数据传输量。

2 基于网络编码的多核组播路由算法

根据多源光网络组播路由问题的分析，可知解决组播路由问题需要:①有|S|条通路传输线性独立编码信息;②减少编码子图链路代价和波长消耗。

针对条件①，算法根据源节点选取一个核心节点将多源网络转变为单源，以该节点为根在各解码节点间搜索|S|条链路分离路径，建立一棵主共享树(编码子图)，以保证编码子图波长消耗尽可能小。针对条件②，将根据目的节点选取的核心节点集设为解码节点，并建立传统共享树(子共享树)，将解码信息传输到目的节点，通过减少解码节点数来减少需要寻找的路径簇数，使总的寻找通路数减少;引入链路共享度［5］概念，使不同路径簇间链路尽可能的共用，链路共用数目增加，消耗的链路总数减少。

为方便描述，我们将数据传输路径分成3个部分:①从源节点到主共享树根节点称为源区域;②主共享树所占区域称为核心区域;③子共享树的集合称为目的区域。其中，核心区域入节点，即主共享树的根节点我们称为in-core节点。子共享树根节点，也是核心区域出节点，称为out-core节点。

基于网络编码的多核组播路由算法大概步骤如下:当组播请求到达，首先，根据网络拓扑G，选取incore与out-core set构造主共享树;然后，根据选定的out-core set和网络拓扑G中目的节点构建子共享树。

2.1 主共享树构建方法

主共享树(算法中的编码子图)以in-core为根，寻找该节点到每个out-core间的多条链路分离路径。主共享树链路负载一直为1，有大量剩余波长资源可用于传输源节点发送的其他数据或其他源节点发送的数据。为发挥网络编码优势，减小目的区域传统共享树的波长资源消耗，设置链路代价限制Δ，out-core节点只能在该限制范围内连接目的节点，使out-core尽可能地靠近目的节点。

主共享树具体构建步骤如下。

步骤1 按照组播请求，根据源节点确定incore，使所有源节点到该核心节点距离之和最小。

①判断中间节点的出度。选择出度大于等于|S|的中间节点作为in-core的候选集，即:

③若多个候选节点代价和相同，选择使用总链路跳数最少的节点作为in-core。

步骤2 根据确定的in-core节点，按照以下方法确定out-core节点。设out-core节点集中共有i个节点，i∈［1，|D|)。具体操作如下。

①判断中间节点m的入度。根据分析，候选out-core入度至少为|S|:out-core_candidate set1={min_degree≥|S|}，m ∈M

② 判断in-core与out-core_candidate set中各节点之间的最大流，保证2点之间能够找到|S|条链路分离路径:

③ 用矩阵法［14］验证候选out-core与目的节点之间的覆盖关系，得到最少out-core节点，即为最终确定的out-core集。

out-core与目的节点之间的关系可以看作一种集合覆盖问题。矩阵法是文献［14］提出的一种基于矩阵解决集合覆盖问题的启发式算法，操作较为简单。矩阵法大体思想在本算法的体现是设置参数Δ，只有out-core候选节点与每个目的节点之间的最短距离在Δ以内时，out-core候选节点与目的节点相连。建立一个大小为|D|×|out-core_candidate set|的覆盖矩阵Mv，矩阵中数值表示out-core与目的节点D之间的连接关系。每个out-core对应一列。按照以下对应关系建立Mv:

优先选择连接目的节点最多的out-core候选节点(“1”最多的列)加入out-core set中，删去该列以及该列中“1”对应的行，使目的节点不重复连接到outcore上。重复上述操作，直到Mv为空集。当有outcore候选节点连接目的节点数目相同，分别对其进行验证，选择含节点数最小的集作为最终选定的out-core。

步骤3 以in-core为根，寻找到out-core set中每个节点的i组路径簇，每个路径簇包含|S|条链路分离路径。

①用Dijkstra算法在网络中搜索in-core和outcorei之间的最短路径，将其加入out-corei对应的第i个路径簇中，设置该路径中链路代价为无穷大，即不再连通;

② 重复①，直到第i个路径簇中有|S|条路径;

③将路径簇中链路的代价设为0.1，以提高核心区域链路共享度，i=i+1，转向1。

步骤4 将步骤3确定的i组路径簇加入主共享树，主共享树构造完成。

源节点通过最短路径与选定的in-core相连。图2，图3分别为网络编码和网络拓扑示意图。

图2 网络编码示意图Fig.2 Network coding diagram

图3 网络拓扑示意图Fig.3 Network topology diagram

考虑到图2中网络拓扑出现的可能性，若core没有编码能力，链路core-D上无论传输a，b或c，解码节点D2和D3总不能同时接收到源节点发送的信息。因此，算法中in-core节点一定具有编码能力。

步骤3得到的路径簇中路径分别为2点之间的最短路径、次短路径…。但在图3中，A和D之间的最大流为2，若链路代价如图3所示，那么寻找到的最短路径为A-B-F-G-D，将之设为不连通后，A和D之间将不存在路径相连。针对这种情况，可找出A和D间的所有路径，进行对比组合，最后，得到2条链路分离路径，但不保证为最短或次短路径。

2.2 子共享树构建方法

算法中的子共享树定义为以out-core为根，寻找到目的节点的最短路径加入树中建立的传统共享树。子共享树通过减少根节点与目的节点之间的路径数来减少目的节点增加对算法链路代价的影响。当新加入的目的节点与核心节点距离在限制范围Δ内时，只需增加一条最短路径就能将源节点数据传输到目的节点。

子共享树构建具体步骤如下。

步骤1 根据组播请求、网络拓扑G和out-core节点集，用Dijkstra算法搜索out-corei与每个目的节点间的最短路径，存入P1中。

步骤2 将最短路径集P1中路径代价不大于Δ的路径选出，存入P2中。

步骤3 每个目的节点对应P2中的一条路径，若多个out-core节点连接到同一目的节点上，选择有最小链路代价的路径;当链路代价相同时，选择跳数较少的路径。因为路径中链路代价越小、跳数越少，意味着子共享树消耗的链路代价和波长资源越少。

至此，算法完成。图4为算法可能得到的数据传输图及波长消耗情况。图4中，源节点发送数据分别为a，b，c，在in-core和out-core间寻找3条链路分离路径。out-core不需在in-core处编码就能解码成功，因此，本例中in-core节点不编码，但一直有编码能力。编码子图中节点D为编码节点。

图4 多核点共享树示意图Fig.4 Multi－core shared－tree diagram

3 仿真与性能分析

为验证本文提出的MCMR－NC算法性能，下面将其与传统共享树(shared tree algorithm，ST)算法、基于网络编码的共享树算法［11］(shared tree based on network coding algorithm，ST－NC)进行对比。

3.1 仿真环境与评价指标

本文采用matlab7.0来构建仿真平台，每次组播请求变换一个随机拓扑［16］，将随机拓扑节点的平均度数设置为4，拓扑中根据链路长度生成的权重值设为该条链路的链路代价。选择拓扑中只有出度没有入度的节点作为源节点，只有入度没有出度的节点作为目的节点。网络中节点均具有分光能力，每条链路中波长数目能满足组播请求。

本文采用以下3个参数来验证MCMR－NC算法的性能。

1 )链路代价。链路代价是网络中数据传输使用的链路代价总和。在不考虑波长消耗的前提下链路代价越小越好。网络编码的提出，使研究目标从用最短的链路传输有限数据变化为充分利用链路容量，使链路能够尽可能多地传输不同的数据。

2 )波长资源消耗［11］。即网络中为一个请求所消耗的所有波长总和。相同组播请求下，波长消耗得越少越好。

3.2 仿真结果与分析

算法主要验证目的节点数目变化对网络性能的影响，所以，固定网络节点数目为100，源节点数目为4，变化目的节点数目并用链路代价、波长资源消耗和链路平均负荷来分析3种算法的性能。

1 )链路代价。目的节点与链路代价关系如图5所示。

图5 目的节点与链路代价关系图Fig.5 Number of destination node VS link cost

图5中，2种对比算法的链路代价随目的节点增加明显增加，MCMR－NC算法的链路代价在目的节点大于20后增长速度变得缓慢。因为在网络规模一定的情况下，目的节点越大，相对分布越紧密，已确定的out-core能满足覆盖需求，不需要增加，使得编码子图大小不变;此时，目的节点数目增加，只需消耗out-core节点到目的节点的一条最短路径，因此，链路代价变化很小。

2 )波长资源消耗。目的节点与波长消耗关系如图6所示。

图6 目的节点与波长消耗关系图Fig.6 Number of destination nodes VS wavelength resource consumption

图6中，随目的节点增加，3种算法波长消耗均增大，MCMR－NC算法的波长消耗始终小于对比算法，且随目的节点数目增加，与2种对比算法之间的差值逐渐增大。这是因为若增加的目的节点在outcore节点集覆盖范围内，那么，MCMR－NC算法编码子图中波长消耗不变，只需消耗少量波长资源将解码信息发送给目的节点。而基于网络编码的共享树算法和传统共享树算法需为每个目的节点重新寻找分离路径或最短路径，消耗的波长较多。

3 )链路平均负荷。目的节点与链路平均负荷关系如图7所示。

图7中，传统共享树平均链路负荷远高于其他2种算法，在3.6～3.8区间内变化。ST－NC算法由于源节点固定为4，编码子图中每条链路需消耗2个波长，链路平均负荷近似为 2;MCMR－NC算法中核心区域每条链路消耗一个波长，目的区域每条链路消耗4个波长，因此，平均链路负荷受各区域链路数目在总的链路数目中所占比重影响，与链路负荷性能较好且比较稳定的ST－NC算法总体相差不大:2种算法差值最大是目的节点为30时，相差0. 19;当目的节点为25时，差值最小为0.01。

图7 目的节点与链路平均负荷关系图Fig.7 Number of destinations nodes VS the average link load

由仿真结果可知，MCMR－NC算法通过减少编码子图链路代价和波长消耗，限制目的区域共享树大小，使得在目的节点较多的网络中，波长消耗小于2种对比算法，链路代价性能有所改善。

4 结束语

本文提出一种基于网络编码的多核点组播路由算法，将传统共享树和基于网络编码的共享树相结合，通过为目的节点选取多个核心节点减少目的节点变化对编码子图的影响。该算法适合目的节点数目较多，且分布相对密集的网络。算法的链路代价、波长资源消耗性能均有改善，链路平均负荷虽受网络拓扑影响，但总趋势与链路平均负载性能较好的网络编码共享树算法相近。

［1］刘焕淋，谢芸徽，李祯，等.基于免疫算法的光组播最少网络编码链路研究［J］.重庆邮电大学学报:自然科学版，2011，23(4):384－388.

LIU Huanlin，XIE Yunhui，LI Zhen，et al.Study on minimizing network coding links based on immune algorithm for optical multicast network ［J］.Journal of Chongqing University of Posts and Telecommunications:Natural Science Edition，2011，23(4):384－388.

［2］刘焕淋，方强，王杨杨，等.WDM网状网络中一种动态多播自适应业务疏导算法［J］.光电子·激光，2013，24(1):69－74.

LIU Huanlin，FANG Qiang，WANG Yangyang，et al.An adaptive algorithm for dynamicmulticast traffic grooming in WDM mesh networks［J］.Journal of Optoelectronics·Laser，2013，24(1):69－74.

［3］AHLSWEDE R.，CAIN.，LI S.Y R.，et al.Network information flow［J］.IEEE Transactions on Information Theory，2000，46(4):1204－1216.

［4］LI S.Y R，YEUNG R W，CAI Ning.Linear network coding［J］.IEEE Transactions on Information Theory，2003，49(2):371－381.

［5］罗莉，覃团发，罗建中，等.基于链路共享度的网络编码多播路由算法［J］.电讯技术，2011，51(3):79－83.

LUO Li，QIN Tuanfa，LUO Jianzhong，et al.A Routing Algorithm for Network Coding Multicast Based on Shareable Links［J］.Telecommunication Engineering，2011，51(3):79－83.

［6］TAO Shaoguo，QIAO Wenbo，YANG Zongkai，et al.Routing Algorithm of Network Coding on Multicast［C］//International Conference on Computational Intelligence and Security Workshops.Harbin，Heilongjiang，China:IEEE Press，2007:354－357.

［7］PU Baoxing，YANG Luming，WANG Weiping，et al.Linear Network Coding Construction forMulti－source Multicast Network［C］//First InternationalWorkshop on Education Technology and Computer Science.Wuhan，China:IEEE Press，2009(3):114－118.

［8］CHEN YuhRong，RADHAKRISHNAN Sridhar，DHALL Sudarshan，et al.On multi－stream multi－source multicast routing［J］.Computer Networks，2013(57):2916－2930.

［9］SEKINE Y，MIKOSHI T，TAKENAKA T.Shared－Tree selection method for aggregated multicast［C］//2012 18th Asia－Pacific Conference on Communications(APCC).Jeju island，Korea:IEEE Press，2012:760－764.

［10］肖昊明，张敏，阳小龙.一种基于分布式网络编码的共享树光组播算法［J］.计算机应用研究，2009，26(12):4719－4721.

XIAO Haoming，ZHANG Min，YANG Xiaolong.Shared tree opticalmulticast algorithm based on distributing network coding ［J］.Application Research of Computers，2009，26(12):4719－4721.

［11］王汝言，刘成耀，吴大鹏.一种基于网络编码的共享树组播算法［J］.半导体光电，2010，31(5):767－770 ，786.

WANG Ruyan，LIU Chengyao，WU Dapeng.A Sharedtree Multicast Algorithm Based on Network Coding［J］.Semiconductor Optoelectronics，2010，31(5):767－770，786.

［12］LU Zhengqiu，HEGuangjun.Research ofMulticast Routing Protocol in Wireless Sensor Networks Based On Network Coding［C］//2012 7th International Conference on Computer Science ＆ Education(ICCSE).Melbourne，Australia:IEEE Press，2012:354－356.

［13］HIROTA Y，HONDA H，TODE H，et al.Multicast Design Method Using Multiple Shared－Trees in Optical WDM Networks［J］.IEICE TRANSACTIONSon Communications，2012，95(2):370－381.

［14］张琨，王珩，刘凤玉.一种时延约束的多共享组播树构造算法［J］.南京理工大学学报，2006，30(2):127－131，141.

ZHANG Kun，WANG Heng，LIU Fengyu.Delay－constrained Multiple Shared Multicast Trees Construction Algorithm［J］.Journal of Nanjing University of Science and Technology，2006，30(2):127－131，141.

［15］HO T，MEDARD M，KOETTER R，et al.A Random Linear Network Coding Approach to Multicast［J］.Information Theory，IEEE Transactions on，2006，52(10):4413－4430.

［16］SALAMA H F，REEVESD S，VINIOTISY.Evaluation ofmulticast routing algorithms for real－time communication on high－speed networks［J］.IEEE Journal on Selected Areas in Communications，1997，15(3):332－345.

(编辑:刘 勇)