Optimizing the CMTS to Improve Quality of Service in Next Generation Networks based on ACO Algorithm
Автор: Dac-Nhuong Le
Журнал: International Journal of Computer Network and Information Security(IJCNIS) @ijcnis
Статья в выпуске: 4 vol.5, 2013 года.
Бесплатный доступ
In this paper, we focus on the network topological design for providing Quality of Service (QoS) in Next Generation Network (NGN) and propose an effective Ant Colony Optimization (ACO) algorithm to solve the capacitated minimum spanning tree (cMTS) problem in dynamic environment. To improve QoS of communication network with considering the network provisioning capability and dynamic environment, we formulate this problem with minimizing the communication cost (as a kind of performance measures for network's QoS). Our objective functions are determined by pheromone matrix of ants satisfies capacity constraints to find good approximate solutions of cMST problems. Numerical experiments show that our algorithm have achieved much better than recent researches.
Capacitated Minimum Spanning Tree (cMTS), Communication Network, Quality of Service (QoS), Next Generation Network, Ant Colony Optimization
Короткий адрес: https://sciup.org/15011180
IDR: 15011180
Текст научной статьи Optimizing the CMTS to Improve Quality of Service in Next Generation Networks based on ACO Algorithm
Published Online April 2013 in MECS
In Next Generation Network (NGN), the backbone of the overall network architecture will be IP network, supporting different access network technologies such as wireless Local Area Network (WLAN), UMTS Terrestrial Radio Access Network (UTRAN), and WiMax. Moreover, this integrated wireless system, will have to handle diverse types of traffics: data traffics (e.g. web browsing, e-mail, ftp), voice traffic (e.g. voIP), and multimedia traffics (e.g. video conferencing, online TV, online games), etc... NGN will provide advanced services, such as Quality of Service (QoS) guarantees, to users and their applications.
However, current Internet routing protocols such as Open Shortest Path First (OSPF), Routing Information Protocol (RIP), and Border Gateway Protocol (BGP) are called " best-effort " routing protocols, which means it will try its best to forward user traffic, but can provide no guarantees regarding loss rate, bandwidth, delay, delay jitter, etc. It's intolerable for NGN services, for example video-conferencing and video on-demand, which require high bandwidth, low delay, and low delay jitter. And provide the different type of network services at the same time is very difficult. Thus, the study of Quality-of-
Service (QoS) is very important nowadays [1]. To provide QoS in NGN, many techniques have been proposed and studied, including Integrated Services [2], Differential Services [3], MultiProtocol Label Switching (MPLS) [4], Traffic Engineering and QoS-based Routing [1]. And most problems can be formulated as the optimization models, such as the network reliability optimization model, shortest path routing model and constrained minimum spanning tree (MTS) model etc.
In [5], Lin Lin et al focus on the network topological design for providing NGN’s QoS. The authors formulated the problem as a extended capacitated minimum spanning tree (cMST) problem, which the objective is minimizing the communication cost (defined as a kind of performance measures for NGN’s QoS) with considering the following constraint:
-
• Consider the capabilities of the network.
-
• Define different priority for different types of services.
-
• Dynamic environment.
As we know, this cMST is NP-hard problem. In addition, the complex structures, complex constraints of this problem to be handled simultaneously, which make the problem intractable to traditional approaches. There are many Evolutionary Algorithms (EAs) have been successfully applied to solve constrained spanning tree problems of the real-life instances; and also have been used extensively in a wide variety of communication network design problems. In [6], the author used traditional Prim’s algorithm (without considering the capacity constraint) to solve MST. G. Raidl and B.A. Julstrom in [7] proposed Edge Sets: An Effective Evolutionary Coding of Spanning Trees. Zhou and Gen presented a note on genetic algorithm approach to the degree-constrained spanning tree problems in [8-9]. The authors in [5] proposed a PrimPred-based Evoluation Algorithm to solving cMTS. They adopted PrimPred-based encoding, Prim-based crossover, LowestCost mutation, Immigration operators and a parameter autotuning strategy.
In the latest paper [10-11], we have introduced two algorithms based on Particle Swarm Optimization (PSO) and Ant Colony Optimization (ACO) to solve the optimal communication spanning tree (OCST) problem finds a spanning tree that connects all node satisfies their communication requirements for a minimum total cost.
In this paper, we proposed a new ACO algorithm approach to solve NGN’s QoS problem. Numerical experiments with various scales of communication network problems show the effectiveness and the efficiency of our approach by comparing with the recent researches. The experimental results show that our algorithms have achieved much better than previous algorithms.
The rest of this paper is organized as follows: Section II presents the problem formulation the capacitated minimal spanning tree. Section III summarized the several kinds of classification of encoding methods for developing an EA to network design problems. Section IV presents our new algorithm for the capacitated minimal spanning tree based on ACO algorithm. Section V presents our simulation and analysis results, and finally, section VI concludes the paper
-
II. Problem Formulation
Following [5], The communication network is modeled using an edge-weighted undirected graph G =( V , E , Q , U ) with n nodes and m edges. Fig.1 presents a simple network with 12 nodes and 40 edges.

(a) Simple example of network

(b) A minimum spanning tree
Figure 1. A simple network with 12 nodes and 40 edges
The network data sets of 12 nodes and 40 edges defined in Table I.
The capacitated minimal spanning tree problem can be defined as follows:
Indices
-
• i, j, k=1, 2, ..., n , is index of node
-
• l=1..L is index of service type
Parameters
-
• n =| V is number of nodes
-
• m =| E | is number of edges
-
• qst e Q is requirement of type l form source node
s to sink node t.
-
• uy e U is capacity of edge ( i , j )
-
• w, e W is weight (priority ) of type l
communication service.
-
• dy e D is delay of edge ( i , j ) (or defined as a
kind of performance measures for NGN’s QoS), where dj-=E lwG (qj- j (1)
-
• G ( q l - Uy ) is function for delay defination of
service type l
Decision variables
-
• y j : the amount of requirement through arc( i , j )
-
• x ij : 0-1 decision variable
table i. The network data sets of 12 nodes and
40 edges
k |
Edge (i, j) |
Weight wi j |
1 |
(1, 2) |
35 |
2 |
(1, 3) |
23 |
3 |
(1, 4) |
26 |
4 |
(1, 5) |
29 |
5 |
(1, 6) |
52 |
6 |
(2, 3) |
34 |
7 |
(2, 4) |
23 |
8 |
(2, 5) |
68 |
9 |
(2, 6) |
42 |
10 |
(3, 4) |
23 |
11 |
(3, 7) |
51 |
12 |
(3, 8) |
23 |
13 |
(3, 9) |
64 |
14 |
(3, 10) |
28 |
15 |
(4, 5) |
54 |
16 |
(4, 7) |
24 |
17 |
(4, 8) |
47 |
19 |
(4, 10) |
24 |
20 |
(5, 6) |
56 |
21 |
(5,7) |
26 |
22 |
(5, 8) |
35 |
23 |
(5, 9) |
63 |
24 |
(5, 10) |
23 |
25 |
(6, 7) |
27 |
26 |
(6, 8) |
29 |
27 |
(6, 9) |
65 |
28 |
(6, 10) |
24 |
29 |
(7, 8) |
38 |
30 |
(7, 11) |
52 |
31 |
(7, 12) |
41 |
32 |
(8, 9) |
62 |
33 |
(8, 11) |
26 |
34 |
(8, 12) |
30 |
35 |
(9, 10) |
47 |
36 |
(9, 11) |
68 |
37 |
(9, 12) |
33 |
38 |
(10, 11) |
42 |
39 |
(10, 12) |
26 |
40 |
(11, 12) |
51 |
Mathematically, the problem is reformulated as a capacitated Minimal Spanning Tree (cMST) model is as follows:
(п\^
min f ( x ) = L | L Wi ХГ |mm { °, У у - « /у } ) l (2)
(I,j)e E к i=1 X
Subject to:
nn
LL Xj = n -1(3)
■=1 у = 1
nn
LL xj < SI — 1 for any set S of nodes(4)
i = 1 у = 1
nn
L У у - L у *
j=1
q j , if i = s
= - 0, if i ' e V - { 5 , t }
- q , if i = t
V ( 5 , t ) e source node and sink node of q j , V i e L
У j > 0, Vi, j = 1..n(6)
xj e{0,1}, Vi, j = 1..n(7)
where,
-
• The constraint (3) is a cardinality constraint implying that we choose exactly n-1 edges.
-
• The packing constraint (4) implies that the set of chosen edges contain no cycles (if the chosen solution contained a cycle, and S were the set of nodes on a chosen cycle, the solution would violate this constraint)
-
• The constraint (5) implies a flow conservation law depended communication requirement on the observed at each of the nodes other than sort.
-
• The constraint (7) implies the 0-1 variable x ij indicates whether we select edge ( i , j ) as part of the chosen spanning tree (note that if y ij >0 then x ij =1, else x ij =0).
-
III. Related works
How to encode a spanning tree T in a graph G is critical for developing an EA to network design problems, it is not easy to find out a nature representation. Because, designing an appropriate encoding method so as to build an effective EA.
In this section, we summarized the several kinds of classification of encoding methods as follows:
-
• Characteristic Vectors-based Encoding: used by Davis et al. (1993) [12], Bean (1994) [13],
Piggott and Suraweera (1995) [14].
-
• Edge-based Encoding: used by Knowles and Corne (2000) [15], Raidl (2000) [16-17], Chou et al.(2001) [8], Raidl and Julstrom (2003) [7].
-
• Node-based Encoding: is discussed by Cayley (1889) [18], Zhou and Gen (1997, 1999, 2000) [19-21].
In [8], Chou et al predecessor-based encoding generates some chromosomes that are illegal (i.e., not a spanning tree). Combining the simple random initialization, most of the chromosomes will be illegal due to three reasons: missing node i , self-loop, or cycles. The complex repair process will be used at each generation (computational cost), and after repairing, the offspring of the crossover and mutation are difficult to represent solutions that combine substructures of their parental solutions (worst heritability and locality).
Lin Lin and Mitsuo Gen in [5], proposed a PrimPred-based encoding, improved predecessor-based encoding. The initialization depends on an underlying random spanning-tree algorithm. The detailed procedure of this PrimPred-based encoding and decoding is introduced in [22].
-
IV. Ant Colony Optimization for the cMST
-
A. Ant Colony Optimization
The ACO algorithm is originated from ant behavior in the food searching. When an ant travels through paths, from nest food location, it drops pheromone. According to the pheromone concentration the other ants choose appropriate path. The paths with the greatest pheromone concentration are the shortest ways to the food. The optimization algorithm can be developed from such ant behavior.
The first ACO algorithm was the Ant System [23], and after then, other implementations of the algorithm have been developed [24-25].
-
B. Solving the cMST based on ACO
In this section, we present application of ACO technique for the cMST problem. Our new algorithm is described as follows. We consider that configurations in the algorithm are sets of n nodes.
The encoding of the ant k configuration is matrix by means, say k = { x j } where xy e { 0,1 } , V i , j = 1.. n . We use fully random initialization in order to initialize the ant population satisfied constraints (3) and (4). After that, the pheromone matrix y is generated with matrix elements that represent a location for ant movement, and in the same time it is possible receiver location.
We use real encoding to express an element of matrix У = { У у } where yy > 0, V i , j = 1.. n and computed by the formula (5).
The next node is selected according to the probability with which ant k will choose to go from current node i to next node j is calculated by the following formula:
k pij
t
E h ] * [ n , ]'
l e N k
In which, Tj is the pheromone content of the path from node i to node j, N k is the neighborhood includes only nodes that have not been visited by ant k when it is at node i , η ij is the desirability of node j , and it depends of optimization goal so it can be our cost function.
The influence of the pheromone concentration to the probability value is presented by the constant α , while constant β do the same for the desirability. These constants are determined empirically and our values are α=1, β=10 .
The ants deposit pheromone on the locations they visited according to the relation.
new current k
T, = T, + At,
where A T k is the amount of pheromone that ant k exudes to the node j when it is going from node i to node j.
This additional amount of pheromone is defined by:
AT ,
T ij
In which, d ij is delay of edge ( i , j ) (or defined as a kind of performance measures for NGN’s QoS) is computed by the formula (1). The cost function for the ant k is computed by the formula (2). The stop condition we used in this paper is defined as the maximum number of interaction N max ( N max is also a designed parameter).
The Fig.2 presents process of our algorithm to solve cMST based on ACO.

Figure 2. The ACO Algorithm’s flow chart
-
V. Experiments and Results
-
A. The problems tackled
For the experiments, we have tackled several cMST instances of different difficulty levels defined as follows:
We use the 3 complete network structures have 20 nodes (n=20) with 3 kinds of services:
-
• Type 1: Cable television.
-
• Type 2: IP phone.
-
• Type 3: Data
The weight (priority) of these 3 types respectively:
-
• w 1 =0.60
-
• w 2 =0.30
-
• w 3 =0.10.
The capacity of each edge ( i , j ) are represented as random variables depend on the uniform distribution: runif ( m , 100, 1000)
The 20 time-period requirements of different service types from node s to node t are represented as random variables depend on the distribution functions:
-
• Type 1: exponential distribution:
r * exp (| Q|, 0.03)
-
• Type 2: lognormal distribution:
0.1*r*lnorm(|Q|, 0.1, 0.1)
-
• Type 3: normal distribution:
r*norm(|Q|,0.01, 0.001)), where |Q|=100.
-
B. ACO algorithm specifications
In our experiments, we have already defined parameters for the ACO algorithm shown in Table II.
TABLE II. the aco algorithm specifications
Ant Population size |
K = 100 |
Maximum number of interaction |
N Max = 500 |
Parameter |
α=1, β=10 |
-
C. Numerical Results
In the experiment, our proposed ACO is compared with PrimPred-based EA [5] various evolutionary algorithms Edge-based EA [10], Prufer number-based GA [7] and traditional Prim’s algorithm (without considering the capacity constraint) [6].

