Evolving algorithms for telecommunications network nodes by genetic programming

<u>Field of the Invention</u>

The present invention relates to telecommunications, in particular to telecommunications networks.

<u>Description of the Related Art</u>

Telecommunications networks increasingly incorporate abilities to self-configure, self-organise and self-adapt. As the size and complexity of telecommunications networks increases, there is a drive to implement these so-called "self-x" properties in a decentralised manner, namely where each node can act individually using only local information.

Accordingly, there is a growing need to develop self-x algorithms, i.e. algorithms for network node self-adaptation, that have to work without global information about the network nor coordinated central control of the network nodes. Some examples of self-x algorithms in wireless networks include algorithms for optimising cell coverage and capacity, and resource scheduling algorithms. Some examples in the field of wireline networks are routing algorithms that operate dependent upon a variety of variables, such as traffic load level, number of hops between nodes along communication paths, and Quality of Service (QoS) requirements.

A known approach is for self-x algorithms to be designed by skilled engineers. based on specific assumptions about the network that may not be realistic, so there is often a need for the algorithms to be evaluated, revised and refined after they have been implemented in networks. This can be a slow and expensive process.

In this known approach, it is difficult for the skilled engineer designing algorithms that take account of the various different environments that the nodes will be deployed in. The algorithms are designed based on specific assumptions about the network that do not hold true in the real world.

In this known approach, a self-x algorithm is designed manually and then the same algorithm is applied across all of the network nodes of a certain type, for example all of the base stations in a wireless cellular network. As there are large differences in operating environments of the nodes, performance is degraded because generally-applicable optimisation algorithms perform less well than algorithms that are more specialised to a particular problem or operating environment. By the way, conversely, specialised algorithms perform less well when applied outside the particular area to which they are specialised.

Referring to another area of background, genetic programming is a known evolutionary approach to generating an algorithm, see for example <nplcit id="ncit0001" npl-type="b"><text>Koza, J.R., Genetic Programming: On the Programming of Computers by Means of Natural Selection 1992: MIT Press, 840</text></nplcit>.

Genetic programming is described briefly here to ease the understanding of the reader.

As shown in <figref idref="f0001">Figure 1</figref>, genetic programming (GP) involves the following steps: <ol id="ol0001" compact="compact" ol-style=""><li>(i) Initialise a population of algorithms- a population is the term used for a collection of individual algorithms, the algorithms in the initial population being generated at least somewhat randomly;</li><li>(ii) Calculate the fitness of each of the algorithms in the population - fitness being the term used for a measure of the algorithms performance in achieving the task of the algorithm;</li><li>(iii) Select algorithms to become "parents" based on their fitness;</li><li>(iv) Create new algorithms by applying genetic operators, such as mutation and crossover to the parents selected in the previous step;</li><li>(v) Produce the next generation population of algorithms using newly created algorithms and survivors chosen from the previous generation population.</li></ol>

The above steps (ii) to (v) are repeated until a termination condition is met (for example the process has gone through a set number of generations, or a target fitness level is met by an algorithm that has been created).

As shown in <figref idref="f0001">Figure 2</figref>, a parse tree representation is typically used in genetic programming (GP) in order to encode an algorithm into a form upon which genetic programming operations can be performed. The parse tree can be used to represent various forms of algorithms, such as computer programs. Algorithms can be represented in other forms, such as by state transition diagrams.

<figref idref="f0002">Figure 3</figref> shows illustrative examples of the crossover and mutation operators mentioned above. Crossover is mixing components from two parent algorithms to produce a next generation (i.e child) algorithm. Mutation is modifying part of an individual parent algorithm to produce a next generation algorithm.

Use of genetic programming to generate an algorithm for use in a telecommunications network is described in a paper by <nplcit id="ncit0002" npl-type="s"><text>Lewis T., Fanning N. and Clemo G. entitled "Enhancing IEEE802.11 DCF using Genetic Programming", IEEE 2006</text></nplcit>.

<u>Summary</u>

The reader is referred to the appended independent claims. Some preferred features are laid out in the dependent claims.

An example of the present invention is a method of evolving algorithms for network node control in a telecommunications network node by updating a model of the network node, and genetic programming by the steps of (a) generating algorithms, (b) determining fitness level of the algorithms based on the model of the network node, and (c) selecting the algorithm that meet a predetermined fitness level. The steps (a), (b) and (c) are repeated automatically to provide a series of algorithms over time adapted to the changing model of the network node for possible implementation in the network node.

In preferred embodiments, information of the status of the network node is obtained from local measurements, for example made by the node, and/or is provided as information from neighbouring nodes.

In preferred embodiments, each network node uses genetic programming to generate new algorithms for its own use, and information of the network is used to update an internal model of the network node. Preferably, the node uses that model along with genetic programming building blocks to create algorithms that meet a target criterion such as of fitness level. Preferably once such an algorithm is provided, it is tested and if deemed acceptable is implemented in the network node.

In consequence a preferred embodiment may be a network in which each network node runs its own distinct algorithms. The approach allows the nodes to adapt their behaviour flexibly, independently and intelligently.

This approach is suitable to various types of network nodes, for example network nodes that are self-adapting, for example femtocell base stations. The approach is suitable for providing algorithms for implementation that are themselves self-adapting algorithms.

Preferred embodiments relate to networks of cellular radio base stations. Other preferred embodiments relate to other types of telecommunications networks.

Preferred embodiments provide for the creation and adaptation of algorithms locally specialised to network nodes in a distributed manner. Preferred embodiments create and optimise the functional form of algorithms in an autonomous and efficient manner for good network performance.

In some preferred embodiments, steps of providing, verifying and implementing algorithms are repeated from time to time, such as periodically. In some preferred embodiments, the series of algorithms provided are a series of algorithms for network node self-configuring.

<u>Brief Description of the Drawings</u>

Embodiments of the present invention will now be described by way of example and with reference to the drawings, in which: <ul id="ul0001" list-style="none" compact="compact"><li><figref idref="f0001">Figure 1</figref> is a diagram illustrating schematically a genetic programming process (PRIOR ART),</li><li><figref idref="f0001">Figure 2</figref> is a diagram illustrating a computer program represented in the form of a parse tree (PRIOR ART),</li><li><figref idref="f0002">Figure 3</figref> is a diagram illustrating crossover and mutation operations applied in genetic programming to program portions represented as parse trees (PRIOR ART),</li><li><figref idref="f0003">Figure 4</figref> is a schematic representation of a network for wireless telecommunications according to a first embodiment of the invention,</li><li><figref idref="f0004">Figure 5</figref> is a diagram illustrating in more detail one of the base stations shown in <figref idref="f0003">Figure 4</figref> plus one of its neighbouring base stations,</li><li><figref idref="f0005">Figure 6</figref> is a flow chart illustrating operation of the genetic programming unit if the base station shown in <figref idref="f0004">Figure 5</figref>,</li><li><figref idref="f0006">Figure 7</figref> is a diagram illustrating how an algorithm verified and implemented in one base station becomes a candidate algorithm in a neighbouring base station, and</li><li><figref idref="f0007">Figure 8</figref> is an example genetically engineered program for optimising radio cell coverage provided by the genetic programming unit.</li></ul>

<u>Detailed Description</u>

The inventors realised that, in known wireless networks, use of a large number of user-deployed small cells would allow high data rates and provide high capacity. Such small cells typically have a range of tens or hundreds of metres, and are often referred to as femtocells. However, the inventors realised that a side-effect of using such a large number of small cells is the diversity of environments which the base stations providing those cells would experience. For example, the performance of a femtocell base station can vary drastically dependent upon where the femtocell base station is placed within a building. This is due in part to the effects of various building materials. For example, a glass wall has a very low propagation loss compared to a concrete wall. This is also due in part to the high variability of traffic demand. For example a femtocell base station covering a traffic demand hotspot such as a busy lounge will experience demands that are very different to another femtocell base station covering a quiet area that is, say, twenty metres away.

The inventors also realised that in small cells of this type, the self-x algorithms used to control and optimise base stations must deliver the appropriate performance in diverse environments, such that general purpose algorithms may not be adequate and algorithms are better specialised to particular environments. As an example, a femtocell operating in a residential area having buildings made of concrete may need a radio coverage control algorithm that is of a different form to one operating in a residential area with glass-fronted buildings. However, the inventors realised that the prior art approach of manually designing new algorithms for each different type of environment is impractical due to the complexity and costs involved.

An example network and network node will now be described, before focussing in on an example genetic programming unit and its operation. In this example, the network node is a femtocell base station.

