During the last years, wireless communications have experienced an explosive growth thus rapidly leading to a dramatic congestion of radio resources. In such complex scenario, the trial-and-error approach commonly adopted by practitioners to design networks has clearly shown its limitations. Telecommunications companies and authorities are thus searching for more effective and efficient design approaches, also looking on Optimization (as shown by the recent call for tenders for developing a Digital Video Broadcasting simulator by the Italian Communications Regulatory Authority [2]). Many models and solution methods have been proposed for solving the problem of designing a wireless network. However, solving to optimality the overall problem is still a big challenge in the case of large instances. In this paper we present a Genetic Algorithm for solving the Power, Frequency and Modulation Assignment Problem, a relevant problem that arises in the design of wireless networks and captures specific features of Next Generation Networks.

For modeling purposes, a wireless network can be described as a set of transmitters B that provide for a telecommunication service to a set of receivers T . A receiver is said to be covered or served if it receives the service within a minimum level of quality. Transmitters and receivers are characterized by a location and a number of radio-electrical parameters (e.g., power emission and frequency). The Wireless Network Design Problem (WND) consists in establishing the location and suitable values for the parameters of the transmitters with the goal of maximizing the number of covered receivers or a revenue associated with coverage.

In this work we consider a generalization of the so-called Power and Frequency Assignment Problem (PFAP), a version of the WND that is known to be NP-hard [12]. In addition to power emission and frequency, we also consider the transmission scheme (burst profile) as parameter to be established, modeling a feature of Next Generation Networks, such as WiMAX [3,6]. We indicate this generalization of the PFAP by the name Power, Frequency and Modulation Assignment Problem (PFMAP).

In the PFMAP two decisions must be taken: (1) establishing the power emission of each transmitter on each available frequency and (2) assigning served receivers to activated transmitters specifying the frequency and the burst profile used to transmit. To model these decisions, as first step we introduce the set F of available frequencies and the set H of available burst profiles. Each frequency has a constant bandwidth D and each burst profile is associated with a , which is the bandwidth required to satisfy one unit of traffic demand generated by a receiver.

Then we can introduce two typologies of decision variables, namely:

– a continuous power variable [0representing the power emission of a transmitter b on frequency f;

– a binary service assignment variable H defined in the following way:

Given a frequency , every receiver picks out signals from every transmitter and the power (t) that t receives from b on f is proportional to the emitted power by a factor [0, 1], i.e. (t) = . The factor is called fading coefficient and summarizes the reduction in power that a signal experiences while propagating from b to t [14].

reference signal (or server), which is the one carrying the service. All the other signals are interfering. We remark that, since each transmitter in B is associated with a unique signal, in what follows we will also refer to B as the set of signals received by t.

on frequency through burst profile , if the ratio of the serving power to the sum of the interfering powers (signal-to-interference ratio or SIR) is above a threshold ) whose value depends on the used burst profile h [14]:

N > 0. By simple algebra operations, inequality (1) can be transformed into the following linear inequality, commonly called SIR inequality:

As we do not know a priori which transmitter will be the server of a receiver and which frequency and burst profile will be used, given a receiver we have one SIR inequality (2) for each potential server and potentially usable frequency f and burst profile h. To ensure that t is covered, at least one of such inequalities must be satisfied. This requirement can be equivalently expressed through the following disjunctive constraint:

Adopting a standard approach used in Mixed-Integer Programming (see [13]), the above disjunction can be represented by a family of linear constraints in the p variables by introducing a large positive constant M, the so-called big-M coefficient. Specifically, given a receiver we use the assignment variable to introduce the following constraint for each potential 3-ple ():

It is easy to check that if = 1 then (4) reduces to the simple SIR con- straint (2). If instead = 0 and M is sufficiently large, then (4) is satisfied by any feasible power vector p and becomes redundant.

By using constraints (4) and by introducing a parameter to denote revenue associated with receiver (e.g., population, number of customers) , we can define the following natural formulation (BM-PFMAP) for the PFMAP [6,7]:

