Reliable Wireless Sensor Network Planning with Multipath Topology through Relay Placement Optimization
DOI:
https://doi.org/10.18196/jrc.v5i2.19921Keywords:
Wireless Sensor Network, Relay Placement, Multipath Topology, Minimum Relay Number, Minimum Cost, Multi-Objective Optimization, Genetic Algorithms, Particle Swarm Optimization.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.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.
Downloads
Additional Files
Published
Issue
Section
License
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 acknowledgment 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 acknowledgment 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 (See The Effect of Open Access).
This journal is based on the work at https://journal.umy.ac.id/index.php/jrc under license from Creative Commons Attribution-ShareAlike 4.0 International License. You are free to:
- Share – copy and redistribute the material in any medium or format.
- Adapt – remix, transform, and build upon the material for any purpose, even comercially.
The licensor cannot revoke these freedoms as long as you follow the license terms, which include the following:
- Attribution. You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
- ShareAlike. If you remix, transform, or build upon the material, you must distribute your contributions under the same license as the original.
- No additional restrictions. You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.
• Creative Commons Attribution-ShareAlike (CC BY-SA)
JRC is licensed under an International License
