MXPA99002741A - Method for putting in operation a system of telecommunications inalambr - Google Patents

Abstract

A method for operating a system is described as a wireless telecommunications system whereby the communication channels are efficiently allocated to cells of the system. According to an illustrative embodiment of the present method, the call demand information is obtained for each cell in the wireless system and is converted to a channel demand. Once the channel demand for each cell is known, a tentative channel assignment is carried out. The call demand information can be obtained as frequently as desired to update the channel allocation throughout the wireless system. In some embodiments, the channel assignment method described herein may be used only to allocate channels. In other embodiments, the present method of channel allocation may be used on an hourly, daily or other temporary basis, such as is appropriate, to provide a channel allocation that is then updated on a substantially continuous basis by any conventional, dynamic channel allocation scheme. To assign channels, an interference graph "that relates the interfering cells to each other defined." When considering the interference of the closest cell, an initial stage is carried out where three channels are assigned iteratively to all the cells in the A system for removing all groups or groups within the interference chart that comprise three mutually interfering cells During the initial stage, the allocation of three channels reduces the channel demand by one in each cell. of such groupings of three elements the demand of the channel is reduced more efficiently where no more than five channels are allocated to satisfy two units of demand of channel.To do this, a decomposition / reconstruction operation is carried out where the graph of Interference is segregated or divided into groupings or groups of cells to which the channels are assigned. The operation to assign channels to the cells when considering the interference of the nearest and closest to the nearest cell does not use the initial stage of assigning three channels. However, it proceeds in a manner analogous to the decomposition / reconstruction process mentioned above , even if the operation is carried out on a cell-by-cell basis, rather than with cell groupings

Description

METHOD FOR PUTTING IN OPERATION A WIRELESS TELECOMMUNICATION SYSTEM. FIELD OF THE INVENTION The present invention is generally concerned with telecommunications. More particularly, the present invention is concerned with a method for putting into operation a wireless telecommunications system wherein the communication channels are efficiently allocated to the various cells or cells of the system to meet the demand for calls.

