Skip to main content
main-content
Top

Hint

Swipe to navigate through the articles of this issue

15-09-2022

GA-UCR: Genetic Algorithm Based Unequal Clustering and Routing Protocol for Wireless Sensor Networks

Authors: Gunjan, Ajay K. Sharma, Karan Verma

Published in: Wireless Personal Communications

Login to get access
share
SHARE

Abstract

Wireless Sensor Networks (WSN) is an increasingly growing field, due to its enormous applications. In WSNs, energy conservation is the most important design challenge. In WSNs, unequal clustering can be classified as the best data transmission method that saves energy, where the size of the cluster changes in proportion to the cluster head’s (CH’s) distance from the base station (BS), so as to prevent energy holes/hot-spots from being formed. We have developed GA-UCR in this paper, a “Genetic Algorithm based Unequal Clustering and Routing Protocol for Wireless Sensor Networks”. For CH election, genetic algorithm (GA) has been utilized with three fitness functions- remaining energy of CH nodes, distance between CH and BS/sink, and inter-cluster separation. For inter-cluster multi-hopping, to route the data towards BS, again GA is utilized due to the NP-Hard nature of the problem, with three fitness functions-residual/remaining energy of next hop nodes, CH to next hop node distance and number of hops. Simulation outcomes and analysis show that with reference to energy consumption, network lifetime and scalability, the proposed algorithm exceeds the existing algorithms such as Direct propagation, LEACH, TL-LEACH, GCA, EAERP and GAECH.
Literature
1.
go back to reference Arampatzis, T., Lygeros, J., & Manesis, S. (2005). A survey of applications of wireless sensors and wireless sensor networks. In Intelligent control, 2005. Proceedings of the 2005 IEEE international symposium on, mediterrean conference on control and automation. IEEE. Arampatzis, T., Lygeros, J., & Manesis, S. (2005). A survey of applications of wireless sensors and wireless sensor networks. In Intelligent control, 2005. Proceedings of the 2005 IEEE international symposium on, mediterrean conference on control and automation. IEEE.
2.
go back to reference Al-Karaki, J. N., & Kamal, A. E. (2004). Routing techniques in wireless sensor networks: A survey. IEEE Wireless Communications, 11(6), 6–28. CrossRef Al-Karaki, J. N., & Kamal, A. E. (2004). Routing techniques in wireless sensor networks: A survey. IEEE Wireless Communications, 11(6), 6–28. CrossRef
3.
go back to reference Puccinelli, D., & Haenggi, M. (2005). Wireless sensor networks: Applications and challenges of ubiquitous sensing. IEEE Circuits and Systems Magazine, 5(3), 19–31. CrossRef Puccinelli, D., & Haenggi, M. (2005). Wireless sensor networks: Applications and challenges of ubiquitous sensing. IEEE Circuits and Systems Magazine, 5(3), 19–31. CrossRef
4.
go back to reference Yick, J., Mukherjee, B., & Ghosal, D. (2008). Wireless sensor network survey. Computer Networks, 52(12), 2292–2330. CrossRef Yick, J., Mukherjee, B., & Ghosal, D. (2008). Wireless sensor network survey. Computer Networks, 52(12), 2292–2330. CrossRef
5.
go back to reference Heinzelman, W. B., Chandrakasan, A. P., & Balakrishnan, H. (2002). An application-specific protocol architecture for wireless microsensor networks. IEEE Transactions on Wireless Communications, 1(4), 660–670. CrossRef Heinzelman, W. B., Chandrakasan, A. P., & Balakrishnan, H. (2002). An application-specific protocol architecture for wireless microsensor networks. IEEE Transactions on Wireless Communications, 1(4), 660–670. CrossRef
6.
go back to reference Younis, M., & Akkaya, K. (2008). Strategies and techniques for node placement in wireless sensor networks: A survey. Ad Hoc Networks, 6(4), 621–655. CrossRef Younis, M., & Akkaya, K. (2008). Strategies and techniques for node placement in wireless sensor networks: A survey. Ad Hoc Networks, 6(4), 621–655. CrossRef
7.
go back to reference Heinzelman, W. R., Chandrakasan, A., & Balakrishnan, H. (2000). Energy-efficient communication protocol for wireless microsensor networks. In System sciences, 2000. Proceedings of the 33rd annual Hawaii international conference on. IEEE. Heinzelman, W. R., Chandrakasan, A., & Balakrishnan, H. (2000). Energy-efficient communication protocol for wireless microsensor networks. In System sciences, 2000. Proceedings of the 33rd annual Hawaii international conference on. IEEE.
8.
go back to reference Intanagonwiwat, C., Govindan, R., & Estrin, D. (2000). Directed diffusion: A scalable and robust communication paradigm for sensor networks. In Proceedings of the 6th annual international conference on Mobile computing and networking. ACM. Intanagonwiwat, C., Govindan, R., & Estrin, D. (2000). Directed diffusion: A scalable and robust communication paradigm for sensor networks. In Proceedings of the 6th annual international conference on Mobile computing and networking. ACM.
9.
go back to reference Heinzelman, W. R., Kulik, J., & Balakrishnan, H. Adaptive protocols for information dissemination in wireless sensor networks. In Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking. ACM. Heinzelman, W. R., Kulik, J., & Balakrishnan, H. Adaptive protocols for information dissemination in wireless sensor networks. In Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking. ACM.
10.
go back to reference Lindsey, S., & Raghavendra, C. S. (2002). PEGASIS: Power-efficient gathering in sensor information systems. In Proceedings, IEEE aerospace conference (Vol. 3). IEEE. Lindsey, S., & Raghavendra, C. S. (2002). PEGASIS: Power-efficient gathering in sensor information systems. In Proceedings, IEEE aerospace conference (Vol. 3). IEEE.
11.
go back to reference Kang, S. H., & Nguyen, T. (2012). Distance based thresholds for cluster head selection in wireless sensor networks. IEEE Communications Letters, 16(9), 1396–1399. CrossRef Kang, S. H., & Nguyen, T. (2012). Distance based thresholds for cluster head selection in wireless sensor networks. IEEE Communications Letters, 16(9), 1396–1399. CrossRef
12.
go back to reference Manjeshwar, A., & Agrawal, D. P. (2001). TEEN: A routing protocol for enhanced efficiency in wireless sensor networks. In Null. IEEE. Manjeshwar, A., & Agrawal, D. P. (2001). TEEN: A routing protocol for enhanced efficiency in wireless sensor networks. In Null. IEEE.
13.
go back to reference Khalil, E. A., & Bara’a, A. A. (2011). Energy-aware evolutionary routing protocol for dynamic clustering of wireless sensor networks. Swarm and Evolutionary Computation, 1(4), 195–203. CrossRef Khalil, E. A., & Bara’a, A. A. (2011). Energy-aware evolutionary routing protocol for dynamic clustering of wireless sensor networks. Swarm and Evolutionary Computation, 1(4), 195–203. CrossRef
14.
go back to reference Tripathi, R. K., Singh, Y. N., & Verma, N. K. (2012). N-leach, a balanced cost cluster-heads selection algorithm for wireless sensor network. In Communications (NCC), 2012 national conference on. IEEE. Tripathi, R. K., Singh, Y. N., & Verma, N. K. (2012). N-leach, a balanced cost cluster-heads selection algorithm for wireless sensor network. In Communications (NCC), 2012 national conference on. IEEE.
15.
go back to reference Heinzelman, W. B., Chandrakasan, A. P., & Balakrishnan, H. (2002). An application-specific protocol architecture for wireless microsensor networks. IEEE Transactions on Wireless Communications, 1(4), 660–670. CrossRef Heinzelman, W. B., Chandrakasan, A. P., & Balakrishnan, H. (2002). An application-specific protocol architecture for wireless microsensor networks. IEEE Transactions on Wireless Communications, 1(4), 660–670. CrossRef
16.
go back to reference Loscri, V., Morabito, G., & Marano, S. (2005). A two-levels hierarchy for low-energy adaptive clustering hierarchy (TL-LEACH). In Vehicular technology conference, 2005. VTC-2005-Fall. 2005 IEEE 62nd (Vol. 3). IEEE. Loscri, V., Morabito, G., & Marano, S. (2005). A two-levels hierarchy for low-energy adaptive clustering hierarchy (TL-LEACH). In Vehicular technology conference, 2005. VTC-2005-Fall. 2005 IEEE 62nd (Vol. 3). IEEE.
17.
go back to reference Neto, J. H. B., Rego, A., Cardoso, A. R., & Celestino, J. (2014). MH-LEACH: A distributed algorithm for multi-hop communication in wireless sensor networks. ICN, 2014, 55–61. Neto, J. H. B., Rego, A., Cardoso, A. R., & Celestino, J. (2014). MH-LEACH: A distributed algorithm for multi-hop communication in wireless sensor networks. ICN, 2014, 55–61.
18.
go back to reference Perillo, M., Cheng, Z., & Heinzelman, W. (2005). Strategies for mitigating the sensor network hot spot problem. In Proceedings of MobiQuitous. Perillo, M., Cheng, Z., & Heinzelman, W. (2005). Strategies for mitigating the sensor network hot spot problem. In Proceedings of MobiQuitous.
19.
go back to reference Perillo, M., Cheng, Z., Heinzelman, W. (2004). On the problem of unbalanced load distribution in wireless sensor networks. In IEEE Global Telecommunications Conference Workshops, 2004. GlobeCom Workshops 2004. IEEE. Perillo, M., Cheng, Z., Heinzelman, W. (2004). On the problem of unbalanced load distribution in wireless sensor networks. In IEEE Global Telecommunications Conference Workshops, 2004. GlobeCom Workshops 2004. IEEE.
20.
go back to reference Jaichandran, R., & Irudhayaraj, A. A. (2010). Effective strategies and optimal solutions for hot spot problem in wireless sensor networks (WSN). In 10th international conference on information science, signal processing and their applications (ISSPA 2010). IEEE. Jaichandran, R., & Irudhayaraj, A. A. (2010). Effective strategies and optimal solutions for hot spot problem in wireless sensor networks (WSN). In 10th international conference on information science, signal processing and their applications (ISSPA 2010). IEEE.
21.
go back to reference Younis, O., & Fahmy, S. (2004). HEED: A hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks. IEEE Transactions on Mobile Computing, 3(4), 366–379. CrossRef Younis, O., & Fahmy, S. (2004). HEED: A hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks. IEEE Transactions on Mobile Computing, 3(4), 366–379. CrossRef
22.
go back to reference Yu, J., Qi, Y., Wang, G., Guo, Q., & Gu, X. (2011). An energy-aware distributed unequal clustering protocol for wireless sensor networks. International Journal of Distributed Sensor Networks, 7(1), 202145. CrossRef Yu, J., Qi, Y., Wang, G., Guo, Q., & Gu, X. (2011). An energy-aware distributed unequal clustering protocol for wireless sensor networks. International Journal of Distributed Sensor Networks, 7(1), 202145. CrossRef
23.
go back to reference Gupta, V., & Pandey, R. (2016). An improved energy aware distributed unequal clustering protocol for heterogeneous wireless sensor networks. Engineering Science and Technology, an International Journal, 19(2), 1050–1058. CrossRef Gupta, V., & Pandey, R. (2016). An improved energy aware distributed unequal clustering protocol for heterogeneous wireless sensor networks. Engineering Science and Technology, an International Journal, 19(2), 1050–1058. CrossRef
24.
go back to reference Bagci, H., & Yazici, A. (2013). An energy aware fuzzy approach to unequal clustering in wireless sensor networks. Applied Soft Computing, 13(4), 1741–1749. CrossRef Bagci, H., & Yazici, A. (2013). An energy aware fuzzy approach to unequal clustering in wireless sensor networks. Applied Soft Computing, 13(4), 1741–1749. CrossRef
25.
go back to reference Jiang, C.-J., Shi, W.-R., & Tang, X.-L. (2010). Energy-balanced unequal clustering protocol for wireless sensor networks. The Journal of China Universities of Posts and Telecommunications, 17(4), 94–99. CrossRef Jiang, C.-J., Shi, W.-R., & Tang, X.-L. (2010). Energy-balanced unequal clustering protocol for wireless sensor networks. The Journal of China Universities of Posts and Telecommunications, 17(4), 94–99. CrossRef
26.
go back to reference Abo-Zahhad, M., Ahmed, S. M., Sabor, N., & Sasaki, S. (2014). A new energy-efficient adaptive clustering protocol based on genetic algorithm for improving the lifetime and the stable period of wireless sensor networks. International Journal of Energy, Information and Communications, 5(3), 47–72. CrossRef Abo-Zahhad, M., Ahmed, S. M., Sabor, N., & Sasaki, S. (2014). A new energy-efficient adaptive clustering protocol based on genetic algorithm for improving the lifetime and the stable period of wireless sensor networks. International Journal of Energy, Information and Communications, 5(3), 47–72. CrossRef
27.
go back to reference Soro, S., & Heinzelman, W. B. (2005). Prolonging the lifetime of wireless sensor networks via unequal clustering. In 19th IEEE international parallel and distributed processing symposium. IEEE. Soro, S., & Heinzelman, W. B. (2005). Prolonging the lifetime of wireless sensor networks via unequal clustering. In 19th IEEE international parallel and distributed processing symposium. IEEE.
28.
go back to reference Ye, M., Li, C., Chen, G., & Wu, J. (2005). EECS: An energy efficient clustering scheme in wireless sensor networks. In PCCC 2005. 24th IEEE international performance, computing, and communications conference, 2005. IEEE. Ye, M., Li, C., Chen, G., & Wu, J. (2005). EECS: An energy efficient clustering scheme in wireless sensor networks. In PCCC 2005. 24th IEEE international performance, computing, and communications conference, 2005. IEEE.
29.
go back to reference Li, C., Ye, M., Chen, G., & Wu, J. (2005). An energy-efficient unequal clustering mechanism for wireless sensor networks. In IEEE international conference on mobile adhoc and sensor systems conference. IEEE. Li, C., Ye, M., Chen, G., & Wu, J. (2005). An energy-efficient unequal clustering mechanism for wireless sensor networks. In IEEE international conference on mobile adhoc and sensor systems conference. IEEE.
30.
go back to reference Gong, B., Li, L., Wang, S., & Zhou, X. (2008). Multihop routing protocol with unequal clustering for wireless sensor networks. In 2008 ISECS international colloquium on computing, communication, control, and management (Vol. 2). IEEE. CrossRef Gong, B., Li, L., Wang, S., & Zhou, X. (2008). Multihop routing protocol with unequal clustering for wireless sensor networks. In 2008 ISECS international colloquium on computing, communication, control, and management (Vol. 2). IEEE. CrossRef
31.
go back to reference Baniata, M., & Hong, J. (2017). Energy-efficient unequal chain length clustering for wireless sensor networks in smart cities. Wireless Communications and Mobile Computing, 2017. CrossRef Baniata, M., & Hong, J. (2017). Energy-efficient unequal chain length clustering for wireless sensor networks in smart cities. Wireless Communications and Mobile Computing, 2017. CrossRef
32.
go back to reference Baranidharan, B., & Santhi, B. (2015). GAECH: genetic algorithm based energy efficient clustering hierarchy in wireless sensor networks. Journal of Sensors, 2015. Baranidharan, B., & Santhi, B. (2015). GAECH: genetic algorithm based energy efficient clustering hierarchy in wireless sensor networks. Journal of Sensors, 2015.
33.
go back to reference Gen, M., & Lin, L. (2007). Genetic algorithms. Wiley Encyclopedia of Computer Science and Engineering, 1-15. Gen, M., & Lin, L. (2007). Genetic algorithms. Wiley Encyclopedia of Computer Science and Engineering, 1-15.
34.
go back to reference Gunjan. (2022). A Review on Multi-objective Optimization in Wireless Sensor Networks Using Nature Inspired Meta-heuristic Algorithms. NEURAL PROCESSING LETTERS. CrossRef Gunjan. (2022). A Review on Multi-objective Optimization in Wireless Sensor Networks Using Nature Inspired Meta-heuristic Algorithms. NEURAL PROCESSING LETTERS. CrossRef
35.
go back to reference Liu, J.-L., & Ravishankar, C. V. (2011). LEACH-GA: Genetic algorithm-based energy-efficient adaptive clustering protocol for wireless sensor networks. International Journal of Machine Learning and Computing, 1(1), 79. CrossRef Liu, J.-L., & Ravishankar, C. V. (2011). LEACH-GA: Genetic algorithm-based energy-efficient adaptive clustering protocol for wireless sensor networks. International Journal of Machine Learning and Computing, 1(1), 79. CrossRef
36.
go back to reference Gupta, S. K., & Jana, P. K. (2015). Energy efficient clustering and routing algorithms for wireless sensor networks: GA based approach. Wireless Personal Communications, 83(3), 2403–2423. CrossRef Gupta, S. K., & Jana, P. K. (2015). Energy efficient clustering and routing algorithms for wireless sensor networks: GA based approach. Wireless Personal Communications, 83(3), 2403–2423. CrossRef
37.
go back to reference Wang, T., Zhang, G., Yang, X., & Vajdi, A. (2018). Genetic algorithm for energy-efficient clustering and routing in wireless sensor networks. Journal of Systems and Software, 146, 196–214. CrossRef Wang, T., Zhang, G., Yang, X., & Vajdi, A. (2018). Genetic algorithm for energy-efficient clustering and routing in wireless sensor networks. Journal of Systems and Software, 146, 196–214. CrossRef
38.
go back to reference Mudundi, S., & Ali, H. H. (2007). A new robust genetic algorithm for dynamic cluster formation in wireless sensor networks. In Proceedings of Wireless and Optical Communications, Montreal. Mudundi, S., & Ali, H. H. (2007). A new robust genetic algorithm for dynamic cluster formation in wireless sensor networks. In Proceedings of Wireless and Optical Communications, Montreal.
39.
go back to reference Farooq, M. O., Dogar, A. B., & Shah, G. A. (2010). MR-LEACH: Multi-hop routing with low energy adaptive clustering hierarchy. In 2010 4th international conference on sensor technologies and applications. IEEE. Farooq, M. O., Dogar, A. B., & Shah, G. A. (2010). MR-LEACH: Multi-hop routing with low energy adaptive clustering hierarchy. In 2010 4th international conference on sensor technologies and applications. IEEE.
40.
go back to reference Liu, J.-L., & Ravishankar, C. V. (2011). LEACH-GA: Genetic algorithm-based energy-efficient adaptive clustering protocol for wireless sensor networks. International Journal of Machine Learning and Computing, 1(1), 79. CrossRef Liu, J.-L., & Ravishankar, C. V. (2011). LEACH-GA: Genetic algorithm-based energy-efficient adaptive clustering protocol for wireless sensor networks. International Journal of Machine Learning and Computing, 1(1), 79. CrossRef
41.
go back to reference Bayraklı, S., & Erdogan, S. Z. (2012). Genetic algorithm based energy efficient clusters (GABEEC) in wireless sensor networks. Procedia Computer Science, 10, 247–254. CrossRef Bayraklı, S., & Erdogan, S. Z. (2012). Genetic algorithm based energy efficient clusters (GABEEC) in wireless sensor networks. Procedia Computer Science, 10, 247–254. CrossRef
42.
go back to reference Gajjar, S., Sarkar, M., & Dasgupta, K. (2016). FAMACROW: Fuzzy and ant colony optimization based combined mac, routing, and unequal clustering cross-layer protocol for wireless sensor networks. Applied Soft Computing, 43, 235–247. CrossRef Gajjar, S., Sarkar, M., & Dasgupta, K. (2016). FAMACROW: Fuzzy and ant colony optimization based combined mac, routing, and unequal clustering cross-layer protocol for wireless sensor networks. Applied Soft Computing, 43, 235–247. CrossRef
43.
go back to reference Whitley, D. (1994). A genetic algorithm tutorial. Statistics and Computing, 4(2), 65–85. CrossRef Whitley, D. (1994). A genetic algorithm tutorial. Statistics and Computing, 4(2), 65–85. CrossRef
Metadata
Title
GA-UCR: Genetic Algorithm Based Unequal Clustering and Routing Protocol for Wireless Sensor Networks
Authors
Gunjan
Ajay K. Sharma
Karan Verma
Publication date
15-09-2022
Publisher
Springer US
Published in
Wireless Personal Communications
Print ISSN: 0929-6212
Electronic ISSN: 1572-834X
DOI
https://doi.org/10.1007/s11277-022-09966-7