deployment,we divide the deployment area into separate over large scale sensor networks,due to the huge computa- partitions and leverage the "hop"as the computation unit tion complexity for large scale deployment instead of the "node",which greatly reduces the computing complexity.By utilizing the characteristics of large scale 3. PROBLEM FORMULATION sensor network,our solution greatly simplifies the computa- Without loss of generality,we consider a data collecting sce- tion complexities. nario in a large-scale sensor network as follows:all sensor nodes are densely and uniformly distributed over a deploy- We aim to minimize the overall energy cost in the data accu- ment area,while the sink is set at some specified position mulation and query by appropriately placing storage nodes within the region in advance.The deployment area is re- over the sensor network.With unlimited number of stor- quired to satisfy the following convex property:for any de- ages,we analyze the optimized storage structure over the ployed sensor node.each point on the straight line segment deployment area,and further provide the optimized parame- that joins the sensor node with the sink also lies within the ters for storage deployment according to the irregular shapes deployment area.The exact shape of the deployment area is of the deployment area.With limited number of storages not restricted,either regular or irregular shape is included. we reduce the problem into an unbounded knapsack prob- We classify these sensor nodes into forwarding nodes and lem.Furthermore,we respectively propose dynamic pro- storage nodes,where storage nodes store sensor data and gramming based algorithm and greedy approximation algo- forwarding nodes simply forward their data to those storage rithm to effectively solve this problem. nodes.For ease of presentation,we can also regard the sink node as a storage node.Raw sensor data collected from The rest of this paper is organized as follows,Section II forwarding nodes are continuously sent upward along the reviews the related work.Section III defines problems for routing tree to the first parent storage node they meet,and storage node placement in the aforementioned scenario.Sec- queries are diffused from the sink to all storage nodes to tion IV and Section V respectively present optimized storage fetch the most recent sensed data,query replies will be sent placement methodologies for unlimited number of storages back from storage nodes to the sink along the routing tree and limited number of storages.Section VI conducts per- structure.Fig.1 depicts the data access model with storage formance analysis.Section VII presents simulation results. nodes.Due to the dense and uniform distribution of sensor Section VIII concludes the paper. nodes,for ease of analysis,we assume to deal with a uniform topology structure for the large-scale sensor network,hence 2.RELATED WORK the network is supposed to have a near-symmetric routing There have been a lot of research works for data-centric tree topology over the deployment area,which implies nodes storage schemes over sensor network,which mainly include at the same hop from the sink have similar subtree topolo- structured storage scheme and unstructured storage scheme gies. Structured storage scheme mainly utilizes a mapping func- tion such as geographic hash function to map event infor- mation to specified geographic points,and leverages routing algorithms like GPSR 6 to route messages to corresponding storage nodes,research works including GHT 6,DIMEN- SIONS [7]and DIM [8]belong to this scheme. Unstruc- tured storage scheme mainly utilizes the "push-pull"scheme to disseminate and gather information,research works in- cluding Double Ruling [9.Comb-Needles 10 belong to this scheme.Fang et.al.[11 propose a hybrid storage scheme to implement the event storage and query.Trigoni et.al. Forwarding Nodes Reply 12 presents a hybrid push and pull scheme for tree based Raw Dat Storage Nedes● structure where queries are injected from the sink.Ahn et.al.[13]conduct fundamental analysis over the scalability Figure 1:Data access model with storage nodes, of these two kinds of data-centric storage schemes. the black nodes denote the storage nodes while the white nodes denote the forwarding nodes. Recent research works focus on the storage placement prob- lem to enhance energy efficiency and load balance.Zhang We define the following parameters for the above scenario: et.al.14 propose a ring based index structure to help re- for data generation,we define rd as data generate rate and sd duce energy consumption of storage schemes.KDDCS [15] as the raw data size;for query diffusion,we use re to denote presents a load-balanced storage scheme for sensor networks query rate and sa to denote query size;for query reply,we based on K-D tree.Sheng et.al.present optimized algo- use a to denote reply reduction rate,for input t,which is rithms based on dynamic programming to solve the storage the size of raw data generated by a set of nodes,function placement problem over fixed tree model 516.moreover f(r)=ox for a E (0,1 returns the size of processed data they propose an approximation algorithm to solve the stor- as query replies. age placement problem over randomized dynamic tree model 17.Their dynamic programming methodology must save a For the large scale deployed sensor network,the objective is large amount of intermediate state parameters,and compute to place storage sensor nodes (and hence forwarding sensor from bottom to top along the tree based routing structure nodes)over the deployment area with irregular shape such While achieving a fair degree of accuracy,their optimized that the overall energy cost is minimized.Then the prob- solutions.however,is not suitable for the storage planning lems to solve are as follows:(1)Given unlimited storagedeployment, we divide the deployment area into separate partitions and leverage the “hop” as the computation unit instead of the “node”, which greatly reduces the computing complexity. By utilizing the characteristics of large scale sensor network, our solution greatly simplifies the computa￾tion complexities. We aim to minimize the overall energy cost in the data accu￾mulation and query by appropriately placing storage nodes over the sensor network. With unlimited number of stor￾ages, we analyze the optimized storage structure over the deployment area, and further provide the optimized parame￾ters for storage deployment according to the irregular shapes of the deployment area. With limited number of storages, we reduce the problem into an unbounded knapsack prob￾lem. Furthermore, we respectively propose dynamic pro￾gramming based algorithm and greedy approximation algo￾rithm to effectively solve this problem. The rest of this paper is organized as follows, Section II reviews the related work. Section III defines problems for storage node placement in the aforementioned scenario. Sec￾tion IV and Section V respectively present optimized storage placement methodologies for unlimited number of storages and limited number of storages. Section VI conducts per￾formance analysis. Section VII presents simulation results. Section VIII concludes the paper. 2. RELATED WORK There have been a lot of research works for data-centric storage schemes over sensor network, which mainly include structured storage scheme and unstructured storage scheme. Structured storage scheme mainly utilizes a mapping func￾tion such as geographic hash function to map event infor￾mation to specified geographic points, and leverages routing algorithms like GPSR [6] to route messages to corresponding storage nodes, research works including GHT [6], DIMEN￾SIONS [7] and DIM [8] belong to this scheme. Unstruc￾tured storage scheme mainly utilizes the “push-pull” scheme to disseminate and gather information, research works in￾cluding Double Ruling [9], Comb-Needles [10] belong to this scheme. Fang et.al. [11] propose a hybrid storage scheme to implement the event storage and query. Trigoni et.al. [12] presents a hybrid push and pull scheme for tree based structure where queries are injected from the sink. Ahn et.al. [13] conduct fundamental analysis over the scalability of these two kinds of data-centric storage schemes. Recent research works focus on the storage placement prob￾lem to enhance energy efficiency and load balance. Zhang et. al. [14] propose a ring based index structure to help re￾duce energy consumption of storage schemes. KDDCS [15] presents a load-balanced storage scheme for sensor networks based on K-D tree. Sheng et. al. present optimized algo￾rithms based on dynamic programming to solve the storage placement problem over fixed tree model [5][16], moreover, they propose an approximation algorithm to solve the stor￾age placement problem over randomized dynamic tree model [17]. Their dynamic programming methodology must save a large amount of intermediate state parameters, and compute from bottom to top along the tree based routing structure. While achieving a fair degree of accuracy, their optimized solutions, however, is not suitable for the storage planning over large scale sensor networks, due to the huge computa￾tion complexity for large scale deployment. 3. PROBLEM FORMULATION Without loss of generality, we consider a data collecting sce￾nario in a large-scale sensor network as follows: all sensor nodes are densely and uniformly distributed over a deploy￾ment area, while the sink is set at some specified position within the region in advance. The deployment area is re￾quired to satisfy the following convex property: for any de￾ployed sensor node, each point on the straight line segment that joins the sensor node with the sink also lies within the deployment area. The exact shape of the deployment area is not restricted, either regular or irregular shape is included. We classify these sensor nodes into forwarding nodes and storage nodes, where storage nodes store sensor data and forwarding nodes simply forward their data to those storage nodes. For ease of presentation, we can also regard the sink node as a storage node. Raw sensor data collected from forwarding nodes are continuously sent upward along the routing tree to the first parent storage node they meet, and queries are diffused from the sink to all storage nodes to fetch the most recent sensed data, query replies will be sent back from storage nodes to the sink along the routing tree structure. Fig.1 depicts the data access model with storage nodes. Due to the dense and uniform distribution of sensor nodes, for ease of analysis, we assume to deal with a uniform topology structure for the large-scale sensor network, hence the network is supposed to have a near-symmetric routing tree topology over the deployment area, which implies nodes at the same hop from the sink have similar subtree topolo￾gies. Figure 1: Data access model with storage nodes, the black nodes denote the storage nodes while the white nodes denote the forwarding nodes. We define the following parameters for the above scenario: for data generation, we define rd as data generate rate and sd as the raw data size; for query diffusion, we use rq to denote query rate and sq to denote query size; for query reply, we use α to denote reply reduction rate, for input x, which is the size of raw data generated by a set of nodes, function f(x) = αx for α ∈ (0, 1] returns the size of processed data as query replies. For the large scale deployed sensor network, the objective is to place storage sensor nodes (and hence forwarding sensor nodes) over the deployment area with irregular shape such that the overall energy cost is minimized. Then the prob￾lems to solve are as follows: (1) Given unlimited storage