Router and gateway node placement in wireless mesh networks for emergency rescue scenarios

Abstract

The focus of this paper is on base functionalities required for UAV-based rapid deployment of an ad hoc communication infrastructure in the initial phases of rescue operations. The main idea is to use heterogeneous teams of UAVs to deploy communication kits that include routers, and are used in the generation of ad hoc Wireless Mesh Networks (WMN). Several fundamental problems are considered and algorithms are proposed to solve these problems. The Router Node Placement problem (RNP) and a generalization of it that takes into account additional constraints arising in actual field usage is considered first. The RNP problem tries to determine how to optimally place routers in a WMN. A new algorithm, the RRT-WMN algorithm, is proposed to solve this problem. It is based in part on a novel use of the Rapidly Exploring Random Trees (RRT) algorithm used in motion planning. A comparative empirical evaluation between the RRT-WMN algorithm and existing techniques such as the Covariance Matrix Adaptation Evolution Strategy (CMA-ES) and Particle Swarm Optimization (PSO), shows that the RRT-WMN algorithm has far better performance both in amount of time taken and regional coverage as the generalized RNP problem scales to realistic scenarios. The Gateway Node Placement Problem (GNP) tries to determine how to locate a minimal number of gateway nodes in a WMN backbone network while satisfying a number of Quality of Service (QoS) constraints.Two alternatives are proposed for solving the combined RNP-GNP problem. The first approach combines the RRT-WMN algorithm with a preexisting graph clustering algorithm. The second approach, WMNbyAreaDecomposition, proposes a novel divide-and-conquer algorithm that recursively partitions a target deployment area into a set of disjoint regions, thus creating a number of simpler RNP problems that are then solved concurrently. Both algorithms are evaluated on real-world GIS models of different size and complexity. WMNbyAreaDecomposition is shown to outperform existing algorithms using 73% to 92% fewer router nodes while at the same time satisfying all QoS requirements.

Keywords

Robotics / UAV deployed ad hoc networks / Wireless mesh networks / Router node placement / Gateway node placement / Emergency rescue

References

[1] DenningP. J.. Hastily formed networks. Commun. ACM, 2006, 49(4):15-20 https://doi.org/10.1145/1121949.1121966

[2] United Nations Office for Coordination of Humanitarian Affairs (UNOCHA), 2010 Haiti Earthquake Response: An After Action Review of Response. INSARAG Haiti Earthquake After-Action Review Meeting. Geneva (2010). https://www.insarag.org/wp-content/uploads/2016/04/Printed_Haiti_Book_Low_Definition_Version.pdf. Accessed Oct 2021.

[3] C. Berger, P. Doherty, P. Rudol, M. Wzorek, Hastily formed knowledge networks and distributed situation awareness for collaborative robotics. arXiv preprint arXiv:2103.14078 (2021).

[4] M. Wzorek, C. Berger, P. Rudol, P. Doherty, in International Electrical Engineering Congress (iEECON). Deployment of ad hoc network nodes using uavs for search and rescue missions, (2018). https://doi.org/10.1109/IEECON.2018.8712230.

[5] GuptaP., KumarP. R.. The capacity of wireless networks. IEEE Transactions on information theory, 2000, 46(2):388-404 https://doi.org/10.1109/18.825799

[6] J. Li, C. Blake, D. S. De Couto, H. I. Lee, R. Morris, in Proceedings of the 7th Annual International Conference on Mobile Computing and Networking. Capacity of ad hoc wireless networks, (2001), pp. 61–69. https://doi.org/10.1145/381677.381684.

[7] JunJ., SichitiuM. L.. The nominal capacity of wireless mesh networks. IEEE Wirel. Commun., 2003, 10(5):8-14

[8] P. Kyasanur, N. H. Vaidya, in Proceedings of the 11th Annual International Conference on Mobile Computing and Networking. Capacity of multi-channel wireless networks: impact of number of channels and interfaces, (2005), pp. 43–57. https://doi.org/10.1145/1080829.1080835.

