7000 6000 5000 4000 3000 2000 1000 10 15 The value of maximum hops Figure 5:Compute coverage area as the maximum hop count increases (d=3m) Figure 4:Compute optimized storage structure with unlimited storage case.We denote these nodes as S.Then as we increase the number of storages from K to K*,the nodes in S will obvi- 5.LIMITED NUMBER OF STORAGES ously switch from storage nodes to forwarding nodes,being In some situations we observe that not all sensor nodes have replaced by other storage nodes within the koptth hop inside each unit zone.During the process,we denote those nodes enough local storages because more storage will come along which switch from forwarding nodes to storage nodes as R. with increased hardware cost,we are only allowed to deploy Based on the above analysis.due to the optimization effect a limited number of specially designed storage nodes for en- ergy efficiency.When dealing with the storage placement of the new storage structure,we obtain the energy reduction AE(R)<AE(S).Due to the increment of K,we know that problem with limited number of storages,it means that the the size of R is larger than the size of S.According to the number of storages,K,is smaller than the optimal num- above inequality,with K limited number of storages,we can ber of storages,K*,for unlimited storages,otherwise it can propose a better optimized solution as compared to the cur- be reduced to the unlimited storage problem.As described rent solution:switch part (or:all)of the storage nodes in S above we only consider the arg<rd situation. to forwarding nodes,and switch equal number of nodes in the R to be new storage nodes,we can rebuild part of the 5.1 Optimized Storage Placement Structure new storage structure and thus achieve better performance. We first give the definition of energy reduction.The energy Hence we get the contradiction with the former assumption, reduction of a node Si means the changed energy cost for S the theorem gets proved. to switch from a forwarding node to a storage node,while the roles of other nodes remain unchanged,we denote it as AE(S).Therefore,when a node Si is selected as a storage As indicated in Theorem 2,it can be inferred that in the node in the optimal solution,it will always satisfy AE(Si)< optimal storage placement with limited number of storages. 0,and its absolute value AE(Si)denotes the amount of the storage node set is a subset of the storage nodes in the energy cost reduction.For ease of representation,in the optimal storage placement with unlimited number of stor- following part we also use the energy reduction AE(S)to ages.Therefore,the solution space for the optimized storage express the changed energy cost for a bunch of nodes S to placement is greatly reduced.Moreover,as the deployment switch from forwarding nodes to storage nodes.Similar to area is divided into a certain number of fan-shaped parti- the strategy proposed in unlimited number of storages,as tions,each fan-shaped partition is fairly regular in shape, Fig.4 illustrates,we divide the deployment area in irregular then nodes in the same hop should have the same opportu- shape into a certain number of fan-shaped partitions.Then nity to be storage nodes or forwarding nodes.Hence we can we compute the optimized storage placement inside each utilize the hop as the computation unit instead of the node partition.The optimized storage placement relies on the then the compute complexity is further reduced.As a matter following conclusion: of fact,even for a large scale sensor network,the maximum hop is very limited.Fig.5 illustrates the coverage area of THEOREM 2.In the optimal storage placement with lim- a conventional sensor network as the maximum hop count ited number of storages,the storage nodes are all within the increases.Here we set the average hop distance d 3m. optimal storage area with unlimited number of storages. We note that as the maximum hop count reaches 15,the coverage area is already near 6500 m2,which is a rather large scale deployment for conventional sensor network ap- PROOF.We prove this theorem by contradiction.Sup- plications.Thus the maximum hop count is smaller than pose in the optimal storage placement with unlimited num- 15 for conventional cases.Therefore,with limited number ber of storages,the essential number of storages is K.As- of storages,it is practical to enumerate all possible storage sume in the optimal solution with K limited number of stor- placement solutions for any unit zone and compare their ages,there exist some storage nodes outside the boundary of performance.The size of solution space is s=2opt,as the optimized storage area calculated in unlimited storage conventionally kopt 15,s is smaller than 215 =32768.Figure 4: Compute optimized storage structure with unlimited storage 5. LIMITED NUMBER OF STORAGES In some situations we observe that not all sensor nodes have enough local storages because more storage will come along with increased hardware cost, we are only allowed to deploy a limited number of specially designed storage nodes for en￾ergy efficiency. When dealing with the storage placement problem with limited number of storages, it means that the number of storages, K, is smaller than the optimal num￾ber of storages, K∗ , for unlimited storages, otherwise it can be reduced to the unlimited storage problem. As described above we only consider the αrq < rd situation. 5.1 Optimized Storage Placement Structure We first give the definition of energy reduction. The energy reduction of a node Si means the changed energy cost for Si to switch from a forwarding node to a storage node, while the roles of other nodes remain unchanged, we denote it as ∆E(Si). Therefore, when a node Si is selected as a storage node in the optimal solution, it will always satisfy ∆E(Si) < 0, and its absolute value |∆E(Si)| denotes the amount of energy cost reduction. For ease of representation, in the following part we also use the energy reduction ∆E(S) to express the changed energy cost for a bunch of nodes S to switch from forwarding nodes to storage nodes. Similar to the strategy proposed in unlimited number of storages, as Fig.4 illustrates, we divide the deployment area in irregular shape into a certain number of fan-shaped partitions. Then we compute the optimized storage placement inside each partition. The optimized storage placement relies on the following conclusion: Theorem 2. In the optimal storage placement with lim￾ited number of storages, the storage nodes are all within the optimal storage area with unlimited number of storages. Proof. We prove this theorem by contradiction. Sup￾pose in the optimal storage placement with unlimited num￾ber of storages, the essential number of storages is K∗ . As￾sume in the optimal solution with K limited number of stor￾ages, there exist some storage nodes outside the boundary of the optimized storage area calculated in unlimited storage 0 5 10 15 0 1000 2000 3000 4000 5000 6000 7000 The value of maximum hops The coverage area (m 2 ) Figure 5: Compute coverage area as the maximum hop count increases (d=3m) case. We denote these nodes as S. Then as we increase the number of storages from K to K∗ , the nodes in S will obvi￾ously switch from storage nodes to forwarding nodes, being replaced by other storage nodes within the koptth hop inside each unit zone. During the process, we denote those nodes which switch from forwarding nodes to storage nodes as R. Based on the above analysis, due to the optimization effect of the new storage structure, we obtain the energy reduction ∆E(R) < ∆E(S). Due to the increment of K, we know that the size of R is larger than the size of S. According to the above inequality, with K limited number of storages, we can propose a better optimized solution as compared to the cur￾rent solution: switch part (or: all) of the storage nodes in S to forwarding nodes, and switch equal number of nodes in the R to be new storage nodes, we can rebuild part of the new storage structure and thus achieve better performance. Hence we get the contradiction with the former assumption, the theorem gets proved. As indicated in Theorem 2, it can be inferred that in the optimal storage placement with limited number of storages, the storage node set is a subset of the storage nodes in the optimal storage placement with unlimited number of stor￾ages. Therefore, the solution space for the optimized storage placement is greatly reduced. Moreover, as the deployment area is divided into a certain number of fan-shaped parti￾tions, each fan-shaped partition is fairly regular in shape, then nodes in the same hop should have the same opportu￾nity to be storage nodes or forwarding nodes. Hence we can utilize the hop as the computation unit instead of the node, then the compute complexity is further reduced. As a matter of fact, even for a large scale sensor network, the maximum hop is very limited. Fig.5 illustrates the coverage area of a conventional sensor network as the maximum hop count increases. Here we set the average hop distance d = 3m. We note that as the maximum hop count reaches 15, the coverage area is already near 6500 m2 , which is a rather large scale deployment for conventional sensor network ap￾plications. Thus the maximum hop count is smaller than 15 for conventional cases. Therefore, with limited number of storages, it is practical to enumerate all possible storage placement solutions for any unit zone and compare their performance. The size of solution space is s = 2kopt , as conventionally kopt ≤ 15, s is smaller than 215 = 32768