Genetic-Algorithm-Based Optimization of Clustering in Mobile Ad Hoc Network

Genetic-Algorithm-Based Optimization of Clustering in Mobile Ad Hoc Network

Koushik Majumder (West Bengal University of Technology, India), Debashis De (West Bengal University of Technology, India), Senjuti Kar (West Bengal University of Technology, India) and Rani Singh (West Bengal University of Technology, India)
DOI: 10.4018/978-1-5225-0058-2.ch006
OnDemand PDF Download:


Mobile Ad hoc Networks (MANET) are wireless infrastructure less networks that are formed spontaneously and are highly dynamic in nature. Clustering is done in MANETs to address issues related to scalability, heterogeneity and to reduce network overhead. In clustering the entire network is divided into clusters or groups with one Cluster Head (CH) per cluster. The process of CH selection and route optimization is extremely crucial in clustering. Genetic Algorithm (GA) can be implemented to optimize the process of clustering in MANETs. GA is the most recently used advanced bio-inspired optimization technique which implements techniques of genetics like selection, crossover, mutation etc. to find out an improved solution to a problem similar to the next generation that inherits the positive traits and features of the previous one. In this chapter several genetic algorithm based optimization techniques for clustering has been discussed. A comparative analysis of the different approaches has also been presented. This chapter concludes with future research directions in this domain.
Chapter Preview


Natural computing encompasses those procedures that are inspired from nature for the optimization of various problem solving mechanisms. Natural computing includes fields like evolutionary algorithms, swarm intelligence, artificial neural network, quantum computing etc. Perceiving natural occurrences as computational processes provide a clear understanding of the natural phenomena and the core principles of computation. Fig. 1 shows the different computation models inspired from nature. Genetic algorithms belong to the category of evolutionary algorithms. Genetic algorithms are employed for the optimization of certain problems using techniques of natural evolution like selection, crossover, mutation and inheritance. It is an advanced bio-inspired optimization technique which has the capability to enhance the performance of a MANET.

Figure 1.

Different models of computation inspired by nature

Mobile Ad hoc Network or MANETs are wireless network which is organized without any infrastructure. In a MANET the devices move about independently of one another and thus its links with other devices also change (Goyal, Pamar & Rishi, 2011; Kumar & Mishra, 2012). All the devices in a MANET forward packets and hence act as routers (Di Caro, Ducatelle & Gambardella, 2005). Due to lack of infrastructure, MANETs are very useful at times of disasters like floods, earthquakes etc., which leads to destruction of infrastructures. MANETs are also very useful for battlefield communication (Wallner, Harder & Agee, 1999; Attia, Rizk & Mariee, 2009).

In a MANET the routing protocol must be efficient enough to search a path from one node to another, to facilitate communication. The network topology in a MANET changes continuously and so the routing scheme has to keep up with the mobility of the nodes to effectively route packets (Papandriopoulos, Dey& Evans, 2006; Chatterjee, Das & Turgut, 2000). However, a flat routing structure generate huge network overhead which can result in poor functioning of the network in terms of performance. Additionally a MANET comprises of heterogeneous nodes (Chatterjee, Das &Turgut, 2002; Ramanathan & Redi, 2002), i.e. the nodes vary with respect to their resources. For example some nodes might have better computation power, longer battery life etc (Ramanathan, Redi, Santivanez, Wiggins &Polit, 2005; Gibson, 2012; Haas, Deng, Liang, Papadimitratos & Sajama, 2002). These nodes can perform better in an ad hoc network scenario. Clustering in MANETs introduces hierarchy and hence effectively addresses the heterogeneity of nodes and significantly limits the propagation of routing related information throughout the network (Yu & Chong, 2005; Agarwal & Motwani, 2009). In clustering the entire network is partitioned into overlapping clusters or groups. In this approach routes between clusters are kept track of instead of routes between individual nodes. This effectively lowers the overhead due to control messages. In cluster-based routing the nodes may be assigned as a clusterhead (CH), cluster gateway or a cluster member. The CH acts like an organizer for a given cluster. A cluster gateway is not a CH and it connects a CH with other CHs. The cluster members redirect the data packets to the corresponding CH, which routes the packets to other members of the cluster or to the cluster gateway if the node meant to receive the packet is in another cluster. The cluster members are nodes without any inter-cluster connections.

Key Terms in this Chapter

Chromosome: It is a linear organized structure that contains the DNA of the living organism. The genes are found on the chromosome.

Mutation: Mutation is a stage in genetic algorithm in which one or more genes in a chromosome are modified to maintain diversity in the population of successive generations.

Clustering: It is a process in which the network is divided into logical groups called clusters. Each cluster has a cluster head and the remaining members are called cluster members. The cluster heads communicate with each other via cluster gateway nodes.

Genetic Algorithm: It is a search technique that imitates the procedure of natural selection. Genetic algorithms are used to optimize different search problems.

Crossover: It is a step in genetic algorithm where two or more parent solutions are chosen to produce a child solution.

Cluster Head: It is a mobile node that is in charge of a cluster. The inter-cluster routing takes place via the cluster head.

Gene: In a living organism a gene is a unit of heredity at the molecular level. It is transferred from the parent to the offspring and determines the characteristics of the offspring.

Complete Chapter List

Search this Book: