Energy efficient clustering and routing algorithms for wireless sensor networks: Particle swarm optimization approach

https://doi.org/10.1016/j.engappai.2014.04.009Get rights and content

Highlights

  • Two algorithms are presented, i.e., PSO based routing and clustering for wireless sensor networks.

  • The former builds a trade-off between transmission distance and hop-count.

  • The clustering algorithm balances energy consumption of the CHs.

  • Experimental results demonstrate the superiority over existing algorithms.

Abstract

Energy efficient clustering and routing are two well known optimization problems which have been studied widely to extend lifetime of wireless sensor networks (WSNs). This paper presents Linear/Nonlinear Programming (LP/NLP) formulations of these problems followed by two proposed algorithms for the same based on particle swarm optimization (PSO). The routing algorithm is developed with an efficient particle encoding scheme and multi-objective fitness function. The clustering algorithm is presented by considering energy conservation of the nodes through load balancing. The proposed algorithms are experimented extensively and the results are compared with the existing algorithms to demonstrate their superiority in terms of network life, energy consumption, dead sensor nodes and delivery of total data packets to the base station.

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., Edλ, 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)

  • A.M. Zungeru

    Classical and swarm intelligence based routing protocols for wireless sensor networks: a survey and comparison

    J. Netw. Comput. Appl.

    (2012)
  • Abdul, L.N.M., et al., 2007. Energy aware clustering for wireless sensor networks using particle swarm optimization....
  • Ahmad, A., et al., 2012. MAC layer overview for wireless sensor networks. In: CNCS 2012, pp....
  • H. Al-Refai

    Efficient routing LEACH (ER-LEACH) enhanced on LEACH protocol in wireless sensor networks

    Int. J. Acad. Res. (Part I)

    (2011)
  • B. Ataul

    Clustering strategies for improving the lifetime of two-tiered sensor networks

    Comput. Commun.

    (2008)
  • B. Ataul

    A genetic algorithm based approach for energy efficient routing in two-tiered sensor networks

    Ad Hoc Netw.

    (2009)
  • Y.M. Aykut

    QoS-aware MAC protocols for wireless sensor networks: a survey

    Comput. Netw.

    (2011)
  • B.H. Calhoun

    Design considerations for ultra-low energy wireless microsensor nodes

    IEEE Trans. Comput.

    (2005)
  • M. Cardai et al.

    Improving wireless sensor network lifetime through power aware organization

    Wirel. Netw.

    (2005)
  • Chakraborty, U.K., et al., 2012. Energy-efficient routing in hierarchical wireless sensor networks using...
  • S.S. Chiang

    A minimum hop routing protocol for home security systems using wireless sensor networks

    IEEE Trans. Consum. Electron.

    (2007)
  • Cited by (456)

    • Integration of artificial intelligence (AI) with sensor networks: Trends, challenges, and future directions

      2024, Journal of King Saud University - Computer and Information Sciences
    View all citing articles on Scopus
    View full text