EEBASS:Energy-Efficient BAlanced Storage Scheme for Sensor Networks Lei Xie,Lijun Chen,Daoxu Chen,Li Xie State Key Laboratory of Novel Software Technology Nanjing University,Nanjing,China Email:xielei@dislab.nju.edu.cn.chenli.cdx.xieli@nju.edu.cn Abstract-Data-centric storage is an effective and important We organize this paper as follows.Section 2 reviews the technique in sensor networks,however,most data-centric storage related work.And Section 3 defines problems for storage node schemes may not be energy efficient and load balanced due to placement in the aforementioned scenario.In Section 4,we non-uniform event and query distributions.This paper proposes EEBASS,it utilizes an approximation algorithm to solve the present an approximation algorithm for optimal solution to optimal storage placement problem according to the variance minimize the overall energy consumption.In Section 5,we of event and query distributions,aiming to minimize the total illustrate the load balance scheme for storage.In Section 6, energy consumption for data-centric storage scheme.And it we present our simulation results,which confirm the energy further leverages a ring based replication structure to achieve efficiency and load balance effect of our schemes.Finally, the load balance goal.Simulation results show that EEBASS is more energy efficient and balanced than traditional data-centric Section 7 concludes the paper. storage mechanisms in sensor network. II.RELATED WORK I.INTRODUCTION Research works for data-centric storage schemes mainly include structured storage scheme and unstructured storage Many sensor network applications generate a large amount scheme.Structured storage scheme mainly utilizes a mapping of sensor data,these data have to be stored somewhere for function such as geographic hash function to map event future retrieval and data analysis.Great efforts have been information to specified geographic points,and leverages addressed in the energy-efficient data gathering and query routing algorithms like GPSR [2]to route messages to coun- processing techniques in sensor networks,among which data terpart storage nodes,research works including GHT [2] centric storage is a very important technique.In data-centric DIMENTIONS [3]and DIM [4]belong to this scheme. scheme [1][2],data are stored at nodes within the network Unstructured storage scheme mainly utilizes the push-pull by name.Each reading will be hashed to a geographic point, scheme to disseminate and gather information,research works and then be routed to the node nearest to this point according including Double Ruling [5].Comb-Needles [6]belong to this to some protocols,such as the GPSR [2]routing algorithm. scheme.In [7]the authors propose a hybrid storage scheme Thus all data with the same general name are stored at the to implement the event storage and query.In [8]the authors same node. perform a fundamental analysis over the scalability of these In this paper,we consider an application scenario in which two kinds of data-centric storage schemes. sensor network provides data centric-storage scheme to users. Recent research works for data-centric storage scheme focus When some sensor node discovers relevant event Ei,it will on the storage placement problem to enhance energy efficiency forward the event information to specified storage node Si and load balance.In [9]the authors present optimal algorithms inside sensor network,and when user sends query Qi through based on dynamic programming to solve the deterministic a neighbor sensor node,the query Qi will be forwarded to placement problem of storage nodes and in [10]they propose counterpart storage node and query results will be replied.an approximation algorithm to solve the random placement Current data-centric storage schemes such as GHT [2]gen- problem.In [11]the authors propose a ring based index struc- erally distribute the storage nodes in a uniform approach ture to help reduce energy consumption of storage schemes. inside sensor network,leveraging a geographic hash mapping KDDCS [12]presents a load-balanced storage scheme for function.As events and queries may not be uniformly dis- sensor networks based on K-D tree. tributed over the sensor network,which is usually that case,the placement of those storage nodes may not achieve the energy- III.PROBLEM FORMULATION efficient goal to minimize the overall energy consumption of We formulate the problem as follows:assume sensor nodes sensor network.And note that the variance of different event are uniformly deployed over the monitoring area,given the and query workloads may incur load balance problem among prior knowledge of event frequency distribution fe(r,y)for storage nodes,we need to devise a replicated storage structure event Ei and query frequency distribution fa(,y)for query to balance the energy consumption for storage nodes,thus Qi inside sensor network deployment area,our goal is to further extend sensor network's lifetime decide the optimal storage placement set S=[S1,S2,...,S 978-1-4244-2324-8/08/S25.00©2008EEE. This full text paper乐B59 ensed asteiet4vafF毛feY8i98sfyA形79s0Teli7eE型头6rEsl8Py”2008 proceedings.EEBASS: Energy-Efficient BAlanced Storage Scheme for Sensor Networks Lei Xie, Lijun Chen, Daoxu Chen, Li Xie State Key Laboratory of Novel Software Technology Nanjing University, Nanjing, China Email: xielei@dislab.nju.edu.cn, {chenlj,cdx,xieli}@nju.edu.cn Abstract—Data-centric storage is an effective and important technique in sensor networks, however, most data-centric storage schemes may not be energy efficient and load balanced due to non-uniform event and query distributions. This paper proposes EEBASS, it utilizes an approximation algorithm to solve the optimal storage placement problem according to the variance of event and query distributions, aiming to minimize the total energy consumption for data-centric storage scheme. And it further leverages a ring based replication structure to achieve the load balance goal. Simulation results show that EEBASS is more energy efficient and balanced than traditional data-centric storage mechanisms in sensor network. I. INTRODUCTION Many sensor network applications generate a large amount of sensor data, these data have to be stored somewhere for future retrieval and data analysis. Great efforts have been addressed in the energy-efficient data gathering and query processing techniques in sensor networks, among which data centric storage is a very important technique. In data-centric scheme [1][2], data are stored at nodes within the network by name. Each reading will be hashed to a geographic point, and then be routed to the node nearest to this point according to some protocols, such as the GPSR [2] routing algorithm. Thus all data with the same general name are stored at the same node. In this paper, we consider an application scenario in which sensor network provides data centric-storage scheme to users. When some sensor node discovers relevant event Ei, it will forward the event information to specified storage node Si inside sensor network, and when user sends query Qi through a neighbor sensor node, the query Qi will be forwarded to counterpart storage node and query results will be replied. Current data-centric storage schemes such as GHT [2] gen￾erally distribute the storage nodes in a uniform approach inside sensor network, leveraging a geographic hash mapping function. As events and queries may not be uniformly dis￾tributed over the sensor network, which is usually that case, the placement of those storage nodes may not achieve the energy￾efficient goal to minimize the overall energy consumption of sensor network. And note that the variance of different event and query workloads may incur load balance problem among storage nodes, we need to devise a replicated storage structure to balance the energy consumption for storage nodes, thus further extend sensor network’s lifetime. We organize this paper as follows. Section 2 reviews the related work. And Section 3 defines problems for storage node placement in the aforementioned scenario. In Section 4, we present an approximation algorithm for optimal solution to minimize the overall energy consumption. In Section 5, we illustrate the load balance scheme for storage. In Section 6, we present our simulation results, which confirm the energy efficiency and load balance effect of our schemes. Finally, Section 7 concludes the paper. II. RELATED WORK Research works for data-centric storage schemes mainly include structured storage scheme and unstructured storage scheme. Structured storage scheme mainly utilizes a mapping function such as geographic hash function to map event information to specified geographic points, and leverages routing algorithms like GPSR [2] to route messages to coun￾terpart storage nodes, research works including GHT [2], DIMENTIONS [3] and DIM [4] belong to this scheme. Unstructured storage scheme mainly utilizes the push-pull scheme to disseminate and gather information, research works including Double Ruling [5], Comb-Needles [6] belong to this scheme. In [7] the authors propose a hybrid storage scheme to implement the event storage and query. In [8] the authors perform a fundamental analysis over the scalability of these two kinds of data-centric storage schemes. Recent research works for data-centric storage scheme focus on the storage placement problem to enhance energy efficiency and load balance. In [9] the authors present optimal algorithms based on dynamic programming to solve the deterministic placement problem of storage nodes and in [10] they propose an approximation algorithm to solve the random placement problem. In [11] the authors propose a ring based index struc￾ture to help reduce energy consumption of storage schemes. KDDCS [12] presents a load-balanced storage scheme for sensor networks based on K-D tree. III. PROBLEM FORMULATION We formulate the problem as follows: assume sensor nodes are uniformly deployed over the monitoring area, given the prior knowledge of event frequency distribution fei (x, y) for event Ei and query frequency distribution fqi (x, y) for query Qi inside sensor network deployment area, our goal is to decide the optimal storage placement set S = {S1, S2, ..., Sk} This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE "GLOBECOM" 2008 proceedings. 978-1-4244-2324-8/08/$25.00 © 2008 IEEE. 1 Authorized licensed use limited to: Nanjing University. Downloaded on July 11,2010 at 07:40:16 UTC from IEEE Xplore. Restrictions apply