2009 15th International Conference on Parallel and Distributed Systems A Decentralized Storage Scheme for Multi-Dimensional Range Queries over Sensor Networks Lei Xie,Lijun Chen,Daoxu Chen,Li Xie State Key Laboratory of Novel Software Technology Department of Computer Science,Nanjing University,Nanjing,China Email:xielei@dislab.nju.edu.cn,[chenlj.cdx,xieli @nju.edu.cn Abstract-This paper presents the design of a decentralized efficiently handle the event insertions and range query pro- storage scheme to support multi-dimensional range queries over cessing in an optimized approach.Contributions of this paper sensor networks.We build a distributed k-d tree based index are listed as follows: structure over sensor network,so as to efficiently map high dimensional event data to a two-dimensional space of sensors 1.We construct the k-d tree based index structure according while preserving the proximity of events.We propose a dynamic to event and range query distributions at sensor data level programming based methodology to control the granularity of instead of the two-dimensional sensor locations,thus we the index tree in an optimized approach,and an optimized can well utilize data level information to facilitate the event routing scheme for range query processing to achieve best energy efficiency.The simulation results demonstrate the efficiency of the insertion and query processing. design. 2.We reduce the problem of optimal routing for sub-queries to the Euclidean Steiner tree problem,which is NP-hard,and I.INTRODUCTION propose corresponding approximation algorithm to solve it. The rest of the paper is organized as follows.Section II In most sensor network applications,data or events are reviews the related work.Section IlI provides preliminaries continuously collected,forwarded and stored in sink nodes upon which the design theory can be built.The details of for further usage.Recently a Data Centric Storage (DCS) the proposed design methodology are given in Section IV. scheme is proposed to store event data in specific sensor nodes In Section V,we present the multi-dimensional event storage according to the "event type",leveraging the"in-network stor- and query processing mechanism.Section VI presents the age"capability of sensor networks.The "event type"refers to simulation results.Finally,we summarize the paper in Section certain pre-defined constellations of attribute values,however, VII. earlier DCS schemes like GHT [1]conventionally deal with event types with unique attribute and only support "exact II.RELATED WORKS match"point queries.As sensor applications are evolving. Data centric storage schemes [2]mainly utilize a mapping it is mandatory for these event data to be represented by function such as geographic hash function to map event in- several different attributes,such as temperature,humidity, formation to specified geographic points,and leverage routing light,and barometric pressure,which may be referred to as algorithms like GPSR [1]to route messages to corresponding multi-dimensional events.One natural way to query for events storage nodes,these research works include GHT [1].DIMEN- of interest is to use multi-dimensional range queries over SIONs [3]and DIFS [4].GHT is the first work which utilizes these attributes.For example,users may impose queries like a geographic hash table as the mapping function.Based on "List all events that have temperatures between 50.F and 60.F, the primitives in GHT,DIMENSIONs is proposed to support and light levels between 10 and 20".However conventional multi-resolution storage and query processing,which allows DCS schemes are inadequate for managing and processing drill-down search for features within sensor network,while these multi-dimensional events,because processing a query DIFS allows range queries on a single key in addition to over multi-dimensional events is much more complex than other operations.And these above storage schemes are mainly processing a query on single-dimensional events.We need to suitable for processing one-dimensional events. figure out how to efficiently map these high dimensional events The basic problem that this paper addresses-multidimen- to a two-dimensional space of sensors while preserving the sional range queries-is typically solved in database systems proximity of events. using indexing techniques.Among these techniques k-d tree[5] Therefore an efficient,decentralized storage framework is as one of the well-known multi-dimensional binary search essential to facilitate multi-dimensional queries over sensor trees,is proposed to support associative searching works over networks.In this paper we propose a framework which can multi-dimensional data attributes.DIM6]draws its inspiration IEEE 1521-9097/09$26.0002009IEEE 166 Φcomputer DOI10.1109/ICPADS.2009.24 society Authorized licensed use limited to:Nanjing University.Downloaded on July 11,2010 at 07:42:17 UTC from IEEE Xplore.Restrictions apply.A Decentralized Storage Scheme for Multi-Dimensional Range Queries over Sensor Networks Lei Xie, Lijun Chen, Daoxu Chen, Li Xie State Key Laboratory of Novel Software Technology Department of Computer Science, Nanjing University, Nanjing, China Email: xielei@dislab.nju.edu.cn, {chenlj,cdx,xieli}@nju.edu.cn Abstract—This paper presents the design of a decentralized storage scheme to support multi-dimensional range queries over sensor networks. We build a distributed k-d tree based index structure over sensor network, so as to efficiently map high dimensional event data to a two-dimensional space of sensors while preserving the proximity of events. We propose a dynamic programming based methodology to control the granularity of the index tree in an optimized approach, and an optimized routing scheme for range query processing to achieve best energy efficiency. The simulation results demonstrate the efficiency of the design. I. INTRODUCTION In most sensor network applications, data or events are continuously collected, forwarded and stored in sink nodes for further usage. Recently a Data Centric Storage (DCS) scheme is proposed to store event data in specific sensor nodes according to the “event type”, leveraging the “in-network stor￾age” capability of sensor networks. The “event type” refers to certain pre-defined constellations of attribute values, however, earlier DCS schemes like GHT [1] conventionally deal with event types with unique attribute and only support “exact match” point queries. As sensor applications are evolving, it is mandatory for these event data to be represented by several different attributes, such as temperature, humidity, light, and barometric pressure, which may be referred to as multi-dimensional events. One natural way to query for events of interest is to use multi-dimensional range queries over these attributes. For example, users may impose queries like “List all events that have temperatures between 50.F and 60.F, and light levels between 10 and 20”. However conventional DCS schemes are inadequate for managing and processing these multi-dimensional events, because processing a query over multi-dimensional events is much more complex than processing a query on single-dimensional events. We need to figure out how to efficiently map these high dimensional events to a two-dimensional space of sensors while preserving the proximity of events. Therefore an efficient, decentralized storage framework is essential to facilitate multi-dimensional queries over sensor networks. In this paper we propose a framework which can efficiently handle the event insertions and range query pro￾cessing in an optimized approach. Contributions of this paper are listed as follows: 1. We construct the k-d tree based index structure according to event and range query distributions at sensor data level instead of the two-dimensional sensor locations, thus we can well utilize data level information to facilitate the event insertion and query processing. 2. We reduce the problem of optimal routing for sub-queries to the Euclidean Steiner tree problem, which is NP-hard, and propose corresponding approximation algorithm to solve it. The rest of the paper is organized as follows. Section II reviews the related work. Section III provides preliminaries upon which the design theory can be built. The details of the proposed design methodology are given in Section IV. In Section V, we present the multi-dimensional event storage and query processing mechanism. Section VI presents the simulation results. Finally, we summarize the paper in Section VII. II. RELATED WORKS Data centric storage schemes [2] mainly utilize a mapping function such as geographic hash function to map event in￾formation to specified geographic points, and leverage routing algorithms like GPSR [1] to route messages to corresponding storage nodes, these research works include GHT [1], DIMEN￾SIONs [3] and DIFS [4]. GHT is the first work which utilizes a geographic hash table as the mapping function. Based on the primitives in GHT, DIMENSIONs is proposed to support multi-resolution storage and query processing, which allows drill-down search for features within sensor network, while DIFS allows range queries on a single key in addition to other operations. And these above storage schemes are mainly suitable for processing one-dimensional events. The basic problem that this paper addresses - multidimen￾sional range queries - is typically solved in database systems using indexing techniques. Among these techniques k-d tree[5] as one of the well-known multi-dimensional binary search trees, is proposed to support associative searching works over multi-dimensional data attributes. DIM[6] draws its inspiration 2009 15th International Conference on Parallel and Distributed Systems 1521-9097/09 $26.00 © 2009 IEEE DOI 10.1109/ICPADS.2009.24 166 Authorized licensed use limited to: Nanjing University. Downloaded on July 11,2010 at 07:42:17 UTC from IEEE Xplore. Restrictions apply