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

Introduction

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.