Apparatus and method for non-regular channel assignment in wireless communication networks.

ES 2 149 803 T3

DESCRIPTION

Device and method for the non-regular allocation of channels in wireless communication networks.

This invention relates to wireless telephone communication systems including a plurality of substantially contiguous cells and a device for assigning radio channels to cells, and to methods for dynamically altering radio channel assignments to a plurality of contiguous non-regular cells in which a service area of ​​a wireless communication system is divided.

The service area of ​​a wireless communication system is divided into connected service domains known as cells, in which radio telephone users communicate, via radio links, with the base station serving the cell. The base station (BS, from the English "base station") was connected to the terrestrial network. Efficient use of the available radio frequency spectrum is achieved through the reuse of the same radio frequencies in designated co-user cells that are sufficiently separated by distance so that the combined interference generated by all co-user cells is below levels. tolerable. The allocation of radio frequencies to cells has been based on assumptions of regularity (that is, cells of equal size and regularly spaced with evenly distributed traffic loads), which allow the adoption of simple rules to identify cells of co-users, and to divide the RF (radio frequency) spectrum in sets of channels. When regularity assumptions are not met - as is often the case in real world situations - regular channel assignment rules do not necessarily lead to efficient use of the RF spectrum, if they can at all. To use the RF spectrum optimally, the problem of non-regular channel assignment must be solved.

WO-A-90/10342 relates to a method for planning radio cells. The method includes the following steps: the demand for trophic is estimated geographically; acceptable coverage of traffic demand is produced with the help of a number of cells with adequate transmitting powers and antenna arrangements; a number of channels are attributed to each cell, which corresponds to the estimated trophic demand, taking into account a margin for an acceptable block; coverage and interference measurements are carried out for the cells, the measurement results of which are stored in a measurement database; an exclusion matrix is ​​calculated based on the measurement results, whose matrix represents the interaction between cells in the system; an attribution algorithm is iterated, whose algorithm, through the use of random techniques, provides different collections of channel attributions for cells; if the allocation of channels is not possible with respect to the number of channels in a given frequency band .. a new attempt is made and the subsequent steps are repeated; and if the number of channels was high enough, a radio call design is obtained which is acceptable from the interference point of view and the blocking point of view.

"A Resource Allocation Technique for FCMA Systems", Alta Frequenza, Vol. LVII-N.2, pages 89-96, Feb.-March, 1988 describes a frequency allocation scheme that systematically uses lower limits for frequency demand and a non-deterministic iterative allocation strategy.

In accordance with one aspect of this invention, a wireless telephone communication system is provided according to claim 1.

In accordance with another aspect of this invention, a method is provided according to claim 5.

A channel assignment system assigns channels to various cells by optimally dividing the available radio frequencies into non-overlapping sets, the optimal grouping of co-user cells, and the best assignment of the former to the latter. The objective is the maximization of the traffic handling capacity, which, given the multitude of cells, is expressed as the maximization of a bottleneck capacity relationship, known as the capacity factor. A capacity ratio for a cell is defined as the ratio of the number of radio frequencies assigned to the cell to the number of radio frequencies necessary to satisfy block probability requirements. Given a channel assignment, the latter is fixed once the trophic loads and the desired blockage have been specified.

Given a group of cells of arbitrary shape, size, and / or position, the available radio frequency spectrum is divided into optimal channel sets, and these channel sets are assigned to cells in an optimal manner. As trophic loads can vary from cell to cell, the goal of the allocation is to maximize the combined traffic handling capacity of cells. This objective is expressed as the maximization of the bottleneck capacity ratio that can be supported for a satisfactory blocking ratio and interference level, which is the lowest capacity ratio across all cells.

The solution of the non-regular or optimal channel assignment is broken down into two mathematical programs designated as Master Program and Subprogram. These are solved iteratively with the help of a channel set augmentation technique implemented between Master and Subprogram solutions.

Brief description of the drawing

In the drawing:

Figure 1 is a schematic of a regular cell area layout of a wireless / cellular radiotelephone system;

Figure 2 is a block diagram of a wireless / cellular radiotelephone system;

Figure 3 is a schematic diagram of a data processing system for assigning radio channels to various cells of a wireless / cellular radiotelephone system;

Figure 4 is a flow chart of a method for assigning channels to various cell cells.

ES 2 149 803 T3 a wireless / cellular radiotelephony system;

Figure 5 is a flow chart of a method for making feasible initial channel assignments;

Figure 6 is a flow chart of a method for providing an entire solution for the Master Program;

Figure 7 is a flow chart of a method for channel set augmentation; and Figure 8 is a flow chart of a method for the resolution of the Subprogram. Detailed description

A conventional regular hexagonal cell design of a cellular radiotelephone system is shown schematically in Figure 1. Representing the geographic service area in terms of a hexagonal grid establishes a geometric pattern that allows frequencies to be assigned according to an arrangement in patterns. which allows the reuse of these frequencies in a controlled repeatable regular assignment model. Cell areas each have specific sets of channels assigned to them. Each set of channels comprises a plurality of individual transmit and receive radio channels for use within the cell area. In this model, shown in Figure 1, the cells marked "A" are co-user cells and all use the same set of channels. The same is true for co-user cells marked "B", "C", etc., each of which has its own assigned set of channels.

Each cell receives radio signals from an antenna system associated with a base station (BS), which includes radio transceivers and which are also connected to the public switched telephone network (PSTN) through trunk lines or a suitable equivalent. The antennas 101 are either omni-directional or directional. Directional antennas 102 are used to sector cells generating smaller service areas of the angle cradle type.

A typical cellular system is shown in the block diagram of Figure 2. A plurality of mobile switching centers (MSCs), 202 and 203, are shown connecting the mobile radiotelephone system to the public telephone network with switched 201 (PSTN). The switching of the MSC centers interconnects a plurality of base stations (BS) 210, each of which provides service to a cell coverage area. Each coverage area is shown with irregular borders typical of a real system. Each base station has radio transmission / reception equipment and radiating antennas to serve 250 mobile radiotelephones within its cell coverage area.

An operations and management center (OMC) 220 is coupled to the MSC 202 and 203 centers to control their system operation and their associated base stations 210. The OMC 220 is a central control station that includes data processing and data entry equipment to accept data inputs from data storage elements and control elements in real time. This data processing arrangement can be used in implementing channel assignments in combination with remotely tunable radio transceivers located at base stations.

An illustrative embodiment of data processing equipment included in the OMC center to control the allocation and tuning of radio transceivers at base stations is shown in block diagram form in Figure 3. A general purpose computer 310 has a stored program included in its memory 311. This program includes instructions for performing the non-regular assignment of radio channels to a cellular system as described in more detail below. The initial input data is supplied through input circuit 312 to computer 310. The input data includes available cells. Available radio frequencies are also entered into computer 310. Other input data includes interference information usually in the form of a cell-to-cell interference matrix, which defines the interference with each cell from every other cell. The input data also includes system restrictions necessary for the desired channel assignment. Traffic usage patterns are provided as an input. Traffic can be measured in real time.

In this illustrative embodiment of the invention, the allocation process is performed in computer 310 in accordance with the instructions contained in memory 311. The resulting non-regular allocation is sent out through outlet 313 to the MSC 315 and in turn, it is forwarded to base stations 321. The individual tunable radios 322 included in the base stations are tuned to the appropriate frequencies in accordance with the radio channel assignment determined by the assignment process. Add-on output conductors allow graphs and data to be printed out at the OMC center.

To pose the previous assignment problem algebraically, the following notation is used. Let j = 1,, J be the index of different logical cells (a logical cell is the part of the coverage area of ​​a cell served by a logical face.) I = 1, ...., J the same as j (the combination (i,

j) designates a pair of logic cells) and j the number of channels needed in the logic cell j to satisfy the blocking requirements

N the number of channels available

Iij was contributed to co-channel interference from the logic face i to the logic cell ^j

Sj the signal intensity of the logic face j T the threshold level of the signal / interference ratio