t T, b B, f F, h H (5)

The objective function is to maximize the total revenue obtained by serving receivers and constraint (6) ensures that each receiver is served at most once. Each receiver generates a traffic demand and each frequency has a bandwidth equal to D. Constraint (7) ensures that the sum of traffic demands (re-sized by the spectral efficiency of the used burst profile) generated by the receivers served by a transmitter does not exceed the bandwidth of the frequency. Finally, (8) and (9) define the decision variables of the problem.

Drawbacks of the natural formulation. The natural formulation (BMPFMAP) expands a basic model that is widely used for the WND in different application contexts, such as DVB, (e.g., [12]), UMTS (e.g., [1,11]) and WiMAX ([6,7]). In principle, such basic model and (BM-PFMAP) can be solved by commercial solvers such as IBM ILOG CPLEX [10]. However, it is well-known (see [7]) that: (i) the fading coefficients may vary in a wide range leading to (very) ill-conditioned coefficient matrices that make the solution process numerically unstable; (ii) the big-M coefficients generate poor quality bounds that dramatically reduce the effectiveness of standard solution approach [13]; (iii) the resulting coverage plans are often unreliable and may contain errors (e.g., [7,11]). In practice, the basic model and (BM-PFMAP) can be solved to optimality only when used for small-sized instances. In the case of large real-life instances, even finding feasible solutions can represent a difficult task, also for state-of-the-art commercial solvers like CPLEX. Though these drawbacks are well-known, it is interesting to note that just a relatively small part of the wide literature devoted to WND has tried to overcome them. We refer the reader to [6] for a review of works that have tried to tackle these drawbacks.

2.1 Contribution of this work and review of related literature

