1. INTRODUCTION

Small sensors constituting a wireless sensor network (WSN) have functions for detecting various forms of information, such as light, sound, temperature, and pressure; processing the detected information as needed for a certain purpose; and transmitting it to a base node [1–3]. Owing to the capabilities of these sensors, WSNs are used in various scenarios in fields such as environmental surveillance, disaster prevention, and healthcare [4,5]. However, despite these features, cases often arise where the sensors cannot be recharged. Thus, path techniques for maximizing network lifespan have emerged as an important area of research [6,7]. Research has focused on efficient routing techniques for large-scale networks that apply biomimicry algorithms modeled on the behavioral principles of various organisms [8–10].

Unlike top–down centralized control methods, which control the behaviors of entities en masse, biomimicry algorithms are bottom–up distributed processing algorithms in which each entity independently performs simple movement to create a consistent overall form [11,12].

Pheromones are excretions used by animals of the same species to communicate. These are a substance similar to hormones, and act to strongly attract other entities of the same species. Ants can be seen as a typical example [13]. Pheromones are also excreted by bees and other insects. It is clear that they play a significant role in communication and recognition among animals [14].

When ants find the shortest path to a destination, they exchange information in an indirect manner through pheromones. If an ant leaves a trail of pheromones along a path it has taken, other ants travelling along the path choose their route according to the strength of the pheromones that were left. If it is a path that has been traveled by several ants, the pheromones are strong, and the likelihood that the path is an optimal one is high. Once the path is determined, the ants all move along the optimal path along which the pheromones are concentrated. Moreover, if an intruder enters the ants’ territory or nest, they sound a chemical alarm. An ant that discovers the intruder immediately excretes and spreads an alarm pheromone, and other worker ants soon assemble at the site of the incident, surrounding the intruder and attacking its legs and antennae. These pheromones are very volatile such that in a short time they are quickly propagated throughout the colony [15].

If humans use these functions to create an algorithm based on natural principles and structures in organisms instead of mere trial and error, they can find answers to problems similar to ones faced by these organisms.

Biomimicry algorithms have mainly been applied to optimization algorithms, among which the ant colony optimization (ACO) algorithm, which is modeled on the process of ants finding optimal paths based on the excreted pheromones, offers an efficient routing method for complex tasks by using the average values of nearby information of entities in a large-scale network [16–18].

In this paper, we propose a technique for selecting optimal paths and improving energy efficiency in a WSN by using the ACO algorithm, which is a biomimicry algorithm. The basic design requirements of the proposed network are as follows:

1. Sensors have a limited amount of energy. Thus, the routing algorithm must be designed to find energy-efficient paths to extend the network's lifespan.

2. In addition, the routing algorithm for the WSN must be designed so that it can operate many sensors for a long time by distributing data throughout the network.

In this paper, we qualitatively analyze the similarities between communications and biological systems to show that biomimicry algorithms can serve as a solution for the major problems in communication networks, i.e., path selection and energy efficiency. We designed a set of algorithms called WSN based on Biomimicry Algorithms (WiBiA) based on the ACO algorithm, which is the main biomimicry algorithm used in communication networks.

The remainder of this paper is organized as follows: Section 2 describes the ACO algorithm, which forms the basis for WiBiA. Section 3 presents the design of the network model to find the optimal solution to the problem. In Section 4, we analyze the model by using the experimental results. Section 5 contains the conclusions of this study and directions for future research.

2. ACO ALGORITHM

For ants to build homes and thrive, a large number of worker ants are needed. The skills of the harvester ants depend on a mechanism that controls the frequency of finding food. It has a function similar to an Internet data-management algorithm. This phenomenon has attracted the interest of scientists and led to research on optimization and control algorithms that use the swarm intelligence of ants.

In this paper, we focus on the method of indirect information transmission through pheromones in the ACO algorithm. Topological changes owing to the mobility of sensor nodes lead to changes in routing and multicasting paths, and these changes must be frequently detected for efficient data transmission. However, there are many challenges in the transmission of this information to each node owing to small bandwidth and power problems [19,20].

This kind of ACO algorithm mimics the food transport behavior of sightless ant groups, which move their food far from their home through the fastest route. This has been applied to various optimization problems, such as communication networks, scheduling problems, moving body path exploration, and task assignment problems [21–23].

