This paper proposes an effective heuristic algorithm The tree constructed by DDMR has the following characteristics： for dynamic multicast routing with delay-constrained DDMR. （1） multicast tree changes with the dy...This paper proposes an effective heuristic algorithm The tree constructed by DDMR has the following characteristics： for dynamic multicast routing with delay-constrained DDMR. （1） multicast tree changes with the dynamic memberships; （2） the cost of the tree is as small as possible at each node addition/removal event; （3） all of the path delay meet a fixed delay constraint; （4） minimal perturbation to an existing tree. The proposed algorithm is based on “damage” and “usefulness” concepts proposed in previous work, and has a new parameter bf（Balancing Factor） for judging whether or not to rearrange a tree region when membership changes. Mutation operation in Genetic Algorithm （GA） is also employed to find an attached node for a new adding node. Simulation showed that our algorithm performs well and is better than static heuristic algorithms, in term of cost especially.展开更多
A layered algorithm by bidirectional searching is proposed in this paper to solve the problem that it is difficult and time consuming to reach an optimal solution of the route search with multiple parameter restrictio...A layered algorithm by bidirectional searching is proposed in this paper to solve the problem that it is difficult and time consuming to reach an optimal solution of the route search with multiple parameter restrictions for good quality of service. Firstly, a set of reachable paths to each intermediate node from the source node and the sink node based on adjacent matrix transformation are calculated respectively. Then a temporal optimal path is selected by adopting the proposed heuristic method according to a non-linear cost function. When the total number of the accumulated nodes by bidirectional searching reaches n-2, the paths from two directions to an intermediate node should be combined and several paths via different nodes from the source node to the sink node can be obtained, then an optimal path in the whole set of paths can be taken as the output route. Some simulation examples are included to show the effectiveness and efficiency of the proposed method. In addition, the proposed algorithm can be implemented with parallel computation and thus, the new algorithm has better performance in time complexity than other algorithms. Mathematical analysis indicates that the maximum complexity in time, based on parallel computation, is the same as the polynomial complexity of O(kn2-3kn+k), and some simulation results are shown to support this analysis.展开更多
文摘This paper proposes an effective heuristic algorithm The tree constructed by DDMR has the following characteristics： for dynamic multicast routing with delay-constrained DDMR. （1） multicast tree changes with the dynamic memberships; （2） the cost of the tree is as small as possible at each node addition/removal event; （3） all of the path delay meet a fixed delay constraint; （4） minimal perturbation to an existing tree. The proposed algorithm is based on “damage” and “usefulness” concepts proposed in previous work, and has a new parameter bf（Balancing Factor） for judging whether or not to rearrange a tree region when membership changes. Mutation operation in Genetic Algorithm （GA） is also employed to find an attached node for a new adding node. Simulation showed that our algorithm performs well and is better than static heuristic algorithms, in term of cost especially.
文摘A layered algorithm by bidirectional searching is proposed in this paper to solve the problem that it is difficult and time consuming to reach an optimal solution of the route search with multiple parameter restrictions for good quality of service. Firstly, a set of reachable paths to each intermediate node from the source node and the sink node based on adjacent matrix transformation are calculated respectively. Then a temporal optimal path is selected by adopting the proposed heuristic method according to a non-linear cost function. When the total number of the accumulated nodes by bidirectional searching reaches n-2, the paths from two directions to an intermediate node should be combined and several paths via different nodes from the source node to the sink node can be obtained, then an optimal path in the whole set of paths can be taken as the output route. Some simulation examples are included to show the effectiveness and efficiency of the proposed method. In addition, the proposed algorithm can be implemented with parallel computation and thus, the new algorithm has better performance in time complexity than other algorithms. Mathematical analysis indicates that the maximum complexity in time, based on parallel computation, is the same as the polynomial complexity of O(kn2-3kn+k), and some simulation results are shown to support this analysis.