In this paper, we develop our original contribution by starting from a recent work, [7], that proposes a family of strong valid inequalities for tackling the drawbacks of (BM-PFMAP) that we have pointed out. The idea at the basis of [7] is to quit modeling emission power as a continuous variable and to use instead a set of discrete power levels , with = 0 (switched- and , for i = 2, . . . , |P|. This basic operation allows the authors to define a family of lifted GUB cover inequalities that are used in a solution algorithm that drastically enhances the quality of solutions found.

The solution algorithm proposed in [7] is motivated by a trade-off that arises from discretization: larger sets of discrete levels lead in principle to better solutions, but on the other hand the corresponding 0-1 Linear Program gets larger and harder to solve. The computational experience shows that very good solutions can be found by considering small sets with well-spaced power values, but that no improvement is obtained within the time limit when a number of levels higher than six is considered.

In the present work, we investigate the possibility of using a Genetic Algorithm (GA) [8] as a fast heuristic to widen the exploration of the discrete power solution space: the aim is to exploit the entire set of discrete power levels and thus to evaluate power configurations with levels not included in the best solutions found in [7]. In particular, our aim is to improve the capacity of solving large realistic instances by finding higher value solutions. We thus design a GA that takes into account the specific features of the PFMAP and we test its performance on the same set of realistic WiMAX instances used in [7].

Heuristics have been extensively used to tackle large instances of different versions of the WND problem. Two relevant cases are provided by [1], where a two-stage Tabu Search algorithm is proposed to solve the base station location and power assignment problem in UMTS networks, and by [12], where a GRASP algorithm is proposed to solve the PFAP arising in the planning of the Italian National DVB network. The use of GA to solve versions of the WND is not a novelty as well and many works can be found in literature. However, to our best knowledge, no GA has been yet developed to solve the PFMAP and the algorithm that we propose is the first for solving this level of generalization of the WND. Until now, GAs were indeed developed to solve just single aspects of the PFMAP: (i) the transmitter location problem (e.g., [4]); (ii) the service assigment problem (e.g., [9]); (iii) the frequency assignment problem (e.g., [5]); (iv) the power assignment problem (e.g., [15]). Moreover, we remark that our algorithm is the first to be designed with the specific aim of improving the capacity of solving instances, while tackling the numerical problems pointed out in Section 2. We now proceed to present our original contributions for the WND.

A Genetic Algorithm (GA) is a heuristic method for solving optimization problems that resembles the evolution process of a population of individuals (for a comprehensive introduction to the topic we refer the reader to [8]). At any iteration, a GA maintains a population whose individuals represent feasible solutions to the problem. The solution is encoded in a chromosome associated with each individual. The genetic strength of an individual is evaluated by a fitness function that establishes the quality of the corresponding solution to the problem. A GA starts by defining an initial population, that iteration after iteration changes by crossover, mutation and death of individuals, according to a natural selection Darwinistic mechanism.

We develop a GA for the PFMAP that presents the following general structure:

1. Creation of the initial population

2. UNTIL the arrest condition is not satisfied DO (a) Selection of individuals who generate the offspring (b) Generation of the offspring by crossover (c) Mutation of part of the population (d) Death of part of the population

We now characterize the elements and the phases presented above for the algorithm (GA-PFMAP) that we propose to solve the PFMAP.

3.1 Characterization of the population

Individual representation. As we have explained in Section 2.1, our aim is to conduct a wider exploration of the power solution space, trying to obtain solutions with higher value. To this end, we establish that the chromosome of an individual corresponds to a power vector p of size . Specifically, the chromosome presents one locus for each transmitter and frequency and each locus stores the power emitted by b on f, namely p = (). Such power belongs to the set of discrete

power levels P, i.e. .

We remark that establishing the power emission does not completely characterize a solution of the PFMAP. We indeed have to fix the value of the assignment variables and thus we need to set some assignment rule. First, note that given a power vector p = () and a receiver

we can compute the power (t) that t receives from b on . Through (t), if we fix the server of t, we can check if there exists a SIR inequality (2) that is satisfied for some frequency and burst profile . We establish the following assignment rule: as server of t we choose the transmitter b that ensures the highest received power (t) on some f. This in fact ensures the highest serving power. Once that the server is chosen, we can identify the SIR inequalities (2) that are satisfied by p when t is served by for some and . If the SIR inequality is satisfied for a multiplicity of frequencies and/or burst profiles, we first choose as serving frequency ˆf the one that ensures the highest value for the left-hand-side of (2) and then we choose as burst profile ˆh the one that ensures the highest spectral efficiency (see Section 2).

Thus for t served by we have = 1 and = 0 .

Note that this last rule may assign a receiver t to a transmitter that violates the capacity constraint (7) of on the chosen frequency ˆf. If this is the case, we choose the second best couple of frequency and burst profile according to the rule. If this not possible, the third best and so on. In the end, if there is no capacity left for any valid couple (f, h), t is not considered covered by .

Fitness function. As the aim of the WND is to maximize coverage, we adopt a fitness function that evaluates the coverage ensured by an individual. Specifi-cally, the fitness COV (p) of an individual is equal to the number of receivers that are covered when the power vector is p and service assignment is done according to the previously introduced rules.

Initial population. Our aim is to consider all the feasible discrete power levels from the beginning. Therefore, the initial population is represented by the power vectors that are obtained by activating a single transmitter on a single frequency at each of the discrete power levels . For every , the corresponding individuals included in the initial population are thus: (0= 0) = 0) . Note that we exclude the individual corresponding to all transmitters turned off, i.e. = = 0 . We thus have initial individuals. We denote the set of individuals representing the population at a generic iteration of the algorithm by P.

3.2 Evolution of the population

Selection. In order to select the individuals who give birth to the new generation, we adopt a tournament selection approach: given the set P of individuals constituting the current population and a value 0 1, we first define a number of groups including individuals who are randomly extracted from P. Then we extract individuals with the best fitness from every group. These are the individuals who generate offspring by crossover.

