Abstract
Evolutionary algorithms are metaheuristic algorithms that provide quasioptimal solutions in a reasonable time. They have been applied to many optimization problems in a high number of scientific areas. In this survey paper, we focus on the application of evolutionary algorithms to solve optimization problems related to a type of complex network like mobile multihop ad hoc networks. Since its origin, mobile multihop ad hoc network has evolved causing new types of multihop networks to appear such as vehicular ad hoc networks and delay tolerant networks, leading to the solution of new issues and optimization problems. In this survey, we review the main work presented for each type of mobile multihop ad hoc network and we also present some innovative ideas and open challenges to guide further research in this topic.
1. Introduction
Mobile wireless multihop ad hoc networks have attracted the attention of the scientific community for more than two decades [1–4]. The basic idea of communicating electronic devices using a wireless multihop path, without the necessity of a central system or a fixed infrastructure, has evolved since its origin and it is still an active focus of research. The proliferation of portable electronic devices with wireless communication capabilities like smartphones and tablets has made possible a world of wireless devices that can exchange information ubiquitously. This concept is also called the Internet of Things since not only can people communicate with each other but also many sensors can generate information autonomously.
The study and analysis of mobile multihop ad hoc networks have been carried out by simulation analysis using event-based network simulators. The main reason is that real testbeds require a high investment in terms of hardware [5], and, more importantly, the replication of real mobile conditions is very difficult in a controlled environment like a laboratory. Consequently, the main mechanism to evaluate the performance of multihop ad hoc networks has been the use of popular networks simulators like NS-2, NS-3, and OMNET++, among others. Many performance metrics have been presented and analyzed to improve the performance of mobile multihop ad hoc networks under different situations. However, some studies have revealed that mobile multihop ad hoc networks are complex networks where many design parameters are intercorrelated [6, 7], which makes the use of analytical models to be optimized from a theoretical viewpoint very difficult. Even in the case that an analytical model is available, it may be very difficult to apply gradient-based optimization mechanisms that require to derivate the model in order to obtain the global maximum and minimum values. This fact is encouraging the research community to explore new mechanisms to optimize the performance of mobile multihop ad hoc network, for instance, by using metaheuristic approaches like evolutionary algorithms.
Evolutionary algorithms are metaheuristic algorithms intended to solve complex optimization problems. Although they were proposed several decades ago, their application on real optimization problems requires high computational resources that were not available at that time. Nowadays, modern computers and laptops based on multicore architectures are capable of running millions of operations per second, making the application of evolutionary algorithms a reality in many scientific areas. They are based on the evolution of a population of potential solutions by the mean of genetic operators like crossover and mutation. Evolutionary algorithms have been successfully applied to many mobile multihop optimization problems such as topology management, broadcasting algorithms, routing protocols and mobility models, and other related problems. The main idea is the integration of an evolutionary algorithm into the simulation framework that performs as the optimization engine to find the most optimal design variables for a given optimization problem.
The aim of this paper is to collect previous research about the application of evolutionary algorithms in the field of mobile multihop ad hoc networks and to provide new insights and challenges still open to the research community. The rest of this paper continues as follows. Section 2 introduces the mobile multihop paradigm and it describes its evolution since its origin. Section 3 details the main features of the evolutionary algorithms and how they can be applied to mobile multihop optimization problems. Section 4 reviews the existing work on the application of evolutionary algorithms for multihop optimization problems and Section 5 presents the main challenges that require further research. Finally, Section 6 concludes this paper.
2. Mobile Wireless Multihop Ad Hoc Networks and Evolutionary Algorithms for Optimization Problems
This section introduces mobile multihop ad hoc network such as MANETs, VANETs, and DTNs. We focus on the main feature of each type of mobile multihop ad hoc network such as types of communications, wireless technology, mobility, and applications.
2.1. MANETs
MANETs represent the original idea of the multihop paradigm [1]. That is, the establishment of an ad hoc network formed by wireless devices without requiring a central system. The original idea was to replicate the wired communications such as TCP/UDP and IP based protocols in MANETs. However, this original idea was not possible due to the intrinsic characteristics of MANETs in terms of mobility and limited node's transmission ranges. Both features make the topology of MANETs extremely changeable. Consequently, the protocols originally designed for static network like the Internet cannot be easily adapted to MANETs. This fact led to a high research on new protocols tailored for MANETs [2]. The routing layer has been by far the most studied one [8]. There are some good surveys on routing protocols in the literature [8, 9]. The basic objective is to find the suitable communication path between a mobile source node and one or several mobile destination nodes. In addition, a good routing protocol must be able to deal with route and link breakages. The basic mechanism to find routes is, namely, broadcasting. This is an all-to-all communication procedure by which each node in the network retransmits the incoming packets at least once. Broadcasting algorithms for MANETs have also been widely studied [10, 11].
Regarding the wireless technology used in MANETs, IEEE 802.11 a/b/g or WiFi has been the preferred technology to be used. The reason is that this wireless technology is easily found in the majority of portable devices such as smartphones, laptops, and tablets. Moreover, WiFi transceiver can be configured in ad hoc mode. IEEE 802.15.4 or Bluetooth is also a personal area wireless technology that can be used to form a MANET since Bluetooth technology enables the formation of ad hoc networks like piconets and scatternets. However, the main issue of Bluetooth is the power consumption, especially when the devices are configured in inquiry mode. The inquiry mode is the one used to find other nearby devices in the node's transmission range.
The mobility of nodes is not so high since MANETs were envisioned to be formed by people carrying a portable device. The mobility of nodes in MANET is normally emulated by using a mobility model [12]. The random waypoint mobility model has been the most used so far. Nevertheless, it has been demonstrated that this mobility model does not represent any real MANET situation [13]. Consequently, new mobility models have been proposed in recent years [14].
MANETs can be applied in any situation where the deployment of a fixed communication infrastructure is not possible. A clear example of this scenario is disaster scenarios, where the fixed communication infrastructure is likely to be destroyed or malfunctioning [15]. In such chaotic scenario an alternative communication network is needed and the rapid deployment of a MANET can be a potential solution. Another potential application of MANETs is the Internet of Things (IoT), which envisions a world full of interconnected devices. In this IoT world, MANETs would be formed everywhere between portable devices [16].
2.2. VANETs
VANETs represent an evolution of multihop paradigm [17]. The idea is to incorporate wireless transceiver into vehicles so that they can communicate with each other. These types of communication are named Vehicle to Vehicle (V2V) communications and they represent the main communications in VANETs. However, there exist communications between the vehicle and the road infrastructure that are called Vehicle to Infrastructure (V2I) communications. In VANETs both routing protocols and broadcasting algorithm have been widely studied [18]. Broadcasting algorithms have attracted more attention due to the fact that collision avoidance is one of the main applications of VANETs. In this scenario, a car tries to inform another incoming car by transmitting a broadcast packet. Therefore, an efficient broadcasting algorithm is primordial in VANETs. Another important feature of VANETs is that power consumption is not a design parameter in VANETs since vehicles can recharge their batteries on the fly.
WAVE technology based on IEEE 802.11p is the main wireless technology envisioned to be used in VANETs [19]. It is still on the development phase but it is expected to be included in every commercial vehicle shortly. IEEE 802.11p defines different levels of prioritizing the transmitting packets. One important feature of WAVE technology is the consideration of Road Site Units (RSUs) that act as static access points, improving the global performance of the network. Consequently, a VANET can be seen as hybrid network that combines both properties of mobile networks like MANETs and static network like the Internet.
Regarding the mobility of nodes in VANETs, it is much higher than the mobility of MANETs. However, the mobility of cars is constrained by the road lines. Consequently, the mobility of nodes in a VANET is more predictable. Mobility models for VANETs are a very hot research topic since a realistic mobility model for VANET is essential to analyze VANETs in simulation-based studies [20].
The main applications of VANETs range from safety traffic applications like collision avoidance and road obstacle warning to traffic information and infotainment services such as games and multimedia streaming [1].
2.3. DTNs
Another type of wireless multihop mobile network that has been deeply researched in recent years is represented by DTNs (delay tolerant networks). They are dynamically built when mobile devices collaborate to form communication paths while users are in close proximity. They are based on a store-carry-and-forward paradigm [1], which means that a node that wants to relay a message begins by storing it, then carries it around the network until the carrier encounters the destination or a node that is more likely to bring the data close to the destination, and then finally forwards it.
Regarding communications in DTNs, we can distinguish between forwarding algorithms and data dissemination algorithms [21]. In the former, the objective is to find a suitable forwarding policy to transmit a piece of information between a source and a destination node. On the contrary, in data dissemination algorithms, the main objective is to spread out certain information throughout the entire network or several destination nodes. Moreover, DTN algorithms are not developed at the routing later; they run in an upper level, namely, bundle layer.
Mobility in DTNs has attracted a lot of attention in recent years [22]. The main idea is to model the mobility of people carrying portable devices. These people encounter each other in controlled environments such as scientific conferences and university campuses. Most mobility models for DTNs are based on real-life traces that are collected through developed applications for smartphones. In this line of work, the Community Resource for Archiving Wireless Data at Dartmouth (CRAWDAD) [23] is an open project aimed to archive data collected from real-life experimentation, so many traces are available.
With regard to the wireless technologies used for DTNs, again WiFi and Bluetooth are the main candidates because they are incorporated in the majority of portable devices. In addition, WiFi direct is expected to gain further momentum as soon as it is included in the new generations of smartphones and other portable devices.
There are many real-life scenarios where DTNs may be employed. One such scenario is represented by disaster management [22]. DTNs have an important use in situations where the contacts between mobile devices happen often and for longer periods of time. Such a situation occurs in crowded places, like a music concert or an amusement park. In these cases, DTNs may be used to broadcast the location of mobile device owners to interested receivers. Another potential practical use of DTNs is in regard to floating content in areas such as open city squares [24], where mobile nodes enter a geographical zone (called an anchor zone), spend some time in it, and then leave. While in the anchor zone (which gives the physical boundaries of the network), the mobile devices produce content and opportunistically replicate it to other nodes. These nodes may copy the data either if they need it for themselves or if they transport it for the benefit of other nodes. A node that exits in the anchor zone deletes the data, so the availability of the floating content is probabilistic. We also believe that a platform for supporting generic context-aware mobile applications such as CAPIM [25] can fully benefit from DTN integration. CAPIM (Context-Aware Platform using Integrated Mobile services) is a solution designed to support the construction of next-generation applications.
More recently, DTNs have been used for other purposes, such as targeted advertising. One such example is MobiAd [26], an application that presents the user with local advertisements in a privacy-preserving manner. The ads are selected by the phone from a pool of advertisements that are broadcast on the local mobile base station or received from local WiFi hotspots. Information about ad views and clicks is encrypted and sent to the ad channel in an opportunistic way, via other mobile devices or static WiFi hotspots.
3. Evolutionary Algorithms for Optimization Problems
Technology is evolving extremely fast providing communication capabilities to tiny devices. This leads towards highly heterogeneous and mobile networks composed of any kind of communicating devices, which are not suitable for existing communication networks: self-organizing mechanisms are thus needed. In nature, there exist many biological systems that after years of evolution are able to cope with the problems we face in these heterogeneous networks: recovery from failure, mobility, self-organization, stability, collaborative behavior, and so forth. Researchers are developing nature inspired algorithms in order to solve complex problems; for example, they have been widely applied for network design. Next, we provide a brief introduction to evolutionary algorithms.
3.1. Introduction to Evolutionary Algorithms
Evolutionary algorithms (EAs) are well-known iterative metaheuristics [45–47] (i.e., approximate optimization techniques) that can be applied to solve NP-complete problems. They usually work on a set of tentative solutions to the problem (called population), which are simultaneously evolved towards (hopefully) better ones. This evolution process is performed by applying some stochastic operators (typically called evolutionary operators) to the solutions (also called individuals), with the aim of mimicking the evolution process we find in nature, as shown in Figure 1. Individuals are evaluated to quantify the quality of the solution they represent (the fittest individuals survive for the next generations thanks to the replacement method). EAs iterate on the set of candidate solutions until the termination condition is met (usually, after the optimal solution is found or a number of iterations are performed). In every iteration, solutions are evolved using some evolutionary operators, as the parent selection, recombination (or crossover), and mutation. Typically, the different EA families differ on the evolutionary operators that are applied in the evolution.
Functioning of a typical evolutionary algorithm.
We can find a large number of different families of EAs in the literature. Traditionally, the first existing families of EAs were genetic algorithms (GAs) [48–50], Evolution Strategies (ESs) [51], Evolutionary Programming (EP) [52], and genetic programming (GP) [53]. GAs were initially designed for combinatorial optimization problems with binary representations (although they are currently used for other combinatorial and continuous optimization problems too), and they evolve solutions by iteratively applying the selection, recombination, and mutation operators as described in Figure 1. Unlike GAs, ESs work on one single solution (instead of a population of them) to solve real-valued variables, and only selection and mutation operators are applied in the evolutionary process. Genetic programming algorithms work on a population of tree-shaped individuals (i.e., programs) instead of the strings of binary characters or real-valued variables traditionally used in GAs and ES, respectively. Finally, EP is similar to GP, but the structure of the program to optimize is fixed.
Nowadays, the evolutionary algorithms field is growing and evolving itself. An evidence is the number of new families that recently emerged, such as Particle Swarm Optimization (PSO) [54], Differential Evolution (DE) [55], ant colony optimization (ACO) [56], or Estimation of Distribution Algorithms (EDAs) [57], to name a few. Both PSO and DE are very efficient algorithms to optimize continuous problems. PSO are inspired in swarms that follow the movements of the leader (e.g., bird or fish swarms), while DE evolve solutions by applying some changes following simple formulae based on geometric operations, using the information of other solutions of the population. ACO algorithms are constructive-based EAs typically applied to combinatorial problems. They are inspired by the behavior of ants looking for sources of food. ACO starts by creating empty solutions and assigning values to every variable in a one-by-one basis. These values are stochastically assigned, but taking into account the quality of the solution the different assignments led to in the past. Finally, EDAs compute the distribution of the variables assignments in the solutions of the population after every iteration and randomly generate the next population of solutions based on the computed distribution.
3.2. Application of Evolutionary Algorithms to Problems in Mobile Multihop Ad Hoc Networks
Evolutionary algorithms can be applied for solving different problems in ad hoc networks in many ways. We classify the optimization process in terms of the execution mode, information needed, and platform used [41].
3.2.1. Online and Offline Techniques
Depending on whether the metaheuristic is executed beforehand or during runtime, we can differentiate between offline and online techniques, respectively.
Offline approaches look for the best possible configuration of the algorithm that will be later used during the execution. These approaches usually evolved until the optimum is found (in case it is known) or the quality of the solutions is evaluated through simulation. In this last case, the model of the systems highly influences the performance of the algorithm. In case the problem varies during the runtime these offline techniques are not suitable.
Online approaches are used during execution, in these time varying algorithms, for adapting the behavior so that the best next step is found. They usually require intensive computation; thus a central unit might be used. However, ad hoc networks are decentralized systems; thus either constrained nodes able to cope with very lightweight metaheuristics are used or offline techniques are preferred.
Literature reveals that the majority of the existing works are offline techniques due to the energy limitation of the nodes composing an ad hoc network and also due to the time the metaheuristics usually take. For instance, an iterated local search that tries to find the minimum spanning tree to connect all the networks is proposed in [58]. Another work that tries to get the minimum power broadcast problem was presented in [59]. In these two last examples, algorithms require global knowledge, and they are run offline and are centralized.
However, we can also find ant colony optimization (ACO) algorithms, which are highly used for online optimization in MANETs, especially when dealing with routing problems. In [60], a routing algorithm based on ant colonies is presented. It also sets to sleeping mode nodes that reach a predefined level of pheromone. This online and decentralized approach uses local knowledge. Some other examples of works using swarm intelligence in an online fashion using local knowledge are BeeSensor [61] and BeeAdHoc [62] or NISR [63] that combines both bees and ants inspiration.
3.2.2. Global or Local Knowledge Techniques
An algorithm that requires information about the whole system for an appropriate operation is said to use global knowledge. This technique might not be always suitable when dealing with ad hoc systems because the lack of a central unit makes the collection of up to date data of the complete network difficult. Only when the data is obtained beforehand or the size of the network is very small, we could consider this technique.
In case the algorithm only uses information obtained locally, that is, node's information and node's neighbors information (using beacons or eavesdropping), then it is said to use local knowledge.
All the online techniques we mentioned before dealing with bees and ants [60–63] use global knowledge. It would be contradictory to design an algorithm that is very lightweight and runs online but requires global knowledge. However, we can always find some exceptions where this combination might be feasible. For example in [64], authors use a glowworm optimization algorithm for increasing the global coverage for optimal sensor deployment in a self-organized way in case nodes are mobile. In this specific problem, having global knowledge beforehand is feasible. Another example is GrAnt [65], which is used for efficiently broadcasting a message, in a delay tolerant network, using the most promising forwarders from node's social connectivity. It is run online in a decentralized fashion but using global knowledge.
3.2.3. Centralized and Decentralized Systems
A centralized system has a central unit in charge of optimizing or making decisions for the whole system. It can use either global information or information gathered locally by all nodes, and this information is sent to the central unit for decision-making. In the latter, the system requires significant coordination, increasing, thus, delays and overhead. If the central unit fails, the complete system crashes.
When nodes locally execute and make decisions, changing future behaviors according to the results obtained, it is then considered a decentralized system.
It is not realistic to design an online optimization process targeting a decentralized mobile ad hoc network that uses global knowledge.
In [66], NSGA-II is used to set the sleeping schedule in sensor networks in order to maximize the coverage achieved while minimizing the number of sensors used. In this case, an offline and centralized technique that needs global knowledge is used. This specific case of sensor networks, where the target area is a priori known and some information can be gathered beforehand for optimal settings, is compatible with a centralized optimization using knowledge of the whole network.
Fortunately, many works in the literature use a decentralized approach when solving problems in ad hoc networks. This is the case of BAOA [67], which uses ant colony optimization algorithms for minimizing the total energy consumption. Although it runs online, it requires global knowledge (location of all nodes).
A decentralized and online genetic algorithm that uses traditional and evolutionary game theory for self-spreading nodes in an area using only local knowledge is proposed in [30].
For an extensive survey on optimization algorithms solving problems in ad hoc networks, please refer to [41].
4. Review of Existing Work
This section reviews the main existing work found in the scientific literature that applies evolutionary algorithms to multihop ad hoc networks. We divide this section into different subsections each one covering the approaches presented for each different ad hoc paradigm such as MANETs, VANETs, and DTNs.
4.1. MANETs
In [41], authors categorize the main research topics in which evolutionary algorithms have been used as topology management, broadcasting algorithms, routing protocols, clustering approaches, protocol optimization, mobility models, selfish behaviors, security issues, and other applications. We follow a similar taxonomy but in this case we focus on the main research topics of MANETs in the last two decades such as topology management, broadcasting, and routing protocols. We refer the readers to [41] for further information on the research topics not covered in this section.
4.1.1. Topology Management
Topology management problems or deployment problems are focused on finding the optimal topology for efficiently achieving a target performance of the network.
In [27], the authors use a single objective optimization algorithm to obtain the optimal positions and speed of a number of auxiliary nodes in a railway station scenario. The objective is to increase the advisory distance at which a train approaching the station receives the information. In [28], the connectivity of crew-member acting a disaster scenario is improved by the deployment of static auxiliary beacon nodes that are used as packet forwarders. The optimization problem is solved by applying a single objective genetic algorithm. In [28], the connectivity of the network is measured as the reachability achieved by broadcasting packets sent by the crew-members. The authors use the well-known disaster area mobility model [68] in which the disaster area is divided into different technical areas. In [29], the authors use a PSO algorithm to deploy mobile nodes, called agents, in order to improve the connectivity of the network. They also predict the future movements of nodes based on the nodes' positions and their speeds. Consequently, the optimization approach finds future best positions for the agents according to the current and future states of the network. They measure the connectivity of the network as the average node's connectivity ratio.
In [30], the authors propose an evolutionary game called NSEG, which is based on game theory and brute-force genetic algorithm. The goal for each node is to distribute itself over an unknown geographical terrain in order to obtain a high coverage of the area by the nodes and to achieve a uniform node distribution while keeping the network connected.
4.1.2. Broadcasting Algorithms
Broadcasting is basic all-to-all communication mechanism widely used in MANETs [69]. The main objective of a broadcasting algorithm is to efficiently disseminate a message throughout the network. Despite its simplicity, the design of broadcasting algorithms has drawn the attention of the ad hoc community for the last two decades [69, 70]. The simplest broadcasting algorithm called flooding has been demonstrated many times to be inefficient, causing the well-known broadcast storm problem [71]. Many broadcasting algorithms mostly based on topological parameters can be found in the literature [69, 70] such as the density of nodes, relative distance, and counter-based mechanisms. Recently, evolutionary algorithms like genetic algorithms have been used to optimize the design of broadcasting algorithms. In [31], the authors solve the well-known minimum energy broadcast NP-hard problem using a hybrid evolutionary algorithm. The idea determines the set of forwarder nodes in a MANET that guarantees maximum dissemination with the minimum energy consumption.
In [32], the authors use the widely used NSGA-II multiobjective algorithm [72] to optimize the design of a broadcasting algorithm based on similarity/dissimilarity coefficients. They maximize the reachability and minimize the number of retransmissions and the delay of the broadcasting algorithm. They simulate their approach in a realistic disaster scenario like the disaster area mobility model [73].
In [33], the design of the AEDB broadcasting algorithm [74] is optimized by using parallel multiobjective optimization algorithm. The AEDB algorithm is based on the relative Euclidean distance between the sender and the receiver of the packet. The idea is to favor nodes located at higher distances from the sender to reduce the number of retransmissions. The objectives for the broadcasting algorithm are to maximize the reachability and to minimize the energy used, the retransmissions, and the delay. They use AEDB-MLS, a multistart population-based local search algorithm that maintains several distributed populations. It is a massively parallel algorithm in which every solution in every population is simultaneously improved by the parallel application of an iterative local search procedure.
4.1.3. Routing Protocols
Routing protocols are massively used in MANETs. They are so important for the correct performance of a dynamic distributed network like a MANET. The primary objective of a routing protocol is to find the most suitable communication route between a source and a destination node. The design of routing protocols has been very active in the last decades, causing a high number of routing protocols in the scientific literature to appear [9]. Moreover, it has been demonstrated that the configuration of a routing protocol can impact notably on the obtained results [75, 76].
Evolutionary algorithms have been widely used for the parameter configuration of routing protocols. The idea is to find the most optimal parameters for the performance of a routing protocol. In [34], the authors test several multiobjective optimization algorithms to optimize a simple routing protocol that finds routes between two nodes in the network. They use Nondominated Sorting Based Genetic Algorithm-II (NSGA-II) and the Multiobjective Differential Evolution (MODE) to optimize energy cost and E2E delay performance metrics. According to the results in [34], MODE algorithm is capable of finding solutions closer to the Pareto Front and, in general, converges faster than the NSGA-II.
4.2. VANETs
We divided the existing works on the application of evolutionary algorithms to VANETs scenarios into four main categories such as topology deployment, broadcasting algorithms, routing protocols, and mobility.
4.2.1. Topology Management
In [35], the authors propose the deployment of auxiliary nodes called injection points to improve the small-world properties of VANETs. The small-world phenomenon has been widely studied in other types of networks like random networks and the Internet [77]. The main idea behind the small-world phenomenon is that nodes have in the majority of cases connections with neighbor nodes in the network. For this reason, nodes have a high clustering coefficient. However, there are also long distance connections to other random nodes. This fact reduces the average path length in the network. In [35], the authors use two well-known evolutionary multiobjective algorithms such as NSGA-II and MOCHC to solve the proposed problem of placing the injection points. Three objectives are defined, minimizing the number of injection points, maximizing the clustering coefficient, and minimizing the difference between the average path length of the resulting network and the average path length of the equivalent random graph. In addition, they propose several real implementations of their approach, which are based on centralized and distributed solutions.
In [36], the authors optimize the deployment of RSU in VANET scenarios. They define the optimization problem as a Maximum Coverage with Time Threshold Problem (MCTTP). They optimize the deployment of k RSUs with transmission range R on an urban road topology of area equal to A and n intersections. The main objective is to maximize the number of vehicles covered by the k RSUs.
4.2.2. Broadcasting Algorithms
In [37], the authors optimized a probabilistic broadcasting algorithm for VANETs. They define four decision variables that determine the performance of the proposed broadcasting algorithm such as the forwarding probability, the total number of repeats, the delay between repeats, and Time to Live (TTL). The authors defined a repeat as the number of times a node in the network can retransmit a given packet. As performance metrics, they use the number of collisions, the propagation time, and the total number of retransmissions.
4.2.3. Routing Protocols
In [38], the authors determine the optimal configuration parameters for the VDTP (Vehicular Data Transfer Protocol) protocol intended for VANET scenarios [78]. This protocol operates on the transport layer protocols of VANETs, allowing the End-to-End file transfer. The authors use up to five different artificial intelligence based algorithms such as Particle Swarm Optimization (PSO), Differential Evolution (DE), genetic algorithm (GA), Evolutionary Strategy (ES), and simulated annealing (SA) to find the optimal values of three configuration parameters like chunk size, total attempts, and retransmission time [78]. They test their proposed approach in two different VANET scenarios such as highway and urban scenarios. As fitness function to measure the quality of the solutions, the authors use one composed of three performance metrics such as the transmission time, the number of lost packets, and the transferred packets.
Optimization of Link State Routing (OLSR) protocol has been considered in [39, 79] with VANET scenarios. OLSR is a proactive routing protocol, which was originally designed for MANETs, that relies on the Multi-Point Relay algorithm to efficiently disseminate information throughout the network. In [39], the authors determine the optimal values of up to 8 different configuration parameters. They use PSO, DE, GA, SA, and Random Search to optimize a weighted fitness function that takes into account three important performance parameters such as NRL, E2E, and PDR. They evaluate the resulting protocol in urban VANET scenarios [20].
In [40], the authors tune the AODV routing protocol in VANET scenarios. AODV was also originally designed for MANETs. However, it has also been demonstrated to be suitable for VANET scenarios [80].
4.2.4. Mobility Models
In [41], the authors optimize five parameters of a mobility model generator for VANET urban scenarios. The idea is to generate realistic mobility for VANET scenarios. The parameters optimized are the level of attraction of certain zones in order to be selected as destination zones. The authors defined up to three parameters that determine such level of attraction. The two other parameters are the inner traffic ration, which is a ratio that represents the amount of traffic originating from residential zones as a percentage of the outer ratio, and the shifting ration that defines the percentage of vehicles whose trip starts at hour h but ends at hour
4.3. DTNs
DTN research has been gaining steam in recent years, due to the great increase in the number of existing mobile devices and their ubiquitousness. A thorough analysis of DTNs was done by Conti et al. [81], where functions such as message forwarding, security, data dissemination, and mobility models are analyzed. Several dissemination algorithms are also reviewed, among them BUBBLE Rap [82], PROPICMAN [83], or HIBOp [84]. A taxonomy for data dissemination algorithms [21] splits them based on network infrastructure, node properties, content characteristics, and social awareness. In [85] the authors classify routing protocols in DTNs as context-oblivious, partially context-aware, and fully context-aware protocols. In this classification, the level of context information that nodes have available is the key component to make the distinction among the routing approaches.
4.3.1. Data Dissemination
Genetic algorithms have also been employed for optimizing DTNs. Bitaghsir and Hendessi [42] proposed one such solution, which performs data dissemination in vehicular-based DTNs. A node decides whether to forward a message to another node it has a contact with by assigning weights to four node properties and comparing the weighted sum with a threshold. The four properties are the encountered node's speed, its direction, the distance between the node and the message destination, and the probability of network disconnectivity (which is computed from a message's hop count). Based on the four weights (one for each of the above parameters), a first generation of chromosomes is randomly created, each being composed of five genomes: the four weights and the threshold (all values between 0 and 1). For the selection phase, a fitness function that takes into account a message's delivery latency is used. Then, one-point crossover is employed for the reproduction phase, while the termination condition is achieved after four generations.
Another data dissemination technique for DTNs that uses genetic algorithms is GAER [43]. In this algorithm, a node that wants to relay a message (either created by itself or transported on behalf of another node) applies a genetic algorithm for all the nodes it is currently in contact with, in order to decide to which node the data will be relayed. The initial chromosomes are generated randomly, and they represent an array containing a node's home, office, and leisure locations (i.e., its home locations), as well as the home locations of the neighboring nodes. A fitness function used for determining the capability of a node to be the next hop is applied, as well as the other genetic operations, that is, selection and crossover, until a limited number of generations are computed. The fitness function is the measure of the capability of a node to deliver a message to the final destination and is composed of two factors (called Mean and Place). However, the main drawback of this method is that it requires the computation of genetic algorithms on the fly, when two nodes are in contact. Since we are dealing with DTNs composed of mobile nodes such as smartphones, this might cause some problems, due to the limited computation capabilities of a node. Moreover, if the nodes are highly mobile, the two encountering nodes might not even be in contact anymore when the genetic algorithm finishes. In addition, GAER assumes that a node is connected to multiple other nodes at the same time, but this is not the case in sparse networks (typical situation in DTNs). The advantage of the proposed solution is that the computations are done offline and are used as guidelines for correctly selecting the parameters of the dissemination function that is computed when a contact occurs. This function is easy to compute, so time and computation resources will not be wasted.
A genetic algorithm for routing in DTNs is also proposed by Da Silva and Guardieiro [44, 86]. The authors assume that the network's topology is known in advance and is represented as a series of evolving graphs. Thus, chromosomes (generated randomly at the start of the genetic algorithm) are composed of genes that represent the nodes located on the route to the destination. The fitness function is computed based on the delivery probability of a message, also taking into consideration the storage capacity of each potential next hop. The genetic operators used are crossover and mutation, and the algorithm is applied for a predefined number of generations. Similarly to GAER, this solution also has the drawback of being computed at every contact. Moreover, it assumes that the topology is known in advance, which is not true in highly mobile DTNs.
In all the cases, the main advantage of using evolutionary computation is dealing with complex optimization problems where other alternatives cannot provide a global optimum. As a summary of all the reviewed optimization problems, Table 1 contains their main features such as the type of mobile multihop network, the evolutionary algorithm used, the type of optimization problem, and the main challenge/s addressed.
Summary of the reviewed optimization problems.
5. Open Challenges
Evolutionary algorithms have been applied to mobile multihop ad hoc networks for the last decade. However, there are still many optimization problems in these complex networks that can be solved using a suitable evolutionary algorithm. New architectures of evolutionary algorithms are continuously proposed such as coevolutionary algorithms and parallel evolutionary algorithms. Since evolutionary algorithms demand high computational resources, the parallelization of the tasks related to the evolution procedure will allow executing genetic algorithms using multiple processors and cores, reducing the computation time. For example, the DEAP Python [87] module allows users to easily parallelize the execution of evolutionary algorithms through the SCOOP module.
Another open challenge is the application of evolutionary algorithms in real testbeds so the simulation results obtained can be corroborated and validated. This can also be an interesting alternative for reducing the amount of time required by simulations, which is probably the main bottleneck when applying evolutionary algorithms to multihop ad hoc networks. For instance, a simulation in NS-2, which is the most popular event-based network simulator for mobile multihop ad hoc network, can take up to several minutes (depending on the computational power of the computer used to run the simulations). Notice that this time can be prohibitive in some cases.
Genetic programming is also a field that can be further investigated in mobile multihop ad hoc networks. Genetic programming does the same as genetic algorithms but using computer programs. With genetic programming, it is theoretically possible to find the best broadcasting algorithms or the best deployment strategy. However, genetic programming has also some disadvantages such as the computation time or the excessive growth of its individuals.
Another important common open challenge is the use of completely distributed implementation of evolutionary algorithms. Most of the studies presented in this survey used centralized implementations. However, obtaining global information in a mobile multihop network is very costly in terms of message exchanges. In addition, the mobility of nodes makes it a must that the information be exchanged continuously in order to have updated information about the current state of the network. Furthermore, distributed implementation of evolutionary algorithm should lead with scarcity of resources since mobile wireless portable devices have generally lower resources compared with laptops or PCs. The main advantage of a distributed implementation is that the algorithm is run online, so the nodes can adapt to the local varying conditions of the network.
In general the performance of mobile wireless multihop networks is conducted by using a set of performance metrics that determine the quality of the algorithms under development. For example, when evaluating routing protocols for VANETs and MANETs the performance metrics most used are the Packet Delivery Fraction (PDF) that accounts for the ratio of received and transmitted packets, the Normalized Routing Load (NRL) that measures the routing load, and the End-to-End (E2E) Delay that calculates the time elapsed since a packet is sent until it is received by the destination. These performance metrics are counterbalanced. For example, increasing the PDF, which is desirable, by sending more routing packets will also increase the NRL and E2E metrics, which is not desirable. Using a multiobjective optimization algorithm will allow the designers to have all the possible solutions and to determine which parameters affect the performance metrics at a glance (Pareto Front). Similarly, in DTNs the most used performance metrics, such as the hit rate, delivery cost, and delivery latency, are also counterbalanced. It is worth mentioning that the application of a multiobjective optimization algorithm is more suitable than weighting the performance metric in just one expression. This is because in such case one performance metric can dominate the solution, hiding the influence of the other performance metrics on the fitness function.
Most of the work done in DTNs has been related to data dissemination. However, forwarding algorithms and mobility models are also two topics that pose many challenges. Forwarding algorithms differ from data dissemination algorithms. In forwarding algorithms, the objective is to send a piece of information to a destination node. On the contrary, in data dissemination algorithm the objective is to disseminate the information throughout the network or a set of nodes in the network. Evolutionary algorithms can be used to optimize forwarding algorithms in a similar way of that done for data dissemination algorithms. Regarding mobility models, the objective is to model the mobility of people considering both geographical and social context based information.
Moreover, there is an emergent field in the area of ad hoc networks related to the tactical movements of nodes, especially when nodes represent UAVs (Unmanned Aerial Vehicles). In this case, multihop ad hoc networks can be used to share information and plan a movement law according to the collected information. This new type of mobile multihop ad hoc network will pose new challenges in the design of mobile networks since they present particular features like high and free mobility in 3D. In addition, currently the autonomy of UAVs is very short. Consequently, new communication protocols tailored for UAVSs should take into consideration such limitation.
Finally in some cases the use of local search algorithms like simulated annealing, hill climbing, and tabu search algorithms after applying an evolutionary algorithm can improve the global solution. The idea is to explore the surrounding areas of the optimum solutions obtained by the evolutionary algorithm.
6. Conclusions
This survey paper has focused on a promising research field such as the application of evolutionary algorithms for optimization problems in multihop ad hoc networks. We have presented the main features and restrictions that should be taken into consideration for the use of evolutionary algorithms in mobile multihop ad hoc networks. In addition, we have reviewed the main works found in the research literature, highlighting the main challenges that require further research. We believe that the use of evolutionary algorithms in mobile multihop ad hoc network is still in an early stage of research. In the near future, the application of more powerful and distributed evolutionary algorithms will be possible thanks to the increment of computational power of embedded electronic devices.
Footnotes
Conflict of Interests
The authors declare that there is no conflict of interests regarding the publication of this paper.