International Journal of Advanced Networking and Applications

Open Access Open Access  Restricted Access Subscription Access

A New Multi-Objective Optimization in Solving Graph Coloring and Wireless Networks Channels Allocation Problems


Affiliations
1 School of Computing, SASTRA Deemed University, Thanjavur-613401, India
 

Graph coloring problem, a combinatorial optimization problem is being widely applied in solving the channels allocation in wireless networks. This paper exhibits a new evolutionary genetic multi-objective strategy that uses the combined single and multi-parent conflict-gene crossover and combined single and multi-parent conflict-gene mutation operators with clique partitioning to solve the graph coloring and channel allocation problems. The proposed operators minimize problem search space by reducing the expected number of genetic generations. A general fitness function is defined on finding the total conflicting edges in the graph for the initial and particularly the successive generations of individuals in the population. The outcomes of this proposed method are better than the well-known methods and are compared with some of the benchmark graph coloring and channel allocation problems. The devised method of clique partitioning with genetic operators also enhances the successful runs.

Keywords

Approximation Methods, Channel Allocation, Chromatic Number, Genetic Algorithm, Graph Coloring, Wireless Networks.
User
Notifications
Font Size

  • L.Mumford: New order-based crossover for the graph coloring problem, T. P. Runarsson et al. (Eds.): PPSN LX, vol. 4193, pp. 80-88, 2006.

  • G. Rudolph: Finite Markov chain results in evolutionary computation: A tour Horizon, Fundamenta Informaticae, vol. 35, no.2, pp. 67-89.

  • Ling-Yuan Hsu; Shi-Jinn Horng; Pingzhi Fan; Muhammad Khurram Khan; Yuh-Rau Wang; Ray-Shine Run; Jui-Lin Lai; Rong-Jian Chen: MTPSO algorithm for solving planar graph coloring problem Expert Syst. Appl., 38:5525–5531, May 2011.

  • Shih Heng Cheng; Ching Yao Huang: Coloring-Based Inter-WBAN Scheduling for Mobile Wireless Body Area Networks, IEEE Transactions on parallel and distributed systems, vol. 24, no. 2, 2013.

  • Elmahdi Driouch; Wessam Ajib: Downlink Scheduling and Resource Allocation for Cognitive Radio MIMO Networks, IEEE Transactions on vehicular technology, vol. 62, no. 8, 2013.

  • Elmahdi Driouch; Wessam Ajib: Efficient Scheduling Algorithms for Multiantenna CDMA Systems, IEEE Transactions on vehicular technology, vol. 61, no. 2, 2012.

  • Matti Peltomäki; Juha-Matti Koljonen; Olav Tirkkonen; Mikko Alava:: Algorithms for SelfOrganized Resource Allocation in Wireless Networks, IEEE transactions on vehicular technology, vol. 61, no. 1, 2012.

  • The Graph Coloring instances, http://mat.gsia.cmu.edu/COLOR/instances.html.

  • Soma Saha; Rajeev Kumar; Gyan Baboo: Characterization of graph properties for improved Pareto fronts using heuristics and EA for bi-objective graph coloring problem, Applied Soft Computing, ASOC-1644, 2012.

  • Sethumadhavan, G; Marappan, R.. A Genetic Algorithm for Graph Coloring using Single Parent Conflict Gene Crossover and Mutation with Conflict Gene Removal Procedure, 2013 IEEE International Conference on Computational Intelligence and Computing Research, India, pages 350-355, 26-28 December 2013.

  • Marappan, R.; Sethumadhavan, G. Solving Graph Coloring Problem for Large Graphs, Global Journal of Pure and Applied Mathematics, ISSN 0973-1768 Volume 11, Number 4 (2015), pp. 2487-2494.

  • Marappan, R.; Sethumadhavan, G. Solving Fixed Channel Allocation using Hybrid Evolutionary Method. ICAET, MATEC Web of Conferences 57, 02015 (2016)

  • Marappan, R.; Sethumadhavan, G. Solving Channel Allocation Problem using New Genetic Algorithm with Clique Partitioning Method. IEEE International Conference on Computational Intelligence and Computing Research (ICCIC 2016) (2017)

  • Marappan, R.; Sethumadhavan, G. Solution to Graph Coloring Using Genetic and Tabu Search Procedures. Arabian Journal for Science and Engineering, DOI 10.1007/s13369-017-2686-9 (2019)

  • Marappan, R.; Sethumadhavan, G. Complexity analysis and stochastic convergence of some wellknown evolutionary operators for solving graph coloring problem. Mathematics 2020, 8, 303. doi: https://doi.org/10.3390/math8030303.

  • Mallikarjunaswamy N J; Latha Yadav T R; Dr. Keshava Prasanna: Message Authentication Protocol for Lifetime Proficient Hash Based Algorithm in Wireless Sensor Networks. Int. J. Advanced Networking and Applications. Volume: 07 Issue: 06 Pages: 2963-2966 (2016) ISSN: 0975-0290


Abstract Views: 205

PDF Views: 3




  • A New Multi-Objective Optimization in Solving Graph Coloring and Wireless Networks Channels Allocation Problems

Abstract Views: 205  |  PDF Views: 3

Authors

Raja Marappan
School of Computing, SASTRA Deemed University, Thanjavur-613401, India

Abstract


Graph coloring problem, a combinatorial optimization problem is being widely applied in solving the channels allocation in wireless networks. This paper exhibits a new evolutionary genetic multi-objective strategy that uses the combined single and multi-parent conflict-gene crossover and combined single and multi-parent conflict-gene mutation operators with clique partitioning to solve the graph coloring and channel allocation problems. The proposed operators minimize problem search space by reducing the expected number of genetic generations. A general fitness function is defined on finding the total conflicting edges in the graph for the initial and particularly the successive generations of individuals in the population. The outcomes of this proposed method are better than the well-known methods and are compared with some of the benchmark graph coloring and channel allocation problems. The devised method of clique partitioning with genetic operators also enhances the successful runs.

Keywords


Approximation Methods, Channel Allocation, Chromatic Number, Genetic Algorithm, Graph Coloring, Wireless Networks.

References