主权项 |
一种基于迭代编码的多约束组播路由算法,其特征在于包括:步骤1:输入网络拓扑结构,以及网络路由约束条件时延De<sub>req</sub>、时延抖动DJ<sub>req</sub>、吞吐量Th<sub>req</sub>、丢包率PLR<sub>req</sub>,利用组播树生成方法生成一个有向组播树;步骤2:基于步骤1,删除组播树中不满足丢包率PLR<sub>req</sub>约束条件的节点以及与这些节点相连的链路,删除不满足时延De<sub>req</sub>、时延抖动DJ<sub>req</sub>、吞吐量Th<sub>req</sub>的链路后,生成一棵组播树x<sub>j</sub>(t);其中t表示迭代次数,t为大于0的正整数;i和j分别表示不同的两棵组播树;步骤3:基于步骤1,再利用组播树生成方法随机生成一棵组播树x<sub>i</sub>(t);步骤4:根据组播树编码方法,合并步骤2与步骤3得到的组播树,生成新的组播树<img file="FDA0001129389570000011.GIF" wi="515" he="62" /><img file="FDA0001129389570000012.GIF" wi="44" he="46" />表示组播树x<sub>i</sub>(t)和x<sub>j</sub>(t)合并为一棵新的组播树x<sub>j</sub>(t+1),合并后的节点集合为x<sub>i</sub>(t)和x<sub>j</sub>(t)所包含的所有节点,链路集合为x<sub>i</sub>(t)和x<sub>j</sub>(t)所包含的所有链路;步骤5:如果组播树x<sub>j</sub>(t+1)满足路由约束条件或者计算过程达到迭代次数,则执行步骤6;否则,t=t+1,执行步骤2;步骤6:输出组播树x<sub>j</sub>(t+1);所述步骤4中组播树编码方法具体包括:步骤41:从目标节点集合M中选择第i个节点作为当前节点,判断i是否大于M的大小,若是,则执行步骤44,否则,执行步骤42;其中i范围是1到目标节点集合M的数量;步骤42:判断当前节点是否为源节点,当前节点不是源节点时,执行步骤43;否则,转步骤41,i=i+1;步骤43:判断当前节点的先验节点数量是否大于1,若先验节点数量大于1,则随机选择一个先验节点作为当前节点,转步骤42;否则,当前节点作为先验节点,转步骤44;步骤44:输出不存在环路的组播树x<sub>j</sub>(t+1)。 |