1 Introduction

WSNs has received considerable attention in recent years due to its adaptability in various domains including medical, military, industrial control, traffic monitoring to name a few. Every device has limited energy and in most scenarios the energy source is irreplaceable [1]. Hardware limitations include limited processing power, low bandwidth and memory. By considering these constraints of sensor nodes, innovative techniques are important to enable reliable communications.Key features of WSNs are [2]:

  • Nodes should be capable of self-configuring dynamically.

  • Nodes can be either static or may move randomly within a given area.

  • Each node is capable of providing network functionalities like routing and maintenance.

  • Distributed algorithms are used for organizing, routing and scheduling.

  • Security is limited as wireless medium is used for communication.

WSN efficiency depends on the cooperation of wireless nodes [3] and efficient data aggregation. Traditional routing strategies try to locate shortest path between source and destination nodes. However, factors like latency, propagation path loss, and variable wireless link quality, protection against intentional jamming, interference, fading, power consumed, reliability, security and recovery from failure can be used for optimization the routes for specific applications. Failing to consider these parameters can degrade network performance and dependability [4]. For sensor network applications, clustering plays vital role where a large number of sensors are deployed for sensing purposes. When each and every sensor nodes starts to communicate and engage in data transmission within the network, data collisions will be experienced leading to drain of limited energy from the network. This issue is addressed by node clustering where the network is divided into interconnected substructures, called clusters, with each cluster having many Sensor Node (SN) led by a CH (CH) which is the coordinator in this substructure as seen in Fig. 1.

Fig. 1
figure 1

Block diagram of WSN deployment with cluster heads

Full size image

In each cluster, the sensor nodes transmit their data to the respective CH and the CH aggregates the data and forwards them to the central base station and thus extending the overall network lifetime. The cluster formation leads to a two-level hierarchy with CH in the higher level. As the CH are responsible for aggregation of data and transmit the same to the sink, it expends more energy. To balance the energy drain, the CH are periodically re-elected [5] and hence to maintain the energy balance among all the nodes re-election of CHs within the clusters is performed which is based on their residual energy with a possible solution for balancing the power consumption of each cluster. The CH can be seen as a temporary base station which keeps in touch with other CHs. Electing the CH is the basic step in clustering and selecting the CH efficiently improves the network life time.

Cluster based data aggregation has two phases, the setup phase and the steady phase. In set up phase, the CH is selected and the members selected. The second phase is the steady phase where the CH receives data from all its members and transmits to the BS. Each process of the setup and the steady phase is called a round. This process is repeated so that CH are rotated at regular intervals such that all nodes dissipate uniform energy. In the selection of CH each node decides whether to turn into CH or not based on the objective function. Some nodes with more residual energy turn into CHs and send CH information to inform other nodes. The other nodes with less residual energy turn into common nodes, and send information about joining cluster to a CH [6].

Selection of CHs is an NP-Hard problem as existing statistical techniques produce sub optimal solutions. Real-world discrete and combinatorial problems are usually challenging and require computationally intensive algorithms. Swarm intelligence (SI) algorithms have been an interesting alternative for providing satisfactory solutions where the individual characteristics of the continuous swarm algorithms are used effectively for solving the given problem. SI [7] is an artificial intelligence technique based around on the study of collective behavior in decentralized, self-organized systems. SI systems are population based, where simple agents interacting locally with one another and also with their environment with no centralized control structure. SI has been used to address WSN issues such as node localization, optimal deployment, clustering and data-aggregation.

In this work the Fish Swarm Metaheuristic is investigated for CH formation. A novel multi objective function is proposed that not only improves the energy efficiency but also ensures better delivery of packets. The rest of the work is divided into the following subsections. Section 2 discusses existing work, Sect. 3 describes the proposed algorithm with Sect. 4 discussing the experimental set up and results obtained. Section 5 concludes the paper.

2 Related Works

Various algorithms using Meta heuristics have been proposed in literature. Karimi et al. [8] proposed two algorithms, GP-Leach and Harmony search (HS)-Leach. The authors improved the energy consumption by partitioning the network and using the evolutionary algorithms for optimized CH selection considering Wireless Sensor Network (WSN) nodes’ position information and residual energy. Kavitha and Wahidabanu [9] proposed an improved CH selection for efficient data aggregation in sensor networks. The proposed algorithm is based on Bacterial Foraging Optimization (BFO). Kaur and Singh [10] introduced an approach for the selection of CH based on Energy Distributed Clustering (EDC) algorithm. Honey Bee Optimization (HBO) was employed over EDC algorithm for effective CH selection. Singh and Lobiyal [11] proposed Particle Swarm Optimization (PSO) approach for generating energy-aware clusters by optimal selection of CHs. The PSO-based approach was implemented within the cluster rather than base station, which made it a semi-distributed method. Jagannatham [12] presented a novel framework for CH selection and sub-carrier allocation towards intra-cluster communication in an Orthogonal Frequency Division Multiple Access (OFDMA) based WSN. Rostami and Mottar [13] introduced a new approach for clustering sensor networks based on PSO algorithm which aimed to extend network lifetime. Simulation results showed that the proposed method is more effective compared to LEACH, CHEF and PSO-MV in terms of network lifetime and energy consumption. Guo et al. [14] presented a weighted average of cluster-head selection algorithm based on an improved Genetic Algorithm (GA) which made the node weights directly related to the decision-making predictions. The initial population is formed in the stage of single-parent evolution by using gene pool, then the algorithm continues to the next further evolution process, finally the best solution was saved in the population.

Wang et al. [15] investigated the maximization of the amount of gathered data in a clustered WSN. The amount of gathered data is maximized by selecting the optimal transmit power or selecting the optimal CH. Thilagavathi and Gnanasambandan Geetha [16] proposed an improved binary PSO algorithm with modified Connected Dominating Set (CDS) for multihop sensor network. Simulations showed that the proposed Binary particle swarm optimization (BPSO)-T and BPSO-EADS performed better than LEACH- and PSO-based system in terms of energy savings and quality of service (QoS). Ni et al. [17] proposed a solution based on fuzzy clustering pre-processing and PSO for CH selection in hierarchical topology control. Firstly fuzzy clustering algorithm is used to initial clustering for sensor nodes according to geographical locations. The fitness function is designed considering both the energy consumption and distance factors of WSN. Finally, the CH nodes in hierarchical topology were determined based on the improved PSO. Experimental results show that compared with traditional methods, the proposed method achieved the purpose of reducing the mortality rate of nodes and extending the network life cycle. Kim et al. [18] proposed an optimal algorithm with cluster balance taken into consideration. Solaiman & Sheta [19] proposed hybrid clustering algorithm based K-Means clustering and PSO to achieve an efficient energy management of the WSNs. Maadi and Maadi [20] proposed new clustering algorithm that using an imperialist competitive algorithm to select CHs in LEACH algorithm. Simulation results showed proposed algorithm could prolong the network lifetime efficiently compared with LEACH protocol. Kavandi et al. [21] proposed optimized network clustering by using fuzzy logic. Gopal et al. [22] focused on coordination of sensor nodes in a network and selection of best node which kept information of affiliated sensor node for communication with CH of other clusters using fuzzy logic with BFO for optimization.

Tavakoli et al. [23] proposed a CH rotation protocol based on Markov model with nearly zero overhead and no dead time. The proposed method outperformed other TDMA access based approaches. Shen and Guo [24] proposed an energy-saving CH method based on fuzzy logic and fish swarm technique. The fuzzifier considered the residual energy, mobility and position of the fish for selection of the CH. Smys and Raj [25] analysed the impact of unstable mobile nodes in Delay Tolerant Networks (DTN). Two mechanisms: self-healing and unstable topology structure for efficient power utilization and improved connectivity.

From literature review it can be concluded that GA, PSO, BFO have been effectively used to solve the CH selection problem. However GA suffers from slow convergence compared to PSO and BFO. PSO has been found to be suboptimal for solutions involving scattering. BFO has poor fault tolerance compared to other metaheuristic algorithms. Artificial Fish Swarm Algorithm mitigate most of the stated issues of metaheuristic algorithms and has fast convergence, good fault tolerance and good local search capabilities. This work investigated a Binary Fish Swarm Algorithm to improve the CH selection for WSN.

3 Materials and Methods

Optimization technique is used to minimize or maximize the outcome of a function by adjusting its factors. All proper values for this problem are called possible solutions and the best one is optimal solution. All swarm intelligence algorithms are based on population, where their iterative procedure leads to improve the position of individual in population and subsequently, their movement toward the better positions [26].

Artificial Fish Swarm Algorithm (AFSA) is one of the best Swarm Intelligence algorithms with advantages like robustness, global search ability, tolerance of parameter setting, and it is also proved to be insensitive to initial values. ASFA mimics the behaviour of fish swarms preying and has been found to converge very fast [27]. The search starts with random solutions mapped to each fish. Fitness is evaluated and the fish follow process is initiated and fish follows another fish with better solution. If the solution is suboptimal, the swarming process is initiated. If the desired solution is not met, preying process is initiated. This process is continued till the desired threshold or termination criteria is met. AFSA has four functions modelled from fish behaviours in fish swarms. The first function is free-move behaviour: as in nature, fishes move freely in the swarm when they do not prey. The second function is preying behaviour where it uses its sense of vision, smell and any other available sensors on their bodies. In AFSA, the area where an artificial fish can sense a prey is modelled as a neighbourhood with a visual-sized radius. The third function is follow behaviour where a fish finds food, other swarm members also follow it to reach the food. The last function is swarm behaviour which mimics fishes in nature where fish always try to be in the swarm and not to leave it in order to be protected from hunters [28].The environment, where an AF lives, is the solution space. Food consistency degree in the water area is AFSA objective function.

Supposed the state vector of artificial fish swarm is X = (x 1, x 2,…x n ), where x 1, x 2,…x n is status of the fish. Visual is the visual distance, the artificial fish occurs only in the inner radius of the circle to the length of the field of vision various acts. The food concentration in this position of fish is expressed as y = f (x), Where y is the objective function value. The distance between the artificial fish is d i,j  = ||X i  − X j ||, i and j is a random fish. Step means the maximum step size of artificial fish. α is the degree of congestion factor [29].

Supposed Xv is the visual position at some moment. Xnext is the new position. Than the movement process is represented as Eq. (1):

$$\begin{aligned} X_{v} = X_{i} + Visual \times rand(), \quad {\text{ i}} \in [ 0 , {\text{ n]}} \hfill \\ {\text{X}}_{next} = X + \frac{{X_{v} - X}}{{||X_{v} - X||}} \times step \times rand() \hfill \\ \end{aligned}$$
(1)

During preying mode the behaviour of fish is given by Eq. (2):

$$prey(X_{i} ) = \left\{ {\begin{array}{ll} x_{i} + step\frac{{x_{j} - x_{i} }}{{||x_{j} - x_{i} ||}}&\quad if \, y_{j} - y_{i} \\ x_{i} + (2rand \, - 1)\cdot step &\quad else \\ \end{array} } \right.$$
(2)

Here rand is random function with range [0, 1].

In the swarming phase the behaviour of the swarm is given by Eq. (3):

$$swarm(X_{i} ) = \left\{ {\begin{array}{ll} X_{i} + step\frac{{x_{j} - x_{i} }}{{||x_{j} - x_{i} ||}}\quad if \, \frac{{y_{c} }}{nf} > \delta y_{i} \hfill \\ prey(X_{i} )\quad else \hfill \\ \end{array}} \right.$$
(3)

In the follow phase the behaviour is given by Eq. (4):

$$follow(X_{i} ) = \left\{ {\begin{array}{ll} X_{i} + step\frac{{x_{\rm{max} } - x_{i} }}{{||x_{\rm{max} } - x_{i} ||}}\quad if\frac{{y_{\rm{max} } }}{nf} > \delta y_{i} \hfill \\ prey(X_{i} )\quad else \hfill \\ \end{array}} \right.$$
(4)

The three steps mentioned ensures both global and local search and the search direction following the best food source are achieved. In this work, AFSA is modified as shown in Fig. 2.

Fig. 2
figure 2

Flowchart of AFSA and proposed algorithm

Full size image

Compared to the AFSA, the proposed technique incorporates two major changes. The solutions are randomly split and perform either swarming or following behaviour. Using tournament selection the best fishes are selected and the preying processing is initiated. Fishes which are extremely successful in preying are selected and allowed to mate amongst themselves. The new solution produced along with best fishes are taken to the next iteration. In this work, the solutions are represented using binary values and distance between the fishes computed using Hamming distance. The hamming distance between two strings u, v is the number of places where u and v differ.

The best fishes are selected using the roulette wheel selection. In roulette wheel selection, probability of a fish being selected is directly proportional to its fitness. The probability of a fish i with fitness f i selected from N number of fishes is computed as Eq. (5):

$$p_{i} = \frac{{f_{i} }}{{\sum\nolimits_{j = 1}^{N} {f_{j} } }}$$
(5)

To improve the QOS a multi objective function based on end to end delay and Energy is proposed and given by Eq. (6):

$${\text{minf}}\text{(}{\text{x}}_{\text{i}} \text{)}{ = }\frac{{{\text{e}}^{{ - \left( {\frac{{D_{td} }}{{D_{m} }}} \right)^{2} }} }}{{\left( {\frac{{{\hbox{E}}_{\rm{ri}} }}{{{\hbox{E}}_{\rm{i}} }}} \right)}}$$
(6)

where dei is the end to end delay, Dtd is the total delay to reach the BS, Dm is the maximum delay in the network to reach BS, Eri is the remaining energy in the CH, Ei is the initial energy.

The following conditions are assumed

  • All nodes are located randomly in the network.

  • Each node has the same initial energy.

  • All fishes are unisex in nature.

  • Since fishes are unisexual in nature, mating is possible between any two fishes.

  • The free space radio model is used and hence as distance increases the energy required to transmit one bit of data also increases.

Since the solutions space is represented in binary format a transfer function is required to filp the bit when the fish changes position. In this work a new transfer function is proposed to flip the bits given by Eq. (7):

$$transfer(X_{i} ) = \frac{1}{{\left( {1 + \text{e}^{{ - tanh(x_{i} )}} } \right)}}$$
(7)

To achieve flipping a random number is generated between 0 and 1 and the bit is flipped if the random number is less than the transfer function given by Eq. (8):

$$\left\{ {\begin{array}{ll} 1,\quad {\text{if }}p ( 0 , {\text{ 1) < \,transfer(}}x_{i} ) \hfill \\ 0,\quad {\text{otherwise}} \hfill \\ \end{array}} \right.$$
(8)

4 Simulation Setup and Results

Simulations were carried out by varying the number of nodes from 100 to 1000 and Network size using 2000 sq m. The simulation setup parameters are shown in Table 1.

Table 1 Simulation parameters
Full size table

Figure 3 shows Number of rounds until first node dies. Figure 4 shows Number of rounds until last node dies. Figure 5 shows Clustering energy/dissipated energy.

Fig. 3
figure 3

Number of rounds until the first node dies

Full size image
Fig. 4
figure 4

Number of rounds until the last node dies

Full size image
Fig. 5
figure 5

Clustering energy/dissipated energy

Full size image

From Fig. 3 it can be observed that for number of rounds until the first node dies the proposed Binary Fish Swarm Algorithm with proposed transfer function is better than LEACH, GA, and Binary Fish Swarm Algorithm. When the number of nodes is 100, proposed Binary Fish Swarm Algorithm with proposed transfer function method has improved number of rounds until the first node dies by 90.22, 27.72, and 22.87 % when compared to LEACH, GA, and Binary Fish Swarm Algorithm respectively. When the number of nodes is 500, proposed Binary Fish Swarm Algorithm with proposed transfer function method has improved number of rounds until the first node dies by 87.47, 27.19, and 8.93 % when compared to LEACH, GA, and Binary Fish Swarm Algorithm respectively. When the number of nodes is 1000, proposed Binary Fish Swarm Algorithm with proposed transfer function method has improved number of rounds until the first node dies by 88.68, 0.87, and 3.96 % when compared to LEACH, GA, and Binary Fish Swarm Algorithm respectively.

From Fig. 4 it can be observed that for number of rounds until the last node dies, the proposed Binary Fish Swarm Algorithm with proposed transfer function is better than LEACH, GA, and Binary Fish Swarm Algorithm. When the number of nodes is 100, proposed Binary Fish Swarm Algorithm with proposed transfer function method has improved number of rounds until the last node dies by 14.24, 1.72, and 1.47 % when compared to LEACH, GA, and Binary Fish Swarm Algorithm respectively. When the number of nodes is 500, proposed Binary Fish Swarm Algorithm with proposed transfer function method has improved number of rounds until the last node dies by 4.41, 2.88, and 1.95 % when compared to LEACH, GA, and Binary Fish Swarm Algorithm respectively. When the number of nodes is 1000, proposed Binary Fish Swarm Algorithm with proposed transfer function method has improved number of rounds until the last node dies by 9.35, 3.3, and 1.64 % when compared to LEACH, GA, and Binary Fish Swarm Algorithm respectively.

From Fig. 5 it can be observed that for Clustering energy/dissipated energy, the proposed Binary Fish Swarm Algorithm with proposed transfer function decreases than LEACH, GA, and Binary Fish Swarm Algorithm. When the number of nodes is 100, proposed Binary Fish Swarm Algorithm with proposed transfer function method decreasesClustering energy/dissipated energy by 108.12, 40.1, and 16.62 % when compared to LEACH, GA, and Binary Fish Swarm Algorithm respectively. When the number of nodes is 500, proposed Binary Fish Swarm Algorithm with proposed transfer function method decreasesClustering energy/dissipated energy by 109.06, 45.32, and 20.14 % when compared to LEACH, GA, and Binary Fish Swarm Algorithm respectively. When the number of nodes is 1000, proposed Binary Fish Swarm Algorithm with proposed transfer function method decreases Clustering energy/dissipated energy by 101.62, 47.69, and 18.62 % when compared to LEACH, GA, and Binary Fish Swarm Algorithm respectively.

Table 2 shows the Packet loss rate. When the number of nodes is 100, proposed Binary Fish Swarm Algorithm with proposed transfer function method increasesPacket loss rate by 5.16 and 3.33 % when compared to LEACH, GA, decreases by 0.9 % for Binary Fish Swarm Algorithm. When the number of nodes is 500, proposed Binary Fish Swarm Algorithm with proposed transfer function method increasesPacket loss rate by 5.49 and 2.18 % when compared to LEACH, GA, decreases by 1.31 % for Binary Fish Swarm Algorithm. When the number of nodes is 1000, proposed Binary Fish Swarm Algorithm with proposed transfer function method increasesPacket loss rate by 2.91 and 0.16 % when compared to LEACH, GA, decreases by 3.8 % for Binary Fish Swarm Algorithm.

Table 2 Packet loss rate
Full size table

5 Conclusion

Selection of CHs is an NP-Hard problem as existing statistical techniques produce sub optimal solutions. This work proposed an optimized CH selection using a Binary Fish Swarm Algorithm metaheuristic. The proposed algorithm has fast convergence, good fault tolerance and good local search capabilities. Extensive simulations was conducted to evaluate the proposed Binary Fish Swarm Algorithm and was compared to other popular techniques including LEACH and GA. Results demonstrate that the proposed CH selection reduces packet loss and improves the network lifetime.