A Spanning Tree for Enhanced Cluster Based Routing in Wireless Sensor Network

Authors: M. Saravanan, M. Madheswaran

Abstract:

Wireless Sensor Network (WSN) clustering architecture enables features like network scalability, communication overhead reduction, and fault tolerance. After clustering, aggregated data is transferred to data sink and reducing unnecessary, redundant data transfer. It reduces nodes transmitting, and so saves energy consumption. Also, it allows scalability for many nodes, reduces communication overhead, and allows efficient use of WSN resources. Clustering based routing methods manage network energy consumption efficiently. Building spanning trees for data collection rooted at a sink node is a fundamental data aggregation method in sensor networks. The problem of determining Cluster Head (CH) optimal number is an NP-Hard problem. In this paper, we combine cluster based routing features for cluster formation and CH selection and use Minimum Spanning Tree (MST) for intra-cluster communication. The proposed method is based on optimizing MST using Simulated Annealing (SA). In this work, normalized values of mobility, delay, and remaining energy are considered for finding optimal MST. Simulation results demonstrate the effectiveness of the proposed method in improving the packet delivery ratio and reducing the end to end delay.

Keywords: Wireless sensor network, clustering, minimum spanning tree, genetic algorithm, low energy adaptive clustering hierarchy, simulated annealing.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1124467

References:

[1] Matheswaran, S., & Madheswaran, M. (2014). A Hybrid Optimized Weighted Minimum Spanning Tree for the Shortest Intrapath Selection in Wireless Sensor Network. Mathematical Problems in Engineering, 2014.
[2] Kumar, D., Aseri, T. C., & Patel, R. B. (2011). A novel multihop energy efficient heterogeneous clustered scheme for wireless sensor networks. Tamkang Journal of Science and Engineering, 14(4), 359-368.
[3] Liu, X. (2012). A survey on clustering routing protocols in wireless sensor networks. Sensors, 12(8), 11113-11153.
[4] Erciyes, K., Ozsoyeller, D., & Dagdeviren, O. (2008). Distributed algorithms to form cluster based spanning trees in wireless sensor networks. InComputational Science–ICCS 2008 (pp. 519-528). Springer Berlin Heidelberg.
[5] Neelamma, B. U., & Challa, M. M. (2014). Efficient Routing Tree Formation to Reduce Energy in Lightweight Routing in Wireless Sensor Networks.International Journal of Computer Science & Information Technologies, 5(4).
[6] Kann, V. (1992). On the approximability of NP-complete optimization problems(Doctoral dissertation, Royal Institute of Technology).
[7] Ferreira, A., & Jarry, A. (2012). Minimum-Energy Broadcast Routing in Dynamic Wireless Networks. Journal of Green Engineering, 2(2), 115-123.
[8] Ghana, B. A. R. O. (2011). Minimum spanning tree route for major tourist centers in the (Doctoral dissertation, kwame nkrumah university of science and technology).
[9] Kavandi, H., Meghdadi, M., & Mortaza BayaT (2014). A method for optimizing of the energy consumption in wireless sensor networks by dynamic selection of cluster head using fuzzy logic
[10] Abdellah Chehri, Paul Fortier & Pierre-Martin Tardif (2008). Geo-Location with Wireless Sensor Networks using Non-linear Optimization. IJCSNS International Journal of Computer Science and Network Security, VOL.8 No.1, pp:145-154.
[11] Tan, N. D., & Viet, N. D. (2015, January). SSTBC: Sleep scheduled and tree-based clustering routing protocol for energy-efficient in wireless sensor networks. In Computing & Communication Technologies-Research, Innovation, and Vision for the Future (RIVF), 2015 IEEE RIVF International Conference on(pp. 180-185). IEEE.
[12] Ramasamy, V., & Balakrishnan, K. (2015) An Efficient Cluster-Tree based Data Collection Scheme for Large Mobile Wireless Sensor Networks.
[13] Karthickraja, N. P., & Sumathy, V. (2010, January). A study of routing protocols and a hybrid routing protocol based on rapid spanning tree and cluster head routing in wireless sensor networks. In Wireless Communication and Sensor Computing, 2010. ICWCSC 2010. International Conference on (pp. 1-6). IEEE.
[14] Chauhan, R., & Gupta, V. (2012, March). Energy Efficient Sleep Scheduled Clustering & Spanning Tree based data aggregation in wireless sensor network. In Recent Advances in Information Technology (RAIT), 2012 1st International Conference on (pp. 536-541). IEEE.
[15] Chatterjee, A., Mukhopadhyay, A. K., & Mukherjee, D. (2012, November). A transport protocol for congestion avoidance in Wireless Sensor Networks using cluster-based single-hop-tree topology. In Emerging Applications of Information Technology (EAIT), 2012 Third International Conference on (pp. 389-393). IEEE.
[16] Kim, K. T., Lyu, C. H., Moon, S. S., & Youn, H. Y. (2010, April). Tree-based clustering (TBC) for energy efficient wireless sensor networks. In Advanced Information Networking and Applications Workshops (WAINA), 2010 IEEE 24th International Conference on (pp. 680-685). IEEE.
[17] Guo, Y., Ren, Q., Zhang, D., Wang, Y., & Hui, L. (2010, October). Constructing a Cluster-Based Multi-Hop Tree for Object Tracking in Wireless Sensor Networks. In Proceedings of the 2010 International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery (pp. 101-107). IEEE Computer Society.
[18] Zhang, Z., & Yu, F. (2010, April). Performance analysis of cluster-based and tree-based routing protocols for wireless sensor networks. In Communications and Mobile Computing (CMC), 2010 International Conference on (Vol. 1, pp. 418-422). IEEE.
[19] Yang, J., Bai, B., & Li, H. (2012). A cluster-tree based data gathering algorithm for wireless sensor networks.
[20] Law, K. L. E., & Okeke, B. (2010, December). Lifetime extending heuristic for clustered wireless sensor networks. In Global Telecommunications Conference (GLOBECOM 2010), 2010 IEEE (pp. 1-5). IEEE.
[21] Abusaimeh, H., & Yang, S. H. (2012, March). Energy-aware optimization of the number of clusters and cluster-heads in WSN. In Innovations in Information Technology (IIT), 2012 International Conference on (pp. 178-183). IEEE.
[22] Bandral, M. S., & Jain, S. (2014, May). Energy efficient protocol for wireless sensor network. In Recent Advances and Innovations in Engineering (ICRAIE), 2014 (pp. 1-6). IEEE.
[23] Sahoo, R. R., Singh, M., Sardar, A. R., Mohapatra, S., & Sarkar, S. K. (2013, March). TREE-CR: Trust based secure and energy efficient clustering in WSN. In Emerging Trends in Computing, Communication and Nanotechnology (ICE-CCN), 2013 International Conference on (pp. 532-538). IEEE.
[24] Abdulsalam, H. M., & Ali, B. A. (2013). W-leach based dynamic adaptive data aggregation algorithm for wireless sensor networks. International Journal of Distributed Sensor Networks, 2013.
[25] Chang, J. Y., & Ju, P. H. (2012). An efficient cluster-based power saving scheme for wireless sensor networks. EURASIP Journal on Wireless Communications and Networking, 2012(1), 1-10.
[26] Handy, M. J., Haase, M., & Timmermann, D. (2002). Low energy adaptive clustering hierarchy with deterministic cluster-head selection. In Mobile and Wireless Communications Network, 2002. 4th International Workshop on (pp. 368-372). IEEE.
[27] Ramesh, K., & Somasundaram, D. K. (2012). A comparative study of clusterhead selection algorithms in wireless sensor networks. arXiv preprint arXiv:1205.1673.
[28] EkbataniFard, G. H., Monsefi, R., Akbarzadeh-T, M. R., & Yaghmaee, M. (2010, May). A multi-objective genetic algorithm based approach for energy efficient QoS-routing in two-tiered wireless sensor networks. In Wireless Pervasive Computing (ISWPC), 2010 5th IEEE International Symposium on (pp. 80-85). IEEE.
[29] Kumar, M., & Gupta, D. R. (2012). A comparative study using simulated annealing and fast output sampling feedback technique based pss design for single machine infinite bus system modeling. International Journal of Engineering Research and Applications (IJERA), 2(2), 223-228.
[30] Weise, T., Skubch, H., Zapf, M., & Geihs, K. (2008). Global optimization algorithms and their application to distributed systems. August, 181, 1-69.
[31] Kaura, R., & Majithia, S. (2012, December). Efficient End to End Routing using RSSI & Simulated Annealing. In International Journal of Engineering Research and Technology (Vol. 1, No. 10 (December-2012)). ESRSA Publications.
[32] Jang, H. C., Lee, H. C., & Huang, J. X. (2006, October). Optimal Energy Consumption for Wireless Sensor Networks. In JCIS.
[33] Guo, W., Zhang, B., Chen, G., Wang, X., & Xiong, N. (2013). A PSO-Optimized minimum spanning tree-based topology control scheme for wireless sensor networks. International Journal of Distributed Sensor Networks, 2013.
[34] Khan, M., Pandurangan, G., & Kumar, V. A. (2009). Distributed algorithms for constructing approximate minimum spanning trees in wireless sensor networks.Parallel and Distributed Systems, IEEE Transactions on, 20(1), 124-139.
[35] Kumar, V., Jain, S., & Tiwari, S. (2011). Energy efficient clustering algorithms in wireless sensor networks: A survey. IJCSI International Journal of Computer Science Issues, 8(5).
[36] Heinzelman, W. R., Chandrakasan, A., & Balakrishnan, H. (2000, January). Energy-efficient communication protocol for wireless microsensor networks. InSystem sciences, 2000. Proceedings of the 33rd annual Hawaii international conference on (pp. 10-pp). IEEE.