Title of Invention

A PROCESS AND A NETWORK FOR CHANNEL ALLOCATION

Abstract

A channel allocation process for a cellular telephone network (99) starts from a position of homogeneity (phase 100) in which each base station has the potential to use all channels, and develops ever greater heterogeneities by processing a combination of short and medium range interactions between the base stations themselves (phase 200), causing each base station of the cellular telephone network to inhibit its neighbours from using a given channel, to generate (step 203) a usage factor for each channel in each cell indicative of the level of interference to be expected on that channel in that cell. Channels can then be allocated to each base station according to the ranking of the usage factors determined for the channels at that base station (phase 300). The entire network may be emulated by a single processing means, controlling the base stations of the network (99) in accordance with the results of the process. Alternatively, each base station of the network (99) performs that part of the process relating to itself, in cooperation with its neighbours, and utilises channels in accordance with the results.

Full Text

CHANNEL ALLOCATION IN CELLULAR TELEPHONY This invention relates :o channel aliocation in cellular telephony, and in particular to a method for dynamically allocating channels to cells according to demand. A cellular telephone network consists of a number of fixed base station transceivers and a much larger number of mobile handsets which communicate with base stations via a radio channel. The number of radio channels which the operator is permitted to use is limited, and there are not enough for each phone call in the network to be carried on a different channel. Thus a central principle of such networks is channel reuse (Lee, W. C. Y. : Mobile Cellular Telecommunications Systems. McGraw-Hill Book Company, New York, 1989': at any time many base stations may be transceiving on each channeL. This introduces the possibility of interference between phone calls. Interference from other calls using the same channel is known as 'co-channel interference'. 'Adjacent channel' interference, due to another call using a different channel, 'S also a problem: a calL made on a channei c_orresponding to a frequency band of 4000 - 4025 kHz is liable to interference from a call on the adjacent band; 4025 -4050 kHz. Adjacent channel interference can occur between two calls in the same cell, as well as between adjacent cells. The 'cells' from which these cellular telephone networks get their name are the coverage areas of the individual fixed radio base stations (Figure 2). The problem facing the network operator is to allocate channels to base stations such that demand for channels across the network is met, while keeping interference within acceptable levels. These aims are clearly in conflict: the more channels allocatec to each base station the harder it is to plan the channel reuse to avoid unacceptable interference. An added difficulty is that the demand across the network is neither uniform nor static. Some cells wiil experience high demand at particular times of the day but lower than average demand for the rest of the day, for example cells containing major arteries of commuter traffic. Even worse, for efficient channel allocation, are the unpredictable fluctuations in demand resulting from events such as road accicents. it is currently common practice for operators to use a fixed channel' allocation plan. The channeis used by any particular base station are determined by a "frecuency plan". This plan is only modified every few months if necessary tc meet quality of service criteria, for example to meet changes in demand, and tc allow for tne instailation of new base stations. During the existence of one frequency plan, each base station has its own allocation of channels,, vvhicn remains the same throughout the life of the plan. New base station technology, allowing speedy changes in channel use by base stations, :s making the idea of dynamic channel allocation planning more attractive ^Akaiwa, Y. and Andoh, H.: Channel Segregation-A Self-Organized Dynamic Channel Allocation Method: Application To TDMA/FDMA Microcellular System. IEEE Journal On Selected Areas In . Communications 11 (6) '1 993) 949-954). Dynamic planning ta; Producing an efficient cnannel allocation plan is not only an important part of running an efficient mobile network, it is a formidable abstract mathematical problem. If there are k available channels the number (23751)® - 6x10' different ways of assigning, to each cell, four of the twenty-nine available cnannels. Clearly an exhaustive search of solution space is not an appropriate method for optimising such a problem. Various processes have been acplied to this problem including; 'subspace approach' (Lochtie, G. D. and Mehier, M. J.: Subspace Approach To Channel Assignment In Mobile Communications. lEE Proceedings Communications 142 (3) (1995) 179-185), "simulated annealing" (Aarts, E. and Korst, J.: Simulated Annealing and Boltzmann Machines. Wijey (1989) and "neural networks" (Kunz, D.: Channel Assignment For Cellular Radio Using Neural Networks. IEEE Transactions on vehicular Technology 40(1) (1991) 188-193). Lochtie, G. D., van EijI, C. A. and Mehier, M.J. compare various methods in Comparison Of Energy Minimising Processs For Channel Assignment In Mobile Radio Networks: Proceedings of the 8th IEEE international Symposium on Personal Indoor and Mobile Radio Communications (PIMRC'97) 3 (1997) 786-790)). According to the present invention a channel allocation process is provided in which the process starts from a position of homogeneity in which ai! cells have the potential to use all channels, and develops ever greater heterogeneities which move it towards a solution by processing a combination of short and medium range interactions among the cells themselves, causing each cell (i.e. each base station) of the cellular telephone network to inhibit its neighbours from using a given channel, to generate a usage factor for each channel in each cell indicative of the level of interference to be expected on that channel in that cell. This process may be' carried out by 3 single processor emulating the network, which can, if the system is to be carried out in real time (dynamically), then transmit the results of the process to each base station, or it can be carried out by the individual base stations, each interacting with its neighbours, The process arrives at progressively better solutions by a process of mutual inhibition between cells. Nc global information is available to these cells and each must act on the bas:s of the inhibition it perceives from its neighbours. The process does not search solution space but instead moves through shades of grey towards a black and white solution (figure 2). Further aspects of the invention relate to a cellular telephone system having means for performing this process, and to a computer program product directly loadable into the interna! memory of a digital computer, said program product comprising software code portions for performing the process when said product is run en a computer, either to control a real network or as a planning too!. The invention also extends to a computer-usable carrier carrying computer-readable program means for performing the various steps of the process. The computer-readable program means may be embodied on any suitable carrier readable by a suitable computer input device, such as CD-ROM, optically readable marks, magnetic media, punched card, or on an electromagnetic or optical signal. An exemplary embodiment of the invention will now be described with reference to the drawings, in which : Figure 1 is a schematic diagram of the various functional elements of the process Figure 2A is a map of a cellular radio network covering part of the United Kingdom. Figures 2B, 2C, and 2D illustrate the allocation of channels to the cells of the network of Figure 2A, at successive stages of the process according to the invention, Figures 3, 4, 5 and 6 illustrate the behaviour of the network of Figure 2A when controlled by the process of the invention, in a typical situation. Figure 1 is a scherratic diagram illustrating the various functional' elements of the process. Ti-'.ese may be embodied as software on a general purpose computer. The process of producing a channel allocation plan begins with an initialisation pnase cf assembling the necessary information (phase 100). This is followed by a" terative progression from homogeneity towards a solution (phase 200). A solution can be extracted (phase 300) at any time but the quality of that solution improves as time goes on. In the initialisation chase (';00) an interference table is first provided (step 101). This is a/x/table (where / is the number of cells) which gives a value to the strength witn which each cell can cause interference in each other cell. Separate rabies may be used for co-channel interference and adjacent channel interference, but in both cases the full / x table is used. Thus if better data is available concerning the interference values between two cells it can be incorporated into the relevant table without changing the number of computations per iteration. The next step (102! is to obtain the demand for channels (i.e. the maximum number of simultaneous phone calls) which is to be met in each ceil. This information can be obtained from the network 99, or from a. theoretical or historical analysis, and can be changed as the process runs, allowing new solutions to be produced in response to unforeseen changes in demand. ■ A maximum value Nmax for the noise parameter N is also needed (step 103). This determines the size of the uniform random distribution from which the initial differences between cells and the perturbations, to which cells are subjected in every iteration, are taken. For the simulations used in the following examples, Nmax, is 1 % of the initial usage values unless otherwise stated. Lastly the 'initial usage' of each channel in each cell must be determined (step 104). The idea of 'usage' in this context is important and needs some explanation. Each cell is imagined, for the purposes of the process, to be partially using all channels. In any one cell the sum of all the partial usages is set equal to demand D in that cell. At the start of the simulation all cells have almost equai 'usage' of all channels but as time goes on cells 'use' some channels more than others, depending on the inhibition they experience from :heir neighbours, and from, adjacent channels in the same cell. This idea :f partial usage is purely a mechanism by which the process moves towards a solution - it would never itself be a valid solution to the channel allocation problem. The job of producing a valid solution from the current usage values fa,is to the 'solution extractor' (phase 300) to be discussed later. The iterative phase {200) involves calculating the new 'usage' of each channel in each cell based on the current 'usage', and on the inhibition perceived by that cel on. tne channel in question, Figure 1 illustrates this process for one channel in respect of one cell - in each iteration the process takes place in respect of al! cnannels in all cells. Inhibition /p, is the sum of all the usages of channel k by all cells other, than cell /, and of adjacent channels by ail cells (including cell j), multiplied by the appropriate interference table value between cell j and the other cell (step 201). (For adjacent channel interference, the interference factor is lower than for co-channel interference). The new usage value can then be calculated (steo 2021 using the formula; " (1+/,) Where: Uikl is usage cf channel k in cell/for iteration t 1ikl, is inhibition calculated for channel k in cell/ N is a noise parameter, randomly selected from the range +/- Max For iow values of lilk (implying low interference) it is possible for Upm to take a value greater than 1 if /V is large. For example, if U,.; = 0.99, N is + 1% of Ujkl; , and I, nas a value of 0.01, U, =1.01. Since actual usage cannot be greater than 1, and larger values couid propagate in subsequent iterations, so any value greater than 1 is set at 1. Finally iteration t increments to f+ /, (step 203) and the next iteration begins. This simulates syncnronous update of all cells. The strength of inhibition on different channels determines how the partial usages change from their initial values (determined in step 104) elative to each other. The important difference between partial usage and actual' usage is that all the channels are partially used in all cells while the terative process runs. 'Actual' usage of a channel only occurs when a solution is extracted (phase 300 below). At any time a simple filter program can be used to produce a valid real solution from the current usage values (phase 300). Channels are allocated to a cell in descending order of their simulated "partial" usage in that cell (step 301), until demand is met (step 302). Satisfying demand for channels is thus treated as a hard constraint. The solution is made up of use or non-use of each channel, in other words it can only produce values of usage of zero or unity, but the iterative process (phase 200) can produce any value between zero and unity. The solution generated (step 302) can then be fed back to control the network 99. If inhibition is high in some cells, the formula used above can converge on a non-idea! solution as very low usage values can be generated in those cells in which high inhibition values are experienced. This problem can be reduced .by making only a part of the usage value for each channel and cell available for change in each iteration. The formula then becomes: where P is the proportion of the usage value aviallable to be changed on a given iteration, and C is a normalisation constant, required to ensure the total usage is equal to the demand D. By reserving part of the usage value, C! - P) Ukl against change, the usgae value is prevented from changing in a single iteration be greater than the factor P. For example if a cell is using a channel with usage 0.3 a time t, then at time t = t+ 1 it cannot be given a usage value less than 0.45, even if ir experienced infinite inhibition from its neighbours. It wil! be seen that jf P = C = 1, this formula reduces to the one given earlier. The method c* the invention is well suited to online dynamic channel allocation. If demand changes in one or more cells, the process may be reinitialised (phase 10C and re-started. Alternatively, the usage values U generated in the most recent iteration may be adjusted by a factor D2/D, determined by the change in demand, and used as the basis for the next iteration (step 204 in Figure 1), For example, if demand halves in a cell, ail the usage factors for that celi are halved so that they total to the new demand value. This has the advantage that the ranking of channels will remain similar at the next iteration, which will ensure continuity of coverage for any calls in progress. Changing demand for channels can therefore be readily acconnmodateG and the channel allocation plan already in use can thus be altered to minimise the increase in interference resulting from use of the new channels. At periods of extreme demand a given channel may be identified as having a partial usage value high enough to form part of the extracted solution in two adjacent cells. In this case, both cells are nevertheless allocated that channel if the demand in both cells requires its use. Of course co-channel interference will result in such a case, but in general the process adjusts partial usages so that this is unlikely to occur in practice. The solution extractor pays no account of what neighbouring cells, or adjacent channels, are doing, tt simply ranks the partial usages of channels in descending order and then reads down the list, allocating every channel, until demand is met. This simulates allocation of channels to ail' cells in parallel. For example, as shown in the table below (for fifteen channels), cell B has a demand of 10 whereas cell A only has a demand of 3. Channel 1 has the tenth highest usage in cell 3 (0A) and the highest usage in cell A (0.9). The solution extractor will nevertheless allocate channel 1 to both ceils (allocations indicated by " - '). Cell A Cell B Total Demand 3.0 10,0 Channel Usage Usage 1 0,9- 0.40+ 2 0.1 0.71+ 3 0.1 0.92+ 4 - 0.2 0.934+ 5 0.1 0.94 + 6 0.1 0.95+ 7 0.1- 0.96 4 8 0.1 0.97-4 9 0.1 0.98- 1. 0.1 0,99-, 1 0.1 0.35 12 0.5- 0.30 13 0.1 0.25 14 0.3- 0.20 15 0.1 0.15 Figure 2A is a map of a fifty-eight cell mobile phone network in East Anglia, UK (redrawn from Lochtie and Mehler 1995, cited above). Figures 2B, 20, and 2D show channel usage and corresponding solutions at progressively later stages of optimisation. In each case the upper half of the Figure shows the simulated/partial usage of each of twenty-nine channels in each of the fifty-eight cells of the network (the darker the dot, the higher the usage). The lower half snows the solution which is extracted from this imulated usage. The solution is 'black and white' - a channel is either used" black) or not (white). Initially simulated usage is homogeneous and the olution is random (Figure 2B). As time goes on the simulated usage becomes more heterogeneous (figure 2C) and the extracted solution can be een to be drawn from the sinulated usage with few ambiguities (Figure 2D). The example ceiiular telephone network to which the process is applied is taken from Lochtie and Mehler (1995). It is a network in the East Anglian region of the United Kingdom, with fifty-eight base stations (figure 2) and twenty-nine radio channels available to be allocated to those base tations. Lochtie and Mehler report a subspace approach technique which allows a fixed, uniform demand for four channels in each cell to be successfully met without breaching their interference criteria. The same nterference criteria are used for the simulations reported below. These criteria are certainly an over-simplification. More subtle interference criteria cou!d be incorporated into the simulation without increasing the computation if the data were available. Lochtie and Mehler (1995) successfully produce a channel allocation plan with uniform demand for four channels. This plan gives zero interference according to their interference criteria, which are adopted herein, it is therefore of interest to see whether the process described here could also produce a zero jnterference plan if each cell demands 4 channels. Figure 3 shows the total interference in the network for simulations with various uniform levels of demand. Total network interference for the solution extracted at each iteration is shown. The key shows the number of channels used by each cell in the five simulations. In effect a solution has been extracted from the process after every iteration and the interference corresponding to that solution is plotted. In the case where uniform demand takes the value of 4 the process rapidly finds a zero interference solution. Indeed the process reproducibly finds zero-interference soiutions even when every cell demands seven channels. At demands of greater than seven channels, no zero-interference soiutions are found. However, tne process still produces a marked downward trend in the interference as iterations progress. Figure 4 illustrates the effect of the noise factor, using optimisation to a uniform demand value of 10 in every cell, with different maximum values chosen for the noise parameter. Once again the total network interference for the solution extracted at each iteration is shown. The key shows noise values as percentage of initial usage U The influence of the value of tne noise parameter on the behaviour of the process was tested by varying that parameter for successive optimisation runs. In each case the demand for channels was 10 in all cells to ensure that no zero-interference solution exists, thereby making this a meaningful test of optimisation behaviour. The results (figure 4) illustrate the dangers of low values for the noise parameter. When Nmax is set to 0.02% the process reaches an asymptote within forty iterations, but this asymptote is not the global minimum. With a Nmax value of 1% the process approaches an asymptote more slowly, (150 iterations) but that asymptote has a lower interference solution. A Nmax value of 10% is sufficient to almost completely destroy the downward trend achieved by the mutually inhibitory mechanisnrv. It results instead in a random search (and illustrates, in the process. thea search method). The results so far have been presented as total interference in the network. This is a good measure of the performance of the process because it shows to what degree the short range inhibition acting between cells, without any knowledge of the total interference for the whole network; is able to drive down the overall interference value. The success of the process In finding low interference plans arises from the purely selfish, shortsighted response of each cell to inhibition. However it is also important to measure the behaviour of the process at the level of individual cells, it is possible that a channel planning process could achieve an overall low interference in the network by producing a plan with zero interference in most cells but high interference in one cell. Figure 5 compares the trend in total network interference with the trend in the highest interference value found in any single cell. A plot of the highest interference in any single cell is shown with the single cell value multiplied by 58 for comparison with total interference. The interference experienced by individual cells falls off in much the same way as the overall interference in the network. The interference is apparently spread across many cells in the network rather than being concentrated in a few. Testing the process under conditions of uniform demand is useful in allowing comparison with earlier work and evaluation of basic behaviour of the process, it does rot, however, address the issue of dynamic, responsive :hannel allocation. A simulation of dynamic demand was created to see how well the process deals with non-uniform, changing patterns of demand, as shown in figure 6. In Figure 5 demand initially has a value of 6 in every ceil in the network and interference is successfully eliminated. At iteration 100 'rush hour' is simulated. At iteration 600 a road accident is simulated and traffic queues form in surrounding cells at iterations 800 and 1200. The simulation begins with uniform demand of 6 and a zero interference solution is found. Rush hour then begins in three of the large towns covered by the network: Ipswich (cells 52, 53 and 54 in figure 2], Great Yarmouth (cells 41, 42, 43, 45, 46), and Norwich (cells 35, 36, 37 spreading into cells 27, 3G and 31, resulting in demand rising to 10 in those cells. Eventually congestion spreads as far as cells 37, 38, 32 and 34. Finally the accident is cleared and demand in all cells returns to a value of 6. Total interference across the network during this scenario is shown in Figure 6. Each surge in demand results in an increase in interference as new channels are grabbed by the cells in question. Clearly the total interference in the network is far less than if ten channels were assigned to each cell (see figure 4). However, comparison with the steady-state allocation plan is not a good measure of the process's performance because other processes could be envisaged which would also outperform the sinnple policy of uniform allocation of 10 channels. For example, a process which, having established a zero-interference uniform six-channel plan, randomly assigns new channels to meet rising demand is plotted on Figure 6 for comparison. The self-organising process of the invention produces significantly better allocation plans than this 'random' process. WE CLAIM : 1. A channel allocation process for a cellular telephone network (99) in which the process starts from a position of homogeneity (100) in which each base station has the potential to use all channels, and develops ever greater heterogeneities by processing (200) a combination of short and medium range interactions between the base stations themselves, causing each base station of the cellular telephone network to inhibit its neighbours from using a given channel, to generate a usage factor Ujkt for each channel in each cell indicative of the level of interference to be expected on that channel in that cell. 2. A process according to claim 1, wherein channels are allocated to each base station according to the ranking of the usage factors determined for the channels at that base station. 3. A process according to claim 1 or 2, wherein the network is emulated by a processing means. 4. A process according to claim 3, wherein the processing means controls the base stations of the network. 5. A process according to claim 1 or 2, in which each base station of the network performs that part of the process relating to itself, in co-operation with its neighbours, and utilises channels in accordance with the results. 6. A cellular telephone network 99 comprising channel allocation means for allocating radio channels to base stations, the allocation means having means (100) for generating an initial homogeneous allocation in which each base station has the potential to use all channels, and means (200) to develop ever greater heterogeneities in the allocation plan by processing a combination of short and medium range interactions between the base stations themselves, causing each base station of the cellular telephone network to inhibit its neighbours from using a given channel, to generate a usage factor Uj^t for each channel in each cell indicative of the level of interference to be expected on that channel in that cell. 7. A cellular telephone network according to claim 6, having means for allocating channels to base stations by selecting those channels having the optimum usage factors, 8. A cellular telephone network according to claim 6 or 7, wherein each base station has means for generating its own channel allocation plan, in co-operation with neighbouring base stations, each base station having means to receive inhibition factors generated by neighbouring base stations, means to generate a usage factor for each channel based on the inhibition factors received from the other base stations, and means to generate inhibition factors for transmission to neighbouring base stations. 9. A channel allocation process for a cellular telephone network substantially as herein described with reference to the accompanying drawings.

Documents:

in-pct-2000-540-che-claims duplicate.pdf

in-pct-2000-540-che-claims original.pdf

in-pct-2000-540-che-correspondance others.pdf

in-pct-2000-540-che-correspondance po.pdf

in-pct-2000-540-che-description complete duplicate.pdf

in-pct-2000-540-che-description complete original.pdf

in-pct-2000-540-che-drawings.pdf

in-pct-2000-540-che-form 1.pdf

in-pct-2000-540-che-form 26.pdf

in-pct-2000-540-che-form 3.pdf

in-pct-2000-540-che-form 5.pdf

in-pct-2000-540-che-other documents.pdf

in-pct-2000-540-che-pct.pdf