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

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.

• Uttam Vijay
• Nitin Gupta

• Algorithm
• Clustering
• Edge-Weighted Graph
• Weighted-LEACH.

<p>[1] F. Akyildiz, W. Su, Y. Sankarasubramaniam and E. Cayirci. &ldquo;A Survey
on Sensor Networks&rdquo; IEEE communication Magazine, Aug 2002:102-
114
[2] Wireless Sensor Network(A Networking Perspective) Jun Jheng and
Abbas Jamalipour [Book]
[3] C.T. Zahn, &ldquo;Graph-Theoretical Methods for Detecting and Describing
Gestalt Clusters,&rdquo; 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, &ldquo;Energy
Efficient Communication Protocol for Wireless Microsensor Networks,&rdquo;
in Proceedings of 33rd Hawaii Int&rsquo;l. Conf. Sys. Sci., 2000.
[6] M. Laszlo and S. Mukherjee, &ldquo;Minimum Spanning Tree Partitioning
Algorithm for Micro aggregation,&rdquo; IEEE Trans. Knowledge and Data
Eng., vol. 17, no. 7, pp. 902-911, July 2005
[7] O. Grygorash, Y. Zhou, and Z. Jorgensen, &ldquo;Minimum Spanning Tree-
Based Clustering Algorithms,&rdquo; Proc. IEEE Int&rsquo;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&rsquo; 2003, San Francisco, USA,
2003, 1702&ndash;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) &copy; (2012) IACSIT Press, Singapore Doi:
10.7763/Ipcsit.2012.V47.61</p>