BACKGROUND OF THE INVENTION Figure 1 illustrates a schematic diagram of a portion of a wireless communications system typical of the prior art. Such a system provides wireless telecommunications service to a variety of wireless terminals (e.g., wireless terminals 101-1 to 103-1) that are located within a geographic region. The heart of a typical wireless telecommunications system is the wireless switching center ("WSC") 120, which may also be known as a "MSC" mobile switching center or a mobile telephone exchange ("MTSO"). Typically, WSC120 is connected to a plurality of base stations (eg, base stations 103-1 to 103-5) that are dispersed throughout the geographic area to which it is attached. ref. 29710 serves the system. In addition, the WSC120 is connected to local and interurban exchanges (for example, the urban center 130, the urban center 130 and the interurban plant 140). The WSC120 is responsible, among other things, for establishing and maintaining calls between wireless terminals and between a wireless terminal and a wired terminal, which is connected to the system via local and / or long distance networks. The geographic area served by a wireless telecommunications system is divided into a diversity of spatially distinct areas called "cells or cells". As illustrated in Figure 1, each cell or cell is schematically represented by a hexagon; in practice, however, each cell usually has an irregular shape that depends on the topography of the terrain. Normally each cell contains a base station, comprising radios and antennas that the base station uses to communicate with the wireless terminals and those cells and also comprises the transmission equipment that the base station uses to communicate with the WSC 120. As an example of wireless telecommunications, when the wireless terminal 101-1 desires to communicate with the wireless terminal 101-2, the wireless terminal 101-1 transmits the desired information to the base station 103-1 which relays the information to the SC120. Upon receipt of the information and with the knowledge that it is intended for the wireless terminal 101-2, the WSC120 then returns the information to the base station 103-1 which relays the information, via radio to the wireless terminal 101-2. The wireless communications described above are presented on a plurality of communication channels. Such channels are characterized by a carrier frequency and a bandwidth (for example, 30 KHz) over which the carrier frequency is modulated to carry information content. Wireless service providers license at a very substantial cost, a spectrum band of sufficient frequency to provide an appropriate number of communication channels to support communications in a given wireless system. The amount of spectrum a provider must obtain to support or support such communications is predominantly a function of: 1) the amount of spectrum a channel consumes, 2) the extent to which the channels used in any of the cells can be reused in other cells, 3) the demand for traffic in the system and 4) the acceptable percentage of blocked calls attempts. With respect to (2), channel reuse is limited by channel interference. Such interference that may occur between cells ("co-channel interference") and between numerically consecutive or nearly consecutive carrier frequencies ("adjacent channel interference") must be maintained within acceptable limits. Since the spectrum is very expensiveIt is disadvantageous that a license provider provides substantially more spectrum than is required to support communications within the wireless telecommunications system. As such, it would be advantageous to have an efficient method for allocating spectrum (that is, allocating channels to each cell in the system) to minimize channel requirements throughout the system. A class of allocation method is referred to as a dynamic channel assignment ("DCA"). DCA schemes usually have a local focus where changes in demand for calls between nearby cells, perhaps at a number of sites or locations or locations throughout a wireless telecommunications system, provide the basis for a revised channel allocation that It is provided by a DCA model. Such models can be used to reassign channels on a base updated to the minute. While the prior art provides a variety of DCA schemes, as a class they usually suffer from several disadvantages, as described hereinafter. First, typical DCA models may be less reliable when used to reassign channels as a result of relatively larger changes in call demand, such as can be presented per hour (that is, hours of "greater affluence" versus hours not peak), daily (that is, Monday, Friday against the weekend) or seasonally. Second, such DCA methods are not necessarily efficient from the point of view of channel allocation on a system-wide basis. Provided with a first estimate value, perhaps from a characteristic frequency reuse configuration, a DCA method is used for the "fine tuning" of the system. To the extent that the original estimating value does not efficiently allocate channels, the ACD will not usually improve the allocation efficiency due to its local rather than global approach. Thus, it would be advantageous to have a channel assignment method that is efficient irrespective of the extent of alterations of the system and that does not depend on the efficiency of an estimate value of the initial channel allocation. BRIEF DESCRIPTION OF THE INVENTION In accordance with an illustrative embodiment of the present invention, a method is provided for putting into operation a wireless telecommunications system by which the communication channels are efficiently allocated to the cells of the system. It is implicit in the procedure to assign channels that no mutually "interfering" cells (more appropriately, base stations) use the same channel (that is, frequency). In a first embodiment, the present method is applied to a situation where only those cells that are adjacent or "closer" to each other are considered to be interfering cells. In a second mode, the present method is applied to a situation where it is considered that the cells nearby and "near to the near" are interfering. Unlike many conventional DCA mapping methods, the present invention provides a way to allocate channels at a minimum determinable efficiency. More particularly, when the present method is used, an upper limit on the number of channels required to satisfy the call demand of the entire system can be determined. The channel allocation efficiency is greater than that of the conventional DCA allocation methods. This is because instead of updating the allocation based on: (1) local changes and (2) a first, perhaps inefficient, channel allocation, the present method provides an allocation based on the channel demand in each cell of the wireless system. The efficiency of the present method does not depend on the normally low efficiency of a first estimate value of channel assignment. According to an illustrative embodiment of the present method, call demand information is obtained for each cell in the wireless system and is converted to a channel demand. Once the channel demand for each cell is known, an "interference graph" that relates to the interfering cells with each other is defined. When considering the interference of the nearest cell, an initial stage is carried out where three channels are assigned iteratively to all the cells in the system to "remove" all the groupings within the interference graph that comprise three cells mutually interfering ("triangles"). During the initial stage, the allocation or determination of the three channels reduces the channel demand by one in each cell. Once the interference graph is "free of triangles" the channel demand is reduced more efficiently (two demand units per allocation of no more than five channels). To do this, the interference graph is "decomposed" by "removing" discrete portions of the graph, which are characterized as "ears" or "strings" depending on the manner in which such portions are linked to other portions of the graph . The decomposition process continues until a single basic cycle remains. A maximum of five channels are assigned to the base cycle to reduce the channel demand of each cell in the same by two units. After the assignment of channels to the base cycle, the last portion of the interference graph that was "withdrawn" during the decomposition process is "added back" to the base cycle. The same five channels (at most are allocated to satisfy two units of channel demand in each cell in the aggregate portion.) After assigning channels to the aggregate portion, the portion next to the last one of the interference graph that was removed during the decomposition is again added or added and the same five channels (maximum) are assigned to satisfy two units of channel demand in the cells in the same.The iteration is continued, from portion to portion until the five channels have been assigned as necessary to each cell that has unsatisfied demand on each "ear" or "string" on the interference chart Additional iterations of the five-channel assignment operation described above are carried out, as required, for satisfy the full channel demand in the system The operation of allocating channels to the cells when considering the cell interference closest and closest to the The closest one is analogous to the operation described in the previous paragraph. In particular, the interference graph is decomposed by "removing" a single cell at a time (instead of groups of them that define chains or ears). The decomposition process continues until only one cell remains. That cell is assigned to the lowest available index channels, as required to satisfy the full channel demand of the cells. After the channels are assigned to the remaining cell, the last cell removed during the decomposition process is added back or added to the final remaining cell and the next lowest available index channels are assigned to it. The operation continues until all the cells have been added again and the channels are assigned to it in sufficient numbers to satisfy the full channel demand for each cell. The call demand information can be obtained as frequently as desired to update the channel allocation throughout the wireless system. In some embodiments, the channel assignment method described herein may be used only to assign channels. In other embodiments, the present method for channel allocation may be used on an hourly, daily or temporary basis, as appropriate, to provide a channel allocation that is then updated on a substantially continuous basis by any conventional DCA scheme. .

BRIEF DESCRIPTION OF THE DRAWINGS Figure 1 illustrates a schematic diagram of a wireless communication system of the prior art. Figure 2a illustrates a method for putting into operation a wireless telecommunications system in accordance with an illustrative embodiment of the present invention.

Figure 2b illustrates a method for channel allocation when considering the interference of the nearest cell. Figure 2c illustrates the steps in one of the operations of the method of Figure 2b. Figure 2d illustrates a method for channel allocation when considering the interference of the nearest and closest to the closest cell. Figure 3 illustrates a wireless telecommunications system and the assignment of three communication channels to the cells therein. Figure 4 illustrates cells in a wireless telecommunications system having a non-zero channel demand and an interference graph defined by such cells. Figure 5 illustrates a cycle of an interference graph where five channels are allocated to satisfy a channel demand of two. Figure 6 illustrates groups of three elements of the interference graph of Figure 4. Figure 7 illustrates the allocation of three channels to satisfy a channel demand of one on the interference graph of Figure 4.

