Loading [MathJax]/jax/output/SVG/jax.js
We use cookies to improve your experience with our site.

Indexed in:

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

Submission System
(Author / Reviewer / Editor)
Advanced Search
Volume 23 Issue 6
November  2008
Turn off MathJax
Article Contents
Abstract
References
Related Articles
Yong-Xuan Lai, Yi-Long Chen, Hong Chen. PEJA: Progressive Energy-Efficient Join Processing for Sensor Networks[J]. Journal of Computer Science and Technology, 2008, 23(6): 957-972.
Citation: Yong-Xuan Lai, Yi-Long Chen, Hong Chen. PEJA: Progressive Energy-Efficient Join Processing for Sensor Networks[J]. Journal of Computer Science and Technology, 2008, 23(6): 957-972.
shu

PEJA: Progressive Energy-Efficient Join Processing for Sensor Networks

  • School of Information, Renmin University of China, Beijing 100872, ChinaKey Laboratory of Data Engineering and Knowledge Engineering, Ministry of Education, Beijing 100872, China

More Information
  • Received Date: March 01, 2008
  • Revised Date: August 26, 2008
  • Published Date: November 09, 2008
    Abstract
  • Sensor networks are widely used in many applications to collaborativelycollect information from the physical environment. In theseapplications, the exploration of the relationship and linkage of sensingdata within multiple regions can be naturally expressed by joiningtuples in these regions. However, the highly distributed andresource-constraint nature of the network makes join a challengingquery. In this paper, we address the problem of processing join queryamong different regions progressively and energy-efficiently in sensornetworks. The proposed algorithm PEJA (Progressive Energy-efficient JoinAlgorithm) adopts an {\it event-driven} strategy to output the joiningresults as soon as possible, and alleviates the storage shortage problemin the in-network nodes. It also installs {\it filters} in the joiningregions to prune unmatchable tuples in the early processing phase,saving lots of unnecessary transmissions. Extensive experiments on bothsynthetic and real world data sets indicate that the PEJA schemeoutperforms other join algorithms, and it is effective in reducing thenumber of transmissions and the delay of query results during the joinprocessing.
    • FullText(HTML)
    • References (21)
  • [1] Cruller D, Estrin D, Srivastava M. Overview of sensor networks. {\it Computer}, Long Beach, CA, 2004, 37(8): 41--49.
    [2]
    } Madden S, Franklin M, Hellerstein J, Hong W. TAG: A Tiny AGgregation service for ad-hoc sensor networks. In {\it Proc. OSDI}, Boston, Massachusetts, USA, 2002, pp.131--146.
    [3]
    } Goldin D. Faster in-network evaluation of spatial aggregation in sensor networks. In {\it Proc. ICDE}, Atlanta, GA, USA, 2006, p.148.
    [4]
    } Wu M, Xu J, Tang X. Processing precision-constrained approximate queries in wireless sensor networks. In {\it Proc. MDM}, Nara, Japan, 2006, p.31.
    [5]
    } Govindan R, Hellerstein J \it et al. \rm The sensor network as a database. {Tech. Rep. 02--771, University of Southern California}, \rm 2002.
    [6]
    } Xu M, Tong K, Kong H, Tang X, Lee W. Monitoring top-k query in wireless sensor networks. In {\it Proc. ICDE}, Atlanta, GA, USA, 2006, pp.962--976.
    [7]
    } Deshpande A, Guestrin C, Madden S, Hellerstein J, Hong W. {Model-driven data acquisition in sensor networks}. In {\it Proc. VLDB}, Toronto, Canada, 2004, pp.588--599.
    [8]
    } Yu H, Lim E, Zhang J. {On in-network synopsis join processing for sensor networks}. In {\it Proc. MDM}, Nara, Japan, 2006, p.32.
    [9]
    } Chowdhary V, Gupta G. Communication-efficient implementation of join in sensor networks. In {\it Proc. DASFAA}, Beijing, China, 2005, pp.447--460.
    [10]
    } Pandit A, Gupta H. Communication efficient implementation of range-joins in sensor networks. In {\it Proc. DASFAA}, Singapore, 2006, pp.859--869.
    [11]
    } Abadi D, Madden S, Lindner W. REED: Robust, efficient filtering and event detection in sensor networks. In {\it Proc. VLDB}, Trondheim, Norway, 2005, pp.769--780.
    [12]
    } Yang X, Lim H, Ozsu T, Tan K. In-network execution of monitoring queries in sensor networks. In {\it Proc. SIGMOD}, Beijing, China, 2007, pp.521--532.
    [13]
    } Ahmad Y, Cetintemel U, Jannotti J, Zgolinski A. Locality aware networked join evaluation. In {\it Proc. NetDB}, Tokyo, Japan, 2005, p.1183.
    [14]
    } Kossmann D. The state of the art in distributed query processing. {\it ACM Computing Surveys (CSUR)}, 2000, 32(4): 422--469.
    [15]
    } Golab L, {\"O}zsu M. Issues in data stream management. {\it ACM SIGMOD Record}, 2003, 32(2): 5--14.
    [16]
    } Golab L, \"Ozsu M. Processing sliding window multi-joins in continuous queries over data streams. In {\it Proc. VLDB}, Berlin, Germany, 2003, pp.500--511.
    [17]
    } Scheufele W, Moerkotte G. On the complexity of generating optimal plans with cross products. In {\it Proc. PODS}, Tucson, Arizona, United States, 1997, pp.238--248.
    [18]
    } Karp B, Kung H. GPSR: Greedy perimeter stateless routing for wireless networks. In {\it Proc. MobiCom}, Boston, Massachusetts, USA, 2000, pp.243--254.
    [19]
    } Lai Y, Chen H, Wang Y. Dynamic balanced storage in wireless sensor network. In {\it Proc. DMSN}, Vienna, Austria, 2007, pp.7--12.
    [20]
    } Varga A. The omnet++ discrete event simulation system. In {\it Proc. ESM}, Prague, Czech, 2001, pp.319--324.
    [21]
    } Intel Lab Data. http://db.csail.mit.edu/labdata/labdata.html.
    • Relative Articles

  • Related Articles

    [1]Xue Zhang, Jue Hong, Sang-Lu Lu, Li Xie, Jian-Nong Cao. Scoped Bellman-Ford Geographic Routing for Large Dynamic Wireless Sensor Networks[J]. Journal of Computer Science and Technology, 2008, 23(6): 944-956.
    [2]Shao-Liang Peng, Shan-Shan Li, Lei Chen, Yu-Xing Peng, Nong Xiao. Scalable Base-Station Model-Based Multicast in Wireless Sensor Networks[J]. Journal of Computer Science and Technology, 2008, 23(5): 780-791.
    [3]Feng Lu, Liang-Tien Chia, Kok-Leong Tay, Wai-Hoe Chong. NBgossip: An Energy-Efficient Gossip Algorithm for Wireless Sensor Networks[J]. Journal of Computer Science and Technology, 2008, 23(3): 426-437.
    [4]Michele Garetto, Marco Gribaudo, Carla-Fabiana Chiasserini, Emilio Leonardi. Sensor Deployment and Relocation: A Unified Scheme[J]. Journal of Computer Science and Technology, 2008, 23(3): 400-412.
    [5]Cheng-Dong Jiang, Guo-Liang Chen. Double Barrier Coverage in Dense Sensor Networks[J]. Journal of Computer Science and Technology, 2008, 23(1): 154-165.
    [6]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.
    [7]Wen Gao, Lionel M. Ni, Zhi-Wei Xu, S. C. Cheung, Li Cui, Qiong Luo. BLOSSOMS: Building Lightweight Optimized Sensor Systems on a Massive Scale[J]. Journal of Computer Science and Technology, 2005, 20(1).
    [8]FENG Jing, MA Xiaojun, GU Boxuan, GU Guanqun. An Aided Tool for Enterprise Network Design[J]. Journal of Computer Science and Technology, 2000, 15(5): 491-497.
    [9]Hou Zhengfeng. A Topology Designing System for a Computer Network[J]. Journal of Computer Science and Technology, 1998, 13(1): 91-96.
    [10]Zhang Bo, Zhang Ling. On Memory Capacity of the Probabilistic Logic Neuron Network[J]. Journal of Computer Science and Technology, 1993, 8(3): 62-66.
    • Supplements (0)

Catalog

    Get Citation
    XML
    Article views (17) PDF downloads (1841) Cited by()
    Related

    Copyright ©2025 JCST, All Rights Reserved     京ICP备05002829号-1

    Institute of Computing Technology, Chinese Academy of Sciences
    P.O. Box 2704, Beijing 100190, P.R. China

    Tel.: 86-10-62610746 E-mail: jcst@ict.ac.cn

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return