Distributed Approach for the Indoor Deployment of Wireless Connected Objects by the Hybridization of the Voronoi Diagram and the Genetic Algorithm
by Wajih Abdallah 1,2,* 
, Sami Mnasri 1,3 and Thierry Val 1
1 UT2J, CNRS-IRIT (RMESS), University of Toulouse, Toulouse, France
2 ISAM Gafsa, Dept. of Design, University of Gafsa, Tunisia
3 University of Tabuk, Community College, Dept. of computer sciences, Tabuk, KSA
* Author to whom correspondence should be addressed.
Journal of Engineering Research and Sciences, Volume 1, Issue 2, Page # 10-23, 2022; DOI: 10.55708/js0102002
Keywords: Coverage, Distributed Deployment, Genetic Algorithm, IoT collection networks, Optimization, Voronoi Diagram
Received: 18 January 2022, Revised: 26 February 2022, Accepted: 27 February 2022, Published Online: 14 March 2022
AMA Style
Abdallah W, Mnasri S, Val T. Distributed approach for the indoor deployment of wireless connected objects by the hybridization of the Voronoi diagram and the genetic algorithm. Journal of Engineering Research and Sciences. 2022;1(2):10-23. doi:10.55708/js0102002
Chicago/Turabian Style
Abdallah, Wajih, Sami Mnasri, and Thierry Val. “Distributed Approach for the Indoor Deployment of Wireless Connected Objects by the Hybridization of the Voronoi Diagram and the Genetic Algorithm.” Journal of Engineering Research and Sciences 1, no. 2 (2022): 10–23. https://doi.org/10.55708/js0102002.
IEEE Style
W. Abdallah, S. Mnasri, and T. Val, “Distributed approach for the indoor deployment of wireless connected objects by the hybridization of the Voronoi diagram and the genetic algorithm,” Journal of Engineering Research and Sciences, vol. 1, no. 2, pp. 10–23, 2022.
331 Downloads
Abstract
Full Text
References
Cited By
Metrics
Abstract
IoT data collection networks have recently become one of the important research areas due to their fundamental role and wide application in many domains. The establishment of networks of objects is based essentially on the deployment of connected objects to process the collected data and transmit them to the various locations. Subsequently, a large number of nodes must be adequately deployed to achieve complete coverage. This manuscript introduces a distributed approach, which combines the Voronoi Diagram and the Genetic algorithm (VD-GA), to maximize the coverage of a region of interest. The Voronoi diagram is used to divide region into cells and generate initial solutions that present the positions of the deployed IoT objects. Then, a genetic algorithm is executed in parallel in several nodes to improve these positions. The developed VD-GA approach was evaluated on an experimental environment by prototyping on a real testbed utilizing M5StickC nodes equipped with ESP32 processor. The experiments show that the distributed approach provided better degree of coverage, RSSI, lifetime and number of neighboring objects than those given by the original algorithms in terms of the suggested distributed Genetic-Voronoi algorithm outperforms the centralized one in terms of speed of computing.
Full Text
References
- P. Asghari, A. M. Rahmani, H. H. S. Javadi, “Internet of Things applications: A systematic review,” Computer Networks, vol. 148, pp. 241–261, 2019, doi:10.1016/j.comnet.2018.12.008.
- D. C. Nguyen et al., “Federated Learning for Internet of Things: A Comprehensive Survey,” IEEE Communications Surveys and Tutorials, vol. 23, no. 3, pp. 1622–1658, 2021, doi:10.1109/COMST.2021.3075439.
- V.A. Laghari et al., “A Review and State of Art of Internet of Things (IoT),” Archives of Computational Methods in Engineering, no. July, 2021, doi:10.1007/s11831-021-09622-6.
- A.H. Puar et al., Communication in internet of things, vol. 672, (Springer Singapore, 2018).
- J. Yick, B. Mukherjee, D. Ghosal, “Wireless sensor network survey,” Computer Networks, vol. 52, no. 12, pp. 2292–2330, 2008, doi:10.1016/j.comnet.2008.04.002.
- P. Rawat et al., “Wireless sensor networks: A survey on recent developments and potential synergies,” Journal of Supercomputing, vol. 68, no. 1, pp. 1–48, 2014, doi:10.1007/s11227-013-1021-9.
- J. Zheng, A. Jamalipour, Wireless Sensor Networks: A Networking Perspective (2008).
- Dulman, Stefan, and Paul JnM Havinga, “Introduction to wireless sensor networks.” Networked Embedded Systems. CRC Press, 2017. 3-1.
- V. Rashid, M. H. Rehmani, “Applications of wireless sensor networks for urban areas: A survey,” Journal of Network and Computer Applications, vol. 60, pp. 192–219, 2016, doi:10.1016/j.jnca.2015.09.008.
- M. Pule, A. Yahya, J. Chuma, “Wireless sensor networks: A survey on monitoring water quality,” Journal of Applied Research and Technology, vol. 15, no. 6, pp. 562–570, 2017, doi:10.1016/j.jart.2017.07.004.
- M.S. Pragadeswaran, M. S. Madhumitha, D. S. Gopinath, “Certain Investigations on Military Applications of Wireless Sensor Networks,” International Journal of Advanced Research in Science, Communication and Technology, vol. 3, no. 1, pp. 14–19, 2021, doi:10.48175/ijarsct-819.
- J. Yang et al., “Integration of wireless sensor networks in environmental monitoring cyber infrastructure,” Wireless Networks, vol. 16, no. 4, pp. 1091–1108, 2010, doi:10.1007/s11276-009-0190-1.
- H. Wang, J. Wang, M. Huang, “Building a smart home system with WSN and service robot,” Proceedings – 2013 5th Conference on Measuring Technology and Mechatronics Automation, ICMTMA 2013, pp. 353–356, 2013, doi:10.1109/ICMTMA.2013.90.
- H. Durani et al., “Smart Automated Home Application using IoT with Blynk App,” Proceedings of the International Conference on Inventive Communication and Computational Technologies, ICICCT 2018, pp. 393–397, 2018, doi:10.1109/ICICCT.2018.8473224.
- Y.J. Chang et al., “Wireless sensor networks for vital signs monitoring: Application in a nursing home,” International Journal of Distributed Sensor Networks, vol. 2012, 2012, doi:10.1155/2012/685107.
- D. Chen et al., “Natural disaster monitoring with wireless sensor networks: A case study of data-intensive applications upon low-cost scalable systems,” Mobile Networks and Applications, vol. 18, no. 5, pp. 651–663, 2013, doi:10.1007/s11036-013-0456-9.
- N. Assad et al., “Efficient deployment quality analysis for intrusion detection in wireless sensor networks,” Wireless Networks, vol. 22, no. 3, pp. 991–1006, 2016, doi:10.1007/s11276-015-1015-z.
- A. Patzer, “Deployment Techniques,” JSP Examples and Best Practices, pp. 215–230, 2002, doi:10.1007/978-1-4302-0831-0_10.
- M. Cardei, D. Z. Du, “Improving wireless sensor network lifetime through power aware organization,” Wireless Networks, vol. 11, no. 3, pp. 333–340, 2005, doi:10.1007/s11276-005-6615-6.
- T.S. Panag, J. S. Dhillon, “Two Stage Grid Classification Based Algorithm for the Identification of Fields Under a Wireless Sensor Network Monitored Area,” Wireless Personal Communications, vol. 95, no. 2, pp. 1055–1074, 2017, doi:10.1007/s11277-016-3813-8.
- Nematy et al., “Ant colony based node deployment and search in wireless sensor networks,” Proceedings – 2010 International Conference on Computational Intelligence and Communication Networks, CICN 2010, pp. 363–366, 2010, doi:10.1109/cicn.2010.138.
- Priyadarshi, B. Gupta, A. Anurag, “Deployment techniques in wireless sensor networks: a survey, classification, challenges, and future research issues”, The Journal of Supercomputing, 1-41 vol. 76, no. 9, (Springer US, 2020).
- Rajpoot, P. Dwivedi, “MADM based optimal nodes deployment for WSN with optimal coverage and connectivity,” IOP Conference Series: Materials Science and Engineering, vol. 1020, no. 1, 2021, doi:10.1088/1757-899X/1020/1/012003.
- Mnasri et al., “Improved Many-Objective Optimization Algorithms for the 3D Indoor Deployment Problem,” Arabian Journal for Science and Engineering, vol. 44, no. 4, pp. 3883–3904, 2019, doi:10.1007/s13369-018-03712-7.
- Holland, J. Adaptation in natural and artificial system. Cambridge, MA: MIT Press,1992.
- Mnasri et al., “3D indoor redeployment in IoT collection networks: A real prototyping using a hybrid PI-NSGA-III-VF,” 2018 14th International Wireless Communications and Mobile Computing Conference, IWCMC 2018, no. July 2019, pp. 780–785, 2018, doi:10.1109/IWCMC.2018.8450372.
- Kennedy, R. Eberhart, “Particle swarm optimization PAPER – IGNORE FROM REFS,” ICNN’95-international conference on neural networks, pp. 1942–1948, 1995.
- Li, J. Cao, “WSN Node Optimal Deployment Algorithm Based on Adaptive Binary Particle Swarm Optimization,” ASP Transactions on Internet of Things, vol. 1, no. 1, pp. 1–8, 2021, doi:10.52810/tiot.2021.100026.
- Karaboga, D. (2005). An idea based on honey bee swarm for numerical optimization. Technical Report-TR06, ErciyesUniversity.
- Dorigo, V. Maniezzo, A. Colorni, “Dorigo-Maniezzo-Colomi_the-Ant-System-Optimization-By-a-Colony-of-Cooperating-Agents,” IEEE Transactions on Systems, Man, and Cybernetics-Part B, vol. 26, no. 1, pp. 1–26, 1999.
- T. Pan, “A new Fruit Fly Optimization Algorithm: Taking the financial distress model as an example,” Knowledge-Based Systems, vol. 26, pp. 69–74, 2012, doi:10.1016/j.knosys.2011.07.001.
- M. Passino, “Biomimicry of Bacterial Foraging for Distributed Optimization and Control,” IEEE Control Systems, vol. 22, no. 3, pp. 52–67, 2002, doi:10.1109/MCS.2002.1004010.
- He, Q. H. Wu, J. R. Saunders, “A novel group search optimizer inspired by animal behavioural ecology,” 2006 IEEE Congress on Evolutionary Computation, CEC 2006, no. March, pp. 1272–1278, 2006, doi:10.1109/cec.2006.1688455.
- El-Abd, “An improved global-best harmony search algorithm,” Applied Mathematics and Computation, vol. 222, pp. 94–106, 2013, doi:10.1016/j.amc.2013.07.020.
- Kaveh, S. Talatahari, “A novel heuristic optimization method: Charged system search,” Acta Mechanica, vol. 213, no. 3–4, pp. 267–289, 2010, doi:10.1007/s00707-009-0270-4.
- Rabanal, P., Rodrı´guez, I., & Rubio, F. Using river formation dynamics to design heuristic algorithms. Lecture Notes in Computer Science, 4618, 163–177,2007.
- Abdallah, S. Mnasri, T. Val, “Genetic-Voronoi algorithm for coverage of IoT data collection networks,” 30th International Conference on Computer Theory and Applications, ICCTA 2020 – Proceedings, no. December, pp. 16–22, 2020, doi:10.1109/ICCTA52020.2020.9477675.
- Pietrabissa, F. Liberati, G. Oddi, “A distributed algorithm for Ad-hoc network partitioning based on Voronoi Tessellation,” Ad Hoc Networks, vol. 46, pp. 37–47, 2016, doi:10.1016/j.adhoc.2016.03.008.
- Banimelhem, M. Mowafi, W. Aljoby, “Genetic Algorithm Based Node Deployment in Hybrid Wireless Sensor Networks,” Communications and Network, vol. 05, no. 04, pp. 273–279, 2013, doi:10.4236/cn.2013.54034.
- Eledlebi et al., “Autonomous deployment of mobile sensors network in an unknown indoor environment with obstacles,” GECCO 2018 Companion – Proceedings of the 2018 Genetic and Evolutionary Computation Conference Companion, no. July, pp. 280–281, 2018, doi:10.1145/3205651.3205725.
- Eledlebi et al., “Voronoi-based indoor deployment of mobile sensors network with obstacles,” Proceedings – 2018 IEEE 3rd International Workshops on Foundations and Applications of Self* Systems, FAS*W 2018, pp. 20–21, 2019, doi:10.1109/FAS-W.2018.00019.
- Jianmin zou et al., “Bio-inspired and Voronoi-based Algorithms for Self-positioning of Autonomous Vehicles in Noisy Environments,” 2015, doi:10.4108/icst.bict.2014.257917.
- Eledlebi et al., “A hybrid voronoi tessellation/genetic algorithm approach for the deployment of drone-based nodes of a self-organizing wireless sensor network (Wsn) in unknown and gps denied environments,” Drones, vol. 4, no. 3, pp. 1–30, 2020, doi:10.3390/drones4030033.
- Tahir, N.H.M.; Atan, F. A Modified Genetic Algorithm Method for Maximum Coverage in Dynamic Mobile Wireless Sensor Networks. J. Basic Appl. Sci. Res. 2016, 6, 26–32.
- Li, Y.; Dong, T.; Bikdash, M.; Song, Y.D. Path Planning for Unmanned Vehicles Using Ant Colony Optimization on a Dynamic Voronoi Diagra. In Proceedings of the 2005 International Conference on Artificial Intelligence, ICAI 2005, Las Vegas, NV, USA, 27–30 June 2005; pp. 716–721.
- A. B. Ab Aziz, A. W. Mohemmed, M. Y. Alias, “A wireless sensor network coverage optimization algorithm based on particle swarm optimization and voronoi diagram,” Proceedings of the 2009 IEEE International Conference on Networking, Sensing and Control, ICNSC 2009, pp. 602–607, 2009, doi:10.1109/ICNSC.2009.4919346.
- Qu, S. V. Georgakopoulos, “A centralized algorithm for prolonging the lifetime of wireless sensor networks using Particle Swarm Optimization,” 2012 IEEE 13th Annual Wireless and Microwave Technology Conference, WAMICON 2012, 2012, doi:10.1109/WAMICON.2012.6208432. 3221–3232.
- Rahmani et al., “Node placement for maximum coverage based on voronoi diagram using genetic algorithm in wireless sensor networks,” Australian Journal of Basic and Applied Sciences, vol. 5, no. 12, pp. 3221–3232, 2011.
- M. Pardalos et al., “Parallel search for combinatorial optimization: Genetic algorithms, simulated annealing, tabu search and GRASP,” Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 980, pp. 318–331, 1995, doi:10.1007/3-540-60321-2_26.
- E. Goldberg, “Sizing populations for serial and parallel genetic algorithms,” in Proceedings of the Third International Conference on Genetic Algorithms, pp. 70-79, San Mateo, CA, 1989.
- Erick Cantú-Paz. A survey of parallel genetic algorithms. CalculateursParalleles, reseaux et systems repartis, 10:30, 1998.
- Di Martino et al., “Towards migrating genetic algorithms for test data generation to the cloud,” Software Testing in the Cloud: Perspectives on an Emerging Discipline, pp. 113–135, 2012, doi:10.4018/978-1-4666-2536-5.ch006.
- Di Geronimo et al., “A parallel genetic algorithm based on hadoop MapReduce for the automatic generation of junit test suites,” Proceedings – IEEE 5th International Conference on Software Testing, Verification and Validation, ICST 2012, pp. 785–793, 2012, doi:10.1109/ICST.2012.177.
- Herrera, M. Lozano, “Gradual distributed real-coded genetic algorithms,” IEEE Transactions on Evolutionary Computation, vol. 4, no. 1, pp. 43–62, 2000, doi:10.1109/4235.843494.
- Yu, W. Zhang, “Study on function optimization based on master-slave structure genetic algorithm,” International Conference on Signal Processing Proceedings, ICSP, vol. 3, pp. 0–3, 2006, doi:10.1109/ICOSP.2006.345926.
- J. Gong et al., “Distributed evolutionary algorithms and their models: A survey of the state-of-the-art,” Applied Soft Computing Journal, vol. 34, pp. 286–300, 2015, doi:10.1016/j.asoc.2015.04.061.
- Muttillo et al., “An OpenMP Parallel Genetic Algorithm for Design Space Exploration of Heterogeneous Multi-processor Embedded Systems,” ACM International Conference Proceeding Series, no. April, 2020, doi:10.1145/3381427.3381431.
- Available: https://www.espressif.com/en/products/ software/ esp-now/overview
- (2020). Accessed: July 28, 2020. Available: https://m5stack.com/products/stick-c
- Mnasri et al., “The 3D redeployment of nodes in Wireless Sensor Networks with real testbed prototyping”, In : International Conference on Ad-Hoc Networks and Wireless, Cham, 2017. p. 18-24.. Springer, doi.org/10.1007/978-3-319-67910-5_2
Cited By
Metrics