Figure 8 illustrates the allocation of six channels to satisfy a channel demand of two on the interference graph of Figure 4. Figure 9 illustrates the interference graph of Figure 4 after groups of three elements are removed in accordance with the teachings of the present. Fig. 10a illustrates a cycle of the interference graph of Fig. 4 after two channel call units is satisfied. FIGS. 10B-10F illustrate the allocation of five channels to the cells in the cycle of FIG. 10a to satisfy two channel demand units. Figure Ia illustrates additional cells comprising an "ear" attached to the cycle of Figure 10a. Figures 11b-llf illustrate the allocation of five channels to the ear cells of figure Ilia to satisfy two channel demand units. Figure 12a illustrates additional cells comprising a "chain" attached to the cycle of Figure 10a. Figures 12b-12e illustrate the allocation of four channels to the cells of the chain of Figure 12a to satisfy two channel demand units. Figure 13a illustrates cells in an illustrative wireless telecommunications system.

Figure 13b illustrates a channel demand in each cell of the wireless telecommunications system of Figure 13a. Figure 13c illustrates an interference chart defined by the cells of the wireless telecommunications system of Figure 13a, when it is considered that interference occurs between adjacent and adjacent cells. Figure 14a illustrates a border of the interference graph of Figure 13c. Figure 14b illustrates a border of the interference graph of Figure 13c after a vertex is removed. Figure 15a illustrates a channel assignment for the final cell and the first five cells to be added again according to a channel assignment operation according to the teachings present. Figure 15b illustrates the channel assignment shown in Figure 15a for the sixth cell to be added again. Figure 15c illustrates a channel allocation according to the teachings herein for all cells in the wireless communication system of Figure 13a. DETAILED DESCRIPTION In accordance with an illustrative embodiment of the present invention, there is provided a method for operating a wireless telecommunications system wherein the communication channels are efficiently allocated between the cells of the system. In a first operation 202 of the illustrative method 200a (Figure 2a) according to the teachings present, a channel demand is determined for each cell in a wireless system. Such channel demand is determined based on a call or traffic demand prevailing in each cell according to known methods. See, for example, the U.S. patent application serial number filed on the same date with the present "Wireless Telecommunications System and Method for Designing Same", proxy case number: Khanna 2-5, incorporated herein by reference . Based on the channel demand in each cell, specific channels are tentatively assigned to each cell in operation 204. In an embodiment of illustrative method 200a, the tentative channel assignments determined in operation 204 are implemented in operation 206 in accordance with known methods. The call demand information can be obtained as frequently as desired to update the channel allocation throughout the wireless system. In a second embodiment of the illustrative method 200a, the tentative channel assignments determined in step 204 are obtained according to a program or time schedule (eg, per hour, daily etc.) which is designed to capture substantial changes in the call demand. Then such channel assignments are used as the basis for a conventional DCA routine that updates the channel assignments on a substantially continuous basis, as indicated in step 205. Accordingly, the conventional DCA routine does not process large oscillations or amplitudes in the demand for calls that are manipulated instead by the present method of channel allocation. Such a procedure would result in a more efficient channel allocation. The channel assignment operation as practiced in accordance with the teachings herein is based on a wireless telecommunications system having a plurality of cells arranged in the usual hexagonal grid topology illustrated in Figure 1. Any Channel assignment between cells in a system should not assign the same frequencies to a pair of interfering cells (more appropriately base stations). For the purposes of this specification, it is considered that two cells "interfere" if they are close enough to interfere with each other when they use the same carrier frequency (ie, channel) for wireless communication. In a first embodiment, described in section I below herein, the channels are assigned assuming that only a second mode, described in section II hereinafter, the channels are assigned assuming that the cells closest and closest to the closer interfere.