After that, we will describe how a verified algorithm is disseminated to other nodes, before giving a particular example of the type of algorithm. This is followed by a description of some variants and alternatives.

In this description we used the term algorithm to mean a set of rules or a method that is used to solve a problem or perform a task. An algorithm may be specified in the form of a mathematical formula having technical application, a computer program, a representation of a system's behaviour such as a state transition diagram or flowchart. Examples of algorithms in telecommunications network nodes are a method to automatically adjust the coverage area of a radio cell, and a method of routing traffic through a network router node.

Network

As shown in <figref idref="f0003">Figure 4</figref>, the telecommunications network 2 includes a radio access network 4 which includes some interconnected cellular base stations 21,22,23,24. The base stations 21,22,23,24 all run respective algorithms to perform a predetermined task.

As shown in <figref idref="f0004">Figure 5</figref>, each of the base stations includes a respective genetic programming unit 10 that is used to provide new improved versions of the algorithm using genetic programming, as explained in more detail below. Each of the base stations is operative to communicate with and sense its neighbouring base stations. For example a first base station 21 is operative to communicate with and sense its neighbouring base stations 22,23,24.

To avoid confusion, we shall refer to the particular base station being considered as the "local" base station 9, which has a group (denoted 25) of neighbouring base stations. Which base stations belong to the group 25 depends on how the local base station 9 has discovered it neighbours. In this example, the local base station 9 performs measurements of received pilot signals from other base stations so as to identify which of the base stations are in its group 25 of neighbours. In an alternative embodiment, the local base station performs a query-and-response procedure over the backhaul network in order to identify neighbours.

The base stations in the group 25 of neighbours are those that have a significant impact on the local base station, and vice versa. For example, increasing transmit power of base stations in the group 25 will increase interference to the local base station 10.

As will be explained in more detail below, the base stations 21,22,23,24,9,25 in the network 20 each run their own algorithms to perform certain tasks, such as adjusting the size of their radio coverage. The base stations also each run an algorithm adaptation process, using genetic programming, in order to periodically update and refme the exact functional forms of the algorithms that they run. Each base station refines their algorithms locally, so the end effect is that each base station runs their own respective algorithm optimised to suit their own local environment and so likely being unique.

Genetic programming unit

As shown in <figref idref="f0004">Figure 5</figref>, the genetic programming unit 10 that uses genetic programming to create algorithms used in the base stations includes a genetic processor 11, an algorithm implementation stage 12 and a local information gathering stage 13.

The genetic processor includes a function and terminal set 111, genetic operators 112 and a fitness function 113 as inputs to an evolution processor 15. The function and terminal set 111 are the building blocks of the algorithms. The genetic operators 112 are operations that manipulate existing algorithms to create new ones, and include operations such as mutation and crossover. The fitness function 113 is a function used to calculate the fitness, in other words performance of the algorithms. The fitness function 113 is predetermined based, for example, on network operator's requirements.

In use, the evolution processor 15 acts to run simulations of the network node using the information of the model 14 of the network node and various different generated algorithms and the performance results are used together with the fitness function 13 to calculate the fitness associated with each algorithm. An up-to-date model 14, of the network node is used in these simulations.

As will be explained in more detail below, new and improved algorithms to be used in the base station are generated on an automatic basis. A flowchart of the main steps taken in this automated process is shown in <figref idref="f0005">Figure 6</figref>.

As shown in <figref idref="f0005">Figure 6</figref>, in the genetic programming unit 10, a next generation algorithm is generated and evaluated (step A) as to fitness level. A determination is made (step B) as to whether a generated algorithm meets a predetermined fitness level. Upon the predetermined fitness level being met, the algorithm is deemed good enough for the algorithm verification process to be undertaken. As explained above, the algorithm verification processor 17 pre-tests (step C) the algorithm to check suitability for deployment in the network 2. A determination is then made (step D) as to whether the tests are failed or passed. If the tests are failed the algorithm is discarded (step E) and a return is made to the generation and fitness evaluation (step A). On the other hand, if the tests are passed, then the algorithm is implemented (step F) in the network node.

The steps A and B in <figref idref="f0005">Figure 6</figref> occur in the evolution processor 15 shown in <figref idref="f0004">Figure 5</figref>. The steps C, D, and E in <figref idref="f0005">Figure 6</figref> occur in the algorithm verification processor 17 shown in <figref idref="f0004">Figure 5</figref>. This is explained in more detail below.

