Constrained K-means and Genetic Algorithm-based Approaches for Optimal Placement of Wireless Structural Health Monitoring Sensors

Shih-Lin Hung, Ching-Yun Kao, Jyun-Wei Huang


Optimal placement of wireless structural health monitoring (SHM) sensors has to consider modal identification accuracy and power efficiency. In this study, two-tier wireless sensor network (WSN)-based SHM systems with clusters of sensors are investigated to overcome this difficulty. Each cluster contains a number of sensor nodes and a cluster head (CH). The lower tier is composed of sensors communicating with their associated CHs, and the upper tier is composed of the network of CHs. The first step is the optimal placement of sensors in the lower tier via the effective independence method by considering the modal identification accuracy. The second step is the optimal placement of CHs in the upper tier by considering power efficiency. The sensors in the lower tier are partitioned into clusters before determining the optimal locations of CHs in the upper tier. Two approaches, a constrained K-means clustering approach and a genetic algorithm (GA)-based clustering approach, are proposed in this study to cluster sensors in the lower tier by considering two constraints: (1) the maximum data transmission distance of each sensor; (2) the maximum number of sensors in each cluster. Given that each CH can only manage a limited number of sensors, these constraints should be considered in practice to avoid overload of CHs. The CHs in the upper tier are located at the centers of the clusters determined after clustering sensors in the lower tier. The two proposed approaches aim to construct a balanced size of clusters by minimizing the number of clusters (or CHs) and the total sum of the squared distance between each sensor and its associated CH under the two constraints. Accordingly, the energy consumption in each cluster is decreased and balanced, and the network lifetime is extended. A numerical example is studied to demonstrate the feasibility of using the two proposed clustering approaches for sensor clustering in WSN-based SHM systems. In this example, the performances of the two proposed clustering approaches and the K-means clustering method are also compared. The two proposed clustering approaches outperform the K-means clustering method in terms of constructing balanced size of clusters for a small number of clusters.


Doi: 10.28991/CEJ-2022-08-12-01

Full Text: PDF


Structural Health Monitoring; Wireless Sensing Network; K-Means Clustering Method; Effective Independence Method.


Cha, Y. J., Agrawal, A. K., Kim, Y., & Raich, A. M. (2012). Multi-objective genetic algorithms for cost-effective distributions of actuators and sensors in large structures. Expert Systems with Applications, 39(9), 7822–7833. doi:10.1016/j.eswa.2012.01.070.

Kammer, D. C. (1990). Sensor Placement for On-Orbit Modal Identification and Correlation of Large Space Structures. 1990 American Control Conference. doi:10.23919/acc.1990.4791265.

Spencer, B. F., Ruiz-Sandoval, M. E., & Kurata, N. (2004). Smart sensing technology: Opportunities and challenges. Structural Control and Health Monitoring, 11(4), 349–368. doi:10.1002/stc.48.

Lynch, J. P. (2006). A Summary Review of Wireless Sensors and Sensor Networks for Structural Health Monitoring. The Shock and Vibration Digest, 38(2), 91–128. doi:10.1177/0583102406061499.

Lin, T. H., Lu, Y. C., & Hung, S. L. (2014). Locating damage using integrated global-local approach with wireless sensing system and single-chip impedance measurement device. The Scientific World Journal, 2014, 729027. doi:10.1155/2014/729027.

Kottapalli, V. A., Kiremidjian, A. S., Lynch, J. P., Carryer, E., Kenny, T. W., Law, K. H., & Lei, Y. (2003). Two-tiered wireless sensor network architecture for structural health monitoring. Smart Structures and Materials 2003: Smart Systems and Nondestructive Evaluation for Civil Infrastructures. doi:10.1117/12.482717.

Zhou, G.-D., Yi, T.-H., Xie, M.-X., Li, H.-N., & Xu, J.-H. (2021). Optimal Wireless Sensor Placement in Structural Health Monitoring Emphasizing Information Effectiveness and Network Performance. Journal of Aerospace Engineering, 34(2), 4020112. doi:10.1061/(asce)as.1943-5525.0001226.

Abdulkarem, M., Samsudin, K., Rokhani, F. Z., & A Rasid, M. F. (2020). Wireless sensor network for structural health monitoring: A contemporary review of technologies, challenges, and future direction. Structural Health Monitoring, 19(3), 693–735. doi:10.1177/1475921719854528.

Hung, S. L., Ding, J. T., & Lu, Y. C. (2019). Developing an energy-efficient and low-delay wake-up wireless sensor network-based structural health monitoring system using on-site earthquake early warning system and wake-on radio. Journal of Civil Structural Health Monitoring, 9(1), 103–115. doi:10.1007/s13349-018-0315-2.

Hussain, S., Matin, A. W., & Islam, O. (2007). Genetic algorithm for hierarchical wireless sensor networks. Journal of Networks, 2(5), 87–97. doi:10.4304/jnw.2.5.87-97.

