which is proposed by [13]. Therefore we compare the energy consumption for the two Therefore,when an event E;is discovered inside the sensor approaches,as we know that n=,thus we finally get: network,it first routes the event message towards the ring E。+Eg-E structure,utilizing the centripetal routing,when it hits the ring structure,it will leverage the round-ring routing to store Ei =∫JD2R(2m-1)R-)·fe(z)dd to each of the storage nodes over the ring structure.Similarly, +∫JD≥R(d-2R)·f.(c,y)dzdy when a query Q;is issued inside the sensor network,it first +∫JD<R(2m+1)R:-是-2D(z,)·fe.(c,y)drdw routes the query message towards the ring structure through +∫∫D<(d+2R-4D(x)f(c,)dd the centripetal routing,when it hits the ring structure,it will From the above formula we note that in some situation the leverage the round-ring routing to find the first storage node ring based replication storage scheme may be less energy- it meets,then the reply message will be routed to the query efficient than the original approach,it all depends on the ring node along the former routing trace. size and the event and query distributions.Anyway,the load balance goal is always achieved. C.Performance Analysis 2)Load Balance:As we have learned from Section 5.1,the energy consumption per storage node for original approach is: In this section we will analyze on the energy efficiency and load balance performance for our ring based replication B,=无c,E,ddy (23) storage. fa()(Er+E.).dzdy 1)Energy Efficiency:Based on the routing mechanism And the energy consumption per storage node for ring based described above,we can calculate E,the energy consumption replication storage scheme is: for event storage: B=6fe,E,:会d 2n (24) E,天6IDeg)-Rdrd +oo fa()(E +E).drdy +6乃2mR·2=)fc,0dd (20) Comparing the two energy consumption expressions we learn that when n is large enough,while the event storage Here D(r,y)is the the distance from the event/query position energy cost keeps nearly the same,the event query energy cost (y)to the center of the ring (i,),and we have D(,y)= will be greatly reduced totherefore,the event storage and V(x-i)2 +(y-i)2,then D(,y)-Ril is the energy query load is effectively balanced via the ring structure. consumption for centripetal routing,its value depends on the sensor node's position to the ring,that is whether it is inside or VI.EXPERIMENTAL EVALUATION outside the ring.And is the energy consumption We have implemented a simulator to simulate the event for round-ring routing in average case.Thus we further have: and query distributions over the deployed sensor networks, thus to evaluate the performance of EEBASS.We consider a E。=∫JD2r(D(a,)-R):fe:(z,)ddy network composed of 10000 sensor nodes randomly deployed +Jp≥R2xR:.2n品）·fe,(e,0drd in a 100 x 100 square field,and we randomly generate the +∫JD<R(B:-D(z,)·fe.(e,)drdy event and query distributions.Here we set the average distance +∫JD<R(2mR·22n)fe,(z,y)drdy d=1,and we calculate the length of routing paths as the energy consumption metric. Similarly the energy consumption E for event query is: A.Convergence of Our Approximate Algorithm ED(,)-Ral-2fa()drdy Figure 5(a)shows the iterative convergence of our approx- +06(2mR·六）2f.(a,)dzd 21) imate algorithm.We vary the convergence threshold e from 10-2 to 10-8,testing how many iterative steps in average are necessary to satisfy the specified convergence threshold. And we can further have: We note that as the threshold grows from 10-2 to 10-8, Eg=∫JD≥R,(D(,）-R)·2f(z,)drdy the necessary number of iterative steps grows linearly from 6 to 29,which means our approximate algorithm has fast +∫JD≥2R,2mB:·品)2fa(e,)ddy convergence rate,even in the situation of e=10-8,our +p<R (Ri-D(,)).2fa(,y)dady approximate algorithm only needs 29 steps to reach that merit. +∫JD<R,(2xR·)·2f(c,)dd B.Energy Efficiency of Our Approximate Optimal Solution As we have learned from Section 4,the energy consumption In Figure 5(b),we compare the energy consumption for var- without ring based replication storage is: ious storage placements with our approximate optimal storage placement.To evaluate the energy efficiency,we generate a E=060 D(x,·(fe.(x,y）+2fg(x,)dzdy(22) sample distribution from which we extract 5 representative points with coordinates and weights.And we have:O1(0,0). 978-1-4244-2324-8/08/S25.00©2008EEE. 5 This full text paper,B9dise4vgfE毛rfei98sO6P9件形69s代hlim艳E头6r裙sfl8P”2008 proceedings.which is proposed by [13]. Therefore, when an event Ei is discovered inside the sensor network, it first routes the event message towards the ring structure, utilizing the centripetal routing, when it hits the ring structure, it will leverage the round-ring routing to store Ei to each of the storage nodes over the ring structure. Similarly, when a query Qi is issued inside the sensor network, it first routes the query message towards the ring structure through the centripetal routing, when it hits the ring structure, it will leverage the round-ring routing to find the first storage node it meets, then the reply message will be routed to the query node along the former routing trace. C. Performance Analysis In this section we will analyze on the energy efficiency and load balance performance for our ring based replication storage. 1) Energy Efficiency: Based on the routing mechanism described above, we can calculate Es, the energy consumption for event storage: Es =  X 0  Y 0 |D(x, y) − Ri|dxdy +  X 0  Y 0 (2πRi · 2n−1 2n ) · fei (x, y)dxdy (20) Here D(x, y) is the the distance from the event/query position (x, y) to the center of the ring (xi , yi), and we have D(x, y) = (x − xi)2 + (y − yi)2, then |D(x, y) − Ri| is the energy consumption for centripetal routing, its value depends on the sensor node’s position to the ring, that is whether it is inside or outside the ring. And 2πRi · 2n−1 2n is the energy consumption for round-ring routing in average case. Thus we further have: Es =   D≥Ri (D(x, y) − Ri) · fei (x, y)dxdy +   D≥Ri (2πRi · 2n−1 2n ) · fei (x, y)dxdy +   D<Ri (Ri − D(x, y)) · fei (x, y)dxdy +   D<Ri (2πRi · 2n−1 2n ) · fei (x, y)dxdy Similarly the energy consumption Eq for event query is: Eq =  X 0  Y 0 |D(x, y) − Ri| · 2fqi (x, y)dxdy +  X 0  Y 0 (2πRi · 1 2n ) · 2fqi (x, y)dxdy (21) And we can further have: Eq =   D≥Ri (D(x, y) − Ri) · 2fqi (x, y)dxdy +   D≥Ri (2πRi · 1 2n ) · 2fqi (x, y)dxdy +   D<Ri (Ri − D(x, y)) · 2fqi (x, y)dxdy +   D<Ri (2πRi · 1 2n ) · 2fqi (x, y)dxdy As we have learned from Section 4, the energy consumption without ring based replication storage is: E = X 0 Y 0 D(x, y) · (fei (x, y)+2fqi (x, y))dxdy (22) Therefore we compare the energy consumption for the two approaches, as we know that n = 2πRi d , thus we finally get: Es + Eq − E =   D≥Ri ((2π − 1)Ri − d 2 ) · fei (x, y)dxdy +   D≥Ri (d − 2Ri) · fqi (x, y)dxdy +   D<Ri ((2π + 1)Ri − d 2 − 2D(x, y)) · fei (x, y)dxdy +   D<Ri (d + 2Ri − 4D(x, y)) · fqi (x, y)dxdy From the above formula we note that in some situation the ring based replication storage scheme may be less energy￾efficient than the original approach, it all depends on the ring size and the event and query distributions. Anyway, the load balance goal is always achieved. 2) Load Balance: As we have learned from Section 5.1, the energy consumption per storage node for original approach is: Bi =  X 0  Y 0 fei (x, y) · Er · dxdy +  X 0  Y 0 fqi (x, y) · (Er + Es) · dxdy (23) And the energy consumption per storage node for ring based replication storage scheme is: B i =  X 0  Y 0 fei (x, y) · Er · 2n−1 2n dxdy +  X 0  Y 0 fqi (x, y) · (Er + Es) · 1 2n dxdy (24) Comparing the two energy consumption expressions we learn that when n is large enough, while the event storage energy cost keeps nearly the same, the event query energy cost will be greatly reduced to 1 2n , therefore, the event storage and query load is effectively balanced via the ring structure. VI. EXPERIMENTAL EVALUATION We have implemented a simulator to simulate the event and query distributions over the deployed sensor networks, thus to evaluate the performance of EEBASS. We consider a network composed of 10000 sensor nodes randomly deployed in a 100 × 100 square field, and we randomly generate the event and query distributions. Here we set the average distance d = 1, and we calculate the length of routing paths as the energy consumption metric. A. Convergence of Our Approximate Algorithm Figure 5(a) shows the iterative convergence of our approx￾imate algorithm. We vary the convergence threshold ε from 10−2 to 10−8, testing how many iterative steps in average are necessary to satisfy the specified convergence threshold. We note that as the threshold grows from 10−2 to 10−8, the necessary number of iterative steps grows linearly from 6 to 29, which means our approximate algorithm has fast convergence rate, even in the situation of ε = 10−8, our approximate algorithm only needs 29 steps to reach that merit. B. Energy Efficiency of Our Approximate Optimal Solution In Figure 5(b), we compare the energy consumption for var￾ious storage placements with our approximate optimal storage placement. To evaluate the energy efficiency, we generate a sample distribution from which we extract 5 representative points with coordinates and weights. And we have: O1(0, 0), This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE "GLOBECOM" 2008 proceedings. 978-1-4244-2324-8/08/$25.00 © 2008 IEEE. 5 Authorized licensed use limited to: Nanjing University. Downloaded on July 11,2010 at 07:40:16 UTC from IEEE Xplore. Restrictions apply.