Novel Heuristics for Cell Radius Determination in WCDMA Systems and Their Application to Strategic Planning Studies

Mobile communications field is, nowadays, one of the most relevant technology research topics. Its fast evolution, from analog (like Advance Mobile Phone System), to digital systems (like Global Systems for Mobile (GSM) Communications or IS-95), and currently to 3G multiservice systems, such as Universal Mobile Telecommunication Systems (UMTSs) and 4G Long Term Evolution (LTE), has required the development of new technics, and produced the convergence of several telecommunication research areas. On the other hand, the high level of acceptance of the mobile technologies by customers (see Figure 1), and their need of new and more complex services, is a catalytic element for doing research to obtain more efficient technics in mobile communications.

The general architecture of a mobile network may be described in the same way as the traditional fixed network; it is formed by an access network and a backbone network. The access network is named Base Station Subsystem (BSSs) in 2G systems like GSM, and UMTS Terrestrial Radio Access Network (UTRAN) in 3G systems like UMTS. The backbone network corresponds to Network Switching Subsystems in GSM and to the Core Network in UMTS. Figure 2 shows an example of these architectures.

One critical problem in mobile network design is the determination of the cell radius [1]. The underestimation of the cell radius leads to an overestimation of the number of Base Stations (BTS) required to provide service in an specific area, and hence excessive deployment investment costs. This is obviously bad news for the business of the network operator. On the other hand, an overestimation of the cell radius results in the installation of fewer BTSs than needed, and then in shadow areas. This means the network operator provides bad Quality of Service (QoS) in terms of coverage, and customers will complain.

Most of second generation systems, like GSM, use Time Division Multiple Access (TDMA) as radio access technology and therefore, they can be defined as hard blocking systems, that is, the number of users in the system is limited by the amount of hardware installed in the Base Station (BTS). Therefore, in GSM systems, the cell radius is mainly determined by the coverage planning (in this paper the term coverage refers to radio propagation coverage). In case that the QoS required (expressed as the blocking probability) is not fulfilled, the network operator must install more electronic equipment to incorporate more traffic channels to the BTS. It is a relatively simple task in TDMA systems.

Most of third generation systems, like UMTS, are based on WCDMA. These are soft blocking systems, where the number of users is not limited by the amount of channels in the BTS, but by the interference generated by their own users, and the users in neighbor cells. The maximum interference allowed in the system can be measured by a parameter named interference margin, which is used in the calculation of the link budget at the coverage planning process, and also to calculate the maximum number of users in the capacity planning process. Note that there is a tight relationship between the capacity and coverage planning processes in this case. Furthermore, the design of 2G systems is mainly oriented to the voice service [2], but 3G systems are designed to handle traffic from different sources, with different bit rates and, obviously, different requirements in terms of Grade and Quality of Service [3]. It is straightforward that this issue increases the planning complexity.

Cell radius calculation in WCDMA systems has been extensively studied before in the literature [4‐8]. However, most of these models only consider a single service, which may result in a nonaccurate estimation of the cell radius in multiservice environments. In addition the studies of multiservice environments are usually based on simulation [9, 10], which requires a large set of input parameters. Moreover, user and service simulation models are usually quite complex. As we will see in the body of the paper, the problem of the cell radius determination in WCDMA systems is equivalent to a problem of capacity assignment among different services. Another approach to this complex problem starts from the cell radius, and finds the optimal capacity assignment to the services [11] or to study the maximum throughput.

Currently most operators are deploying their 3G and beyond networks in order to offer high speed data services to their customers. Furthermore in developing countries, or in some rural areas where the 2G deployment is not completely finished, the operators are studying whether implement a proper 3G infrastructure or subcontract it to the dominant operator. Note that a very relevant factor in this decision will be the price that the dominant operator establishes, which may be sometimes conditioned by the National Regulatory Authority (NRA). The determination of the interconnection, roaming or termination price must be based on technoeconomic studies under the so-called Bottom-Up Long Run Incremental Cost model (LRIC) [12, 13] which is recommended by the European Union [14]. The objective of the LRIC is to estimate the costs incurred by an hypothetical operator with the same market power of the operator under study, that tries to implement his network with the best suitable technology. To do this, a complete design of the network has to be done at a national level, that is, to calculate the network equipment for each city, town, rural area, highway, road, and so on. Based on this, the mobile operator will have enough information to make the decision about built or buy, and/or to claim to the NRA with objective data to obtain better price.