Crossover, mutation and death. The individuals selected for crossover are randomly paired up to constitute couples. Each couple generates two offspring by mixing its chromosome. Given a couple of parents with power vectors p1, p2, the crossover operation consists in mixing power levels that are in the same position of p1 and p2 to generate two offspring with (possibly) higher fitness power vectors p3, p4.

Before presenting the crossover procedure, we need to define a measure that evaluates the impact of crossover on coverage. To this end, let COV(= denote the variation in the number of covered receivers caused by changing the power value in position (b, f) of vector p to the value , while maintaining all the other power values unchanged. We can then propose the following crossover procedure, that concentrates the effort of creating a higher fitness individual on p3. At the beginning of the crossover, p3 and p4 have all elements equal to 0. Then, by following this ordering of indices (b, f) : F: (1, 1) (1, 2) . . . (1, |F|) (2, 1) . . . (2, |F|) . . . (|B|, 1) . . . (|B|, |F|), each null value inherits the power value in the same position of one of the two parents.

We now present the crossover rule for a generic position (). For indices (b, f) : , the crossover was already executed and thus the offspring vectors p3, p4 present power levels inherited by the parents p1, p2. Power levels of p3, p4 in positions (b, f) : are instead still equal to zero. The rule to establish the power value inherited by p3, p4 in () is the following:

This ensures that, at any step of the crossover procedure, offspring p3 inherits the power level of the parent that allows the most favourable variation in coverage.

In addition to crossover, we also allow to alter the power vector of single individuals by mutation. This introduces new genetic information in the population and helps to widen the solution space exploration and to avoid entrapment in local optima. At any iteration, a number of individuals with 0 1 is randomly chosen. Then, still by random selection, |F| power levels corresponding with different frequencies are reduced to the immediately lower power level allowed in P. This mutation rule is set with the aim of defining new power vectors that have lower powers but ensure the same coverage. The reduction in power is generally desirable as a signal that is useful for a receiver may be interfering for a different receiver.

Finally, after crossover and mutation, the weakest individuals die and are removed from P. Specifically, we choose to select and remove the 2 individuals with the worst fitness function. The size of P is thus maintained constant over all the iterations.

We test the performance of our GA on a set of 15 realistic instances, developed with the Technical Strategy & Innovations Unit of British Telecom Italia (BT Italia SpA). All the instances refers to a Fixed WiMAX Network [3], deployable in an urban area corresponding to a residential neighborhood of Rome (Italy). The instances consider various scenarios with up to |T | = 529 receivers, |B| = 36 transmitters, |F| = 3 frequencies, |H| = 4 burst profiles (see Table 1). This leads to large formulations (BM-PFMAP) that are very hard to solve. For a detailed description of the instances, we refer the reader to [7].

For each instance, we run the proposed algorithm (GA-PFMAP) 50 times with a time limit of 1 hour by using a machine with a 1.80 GHz Intel Core 2 Duo processor and 2 GB of RAM. Each tournament selection involves k = 20

Table 1. Comparisons between (BM) and WPLAN formulations

groups that include a fraction = 0.05 of the population P. The best m = 8 individuals of each group are selected for crossover and, after the generation of the new individuals, mutation affects a fraction = 0.1 of the population.

In Table 1, we compare the value of the best solution obtained through the three approaches that we consider, namely the direct solution of (BM-PFMAP) by ILOG Cplex 10.1, the solution of the Power-Indexed formulation by the algorithm WPLAN [7] and the solution of (BM-PFMAP) by the proposed algorithm (GA-PFMAP). Results for (BM-PFMAP) and WPLAN are derived from [7]. The presence of two values in some lines of the column of (BM-PFMAP) indicates that the coverage plans returned by Cplex contain errors and some receivers are actually not covered. We remark that (GA-PFMAP) provides solutions that always ensure a higher coverage than (BM-PFMAP) and without coverage errors. Making a comparison with WPLAN, we instead note that (GA-PFMAP), though in some cases finds solutions with lower coverage, for most of the cases is able to find solutions that ensure an equal or higher number of covered receivers than WPLAN. This is particularly evident for instances that seems to be very hard to solve through (BM-PFMAP). The algorithm is thus effective and is worth of further investigations.

We presented a Genetic Algorithm (GA) to tackle large realistic instances of a relevant problem arising in wireless network design. We showed that a GA helps to improve the value of solutions found through a wider exploration of the power space. A future research path could be represented by the integration of a refined GA into an exact solution method. It is indeed common experience that the combination of fast heuristics with Mixed-Integer Linear Programming leads to a great reduction in the running times w.r.t pure exact optimization methods. A sensitivity analysis of the GA parameters and a study on the impact of different starting conditions and selection strategies would also constitute important subjects of investigations.

Acknowledgments. The author thanks Carlo Mannino and Antonella Nardin for fruitful discussions. Thanks go also to the three anonymous referees who provided valuable comments.

1. Amaldi, E., Belotti, P., Capone, A., Malucelli, F.: Optimizing base station location and configuration in UMTS networks. Ann. Oper. Res. 146 (1), 135–152 (2006)

2. Autorit´a per la Garanzia nelle Comunicazioni, Delibera N.269/09/CONS, http://www.agcom.it/default.aspx?DocID=3359

3. Andrews, J.G., Ghosh, A., Muhamed, R.: Fundamentals of WiMAX. Prentice Hall, Upper Saddle River, USA (2007)

4. Choi, Y.S., Kim, K.S., Kim, N.: The Displacement of Base Station in Mobile Com- munication with Genetic Approach. EURASIP J. Wireless Comm. and Net. Vol. 2008 (2008)

5. Colombo, G.: A Genetic Algorithm for Frequency Assigment with Problem Decom- position. Int. J. Mob. Net. Des. and Innov. 1 (2), 102–112 (2006)

6. D’Andreagiovanni, F.: Pure 0-1 Programming Approaches to Wireless Network De- sign. Ph.D. Thesis, Sapienza Universit`a di Roma, Rome, Italy, Winner of the 2010 INFORMS Doctoral Dissertation Award for Operations Research in Telecommunications, (2010)

7. D’Andreagiovanni, F., Mannino, C., Sassano, A.: GUB Covers and Power-Indexed Formulations for Wireless Network Design. Technical Report vol. 2 n. 14, Department of Computer and System Sciences, Sapienza Universit`a di Roma, Rome, Italy (2010)

8. Goldberg, D.E.: Genetic Algorithms in Search, Optimization & Machine Learning. Addison-Wesley, Reading, USA (1988)

9. Hu, T., Chen, Y.P., Banzhaf, W.: WiMAX Network Planning Using Adaptive- Population-Size Genetic Algorithm. In: Di Chio, C., et al. (eds.) EvoApplications 2010. LNCS, vol. 6025, 31–40. Springer, Heidelberg (2010)

10. IBM ILOG CPLEX, http://www-01.ibm.com/software/integration/optimization/cplex-optimizer

11. Kalvenes, J., Kennington, J., Olinick, E.: Base Station Location and Service Assignments in W-CDMA Networks. INFORMS J. Comp. 18 (3), 366–376 (2006).

12. Mannino, C., Rossi, F., Smriglio, S.: The Network Packing Problem in Terrestrial Broadcasting. Oper. Res. 54 (6), 611–626 (2006)

13. Nehmauser, G., Wolsey, L.: Integer and Combinatorial Optimization. John Wiley & Sons, Hoboken, USA (1988)

14. Rappaport, T.S.: Wireless Communications: Principles and Practice, 2nd Edition. Prentice Hall, Upper Saddle River, USA (2001)

15. Song, W.J., et al.: Evolutionary Computation and Power Control for Radio Re- source Management in CDMA Cellular Radio Networks. PIMRC 2002, vol. 3, 1417– 1421 (2002)