Genetic Algorithm based Routing in Wireless Sensor Networks with Various Distance Metrics
DOI:
https://doi.org/10.47839/ijc.23.4.3774Keywords:
routing, genetic algorithm, wireless sensor network, greedy algorithm, Euclidean metric, Chebyshev metric, Manhattan metric, Minkowski metricAbstract
The study highlights the operational characteristics of wireless sensor networks (WSNs). It describes genetic operators and parameters that serve as the foundation for the genetic algorithm's functionality. The optimal values for population size and the number of generations required for data routing in WSNs were determined. The mathematical framework and application aspects of distance metrics such as Euclidean, Chebyshev, Manhattan, and Minkowski were analyzed. A block diagram of the proposed genetic algorithm for data transmission between sensor nodes is presented. The effectiveness of the developed genetic algorithm was investigated for route formation using different distance metrics in a network with nodes characterized by three operational radii. Experimental results indicate that, for finding the shortest route with minimal computational time in a network of 25 sensor nodes, the optimal genetic algorithm parameters are 150 generations and a population size of 300. Simulation results demonstrate the superiority of the proposed solution over the greedy algorithm in terms of route length.
References
Z. Nurlan, T. Zhukabayeva, M. Othman, A. Adamova, N. Zhakiyev, “Wireless sensor network as a mesh: Vision and challenges,” IEEE Access, vol. 10, pp. 46-67, 2022, https://doi.org/10.1109/ACCESS.2021.3137341.
M. A. Jamshed, K. Ali, Q. H. Abbasi, M. A. Imran, M. Ur-Rehman, “Challenges, applications, and future of wireless sensors in Internet of Things: A review,” IEEE Sensors Journal, vol. 22, no. 6, pp. 5482-5494, 2022, https://doi.org/10.1109/JSEN.2022.3148128.
O. Duda et al., “Data Processing in IoT for Smart City Systems,” Proceedings of the 2019 10th IEEE International Conference on Intelligent Data Acquisition and Advanced Computing Systems: Technology and Applications (IDAACS), Metz, France, 2019, pp. 96-99, https://doi.org/10.1109/IDAACS.2019.8924262.
M. Klymash, O. Lavriv, T. Maksymyuk and M. Beshley, “State of the art and further development of information and communication systems,” Proceedings of the 2016 International Conference Radio Electronics & Info Communications (UkrMiCo), Kiev, Ukraine, 2016, pp. 1-6, https://doi.org/10.1109/UkrMiCo.2016.7739637.
Y. Sun et al., “UAV and IoT-based systems for the monitoring of industrial facilities using digital twins: Methodology, reliability models, and application,” Sensors, vol. 22, no. 17, p. 6444, 2022, https://doi.org/10.3390/s22176444.
V. Inzillo, F. De Rango, and A. Ariza Quintana, “A low energy consumption smart antenna adaptive array system for mobile ad hoc networks,” International Journal of Computing, vol. 16, no. 3, pp. 124–132, 2017, https://doi.org/10.47839/ijc.16.3.895.
D. D. Sokolov, et al., “Environmental monitoring with wireless sensor networks application: Development and experiments,” Radioelectronic and Computer Systems, vol. 3, pp. 40-47, 2019. https://doi.org/10.32620/reks.2019.3.04.
N. Ocheretnyuk, I. Voytyuk, M. Dyvak, and Y. Martsenyuk, “Features of structure identification the macromodels for nonstationary fields of air pollutions from vehicles,” Proceedings of the International Conference on Modern Problem of Radio Engineering, Telecommunications and Computer Science, Lviv, Ukraine, 2012, pp. 444–444. https://ieeexplore.ieee.org/document/6192692.
B. Rusyn, O. Lutsyk, R. Kosarevych, and J. Varetsky, “Automated recognition of numeric display based on deep learning,” Proceedings of the IEEE 3rd International Conference on Advanced Information and Communications Technologies (AICT), 2019, pp. 244–247. https://doi.org/10.1109/AIACT.2019.8847868.
B. E. Kapustiy, B. P. Rusyn, and V. A. Tayanov, “Peculiarities of application of statistical detection criteria for problem of pattern recognition,” Journal of Automation and Information Science, vol. 37, no. 2, pp. 30–36, 2005.
M. Dyvak, I. Voytyuk, N. Porplytsya and A. Pukas, “Modeling the process of air pollution by harmful emissions from vehicles,” Proceedings of the 2018 14th International Conference on Advanced Trends in Radioelecrtronics, Telecommunications and Computer Engineering (TCSET), Lviv-Slavske, Ukraine, 2018, pp. 1272-1276, https://doi.org/10.1109/TCSET.2018.8336426.
D. Zhao, H. Yang and Q. Ren, “Distance metric,” Proceedings of the 34th Conference on Neural Information Processing Systems (NeurIPS 2020), Vancouver, Canada, 2020.
X. Xu and G. Li, “Chebyshev metric based multi-objective Monte Carlo tree search for combat simulations,” Proceedings of the 2017 21st International Conference on System Theory, Control and Computing (ICSTCC), Sinaia, Romania, 2017, pp. 607-612, https://doi.org/10.1109/ICSTCC.2017.8107102.
U. C. Altın, N. At and C. Topal, “Effect of distance metrics on positioning accuracy,” Proceedings of the 2018 26th Signal Processing and Communications Applications Conference (SIU), Izmir, Turkey, 2018, pp. 1-4, https://doi.org/10.1109/SIU.2018.8404795.
A. Sachenko, V. Kochan, V. Turchenko, V. Tymchyshyn and N. Vasylkiv, “Intelligent nodes for distributed sensor network,” IMTC/99. Proceedings of the 16th IEEE Instrumentation and Measurement Technology Conference (Cat. No.99CH36309), Venice, Italy, 1999, pp. 1479-1484 vol. 3, https://doi.org/10.1109/IMTC.1999.776072.
V. Yatskiv, N. Yatskiv, Su Jun, A. Sachenko and Hu Zhengbing, “The use of modified correction code based on residue number system in WSN,” Proceedings of the 2013 IEEE 7th International Conference on Intelligent Data Acquisition and Advanced Computing Systems (IDAACS), Berlin, 2013, pp. 513-516, https://doi.org/10.1109/IDAACS.2013.6662738.
P. Bykovyy, V. Kochan, A. Sachenko and G. Markowsky, “Genetic Algorithm Implementation for Perimeter Security Systems CAD,” Proceedings of the 2007 4th IEEE Workshop on Intelligent Data Acquisition and Advanced Computing Systems: Technology and Applications, Dortmund, Germany, 2007, pp. 634-638, https://doi.org/10.1109/IDAACS.2007.4488498.
L. Venkatesan and P. Sivakumar, “Enhancement of coarse-grained parallel genetic algorithm for shortest path routing,” Proceedings of the 2013 Fourth International Conference on Computing, Communications and Networking Technologies (ICCCNT), Tiruchengode, India, 2013, pp. 1-6, https://doi.org/10.1109/ICCCNT.2013.6726511.
J. Mishra, J. Bagga, S. Choubey and I. K. Gupta, “Energy optimized routing for wireless sensor network using elitist genetic algorithm,” Proceedings of the 2017 8th International Conference on Computing, Communication and Networking Technologies (ICCCNT), Delhi, India, 2017, pp. 1-5, https://doi.org/10.1109/ICCCNT.2017.8204110.
M. Rares, “Adaptive mutation in genetic algorithms for shortest path routing problem,” Proceedings of the 2015 7th International Conference on Electronics, Computers and Artificial Intelligence (ECAI), Bucharest, Romania, 2015, pp. 69-74, https://doi.org/10.1109/ECAI.2015.7301163.
G. Chen and H. -X. Hu, “Finding the optimal network topology for the distributed multi-short-paths routing algorithm – A genetic algorithm-based approach,” Proceedings of the 2022 International Conference on Intelligent Systems and Computational Intelligence (ICISCI), Changsha, China, 2022, pp. 35-38, https://doi.org/10.1109/ICISCI53188.2022.9941373.
S. Biswas, S. Biswas, S. Zafar and M. A. Ahad, “Genetic algorithm based optimized routing methodology through big data analytics in MANET,” Proceedings of the 2019 International Conference on Computing, Power and Communication Technologies (GUCON), New Delhi, India, 2019, pp. 645-649.
K. N. Premnath and S. Rajavelu, “Challenges in self organizing networks for wireless telecommunications,” Proceedings of the 2011 International Conference on Recent Trends in Information Technology (ICRTIT), Chennai, India, 2011, pp. 1331-1334, https://doi.org/10.1109/ICRTIT.2011.5972332.
Y. Pyrih, M. Kaidan, I. Tchaikovskyi and M. Pleskanka, “Research of genetic algorithms for increasing the efficiency of data routing,” Proceedings of the 2019 3rd International Conference on Advanced Information and Communications Technologies (AICT), Lviv, Ukraine, 2019, pp. 157-160, https://doi.org/10.1109/AIACT.2019.8847814.
A. More and V. Raisinghani, “A survey on energy efficient coverage protocols in wireless sensor networks,” Journal of King Saud University - Computer and Information Sciences, vol. 29, issue 4, pp. 428-448, 2017, https://doi.org/10.1016/j.jksuci.2016.08.001.
A. Agnihotri and I. K. Gupta, “A hybrid PSO-GA algorithm for routing in wireless sensor network,” Proceedings of the 2018 4th International Conference on Recent Advances in Information Technology (RAIT), Dhanbad, India, 2018, pp. 1-6, https://doi.org/10.1109/RAIT.2018.8389082.
N. Muruganantham and H. El-Ocla, “Routing using genetic algorithm in a wireless sensor network,” Wireless Personal Communications, vol. 111, pp. 2703–2732, 2020, https://doi.org/10.1007/s11277-019-07011-8.
R. Hamidouche, Z. Aliouat, and A. M. Gueroui, “Genetic algorithm for improving the lifetime and QoS of wireless sensor networks,” Wireless Personal Communications, vol. 101, pp. 2313–2348, 2018, https://doi.org/10.1007/s11277-018-5817-z.
S. Gunjan, and A. K. Verma, “GA-UCR: Genetic algorithm based unequal clustering and routing protocol for wireless sensor networks,” Wireless Personal Communications, vol. 128, pp. 537–558, 2023, https://doi.org/10.1007/s11277-022-09966-7.
G. Jin and W. Muqing, “Genetic-based cluster routing algorithm for wireless sensor networks,” Proceedings of the 2021 7th International Conference on Computer and Communications (ICCC), Chengdu, China, 2021, pp. 48-52, https://doi.org/10.1109/ICCC54389.2021.9674406.
T. Bhatia, S. Kansal, S. Goel, and A. K. Verma, “A genetic algorithm based distance-aware routing protocol for wireless sensor networks,” Computers & Electrical Engineering, vol. 56, pp. 441–455, 2016, https://doi.org/10.1016/j.compeleceng.2016.09.016.
R. Lal and K. Sharma, “GAEER: Genetic algorithm based energy efficient routing protocol in wireless sensor network,” International Journal of Scientific & Technology Research, vol. 9, pp. 538–544, 2020.
Y. Pyrih, M. Klymash, M. Kaidan and B. Strykhalvuk, “Investigating the efficiency of tournament selection operator in genetic algorithm for solving TSP,” Proceedings of the 2023 IEEE 5th International Conference on Advanced Information and Communication Technologies (AICT), Lviv, Ukraine, 2023, pp. 170-173, https://doi.org/10.1109/AICT61584.2023.10452423.
R. N. Shukla, A. S. Chandel, S. K. Gupta, J. Jain and A. Bhansali, “GAE3BR: Genetic algorithm based energy efficient and energy balanced routing algorithm for Wireless Sensor Networks,” Proceedings of the 2015 International Conference on Advances in Computing, Communications and Informatics (ICACCI), Kochi, India, 2015, pp. 942-947, https://doi.org/10.1109/ICACCI.2015.7275732.
O. Zorlu, S. Dilek and A. Özsoy, “GPU-based parallel genetic algorithm for increasing the coverage of WSNs,” Proceedings of the 2017 IEEE 23rd International Conference on Parallel and Distributed Systems (ICPADS), Shenzhen, China, 2017, pp. 640-647, https://doi.org/10.1109/ICPADS.2017.00088.
K. Almakadmeh and W. Alma'aitah, “Comparison of crossover types to build improved queries using adaptive genetic algorithm,” Proceedings of the 2017 International Conference on New Trends in Computing Sciences (ICTCS), Amman, Jordan, 2017, pp. 1-5, https://doi.org/10.1109/ICTCS.2017.18.
H. Crosby, T. Damoulas, T., S.A. Jarvis, “Embedding road networks and travel time into distance metrics for urban modelling,” International Journal of Geographical Information Science, vol. 33, issue 3, pp. 512–536, 2018, https://doi.org/10.1080/13658816.2018.1547386.
X. Chen, “A comparison of greedy algorithm and dynamic programming algorithm,” Proceedings of the 2022 International Conference on Science and Technology Ethics and Human Future (STEHF 2022), SHS Web Conf. 144 03009, 2022, https://doi.org/10.1051/shsconf/202214403009.
S.A. Curtis, “The classification of greedy algorithms,” Science of Computer Programming, vol. 49, issues 1–3, pp. 125-157, 2003. https://doi.org/10.1016/j.scico.2003.09.001.
Downloads
Published
How to Cite
Issue
Section
License
International Journal of Computing is an open access journal. Authors who publish with this journal agree to the following terms:• Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
• Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
• Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
