Rank-Based Gravitational Search Algorithm: a Novel Nature-Inspired Optimization Algorithm for Wireless Sensor Networks Clustering

gravitational search algorithm

Table of Contents


Recently, wireless sensor networks (WSNs) have had many real-world applications; they have thus become one of the most interesting areas of research. The network lifetime is a major challenge researched on this topic with clustering protocols being the most popular method used to deal with this problem. The determination of the cluster heads is the main issue in this method. Cognitively inspired swarm intelligence algorithms have attracted wide attention in the research area of clustering since it can give machines the ability to self-learn and achieve better performance. This paper presents a novel nature-inspired optimization algorithm based on the gravitational search algorithm (GSA) and uses this algorithm to determine the best cluster heads. First, the authors propose a rank-based definition of mass calculation in GSA. They also introduce a fuzzy logic controller (FLC) to compute the parameter of this method automatically. Accordingly, this algorithm is user-independent. Then, the proposed algorithm is used in an energy-efficient clustering protocol for WSNs. The proposed search algorithm is evaluated in terms of some standard test functions. The results suggest that this method has a better performance than other state-of-the-art optimization algorithms. In addition, simulation results indicate that the proposed clustering method outperforms other popular clustering methods for WSNs. The proposed method is a novel way to control the exploration and exploitation abilities of the algorithm with simplicity in implementation; therefore, it has a good performance in some real-world applications such as energy-efficient clustering in WSNs.


Wireless sensor network (WSN), Energy-efficient protocol, Clustering method, Gravitational search algorithm
(GSA), Rank-based selection, Fuzzy logic controller (FLC).


Biologically inspired algorithms (BIAs) have attracted considerable research interest from science and engineering communities around the world. These algorithms are motivated by challenges in applications where classical optimization algorithms are not effective. Evolutionary algorithms and swarm intelligence are the two main branches of BIAs [1]. In recent years, the investigation of the behavior of swarm animals and natural phenomena has introduced many metaheuristic algorithms. These algorithms which are inspired by social cognitive science are used to solve optimization problems in real-life applications [2]. However, these algorithms do not have their origin primarily in mathematics; they are inspired by biological phenomena. In BIAs and swarm intelligence algorithms, agents share their information with other agents in the population in order to improve the performance of the whole swarm. Although each agent in these approaches has low-level cognition and is not individually smart enough to solve sophisticated problems, there are some valuable properties such as thinking, learning, recognition [3], reasoning, and high-cognition in the swarm intelligence algorithms which can be used to solve many complicated and industrial problems [4, 5]. There have been numerous advances in swarm intelligence based on cognitively inspired algorithms [6, 7]. Cognitively inspired swarm intelligence algorithms (SIAs) have attracted wide attention in many scientific and engineering fields [8–11]. In SIAs, particles usually either make decisions according to their own experience or according to the elite’s suggestions. Moreover, the stochastic mechanism is introduced to all SIAs to promote its optimization capability [12].

Gravitational search algorithm (GSA) is one of the new nature-inspired optimization algorithms which has been proposed by Rashedi et al. [13, 14]. This method is inspired by the Newtonian law of motion, gravity, and mass interactions. In this method, agents or masses can search for feasible areas in order to find better solutions. They are placed in a feasible area where their weight is determined by their position in this area and their fitness function value. Thus, the objects which are placed in a better position, in the feasible area, are heavier
and attract lighter objects with worse fitness values. GSA is used in applications such as clustering, robotics, filter modeling, and artificial intelligence [15]. Up to date, numerous efforts have been made to enhance the performance of the GSA. Clustered-GSA (CGSA), inspired by calculating the central mass of a structure in nature, is used to reduce the computation of GSA. Further, this method reduces the number of fitness function calculations [16]. Also, some researchers have added a new operator to improve the performance of GSA. Doraghinejad et al. introduced an operator called “Black-hole” for GSA which is inspired by characteristics of black-holes as an astronomical phenomenon [17].

Disruption is another operator inspired by astrophysics. This operator can balance and control the exploitation and exploration properties of GSA [18]. Some of the different variants of GSA which have been developed to enhance and improve the original version of the algorithm have been reviewed here [15]. In this paper, we use the rank-based fitness assignment method to overcome the scaling problems of the proportional fitness assignment. Rank-based methods tend to prevent premature convergence by tempting selection pressure for large fitness differentials that occur in early generations. Conversely, by amplifying small fitness differences in later generations, selection pressure is enhanced compared to other fitness assignment strategies.

