1 Introduction

Wireless sensor network (WSN) is composed of an interconnection of small, low cost, low power, and multifunctional sensor nodes [1–5]. Wireless sensor networks for healthcare have emerged in recent years as a result of the need to collect data about patients’ physical, physiological, and vital signs in the spaces ranging from personal to hospital, and to enable sensors at low costs that available this data collection. In order to maximize the lifetime of WSNs, traffic should be sent via routes that can avoid nodes with low power while minimizing the total transmission power [6–12].

One of the bottlenecks of sensor devices is the batteries. Because of the high likelihood of forgetting to recharge the batteries of several sensors, this is a significant issue needs to be solved. Although there is much effort on designing lowpower sensors to minimize this bottleneck [5], we still need to find energy scavenging techniques. MobiHealth [6] is one of the early projects that integrates all the wearable sensor devices such as PDA’s mobile phones and watches that a person carries around during the day. The sensors continuously measure and transmit physiological data together with the audio and video recordings to health service providers in order to provide fast and reliable remote assistance in case of accidents. Amgoth et al. [7] propose a new distributed, energy and coverage aware routing algorithm called DECAR to achieve this goal. In the proposed algorithm, sensor nodes are grouped into clusters of unequal size to minimize the hot spot problem during the process of data routing towards sink.

Multipath routing in WSNs has attracted immense research interests due to its capability of providing increased robustness for balanced data gathering, and achieving fault tolerance by extend network lifetime. Hao et al. [8] design a distributed topology control and channel allocation algorithm from a game perspective in order to alleviate the interference and balance the energy consumption. Tang et al. [9] study the relay node placement problem in large scale wireless sensor networks. Data communication from relay nodes to the multipath node may be either single-hop or multi-hop. In [10], Shin et al. design and implement a reliable energy aware routing (REAR) protocol for wireless sensor networks and evaluate the performance of REAR by comparing with existing routing protocols. REAR considers residual energy capacity of each sensor node in establishing routing paths and supports multi-path routing protocol for reliable data transmission. Liang et al. [11] have proposed an energy and mobility aware geographical multipath routing for wireless sensor networks. Wang et al. [12] propose an energy efficient and collision aware (EECA) node-disjoint multipath routing algorithm. The data collection rate in pervasive healthcare systems is high. The development of efficient data and energy processing techniques are of great importance.

Genetic algorithm (GA) is one of the varieties of evolutionary algorithms inspired from biology. Information is formed as chromosomes and is combined by special operations such as inheritance, mutation, selection and crossover to search for beneficial adaptations for solving the given problem [13]. GA provides robust and efficiency for global optimization search in a complex space. WSNs are typically designed and evaluated in generic simulation environments. Michalewicz et al. [14] indicate that there are many theoretical and experimental results on parameter tuning and parameter control. De Jong [15] indicates that it is difficult to ascertain whether any advantage can be gained by dynamically changing the value of a parameter during an GA run and, if so, how to change it. A GA based approach for energy efficient routing has been proposed by Bari et al. [16]. They have suggested this approach for two tiered sensor network for data gathering with aggregation. Rana et al. [17] propose an emphasized heuristic search technique, called A-Star algorithm, for searching the best path for routing in WSN. Criteria used to search for the best path include not only to get the path with minimum energy consumption, but also to see that nodes selected in the path contain enough residual energy.

In this paper, we have proposed a genetic algorithm for energy-entropy based multipath routing in WSNs (GAEMW). The key idea of the protocol is to find the minimal node residual energy of each route in the process of selecting multipath routing by descending nodal residual energy. The proposed method can balance individual nodes battery power utilization and hence prolong the entire networks lifetime, energy variance, average energy consumption, and packet delivery ratio. Experimental results show that the approach is efficient, and have promising performance advantage for multipath traffic engineering and evaluating the route stability in WSNs.

The rest of the paper is organized as follows. In Sect. 2, we present the energy consumption model. A genetic algorithm for energy-efficient based multipath routing in WSNs (GAEMW) is proposed in Sect. 3. Simulation results are provided in Sect. 4. In Sect. 5, conclusion will be given.

2 Energy Consumption Model

The traffic of a given WSN \(G = (V, E)\) , where V is the set of n nodes, and E is the set of n links, \(\vert V\vert =n\), can be specified by a set of minimal and distinct communication patterns \(P = \{P_{1}, P_{2}, \ldots , P_{m}\}\), where each traffic pattern \(P_{k} = (s_{k}, D_{k})\) has the sender node \(s_{k}\), the sink nodes \(D_{k}\) specified, \(1 \le k \le m\), when \(D_{k}\) is a proper subset of all other nodes \(D_{k} \subseteq V-\{s_{k}\}\). We note that \(m \le n\).

We consider that a WSN in which the node locations are fixed, nodes are battery operated and equipped with omnidirectional antennas. Every transmission by a node u can be received by all nodes situated within its communication range. We also assume that ample bandwidth is available to accommodate all transmission requests.

Before describing our proposed algorithm, we present in this section the energy model that have been used in our solution and which is similar to the one used in [18].

We consider an interference-free model. The main factors that influence the energy consumption include: the energy/bit consumed by the transmitter \(({\alpha }_{t})\), the energy dissipated in the transmit \(({\alpha }_{amp})\), and the energy/bit consumed by the receiver electronics \(({\alpha }_{r})\). With the assumption of \(1/d^{2}\) path loss, the energy consumed for sending and receiving bits is given as:

$$E_{tr} = (\alpha _t + \alpha _{amp} \times d^2)\times r,\quad \hbox {and} \quad E_{rec} = \alpha _r \times r$$
(1)

where \(E_{tr}\) is the consumed energy to send r bits, \(E_{rec}\) is the consumed energy to receive r bits, and d is the distance the message traverses.

The energy required to transmit and receive a packet at a single link is given by \(E_{tr}+E_{rec}\), and the energy that is required to transmit and receive an entire compressed image over a single link is given by

$$(E_{tr} + E_{rec})\times N_I$$
(2)

where \(N_{I}\) is the number of transmission packet.

The energy required to transmit and receive a packet over the WSN from its source s to its sink d over a path k is given by

$$(E_{tr} + E_{rec})\times P_k^{s,d}$$
(3)

where \(P_{k}^{s,d}\) is the number of hops from source s to sink d.

We model routing decisions at an abstract level by routing probability. The energy required to transmit and receive a packet over the WSN from its source s to its sink d where the individual packet follows one path k, chosen with probability \(P_{k}\). \(Paths_{s,d}\) from s to d is given by

$$(E_{tr} + E_{rec} )\times P_k \times P_k^{s,d}$$
(4)

where \(\sum \nolimits _{k = 1}^{paths_{s,d} } {p_k } = 1\).

3 Genetic Algorithms

3.1 GA Overview

GA is based on the mechanics of natural evolution. Throughout their artificial evolution, each successive generation consists a population of possible solutions, called individuals, beneficial adaptations are sought to solve the given problem. In [19], a GA approach is presented to solve the shortest path routing problem. In [19], a GA approach was presented to the shortest path routing problem. A population-sizing equation that facilitates a solution with the desired quality is also developed. GA provides robust and efficiency for global optimization search in a complex space. WSNs are typically designed and evaluated in generic simulation environments.

A GA’s flowchart for its iterative process is shown in Fig. 1. GA is a reward based multi-solution search algorithm. When a GA is used for problem-solving, three operations have impact on the effectiveness of the algorithm, they are: (1) the selection of the fitness function; (2) the representation of individuals; and (3) the values of GA parameters.

Fig. 1
figure 1

The general scheme of an evolutionary algorithm

Full size image

GA search process has two major challenges, search speed and solution quality. All three GA operations heavily rely on randomness. Although the randomness is necessary in GA, it introduces many unnecessary and worse solutions. It slows down the search process and results in low quality solution.

3.2 Encoding

Based on the proposed GAEMW algorithm, the encoding scheme of the GAEMW problem is designed and the first generation is created. This step is called population initialization. A general method to initialize the population is to explore the genetic diversity.