Section I-Channel assignment for the interference of the nearest cell. Figure 3 illustrates cells 3-i, i, n arranged in the usual hexagonal topology comprising a portion of a wireless telecommunications system 300. Figure 3 shows that when only the closest cells interfere, three channels A, B and C (that is, carrier frequencies) must be used to satisfy a "unit" of channel demand in each cell 3-i in such a way that none of two interfering cells are assigned to the same channel. The channel assignment illustrated in Figure 3 is arbitrary; it will be appreciated that several other assignments are possible. Figure 4 illustrates cells 3-1 to 3-23 of the illustrative wireless telecommunications system 302. Cells 3-1 to 3-23 have a non-zero channel demand DI to D23 respectively. Unlabeled cells have zero channel demand and are ignored when the present method is applied. Three "groups" ("triangles") formed in a triangular manner T1, T2 and T3 are presented in an "interference graph" 402 of the system 302. An "interference graph" is defined by placing a "point" in the center of each cell that has a non-zero channel demand and then by joining such centrally located points of the interfering cells. The term "group" refers to a group of mutually interfering cells. For the case of interference from the nearest cell the group size is a maximum of three (that is, no more than three cells can mutually interfere with each other) and such groups of three elements are formed triangularly. Thus, triangles T1, T2 and T3 are groups that have three elements. All other groups show an interference graph 402 that has two elements. For example, cells 3-4 and 3-5 form a group of two elements, such as cells 3-4 and 3-3. Cells 3-3, 3-4 and 3-5 do not form a single group of three elements because, for the present case of interference from the nearest cell, cells 3-4 and 3-6 do not interfere with each other. It will be appreciated that in a typical wireless telecommunications system, there will be many such groups. It has been found that a maximum of five communication channels are required to satisfy a channel demand of two, in the whole system, for "triangle-free" interference graphics. In other words, given an arbitrary cycle having a maximum group size of two, such as cycle 501 illustrated in Figure 5, a maximum of five channels is used in the cycle to reduce the channel demand in each cell by two. while the same channel is not assigned to two interfering cells. When using cycle 501 as an example, channels A-6 are assigned, two to each cell, in such a way that no interfering (ie, adjacent) cells are assigned to the same channels. A methodology for such an assignment is described later in this specification. Thus, while three channels must be allocated to satisfy a demand of one ("three-channel allocation operation") in groups of three elements, the allocation of a maximum of five channels satisfies a demand of two ("assignment operation"). five-channel ") in cycles that have a maximum group size of two. The allocation of five channels is clearly more efficient than the allocation of three channels, but they can not be used if groups of three elements are present. According to the present teachings, all groups of three elements are first "removed" from the interference graph of a system by using a three channel assignment operation and once removed, a five channel assignment operation is used to satisfy the demand of remaining channel. Thus, for interference from the nearest cell, the present method advantageously utilizes both of the three and five channel allocation operations, which results in a more efficient channel allocation than if the three channel allocation operation were used. alone. Figure 2b illustrates a flow diagram of a method 200b for channel allocation that considers only the interference of the closest cell. In operation 222, groups of three elements (that is, groups or triangles) of mutually interfering cells are "removed" from an interference graph of the system by iteratively assigning three channels, one to each cell in the interference graph, until the demand for channel in at least one of the cells in each triangle is completely satisfied. When the channel demand of a cell is completely satisfied, it "disappears" from the interference graph. Thus, at the completion of operation 222, no triangle remains in the interference graph. As an illustration of step 222, triangles T1-T3 of FIG. 4 are removed by assigning AC channels to all cells in the interference graph during a first iteration and DF channels to all of such cells during a second iteration as it is illustrated in figures 6-9. The triangles of the interference graph 402 shown in Figure 3 are illustrated alone, for clarity in Figure 6. For the present example, the following channel demands are assumed: Dll and D12 = 2, and the demand for all the others cells is 4. Thus, in a first iteration, the first three AC channels are assigned to all the cells as shown in figure 7. Such allocation is implemented in the manner illustrated in figure 3. As a result of such allocation, the Channel demand is reduced by one in each of the cells in the wireless system. Thus, at the end of the first iteration, the remaining unsatisfied channel demand in cells D12 and Dll in triangles T1-T3 is one. The result of a second iteration, where the next three DF channels are assigned to each cell in the system, is illustrated in Figure 8. When subsequent channels are selected for allocation, the lowest available channels (in numerical sequence) are selected. . For example, if the channels that have carrier frequencies of 1,025, 1,050, 1,075, 2,000, 2,025 and 2,050 MHz are available after the allocation of the first three channels, the channels that have the carrier frequencies of 1,025, 1,050 and 1,075 MHz should be assigned right away. The channel assignment is implemented as follows. The cells that were assigned to channel A during the first iteration are assigned to channel D during the second iteration. The cells that were assigned to channel B during the first iteration are assigned to channel E during the second iteration and the cells that were assigned to channel C during the first iteration are assigned to channel F during the second iteration. Again, the allocation of the three channels reduces the channel demand by one in each cell. Since the demand for channel without satisfying in cells D12 and Dll is one, that demand is fully satisfied by the second iteration. Thus, as a result of the assignment of DF channels during the second iteration, cells 3-12 and 3-11"fall" from the interference graph and triangles T1, T2 and T3 do the same, to result in the graph of free interference of triangles illustrated in figure 9. Note that if one or both of cells 3-12 and 3-11 had a channel demand greater than two, then additional iterations and additional channels (three for each iteration) would be required to fully satisfy your channel demand and remove the triangles from the interference graph.

In a second operation 224 of method 200b (FIG. 2b), the channel demand of the remaining cells (joined in a triangle-free interference graph) is met iteratively. The second operation 224 is carried out, in some embodiments, in accordance with the steps illustrated in Figure 2c. In step 232, the free interference graph of triangles is "decomposed" by removing portions thereof until a single "base" cycle remains such as cycle 501 shown in Figure 5 (although the number of cells and / or their relative positions may be different than in cycle 501). The decomposition process involves removing "chains" and "ears" from the interference chart. A "string" is a grouping of cells attached to the rest of an interference graph at an endpoint or endpoint (that is, a cell).

For example, in Figure 9, cells 3-1 through 3-7 define a string 902. Cell 3-7 is the endpoint at which string 902 is joined to the rest of interference graph 402. A " ear "is a grouping of cells joined to the rest of a graph in both of its extreme points (possibly to the same cell). For example, with reference again to Figure 9, cells 3-14 to 3-18 define an ear 904. Cells 3-14 and 3-18 are the end points of ear 904. After removing chain 902 and the ear 904 of the interference graph 402, only the base cycle 906 remains defined by cells 3-8, 3-9, 3-10, 3-13, 3-20, 3-19, 3-21 3- 22 and 3-23. In step 234, the channels are first assigned to the base cycle 906. Such channel assignment is illustrated sequentially in Figures 10a to lOf. The present description cnues with the assumption that a channel demand of two exists in each of the remaining cells (that is, in cycle 906, ear 904 and chain 902), remember that two demand units have already been satisfied during the assignment of AF channels during the removal of triangles T1-T3. It was previously described that once the interference graph is free of triangles in such a way that the remaining graph has a maximum group size of two, a maximum of five channels is used to satisfy a channel demand of two. In the present illustration, all triangles T1-T3 have been removed in such a way that now, in the second operation 224, the channel demand can be satisfied in a more efficient manner than during the first operation. In FIGS. 10a-lOf, the next 5 channels available in the spectrum band, which are assumed to be G-K channels, are allocated to satisfy the remaining channel demand of two for each cell. Figure 10a illustrates the channel assignments to the cells of the base cycle 906 after the first operation 222 is completed and before any remaining channel demand is satisfied during the second operation 224. Figure 10b illustrates the process of allocating the channel G to the base cycle 906. For the allocation process, a cell is chosen arbitrarily as the starting point. In Figure 10b, cell 3-13 is such a starting point. Thus, channel G is assigned to cell 3-13 and to each second cell after that in base cycle 906 unless this results in the assignment of channel G to adjacent cells. In particular, after cell 3-13, channel G is assigned to cell 3-19, 3-22 and 3-8. Channel G is not assigned to cell 3-10 which is the second cell after 3-8, because such assignment would conflict with the assignment of channel G to cell 3-13. As such, the G channel can not be assigned to any additional cells in the base cycle 906.