BIAs and meta-heuristic methods have the problem of parameter adaptation. Many researchers use a fuzzy logic controller (FLC) to solve this problem and obtain better results than original algorithms [19]. In this regard, Ref. [20]usedthe fuzzy logic to combine the result of real genetic algorithm (RGA) and particle swarm optimization (PSO) which are biologically inspired optimization algorithms, in an optimal way to achieve the best performance. Ref. [21] investigated a new fuzzy PSO method with-cross mutated operation. This method improved the performance of the algorithm by controlling the parameters of the method and the new operator. This approach was used to compute a decision-based filter for a cDNA microarray image restoration. In this paper, a fuzzy logic controller was used to control the selection pressure of the algorithm according to the computational process of GSA. In other words, the exploitation and exploration abilities of the algorithm can be controlled automatically.

In our previous works [18, 22], we attempted to improve the performance of the GSA by introducing new versions of GSA. The authors in [18] proposed a modified version of GSA, with a new operator and mutation, which used the fuzzy logic controller to control the parameters of this operator. In GSA, the value of masses was calculated with respect to the fitness of agents. To enhance the performance
of GSA, the definition and calculation of masses are necessary. Accordingly, [22] proposed new methods for defining and calculating the value of masses. The proposed mass scaling and Boltzmann selection functions to calculate the value of the masses. Thereby, the exploration and exploitation properties of the algorithm could be controlled and its performance improved. In these methods, the value of masses for each agent was heavily dependent on the value of the objective function and fitness function.
In past years, researchers have focused on wireless sensor networks (WSNs) in both theoretical and industrial fields, as they are effective means in monitoring and tracking applications. For example, WSNs are used for health monitoring, military applications, agriculture, forecasting, and decision systems [6, 23]. WSNs contain many cheap independent nodes known as sensor nodes. Each sensor node has units including sensing, processing, communication, and energy units. These sensors are located in the target area randomly or manually. They can sense data such as pressure, humidity, sounds, and chemical concentration from the target area. Sensor nodes collect these data and communicate with other nodes to ultimately relay information to the base station. The power unit of the sensor nodes is limited. Further, in most applications, sensor nodes are not accessible once they are located in the target space. Therefore, their power unit and the battery cannot be changed, and the sensor node will die once its battery runs out. Thus, energy consumption is an issue for WSN investigations in order to enhance the lifetime of the entire network.

Clustering methods have been used in many real-world applications and problems. Hence, it is a fundamental topic in artificial intelligence. In [24], the authors proposed a new clustering protocol called the spectral embedded clustering framework and used linearity regularization to deal with out-of-sample data. Ref. [10] used a social recognition-based multi-objective GSA, for the clustering of remote sensing imagery. One of the most common techniques for energy-efficient consumption in WSNs is clustering. A clustering method gathers the sensor nodes into clusters, where each cluster has its own cluster head. The nodes sense the data from the target area and transmit them to their corresponding cluster head. Thus, the raw information of all sensors in each cluster is collected into the cluster head.

Finally, the cluster head compresses and transmits this information to the base station. Clustering methods can improve energy usage in the WSNs by reducing the number of nodes with long-distance communications and preventing them from sending irrelevant data to the base station. Low energy adaptive clustering hierarchy (LEACH) is one of the most popular clustering methods for WSNs, first proposed by Heinzelman in [25]. LEACH cannot provide an ideal and desired number of cluster heads in WSNs architecture. A centralized energy-efficient clustering method, LEACH-C, was introduced by Muruganathan et al. [26]. In this protocol, the base station forms the clusters at the beginning of each round using a centralized algorithm. The results reveal that the LEACH-C protocol can outperform the LEACH algorithm and has a better performance in terms of the network lifetime and total data transmission. Ref. [27] studied some popular clustering methods in WSNs and examined their performance in terms of power consumption. BIAs and swarm intelligence algorithms have been used in some clustering protocols for WSNs [28]. For example, in [29], the authors defined a new cost function which could minimize intra-cluster node distances and improve the battery usage of the network simultaneously. Then, the PSO algorithm was used to find a good solution for this cost function. In [30], a new version of GSA, quadrivalent quantum-inspired gravitational search algorithm (QQIGSA), inspired by quantum mechanics, was introduced, where this optimization algorithm was used in WSNs in order to improve the energy consumption in the network. In Ref. [6], a new, cognitively inspired artificial bee colony clustering algorithm was introduced.
This algorithm which has a clustering evaluation model was used in clustering for energy management in cognitive WSNs, special models of WSNs. The objective function defined in this paper tries to improve the energy consumption in WSNs by determining compact clusters
with high remaining energy cluster heads. In the proposed method, we use the modified version of GSA to find a good solution for this optimization problem.

