nodes,how to deploy storage nodes so as to attain the min PROOF.According to conclusion from [5],all storage nodes imum overall energy cost?(2)Given limited storage nodes have storage ancestors over the tree in the optimal solution (number of storage nodes=K),how to deploy storage nodes thus we can deduce the optimized storage placement struc- so as to attain the minimum overall energy cost?Most im- ture is a storage area surrounding the sink node.As the portant of all,the corresponding solutions are required to be network topology in the unit zone is uniform and symmet- scalable to the large scale deployment in computation com- ric,we can prove the storage area is a fan-shaped area by plexity,such that the optimized storage placement can be contradiction.As Fig.3 shows,suppose the storage area in figured out in an efficient approach. a unit zone is in an irregular shape instead of a regular fan shape,as the gray area depicts.Inside the storage area,we 4. UNLIMITED NUMBER OF STORAGES can find a fan-shaped region R with the maximum radius When the storage capability over each sensor node is large then we randomly choose a storage node outside R,we de- enough to hold some raw sensor data for further usage,then note it as node A.Due to the symmetry of the topology any sensor node has the opportunity to become a storage any node with the same hop of node A,e.g.,node B,must node,thus we can suppose to have unlimited number of have the same opportunity to be storage nodes in the op- timal solution.However,node B is set to be a forwarding storages,every sensor node over the routing tree structure can switch to the role of storage node if necessary node in the former hypothesis.Therefore we get a contradic- tion against the former hypothesis,hence the theorem gets proved.☐ 4.1 Optimized Storage Placement Structure Before analyzing on the optimized storage placement,we give the definition of unit zone.A unit zone is a fan-shaped Sink region rooted from the sink within the deployment area,it has a complete tree based topology with the minimum gran- ularity,which we called unit topology.Fig.2 illustrates an example of the unit zones within the gray deployment area. Due to the irregular shape of the deployment area,the max- imum hop varies among the unit zones,but the degree 0 is equivalent for all unit zones.Therefore,the overall deploy- ment area can be divided into a certain number of unit zones and the whole topology is composed of these corresponding unit topologies.The optimal storage placement inside each Forwarding Area unit zone is independent with each other among the unit zones. Figure 3:Proof of Theorem 1,we prove it by con- tradiction. Unit Zone ●、 5 4.2 Calculating Optimized Parameters According to the conclusion from [5]:If ara rd,then the optimal tree with the minimum energy cost contains only forwarding nodes (except for the root).If ara <rd,there erits a storage area for the optimal tree.,we know that if ara 2 rd,the optimized solution includes no storage nodes. Therefore in the remaining of this paper we only consider the are<rd situation.According to Theorem 1,it is proved that the optimized storage structure inside each unit zone is a fan-shaped area around the sink,there must exist an opti- Figure 2:Unit zone mized hop-count kopt for the fan-shaped area,where sensors within the kopt hops are storage nodes,and sensors outside We rely on the following conclusion to obtain the optimized the kopt hops are forwarding nodes.Hence kopt actually de- storage structure,which is first proposed by 5:In the op- notes the boundary of the storage area.Next we will calcu- timal tree,if si is a forwarding node,all of its descendants late the optimized parameter kop for the optimized storage are forwarding nodes as well.If si is a storage node,all area.Without loss of generality,in the rest of this paper its ancestors are storage nodes as well.According to this we utilize the equal sign "="to denote the expected value conclusion,we have Theorem 1. of specified variables. Assume the degree of a unit zone is 0(0<6<),the THEOREM 1.With unlimited number of storages,the op- maximum hop of a specified unit topology is n,the average timized placement structure for storage nodes in the unit hop distance is d,and the network node density is p,thus the zone is a fan-shaped area,where sensors inside the fan- number of sensor nodes for the ith hop is N =0(2i-1)d2p. shaped area are storage nodes,and others are forwarding Now we analyze the energy consumption model.To transmit nodes. s data units,the energy costs of the sender and receiver arenodes, how to deploy storage nodes so as to attain the min￾imum overall energy cost? (2) Given limited storage nodes (number of storage nodes= K), how to deploy storage nodes so as to attain the minimum overall energy cost? Most im￾portant of all, the corresponding solutions are required to be scalable to the large scale deployment in computation com￾plexity, such that the optimized storage placement can be figured out in an efficient approach. 4. UNLIMITED NUMBER OF STORAGES When the storage capability over each sensor node is large enough to hold some raw sensor data for further usage, then any sensor node has the opportunity to become a storage node, thus we can suppose to have unlimited number of storages, every sensor node over the routing tree structure can switch to the role of storage node if necessary. 4.1 Optimized Storage Placement Structure Before analyzing on the optimized storage placement, we give the definition of unit zone. A unit zone is a fan-shaped region rooted from the sink within the deployment area, it has a complete tree based topology with the minimum gran￾ularity, which we called unit topology. Fig.2 illustrates an example of the unit zones within the gray deployment area. Due to the irregular shape of the deployment area, the max￾imum hop varies among the unit zones, but the degree θ is equivalent for all unit zones. Therefore, the overall deploy￾ment area can be divided into a certain number of unit zones and the whole topology is composed of these corresponding unit topologies. The optimal storage placement inside each unit zone is independent with each other among the unit zones. Unit Zone Figure 2: Unit zone We rely on the following conclusion to obtain the optimized storage structure, which is first proposed by [5]: In the op￾timal tree, if si is a forwarding node, all of its descendants are forwarding nodes as well. If si is a storage node, all its ancestors are storage nodes as well. According to this conclusion, we have Theorem 1. Theorem 1. With unlimited number of storages, the op￾timized placement structure for storage nodes in the unit zone is a fan-shaped area, where sensors inside the fan￾shaped area are storage nodes, and others are forwarding nodes. Proof. According to conclusion from [5], all storage nodes have storage ancestors over the tree in the optimal solution, thus we can deduce the optimized storage placement struc￾ture is a storage area surrounding the sink node. As the network topology in the unit zone is uniform and symmet￾ric, we can prove the storage area is a fan-shaped area by contradiction. As Fig.3 shows, suppose the storage area in a unit zone is in an irregular shape instead of a regular fan shape, as the gray area depicts. Inside the storage area, we can find a fan-shaped region R with the maximum radius, then we randomly choose a storage node outside R, we de￾note it as node A. Due to the symmetry of the topology, any node with the same hop of node A, e.g., node B, must have the same opportunity to be storage nodes in the op￾timal solution. However, node B is set to be a forwarding node in the former hypothesis. Therefore we get a contradic￾tion against the former hypothesis, hence the theorem gets proved. Figure 3: Proof of Theorem 1, we prove it by con￾tradiction. 4.2 Calculating Optimized Parameters According to the conclusion from [5]: If αrq ≥ rd, then the optimal tree with the minimum energy cost contains only forwarding nodes (except for the root). If αrq < rd, there exits a storage area for the optimal tree., we know that if αrq ≥ rd, the optimized solution includes no storage nodes. Therefore in the remaining of this paper we only consider the αrq < rd situation. According to Theorem 1, it is proved that the optimized storage structure inside each unit zone is a fan-shaped area around the sink, there must exist an opti￾mized hop-count kopt for the fan-shaped area, where sensors within the kopt hops are storage nodes, and sensors outside the kopt hops are forwarding nodes. Hence kopt actually de￾notes the boundary of the storage area. Next we will calcu￾late the optimized parameter kopt for the optimized storage area. Without loss of generality, in the rest of this paper we utilize the equal sign “=” to denote the expected value of specified variables. Assume the degree of a unit zone is θ(0 < θ < π), the maximum hop of a specified unit topology is n, the average hop distance is d, and the network node density is ρ, thus the number of sensor nodes for the ith hop is Ni = θ(2i−1)d 2 ρ. Now we analyze the energy consumption model. To transmit s data units, the energy costs of the sender and receiver are