一种基于多核的多点到多点光组播路由方法

摘要

本发明涉及一种光网络中多点到多点组播的路由选择问题，提出构造多核共享树解决多点到多点的光组播路由问题，实现最小化波长使用数。使所有目的节点加入所有共享树，而源节点则通过链路分离路径加入一棵共享树。基于矩阵的启发式算法选择核点，使得核点数据最小的情况下保证每个源节点加入了组播树，这样节约波长信道。为进一步最小化波长使用数量，在构造共享树阶段，采用网络编码寻找网络编码路径。本发明采用的核点选择方法和构造共享树的方法，有利于最小化波长使用数量，提高光组播网络的波长资源利用率，使网络负载更为平衡。

主权项

一种多点到多点的光组播路由实现最小化波长使用量的方法，其特征在于：对节点集中的任意节点，寻找该节点到所有目的节点的两条编码路径P_code1、P_code2，若P_code1、P_code2中包含任何源节点，在节点集中删去该节点，遍历完节点集中所有节点后，得出的节点集为备选核点集V，针对备选核点集中的任一备选核点v_i，寻找源节点之间的链路分离路径P_{link disjoint}(v_i,s_i)，s_i表示源节点,构造源节点覆盖矩阵M_v，M_v中元素表示以节点v_i为核点的共享树覆盖源节点s_i的关系，其中，用R_i表示以核点v_i所能覆盖源节点的集合，M_v为1表示以v_i为核点的共享树能够覆盖源节点s_i，为0则表示以v_i为核点的共享树不能够覆盖源节点s_i,矩阵中的列表示对应的核点，行表示对应的源节点,通过对矩阵M_v操作完成以最少的核点覆盖所有的源节点，首先选择包含1最多的列，将该列所对应的备选核点v_i加入核点集中，然后删除该列和该列中1所对应的行，继续对删除了行和列的矩阵进行上述选择和删除操作，直到矩阵M_v成为空矩阵或全零矩阵，所有的核点都加入核点集中，完成了核点的选择；把从源节点到核点的链路分离路径加入共享树，首先用最短路径算法算出第一条最短路径做为第一条编码路径；搜索目的节点d_i的临近节点v_x，且v_x不在P_code1上；若v_x没有直接连接到另一目的节点d_j上，找到中间节点连接到d_j上；若v_x没直接连接到P_code1上，找到中间节点连接到P_code1上；若v_x直接连接到P_code1上，返回第二条编码路径P_code2，为核点构造共享树。