It is straightforward that constructing a LRIC model requires the calculation of a large number of different scenarios, where the cell radius of the Nodes B (the 3G Base Stations), has to be estimated. Therefore the heuristic model used for this estimation has to be general enough to be applied to a large set of scenarios with a reduced set of parameters, so simulation is not valid. Furthermore, note that obtaining a good LRIC model for a country involves thousands of B Nodes, so the heuristics applied must be computational efficient. Thus, modern heuristics as evolutionary computation are limited approach in this case. Finally the selected calculation method has to be able to provide a fair estimation of the cell radius.

This paper proposes several novel algorithmic approaches to the cell radius determination problem under the constraints presented previously. Our approach starts from a multiservice scenario and the maximum capacity of the cell, and based on the services parameters we obtain the optimal capacity assignment for each service, and then, as final objective, we obtain the optimal cell radius. We propose the following heuristics. First, an iterative load factor reassignment heuristic is presented, which is able to solve the problem giving encouraging results. An analytical algorithm is also proposed and compared with the iterative heuristic. Finally, a combination of both algorithms is also tested, where the analytical approach is used to generate an initial solution for the iterative approach. We will show the performance of our approaches in several test problems considering WCDMA multiservice scenarios. With the proposed heuristics we fulfil all the requirements defined in the paragraph previously, that is, a fast procedure that is able to provide good estimations of the cell radius using a limited set of input parameters, and hence easy to use in different scenarios.

The rest of the paper is structured as follows. Next section defines the cell radius determination problem in WCDMA networks. In Section 3 we propose the heuristics for solving the problem, and in Section 4 we show the performance of the heuristics proposed by performing some experiments in WCDMA multiservice scenarios. We also present the implementations of our heuristics in a software tool named DIDERO and their applications in different regulatory projects. Section 6 concludes the paper giving some final remarks.

Let us consider a 3G mobile network based on WCDMA technology, where the mobile operator provides a set of services (voice, data 16 kbps, data 64 kbps, etc.) each one defined by a set of parameters (binary rate, user density, quality of service, etc.). The mobile operator needs to have an estimation of the number of B Nodes in each area and thus it is required to calculate the cell radius for each B Node. As it is mentioned in the introduction, cell radius determination in WCDMA is a complicated process because, opposite to TDMA, the number of users and the total throughput is limited by the amount of interference in the radio interface. Of course, this interference not only limits the capacity of the system, but also the coverage by propagation, because the total noise in the system increases as more users are active.

Propagation coverage studies mainly imply two steps. The first one is to calculate the maximum allowed propagation loss in the cell, defined here as , and the second is to use an empirical propagation method to calculate the cell radius for this pathloss. Typical methods are the Okumura Hata COST 231 model, [15], or the Walfish and Bertoni [16].

The value of is calculated using a classical link budget equation

where is the transmitter power, is the sum of all gains in the chain, transmitter antenna, receiver antenna, and soft handover gain, is the sum of all the losses in cables, body losses, and in-building losses, is the receiver sensitivity which includes the required , thermal noise, receiver noise figure, and processing gain, and finally, is the different margins we need to take into account, fast fading margin, log-normal fading margin, and the interference margin, . This interference margin is a very relevant value, because it measures the maximum interference allowed in the system due to its own users. Therefore this value indirectly limits the maximum number of users in the system. Note that all the parameters in (1) are inputs of the system and therefore can be obtained from this equation.

As it was mentioned before the cell radius by propagation is obtained applying the into an empirical propagation method. In our work we have used the 231-Okumura Hata model because it is broadly considered as the most general one in mobile networks applications [17]

where is the frequency in MHz, is the height of the Node B in meters, is the height of the mobile user in meters, and is the cell radius by propagation in Km. Note that and are parameters defined in the COST 231 specification. They provide the influence of the height of mobile terminal and the type of city, respectively, and they are defined as follows:

Note that as the value of changes for the different services, the propagation coverage study has to be done specifically for each one, and of course for the uplink and the downlink. Therefore the formulation explained previously, and the value , has to be applied for each service and each direction (Uplink (UL) and Downlink (DL)) obtaining a set of two vectors containing, for each service, the cell radius by propagation, ( and )