With reference to Figure 10c, channel H, the next channel in the channel sequence, is assigned to the cell next to cell 3-13, which is cell 3-20. In the present modality, it is considered that cell 3-13 is the cell that follows cell 3-13 since, when channel G was assigned, the assignment preceded in one direction on the hands of the clock. In another mode, the assignment proceeds in a counter-clockwise direction such that the allocation of channel H would begin with cell 3-10. Channel H is thus assigned to cell 3-20 and every second cell thereafter in base cycle 906 unless in doing so it results in the assignment of channel G to adjacent cells. Thus, channel H is assigned, as shown in Figure 10c, to cells 3-21, 3-23 and 3-9. Channel H can not be assigned to any other cell in cycle 906. Accordingly channel assignment continues with channel I, as illustrated in FIG. 10d. The channel assignment continues with the cell after 3-20, which, in the present mode, is cell 3-19. Channel I is thus assigned to cells 3-19, 3-23, 3-8 and 310. Figure 10 illustrates the assignment of channel J to cells 3-21, 3-23, 3-9 and 3-13. . Of the last five channels, channel K is assigned to cells 3-10 and 320, as illustrated in FIG. 10F. Thus, the channel demand of the cells in the base cycle 906 is completely satisfied with the allocation of four channels to each cell, where, within a given cell and the cells adjacent to it, there is no channel that is assigned more at once. According to step 236, the interference graph is gradually reassembled by adding again the ear or chain that was last removed and then the allocation of channels thereto, according to step 238. In the present example in Based on the interference graph 402 of FIG. 9, it is not critical which of the string 902 or the ear 904 is first removed or re-added again in the first place for the channel assignment. It must be recognized that such an example is greatly simplified for clarity and brevity. In a typical wireless communications system, there will be many more cells that have a channel demand than in the present example. Thus, the interference graph for such a system will be considerably more complex than in the example. Such a graph would normally have many spliced "ears" where separation or removal and gathering of such ears should proceed in a definite order. In the present example, it is assumed that the ear 904 is the last portion of the removed graph and therefore, is the first portion to be added again. The figures lia -llf illustrate the process of re-adding ear 904 and allocating channels thereto.

Figure Ia shows the ear 904"reconnected" to the base cycle 906 before the assignment of any additional channel. The two previously assigned channels (that is, during operation 222) to each cell on the ear 904 are indicated in figure a, along with the channel assignment of cells 3-19 and 3-13 of the base cycle 906. will appreciate that since cells 3-19 and 3-13 are adjacent to the respective endpoints or endpoints 3-18 and 3-14 of ear 904, the channel assignments in cells 3-19 and 3-13 determine the channel assignments within the ear 904. Note that the first iteration of the second operation 224 is not complete until two units (that is, channels) of demand are satisfied in the whole graph of complete interference (since it exists after the separation of triangles in operation 222). In other words, the channel allocation process to the ear 904 and subsequently the chain 902 are both included in the first iteration that begins with the assignment of GK channels to the 906 base cycle. Thus, the GK channels are assigned to the ear. 904 and the chain 902 after this. Figure 11b illustrates the assignment of the G-channel to the cells in the ear 904. Again, the channels are assigned in a clockwise manner at the beginning of the ear endpoint (ie, cell 3). -14) followed by cell 3-13. Note that such an assignment in the clockwise direction is not determined by the clockwise configuration adopted for the channel assignment in the base cycle 906; the choice of the allocation address is again arbitrary. Since channel G is assigned to cell 3-13 of base cycle 906, it can not be assigned to adjacent cell 3-14 in ear 904. Channel G is assigned instead to cell 3-15 and 3-17. Figure 11c illustrates the allocation of channel H to the cells in ear 904. Channel H is assigned to cell 3-14 and every second cell after that, such as cells 3-16 and 3-18. The allocation of channel I is shown in the figure lid. Channel I is assigned to cells 3-15 and 3-17. The figure ill illustrates the assignment of channel J. Since channel J can not be assigned to cell 3-14 since it was assigned to cell 3-13 in base cycle 906 and since the full channel demand of the cell 3-15 has been satisfied with the assignment of channel I (figure lid), channel J is assigned first to cell 3-16 and then to cell 3-18. Only one unit of channel demand without satisfying persists. That demand unit is satisfied by assigning channel K to cell 3-14, as shown in Figs. Having satisfied two channel demand units at the ear 904 by assigning five channels to the cells therein, the string 902 is "reattached" to the base cycle 906 and the G-K channels are assigned to it. Note that based on the original four channel demand in the cells comprising the base cycle 906 and the ear 904, which is reduced to two after the first operation 222, a single iteration during the operation 224 is sufficient to satisfy the full channel demand in both of such portions. Even if the full channel demand in the 906 base cycle or the 904 ear was not satisfied after the allocation of five channels to the cells in it, the present method for channel allocation continues with the meeting of the appropriate portion ( that is, the ear 904 or the chain 902 if the channels have already been assigned to the ear 904) and the allocation of channels thereto. For the present example where the interference graph at the beginning of the second operation 224 includes the base cycle 906, a single ear 904 and a single string 902, the first iteration of the second operation 224 ends after the same five channels (in this case GK channels) have been assigned, as necessary, to the cells in the base cycle 906, the ear 904 and the string 902. If the full demand has not been satisfied when the first iteration of the operation 904 is complete, then a second iteration is used, where the graph is decomposed to access the portion with the unmet demand and the next group of five channels are allocated as necessary, to satisfy the remaining demand.

