Reliable Wireless Sensor Network Planning with Multipath Topology through Relay Placement Optimization

Kasyful Amron, Wuryansari M Kusumawinahyu, Syaiful Anam, Wayan F Mahmudy

Abstract


Recent developments in Wireless Sensor Networks (WSN) focus on scalability and reliability. This research addresses the challenge of improving reliability in WSNs through optimal relay placement and multipath topology design. A heuristic method with a Multi-Objective Optimization (MOO) approach is proposed to solve this problem. The proposed method integrates a modified Genetic Algorithm (GA) with Particle Swarm Optimization (PSO) characteristics. The hybrid approach aims to minimize the number of relays and associated communication costs while maintaining network reliability. The method encodes relay positions and quantities into GA chromosomes that are updated by mutation, crossover, and PSO-inspired particle motion. Simulations are performed in a simplified square area with twenty randomly placed sensors, a hundred and thirty-two arranged relays, and a single sink node. As a result, the simulation generated two multipath topologies that offer unique advantages. The first emphasizes relay efficiency (61 relays, with 2096 costs), while the second ensures lower communication costs (64 relays, 1832 costs). Comparisons with alternative algorithms, including Dijkstra, A-star, GA, and PSO, prove the superiority of the proposed approach. The optimum results obtained with a composition of 95% GA and 5% PSO, outperform alternative algorithms in terms of relay efficiency and communication cost. This research contributes to the field by providing a robust solution for designing reliable multipath WSNs with a minimum number of relays.

Keywords


Wireless Sensor Network; Relay Placement; Multipath Topology; Minimum Relay Number, Minimum Cost; Multi-Objective Optimization; Genetic Algorithms; Particle Swarm Optimization.

Full Text:

PDF

References


L. Phan and T. Kim, "Hybrid time synchronization protocol for large-scale wireless sensor networks," Journal of King Saud University - Computer and Information Sciences, vol. 34, no. 10, pp. 10423-10433, 2022.

Z. Nurlan, T. Zhukabayeva, M. Othman, A. Adamova, and N. Zhakiyev, "Wireless Sensor Network as a Mesh: Vision and Challenges," IEEE Access, vol. 10, pp. 46-67, 2022.

R. I. da Silva, J. D. C. V. Rezende, and M. J. F. Souza, "Collecting large volume data from wireless sensor network by drone," Ad Hoc Networks, vol. 138, p. 103017, 2023.

S. Karimi-Bidhendi, J. Guo, and H. Jafarkhani, "Energy-Efficient Node Deployment in Heterogeneous Two-Tier Wireless Sensor Networks with Limited Communication Range," IEEE Transaction on Wireless Communication, vol. 20, no. 1, pp. 40–55, 2021.

M. Nikolov and Z. J. Haas, "Relay placement in wireless networks: Minimizing communication cost," IEEE Transaction on Wireless Communication, vol. 15, no. 5, pp. 3587–3602, 2016.

S. Veeranami and S. Noor Mohammad, "An Approach to Place Sink Node in Wireless Sensor Network," Wireless Personal Communication, vol. 111, pp. 1117-1127, 2020.

E. H. Houssein, M. R. Saad, K. Hussain, W. Zhu, H. Shaban, and M. Hassaballah, "Optimal Sink Node Placement in Large Scale Wireless Sensor Networks Based on Harris' Hawk Optimization Algorithm," IEEE Access, vol. 8, pp. 19381-19397, 2020.

A. Shukla and S. Tripathi, "A multi-tier-based clustering framework for scalable and energy-efficient WSN-assisted IoT network," Wireless Networks, vol. 26, pp. 3471–3493, 2020.

Z. Wang, H. Xie, D. He, and S. Chan, "Wireless sensor network deployment optimization based on two flower pollination algorithms," IEEE Access, vol. 7, pp. 180590–180608, 2019.