In this paper, a new method is used for mass calculation in GSA where a rank-based approach considers the rank of individuals instead of their fitness values is employed to determine the value of masses. The exploration and exploitation of the algorithm can be controlled by
the parameter of the algorithm. In the proposed method, a fuzzy controller is defined to determine the value of this parameter; therefore, the parameter is determined automatically and independent of the user. Further, this controller can balance the exploitation and exploration abilities of the algorithm to achieve the best performance for solving optimization problems. The performance of the proposed method is compared with state-of-the-art heuristic algorithms. The experimental results and statistical analysis revealed that the proposed method outperforms other approaches in many test functions. Reviews of the literature show that the proposed method is the first application of a rank-based method in the mass calculation in GSA. Also, the use of a controller to determine the value of this parameter and to control the abilities of the algorithm has not been previously done. This novel version of GSA was then used in WSN protocols to optimize battery usage and maximize the network lifetime. The simulation results suggest that the proposed clustering method has a better performance than other popular clustering algorithms. This is particularly important as this application of GSA in energy-efficient clustering problems is the first of its kind.

The paper is organized as follows: the “Basic Concepts” section introduces the basic concepts required to present the proposed method; “Rank-Based GSA” section displays the improved version of GSA; “Adapting the Proposed Method to Energy Efficient Clustering for WSN” section details the adaptation and application of the proposed method for clustering in WSN; “Simulations and Experimental Results” section presents the evaluation of experimental results, the comparison of the results to other algorithms, and statistical analysis of the results, and finally, the “Conclusion” section summarizes and concludes the paper.


In this paper, a rank-based fitness assignment method was used to calculate the value of masses in the GSA. This method was applied to overcome the scaling problems of the proportional fitness assignment. In the proposed algorithm, values of agent masses were dependent only on relative fitness rather than on the absolute objective functions. Controlling values of parameters was an effective solution to improve the optimization performance of a meta-heuristic algorithm by automatically setting the parameters to appropriate values during the computational processes of the evolutionary search. Further, in this paper, an FLC was proposed to calculate and compute the parameter of rank-based method automatically and independently of the user. The exploitation and exploration abilities of this algorithm could be controlled by this FLC. The performance of the proposed optimization method was assessed by simulation and compared against other popular and state-of-the-art BIAs and optimization methods. The simulation results and statistical assessment revealed the proposed method to outperform the other methods. The difference between the performance of the proposed method and that of other approaches was a significant one. Therefore, it can be said that the proposed algorithm is an effective method to improve results while also having simplicity in implementation.
Then, the new version of GSA was applied to energy-efficient clustering protocols for WSNs in order to optimize the objective function. This objective function defined compact clusters with more remaining energy nodes as their cluster heads. The observed experiments and comparisons suggested that, by using RB-GSA, the proposed approach outperformed other popular energy-efficient clustering methods for WSNs.

About KSRA

The Kavian Scientific Research Association (KSRA) is a non-profit research organization to provide research / educational services in December 2013. The members of the community had formed a virtual group on the Viber social network. The core of the Kavian Scientific Association was formed with these members as founders. These individuals, led by Professor Siavosh Kaviani, decided to launch a scientific / research association with an emphasis on education.

KSRA research association, as a non-profit research firm, is committed to providing research services in the field of knowledge. The main beneficiaries of this association are public or private knowledge-based companies, students, researchers, researchers, professors, universities, and industrial and semi-industrial centers around the world.

Our main services Based on Education for all Spectrum people in the world. We want to make an integration between researches and educations. We believe education is the main right of Human beings. So our services should be concentrated on inclusive education.

The KSRA team partners with local under-served communities around the world to improve the access to and quality of knowledge based on education, amplify and augment learning programs where they exist, and create new opportunities for e-learning where traditional education systems are lacking or non-existent.

FULL Paper PDF file:

Rank-Based Gravitational Search Algorithm: a Novel Nature-Inspired Optimization Algorithm for Wireless Sensor Networks Clustering



Sepehr Ebrahimi Mood (s.ebrahimi.mood@gmail.com)
Mohammad Masoud Javidi (javidi@uk.ac.ir)




Rank-Based Gravitational Search Algorithm: a Novel Nature-Inspired Optimization Algorithm for Wireless Sensor Networks Clustering

Publish in

Cognitive Computation



PDF reference and original file: Click here

+ posts