Optical Distribution Network Partitioning Method Based on Tabu Search

Abstract:

Since the 1970s, with the in-depth study of graph partitioning, we have found that, graph partitioning, both in the fields of academic researches and engineering applications, has its own important applications, such as the layout of the fiber-optic network in telecommunication network. Therefore, the graph partitioning problem has been widespread concerning and largely studied by the scholars at home and abroad. Tabu search, as one of the modern optimization algorithm, has been playing an invaluable effect in many fields. And by now, both graph partitioning and tabu search have been developed to a certain extent, but few people consider the integration of the two problems, coordinate optimization, so as to achieve better results. Therefore, this paper proposes a graph partitioning method based on coordination and optimization of constructive graph partitioning algorithm and tabu search algorithm and obtains a graph partitioning algorithms of good efficiency and quality. In the experimental part of the paper, optical distribution network partitioning problem is transformed into a graph partitioning model. Experimental results show that the efficiency and quality of the partitioning method are acceptable in optical distribution network division.

• Periodical: Applied Mechanics and Materials (Volumes 427-429)
• Pages: 2395-2398
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.427-429.2395
• Online since: September 2013
• Authors: Xia Gao*, Ya Gao
• Keywords: K-Way Graph Partitioning, Optical Distribution Network, Tabu Search

References

[1] GAREY M R, JOHNSON D S, STOCKMEYER L., in: Some Simplified NP-Complete Graph Problems, edited by Theoretical Computer Science, 1: 237-267(1976).

DOI: 10.1016/0304-3975(76)90059-1

[2] JOHNSON D S, ARAGON C R, MCGEOCH L A. , in: Optimization by Simulated Annealing: An Experimental Evaluation ; Part-I, Graph Partitioning, Operations Research(1989).

DOI: 10.1287/opre.37.6.865

[3] UNA BENLIC, Jin-Kao Hao, in: An Effective Multilevel Tabu Search Approach for Balanced Graph Partitioning, edited by Computers and Operations Research, 38(7): 1066-1075(2010).

DOI: 10.1016/j.cor.2010.10.007

[4] ERIK R, PIRKUL H, GLOVER F, in: Tabu Search for Graph Partitioning, edited by Annals of Operations Research, 63(2): 209-232(1996).

DOI: 10.1007/bf02125455

[5] Cui, Q., Ye, T., Lee, T. T. et al, in: Throughput and Efficiency of EPON Registration Protoco, edited by Journal of Lightwave Technology, 30(21): 3357-3366(2012).

DOI: 10.1109/jlt.2012.2217730

[6] Agata, A., Horiuchi, Y., Suboptimal ODN design algorithm for minimizing cable deployment cost. Optical Fiber Communication Conference and Exposition and the National Fiber Optic Engineers Conference, 1-3（2011).

DOI: 10.1364/nfoec.2011.jwa018

[7] M. STORE, F. WAGNER., in: A Simple Min-Cut Algorithm, edited by Journal of the ACM, 44(4): 585-591(1997).

[8] Sadegh Nobari, Thanh-Tung Cao, Panagiotis Karras et al., in: Scalable Parallel Minimum Spanning Forest Computation., edited by ACM SIGPLAN Notices, 47(8): 205-214(2012).

DOI: 10.1145/2370036.2145842

[9] KERNIGHAN B., LINIAL N., in: An Efficient Heuristic Procedure for Partitioning Graphs, edited by Bell Systems Technical Journal, 49(1): 291-30(1970).

DOI: 10.1002/j.1538-7305.1970.tb01770.x