Now we focus on capacity studies. As it is done in propagation studies, cell radius must be calculated independently for the uplink and the downlink. The equations that determines the radius in both directions are quite similar. Then for simplicity reasons, this paper focuses in the calculation of the cell radius for the downlink case, since this is the most restrictive direction [18‐20].

The interference margin used in (1) determines the maximum load of the cell, , by means of the following relation, [18, 21]

This factor indicates the load of the cell. If there is no user in the system. On the opposite if , the amount of interference in the system grows to and hence the system goes to an unstable state. Therefore typical values of the are between 3 and 6 dB, which means a load of 0.5–0.75.

Although in the real operation of the system, there is no capacity reservation between the different services, in the dimensioning process it is required to allocate part of the capacity to each service. Therefore the load factor, that is, the capacity of the cell, must be allocated to the different services, resulting the load factors of the each service

The number of active connections of each service is calculated by dividing the total load factor of each service type over the average individual downlink load factor of the connections of the service

where the downlink load factor is defined by the following equation:

where is the so-called downlink orthogonality factor, is the binary rate, is the so-called activity factor of the service , is the average intercell interference factor, and is the bandwidth of the WCDMA system.

The total offered traffic demand, in Erlangs, is obtained by using the inversion of the Erlang B Loss formula [22]. The inputs for this algorithm are the maximum number of active connections in the cell and the Quality of Service (QoS) of the service expressed by the blocking probability

Note that in (9) the total offered traffic demand, , is divided by the factor and the maximum number of active connections, , of the service is multiplied by it. This is included to considerer the soft blocking feature inherent to the WCDMA system, [23].

Multiservice traffic in UMTS has been extensively studied in the literature [24]. However in the strategic planning mobile operators trend to use simplified models that provides under estimations of the cell capacity to be in the safe side when they estimate the number of Node B's to provide service to the customers in the area under study, [25]. Because of the reasons stated in the previous sentence, in this proposal we use the Erlang B formulation. However it is and independent part that can be substituted by any other traffic model formulation.

The number of users in the cell ( ) is obtained from the division of the total offered traffic demand for service i, ( in Erlangs), by the individual traffic of a single user of this service (obtained from the connection rate and the mean service time ):

The cell radius for each individual service is calculated as a function of the number of sectors in the BTS, , the number of users of service i per sector and the user density as follows (note that a Node B may be divided into several sectors. Each sector corresponds to a cell):

Note that this process has to be done also for the uplink direction (UL). Therefore, at the end we have obtained another set of two vectors (one for the uplink and one for the downlink), with the cell radius by capacity of each service:

Note that the values of and largely depend on the distribution of the capacity over the different services by means of the total load factor allocated to each service and . A bad allocation will lead to large differences in the values of the radius, while an equilibrated one will produce approximately the same value for all the services.

Note that at the end of this process we have obtained a set of four vectors, , , , and . The final cell radius, will be the minimum value between and which represents the most restrictive cell radius under propagation and traffic criteria respectively

As a conclusion of this section we have identified two problems in the cell radius dimensioning, that can be named outer problem and inner problem, as it is shown in Figure 3.

The outer problem is solved just making an iterative process to equilibrate the value of the cell radius between the resulting value calculated by propagation studies and the resulting one calculated by capacity studies. This is done by means of increasing the value of the interference margin, , when the cell radius by propagation is higher than by capacity or vice versa. The inner problem is much more complicated because it implies the use of the traffic concepts and nonlinear process which underlies to (9)–(12).

This paper focuses on the design of heuristics for solving the inner problem (from now on we will focus on the donwlink direction, we therefore do not include the DL subindex in the formulation since it is assumed). With the definitions given before, the cell radius determination problem by capacity criterium can be defined as follows:

Find , such that

which maximizes . Note that we focus on the inner problem, where the traffic is the most restrictive factor, therefore, in this case.

Note that if we allocate optimally the capacity to the services, by means of the values, the cell radius of all service will have almost the same value, and hence the cell radius by capacity will be maximized. Note that a suboptimal allocation leads to very different values of the cell radius of the different services, and hence to a bad estimation of the final radius. This situation is shown in Figure 4, where the dashed red arrow determines the final cell radius.

In order to validate the heuristics presented in this paper, we have tested them in several experiments based on scenarios with different service combinations. Specifically, we have defined mixtures of two, three and four services, each one having its own requirements in terms of binary rate, quality of service, user movement speed and user density in the area under study. Furthermore we have modified the traffic figures of the services to consider balanced and unbalanced traffic. Balanced traffic means that the individual throughput of each service is similar to the throughput of the other services.

We have used an interference margin of 6 dB which means a cell load factor of 0.75. We have also configured the radio propagation parameters to make the capacity the most restrictive criteria. This set of radio propagation parameters is shown in Table 1.

The parameters of the different services are shown in Table 2, with being the binary rate, the user speed in Km/h (services in which users have different speeds can be considered as different services. This is because they have different values of and therefore different values of individual load factor ), the bit energy-to-noise ratio in the downlink, the orthogonality factor and the activity factor. The quality of service is defined by the Blocking/Loss probability . The value of the total downlink load factor, , is 0.75 according to the previously defined. Finally, the value of the average intercell interference factor to 0.88 [29].

As we have mentioned before the complete set of scenarios are divided into balanced and unbalanced traffic scenarios. Tables 3 and 4 provides the traffic figures for the different services in these two general categories. In this case and are the call attempt rate and the service time in the business hour, respectively, and is the user density in the considered area. Table 5 shows the combination of the services involved in each experiment. Note that the third column in the table shows if the experiment is based on balanced (B) or unbalanced (U) traffic.

The results of the different experiments are shown in Table 6 and Figure 5. For the iterative and combined algorithms, Table 6 also shows the number of iterations. The reduced algorithm obtains the optimal value of the cell radius in all experiments, excluding those scenarios in which users are moving at different speeds. This low performance of the reduced algorithm is due to the fact that the differences in the individual load factors of a service with different user speeds are very small. Therefore the algorithm is not able to distinguish between them.

As it was mentioned in Section 2, the optimum value of the cell radius is obtained when there are quite small differences in the cell radius of the different services. We will illustrate this in Experiment . In this experiment, we have compared the results obtained by the three heuristics proposed against the cell radius calculated with an assignment done using the binary rate and the user density, let us name it free assignment (FA) following the equation

The initial values of the load factors are for the service , voice, for , data 64 Kbps and for , data 144 Kbps. The results for the downlink cell radius per traffic are shown in Table 7.

Note that the cell radius of each service is quite similar in the three proposed heuristics but in the FA the cell radius of the is almost 50% larger than .

Another interesting point to observe is the final occupancy level of the load factor. In case of an optimal allocation, the sum of the individual load factors, allocated to the services after the cell radius is calculated has to tend to the limit established in the design, in our experiments . The results are shown in Table 8. Note that the proposed heuristics use more than 99% of the total available capacity, while the FA only uses 62%.

Finally note that the combined algorithm always obtains the optimal value even in scenarios with different users speeds, and it requires fewer number of iterations than the iterative algorithm. Figure 6 shows a comparison of the number of iterations needed to obtain the optimum cell radius in problem Exp-5. Note that the combined heuristic obtains the optimum cell radius faster than the iterative algorithm, since it starts from the result obtained by the Reduced heuristic.

Finally, regarding the computation time, the three algorithms we propose in this paper for the cell radius determination problem obtain the solution to the problem in less than 1 second. This is a very important point for the inclusion these algorithms in a strategic network planning tool, where a large number of scenarios have to be calculated.

This paper proposes three different algorithms for the calculation of the cell radius under traffic criteria in multiservices scenarios, named iterative, reduced and combined. We have shown that the three algorithms are able to solve the cell radius determination problem, providing good quality solutions. However, the reduced algorithm is not able to produce optimal solutions when the users are moving at different speeds. The iterative and combined heuristics provides the optimal solution in all the cases studied, but the combined approach converges faster than the iterative heuristic.

The combined heuristic has been implemented in existing strategic planning software tool to calculate the Node B deployment in a whole country. We have presented a work scenario in Spain were our proposed heuristic obtains better solutions in terms of number of Node Bs, which represents a great investment cost saving. This heuristic has been applied in several regulatory processes under the supervision of the corresponding National Regulatory Authority.