In this chapter, we introduce a topology control mechanism based on genetic algorithms (GAs) within a mobile ad hoc network (MANET). We provide formal and practical aspects of convergence properties of our force-based genetic algorithm, called FGA. Within this framework, FGA is used as a decentralized topology control mechanism among active running software agents to achieve a uniform spread of autonomous mobile nodes over an unknown geographical terrain. FGA can be treated as a dynamical system in order to provide formalism to study its convergence trajectory in the space of possible populations. Discrete time dynamical system model is used for calculating the cumulative effects of our FGA operators such as selection, mutation, and crossover as a population of possible solutions evolves through generations. To demonstrate applicability of FGA to real-life problems and evaluate its effectiveness, we implemented a simulation software system and several different testbed platforms. The simulation and testbed experiment results indicate that, for important performance metrics such as normalized area coverage (NAC) and convergence rate, FGA can be an effective mechanism to deploy nodes under restrained communication conditions in MANETs operating in unknown areas. Since FGA adapts to the local environment rapidly and does not require global network knowledge, it can be used as a real-time topology controller for realistic military and civilian applications.
TopIntroduction
Autonomous systems represent a blend of software and machinery to create intelligent platforms for complex real world problems without human control and guidance. These systems must be self-sufficient and capable of adapting their behavior to rapidly changing and most likely unfamiliar environments.
A mobile ad hoc network (MANET) consists of an autonomous system of mobile nodes which dynamically form a network without any pre-existing structure. These mobile entities are geographically dispersed and equipped with wireless transmitters and receivers to communicate with each other within the MANET. The communications among the mobile nodes are generally established through multi-hop routing due to the limited range of transmission capabilities of each individual node. Since the mobile nodes move arbitrarily in a MANET, the network topology may change dynamically and unpredictably. One way of maintaining a uniform distribution of mobile nodes over any terrain is to provide the nodes with the ability to adapt their speeds and movement directions based on their local neighbor nodes and surroundings (e.g., number of neighbors, neighbors’ locations, obstacles within node sensing range, etc.).
It is easy to envision many applications for GA-based topology control approach ranging from military to commercial applications, such as search and rescue missions (e.g., locating humans trapped in rubble after an earthquake), controlling unmanned vehicles and transportation systems, clearing mine-fields, and spreading military assets (e.g., robots, mini-submarines, etc.) under harsh and bandwidth-limited conditions. In these applications a large number of mobile nodes can gather information from multiple viewpoints simultaneously, allowing them to share information and adapt to the environment quickly and comprehensively. A common objective among these applications is the uniform distribution of autonomous mobile nodes operating on geographical areas without prior geographical terrain knowledge. The topology control of autonomous mobile nodes faces extra challenges in MANETs since: (a) due to mobility, local terrain may change dramatically in a short time-span during an operation, (b) the number of mobile nodes may increase or decrease unpredictably due to malfunctions, (c) mobile nodes may not have access to neither navigation maps or GPS devices, but can only have limited information collected from local neighbors, and (d) nodes may be deployed into a terrain from a single entry point (rather than random or other types of initial distributions often seen in existing research).
Genetic algorithms (GAs) are adaptive heuristic search algorithms which have been demonstrated to be useful tools in a variety of search and optimization problems. GAs premise on the evolutionary ideas of natural selection and search for the best individuals within a population as the GA evolves toward the fittest solution or optimum result in an entire problem space (Holland, 1995; Mitchell, 1996). We introduce a force-based GA called FGA as a topology control mechanism in MANETs (see, for example, Sahin et al., 2008; Urrea et al., 2009; Sahin et al., 2010; Sahin, 2010). In this framework, each mobile node runs FGA to decide its next speed and movement direction based on its current local information to obtain a uniform distribution. The objective function used in FGA is inspired by the equilibrium of the molecules in physics where each molecule tries to be in the balanced position and to spend minimum energy to protect its own position. FGA uses the objective function (also called fitness function) to quantify the optimality of a solution (chromosome) and rank it against all the other chromosomes.
We implemented simulation software to evaluate FGA’s effectiveness and applicability to real-life problems. In addition, in the Bio-inspired Computing Laboratory at the City College of New York, we built several testbeds to study the convergence properties of various GA-based topology control mechanisms, including FGA, in MANETs. Our testbeds use different technologies and components namely FPGA Virtex-IITM with laptops and desktops and small robots (iRobotsTM) controlled by gumstixTM processors (Dogan et al., 2008; Dogan et al., 2009).