Various components and aspects of the genetic programming unit 10 will now be described in more detail. In particular, the evolution processor, the model building processor, the algorithm verification processor and the algorithm implementation stage will now be described.

Evolution Processor

The function and terminal set 111, genetic operators 112, a fitness function 113 and the simulation results from model (simulator) 14 are input to an evolution processor 15. The evolution processor 15 undertakes genetic programming.

As previously described, genetic programming (GP) involves the following steps: <ol id="ol0002" compact="compact" ol-style=""><li>(i) Initialise a population of algorithms- a population is the term used for a collection of individual algorithms, the algorithms in the initial population being generated at least somewhat randomly;</li><li>(ii) Calculate the fitness of each of the algorithms in the population - fitness being the term used for a measure of the algorithms performance in achieving the task of the algorithm;</li><li>(iii) Select algorithms to become "parents" based on their fitness;</li><li>(iv) Create new algorithms by applying genetic operators, such as mutation and crossover to the parents selected in the previous step;</li><li>(v) Produce the next generation population of algorithms using newly created algorithms and survivors chosen from the previous generation population.</li></ol>

The above steps (ii) to (v) are repeated until a termination condition is met (for example a target fitness level is met by an algorithm that has been created).

It can be considered that the algorithm output from the evolution processor 15 is one that has been selected by the evolution process. This algorithm is output from the evolution processor 15 to an algorithm verification processor 17.

Model Building process

In the genetic programming unit 10, there is a model building processor 16 which acts on the model 14 of the network node to keep the model 14 up to date by making use of information on the status of neighbouring nodes 25, such as what algorithm they are currently using plus the traffic conditions that they are experiencing such as load, type of calls etc, and also of local information about the local base station 9 itself.

The local information about the local node 9 itself is gathered by a local information gathering processor 13 that uses various tools to obtain information on the local radio environment, such as measurement reports sent by user terminals, and measurements made by a built-in radio receiver (not shown). This processor 13 also collects internal information that is available, such as statistics regarding the local base station's traffic load. This processor 13 also disseminates relevant information about the local base station 9, such as transmit power and average load in terms of numbers of active users, to its neighbours 20.

Accordingly, the model building processor 16 incorporates significant changes that occur in the radio environment ad conditions applied to the base station so may have an impact on the algorithm evolution process, and also acts to refine the model 14 so as to improve its accuracy. Accordingly, the model changes by being updated from time to time, for example periodically. The model building processor 16 uses information on the network node that is obtained from the network node itself plus its neighbours.

Algorithm verification

The algorithm verification processor 17 pre-tests the selected algorithm to check suitability for deployment in the base station. The tests are done prior to deployment and are intended to ensure that the algorithm is well-behaved and will not cause unwanted behaviours to occur in the network. This testing is particularly important for self-x algorithms (i.e. self-configuring, self-organising etc) for decentralised control of network nodes, as undesirable and unexpected behaviour may occur. Such undesirable behaviours can cause inefficient operation of the network and in extreme cases can cause cascading failures throughout the network. It should be noted that adverse effects can occur generally in algorithms and are not a specific side effect of being generated by genetic programming.

The algorithm verification processor 17 performs an automated verification process. Although the selected algorithm from the evolution processor 15 was developed using simulated scenarios and an up-to-date model 14 of the base station in its local environment, the algorithm may have flaws causing undesirable outcomes in other scenarios. An example of such a flaw that is easy to detect is a divide-by-zero calculation. Accordingly this pre-testing is undertaken.

Once the algorithm has been pre-tested and deemed suitable, the algorithm is implemented in the network node.

Algorithm Implementation

The algorithm, now deemed suitable, is implemented in the network node by the algorithm implementation stage 12. This algorithm implementation stage 12 takes the algorithm in its parse tree form and translates that into software instructions that replace the previous algorithm used. In this example, the algorithm implementation stage 12 includes an algorithm reader (not shown) which translates and runs the algorithm directly from its parse tree form. In a similar embodiment (not shown) the parse tree is converted into software code (C++, Java) and then compiled.

Algorithm dissemination to other nodes

As shown in <figref idref="f0006">Figure 7</figref>, the verified algorithm is also sent by the algorithm implementation stage 12 to the neighbouring base stations 25(one of which denoted 21 is shown for simplicity) so as to be included in their evolution processes. Looking from the neighbours perspective, when the base station 21 receives this algorithm from one of its neighbours, the base station 21 inserts the algorithm as an individual in the current population of algorithms in the evolution process.

