The speedy pace of change in telecommunications and its ubiquitous presence have drastically altered the way people interact, impacting production, government, and social life. The infrastructure for providing telecommunication services must be continuously renewed, as innovative technologies emerge and drive changes by offering to bring new services to the end users. In this context, the problem of efficiently designing the underlying networks in order to satisfy different requirements while at the same time keeping the capital and operative expenditures bounded is of ever growing importance and actuality. Network design problems have many variations, depending on the characteristics of the technologies to be employed, as well as on the simplifying hypothesis that can be applied on each particular context, and on the planning horizon. Nevertheless, in most cases they are extremely complex problems, for which exact solutions cannot be found in practice. Nature-inspired optimization techniques (belonging to the metaheuristic computational methods) are important tools in these cases, as they are able to achieve good quality solutions in reasonable computational times. The objective of this chapter is to present a systematic review of nature-inspired techniques employed to solve optimization problems related to telecommunication network design. The review is aimed at providing an insight of different approaches in the area, in particular covering four main classes of applications: minimum spanning trees, reliable networks, local access network design and backbone location, and cellular and wireless network design. A large proportion of the papers deal with single objective models, but there is also a growing number of works that study multi-objective problems, which search for solutions that perform well in a number of different criteria. While genetic algorithms and other evolutionary algorithms appear most frequently, there is also significant research on other methods, such as ant colony optimization, particle swarm optimization, and other nature-inspired techniques.
TopIntroduction
In the last twenty years, our society has witnessed the fast development of the telecommunication technologies for communication of data, voice, video, and resources all around the globe. It has also observed the rapid evolution of network infrastructures, the great expansion of the Internet, cellular, satellite, Wi-Fi networks, and numerous networking applications that are at the very heart of the functioning and success of our modern society. As a consequence, there has been a renewed interest in structural network design problems, due to the critical need to properly design a telecommunication infrastructure to satisfy customer requirements. In a general formulation, network design problems challenge problem techniques to find a connection topology that guarantees an optimized utilization of network resources under specified constraints, ensuring reliability, Quality of Service (QoS), and other important features for source-to-destination communication.
Since the size of the existing communication networks is continuously enlarging, the underlying instances of related optimization problems frequently pose a challenge to classical algorithms. The research community is nowadays searching for new techniques that are able to replace and improve over to the traditional exact ones, whose low efficiency often makes them useless for solving complex real-life problems of large complexity in reasonable times. Heuristic algorithms have been successfully applied to solve network design problems, exploiting their ability to obtaining accurate solutions in a reasonable time. Although heuristics and metaheuristics could sometimes fail in computing an optimum for the problem, they get appropriate quasi-optimal solutions that satisfy network designers. Among a whole new set of heuristics and modern optimization techniques, newly nature-inspired computational methods have emerged as flexible and robust tools for solving the underlying complex optimization problems found in telecommunication network design, exhibiting high level of problem solving effectiveness also shown in many other areas of application (Blum & Roli, 2003; Glover & Kochenberger, 2003).
Nowadays, telecommunication networks are increasingly complex, dynamic, and often composed of heterogeneous devices. These characteristics imply several challenging issues to the network topology design, essentially concerning performance, robustness, and security in data transmission. The emergent computational heuristics inspired from nature are an appealing option for network topology design, as they have provided accurate results for tackling many problems with this kind of distinctive characteristics. Natural and biological systems have key properties, such as self-organization, adaptation, robustness, scalability, and distribution, which are highly desirable for dealing with the high complexity of designing current and future telecommunication networks that are able to properly handle highly increasing amount of data. Therefore, in recent years, an increasing number of accurate and efficient techniques for solving optimization problems related to network design have been proposed taking inspiration from the observation of natural systems and processes such as biological evolution, insect colonies, immune systems, cultural systems, and collective behaviors of groups of animals, among others (Zomaya, 2006).
This chapter provides a survey of the current state-of-the-art on using nature-inspired techniques to solve structural telecommunication network design problems. The survey focuses mainly on application areas, regarding only to those problems inherently related to topology design. The analysis explicitly excludes other applications, such as network routing and problems concerning commodities transportation or resource assignment, unless the network topology design was also considered in the optimization process.