Article Preview
TopIntroduction
WMNs distinguish for their low cost nature that makes them attractive for providing wireless Internet connectivity. Moreover, such infrastructure can be used to deploy community networks, metropolitan area networks, municipal and, corporative networks, and to support applications for urban areas (Chen et al., 2007), medical, transport, and surveillance systems. The main issue of WMNs (Akyildiz et al., 2005) is to achieve network connectivity and stability as well as QoS in terms of user coverage. This problem is very closely related to the family of node placement problems in WMNs (Muthaiah et al., 2008; Tang et al., 2009; Franklin et al., 2007; Vanhatupa et al., 2007; Amaldi et al., 2008; Zhou et al., 2007) among them, the mesh router mesh nodes placement. Here, we consider the version of the mesh router nodes placement problem in which we are given a grid area where to deploy a number of mesh router nodes and a number of mesh client nodes of fixed positions (of an arbitrary distribution) in the grid area. As node placement problems are known to be computationally hard to solve for most of the formulations (Garey et al., 1979; Lim et al., 2005; Wang et al., 2007), Genetic Algorithms (GAs) have been recently investigated as effective resolution methods. However, GAs require the user to provide values for a number of parameters and a set of genetic operators to achieve the best GA performance for the problem (Yao et al., 1993; Dezigner et al., 2006; Odetayo et al., 1997; Xhafa et al., 2008; Xhafa et al., 2007, 2009; Ochoa, 2002; Back, 1993).
In this paper, we deal with connectivity and coverage problem in WMNs. Because these problems are known to be NP-Hard, we propose and implement a system based on GAs, called WMN-GA. We evaluate the performance of the proposed system by different scenarios using different metrics such as crossover rate, mutation rate, giant component and covered users. We compared the performance of the system for normal distribution and different rates of crossover and mutation. Different from our other paper (Oda et al.), where we use as selection operator Linear Ranking, in this paper we use as selection operator Exponential Ranking. Setting the values of parameters in GAs has been and still is a major issue in GA research field. One such parameter is mutation rate. It has a considerable effect on GA convergence and, consequently in the quality of the found solution. For this reason we change the rates of crossover and mutation to see the behaviour of the system. By comparing the simulation results, we found out that the system has better behaviour when the setting of crossover rate is 0.7 and the mutation rate is 0.3.