[9] HeB., XieB., AgrawalD. P.. Optimizing the internet gateway deployment in a wireless mesh network. 2007 IEEE International Conference on Mobile Adhoc and Sensor Systems, 2007 Pisa IEEE 1-9 https://doi.org/10.1109/MOBHOC.2007.4428603

[10] ShillingtonL., TongD.. Maximizing wireless mesh network coverage. Int. Reg. Sci. Rev., 2011, 34(4):419-437

[11] H. Suzuki, Y. Kaneko, K. Mase, S. Yamazaki, H. Makino, in IEEE Vehicular Technology Conference. An ad hoc network in the sky, skymesh, for large-scale disaster recovery (IEEE, 2006), pp. 1–5. https://doi.org/10.1109/VTCF.2006.496.

[12] DilmaghaniR. B., RaoR. R.. Hybrid wireless mesh network with application to emergency scenarios. J. Softw., 2008, 3(2):52-60

[13] LinC. -C.. Dynamic router node placement in wireless mesh networks: A pso approach with constriction coefficient and its convergence analysis. Inf. Sci., 2013, 232: 294-308 https://doi.org/10.1016/j.ins.2012.12.023

[14] DrabuY., PeyraviH.. Gateway placement with QoS constraints in wireless mesh networks. Seventh International Conference on Networking (Icn 2008), 2008 Cancun IEEE 46-51 https://doi.org/10.1109/ICN.2008.89

[15] LeeG., MurrayA. T.. Maximal covering with network survivability requirements in wireless mesh networks. Comput. Environ. Urban. Syst., 2010, 34(1):49-57 https://doi.org/10.1016/j.compenvurbsys.2009.05.004

[16] LinC. -C., ChenT. -H., ChinH. -H.. Adaptive router node placement with gateway positions and qos constraints in dynamic wireless mesh networks. J. Netw. Comput. Appl., 2016, 74: 149-164 https://doi.org/10.1016/j.jnca.2016.05.005

[17] XhafaF., SánchezC., BarolliL.. Genetic algorithms for efficient placement of router nodes in wireless mesh networks. 2010 24th IEEE International Conference on Advanced Information Networking and Applications, 2010 Perth IEEE 465-472 https://doi.org/10.1109/AINA.2010.41

[18] LinC. -C., TsengP. -T., WuT. -Y., DengD. -J.. Social-aware dynamic router node placement in wireless mesh networks. Wirel. Netw., 2016, 22(4):1235-1250 https://doi.org/10.1007/s11276-015-1036-7

[19] LinC. -C., ShuL., DengD. -J.. Router node placement with service priority in wireless mesh networks using simulated annealing with momentum terms. IEEE Syst. J., 2016, 10(4):1402-1411 https://doi.org/10.1109/JSYST.2014.2341033

[20] J. J. Kuffner, S. M. LaValle, in Proc. ICRA. RRT-connect: An efficient approach to single-query path planning, (2000). https://doi.org/10.1109/ROBOT.2000.844730.

[21] BejeranoY.. Efficient integration of multihop wireless and wired networks with qos constraints. IEEE/ACM Trans. Netw., 2004, 12(6):1064-1078 https://doi.org/10.1109/TNET.2004.838599

[22] AounB., BoutabaR., IraqiY., KenwardG.. Gateway placement optimization in wireless mesh networks with qos constraints. IEEE J. Sel. Areas Commun., 2006, 24(11):2127-2136 https://doi.org/10.1109/JSAC.2006.881606

[23] WzorekM., BergerC., DohertyP.. NayakA. C., SharmaA.. Router node placement in wireless mesh networks for emergency rescue scenarios. PRICAI 2019: Trends in Artificial Intelligence, 2019 Cham Springer 496-509 https://doi.org/10.1007/978-3-030-29911-8\_38

[24] HansenN.. The CMA Evolution Strategy: A Comparing Review, 2006 Berlin, Heidelberg Springer https://doi.org/10.1007/3-540-32494-1\_4

[25] R. Eberhart, J. Kennedy, in MHS’95. Proceedings of the Sixth International Symposium on Micro Machine and Human Science. A new optimizer using particle swarm theory, (1995), pp. 39–43. https://doi.org/10.1109/MHS.1995.494215.