C. A. R. Soares, R. de Souza Couto, A. Sztajnberg, and J. L. M. do Amaral, "POSIMNET-R: An immunologic resilient approach to position routers in Industrial Wireless Sensor Networks," Expert Systems with Applications, vol. 188, p. 116045, 2022.

D. Zhang, H. Wu, P. Zhao, X. Liu, Y. Cui, L. Chen, and T. Zhang, "New approach of multi-path reliable transmission for marginal wireless sensor network," Wireless Networks, vol. 26, no. 2, 2020.

B. A. Attea, M. N. Abbas, M. Al-Ani, and S. Özdemir, "Bio-inspired multi-objective algorithms for connected set K-covers problem in wireless sensor networks," Soft Computing, vol. 23, no. 22, pp. 11699–11728, 2019.

A. Dâmaso, N. Rosa, and P. Maciel, "Reliability of Wireless Sensor Networks," Sensors, vol. 14, no. 9, pp. 15760–15785, 2014.

A. Mouradian and I. Augé-Blum, "On the Reliability of Wireless Sensor Networks Communications," Ad-hoc, Mobile, and Wireless Network, pp. 38-49, 2013.

S. Chakraborty, N. K. Goyal, S. Mahapatra, and S. Soh, "Minimal Path-Based Reliability Model for Wireless Sensor Networks With Multistate Nodes," IEEE Transactions on Reliability, vol. 69, no. 1, pp. 382-400, 2020.

H. M. F. AboElfotoh, E. S. Elmallah, and H. S. Hassanein, "On The Reliability of Wireless Sensor Networks," 2006 IEEE International Conference on Communications, pp. 3455-3460, 2006.

C. Wang, L. Xing, V. M. Vokkarane, and Y. Sun, "Reliability analysis of wireless sensor networks using different network topology characteristics," International Conference on Quality, Reliability, Risk, Maintenance, and Safety Engineering, pp. 12-16, 2012.

S. Chelbi, H. Dhahri, and R. Bouaziz, "Node placement optimization using particle swarm optimization and iterated local search algorithm in wireless sensor networks," International Journal of Communication Systems, vol. 34, no. 9, 2021.

S. Sapre and S. Mini, "Optimized Relay Nodes Positioning to Achieve Full Connectivity in Wireless Sensor Networks," Wireless Personal Communications, vol. 99, pp. 1521–1540, 2018.

J. Xu, K. Li, and G. Min, "Reliable and Energy-Efficient Multipath Communications in Underwater Sensor Networks," IEEE Transactions on Parallel and Distributed Systems, vol. 23, no. 7, pp. 1326-1335, 2012.

P. L. Nguyen, T. H. Nguyen, and K. Nguyen, "A Path-Length Efficient, Low-Overhead, Load-Balanced Routing Protocol for Maximum Network Lifetime in Wireless Sensor Networks with Holes," Sensors, vol. 20, no. 9, p. 2506, 2020.

K. Sha, J. Gehlot, and R. Greve, "Multipath Routing Techniques in Wireless Sensor Networks: A Survey," Wireless Personal Communications, vol. 70, pp. 807–829, 2013.

M. Li, Z. Yin, Y. Ma, C. Wang, A. Chai, and M. Lian, "Design and verification of secure communication scheme for industrial IoT intelligent production line system with multi-path redundancy and collaboration," Neural Computing and Applications, vol. 35, pp 13879–13893, 2023.

C. Ma, W. Liang, M. Zheng, and H. Sharif, "A Connectivity-Aware Approximation Algorithm for Relay Node Placement in Wireless Sensor Networks," IEEE Sensors Journal, vol. 16, no. 2, pp. 515-528, 2016.

B. Alshaqqawi, S. A. Haque, M. Alreshoodi, and I. Alsukayati, "Enhanced Particle Swarm Optimization for Effective Relay Node Deployment in Wireless Sensor Networks," International Journal of Computer Networks and Communication – IJCNC, vol. 13, no.1, 2021.