Heinzelman, W. R., Chandrakasan, A., & Balakrishnan, H. (2000). Energy-efficient communication protocol for wireless microsensor networks. Proceedings of the 33rd Annual Hawaii International Conference on System Sciences, Maui, HI, USA. doi:10.1109/hicss.2000.926982.

Sasikumar, P., & Khara, S. (2012). K-Means Clustering in Wireless Sensor Networks. 2012 Fourth International Conference on Computational Intelligence and Communication Networks. doi:10.1109/cicn.2012.136.

Ray, A., & De, D. (2016). Energy efficient clustering protocol based on K-means (EECPK-means)-midpoint algorithm for enhanced network lifetime in wireless sensor network. IET Wireless Sensor Systems, 6(6), 181–191. doi:10.1049/iet-wss.2015.0087.

Periyasamy, S., Khara, S., & Thangavelu, S. (2016). Balanced Cluster Head Selection Based on Modified k -Means in a Distributed Wireless Sensor Network. International Journal of Distributed Sensor Networks, 2016(3), 5040475. doi:10.1155/2016/5040475.

Holland, J. H. (2019). Adaptation in Natural and Artificial Systems. The University of Michigan Press, Ann Arbor, United States. doi:10.7551/mitpress/1090.001.0001.

Goldberg, D. E. (1989). Genetic algorithms in search, optimization, and machine learning. (1989). Choice Reviews Online, 27(02), 27-0936-27–0936. doi:10.5860/choice.27-0936.

Adeli, H., & Hung, S. L. (1994). Machine learning: neural networks, genetic algorithms, and fuzzy systems. John Wiley & Sons, Hoboken, United States.

Jin, S., Zhou, M., & Wu, A. S. (2003). Sensor network optimization using a genetic algorithm. Proceedings of the 7th world multiconference on systemics, cybernetics and informatics, 27-30July, 2003, Orlando, United States.

Ferentinos, K. P., & Tsiligiridis, T. A. (2007). Adaptive design optimization of wireless sensor networks using genetic algorithms. Computer Networks, 51(4), 1031–1051. doi:10.1016/j.comnet.2006.06.013.

Peiravi, A., Mashhadi, H. R., & Hamed Javadi, S. (2013). An optimal energy-efficient clustering method in wireless sensor networks using multi-objective genetic algorithm. International Journal of Communication Systems, 26(1), 114–126. doi:10.1002/dac.1336.

Nayak, P., & Vathasavai, B. (2017). Genetic algorithm based clustering approach for wireless sensor network to optimize routing techniques. 2017 7th International Conference on Cloud Computing, Data Science & Engineering - Confluence. doi:10.1109/confluence.2017.7943178.

Pal, R., Yadav, S., Karnwal, R., & Aarti. (2020). EEWC: energy-efficient weighted clustering method based on genetic algorithm for HWSNs. Complex & Intelligent Systems, 6(2), 391–400. doi:10.1007/s40747-020-00137-4.

Bhola, J., Soni, S., & Cheema, G. K. (2020). Genetic algorithm based optimized leach protocol for energy efficient wireless sensor networks. Journal of Ambient Intelligence and Humanized Computing, 11(3), 1281–1288. doi:10.1007/s12652-019-01382-3.

Khoshraftar, K., & Heidari, B. (2020). A Hybrid Method Based on Clustering to Improve the Reliability of the Wireless Sensor Networks. Wireless Personal Communications, 113(2), 1029–1049. doi:10.1007/s11277-020-07266-6.

Hassan, A. A. hussian, Shah, W. M., Othman, M. F. I., & Hassan, H. A. H. (2020). Evaluate the performance of K-Means and the fuzzy C-Means algorithms to formation balanced clusters in wireless sensor networks. International Journal of Electrical and Computer Engineering, 10(2), 1515–1523. doi:10.11591/ijece.v10i2.pp1515-1523.

Middleton, D. (2009). An Introduction to Statistical Communication Theory. McGraw-Hill, New York, United States. doi:10.1109/9780470544112.

Jain, A.K., & Dubes, R.C. (1988). Algorithms for Clustering Data. Prentice Hall, New Jersey, United States. doi:10.2307/1268876.

Forero, P. A., Cano, A., & Giannakis, G. B. (2011). Distributed Clustering Using Wireless Sensor Networks. IEEE Journal of Selected Topics in Signal Processing, 5(4), 707–724. doi:10.1109/jstsp.2011.2114324.

Jae-Hwan Chang, & Tassiulas, L. (n.d.). Energy conserving routing in wireless ad-hoc networks. Proceedings IEEE INFOCOM 2000. Conference on Computer Communications. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies (Cat. No.00CH37064). doi:10.1109/infcom.2000.832170.

Li, Q., Aslam, J., & Rus, D. (2001). Hierarchical power-aware routing in sensor networks. Proceedings of the DIMACS workshop on pervasive networking, 10, No. 381677.381687, 21 May, 2001, New Jersey, United States.

Full Text: PDF

DOI: 10.28991/CEJ-2022-08-12-01


  • There are currently no refbacks.

Copyright (c) 2022 Ching-Yun Kao, Jyun-Wei Huang, Shih-Lin Hung

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