DOI:10.32604/iasc.2021.016780
| Intelligent Automation & Soft Computing DOI:10.32604/iasc.2021.016780 | |
| Article |
Improving Network Longevity in Wireless Sensor Networks Using an Evolutionary Optimization Approach
1Department of Computer Science and Engineering, SSM Institute of Engineering and Technology, TamilNadu, 624002, India
2Department of Electronics and Communication Engineering, NPR College of Engineering and Technology, Tamil Nadu, 624401, India
3Department of Electronics and Communication Engineering, PSNA College of Engineering and Technology, TamilNadu, 624622, India
*Corresponding Author: V. Nivedhitha. Email: v.nivedhitha.it@gmail.com
Received: 11 January 2021; Accepted: 25 February 2021
Abstract: Several protocols strive to improve network longevity but fail to ameliorate the uneven overhead imparted upon the sensor nodes that lead to temporal deaths. The proposed work uses a metaheuristic approach that promotes load balancing and energy-efficient data transmission using the fruit fly optimization algorithm (FFOA). The approach combines the LEACH protocol with differential evolution (DE) to select an optimum cluster head in every cluster. The algorithm is designed to provide energy-efficient data transmissions based on the smell and vision foraging behavior of fruit flies. The approach considers the compactness of nodes, energy capacity, and the distance of sensor nodes from the base station and geocentric location, and other factors to select an optimal cluster head. It provides an optimal solution for the nodes in overlapping cluster heads and the energy problem that occurs due to uneven clustering. The metaheuristic approach implements multi-hop routing by finding an optimal path and allows the cluster head re-election strategy when the data transmission is intense. Simulations prove that FFOA-based LEACH increases the network lifetime through energy-efficient clustering and routing when compared with LEACH and DE-LEACH.
Keywords: LEACH; differential evolution; fruit fly optimization algorithm; cluster head selection; multi-hop routing
Wireless sensor networks (WSNs) have attracted interest in recent years for many applications where human intervention is not possible. Application-oriented sensor nodes are positioned in a geographical location referred to as a sensing field to perceive the changes in the surroundings. These sensor nodes are of low cost, use less power, and have limited transmission capability. Hence, prolonging the lifetime of WSNs is a major challenge in addition to security, reliability, and scalability [1]. Balancing the energy consumption for the sensing and transmission of data can be achieved by clustering. This process organizes a set of sensor nodes, which are referred to as clusters, based on criteria like distance or location. Clustering enables these clusters to elect a cluster head that acts as a leader node. The remaining sensor nodes are member nodes. The choice of opting for the cluster head is yet another challenge as energy efficiency becomes a major concern. The role of member nodes is to observe the real-world environment and measure parameters such as temperature, humidity, and other parameters. The cluster head accumulates the data from various member nodes and communicates them to the base station using hopping. Thus, clustering reduces the remarkable amount of energy spent by individual nodes to transfer data to the sink. Hopping is another mechanism to lessen the utilization of energy by nodes. The aggregated data from the sensor nodes to the sink node must be transmitted by the cluster heads using either single- or multi-hop routing techniques [2]. The former delivers data transfer directly from the cluster head to the base station without using intermediate cluster heads, whereas the latter relays data from the cluster head to the base station using one or more intermediate cluster heads.
Several protocols exist to perform energy-efficient clustering and routing [3] like HEED, TEEN, APTEEN, GEAR, SPEED, and others. However, energy optimization in WSNs remains a very active research area. The LEACH protocol is a probabilistic clustering technique that facilitates the usage of limited energy by sensor nodes. Numerous sensor nodes are expanded over the sensing field. The sensor nodes are grouped into clusters, each having a cluster head that is selected if it fulfills essential criteria: The primary factor for a normal node to become a cluster head is that it should possess high energy at any point in time. The secondary factor is the distance from the self-node to its neighboring nodes. LEACH has some disadvantages in addition to it performing a probabilistic approach to elect cluster heads with low message overheads [4]. Cluster heads are chosen where the intra-cluster communication can be done faster by covering a lesser distance from the cluster head to the member nodes. Thus, high-energy nodes exist that are at longer distances and have fewer neighboring nodes. The cluster head suffers from premature death since it prolongs usage of the same nodes to route data packets and produces uneven energy consumption. This hostile environment is distributed with a compact set of nodes, and more than one node may appear in two adjacent clusters. As a result, this may cause the node to communicate with both cluster heads, which leads to data replication.
The proposed paper depicts a blend of differential evolution (DE) with a metaheuristic approach using the fruit fly optimization algorithm (FFOA) to choose the cluster heads. The study also strives to render optimal path selection of cluster heads to the base station and analyzes multiple ways to discover an energy-efficient network. The cluster heads are re-elected whenever the residual energy goes below the threshold to promote the network lifetime and to thus reduce the premature death of nodes.
Section 3 describes fruit fly behavior and the mathematical model of the way the flies locate their food. This Section hybridizes DE with optimization of the fruit fly algorithm to perform clustering in the LEACH protocol. Section 4 portrays multi-hop routing using the Floyd-Warshall algorithm. Implementation results are discussed in Section 5, and the final conclusion and future scope are presented in Section 6.
LEACH, an improved energy-efficient communication model [5], was proposed for WSNs. LEACH uses low energy medium access control to perform application-specific data aggregation. The method realizes self-configuring cluster formation through a randomized probabilistic value. The cluster heads were selected based on the probability value, Pi(t), given in Eq. (1).
where N is the total node count and k is the cluster count in every round. Since the sensor nodes follow a randomized rotation of cluster heads, the nodes do not result in temporal deaths. The probability of a node becoming a cluster head is given by Eq. (2). The main disadvantage of LEACH is the random selection of clusters and cluster heads.
An improved version of the LEACH protocol curtailed the energy utilization for data transmission in WSNs [6]. This method considers the remaining energy of the nodes and compares it with the average threshold residual value. The node distance between the base station and sensor node is another parameter considered for opting for a node as the cluster head. The protocol undergoes three phases. The first is the setup phase that selects the cluster head based on the energy model, forms the cluster through message exchanges, and schedules the member node based on time division multiple access (TDMA) and code division multiple access (CDMA) techniques. The second phase is the steady-state phase that finds a path from the cluster head to the base station. The last phase is the data transmission phase, which sends data packets through the hopping technique. Simulation results surpassed the outcomes for the LEACH and LEACH-C protocols. A comparison of several protocols was made [7] and a modified LEACH protocol was proposed to use energy efficiently in WSN. The cluster head was elected depending on the distance and energy parameters. In relation to the LEACH protocol, the author updated the energy model of the LEACH system and proved that living nodes are large at any point of time. An extensive study was made on several evolutionary approaches [8] to improve the lifetime of sensor nodes in WSN. A modified version of the FFOA was described to perform energy efficacy. A fitness value was computed based on distance, and energy was formalized to perform intelligent searching. The simulated results show that the algorithm improved the network lifetime when evaluated with FFOA and DE algorithms.
A biologically inspired optimal method [9] was proposed to perform clustering and routing in heterogeneous WSNs. A genetic algorithm defines a search-based optimization procedure that determines a better solution. The solutions are referred to as hypotheses and the members of the population having the set of hypotheses are the chromosomes. Successors are identified based on selection, mutation, and crossover of the existing hypotheses. A hypothesis fitness function satisfying all the criteria, including residual energy, energy overhead expected, node position, and distance to the base station, is generated over several iterations. The fitness function is given in Eq. (3):
The well-known particle swarm optimization (PSO) clustering [10] algorithm was modeled to improve clustering for WSN. The principle behind this evolutionary algorithm is to optimize the search time for food by birds in a flock over a region. Stationary sensor nodes are arbitrarily positioned over the studied region. The evolutionary algorithm maximizes the network lifetime to a greater extent by considering the minimal usage of energy. The optimization approach performs several rounds of two operations, namely the setup phase and the steady-state phase. The setup phase organizes the sensor nodes and elects the cluster heads. This is followed by the steady-state phase, which enables the sensor nodes to accumulate data and periodically send them to the base plate through cluster heads. The cluster heads were selected based on the fitness function calculated by every node. The evaluation is performed by all nodes that choose the cluster head closest to them.
An evolutionary-based optimization algorithm was presented based on the prey chasing behavior of grey wolves [11]. A great deal of energy is spent in performing cluster head selection while performing clustering in wireless networks. A hierarchical clustering-based protocol addresses the issue by reducing energy spent for control message exchanges through piggybacking and hand-over techniques. The cluster heads are nominated if they have more impact on the current energy level of each node. The nodes with higher ranks are elected as cluster heads, thus reducing the number of control messages among the sensor nodes. Member nodes sense the real-world parameters and communicate them to the cluster heads as data packets using the radio transmitter. The cluster heads, after turning on its receiver, collect the packets from its member nodes and send the data to the base station after pre-processing. A new algorithm was formulated to perform routing based on the ant colony optimization (ACO) technique [12]. The proposed scheme uses an improved ACO method to perform clustering by considering the energy capacity and path distance of the nodes. A pseudo-random path establishment technique is used to provide an energy-efficient route. The technique replaces flooding by performing opportunistic broadcasting of control data. An improved clustering and routing protocol [13] with efficient resource exploitation was developed. This work proposed a modified PSO-based clustering protocol to perform the selection of cluster heads in an optimum way by considering the start time and delivery time for energy and data communication to check for malicious intrusion. A multi-hop firefly optimized routing was developed based on certain key features to ensure security in data transmission. Cluster heads were selected based on simulations that prove that the approach is far better than previous work. A swarm intelligence-based technique, which was inspired by the FFOA sensing technique, [14] was developed for the traveling salesman problem (TSP). The flies perform a rummaging behavior to smell the food around them with the aid of olfactory organs. The fruit flies determine the smell concentration value (SCV) of the flies and perform vision-based search based on the best SCV as shown in Fig. 1.
Figure 1: Flow graph of FFOA
3 FFOA-LEACH Optimization Protocol
The selection of cluster head plays a predominant role in establishing the WSN and reducing the extent of the temporal death of nodes. This can be achieved by combining the DE and FFOA [15] with the existing LEACH protocol.
The main motivation behind the proposed work is to examine the existing methods and develop a more energy-efficient WSN. Usually, proactive protocols are applied for intra-cluster communication and reactive protocols are used for inter-cluster communications. Routing enables connectivity between sensor nodes and improves the mobility of data. The following assumptions and network models are implemented to improve the residual energy of the nodes:
• The cluster heads and member nodes are kept with the least mobility, and the base station is kept static.
• Communication between the member nodes and the cluster heads are bidirectional.
• The network consists of cluster heads, member nodes, base station, and helper cluster head to assist the cluster heads if needed.
• Multi-hop routes should be established from the cluster head. Routes cannot be established by member nodes.
• Routes are given with an identification number (ID) to perform message exchanges.
• Channel capacity may vary from node to node according to link strength.
• Least hop count makes the data packets reach the base station quickly.
• Time-division multiple access with collision detection can be implemented.
• A member node can sense and send the data and sleep if no data are sensed or exchanged. A node selected as cluster head or helper cluster head will not sleep.
Procedure for LEACH-DE-FFOA
The steps for LEACH-DE-FFOA are as follows:
Step A: Initial selection of cluster heads using the energy model of LEACH.
Step B: Assess the fitness function (ffn) using DE.
Step C: Find the initial positions of fruit flies using DE.
Step D: Selection of cluster heads using FFOA with the following steps:
a) Handle nodes that are common to two or more clusters.
b) Find an optimal path using multi-hop transmission.
Step E: Calculate the residual energy of cluster heads:
a) If cluster heads consume more energy, repeat step 4.
b) Or if cluster heads consume less energy, Stop.
The nodes in the network are considered to be static in the network. Messages are exchanged between the neighboring nodes to share the location and energy information. The cluster head is selected for the first time based on two important facets: the node has more energy capacity and the node is nearer to the base station. The cluster heads have the role of aggregating data from member nodes using their limited memory and power and need to send the same information to the base station through the least hops. Hence, the cluster heads nearer to the base station can transmit data faster without spending much more energy than those that are farthest.
The proposed protocol considers the geometric center (GC) of the network based on the density of the nodes. The cluster heads nearer to the GC are considered to be super cluster heads and possess more neighbors nearby. The super cluster heads relay the data transferred by the cluster heads that are farthest from the base station. If a cluster is dense, it is likely to aggregate data from its member nodes with lesser energy as the distance is smaller between member nodes and the cluster head. Etemp is formulated as in Eq. (4) based on the geometric center model:
Here,
IEm Inceptive Energy of a node, m
REm Residuary Energy of node m
dtoBS Euclidean distance of node m to BS.
dfartoBS Euclidean distance of the farthest node to BS.
dtoGC Euclidean distance between a node to the geometric center.
dfartoGCEuclidean distance from the farthest node to the geometric center.
The Nc factor represents the number of nodes that a cluster head can cover. The probability of a node ‘i’ at time‘t’ becoming a cluster head can be formulated as in Eq. (5) based on the obtained Etemp value:
The proposed methodology uses DE to find the positions of nodes through mutation, crossover, and selection [16].
In the first step, the initial fitness/adaptive function of the parent generation is defined. In the subsequent production, if the appropriateness of the child is superior to the parent, then the fitness value of the child is considered and replaces the set of parents with children. If not, then the fitness function value of the parent is considered when selecting the cluster head in the next iteration. This helps to fix the primary positions of the fruit flies in the FFOA. The spots of the fruit flies are identified based on mutation value, crossover probability, and mutation probability as in Eqs. (6) and (7):
where Mc represents the number of individuals exchanged in the group, B represents the number of mutated genes, and M represents the number of individuals in a population. Eqs. (6) and (7) can be optimized based on the fitness function in every round. The final crossover probability remains the Pcross value if the fitness value is less than the average fitness value. Otherwise, the following applies:
Similarly, the final mutation probability will be the same as Pmut if the fitness value is less than the average fitness value. Otherwise, the following applies:
where fmff represents the maximum fitness function value.
The limitation of DE is that it requires more time to find the search distance during the initial steps. Sometimes it may be inaccurate due to the failure of global search. Hence, FFOA is used to minimize the scope of the search. FFOA follows the shortest distance between the nodes to improve the search accuracy. Let ds be the shortest distance between the nodes and dsFFtoB be the shortest distance between the initial position of the fruit fly and the boundary. Search scope is then defined as:
dss = dsFFtoB * (1 – n/k),
where k is dsFFtoB/ds. The approach selects cluster heads such that the average distance between the cluster heads is short. Therefore the reduced energy consumption, Eopt, is modeled as in Eq. (8):
Similarly, the common nodes between clusters may lead to replication of data and cause energy loss to the cluster heads [17]. This can be avoided by segmenting the nodes between the clusters properly so that no node appears to be the member of two or more clusters as shown in Fig. 2.
Figure 2: Handling common nodes
The replication of data transfer by a node through two distinct cluster heads must be eliminated. The common nodes therefore have an entry for the hop count and distance to reach the respective cluster heads. A node can transmit data through the corresponding cluster head to the base station based on the least hop count value maintained within it. In such a case, the energy consumption can still be optimized as in Eq. (9):
where
When the cluster heads are elected using the LEACH-DE-FFOA protocol, they are advertised to form clusters by announcing cluster head_ADV. The nodes other than cluster heads reply JOIN_REQ to the corresponding cluster head. In turn, the cluster head accepts the member node based on its closeness and allocates the schedule using the TDMA approach. When member nodes receive the slot to transfer data, they transmit packets and return to the sense/sleep mode. The cluster head performs aggregation of data packets from all its member nodes and communicates them to the base station [18]. The data transmission scheme is shown in Fig. 3.
Figure 3: Data Transmission in WSN
The limitation ofthe cluster head is that it may lose more energy when data packets are too numerous. In such a condition, a helper-cluster head is represented by the cluster head considering the resource capacity and nearness to the cluster head. The nominated helper-CH takes the responsibility of route discovery and transfers the packets to the base station. All of the member nodes sleep when they are not performing the sensing operation, but the helper cluster heads never sleep. Single-hop or multi-hop transmissions are used to transfer data from a node to the base station through the cluster head. When the distance between the cluster head to reach the super-cluster head is less than the threshold distance, d, then the data packets are transferred by single-hop communication. Otherwise, multi-hop communication is applied. The Floyd-Warshall algorithm is used to find the shortest distance to reach the super-cluster head by a cluster head as opposed to computing an optimal path. The algorithm shown in Fig. 4 considers the edge weight between the nodes and computes the shortest path based on minimum cost. It uses intermediate nodes with less cost to transfer data rather than costing more to transfer data directly.
Figure 4: Floyd-Warshall’s algorithm
5 Simulation Results and Discussion
The DE- and FFOA-combined LEACH protocol was tested in a simulation using NS2 to verify its performance. Sensor nodes of 100 count were randomly deployed over a region of 100 m × 100 m. The simulation parameters are shown in Tab. 1 Simulation Parameters
Table 1: Simulation parameters
Let the initial energy, IR, of the sensor nodes be 0.5J, and let a few nodes with 1J be introduced to portray the uneven energy distribution in the network. Let the geometric center be at the location (50, 50) and the transmission and reception energy be 50nJ/bit. The maximum number of rounds considered is 2000.
The number of nodes alive in each round is shown in Fig. 5. The alive node count is considered on the y-axis and the iterations/rounds are considered on the x-axis. It is observed that the first node dies only after 900 rounds in the DE-LEACH-FFOA and is larger when compared with DE-LEACH and LEACH protocols.
Figure 5: Alive nodes after each round
The residual energy of the nodes in the proposed protocol is comparatively larger than those described in previous work at each round of iteration as shown in Fig. 6. This figure illustrates the comparison of energy consumption which is varied on the y-axis and the number of nodes which is varied on x-axis. The proposed protocol spends very little energy on data packet transmission compared with previous schemes.
Figure 6: Residual energy vs. Rounds
Delivery ratio is the number of data packets sent to the base station per unit time. The packet delivery ratio of the proposed method is analyzed as shown in Fig. 7. The protocol achieves high packet delivery ratio compared with existing protocols because of the reliable multi-hop routing.
Figure 7: Mobility of nodes vs. Data packet delivery ratio
The comparison of network lifetime for LEACH-DE-FFOA compared with LEACH and DE-LEACH was studied, and the findings are shown in Fig. 8. Network lifetime is varied on the y-axis, and the number of nodes is varied on the x-axis. The proposed protocol achieved an elevated network lifetime compared with existing methods because of the energy model of the system. The LEACH protocol is therefore optimized by DE and FFOA techniques based on the above simulations. The delivery of packets is therefore improved through even-handed employment of energy.
Figure 8: Network lifetime vs. No. of nodes
Many approaches improve the lifetime of WSNs. However, the problem of uneven overhead imparted upon the sensor nodes still prevails. The DE-based FFOA hybrid optimization technique is a metaheuristic approach that prolongs the lifespan of WSNs. The uneven distribution of load on a sensor node is focused on and a scheme to distribute the load on multiple sensor nodes at each round is performed. The issue of nodes in overlapping cluster heads and the energy problem that occurs due to uneven clustering has been addressed. Multi-hop routing and a re-election strategy for cluster heads reduces the usage of energy and provides an optimal solution. Simulation results prove that the approach outperforms previousmethods and improves the overall network performance. Further, the work can be extended by applying several other nature-inspired optimization algorithms. The algorithm canbe made secure by usingother adaptive algorithms that result in secured commutation of packets.
Acknowledgement: We thank LetPub (www.letpub.com) for its linguistic assistance during the preparation of this manuscript.
Funding Statement: The authors received no specific funding for this study.
Conflicts of Interest: The authors declare that they have no conflicts of interest to report regarding the present study.
1. Y. Zhang and L. Cheng, “Self-nominating: A robust affordable routing for wireless sensor networks,” in proc. IEEE 58th Vehicular Technology Conf. VTC 2003-Fall, Orlando, FL, vol.5, pp. 2829–2833, 2003. [Google Scholar]
2. M. Panda and P. K. Sethy, “Network structure based protocols for wireless sensor networks,” in proc. Int. Conf. on Advances in Engineering & Technology Research (ICAETR - 2014Unnao, pp. 1–10, 2014. [Google Scholar]
3. D. Bhattacharyya, T. H. Kimand and S. Pal, “A comparative study of wireless sensor networks and their routing protocols,” Sensors, vol. 10, no. 12, pp. 10506–10523, 2010. [Google Scholar]
4. T. Yang, Y. Guo, J. Dong and M. Xia, “Wireless routing clustering protocol based on improved LEACH algorithm,” in proc. IEEE Int. Conf. on RFID Technology & Application (RFID-TAMacau, pp. 1–6, 2018. [Google Scholar]
5. H. Wang, P. Tu, P. Wang and J. Yang, “A redundant and energy-efficient clusterhead selection protocol for wireless sensor network,” in proc. Second Int. Conf. on Communication Software and Networks, Singapore, pp. 554–558, 2010. [Google Scholar]
6. N. D. Tan, L. Han, N. D. Viet and M. Jo, “An improved LEACH routing protocol for energy-efficiency of wireless sensor networks,” Smart Computing Review, vol. 2, no. 5, pp. 360–368, 2012. [Google Scholar]
7. A. Amuthan and A. Arulmurugan, “Semi-markov inspired hybrid trust prediction scheme for selection in WSNs,” Journal of King Saud University - Computer and Information Sciences, pp. 1– 11, 2018.https://doi.org/10.1016/j.jksuci.2018.07.006. [Google Scholar]
8. L. Wang, Y. Shi and S. Liu, “An improved fruit fly optimization algorithm and its application to joint replenishment problems,” Expert Systems with Applications, vol. 42, no. 9, pp. 4310–4323, 2015. [Google Scholar]
9. M. Elhoseny, X. Yuan, X. Yu, C. Mao, H. K. El-Minir et al., “Balancing energy consumption in heterogeneous wireless sensor networks using genetic algorithm,” IEEE Communications Letters, vol. 19, no. 12, pp. 2194–2197, 2015. [Google Scholar]
10. L. Dehni, F. Krief and Y. Bennani, “Power control and clustering in wireless sensor networks,” in proc. IFIP Annual Mediterranean Ad Hoc Networking Workshop, Challenges in Ad Hoc Networking, France, vol.197, pp. 31–40, 2006. [Google Scholar]
11. S. M. M. H. Daneshvar, P. A. A. Mohajer and S. M. Mazinani, “Energy-efficient routing in WSN: A centralized cluster-based approach via grey wolf optimizer,” IEEE Access, vol. 7, pp. 170019–170031, 2019. [Google Scholar]
12. V. Gangal, G. Hacioglu and E. Sesl̇i, “Energy efficient multihop routing in wireless sensor networks based on ant colony algorithm,” in proc. 23nd Signal Processing and Communications Applications Conference (SIUMalatya, pp. 1877–1880, 2015. [Google Scholar]
13. M. Pavani and P. T. Rao, “Adaptive PSO with optimised firefly algorithms for secure cluster-based routing in wireless sensor networks,” IET Wireless Sensor Systems, vol. 9, no. 5, pp. 274–283, 2019. [Google Scholar]
14. H. Iscan and M. Gunduza, “An application of fruit fly optimization algorithm for traveling salesman problem,” Procedia Computer Science, vol. 111, no. 16, pp. 58–63, 2017. [Google Scholar]
15. T. Siron Anita Susan and B. Nithya, “Fruit fly optimization-based reliable routing algorithm for wireless sensor networks,” in Proc. Int. Conf. on Advanced Communication and Networking, Applied Soft Computing and Communication Networks, Trivandrum, India, vol. 125,2020. [Google Scholar]
16. M. Kaddi, Z. Khalili and M. Bouchra, “A differential evolution based clustering and routing protocol for WSN,” in proc. 2nd Int. Conf. on Mathematics and Information Technology (ICMITAdrar, Algeria, pp. 190–195, 2020. [Google Scholar]
17. B. V. DevendraRao, D. Vasumathi and S. V. Nandury, “Exploiting common nodes in overlapped clusters for path optimization in wireless sensor networks,” in proc. Second Int. Conf. on Computer and Communication Technologies, Advances in Intelligent Systems and Computing, vol. 381, pp. 209–217, 2016. [Google Scholar]
18. L. Jun, Q. Hua and L. Yan, “A modified LEACH algorithm in wireless sensor network based on NS2,” in proc. Int. Conf. on Computer Science and Information Processing (CSIPXian, Shaanxi, pp. 604–606, 2012. [Google Scholar]
 | This work is licensed under a Creative Commons Attribution 4.0 International License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. |