[26] JohnsonD. B., MaltzD. A., BrochJ., et al.. Dsr: The dynamic source routing protocol for multi-hop wireless ad hoc networks. Ad hoc Netw., 2001, 5(1):139-172

[27] C. Perkins, E. Belding-Royer, S. Das, RFC3561: Ad hoc on-demand distance vector (AODV) routing. RFC Editor (2003). https://doi.org/10.17487/RFC3561.

[28] OgierR., TemplinF., LewisM.. RFC3684: Topology Dissemination Based on Reverse-Path Forwarding (TBRPF), 2004 USA RFC Editor https://doi.org/10.17487/RFC3684

[29] A. Neumann, C. Aichele, M. Lindner, S. Wunderlich, Better Approach To Mobile Ad-hoc Networking (B.A.T.M.A.N.) (Internet Engineering Task Force, 2008). https://datatracker.ietf.org/doc/html/draft-openmesh-b-a-t-m-a-n-00.

[30] KyasanurP., VaidyaN. H.. Routing and interface assignment in multi-channel multi-interface wireless networks. IEEE Wireless Communications and Networking Conference, 2005, 2005 New Orleans IEEE 2051-2056 https://doi.org/10.1109/WCNC.2005.1424834

[31] K. N. Ramachandran, E. M. Belding-Royer, K. C. Almeroth, M. M. Buddhikot, in Infocom, 6. Interference-aware channel assignment in multi-radio wireless mesh networks, (2006), pp. 1–12. https://doi.org/10.1109/INFOCOM.2006.177.

[32] R. Ramanathan, in Proceedings of the 2nd ACM International Symposium on Mobile Ad Hoc Networking & Computing. On the performance of ad hoc networks with beamforming antennas, (2001), pp. 95–105. https://doi.org/10.1145/501426.501430.

[33] BlosteinS. D., LeibH.. Multiple antenna systems: their role and impact in future wireless access. IEEE Commun. Mag., 2003, 41(7):94-101 https://doi.org/10.1109/MCOM.2003.1215645

[34] NaeemT., LooJ. K. -K.. Common Security Issues and Challenges in Wireless Sensor Networks and IEEE 802-11 Wireless Mesh Networks. J. Dig. Content Technol. Appl., 2009, 3: 88-93 https://doi.org/10.4156/jdcta.vol3.issue1.naeem

[35] KhanS., MauriJ. L.. Security for Multihop Wireless Networks, 2014 Boca Raton Crc Press

[36] PathanA. -S. K.. Security of self-organizing networks: MANET, WSN, WMN, VANET, 2016 Boca Raton CRC press

[37] MaolinT., et al.. Gateways placement in backbone wireless mesh networks. Int. J. Commun. Netw. Syst. Sci., 2009, 2(01):44 https://doi.org/10.4236/ijcns.2009.21005

[38] FranklinA. A., MurthyC. S. R.. Node placement algorithm for deployment of twotier wireless mesh networks. IEEE GLOBECOM 2007-IEEE Global Telecommunications Conference, 2007 Washington DC IEEE 4823-4827 https://doi.org/10.1109/GLOCOM.2007.915

[39] J. Camp, J. Robinson, C. Steger, E. Knightly, in Proceedings of the 4th International Conference on Mobile Systems, Applications and Services. Measurement driven deployment of a two-tier urban mesh access network, (2006), pp. 96–109. https://doi.org/10.1145/1134680.1134691.

[40] XhafaF., BarolliA., SánchezC., BarolliL.. A simulated annealing algorithm for router nodes placement problem in wireless mesh networks. Simul. Model. Pract. Theory, 2011, 19(10):2276-2284 https://doi.org/10.1016/j.simpat.2010.08.014

[41] XhafaF., BarolliA., TakizawaM., et al.. A tabu search algorithm for efficient node placement in wireless mesh networks. 2011 Third International Conference on Intelligent networking and collaborative systems, 2011 Fukuoka IEEE 53-59 https://doi.org/10.1109/INCoS.2011.44

[42] SakamotoS., KullaE., OdaT., IkedaM., BarolliL., XhafaF.. A comparison study of simulated annealing and genetic algorithm for node placement problem in wireless mesh networks. J. Mob. Multimedia, 2013, 9(1&2):101-110