As shown in Figure 1, if an ant finds food (F), it follows the pheromones left along the path (a) that it had taken to the food and carries (b) the food to the nest (N). If the ant colony tries carrying food in this manner along several paths, a large amount of pheromones accumulate along the shortest path between the nest and food. Ants have a tendency to select and move along paths with the largest amount of pheromones. Thus, once a certain amount of time has passed, the entire colony carries food along the shortest path. If the given amount of pheromones between points i and j is τij, the pheromone evaporation rate is ρ, number of ants moving from i to j is m, and the amount of pheromones excreted along the path by the kth ant is Δτijk. Further, the amount of pheromones τijk along the path from i to j after a certain time is defined as follows:

Figure 1

Ant colony optimization algorithm.

Ants determine where they will move to next according to the amount of pheromones, as calculated through Eq. (1). The ants do not return to their source by the same path, instead select their destination within a one-hop distance. If a position within a one-hop distance that has not been visited by the kth ant is l, a collection of these positions is Nsp, and the heuristic information is μij; then, probability Pij k that the kth ant will move to the next path j when it arrives at position i is determined as follows:

When the distance from i to j is dij, heuristic information μij is defined as 1/dij, and α and β are parameters that assign weights to the amounts of pheromones and heuristic information, respectively. Therefore, as the amount of pheromones increases and the distance decreases, the probability of moving via the given path increases.

3. WiBiA

Although the ACO algorithm is well known as a method suitable for selecting the optimal path in packet routing, it has the drawback of stagnation [24,25]. It also lowers the probability of selecting other paths, thus causing congestion along the optimal path. As such, the path would no longer be optimal, and the overall energy consumption of the network increases. Therefore, in this paper, we propose the congestion-free algorithm (CFA) with the intention of designing an efficient WSN and overcoming problems that occur when using biomimicry algorithms.

3.1. CFA

As the path along which ants travel reaches the shortest path, a large amount of pheromones accumulate along it, and it is thus recognized as close to the shortest path and selected by ants. However, this kind of path setting leads to congestion in WSNs, and the limited amount of energy of the sensor nodes along the optimal path is exhausted.

The goal of the CFA proposed in this paper is to allow nodes to resolve their own congestion and prevent excessive battery consumption in a WSN environment where network resources are limited.

The existing ad hoc on-demand distance vector (AODV) protocol possesses a mechanism to set new paths and paths with the smallest delays whenever the network topology changes in an environment with high node mobility. It can, therefore, be said to naturally achieve a balance in data traffic [26].

However, the typical environment in which appropriate traffic distribution has not been achieved is one where node mobility is low and the density between nodes is high. Even if traffic congestion occurs, a mechanism for setting new paths is not available, because of which node congestion gradually worsens, and results in an increase in end-to-end delays, which can degrade network performance.

To resolve these problems, in the proposed CFA, once a node determines that excessive traffic is being sent to it, it can transmit a pheromone-PULL message to the source node to inform about its intention to reject further data relays so that nodes that receive this message can set new detours. Moreover, the node that transmits the pheromone-PULL message does not relay route request (RREQ) messages arriving from nearby nodes, thus blocking the setting of a new path through the node.

Figure 2 shows a situation where congestion occurs because excessive traffic is concentrated on Node A and the actions of the CFA to resolve this issue. Node A is a relay node along the data paths of pairs [S₁, D₁], [S₂, D₂], and [S₃, D₃]. If the amount of traffic sent to Node A reaches a predefined threshold, Node A shifts to a pheromone-PULL state by transmitting a pheromone-PULL message. The message is sent to the source node that sent the last data packet to Node A (assumed to be S₂ in the figure) to request that a different detour be set. Node S₂ receives the pheromone-PULL message and broadcasts an RREQ to set a new path to Node D₂, and the mechanism of setting the new path is activated.

Figure 2

Basic concept of congestion-free algorithm.

If node S₂ successfully completes the setting of a new detour, and data transmission via the new path through Node B begins, the path containing Node A is no longer used. The corresponding entry timer thus expires, and is naturally deleted from the routing table. Node A, which is in a pheromone-PULL state, does not provide packet relay service for RREQ messages sent by S₂ or any other node. The setting of new paths that pass through Node A is thus blocked. In this pheromone-PULL state, if the congestion situation of Node A improves and the amount of traffic falls below a given threshold, the node shifts back into a normal state. Table 1 shows the operational process described so far.

Algorithm 1: CFA

