Ping-Liang Chen, Yu-Cheng Lin, and Shin-Jia Chen

1. Introduction

As wireless products such as the wireless local area networking, Bluetooth products, and mobile phones are widely used, the spectrum optimization problem in recent years becomes a popular topic. There are many researches focusing on the spectrum management[1]–[4],[5]–[8], including the static and dynamic spectrum management as the wireless products become more and more popular. In this study we discuss issues of the dynamic spectrum management.

From the optimization point of view, the study of dynamic spectrum management can be divided into three kinds of methods, including Nash equilibrium, social utility maximization and competitive economy equilibrium.Chung et al.[9]proved that a Nash equilibrium always exists in the noncooperative rate maximization game. Yu et al.[7]proposed an iterative water-filling algorithm to efficiently reach the Nash equilibrium for solving multiple power control problem of the digital subscriber loop. Leon Walras et al.[10]proposed the competitive equilibrium concept which dynamically balances by the supply and demand to model the market operation. Ye[6]proposed a competitive economy equilibrium solution that may achieve both social economic efficiency and individual optimality in dynamic spectrum management. Lin et al.[2]further observed that adjusting budget can meet each user’s physical power demand or balance all individual utilities in a competitive spectrum market. It is difficult to optimize the overall performance utility if we only improve the individual performance of individual user. Yu et al.[7]proposed a method which refined the optimal spectrum management with less complexity and generalized the multi-user power management for orthogonal frequency division multiplex systems maximizing the overall utility. Some traditional methods can not guarantee to obtain the global optimal solution for the nonconvex problem[7]and the time complexity grows exponentially.

The genetic algorithm (GA) is a search heuristic that is routinely used to generate useful solutions to optimization and search problems. It generates solutions to optimization problems using techniques inspired by natural evolution,such as inheritance, mutation, selection, and crossover.Genetic algorithm is widely used in many applications[11]–[14], such as wireless local network, trading rules, music generation, and cryptanalysis. For example,Rastin Pries et al.[14]proposed the genetic algorithm method to handle a max-min fair throughput allocation on routing and channel assignment in large-scale Wireless Mesh Networks. Allen et al.[12]used a genetic algorithm to learn technical trading rules. Alfonseca et al.[11]used genetic algorithms to automatically generate music in a given pre-defined style. Gorodilov et al.[13]discussed a possibility to use genetic algorithms in cryptanalysis.

The main contributions of the paper are as follows. First,our proposed method effectively maximizes the social utility instead of the individual utility. Second, we propose the genetic algorithm based method, which searches the solution space globally under the given background interference and crosstalk ratio and maximizes the spectrum utility for multi-user and multi-channel. Third, compared with [1], this study has significantly improved execution time, and obtained a better solution.

The outline of this paper is organized as follows.Section 2 describes the motivation and problem formulation.In section 3, we discuss the details of our approach. The experimental result and conclusion are discussed in sections 4 and 5, respectively.

2. Problem Formulation

In this section, we will discuss the terminology,motivation and problem definition.

2.1 Terminology and Motivation

In the subsection, we describe the motivation of searching social utility maximization, discuss the Shannon utility, and illustrate the social utility maximization with examples having the different social utility.

First, as it is well known, if we maximize the utility for each individual user with multi-channel, it does not guarantee to maximize the overall social utility for the communication system. Since the traditional approach which maximizes the utility for each individual user obtains the local optimal solution by greedy method, we try to apply genetic algorithm to solve the spectrum management problem.

Second, the formula of Shannon utility for each individual user is defined in the follows. To explore the social utility maximization, for the three users and two channels, we first explain how to estimate the utility and then discuss the solution with the maximal social utility. In the paper, we evaluate user utility based on the Shannon utility function as follows:where uiis the Shannon utility function for user i , xi,jis the power allocation for user i on channel j.denotes the crosstalk rate between users k and user i on channel j. σi,jis the background interference for user i on channel j.

Third, the Shannon utility function could be applied to evaluate the individual user utility with the background interference and crosstalk consideration. We use the parameters of the background interference and crosstalk in[1] for examples illustrate. In this case, there are five users sharing five channels, the individual user utilities are shown as follows:

When we search the assignment solution for user 1, 2, 3,4, 5 and channel 1, 2, 3, 4, 5, respectively, there are many feasible solutions. The assignment of the first example with five users and five channels is as follows.

It means that user 1, 2, 3, 4 and 5 are assigned to channels 1, 2, 3, 4 and 5, respectively. According to the above formulas, the maximization utility of social utility is 0.3291580 as shown in Fig. 1.