Figure 12a shows the base cycle 906 and the ear 904 of the interference chart with its four channel demand units fully satisfied by the allocation of four channels. Figure 12a further illustrates the assembled string 902 and identifies the channels previously assigned to the cells therein. Two demand units remain unsatisfied or satisfied in the string 902. Since, as previously described, the first iteration is not yet complete, the G-K channels are available for allocation. Figure 12b illustrates the assignment of channel G to the chain 902. Again, channel assignment in a clockwise fashion, channel G is assigned to cell 3-6.3-4 and 3- 2. Channel G can not be assigned to cell 3-7 because channel G has previously been assigned to adjacent cell 3-8. As shown in Figure 12c channel H is assigned to cells 3-7,3-5,3-3 and 3-1. Channel I is assigned to cells 3-6, 3-4 and 3-2, as illustrated in Figure 12d. The remaining unchanged channel demand of a unit is satisfied by assigning channel J to cells 3-7,3-5,3-3 and 3-1, as illustrated in Fig. 12e. Note that the K channel was not assigned. In other words, only four channels were required to satisfy a channel demand of two in the 902 chain and certainly in any chain. In addition, while five channels are required to satisfy a channel demand of two in cycles having an odd number of cells, such as the 906 base cycle, only four channels are required to satisfy a channel demand of two in cycles that they have an even number of cells. Thus, the channel demand of the illustrative wireless telecommunications system 302 (Figure 4) is fully satisfied by the allocation of 11 channels throughout the system. Four channels are assigned to all cells in the system with the exception of cells 3-11 and 3-12. Only two channels are assigned to cells 3-11 and 3-12 because that is all that is required to satisfy their demand for channel two. The upper limit on the number of channels? D required to satisfy the call demand of the system based on the use of the method described above for the channel assignment is determined as follows. A channel demand is determined for each group in the interference graph by adding the channel demand for each cell in a given group. The highest channel demand of all groups determines a "maximum group demand"? D. When the mutually interfering cells are adjacent cells, as in the present mode, the upper limit as to the number of channels required to satisfy the call demand in the whole system is given by the expression:? D < 17/12? D. For the previous example, the maximum group demand is 10, which is the group demand of triangles TI and T3. Thus, the upper limit in terms of the channel requirement of the whole system predicted by the previous expression is (17/12) x 10 = 14.1 or 15 channels. The present method satisfies the demand with 11 channels. The above example demonstrates the manner in which the method 200a for putting into operation a wireless telecommunications system is implemented when channel allocation is carried out by considering only the interference of the closest (adjacent) cell. The implementation of method 200a for the interference of the closest and closest to the closest cell is described later in the present in section II.

Section II- channel assignment for the interference of the nearest and closest cell to the nearest one. As indicated above, in step 204 of the present method for operating a wireless telecommunications system, specific channels are tentatively assigned to each cell in the system. The operations used to allocate channels when interference from the closest to the closest cell is considered are analogous to those used to implement step 224 of the 200b method for interference from the closest cell. In particular, in operation 242 of method 200c (figure 2d), the interference graph is decomposed until only one cell remains. Recall that for the interference of the nearest cell, the decomposition operation ends when there is only one cycle remaining. In operation 224, the lowest available graduation channels are assigned to the only remaining cell as required to satisfy their channel demand. In operation 246, the cells are "added back", one at a time, in the reverse order in which they were removed during decomposition operation 242. As each cell is added again, the channels are assigned to satisfy the full channel demand of the cell, as indicated in step 248. The lowest available channels are allocated consistent with the neighboring channel assignments. The implementation of operation 204, according to method 200c, is demonstrated for the illustrative wireless telecommunications system 602 illustrated in Figure 13a. System 602 includes cells 6-1 to 6-12 that have the channel demands illustrated in Figure 13b. Figure 13c illustrates an interference graph 604 for system 602 based on the interference of the nearest and closest to the closest cell. The lines that join the cells next to the closest ones are curves for clarity. Figure 14 illustrates the boundary or polygonal cube 702a of interference graph 604. Cells 6-1, 6-5, 6-10.6-11, 6-12, 6-9, 6-4, 6-3 and 6-2 define the boundary 702a.

