Particle swarm optimization for maximizing lifetime of wireless sensor networks

https://doi.org/10.1016/j.compeleceng.2016.03.002Get rights and content

Abstract

Particle swarm optimization (PSO) is a popular bio-inspired algorithm which is applied to solve various optimization problems in many areas including machine intelligence, data mining, robotics and computer networks. In this paper, we propose a PSO-based scheme to solve hot spot problem caused by multi-hop communication in a cluster-based wireless sensor network. The scheme consists of routing and clustering algorithms which are shown to be energy efficient. In the routing phase, traffic load over the cluster heads (CHs) is evenly distributed, whereas in the clustering phase, we take care of all the CHs whose energy is exhausted fast by assigning lesser number of sensor nodes. In addition to this, we also develop a distributed scheme to prevent the CHs from their quick death which is resulted from complete energy depletion. We perform extensive simulation on the proposed algorithms and compare the results with some existing algorithms to demonstrate its strength.

Introduction

Energy conservation of sensor nodes is the main concern which has been studied extensively in wireless sensor networks (WSNs) [1]. Clustering is one of the most efficient techniques to conserve energy of the sensor nodes. In a cluster-based WSN, some leader nodes called cluster heads (CHs) are responsible for forwarding aggregated data to a remote sink or base station (BS) after collecting data from their member sensor nodes in one-hop communication. However, forwarding aggregated data through multi-hop communication suffers from hot spot problem [2] in which the CHs nearby the sink deplete their energy quickly and die soon as they bear maximum data forwarding load. Many algorithms have been developed to solve the hot spot problem [2], [3], [4], [5], [6]. However, they do not perform well for large and dense networks. Moreover, these algorithms are not fault tolerant. One possible solution to this problem is to distribute the forwarded data evenly over the CHs so that their traffic load can be balanced. Another solution is unequal clustering in which the clusters are formed with small size nearby the BS. This method reduces the burden of the CHs near the BS as the number of their member sensor nodes are relatively small and therefore it conserves their energy. In this paper, we propose a particle swarm optimization (PSO)-based scheme for clustering and routing in large scale WSNs. The scheme uses unequal clustering and even distribution of data forwarding load of the CHs nearby the BS to address the hot spot problem.

This is worth to note that energy efficient clustering and routing can be formulated as optimization problems. However, the computational complexity of finding optimal route and optimal clusters is very high by a brute force approach for a large scale WSN [7], [8]. Therefore, PSO can be very effective to achieve an efficient and faster solution. Note that there are many meta-heuristic approaches to solve the optimization problems such as genetic algorithm (GA), ant colony optimization (ACO), differential evolution (DE) etc. However, the PSO has the following advantages over these algorithms [9]: 1) It is very easy to implement in hardware or software; 2) it produces high quality of solutions due to its availability to escape from local optima and 3) it converges faster than other meta-heuristic approaches.

We first propose PSO-based routing and unequal clustering algorithms. Next, we propose a distributed scheme for fault tolerance of CHs. In the routing phase, we increase the average lifetime of the CHs by evenly distributing the data traffic load over the CHs. We derive an efficient fitness function for the routing solution and present a linear programming (LP) formulation for the same. In the clustering phase, we calculate unequal clustering radius of each CH based on its lifetime computed from the routing phase. We further increase the average lifetime of the CHs by assigning less number of sensor nodes to them. The proposed algorithms are simulated extensively and the results are compared with existing PSO- and GA-based approaches [8,[10], [11], [12]] in terms of network lifetime, energy consumption, number of data packets received by the BS and number of inactive sensor nodes.

Note that Kuila et al. [8] have also proposed routing and clustering algorithms using PSO. However, our proposed scheme has the following differences with them. 1) While our scheme is developed to address hot spot problem, the scheme proposed in [8] does not deal with it. 2) The fitness function in [8] is based on maximum distance between two nodes in routing path and maximum hop count of gateways for routing and average cluster distance for clustering; on the other hand, the fitness function of our proposed scheme is based on approximate life time of the gateways for routing and energy consumption owing intra-cluster and inter-cluster activities for unequal clustering. Further, routing path selected by the algorithm in [8] remains fixed for the entire network operation, the routing path selected by our proposed scheme changes in every network setup and thus enhance network lifetime. 3) Our proposed scheme also considers fault tolerant issue; no such scheme is considered in [8]. Through simulation, we show that our proposed scheme outperforms the scheme of [8].

We summarize our contributions as follows:

  • PSO-based routing and unequal clustering algorithms for solving hot spot problem to maximize the network lifetime.

  • Derivation of efficient fitness functions for routing and clustering algorithms.

  • LP formulation for routing and clustering problems.

  • Distributed recovery of neighbour CHs and member sensor nodes for fault tolerance.

  • Simulations of the proposed algorithms to demonstrate its strength over existing algorithms.

