In frequency assignment problems (FAPs), separation of the frequencies assigned to the transmitters is necessary to avoid the interference. However, unnecessary separation causes an excess requirement of spectrum, the cost of which may be very high. Since FAPs are closely related to T-coloring problems (TCP), multiagent systems and evolutionary algorithms are combined to form a new algorithm for minimum span FAPs on the basis of the model of TCP, which is named as Multiagent Evolutionary Algorithm for Minimum Span FAPs (MAEA-MSFAPs). The objective of MAEA-MSFAPs is to minimize the frequency spectrum required for a given level of reception quality over the network. In MAEA-MSFAPs, all agents live in a latticelike environment. Making use of the designed behaviors, MAEA-MSFAPs realizes the ability of agents to sense and act on the environment in which they live. During the process of interacting with the environment and other agents, each agent increases the energy as much as possible so that MAEA-MSFAPs can find the optima. Experimental results on TCP with different sizes and Philadelphia benchmark for FAPs show that MAEA-MSFAPs have a good performance and outperform the compared methods.
TopIntroduction
Wireless communication networks, which employ radio frequencies to establish communication links, have undergone a dramatic expansion over the past two decades. Since the available radio spectrum is very limited, to meet the demand of today’s radio communication, this resource has to be administered and reused carefully in order to control mutual interference. Thus, given the continuing rapid growth in demand for wireless services, frequency assignment problems (FAPs) play a key role in the planning of such networks (Galinier, Gendreau, Soriano, & Bisaillon, 2005), which are concerned with the assignment of discrete channels to the transmitters of a radio network. FAPs are difficult in terms of complexity theory. Deciding whether a mobile network allows a feasible assignment is NP-complete, and the corresponding optimization problems are strongly NP-hard (Martin, 2000).
There has been a considerable research effort for solving FAPs. Valenzuela et al. (1998) proposed a permutation based genetic algorithm for solving minimum span FAPs (MSFAPs). Won-Young et al. (2006) proposed a heuristic method, namely frequency insertion strategy (FIS), which starts with a narrow enough frequency bands so as to provoke violations of constraints and then resolve the violations by inserting frequencies. Several neural network algorithms have been also proposed for FAPs. For example, Kunz (1993) used Hopfield neural network and obtained optimal solutions for some special instances of MSFAPs Idoumghar et al. (2009) proposed two distributed algorithms for the FAP in the field of radio broadcasting.
In FAPs, separation of the frequencies assigned to the transmitters is necessary to avoid the interference. However, unnecessary separation causes an excess requirement of spectrum, the cost of which may be very high. From this viewpoint, FAPs are closely related to T-coloring problems (TCPs) where the vertices of a graph represent the transmitters and adjacencies indicate possible interferences (Riihijärvi, Petrova, & Mähönen, 2005; Hurley & Smith, 1997; Bodlaender, Kloks, Tan, & van Leeuwen, 2000). TCPs are a generalized version of classical graph coloring problems (GCPs), which are one of the most studied NP-hard problems and can be defined informally as follows (Costa, 1993): Given an undirected graph, one wishes to color the vertices of the graph with a minimum number of colors in such a way that two colors assigned to any two adjacent vertices must be different. That is to say, they must have a minimum distance greater than zero. These classical GCPs are just a special case of TCPs. Unfortunately, due to the difficulty and complexity of TCPs, there has rather few researches on this problem. Some classical methods were proposed several years ago, such as tabu search (Dorne & Hao, 1998) and Dsatur (Janczewski & Kubale, 1998). Until now, there is no benchmark available for evaluating and comparing different algorithms for TCPs.
To solve TCPs, optimizing algorithms with strong searching ability are required. In our previous work, based on multiagent systems, a new numerical optimization algorithm, multiagent genetic algorithm (MAGA), has been proposed in Zhong, Liu, Xue, and Jiao (2004) to handle large-scale global numerical optimization problems. The experimental results shown that MAGA can solve numerical optimization problems with 1000 dimensions. The method was also extended to handle constraint satisfaction problems (Liu, Zhong, & Jiao, 2006) and combinatorial optimization problems (Liu, Zhong, & Jiao, 2010), which illustrated the potential of the combination of multiagent systems and evolutionary algorithms in solving complex problems. Thus, on the basis of TCPs, we extended MAGA to solve minimum span FAPs, which is labeled as MAEA-MSFAPs. In experiments, TCP with different sizes and Philadelphia benchmark for FAPs are used to validate the performance of MAEA-MSFAPs.
In the rest of this paper, the mathematical model for FAPs is described first. Next we describe MAEA-MSFAPs. We give the experimental results and the last section concludes this paper.