Router and gateway node placement in wireless mesh networks for emergency rescue scenarios
Tóm tắt
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.
Tài liệu tham khảo
P. J. Denning, Hastily formed networks. Commun. ACM. 49(4), 15–20 (2006). https://doi.org/10.1145/1121949.1121966.
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.
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).
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.
P. Gupta, P. R. Kumar, The capacity of wireless networks. IEEE Transactions on information theory. 46(2), 388–404 (2000). https://doi.org/10.1109/18.825799.
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.
J. Jun, M. L. Sichitiu, The nominal capacity of wireless mesh networks. IEEE Wirel. Commun.10(5), 8–14 (2003).
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.
B. He, B. Xie, D. P. Agrawal, in 2007 IEEE International Conference on Mobile Adhoc and Sensor Systems. Optimizing the internet gateway deployment in a wireless mesh network (IEEEPisa, 2007), pp. 1–9. https://doi.org/10.1109/MOBHOC.2007.4428603.
L. Shillington, D. Tong, Maximizing wireless mesh network coverage. Int. Reg. Sci. Rev.34(4), 419–437 (2011).
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.
R. B. Dilmaghani, R. R. Rao, Hybrid wireless mesh network with application to emergency scenarios. J. Softw.3(2), 52–60 (2008).
C. -C. Lin, Dynamic router node placement in wireless mesh networks: A pso approach with constriction coefficient and its convergence analysis. Inf. Sci.232:, 294–308 (2013). https://doi.org/10.1016/j.ins.2012.12.023.
Y. Drabu, H. Peyravi, in Seventh International Conference on Networking (Icn 2008). Gateway placement with QoS constraints in wireless mesh networks (IEEECancun, 2008), pp. 46–51. https://doi.org/10.1109/ICN.2008.89.
G. Lee, A. T. Murray, Maximal covering with network survivability requirements in wireless mesh networks. Comput. Environ. Urban. Syst.34(1), 49–57 (2010). https://doi.org/10.1016/j.compenvurbsys.2009.05.004.
C. -C. Lin, T. -H. Chen, H. -H. Chin, Adaptive router node placement with gateway positions and qos constraints in dynamic wireless mesh networks. J. Netw. Comput. Appl.74:, 149–164 (2016). https://doi.org/10.1016/j.jnca.2016.05.005.
F. Xhafa, C. Sánchez, L. Barolli, in 2010 24th IEEE International Conference on Advanced Information Networking and Applications. Genetic algorithms for efficient placement of router nodes in wireless mesh networks (IEEEPerth, 2010), pp. 465–472. https://doi.org/10.1109/AINA.2010.41.
C. -C. Lin, P. -T. Tseng, T. -Y. Wu, D. -J. Deng, Social-aware dynamic router node placement in wireless mesh networks. Wirel. Netw.22(4), 1235–1250 (2016). https://doi.org/10.1007/s11276-015-1036-7.
C. -C. Lin, L. Shu, D. -J. Deng, Router node placement with service priority in wireless mesh networks using simulated annealing with momentum terms. IEEE Syst. J.10(4), 1402–1411 (2016). https://doi.org/10.1109/JSYST.2014.2341033.
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.
Y. Bejerano, Efficient integration of multihop wireless and wired networks with qos constraints. IEEE/ACM Trans. Netw.12(6), 1064–1078 (2004). https://doi.org/10.1109/TNET.2004.838599.
B. Aoun, R. Boutaba, Y. Iraqi, G. Kenward, Gateway placement optimization in wireless mesh networks with qos constraints. IEEE J. Sel. Areas Commun.24(11), 2127–2136 (2006). https://doi.org/10.1109/JSAC.2006.881606.
M. Wzorek, C. Berger, P. Doherty, in PRICAI 2019: Trends in Artificial Intelligence, ed. by A. C. Nayak, A. Sharma. Router node placement in wireless mesh networks for emergency rescue scenarios (SpringerCham, 2019), pp. 496–509. https://doi.org/10.1007/978-3-030-29911-8\_38.
N. Hansen, The CMA Evolution Strategy: A Comparing Review (Springer, Berlin, Heidelberg, 2006). https://doi.org/10.1007/3-540-32494-1\_4.
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.
D. B. Johnson, D. A. Maltz, J. Broch, et al, Dsr: The dynamic source routing protocol for multi-hop wireless ad hoc networks. Ad hoc Netw.5(1), 139–172 (2001).
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.
R. Ogier, F. Templin, M. Lewis, RFC3684: Topology Dissemination Based on Reverse-Path Forwarding (TBRPF) (RFC Editor, USA, 2004). https://doi.org/10.17487/RFC3684.
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.
P. Kyasanur, N. H. Vaidya, in IEEE Wireless Communications and Networking Conference, 2005, 4. Routing and interface assignment in multi-channel multi-interface wireless networks (IEEENew Orleans, 2005), pp. 2051–2056. https://doi.org/10.1109/WCNC.2005.1424834.
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.
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.
S. D. Blostein, H. Leib, Multiple antenna systems: their role and impact in future wireless access. IEEE Commun. Mag.41(7), 94–101 (2003). https://doi.org/10.1109/MCOM.2003.1215645.
T. Naeem, J. K. -K. Loo, Common Security Issues and Challenges in Wireless Sensor Networks and IEEE 802-11 Wireless Mesh Networks. J. Dig. Content Technol. Appl.3:, 88–93 (2009). https://doi.org/10.4156/jdcta.vol3.issue1.naeem.
S. Khan, J. L. Mauri, Security for Multihop Wireless Networks (Crc Press, Boca Raton, 2014).
A. -S. K. Pathan, Security of self-organizing networks: MANET, WSN, WMN, VANET (CRC press, Boca Raton, 2016).
T. Maolin, et al, Gateways placement in backbone wireless mesh networks. Int. J. Commun. Netw. Syst. Sci.2(01), 44 (2009). https://doi.org/10.4236/ijcns.2009.21005.
A. A. Franklin, C. S. R. Murthy, in IEEE GLOBECOM 2007-IEEE Global Telecommunications Conference. Node placement algorithm for deployment of twotier wireless mesh networks (IEEEWashington DC, 2007), pp. 4823–4827. https://doi.org/10.1109/GLOCOM.2007.915.
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.
F. Xhafa, A. Barolli, C. Sánchez, L. Barolli, A simulated annealing algorithm for router nodes placement problem in wireless mesh networks. Simul. Model. Pract. Theory. 19(10), 2276–2284 (2011). https://doi.org/10.1016/j.simpat.2010.08.014.
F. Xhafa, A. Barolli, M. Takizawa, et al., in 2011 Third International Conference on Intelligent networking and collaborative systems. A tabu search algorithm for efficient node placement in wireless mesh networks (IEEEFukuoka, 2011), pp. 53–59. https://doi.org/10.1109/INCoS.2011.44.
S. Sakamoto, E. Kulla, T. Oda, M. Ikeda, L. Barolli, F. Xhafa, A comparison study of simulated annealing and genetic algorithm for node placement problem in wireless mesh networks. J. Mob. Multimedia. 9(1&2), 101–110 (2013).
T. Oda, Y. Liu, S. Sakamoto, D. Elmazi, L. Barolli, F. Xhafa Xhafa, Analysis of mesh router placement in wireless mesh networks using friedman test considering different meta-heuristics. Int. J. Commun. Netw. Distrib. Syst.15(1), 84–106 (2015). https://doi.org/10.1504/IJCNDS.2015.070289.
M. Friedman, The use of ranks to avoid the assumption of normality implicit in the analysis of variance. J. Am. Stat. Assoc.32(200), 675–701 (1937). https://doi.org/10.1080/01621459.1937.10503522.
A. Barolli, T. Oda, M. Ikeda, L. Barolli, F. Xhafa, V. Loia, Node placement for wireless mesh networks: Analysis of wmn-ga system simulation results for different parameters and distributions. J. Comput. Syst. Sci.81(8), 1496–1507 (2015). https://doi.org/10.1016/j.jcss.2014.12.024.
B. He, B. Xie, D. P. Agrawal, Optimizing deployment of internet gateway in wireless mesh networks. Comput. Commun.31(7), 1259–1275 (2008). https://doi.org/10.1016/j.comcom.2008.01.061.
M. Seyedzadegan, M. Othman, B. M. Ali, S. Subramaniam, Zero-degree algorithm for internet gateway placement in backbone wireless mesh networks. J. Netw. Comput. Appl.36(6), 1705–1723 (2013). https://doi.org/10.1016/j.jnca.2013.02.031.
J. Wang, B. Xie, K. Cai, D. P. Agrawal, in 2007 IEEE International Conference on Mobile Adhoc and Sensor Systems. Efficient mesh router placement in wireless mesh networks (IEEEPisa, 2007), pp. 1–9. https://doi.org/10.1109/MOBHOC.2007.4428616.
E. Amaldi, A. Capone, M. Cesana, I. Filippini, F. Malucelli, Optimization models and methods for planning wireless mesh networks. Comput. Netw.52(11), 2159–2171 (2008). https://doi.org/10.1016/j.comnet.2008.02.020.
F. J. Solis, R. J. -B. Wets, Minimization by random search techniques. Math. Oper. Res.6(1), 19–30 (1981).
F. Xhafa, C. Sánchez, A. Barolli, M. Takizawa, Solving mesh router nodes placement problem in wireless mesh networks by tabu search algorithm. J. Comput. Syst. Sci.81(8), 1417–1428 (2015). https://doi.org/10.1016/j.jcss.2014.12.018.
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.
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.
Lantmäteriet, Lantmäteriet open geodata (2020). https://lantmateriet.se/en/maps-and-geographic-information/open-geodata/. Accessed Dec 2019.
S. Hert, V. Lumelsky, Polygon area decomposition for multiple-robot workspace division. International Journal of Computational Geometry and Applications. 8:, 437–466 (1998). https://doi.org/10.1142/S0218195998000230.
M. Wzorek, C. Berger, P. Doherty, Polygon Area Decomposition using a Compactness Metric. arXiv preprint arXiv:2110.04043 (2021).
J. E. Schwartzberg, Reapportionment, gerrymanders, and the notion of compactness. Minn. L. Rev.50:, 443 (1965).