Optimized Storage Placement 12- Random Storage Placement o-Random Storage Placemen 12 08 8 o. 10 04 0.5 04 090 02 n 000204060a10214102022 The Bound of Storage Area Value of reduction rate Value of query rate rq (a)Varying values of storage area bound(b)Varying values of reply reduction rate (c)Varying values of query rate ra Figure 6:Energy cost comparison with unlimited number of storages placement we randomly assign the roles (storage or forward- ing)to each sensor node.We note that as a increases from 1.04 0.1 to 1,the energy cost of random storage placement in- 106 creases from 0.33 to 1.10,and the energy cost of optimized 0.9 0.96 Random Storage Placement (Maximum) storage placement increases from 0.22 to 1.When a =0.1. 0.4 Random Stora ent(Average our optimized solution reduces 33%of the energy cost than An ate Al ic Programming based Algorithm the random storage placement;when a =1,our optimized storage solution can only reduce 9.1%of the energy cost than 0.86 the random placement.The reason is that as the reply re- duction rate increases,the transmission cost of query replies from storage nodes are increased,those storage nodes'capa- 0.74 bility of"in network processing"cannot be sufficiently lever- 0.72 人-t aged to filter enough raw sensor data to achieve the energy 0 0203004050060700 efficiency. The Number of Storages:K In Fig.6(c)we compare the optimized storage placement with the random storage placement in term of the energy Figure 7:Energy cost with varying values of K cost,as query rate ra varies.Note that as rg increases from 0.2 to 2,the energy cost of random storage placement in- creases from 0.25 to 1.2,and the energy cost of the opti- deployment area,we obtain the optimal number of storages mized storage placement increases from 0.125 to 1.When K*700 for the situation with unlimited number of stor- r=0.2,our optimized solution reduces 50%of the energy ages.We note that as the number of storages increases, cost than the random storage placement;when ra =2,our all energy costs decreases except the maximum energy cost optimized storage solution can only reduce 16.7%of the en- for the random storage placement.The dynamic program- ergy cost than the random placement.The reason is that as ming based algorithm always achieves the best performance query rate increases,the query diffusion cost will become a in term of energy cost.When K=50,it can reduce 169 quite large number as compared to the raw sensor data for- energy cost than the average energy cost of random stor- warding cost,thus the storage nodes'local filtering effect to age placement.As K increases to 700,it can further reduce reduce energy cost will be counteracted by the large amount 31%energy cost than the average energy cost of random of query diffusion cost,hence the energy cost continue to in storage placement.The greedy approximate algorithm also crease as query rate increases,and more storage nodes will achieves a good performance in term of energy cost,which be replaced by forwarding nodes in the optimized solution is just next to the dynamic programming based algorithm Moreover,among the random storage placement solutions, 7.2 Effect of the Optimized Placement with Lim- we observe that when K<150,the maximum energy cost ited Number of Storages is contributed by the all forwarding node solution,and as K In Fig.7,we compare various solutions in term of en- increases from 150,the maximum energy cost is contributed ergy cost with varying values of K(K<K*).These so- by the solution which places all storage nodes over the last lutions include the dynamic programming based algorithm, hop,which brings a large amount of query diffusion cost and reply cost. the greedy approximate algorithm and the random storage placement.In the random storage placement we randomly select K nodes as the storage nodes.Among the random 8.CONCLUSION storage placement solutions we respectively calculate the av- In this paper,we investigate into the optimized storage place- erage energy cost and the maximum energy cost for compar- ment problem over large scale sensor networks.We consider ison.Here we set rg 1.2,rd =1.Based on the specified the situation with unlimited number of storages and K lim-0 2 4 6 8 10 0.90 0.92 0.94 0.96 0.98 1.00 1.02 1.04 Energy Cost rate Es/Ef The Bound of Storage Area (a) Varying values of storage area bound 0.0 0.2 0.4 0.6 0.8 1.0 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 1.1 1.2 Energy cost Rate Es/Ef Value of reduction rate Optimized Storage Placement Random Storage Placement (b) Varying values of reply reduction rate α 0.0 0.2 0.4 0.6 0.8 1.0 1.2 1.4 1.6 1.8 2.0 2.2 0.0 0.2 0.4 0.6 0.8 1.0 1.2 Optimized Storage Placement Random Storage Placement Energy cost Rate Es/Ef Value of query rate rq (c) Varying values of query rate rq Figure 6: Energy cost comparison with unlimited number of storages placement we randomly assign the roles (storage or forward￾ing) to each sensor node. We note that as α increases from 0.1 to 1, the energy cost of random storage placement in￾creases from 0.33 to 1.10, and the energy cost of optimized storage placement increases from 0.22 to 1. When α = 0.1, our optimized solution reduces 33% of the energy cost than the random storage placement; when α = 1, our optimized storage solution can only reduce 9.1% of the energy cost than the random placement. The reason is that as the reply re￾duction rate increases, the transmission cost of query replies from storage nodes are increased, those storage nodes’ capa￾bility of “in network processing” cannot be sufficiently lever￾aged to filter enough raw sensor data to achieve the energy efficiency. In Fig.6(c) we compare the optimized storage placement with the random storage placement in term of the energy cost, as query rate rq varies. Note that as rq increases from 0.2 to 2, the energy cost of random storage placement in￾creases from 0.25 to 1.2, and the energy cost of the opti￾mized storage placement increases from 0.125 to 1. When rq = 0.2, our optimized solution reduces 50% of the energy cost than the random storage placement; when rq = 2, our optimized storage solution can only reduce 16.7% of the en￾ergy cost than the random placement. The reason is that as query rate increases, the query diffusion cost will become a quite large number as compared to the raw sensor data for￾warding cost, thus the storage nodes’ local filtering effect to reduce energy cost will be counteracted by the large amount of query diffusion cost, hence the energy cost continue to in￾crease as query rate increases, and more storage nodes will be replaced by forwarding nodes in the optimized solution. 7.2 Effect of the Optimized Placement with Lim￾ited Number of Storages In Fig. 7, we compare various solutions in term of en￾ergy cost with varying values of K(K < K∗ ). These so￾lutions include the dynamic programming based algorithm, the greedy approximate algorithm and the random storage placement. In the random storage placement we randomly select K nodes as the storage nodes. Among the random storage placement solutions we respectively calculate the av￾erage energy cost and the maximum energy cost for compar￾ison. Here we set rq = 1.2, rd = 1. Based on the specified 0 100 200 300 400 500 600 700 800 0.72 0.74 0.76 0.78 0.80 0.82 0.84 0.86 0.88 0.90 0.92 0.94 0.96 0.98 1.00 1.02 1.04 Energy cost Rate Es/Ef The Number of Storages: K Random Storage Placement (Maximum) Random Storage Placement (Average) Greedy Approximate Algorithm Dynamic Programming based Algorithm Figure 7: Energy cost with varying values of K deployment area, we obtain the optimal number of storages K∗ ≈ 700 for the situation with unlimited number of stor￾ages. We note that as the number of storages increases, all energy costs decreases except the maximum energy cost for the random storage placement. The dynamic program￾ming based algorithm always achieves the best performance in term of energy cost. When K = 50,it can reduce 16% energy cost than the average energy cost of random stor￾age placement. As K increases to 700, it can further reduce 31% energy cost than the average energy cost of random storage placement. The greedy approximate algorithm also achieves a good performance in term of energy cost, which is just next to the dynamic programming based algorithm. Moreover, among the random storage placement solutions, we observe that when K < 150, the maximum energy cost is contributed by the all forwarding node solution, and as K increases from 150, the maximum energy cost is contributed by the solution which places all storage nodes over the last hop, which brings a large amount of query diffusion cost and reply cost. 8. CONCLUSION In this paper, we investigate into the optimized storage place￾ment problem over large scale sensor networks. We consider the situation with unlimited number of storages and K lim-