Abstract
Biogeography-based optimization (BBO) is a relatively new paradigm for optimization which is yet to be explored to solve complex optimization problems to prove its full potential. In wireless sensor networks (WSNs), optimal cluster head selection and routing are two well-known optimization problems. Researchers often use hierarchal cluster-based routing, in which power consumption of cluster heads (CHs) is very high due to its extra functionalities such as receiving and aggregating the data from its member sensor nodes and transmitting the aggregated data to the base station (BS). Therefore, proper care should be taken while selecting the CHs to enhance the life of the network. After formation of the clusters, data to be routed to the BS in inter-cluster fashion for further enhancing the life of WSNs. In this paper, a biogeography-based energy saving routing architecture (BERA) is proposed for CH selection and routing. The biogeography-based CH selection algorithm is proposed with an efficient encoding scheme of a habitat and by formulating a novel fitness function that uses residual energy and distance as its metrics. The BBO-based routing algorithm is also proposed. The efficient encoding scheme of a habitat is developed, and its fitness function considers the node degree in addition to residual energy and distance. To exhibit the performance of BERA, it is extensively tested with some existing routing algorithms such as DHCR, Hybrid routing, EADC and some bio-inspired algorithms, namely GA and PSO. Simulation results confirm the superiority/competitiveness of the proposed algorithm over existing techniques.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
1 Introduction
Wireless sensors are widely used for data gathering applications such as monitoring systems, automations. Each sensor node collects data from its target area and forwards it to the base station (BS). In this process, sensors consume some energy in gathering, processing and transmitting the data to the BS. This entire process of interaction is called as a round. In each round, energy of sensors depletes and after a certain number of rounds, sensors are exhausted due to lack of residual energy (Liu et al. 2010; Taheri et al. 2012). Since, each sensor node is powered by non-rechargeable and non-replaceable batteries, conserving the energy of sensor nodes is the most crucial issue in designing any WSNs. To enhance the performance of the network, various routing protocols have been devised (Heinzelman et al. 2000; Jian et al. 2010; Kundra et al. 2009; Rao and Banka 2016). One of them is a hierarchical cluster-based routing, which divides the network into several subgroups called clusters (Jian et al. 2010; Li et al. 2013; Mao et al. 2013). Each cluster contains a head node known as cluster head (CH). CH collects data from its members (non-CHs) and communicates that to another CH or the BS as demonstrated in Fig. 1.
In the CH selection, if m nodes are selected as CHs out of n nodes, a total of \(^nC_m\) possible combinations exists. Hence, the computational complexity grows exponentially with the network size. It becomes an NP-hard problem and it is difficult to solve using heuristic approaches (Agarwal and Procopiuc 2002). Due to limited energy resources of sensor nodes, direct data transmission from CHs to the BS is not a feasible option for large-scale WSNs. Therefore, multi-hop inter-cluster communication is essential to handle this problem. In routing, the computational complexity varies exponentially with the size of the network. For example, if an average k CHs in the communication range of m CHs, then the computational complexity becomes \(k^m\). As the size of the network increases, the value of m also increases. Therefore, finding the shortest path for large-scale sensor network becomes an NP-hard problem (Dorigo et al. 2006). We have considered scalable network ranging from small size to large size. It means that the computational complexity for selecting a route grows exponentially with the network size. Therefore, meta-heuristic approaches (Song and Cheng-Lin 2011; Bhari et al. 2009; Yu and Xiaohui 2011) can better approximate the solution to such kind of problems compared to heuristics.
Biogeography-based optimization (BBO) is a new optimization paradigm (Simon 2008) which is proved to be instrumental in solving complex problems in wide variety of domains such as sensor selection (Simon 2008), CT scan image segmentation (Chatterjee et al. 2012), power system optimization (Rarick et al. 2009; Roy et al. 2010; Bhattacharya and Chattopadhyay 2011), parameter estimation (Wang and Xu 2011), satellite image classification (Panchal et al. 2009), optimal meter placement (Jamuna and Swarup 2011), groundwater detection (Kundra et al. 2009). BBO has certain similarities with existing bio-inspired algorithms such as GAs and PSO in the way of sharing information among the solutions. In GA, if the parent is not fittest than its child, it has a low probability of survival for the next generation, while in PSO and BBO, such a solution survives for the next generation. In PSO, solutions are more likely to clump together in similar groups, while in BBO and GA, solutions are not grouped in the cluster. Solution of PSO is updated via velocity, whereas BBO solution is updated directly. Since BBO has provided better performance than GA and PSO in certain cases (Simon 2008), it motivated us to develop BBO-based algorithm for CH selection and routing in WSNs. To the best of our knowledge, it is the first such attempt.
In the present work, two BBO-based optimization algorithms, one for CH selection and another for routing in WSNs, have been proposed. The CH selection algorithm is capable of identifying near-optimal CHs among available sensor nodes. In order to achieve the objective, a novel fitness function is designed with an effective encoding scheme. For the derivation of fitness function, we considered various parameters such as energy, intra-cluster distance and distance from CHs to the BS. Afterward, non-CH nodes are assigned to the CHs using distance. Secondly, the routing algorithm is devised to find the near-optimal path from every CH to the BS. To accomplish this task, a new fitness function and an efficient encoding scheme are presented. The fitness function for the routing algorithm consists of parameters such as energy, distance and node degree. In the extensive simulation, firstly our proposed work (BERA) is compared with some recent existing approaches. Afterward, we have also executed well-established algorithms (GA, PSO) on the above stated problems, and compared with the proposed work in terms performance metrics.
The main contributions of this paper are as follows:
-
BBO-based CH selection algorithm with a novel fitness function and efficient encoding scheme.
-
BBO-based multi-hop routing algorithm with a new fitness function and a novel encoding scheme.
-
In performance analysis, proposed algorithm BERA is compared with some of the existing conventional methods and also tested with well-established bio-inspired techniques (GA, PSO).
The rest of the paper is organized as follows. Next section summarizes the clustering and the routing literature of WSNs. Important preliminaries on network model, energy model and BBO have been discussed in Sect. 3. The proposed cluster head selection and routing algorithms are discussed in detail in Sect. 4. Simulation analysis with some existing conventional and population-based algorithm is shown in Sect. 5. Finally, Sect. 6 concludes the paper.
2 Literature review
In this section, recent advances in clustering and routing algorithms are presented.
2.1 Clustering
A large number of clustering algorithms have been devised for WSNs (Bagci and Yazici 2010; Ran et al. 2010; Singh et al. 2013; Rao and Banka 2015; Rao et al. 2016). LEACH is very popular among them. Its objective is to reduce the energy consumption in WSN (Heinzelman et al. 2000). Each sensor node transmits data to the BS via its respective CH. To balance the energy consumption in the network, CH rotates randomly over time. However, the limitation of LEACH is to choose a sensor node as a CH with low residual energy which hampers the performance of the network. The authors in (Lindsey and Raghavendra 2002) have proposed an improved version of LEACH protocol. In the communication process, node receives data from its neighbor and one node selected from its chain to transmit the data to the BS. However, single leader dissipates energy rapidly as it is involved in regular transmission. Heinzelman et al. (2002) proposed LEACH-centralized (LEACH-C) protocol. In this protocol, the BS collects residual energy and the location information from all the sensors. After that BS forms clusters using a simulated annealing algorithm. But, it ignores the distance between sensors and its respective CH in the cluster formation process which decreases the life of the network. Wang et al. (2012) enhanced the performance of LEACH by considering the residual energy of nodes in the CH selection process. In data transmission phase, CH communicates directly with the BS, it is not feasible for large WSN. The authors in (Chang and Ju 2012) have proposed an energy saving clustering architecture. It enhances the life of the network by uniform cluster formation in which average distance and the center point are taken as input. In the CH selection process, residual energy of nodes within the cluster is taken as an input. However, it does not take care of node degree in the cluster formation process. In Yang and Ju (2014), a communication protocol has been presented. In its cluster formation process, initially BS collects location and the residual energy information of sensor nodes. Afterward, tree structure is formed within the cluster for connecting sensor nodes to its respective CH. In this process, it ignores residual energy while joining sensor nodes to its respective CH. Bagci and Yazici (2013) proposed an unequal clustering algorithm. To achieve the objective, it calculates the competitive radii of each cluster using fuzzy logic which consists of energy and distance as input. It increases the life of WSN. But, it does not consider the average distance between sensors and its respective CH in the cluster formation process. Lee and Cheng (2012) proposed a distributed algorithm for CH selection. It is executed in two phases. In the first phase, cluster formation is done using LEACH algorithm. In the second phase, CH is selected within the cluster using fuzzy logic. It takes residual energy and expected residual energy as input. However, it does not taken consideration of distance to the BS and node centrality for CH selection. Kumar et al. (2011) proposed a fuzzy-based clustering algorithm. In the CH selection process, fuzzy inference system is used which consists of distance, node density and battery level as input. The parameters taken into consideration increases the life of the network. However, it is unable to provide adaptive multi-hop communication.
2.2 Routing
In large WSN, direct communication between CHs and the BS is not feasible due to the higher communication cost. Every node needs to communicate with the BS at the minimum possible cost. Thus, the routing techniques have been devised by researchers (Younis and Fahmy 2004; Senouci et al. 2012; Lai et al. 2012; Abdulla et al. 2012). Among them, one of the popular algorithm is HEED (Younis and Fahmy 2004). Its CH selection process is based on residual energy. When tie occurs for choosing the CHs, then ARMP cost function is used to break it. Each CH transmits data to the BS in a multi-hop fashion. Therefore, it increases the life of the network. Even so, it does not take care of distance in CH selection process. The authors in (Senouci et al. 2012) have proposed an improved version of HEED algorithm. In the cluster formation process, it uses a similar mechanism as HEED. In addition, each cluster is divided into zones, based on distance between non-CH and CH nodes. It reduces the energy consumption of each CH member. In Lai et al. (2012), authors have proposed an unequal cluster formation mechanism. The size of every cluster is computed using load on its respective CH. Therefore, it avoids cluster reconfiguration and increases the life of the network. Abdulla et al. (2012) proposed a hybrid routing algorithm, with an objective to remove the hot-spot problem. In the communication process, it performs flat routing inside the hot-spot zone and hierarchical outwards. However, it does not analyze the effect of the hybrid boundary on the network performance. The authors in (Yu et al. 2012) have proposed a routing algorithm (EADC), which scouts the routing path between every CH and the BS using energy and node degree of CHs. Therefore, it increases the life of the path. Even so, it does not take care of distance between CH and next-hop for finding the routing path. Maryam and Reza (2015) proposed an enhanced version of EADC by adding one more parameter for scouting the communication path, namely the transmission power. Song and Cheng-Lin (2011) proposed a routing algorithm. In the cluster formation process, it finds the competitive radii for each cluster and also estimates the chance of a sensor node to become a CH, in which fuzzy logic is used. It considers density, distance and energy as input parameter. Thereafter, routing path for every CH is computed using ant colony optimization (ACO). Therefore, it enhances the performance of the network. In Bhari et al. (2009), authors have proposed a routing algorithm for large-scale WSN-based genetic algorithm. They derived the fitness function based on network lifetime. However, it does not take care of other essential parameters such as node degree, BS distance. Elhabyan and Yagoub (2015) proposed a particle swarm intelligence-based clustering and routing algorithm. In the clustering process, fitness function consists of energy, cluster quality and network coverage. In routing algorithm, fitness function is derived using energy and link quality. However, it does not take care of power control in the derived fitness in the routing process.
2.3 Advantages of proposed work over existing works
-
Classical approaches mentioned in related work are not able to tackle CH selection and routing problem for large-scale network (Younis and Fahmy 2004; Senouci et al. 2012; Lai et al. 2012), as both the problems has been proven to be NP-hard in nature (Agarwal and Procopiuc 2002; Dorigo et al. 2006). The stochastic approaches mentioned in the literature are not able to provide better quality of solution due to the lack of consideration of essential parameters in the derivation of the fitness function (Elhabyan and Yagoub 2015). In the proposed work, biogeography-based optimization is used with proper consideration of essential parameters like energy, distance and node degree. So, that better quality of solution was achieved compared to existing works.
-
Newly devised bio-inspired technique has been adopted and compared with well-established techniques (GA, PSO) with the same fitness function. In contrast, bio-inspired techniques adopted by authors (Song and Cheng-Lin 2011; Elhabyan and Yagoub 2015), but simulated results were not compared with existing well-established bio-inspired techniques (GA, PSO).
3 Preliminaries
In the current section, we have tried to describe the notations, network model, energy model and biogeography-based optimization.
3.1 Notation
Table 1 introduces some of the notations and/or abbreviation used in this study.
3.2 Network model
In this paper, hierarchal routing architecture is proposed with following properties. In node configuration, all nodes are homogeneous in nature, it means all nodes have equal initial energy, processing and communication capabilities. Distance calculation is based on received signal strength (Xu et al. 2010). Initially, all sensors are deployed randomly in the target area and position of sensors are fixed after deployment. All nodes then transmits its residual energy and location information to the BS. Based on it, the number of CHs (m) are selected out of n nodes by our proposed CH selection algorithm (see Sect. 4.1). Finally, the proposed routing algorithm is executed to establish the path from every CH to the BS (see Sect. 4.2).
3.3 Energy model
The first-order radio model considers for energy computation (Heinzelman et al. 2000). Energy dissipation in transmitting L bits of data at distance \(d_{\mathrm{o}}\) is shown in Eq. 3.1, where \(E_{\mathrm{ele}}\) is the energy dissipation in transmitter circuitry, and \(E_{\mathrm{amp}}\) is the energy dissipation in amplification.
Energy depletion for receiving L bits of data is mentioned in Eq. 3.2
3.4 Biogeography-based optimization
Biogeography-based optimization was devised by Simon (2008). It is a geographical way of assignment of biological species. Each geographical zone is represented by an index known as a habitat suitability index (HSI). Another index is used to represent the area of habitat and livelihood conditions is called as suitability index variable (SIV). The fitness of each habitat is analogous to its HSI value and number of species. To improve the low HSI solution, it accepts features from high HSI solution. This mechanism is known as biogeography-based optimization (BBO).
The model of species abundance in a single habitat is demonstrated in Fig. 2, where immigration rate is \(\lambda \) and emigration rate is \(\mu \). In the immigration curve, the maximum immigration rate is I when habitat consists of zero species. It is also estimated from this curve, as the number of species increases then \(\lambda \) decreases. The maximum number of species in the habitat is \(S_{\mathrm{max}}\), at that point immigration rate is zero.
In the emigration curve, the maximum emigration rate is E when habitat consists of maximum number of species (\(S_{\mathrm{max}}\)). It is estimated from the curve, as the number of species increases in the habitat, then emigration rate also increases. Moreover, emigration rate is zero, when there is no species in the habitat. At the equilibrium point (\(S_0\)), both immigration and emigration rates are equal.
From the straight line curve as shown in Fig. 2, immigration rate and emigration rate are as follows:
where k is number of species in the habitat, and \(n_{\mathrm{s}}\) is the maximum number of species.
The working principle of BBO is as follows.
3.4.1 Migration
Lets have an optimization problem and a population of candidate solutions, where each solution is represented by a n dimension vector known as a habitat. Each dimension in the habitat is considered to be an SIV. The goodness of a habitat is analogous to HSI value and number of species. To improve the solution, low HSI solution shares information with high HSI solution (similar as GA and PSO), whereas sharing is based on immigration (\(\lambda \)) and emigration rates (\(\mu \)). In this process, two habitats are chosen from the population. Firstly, habitat (\(H_i\)) is selected based on the immigration rate (\(\lambda _i\)), and other habitat (\(H_j\)) is selected using emigration rate (\(\mu _j\)). Afterward, the randomly selected SIVs are migrated from \(H_j\) solution and appears in \(H_i\).
3.4.2 Mutation
In a geographical region, due to some natural disasters, HSI of a habitat changes suddenly and causes habitat deviation from its equilibrium position. Similar effect demonstrated in BBO using mutation operation. It is performed using the species count of each habitat as shown in Eqs. (3.4, 3.5). A probability is assigned to each habitat for mutation. If it is high, it means that there is a less chance for mutation and a solution is nearer to the optimized solution. If it is low, it means a high chance for mutation and a solution is far away from the optimized solution.
where m(s) is mutation rate of S species, \(m_{\mathrm{max}}\) is maximum mutation rate and \(P_{\mathrm{max}}\) is maximum mutation probability.
Merits of mutation operation describe as follows: (i) increase the variety of population. (ii) Resist high HSI solution to disrupt. (iii) Improves high and low HSI solutions.
The demerit of mutation operation is probability of degrade the solution.
4 BERA: the proposed approach
The proposed approach entails of two phases. In the first phase, BBO-based cluster head selection algorithm is executed to select some nodes as CHs (see Sect. 4.1). In the second phase, the proposed routing algorithm is used to compute the data transmission path from each CH to the BS (see Sect. 4.2).
4.1 BBO-based cluster head selection algorithm
It selects near-optimal nodes as CHs among all sensor nodes using residual energy, intra-cluster distance and distance between CHs and the BS.
4.1.1 Representation of habitat
In BBO, a potential solution is called as habitat. In the CH selection phase, a habitat represents a set of sensor nodes to be selected as CHs. The dimension of each habitat is equal to the number of CHs in the network.
4.1.2 Initialization of habitat
Each habitat position is initialized with a random node_id between 1 and n. Let \(H_i = (H_{i,1}(t), H_{i,2}(t),\ldots , H_{i,m}(t))\) be the \(i\hbox {th}\) habitat, where each habitat position \(H_{i,d}, 1\le d\le m\) represents node_id between 1 to n in the network.
Illustration of Fig. 3: let the number of sensor nodes be 100, number of CHs are 10% of total number of nodes and dimension of each habitat is equal to the number of CHs i.e., 10. Now each habitat position \(H_{i,d},1\le d\le 10\) is initialized with random number between 1 and 100, i.e., node_id.
4.1.3 Derivation of fitness function
The fitness function is derived using the following parameters:
-
(a)
Residual energy of cluster head: in the communication process, energy consumption of CH is high due to its functioning such as receiving data from its respective CH members, performing aggregation and then transmitting the data to a CH or the BS. Therefore, sensor node with higher residual energy is a more preferable choice as a CH. It enhances the life of the network. So, our first objective in terms of residual energy is \(f_1\), which can be minimized as follows:
Objective 1
-
(b)
Intra-cluster distance: it is the average distance between CH and its respective members. Energy dissipation of a sensor node depends on transmission distance that is described in Sect. 3.3. If it is minimum, then energy consumption is also less. So, a second objective in terms of intra-cluster distance is \(f_2\), which can be minimized as follows:
Objective 2
-
(c)
Distance between CH and the BS: it is the distance between each CH to the BS. Energy consumption of a sensor node depends on transmission distance that is described in Sect. 3.3. In the data transmission process, CHs transmitting data to the BS. Therefore, CHs with minimum distance from the BS is a more preferable choice. So, our third objective is \(f_3\), which can be minimized as follows:
Objective 3
All of the above stated objectives are not strongly conflicting with each other. Therefore, the weighted sum approach is applied and all objectives converted into a single objective function as shown in Eq. 4.5, where \(\alpha _1\), \(\alpha _2\) and \(\alpha _3\) are the weights assigned to each objective. As we know that all the objectives have different units and values, therefore, min–max normalization function is applied to each objective using Eq. 4.4.
where \(f_i\) is the value of the function, \(f_{\mathrm{min}}\) is minimum value, \(f_{\mathrm{max}}\) is maximum value and F(x) is the normalized value between 0 and 1.
4.1.4 Habitat migration
In the migration process, firstly habitat (\(H_i\)) is selected based on the immigration rate (\(\lambda _i\)) probabilistically. Thereafter, another habitat (\(H_j\)) is also selected based on the emigration rate (\(\mu _j\)) in a probabilistic way. After selection of two habitats, some SIVs from \(H_j\) appears in \(H_i\), i.e., node_ids of the high HSI solution appears in the low HSI solution. For that, one position is randomly generated between 1 and \(m\hbox {th}\) dimension. From generated position to the last position, all node_ids from \(H_j\) appears in \(H_i\) solution. In this way, all habitats are updated until the best solution is achieved.
Illustration of Fig. 4: it shows all the steps from habitat initialization to the migration process. In Fig. 4a, all the habitats are initialized randomly by generating node_id between 1 and n. Afterward, HSI of each habitat is calculated using Eq. 4.5 as shown in Fig. 4b and species are distributed accordingly as demonstrated in Fig. 4c. The immigration rate (\(\lambda _i\)) and emigration rate (\(\mu _j\)) of each habitat are calculated based on the number of species as shown in Fig. 4d. In migration process, firstly, a habitat \(H_4\) is selected based on high immigration rate (\(\lambda _4=0.99\)) and \(H_5\) is also selected based on high emigration rate (\(\mu _5=0.77\)). Afterward, a random position (say \(5\hbox {th}\)) is chosen among all the positions. Then from \(5\hbox {th}\) position onward all the SIVs from \(H_5\) appears in \(H_4\) habitat, i.e., node_ids as shown in Fig. 4e.
4.1.5 Mutation
For example, we consider 100 sensor nodes in a target area with node_ids ranges from 1 to 100. In mutation, a habitat is selected by considering the mutation probability. Afterward, a random position/SIV is chosen in the habitat and its value is replaced with node_id generated randomly between 1 and 100.
Illustration of Fig. 5: let the emigration rate of \(H_1\)–\(H_5\) habitats as [0.02, 0.13, 0.07, 0.01, 0.77] is shown in Fig. 5a, and its corresponding mutation probability is calculated and shown in Fig. 5b. Suppose a habitat \(H_4\) is selected for mutation and the random number (rand) is generated between 0 and 1. If rand is less than the mutation probability (\(M_4\)), then mutation is performed. For that, a random position is selected (say \(6\hbox {th}\)) within a habitat and its corresponding position value is replaced with newly generated random nod_id between 1 and 100. In Fig. 5c, \(N_3\) is replaced with \(N_{91}\).
4.1.6 Pseudo-code of BBO-based cluster head selection algorithm
4.2 BBO-based routing algorithm
In the second phase, the near-optimal route from each CH to the BS is computed based on residual energy, distance and node degree of CH.
4.2.1 Representation of habitat
In routing, each habitat represents the data forwarding path from every CH to the BS. The dimension of each habitat is equal to the total number of CHs in the network.
4.2.2 Initialization of habitat
Here, the dimension of the habitat is equal to the number of CHs in the network. Let \(H_{i}= (H_{i,1}(t), H_{i,2}(t),\ldots ,H_{i,m}(t))\) be the \(i\hbox {th}\) habitat, where each position \(H_{i,d}, 1\le d \le m\) denotes next-hop (\(\hbox {CH}_j\)) toward the BS as shown in Fig. 7.
Example 1
Let the number of CHs are 10 and BS is denoted by Id 11 as shown in Fig. 6. Therefore, the dimension of a habitat is 10. Now, for every position \(H_{i,d}, 1\le d \le 10\) is initialized by randomly generated next-hop within its range as shown in Fig. 7. The routing path from every CH to the BS is mentioned in Table 2.
4.2.3 Derivation of fitness function
The formulation of fitness function is based on following parameters: residual energy, euclidean distance and node degree.
-
(a)
Residual energy of next-hop node: our first objective is to consider the residual energy of the next-hop (NH) node use to relay the data toward the BS. If the residual energy of a NH node is high, it would be more preferable choice for data to receive, aggregate and transmit to the next CH or the BS. So, our first objective in terms of residual energy is \(g_1\), which can be maximized as follows:
Objective 1
-
(b)
Euclidean distance: it is the distance from the CH to the NH node and from there to the BS. As shown in Sect. 3.3, energy consumption depends on transmission distance. If the distance is minimum, it will expense less amount of energy and will also increase the life of the network. So, the second objective in terms of distance is \(g_2\), which can be maximized as follows:
Objective 2
-
(c)
Node degree: it is the number of CH members contained by NH node. If the node degree of NH node is less, then it consumes less energy to receive the data from its respective members and sustain for a longer duration. So, the third objective in terms of node degree is \(g_3\), which can be maximized as follows:
Objective 3
As all the objectives weekly conflicting to each other, a weighted sum approach is applied and the weighted value is assigned to each objective. In this way, all multiple objectives converted into the single objective function as shown in Eq. 4.9. Here, \(\beta _1\), \(\beta _2\) and \(\beta _3\) are weighted value assigned to each objective. As we know that all objectives have different units and values. Therefore, normalization function is applied to each objective as shown in Eq. 4.4.
4.2.4 Habitat migration
In migration process, two habitats are selected probabilistically. The first one (\(H_i\)) is selected based on immigration rate (\(\lambda _i\)). Another one (\(H_j\)) is selected based on emigration rate (\(\mu _j\)). Afterward, some NHs from high HSI solution (\(H_j\)) appears in the low HSI solution (\(H_i\)). For that, one position is randomly generated between 1 and \(m\hbox {th}\) dimension. From generated position onward, all NHs from \(H_j\) appears in \(H_i\). In this way, habitats are updated until the best solution is achieved.
Illustration of Fig. 8: it shows all the steps from habitat initialization to the migration process. In Fig. 8a, all the habitats are initialized. For that, every CH chooses NH randomly within its communication range. Afterward, the HSI value of each habitat is calculated using Eq. 4.9 as shown in Fig. 8b and species are distributed accordingly as demonstrated in Fig. 8c. The immigration rate (\(\lambda _i\)) and emigration rate (\(\mu _j\)) of each habitat are computed based on the number of species as depicted in Fig. 8d. In migration process, two habitats are chosen. Firstly, a habitat \(H_5\) is selected based on high immigration rate (\(\lambda _4=0.87\)). Another habitat \(H_1\) is selected based on high emigration rate (\(\mu _5=0.27\)). Finally, a random position ( say \(5\hbox {th}\)) is chosen among all the positions. Then, from \(5\hbox {th}\) position onward all the SIVs from \(H_1\) appears in \(H_5\) habitat i.e., NHs as shown in Fig. 8e.
4.2.5 Mutation
In mutation process, we have considered habitat (\(H_i\)) based on mutation probability. It is computed using emigration and immigration rate as shown in Eq. 3.4. The chance of habitat to be selected is less if the mutation probability is high and vice versa. In a habitat \(H_i\), a randomly selected position change its NH by choosing random NH within its range.
Illustration of Fig. 9: let the emigration rate of \(H_1\)–\(H_5\) habitats as [0.27, 0.23, 0.20, 0.17, 0.13] is shown in Fig. 9a and its mutation probability is computed as demonstrated in Fig. 9b. Suppose, a habitat \(H_5\) is selected based on its mutation probability (\(M_5\)). Thereafter, a random position is chosen in \(H_5\) (say \(6\hbox {th}\)) and the corresponding position value (i.e., NH) is replaced with randomly selected NH from its communication range, i.e., \(\hbox {CH}_8\) is replaced with \(\hbox {CH}_{10}\) as shown in Fig. 9c.
4.2.6 Pseudo-code of BBO-based routing algorithm
5 Performance analysis
To evaluate the performance of BERA, simulation was performed using JAVA programming and results are plotted using MATLAB (version 7.11). The parameters considered for WSN and BERA are listed in Tables (3, 4). We have extensively tested the proposed algorithm in three different scenarios. In the first scenario, we have positioned the BS at the center of the target area \(\left( 100\times 100\,\hbox {m}^2\right) \), further at the corner \(\left( 200\times 200\,\hbox {m}^2\right) \) and finally at outside \(\left( 250\times 250\,\hbox {m}^2\right) \). In performance analysis, some existing algorithms are executed on similar platform such as DHCR (Maryam and Reza 2015), Hybrid routing (HF) Abdulla et al. (2012) and EADC (Yu et al. 2012). To show the full potential of BERA, we have also executed well-established optimization techniques GA and PSO on the same problem with same fitness function and termed as GA-routing and PSO-routing.
5.1 Performance metrics
The performance metrics used for the analysis of the proposed and existing algorithms are as follows:
-
Residual energy: in WSN, sensor node dissipates its energy while data receiving, processing and transmitting to the BS. After performing these tasks, remaining energy of a node is called as residual energy. Network performance can be enhanced by saving adequate amount of residual energy of sensors.
-
Number of alive nodes: it is the number of nodes alive in the network. It can be expressed in different ways such as last node is alive or half of the nodes are alive or some percentage of nodes are alive in the network. If the number of alive nodes increases, it will increase the network performance.
-
Data packets received at the BS: every node senses the environment and collects information. Afterward, it transmits the collected information in the form of the data packets to the BS. If the number of alive nodes is in large quantity and residual energy of sensors is also high, then more information is collected and subsequently a large number of data packets are transmitted to the BS.
5.1.1 Performance measurement in terms of residual energy
In this section, performance of the proposed algorithm is analyzed with some existing algorithms as shown in following Figs. 10 and 11.
Illustration of Fig. 10: it shows the performance analysis of the proposed algorithm with PSO-routing and GA-routing in terms of residual energy. In Fig 10a, it is observed that the performance of BERA is better than GA-routing and PSO-routing, when BS was placed at the center. In Fig. 10b, performance of BERA is nearly equal to PSO-routing and GA-routing, when BS was placed at the corner. In Fig. 10c, performance of BERA is found slightly equal to GA-routing and PSO-routing, when BS was placed at outside of the target area. In this test, BERA outperforms GA-routing and PSO-routing in most of the cases. So, BERA is well suited for WSN where residual energy is an important factor.
Illustration of Fig. 11: it shows the comparative results of BERA with existing approaches such as HF, EADC and DHCR in terms of residual energy. In Fig. 11a–c, BERA shows the superior performance over HF, EADC and DHCR in all the cases, i.e., when BS was placed at the center, corner or outside of the target area. This is due to the fact that in the derivation of fitness functions one of the objectives is distance. In the CH selection algorithm, distance between CH members to its respective CH is taken into consideration. In the routing algorithm, distance from CH to the next-hop and from there to the BS is considered, which reduces the energy dissipation in the transmission process. Therefore, BERA outperforms existing routing techniques.
5.1.2 Performance measurement in terms of number of alive nodes
This section shows the performance of BERA with existing routing algorithms, GA-routing, and PSO-routing in terms of number of alive nodes.
Illustration of Fig 12: it shows the comparative analysis of the proposed algorithm with PSO-routing and GA-routing in terms of number of alive nodes. In Fig 12a, it shows that the performance of PSO-routing is better than GA-routing and almost similar to BERA, when BS was placed at the center. In Fig. 12b, it implies that the performance of BERA is superior than its comparatives, when BS was placed at the corner. Figure 12c demonstrates that the performance of BERA is nearly same as GA-routing and PSO-routing, when BS was placed at the outside of the target area. Therefore, in this test BERA is competitive/superior over PSO and GA-based routing techniques. So, BERA is well suited for those applications of WSN, where the number of alive nodes is an important factor.
Illustration of Fig. 13: it shows the performance comparison of BERA with some existing routing approaches. In Fig. 13a, it shows that BERA outperforms HF, EADC and DHCR, when BS was placed at the center. In Fig. 13b, it is demonstrated that BERA performs better than HF, EADC and DHCR, when BS was placed at the corner. In Fig. 13c, it depicts that BERA performs better than HF, EADC and DHCR, when BS was placed outside of the target area. It implies that proposed technique BERA selects a better path for the communication, which sustains for a longer duration. This is due to the fact that in both the derived fitness functions, one of the objectives is residual energy. First, we have considered residual energy for the CH selection process. Afterward, again residual energy has been considered for the NH selection in the routing process in addition to the node degree. Therefore, in all the cases BERA outperforms comparatives. Another important observation is that the number of alive nodes are decreasing rapidly in HF, EADC and DHCR. Therefore, these protocols are not suitable for large WSN.
5.1.3 Performance measurement in terms of data packets received at the BS
This section shows the performance of BERA with some existing routing algorithms and other tested optimization techniques in terms of the number of data packets received at the BS.
Illustration of Fig. 14: it shows the comparative performance of BERA, PSO-routing and GA-routing in terms of the number of data packets received at the BS. It is observed that the number of packets received at the BS in BERA are almost similar to PSO-routing and GA-routing, when BS was placed at the center. In second observation, BERA received more number of data packets compare to PSO-routing and GA-routing, when BS was placed at the corner. In third observation, BERA outperforms PSO-routing and GA-routing, when BS was placed outside of the target area. In most of the cases, BERA confirms the superiority over other optimization techniques. The is due to the fact that the number of packets received at the BS depends on residual energy and the number of alive nodes as described in Sect. 5.1.
Illustration of Fig. 15: it shows the number of data packets received at the BS of BERA, HF, EADC and DHCR routing techniques. It is estimated that the number of packets received at the BS in BERA is more than HF, EADC and DHCR in all the cases, i.e., when BS was placed at the center, corner and outside of the target area. Another important observation is that the number of packets received at the BS decreases rapidly in EADC and HF, when BS was placed at the corner or outside of the target area while consistent in BERA. The reason behind that fitness function derivations described in Sects. (4.1.3, 4.2.3) take care of objectives in such way that it saves the residual energy and resist to number of alive nodes to demise earlier, it will increase the data packets received at the BS.
6 Conclusion
Finding an optimal route from each sensor node to the BS through CHs is a computationally expensive task in WSNs. Moreover, possible routes increase exponentially with the size of the network. In this situation, bio-inspired optimization algorithms offer an attractive alternative to resolve above stated problem. Biogeography-based optimization (BBO) is a recent paradigm for solving optimization problems. In the present study, an effort has been made to establish BBO as an efficient algorithm for solving WSN-related problems. A new objective function based on residual energy, intra-cluster distance and distance from CH to the BS was derived for CH selection. A BBO-based routing algorithm was proposed which considers residual energy, distance and node degree as metrics of the fitness function. The proposed algorithms were rigorously tested and compared with existing algorithms. Firstly, BERA was compared with well-established routing algorithms such as HF, EADC and DHCR, it performed better in most of the cases on various scenarios. To show the full potential of BERA, aforementioned problems were also solved by other bio-inspired optimization techniques such as GA and PSO with same fitness functions. It found that in most of the cases BERA was competitive and/or better than GA and PSO.
References
Abdulla AEAA, Nishiyama H, Kato N (2012) Extending the lifetime of wireless sensor networks: a hybrid routing algorithm. Comput Commun 35:1056–1063
Agarwal PK, Procopiuc CM (2002) Exact and approximation algorithms for clustering. Algorithmica 33(2):201–226
Bagci H, Yazici A (2010) An energy aware fuzzy unequal clustering algorithm for wireless sensor networks. In: Proceedings of the IEEE international conference on fuzzy system, pp 1–8
Bagci H, Yazici A (2013) An energy aware fuzzy approach to unequal clustering in wireless sensor networks. Appl Soft Comput 13(4):1741–1749
Bhari A, Wazed S, jaekal A, Bandyopadhyay S (2009) A genetic algorithm based approach for energy efficient routing in two-tiered sensor networks. Ad-Hoc Netw 7:665–676
Bhattacharya A, Chattopadhyay PK (2011) Hybrid differential evolution with biogeography-based optimization algorithm for solution of economic emission load dispatch problems. Exp Syst Appl 38(11):14001–14010
Chang JY, Ju PH (2012) An efficient cluster-based power saving scheme for wireless sensor networks. EURASIP J Wirel Commun Netw 172:1–10
Chatterjee A, Siarry P, Nakib A, Blanc R (2012) An improved biogeography based optimization approach for segmentation of human head CT-scan images employing fuzzy entropy. Eng Appl Artif Intell 25:1698–1709
Dorigo M, Birattari M, Stutzle T (2006) Ant colony optimization. IEEE Comput Intell Mag 1(4):28–39
Elhabyan RSY, Yagoub MCE (2015) Two-tier particle swarm optimization protocol for clustering and routing in wireless sensor network. J Netw Comput Appl 52:116–128
Heinzelman WR, Chandrakasan A, Balakrishnan H (2000) Energy-efficient communication protocol for wireless microsensor networks. In: Proceedings of the 33rd Hawaii international conference on system sciences, pp 1–10
Heinzelman WB, Chandrakasan AP, Balakrishnan H (2002) An application specific protocol architecture for wireless microsensor networks. IEEE Trans Wirel Commun 1:660–670
Jamuna K, Swarup KS (2011) Biogeography based optimization for optimal meter placement for security constrained state estimation. Swarm Evolut Comput 1(2):89–96
Jian JC, Ren WC, Min X, Lun TX (2010) Energy-balanced unequal clustering protocol for wireless sensor networks. J China Univ Posts Telecommun 17(4):94–99
Kumar SS, Kumar MN, Sheeba VS (2011) Fuzzy logic based energy efficient hierarchical clustering in wireless sensor networks. Int J Res Rev Wirel Sens Netw 1:53–57
Kundra H, Kaur A, Panchal V (2009) An integrated approach to biogeography based optimization with case based reasoning for retrieving groundwater possibility. In: Proceedings of the 8th annual Asian conference and exhibition on geospatial information, technology and applications
Lai Wk, Fan CS, Lin LY (2012) Arranging cluster sizes and transmission ranges for wireless sensor networks. Inf Sci 183(1):117–131
Lee JS, Cheng WL (2012) Fuzzy-logic-based clustering approach for wireless sensor networks using energy prediction. IEEE Sens J 12(9):2891–2897
Li H, Liu Y, Chen W, Jia W, Li B, Xiong J (2013) COCA: constructing optimal clustering architecture to maximize sensor network lifetime. Comput Commun 36(3):256–268
Lindsey S, Raghavendra CS (2002) Power-efficient gathering in sensor information system. In: Proceedings of the IEEE aerospace conference 3, p 112530
Liu AF, You WX, Gang CZ, Hua GW (2010) Research on the energy hole problem based on unequal cluster-radius for wireless sensor networks. Comput Commun 33(3):302–321
Mao S, Zhao C, Zhou Z, Ye Y (2013) An improved fuzzy unequal clustering algorithm for wireless sensor network. Mob Netw Appl 18:206–214
Maryam S, Reza NH (2015) A decentralized energy efficient hierarchical cluster-based routing algorithm for wireless sensor networks. Int J Electron Commun 69:790–799
Panchal V, Singh P, Kaur A, Kundra H (2009) Biogeography based satellite image classification. Int J Comput Sci Inf Secur 6(2):269–274
Ran G, Zhang H, Gong S (2010) Improving on LEACH protocol of wireless sensor networks using fuzzy logic. J Inf Comput Sci 7(3):767–775
Rao PS, Banka H (2015) Energy efficient clustering algorithms for wireless sensor networks: novel chemical reaction optimization approach. Wirel Netw 1–20. doi:10.1007/s11276-015-1156-0
Rao PS, Banka H (2016) Novel chemical reaction optimization based unequal clustering and routing algorithms for wireless sensor networks. Wirel Netw 1–20. doi:10.1007/s11276-015-1148-0
Rao PS, Jana PK, Banka H (2016) A particle swarm optimization based energy efficient cluster head selection algorithm for wireless sensor networks. Wirel Netw 1–16. doi:10.1007/s11276-016-1270-7
Rarick R, Simon D, Villaseca F, Vyakaranam B (2009) Biogeography-based optimization and the solution of the power flow problem. In: Proceedings of the IEEE conference on systems, man, and cybernetics. San Antonio, pp 1029–1034
Roy P, Ghoshal S, Thakur S (2010) Biogeography-based optimization for economic load dispatch problems. Electr Power Compon Syst 38:166181
Senouci MR, Mellouk A, Senouci H, Aissani A (2012) Performance evaluation of network lifetime spatial–temporal distribution for WSN routing protocols. J Netw Comput Appl 35:1317–1328
Simon D (2008) Biogeography-based optimization. IEEE Trans Evolut Comput 12(6):702–713
Singh AK, Purohit N, Varma S (2013) Fuzzy logic based clustering in wireless sensor networks: a survey. Int J Electron 100:126–141
Song M, Cheng-Lin Z (2011) Unequal clustering algorithm for WSN based on fuzzy logic and improved ACO. J China Univ Posts Telecommun 18:89–97
Taheri H, Neamatollahi P, Younis OM, Naghibzadeh S, Yaghmaee MH (2012) An energy-aware distributed clustering protocol in wireless sensor networks using fuzzy logic. Ad-Hoc Netw 10(7):1469–1481
Wang L, Xu Y (2011) An effective hybrid biogeography-based optimization algorithm for parameter estimation of chaotic systems. Expert Syst Appl 38(12):15103–15109
Wang A, Yang D, Sun D (2012) A clustering algorithm based on energy information and cluster heads expectation for wireless sensor networks. Comput Electr Eng 38:662–671
Xu J, Liu W, Lang F, Zhang Y, Wang C (2010) Distance measurement model based on RSSI in WSN. Wirel Sens Netw 2(08):606–611
Yang J, Ju PH (2014) An energy-saving routing architecture with a uniform clustering algorithm for wireless sensor networks. Future Gener Comput Syst 36:128–140
Younis O, Fahmy S (2004) A hybrid energy-efficient, distribution clustering approach for ad-hoc sensor networks. IEEE Trans Mob Comput 3:366–379
Yu H, Xiaohui W (2011) PSO-based energy-balanced double cluster-head clustering routing for wireless sensor networks. Proc Eng 15:3073–3077
Yu J, Qi Y, Wang G, Gu X (2012) A cluster-based routing protocol for wireless sensor networks with nonuniform node distribution. Int J Electron Commun 66:54–61
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
The authors declare that they have no conflict of interest.
Additional information
Communicated by V. Loia.
Rights and permissions
About this article
Cite this article
Lalwani, P., Banka, H. & Kumar, C. BERA: a biogeography-based energy saving routing architecture for wireless sensor networks. Soft Comput 22, 1651–1667 (2018). https://doi.org/10.1007/s00500-016-2429-y
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00500-016-2429-y