The rest of the paper is organized as follows. The related works are presented in Section 2. The system model is described in Section 3 which includes network model and terminologies used. The proposed PSO-based scheme for routing and clustering is presented in Section 4 followed by the proposed fault tolerance scheme in Section 5. The performance evaluations are described in Section 6. We conclude our paper in Section 7.

Section snippets

Related works

WSNs have created enormous attention due to their wide applications in various areas including environmental monitoring, agriculture, health care, military, domestic and disaster management [13]. Many clustering and routing algorithms have been developed for WSNs. However, here we discuss some of these algorithms which are relevant to our proposed work.

Low-energy adaptive clustering hierarchy (LEACH) [14] is a well-known cluster-based routing protocol in WSNs. In LEACH, each node becomes a CH

Models

We consider a WSN deployed randomly in a rectangular area with a set of normal sensor nodes and high energy gateways. The gateways act as CHs in the network. Normal sensor nodes sense local data and forward to their respective CHs, whereas the gateway receive sensed data from their member nodes, aggregate and forward them to the BS directly or through other gateways. Nodes can be deployed manually or randomly in the target area. However, all the sensor nodes and gateways become stationary after

Proposed algorithms

The operation of the proposed scheme is as follows. At the beginning, each sensor node and gateway undergoes bootstrapping process in which the BS assigns unique IDs to all of them. After that, all the sensor nodes and the gateways broadcast their IDs using CSMA/CA MAC layer protocol, so that each gateway can collect IDs of all sensor nodes and gateways located within the communication range dmax and Rmax respectively. Finally, each gateway forwards this local information to the BS for network

Prevention of gateway failure

As discussed earlier, gateways near the BS deplete their energy faster than other gateways which are far from the BS. A solution to this problem is to allow other gateways which have no the BS in their communication range to communicate directly. The basic mechanism is to minimize the transmission cost by removing the traffic load from a gateway gi whose remaining residual energy is below certain threshold limit and allow the gateway gj, such that next-hop (gj) = gi to communicate directly to the

Performance evaluation

We carried out extensive simulations to evaluate the performance of the proposed clustering and routing algorithms jointly. Here, at first we discuss the simulation setup and then we analyse various simulation results.

Conclusion

In this paper, we have presented energy efficient routing and clustering algorithms which are based on particle swarm optimization. We have also presented a prevention technique which further extends network lifetime by removing the traffic load of the gateways whose remaining energy is beyond a certain threshold value. We have performed extensive simulation. The results are compared with the existing algorithms, namely, PSOK, GARS, GLBC and GARA. We have shown that our proposed algorithms

Md Azharuddin received MCA and Ph.D. from Aligarh Muslim University and Indian School of Mines in 2011 and 2016 respectively. Currently he is Assistant Professor in the department of Computer Application, Integral University, India. His main research interests include wireless sensor networks, soft computing and cloud computing.

Cited by (69)

  • High-throughput and energy-efficient data gathering in heterogeneous multi-channel wireless sensor networks using genetic algorithm

    2023, Ad Hoc Networks
    Citation Excerpt :

    The common approach to achieving evenness of energy depletion of the sensors is to minimize the standard deviation of their residual energy. This metric is used in many algorithms such as [9,10,18–21]. However, the energy consumption rate of nodes depends on their distances from the BS.

  • FIS-RGSO: Dynamic Fuzzy Inference System Based Reverse Glowworm Swarm Optimization of energy and coverage in green mobile wireless sensor networks

    2020, Computer Communications
    Citation Excerpt :

    As battery energy may be depleted from any sensor device due to its several activities, so it is a burning issue on how to enhance the efficiency of the sensor network. Many researchers have been used several bio-inspired swarm intelligence algorithms [1–14] to enhance the throughput of the wireless sensor networks including enhancing coverage area, the lifespan of the network, routing techniques and deployment of the sensors. A Reverse Glowworm Swarm Optimization technique has been endorsed in this article for optimizing energy as well as area coverage by examining the similarities between a glowworm and the sensor nodes.

  • A Hybrid Trust Based WSN protocol to Enhance Network Performance using Fuzzy Enabled Machine Learning Technique

    2023, International Journal of Intelligent Systems and Applications in Engineering
View all citing articles on Scopus

Md Azharuddin received MCA and Ph.D. from Aligarh Muslim University and Indian School of Mines in 2011 and 2016 respectively. Currently he is Assistant Professor in the department of Computer Application, Integral University, India. His main research interests include wireless sensor networks, soft computing and cloud computing.

Prasanta K. Jana received M. Tech. in Computer Science from University of Calcutta and Ph.D. from Jadavpur University in 1988 and 2000 respectively. Currently he is a Professor in Computer Science and Engineering department, Indian School of Mines, India. He is an IEEE senior member. His current research interests include wireless sensor networks, cloud computing and big data.

Reviews processed and recommended for publication to the Editor-in-Chief by Associate Editor Dr. A. Isazadeh.

View full text