Genetic Approach for Radio Labeling of Networks

Abstract

Effective frequency assignment is critical for modern wireless and communication systems, where limited spectrum must be allocated in a way that minimizes interference and maximizes service reliability. Radio labeling of graphs provides a mathematical framework for modeling frequency assignment in wireless and communication networks, where channel (frequency) indices must be allocated to network nodes with sufficient separation to avoid interference. For a connected graph G, a radio labeling assigns integer frequencies to vertices such that|f(u) − f(v)| ≥ d(G) + 1 − d(u, v) for all u, v ∈ V (G), where d(u, v) denotes the length of the shortest path between u and v, and d(G) denotes the diameter of G. The minimum span of such a labeling defines the radio number rn(G). Finding an optimal labeling is computationally hard for many graph families, thus motivating the use of heuristic methods. This paper investigates the use of a Genetic Algorithm (GA) as a heuristic optimization method for computing efficient radio labeling and estimating the radio number of several graphs on path, cycle, and friendship graphs. Seven crossover operators—PMX, CX, OX1, OX2, POX, MPX, and EMPX—are evaluated. The paper also provides new upper bounds of radio number for various classes of k-partite networks.