X. Yang. Optimization techniques and applications with examples. John Wiley and Sons, 2018.

G. Gunjan, "A Review on Multi-objective Optimization in Wireless Sensor Networks Using Nature Inspired Meta-heuristic Algorithms," Neural Processing Letters, vol. 55, pp. 2587–2611, 2023.

P. Parwekar, S. Rodda, and N. Kalla, “A Study of the Optimization Techniques for Wireless Sensor Networks (WSNs),” in Advances in Intelligent Systems and Computing, vol. 672, pp. 909-915, 2018.

H. M. Abdulwahid and A. Mishra, "Deployment Optimization Algorithms in Wireless Sensor Networks for Smart Cities: A Systematic Mapping Study," Sensors, vol. 22, no. 14, 2022.

M. Younis and K. Akkaya, "Strategies and techniques for node placement in wireless sensor networks: A survey," Ad Hoc Networks, vol. 6, no. 4, pp. 621–655, 2008.

S. Mirjalili and J. S. Dong, "Non-dominated Sorting Genetic Algorithm," in Multi-Objective Optimization using Artificial Intelligence Techniques, pp. 37–45, 2020.

M. Sanchez, J. M. Cruz-Duarte, J. C. Ortiz-Bayliss, H. Ceballos, H. Terashima-Marin, and I. Amaya, "A Systematic Review of Hyper-Heuristics on Combinatorial Optimization Problems," IEEE Access, vol. 8, pp. 128068–128095, 2020.

N. Samarji and M. Salamah, "A fault tolerance metaheuristic-based scheme for controller placement problem in wireless software-defined networks," International Journal of Communication Systems, vol. 34, no. 4, 2021.

S. Singh, A. S. Nandan, A. Malik, N. Kumar, and A. Barnawi, "An Energy-Efficient Modified Metaheuristic Inspired Algorithm for Disaster Management System Using WSNs," IEEE Sensors Journal, vol. 21, no. 13, pp. 15398–15408, 2021.

L. Abualigah et al., "Meta-heuristic optimization algorithms for solving real-world mechanical engineering design problems: a comprehensive survey, applications, comparative analysis, and results," Neural Computing and Applications, vol. 34, no. 6, pp. 4081–4110, 2022.

R. Cerulli, C. D'Ambrosio, A Iossa, and F. Palmieri, "Maximum Network Lifetime Problem with Time Slots and Coverage Constraints: heuristic approaches," Journal of Supercomputing, vol. 78, no. 1, 2022.

M. Manju, "A Meta-Heuristic Based Approach with Modified Mutation Operation For Heterogeneous Networks," Wireless Personal Communications, vol. 122, no. 2, 2022.

R. K. Yadav and R. P. Mahapatra, "Hybrid metaheuristic algorithm for optimal cluster head selection in Wireless Sensor Network," Pervasive and Mobile Computing, vol. 79, 2022.

L. Mostarda, A. Navarra, and R. De Leone, "Optimal vs rotation heuristics in the role of cluster-head for routing in IoT constrained devices," Internet of Things, vol. 22, p. 100757, 2023.

A. Srivastava and P. K. Mishra, "A Survey on WSN Issues with its Heuristics and Meta-Heuristics Solutions," Wireless Personal Communications, vol. 121, pp. 745–814, 2021.

Z. Lalama, S. Boulfekhar, and F. Semechedine, "Localization Optimization in WSNs Using Meta-Heuristics Optimization Algorithms: A Survey," Wireless Personal Communications, vol. 122, pp. 1197–1220, 2022.

M. Iqbal, M. Naeem, A. Anpalagan, A. Ahmed, and M. Azam, "Wireless sensor network optimization: Multi-objective paradigm," Sensors, vol. 15, no. 7, pp. 17572–17620, 2015.

