We use cookies to improve your experience with our site.

Indexed in:

SCIE, EI, Scopus, INSPEC, DBLP, CSCD, etc.

Submission System
(Author / Reviewer / Editor)
Xiu-Li Ma, Hai-Feng Hu, Shuang-Feng Li, Hong-Mei Xiao, Qiong Luo, Dong-Qing Yang, Shi-Wei Tang. DHC: Distributed, Hierarchical Clustering in Sensor Networks[J]. Journal of Computer Science and Technology, 2011, 26(4): 643-662. DOI: 10.1007/s11390-011-1165-0
Citation: Xiu-Li Ma, Hai-Feng Hu, Shuang-Feng Li, Hong-Mei Xiao, Qiong Luo, Dong-Qing Yang, Shi-Wei Tang. DHC: Distributed, Hierarchical Clustering in Sensor Networks[J]. Journal of Computer Science and Technology, 2011, 26(4): 643-662. DOI: 10.1007/s11390-011-1165-0

DHC: Distributed, Hierarchical Clustering in Sensor Networks

More Information
  • Received Date: September 08, 2009
  • Revised Date: March 14, 2011
  • Published Date: July 04, 2011
  • In many sensor network applications, it is essential to get the data distribution of the attribute value over the network. Such data distribution can be got through clustering, which partitions the network into contiguous regions, each of which contains sensor nodes of a range of similar readings. This paper proposes a method named Distributed, Hierarchical Clustering (DHC) for online data analysis and mining in senior networks. Different from the acquisition and aggregation of raw sensory data, DHC clusters sensor nodes based on their current data values as well as their geographical proximity, and computes a summary for each cluster. Furthermore, these clusters, together with their summaries, are produced in a distributed, bottom-up manner. The resulting hierarchy of clusters and their summaries facilitates interactive data exploration at multiple resolutions. It can also be used to improve the efficiency of data-centric routing and query processing in sensor networks. We also design and evaluate the maintenance mechanisms for DHC to make it be able to work on evolving data. Our simulation results on real world datasets as well as synthetic datasets show the effectiveness and efficiency of our approach.
  • [1]
    Volgyesi P, Nadas A, Koutsoukos X, Ledeczi A. Air qualitymonitoring with Sensor Map. In Proc. IPSN 2008, St. Louis, USA,Apr.22-24, 2008, pp.529-530.
    [2]
    Barrenetxea G, Ingelrest F, Schaefer G, Vetterli M.SensorScope: Out-of-the-box environmental monitoring. In Proc. IPSN 2008,St. Louis, USA, Apr.22-24, 2008, pp.332-343.
    [3]
    Michel S, Salehi A, Luo L, Dawes N, Aberer K, Barrenetxea G,Bavay M, Kansal A, Kumar A, Nath S, Parlange M, Tansley S, Ingen C V,Zhao F, Zhou Y. Environmental monitoring 2.0. In Proc. ICDE 2009,Shanghai, China, Mar.29-Apr.2, 2009, pp.1507-1510.
    [4]
    Krause A, Leskovec J, Guestrin C, Van Briesen J, Faloutsos C.Efficient sensor placement optimization for securing large waterdistribution networks. Journal of Water Resources Planning andManagement, 2008, 134(6): 516-526.
    [5]
    Xue W, Luo Q, Chen L, Liu Y. Contour map matching for eventdetection in sensor networks. In Proc. SIGMOD 2006, Chicago, USA,Jun.27-29, pp.145-156.
    [6]
    Meka A, Singh A K. Distributed spatial clustering in sensornetworks. In Proc. EDBT 2006, Munich, Germany, Mar.26-31, 2006, pp.980-1000.
    [7]
    Guestrin C, Bodik P, Thibaux R, Paskin M, Madden S. Distributedregression: An efficient framework for modeling sensor network data. In Proc. IPSN 2004, Berkeley, USA, Apr.26-27, 2004, pp.1-10.
    [8]
    Yin J, Gaber M M. Clustering distributed time series in sensornetworks. In Proc. ICDM 2008, Pisa, Italy, Dec.15-19, 2008, pp.678-687.
    [9]
    Ma X, Li S, Luo Q, Yang D, Tang S. Distributed, hierarchicalclustering and summarization in sensor networks. In Proc. APWeb2007/WAIM 2007, Huangshan, China, Jun.16-18, 2007, pp.168-175.
    [10]
    Han J, Kamber M. Data Mining: Concepts and Techniques, SecondEdition. Morgan Kaufmann Publishers, 2006.
    [11]
    Zhang T, Ramakrishnan R, Livny M. BIRCH: An efficient dataclustering method for very large databases. In Proc. SIGMOD 1996,Montreal, Canada, Jun.4-6, 1996, pp.103-114.
    [12]
    Johnson D B, aMaltz D A. Dynamic Source Routing in Ad-HocWireless Networks. Mobile Computing, Kluwer Academic Publishers, 1996, pp.153-181.
    [13]
    Madden S, Franklin M J, Hellerstein J M, Hong W. Tag: A tinyaggregation service for ad hoc sensor networks. In Proc. OSDI 2002,Boston, USA, Dec.9-11, 2002.
    [14]
    Olston C, Jiang J, Widom J. Adaptive filters for continuousqueries over distributed data streams. In Proc. SIGMOD 2003, San Diego,USA, Jun.9-12, pp.563-574.
    [15]
    Deligiannakis A, Kotidis Y, Roussopoulos N. Hierarchicalin-network data aggregation with quality guarantees. In Proc. EDBT2004, Crete, Greece, Mar.14-18, 2004, pp.658-675.
    [16]
    CRU data. http://www.cru.uea.ac.uk/cru/data, Jul.2009.
    [17]
    Intel Lab data. http://berkeley.intel-research.net/labdata/, Sept. 2008.
    [18]
    Jindal A, Psounis K. Modeling spatially-correlated sensor networkdata. In Proc. SECON 2004, Santa Clara, USA, Oct.4-7, 2004, pp.162-171.
    [19]
    Madden S, Franklin M J, Hellerstein J M, Hong W. The design ofan acquisitional query processor for sensor networks. In Proc. SIGMOD 2003,San Diego, USA, Jun.9-12, pp.491-502.
    [20]
    Breunig M M, Kriegel H, Kroger P, Sander J. Data bubbles: Qualitypreserving performance boosting for hierarchical clustering. In Proc.SIGMOD 2001, Santa Barbara, USA, May 21-24, 2001, pp.79-90.
    [21]
    Bandyopadhyay S, Coyle E J. An energy efficient hierarchicalclustering algorithm for wireless sensor networks. In Proc. INFOCOM2003, San Francisco, USA, Mar.30-Apr.3, 2003, pp.1713-1723.
    [22]
    Zhang Q, Liu J, Wang W. Approximate clustering on distributeddata streams. In Proc. ICDE 2008, Cancun, Mexico, Apr.7-12, 2008, pp.1131-1139.
    [23]
    Hua M, Lau MK, Pei J, Wu K. Continuous K-means monitoring with lowreporting cost in sensor networks. IEEE Transaction on Knowledge and Data Engineering,2009, 21(12): 1679-1691.
    [24]
    Liu C, Wu K, Pei J. An energy-efficient data collection frameworkfor wireless sensor networks by exploiting spatiotemporal correlation. IEEE Transaction on Parallel and Distributed Systems, July 2007, 18(7): 1010-1023.
    [25]
    Kotidis Y. Snapshot queries: Towards data-centric sensor networks.In Proc. ICDE 2005, Tokyo, Japan, Apr.5-8, 2005, pp.131-142.
  • Related Articles

    [1]Xiao-Long Zheng, Meng Wan. A Survey on Data Dissemination in Wireless Sensor Networks[J]. Journal of Computer Science and Technology, 2014, 29(3): 470-486. DOI: 10.1007/s11390-014-1443-8
    [2]Yu Gu, Bao-Hua Zhao, Yu-Sheng Ji, Jie Li. Theoretical Treatment of Target Coverage in Wireless Sensor Networks[J]. Journal of Computer Science and Technology, 2011, 26(1): 117-129. DOI: 10.1007/s11390-011-1115-x
    [3]Haixun Wang, Jian Pei. Clustering by Pattern Similarity[J]. Journal of Computer Science and Technology, 2008, 23(4): 481-496.
    [4]Xiao-Lin Li, Jian-Nong Cao. Coordinated Workload Scheduling in Hierarchical Sensor Networks for Data Fusion Applications[J]. Journal of Computer Science and Technology, 2008, 23(3): 355-364.
    [5]Yu-Bao Liu, Jia-Rong Cai, Jian Yin, Ada Wai-Chee Fu. Clustering Text Data Streams[J]. Journal of Computer Science and Technology, 2008, 23(1): 112-128.
    [6]Bo Yang, Da-You Liu. A Heuristic Clustering Algorithm for Mining Communities in Signed Networks[J]. Journal of Computer Science and Technology, 2007, 22(2): 320-328.
    [7]Liu-Sheng Huang, Hong-Li Xu, Yang Wang, Jun-Min Wu, Hong Li. Coverage and Exposure Paths in Wireless Sensor Networks[J]. Journal of Computer Science and Technology, 2006, 21(4): 490-495.
    [8]QIAN WeiNing, GONG XueQing, ZHOU AoYing. Clustering in Very Large Databases Based on Distance and Density[J]. Journal of Computer Science and Technology, 2003, 18(1).
    [9]HE Zengyou, XU Xiaofei, DENG Shengchun. Squeezer: An Efficient Algorithm for Clustering Categorical Data[J]. Journal of Computer Science and Technology, 2002, 17(5).
    [10]ZHOU Aoying, JIN Wen, ZHOU Shuigeng, QIAN Weining, TIAN Zenping. Incremental Mining of the Schema of Semistructured Data[J]. Journal of Computer Science and Technology, 2000, 15(3): 241-248.

Catalog

    Article views (24) PDF downloads (1553) Cited by()
    Related

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return