[When the node A receives a packet] if RREQ message in a packet if the node A is in pheromone-PULL state ignore the packet else process the packet using the existing routing algorithm else if pheromone-PULL state if the pheromone-PULL state is destined to the node A initiate the route discovery mechanism of the existing routing algorithm else forward the packet with the alternative route [At the end of a time interval] if # of forwarding packets for the time interval ≥ threshold change the state to pheromone-PULL send a pheromone-PULL message to the src. of last received packet if # of forwarding packets for the time interval < threshold change the state to normal

CFA = congestion-free algorithm; RREQ = relay route request.

Table 1

Operational process of CFA.

The CFA proposed in this paper considers the limitations of WSNs and focuses on resolving node congestion by balancing traffic. It can resolve the problem of traffic concentration on a particular node, whether node mobility is high or low, and can support load-balancing features through the addition of a simple module to existing routing protocols.

3.2. Alternative Route Algorithm

Alarm pheromones are released by social insects (ants, honeybees, etc.) to alert fellow insects when their habitat is attacked by an enemy. They require urgency and are strongly diffusible. By applying these properties to path restoration techniques in WSNs, we can resolve the problem in the proposed protocol: setting optimal paths for moving nodes [27].

The proposed technique focuses on reducing the number of RREQ messages broadcast. To do this, the technique does not use a method of restoring paths when a disconnection occur, instead predicts disconnections and substitutes new paths for old ones. Figure 3 shows the prediction process. In the Node S₂ to Node D₂ path maintenance process, a disconnection was predicted between Nodes [B, G] because Node B moves. This prediction is made by detecting the packet transmission power when data packets are transmitted or messages are exchanged during the path maintenance process. The value of the alternative threshold power is set to a parameter for predicting disconnections, and the received power from Node G is compared with the threshold power ratio; if it is smaller than or the same as the alternative threshold power, an alternative route is specified. When Node B generates an RREQ message to find an alternative route, unlike in AODV path restoration, the Time To Live (TTL) value of the RREQ message is set to one and the RREQ message is sent only to nodes within its own wireless transmission radius. This RREQ message requests a route reply (RREP) message from Nodes A and G, which are nodes along the active path, regarding nodes within the transmission radius. This is depicted by Node G in Figure 3.

Figure 3

Prediction process for disconnection.

Figure 4 shows the actions of Node C, which has a transmission radius including Nodes A and G among those receiving the RREQ message. Node C, which is satisfied with the received RREQ message, updates its own routing table, generates an RREP message with a TTL value of one, and broadcasts it. Node B, which generated an RREQ message, receives this RREP message, deletes existing active paths in its own routing table, and moves out of range. Nodes A and G, which did not generate RREQ messages, receive the RREP message and recognize that the alternative route goes through Node C; they update their own routing tables and maintain the active path, S₂-A-C-G-E-D₂.

Figure 4

The discovery process for alternative route.

To set alternative paths, the formats of the RREQ and RREP messages in AODV were extended, as shown in Figure 5.

Figure 5

Proposed relay route request (RREQ) message format.

It shows the addition of flag A and the superior node IP address of the active path in the RREQ message. Flag A is the alternative flag specifying that it is not an existing-path-request message but an alternative-path-request message. If flag A is set, the hop count is unconditionally set to one, and the destination address is substituted by the IP address of the hop where disconnection is expected. The previous address of the active path was also added.

Figure 6 shows the addition of flag A to the RREP message to confirm that it is an alternative-path reply message. The node receiving the RREQ message checks the previous address of its active path and the expected disconnection address, and compares these addresses with information about its own neighborhood. The node then creates an RREP message in case a matching address is found. The IP address of the node transmitting the alternative-path request is added and if the node receiving the RREP message includes this address in its own routing table along the active path, it is updated with the address that generated the RREP message to delete this address.

Figure 6

Proposed relay route request (RREP) message format.

4. PERFORMANCE EVALUATION

In the simulations, we compared the WiBiA protocol proposed in this paper and the low-energy adaptive clustering hierarchy (LEACH) protocol, which uses highly energy-efficient routing in WSNs [28] by using Network Simulator-2 (NS-2) [29].

To execute a simulation using the proposed algorithm, we randomly distributed 500 nodes in a square area with sides of 1000 m (W). Here, the node's communication radius was determined to be 2W/n. By considering a network topology in which all nodes can connect to a multihub, the send/receive scheduling for data aggregation was assumed to be perfect, and no collisions or transmission errors were observed. All nodes periodically generated 100 Kbits of sensing data. The channel bandwidth was assumed to be 100 kHz, and the power used to send and receive messages was assumed to be 100 mW.

