• Article
  • | |
  • Metrics
  • |
  • Reference [32]
  • |
  • Related [20]
  • | | |
  • Comments
    Abstract:

    This paper proposes a query in wireless sensor networks: Peak Region Query (PRQ). Given the shape and size of the query region, i.e., a disk region with radius R, peak region query finds out a region with this shape in the network field, in which the aggregation value of the data of the sensors can be maximized. This paper first gives the definition of PRQ, and then proposes a centralized algorithm for the problem. Because the sensors have limited energy, a distributed approach EXQ (an algorithm for extreme value query processing) is proposed, which not only reduces the energy cost but also balances the workload of the sensors, so as to prolong the lifetime of the network. The basic idea is to divide the network field into overlapped sub-regions, compute a local result for each sub-region and aggregate these results to obtain the query answer. The paper compares the energy efficiency and load balance between EXQ and the centralized approach analytically and experimentally.

    Reference
    [1] Li JZ, Li JB, Shi SF. Concepts, issues and advance of sensor networks and data management of sensor networks. Journal of Software, 2003,14(10):1717?1727 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/14/1717.htm
    [2] Sun LM, Li JZ, Chen Y, Zhu HS. Wireless Sensor Networks. Beijing: Tsinghua University Press, 2005 (in Chinese).
    [3] Akyildiz IF, Su W, Sankarasubramaniam Y, Cayirci E. Wireless sensor networks: A survey. Computer Networks, 2002,38(4): 393?422. [doi: 10.1016/S1389-1286(01)00302-4]
    [4] Li M, Liu YH. Rendered path: Range-Free localization in anisotropic sensor networks with holes. In: Kranakis E, Hou J, Ramanathan R, eds. Proc. of the ACM MobiCom. New York: ACM Press, 2007. 51?62.
    [5] Madden SR, Franklin MJ, Hellerstein JM, Hong W. TINYDB: An acquisitional query processing system for sensor networks. ACM Trans. on Database Systems, 2005,30(1):122?173. [doi: 10.1145/1061318.1061322]
    [6] Yao Y, Gehrke J. Query processing in sensor networks. In: Proc. of the ACM CIDR. New York: ACM Press, 2003. 21?32.
    [7] Olston C, Loo BT, Widom J. Adaptive precision setting for cached approximate values. In: Mehrotra S, Sellis T, eds. Proc. of the ACM SIGMOD. New York: ACM Press, 2001. 355?366.
    [8] Silberstein A, Munagala K, Yang J. Energy-Efficient monitoring of extreme values in sensor networks. In: Yu C, Scheuermann P, Chaudhuri S, eds. Proc. of the ACM SIGMOD. New York: ACM Press, 2006. 169?180.
    [9] Silberstein A, Braynard R, Ellis C, Munagala K, Yang J. A sampling-based approach to optimizing top-k queries in sensor networks. In: Liu L, Reuter A, Whang KY, Zhang JJ, eds. Proc. of the IEEE ICDE. Washington: IEEE Computer Society Press, 2006. 68?77.
    [10] Rajagopalan R, Varshney PK. Data aggregation techniques in sensor networks: A survey. Communications Surveys and Tutorials, 2006,8(4):48?63. [doi: 10.1109/COMST.2006.283821]
    [11] Heinzelman WB, Chandrakasan AP, Balakrishnan H. An application-specific protocol architecture for wireless Microsensor networks. IEEE Trans. on Wireless Communications, 2002,1(4):660?670. [doi: 10.1109/TWC.2002.804190]
    [12] Younis O, Fahmy S. HEED: A hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks. IEEE Trans. on Mobile Computing, 2004,3(4):660?669.
    [13] Vaidhyanathan K, Sur S, Narravula S, Sinha P. Data aggregation techniques in sensor networks. Technical Report, The Ohio State University, 2004. ftp://ftp.cse.ohio-state.edu/pub/tech-report/2004/TR60.pdf
    [14] Madden S, Franklin MJ, Hellerstein J, Hong W. TAG: A tiny aggregation service for ad-hoc sensor networks. In: Culler D, Druschel P, eds. Proc. of the USENIX OSDI. New York: ACM Press, 2002. 131?146.
    [15] Intanagonwiwat C, Govindan R, Estrin D. Directed diffusion: A scalable and robust communication paradigm for sensor networks. In: Pickholtz R, Das SK, Caceres R, Garcia-Luna-Aceves JJ, eds. Proc. of the ACM MobiCom. New York: ACM Press, 2000. 56?67.
    [16] Abadi DJ, Madden S, Lindner W. REED: Robust, efficient filtering and event detection in sensor networks. In: Jensen CS, ed. Proc. of the ACM VLDB. New York: ACM Press, 2005. 769?780.
    [17] Akdere M, Cetintemel U, Tatbul N. Plan-Based complex event detection across distributed sources. In: Proc. of the ACM VLDB. New York: ACM Press, 2008. 66?77.
    [18] Yang XY, Lim HB, ?zsu MT, Tan KL. In-Network execution of monitoring queries in sensor networks. In: Zhou LZ, Ling TW, Ooi BC, eds. Proc. of the ACM SIGMOD. New York: ACM Press, 2007. 521?532.
    [19] Hua M, Pei J, Zhang WJ, Lin XM. Ranking queries on uncertain data: A probabilistic threshold approach. In: Lakshmanan LVS, Ng RT, Shasha D, eds. Proc. of the ACM SIGMOD. New York: ACM Press, 2008. 673?686.
    [20] Terzis A, Anandarajah A, Moore K, Wang I. Slip surface localization in wireless sensor networks for landslide prediction. In: Stankovic J, Gibbons P, Wicker S, Paradiso J, eds. Proc. of the ACM IPSN. New York: ACM Press, 2006. 109?116.
    [21] Subramaniam S, Palpanas T, Papadopoulos D, Kalogeraki V, Gunopulos D. Online outlier detection in sensor data using non-parametric models. In: Dayal U, ed. Proc. of the ACM VLDB. New York: ACM Press, 2006. 187?198.
    [22] Madden S, Szewczyk R, Franklin MJ, Culler D. Supporting aggregate queries over ad-hoc wireless sensor networks. In: Martin DC, ed. Proc. of the IEEE Workshop on Mobile Computing Systems and Applications. Washington: IEEE Computer Society Press, 2002. 49?58.
    [23] Zhang H, Shen H, Tan Y. Optimal energy balanced data gathering in wireless sensor networks. In: Mueller F, ed. Proc. of the IEEE IPDPS. Washington: IEEE Computer Society Press, 2007. 1?10.
    [24] Gao J, Guibas L, Milosavljevic N, Hershberger J. Sparse data aggregation in sensor networks. In: Abdelzaher T, Guibas L, Welsh M, eds. Proc. of the ACM IPSN. New York: ACM Press, 2007. 430?439.
    [25] Shrivastava N, Buragohain C, Agrawal D, Suri S. Medians and beyond: New aggregation techniques for sensor networks. In: Stankovic JA, Arora A, Govindan R, eds. Proc. of the ACM SenSys. New York: ACM, 2004. 239?249.
    [26] Deshpande A, Guestrin C, Madden SR. Model-Driven data acquisition in sensor networks. In: Nascimento MA, ?zsu MT, Kossmann D, Miller RJ, Blakeley JA, Schiefer KB, eds. Proc. of the ACM VLDB. New York: ACM Press, 2004. 588?599.
    [27] Huang CF, Tseng YC. The coverage problem in a wireless sensor network. In: Raghavendra CS, Sivalingam KM, Govindan R, Ramanathan P, eds. Proc. of the ACM WSNA. New York: ACM Press, 2003. 115?121.
    [28] So AMC, Ye YY. On solving coverage problems in a wireless sensor network using Voronoi diagrams. In: Deng XT, Ye YY, eds. Proc. of the WINE. Berlin: Springer-Verlag, 2005. 584?593.
    [29] Chraibi Y. Localization in wireless sensor networks [MS. Thesis]. 2005. http://www.ee.kth.se/php/modules/publications/reports/ 2005/2286.pdf
    [30] Levis P, Lee N. TOSSIM: A simulator for Tinyos networks. User’s Manual in TinyOS. 2003. http://www.cs.berkeley.edu/pal/ pubs/nido.pdf
    附中文参考文献: [1] 李建中,李金宝,石胜飞.传感器网络及其数据管理的概念、问题与进展.软件学报,2003,14(10):1717?1727. http://www.jos.org.cn/ 1000-9825/14/1717.htm
    [2] 孙利民,李建中,陈渝,朱红松.无线传感器网络.北京:清华大学出版社,2005.
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

熊蜀光,李建中,陈 雷,王新兵.无线传感器网络上的极值区域查询处理.软件学报,2010,21(8):1920-1935

Copy
Share
Article Metrics
  • Abstract:4879
  • PDF: 6466
  • HTML: 0
  • Cited by: 0
History
  • Received:September 26,2008
  • Revised:July 23,2009
You are the first2044126Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063