Search

Evolutionary computation is used to automatically evolve small cell schedulers on a realistic simulation of a 4G-LTE heterogeneous cellular network. Evolved schedulers are then further augmented by human design to improve robustness. Extensive analysis of evolved solutions and their performance across a wide range of metrics reveals evolution has uncovered a new human-competitive scheduling technique which generalises well across cells of varying sizes. Furthermore, evolved methods are shown to conform to accepted scheduling frameworks without the evolutionary process being explicitly told the form of the desired solution. Evolved solutions are shown to out-perform a human-engineered state-of-the-art benchmark by up to 50%. Finally, the approach is shown to be flexible in that tailored algorithms can be evolved for specific scenarios and corner cases, allowing network operators to create unique algorithms for different deployments, and to postpone the need for costly hardware upgrades.

The scale at which the human race consumes data has increased exponentially in recent years. One key part in this increase has been the usage of smart phones and connected devices by the populous. Multi-level heterogeneous networks are the driving force behind this mobile revolution, but these are constrained with limited bandwidth and over-subscription. Scheduling users on these networks has become a growing issue. In recent years grammar-guided genetic programming (G3P) has shown its capability to evolve beyond human-competitive network schedulers. Despite the performance of the G3P schedulers, a large margin of improvement is demonstrated to still exist. In the pursuit of this goal we recently proposed a multi-level grammar approach to generating schedulers. The complexity of the grammar was increased at various stages during evolution, allowing for individuals to add more complex functions through variation operations. The goal is to evolve good quality solutions before allowing the population to specialise more as the grammar functionality increased in a layered learning way. In this paper the results of this initial study are replicated, and confirmed, and it is seen that this approach improves the quality of the evolved schedulers. However, despite the gain in performance, we notice that the proposed approach comes with an acute sensitivity to the generation at which the grammar complexity is increased. Therefore, we put forward a novel seeding strategy and show that the seeding strategy mitigates the shortcomings of the original approach. The use of the seeding strategy outperforms the original approach in all the studied cases, and thus yields a better overall performance than the state-of-the-art G3P generated schedulers.

Grammar-Guided Genetic Programming is already outperforming humans at creating efficient transmission schedulers for large heterogeneous communications networks. We have previously proposed a multi-level grammar approach which achieved significantly better results than the canonical Grammar-Guided Genetic Programming approach. Initially, a restricted ‘small’ grammar is utilised in order to discover suitable structures. A full grammar is then adopted after this initial phase. Hence, evolution can focus on maximising performance, by fine-tuning the well-structured models. In this work, we propose to use a hierarchical approach by employing multiple small grammars instead of a unique small grammar at the lower level, in conjunction with the full grammar at the upper level. To use multiple small grammars while maintaining the same computational budget, we have to use either (i) reduce the number of generations, or (ii) reduce the size of the population for the evolution with each of the small grammars. In this work, we confirm that the hierarchical grammar approach using the division of number of generations strategy achieves significantly better results than the multi-level approach, but requires defining an ideal number of small grammars to achieve the best performance. We also show that the hierarchical grammar approach using the division of population size strategy achieves significantly better results than the multi-level approach. However the division of population size strategy is less sensitive to the number of small grammars.

An important but elusive goal of computer scientists is the automatic creation of computer programs given only input and output examples. We present a novel approach to program synthesis based on the combination of grammars, generative neural models, and evolutionary algorithms. Programs are described by sequences of productions sampled from a Backus-Naur form grammar. A sequence-to-sequence Variational Autoencoder (VAE) is trained to embed randomly sampled programs in a continuous space – the VAE’s encoder maps a sequence of productions (a program) to a point z in the latent space, and the VAE’s decoder reconstructs the program given z. After the VAE has converged, we can engage the decoder as a generative model that maps locations in the latent space to executable programs. Hence, an Evolutionary Algorithm can be employed to search for a vector z (and its corresponding program) that solves the synthesis task. Experiments on the program synthesis benchmark suite suggest that the proposed approach is competitive with tree-based GP and PushGP. Crucially, code can be synthesised in any programming language.

Wireless communications networks are operating at breaking point during an era of relentless traffic growth. Network operators must utilize scarce and expensive wireless spectrum efficiently in order to satisfy demand. Spectrum on the links between cells and user equipments ('users': smartphones, tablets, etc.) frequently becomes congested. Capacity can be increased by transmitting data packets via multiple links. Packets can be routed through multiple Long Term Evolution (LTE) links in existing fourth generation (4G) networks. In future 5G deployments, users will be equipped to receive packets over LTE, WiFi, and millimetre wave links simultaneously. How can we allocate spectrum on links, so that all customers experience an acceptable quality of service? Building effective schedulers for link allocation requires considerable human expertise. We automate the design process through the novel application of evolutionary algorithms. Evolved schedulers boost downlink rates by over 150% for the worst-performing users, relative to a single-link baseline. The proposed techniques significantly outperform a benchmark algorithm from the literature. The experiments illustrate the promise of evolutionary algorithms as a paradigm for managing 5G software-defined wireless communications networks.

Evolutionary Computation is used to automatically evolve small cell schedulers on a realistic simulation of a 4G-LTE heterogeneous cellular network. Evolved schedulers are then further augmented by human design to improve robustness. Extensive analysis of evolved solutions and their performance across a wide range of metrics reveals evolution has uncovered a new human-competitive scheduling technique which generalises well across cells of varying sizes. Furthermore, evolved methods are shown to conform to accepted scheduling frameworks without the evolutionary process being explicitly told the form of the desired solution. Evolved solutions are shown to out-perform a human-engineered state-of-the-art benchmark by up to 50%. Finally, the approach is shown to be flexible in that tailored algorithms can be evolved for specific scenarios and corner cases, allowing network operators to create unique algorithms for different deployments, and to postpone the need for costly hardware upgrades. This work appears in full in Fenton et al., "Towards Automation & Augmentation of the Design of Schedulers for Cellular Communications Networks", Evolutionary Computation, 2018. DOI 10.1162/evco_a_00221.

Small Cells are being deployed alongside pre-existing Macro Cells in order to satisfy demand during the current era of exponential growth in mobile traffic. Heterogeneous networks are economical because both cell tiers share the same scarce and expensive spectrum. However, customers at cell edges experience severe cross-tier interference in channel sharing Het-Nets, resulting in poor service quality. Techniques for improving fairness globally have been developed in previous works. In this paper, a novel method for service differentiation at the level of individual customers is proposed. The proposed algorithm redistributes spectrum on a millisecond timescale, so that premium customers experience minimum downlink rates exceeding a target threshold. System level simulations indicate that downlink rate targets of at least 1 [Mbps] are always satisfied under the proposed scheme. By contrast, naive scheduling achieves the 1 [Mbps] target only 83% of the time. Quality of service can be improved for premium customers without significantly impacting global fairness metrics. Flexible service differentiation will be key to effectively monetizing the next generation of 5G wireless communications networks.

Grammar-Guided Genetic Programming has shown its capability to evolve beyond human-competitive transmission schedulers for the benefit of large and heterogeneous communications networks. Despite this performance, a large margin of improvement is demonstrated to still exist. We have recently proposed a multi-level grammar approach which evolves structurally interesting individuals using a small grammar, before introducing a thorough grammar to probe a larger search space and evolve better-performing individuals. We investigate the advantage of using a hierarchical approach with multiple small grammars at the lower level instead of a unique one, in conjunction with a full grammar at the upper level. While we confirm in our experiment that the multi-level approach outperforms the use of a unique grammar, we demonstrate that two hierarchical grammar configurations achieve significantly better results than the multi-level approach. We also show the existence of an ideal number of small grammars that could be used in the lower level of the hierarchical approach to achieve the best performance.

Co-ordination of Inter-Cell Interference through scheduling enables telecommunication companies to better exploit their Heterogeneous Networks. However, it requires from these entities to implement an effective scheduling algorithm. The state-of-the-art for the scheduling in Heterogeneous Networks is a Grammar-Guided Genetic Programming algorithm which evolves, from a given grammar, an expression that maps to the scheduling of transmissions. We evaluate in our work the possibility of improving the results obtained by the state-of-the-art using a layered grammar approach. We show that starting with a small restricted grammar and introducing the full functionality after 10 generations outperforms the state-of-the-art, even when varying the algorithm used to generate the initial population and the maximum initial tree depth.

Operators deploy Small Cells in high traffic regions to boost the capacity of their wireless networks. However, User Equipments (UEs) at Small Cell edges experience severe interference from neighbouring high-powered Macro Cells. A fair trade-off between cell-edge and cell-centre performance can be realised by intelligently scheduling Small Cell attached UEs. Grammar-based Genetic Programming is employed to learn models that map measurement reports to schedules on a millisecond timescale. The evolved schedulers are then aggregated into ensembles. The proposed system significantly outperforms a state of the art benchmark algorithm and is within 10% of the estimated optimum.