In the second example, we try to show the large social utility due to the better assignment of power allocation.Similarly, we remove the detailed formulas in the first example and only give the final assignment of power allocation. The assignment of the example with five users and five channels is as follows.

As shown in Fig. 2, this means that five users have all been assigned to the first channel at the same time.According to the above formulas, the maximization utility of social utility is 0.3590798. However, from the randomly assignment for maximizing of individual utility, the solutions are not the best results.

Fig. 1. The first solution with feasible social utility for spectrum management problem.

Fig. 2. The second solution with feasible social utility for spectrum management problem.

From the viewpoint of social utility, we can further improve the social utility under the same parameter.According to the above parameters, we can maximize the social utility with

and the maximal social utility is 1 as shown in Fig. 3.

Fig. 3. The third solution with maximal social utility for spectrum management problem.

Obviously, the different assignments of all power allocations lead to the different social utility. To find the better solution of the power allocation among all assignments is an important issue. By the observation, it motivates us to develop the genetic algorithm based method to maximize the social utility for spectrum management problem with multi-user and multi-channel.

2.2 Problem Definition

If we maximize the utility for each individual user with multi-channel, it does not guarantee to maximize the overall social utility for the communication system. As the traditional greedy approach attempt to maximize the utility for each individual user, it is usually to obtain the local optimal solution, so we try to use genetic algorithm to solve the spectrum management problem. In order to explore the social utility maximization and define the social utility maximization problem, we evaluate user utility based on the Shannon utility function.

The problem solved in this paper is to maximize the sum of individual Shannon utility in a multi-user communication system with background interference and crosstalk.

The problem of social utility maximization is defined as follows:

where m denotes the number of users, n denotes the number of channels, andis the power constraint for user i.

3. Problem Solution

In this section, a genetic algorithm based approach will be proposed to solve the social utility maximization problem.The pseudo code of the basic genetic algorithm is shown in Fig. 4. There are some issues that we should consider in our approach, for example, population initialization, fitness evaluation, selection procedure, crossover rate, mutation rate,constraint verification, fine-tune, population update, and stopping condition. The following is the description of the approach in detail.

? Population initialization

During the initial procedure, the initial population of individuals would be chosen. The solution quality is estimated by the Shannon utility function. The user power allocation of the initial solution is assigned with the consideration of the background interference. The population size is set to be 30.

? Fitness evaluation

During this procedure, we evaluate the fitness of each individual in the population. For each user, we use Shannon utility function to evaluate the utility of individual users;the sum of individual utility is viewed as the fitness value.

? Selection, crossover and mutation

During the selection procedure, we select the best fit individuals for reproduction. New individuals are bred through crossover and mutation operations to give birth to offspring. In this study, the crossover rate is set to be 0.2 and the mutation rate is set to be 0.1. During the mutation procedure, we select two genes randomly, and then evenly distribute the contents of two genes.

? Fine-tune

After genetic selection, crossover, and mutation, the resulting offspring may violate the restrictions. If an individual violates any restriction, the individual should pass through the fine-tuning process. There are three methods in the fine-tuning process, the first method is proportional compression, and the second is to allocate the user power in the channel with lower background interference. The third is to retain the maximum power distribution of the channels for each user; the remaining power will be randomly assigned to each channel.

? Population update

In this stage, we replace the least-fit population with new individuals.

? Stopping condition

The proposed approach terminates when finishing the generation. The generation number is set to be 20000 as default.

The above description is for the procedure of the genetic method. Fig. 5 shows the whole design flow of the proposed method. The key points will be described briefly as follows. First, the initial solution is obtained with consideration of the background interference. Then, the algorithm searches the neighbor solution by perturbing the power allocation for multi-users and multi-channels.During the searching procedure, we use the fit sum of individual Shannon utility as genetic candidates.

Fig. 4. Genetic algorithm pseudocode.

Fig. 5. Design flow of the genetic algorithm based approach.

Finally, we use an example with 5 users and 5 channels to illustrate the solutions with different social utilities. The nonlinear programming (NLP) formulations are as below:

whereiui=1, 2, 3, 4, 5 are the same as those in (2).

Fig. 6 (a), (b), and (c) show the results of the different power allocations.

Fig. 6. Example with five users and five channel: (a) user 1, 2, 3, 4 and 5 are assigned to channels 1, 2, 3, 4 and 5, (b) all users are assigned to channel 1, and (c) user 1, 2, 3, 4 and 5 are assigned to channels 3, 4, 5, 2 and 1.

4. Experimental Result