Cells 6-1, 6-10, 6-12, 6-9 and 6-4 are the "vertices" of polygonal boundary 702a that subtend respective internal angles? I,? 2,? 3,? 4, and? 5. In accordance with the present teachings, the interference graph 604 is iteratively decomposed by selecting the cell at the border that subtends the smallest internal angle and then upon removing that cell. The internal angle of each vertex of the boundary is measured according to known methods. With reference to Figure 14, cell 6-1 that subtends the internal angle i i equal to 60 ° is the cell boundary or vertex with the smallest internal angle. Figure 14b illustrates the border 702b of the interference graph for the wireless telecommunications system 602. Four vertices that include cells 6-10, 6-12, 6-4 and 6-2 subtend the same minimum angle of 120 °. In such a case, the selection of a cell for its separation or withdrawal is somewhat arbitrary, although the specific details of the resulting channel assignment and even the total number of channels allocated may finally vary with such selection. When presented with such a choice, it is generally preferable to select a cell belonging to the same group as those cells that have already been removed, if possible. Thus, either one of the cells 6-2 or 6-10 is removed in preference to cells 6-4 and 6-12. For the present example, cell 6-2 is removed. The decomposition operation 242 proceeds like this until only one cell remains. Table 1 below lists the cells of the system 602, in order of removal and the size of the internal angle subtended by them. Table 1 Separation order for system cells 602 Cell 6-12 is the final remaining cell. According to operation 244 of method 200c, the channels are assigned to cell 6-12 as required to satisfy their channel demand. As indicated in Figure 13b, the channel demand of cell 6-12 is 2. Thus, the two lowest graduation channels, which in the present example are channels A and B, are assigned to cell 6 -12. As indicated in step 246, the cells removed are added back in reverse order. As each cell is added back, the channels are assigned to it. The final cell removed during the decomposition operation was cell 6-9. Thus, according to operation 246, cell 6-9 is the first cell to be added again. Since cell 6-9 is adjacent to cell 6-12, the next two channels in sequence are assigned to cell 6-9 to satisfy their full channel demand of two.

The channel assignments for cells 6-12 and the first five cells that are to be added again are illustrated in figure 15. Note that the cells shown in figure 15a are elements of a group (that is, they are mutually interfering cells). As such, a given channel could not be assigned to more than one cell in the group. Since the channel demand of the group illustrated in Figures 15a is 2 + 2 + 1 + 2 + 2 + 3 = 12, a total of twelve channels A-L must be assigned to such cells to satisfy that demand. The next cell to be added back is cell 6-11. Since cell 6-11 does not interfere with cell 6-9 and 6-4, it is not an element of the group illustrated in Figure 15a. According to the method, cell 6-9 is assigned to the two lowest graduation channels available to satisfy its demand of two. Cell 6-11 is a neighbor next to the nearest cell 6-12. As such, they interfere. Therefore, channels A and B, which have been assigned to cell 6-12 can not be assigned to cell 6-11. The next lower channels are channels C and D. Cell 6-9 has been assigned to channels C and D. Since channels 6-11 and 6-9 are not the closest neighbors or closest to the nearest ones , they do not interfere. As such, channels C and D are assigned to cell 6-11. Operations 246 and 248 are repeated until all cells have been added back to the interference chart. The allocation of channels to all cells in system 602 is illustrated in Figure 15c. Thirteen A-M channels are assigned to satisfy the channel demand of the entire system. When the mutually interfering cells are adjacent cells and next to the adjacent one, as in the present modality, the upper limit in the number of channels required to satisfy the call demand of the whole system is given by the expression:? d <; 2.? D - dm? N, where d "an. is the minimum channel demand, per cell, of the entire system. For the previous example, the maximum group demand is 12 and the minimum channel demand is 1. Thus, the upper limit in terms of the channel requirement of the entire system predicted by the previous expression is [2 x (12)] - 1 = 24 channels. The present method satisfies the demand with thirteen channels. The above example demonstrates the manner in which the method 200a for putting into operation a wireless telecommunications system is implemented when the channel assignment is carried out by considering the interference of the nearest (adjacent) cell and next to the closest one . The details concerning the derivation of the present methods are not necessary for the understanding or use of the present invention and as such are not presented herein. Such details are provided in a document of the inventors entitled "On Wireless Spectrum Estimation and Generalized Graphing Coloring", presented at IEEE INFOCOM 98 March 29 - April 2, 1998 in San Francisco, CA (17th Annual Joint Conf. Of the IEEE Computer and Communications Society), incorporated herein by reference.

It will be understood that the embodiments described herein are illustrative only of the present invention. Other embodiments may be devised in the application of the teachings present by those skilled in the art without deviating from the scope and spirit of the invention. Accordingly, it is proposed that such other embodiments be included within the scope of the following claims and their equivalents. It is noted that, in relation to this date, the best method known to the applicant to carry out the aforementioned invention is that which is clear from the present description of the invention.

Claims (15)