Z. Fei, B. Li, S. Yang, C. Xing, H. Chen, and L. Hanzo, "A Survey of Multi-Objective Optimization in Wireless Sensor Networks: Metrics, Algorithms, and Open Problems," IEEE Communications Surveys and Tutorials, vol. 19, no. 1, pp. 550–586, 2017.

S. Zhou, Z. Zhan, Z. Chen, S. Kwong, and J. Zhang, "A Multi-Objective Ant Colony System Algorithm for Airline Crew Rostering Problem With Fairness and Satisfaction," IEEE Transactions on Intelligent Transportation Systems, vol. 22, no. 11, pp. 6784-6798, 2021.

O. Singh, V. Rishiwal, R. Chaudhry, and Y. Mano, "Multi-Objective Optimization in WSN: Opportunities and Challenges," Wireless Personal Communications, vol. 121, pp. 127–152, 2021.

M. Sánchez, J. M. Cruz-Duarte, J. c. Ortíz-Bayliss, H. Ceballos, H. Terashima-Marin, and I. Amaya, "A Systematic Review of Hyper-Heuristics on Combinatorial Optimization Problems," IEEE Access, vol. 8, pp. 128068-128095, 2020.

K. Amron, W. M. Kusumawinahyu, S. Anam, and W. F. Mahmudy, "Relay nodes placement for optimal coverage, connectivity, and communication of wireless sensor networks: A PSO-based multi-objective optimization research idea," 5th International Conference of Sustainable Informatics and Engineering Technology, SIET 2020, pp. 177–182, 2020.

K. Amron, W. M. Kusumawinahyu, S. Anam, and W. F. Mahmudy, "Multi-Tier Topology Design of Wireless Sensor Networks using Multi-Objective Particle Swarm Optimization," 7th International Conference of Sustainable Informatics and Engineering Technology, SIET 2022, pp. 103–110, 2022.

K. Zaimen, M.-E.-A. Brahmia, L. Moalic, A. Abouaissa, and L. Idoumghar, "A Survey of Artificial Intelligence Based WSNs Deployment Techniques and Related Objectives Modeling," IEEE Access, vol. 10, pp. 113294–113329, 2022.

C. Ma, W. Liang, M. Zheng, and B. Yang, "Relay Node Placement in Wireless Sensor Networks with Respect to Delay and Reliability Requirements," IEEE Systems Journal, vol. 13, no. 3, pp. 2570–2581, 2019.

M. Elhoseny, A. Tharwat, A. Farouk, and A. E. Hassanien, "K-Coverage Model Based on Genetic Algorithm to Extend WSN Lifetime," IEEE Sensors Letters, vol. 1, no. 4, pp. 1-4, 2017.

I. Jannoud, Y. Jaradat, M. Z. Masoud, A. Manasrah, and M. Alia, "The Role of Genetic Algorithm Selection Operators in Extending WSN Stability Period: A Comparative Study," Electronics, vol. 11, no. 1, p. 28, 2021.

J. Chen, S. H. Sackey, J. H. Anajemba, X. Zhang, and Y. He, "Energy-Efficient Clustering and Localization Technique Using Genetic Algorithm in Wireless Sensor Networks," Complexity, vol. 2021, pp. 1-12, 2021.

N. S. Abu, W. M. Bukhari, M. H. Adli, and A. Ma'arif, "Optimization of an Autonomous Mobile Robot Path Planning Based on Improved Genetic Algorithms," Journal of Robotics and Control (JRC), vol. 4, no. 4, pp. 557-571, 2023.

M. Zadehbagheri, A. Ma'arif, R. Ildarabadi, M. Ansarifard, and I. Suwarno, "Design of Multivariate PID Controller for Power Networks Using GEA and PSO," Journal of Robotics and Control (JRC), vol. 4, no. 1, 2023.

