Energy-efficient clustering method for wireless sensor networks using modified gravitational search algorithm

Abstract

Past decades have witnessed the advancement of wireless sensor networks (WSNs) in both academic and industrial communities. Clustering is one of the most popular methods to increase the lifespan of WSNs. The optimal number of cluster heads and how to organize the clusters are the most important issues to be addressed in the clustering methods. In this paper, we proposed a novel user-independent and dynamical method to calculate the optimal number of clusters, organize the clusters, and determine the best cluster heads in each round. In this method, efficient energy consumption and link quality were considered to compute the optimal number of clusters. Then, the algorithm began to organize the compact clusters with high energy level cluster heads. We investigated a new fitness function in order to achieve these objectives. A new version of gravitational search algorithm (GSA) was used to solve this optimization problem. In this algorithm, the power distance sums scaling method was applied to calculate the mass values. Then, a fuzzy logic controller is employed to identify the parameter of this algorithm to control the exploitation and exploration abilities of the method during the computational process of the algorithm. Then, the novel version of GSA was applied to reach an appropriate solution for the fitness function, find the optimal number of clusters, and properly organize these clusters. To evaluate the effectiveness of the proposed method, several experiments were performed and the obtained results were compared with the results of other popular clustering methods. The simulation results revealed that the performance of the modified GSA was better than other state-of-the-art meta-heuristic optimization algorithms. Moreover, the proposed method for the clustering problem in WSNs outperformed other popular clustering methods and increased the lifetime of WSNs.

Appendix

Reconsider Lemma 1.

$$\mathop {\lim }\limits_{\alpha \to \infty } M_{best} = 1.$$

Proof

The scaled fitness values for all agents in each population can be derived as follows:

$$\mathop {\lim }\limits_{\alpha \to \infty } fit_{i}^{s} = \left( {\mathop \sum \limits_{{fit_{j} \in fit_{i}^{ + } }} \left( {fit_{i} - fit_{j} } \right)^{1/\infty } } \right)^{\infty } - \left( {\mathop \sum \limits_{{fit_{j} \in fit_{i}^{ - } }} \left( {fit_{j} - fit_{i} } \right)^{\infty } } \right)^{1/\infty } = \left\{ {\begin{array}{*{20}l} {\left( {N - 1} \right)^{\infty } } \hfill & {\quad fit_{i} = fit_{best} } \hfill \\ { - \left( {fit_{best} - fit_{worst} } \right) } \hfill & {\quad fit_{i} = fit_{worst} } \hfill \\ {N_{{i^{ - } }}^{\infty } - \left( {fit_{best} - fit_{i} } \right)} \hfill & {\quad otherwise } \hfill \\ \end{array} } \right.,$$

where $N_{{i^{ - } }}$ denotes the number of $fit_{j} \in fit_{i}^{ - }$. The value of $\mathop {\lim }\nolimits_{\alpha \to \infty } M_{best}$ can be computed as follows:

$$\mathop {\lim }\limits_{\alpha \to \infty } M_{best} = \mathop {\lim }\limits_{\alpha \to \infty } \frac{{fit_{best}^{s} - fit_{worst}^{s} }}{{\mathop \sum \nolimits_{j = 1}^{N} \left( {fit_{j}^{s} - fit_{worst}^{s} } \right)}} = \frac{{\left( {N - 1} \right)^{\infty } + (fit_{best} - fit_{worst} )}}{{\left( {N - 1} \right)^{\infty } + \left( {fit_{best} - fit_{worst} } \right) + \mathop \sum \nolimits_{i \ne best} (fit_{i}^{s} + (fit_{best} - fit_{worst} ))}} = \frac{1}{{1 + \mathop \sum \nolimits_{i \ne best} \frac{{N_{{i^{ - } }}^{\infty } - (fit_{best} - fit_{i} )}}{{\left( {N - 1} \right)^{\infty } + \left( {fit_{best} - fit_{worst} } \right)}} + \frac{{(N - 1)(fit_{best} - fit_{worst} )}}{{\left( {N - 1} \right)^{\infty } + \left( {fit_{best} - fit_{worst} } \right)}}}}.$$

We know that $\frac{{(N - 1)(fit_{best} - fit_{worst} )}}{{\left( {N - 1} \right)^{\infty } + \left( {fit_{best} - fit_{worst} } \right)}} = 0$. Moreover $1> \frac{{N_{{i^{ - } }} }}{N - 1} \ge 0$. Thus $\left( {\frac{{N_{{i^{ - } }} }}{N - 1}} \right)^{\infty } = \frac{{N_{{i^{ - } }}^{\infty } }}{{\left( {N - 1} \right)^{\infty } }} = 0$.

Moreover $\frac{{N_{{i^{ - } }}^{\infty } }}{{\left( {N - 1} \right)^{\infty } }} \ge \frac{{N_{{i^{ - } }}^{\infty } - \left( {fit_{best} - fit_{i} } \right)}}{{\left( {N - 1} \right)^{\infty } + \left( {fit_{best} - fit_{worst} } \right)}} \ge 0.$ So, $\frac{{N_{{i^{ - } }}^{\infty } - (fit_{best} - fit_{i} )}}{{\left( {N - 1} \right)^{\infty } + \left( {fit_{best} - fit_{worst} } \right)}} = 0$.

Thus, $\mathop {\lim }\nolimits_{\alpha \to \infty } M_{best} = 1$.

On the other hand, we know that $\mathop \sum \nolimits_{i = 1}^{N} M_{i} \left( t \right) = 1.$ Thus, the value of other masses is equal to 0.

Reconsider Lemma 2.

$$\mathop {\lim }\limits_{\alpha \to \infty } M_{i} = \frac{1}{N} , i = 1, \ldots ,N.$$

Proof

The scaled fitness values for all agents in each population can be derived as follows:

$$\mathop {\lim }\limits_{\alpha \to 0} fit_{i}^{s} = \left( {\mathop \sum \limits_{{fit_{j} \in fit_{i}^{ + } }} \left( {fit_{i} - fit_{j} } \right)^{\infty } } \right)^{1/\infty } - \left( {\mathop \sum \limits_{{fit_{j} \in fit_{i}^{ - } }} \left( {fit_{j} - fit_{i} } \right)^{1/\infty } } \right)^{\infty } = \left\{ {\begin{array}{*{20}l} {(fit_{best} - fit_{worst} )} \hfill & {\quad fit_{i} = fit_{best} } \hfill \\ {\left( {N - 1} \right)^{\infty } } \hfill & {\quad fit_{i} = fit_{worst} } \hfill \\ {\left( {fit_{i} - fit_{worst} } \right) - N_{{i^{ + } }}^{\infty } } \hfill & {\quad otherwise} \hfill \\ \end{array} } \right.,$$

where $N_{{i^{ + } }}$ denotes the number of $fit_{j} \in fit_{i}^{ + }$. This lemma can be proved similarly as above for Lemma 1.