An Improved Optimal-K and K-Means clustering-based Routing Protocol for Wireless Sensor Networks

Samah Alnajdi, Fuad Bajaber


In recent years, wireless sensor network (WSN) applications have become widely used in various domains, such as in the military, disaster management, industrial and environmental monitoring, and healthcare. However, the networks have many challenges. One of the main challenges is that the sensor nodes are critically constrained for resources and usually have un-rechargeable batteries, which directly impacts the network’s performance and makes routing a critical issue. Therefore, many hierarchical routing protocols have been proposed to address the issue and establish efficient energy consumption based on different types of clustering algorithms. In this paper, we proposed an efficient hierarchical routing protocol based on chain-based clustering along with an improved existing method that includes an optimal-K model for the dynamic selection of the number of formed chains and k-means clustering. The simulation performed on MATLAB and the proposed protocol showed improvements in comparison with other existing protocols in terms of the network’s lifetime, the data transmission delay, and the control overhead.


chain-based clustering; energy consumption; hierarchical routing; k-means; network lifetime; optimal K; overhead; routing protocols; WSN;


A. R. Bhawna Sharma, “Energy Efficiency in Distributed Clustering of WSN using HEED Protocol,” International Journal of Engineering Research & Technology (IJERT), vol. 5, no. 06, Jun. 2016.

S. K. Singh, M. . Singh, and D. K. Singh, “Routing Protocols in Wireless Sensor Networks - A Survey,” International Journal of Computer Science & Engineering Survey, vol. 1, no. 2, pp. 63–83, Nov. 2010.

S. Lindsey and C. S. Raghavendra, “PEGASIS: Power-efficient gathering in sensor information systems,” in Proceedings, IEEE Aerospace Conference, 2002, vol. 3, pp. 3-1125-3–1130 vol.3.

Y. Yu and Y. Song, “An Energy-Efficient Chain-Based routing protocol in Wireless Sensor Network,” in 2010 International Conference on Computer Application and System Modeling (ICCASM 2010), 2010, vol. 11, pp. V11-486-V11-489.

S. Feng, B. Qi, and L. Tang, “An improved Energy-Efficient PEGASIS-Based protocol in Wireless Sensor Networks,” in 2011 Eighth International Conference on Fuzzy Systems and Knowledge Discovery (FSKD), 2011, vol. 4, pp. 2230–2233.

N. D. Tan and N. D. Viet, “SCBC: Sector-chain based clustering routing protocol for energy efficiency in heterogeneous wireless sensor network,” in 2015 International Conference on Advanced Technologies for Communications (ATC), 2015, pp. 314–319.

M. Dorigo and M. Birattari, “Ant Colony Optimization,” in Encyclopedia of Machine Learning, Springer, Boston, MA, 2011, pp. 36–39.

S. Ghosh, S. Mondal, and U. Biswas, “Enhanced PEGASIS using ant colony optimization for data gathering in WSN,” in 2016 International Conference on Information Communication and Embedded Systems (ICICES), 2016, pp. 1–6.

M. Gupta and L. Saraswat, “Energy aware data collection in wireless sensor network using chain based PEGASIS,” in International Conference on Recent Advances and Innovations in Engineering (ICRAIE-2014), 2014, pp. 1–5.

S. M. Jung, Y. J. Han, and T. M. Chung, “The Concentric Clustering Scheme for Efficient Energy Consumption in the PEGASIS,” in The 9th International Conference on Advanced Communication Technology, 2007, vol. 1, pp. 260–265.

K. H. Chen, J. M. Huang, and C. C. Hsiao, “CHIRON: An energy-efficient chain-based hierarchical routing protocol in wireless sensor networks,” in 2009 Wireless Telecommunications Symposium, 2009, pp. 1–5.

S. Mao and Y. T. Hou, “BeamStar: An Edge-Based Approach to Routing in Wireless Sensor Networks,” IEEE Transactions on Mobile Computing, vol. 6, no. 11, pp. 1284–1296, Nov. 2007.

M. F. Shekh, A. Kumar, and G. Sharma, “Improved energy-efficient chain-based routing protocol for edge-based wireless sensor networks,” in 2016 International Conference on Communication and Signal Processing (ICCSP), 2016, pp. 2225–2231.

M. Hadjila, H. Guyennet, and M. Feham, “A Chain-Based Routing Protocol to Maximize the Lifetime of Wireless Sensor Networks,” vol. 2013, May 2013.

T. M. Jawad and N. A. Ali, “Using K-means clustering algorithm with Power Efficient Gathering in Sensor Information Systems Protocol,” IJCSET, vol. 6, no. 1, p. 5, 2016.

W. B. Heinzelman, A. P. Chandrakasan, and H. Balakrishnan, “An application-specific protocol architecture for wireless microsensor networks,” IEEE Transactions on Wireless Communications, vol. 1, no. 4, pp. 660–670, Oct. 2002.

N. Amini, A. Vahdatpour, W. Xu, M. Gerla, and M. Sarrafzadeh, “Cluster Size Optimization in Sensor Networks with Decentralized Cluster-Based Protocols,” Comput Commun, vol. 35, no. 2, pp. 207–220, Jan. 2012.

V. Kumar, S. B. Dhok, R. Tripathi, and S. Tiwari, “A Review Study on Analytical Estimation of Optimal Number of Clusters in Wireless Sensor Networks,” Transactions on Networks and Communications, vol. 2, no. 5, pp. 75–103, Nov. 2014.

Total views : 13 times


  • There are currently no refbacks.

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

shopify stats IJEECS visitor statistics