All experiments are implemented using C++ language(VS 2008 .Net development platform) on AMD CPU 3 GHz machine with 4 GB memory. To facilitate the comparison of the efficiency and quality, we take the same test cases in [1] with the same background interference and crosstalk. The range of background interference is from 1 to 9 and the range of crosstalk is from 0.1 to 0.9. The relative parameters which we used in the paper are listed in Table 1.

We investigate the efficiency of our proposed genetic algorithm based approach. The experiment result is shown in Table 2. For the small test case with few users and few channels, our method efficiently solves the problem with acceptable runtime. Even though for the largest test case,including 50 users and 50 channels, our method still maximizes the social utility within 13 minutes.

This study compared the algorithm proposed in [1], and the experimental result is listed in Table 2. Compared with[1], the algorithm proposed in this paper has a 20.54%improvement rate. In some cases, our algorithm can even obtain up to a 37.90% improvement rate, as shown in Fig.7.

Table 1: Coefficient of our experiment

Table 2: Experimental result

Fig. 7. Improvement of social utility compared with [1].

5. Conclusions

Dynamic spectrum management problems have been proved to be NP-hard[4]when the number of users is greater than 2 and the number of channels greater than 3. In this paper, we propose a genetic algorithm-based approach to solve the problem of dynamic spectrum management, and consider the background interference on the channel and crosstalk caused by other users on the same channel.Experimental results show that the algorithm proposed in this paper has a better solution quality than the algorithm proposed in [1], and overall solution time is also more efficient.

[1] Y.-C. Lin, M.-H. Lin, H.-H. Huang, and L.-Y. Lee, “Using simulated annealing algorithm for maximizing social utility in dynamic spectrum management,” WSEAS Trans. on Communications, no. 7, vol. 8, pp. 638–647, 2009.

[2] M.-H. Lin, J.-F. Tsai, and Y.-Ye, “Budget allocation in a competitive communication spectrum economy,” EURASIP Journal on Advances in Signal Processing, vol. 2009, no. 8,pp. 12 , Jan. 2009.

[3] Y.-C. Lin, M.-H. Lin, H.-H. Huang, and L.-Y. Lee, “A simulated annealing approach for social utility maximization in dynamic spectrum management,” in Proc. of the 8th WSEAS Intl. Conf. on Instrumentation, Measurement,Circuits and Systems, Hangzhou, 2009, pp. 244–247.

[4] Z.-Q. Luo and S. Zhang, “Dynamic spectrum management:complexity and duality,” IEEE Journal of Selected Topics in Signal Processing, vol. 2, no. 1, pp. 57–73, 2008.

[5] Y. Xie, B. Armbrustery, and Y. Ye, “Dynamic spectrum management with the competitive market model,” IEEE Trans. on Signal Processing, vol. 58, no. 4, pp. 2442–2446,2010.

[6] Y. Ye. Competitive communication spectrum economy and equilibrium. [Online]. Available: http://bolyai.cs.elte.hu/~illes/Tantargyak/Szakmai%20anyagok/Cikk15/spectrumpri cing1.pdf

[7] W. Yu and R. Lui, “Dual methods for nonconvex spectrum optimization of multicarrier systems,” IEEE Trans. on Communications, vol. 54, pp. 1310–1322, Jul. 2006.

[8] W. Yu, R. Lui, and R. Cendrillon, “Dual optimization methods for multi-user orthogonal frequency division multiplex systems,” in Proc. of IEEE Global Telecommunications Conf., Dallas, 2004, pp. 225–229.

[9] S. Chung, S. J. Kim, J. Lee, and J. Cioffi, “A game-theoretic approach to power allocation in frequency-selective Gaussian interference channels,” in Proc. of IEEE Int.Symposium on Information Theory, Yokohama, 2003, pp.316.

[10] L. Walras, Elements of Pure Economics; Or the Theory of Social Wealth, Paris: Lausanne, 1874.

[11] M. Alfonseca, M. Cebri’an and A. Ortega “A simple genetic algorithm for music generation by means of algorithmic information theory,” in Proc. of IEEE Congress on Evolutionary Computation, Singapore, 2007, pp.3035–3042.

[12] F. Allen and R. Karjalainen, “Using genetic algorithms to find technical trading rules,” Journal of Financial Economics, vol. 51, no. 2, pp. 245–271, 1999.

[13] A. Gorodilov and V. Morozenko, “Genetic algorithm for finding the keys length and cryptanalysis of the permutation cipher,” Int. Journal of Information Theories & Applications,vol. 15, no. 1, pp. 94–99, 2008.

[14] R. Pries, D. Staehle, B. Staehle, and P. Tran-Gia, “On optimization of wireless mesh networks using genetic algorithms,” Int. Journal on Advances in Internet Technology, vol. 3, no. 1–2, pp. 13–28, 2010.