Dynamic Genetic Algorithms with Hyper-Mutation Schemes for Dynamic Shortest Path Routing Problem in Mobile Ad Hoc Networks

Dynamic Genetic Algorithms with Hyper-Mutation Schemes for Dynamic Shortest Path Routing Problem in Mobile Ad Hoc Networks

Hui Cheng (University of Bedfordshire, UK)
DOI: 10.4018/jaras.2012010105
OnDemand PDF Download:
List Price: $37.50


In recent years, the static shortest path (SP) routing problem has been well addressed using intelligent optimization techniques, e.g., artificial neural networks (ANNs), genetic algorithms (GAs), particle swarm optimization (PSO), etc. However, with the advancement in wireless communications, more and more mobile wireless networks appear, e.g., mobile ad hoc network (MANET), wireless mesh network (WMN), etc. One of the most important characteristics in mobile wireless networks is the topology dynamics, that is, the network topology changes over time due to energy conservation or node mobility. Therefore, the SP routing problem in MANETs turns out to be a dynamic optimization problem. This paper proposes to use two types of hyper-mutation GAs to solve the dynamic SP routing problem in MANETs. The authors consider MANETs as target systems because they represent new generation wireless networks. The experimental results show that the two hyper-mutation GAs can quickly adapt to the environmental changes (i.e., the network topology change) and produce good solutions after each change.
Article Preview


Mobile ad hoc network (Siva Ram Murthy et al., 2004) is a self-organizing and self-configuring multi-hop wireless network, comprised of a set of mobile hosts (MHs) that can move around freely and cooperate in relaying packets on behalf of one another. MANET supports robust and efficient operation by incorporating routing functionality into MHs. In MANETs, unicast routing establishes a multi-hop forwarding path for two nodes beyond the direct wireless communication range. Routing protocols also maintain connectivity when links on these paths break due to effects such as node movement, battery drainage, radio propagation, or wireless interference. In multi-hop networks, routing is a very important issue that has significant impact on the network's performance. So far, there are mainly two types of routing protocols in MANETs, namely, topological routing and geographic routing. In topological routing, mobile nodes utilize topological information to construct routing tables or search routes directly. In geographic routing, each node knows its own position and makes routing decisions based on the destination’s position and its local neighbors' positions.

In this paper, we investigate the shortest path routing, which belongs to the topological routing. The shortest path routing problem concerns with finding the shortest path from a specific source to a specific destination in a given network while minimizing the total cost associated with the path. The SP routing problem involves a classical combinatorial optimization problem arising in many designs and planning contexts (Ali et al., 1993; Ahn et al., 2001). There are several search algorithms for the SP routing problem: the Dijkstra's algorithm, the breadth-first search algorithm and the Bellman-Ford algorithm, etc. All these algorithms have polynomial time complexity. Therefore, they will be effective in fixed infrastructure wireless or wired networks. But, they exhibit unacceptably high computational complexity for real-time communications involving rapidly changing network topologies (Ahn et al., 2001, 2002). Therefore, for the dynamic SP routing problem in a changing network environment, we need to employ new appropriate approaches.

Since the static SP routing problem is a combinatorial optimization problem, the dynamic SP routing problem turns out to be one dynamic optimization problem (DOP). In recent years, studying EAs for DOPs has attracted a growing interest due to its importance in EA's real world applications (Yang et al., 2008). The simplest way of addressing DOPs is to restart EAs from scratch whenever an environment change is detected. Though the restart scheme really works for some cases (Yang et al., 2005), for many DOPs it is more efficient to develop other approaches that can efficiently adapt to the environmental changes. One of the possible approaches is to adaptively adjust the mutation rate during the run of EAs, i.e., the hyper-mutation schemes (Cobb, 1990; Kramer et al., 2003). In the basic hyper-mutation scheme, the mutation rate is increased following an environmental change and then slowly decreased back to its original level. This way, the solution's diversity of GA can be kept to the changing environment.

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 8: 2 Issues (2017): Forthcoming, Available for Pre-Order
Volume 7: 1 Issue (2016)
Volume 6: 2 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing