Optimized Storage Placement over Large Scale Sensor Networks Lei Xie,Sanglu Lu,Yingchun Cao,and Daoxu Chen State Key Laboratory of Novel Software Technology Nanjing University.Nanjing,China Ixie@nju.edu.cn,sanglu@nju.edu.cn,yccao@nju.edu.cn,cdx@nju.edu.cn ABSTRACT they can process these queries,filter locally stored raw sen- Data storage has become an important issue for energy effi- sor data,and send out query replies to users[2].In this way cient data management over sensor networks.In this paper, a large amount of raw sensor data can be avoided for trans- we investigate into the optimized storage placement prob- mission such that the overall energy cost for data forwarding lem over large scale sensor networks,aiming to achieve min- is greatly reduced.Based on the above understanding,var- imized energy cost.In order to efficiently deal with the ious data-centric storage schemes [3]have been proposed to large scale deployment area with irregular shape,we pro- sufficiently leverage the sensors'local storage capability to pose to utilize the "hop"as the computation unit instead of achieve energy efficiency. the "node",such that the computation complexity can be greatly reduced.We propose methodologies to solve the op- However,on the other side,it has also been demonstrated timization problem respectively in situations for unlimited not energy-efficient to locally store the collected raw sensor number of storages and limited number of storages.The ul- data in all sensor nodes.This will introduce a large amount timate goal of this paper is to give a fundamental guidance of query diffusion cost,since the queries should be broad- of optimized storage placement for large scale sensor net- casted from the sink to each of the storage nodes.We note works.Simulation results confirm the performance of our that by appropriately deploying storage nodes over sensor methodologies. networks,the heavy load of query diffusion and raw sensor data forwarding can be alleviated,through making appro- Keywords priate tradeoffs between the above“pure push”and“pure pull”schemes[3.Therefore,a“push and pull'”based stor- Data Storage,Optimization,Storage Placement,Sensor Net- age scheme is essential to extract information from sensor work,Large Scale network,while achieving the overall energy efficiency 4 In this scheme,some intermediate "storage nodes"are de- 1 INTRODUCTION ployed over the sensor network,other ordinary nodes called Sensor networks in pervasive computing applications,such "forwarding nodes"just send their raw data upward to these as environment monitoring,health caring and target track- storages nodes along the routing tree,and queries are dif- ing,generate a large amount of data.Generally these data fused to these storage nodes to fetch those filtered sensor are collected from sensor nodes over the sensor network and data as query replies.Based on the above scenario,a chal- the end users retrieve them through diffusing specific queries lenging problem appears,that is how to place the storage from the sink into the network [1.Conventionally both raw nodes over the sensor network such that the overall energy sensor data and queries are continuously generated over the efficiency can be achieved. sensor network.Due to the limited battery power in these sensor nodes,it will greatly increase the overall energy cost To deal with this problem,Sheng et al.have proposed op- by simply forwarding all raw sensor data to the sink,more- timized algorithms based on dynamic programming to solve over,this will make sensor nodes around the sink heavily the storage placement problem in the tree based model 5 used and quickly exhausted in energy.We note that cur- However,in some industrial or research applications where rently some specially designed sensor nodes are equipped sensor networks are widely and densely deployed in a large with larger storage capability than normal sensors,thus they scale approach,it is laborious and time-consuming to com- can store a certain amount of raw sensor data in their local pute the optimized storage placement one by one based on storages.Hence when queries are diffused into these nodes the above algorithm.As a matter of fact,suppose the sensor nodes are uniformly distributed,it is not essential to com- pute the exact optimized storage placement due to the large scale deployment.Therefore,novel approaches should be proposed to simplify the computation of storage placement over the large scale sensor network,which is in irregular shape for general cases.In this paper,we investigate into this problem and propose optimized storage placement in the situations respectively with unlimited number of stor- ages and limited number of storages.Due to the large scaleOptimized Storage Placement over Large Scale Sensor Networks Lei Xie, Sanglu Lu, Yingchun Cao, and Daoxu Chen State Key Laboratory of Novel Software Technology Nanjing University, Nanjing, China lxie@nju.edu.cn, sanglu@nju.edu.cn, yccao@nju.edu.cn, cdx@nju.edu.cn ABSTRACT Data storage has become an important issue for energy effi- cient data management over sensor networks. In this paper, we investigate into the optimized storage placement prob￾lem over large scale sensor networks, aiming to achieve min￾imized energy cost. In order to efficiently deal with the large scale deployment area with irregular shape, we pro￾pose to utilize the “hop” as the computation unit instead of the “node”, such that the computation complexity can be greatly reduced. We propose methodologies to solve the op￾timization problem respectively in situations for unlimited number of storages and limited number of storages. The ul￾timate goal of this paper is to give a fundamental guidance of optimized storage placement for large scale sensor net￾works. Simulation results confirm the performance of our methodologies. Keywords Data Storage, Optimization, Storage Placement, Sensor Net￾work, Large Scale 1. INTRODUCTION Sensor networks in pervasive computing applications, such as environment monitoring, health caring and target track￾ing, generate a large amount of data. Generally these data are collected from sensor nodes over the sensor network and the end users retrieve them through diffusing specific queries from the sink into the network [1]. Conventionally both raw sensor data and queries are continuously generated over the sensor network. Due to the limited battery power in these sensor nodes, it will greatly increase the overall energy cost by simply forwarding all raw sensor data to the sink, more￾over, this will make sensor nodes around the sink heavily used and quickly exhausted in energy. We note that cur￾rently some specially designed sensor nodes are equipped with larger storage capability than normal sensors, thus they can store a certain amount of raw sensor data in their local storages. Hence when queries are diffused into these nodes, they can process these queries, filter locally stored raw sen￾sor data, and send out query replies to users[2]. In this way, a large amount of raw sensor data can be avoided for trans￾mission such that the overall energy cost for data forwarding is greatly reduced. Based on the above understanding, var￾ious data-centric storage schemes [3] have been proposed to sufficiently leverage the sensors’ local storage capability to achieve energy efficiency. However, on the other side, it has also been demonstrated not energy-efficient to locally store the collected raw sensor data in all sensor nodes. This will introduce a large amount of query diffusion cost, since the queries should be broad￾casted from the sink to each of the storage nodes. We note that by appropriately deploying storage nodes over sensor networks, the heavy load of query diffusion and raw sensor data forwarding can be alleviated, through making appro￾priate tradeoffs between the above “pure push” and “pure pull” schemes[3]. Therefore, a “push and pull” based stor￾age scheme is essential to extract information from sensor network, while achieving the overall energy efficiency [4]. In this scheme, some intermediate “storage nodes” are de￾ployed over the sensor network, other ordinary nodes called “forwarding nodes” just send their raw data upward to these storages nodes along the routing tree, and queries are dif￾fused to these storage nodes to fetch those filtered sensor data as query replies. Based on the above scenario, a chal￾lenging problem appears, that is how to place the storage nodes over the sensor network such that the overall energy efficiency can be achieved. To deal with this problem, Sheng et al. have proposed op￾timized algorithms based on dynamic programming to solve the storage placement problem in the tree based model [5]. However, in some industrial or research applications where sensor networks are widely and densely deployed in a large scale approach, it is laborious and time-consuming to com￾pute the optimized storage placement one by one based on the above algorithm. As a matter of fact, suppose the sensor nodes are uniformly distributed, it is not essential to com￾pute the exact optimized storage placement due to the large scale deployment. Therefore, novel approaches should be proposed to simplify the computation of storage placement over the large scale sensor network, which is in irregular shape for general cases. In this paper, we investigate into this problem and propose optimized storage placement in the situations respectively with unlimited number of stor￾ages and limited number of storages. Due to the large scale