A Heuristic Algorithm for the QoS Problem Based on MultiConstraints

J4 ›› 2011, Vol. 33 ›› Issue (9): 19-23.

• 论文 • Previous Articles Next Articles

A Heuristic Algorithm for the QoS Problem Based on MultiConstraints

XIONG Lijun1,XIE Zheng2,CHEN Zhi2,ZHANG Jun3

(1.Corps 63655,Urumqi 841700;
2.School of Science,National University of Defense Technology,Changsha 410073;
3.School of Electronics and Information Engineering,
Beijing University of Aeronautics and Astronautics,Beijing 100083,China)

Received:2009-11-20 Revised:2010-03-26 Online:2011-09-25 Published:2011-09-25

Abstract

Abstract:

On the communication network, QoSbased routing has become the hot technique in order to fulfill the requirements of multimedia communications. Generally, finding a path in the network that satisfies multiple independent constraints is known to be NPcomplete. In this paper, we discuss the multiconstrained path (MCP) problem. By transforming the problem to discrete dynamic networks, which is acyclic, we propose a more efficient heuristic algorithm for QoS routing. The running time complexity is reduced from O(Tmn) to O(Tm), where m is the number of edges and n is the number of nodes, T is an integer defined by the algorithm. Further more, we theoretically prove the correctness of the algorithm. In the end, some experimental results are presented to show that the proposed algorithm performs better than other algorithms when used to solve the MCP problem. This improved heuristic algorithm can also be used in largescale networks.

Key words: QoS routing;path selection;multiconstraints;heuristic algorithm;MCP

XIONG Lijun1,XIE Zheng2,CHEN Zhi2,ZHANG Jun3. A Heuristic Algorithm for the QoS Problem Based on MultiConstraints[J]. J4, 2011, 33(9): 19-23.

A Heuristic Algorithm for the QoS Problem Based on MultiConstraints

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 0

Recommended Articles

Metrics

Comments