Home   >   CSC-OpenAccess Library   >    Manuscript Information
Full Text Available

This is an Open Access publication published under CSC-OpenAccess Policy.
SDC: A Distributed Clustering Protocol
Yan Li, Li Lao, Jun-Hong Cui
Pages - 205 - 226     |    Revised - 31-01-2011     |    Published - 08-02-2011
Volume - 2   Issue - 6    |    Publication Date - January / February  Table of Contents
network clustering, distributed algorithm, Scaled Coverage Measure, dynamic network, SDC
Network clustering is an important technique used in many large-scale distributed systems. Given good design and implementation, network clustering can significantly enhance the system\'s scalability and efficiency. However, it is very challenging to design a good clustering protocol for networks that scale fast and change continuously. In this paper, we propose a distributed network clustering protocol SDC targeting large-scale decentralized systems. In SDC, clusters are dynamically formed and adjusted based on SCM, a practical clustering accuracy measure. Based on SCM, each node can join or leave a cluster such that the clustering accuracy of the whole network can be improved. A big advantage of SDC is it can recover accurate clusters from node dynamics with very small message overhead. Through extensive simulations, we conclude that SDC is able to discover good quality clusters very efficiently.
CITED BY (5)  
1 Selvan, S. K. (2015). Distributed space time and space frequency codes to achieve cooperative diversity in wireless network.
2 Selvan, K. S., Ravi, S., & Jabeen, F. (2013). Improved QoS by Clustering Identically Modulated WSN Nodes using Reprogrammable High Speed Architecture. International Journal of Computer Applications, 68(8).
3 Tsugawa, S., Ohsaki, H., & Imase, M. (2012, March). Lightweight Distributed Method for Connectivity-based Clustering Based on Schelling's Model. In Advanced Information Networking and Applications Workshops (WAINA), 2012 26th International Conference on (pp. 1137-1142). IEEE.
4 Hussen, F., Elleithy, K., & Razaque, A. (2012). Implementation of Fault Tolerance Algorithm to Restore Affected Nodes in Scheduling Clusters. International Journal of Computer Networks & Communications, 4(1), 1.
5 Sho Tsugawa, Jumori Keita, Hiroyuki Osaki, and now SeraShin. (2011). Proposal of lightweight distributed clustering technique based on the Schelling model (home network, ubiquitous network, cloud computing, context-aware, location-based services, e- commerce and , general). Electronics, information and communication Engineers technical report. IN, infor
1 Google Scholar
2 CiteSeerX
3 refSeek
4 Socol@r
5 Scribd
6 WorldCat
7 SlideShare
8 PdfSR
1 A. A. Abbasi and M. Younis. A survey on clustering algorithms for wireless sensor networks.Computer Communications, 30:2826–2841, June 2007.
2 J. Ahuja and J.-H. Cui. A scalable peer-to-peer file sharing system supporting complex queries. UCONN CSE Technical Report, UbiNet TR05-01, January 2005.
3 J. N. Al-Karaki and A. E. Kamal. Routing techniques in wireless sensor networks: a survey.IEEE Wireless Communications, 11(6):6–28, December 2004.
4 R. Albert, H. Jeong, and A.-L. Barabasi. Error and attack tolerance of complex networks.Discrete Applied Mathematics, 406:378–382, August 2000.
5 A. Barbu and S.-C. Zhu. Graph partition by swendsen-wang cuts. Ninth IEEE International Conference on Computer Vision Volume 1, 10 13 - 10 2003, Nice, France.
6 D. S. Callaway, M. E. J. Newman, S. H. Strogatz, and D. J. Watts. Network robustness and fragility: Percolation on random graphs. Physical Review Letters, 85(25):5468–5471, Dec 2000.
7 K. Calvert and E. Zegura. Gt-itm: Georgia tech internetwork topology models.http://www.cc.gatech.edu/fac/Ellen.Zegura/gt-itm/gt-itm.tar.gz, 1996.
8 M. Chatterjee, S. K. Das, and D. Turgut. Wca: A weighted clustering algorithm for mobile ad hoc networks. Cluster Computing, 5:193–204, April 2002.
9 A. Crespo and H. Garcia-Molina. Semantic overlay networks for p2p systems, 2002.
10 J. S. Deogun, D. Kratsch, and G. Steiner. An approximation algorithm for clustering graphs with dominating diametral path. Inf. Process. Lett., 61(3):121–127, 1997.
11 N. Dimokas, D. Katsaros, and Y. Manolopoulos. Node clustering in wireless sensor networks by considering structural characteristics of the network graph. International Conference on Information Technology, 00:122–127, 2007.
12 D. Doleva, S. Jaminb, O. Mokrync, and Y. Shavittc. Internet resiliency to attacks and failures under bgp policy routing. Computer Networks, 50:3183–3196, November 2005.
13 D. Estrin, Y. Rekhter, and S. Hotz. Scalable inter-domain routing architecture. In SIGCOMM’92: Conference proceedings on Communications architectures & protocols, pages 40–52, 1992.
14 Y. Fernandess and D. Malkhi. K-clustering in wireless ad hoc networks. POMC ’02:Proceedings of the second ACM international workshop on Principles of mobile computing, pages 31–37, 2002.
15 A. Ganesh, L. Massoulie, and D. Towsley. The effect of network topology on the spread of epidemics. In IEEE INFOCOM, volume 2, pages 1455–1466, March 2005.
16 L. Garces-Erice, E. W. Biersack, K. W. Ross, P. A. Felber, and G. Urvoy-Keller. Hierarchical p2p systems. In Proceedings of ACM/IFIP International Conference on Parallel and Distributed Computing (Euro-Par), 2003.
17 C. Gkantsidis, M. Mihail, , and E. Zegura. Spectral analysis of internet topologies. IEEE INFOCOM, 2003.
18 R. Hoes, T. Basten, W.-L. Yeow, C.-K. Tham, M. Geilen, and H. Corporaal. Qos management for wireless sensor networks with a mobile sink. In EWSN ’09: Proceedings of the 6th European Conference on Wireless Sensor Networks, pages 53–68, Berlin, Heidelberg, 2009.Springer-Verlag.
19 J. Jin, J. Liang, J. Jin, and K. Nahrstedt. Large-scale qos-aware service-oriented networking with a clustering-based approach. In 16th International Conference on Computer Communications and Networks, pages 522–528, August 2007.
20 V. Kantere, D. Tsoumakos, T. Sellis, and N. Roussopoulos. Groupeer: Dynamic clustering of p2p databases. Information Systems, 34:62–86, March 2009.
21 G. Kwon and K. D. Ryu. An efficient peer-to-peer file sharing exploiting hierarchy and asymmetry. In SAINT, pages 226–233, 2003.
22 Y. Li, J.-H. Cui, D. Maggiorini, and M. Faloutsos. Characterizing and modeling clustering features in as-level internet topology. In Proceedings of IEEE INFOCOM, 2008.
23 A. McDonald and T. Znati. A mobility-based framework for adaptive clustering in wireless ad hoc networks. IEEE Journal on Selected Areas in Communication, Vol. 17, No. 8, August 1999.
24 A. Medina, A. Lakhina, I. Matta, , and J. Byers. Brite: Universal topology generation from a user’s perspective. In Proceedings of Workshop the International Workshop on Modeling,Analysis and Simulation of Computer and Telecommunications Systems (MASCOTS ’01),October 2001.
25 D. Moore, J. Leonard, D. Rus, and S. Teller. Robust distributed network localization with noisy range measurements. In SenSys ’04: Proceedings of the 2nd international conference on Embedded networked sensor systems, pages 50–61, New York, NY, USA, 2004. ACM.
26 R. Pastor-Satorras and A. Vespignani. Epidemic spreading in scale-free networks. Phys.Rev. Lett., 86(14):3200–3203, Apr 2001.
27 L. Ramaswamy, B. Gedik, and L. Liu. A distributed approach to node clustering in decentralized peerto-peer networks. IEEE Transactions on Parallel and Distributed Systems,16(9), Sept. 2005.
28 S. van Dongen. A new cluster algorithm for graphs. Technical report INS-R9814, Centrum voor Wiskunde en Informatica (CWI), ISSN 1386-3681, Dec. 1998.
29 S. van Dongen. Performancde criteria for graph clustering and markov cluster experiments.Technical report, National Research Institute for Mathematics and Computer Science in the Netherlands, Amsterdam, 2000.
30 O. Younis and S. Fahmy. Distributed clustering in ad-hoc sensor networks: A hybrid, energyefficient approach. In IEEE INFOCOM, 2004.
31 W. Zheng, S. Zhang, Y. Ouyang, F. Makedon, and J. Ford. Node clustering based on link delay in p2p networks. In SAC ’05: Proceedings of the 2005 ACM symposium on Applied computing, pages 744–749, 2005.
32 C. C. Zou, D. Towsley, and W. Gong. Modeling and simulation study of the propagation and defense of internet email worm. IEEE Transactions on Dependable and Secure Computing,4:105–118, 2007.
Dr. Yan Li
University of Connecticut - United States of America
Dr. Li Lao
Google Santa Monica - United States of America
Dr. Jun-Hong Cui
University of Connecticut - United States of America