微信服务号

微信订阅号

2025-4-5- 17
Home > Archive>Volume 18, Issue 5, 2007 >1186-1197
PDF HTML XML Export Cite reminder
An Algorithm for Optimizing Multidimensional K-NN Queries in Wireless Sensor Networks
Author:
Affiliation:

  • Article
    • | |
  • Metrics
    • |
  • Reference [26]
    • |
  • Related [20]
    • |
  • Cited by [1]
    • | |
  • Comments
    Abstract:

    This paper presents a filter-based algorithm called PREDICTOR for optimizing multidimensional K-NN queries in WSN. A filter installed at each sensor node is a node value distribution range. It is used to prevent the node from sending the data that belongs to the covering range of the filter, and so the node's energy is saved. The server keeps the historical sample data of all the nodes, and determines filters for them according to the query requirement and the samples. Three optimization strategies are proposed: (1) the method for dynamically adjusting the assignment strategies of the filter covering ranges so that a node with little chance to contribute to the final result is assigned with a larger covering range; (2) the method for sharing the filter among nodes so that the nodes with similar historical data are assigned with the same filter; (3) the method for transmitting filters in a compressed way to reduce the cost of filter updating for different K-NN queries. Evaluation experiment results prove the efficiency of the algorithm PREDICTOR in energy saving. Compared with the naive method, this approach can reduce the transmission volume dramatically.

    Reference
    [1]Mainwaring A,Polastre J,Szewczyk R,Culler D,Anderson J.Wireless sensor networks for habitat monitoring.In:Proc.of the 1st ACM Int'l Workshop on Wireless Sensor Networks and Applications.Atlanta:ACM Press,2002.88-97.
    [2]SMER sensor network advances bioscience discoveries.http://fs.sdsu.edu/kf/news/view/index.php-id=0021
    [3]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
    [4]Cui L,Ju HL,Miao Y.Overview of wireless sensor networks.Journal of Computer Research and Development,2005,42(1):163-174 (In Chinese with English abstract).
    [5]Crossbow.MPR (mote processor radio board) and MIB (mote interface/programming board) user's manual.Crossbow Technology Inc.,2003.http:// www.xbow.com/Support/Support_pdf_files/MPR-MIB_Series_Users_Manual.pdf
    [6]Roussopoulos N,Kelley S,Vincent F.Nearest neighbor queries.In:Carey MJ,Schneider DA,eds.Proc.of the '95 ACM SIGMOD Int'l Conf.on Management of Data.San Jose:ACM Press,1995.71-79.
    [7]Song ZX,Roussopoulos N.K-Nearest neighbor search for moving query point.In:Jensen CS,Schneider M,Seeger B,Tsotras VJ,eds.Proc.of the 7th Int'l Symp.on Spatial and Temporal Databases.Berlin:Springer-Verlag,2001.79-96.
    [8]TAO (tropical atmosphere ocean) project.http://www.pmel.noaa.gov/tao/index.shtml
    [9]Intel Berkeley Research Lab.http://berkeley.intel-research.net/labdata
    [10]Guttman A.R-Trees:A dynamic index structure for spatial searching.In:Yormark B,ed.Proc.of the '84 ACM SIGMOD Int'l Conf.on Management of Data.Boston:ACM Press,1984.47-57.
    [11]Beckmann N,Kriegel HP,Schneider R,Seeger B.The R·-tree:An efficient and robust access method for points and rectangles.In:Garcia-Molina H,Jagadish HV,eds.Proc.of the '90 ACM SIGMOD Int'l Conf.on Management of Data.Atlantic City:ACM Press,1990.322-331.
    [12]Robinson JT.The K-D-B-tree:A search structure for large multidimensional dynamic indexes.In:Edmund Lien Y,ed.Proc.of the '81 ACM SIGMOD Int'l Conf.on Management of Data.Ann Arbor:ACM Press,1981.10-18.
    [13]White DA,Jain R.Similarity indexing with the SS-tree.In:Su SYW,ed.Proc.of the 12th Int'l Conf.on Data Engineering.New Orleans:IEEE Computer Society,1996.516-523.
    [14]Berchtold S,Keim DA,Kriegel H.The X-tree:An index structure for high-dimensional data.In:Vijayaraman TM,Buchmann AP,Mohan C,Sarda NL,eds.Proc.of the 22nd VLDB Conf.Bombay:Morgan Kaufmann Publishers,1996.28-30.
    [15]Arya S,Mount D,Netanyahu NS,Silverman R,Wu AY.An optimal algorithm for approximate nearest neighbor searching in fixed dimensions.Journal of the ACM,1998,45(6):891-923.
    [16]Cui B,Ooi BC,Su J,Tan KL.Contorting high dimensional data for efficient main memory K-NN processing.In:Alon Y,Halevy,et al.,eds.Proc.of the 2003 ACM SIGMOD Int'l Conf.on Management of Data.San Diego:ACM Press,2003.479-490.
    [17]Zhang R,Kalnis P,Ooi BC,Tan KL.Generalized multidimensional data mapping and query processing.ACM Trans.on Database Systems,2005,30(3):661-697.
    [18]Shi QX,Nickerson BG.Decreasing radius k-nearest neighbor search using mapping-based indexing schemes.2006.http://www.cs.unb.ca/tech-reports/reportpage2006.shtml
    [19]Babcock B,Olston C.Distributed top-k monitoring.In:Halevy AY,et al.,eds.Proc.of the 2003 ACM SIGMOD Int'l Conf.on Management of Data.San Diego:ACM Press,2003.28-39.
    [20]Deshpande A,Guestrin C,Madden S,Hellerstein J,Hong W.Model-Driven data acquisition in sensor networks.In:Mario A,et al.,eds.Proc.of the 2004 Int'l Conf.on Very Large Databases.Toronto:Morgan Kaufmann Publishers,2004.588-599.
    [21]Chu D,Deshpande A,Hellerstein JM,Hong W.Approximate data collection in sensor networks using probabilistic models.In:Liu L,Reuter A,et al.,eds.Proc.of the 2006 Int'l Conf.on Data Engineering.Atlanta:IEEE Computer Society,2006.
    [22]Silberstein A,Braynard R,Ellis C,Munagala K.A sampling-based approach to optimizing top-k queries in sensor network.In:Liu L,Reuter A,et al.,eds.Proc.of the 2006 Int'l Conf.on Data Engineering.Atlanta:IEEE Computer Society,2006.
    [23]Wu MJ,Tang XY.Monitoring top-k query in wireless sensor networks.In:Liu L,Reuter A,et al.,eds.Proc.of the 2006 Int'l Conf.on Data Engineering.Atlanta:IEEE Computer Society,2006.
    [24]Silberstein A,Munagala K,Yang J.Energy-Efficient monitoring of extreme values in sensor networks.In:Chaudhuri S,Hristidis V,et al.,eds.Proc.of the 2006 ACM SIGMOD Int'l Conf.on Management of Data.Chicago:ACM Press,2006.169-180.
    [3]李建中,李金宝,石胜飞.传感器网络及其数据管理的概念、问题与进展.软件学报,2003,14(10):1717-1727.http://www.jos.org.cn/ 1000-9825/14/1717.htm
    [4]崔莉,鞠海玲,苗勇.无线传感器网络研究进展.计算机研究与发展,2005,42(1):163-174.
    Comments
    Comments
    分享到微博
    Submit
Get Citation

赵志滨,于戈,李斌阳,姚兰,杨晓春.一种无线传感器网络中的多维K-NN查询优化算法.软件学报,2007,18(5):1186-1197

Copy
Share
Article Metrics
  • Abstract:8332
  • PDF: 7870
  • HTML: 0
  • Cited by: 0
History
  • Received:December 31,2006
  • Revised:December 31,2006
Links:Institute of Software, CASChina Computer FederationCASNSFC
You are the first2033211Visitors
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