Abstract
Wireless ad-hoc networks are infrastructureless networks in which heterogeneous capable nodes assemble together and start communicating without any backbone support. These networks can be made truly dynamic and the nodes in these networks can move about freely while connecting and disconnecting with other nodes in the network. This property of ad-hoc networks to self-organize and communicate without any extrinsic support gives them tremendous flexibility and makes them perfect for applications such as emergencies, crisis-management, military and healthcare. For example, in case of emergencies such as earthquakes, often most of the existing wired network infrastructure gets destroyed. In addition, since most of the wireless networks such as GSM and IEEE 802.11 wireless LAN use wired infrastructure as their backbone, often they are also rendered useless. In such scenarios, ad-hoc networks can be deployed swiftly and used for coordinating relief and rescue operations. Ad-hoc networks can be used for communication between various stations in the battle-field, where setting up a wired or an infrastructure-based network is often considered impractical. Though a lot of research has been done on ad-hoc networks, a lot of problems such as security, qualityof- service (QoS) and multicasting need to be addressed satisfactorily before ad-hoc networks can move out of the labs and provide a flexible and cheap networking solution. Evolutionary computing algorithms are a class of bio-inspired computing algorithms. Bio-inspired computing refers to the collection of algorithms that use techniques learnt from natural biological phenomena and implement them to solve a mathematical problem (Olario & Zomaya, 2006). Natural phenomena such as evolution, genetics, and collective behavior of social organisms and functioning of a mammalian brain teach us a variety of techniques that can be effectively employed to solve problems in computer science which are inherently tough. In this Chapter and the chapter entitled, “Swarm Intelligence Approach for Wireless Ad Hoc Networks” of this book, we present some of the currently available important implementations of bio-inspired computing in the field of ad-hoc networks. This chapter looks at the problem of optimal clustering in ad-hoc networks and its solution using Genetic Programming (GP) approach. The chapter entitled, “Swarm Intelligence Approaches for Wireless Ad Hoc Networks” of this book, continues the same spirit and explains the use of the principles underlying Ant Colony Optimization (ACO) for routing in ad-hoc networks.
TopBackground
The first infrastructureless network was implemented as packet radio (Toh, 2002). It was initiated by the Defense Advanced Research Projects Agency (DARPA) in 1970s. By this time the ALOHA project (McQuillan & Walden, 1977) at the University of Hawaii had demonstrated the feasibility of using broadcasting for sending / receiving the data packets in single-hop radio networks. ALOHA later led to the development of Packet Radio Network (PRNET), which was a multi-hop multiple-access network, under the sponsorship of Advanced Research Projects Agency (ARPA). PRNET had the design objectives similar to the current day ad-hoc networks such as flow and error control over multi-hop communication route, deriving and maintaining network topology information and mechanism to handle router mobility and power and size requirements, among others. However, since the electronic devices were huge then, the packet radios were not easily movable, leading to limited mobility. In addition, the network coverage was slow and since Bellman-Ford’s shortest path algorithm was used for routing, transient loops were present. Since then, a lot of research has been done on ad-hoc networks and a number of routing algorithms have been developed which provide far greater performances and are loop free. The rapid development of silicon technology has also led to ever shrinking devices with increasing computation power. Ad-hoc networks are deliberated for use in medical, relief-and-rescue, office environments, personal networking, and many other daily life applications.
Key Terms in this Chapter
Genetic Algorithms: The algorithms that are modelled on the natural process of evolution. These algorithms employ methods such as crossover, mutation and natural selection and provide the best possible solutions after analyzing a group of sub-optimal solutions which are provided as inputs
Clustering: Grouping the nodes of an ad hoc network such that each group is a self-organized entity having a cluster-head which is responsible for formation and management of its cluster.
Chromosome: A proposed solution to a problem which is represented as a string of bits and can mutate and cross-over to create a new solution.
Initial Population: Set of sub-optimal solutions which are provided as inputs to a genetic algorithm and from which an optimal solution evolves.
Mutation: Genetic operation which randomly alters a chromosome to produce a new chromosome adding new solution to the solution-set.
Bio-Inspired Algorithms: Group of algorithms modelled on the observed natural phenomena which are employed to solve mathematical problems.
Fitness Function: A function which maps the subjective property of a fitness of a solution to an objective value which can be used to arrange different solutions in the order of their suitability as final or intermediate solution.
Mobile Ad-Hoc Network: A multi-hop network formed by a group of mobile nodes which co-operate among each other to achieve communication, without requiring any supporting infrastructure
Cross-Over: Genetic operation which produces a new chromosome by combining the genes of two or more parent chromosome.
Genes: Genes are building blocks of chromosomes and represent the parameters that need to be optimized.