A routing path is encoded by a string of positive integers that represent the IDs, energy and other related information of sensor nodes through which the path passes. The gene of the first locus is for the source node and the gene of the last locus is for the sink node. Given a source node s and sink node d, a chromosome can be represented by a string of integers with length m. Fig. 2 shows an example of the proposed encoding method. The multi-path is from the source s to the sink d. The multi-path routing paths in the example are expressed as follows: the first path is \((s \rightarrow 1 \rightarrow 3 \rightarrow 4 \rightarrow d)\), and the second path is \((s \rightarrow 2 \rightarrow 3 \rightarrow 5 \rightarrow d)\).

Fig. 2
figure 2

Encoding a chromosome by multipath

Full size image

3.3 Fitness Function

Given a solution, its quality should be accurately evaluated by the fitness value, which is determined by the fitness function. In our algorithm, we aim to find the least cost multipath between the source and the sink. The fitness function for the genetic algorithm determines the score or quality of each chromosome. After the chromosome has been run through the schedule builder and a solution is obtained, this solution will be the input for our fitness function. Therefore, the fitness function of a chromosome \(C_{i}\) in the population is defined as:

$$f(C_i ) = \frac{1}{G}\sum \limits _{k = 1}^{path} \left( (E_{tr} + E_{rec} )\times P_{ki} \times \left| {P_{ki} ^{s,d}} \right| - E_{avg} \right)$$
(5)

where G is the total number of path in the WSN and \(E_{avg}\) is the average loads of all path. Equation (5) is the fitness function of a given solution, where a lower variance indicates a better fitness of a chromosome, i.e., a better solution.

3.4 Selection Operator

The selection of chromosome is based on the fitness value. Roulette wheel selection is one of the common techniques used in genetic algorithm implementations that also works well for the multipath routing problem. The first step in the selection process is to run all of our chromosomes from the initial population through our schedule builder. The schedule builder will produce a solution for the scheduled task requests for each chromosome. This schedule will then be the input to our fitness function and be scored appropriately. After all of the chromosomes have been scheduled and scored, the sum of all of the individual fitness is calculated. This will represent the total fitness for the population.

3.5 Crossover and Mutation Operator

A GA relies on two basic genetic operators (crossover and mutation). In our approach, to apply crossover, we swap the genes between chromosomes only if the same sensor in both parents does not depend on any other sensor and no other sensor depends on it. The fitness of the resulting children is calculated to be compared with the fitness of the current population during the selection phase. In our implementation, we set the crossover probability at 0.95. This value was chosen to allow the majority of chromosomes in the population to mate and pass on their genetic information to their offspring. After two parents are chosen, if a random number, \(p \in (0, 1) < 0.95\), then the parents will successfully mate and children will be generated. Fig. 3 shows an example of the crossover procedure.

Fig. 3
figure 3

Overall procedure of the crossover

Full size image

Our genetic algorithms utilize the random swap mutation and the genetic information for two randomly chosen genes in the offspring is switched. To replicate mutation in our GA’s, a random number, \(r \in (0, 1)\) is chosen. If \(r < 0.05\), a mutation will occur. When the mutation process is completed on both children, their fitness value is calculated. Then they are reinserted into the current population, and become ready for the next selection phase. Fig. 4 shows the overall procedure of the mutation operation.

Fig. 4
figure 4

Overall procedure of the mutation

Full size image

4 Simulation Experiments

4.1 Simulation Environment and Parameters

To test the GAEMW approach, we randomly deploy 100 sensor nodes in an area of \(500\,\hbox {m} \times 500\,\hbox {m}\) in 2-D freespace. On this network, we experiment with place five randomly sinks. Each source generates data packet continuously until the end of the simulation run. The sources and the sinks are randomly selected with uniform probabilities.

At the beginning of the simulation, each node waits for a pause time, then the radio propagation model is TwoRayGround model with a nominal radio range of 100 m and channel capacity of 2 Mbps. The application used is CBR with packet size of 512 bytes. Each node has the initial energy of 30 joules and the “energy_threshold” is set to 5 joules through the network. Each simulation is executed for 600 s of simulation time. Multiple runs with different seed values were conducted for each scenario and data collected were averaged over those runs. A free space propagation model was used in our experiments. The energy performances of protocol GAEMW and A-algorithm [17] are compared in networks lifetime, energy variance, average energy consumption, packet delivery ratio, and average delay.