Figure 3.Comparisons total time average delay results of five Algorthms
The objective function is total time average delay of our algorithms has achieved a much better performance than other algorithms. The experimental results show in Fig.3.
-
VI. Conclusion and Future Work
In this paper, we have proposed an effective ACO algorithm for improvement of Quality of Service in Next Generation Network. We have formulated this problem as an extended capacitated minimum spanning tree (cMST) problem with considering capabilities of the network, different priority for different types of services and dynamic environment. In our algorithm, the objective functions are determined by the total average time delay based pheromone matrix of ants satisfies capacity constraints to find good approximate solutions.
Numerical experiments with various scales of communication network problems show the effectiveness and the efficiency show that our algorithm is much better than the recent researches. Optimizing quality of service in Next Generation Network with considering capabilities, different types of services, profit, coverage area and throughput maximization in dynamic environment is our next research goal.
Список литературы Optimizing the CMTS to Improve Quality of Service in Next Generation Networks based on ACO Algorithm
- Sun, W., QoS/Policy/Constraint Based Routing, Technical Report, Ohio State University, 1999.
- Braden, R., Clark, D. and S. Shenker, Integrated Services in the Internet Architecture: an Overview, RFC 1633, 33 pages, 1994. http:/ /www.ietf.org/rfc/rfc1633.txt
- Blake, S. et. All, An Architecture for Differentiated Service, RFC 2475, 36 papes. ftp://ftp.isi.edu/in-notes/rfc2475.txt
- Callon, R., et. al., A frramework for Multiprotocol Label Switching, 69 pages, draft-ietf-mpls-framework-05.txt
- Lin Lin and Mitsuo Gen, Auto-tuning Evolutionary Algorithm for a Capacitated QoS Model in Communication Network, 2008.
- Hu, T.C, Optimum Communication Spanning Trees, SIAM Journal of Computing, 3(3), 188–195 (1974)
- Raidl, G and Julstrom, B.A, Edge Sets: An Effective Evolutionary Coding of Spanning Trees, IEEE Trans, on Evolutionary Computing, Vol. 7, No.3, pp.225-239, 2003.
- Chou, H., Premkumar, G. and Chu, C., Genetic algorithms for communication network design – an empirical study of the factors that influence performance, IEEE Trans, on Evolutionary Computing, Vol. 5, No.3, pp.236-249, 2001.
- Gen, M., Zhou, G and Takayama, M., Matrix-based genetic algorithm approach on bicriteria minimum spanning tree problem with interval coefficients, J.of Japan Society for Fuzzy Theory and Systems, vol.10, no.6, pp.643-656, 2000.
- Anh Tuan Hoang, Vinh Trong Le, Nhu Gia Nguyen, A Novel Particle Swarm Optimization- based Algorithm for the Optimal Communication Spanning Tree problem, Proceedings of The 2010 International Conference on Communication Software and Network (ICCSN 2010).pp.232-236, 2010.
- Dac-Nhuong Le, Nhu Gia Nguyen, and Nguyen Dang Le, A Novel Ant Colony Optimization-based Algorithm for the Optimal Communication Spanning Tree problem, 5th International Conference on Computer Science and Information Technology (ICCSIT 2012), December 29-30, 2012, IPCSIT, Vol.55, pp.81-86, Hongkong.
- L. Davis, D. Orvosh, A. Cox and Y. Qiu, A genetic algorithm for survivable network design, in Proc. 5th Int. Conf. Genetic Algorithms, pp. 408-415, 1993
- J. C. Bean, "Genetic algorithms and random keys for sequencing and optimization," ORSA J. Comput., vol. 6, no. 2, pp. 154-160, 1994
- P. Piggott and F. Suraweera. Encoding graphs for genetic algorithms: An investigation using the minimum spanning tree problem. In X. Yao, editor, Progress in Evolutionary Computation, LNAI 956, pages 305–314. Springer, Berlin, 1995
- Knowles, J. and Corne, D, A new evolutionary approach to the degree-constrained minimum spanning tree problem, IEEE Trans, on Evolutionary Computing, Vol. 4, No.2, pp.125-134, 2000.
- Rail, G, A weighted coding in a genetic algorithm for the degree-constrained minimum spanning tree problem, Proc. SAC(1), pp. 440-445, 2000.
- Raidl, G. and Drexe, C, A predecessor coding in an evolutionary algorithm for the capacitated minimum spanning tree problem, Proc. GECCO, pp. 309-316, 2000.
- A. Cayley, A theorem on trees, Quart. J. Math. 23 (1889), 376–378.
- Zho, G. and Gen, M., A note on genetic algorithm approach to the degree-constrained spanning tree problems, Networks, vol.30, pp. 105-109, 1997
- Zho, G. and Gen, M., Genetic algorithm approach on multi-criteria minimum spanning tree problem, E. J. of Operational Research, vol. 114, no. 1, pp. 141-152, 1999.
- Zho, G. and Gen, M., Approach to degree-contrainted minimum spanning tree problem using genetic algorithm, in M. Gen and R. Chen, Genetic algorithms & Engineering Design, New York: John Wiley, 2000
- Lin, L. and Gen, M, Node-based genetic algorithm for communication spanning tree problem, IEICE Transactions on Communications, vol.E89-B, no.4, pp.1091-1098, April 2006.
- M. Dorigo, V. Maniezzo, and A. Colorni, Ant system: Optimization by a colony of cooperating agents, IEEE Trans. on System, MAN, and Cybernetics-Part B, vol. 26, pp. 29-41, 1996
- E.Rajo-Iglesias, O.Quevedo-Teruel, Linear Array Synthesis using an Ant Colony Optimization based Algorithm, IEEE Trans. on Antennas and Propagation, 2005.
- M. Dorigo, M. Birattari, and T. Stitzle, Ant Colony Optimization: Artificial Ants as a Computational Intelligence Technique", IEEE computational intelligence magazine, November, 2006
- Dac-Nhuong Le, and Nhu Gia Nguyen, A New Evolutionary Approach for Gateway Placement in Wireless Mesh Networks, International Journal of Computer Networks and Wireless Communications (IJCNWC), Vol.2, No.5, pp.550-555, October 2012, India.