The algorithms disseminated to neighbouring algorithms in this way are not immediately used by the neighbours, but only included in the population of the next generation of algorithms to be further evolved. This is shown in <figref idref="f0006">Figure 7</figref> where, from the perspective of the local base station 9, a neighbouring base station 21 receives the new algorithm of the local base station 9. If this received algorithm happens to be the best algorithm amongst the population of base station 21 then the genetic processor 15, as part of its usual operation, starts using that algorithm in subsequent cycles of evolution.

By this step, good algorithms evolved and verified in one base station are spread to other base stations. This may improve the rate of convergence of the algorithm adaptation processes through the network, in what can be seen as a form of parallel computation where the search is being performed by a group of base stations rather than individually. The spread of an algorithm may be limited due to the diverse environments that the base stations experience. For example, a good algorithm for base stations in a dense urban environment would not necessarily work well in a suburban or rural environment.

Dissemination of algorithms as described above, happens both to and from base stations, for example a base station sends good algorithms to its neighbours and also receives good algorithms from them.

Example of type of algorithm :Optimising radio coverage

An example of a type of algorithm that would be subject to genetic programming and selection as explained above is one for optimising radio coverage of a cell in a wireless network, in other words automatically adjusting the radio coverage are of a base station based on measurements made in the network in the environment of the base station. An example of this type of algorithm is represented in <figref idref="f0007">Figure 8</figref> both in the form of a parse tree and as an equation. The equation is: <maths id="math0001" num=""><math display="inline"><msub><mi>R</mi><mrow><mi>t</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>=</mo><mfenced separators=""><msub><mi>R</mi><mi>t</mi></msub><mo>+</mo><mfrac><mn>1</mn><msub><mi>N</mi><mi>i</mi></msub></mfrac></mfenced><mo>×</mo><msub><mi>D</mi><mi>t</mi></msub></math><img file="EP2261841A1_D0001.tif" /></maths> where <i>D_t</i> denotes Number of calls dropped during timeslot t, <i>R_t</i> denotes Cell radius during timeslot t, and <i>N_¡</i> denotes Total number of increments performed.

Example function and terminal sets used as input to the evolution processor in this example are as follows: Function set F={+, -, *,/}, is composed of basic mathematical operations.

Terminal set T={<i>D_t</i>, <i>R_t, C_t, N_i,</i> 1}, is composed of measurements, node states, and constants as follows: <ul id="ul0002" list-style="none" compact="compact"><li><i>D_t</i> - Number of calls dropped during timeslot t.</li><li><i>R_t</i> - Cell radius during timeslot t.</li><li><i>C</i> - Coverage overlap.</li><li><i>N_i</i> - Total number of increments performed.</li></ul>

Some variants

Network nodes in a wireless cellular network have been referred to above, but the approach is applicable in other types of network nodes and networks. For example, algorithms specialised to particular nodes and their specific local environments, are also useful in Internet Protocol networks, for example where it is useful to support rerouting and reallocation of resources so as to maintain basically seamless mobility and Quality of Service (QoS) for mobile users. Examples include wireline access network nodes, such as Digital Subscriber Line (DSL) lines and residential gateways.

The approach above has been focussed on use of genetic programming to generate self-x, i.e. self-configuring, self-adapting algorithms. In some other embodiments, the approach is used to provide algorithms for implementation that are not self-x algorithms.

The present invention may be embodied in other specific forms without departing from its essential characteristics. The described embodiments are to be considered in all respects only as illustrative and not restrictive. The scope of the invention is, therefore, indicated by the appended claims rather than by the foregoing description. All changes that come within the meaning and range of equivalency of the claims are to be embraced within their scope.

A person skilled in the art would readily recognize that steps of various above-described methods can be performed by programmed computers. Some embodiments relate to program storage devices, e.g., digital data storage media, which are machine or computer readable and encode machine-executable or computer-executable programs of instructions, wherein said instructions perform some or all of the steps of said above-described methods. The program storage devices may be, e.g., digital memories, magnetic storage media such as a magnetic disks and magnetic tapes, hard drives, or optically readable digital data storage media. Some embodiments involve computers programmed to perform said steps of the above-described methods.