Clustering in WSN Based on Minimum Spanning Tree Using Divide and Conquer Approach

Authors: Uttam Vijay, Nitin Gupta

Abstract:

Due to heavy energy constraints in WSNs clustering is an efficient way to manage the energy in sensors. There are many methods already proposed in the area of clustering and research is still going on to make clustering more energy efficient. In our paper we are proposing a minimum spanning tree based clustering using divide and conquer approach. The MST based clustering was first proposed in 1970’s for large databases. Here we are taking divide and conquer approach and implementing it for wireless sensor networks with the constraints attached to the sensor networks. This Divide and conquer approach is implemented in a way that we don’t have to construct the whole MST before clustering but we just find the edge which will be the part of the MST to a corresponding graph and divide the graph in clusters there itself if that edge from the graph can be removed judging on certain constraints and hence saving lot of computation.

Keywords: Algorithm, Clustering, Edge-Weighted Graph, Weighted-LEACH.

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

References:

[1] F. Akyildiz, W. Su, Y. Sankarasubramaniam and E. Cayirci. “A Survey on Sensor Networks” IEEE communication Magazine, Aug 2002:102- 114
[2] Wireless Sensor Network(A Networking Perspective) Jun Jheng and Abbas Jamalipour
[Book]
[3] C.T. Zahn, “Graph-Theoretical Methods for Detecting and Describing Gestalt Clusters,” IEEE Trans. Computers, vol. 20, no. 1, pp. 68-86, Jan. 1971
[4] A Divide-and-Conquer Approach for Minimum Spanning Tree-Based Clustering Xiaochun Wang, Xiali Wang, and D. Mitchell Wilkes, Member, IEEE Transactions On Knowledge And Data Engineering, Vol. 21, No. 7, July 2009
[5] W. B. Heinzelman, A. P. Chandrakasan, and H. Balakrishnan, “Energy Efficient Communication Protocol for Wireless Microsensor Networks,” in Proceedings of 33rd Hawaii Int’l. Conf. Sys. Sci., 2000.
[6] M. Laszlo and S. Mukherjee, “Minimum Spanning Tree Partitioning Algorithm for Micro aggregation,” IEEE Trans. Knowledge and Data Eng., vol. 17, no. 7, pp. 902-911, July 2005
[7] O. Grygorash, Y. Zhou, and Z. Jorgensen, “Minimum Spanning Tree- Based Clustering Algorithms,” Proc. IEEE Int’l Conf. Tool with Artificial Intelligence, pp. 73-81, 2006
[8] Wang, D.: An Energy-Efficient Cluster Head Assignment Scheme for Hierarchical Wireless Sensor Networks. Int. Journal of Wireless Inf. Networks 15(2) (2008) 61-71
[9] Weighted Spanning Tree Clustering Routing Algorithm based on LEACH Huazhong Zhang, PeipeiChe2nd International Conference on Future Computer and Communication 2010 volume 2 page 223-227
[10] N. Li, J. C. Hou, and L. Sha. Design and Analysis of an MST-based Topology control algorithm. IEEE Infocom’ 2003, San Francisco, USA, 2003, 1702–1712
[11] MST-Based Clustering Topology Control Algorithm ForWireless Sensor Networks1Cai Wenyu Zhang Meiyan (School of Electronics and Information, Hangzhou Dianzi University, Hangzhou 310018, China)Vol.27 No.3 Journal Of Electronics (China) May 2010
[12] An Energy Effective Adaptive Spatial Sampling Algorithm for Wireless Sensor Networks Zhang Meiyan+, ZhengXiaodan 2012 International Conference on Computer Technology and Science (ICCTS 2012) IPCSIT vol. 47 (2012) © (2012) IACSIT Press, Singapore Doi: 10.7763/Ipcsit.2012.V47.61