Article Preview
TopIntroduction
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.