Article Preview
TopIntroduction
Wireless Mesh Networks (WMNs) (Akyildiz, Wang, & Wang, 2005; Nandiraju, Nandiraju, Santhanama, He, Wang, & Agrawal, 2007; Chen & Chekuri, 2007) are important network infrastructure for providing cost-efficient broadband wireless connectivity. They are showing their applicability in deployment of medical, transport and surveillance applications in urban areas, metropolitan, neighboring communities and municipal area networks. At the heart of WMNs are the issues of achieving network connectivity and stability as well as QoS in terms of user coverage. These issues are very closely related to the family of node placement problems in WMNs, such as mesh router nodes placement.
Node placement problems have been long investigated in the optimization field due to numerous applications in location science (facility location, logistics, services, etc.) and classification (clustering). Facility location problems are thus showing their usefulness to communication networks, and more especially from WMNs field. WMNs are currently attracting a lot of attention from wireless research and technology community for providing cost-efficient broadband wireless connectivity.
WMNs are based on mesh topology, in which every node (representing a server) is connected to one or more nodes, enabling thus the information transmission in more than one path (Durresi, Zhang, Durresi, & Barolli, 2010). The path redundancy is a robust feature of this kind of topology.
Compared to other topologies, mesh topology needs not a central node, allowing networks based on such topology to be self-healing. These characteristics of networks with mesh topology make them very reliable and robust networks (Behera & Tripathy, 2014) to potential server node failures. In WMNs mesh routers provide network connectivity services to mesh client nodes. The good performance and operability of WMNs largely depends on placement of mesh routers nodes in the geographical deployment area to achieve network connectivity, stability and user coverage. The objective is to find an optimal and robust topology of the mesh router nodes to support connectivity services to clients.
For most formulations, node placement problems are shown to be computationally hard to solve to optimality (Garey & Johnson, 1979; Lim, Rodrigues, Wang & Xua, 2005; Amaldi, Capone, Cesana, Filippini, Malucelli, 2008; Wang, Xie, Cai & Agrawal, 2007), and therefore heuristic and meta-heuristic approaches are useful approaches to solve the problem for practical purposes. Several heuristic approaches are found in the literature for node placement problems in WMNs (Muthaiah & Rosenberg, 2008; Zhou, Manoj & Rao, 2007; M. Tang, 2009; Antony Franklin & Siva Ram Murthy, 2007; Vanhatupa, Hannikainen & Hamalainen, 2007).
In our previous work (Xhafa, Sanchez, Barolli & Miho, 2010; Sakamoto, Kulla, Oda, Ikeda, Barolli & Xhafa, 2014), we implemented a simulation system using Simulated Annealing (SA) for WMNs. We call this simulation system WMN-SA.
In this work, we applied our implemented WMN-SA system in a realistic scenario considering the distribution of mesh clients in Itoshima City, Fukuoka Prefecture, Japan. For simulations, we consider a realistic distributions of 108 mesh clients in Itoshima city. Then, we deployed 36 mesh routers and run WMN-SA simulation system to maximize the size of Giant Component (GC) and Number of Covered Mesh Clients (NCMC).
The rest of the paper is organized as follows. In the next section, we present the definition of node placement problem. Then, we describe the proposed and implemented WMN-SA simulation system. After that, we present the simulation results. Finally, we give concluding remarks and future work.