[43] OdaT., LiuY., SakamotoS., ElmaziD., BarolliL., Xhafa XhafaF.. Analysis of mesh router placement in wireless mesh networks using friedman test considering different meta-heuristics. Int. J. Commun. Netw. Distrib. Syst., 2015, 15(1):84-106 https://doi.org/10.1504/IJCNDS.2015.070289

[44] FriedmanM.. The use of ranks to avoid the assumption of normality implicit in the analysis of variance. J. Am. Stat. Assoc., 1937, 32(200):675-701 https://doi.org/10.1080/01621459.1937.10503522

[45] BarolliA., OdaT., IkedaM., BarolliL., XhafaF., LoiaV.. Node placement for wireless mesh networks: Analysis of wmn-ga system simulation results for different parameters and distributions. J. Comput. Syst. Sci., 2015, 81(8):1496-1507 https://doi.org/10.1016/j.jcss.2014.12.024

[46] HeB., XieB., AgrawalD. P.. Optimizing deployment of internet gateway in wireless mesh networks. Comput. Commun., 2008, 31(7):1259-1275 https://doi.org/10.1016/j.comcom.2008.01.061

[47] SeyedzadeganM., OthmanM., AliB. M., SubramaniamS.. Zero-degree algorithm for internet gateway placement in backbone wireless mesh networks. J. Netw. Comput. Appl., 2013, 36(6):1705-1723 https://doi.org/10.1016/j.jnca.2013.02.031

[48] WangJ., XieB., CaiK., AgrawalD. P.. Efficient mesh router placement in wireless mesh networks. 2007 IEEE International Conference on Mobile Adhoc and Sensor Systems, 2007 Pisa IEEE 1-9 https://doi.org/10.1109/MOBHOC.2007.4428616

[49] AmaldiE., CaponeA., CesanaM., FilippiniI., MalucelliF.. Optimization models and methods for planning wireless mesh networks. Comput. Netw., 2008, 52(11):2159-2171 https://doi.org/10.1016/j.comnet.2008.02.020

[50] SolisF. J., WetsR. J. -B.. Minimization by random search techniques. Math. Oper. Res., 1981, 6(1):19-30

[51] XhafaF., SánchezC., BarolliA., TakizawaM.. Solving mesh router nodes placement problem in wireless mesh networks by tabu search algorithm. J. Comput. Syst. Sci., 2015, 81(8):1417-1428 https://doi.org/10.1016/j.jcss.2014.12.018

[52] D. V. Arnold, N. Hansen, in Proceedings of the 14th Annual Conference on Genetic and Evolutionary Computation. A (1+ 1)-cma-es for constrained optimisation, (2012), pp. 297–304.

[53] M. Kohler, L. Forero, M. Vellasco, R. Tanscheit, M. A. Pacheco, in 2016 IEEE Congress on Evolutionary Computation (CEC). Pso+: A nonlinear constraints-handling particle swarm optimization, (2016), pp. 2518–2523. https://doi.org/10.1109/CEC.2016.7744102.

[54] Lantmäteriet, Lantmäteriet open geodata (2020). https://lantmateriet.se/en/maps-and-geographic-information/open-geodata/. Accessed Dec 2019.

[55] HertS., LumelskyV.. Polygon area decomposition for multiple-robot workspace division. International Journal of Computational Geometry and Applications, 1998, 8: 437-466 https://doi.org/10.1142/S0218195998000230

[56] M. Wzorek, C. Berger, P. Doherty, Polygon Area Decomposition using a Compactness Metric. arXiv preprint arXiv:2110.04043 (2021).

[57] SchwartzbergJ. E.. Reapportionment, gerrymanders, and the notion of compactness. Minn. L. Rev., 1965, 50: 443

Funding

Stiftelsen f?r?Strategisk Forskning(RIT15-0097); Knut och Alice Wallenbergs Stiftelse; ELLIIT Network Organization for Informa- tion and Communication Technology, Sweden; (guest) professor grant from Jinan University; RExperts Program Grant 2020A1313030098 from the Guangdong Department of Sci- ence and Technology