The unknown quantities of the problem are:

g the capacity factor (bottleneck capacity ratio)

ES 2 149 803 T3

K the number of channel sets N_k the size of the set k of channels {1 if the logical cell j is covered by the set k of channels

0deotromode

Channel assignment can be expressed as a mathematical programming problem of the form:

Maximize g

<td colspan="2">subject to:</td><td>xkj Nk&gt; yj g k</td><td> (1)</td>

<td>to J</td><td> =1,</td><td>..., J</td><td></td>

<td></td><td></td><td>Nk &lt;N k</td><td> (2)</td>

<td>Prob</td><td>Σ i = j</td><td>^Sj Iij Xki &lt;+ M (1 - Xki)</td><td> &gt;1</td>

<td></td><td></td><td> (3)</td><td></td>

<td colspan="2">for j = 1 xkj = 1.0</td><td>, ...., J and k = 1, ...., K</td><td></td>

N_k &gt; 0, an integer where M is a large positive number.

The constraints in (1) attribute channels to logic cells in proportion to the requirements of the cells. In restriction (2) the total number of assigned channels is limited by the number of available channels. Constraint (3) ensures that the ratio of signal intensity to co-channel interference is above the desired threshold value with a 1-α confidence level. The previous formulation of the channel assignment problem may allow for additional restrictions that would reflect special needs of the user. Examples of such restrictions are discussed later in a discussion of the solution procedure for the basic formulation.

The above problem constitutes a large-scale nonlinear mixed-integer stochastic mathematical program. If, for example, a cell grid has 210 logical cells (70 cell positions, with 3 logical faces for each cell position), and 200 sets of channels are considered, there will be 42,211 restrictions and 42,200 integer variables (excluding remainder variables ( slack variables)), of which 42,000 will be binary.

This problem is broken down into two computationally treatable parts that use generalized linear programming. The original problem is decomposed into two smaller problems that are solved one after the other in an iterative sequence, exchanging their respective solutions, until the optimal solution is reached. Following the established conviction, the two problems are called Master Program and Subprogram. The Master Program consists of all restrictions except the stocetic ones in (3), which constitute the restrictions of the Subprogram.

The algebraic formulation of the Master Program and the Subprogram is expressed as follows.

The following expressions define the Master Program of block 420, discussed subsequently with respect to Figure 4:

Maximize g subject to:

^Σ xkj Nk&gt; yjg (4) all k available for = 1, ..., J

Σ Nk &lt;N (5) all available k

Nk&gt; 0, integer where xkj are constants that satisfy the co-channel interference conditions. These values ​​are supplied by the Subprogram described later.

The applet contains the constraints that ensure that the ratio of signal strength to co-channel interference is above a desired threshold value. Its objective coefficients are the simplex multipliers corresponding to the constraints (4) of the Master Program.

The Subprogram has the following form:

Maximize

<td colspan="4">^v = Σ ^{λ x}j^j</td>

<td>subject</td><td>to:</td><td></td><td></td>

<td></td><td></td><td rowspan="2">^Sj x &lt;τ + ^{m (1} - ^xj)</td><td></td>

<td>Prob</td><td>Σ i¿ „ i = j</td><td>&gt; 1-α</td>

<td></td><td></td><td> (6)</td><td></td>

<td>to J</td><td> = 1, ....</td><td>, J</td><td></td>

xj = 1, 0 where λ₄ is the simplex multiplier corresponding to the j-th constraint in (4).

The collection of channel sets included in the Master Program is made up of all the solutions of the Subprogram. The kth solution of the Subprogram provides values ​​for the binary variables xkj. A set of channels is defined in terms of the co-user cells it serves. The collection of channel sets grows with each new Subprogram solution, and this growth helps to improve the Master Program solution. Growth in the channel set collection stops when the optimal solution is reached.

The general structure of the allocation process comprising the Master Program and the Subprogram is shown in figure 4. The solution procedure, as shown in the flow process in figure 4, involves four main functions. These are: Channel Assignment Initialization (block 410), a Master Program Solution (block 420), Channel Set Increase, and Subprogram Solution (closely related blocks 430 and 440). In the first function, block 410,

ES 2 149 803 T3 which is the initialization of the channel assignment, a feasible channel assignment is obtained before proceeding with the optimization. If the model is applied to an existing grid, the present channel assignment can serve as the initial channel assignment, assuming it satisfies all system constraints. If it violates any of the restrictions, it is modified by the Initial Channel Allocation algorithm, as described later, to satisfy all the restrictions.

Once a feasible initial channel assignment is obtained, the remaining three functions are executed in an iterative sequence. First comes the solution of the Master Program in block 420, whose solution provides the system values ​​of g, N_k, τ, and Xj. τ is a simplex multiplier corresponding to the constraint (5) and Xj is a simplex multiplier corresponding to the j-th constraint in (4). This information is used by the Channel Set Increment algorithm at block 430 which invokes the Subprogram Solution algorithm at block 440 several times in order to generate new channel sets.

The Channel Group Augmentation algorithm is a heuristic process that improves problem solving. Check the values ​​of Nk and Xj, which are used in the following solution of the Subprogram. The Subprogram solution provides the values ​​of ν and xkj.

After a specified number of channel sets have been generated, the optimality as prescribed in decision block 450 is examined. If the solution is optimal, as determined in decision block 450, the algorithm terminates and the assignments are provided in block 460. In another case, the cycle is repeated again with the solution of the restricted Master Program in block 420.

The following condition indicates optimality: Let K-1 be the current cycle, and let xkj be the optimal solution of the new Subprogram. Let τ be the simplex multiplier corresponding to the constraint (5) of the relaxed Master Program. Yes

Σ ^xKj^Xj &lt; ^τ (7) ^j then the present solution is optimal for the relaxed Master Program.

The solution procedure described here is finite as the number of sets of different channels is finite, and each solution of the Subprogram contributes a new set of channels to the Master Program. That the set of channels that enter the Master Program in each cycle is new is based on the following observation. The simplex multipliers of the relaxed Master Program in cycle K-1 satisfy the conditions: (5)

Σ XkjXj - T &lt;0 (8) ^j for k = 1, ..., K-1

If the new solution xKj of the Subprogram is added to the Master Program, it cannot satisfy the condition in (7), since this will lead to the termination of the process. As it violates the requirement in (7), it cannot be identical to any of the K-1 solutions found previously, by condition (8). Therefore, xKj represents a new set of channels. Since the number of cells in a grid is finite, the number of distinct cell clusters representing different sets of channels is also finite. Therefore, the solution procedure is finite.

The solution procedure should start with a feasible channel assignment, that is, a channel assignment that covers all cells and satisfies the channel availability restriction and the co-channel interference restrictions. For an existing cellular grid, the current channel assignment can serve as the initial channel assignment, assuming it is feasible. If the existing channel assignment is not feasible (the fact that it is not feasible would topically result from the violation of interference restrictions), or if there is no existing channel assignment, it is necessary to generate an initial feasible channel assignment.

The method for deriving an initial channel assignment is based on a variation of the Channel Group Augmentation algorithm. In the most general case, as shown in Figure 5, the existing channel assignment violates the interference constraints. In this case, the Channel Assignment Initialization consists of two phases. In Phase I, the channel sets in the existing channel assignment are modified (Block 507), one at a time changing values ​​for Nk and Xj. If a set of channels violates the interference constraint (Decision Block 502), cells are removed (Block 504) until the interference constraint is satisfied. If the interference constraint is satisfied by an existing set of channels, the algorithm will assign as many additional cells as possible (Block 505), assuming the interference constraint is satisfied. If the resulting channel sets cannot cover all cells, the second phase is implemented. In phase II, additional channel sets are generated until all cells are covered (Block 506).

Both phases employ the Channel Set Augmentation algorithm. They differ in terms of the initial values ​​used for Xj. In phase I, Xj is equal to 1 for all cells j covered by the existing set of channels, and zero for the remaining cells. In phase II, Xj is calculated using equation (10) described later here.

The Master Program is a linear program that involves the integer variables Nk, which assume values ​​that vary from 0 to N - the number of frequencies available, a number that is normally between 300 and 400. Given the magnitude of the integer variables, they can be obtain almost optimal solutions to this mixed-integer linear program by solving the relaxed linear program without the integer requirements such as by Block 601 in figure 6. For channel assignment purposes, entire solutions must be provided.

The algorithm that provides an integer solution to the Master Program shown in the figure

ES 2 149 803 T3 uses the fact that the optimal channel assignment will use all N available channels. Given an optimal solution to the relaxed problem (the linear program without the integer requirements), the algorithm begins by equating the sizes of the channel sets to the nearest integers to the relaxed solution (Block 601). It ends if the whole sizes of the sets add up to N (Blocks 605, 607, 609). If not, increase (or decrease) by 1 the sizes of the channel sets with the largest positive (or negative) deviation from the optimal non-integer value (Blocks 611, 615). The steps of the algorithm are shown in Figure 6 and are described later in detail.

The term N_k denotes the sizes of the channel sets in the optimal solution, and by N_kits nearest integers. The procedure for obtaining an integer solution to the Master Program is outlined in Figure 5 as follows:

Step 1 Match N_k to the integer closest to N_k. (Block 603)

Step 2 Calculate the difference D © N_k.- N (Blok than 605)

If D = 0, terminate (Block 607). Otherwise, go to step 3.

Step 3 If D &lt;0, go to step 5. Otherwise, go to step 4. (Block 607)

Step 4 Find D sets of channels with the largest difference δ, ^; = N_k - N_k

Reduce the size of each of the D channel sets by 1.

Finish (Blocks 611, 613)

Step 5 Find | D | sets of channels with the largest difference δ, ^; = N_k-N_k

Increase the size of each of the channel sets | D | by 1.

End up. (Blocks 615, 617)

It is easy to verify that, given a non-negative solution to the relaxed linear program, the resulting integer solution will also be non-negative.

Once the complexity caused by entire constraints is removed, the Master Program solution is straightforward. Standard linear programming software can be used. For linear programming standards, the relaxed Master Program is a relatively small linear program, which has a number of constraints equal to one plus the number of log cells on the grid, and a number of variables equal to one plus the number of groups. channels. A large grid is expected to have no more than 500 loology cells. Seven hundred and fifty sets of channels far exceed the number needed to produce an optimal solution.

The cycle number of the Master Program is reduced by generating channel set lists with the channel group augmentation heuristics. One of the factors that contribute to the computational effort in the decomposition of mathematics programming is the repeated solution of the

Master program. Since the optimal channel allocation is derived from the latest Master Program solution, and all previous Master Programs serve only to generate a list of desirable channel sets that are candidates, generating a larger number of candidates in each cycle would tend to reduce the number of solutions in the Master Program while still producing an optimal solution. Therefore, between any two consecutive solutions of the Master Program, the method used generates several new channel sets. The number to generate is specified by the user.

The criteria used in the generation of new sets of channels is that they must have the potential to improve the target value of the Master Program. The first set of channels generated after the solution of the K-th Master Program has this potential since it has a negative cost reduced by the condition (7). In order to heuristically obtain additional channel sets with reduced negative cost, the simplex multiplier Xj is needed. Typically, Xj is supplied by the Master Program solution. As our goal is to generate more than one set of channels between consecutive solutions of the Master Program, it is necessary to review the values ​​of Xj before each solution of the Subprogram without resolving the Master Program again.

Xj's review is based on properties that would be met if the Master Schedule were resolved. They are derived from the following Complementary Remains conditions defined by equation (9):

Xj (xkj Nk -yj g) = 0 (9) k = 1 for j = 1, ..., J

A consequence of the above conditions is that the simplex multiplier Xj, which is required to be non-negative, would be positive only if the corresponding fundamental constraint in equation (1) is binding or, equivalently, provided that the capacity ratio of cell j is equal to the capacity factor of the grid. A cell is referred to as a binding cell.

The condition of equation (9) is used to update the Xj values ​​of binding cells as follows. A new set K of channels, derived from the last solution of the Subprogram, will receive a part of the available channels in the next iteration. This implies that if set K covers cell j, cell j will not be topically binding in the next iteration. By equation (9), the corresponding simplex multiplier Xj will be set equal to zero. Therefore, the following revision rule is used:

_{Xj =} 0sixKj = 1 invariable if xKj = 0 (10)

This revision causes the sets of channels generated by subsequent solutions of the Subprogram to favor binding cells that

ES 2 149 803 T3 were not covered by the last set of channels, since they will have positive Xj values.

The above revision rules deal with binding cells when they become non-binding. Rules are also needed for cells that are not binding in the Master Program solution but which, when new channel sets are added, can become binding. Such cells should be covered by subsequent channel sets. Having Xj assigned a null value by equation (9), however, they don't stand a chance, unless Xj is updated. An alternative way is to communicate to the Subprogram the link status of a cell by transmitting the new sizes N_k channel sets. The Subprogram considers the linkage state of a cell together with the values ​​of the simplex multiplier Xj in the derivation of a new set of channels.

There are several ways to review Nk. In this implementation of the algorithm, it is assumed that the new K-set of channels will receive a K-th of the available channels, while the size of the existing K-1 sets of channels will be adjusted accordingly. . This is,

N ⁿk = _K (¹¹)

If the existing sets of channels were of size N '_k, their new sizes would be

Nk = N'k (12) for k = 1, ..., K-1

The algorithm for generating F new channel sets is shown in flow form in Figure 7.

Step 1 Match Xj and N_k to the values ​​obtained by solving the Master Program. (Block 701)

Step 2 Repeat Steps 3 through 6, F times (Blocks 702, 713)

Step 3 Solve the Subprogram to obtain xkj. (Block 704)

Step 4 Check Xj using equation (10) (Block 705)

Step 5 Calculate NK using equation (11) (Block 709), and check Nk for k = 1, ..., K1 using equation (12). (Block 711)

Step 6 Increase K. (Block 711)

Given the difficulty of searching for a globally or seventh solution method, the inventors have designed an efficient heuristic algorithm for the Subprogram solution. This algorithm builds a solution by selecting among the cells in the grid those that will maximize the target value of the Subprogram without violating the interference constraints of equation (6). Such a set is constructed by adding one cell at a time, giving priority to the cells with the highest value of Xj. A cell can be added to the pool if it does not interfere with cells already in the pool. For cells with the same Xj values, the order in which the cells are considered is important because the inclusion of one cell could exclude, through the interference it generates, more cells than another. Preference is given to cells with a low exclusionary potential. The exclusionary potential would change at each step, when new cells are added to the set. Therefore, the criteria function used to include a cell in the solution is updated after the addition of each cell.

The logic algorithm can be described as follows. At each step, the cells are divided into three subsets. Set C, consisting of the cells included in the solution (that is, xj = 1); set C, consisting of cells excluded from the solution (that is, xj = 0), and set U, consisting of cells whose fate has not yet been determined. At the beginning of the algorithm, U contains all cells, and C and C are empty. In each step, an element of U is placed in C. Their inclusion in the solution may prevent other elements of U from being included. Items excluded from U are moved to C. The algorithm ends when U is empty.

Among cells with equal Xj values, the cell to move from U to C is chosen on the basis of its potential to block other U elements from entering C. There are several ways to measure this potential. In the implementation described in this article, the exclusive potential function pj is defined as the inverse of the “remainder” aj in the interference constraint in equation (6), which measures the margin for additional contributions to the interference experienced in the cell. j.

Pj = ^j aj (13)

The Subprogram solution is expanded to include cells with null Xj. This is necessary in order to deal with non-binding cells that become binding when more sets of channels are generated. Furthermore, the inclusion of as many cells as possible in the Subprogram solution is desirable because of the increased planning flexibility of the system it provides. Therefore, the cells are chosen in the order of descending values ​​of the following criterion function fj:

fj = Xj - ε

K ^xkj ^Nkk = 1

- ε² Pj (14) and j in which K is the last set of channels generated, and ε is a very small positive number.

Given a sufficiently small value for ε, priority will be given to cells with positive values ​​of Xj. The remaining cells will be considered only when all cells with positive Xj have been considered. Between cells with positive and equal values ​​of Xj, the choice of the cell

ES 2 149 803 T3 to be included in set C is based on the excluding potential pj, since according to condition (9), the capacity relationship in the second term of (14) is the same for all these cells - equals the capacity factor of the grid. For cells with null values ​​of Xj, the capacity relationship dominates the choice of a cell to include in C.

The algorithm for the solution of the Subprogram is shown in flow form in figure 8.

Step 1 Place all cells in set U, and empty sets C and C. (block 801)

Y = 10log10 ^Iij i = j'.eC (16)

Following other treatments, it is assumed that

And it is normally distributed. Let μ_γ and σ²γ is the mean and variance of Y, respectively, and R is the threshold value T of the signal / interference ratio expressed in decibels. The¹⁰ equation (15) can be written as follows:

Prob [y&gt; R = 1 - Prob

R - μ γ σγ&gt; 1-α

Step 2 For each element j of U, calculate fj using equation (14). (block 803)

Step 3 Select j * as the element of U with the largest value of fj. (block 805)

Delete j^* of U. (block 806)

Step 4 Calculate aj for each element j of C assuming that j^* (block 807) is also in C.

Step 5 If aj &lt;0 for some j in C, place j^* at C and go to step 8. (block 809)

Otherwise, place j^* at C (block 811) eiralstep6.

Step 6 For each element j of U, calculate aj. (block 813)

Step 7 Eliminate from U any of its elements j with aj &lt;0 and place them in C. (block 815)

Step 8 If U is empty, finish. (block 817) Otherwise, go to step 2.

The calculation of the exclusionary potential pj in the solution of the Subprogram, discussed above, implies the remainder aj of the interference constraint, which measures the margin for additional contributions to the interference experienced in cell j. The rest will vary with the composition of C, the collection of cells covered by the set of channels.

To calculate the remainder aj, the probability expression of equation (6) is converted into an equivalent deterministic constraint for each cell j in U, the collection of indeterminate cells. The restriction in equation (6) can be written as follows:

¹⁵ (17) for j ε U where z is a normal random variable. The res₂₀ Equivalent deterministic triction is as follows:

μγ + ζ_α σγ&gt; R (18) where z_to is the quantile α of a normal random variable. aj is the remainder variable of the above inequality. Therefore, aj = μ_γ + ζ_α σ_γ - R (19)

The values ​​of μγ and σγ depend on the composition of the set C. They are calculated using the assumption that the signals from all antenna faces, when expressed in decibels, are normally distributed independent random variables and that the cumulative interference experienced in the cell j is also normally distributed, when expressed in decibels [9]. Be

Y = P - L (20) where ^L = ¹⁰ &gt; »Gi¿ j ^{I, j} ] ⁽²¹⁾

P = 10 log10Sj (22)

If μ_L is the mean of the cumulative interference L in cell j, expressed in decibels σ /,² the variance of L μ_ρ the mean of the power signal P in cell j, is expressed in decibels as σ_ρ² the variance of P then, the mean and variance of Y are given by:

μγ = E (Y) = E (P) - E (L) = μρ - μL (23)

Prob ^Iij »= j'-eC&gt; T&gt; 1-α (15) for j ε U

To write the above as an equivalent deterministic inequality, we need to know the probability distribution of the signal / interference relationship. Let Y be the value of this ratio, expressed in decibels. That is, σ_γ² = Var (Y) = Var (P) + Var (L) = σΡ ² + aL²(24) μ_ρ and μ_Ρ² they are specified as input data to the model. μ_L and &lt;7l², which vary with the composition of the set C, are calculated in each step of the Subprogram Solution algorithm by a power addition procedure.