Wireless communications networks are a global trillion dollar industry, where small improvements can scale to provide significant cost savings to networks operators. In a field full of NP-hard optimisation problems, heuristic optimisation techniques such as Evolutionary Computation offer a means to provide bespoke, scalable solutions. Grammatical Genetic Programming is applied to optimise three aspects of an LTE Heterogeneous Network: setting optimal Small Cell powers and biases, Macro Cell ABS patterns, and Small Cell scheduling. The evolved heuristics yield minimum downlink rates three times greater than a baseline technique, and twice that of a state-of-the-art industry standard benchmark. This work appears in full in Fenton et al., "Multilayer Optimization of Heterogeneous Networks using Grammatical Genetic Programming", IEEE Transactions on Cybernetics, 2017. DOI: 10.1109/TCYB.2017.2688280.

Genetic Algorithms (GAs) have been shown to be a very effective optimisation tool on a wide variety of problems. However, they are not without their drawbacks. GAs require time to run, and evolve a bespoke solution to the desired problem in real time. This requirement can prove to be prohibitive in a high-frequency dynamic environment where on-line training time is limited. Neural Networks (NNs) on the other hand can be trained at length off-line, before being deployed on-line, allowing for fast generation of solutions on demand. This study presents a hybrid approach to time-frame scheduling in a high frequency domain. A GA approach is used to generate a dataset of optimised human-competitive solutions. Deep Learning is then deployed to extract the underlying model within the GA, enabling fast optimisation on unseen data. This hybrid approach allows for NNs to generate GA-quality schedules on-line, almost 100 times faster than running the GA.

Wireless traffic is surging due to the prevalence of smart devices, rising demand for multimedia content and the advent of the “Internet of Things”. Network operators are deploying Small Cells alongside existing Macro Cells in order to satisfy demand during this era of exponential growth. Such Heterogeneous Networks (HetNets) are highly spectrally efficient because both cell tiers transmit using the same scarce and expensive bandwidth. However, load balancing and cross-tier interference issues constrain cell-edge rates in co-channel operation. Capacity can be increased by intelligently configuring Small Cell powers and biases, and the muting cycles of Macro Cells. This paper presents a customised Genetic Algorithm (GA) for reconfiguring HetNets. The GA converges within minutes so tailored settings can be pushed to cells in real time. The proposed GA lifts cell-edge (2.5th percentile) rates by 32% over a non-adaptive baseline that is used in practice. HetNets are highly dynamic environments. However, customers tend to cluster in hotspots which arise at predictable locations over the course of a typical day. An explicit memory of previously evolved solutions is maintained and used to seed fresh runs. System level simulations show that the 2.5th percentile rates are boosted to 36% over baseline when prior knowledge is utilised.

Network operators are struggling to cope with exponentially increasing demand. Capacity can be increased by densifying existing Macro Cell deployments with Small Cells. The resulting two-tiered architecture is known as a Heterogeneous Network or 'HetNet'. Significant inter-tier interference in channel sharing HetNets is managed by resource interleaving in the time domain. A key task in this regard is scheduling User Equipment to receive data at Small Cells. Grammar-based Genetic Programming (GBGP) is employed to evolve models that map measurement reports to schedules on a millisecond timescale. Two different fitness functions based on evaluative and instructive feedback are compared. The former expresses an industry standard utility of downlink rates. Instructive feedback is obtained by computing highly optimised schedules offline using a Genetic Algorithm, which then act as target semantics for evolving models. This paper also compares two schemes for mapping the GBGP parse trees to Boolean schedules. Simulations show that the proposed system outperforms a state of the art benchmark and is within 17% of the estimated theoretical optimum. The impressive performance of GBGP illustrates an opportunity for the further use of evolutionary techniques in software-defined wireless communications networks.

Heterogeneous Cellular Networks are multi-tiered cellular networks comprised of Macro Cells and Small Cells in which all cells occupy the same bandwidth. User Equipments greedily attach to whichever cell provides the best signal strength. While Macro Cells are invariant, the power and selection bias for each Small Cell can be increased or decreased (subject to pre-defined limits) such that more or fewer UEs attach to that cell. Setting optimal power and selection bias levels for Small Cells is key for good network performance. The application of Genetic Programming techniques has been proven to produce good results in the control of Heterogenous Networks. Expanding on previous works, this paper uses grammatical GP to evolve distributed control functions for Small Cells in order to vary their power and bias settings. The objective of these control functions is to evolve control functions that maximise a proportional fair utility of UE throughputs.

Effective scheduling in Heterogeneous Networks is key to realising the benefits from enhanced Inter-Cell Interference Coordination. In this paper we address the problem using Grammar-based Genetic Programming. Our solution executes on a millisecond timescale so it can track with changing network conditions. Furthermore, the system is trained using only those measurement statistics that are attainable in real networks. Finally, the solution generalises well with respect to dynamic traffic and variable cell placement. Superior results are achieved relative to a benchmark scheme from the literature, illustrating an opportunity for the further use of Genetic Programming in software-defined autonomic wireless communications networks.