| Joe Fiala (A paper written under the guidance of Prof. Raj Jain) |
Download |
As the demands of wireless communication continue to increase, bio-inspired algorithms (BIAs) are gaining popularity due to their capacity to adapt, evolve, and survive a variety of both expected and unexpected circumstances, as well as their inherent ability to expand in complexity and focus on both global and local management. This paper explores a number of the most common BIAs — including genetic algorithms (GAs), ant colony optimization (ACO), and artificial bee colony (ABC) — and it also highlights popular usage of each of the aforementioned bio-inspired algorithms within the scope of wireless communication.
bio-inspired, bio-inspired algorithm, wireless communication, genetic, ant colony, artificial bee colony
In response to the continued demands of contemporary networking, bio-inspired algorithms (BIAs) have emerged as feasible solutions to many of the problems at hand. In the following paper, I provide a brief survey of the more popular bio-inspired algorithms used in wireless communication. The structure of this paper is as follows: First, I briefly outline BIAs, more generally, and state the primary motivations cited for using BIAs. I then turn to an examination of three of the most commonly implemented BIAs: Genetic Algorithms (GAs), Ant Colony Optimization Algorithms (ACOs), and Artificial Bee Colony Algorithms (ABCs). Although these three BIAs are only a small subset of the many BIAs currently utilized, they offer an accessible and integrated introduction to the capabilities of BIAs pertaining to wireless communication. Once all three algorithms have been discussed, I proffer a brief section outlining other BIAs that are either similar or dissimilar to those three algorithms already discussed in prior sections in order to facilitate additional interest and activity within this field.
To better understand why BIAs are being used more frequently in wireless communication, it is helpful to both define "BIA" and sketch why one might choose to use a BIA over other, more traditional, algorithms or solutions. Consequently, this section is divided into two subsections, which answer the aforementioned two concerns. The hope is to set forth sufficient groundwork to continue our examination in further sections.
In this section, I offer a broad definition of BIA, as well as a brief discussion of the scope in which BIAs are being used, in order to facilitate a general understanding both of what constitutes a BIA as well as where one might find a BIA in use.
Essentially, a BIA is an algorithm that takes inspiration from biological phenomena in order to aid in computation. What this means is that it is an algorithm designed to mimic the complexities and optimization found in natural phenomena in order to solve computationally similar problems. Additionally, BIAs are most commonly separated into two groups: evolutionary algorithms (EAs) and swarm intelligence (SI) algorithms. The main distinction between these two groups is that EAs are more commonly inspired by evolutionary phenomena, such as reproduction and mutation, whereas SIs are more commonly inspired by local agents working in an environment ("swarming") to produce a type of global intelligence, such as ant colonies and bee colonies [Jamalipour09].
As far as usage, BIAs are found in the fields of computing, systems, and networking, leading to the appropriately named fields: bio-inspired computing, bio-inspired systems, and bio-inspired networking [Dressler10b]. Furthermore, these fields are not mutually exclusive, but can overlap with one or more of the other bio-inspired fields (see Figure 1). For the purposes of this paper, however, we will only be focusing on BIAs as they relate to bio-inspired wireless communication, which occupies only a subsection of the diagram illustrated in Figure 1 (i.e. bio-inspired wireless communication may lie within any of the areas covered by bio-inspired networking, including those overlapping with bio-inspired computing and/or bio-inspired systems).
This section has provided a broad overview of what constitutes a BIA as well as a glimpse into the fields in which BIAs are currently being used. Furthermore, it has detailed where the field of bio-inspired wireless communication lies within the aforementioned fields. In the following section, I will explain why BIAs are used in place of other, more traditional algorithms, particularly in the field of bio-inspired wireless communication.
The purpose of this section is to provide an explanation of why BIAs are used for bio-inspired wireless communication rather than other, more traditional, algorithms. Although further motivations may exist, I will outline only the following six motivations: (i) adaptivity, (ii) robustness, (iii) complexity, (iv) evolution, (v) management, and (vi) survivability, which are the most commonly cited motivations in the relevant literature [Binitha12][Dressler10a][Dressler10b].
Here, I have outlined the motivating factors in using BIAs for wireless communication. (Additionally, it should be noted that the above motivations are not mutually exclusive, but are often mutually beneficial.) In the following sections, these factors will pop up again as we see the various usage of BIAs in wireless communication, particularly in discussions of why BIAs are superior to other solutions.
At this point, I have provided a brief, but sufficient background into the nature of BIAs, both in terms of what constitutes a BIA as well as the ways in which BIAs are particularly applicable. Furthermore, from the motivations listed in Section 2.2, we now also have a way of identifying which future problems may benefit from using BIAs. Going forward, I will assume this basic knowledge of BIAs to be given; this allows me to now turn to an outline of the most popular BIAs currently in use.
The first type of algorithm we will outline is the GA, a type of EA. This section will contain a brief background of GAs, an outline of its execution, and a description of contemporary uses of GAs in wireless communication.
Developed by John Holland [Holland73], GAs are a type of EA that aim to provide solutions to optimization problems, much in the same way as can be found in the process of natural selection within an environment. The basic process of a GA can be broken into the following steps:
Once a problem has undergone the Initialization, Selection, and Mutation steps, the algorithm then checks to see if the Termination condition(s) has been satisfied. If it has, then the process proceeds to the Termination step and exits. Otherwise, the process loops over the Selection and Mutation steps, but uses the resulting population (rather than the initial population). This is repeated until Termination condition(s) are met.
This section will focus on the usage of GAs in wireless communication. It is divided into three subsections — (i) Wireless Node Placement, (ii) Bandwidth Allocation, and (iii) Channel Assignment/Allocation — each providing a brief discussion of the usage of the algorithm.
As a result of the simplicity of setup for GAs, as well as its ability to adapt to varying circumstances, GAs have been popularly used to plan wireless mesh networks (WMNs) using max-min distribution and evaluation of node positions, routing configurations, and channel assignments. Such planning has shown marked improvement over other standard methods, such as greedy algorithms, averaging between 15% and 20% improvement in terms of throughput (and as much as 200% improvement in some cases). Pries10] Furthermore, GAs have also been used to compute optimal placement of mesh router nodes to ensure connectivity. In such cases, GAs have demonstrated the ability to not only maximize geographic coverage with a set number of mesh router nodes, but also consolidate within a particular geographic coverage to optimize connectivity [Xhafa10].
Additionally, in combination with game theory, GA can be utilized as a means for Mobile Ad-hoc Network (MANET) nodes to maximize optimality in terms of network area coverage (defined as a ratio of the area covered by the range of nodes to the total geographic area covered). Thus, a ratio 0f 0.5 implies that half of the area is covered and a ratio of 1.0 implies the whole area is covered. To see how this algorithm progresses, consider the Figure 2 below (adapted from [Kusyk11]'s Figures 4, 5, and 6):
As shown in the figure above, a ratio of 1.0 is achieved by 60 iterations (and in fact, was achieved by ~40 iterations, on average) [Kusyk11]. This demonstrates not only an ability for GAs to adapt to the extreme networking demands of MANETs, which often involve high speed nodes and varying number of targets, but also the ability to make such changes quickly, which is essential to the success of any MANET.
Furthermore, GAs have also proven to be particularly effective when dealing with adversarial situations, such as when particular nodes are destroyed or otherwise rendered inoperable. In tests simulating military conflict, GAs were able to effectively distribute and redistribute nodes within a MANET even after particular nodes had been destroyed by "enemy combatants". More specifically, the nodes were able to achieve 95% coverage after 400 steps. Following an attack reducing the total number of nodes from 70 to 66, it took 150 additional steps to achieve 92% coverage. In more extreme cases, even after 15% of the total nodes have been destroyed, the algorithm was still capable of producing greater than 90% coverage, a remarkable feat demonstrating the resilience and survivability of GAs as a whole [Sahin08].
Gas are also effective at handling varying bandwidth needs. An example of its effectiveness is found in the medical community, where certain patients require different bandwidth allocations depending on their varying needs (set by a patient priority level). It has been shown that the use of GAs, with regard to quality of service (QoS) requirements (for both patients and practitioners), greatly reduces computation time, serving to increase QoS across the board. Furthermore, GAs are computationally quicker across all tested tolerable relative error thresholds, displaying absolute computational speed dominance [Lin12a].
For more general usage, GA has also proven to be an efficient optimization approach for residual bandwidth allocation. This is particularly apparent in medium to large sized networks, where routing links for multiclass traffic can be shown to be particularly beneficial. Indeed, in all tests performed by [Kandavanam10], the GA used found an optimum or near optimum solution of bandwidth allocation to maximize QoS. This demonstrates the ability of GAs to work in scale, allowing for applicability in a wide array of larger networks, too.
Another use of GAs is to solve channel assignment and channel allocation problems. This is most commonly seen being used for Cellular Radio Networks (CRNs), where the goal is both a conflict free channel assignment as well as minimum interference and minimum channel span.
Indeed, as seen in [Zhenhua10], GAs has been proven effective at obtaining conflict free channel assignment even under the constraints of traffic demands and electromagnetic compatibility. In particular, the algorithm proved to have a high convergence rate, especially compared to competitors, as illustrated by the table below (where CR = convergence rate and ACG = average convergence generation).
| Problem No. | Benchmark CR #1 (%) | Benchmark CR #2 (%) | Modified GA CR (%) | Modified GA ACG |
| 1 | 100 | 100 | 100 | 0 |
| 2 | - | 93 | 100 | 172 |
| 3 | 92 | 79 | 100 | 239 |
Not only did the modified GA outperform both competitor algorithms by achieving a 100% convergence rate in all problems tested, it also achieves convergence within a reasonable number of generations (172 and 239 for Problem No. 2 and 3, respectively). Additionally, the number of additional generations required for further adaptation between Problem No. 2 and 3 highlights the adaptability of GAs, thereby promoting their ability to handle both scalability and novelty in a variety of circumstances.
Furthermore, in the cases in which the frequency spectrum is limited, but with sufficient demand, channel allocation becomes particularly important. To obtain a conflict free allocations with minimum interference in such situations (an NP-hard problem) GAs are often used due to their heuristic efficiency. In fact, GAs have shown the ability to solve both dynamic and fixed channel allocation problems in multi-cell CRNs with quick convergence, even in higher population systems, again outlining their value in networks of sizable scale [Pinagapany08].
This section outlined the usage of GAs in terms of wireless node placement, bandwidth allocation, and channel assignment/allocation. For all cases examined, the GA used not only was capable of meeting the demand(s) of the network, but often proved to be indispensable due to its inherent ability to adapt, evolve, survive, and scale in a variety of circumstances and scenarios.
Another popular algorithm, and the first of the SI algorithms discussed, is the ACO algorithm. This section will contain a brief background of the ACO algorithm, an outline of its execution, and a description of contemporary uses of ACO in wireless communication.
Based on stigmergy, and, in particular, on the behavior of ants, Marco Dorigo developed ACO in as part of his thesis work [Dorigo92] (and also expanded upon in association with Alberto Colorni and Vittorio Maniezzo [Colorni91]). Essentially, ACO can be broken down into the following steps:
In ACO, the Construction, Pheromone Update, and (potentially) Daemon Actions steps are repeated continuously until the Termination step is met. At each iteration, the possible trails are evaluated, with the better trails leaving stronger pheromones and the worse trails leaving continually weaker pheromones, thereby converging at the optimas for the solution set.
This section will focus on the usage of ACOs in wireless communication. It is divided into two subsections — (i) Energy Efficiency and (ii) MANET Routing — each providing a brief discussion of the usage of the algorithm.
An important issue in wireless sensor network (WSN) implementation is the issue of energy efficiency, and, in particular, energy efficiency without sacrificing coverage. In order for this to be achieved, ACO algorithms are often used to either reduce CPU time or reduce the number of redundant devices.
In using ACOs to reduce CPU time, [Lin12b] found satisfactory solutions to 20 of the 33 tested networks within 1 second. For 12 of the remaining 13 networks, solutions are found within 1 minute, with only a single test network taking longer than 1 minute to produce a solution (primarily due to large scale and small redundancy in the test network).
| Case No. | Time (sec.) | Case No. | Time (sec.) | Case No. | Time (sec.) |
| A1 | 0.06 | B1 | 2.01 | C1 | 0.95 |
| A2 | 0.03 | B2 | 0.03 | C2 | 1.01 |
| A3 | 0.13 | B3 | 0.12 | C3 | 0.42 |
| A4 | 0.07 | B4 | 0.06 | C4 | 14.36 |
| A5 | 0.26 | B5 | 0.41 | C5 | 54.59 |
| A6 | 0.07 | B6 | 0.03 | C6 | 0.05 |
| A7 | 0.25 | B7 | 0.18 | C7 | 2.80 |
| A8 | 0.59 | B8 | 0.57 | C8 | 164.59 |
| A9 | 0.18 | B9 | 33.85 | C9 | 0.23 |
| A10 | 10.41 | B10 | 1.00 | C10 | 47.40 |
| A11 | 1.78 | B11 | 26.37 | C11 | 5.11 |
In addition to reducing CPU time, the ACO algorithm used by [Lin12b] proved to be extremely effective at an finding optimal solution for the test networks, especially compared to the competing greedy algorithm.
| Optimal Solution (%) | Optimal Solution (%) | Optimal Solution (%) | ||||||
| Case No. | ACO Algorithm | Greedy Algorithm | Case No. | ACO Algorithm | Greedy Algorithm | Case No. | ACO Algorithm | Greedy Algorithm |
| A1 | 100 | 0 | B1 | 100 | 0 | C1 | 10 | 0 |
| A2 | 100 | 87 | B2 | 100 | 0 | C2 | 100 | 0 |
| A3 | 100 | 90 | B3 | 100 | 37 | C3 | 100 | 0 |
| A4 | 100 | 43 | B4 | 100 | 0 | C4 | 100 | 0 |
| A5 | 100 | 13 | B5 | 100 | 0 | C5 | 80 | 0 |
| A6 | 100 | 90 | B6 | 100 | 0 | C6 | 100 | 0 |
| A7 | 100 | 87 | B7 | 100 | 37 | C7 | 10 | 0 |
| A8 | 100 | 87 | B8 | 100 | 10 | C8 | 63 | 0 |
| A9 | 100 | 0 | B9 | 100 | 0 | C9 | 0 | 0 |
| A10 | 100 | 0 | B10 | 3 | 0 | C10 | 0 | 0 |
| A11 | 100 | 0 | B11 | 100 | 0 | C11 | 0 | 0 |
As seen from the above table, the ACO algorithm proved to be at least as fast as the competing greedy algorithm in computing an optimal solution and, in the vast majority of cases, proved to be significantly faster. Indeed, in only 4 of the 33 test cases was the Optimal Solution (%) for the ACO algorithm less than 10% higher than the greedy algorithm; and in 15 of the 33 test cases, the ACO algorithm had an Optimal Solution (%) value of 100% while the greedy algorithm had an Optimal Solution (%) value of 0%.
The effectiveness of an ACO algorithm for energy efficiency is further corroborated by [Lee11], where the lifespan of a test WSN was measured based on varying numbers of sensors and points of interest (PoIs).
| Scenario | Avg. Network Lifetime (cycle) | ||
| # of Sensors | # of PoIs | Greedy Algorithm | ACO Algorithm |
| 100 | 10 | 31 | 31.7 |
| 150 | 10 | 67 | 68.2 |
| 200 | 10 | 105 | 105.5 |
| 100 | 30 | 24 | 25.8 |
| 150 | 30 | 45 | 46.4 |
| 200 | 30 | 60 | 62 |
Indeed, although the results are not as drastic as those found in [Lin12b], the ACO algorithm displays absolute dominance in terms of average network lifetime across all measured factors.
Due to the inherently mobile nature of MANETs, and in conjunction with the lack of central control, the task of delivering packets successfully to the destination with minimum loss, minimum delay, and maximum packet delivery ratio requires efficient and flexible routing algorithms, for which ACOs are often used.
In a study performed with Vehicular Ad-Hoc Networks (VANETs) — a special type of MANET — researchers found that algorithms using ACO consistently and drastically outperformed the algorithms using Ad-Hoc On-Demand Distance Vector (AODV) Routing, a standard routing protocol for MANETs. In [Correia11]'s study, which compared the routing overhead to the number of vehicles for each of the two algorithms, it was found that as the number of vehicles grew from 25 to 150, the routing overhead for AODV jumped from ~1 to ~12, whereas for ACO the routing overhead only grew from ~1 to ~1.5-3 (depending on the implementation used).
In another study, which compares the performance of an ACO-based algorithm, Multi Agent Ant Based Routing Algorithm (MAARA), to other standard algorithms — AODV, AntHocNet, and Dynamic Source Routing (DSR) — it was found that while all aforementioned algorithms performed similarly with regards to packet delivery ratio as the number of nodes increased, MAARA was the clear winner in terms of average end-to-end delay as the number of nodes increased and packet delivery ratio with increasing pause time.
From the above graphs, MAARA shows clear dominance over the other algorithms, except for a small window in the Average end-to-end delay graph (~150 nodes to ~200 nodes) in which MAARA is briefly bested by the AntHocNet algorithm. Furthermore, in the same graph, as the number of nodes continue to increase, MAARA's path implies continued dominance over the other algorithms, which all have at least 0.1 average end-to-end delay greater.
This section outlined the usage of ACOs in terms of energy efficiency and MANET routing. In the cases cited, the ACO algorithms used not only extended the lifespan of the networks, but also helped to increase QoS by maximizing packet delivery ratio while also minimizing loss and delay. This serves to demonstrate the great capacity for ACOs to adapt and manage even in the most complex networks.
The next SI algorithm, which also focuses on foraging, is the ABC algorithm. This section will contain a brief background of the ABC algorithm, an outline of its execution, and a description of contemporary uses of ABCs in wireless communication.
Similarly based on foraging behavior, but this time with honeybees, is the ABC algorithm. Proposed by Dervis Karaboga [Karaboga05] and later added to in association with Bahriye Basturk [Karaboga07], ABC first divides the artificial "bees" into groups — employed bees, onlookers, and scouts — each with their own duties. The algorithm then proceeds in the following steps:
Once the Initialization step is completed, the algorithm repeats the Update step until the Termination condition(s) is met, at which point the algorithm exits.
This section will focus on the usage of ABCs in wireless communication. It is divided into two subsections — (i) Energy Efficiency and (ii) Sensor Deployment — each providing a brief discussion of the usage of the algorithm.
As it has already been stated in the section about energy efficient uses for ACO, WSNs are greatly dependent on the ability to minimize energy expenditure to increase their lifespan. Similar to ACO, ABC can also be used to prolong the lifespan of a WSN and maximize energy efficiency.
In one study comparing the results of ABC routing versus Leech communication or Direct communication strategies, researchers found that the network that utilized ABC routing was capable of a much longer lifespan than the competitors, as seen below.
Essentially, whereas the Leech communication and Direct communication strategies were capable of only receiving ~2000 and ~6000 items, respectively, the ABC routing strategy was able to receive ~9000 items, due to its prolonged lifespan.
However, the energy efficient uses of ABC are not just restricted to WSNs. As can be seen in a study by [Mohan11], ABC has proven to be greatly valuable in MANET functionality, too. In this study, it was found that ABC routing outperformed all other competitors — including Destination Sequenced Direct Routing (DSDR), DSR, AODV and even ACO — in terms of response time and throughput. Furthermore, it was also shown that the ABC algorithm was benefitted by low running overhead and a lesser number of parameters required, which served to increase energy efficiency and decrease network traffic.
As WSNs are becoming increasingly more common, the problem of proper sensor deployment gains proportional stature, since proper sensor deployment is vital to the coverage (and therefore the overall QoS) of any WSN. As a result, ABC algorithms have been utilized for effective and dynamic employment of sensors.
In a study by [Ozturk11], wireless sensors are deployed as part of a WSN using a combination of ABC and probabilistic models (to further enhance the ABC algorithm). The algorithm is then run a scenario 30 times, with each of the 1000 iterations having random initialization. For comparison, a particle swarm optimization (PSO) algorithm is also run under the same scenario, with the following results:
| Initial Coverage | PSO Coverage | ABC Coverage | |
| Mean | 0.7436 | 0.9368 | 0.9601 |
| Std | 0.0224 | 0.0128 | 0.0078 |
| Best | 0.7888 | 0.9581 | 0.9752 |
| Worst | 0.6975 | 0.9094 | 0.9365 |
As can be seen in the table above, both PSO and ABC strictly outperform the initial coverage produced by the random deployment of sensors by a large margin. However, perhaps more surprising is that ABC also strictly outperformed PSO by a significant margin. The differences between the Mean, Best, and Worst Coverage for PSO and ABC are 0.0233, 0.0171, and 0.0271, respectively.
In another study, in which ABC was used to test wireless sensor deployment in a 3D region (specifically 1000x1000x20 units), researchers further supported ABC's ability to maximize coverage in a WSN, as can be seen in the figure below.
Compared to the initial, random placement of sensors in the 3D region, the placement of sensors resulting from the ABC algorithm shows a much more compact and centralized method of placement in order to maximize coverage among the targets. Indeed, this result is further corroborated by their examination into the required sensing range of each sensor in environments with varying numbers of targets and available sensors. The ABC algorithm yielded sensor placement that allowed for required sensor range to be cut by at least 50% as the number of sensors grew from 10 to 50, even as the number of targets increased, both in the best results and mean results [Mini10].
This section outlined the usage of ABCs in terms of energy efficiency and sensor placement. According to the relevant research, ABCs were capable of maximizing energy efficiency by optimizing the routing paths used in WSNs and MANETs (even outperforming an ACO algorithm in the tests). Furthermore, ABCs also proved valuable in terms of sensor placement by being capable of maximizing coverage and reducing redundancy in both 2D and 3D tested regions. This highlights the abilities of ABCs to adapt and manage even in robust and complex networks, and even in adversarial situations.
In this paper, I have provided a brief background into BIAs, particularly GAs, ACOs, and ABCs. In addition to this, each of the algorithms discussed was supplemented with a discussion of its usage in contemporary wireless communication, with particular emphasis placed on the advantages of using a BIA over other, more standard, algorithms or solutions. As the research has shown, the algorithms discussed showed remarkable capabilities in the following areas: (i) adaptivity, (ii) robustness, (iii) complexity, (iv) evolution, (v) management, and (vi) survivability, which serve as the primary motivators for using BIAs.
Although GAs, ACOs, and ABCs are among the most commonly used BIAs, they are only a small subset of the current BIAs in use in wireless communication. For more EAs (i.e. algorithms like GAs), consider Genetic Programming (GP), Evolution Strategies (ES), and Differential Evolution (DE) algorithms. For more SIs (i.e. algorithms like ACO and ABC), consider PSO, Fish Swarm (FS), Intelligent Water Drops (IWD), Artificial Immune System (AIS), Firefly, and Shuffled Frog Leaping (SFL) algorithms.