主权项 |
一种光组播路由方法实现最小光组播代价和最少波长使用量的联合优化方法,其特征在于,通过最短路径算法构造一棵最小代价组播树<i>T</i>;检查组播树<i>T</i>是否满足分光约束条件,对不满足分光约束条件的网络节点进行长路优先的新波长分配重路由操作寻找替代的重路由,使重路由需求的波长使用量最小,直至求得的光组播树满足分光约束且总代价最小;对不满足分光约束的组播树T,根据组播树T源节点的度数degree(s),将T划分为degree(s)棵子树,每颗子树计为<i>T</i>(<i>v<sub>i</sub></i>),<i>i</i>=1, 2, … , <i>degree</i>(<i>s</i>),对于每棵子树,确定该子树中距离源节点s最远且所在路径代价最大的那个目的节点<i>Far</i>(<i>v<sub>i</sub></i>)、路径<i>P</i><sup>1</sup>(<i>s</i>, <i>Far</i>(<i>v<sub>i</sub></i>))、边集<i>Edge</i>(<i>P</i><sup>1</sup>(<i>s</i>,<i>Far</i>(<i>v<sub>i</sub></i>)),同时确定源到任意一棵子树的目的节点<i>Far</i>(<i>v<sub>i</sub></i>)的最小代价路径,从波长分层网络<i>G<sub>k</sub></i>中删去与之对应的边集<i>Edge</i>(<i>P<sup>k</sup></i>(<i>s</i>,<i>Far</i>(<i>v<sub>i</sub></i>))得到子图<i>G<sub>k</sub></i><sup>’</sup>,重新确定边集<i>Live</i>(<i>Far</i>(<i>v<sub>i</sub></i>)),构建需要重路由的目的节点集合<i>UNREACH</i>,若<i>UNREACH</i>为空,则输出重路由后的光组播树;所述使重路由需求的波长使用量最小具体包括:选择<i>UNREACH</i>中距离源节点最远的目的节点<i>v</i><i>,</i>对于任意一颗子树<i>T</i>(<i>v<sub>i</sub></i>),<i>i</i>=1, 2, … , <i>degree</i>(<i>s</i>),根据其目的节点<i>Far</i>(<i>v<sub>i</sub></i>),为其构造一个子图<i>SG</i>,其中<i>SG</i>={<i>G<sub>j</sub></i><sup>’</sup>, <i>G<sub>j</sub></i><sup>’</sup>∪<i>Live</i>(<i>Far</i>(<i>v<sub>i</sub></i>)),<i>j</i>=1, 2, …, <i>k</i>+1 };在<i>degree</i>(<i>s</i>)个<i>SG</i>中寻找到<i>v</i>的最小代价路径<i>P</i>(<i>s</i>, <i>v</i>),并将该路径分配至当前波长分层网络<i>G<sub>j</sub></i>,其中,<i>G<sub>j</sub></i><sup>’</sup>代表从波长分层网络<i>G<sub>j</sub></i>中删去从源节点到任意一棵子树的目的节点<i>Far</i>(<i>v<sub>i</sub></i>)的最小代价路径边后剩余的子图。 |