Optimization of Clustering in Wireless Sensor Networks Using Genetic Algorithm

Introduction

The twenty first century has harbingered a new technology in form of the Wireless sensor networks (WSN). In the near past it has generated tremendous interest from both academia and industry across the world. A WSN typically a network of many low-cost, low-power, and multifunctional wireless sensor nodes, which are battery powered, have wireless communication and limited computation capabilities. These sensor nodes have been designed to communicate over short distances via a wireless medium in standalone or a collaborative manner to accomplish the desired network function. The applications range from military, to environment to industry. In other words, any inhospitable environment where physical placement of sensors may not be feasible, or a wired network cannot be setup, a WSN facilitates remarkable solutions. The basic philosophy behind WSN is that, while the capability of each sensor node is limited, the aggregate power of the entire network is sufficient for the required mission.

Wireless sensor networks consist of a large number of battery powered sensors having a finite battery life. The energy consumption depends upon either the communication range that the sensor is expected to transmit or receive, and also the active period for which the sensor is to communicate. Power consumption of each sensor has thus become a critical research area which has governed the development of hardware as well as the software in WSNs. Clustering of sensors is one of such methods which has emerged as one of the best approaches that efficiently help in increasing the overall network lifetime.

Clustering is a hierarchical process in which the sensors are grouped into clusters with help of a clustering algorithm. One of the sensor node in each cluster is identified to act as the cluster head and perform a majority of functions, which include maintaining a collision-free schedule, aggregating the information from other sensors in the cluster and finally transmitting the aggregated information to the base station. This consumes a lot of energy of the cluster-head sensor, and therefore in many approaches the role of the cluster-head is periodically rotated among the nodes within the cluster. The succeeding paragraph enumerates a few notable optimization techniques used in clustering protocols.

Classical approaches such as linear programming and non-linear programming are not efficient enough in solving optimization problems since they are based on certain pre-conditions. Heuristic approaches (typically nature-inspired) do not expose most of the drawbacks of classical and technical approaches. Ant colony optimization technique is a probabilistic method which replicates the natural tendency of the ant to find shortest route to food. The ants also transmit this information to other ants through chemicals secreted on the path. Such behaviors can be easily replicated in electronic environment through multicasting and broadcasting and therefore suited to entire network optimization problems. However, clustering is a local phenomenon and ant colony optimization is not suitable here. In 1995 Kennedy and Eberhart came up with a stochastic technique called particle swarm optimization (PSO). This technique is inspired by social interactions within a community of animals or birds especially who live in large flocks or school. This technique starts with a random initialization of the swarm in which each member or particle carries two values in its memory – one based on its own experience and the second based on the experience of the entire swarm. In the problem at hand, the number of clusters and identification of the clusterhead is not known. Further the node distribution in heterogeneous WSNs not uniform. Such a situation is not suitable either for Ant Colony or Particle Swarm optimization techniques. Such a problem could be best treated using a genetic algorithm which is probabilistic and not deterministic. The chromosomes used are encoded with potential solution rather than the parameters it selves. The fitness code in GA is based on an objective function rather than the personal based and global based or other such information used in other optimization techniques.