Home   >   CSC-OpenAccess Library   >    Manuscript Information
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
MORE INFORMATION
KEYWORDS
network clustering, distributed algorithm, Scaled Coverage Measure, dynamic network, SDC
ABSTRACT
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 
A. A. Abbasi and M. Younis. A survey on clustering algorithms for wireless sensor networks.Computer Communications, 30:2826–2841, June 2007.
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.
A. Crespo and H. Garcia-Molina. Semantic overlay networks for p2p systems, 2002.
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.
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.
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.
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.
C. Gkantsidis, M. Mihail, , and E. Zegura. Spectral analysis of internet topologies. IEEE INFOCOM, 2003.
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.
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.
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.
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.
G. Kwon and K. D. Ryu. An efficient peer-to-peer file sharing exploiting hierarchy and asymmetry. In SAINT, pages 226–233, 2003.
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.
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.
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.
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.
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.
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.
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.
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.
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.
O. Younis and S. Fahmy. Distributed clustering in ad-hoc sensor networks: A hybrid, energyefficient approach. In IEEE INFOCOM, 2004.
R. Albert, H. Jeong, and A.-L. Barabasi. Error and attack tolerance of complex networks.Discrete Applied Mathematics, 406:378–382, August 2000.
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.
R. Pastor-Satorras and A. Vespignani. Epidemic spreading in scale-free networks. Phys.Rev. Lett., 86(14):3200–3203, Apr 2001.
S. van Dongen. A new cluster algorithm for graphs. Technical report INS-R9814, Centrum voor Wiskunde en Informatica (CWI), ISSN 1386-3681, Dec. 1998.
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.
V. Kantere, D. Tsoumakos, T. Sellis, and N. Roussopoulos. Groupeer: Dynamic clustering of p2p databases. Information Systems, 34:62–86, March 2009.
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.
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.
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.
Dr. Yan Li
University of Connecticut - United States of America
2yanli@gmail.com
Dr. Li Lao
Google Santa Monica - United States of America
Dr. Jun-Hong Cui
University of Connecticut - United States of America


CREATE AUTHOR ACCOUNT
 
LAUNCH YOUR SPECIAL ISSUE
View all special issues >>
 
PUBLICATION VIDEOS