For each simulation, two main types of parameters are set, namely, parameters related to the network and parameters related to the GA. Table 1 lists all the parameters and their values for both the network and the GA.

Table 1 Simulation parameters
Full size table

4.2 Performance Metrics

We used several metrics to evaluate the performance of our GAEMW approach, they are:

4.2.1 Variance of Remaining Energy

The variance of energy remained for a node in the network, which is used to evaluate the performance of the algorithm in distributing network loads and equalizing the energy consumptions.

4.2.2 Average Energy Remaining in Sensors

The average amount of energy consumed by sensors in the network during the simulation time.

4.2.3 Network Lifetime

The time from the very beginning till the first node failure due to exhaustion of battery power, which is one of the most important performance evaluation metrics for protocol designing with energy considered.

4.2.4 Packet Delivery Ratio

The ratio between the number of data packets received by the sink and the number of data packets sent by the source.

4.3 Simulation Results

To evaluate the performances of our multipath routing protocol, we simulate the proposed mechanisms using NS-2 [20] extended by a complete implementation of IEEE 802.11.

For our simulation scenarios, we notice that all resulting fitness values have been converged, and no noticeable divergence is occurring before reaching 40 generations. Fig. 5 shows the improvement in the fitness value of the GA’s best solution as the number of generations increases for a network with 5 sinks and 100 uniformly distributed nodes. It is shown that no significant improvement in the fitness value after 40 generations.

Fig. 5
figure 5

Improvement in the fitness value of the GAs best solution as the number of generations is increased

Full size image

We begin by calculating the variance of remaining energy among sinks during the simulation time. Fig. 6 shows the variance of the remaining energy among the sinks in WSN with 100 nodes and 5 sinks. Fig. 6 shows that GAEMW maintains a better variance of remaining energy in multiple scenarios, involving the increase in the number of sensors or the increase in the number of sinks in the WSN. The increase in the slope of the curve for A-Star algorithm in Fig. 6 supports our argument, and indicates that the variance of remaining energy among sinks is high due to the unbalanced loads.

Fig. 6
figure 6

Comparison of variance of remaining energy

Full size image

Figure 7 illustrates the average energy remaining in sensors overtime in a WSN with 5 sinks and 100 sensors. It is shown that our approach sustains a better level of average energy remaining in sensors over time than the A-Star algorithm approach. The results gather for this metric from all other experiments (i.e., changing topology type, increasing number of sinks, and increasing number of sensors), exhibit similar plots to that of Fig. 7, which can be explained using the same argument above.

Fig. 7
figure 7

Comparison of average energy remaining

Full size image

Figure 8 shows the network’s lifetime. It can be seen from Fig. 8 that, using GAEMW, network lifetime is extended. In most of the cases, it is extended around 15 % than that of A-Star algorithm. We can also observe that the network lifetime with multipath routing degrades more gracefully than other routing protocols when node’s movement speed increases. It demonstrates that our routing scheme is more stable as the variation of the node’s movement speed increases.

Fig. 8
figure 8

Comparison of network lifetime

Full size image

Figure 9 illustrates the results for the WSN. It is shown that our approach improves the packet delivery ratio compared to that of the A-Star algorithm. GAEMW has much higher packet delivery ratio than both A-Star algorithm. A-Star algorithm have a similar low delivery ratio under a same network. This proves that GAEMW outperforms A-Star algorithm in packet delivery ratio because GAEMW can balance the traffic load among different nodes depending on their nodal residual energy and prolong the individual node’s lifetime.

Fig. 9
figure 9

Comparison of packet delivery ratio

Full size image

5 Conclusion

In this paper, we have proposed a Genetic Algorithm for Energy-efficient based Multipath routing in WSNs (GAEMW). The key idea of the protocol is to find the minimal node residual energy of each route in the process of selecting multipath routing by descending nodal residual energy. The performance of our proposed methods is evaluated via modeling and simulation. The simulation results demonstrate that the proposed approach and parameters provide an accurate and efficient method for estimating and evaluating the route stability in WSNs. Future work is to formulate the problem as an optimization problem in order to compute the optimal solution and to check how far from optimality the best GA feasible solution.