Abstract
The Wireless Mesh Networks (WMNs) enable routers to communicate with each other wirelessly in order to create a stable network over a wide area at a low cost and it has attracted much attention in recent years. There are different methods for optimizing the placement of mesh routers. In our previous work, we proposed a Coverage Construction Method (CCM), CCM-based Hill Climbing (HC) and CCM-based Simulated Annealing (SA) system for mesh router placement problem considering normal and uniform distributions of mesh clients. We also proposed Delaunay edge and CCM-based SA. In this approach, we consider a realistic scenario for mesh client placement rather than randomly generated mesh clients with normal or uniform distributions. However, this approach required many mesh routers to cover mesh clients located over a wide area. In this paper, we propose a method for optimization of number of mesh routers in WMNs. For the simulations, we consider the evacuation areas in Okayama City, Japan, as the target to be covered by mesh routers. From the simulation results, we found that the proposed method was able to cover the evacuation area. The proposed method also reduced the number of mesh routers by an average of 28 [\(\%\)].
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Akyildiz, I.F., et al.: Wireless mesh networks: a survey. Comput. Netw. 47(4), 445–487 (2005)
Oda, T., et al.: Implementation and experimental results of a WMN testbed in indoor environment considering LoS scenario. In: Proceedings of the IEEE 29-th International Conference on Advanced Information Networking and Applications (IEEE AINA-2015), pp. 37-42 (2015)
Jun, J., et al.: The nominal capacity of wireless mesh networks. IEEE Wirel. Commun. 10(5), 8–15 (2003)
Oyman, O., et al.: Multihop relaying for broadband wireless mesh networks: from theory to practice. IEEE Commun. Mag. 45(11), 116–122 (2007)
Oda, T., et al.: Evaluation of WMN-GA for different mutation operators. Int. J. Space-Based Situated Comput. 2(3) (2012)
Oda, T., et al.: Performance evaluation of WMN-GA for different mutation and crossover rates considering number of covered users parameter. Mob. Inf. Syst. 8(1), 1–16 (2012)
Oda, T., et al.: WMN-GA: a simulation system for WMNs and its evaluation considering selection operators. J. Ambient. Intell. Humaniz. Comput. 4(3), 323–330 (2013)
Oda, T., et al.: Node placement in WMNs using WMN-GA system considering uniform and normal distribution of mesh clients. In: Proceedings of the IEEE 8-th International Conference on Complex, Intelligent and Software Intensive Systems (IEEE CISIS-2014), pp. 120-127 (2014)
Oda, T., et al.: A GA-based simulation system for WMNs: performance analysis for different WMN architectures considering TCP. In: Proceedings of the IEEE 9-th International Conference on Broadband and Wireless Computing, Communication and Applications (IEEE BWCCA-2014), pp. 120-126 (2014)
Oda, T., et al.: Effects of population size for location-aware node placement in WMNs: evaluation by a genetic algorithm-based approach. Pers. Ubiquit. Comput. 18(2), 261–269 (2014)
Ikeda, M., et al.: Analysis of WMN-GA simulation results: WMN performance considering stationary and mobile scenarios. In: Proceedings of the 28-th IEEE International Conference on Advanced Information Networking and Applications (IEEE AINA-2014), pp. 337-342 (2014)
Oda, T., et al.: Analysis of mesh router placement in wireless mesh networks using friedman test. In: Proceedings of the IEEE 28-th International Conference on Advanced Information Networking and Applications (IEEE AINA-2014), pp. 289-296 (2014)
Oda, T., et al.: Effect of different grid shapes in wireless mesh network-genetic algorithm system. Int. J. Web Grid Serv. 10(4), 371–395 (2014)
Oda, T., et al.: Analysis of mesh router placement in wireless mesh networks using friedman test considering different meta-heuristics. Int. J. Commun. Networks Distributed Syst. 15(1), 84–106 (2015)
Oda, T., et al.: A genetic algorithm-based system for wireless mesh networks: analysis of system data considering different routing protocols and architectures. Soft. Comput. 20(7), 2627–2640 (2016)
Sakamoto, S., et al.: Performance evaluation of intelligent hybrid systems for node placement in wireless mesh networks: a comparison study of WMN-PSOHC and WMN-PSOSA. In: Proceedings of the 11-th International Conference on Innovative Mobile and Internet Services in Ubiquitous Computing (IMIS-2017), pp. 16-26 (2017)
Holland, J.H.: Genetic algorithms. Sci. Am. 267(1), 66–73 (1992)
Skalak, D.B.: Prototype and feature selection by sampling and random mutation hill climbing algorithms. In: Proceedings of the 11-th International Conference on Machine Learning (ICML-1994), pp. 293-301 (1994)
Kirkpatrick, S., et al.: Optimization by simulated annealing. Science 220(4598), 671–680 (1983)
Glover, F.: Tabu search: a tutorial. Interfaces 20(4), 74–94 (1990)
Kennedy, J., Eberhart, R.: Particle swarm optimization. In: Proceedings of the IEEE International Conference on Neural Networks (ICNN-1995), pp. 1942-1948 (1995)
Hirata, A., et al.: Approach of a solution construction method for mesh router placement optimization problem. In: Proceedings of the IEEE 9-th Global Conference on Consumer Electronics (IEEE GCCE-2020), pp. 467-468 (2020)
Hirata, A., et al.: A coverage construction method based hill climbing approach for mesh router placement optimization. In: Proceedings of the 15-th International Conference on Broadband and Wireless Computing, Communication and Applications (BWCCA-2020), pp. 355–364 (2020)
Hirata, A., et al.: Simulation results of CCM based HC for mesh router placement optimization considering two Islands model of mesh clients distributions. In: Proceedings of the 9-th International Conference on Emerging Internet, Data & Web Technologies (EIDWT-2021), pp. 180–188 (2021)
Hirata, A., et al.: A coverage construction and hill climbing approach for mesh router placement optimization: simulation results for different number of mesh routers and instances considering normal distribution of mesh clients. In: Proceedings of the 15-th International Conference on Complex, Intelligent and Software Intensive Systems (CISIS-2021), pp. 161-171 (2021)
Hirata, A., et al.: A CCM-based HC system for mesh router placement optimization: a comparison study for different instances considering normal and uniform distributions of mesh clients. In: Proceedings of the 24-th International Conference on Network-Based Information Systems (NBiS-2021), pp. 329-340 (2021)
Hirata, A., et al.: A simulation system for mesh router placement in WMNs considering coverage construction method and simulated annealing. In: Proceedings of the 16-th International Conference on Broadband and Wireless Computing, Communication and Applications (BWCCA-2021), pp. 78–87 (2021)
Hirata, A., et al.: Delaunay edge and CCM-based SA approach for mesh router placement optimization in WMN: a case study for evacuation area in Okayama City. In: Proceedings of the 10-th International Conference on Emerging Internet, Data & Web Technologies (EIDWT-2022), pp. 346–356 (2022)
Tarjan, R.: Depth-first search and linear graph algorithms. SIAM J. Comput. 1(2), 146–160 (1972)
Integrated GIS for all of Okayama Prefecture. http://www.gis.pref.okayama.jp/pref-okayama/OpenData, ref. Nov. 16 2021
Acknowledgement
This work was supported by JSPS KAKENHI Grant Number JP20K19793.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Hirata, A. et al. (2022). A New Method for Optimization of Number of Mesh Routers and Improving Cost Efficiency in Wireless Mesh Networks. In: Barolli, L. (eds) Complex, Intelligent and Software Intensive Systems. CISIS 2022. Lecture Notes in Networks and Systems, vol 497. Springer, Cham. https://doi.org/10.1007/978-3-031-08812-4_5
Download citation
DOI: https://doi.org/10.1007/978-3-031-08812-4_5
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-08811-7
Online ISBN: 978-3-031-08812-4
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)