Energy efficient clustering and routing algorithms for wireless sensor networks: Particle swarm optimization approach
Introduction
With the proliferation of soft computing techniques, nature-inspired algorithms have drawn enormous attention among researchers. Such algorithms have been studied to solve many optimization problems. For examples, genetic algorithm (GA) has been applied to enhance the efficiency of construction automation system (Wi et al., 2012). Similarly, particle swarm optimization (PSO) has been applied to solve various optimization problem in manufacturing (Issam et al., 2013, Thitipong and Nitin, 2011). Clustering and routing are two well known optimization problems which are well researched for developing many nature-inspired algorithms (Saleem et al., 2011, Kulkarni et al., 2011) in the field of wireless sensor networks (WSNs). PSO (Kennedy and Eberhart, 1995) is one such metaheuristic technique that has gained immense popularity in the recent years. In this paper, the authors propose two PSO-based algorithms for clustering and routing in wireless sensor networks.
A WSN consists of a large number of tiny and low power sensor nodes, which are randomly or manually deployed across an unattended target area. WSNs have potential applications in environment monitoring, disaster warning systems, health care, defense reconnaissance, and surveillance systems (Akyildiz et al., 2002). However, the main constraint of the WSNs is the limited power sources of the sensor nodes. Therefore, energy conservation of the sensor nodes is the most challenging issue for the long run operation of WSNs. Various issues have been studied for this purpose that include low-power radio communication hardware (Calhoun et al., 2005), energy-aware medium access control (MAC) layer protocols (Ahmad et al., 2012, Aykut et al., 2011), etc. However, energy efficient clustering and routing algorithms (Abbasi and Mohamad, 2007, Kemal and Mohamed, 2005) are the most promising areas that have been studied extensively in this regard.
In a two-tier WSN, sensor nodes are divided into several groups called clusters. Each cluster has a leader known as cluster head (CH). All the sensor nodes sense local data and send it to their corresponding CH. Then the CHs aggregate the local data and finally send it to the base station (BS) directly or via other CHs. The functionality of a cluster-based WSN is shown in Fig. 1. Clustering sensor nodes has the following advantages: (1) It enables data aggregation at cluster head to discard the redundant and uncorrelated data; thereby, it saves energy of the sensor nodes. (2) Routing can be more easily managed because only CHs need to maintain the local route set up of other CHs and thus require small routing information; this in turn improves the scalability of the network significantly. (3) It also conserves communication bandwidth as the sensor nodes communicate with their CHs only and thus avoid exchange of redundant messages among themselves.
However, CHs bear some extra work load contributed by their member sensor nodes as they receive the sensed data from their member sensor nodes, aggregate them and communicate it to the BS. Moreover, in many WSNs, the CHs are usually selected amongst the normal sensor nodes which can die quickly for this extra work load. In this context, many researchers (Gupta and Younis, 2003, Low et al., 2008, Ataul et al., 2009, Kuila and Jana, 2012a, Kuila et al., 2013) have proposed the use of some special nodes called gateways, which are provisioned with extra energy. These gateways act like cluster heads and are responsible for the same functionality of the CHs. Therefore, gateways and CHs are used interchangeably in the remainder of the paper.
Unfortunately, the gateways are also battery-operated and hence power constrained. Lifetime of the gateways is very crucial for the long run operation of the network. It is noteworthy that the transmission energy (E) which mainly dominates the overall energy consumption is proportional to the distance (d) between transmitter and receiver, i.e., E∝dλ, where λ is the path loss exponent and 2≤λ≤4 (Habib and Sajal, 2008). Therefore, minimization of transmission distance can reduce the energy consumption. However, some applications are very time-critical in nature. Hence, they should satisfy strict delay constraints so that the BS can receive the sensed data within a specified time bound. But the delay is proportional to the number of forwards on the dissemination path between a source and the BS. In order to minimize the delay, it is necessary to minimize the number of forwards, which can be achieved by maximizing the distance between consecutive forwards. Therefore, while designing routing algorithms we need to incorporate a trade-off between transmission distance and number of forwards as they pose two conflicting objectives. Furthermore, load balancing is another important issue for WSN clustering. Particularly, this is a pressing issue when the sensor nodes are not distributed uniformly. In this paper we address the following problems:
- (1)
Energy efficient routing with a trade-off between transmission distance and number of data forwards.
- (2)
Energy efficient load balanced clustering with energy conservation of the WSN.
Note that given n sensor nodes and m gateways, the number of possible clusters is mn. It should also be noted that if the gateways have an average of d valid one-hop neighbor relay nodes, then the number of valid routes is dm. Therefore the computational complexity of finding the optimal route and cluster for a large WSN seems to be very high by a brute force approach. Moreover, an optimization method requires reasonable amount of memory and computational resources and yet finding out good results is desirable. In order to obtain a faster and efficient solution of the clustering and routing problem with the above issues, a metaheuristic approach such as particle swarm optimization (PSO) is highly desirable. The main objective of this paper is to develop an efficient PSO-based clustering and routing algorithms for WSNs with the consideration of energy consumption of the sensor nodes for prolonging network life time.
In this paper, first Linear Programming (LP) and Non-linear Programming (NLP) formulations are presented for the routing and clustering problems respectively. Then two PSO-based algorithms for the same are proposed. The PSO-based routing builds a trade-off between energy consumption of the CHs and delay in forwarding the data packets. It finds out a route from all the gateways to the base station which has comparably lower overall distance with less number of data forwards. We present an efficient particle encoding scheme for complete routing solution and design the multi-objective fitness function using weighted sum approach.
The proposed PSO-based clustering takes care of energy consumption of the normal sensor nodes as well as the gateways. For clustering, particles are cleverly encoded to produce complete clustering solution. A different fitness function is also used by taking care of those gateways which inevitably consumes more energy by acting as relay node in packet forwarding. We perform extensive simulation on the proposed methods and evaluate them with several performance metrics including network life-time, number of active sensor nodes, energy consumption, total number of packets delivery and so on. The results are compared with GA-based clustering (Kuila et al., 2013), GLBCA (Low et al., 2008) and LDC (Ataul et al., 2008). Our main contributions can be summarized as follows:
- •
LP and NLP formulations for the routing and clustering problems respectively.
- •
PSO-based routing algorithm with a trade-off between transmission distance and number of data forwards with efficient particle encoding scheme for complete routing solution and derivation of efficient multi-objective fitness function.
- •
PSO-based clustering algorithm with efficient particle encoding scheme and fitness function.
- •
Simulation of the proposed algorithm to demonstrate superiority over some existing algorithms.
The rest of the paper is organized as follows. The related work is presented in Section 2. An overview of particle swarm optimization is given in Section 3. The system model and used terminologies are described in Section 4 which includes energy model and network model. The proposed algorithms and the experimental results are presented in 5 Proposed algorithms, 6 Experimental results respectively and we conclude in Section 7.
Section snippets
Related works
A number of clustering and routing algorithms have been developed for WSNs. We present the review of such works based on heuristic and metaheuristic approaches. However, we emphasize on the metaheuristic approach as our proposed algorithm is based on it.
Overview of particle swarm optimization
Particle swarm optimization (PSO) is inspired by natural life, like bird flocking, fish schooling and random search methods of evolutionary algorithm (Kennedy and Eberhart, 1995, Wei and Nor, 2014). It can be observed from the nature that animals, especially birds, fishes, etc. always travel in a group without colliding. This is because each member follows the group by adjusting its position and velocity using the group information. Thus it reduces individual׳s effort for searching of food,
Energy model
The radio model for energy used in this paper is same as discussed by Heinzelman et al. (2002). In this model, both the free space and multi-path fading channels are used depending on the distance between the transmitter and receiver. When the distance is less than a threshold value d0, then the free space (fs) model is used, otherwise, the multipath (mp) model is used. Let Eelec, εfs and εmp be the energy required by the electronics circuit and by the amplifier in free space and multipath
Proposed algorithms
Network setup is performed in three phases: bootstrapping; route setup; and clustering. During the bootstrapping process, all the sensor nodes and gateways are assigned unique IDs. Then the sensor nodes and the gateways broadcast their IDs using CSMA/CA MAC layer protocol. Therefore, the gateways can collect the IDs of the sensor nodes and the other gateways those are within their communication range and finally send the local network information to the base station. Now, using the received
Experimental results
We performed extensive experiments on the proposed algorithm using MATLAB R2012b and C programming language. The experiments were performed with diverse number of sensor nodes ranging from 200 to 700 and 60 to 90 gateways. Each sensor node was assumed to have initial energy of 2 J and each gateway has 10 J. In the simulation run, we used following parameter values same as in Heinzelman et al. (2002) as shown in Table 5.
We have tested our proposed algorithms extensively and depict the experimental
Conclusions
In this paper, first a Linear and a Non-linear Programming have been formulated for two important optimization problems for wireless sensor networks, i.e., energy efficient routing and clustering respectively. Then, two algorithms have been presented for the same based on particle swarm optimization. The routing algorithm has been developed by considering a trade-off between transmission distance and the number of hop-count. In the clustering phase, routing overhead of the CHs is considered for
References (42)
- et al.
A survey on clustering algorithms for wireless sensor networks
Comput. Commun.
(2007) Wireless sensor networks: a survey
Comput. Netw.
(2002)Wireless sensor networks: a survey on the state of the art and the 802.15.4 and ZigBee standards
Comput. Commun.
(2007)Multi-objective optimization using genetic algorithms: a tutorial
Reliab. Eng. Syst. Saf.
(2006)- et al.
A novel evolutionary approach for load balanced clustering problem for wireless sensor networks
Swarm Evol. Comput.
(2013) Efficient load-balanced clustering algorithms for wireless sensor networks
Comput. Commun.
(2008)- et al.
Simple heuristics-based selection of guides for multi-objective PSO with an application to electrical distribution system planning
Eng. Appl. Artif. Intell.
(2011) Swarm intelligence based routing protocol for wireless sensor networks: survey and future directions
Inf. Sci.
(2011)- et al.
Energy-aware cluster head selection using particle swarm optimization and analysis of packet retransmission in WSN
Procedia Technol.
(2012) - et al.
A systematic review on clustering and routing techniques based upon LEACH protocol for wireless sensor networks
J. Netw. Comput. Appl.
(2013)
Classical and swarm intelligence based routing protocols for wireless sensor networks: a survey and comparison
J. Netw. Comput. Appl.
Efficient routing LEACH (ER-LEACH) enhanced on LEACH protocol in wireless sensor networks
Int. J. Acad. Res. (Part I)
Clustering strategies for improving the lifetime of two-tiered sensor networks
Comput. Commun.
A genetic algorithm based approach for energy efficient routing in two-tiered sensor networks
Ad Hoc Netw.
QoS-aware MAC protocols for wireless sensor networks: a survey
Comput. Netw.
Design considerations for ultra-low energy wireless microsensor nodes
IEEE Trans. Comput.
Improving wireless sensor network lifetime through power aware organization
Wirel. Netw.
A minimum hop routing protocol for home security systems using wireless sensor networks
IEEE Trans. Consum. Electron.
Cited by (456)
Clustering at the Edge: Load balancing and energy efficiency for the IoT
2024, Ad Hoc NetworksQuantum-inspired particle swarm optimization for efficient IoT service placement in edge computing systems
2024, Expert Systems with ApplicationsIntegration of artificial intelligence (AI) with sensor networks: Trends, challenges, and future directions
2024, Journal of King Saud University - Computer and Information SciencesEfficient offloading in disaster-affected areas using unmanned aerial vehicle-assisted mobile edge computing: A gravitational search algorithm-based approach
2023, International Journal of Disaster Risk ReductionImproved wireless sensor network data collection using discrete differential evolution and ant colony optimization
2023, Journal of King Saud University - Computer and Information SciencesStudy on the wireless sensor networks routing for Low-Power FPGA hardware in field applications
2023, Computers and Electronics in Agriculture