For the simulation environment, the distributed coordination function of IEEE 802.11 was used in the wireless LAN for the MAC layer protocol. After setting the constant bit rate for transmission of the packet traffic, the simulation experiment was performed for 600 s while changing the pause time from 0 to 600 s.

The pause time of the node implies the node starts to move again to a random direction after a specified pause time. Zero pause time implies that the node is continuously moving, and a larger pause time indicates lower mobility of the node. This is calculated to evaluate the performance ability of the protocol according to the node mobility in the ad hoc network.

Figure 7 shows the number of active nodes during the simulation in LEACH and the proposed WiBiA. In the case of LEACH, the energy consumption of all nodes was unbalanced, and the time at which energy was exhausted was not fixed, and thus the number of active nodes rapidly decreased. On the contrary, in the case of WiBiA, all nodes consumed energy in a balanced manner. In addition, WiBiA used alternative routes to re-form a direct path during a path disconnection, because of which network delays and energy consumption activities of the nodes were markedly reduced and the WSN was continuously maintained. In a WSN environment with limited network resources, the nodes resolved their own congestion situations and prevented excessive battery use.

Figure 7

Number of active nodes during the simulation in low-energy adaptive clustering hierarchy (LEACH) and the proposed wireless sensor network based on biomimicry algorithms (WiBiA).

Figure 8 shows the time taken to deliver a packet from the source node to the destination node. The average delay time of the proposed WiBiA increased by 24% compared with that of LEACH for the zero pause time, and increased by 12% when the pause time was 3000 s. This is because when an alternative path is used, the distance between the source and destination nodes increases, and with increasing pause time, the rate of use of the alternative path decreases. Thus, the difference between the average delay times of LEACH and WiBiA decreased. WiBiA exhibited excellent performance improvements in terms of packet distribution compared with the AODV or LEACH protocols. Figures 7 and 8 can conclude that the proposed algorithms ease the demand on the battery with regard to nodes with larger traffic concentration.

Figure 8

Time taken to deliver a packet from the source node to destination node during the simulation in low-energy adaptive clustering hierarchy (LEACH) and the proposed wireless sensor network based on biomimicry algorithms (WiBiA).

5. CONCLUSION

In this paper, we proposed and tested a biomimicry algorithm based on the similarity between biological systems and communication networks to solve problems in communication networks.

Moving nodes in a wireless network have limitations in CPU performance and battery, and traffic is concentrated on a small number of nodes in an environment where the node mobility is low.

The proposed biomimetic routing protocol is a CFA protocol, which analyzes traffic concentration in specific moving nodes and causes the congested nodes to give up data packet relay and inform it to the packet source node so that the source node could set a new bypass route, thus mitigating traffic concentration.

Compared to the existing protocols, such as AODV and DSR, that do not consider load balance, the proposed protocol solved the problem of forcing specific moving nodes to sacrifice by distributing traffic without performance loss in terms of transmission rate and end-to-end delay.

The simulation results showed that the proposed routing algorithm has short data collecting times and low-energy consumption, and can thus maximize the energy efficiency of the network.

Biomimicry algorithms, such as WiBiA, reliably provide optimal solutions to problems in complex environments by performing distributed operations according to simple behavioral rules. The rapid path setting and shortest path resetting between moving nodes in WiBiA can be considered the most important element for network lifespan.

Therefore, to ensure efficient communication between each pair of moving nodes, a routing method that can effectively and quickly restore disconnected paths is required. We expect that this kind of biomimicry algorithm can be effectively applied to large-scale communication networks in the future.

CONFLICT OF INTEREST

The authors have no affiliation with any organization with a direct or indirect financial interest in the subject matter discussed in the manuscript. The authors have no perceived or potential conflict of interest to declare with regards to the research and content of the above mentioned manuscript.

AUTHORS' CONTRIBUTIONS

The computational and informatics component of this manuscript have been developed by Meonghun Lee. All authors have participated in (a) drafting the article or revising it critically for important intellectual content and (b) approval of the final version.

ACKNOWLEDGMENTS

This work was supported by Korea Institute of Planning and Evaluation for Technology in Food, Agriculture and Forestry (IPET) through Advanced Production Technology Development Program, funded by Ministry of Agriculture, Food and Rural Affairs (MAFRA) (318092-3).