1 Introduction

WSNs are communication structures using many self-sufficient devices to form a network. A WSN node can sense surroundings, processing information locally and send it to one or more destinations through wireless links [1]. Sensors are generally small in size, using minimal energy, functioning in high concentrations, and autonomous. A wireless sensor node is made up of 4 practical modules: processing unit, sensing unit, transceiver, and power unit [2]. The continuous analog signal from sensors is converted into digitized signal and sent to controllers by an analog-to-digital converter for processing.

WSN made up of biomedical sensors is gaining popularity due to its versatility and easy monitoring for patients confined inside a hospital. In biomedical applications, the sensors gather vital body parameters and relay the data to a central server where the data is processed by a health care professional. Energy proficiency, size decline and least possible cost are concerns for sensor node architecture.

WSN are also used to sense data from unreachable areas and forward collected data. As sensor nodes do not have much power, recurrent and lengthy range transmissions have to be at a minimum to prolong network life [3]. Various communications protocols were proposed in the literature to get power-effective communication. A simple method is to split a network into smaller units and have a member to aggregate data from its network and transmit to a BS. So, only CHs transmit data over lengthy distances and others do only smaller length transmission. Hence, saving of additional energy and prolonging of network life is got. Thus, more energy effective protocols where CHs are selected systematically based on clustering structure [4, 5] are designed.

WSN routing protocols ensures signalling messages are propagated only within the cluster to reduce communications overhead [6]. CHs should be spaced to cover all network nodes and improve spatial reuse. Efficient techniques ensure formation of non-overlapping clusters efficiently such that energy dissipated by each node is minimal [7]. Figure 1 shows WSN’s clustering communication hierarchy.

Fig. 1
figure 1

Cluster based WSN

Full size image

Clustering algorithms in literature vary in objectives based on the application. Popular objectives for cluster formation are discussed in [8–12]. Problems arise if CHs are found first and are fixed in a system’s life, as in popular clustering approaches. Due to the huge amount of exchanged information between cluster members and CH and between CH and BS (called Sink); a problem here is detecting CHs. Here, CH nodes may use up all the power and not be of use [13]. Cluster based protocols like LEACH randomly changes CHs between nodes with high remaining energy and thus ensures graceful degradation of the network. Cluster formation helps in local data aggregation which improves considerable power savings in the network [14].

Various heuristic methods have been suggested in the literature for CH selection based on evolutionary and swarm intelligence algorithms. This paper proposes a shuffled frog metaheuristic algorithm for CH selection. The CH are selected on the criteria of minimizing intra-cluster distance between CH and cluster member, which optimizes network energy management to prolong WSN life.

2 Related Works

LEACH [13] a hierarchical cluster based protocol uses cluster based routing to minimize energy consumption. BS periodically changes cluster membership and CH to preserve energy. By rotating CH arbitrarily, energy usage is uniformly distributed. But, LEACH selects many CHs at a time or arbitrarily selects CHs far from the BS without considering nodes’ remaining energy. So, certain CHs drain energy quickly decreasing WSN lifespan.

An improved algorithm called Novel LEACH based on LEACH protocol pioneered by Kaur and Seehra [15] shows significant improvement in network life. A right combination of parameters to select CH to minimize total energy consumption required for data collection and aggregation was proposed by Din et al. [16]. The proposed three parameters; residual energy, centrality and communication cost all blended together with Fuzzy Logic. An enhanced form of LEACH protocol whose goal is to diminish energy consumption within a WSN and prolong network life was presented by Ray and De [17]. The new method enhanced LEACH protocol by refining CH nodes election strategy based on sensor nodes residual energy, distance from BS and successive rounds in which a node was not a CH. Improving LEACH by selecting CHs corresponding to the nodes remaining energy was proposed by Wang et al. [18]. A sliding window adjusts electing probability and stabilizes the anticipated CHs using 2 specifications in this method: the first is nodes primary energy information and the second is average energy information of those which have not been CHs in a network. Simulations reveal that improvement for FND is 41 % for LEACH, 17 % for LEACH with Deterministic CH Selection, 22 % for Advanced LEACH. Simulations reveal that improvement for HNA is 36 % for LEACH, 26 % for LEACH with Deterministic CH Selection, 21 % for Advanced LEACH. A local clustering mechanism adopted in a cluster to reduce computation and communication cost was presented by Mahajan et al. [19]. CHs are selected first based on weight metric and then cluster formation happens. A new technique for data transmission is also explored. Results of the new approach are compared via simulation with LEACH, WCA and IWCA. The new approach improves average over rounds by 51 % over LEACH, 27 % from WCA and 18.8 % from IWCA regarding lifetime and energy consumption.

A CH selection algorithm for a WSN where a node can be CH if connected to one unique neighbour node where the neighbour is one not connected to any other node was proposed by Jain et al. [20]. If there is no connected unique node then CH is selected based on residual energy and neighbour nodes. With increased clusters, the network’s processing energy increases; hence, the algorithm proposes minimum clusters which further increases network life. A CH selection scheme that deals with 2 level heterogeneous WSNs was proposed by Gupta and Verma [21]. Improved CH selection process has less energy consumption and prolongs network life and stability. An Energy Constrained minimum Dominating Set based efficient clustering called ECDS to optimally choose CHs with energy constraints was presented by Albath et al. [22]. This paper also proposed multiple extensions to the distributed algorithm for energy constrained dominating set. It experimentally shows that extensions perform well regarding energy usage, node life and clustering time when compared and so suit WSNs. A two-layer CH election based on distance was proposed by Lee et al. [23]. Sensor nodes are divided into 2 layers, the first layer and second layers i.e. a sub layer of first layer, and sequence per layer is based on nodes to BS distance. CH is selected in the sequence of second layer without communicating with other nodes. Simulations show that the new protocol enhances network life. Effective CH Selection based on Energy, Density and Mobility (EDM) model for WSN was proposed by Bhat and Shenoy [24]. Effective CH selection based on EDM for WSN protocol enhances efficient energy use and increases network life. Ideal cluster size to minimize energy spent in WSN is analytically provided by Amini et al. [25], where sensors communicate through selected CHs to BS in a decentralized way.

A PSO approach to split a node field into equal sized groups of nodes was proposed by Tillett et al. [26]. PSO is a heuristic technique mimicking interaction of swarms of insects or birds to find good solutions. Soliman and Sheta [27] proposed a K-Means clustering and Particle Swarm Optimization (PSO) to achieve an efficient energy management of the WSNs. Kuila and Jana [28] presented a PSO based clustering for energy conservation of the nodes with load balancing.

Energy optimization in WSN using GA was proposed by Jin et al. [29]. In the new work, GA was used to find independent clusters which reduced total communication distance. GA’s optimization properties were focused upon by Ferentionos et al. [30]. GA determined energy efficient clusters and CHs were chosen as associates for improvement. Simple heuristics were used to increase overall performance.

Though various meta heuristic algorithms are available in literature, Shuffled frog algorithm is chosen in this work due to its high efficiency in performance computation and good search capability. The shuffling strategy of frogs are used to exchange the information’s between local searches to obtain global optimum.

3 Problem Formulation

Consider a connected undirected graph G = (V, E), where V = {v1, v2, …, vn} is a finite set of vertices representing nodes in the network and E = {e1, e2, …, em} is a finite set of edges representing connectivity. Each edge has p attributes given by \(w_{i} = (w_{1i} ,w_{2i} ,w_{3i} ,{\ldots},w_{pi} )(i = 1, {\ldots},m).\) In practice \(w_{ki} (k = 1,2, {\ldots} ,p)\) may represent network parameters, the objectives that has to be optimized.

The connectivity between nodes \(v = (v_{1} ,v_{2},{\ldots},v_{m} )\) be defined by Eq. (1):

$$v_{{ij}} = \left\{ {\begin{array}{l} {1,\;if{\text{ }}node{\text{ }}i{\text{ }}can{\text{ }}communicate{\text{ }}with{\text{ }}node{\text{ }}j} \\ {0,\;otherwise} \\ \end{array} } \right.$$
(1)

The objective of the data aggregation algorithm can be represented by Eq. (2):

$$\begin{array}{l} {\min z_{1} (x) = \sum\nolimits_{{i = 1}}^{m} {w_{{1i}} e_{i} } } \\ {\min z_{2} (x) = \sum\nolimits_{{i = 1}}^{m} {w_{{2i}} e_{i} } } \\ {..........} \\ {\min z_{p} (x) = \sum\nolimits_{{i = 1}}^{m} {w_{{pi}} e_{i} } } \\ \end{array}$$
(2)

where z i (x) is the ith objective

In this work, the objective is to reduce packet loss rate and increase the network life time.

4 Methodology

In each cluster formation round of LEACH, the network follows two steps to select CH and transfer aggregated data.

  1. (i)

    Set-Up Phase, which is subdivided into network splitting phase, Cluster Set-Up and Schedule Creation phases. Based on a random number, nodes are selected as CH provided it has remaining energy above a set threshold. The threshold value can be set based on Eq. (3):

    $$T(n) = \frac{P}{1 - P(r\bmod (1/P))} {\quad} if \, \, n\, \varepsilon\,G$$
    (3)

    where P is the probability of a node being elected as CH, r is the round count that has completed and G are the remaining nodes who have not been cluster heads in the 1/p rounds.

  2. (ii)

    In Steady-State Phase, data transmission using Time Division Multiple is initiated [13]. Unreasonable CH selection occurs when nodes have different energy. The algorithm does not consider nodes location [31].

When all data is received, CH aggregates it and forwards it to the BS. LEACH performs local data aggregation in each cluster to reduce transmitted data. Though LEACH protocol is efficient it suffers drawbacks like;

  • CH selection is random without considering energy consumption

  • It covers a small area

  • CHs may be concentrated at one location

This paper proposed a Shuffled frog algorithm based on residual energy to locate optimal cluster numbers and CH and increasing Packet Delivery Ratio. Clustering is the process of partitioning a network into k groups called clusters based on some similarity metric. For WSN distance is one of the popular metric for network partitioning and either Euclidean distance or the Minkowski metric shown in Eq. (4 and 5) can be used:

$$d(x,y) = \left( {\sum\limits_{i = 1}^{m} {|x_{i} - y_{j} |^{r} } } \right)^{1/r}$$
(4)
$$d(x,y) = \sqrt {\sum\limits_{i = 1}^{m} {(x_{i} - y_{i} )^{2} } }$$
(5)

In the above method only distance is minimized leading to inefficient clusters. In the new method, fitness function is a target function where a maximum or minimum value is searched. This function is a part of an evolutional algorithm dependent on the problem directly. This fitness function is a criterion to choose nodes in clusters leading to minimum energy loss and maximum battery life for a node. Fitness function is based on distance and available energy as in Eq. (6):

$$f(i) = \alpha \left( {\frac{{energy_{i} }}{{\sum\nolimits_{{i = 1}}^{n} {energy_{i} } }}} \right) + (1 - \alpha )\left( {\frac{1}{{\sum\nolimits_{{j = 1}}^{m} {D_{{i,j}} } }}} \right)$$
(6)

where energyi is residual energy in node i, n is number of nodes in a network, Di,j is distance between node which are evaluated to become cluster head and its two hop neighbours, α is a constant whose value lies between 0 < α ≤ 1

As α increases, energy savings increases, but, if QoS is required, value of α is reduced. In this work we set \(\alpha = 0.7\) with the goal of energy savings over packet loss rate. The objective function is minimized using the steps given in the algorithm. The shuffled frog algorithm’s flow chart is seen in Fig. 2.

Fig. 2
figure 2

Flow chart of Shuffled Frog Algorithm

Full size image

An example of working of the Shuffled frog algorithms is shown using a ten node example

Initial random solution (Frogs)

v1

v2

v3

v4

v5

v6

v7

v8

v9

v10

S1

0

0

1

0

0

1

0

0

0

1

S2

0

0

1

0

0

0

0

1

0

0

S3

1

0

0

0

0

0

1

0

0

0

S4

0

1

1

0

1

1

0

0

0

1

S5

0

0

0

0

1

0

1

0

0

0

S6

1

0

0

0

1

0

1

0

0

1

Here ‘0’ represents a node as not selected and ‘1’ represents a node is selected as CH. In the first random solution \(v3,v6,v10\) are selected as CH. Computing the objective function, and eliminating poor solutions (by way of clusters), the above solution becomes

Initial random solution (Frogs)

v1

v2

v3

v4

v5

v6

v7

v8

v9

v10

S2

0

0

1

0

0

0

0

1

0

0

S4

0

1

1

0

1

1

0

0

0

1

S5

0

0

0

0

1

0

1

0

0

0

In the memplex evolution stage the solution is evolved as shown in highlighted content.

Initial random solution (Frogs)

v1

v2

v3

v4

v5

v6

v7

v8

v9

v10

S2

0

0

0

1

0

0

0

1

0

0

S4

0

1

1

0

1

0

1

0

0

1

S5

0

0

0

1

0

0

1

0

0

0

When new solutions are added in the final stage, the new solution evaluation becomes

Initial random solution (Frogs)

v1

v2

v3

v4

v5

v6

v7

v8

v9

v10

S2

0

0

0

1

0

0

0

1

0

0

S4

0

1

1

0

1

0

1

0

0

1

S5

0

0

0

1

0

0

1

0

0

0

S7

1

0

1

1

0

1

0

0

0

1

S8

1

0

0

1

1

1

1

1

0

0

S9

0

1

1

1

1

1

1

1

1

1

Since binary solutions are generated, the solutions are squashed to the range of [−10, 10] and a novel transfer function is proposed to flip the position of the bits from 0 to 1 or vice versa. Sigmoidal function is typically used and given by Eq. (7)

$$transfer(x) = \frac{1}{{(1 + e^{{ - x}} )}}$$
(7)

The proposed transfer function is given by Eq. (8)

$$transfer(x) = \frac{1}{{(1 + e^{{( - \tanh (x_{i} )\pi )}} )}}$$
(8)

5 Results and discussion

Simulations were carried out using LEACH, Genetic Algorithm (GA), Shuffled Frog Algorithm and the proposed transfer function based Shuffled frog algorithm using parameters shown in Table 1. The GA was initialized with a population of 15 chromosomes, two point crossover with a crossover rate of 0.1 and mutation rate of 0.01 was used. Simulations were carried out for small to medium size network consisting of 75 to 450 nodes.

Table 1 Simulation parameters
Full size table

Figures 3, 4 and 5 shows theQoS parameters obtained after simulation.

Fig. 3
figure 3

Number of Clusters Formed

Full size image

Figure 3 shows the number of clusters formed. It can be observed that as the network scales up to larger number of nodes the number of clusters formed for proposed technique increases. Results proves that the proposed shuffled frog algorithm performs better than LEACH, GA, and shuffled frog algorithm with best improvements of 13.33, 6.89, and 9.52 % respectively.

Figure 4 shows the average end to end delay. It can be observed that as the network scales up to larger number of nodes the average end to end delay for proposed technique decreases. Results prove that the proposed shuffled frog algorithm performs better by lowering delay than LEACH, GA, and shuffled frog algorithm in the range of 0.08 % to 6.91 %, 0.16 % to 21.60 %, and of 0.39 % to 21.77 % respectively. The efficiency of the proposed technique can be observed better when the number of nodes is greater than 200. At lower number of nodes the packets dropped are low due to free availability of physical medium.

Fig. 4
figure 4

Average End to End Delay

Full size image

Figure 5 shows the average packet loss rate. It can be observed that as the network scales up to larger number of nodes the average packet loss rate for proposed technique decreases. Results prove that the proposed shuffled frog algorithm performs better by lowering packet loss rate than LEACH, GA, and shuffled frog algorithm in the range of 15.3 % to 35.33 %, 7.68 % to 26.31 %, and 8.22 % to 30.31 % respectively. It can also be observed that losses decrease significantly as the number of nodes increase indicating efficient use of wireless medium.

Fig. 5
figure 5

Average Packet Loss Rate

Full size image

Figure 6 compares the life time computation of a 225 node network for LEACH, Shuffled frog algorithm and proposed shuffled frog algorithm. Results proves that the proposed shuffled frog algorithm performs better by increasing life time than LEACH in the range of 0 to 152 %, better than GA in the range of 0 to 200 %, and better than shuffled frog algorithm in the range of 0 to 20 %.

Fig. 6
figure 6

Life Time Computation

Full size image

Figure 7 compares the remaining energy consumption of 225 node network for LEACH, GA, Shuffled frog algorithm, and proposed shuffled frog algorithm. Results show that the proposed shuffled frog algorithm performs better than LEACH, GA, and shuffled frog algorithm.

Fig. 7
figure 7

Remaining Energy Consumption

Full size image

6 Conclusion

A Sensor node capacity to compute, communicate and store energy is limited, which ensure that WSN protocols need to conserve energy to maximize network life. CH selection method is a critical and energy constraint process in WSN requiring significant energy affecting WSN performance and operation. This work proposes a residual energy based Shuffled frog algorithm to locate optimal CH. Simulations are conducted for varied number of nodes (75 to 450) to find a performance measurement like average end to end delay, number of clusters formed, life time computation, average packet loss rate and remaining energy consumption. Results prove that the new shuffled frog algorithm performs better by increasing network life.