1. Rei indications Having described the invention as above, the content is claimed as contained in the following: 1. A method for putting into operation a wireless telecommunications system, characterized in that it comprises the steps of: determining the channel demand for each cell in the system; determine a tentative channel assignment by iteratively assigning channels to each cell until the channel demand in each cell is satisfied; and assign channels to each cell according to the tentative channel assignment. The method according to claim 1, characterized in that the step of determining a tentative channel assignment further comprises the steps of: providing the tentative channel allocation to an operational dynamic channel allocation routine to provide a tentative channel assignment updated; obtain an updated channel demand for each cell in the system; and update the tentative channel assignment by using the dynamic channel allocation routine based on the updated channel demand and the tentative channel allocation. 3. The method according to claim 1, characterized in that the channel assignment is based on the adjacent cell interference and the step of determining a tentative channel assignment further comprises the steps of: defining a first interference pattern of the interfering cells; satisfying at least a portion of the channel demands on all the interfering cells by using a three-channel allocation operation, wherein, the three-channel allocation operation is continued until the channel demand in at least one cell in each group of three mutually interfering cells it is reduced to zero; satisfy the demand of remaining channel. The method according to claim 3, characterized in that the step of satisfying the remaining channel demand comprises using a five channel assignment operation. 5. The method according to claim 4, characterized in that the step of satisfying the remaining channel demand further comprises the steps of: defining a second interference graph from interfering cells that have non-zero channel demand after it is consumed the assignment operation of three channels; decompose the second interference graph by sequentially removing portions of it until there is a group of interfering cells that define a single cycle; assign channels to the individual cycle; reconstruct the second interference graph by gradually adding each portion removed from it in the reverse order of removal; and assigning channels to each added portion before the addition or aggregation of a next removed portion. The method according to claim 5, characterized in that the steps of channel assignment to the individual cycle and to each aggregate portion further comprises using the five-channel assignment operation. The method according to claim 1, characterized in that the channel assignment is based on the interference of the adjacent and adjacent cell to the adjacent one and the step of determining a tentative channel assignment further comprises the steps of: defining a first interference graph; decompose the first interference graph by sequentially removing cells from it until a single cell remains; assign one or more channels to the individual cell as required to satisfy the channel demand of the cell; reconstruct the first interference graph by gradually adding each cell removed from it in reverse order of removal; and assign channels to each added cell before the addition of a next removed cell. The method according to claim 7, characterized in that the step of defining a first interference graph further comprises the steps of: defining a polygonal boundary of the first interference graph, the polygonal boundary has a plurality of vertices each characterized by an internal angle, each vertex consists of a cell; determine a magnitude of the internal angle for each vertex and a minimum magnitude between all the magnitudes. The method according to claim 8, characterized in that the decomposition step comprises the steps of: (A) removing a cell characterized by an internal angle having the minimum magnitude; (B) define a revised polygonal boundary that does not include the removed cell; (C) determine a magnitude of the internal angle for each vertex at the revised polygonal boundary and a minimum magnitude between all the magnitudes; (D) repeat steps A to C until only one cell remains. The method according to claim 9, characterized in that the step of assigning channels to each aggregate cell further comprises the step of assigning to an aggregate cell the lowest index channels not assigned to any cells interfering with the aggregate cell. A method for putting into operation a wireless telecommunications system, wherein communication channels are assigned to cells within the system based on adjacent cell interference, characterized in that it comprises the steps of: determining the channel demand for each cell in the system; assign one or more channels to each cell as required to satisfy a channel demand for each cell, where the channels are assigned to: define a first interference graph from interfering cells; satisfy at least a portion of the channel demand in all the interfering cells by using a three-channel allocation operation where the three-channel allocation operation is continued until the channel demand in at least one cell in each group of three mutually interfering cells is reduced to zero; satisfy the remaining channel demand by using a five-channel allocation operation. The method according to claim 11, characterized in that the step of satisfying the remaining channel demand further comprises the steps of: defining a second interference graph from interfering cells that have non-zero channel demand after an operation Three-channel allocation is consummated; decompose the second interference graph by sequentially removing portions of it until there is only a group of interfering cells that define a single cycle; assign channels to the individual cycle when using the five-channel assignment operation; reconstruct the second interference graph by gradually adding each portion removed from it in the reverse order of removal; and assigning channels to each added portion before the addition of a next removed portion, wherein the channels are allocated when using the five-channel allocation operation. 13. A method for putting into operation a wireless telecommunications system, wherein the communication channels are assigned to the cells within the system based on the interference of the adjacent cell and adjacent to the adjacent one, characterized in that it comprises the steps of: determine the channel demand for each cell in the system; assign one or more channels to each cell as required to satisfy a channel demand for each cell, where the channels are assigned to: define an interference graph from the interfering cells; sequentially remove the cells from the interference graph until only one cell remains; where the sequence of removal is based on a geometric property of the interference graph; assign a lower index channel of one or more channels to the individual cell as required to satisfy a channel demand of the individual cell; sequentially reconstruct the interference graph by re-adding the cells removed in reverse order of their removal and assigning an acceptable lower index channel of one or more channels to each added cell before the addition of the next removed cell, where the The acceptability of the assigned channels is dependent on the previous assignment of the channels to the interfering cells. The method according to claim 13, characterized in that a border of the interference graph is defined from a portion of the interfering cells, at least some of which portion of interfering cells define vertices of the border, in where the geometric property is a magnitude of an internal angle subtended by each vertex. 15. The method according to claim 14, characterized in that a cell defining a vertex having a minimum magnitude between all the magnitudes is removed. SUMMARY OF THE INVENTION A method is described for putting into operation a wireless telecommunications system whereby the communication channels are efficiently allocated to cells of the system. According to an illustrative embodiment of the present method, the call demand information is obtained for each cell in the wireless system and is converted to a channel demand. Once the channel demand for each cell is known, a tentative channel assignment is carried out. The call demand information can be obtained as frequently as desired to update the channel allocation throughout the wireless system. In some embodiments, the method for channel assignment described herein can be used only to assign channels. In other embodiments, the present method of channel allocation may be used on an hourly, daily, or other temporary basis, as appropriate, to provide a channel allocation that is then updated on a substantially continuous basis by any allocation scheme of dynamic, conventional channel. To assign channels, an "interference graph" that relates the interfering cells to each other is defined. When considering the interference of the nearest cell, an initial stage is carried out where three channels are assigned iteratively to all the cells in the system to remove all groups or groupings within the interference graph that comprise three cells mutually interfering During the initial stage, the allocation of three channels reduces the channel demand by one in each cell. Once the interference graph is free from such groupings of three elements the channel demand is reduced more efficiently where no more than five channels are allocated to satisfy two channel demand units. To do this, a decomposition / reconstruction operation is carried out where the interference graph is segregated or divided into groups or groups of cells to which the channels are assigned. The operation to assign channels to the cells when considering the interference of the nearest and closest cell does not use the initial stage of assigning three channels. However, it proceeds analogously to the decomposition / reconstruction process mentioned above, although the operation is carried out on a cell-by-cell basis, rather than with groupings of cells.