Metaheuristic proposal to minimize self-interference in single frequency networks

EUROPEAN COOPERATION IN THE FIELD OF SCIENTIFIC AND TECHNICAL RESEARCH ———————————————— EURO-COST ———————————————— COST 2100 TD(10)11032 Aalborg, Denmark 2010/June/02-04 SOURCE: UPC - Universitat Polit`ecnica de Catalunya I2CAT Foundation Metaheuristic Proposal to Minimize Self-Interference in Single Frequency Networks M. Garc´ıa-Lozano, S. Ruiz-Boqu´e, M.A. Lema, E. Torras, J.J. Olmos, F. Minerva? UPC. C/ Esteve Terradas 6, EPSC-214. Castelldefels, Spain. ?I2CAT Foundation. C/ Gran Capit`a 2-4. Nexus I. 08034, Barcelona, Spain. Phone: +34 93 413 72 13 Fax: +34 93 413 70 07 Email: [email protected]c.edu Metaheuristic Proposal to Minimize Self-Interference in Single Frequency Networks M. Garc´ıa-Lozano, S. Ruiz-Boqu´e, M.A. Lema, E. Torras, J.J. Olmos, F. Minerva. May 26, 2010 Abstract This paper concentrates on the maximization of coverage in OFDM networks with a single frequency deployment. The case-study is particularized to DVB-T networks. To achieve this objective, internal delays at the transmitters are jointly optimized so that self-interfered areas can be reduced as much as possible before having to deploy new centers. A metaheuristic approach is proposed and validated. Results show that the strategy succeeds in its objective and constitutes a practical tool that helps to assess radio planning decisions. 1 Introduction Digital Video Broadcasting Terrestrial (DVB-T) operators commonly exploit (part of) their networks using a single-frequency network (SFN) scheme. This is possible because the physical layer is based on Orthogonal Frequency Division Multiplexing (OFDM) and the introduction of a cyclic prefix between consecutive symbols. This allows having a guard interval (GI) that copes with intersymbol interference (ISI) induced by the multipath channel. SFNs allow a more efficient use of available bandwidth than classic Multiple Frequency Networks (MFNs). They also simplify the radio-planning process since frequency allocation strategies are not required. Indeed, coverage holes can be easily solved by just the installation of a new transmitter (TX) or gap-filler without having to revise a pre-existent frequency plan. On the other hand, during the design of the network, the radioplanning engineer has to guarantee the GI condition since signals that fall outside it cause self-interference. As a general rule-of-thumb, TXs should be placed at a distance equal to that covered by the signal in one GI. For classic DVB-T networks operating in 8K mode with a GI of 1/4 of the duration of the OFDM symbol, this yields to a separation of around 67 km which implies that the earth curvature will also contribute to isolate receivers from interferer TXs. It is clear that the longer the GIs, the easier the reduction of self-interference, however this also implies a less efficient transmission since no new information is contained in the added interval and so the effective data rate is reduced. Besides, mobile television is gaining focus particularly in the context of the DVB-T2 standard, and long symbols with large GIs are much more sensitive to doppler effect. A good system design implies as short as possible GIs while maintaining sufficient multipath protection. Thus strategies to minimize self-interfered areas arise as paramount. In this sense, the variables with a higher impact can be grouped in those that are uncontrollable by the operator and those that are susceptible of optimization: •In the first group one can find the propagation environment and the configuration of OFDM receivers. Different commercial equipment position the beginning of the GI (and so the FFT window) following different criteria that imply different coverage and interference footprints [1]. Given this, different receiver options should be considered and assessed when optimizing the network planning, or at least the worst case should be studied. 1 •The second group of variables are the geographic position of the TXs, their transmission power, the configuration of their radiant system (diagram pattern, downtilt, null-filling techniques, polarization...) and their static internal delays. Among these, the last one is of special interest because changes can be done with cost zero. Moreoever, in a context of operative DVB-T networks and in some cases in the beginning of a transition towards DVB-T2, powers, antennas and positions (in this order) are increasingly more static and unlikely to be dramatically changed. Given this, this work deals with the optimal adjustment of static delays of the TXs in SFNs. The final aim is to reconfigure this parameter so that self-interfered areas are minimized, with the correspondent increase in coverage for a given layout of TXs. This action is typically done manually by the radio planning engineer as TXs are installed, that means one-by-one sequentially. A manual joint adjustment of all the nodes in a certain area is very complex because of interdependencies among them. In this sense, there are not many proposals in the literature to automate this process. The recent references [2; 3] are an example on how addressing this problem successfully with the help of a particle swarm optimization algorithm. The authors in [4] simplify the problem reasonably and address it smartly from an analytical viewpoint. Also, [5] proposes a technique under the assumption that the position of users is known, who require a GPS receiver. Other examples of radio planning optimization focus on the adjustment of parameters such as the number of TXs, their location, emitted power and antenna height [6; 7]. The novelty of this paper is the proposal of a new technique to jointly optimize the static internal delays of a certain set of TXs in a SFN. It actively searches for the set of delays that minimize the areas affected by ISI and so that increase the final network coverage. The proposal solves the optimization problem making use of the metaheuristic Simulated Annealing, already applied with success in other areas of the wireless communications field, as detailed afterwards. Several realistic scenarios have been successfully solved and compared with usual manual resolution. The rest of the paper is organized as follows. Next section describes the system model and its assumptions, the impact of delays adjustment on self-interfered areas is also addressed. Subsequently, Section 3 explains the basis of the optimization algorithm. Results are presented in Section 4 and also some remarks on the implementation of the strategy and its execution are included. Finally, the paper is closed with the conclusions and some final remarks. 2 System Model 2.1 Self-Interference Modelling We assume a generic SFN deployment covering a certain service area with NTXs broadcasting in a synchronized manner, for example making use of a GPS reference. Internal delays in each TX can be reconfigured to modify the time of transmission. Considering that the program does not reaches all TXs at the same time, some of them have a margin for negative adjustments. The quality of the service at a given location is given by the Carrier-to-Interference-plus-Noise Ratio (CINR), denoted by Γ. Note that the minimum required CINR is found before computing the coverage areas. One possibility is to combine link-budgets with link level simulations with an appropriate radio channel model. In general, dense SFNs imply many paths inside the GI without a clear dominant, which leads to a purely Rayleigh behavior with important frequency selective fadings. The ith path is considered to be useful or interfering considering its delay ∆τiwith respect to the beginning of the FFT window. The final value depends on the receiver because different strategies to synchronize this window are possible [1]. Besides, echoes falling out the GI but with an important overlapping with the FFT window, contribute partly to the useful signal and partly to the interference perceived in the next symbol [1]. The weighting function w(∆τi) that is used to compute the final contribution in Γ is given next. w(∆τi) =      1 if 0 ≤∆τi≤TGI TU−∆τi+TGI TU2if TGI <∆τi≤Te 0 otherwise (1) 2 Locus of points where the difference of the distances to the two foci is a constant CIRth IG Figure 1: Different receiving situations in a canonical scenario. (a) Equal static delay (b) Positive delay on the left Figure 2: Reduction of left interfered area by means of delays modification Being TGI the GI value, TUthe useful symbol part and Tethe equalization interval. Pre-echoes and signals falling out of TU+Teare considered as full interference. Given this, the formal expression of Γ is: Γ = PN i=1 w(∆τi)Pi PN i=1 [1 −w(∆τi)] Pi+PN (2) Where, Piis the power received from the ith TX and PNis the thermal noise power. 2.2 On the Impact of Time Offset Adjustments Let consider a canonical scenario in which two TXs (L on the left and R on the right) are deployed in a flat terrain. Under these circumstances, the border between the areas with the second contribution falling inside or outside the GI is given by the locus of points where the difference of the distances to the two TX is a constant, that is a hiperbola (Fig. 1) with both TXs as foci. However, not the full area on the left of the left semi-hiperbola and on the right of the right semi-hiperbola are necessarily out of coverage. As long as the CINR is good enough, other contributions can be received out of the GI, as it is graphically pointed out. In this sense, the configuration of the OFDM receiver plays and important role, as previously mentioned. Self-interfered areas can be modified by means of changes on static delays. Thus, for example, if the internal delay of L is increased, then R has virtually got closer and consequently the left semi-hiperbola is reduced (eventually eliminated). Conversely, this action has a negative effect on R, because now L has been virtually moved further away and so the self-interfered area on the right is increased. This is graphically represented on Fig. 2 where the before and after situation are plotted. Note that the blue area represents those points with a probability of coverage of 90% or higher, the red one represents the opposite. Thus, this simple modification could be useful for example in an environment in which R transmits with a higher power and so can cope with the signal from L causing interference. If the number of nodes is increased to 3, crossed effects start to make difficult the adjustment. That is why the different delays are typically set in a manual manner but just one-by-one. Whenever a new node is added 3 to the network, the new self-interference is evaluated and actions are taken over the new TX, commonly respecting the existing network or with minor changes on it. Note that this procedure is indeed a Local Search (LS), because it is just an iterative search procedure that, starting from an initial feasible solution S, progressively improves it with a series of modifications. In particular, the set of new solutions that can be generated from the current one is the solution neighborhood N(S) and all the possible solutions conform the solutions space. This procedure implies suboptimal solutions that could be improved if the whole target area was optimized at a time. The point is that the complexity of the problem increases exponentially with the number of TXs and in general, it cannot be jointly solved manually if more than 4 nodes are to be optimized. Given this, the proposed technique is able to optimize a random number of nodes and find a set of optimized delays performing a joint analysis. 3 Basis of the Optimization Algorithm The resolution method is basically oriented to the minimization of a cost function Fcost that gathers the operator’s requirements and expresses the global value of a certain radio planning solution S. In particular, Fcost represents the summation of the pixels, in the digital elevation model, that are not correctly served and weighted by a factor representing the population density in that particular pixel. The optimization can be subject to several constraints, as for example not modifying the existing coverage of a particular area. Because of non-linearities and dependencies among different TXs, the problem can be considered a combinatorial optimization one with a very high number of solutions when a significant group of TXs is considered. In 1983, Kirkpatrick, Gelatt and Vecchi described in [8] a new heuristic approach called Simulated Annealing (SA) with the outstanding feature that converged to the optimal solution of a combinatorial problem, although infinite computing time was required. Nevertheless, the appearance of SA showed that other ways to tackle combinatorial optimization problems were possible and it boosted the interest of the research community. Other examples are Genetic Algorithms and the Ant Colony Algorithm. All these methods are now collectively known as metaheuristics. Metaheuristics also require a procedure to generate a new combination (or solution, state...), usually derived from the current one. This is usually a probabilistic action that mutates the present solution. In most of them, it is interesting to note that moves in the space of solutions can be both uphill or downhill and that means accepting solutions with a worst cost at particular moments of the search. In fact, this is one of the main differences with respect to LS since it is intended to avoid getting trapped in local minima. As previously mentioned, SA is one of the algorithms that enjoys more popularity in the resolution of combinatorial optimization problems and it is the one that has been adopted in this work. SA is being widely used at many levels of telecommunications engineering as for example: •Frequency allocation problem: [9; 10; 11]. •Location of TXs and transmission powers: [6; 12]. •Hub location problem: [13; 14]. The name and inspiration comes from the cooling process of a liquid and its conversion into a solid which SA attempts to mathematically capture. The cooling process is formulated as the search of the solution implying a lower cost (energy). Every new solution is generated by applying a slight perturbation over the current one. Likewise, from a physical viewpoint, there is some non-zero probability of reaching a higher energy state. As a consequence the acceptance of worse solutions is allowed with a certain probability too, as it usually happens with all metaheuristics. The process is summarized in Table 1, where previously defined notation Fcost and N(S) has been used. The quality of the final solution depends on aspects such as the initial heating or generation of the starting solution, the cooling strategy, the criteria to generate the neighborhood of solutions, etc. In general, a trade-off is always present between the quality of the result and execution time. In order to make the algorithm robust, it is desirable that the quality of the final solution is independent of the initial one. Thus, the parameter that controls the probability of accepting worse solutions (temperature 4 Table 1: Basic SA schema. 1. Obtain initial solution Sand temperature T 2. Obtain initial cost: C←Fcost (S) 3. Generate new solution S0∈N(S) 4. C0←Fcost (S0) 5. Accept S0as current solution Swith probability P P=exp [(C−C0)/T] if C0≥C P= 1 if C0< C 6. If equilibrium condition not reached, go to 3 7. Update temperature T 8. If termination criterion not reached, go to 3 of the algorithm, T) must be high enough, otherwise the algorithm could be conditioned to be trapped in a local minima. In the proposed design an initial heating process is executed until the ratio of accepted solutions is higher than 85%. The generation of a new solution consists of a slight perturbation over the current one. This modification is done according to two random elections: one delay in the range of possible values and one TX in the area to be optimized. The new value of Fcost is recalculated and possible operator constraints are evaluated, in this sense the scenarios evaluated in this work are no subject to restrictions. Finally, the update of Tis done according to equation 3 because it is mathematically demonstrated that it preserves the convergence theory of the algorithm towards optimum solutions as much as possible [15]. Tn+1 =Tn 1 + Tnln(1+δ) 3σn (3) The speed in the reduction of Tcan be controlled with δso that simulation time can be adjusted at will. On the other hand, σnrepresents the standard deviation of the cost evolution with the previous temperature Tn. 4 Results Results are presented for three different scenarios covering different areas of Catalonia, in the northeast of Spain. A digital elevation model with a resolution of 100 ×100 m2has been used and path-losses have been computed following the recommendation ITU-R 526. Only those pixels receiving at least one signal contribution with a significant level are evaluated by the algorithm. For the sake of clarity Fcost is expressed in km2and not in number of pixels. Fig. 8 shows how the proposed solution is modified as the algorithm advances in the optimization. It is noticeable how the curves are very noisy at the beginning; the algorithm explores the solution space randomly and as it advances in its search, a defined trend in the optimal delays is observed. By the end of the simulation it can be seen how the closer the algorithm to the solution, the more correlated the changes are. This is logical, because SA is positioned in an interesting area of the space of solutions and so it is normal that after a new change, several delays are readjusted to keep the relative time offset, which in fact is the important metric, rather than absolute values. Similarly, Fig. 4 represents an example of the evolution of the cost function. It can be observed how the algorithm succeeds in its commitment and the uncovered area is effectively reduced. The initial situation is that in which the delays are not adjusted. However, as stated before, some type of manual adjustment is usually performed every time a new node is installed. In this sense, in order to capture and represent the result of these actions, a LS based optimization was also assessed . The process is as follows, TXs are randomly ordered and evaluated sequentially considering all possible delays, if a better solution is found, it substitutes the previous one. Different runs have been done considering different orders and results are plotted in Fig. 5 for two of the scenarios. Given that 10 tests where performed, the average cost value is shown along with the maximum and minimum results. From here, it can be observed how SA outperforms 5 020 40 60 80 100 120 0 20 40 60 80 Iterations Evolution of delays [μs] Figure 3: Evolution of proposed delays. 020 40 60 80 100 120 1400 1600 1800 2000 2200 2400 2600 Iterations Uncovered area [km2] Figure 4: Evolution of uncovered area. No LS SA 1200 1300 1400 1500 1600 1700 1800 Uncovered area [km2] No LS SA 350 400 450 500 550 600 2287 Figure 5: Average, Max. and Min. uncovered area with no optimization (No), LS and SA for two different study cases. all possible LSs. Besides, the order of evaluation in the LS showed a significant impact on the final result and that is why the deviation of results is clearly higher. Finally, Fig. 6 illustrates the coverage before and after the optimization for the three considered scenarios. Note that the maps have been scaled to the same size but their real dimensions are 90×90 km2, 100×90 km2 and 50 ×50 km2for scenarios 1, 2 and 3 respectively. Although in all cases there is a coverage gain, different levels of improvement are obtained and this obviously depends on the layout of the network and the orography. Besides, it can be observed that gains are not at cost zero. Areas are modified and in some pixels the initial coverage is lost. Of course, in this point is where the population weight in the cost function plays its importance, also critical areas can be protected by means of constraints to be respected. 6 (a) Scenario 1. Before. (b) Scenario 1. After. (c) Scenario 2. Before. (d) Scenario 2. After. (e) Scenario 3. Before. (f) Scenario 3. After. Figure 6: Comparison of covered areas before and after the optimization. 7 5 Implementation issues and other results This section constitutes a complement to the description of the algorithm. Although, next graphs and figures were obtained prior to the final result, for the sake of clarity, it was considered more interesting to keep this section at the end of the paper. Since a lot of evaluations are required, one of the drawbacks of the proposal could be its execution time, however the method was easily parallelized because each pixel can be evaluated independently of others. Our particular implementation was programmed in C++ and OpenMP [16] to achieve the parallel execution. In a computer with four 3 GHz processors (quad-core), the optimization of 10 TXs in an area of 90 ×90 km2 took less than two hours. Even though SA is a metaheuristic with very few parameters to adjust, some preliminary simulations where required to guarantee that CPU time was minimized. In particular, it was analyzed the impact of the δfactor in the cooling equation, the length of the equilibrium condition for each temperature value and the maximum range of delays to evaluate. Note that all subsequent results are normalized to the maximum obtained value in each case. 5.1 Length of equilibrium condition Equilibrium is defined as the number of iterations that must be evaluated in each temperature value. It can be demonstrated mathematically that the higher this number, the higher the probability of reaching the optimum solution [8]. However, an upper bound is needed for practical optimizations. A general accepted rule-of-thumb is a number of times around the number of neighboring solutions. This is estimated as the product of the number of TXs and the number of delays to be evaluated. Note that we assume a discrete range, with delay values rounded to the second decimal place when expressed in µs. For a finer adjust of this empirical adjustment, the rule was multiplied by a parameter βwith the final aim of obtaining faster simulations. Results perfectly match the theory, but marginal cost gains are obtained whereas execution time increases exponentially. Following the results in Fig. 7, even 0.5 can be an appropriate value for β, so simulation time can be dramatically reduced in the scenario of optimizing very large networks. 5.2 Maximum range of delays to evaluate Regarding the selection of the maximum range of delays to evaluate, it is remarkable that what it is important is the relative value between the minimum and maximum delay and not the absolute ones. In fact, as stated before, data does not reaches all TXs at the same time in large SFN networks and so some TXs have a margin for negative adjustments. With some quick pre-simulations the operator can obtain an idea of the best range of delays. Adjusting this margin to a too low value reduces the solution space, and so SA is limited to find the best solution. On the other hand, an indiscriminate increase of this range hinders the normal operation of SA, which is forced to evaluate redundant solutions. Fig. 8 quantifies these facts for an easy scenario with 4 TXs. 5.3 Impact of δ Finally, in order to compute the most adequate value for δ, several values were simulated and again compared in terms of cost and execution time. The most clear impact of δappears on execution time which increases prohibitively for the smallest simulated values (Fig. 9(b)). Regarding the impact on cost (Fig. 9(a)), gains are very modest, although it was observed a close dependence with the size of the scenario. In this test case, what would determine the final value of δis hardware capabilities and the available simulation time. 8