B. Alnajjar, A. M. Kadim, R. A. Jaber, N. A. Hasan, E. Q. Ahmed, M. S. M. Altaei, and A. L. Khalaf, "Wireless Sensor Network Optimization Using Genetic Algorithm," Journal of Robotics and Control (JRC), vol. 3, no. 6, 2022.

Z. Al-Ani, A. M. Gujarathi, G. R. Vakili-Nezhaad, and A. H. Al-Muhtaseb, "Hybridization Approach Towards Improving the Performance of Evolutionary Algorithm," Arabian Journal for Science and Engineering, vol. 45, pp. 11065–11086, 2020.

A. Maghawry, R. Hodhod, Y. Omar, and M. Kholief, "An Approach to Optimize Multi-objective Problems Using Hybrid Genetic Algorithms Supported by Initial Centroid Selection Optimization Enhanced K-Means Based Selection Operator," in Artificial Intelligence in Intelligent Systems, Computer Science Online Conference – CSOC, vol. 2, pp. 64-87, 2021.

M. Peng, W. Liu, T. Wang, and Z. Zeng, "Relay Selection Joint Consecutive Packet Routing Scheme to Improve Performance for Wake-Up Radio-Enabled WSNs," Wireless Communications and Mobile Computing, vol. 2020, 2020.

M. Sheikh-Hosseini and S. R. Samareh Hashemi, "Connectivity and coverage constrained wireless sensor nodes deployment using steepest descent and genetic algorithms," Expert Systems with Applications, vol. 190, 2022.

D. Zhang and B. Wei, "Comparison between differential evolution and particle swarm optimization algorithms," 2014 IEEE International Conference on Mechatronics and Automation, pp. 239-244, 2014.

T. M. Shami, A. A. El-Saleh, M. Alswaitti, Q. Al-Tashi, M. A. Summakieh, and S. Mirjalili, "Particle Swarm Optimization: A Comprehensive Survey," IEEE Access, vol. 10, pp. 10031-10061, 2022.

H. P. Gupta, P. K. Tyagi, and M. P. Singh, "Regular Node Deployment for k-Coverage in m -Connected Wireless Networks," IEEE Sensors Journal, vol. 15, no. 12, pp. 7126–7134, 2015.

J. Amutha, S. Sharma, and J. Nagar, "WSN Strategies Based on Sensors, Deployment, Sensing Models, Coverage and Energy Efficiency: Review, Approaches, and Open Issues," Wireless Personal Communications, vol. 111, pp. 1089–1115, 2020.

M. A. Benatia, M. Sahnoun, D. Baudry, A. Louis, A. El-Hami, and B. Mazari, "Multi-Objective WSN Deployment Using Genetic Algorithms Under Cost, Coverage, and Connectivity Constraints," Wireless Personal Communications, vol. 94, pp. 2739–2768, 2017.

A. Zrelli and T. Ezzedine, "A New Approach of WSN Deployment, K-Coverage, and Connectivity in Border Area," Wireless Personal Communications, vol. 121, pp. 3365–3381, 2021.

L. Wenxing, W. Muqing, Z. Min, L. Peizhe, and L. Tianze, "Hop count limitation analysis in wireless multi-hop networks," International Journal of Distributed Sensor Networks, vol. 13, no. 1, p. 2017, 2017.

S. Sapre and S. Mini, "Moth flame optimization algorithm based on decomposition for placement of relay nodes in WSNs," Wireless Networks, vol. 26, pp. 1473-1492, 2020.

T. Wang, Y. Li, G. Wang, J. Cao, M. Z. A. Bhuiyan, and W. Jia, "Sustainable and Efficient Data Collection from WSNs to Cloud," IEEE Transactions on Sustainable Computing, vol. 4, no. 2, pp. 252-262, 2019.

A. Seyyedabbasi, F. Kiani, T. Allahviranloo, U. Fernandez-Gamiz, and S. Noeiaghdam, "Optimal data transmission and pathfinding for WSN and decentralized IoT systems using I-GWO and Ex-GWO algorithms," Alexandria Engineering Journal, vol. 63, pp. 339-357, 2023.

A. Hassanat, K. Almohammadi, E. Alkafaween, E. Abunawas, A. Hammouri, and V. B. S. Prasath, "Choosing Mutation and Crossover Ratios for Genetic Algorithms—A Review with a New Dynamic Approach," Information, vol. 10, no. 12, p. 390, 2019.

S. Katoch, S. S. Chauhan, and V. Kumar, "A review on genetic algorithm: past, present, and future," Multimedia Tools and Applications, vol. 80, pp. 8091–8126, 2021.

L. Zhai, Z. Yang, and W. Ji, "Understanding Crowd Intelligence in Large-scale Systems: A Hierarchical Binary Particle Swarm Optimization Approach," Intl. Conference on Parallel & Distributed Processing with Applications, Big Data & Cloud Computing, Sustainable Computing & Communications, Social Computing & Networking (ISPA/BDCloud/SocialCom/SustainCom), pp. 728-735, 2020.

B. H. Nguyen, B. Xue, P. Andreae, and M. Zhang, "A New Binary Particle Swarm Optimization Approach: Momentum and Dynamic Balance between Exploration and Exploitation," IEEE Transactions on Cybernetics, vol. 51, no. 2, pp. 589–603, 2021.

B. Abhishek, S. Ranjit, T. Shankar, G. Eappen, P. Sivasankar, and A. Rajesh, "Hybrid PSO-HSA and PSO-GA algorithm for 3D path planning in autonomous UAVs," SN Applied Science, vol. 2, no. 10, 2020.

M. Abderrahim, H. Hakim, H. Boujemaa, and F. Touati, "Energy-Efficient Transmission Technique based on Dijkstra Algorithm for decreasing energy consumption in WSNs," 19th International Conference on Sciences and Techniques of Automatic Control and Computer Engineering, STA 2019, pp. 599–604, 2019.

I. Diakhate, B. Niang, A. D. Kora, and R. M. Faye, "Optimizing The Energy Consumption of WSN by Using Energy Efficient Routing Protocol Using Dijkstra Algorithm," Proceedings - 2nd International Conference on Electronic and Electrical Engineering and Intelligent System, ICE3IS 2022, pp. 147–152, 2022.

M. Razzaq, G. R. Kwon, and S. Shin, "Energy efficient Dijkstra-based weighted sum minimization routing protocol for WSN," 3rd International Conference on Fog and Mobile Edge Computing, FMEC 2018, pp. 246–251, 2018.

I. S. Alshawi, L. Yan, W. Pan, and B. Luo, "Lifetime enhancement in wireless sensor networks using fuzzy approach and a-star algorithm," IEEE Sensors Journal, vol. 12 no. 10, pp. 3010–3018, 2012.

R. Septiana, I. Soesanti, and N. A. Setiawan, "Evaluation function effectiveness in Wireless Sensor Network routing using A-star algorithm," Proceedings of 4th International Conference on Cyber and IT Service Management, pp. 1-5, 2016.




DOI: https://doi.org/10.18196/jrc.v5i2.19921

Refbacks

  • There are currently no refbacks.


Copyright (c) 2024 Kasyful Amron, Wuryansari Muharini Kusumawinahyu, Syaiful Anam, Wayan Firdaus Mahmudy

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

 

Journal of Robotics and Control (JRC)

P-ISSN: 2715-5056 || E-ISSN: 2715-5072
Organized by Peneliti Teknologi Teknik Indonesia
Published by Universitas Muhammadiyah Yogyakarta in collaboration with Peneliti Teknologi Teknik Indonesia, Indonesia and the Department of Electrical Engineering
Website: http://journal.umy.ac.id/index.php/jrc
Email: jrcofumy@gmail.com

Kuliah Teknik Elektro Terbaik